分类决策树_ID3算法

决策树,决策树基本概念,决策树算法,主要内容,决策树基本概念,决策树算法,决策树基本概念,关于分类问题,分类（Classification）任务就是通过学习获得一个目标函数（TargetFunction）f,将每个属性集x映射到一个预先定义好的类标号y。,分类任务的输入数据是纪录的集合，每条记录也称为实例或者样例。用元组(X,y)表示，其中，X是属性集合，y是一个特殊的属性，指出样例的类标号（也称为分类属性或者目标属性）,决策树基本概念,关于分类问题,X,y,分类与回归,分类目标属性y是离散的，回归目标属性y是连续的,决策树基本概念,解决分类问题的一般方法,分类技术是一种根据输入数据集建立分类模型的系统方法。分类技术一般是用一种学习算法确定分类模型，该模型可以很好地拟合输入数据中类标号和属性集之间的联系。学习算法得到的模型不仅要很好拟合输入数据，还要能够正确地预测未知样本的类标号。因此，训练算法的主要目标就是要建立具有很好的泛化能力模型，即建立能够准确地预测未知样本类标号的模型。分类方法的实例包括：决策树分类法、基于规则的分类法、神经网络、支持向量级、朴素贝叶斯分类方法等。,决策树基本概念,解决分类问题的一般方法,通过以上对分类问题一般方法的描述，可以看出分类问题一般包括两个步骤：1、模型构建（归纳）通过对训练集合的归纳，建立分类模型。2、预测应用（推论）根据建立的分类模型，对测试集合进行测试。,决策树基本概念,解决分类问题的一般方法,学习算法,学习模型,模型,应用模型,训练集（类标号已知）,检验集（类标号未知）,归纳,推论,决策树基本概念,决策树,决策树是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。,决策树基本概念,决策树的优点1、推理过程容易理解，决策推理过程可以表示成IfThen形式；2、推理过程完全依赖于属性变量的取值特点；3、可自动忽略目标变量没有贡献的属性变量，也为判断属性变量的重要性，减少变量的数目提供参考。,主要内容,决策树基本概念,决策树算法,决策树算法,与决策树相关的重要算法,1、Hunt,Marin和Stone于1966年研制的CLS学习系统，用于学习单个概念。2、1979年,J.R.Quinlan给出ID3算法，并在1983年和1986年对ID3进行了总结和简化，使其成为决策树学习算法的典型。3、Schlimmer和Fisher于1986年对ID3进行改造，在每个可能的决策树节点创建缓冲区，使决策树可以递增式生成，得到ID4算法。4、1988年，Utgoff在ID4基础上提出了ID5学习算法，进一步提高了效率。1993年，Quinlan进一步发展了ID3算法，改进成C4.5算法。5、另一类决策树算法为CART，与C4.5不同的是，CART的决策树由二元逻辑问题生成，每个树节点只有两个分枝，分别包括学习实例的正例与反例。,CLS,ID3，C4.5，CART,决策树算法,假定公司收集了左表数据，那么对于任意给定的客人（测试样例），你能帮助公司将这位客人归类吗？即：你能预测这位客人是属于“买”计算机的那一类，还是属于“不买”计算机的那一类？又：你需要多少有关这位客人的信息才能回答这个问题？,决策树的用途,谁在买计算机？,年龄？,学生？,信誉？,青,中,老,否,是,优,良,决策树的用途,决策树算法,谁在买计算机？,年龄？,学生？,信誉？,青,中,老,否,是,优,良,决策树的用途,决策树算法,决策树算法,决策树的表示,决策树的基本组成部分：决策结点、分支和叶子。,年龄？,学生？,信誉？,青,中,老,否,是,优,良,决策树中最上面的结点称为根结点。是整个决策树的开始。每个分支是一个新的决策结点，或者是树的叶子。每个决策结点代表一个问题或者决策.通常对应待分类对象的属性。每个叶结点代表一种可能的分类结果,在沿着决策树从上到下的遍历过程中，在每个结点都有一个测试。对每个结点上问题的不同测试输出导致不同的分枝，最后会达到一个叶子结点。这一过程就是利用决策树进行分类的过程，利用若干个变量来判断属性的类别,ID3,决策树算法,ID3算法主要针对属性选择问题。是决策树学习方法中最具影响和最为典型的算法。该方法使用信息增益度选择测试属性。当获取信息时，将不确定的内容转为确定的内容，因此信息伴着不确定性。从直觉上讲，小概率事件比大概率事件包含的信息量大。如果某件事情是“百年一见”则肯定比“习以为常”的事件包含的信息量大。如何度量信息量的大小？,ID3信息量大小的度量,决策树算法,Shannon1948年提出的信息论理论。事件ai的信息量I（ai）可如下度量：,其中p(ai)表示事件ai发生的概率。假设有n个互不相容的事件a1,a2,a3,.,an,它们中有且仅有一个发生，则其平均的信息量可如下度量：,ID3信息量大小的度量,决策树算法,上式，对数底数可以为任何数，不同的取值对应了熵的不同单位。通常取2，并规定当p(ai)=0时=0,信息增益用来衡量给定的属性区分训练样例的能力，中间（间接）表示属性ID3算法在生成树的每一步使用信息增益从候选属性中选择属性用熵度量样例的均一性,决策树算法,信息增益用熵度量样例的均一性熵刻画了任意样例集合S的纯度给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类（函数）的熵为信息论中对熵的一种解释：熵确定了要编码集合S中任意成员的分类所需要的最少二进制位数；熵值越大，需要的位数越多。更一般地，如果目标属性具有c个不同的值，那么S相对于c个状态的分类的熵定义为,决策树算法,用信息增益度量熵的降低程度属性A的信息增益，使用属性A分割样例集合S而导致的熵的降低程度Gain(S,A)是在知道属性A的值后可以节省的二进制位数例子，注意是对当前样例集合计算上式,理解信息熵,1、信息熵是用来衡量一个随机变量出现的期望值，一个变量的信息熵越大，那么它出现的各种情况也就越多，也就是包含的内容多，我们要描述它就需要付出更多的表达才可以，也就是需要更多的信息才能确定这个变量。2、信息熵是随机变量的期望。度量信息的不确定程度。信息的熵越大，信息就越不容易搞清楚（杂乱）。3、一个系统越是有序，信息熵就越低；反之，一个系统越是混乱，信息熵就越高。信息熵也可以说是系统有序化程度的一个度量。4、信息熵用以表示一个事物的非确定性，如果该事物的非确定性越高，你的好奇心越重，该事物的信息熵就越高。5、熵是整个系统的平均消息量。信息熵是信息论中用于度量信息量的一个概念。一个系统越是有序，信息熵就越低；反之，一个系统越是混乱，信息熵就越高。6、处理信息就是为了把信息搞清楚，实质上就是要想办法让信息熵变小。,理解信息增益,熵：表示随机变量的不确定性。条件熵：在一个条件下，随机变量的不确定性。信息增益：熵-条件熵。表示在一个条件下，信息不确定性减少的程度。例如：假设X(明天下雨)的信息熵为2（不确定明天是否下雨），Y(如果是阴天则下雨）的条件熵为0.01（因为如果是阴天就下雨的概率很大，信息就少了）信息增益=2-0.01=1.99。信息增益很大。说明在获得阴天这个信息后，明天是否下雨的信息不确定性减少了1.99，是很多的，所以信息增益大。也就是说阴天这个信息对下雨来说是很重要的。,ID3信息量大小的度量,决策树算法,Gain（S，A）是属性A在集合S上的信息增益Gain（S，A）=Entropy（S）-Entropy（S，A）Gain（S，A）越大，说明选择测试属性对分类提供的信息越多,决策树算法,第1步计算决策属性的熵,决策属性“买计算机？”。该属性分两类：买/不买S1(买)=641S2（不买）=383S=S1+S2=1024P1=641/1024=0.6260P2=383/1024=0.3740I(S1,S2)=I(641,383)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9537,决策树算法,第2步计算条件属性的熵,条件属性共有4个。分别是年龄、收入、学生、信誉。分别计算不同属性的信息增益。,决策树算法,第2-1步计算年龄的熵,年龄共分三个组：青年、中年、老年青年买与不买比例为128/256S1(买)=128S2（不买）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9183,决策树算法,第2-2步计算年龄的熵,年龄共分三个组：青年、中年、老年中年买与不买比例为256/0S1(买)=256S2（不买）=0S=S1+S2=256P1=256/256P2=0/256I(S1,S2)=I(256，0)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0,决策树算法,第2-3步计算年龄的熵,年龄共分三个组：青年、中年、老年老年买与不买比例为257/127S1(买)=257S2（不买）=127S=S1+S2=384P1=257/384P2=127/384I(S1,S2)=I(257，127)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9157,决策树算法,第2-4步计算年龄的熵,年龄共分三个组：青年、中年、老年所占比例青年组384/1025=0.375中年组256/1024=0.25老年组384/1024=0.375计算年龄的平均信息期望E（年龄）=0.375*0.9183+0.25*0+0.375*0.9157=0.6877G（年龄信息增益）=0.9537-0.6877=0.2660（1）,决策树算法,第3步计算收入的熵,收入共分三个组：高、中、低E（收入）=0.9361收入信息增益=0.9537-0.9361=0.0176(2),决策树算法,第4步计算学生的熵,学生共分二个组：学生、非学生E（学生）=0.7811年龄信息增益=0.9537-0.7811=0.1726（3）,决策树算法,第5步计算信誉的熵,信誉分二个组：良好，优秀E（信誉）=0.9048信誉信息增益=0.9537-0.9048=0.0453（4）,决策树算法,第6步计算选择节点,年龄信息增益=0.9537-0.6877=0.2660（1）收入信息增益=0.9537-0.9361=0.0176（2）年龄信息增益=0.9537-0.7811=0.1726（3）信誉信息增益=0.9537-0.9048=0.0453（4）,决策树算法,年龄,青年,中年,老年,买/不买,买,买/不买,叶子,决策树算法,青年买与不买比例为128/256S1(买)=128S2（不买）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9183,决策树算法,如果选择收入作为节点分高、中、低,平均信息期望（加权总和）：E(收入）=0.3333*0+0.5*0.9183+0.1667*0=0.4592Gain(收入)=I(128,256)-E(收入)=0.91830.4592=0.4591,I(0,128)=0比例:128/384=0.3333I(64,128)=0.9183比例:192/384=0.5I(64,0)=0比例:64/384=0.1667,注意,决策树算法,年龄,青年,中年,老年,学生,买,信誉,叶子,否,是,优,良,买,不买,买/不买,买,叶子,叶子,叶子,决策树算法,ID3决策树建立算法1决定分类属性；2对目前的数据表，建立一个节点N3如果数据库中的数据都属于同一个类，N就是树叶，在树叶上标出所属的类4如果数据表中没有其他属性可以考虑，则N也是树叶，按照少数服从多数的原则在树叶上标出所属类别5否则，根据平均信息期望值E或GAIN值选出一个最佳属性作为节点N的测试属性6节点属性选定后，对于该属性中的每个值：从N生成一个分支，并将数据表中与该分支有关的数据收集形成分支节点的数据表，在表中删除节点属性那一栏如果分支数据表非空，则运用以上算法从该节点建立子树。,决策树算法,决策树的数据准备,原始表,决策树算法,整理后的数据表,决策树的数据准备,Datacleaning删除/减少noise，补填missingvaluesDatatransformation数据标准化（datanormalization）数据归纳（generalizedatatohigher-levelconceptsusingconcepthierarchies）例如：年龄归纳为老、中、青三类控制每个属性的可能值不超过七种（最好不超过五种）Relevanceanalysis对于与问题无关的属性：删对于属性的可能值大于七种又不能归纳的属性：删,决策树算法,决策树的数据准备,决策树算法,处理连续属性值,决策树算法比较适合处理离散数值的属性。实际应用中属性是连续的或者离散的情况都比较常见。在应用连续属性值时，在一个树结点可以将属性Ai的值划分为几个区间。然后信息增益的计算就可以采用和离散值处理一样的方法。原则上可以将Ai的属性划分为任意数目的空间。C4.5中采用的是二元分割（BinarySplit）。需要找出一个合适的分割阈值。参考C4.5算法Top10algorithmsindataminingKnowledgeInformationSystem200814:137,决策树算法,ID3算法小结,ID3算法是一种经典的决策树学习算法，由Quinlan于1979年提出。ID3算法的基本思想是，以信息熵为度量，用于决策树节点的属性选择，每次优先选取信息量最多的属性，亦即能使熵值变为最小的属性，以构造一颗熵值下降最快的决策树，到叶子节点处的熵值为0。此时，每个叶子节点对应的实例集中的实例属于同一类。,决策树算法,ID3算法实际应用-在电信行业应用实例（1）,通过ID3算法来实现客户流失的预警分析，找出客户流失的特征，以帮助电信公司有针对性地改善客户关系，避免客户流失利用决策树方法进行数据挖掘，一般有如下步骤：数据预处理、决策树挖掘操作，模式评估和应用。电信运营商的客户流失有三方面的含义：一是指客户从一个电信运营商转网到其他电信运营商，这是流失分析的重点。二是指客户月平均消费量降低，从高价值客户成为低价值客户。三、指客户自然流失和被动流失。在客户流失分析中有两个核心变量：财务原因非财务原因、主动流失被动流失。客户流失可以相应分为四种类型：其中非财务原因主动流失的客户往往是高价值的客户。他们会正常支付服务费用，并容易对市场活动有所响应。这种客户是电信企业真正需要保住的客户。,决策树算法,ID3算法实际应用-在电信行业应用实例（2）,数据预处理数据挖掘的处理对象是大量的数据，这些数据一般存储在数据库系统中（该用户相关数据存储在其CRM中），是长期积累的结果。但往往不适合直接挖掘，需要做数据的预处理工作，一般包括数据的选择(选择相关的数据)、净化(消除冗余数据)、转换、归约等。数据预处理工作准备是否充分，对于挖掘算法的效率乃至正确性都有关键性的影响。该公司经过多年的电脑化管理，已有大量的客户个人基本信息(文中简称为客户信息表)。在客户信息表中，有很多属性，如姓名用户号码、用户标识、用户身份证号码(转化为年龄)、在网时间（竣工时间）、地址、职业、用户类别、客户流失（用户状态）等等，数据准备时必须除掉表中一些不必要的属性，一般可采用面向属性的归纳等方法去掉不相关或弱相关属性。,决策树算法,ID3算法实际应用-在电信行业应用实例（3）,属性删除：将有大量不同取值且无概化操作符的属性或者可用其它属性来代替它的较高层概念的那些属性删除。比如客户信息表中的用户标识、身份证号码等，它们的取值太多且无法在该取值域内找到概化操作符，应将其删除，得到表1。,决策树算法,ID3算法实际应用-在电信行业应用实例（4）,属性概化：用属性概化阈值控制技术沿属性概念分层上卷或下钻进行概化。文化程度分为3类：W1初中以下(含初中)，W2高中(含中专)，W3大学(专科、本科及以上)；职业类别：按工作性质来分共分3类：Z1一Z3；缴费方式：托收：T1,营业厅缴费：T2,充值卡：T3。连续型属性概化为区间值：表中年龄、费用变化率和在网时间为连续型数据，由于建立决策树时，用离散型数据进行处理速度最快，因此对连续型数据进行离散化处理，根据专家经验和实际计算信息增益，在“在网时长”属性中，通过检测每个划分，得到在阈值为5年时信息增益最大，从而确定最好的划分是在5年处，则这个属性的范围就变为5：H1,H2。而在“年龄”属性中，信息增益有两个锋值，分别在40和50处，因而该属性的范围变为40-50即变为青年，中年，老年：N1,N2,N3；费用变化率：指（当月话费近3个月的平均话费）/近3个月的平均话费）0，F1:30%，F2：30%-99%,F3:100%变为F1,F2,F3。,决策树算法,ID3算法实际应用-在电信行业应用实例（5）,决策树算法,ID3算法实际应用-在电信行业应用实例（6）,在图中，NO表示客户不流失，YES表示客户流失。从图可以看出，客户费用变化率为100%的客户肯定已经流失；而费用变化率低于30%的客户；即每月资费相对稳定的客户一般不会流失，费用变化率在30%99%的客户有可能流失，其中年龄在4050岁之间的客户流失的可能性非常大，而年龄低于40岁的客户，用充值卡缴费的客户和在网时间较短的客户容易流失；年龄较大的客户，则工人容易流失。,步骤1：生成训练集和测试集生成训练集iris.train=iris2*(1:75)-1,（意思是返回原数据集1、3、5、7、8。、149奇数行行所有列的数据）生成测试集iris.test=iris2*(1:75),（意思是返回原数据集2、4、6、8、10、。、150偶数行所有列的数据）步骤2：生成决策树模型model-rpart(SpeciesSepal.Length+Sepal.Width+Petal.Length+Petal.Width,data=iris.train,method=class)绘制决策树fancyRpartPlot(model)步骤3：对测试集进行预测iris.rp3=predict(model,iris.test,-5,type=class)注释：iris.test,-5的意思是去掉原测试集第5列后的数据步骤4：查看预测结果并对结果进行分析，计算出该决策树的accuracy（分类正确的样本数除以总样本数）table(iris.test,5,iris.rp3)注释：iris.test,5的意思是取出测试集第5列的数据R语言中使用table(data)进行频数统计iris.rp3setosaversicolorvirginicasetosa2500versicolor0241virginica0322accuracy=（25+24+22）/75=94.67%步骤5：生成规则asRules(model),步骤1：生成训练集和测试集生成训练集iris.train=iris2*(1:75)-1,（意思是返回原数据集1、3、5、7、8。、149奇数行行所有列的数据）生成测试集iris.test=iris2*(1:75),（意思是返回原数据集2、4、6、8、10、。、150偶数行所有列的数据）步骤2：生成决策树模型model-rpart(SpeciesSepal.Length+Sepal.Width+Petal.Length+Petal.Width,data=iris.train,method=class)绘制决策树fancyRpartPlot(model)步骤3：对测试集进行预测iris.rp3=predict(model,iris.test,-5,type=class)注释：iris.test,-5的意思是去掉原测试集第5列后的数据步骤4：查看预测结果并对结果进行分析，计算出该决策树的accuracy（分类正确的样本数除以总样本数）table(iris.test,5,iris.rp3)注释：iris.test,5的意思是取出测试集第5列的数据R语言中使用table(data)进行频数统计iris.rp3setosaversicolorvirginicasetosa2500versicolor0241virginica0322accuracy=（25+24+22）/75=94.67%步骤5：生成规则asRules(model),