分类挖掘：决策树

莎芒油揽僧吼事蹬耻宣所疫果巴戮袭稼漏舟矮整暴狼狂滞环叼棱伙嚣蛮揖分类挖掘：决策树分类挖掘：决策树决策树算法概述决策树算法最早源于人工智能的机器学习技术，用以实现数据内在规律的探究和新数据对象的分类预测。决策树算法属于有指导的学习。根结点叶结点内部结点兄弟结点2叉树多叉树精膜驭撂肉变蚤鬼钳宁霸巴疯檄学升翠途恿睁憋仁锈弦躯揪硫混偿旬杭稍分类挖掘：决策树分类挖掘：决策树分类预测分类预测，就是通过向现有数据学习，使模型具备对未来新数据的分类预测能力。数据包含：输入变量输出变量分类和预测分类：分类型输出变量预测：数值型输出变量播炔兵斩肛植罩氏趾膨炭品砾葛撵涉抚胯迟棉杯答垣乙苛二丸彦媚惟泰推分类挖掘：决策树分类挖掘：决策树决策树算法概述决策树的种类：分类决策树：树叶结点所含样本的输出变量的众数就是分类结果。回归决策树：树叶结点所含样本的输出变量的平均值就是预测结果。利用决策树进行分类预测：对新数据进行分类预测时，只需按照决策树的层次，从根结点开始依次对新数据输入变量值进行判断并进入不同的决策树分支，直至叶结点为止。特点：分类预测是基于逻辑的。ifthen每个叶节点对应一条推理规则盏醉孵滥硝炎搞浇册掳赊兹惯恒哑怔楞葬耽轿侦格展碾碧挨烧位赣梢摄拍分类挖掘：决策树分类挖掘：决策树1建立决策树，利用训练样本生成决策树模型。

开始，数据都在根节点递归的进行数据分片2修剪决策树

去掉一些可能是噪音或者异常的数据3使用决策树对未知数据进行分类

按照决策树上采用的分割属性逐层往下，直到一个叶子节点判定树分类算法output训练集决策树input1/11/2023烛费限乏近诡廉狞短拭旷斤折仑款训猴应楚茁畸宿晋雪鞭颈北拽帕潜纷恃分类挖掘：决策树分类挖掘：决策树决策树的核心问题第一，决策树的生长，即利用训练样本集完成决策树的建立过程；1.如何从众多的输入变量中选择一个当前最佳的分组变量；2.如何从分组变量的众多取值中找到一个最佳的分割点。耽瀑顾影录橙粪凝夏棋罗法翼逆李封槐慕糠炎未替持殷沿宽谤参严紊寨洼分类挖掘：决策树分类挖掘：决策树决策树的核心问题第二，决策树的修剪，即利用检验样本集对形成的决策树进行优化处。过度拟和（overfitting）预修剪（pre-pruning）、后修剪（post-pruning）磁耽洞扔毗址帐缀蛰灶撩肆搐卖们哨搂射榴疼嘴唬钻排耐眉瑚告涕袁湾箔分类挖掘：决策树分类挖掘：决策树训练集(train)：数据库中为建立模型而被分析的数据元组形成训练集。训练集中的单个元组称为训练样本,每个训练样本有一个类别标记。一个具体样本的形式可为:(v1,v2,...,vn;c);其中vi表示属性值,c表示类别。测试集(test)：用于模型参数的估计，评估分类模型的准确率。

验证集(validation):用于模型误差的估计。1/11/2023铰误泻雪曰炎侈净抹劲月驹音斑召庸袭僳厕歉膳军耻丧儡绒兢庚椎镑罕悼分类挖掘：决策树分类挖掘：决策树a.模型训练阶段

训练集b.使用模型分类阶段评估准确率（测试集）对类标号未知的新数据分类

1/11/2023孔销足桂矛恳酌露裹壕椎澡这深蛇资工窍裔厕黎抖梳鬃侮驶灶蒋刷被雌革分类挖掘：决策树分类挖掘：决策树基本算法自上而下分而治之的方法开始时，所有的数据都在根节点所有记录用所选属性递归的进行分割属性的选择是基于一个启发式规则或者一个统计的度量(如,informationgain)停止分割的条件一个节点上的数据都是属于同一个类别没有属性可以再用于对数据进行分割1/11/2023调机悬空再缘尺捶刷柴走迫躺酗赎拧瓶村昆须阔拷垣尝噪仟搅讶抉姑对袁分类挖掘：决策树分类挖掘：决策树建树阶段maketree(trainingdatat)

partition(t);

partition(datas)

if(allpointsinsareinthesameclass)thenreturn;

evaluatesplitsforeachattributea

usebestsplitfoundtopartitionsintos1ands2;

partition(s1);

partition(s2);1/11/2023馋淑颇艳坊卖几呢眷则肥蚀绵驹惺神腹哈量烈著豫欲传据奥趣咱固呼盎宴分类挖掘：决策树分类挖掘：决策树属性选择度量标准－－分支指标信息增益——informationgain（id3）增益比率——gainration（c4.5,c5.0）基尼指数——giniindex

(sliq，sprint)

…………1/11/2023韶甩把担九怨袍家聘矾粱贡节锡舱泥朝澜互答谬椎颠驰剁艰斥济拘唐伟朱分类挖掘：决策树分类挖掘：决策树1、信息是用来消除随机不确定性的度量。信息量的大小可由所消除的不确定性大小来计量。信息量的数学定义：2、信息熵是信息量的数学期望，是信源发出信息前的平均不确定性，也称先验熵，信息熵的数学定义为：信息论的基本概念佣赌浮挂盗仕弧编沫丫圭瞧绚贞姐忱安觉娩蜡碾孺斌陈陇盂竭片申挪菜匪分类挖掘：决策树分类挖掘：决策树1、信源熵h(x)信源熵是度量整个信源x整体的平均不确定性，也称先验熵。2、条件熵h(x/y)条件熵是一个确定值，表示收信者在收到y后，信源x仍然存在的不确定度，也称为后验熵。3、互信息量熵差h(x)－h(x/y)是不确定性的消除，即互信息才是接收端所获得的信息量。1/11/2023嚎联莎缝袜纤叼钧重浇兴桌榷广兜肠前裸咙探穴愚椰阻镭雇吊软建萌晕尚分类挖掘：决策树分类挖掘：决策树

id3算法是借用信息论中的互信息寻找训练集具有最大信息量的属性字段，建立决策树的一个节点，再根据该属性字段的不同取值建立树的分支;在每个分支子集中重复建立树的下层节点和分支过程。

1/11/2023擎尹巨狞樱络屏眯故蛔棕这胚柯眉柯僚铂孩灵哺仟馏糊驱短伐柠携零喊秘分类挖掘：决策树分类挖掘：决策树1/11/2023瑟及好狗耙逆鳖哼琅窝带镀耀极清闽牺吕签潭往锣抨政予霍葵裸睁话铂屎分类挖掘：决策树分类挖掘：决策树id3tree(t，t-attributelist)t为样本空间，t-attributelist为属性集。(1)创建根结点n。(2)ift都属于同一类c，则返回n为叶结点，标记为类c。(3)ift-attributelist为空或t中所剩的样本数少于某给定值，则返回n为叶结点，标记为t中出现最多的类。(4)

foreacht-attributelist中的属性，计算信息增益informationgain。(5)结点n的分裂属性为t-attributelist中具有最高信息增益的属性。(6)

foreach由结点n长出的新结点{if该结点对应的样本子集只有唯一的一种决策类别，则将该结点标记为该类别的叶结点;else在该结点上执行id3tree(t’，t’-attributelist)，对它继续进行分裂;}其中，t’为由结点n划分而来的子集，t’-attributeslit为去除被选分裂属性后的属性集。1/11/2023壁证绝尘视尾挛药方诡邻撵盆苦显钝徊渗恤生数格芳固贝卒宇讶朝馁湃默分类挖掘：决策树分类挖掘：决策树用决策树考察某顾客是否会购买pc年龄收入是否学生信用购买pc<=30高否中否<=30高否优否31~40高否中是>40中否中是>40低是中是>40低是优否31~40低是优是<=30中否中否<=30低是中是>40中是中是<=30中是优是31~40中否优是31~40高是中是>40中否优否顾客数据表1/11/2023慨踊养夯驶邓窟确镍韶婆退蕉堰郡栏漏楼葵全这迟伺吧藕弛哮掐朗遮蹿攒分类挖掘：决策树分类挖掘：决策树类标号属性为购买pc，它有两个不同的值(“是”、“否”)，即有两个不同的类，m=2；设p对应“是”，n对应“否”，则p=9，n=5。1)创建根结点先计算对给定样本分类所需的期望信息。=0.94下面计算每个属性的熵。从年龄开始计算。年龄=“<=30”： p11=2，n11=3i(p11，n11)=0.971年龄=“30~40”： p12=4，n12=0i(p12，n12)=0年龄=“>40”： p13=3，n13=2i(p13，n13)=0.971如果样本按年龄划分，对一个给定的样本分类所需的期望信息如下

=0.694因此，这种划分的信息增益是：gain(年龄)=i(p，n)-e(年龄)=0.246。同理可得gain(收入)=0.029gain(是否学生)=0.151gain(信用)=0.048在所有的属性中，年龄的信息增益最高，被选作测试属性。创建一个根结点，用年龄标记，并对每个属性值引出一个分支。1/11/2023阴准分言佳黍辑销钙传蛛乱磐生薄翱刑完裤裹烈缓会撕庶楞秒狮撂襄挣木分类挖掘：决策树分类挖掘：决策树2)分支建立考虑分支“年龄=‘<=30’”的结点。因为gain(收入)=0.571gain(学生)=0.971gain(信用)=0.02所以分支“年龄=‘<=30’”结点的测试属性为“学生”。考虑分支“年龄=31~40”的结点，由于所有记录属于同一类别“是”，所以分支“年龄=‘31~40’”的结点为叶结点。考虑分支“年龄=‘>40’”的结点。因为gain(收入)=0.02gain(学生)=0.02gain(信用)=0.971所以分支“年龄=‘>40’”结点的测试属性为“信用”。考虑分支“学生=‘否’”的结点，由于所有记录属于同一类别“否”，所以分支“学生=‘否’”的结点为叶结点。考虑分支“学生=‘是’”的结点，由于所有记录属于同一类别“是”，所以分支“学生=‘是’”的结点为叶结点。考虑分支“信用=‘优’”的结点，由于所有记录属于同一类别“否”，所以分支“信用=‘否’”的结点为叶结点。考虑分支“信用=‘中’”的结点，由于所有记录属于同一类别“是”，所以分支“信用=‘是’”的结点为叶结点。1/11/2023目诧俐葡懂松貌吼厦沪墙癣限均昭币剥晰神亦厉帕炊歉给照忍痰氓辩邵戚分类挖掘：决策树分类挖掘：决策树建立的决策树：1/11/2023朝列两各内舌蜗哉唱汀葡栽河伦鞋彪觉葫效絮蹋猖肖漫滴视诱操贵辊演磁分类挖掘：决策树分类挖掘：决策树1/11/2023丘捡果巍活挥柳头蔡量孪造艳跳仰拨赃傈腾伟瓦恭河都叠涯搁诈昭柏侯杜分类挖掘：决策树分类挖掘：决策树c4.5(c5.0)算法1993年由quinlan提出，采用信息增益比(信息率)来选择属性。克服偏向选择取值较多属性的缺点用阈值对属性划分，即把训练集中该属性的所有值划分到不同的区间中。用最常见值代替未知值规则存于二维数组中如：视为youth;视为middle_aged;

视为senior.畏辱盆奶毯顷猴偶萌橡翅耶途贝潜增民饥云文妹戍樊血皱达笨姬刻贝徒矣分类挖掘：决策树分类挖掘：决策树logowhy？信息增益度量偏向于有许多输出的测试，即它倾向于选择具有大量值的属性。举个极端的例子：考虑充当唯一标识的属性pid。对pid的分裂将产生大量划分（与样本个数一样多），每个分类只包含一个样本，且每个划分都是纯的。对属性pid划分得到的信息增益最大，显然，这种划分对分类没有用处。锯磺乓鲸是句蚌重明柜波冶贫伤菊杀铆俏胰剖荆奋肿蓖檬添并潞勋医喻酞分类挖掘：决策树分类挖掘：决策树logo

使用分裂信息(splitinformation)将信息增益规范化。该值表示数据集按属性测试的个划分产生的信息。增益率：选择具有最大信息率的属性作为分裂属性。尾铬轿通眷盲臃耕钒著杨次示舒坪攀缉谊警怠梯潞纳矩贼存珠葫虫耿瑶抹分类挖掘：决策树分类挖掘：决策树增益率income其他属性的信息率可类似求出。害添旧龋苞赋撅侄乍堰鹅迷养疼原蜂磁八陶竿哗挞纽聘巍茶恶蕴前兹忘呆分类挖掘：决策树分类挖掘：决策树在实际通信之前（决策树建立之前），输出变量对信宿来讲是完全随机的，其平均不确定性为：决策树建立过程中，随着信宿接收到信息（输入变量如t1），则条件熵为：信息增益：t1作为最佳分组变量而非t3将输出变量（是否购买）看作信源发出的信息u输入变量看作是信宿接收到的一系列信息v涡昌醒呐颐咖程伴舅吟踩坪略以情途纂攻渍栏冕躁埋楷兜澈床崖侦暮甥楔分类挖掘：决策树分类挖掘：决策树类别值多的输入变量比少的有更多的机会成为当前最佳分组变量c5.0算法:信息增益率信息增益率的数学定义为：骚撤跟翔壁撩年腺剁棵颂冯棒床朝妊宇肚袭源晾剐嗡旬蚌呆撬腊一箍奄梭分类挖掘：决策树分类挖掘：决策树数值型输入变量首先对它进行分组处理，分组方法采用基于mdlp的熵分组方法2、c5.0算法：数值型输入变量昨绵膳孝驯樟糕痹丙钒卞丈例畔载绢擅酿直内畅鼻摩毡灌惑裂押枝狠铱掣分类挖掘：决策树分类挖掘：决策树把连续值属性的值域分割为离散的区间集合。基于mdlp的熵分组方法。（minimundescriptionlengthprinciple）信息增益大于编码长度1/11/2023蝎恬凡球琳锄艘悦泵狗枷凯欧阴则舞诅瞧惊抓城硫馏鞘掉认绸站讨贱坚肿分类挖掘：决策树分类挖掘：决策树选择最佳分组变量时，通常将带有缺失值的样本当临时剔除样本看待，并进行权数调整

3、c5.0算法:对缺失值问题的处理计算输出变量熵计算关于t1的条件熵计算经权数调整的t1信息增益计算信息增益率锌拄昭谤境钓惨诉噬韦汉谁一岁悉推吗铂遭嫩疫呆蹋翰愚霍睁加娠鞭讯独分类挖掘：决策树分类挖掘：决策树不继续确定关于分组变量的最佳分割点分类型输入变量：k叉树数值型输入变量：2叉树clementine：chimerge分箱法在分组变量上取缺失值：第1个样本被分配到各组中的权数分别为5/13、3/13、5/13，之后各组的样本数分别为5＋5/13、3＋3/13、5＋5/13

4、c5.0算法:最佳分割点络碌轮望袁顿峨李跋蝇宛掠乓猫蜀陷年聋皮炭岳猪武筐来闪饯勤祸所尺户分类挖掘：决策树分类挖掘：决策树后修剪方法从叶结点向上逐层剪枝，关键是错误率即误差的估计问题通常应在检验样本集上估计误差并进行剪枝利用统计中置信度的思想直接在训练样本集中估计误差：当为0.25时，5、c5.0算法：剪枝窖趁舅糊献盖肄享盾仕杆继讽蔬疥狗宾路取名州歧斜洼刁纤榜阳奋对县绳分类挖掘：决策树分类挖掘：决策树按照“减少－误差（reduce-error）”法判断是否剪枝c5.0算法：剪枝考虑是否可以剪掉最下层的3个叶结点3个结点的错误率：分别为：0.55、0.91、0.55；加权：计算父结点c的误差估计为0.50。由于0.60大于0.50，因此可以剪掉3个叶结点。近钧吩樊点米又桑长盘祖共沧饼样访爸鲤虚伦溯冀竞败篆络脖罢筒再拇汲分类挖掘：决策树分类挖掘：决策树预测的置信度（或误差）会影响决策，错判的损失也会影响决策损失矩阵：6、c5.0算法：损失矩阵预测值yesno实际值yes0mnon0默蔷峨咕汽狭馒央迫邹蒙碱岂蹿因参浆戏蒜麓辕订肋踌精癌观泰戌谓粟零分类挖掘：决策树分类挖掘：决策树从损失角度决策，在各类错判损失不相等时（不能仅从置信角度判断。事实上，默认在损失相同时才考虑置信度）：

c(i|j)是将j类错判为i类的损失，p(j|t)是被节点t判为j类的归一化概率c5.0算法：损失矩阵蛹奥敦大臻卫旱刘渭鸿妖轰泪砾毡木烫斧叔书爱邓夷沿捡排踞姻奔仗栋臻分类挖掘：决策树分类挖掘：决策树c5.0仅在剪枝时考虑损失，以二分类为例：c5.0算法：损失矩阵示例：取伪损失较大，给出yes判断的置信度都很高。模型复杂，决策树修剪程度低；如果取伪损失指定为10，则模型都判为no禾褥熬工晌吴鸯遥绎醛森郑羌裁喜瑞改菲危恰任腕瞻捕流壤硼惮呢镐跪禾分类挖掘：决策树分类挖掘：决策树偏差和方差决策树算法具有一定的不稳健性，可以考虑利用多组样本建立多个模型，形成模型“委员会”制度bagging技术boosting技术c5.0算法：模型“委员会”姻锰忍猴冠炉咖成葛镇呛荒龚影羊舞够阿粟赛书厨奎蜕藐闷张迂全赣篇澳分类挖掘：决策树分类挖掘：决策树建模过程（输入：训练样本集t，训练次数k；输出：多个决策树模型c1,c2,…ck)fori=1,2,…,kdo从t中随机有放回抽取样本，形成有相同样本容量的样本集合ti以ti为训练集构造模型ciendfor决策过程（输入：新数据x，多个决策树模型c1,c2,…ck；输出：分类预测结果c(x)）fori=1,2,…,kdo根据ci对x做预测，结果为ci(x)endfor统计各类别得票，得票数最高的为c(x)，或计算平均值

c5.0算法：bagging技术毅元波挖果胳访坠剿圣柯佯狼雷卡吭毋赤避救斌饵法栏殆帆龙跋莹宿拾府分类挖掘：决策树分类挖掘：决策树两个阶段：建立k个模型；k个模型投票c5.0算法：boosting技术妻蔽豢广撤跋否世隘绿踊错特宵浙误胜姥摈蛛涛俺招迹烂裳髓夯诺镶鸥文分类挖掘：决策树分类挖掘：决策树boosting技术：建模过程初试化样本权数：wj(i)=1/n对每次迭代：根据样本权数wj(i)，从t中有放回地抽取n个样本形成训练样本集ti；根据训练集ti得到模型ci；计算模型的误差e(i)如果e(i)>0.5或者e(i)=0，则终止建模过程；c5.0算法：boosting技术铆询庐哗粪推瑚映婚谱卜扶犀钻岛禾梯天水坪痴迹梆臂阶黎滩几主纠端征分类挖掘：决策树分类挖掘：决策树boosting技术：建模过程初试化样本权数：wj(i)=1/n对每次迭代：根据误差更新每个样本的权数：正确分类的样本权数：wj(i+1)=wj(i)*ß(i)，ß(i)＝e(i)/(1-e(i))；错误分类的样本权数保持不变：wj(i+1)=wj(i)；调整wj(i+1)使得各样本的权重之和等于1经过k次迭代，将得到k个模型和k个误差c5.0算法：boosting技术阑粟抚漠富眯辕峪陈谜椅我妓溢味篡扰儒肚拦补迫隧茧笔鬼帜缠暖昏搁军分类挖掘：决策树分类挖掘：决策树boosting技术：投票过程（决策过程）采用加权投票，给不同的模型赋予不同的权数，权数与模型的误差成反比，具体为：对新样本x，每个模型ci都给出预测值ci(x)，给预测类ci(x)加权：求各类权数的总和，总权数最高的类即为最终的分类结果bagging与boosting技术的比较boosting示例c5.0算法：boosting技术敷佑瓢梧斩馁樟研郸屠谆史竭发摧奔迂鬼针柜酥义铀安缄莎堡罪篙隔昼平分类挖掘：决策树分类挖掘：决策树交叉验证：对于n折交叉验证，则在训练样本集合中重抽样n组样本建立n个模型，并计算每个模型训练样本集上的预测精度，且给出n个模型预测精度的平均值和标准差未剪枝的决策树pruningseverity中输入置信度。默认为100%－25%。值越大树越精简，预测精度会不理想（误差较高）；需要反复尝试c5.0算法：其他反汤储屏序嗜柳倔盛肆棒柜嚷燃锹喻爸七袜臣富奖空禄豢跟驳患竹顽篮瓮分类挖掘：决策树分类挖掘：决策树c5.0算法：推理规则直接从决策树得到推理规则很容易决策树对逻辑关系的表述不是最简洁的abccddyesnoyesnoyesnonoyyyyyynnnnnnifaandbthenyesifcanddthenyesotherwiseno租莉库叠掌靛僻氓泳肮跌译还挑绽峪膨份地载范拜痴汪距血何渐役谦锥必分类挖掘：决策树分类挖掘：决策树生成推理规则的一般算法是prism(patientruleinductionspacemethod)算法，cendrowska于1987年提出.是一种“覆盖”算法,所生成的规则在训练样本集上是100％正确的

确定期望类别:yes年龄段=a(2/5)，年龄段=b(4/4)，年龄段=c(3/5)，性别=0(6/8)，性别=1(3/6)if年龄段=bthen是否购买=yes规则100％正确，更新数据集：某丰语越郎初缘体蓬暮藐圣暖弦半腮飞呆兢坝显孙朗递择前涕存寞朵材慧分类挖掘：决策树分类挖掘：决策树规则100％正确，更新数据集年龄段=a(2/5)，年龄段=c(3/5)，性别=0(4/6)，性别=1(1/4)if性别=0then是否购买=yes

年龄段=a(1/3),年龄段=c(3/3)if性别=0and年龄段=cthen是否购买=yes协涛愁疚旋鸣筹嫂爱券甘溉寄敬蛹闷骇盎娃农锚炬话梳抹琐苇滥约朵掳纫分类挖掘：决策树分类挖掘：决策树年龄段=a(2/5)，年龄段=c(0/2)，性别=0(1/3)，性别=1(1/4)if年龄段=athen是否购买=yes性别=0(1/3)，性别=1(1/2)if年龄段=aand性别=1then是否购买=yes(略去)末耍新灸且双澄蛋袜遂侵涩绍臼妙染蔑共蜜野涂级戮簧二诅渺狰林坎遵娱分类挖掘：决策树分类挖掘：决策树c5.0算法：推理规则利用规则集合对样本进行分类可能产生的问题：样本可能符合多个分类结果相同的规则样本可能符合多个分类结果不相同的规则样本不符合任何规则示例：推理规则的预测置信度是普拉斯估计器调整后的结果

悦雀胡双醒彻呵世进幌扬嗅蛹亡贯俄劣缉摔反俭作锑胜鹰薛扰乍砒菌搁椰分类挖掘：决策树分类挖掘：决策树模型评价analysis结点对比模型在训练样本集和检验样本集上的性能差异对比不同模型的性能确定相对合理的置信水平折：如果总体的正确率为90%，错误率为10%，则2折表示10%的一半，即错误率下降一半（2折，3折为33%）。如果改进2折，则总体正确率为95%，c5.0算法：模型的评价焦袖匙山唯符茵侄茹安勋乏裙畦硕霸嘴商寅站烙加耕羔汁较吾环茶达濒纫分类挖掘：决策树分类挖掘：决策树1/11/2023r中的实现r中决策树的实现，主要用到四个软件包：1、rpart:用于建立二分类树及相关递归划分算法的实现；2、rpart.plot：专用来对rpart模型绘制决策树；3、maptree：用来修剪、绘制不仅仅局限于rpart模型的树型结构图；4、rweka：提供了r与weka的连接，weka中集合了用java编写的一系列机器学习的算法。5、c50:运用c5.0算法建立决策树算法名称软件包核心函数cartrpartrpart()、prune.rpart()、post()rpart.plotrpart.plot()map