25/1/261第2讲决策树分类25/1/262数据实例•PlayTennis数据库片段：25/1/263决策树实例•关于PlayTennis的决策树：HighOvercastNormalStrongWeakSunnyRainOutlookWindHumidityNoYesYesNoYes25/1/264决策树学习算法的代表•早在1986年的时候，Quinlan就提出了著名的ID3算法。（PublishedonMLJ）•用ID3算法长树的基本思想：–分类能力最好的属性被测试并创建树的根结点–测试属性每个可能的值产生一个分支–训练样本划分到适当的分支形成儿子结点–重复上面的过程，直到所有的结点都是叶子结点两个问题：什么属性最好？什么结点才是叶子结点？25/1/265信息增益（InformationGain）•属性A划分样本集S的信息增益Gain(S,A)为：Gain(S,A)=E(S)–E(S,A)其中，E(S)为划分样本集S为c个类的熵；E(S,A)为属性A划分样本集S导致的期望熵。25/1/266熵（Entropy）•划分样本集S为c个类的熵E(S)为：其中，pi＝ni/n，为S中的样本属于第i类Ci的概率，n为S中样本的个数。ciiippSE12log25/1/267期望熵（ExpectedEntropy）•属性A划分样本集S导致的期望熵E(S,A)为：其中，Values(A)为属性A取值的集合；Sv为S中A取值为v的样本子集，Sv={sSA(s)=v}；E(Sv)为将Sv中的样本划分为c个类的信息熵。|Sv|/|S|为Sv和S中的样本个数之比。AValuesvvvSESSASE,25/1/268回味ID3算法•ID3算法每一步选择具有最大信息增益的属性作为测试属性来长树。直到最大的信息增益为也零为止。（两个问题的解决）•熵（Entropy）刻画了样本集的纯度，长树的过程是一个熵降低、信息增益、从混沌到有序的过程。（长树的物理意义）25/1/269伪代码•算法Decision_Tree（samples,attribute_list）•输入由离散值属性描述的训练样本集samples；候选属性集合atrribute_list。•输出一棵决策树。•方法•(1)创建节点N；•(2)ifsamples都在同一类C中then•(3)返回N作为叶节点，以类C标记；•(4)ifattribute_list为空then25/1/2610伪代码（续）•(5)返回N作为叶节点，以samples中最普遍的类标记；//多数表决•(6)选择attribute_list中具有最高信息增益的属性test_attribute；•(7)以test_attribute标记节点N；•(8)foreachtest_attribute的已知值v//划分samples•(9)由节点N分出一个对应test_attribute=v的分支；•(10)令Sv为samples中test_attribute=v的样本集合；//一个划分块•(11)ifSv为空then•(12)加上一个叶节点，以samples中最普遍的类标记；•(13)else加入一...
