柚子快报激活码778899分享：数据分类分析--决策树算法
一、基本介绍
决策树是一种类似于流程图的树结构，其中每个内部节点表示在一个属性上的测试，每个分支代表该测试的一个输出，而每个叶子节点（终端节点）存放一个分类结果。 上图是一个决策时的示例。 当决策树构建好之后，对检验记录进行分类就很容易，从树的根节点开始，将测试条件用于检验记录，沿着树的分支达到叶子节点，得到分类结果。
二、决策树构建
原则上讲，对于给定的属性集，可以构造的决策树很多，所有如何在合理的时间内构造出具有一定准确率的决策树？通常都采用贪心算法，即在选择属性来划分数据时，采用一系列局部最优决策来构建决策树。 决策树构建过程必须要考虑两个问题 （1）选择哪一个属性来划分数据？即如何度量该属性对于划分之后的数据集的影响。 （2）停止划分的条件。 同时还要考虑属性的不同情况。
1.属性选择度量方法：
ID3/C4.5算法选择信息增益作为度量方法：原始的算法只适用于标称属性，改进后，可以在连续属性上使用。 CART算法选择Gini指数作为度量方法：原始的算法只适用于连续属性，改进后，可以在标称属性上使用。 信息熵：熵的定义如下： 如果一件事情越确定，发生概率越大，信息熵越低。如果一件事情越不确定，发生概率小，信息熵越高。 整个信息空间的期望信息熵： 决策树算法ID3使用的属性度量是信息增益 信息增益定义为如下：
当类别标签有m个不同的值时，所以定义m个不同的类Ci（i = 1，2，…，m），D为数据集，设Ci,d是D中Ci类的元组的集合，|D|，|Ci,d|分别是D和Ci,d中元组的个数，则整个数据集D空间下的期望信息熵为 其中Pi = |Ci,d| / |D|，代表D中不同类别的概率。Info代表识别D中元组的类标号所需要的平均信息量，又称为D的信息熵。
假设用属性A的不同取值将D划分为D1，D2，…，Dv。 其中对于任意一个Dj，它的A属性值都为Aj，对于属性A划分之后的空间，对应的期望信息熵 其中：
其中，|Dj|代表Dj元组的个数（既是属性A的值等于Aj的元组个数），|D|代表按照属性A划分的分支数。 Info（Dj）表示的是当属性A = Aj时，空间的期望信息熵。 我的理解如下： 整个数据集空间按照A的取值不同（Aj）被分为不同的Dj空间，对于每一个Dj空间，也有类别标签不同的情况。 所以当数据集空间D被划分之后，计算空间的期望信息熵分成两步，第一步针对每一个子空间Dj，计算Info（Dj），第二步根据每个子空间Dj的概率，求整个空间的期望。
所以信息增益代表着原来的信息熵与新的信息熵之间的差。 ID3算法会选择信息增益最大的属性作为划分属性，即是选择的划分属性A会使得划分之后的空间，熵值最小，也就是最稳定。
ID3算法的缺点： （1）ID3算法会倾向于选择属性取值较多的属性，因为当属性取值较多时，划分之后的信息熵较小，对应的信息增益更大。 （2）ID3算法只能处理离散属性。 针对缺点1，C4.5算法做出了以下改进： 选择具有最大信息增益率的属性作为分裂属性， 增益率的公式如下： 其中，Gain（A）与ID3算法的定义相同， 分裂信息SplitInfo（A）定义为： 针对缺点2： 将A的值递增排序，每对相邻值的中点被看做可能的分裂点，这样给定A的V个值，则需要计算V-1个可能的划分
对于A的每个可能分裂点，计算Info（D）,其中分区个数为2，A具有最小期望信息需求的点选做A的分裂点。
CART算法选择Gini指数作为度量方法 Gini（T）定义如下： 也可以看成在计算不纯度，其中Pi代表类别标签i的概率。 如果通过属性A将数据集划分成了大小分别为N1和N2的两个子集T1，T2。那么划分之后的GIni定义为： 选择具有最小的属性作为划分属性。 即是选择 最大的属性作为划分属性。
2.计算实例
题目： 使用ID3算法构建决策树 计算Infor（D）以及每个属性对应的信息熵， 然后选择信息增益最大的属性作为分裂属性。 第一个属性选择”类型”作为分裂属性，决策树如下： 然后对于‘类型‘节点的左子树，当类型 == ‘浪漫’时，数据如下： 再次计算信息增益 选择题材作为分裂属性，决策树如下： 对于‘题材‘节点的右子树，当类型 == ‘浪漫’ and 题材 == ‘校园’时，表格如下： 再次计算信息增益 选择语言做为分裂属性，其决策树如下： 然后对于‘类型‘节点的右子树，当类型 == ‘动作’时，图表变成如下： 由于选择题材和语言的信息增益相等，并且同时为最大，所以选择任意一个做为分裂属性都可以，我选择题材做为分裂属性。其决策树如下： 对于‘题材’节点的右子树，当类型 =‘动作’ and 题材= ‘校园’时，表格如下： 选择语言做为分裂属性，其决策树如下：
柚子快报激活码778899分享：数据分类分析--决策树算法
发表评论