决策树及应用.docx

第 5 章 决策树及应用5.1 问题概述各个领域的人工智能实现，常常要涉及这样的问题：从实际问题中提取数据，并从数据中提炼一组数据规则，以支持知识推理实现智能的功能知识规则一般以“原因—结果”形式表示一般地，获取知识规则可以通过样本集，{(𝑥(𝑘)1， 𝑥(𝑘)2， ⋯， 𝑥(𝑘)𝑛， 𝑦(𝑘))│𝑘=1,2,⋯,𝑚}建模实现由于推理结果是有限个，即 的取值是有限的，所以这样的建模属于分类𝑦问题利用神经网络可以实现分类问题建模，但当影响因素变量 的个数较大时，建模后𝑥𝑖的知识规则不易表示，特别地，当默写变量 的取值缺失时，即使神经网络具有容错性，𝑥𝑖也会在一定程度上影响分类结果的不确定性实际应用中，决定分类结果可能只是几个主要影响因素取值，不依赖全部因素变量，因此，知识规则的提取，可以转换为这样的问题：某一分类下哪些变量是主要的影响因素，这些主要影响因素与分类结果的因素规则表示如何获取？决策树就是解决这些问题的方法之一5.2 决策树概述决策树学习算法是一组样本数据集（一个样本数据也可以称为实例）为基础的一种归纳学习算法，它着眼于从一组无次序、无规则的样本数据（概念）中推理出决策树表示形式的分类规则。

假设这里的样本数据应该能够用“属性—结论” 决策时是一个可以自动对数据进行分类的树形结构，是树形结构的知识表示，可以直接转换为分类规则它能被看做基于属性的预测模型，树的根节点是整个数据集空间，每个分结点对应一个分裂问题，它是对某个单一变量的测试，该测试将数据集合空间分割成两个或更多数据块，每个叶结点是带有分类结果的数据分割决策树算法主要针对“以离散型变量作为属性类型进行分类”的学习方法对于连续性变量，必须被离散化才能被学习和分类基于决策树的决策算法的最大的有点就在于它在学习过程中不需要了解很多的背景知识，只从样本数据及提供的信息就能够产生一颗决策树，通过树结点的分叉判别可以使某一分类问题仅与主要的树结点对应的变量属性取值相关，即不需要全部变量取值来判别对应的范类5.2.1 决策树基本算法一颗决策树的内部结点是属性或属性的集合，儿叶结点就是学习划分的类别或结论，内部结点的属性称为测试属性或分裂属性当通过一组样本数据集的学习产生了一颗决策树之后，就可以对一组新的未知数据进行分类使用决策树对数据进行分类的时候，采用自顶向下的递归方法，对决策树内部结点进行属性值的判断比较并根据不同的属性值决定走向哪一条分支，在叶节点处就得到了新数据的类别或结论。

从上面的描述可以看出从根结点到叶结点的一条路径对应着一条合取规则，而整棵决策树对应着一组合取规则图 5.1 简单决策树根据决策树内部结点的各种不同的属性，可以将决策树分为以下几种：（1 ）当决策树的每一个内部结点都只包含一个属性时，称为单变量决策树；当决策树存在包含多个变量的内部结点时，称为多变量决策树2 ）根据测试属性的不同属性值的个数，可能使得每一个内部结点有两个或者是多个分支，如果每一个内部结点只有两个分支则称之为二叉树决策3 ）分类结果可能是两类也可能是多类，二叉树决策的分类结果只能有两类，股也称之为布尔决策树5.2.2 CLS 算法CLS 学习算法是 1966 年有 Hunt 等人提出的它是最早的决策树学习算法后来的许多决策树算法都可以看作是 CLS 学习算法的改进与更新CLS 的算法的思想就是从一个空的决策出发，根据样本数据不断增加新的分支结点，直到产生的决策树能够正确地将样本数据分类为止CLS 算法的步骤如下：B CA1 2 3 4𝑎1 𝑎2𝑏1 𝑏2 𝑐1 𝑐2（1 ）令决策树 T 的初始状态只含有一个树根（X,Q ） ，其中 X 是全体样本数据的集合，Q 是全体测试属性的集合。

2 ）如果 T 中所有叶结点（ ）都有如下状态：或者 中的样本数据都是属于同𝑋'， 𝑄‘ 𝑋'一个类，或者 为空，则停止执行学习算法，学习的结果为 T𝑄‘（3 ）否则，选择一个不具有（2 ）所描述状态的叶节点（ ）.𝑋'， 𝑄‘（4 ）对于 ，按照一定规则选取属性 ，设 被 b 的不同取值分为 m 个不同的子𝑄‘ 𝑏∈𝑄‘ 𝑋'集 ， ，从（ ）伸出 m 个分支，每个分支代表属性 b 的一个不同取值，从𝑋' 1≤𝑖≤𝑚 𝑋'， 𝑄‘而形成 m 个新的叶结点（ ） 𝑋'， 𝑄‘‒|𝑏| ,1≤𝑖≤𝑚（5 ）转（2 ） 在算法步骤（4）中，并没有明确地说明按照怎样的规则来选取测试属性，所以 CLS 有很大的改进空间，而后来很多的决策树学习算法都是采取了各种各样的规则和标准来选取测试属性，所以说后来的各种决策树学习算法都是 CLS 学习算法的改进5.2.3 信息熵Shannon 在 1948 年提出并发展了信息论的观点，主张用数学方法度量和研究信息，提出了以下的一些概念决策树学习算法是以信息熵为基础的，这些概念将有助于理解后续的算法1 ）自信息量：在收到 之前，接收者对信源发出 的不确定性定义为信息符号 的𝑎𝑖 𝑎𝑖 𝑎𝑖自信息量 ，其中 是取值为 的概率。

自信息量反映了接收 的不确I(𝑎𝑖)=‒log2𝑝(𝑎𝑖) 𝑝(𝑎𝑖) 𝑎𝑖 𝑎𝑖定性，自信息量越大，不确定性越大2 ）信息熵：自信息量只能反映符号的不确定性，而信息上可以用来度量整个信源 X整体的不确定性H(𝑋)=[‒𝑝(𝑎1)log2𝑝(𝑎1)]+⋯+[‒𝑝(𝑎𝑛)log2𝑝(𝑎𝑛)](5.1)=‒∑𝑛𝑖=1𝑝(𝑎𝑖)log2𝑝(𝑎𝑖)式中：n 是信源 X 所有可能的符号数； 是可能取到的值； 是取值为 的概率；信息熵𝑎𝑖 𝑝(𝑎𝑖) 𝑎𝑖是各个自信息量的期望3 ）条件熵：如果信源 X 与随机变量 Y 不是相互独立的，接收者收到信息 Y，那么用条件熵 来度量接信者收到随机变量 Y 之后，对随机变量 X 仍然存在的不确定性XH(𝑋|𝑌)对应信源符号 ，Y 对应信源符号 ， 为当 Y 为𝑎𝑖(𝑖=1， 2， ⋯， 𝑛) 𝑏𝑖(𝑖=1， 2， ⋯， s) 𝑝(𝑎𝑖|𝑏𝑗)时 X 为 的概率，则有𝑏𝑗 𝑎𝑖H(𝑋|𝑌)=𝑠∑𝑗=1𝑝(𝑏𝑗)𝐻(𝑋|𝑏𝑗)=𝑠∑𝑗=1𝑝(𝑏𝑗)[‒𝑛∑𝑖=1𝑝(𝑎𝑖|𝑏𝑗)log2𝑝(𝑎𝑖|𝑏𝑗)]=‒ 𝑠∑𝑗=1𝑛∑𝑖=1𝑝(𝑏𝑗) 𝑝(𝑎𝑖|𝑏𝑗)log2𝑝(𝑎𝑖|𝑏𝑗)=‒ 𝑠∑𝑗=1𝑛∑𝑖=1 𝑝(𝑎𝑖， 𝑏𝑗)log2𝑝(𝑎𝑖│𝑏𝑗)即条件熵是各种不同条件下的信息熵期望。

4 ）平均互信息量：用来表示信号 Y 所能提供的关于 X 的信息量的大小，用下式表示，即𝐼(𝑋|𝑌)=𝐻(𝑋)‒𝐻(𝑋|𝑌)5.3 ID3 算法上一节已经提到的 CLS 算法并没有明确地说明按照怎样的规则和标准来确定不同层次的树结点（即测试属性） ，Quinlan 于 1979 年提出的以信息熵的下降速度作为选取测试属性的标准ID3 算法是各种决策树学习算法中最有影响力、使用最广泛的一种决策树学习算法5.3.1 基本思想设样本数据集为 X，目的是要把样本数据集分为 n 类设属于第 i 类的样本数据个数是，X 中总的样本数据个数是 ，则一个样本数据属于第 i 类的概率 此时决策𝐶𝑖 |𝑋| p(𝐶𝑖)=𝐶𝑖|𝑋|树对划分 C 的不确定程度（即信息熵）为H(𝑋,𝐶)=𝐻(𝑋)=‒∑𝑛𝑖=1p(𝐶𝑖)log2p(𝐶𝑖)若选择属性 a（设属性 a 有 m 个不同的取值）进行测试，其不确定程度（即条件熵）为H(𝑋|𝑎)=‒𝑛∑𝑖=1𝑚∑𝑗=1𝑝(𝐶𝑖， 𝑎=𝑎𝑗 )log2𝑝(𝐶𝑖|𝑎=𝑎𝑗 )=‒𝑛∑𝑖=1𝑚∑𝑗=1𝑝(𝑎=𝑎𝑗 )𝑝(𝐶𝑖|𝑎=𝑎𝑗 )log2𝑝(𝐶𝑖|𝑎=𝑎𝑗 ) =𝑚∑𝑗=1𝑝(𝑎=𝑎𝑗 ) 𝑛∑𝑖=1𝑝(𝐶𝑖|𝑎=𝑎𝑗 )log2𝑝(𝐶𝑖|𝑎=𝑎𝑗 )则属性 a 对于分类提供的信息量为𝐼(𝑋， 𝑎)=𝐻(𝑋)‒𝐻(𝑋|𝑎)式中： 表示选择了属性 a 作为分类属性之后信息熵的下降程度，亦即不确定性下降𝐼(𝑋， 𝑎)的程度，所以应该选择时的 最大的属性作为分类的属性，这样得到的决策树的确定𝐼(𝑋， 𝑎)性最大。

可见 ID3 算法继承了 CLS 算法，并且根据信息论选择时的 最大的属性作为分类𝐼(𝑋， 𝑎)属性的测试属性选择标准另外，ID3 算法除了引入信息论作为选择测试属性的标准之外，并且引入窗口的方法进行增量学习ID3 算法的步骤如下：（1 ）选出整个样本数据集 X 的规模为 W 的随机子集 （W 称为窗口规模，子集称为𝑋1窗口） 2 ）以 的值最大，即 的值最小为标准，选取每次的测𝐼(𝑋， 𝑎)=𝐻(𝑋)‒𝐻(𝑋|𝑎) 𝐻(𝑋|𝑎)试属性，形成 当前窗口的决策树3 ）顺序扫描所有样本数据，找出当前的决策树的例外，如果没有例外则结束4 ）组合当前窗口的一些样本数据与某些（3 ）中找到的李哇哦形成新的窗口，转（2 ） 5.3.2 ID3 算法应用实例表 5.1 是有关天气的数据样本集合每一样本有 4 个属性变量：Outlook，Temperature，Humidity 和 Windy样本被分为两类，P 和 N，分别表示正例和反例表 5.1 天气样本数据首先计算信息熵 ，由表 5.1 可知，一共有 24 条记录，其中 P 类的记录和 N 类的记录都H(𝑋)是 12 条，则根据上面介绍的信息熵和条件熵的算法，可以得到信息熵值为H(𝑋)=‒1224log21224‒1224log21224=1如果选取 Outlook 属性作为测试属性，则计算条件熵值 。

有表 5.1 可知，H(𝑋|𝑂𝑢𝑡𝑙𝑜𝑜𝑘)Outlook 属性共有 3 个属性值，分别是 Overcast、Sunny 和 RainOutlook 属性取 Overcast 属性值的记录共有 9 条，其中 P 类的记录和 N 类的记录分别是 4条和 5 条，因此有 Overcast 引起的熵值为 ‒924(49log249+59log259)而 Outlook 属性取 Sunny 属性值的记录共有 7 条，其中 P 类的记录和 N 类的记录分别是 7条和 0 条，因此有 Sunny 引起的熵值为 ‒724(77log277)同理，Outlook 属性取 Rain 属性值的记录共有 8 条，其中 P 类的记录和 N 类的记录分别是1 条和 7 条，因此有 Rain 引起的熵值为 ‒824(18log218+78log278)因此条件熵值 应为上述三个式子之和，得到H(𝑋|𝑂𝑢𝑡𝑙𝑜𝑜𝑘)H(𝑋|𝑂𝑢𝑡𝑙𝑜𝑜𝑘)=‒924(49log249+59log259)‒724(77log277) ‒824(18log218+78log278)=0.5528仿照上面条件熵值 的计算方法，可以得到，如果选取 Temperature 属性为测H(𝑋|𝑂𝑢𝑡𝑙𝑜𝑜𝑘)试属性，则条件熵值为H(𝑋|Temperature)=‒824(48log248+48log248)‒1124(411log2411+711log2711)‒524(45log245+15log215)=0.9172如果选取 Humidity 属性为测试属性，则条件熵值为H(𝑋|𝐻𝑢�。