人工智能之决策树

1、1. 决策树基本概念2. 信息论基础3. 应用实例及ID3算法4. 决策树总结5. 一些思考目录生活中的决策树1(Decision Tree)1.决策树基本概念 A decision tree is a flowchart-like structure in which each internal node represents a test on an attribute (e.g. whether a coin flip comes up heads or tails), each branch represents the outcome of the test, and each le

2、af node represents a class label (decision taken after computing all attributes). The paths from root to leaf represent classification rules. 决策树是一种类似于流程图的结构，其中每个内部节点代表一个属性上的“测试”（例如，一个硬币的翻转是正面还是反面），每个分支代表测试的结果，每个叶节点代表一个类标签（在计算所有属性之后做出的决定）。从根到叶子的路径表示分类规则。定义1.决策树基本概念生活中的决策树2(Decision Tree)属性测试属性测试决定决定

3、分支 构建决策树的关键问题： 1. 以何种属性进行测试 2. 以何种顺序进行测试 3. 何时做出决定1.决策树基本概念 连接主义者认为，机器学习分为监督学习，无监督学习和强化学习。监督学习就是训练样本带有属性标签。监督学习又可分为“回归”和“分类”问题。 机器学习中的分类技术一般是用一种学习算法确定分类模型，该模型可以很好地拟合类标号和属性集之间的映射关系。 常用的分类算法包括：决策树分类法、逻辑回归分类法、神经网络、支持向量级、朴素贝叶斯分类方法等。机器学习中的决策树（1/2）1.决策树基本概念 在机器学习中，决策树是一个带有标签的监督式学习预测模型，代表的是对象属性与对象值之间的一种映射关

4、系。算法ID3，C4.5和C5.0是基于信息学理论中熵的理论而设计的。 相比大多数分类算法，如 kNN 等，决策树易于理解和实现，使用者无需了解很多背景知识。它能够对数据集合进行分析，挖掘其中蕴含的知识信息。机器学习中的决策树（2/2）1.决策树基本概念 决策树算法采用自上至下递归建树的技术，该算法的产生源于CLS系统，即概念学习系统。决策树算法发展历史(1/2)1.决策树基本概念 1980年，戈登V.卡斯创建CHAID（卡方自动交叉检验） 1979年，J.R. Quinlan 给出ID3算法，在1983年和1986年进行总结和简化 1986年，Schlimmer 和Fisher 于对ID3进

5、行改造，使决策树可以递增式生成，得到ID4算法。 1988年，Utgoff 在ID4基础上提出了ID5学习算法 1993年，Quinlan 进一步发展了ID3算法，改进成C4.5算法。 另一类决策树算法为CART，与C4.5不同的是，CART的决策树由二元逻辑问题生成，每个树节点只有两个分枝，分别包括学习实例的正例与反例决策树算法发展历史(2/2)1.决策树基本概念决策树重要概念1.决策树基本概念 信息的大小可以度量么？ 信息量的大小与概率有关！ 概率越小，信息量越大。出现概率为0，信息量无穷大 概率越大，信息量越小。出现概率为1，信息量为0.信息量2. 信息论基础1948年10月，香农在贝尔

6、系统技术学报上发表论文A Mathematical Theory of Communication，首次建立通讯过程的数学模型，成为现代信息论研究的开端。香农理论的重要特征是熵（entropy）的概念，他证明熵与信息内容的不确定程度有等价关系。信息论2. 信息论基础消息 发生后所含有的信息量，反映了消息 发生前的不确定性：信息量ixix譬如袋子里有红球和黑球，取红球譬如袋子里有红球和黑球，取红球的概率的概率为为0.4，取黑球的概率为，取黑球的概率为0.6。取出红球的信息量取出红球的信息量为为1.322，取出黑球的取出黑球的信息量信息量0.737。2. 信息论基础1( )loglog( )( )

7、iiiI xP xP x 熵 (entropy) 这一词最初来源于热力学。1948年，克劳德爱尔伍德香农将热力学中的熵引入信息论，所以也被称为香农熵 (Shannon entropy)，信息熵 (information entropy)。表示系统的不确定性。 公式：信息熵)(log)()(1log)()(212iniiiixpxpxpExIEXH譬如袋子里有红球和黑球，取红球譬如袋子里有红球和黑球，取红球的概率的概率为为0.4，取黑球的概率为，取黑球的概率为0.6。取出红球的信息量取出红球的信息量为为1.322，取出黑球的取出黑球的信息量信息量0.737。取出。取出1个球的加权个球的加权平均信

8、息量为平均信息量为1.322*0.4+0.737*0.6。思考：什么情况下，熵最大？思考：什么情况下，熵最大？2. 信息论基础 条件熵H(X|Y)表示在已知随机变量Y的条件下随机变量X的不确定性。H(X|Y)，其实质是给定Y情况下X条件概率分布的熵，对Y的数学期望： 条件熵2. 信息论基础21(|) ()|-(|)log(|)njjijijiH X YyE I XYyP xyP xy1(|)()(|)mjjjH X YP yH X Yy条件熵和互信息量2. 信息论基础互信息量，又称信息增益11(; )()(|)( ,)=( ,)log()( ) ()mnijijjiijI X YH XH X

9、YP x yP x yP x P y Y代表性别，取值为男和女；X代表穿着，取值为裙子和裤子。信息增益计算实例男男女女裙子裤子0.40.6注意：注意：H（Y/X）代表已知某人穿着，其性别的不确定性）代表已知某人穿着，其性别的不确定性2. 信息论基础求信息增益：求信息增益：I(X;Y)=H(Y)-H（Y/X）首先计算条件熵2. 信息论基础Step1：计算信息熵Step2：计算给定X条件下，Y条件概率的熵Step3：Y条件概率的熵值对X求数学期望其次计算信息增益2. 信息论基础互信息量，也就是随机变量X对随机变量Y的信息增益 ID3由Ross Quinlan在1

10、986年提出。其核心是根据“最大信息熵增益”原则选择划分当前数据集的最好特征，减少数据的熵(混乱度)。 ID3是一种贪心算法：1）从根结点(root node)开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征。2）由该特征的不同取值建立子节点，再对子节点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止；3）最后得到一个决策树。 每次选取的分割数据的特征都是当前的最佳选择，并按照该特征的所有取值来切分，也就是说如果一个特征有4种取值，数据将被切分4份。ID3算法简介3. 应用实例及ID3算法ID3算法伪代码ID年龄年龄有工作有工作有

11、房子有房子信贷情况信贷情况类别类别(是否是否放贷放贷)1青年否否一般否2青年否否好否3青年是否好是4青年是是一般是5青年否否一般否6中年否否一般否7中年否否好否8中年是是好是9中年否是非常好是10中年否是非常好是11老年否是非常好是12老年否是好是13老年是否好是14老年是否非常好是15老年否否一般否应用实例：是否放贷的决策树对特征进行标注（预处理）对特征进行标注（预处理）年龄：0代表青年，1代表中年，2代表老年；有工作：0代表否，1代表是；有自己的房子：0代表否，1代表是；信贷情况：0代表一般，1代表好，2代表非常好；类别(是否给贷款)：no代表否，yes代表是。3. 应用实例及ID3算法信

12、息熵计算公式采用频率替代概率。数据集D为是否放贷的类别，Ck代表该类别的某一取值的出现频率，如不放贷出现的频次特征A有n种取值，H(Di)代表在A属性的第i个取值下，D的条件概率熵H(D/Ai)信息增益，即特征A对D的信息增益注意：要计算所有特征（属性）A、B、C的信息增益，选择信息增益最大的特征作为节点；然后以该节点的取值为分支，在剩余的特征（属性）中选取信息增益最大的特征作为子节点3. 应用实例及ID3算法 https:/ 三个源文件： ent.py 计算数据集D类别的信息熵 entgain.py 分别计算各个特征对计算数据集D类别的信息增益 id3.py ID3算法Python程序展示3

13、. 应用实例及ID3算法 决策树生成算法递归的产生决策树，直到不能继续下去为止，这样产生的树往往对训练数据的分类很准确，但对未知测试数据的分类缺没有那么精确，即会出现过拟合现象。过拟合产生的原因在于在学习时过多的考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树，解决方法是考虑决策树的复杂度，对已经生成的树进行简化。 剪枝（剪枝（pruning）：）：从已经生成的树上裁掉一些子树或叶节点，并将其根节点或父节点作为新的叶子节点，从而简化分类树模型。 实现方式：实现方式：极小化决策树整体的损失函数或代价函数来实现决策树剪枝3. 应用实例及ID3算法损失函数定义(1/2)Ntk代表t个叶子

14、上的第k种类型个数3. 应用实例及ID3算法损失函数定义(2/2)3. 应用实例及ID3算法 C4.5是Ross Quinlan在1993年在ID3的基础上改进而提出的。ID3采用的信息增益度量存在一个缺点，它一般会优先选择有较多属性值的Feature,因为属性值多的Feature会有相对较大的信息增益?(信息增益反映的给定一个条件以后不确定性减少的程度,必然是分得越细的数据集确定性更高,也就是条件熵越小,信息增益越大)。为了避免这个不足C4.5中是用信息增益比率(gain ratio)来作为选择分支的准则。信息增益比率通过引入一个被称作分裂信息(Split information)的项来惩罚

15、取值较多的Feature。除此之外，C4.5还弥补了ID3中不能处理特征属性值连续的问题。但是，对连续属性值需要扫描排序，会使C4.5性能下降，有兴趣可以参考博客。C4.5算法简介3. 应用实例及ID3算法信息增益比率定义3. 应用实例及ID3算法 1.决策树又叫判定树，是一种基本的分类与回归方法。 2.优点：可读性强，分类速度快，容易转换成if-then分类规则 3.通常分为3个步骤：特征（属性）选择、决策树的生成、决策树的修剪。 4.特征选择即选择分裂属性，又叫属性选择度量，把数据划分成较小的分区。 5.决策树的生成又叫决策树学习或者决策树归纳。 6.决策树生成时采用贪心（即非回溯的、局部

16、最优的）方法，以自顶向下递归的分治方式构造，只考虑局部最优。 7.决策树修剪时递归地从树的叶节点向上回缩，考虑全局最优。 8.决策算法之间的差别包括在创建树时如何选择属性和用于剪枝的机制。 9.决策算法主要为：ID3算法，C4.5算法和CART算法。决策树总结(1/2)4. 决策树总结 10.ID3算法和算法和C4.5算法只有决策树的生成，没有对决策树进行剪枝。算法只有决策树的生成，没有对决策树进行剪枝。CART算法包括决策树的剪枝。算法包括决策树的剪枝。 11.在在进行特征选择时，各个算法采用的选择分裂准则不同进行特征选择时，各个算法采用的选择分裂准则不同:ID3算法使用信息增益准则，选择信

17、息增益最大(熵最小)的特征作为分裂属性。C4.5算法使用信息增益比准则，选择信息增益比最大的特征作为分裂属性。CART算法使用基尼指数准则，选择基尼指数最小的特征作为分裂属性。 12.以以信息增益准则划分训练数据集的特征时，偏向于选择属性取值较多的作为分裂属性；信息增益比信息增益准则划分训练数据集的特征时，偏向于选择属性取值较多的作为分裂属性；信息增益比准则调整了这种偏倚，但它倾向于产生不平衡的划分，其中一个分区比其他分区小得多；基尼指数准则准则调整了这种偏倚，但它倾向于产生不平衡的划分，其中一个分区比其他分区小得多；基尼指数准则也是偏向于多值属性，并且当类的数量很大时会有困难。也是偏向于多值

18、属性，并且当类的数量很大时会有困难。 13.所有所有的属性选择度量都具有某种偏倚。的属性选择度量都具有某种偏倚。 14.决策树决策树归纳时的时间复杂度一般随树的高度指数增加。因此，倾向于产生较浅的树（如多路划分而归纳时的时间复杂度一般随树的高度指数增加。因此，倾向于产生较浅的树（如多路划分而不是二元划分）的度量可能更可取。但是，较浅的树趋向于具有大量树叶和较高的准确率。不是二元划分）的度量可能更可取。但是，较浅的树趋向于具有大量树叶和较高的准确率。 15.信息信息增益的度量标准：熵。熵越大，随机变量的不确定性就越大，分类能力就越低增益的度量标准：熵。熵越大，随机变量的不确定性就越大，分类能力就

19、越低.决策树总结(2/2)4. 决策树总结 10.ID3算法和算法和C4.5算法只有决策树的生成，没有对决策树进行剪枝。算法只有决策树的生成，没有对决策树进行剪枝。CART算法包括决策树的剪枝。算法包括决策树的剪枝。 11.在在进行特征选择时，各个算法采用的选择分裂准则不同进行特征选择时，各个算法采用的选择分裂准则不同:ID3算法使用信息增益准则，选择信息增益最大(熵最小)的特征作为分裂属性。C4.5算法使用信息增益比准则，选择信息增益比最大的特征作为分裂属性。CART算法使用基尼指数准则，选择基尼指数最小的特征作为分裂属性。 12.以以信息增益准则划分训练数据集的特征时，偏向于选择属性取值较多的作为分裂属性；信息增益比信息增益准则划分训练数据集的特征时，偏向于选择属性取值较多的作为分裂属性；信息增益比准则调整了这种偏倚，但它倾向于产生不平衡的划分，其中一个分区比其他分区小得多；基尼指数准则准则调整了这种偏倚，但它倾向于产生不平