机器学习4.1 决策树1.pptVIP

例子：算法过程RefundYesNo假设选择MarSt为最优分割属性：3.samples={2,3,5,6,8,9,10}attribute_list={MarSt,TaxInc}NOMarStSingleMarriedDivorced4.samples={3,8,10},attribute_list={TaxInc}5.samples={5},attribute_list={TaxInc}6.samples={2,9},attribute_list={TaxInc}例子：算法过程RefundYesNo选择TaxInc为最优分割属性：4.samples={3,8,10}attribute_list={TaxInc}NOMarStSingleMarriedDivorcedTaxInc80K=80KYESNO问题1：分类从哪个属性开始？——选择分裂变量的标准问题2：为什么工资以80为界限？——找到被选择的变量的分裂点的标准（连续变量情况）分类划分的优劣用不纯性度量来分析。如果对于所有分支，划分后选择相同分支的所有实例都属于相同的类，则这个划分是纯的。对于节点m，令为到达节点m的训练实例数，个实例中个属于类，而。如果一个实例到节点m，则它属于类的概率估计为：节点m是纯的，如果对于所有i，为0或1。当到达节点m的所有实例都不属于类时，为0，当到达节点m的所有实例都属于类时，为1。一种度量不纯性的可能函数是熵函数（entropy)。Fatherofinformationtheory证明熵与信息内容的不确定程度有等价关系系统科学领域三大论之一C.Shannon的信息论信息熵熵(entropy)描述物质系统状态:该状态可能出现的程度。平均信息量若一个系统中存在多个事件E1,E2,…En每个事件出现的概率是p1,p2,…pn则这个系统的平均信息量是指的是系统的混乱的程度!(bits)?系统越无序、越混乱，熵就越大。?构造决策树，熵定义为无序性度量。?选择一个属性划分数据，使得子女节点上数据的类值（例中“yes”或“no”）大部分都相同（低无序性）。?如果一个节点上的数据类值在可能的类值上均匀分布，则称节点的熵（无序性）最大。?如果一个节点上的数据的类值对于所有数据都相同，则熵最小。?通过分裂，得到尽可能纯的节点。这相当于降低系统的熵。例子气象数据集什么因素影响是否去打网球？OutlookTemperatureHumidityWindyPlay?sunnyhothighfalseNosunnyhothightrueNoovercasthothighfalseYesrainmildhighfalseYesraincoolnormalfalseYesraincoolnormaltrueNoovercastcoolnormaltrueYessunnymildhighfalseNosunnycoolnormalfalseYesrainmildnormalfalseYessunnymildnormaltrueYesovercastmildhightrueYesovercasthotnormalfalseYesrainmildhightrueNo1.基于天气的划分2.基于温度的划分3.基于湿度的划分4.基于有风的划分构造树训练样本的信息值，即熵的描述第一棵树，属性，各叶节点的信息值第一棵树，属性，导致的信息增益依次，计算每棵树导致的信息增益选择获得最大信息增益的属性进行划分以此类推，递归，继续划分当所有叶节点都是纯的，划分过程终止下面看具体例子分析（1）训练样本的信息值(基于类的比例）?训练样本（用来创建树的数据集）在包含9个yes和5个no的根节点上，对应于信息值info([9,5])=0.940位→总的信息（2）第一棵树，属性，各叶节点的信息值?基于天气(outlook)的划分，在叶节点的yes和no类的个数分别是[2,3]，[4,0]，和[3,2]，而这些