人工智能之决策树

1.决策树基本概念2.信息论基础3.应用实例及ID3算法4.决策树总结5.一些思考目录生活中的决策树1(DecisionTree)1.决策树基本概念Adecisiontreeisaflowchart-likestructureinwhicheachinternalnoderepresentsatestonanattribute(e.g.whetheracoinflipcomesupheadsortails),eachbranchrepresentstheoutcomeofthetest,andeachleafnoderepresentsaclasslabel(decisiontakenaftercomputingallattributes).Thepathsfromroottoleafrepresentclassificationrules.决策树是一种类似于流程图的结构，其中每个内部节点代表一个属性上的“测试”（例如，一个硬币的翻转是正面还是反面），每个分支代表测试的结果，每个叶节点代表一个类标签（在计算所有属性之后做出的决定）。从根到叶子的路径表示分类规则。定义1.决策树基本概念生活中的决策树2(DecisionTree)属性测试属性测试决定决定分支构建决策树的关键问题：1.以何种属性进行测试2.以何种顺序进行测试3.何时做出决定1.决策树基本概念连接主义者认为，机器学习分为监督学习，无监督学习和强化学习。监督学习就是训练样本带有属性标签。监督学习又可分为“回归”和“分类”问题。机器学习中的分类技术一般是用一种学习算法确定分类模型，该模型可以很好地拟合类标号和属性集之间的映射关系。常用的分类算法包括：决策树分类法、逻辑回归分类法、神经网络、支持向量级、朴素贝叶斯分类方法等。机器学习中的决策树（1/2）1.决策树基本概念在机器学习中，决策树是一个带有标签的监督式学习预测模型，代表的是对象属性与对象值之间的一种映射关系。算法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进行改造，使决策树可以递增式生成，得到ID4算法。1988年，Utgoff在ID4基础上提出了ID5学习算法1993年，Quinlan进一步发展了ID3算法，改进成C4.5算法。另一类决策树算法为CART，与C4.5不同的是，CART的决策树由二元逻辑问题生成，每个树节点只有两个分枝，分别包括学习实例的正例与反例决策树算法发展历史(2/2)1.决策树基本概念决策树重要概念1.决策树基本概念信息的大小可以度量么？信息量的大小与概率有关！概率越小，信息量越大。出现概率为0，信息量无穷大概率越大，信息量越小。出现概率为1，信息量为0.信息量2.信息论基础1948年10月，香农在《贝尔系统技术学报》上发表论文《AMathematicalTheoryofCommunication》，首次建立通讯过程的数学模型，成为现代信息论研究的开端。香农理论的重要特征是熵（entropy）的概念，他证明熵与信息内容的不确定程度有等价关系。信息论2.信息论基础消息发生后所含有的信息量，反映了消息发生前的不确定性：信息量ixix譬如袋子里有红球和黑球，取红球的概率为0.4，取黑球的概率为0.6。取出红球的信息量为1.322，取出黑球的信息量0.737。2.信息论基础1()loglog()()iiiIxPxPx熵(entropy)这一词最初来源于热力学。1948年，克劳德·爱尔伍德·香农将热力学中的熵引入信息论，所以也被称为香农熵(Shannonentropy)，信息熵(informationentropy)。表示系统的不确定性。公式：信息熵)(log)(])(1[log)]([)(212iniiiixpxpxpExIEXH譬如袋子里有红球和黑球，取红球的概率为0.4，取黑球的概率为0.6。取出红球的信息量为1.322，取出黑球的信息量0.737。取出1个球的加权平均信息量为1.322*0.4+0.737*0.6。思考：什么情况下，熵最大？2.信息论基础条件熵H(X|Y)表示在已知随机变量Y的条件下随机变量X的不确定性。H(X|Y)，其实质是给定Y情况下X条件概率分布的熵，对Y的数学期望：条件熵2.信息论基础21(|)[()|]-(|)log(|)njjijijiHXYyEIXYyPxyPxy1(|)()(|)mjjjHXYPyHXYy条件熵和互信息量2.信息论基础互信息量，又称信息增益11(;)()(|)(,)=(,)log()()()mnijijjiijIXYHXHXYPxyPxyPxPyY代表性别，取值为男和女；X代表穿着，取值为裙子和裤子。信息增益计算实例男女裙子0.20.50.7裤子0.20.10.30.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由RossQuinlan在1986年提出。其核心是根据“最大信息熵增益”原则选择划分当前数据集的最好特征，减少数据的熵(混乱度)。ID3是一种贪心算法：1）从根结点(rootnode)开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征。2）由该特征的不同取值建立子节点，再对子节点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止；3）最后得到一个决策树。每次选取的分割数据的特征都是当前的最佳选择，并按照该特征的所有取值来切分，也就是说如果一个特征有4种取值，数据将被切分4份。ID3算法简介3.应用实例及ID3算法ID3算法伪代码ID3(Examples,Target_attributes,Attributes)Examplesarethetrainingexamples.Target_attributeistheattributewhosevalueistobepredictedbythetree.Attributesisalistofotherattributesthatmaybetestedbythelearneddecisiontree.ReturnsadecisiontreethatcorrectlyclassifiesthegivenExamples.CreateaRootnodeforthetreeIfallExamplesarepositive,Returnthesingle‐nodetreeRoot,withlabel=+IfallExamplesarenegative,Returnthesingle‐nodetreeRoot,withlabel=‐IfAttributesisempty,Returnthesingle‐nodetreeRoot,withlabel=mostcommonvalueofTarget_attributeinExamplesOtherwiseBeginA←theattributefromAttributesthatbestclassifiesExamplesThedecisionattributeforRoot←AForeachpossiblevalue,vi,ofAAddanewtreebranchbelowRoot,correspondingtothetestA=viLetExamplesvibethesubsetofExamplesthathavevalueviforAIfExamplesviisemptyThenbelowthisnewbranchaddaleafnodewithlabel=mostcommonvalueofTarget_attributeinExamplesElsebelowthisnewbranchaddthesubtreeID3(Examplesvi,Target_attribute,Attributes‐{A})EndReturnID年龄有工作有房子信贷情况类别(是否放贷)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算法信息熵计算公式采用频率替代概率。数据集D为是否放贷的类别，Ck代表该类别的某一取值的出现频率，如不放贷出现的频次特征A有n种取值，H(Di)代表在A属性的第i个取值下，D的条件概率熵H(D/Ai)信息增益，即特征A对D的信息增益注意：要计算所有特征（属性）A、B、C…的信息增益，选择信息增益最大的特征作为节点；然后以该节点的取值为分支，在剩余的特征（属性）中选取信息增益最大的特征作为子节点3.应用实例及ID3算法=blogxgwz5三个源文件：ent.py计算数据集D类别的信息熵entgain.py分别计算各个特征对计算数据集D类别的信息增益id3.pyID3算法Python程序展示3.应用实例及ID3算法决策树生成算法递归的产生决策树，直到不能继续下去为止，这样产生的树往往对训练数据的分类很准确，但对未知测试数据的分类缺没有那么精确，即会出现过拟合现象。过拟合产生的原因在于在学习时过多的考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树，解决方法是考虑决策树的复杂度，对已经生成的树进行简化。剪枝（pruning）：从已经生成的树上裁掉一些子树或叶节点，并将其根节点或父节点作为新的叶子节点，从而简化分类树模型。实现方式：极小化决策树整体的损失函数或代价函数来实现决策树剪枝3.应用实例及ID3算法损失函数定义(1/2)Ntk代表t个叶子上的第k种类型个数3.应用实例及ID3算法损失函数定义(2/2)3.应用实例及ID3算法C4.5是RossQuinlan在1993年在ID3的基础上改进而提出的。ID3采用的信息增益度量存在一个缺点，它一般会优先选择有较多属性值的Feature,因为属性值多的Feature会有相对较大的信息增益?(信息增益反映的给定一个条件以后不确定性减少的程度,必然是分得越细的数据集确定性更高,也就是条件熵越小,信息增益越大)。为了避免这个不足C4.5中是用信息增益比率(gainratio)来作为选择分支的准则。信息增益比率通过引入一个被称作分裂信息(Splitinformation)的项来惩罚取值较多的Feature。除此之外，C4.5还弥补了ID3中不能处理特征