
一、决策树分类算法概述
决策树算法是从数据的属性(或者特征)出发,以属性作为基础,划分不同的类。例如对于如下数据集
(数据集)
其中,第一列和第二列为属性(特征),最后一列为类别标签,1表示是,0表示否。决策树算法的思想是基于属性对数据分类,对于以上的数据我们可以得到以下的决策树模型
(决策树模型)
先是根据第一个属性将一部份数据区分开,再根据第二个属性将剩余的区分开。
实现决策树的算法有很多种,有ID3、C4.5和CART等算法。下面我们介绍ID3算法。
二、ID3算法的概述
ID3算法是由Quinlan首先提出的,该算法是以信息论为基础,以信息熵和信息增益为衡量标准,从而实现对数据的归纳分类。
首先,ID3算法需要解决的问题是如何选择特征作为划分数据集的标准。在ID3算法中,选择信息增益最大的属性作为当前的特征对数据集分类。信息增益的概念将在下面介绍,通过不断的选择特征对数据集不断划分;
其次,ID3算法需要解决的问题是如何判断划分的结束。分为两种情况,第一种为划分出来的类属于同一个类,如上图中的最左端的“非鱼类”,即为数据集中的第5行和第6行数据;最右边的“鱼类”,即为数据集中的第2行和第3行数据。第二种为已经没有属性可供再分了。此时就结束了。
通过迭代的方式,我们就可以得到这样的决策树模型。
(ID3算法基本流程)
三、划分数据的依据
ID3算法是以信息熵和信息增益作为衡量标准的分类算法。
1、信息熵(Entropy)
熵的概念主要是指信息的混乱程度,变量的不确定性越大,熵的值也就越大,熵的公式可以表示为:
其中为类别在样本s中出现的概率。
2、信息增益(Information gain)
信息增益指的是划分前后熵的变化,可以用下面的公式表示:
其中,a表示样本的属性,是属性所有的取值集合。v是a的其中一个属性值,sv是s中a的值为v的样例集合。
四、实验仿真
1、数据预处理
我们以下面的数据为例,来实现ID3算法:
我们首先需要对数据处理,例如age属性,我们用0表示youth,1表示middle_aged,2表示senior等等。
(将表格数据化)
2、实验结果
(原始的数据)
(划分1)
(划分2)
(划分3)
(最终的决策树)
MATLAB代码
主程序
[plain] view plain copy 在CODE上查看代码片派生到我的代码片
%% Decision Tree
% ID3
%导入数据
%data = [1,1,1;1,1,1;1,0,0;0,1,0;0,1,0];
data = [0,2,0,0,0;
0,2,0,1,0;
1,2,0,0,1;
2,1,0,0,1;
2,0,1,0,1;
2,0,1,1,0;
1,0,1,1,1;
0,1,0,0,0;
0,0,1,0,1;
2,1,1,0,1;
0,1,1,1,1;
1,1,0,1,1;
1,2,1,0,1;
2,1,0,1,0];
% 生成决策树
createTree(data);
生成决策树
[plain] view plain copy 在CODE上查看代码片派生到我的代码片
function [ output_args ] = createTree( data )
[m,n] = size(data);
disp('original data:');
disp(data);
classList = data(:,n);
classOne = 1;%记录第一个类的个数
for i = 2:m
if classList(i,:) == classList(1,:)
classOne = classOne+1;
end
end
% 类别全相同
if classOne == m
disp('final data: ');
disp(data);
return;
end
% 特征全部用完
if n == 1
disp('final data: ');
disp(data);
return;
end
bestFeat = chooseBestFeature(data);
disp(['bestFeat: ', num2str(bestFeat)]);
featValues = unique(data(:,bestFeat));
numOfFeatValue = length(featValues);
for i = 1:numOfFeatValue
createTree(splitData(data, bestFeat, featValues(i,:)));
disp('-------------------------');
end
end
选择信息增益最大的特征
[plain] view plain copy 在CODE上查看代码片派生到我的代码片
%% 选择信息增益最大的特征
function [ bestFeature ] = chooseBestFeature( data )
[m,n] = size(data);% 得到数据集的大小
% 统计特征的个数
numOfFeatures = n-1;%最后一列是类别
% 原始的熵
baseEntropy = calEntropy(data);
bestInfoGain = 0;%初始化信息增益
bestFeature = 0;% 初始化最佳的特征位
% 挑选最佳的特征位
for j = 1:numOfFeatures
featureTemp = unique(data(:,j));
numF = length(featureTemp);%属性的个数
newEntropy = 0;%划分之后的熵
for i = 1:numF
subSet = splitData(data, j, featureTemp(i,:));
[m_1, n_1] = size(subSet);
prob = m_1./m;
newEntropy = newEntropy + prob * calEntropy(subSet);
end
%计算增益
infoGain = baseEntropy - newEntropy;
if infoGain > bestInfoGain
bestInfoGain = infoGain;
bestFeature = j;
end
end
end
计算熵
[plain] view plain copy 在CODE上查看代码片派生到我的代码片
function [ entropy ] = calEntropy( data )
[m,n] = size(data);
% 得到类别的项
label = data(:,n);
% 处理完的label
label_deal = unique(label);
numLabel = length(label_deal);
prob = zeros(numLabel,2);
% 统计标签
for i = 1:numLabel
prob(i,1) = label_deal(i,:);
for j = 1:m
if label(j,:) == label_deal(i,:)
prob(i,2) = prob(i,2)+1;
end
end
end
% 计算熵
prob(:,2) = prob(:,2)./m;
entropy = 0;
for i = 1:numLabel
entropy = entropy - prob(i,2) * log2(prob(i,2));
end
end
划分数据
[plain] view plain copy 在CODE上查看代码片派生到我的代码片
function [ subSet ] = splitData( data, axis, value )
[m,n] = size(data);%得到待划分数据的大小
subSet = data;
subSet(:,axis) = [];
k = 0;
for i = 1:m
if data(i,axis) ~= value
subSet(i-k,:) = [];
k = k+1;
end
end
end
数据分析咨询请扫描二维码
若不方便扫码,搜微信号:CDAshujufenxi
尊敬的考生: 您好! 我们诚挚通知您,CDA Level I和 Level II考试大纲将于 2025年7月25日 实施重大更新。 此次更新旨在确保认 ...
2025-07-10BI 大数据分析师:连接数据与业务的价值转化者 在大数据与商业智能(Business Intelligence,简称 BI)深度融合的时代,BI ...
2025-07-10SQL 在预测分析中的应用:从数据查询到趋势预判 在数据驱动决策的时代,预测分析作为挖掘数据潜在价值的核心手段,正被广泛 ...
2025-07-10数据查询结束后:分析师的收尾工作与价值深化 在数据分析的全流程中,“query end”(查询结束)并非工作的终点,而是将数 ...
2025-07-10CDA 数据分析师考试:从报考到取证的全攻略 在数字经济蓬勃发展的今天,数据分析师已成为各行业争抢的核心人才,而 CDA(Certi ...
2025-07-09【CDA干货】单样本趋势性检验:捕捉数据背后的时间轨迹 在数据分析的版图中,单样本趋势性检验如同一位耐心的侦探,专注于从单 ...
2025-07-09year_month数据类型:时间维度的精准切片 在数据的世界里,时间是最不可或缺的维度之一,而year_month数据类型就像一把精准 ...
2025-07-09CDA 备考干货:Python 在数据分析中的核心应用与实战技巧 在 CDA 数据分析师认证考试中,Python 作为数据处理与分析的核心 ...
2025-07-08SPSS 中的 Mann-Kendall 检验:数据趋势与突变分析的有力工具 在数据分析的广袤领域中,准确捕捉数据的趋势变化以及识别 ...
2025-07-08备战 CDA 数据分析师考试:需要多久?如何规划? CDA(Certified Data Analyst)数据分析师认证作为国内权威的数据分析能力认证 ...
2025-07-08LSTM 输出不确定的成因、影响与应对策略 长短期记忆网络(LSTM)作为循环神经网络(RNN)的一种变体,凭借独特的门控机制,在 ...
2025-07-07统计学方法在市场调研数据中的深度应用 市场调研是企业洞察市场动态、了解消费者需求的重要途径,而统计学方法则是市场调研数 ...
2025-07-07CDA数据分析师证书考试全攻略 在数字化浪潮席卷全球的当下,数据已成为企业决策、行业发展的核心驱动力,数据分析师也因此成为 ...
2025-07-07剖析 CDA 数据分析师考试题型:解锁高效备考与答题策略 CDA(Certified Data Analyst)数据分析师考试作为衡量数据专业能力的 ...
2025-07-04SQL Server 字符串截取转日期:解锁数据处理的关键技能 在数据处理与分析工作中,数据格式的规范性是保证后续分析准确性的基础 ...
2025-07-04CDA 数据分析师视角:从数据迷雾中探寻商业真相 在数字化浪潮席卷全球的今天,数据已成为企业决策的核心驱动力,CDA(Certifie ...
2025-07-04CDA 数据分析师:开启数据职业发展新征程 在数据成为核心生产要素的今天,数据分析师的职业价值愈发凸显。CDA(Certified D ...
2025-07-03从招聘要求看数据分析师的能力素养与职业发展 在数字化浪潮席卷全球的当下,数据已成为企业的核心资产,数据分析师岗位也随 ...
2025-07-03Power BI 中如何控制过滤器选择项目数并在超限时报错 引言 在使用 Power BI 进行数据可视化和分析的过程中,对过滤器的有 ...
2025-07-03把握 CDA 考试时间,开启数据分析职业之路 在数字化转型的时代浪潮下,数据已成为企业决策的核心驱动力。CDA(Certified Da ...
2025-07-02