1、决策树决策树决策树基本概念决策树基本概念决策树算法决策树算法主要内容主要内容决策树基本概念决策树基本概念决策树算法决策树算法决策树基本概念决策树基本概念关于分类问题关于分类问题 分类(Classification)任务就是通过学习获得一个目标函数(Target Function)f,将每个属性集x映射到一个预先定义好的类标号y。分类任务的输入数据是纪录的集合,每条记录也称为实例或者样例。用元组(X,y)表示,其中,X 是属性集合,y是一个特殊的属性,指出样例的类标号(也称为分类属性或者目标属性)决策树基本概念决策树基本概念关于分类问题关于分类问题名称体温表皮覆盖胎生水生动物飞行动物有腿冬眠类标
2、号人类恒温毛发是否否是否哺乳动物海龟冷血鳞片否半否是否爬行类鸽子恒温羽毛否否是是否鸟类鲸恒温毛发是是否否否哺乳类Xy分类与回归分类与回归分类目标属性分类目标属性y是离散的,回归目标属性是离散的,回归目标属性y是连续的是连续的决策树基本概念决策树基本概念解决分类问题的一般方法解决分类问题的一般方法 分类技术是一种根据输入数据集建立分类模型的系统方法。分类技术一般是用一种学习算法确定分类模型,该模型可以很好地拟合输入数据中类标号和属性集之间的联系。学习算法得到的模型不仅要很好拟合输入数据,还要能够正确地预测未知样本的类标号。因此,训练算法的主要目标就是要建立具有很好的泛化能力模型,即建立能够准确地
3、预测未知样本类标号的模型。分类方法的实例包括:决策树分类法、基于规则的分类法、神经网络、支持向量级、朴素贝叶斯分类方法等。决策树基本概念决策树基本概念解决分类问题的一般方法解决分类问题的一般方法 通过以上对分类问题一般方法的描述,可以看出分类问题一般包括两个步骤:1、模型构建(归纳)通过对训练集合的归纳,建立分类模型。2、预测应用(推论)根据建立的分类模型,对测试集合进行测试。决策树基本概念决策树基本概念解决分类问题的一般方法解决分类问题的一般方法TIDA1A2A3类1Y100LN2N125SN3Y400LY4N415MN学习算法学习模型模型模型应用模型TIDA1A2A3类1Y100L?2N1
4、25S?3Y400L?4N415M?训练集(类标号已知)训练集(类标号已知)检验集(类标号未知)检验集(类标号未知)归纳推论决策树基本概念决策树基本概念决策树决策树 决策树是一种典型的分类方法,首先对数据进行处理,利用归纳算法生成可读的规则和决策树,然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。决策树基本概念决策树基本概念决策树的优点决策树的优点1、推理过程容易理解,决策推理过程可以表示成If Then形式;2、推理过程完全依赖于属性变量的取值特点;3、可自动忽略目标变量没有贡献的属性变量,也为判断属性 变量的重要性,减少变量的数目提供参考。主要内容主要内容决
5、策树基本概念决策树基本概念决策树算法决策树算法决策树算法决策树算法与决策树相关的重要算法与决策树相关的重要算法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 进一步
6、发展了ID3算法,改进成C4.5算法。5、另一类决策树算法为CART,与C4.5不同的是,CART的决策树由二元逻辑问题生成,每个树节点只有两个分枝,分别包括学习实例的正例与反例。CLS,ID3,C4.5,CART决策树算法决策树算法计数年龄收入学生信誉归类:买计算机?归类:买计算机?64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买假定公司收集了左表数据,那么对假定公司收集了左表数据,那么对于任意给定的客人(测试样例)
7、,于任意给定的客人(测试样例),你能帮助公司将这位客人归类吗?你能帮助公司将这位客人归类吗?即:你能预测这位客人是属于即:你能预测这位客人是属于“买买”计算机的那一类,还是属于计算机的那一类,还是属于“不买不买”计算机的那一类?计算机的那一类?又:你需要多少有关这位客人的信又:你需要多少有关这位客人的信息才能回答这个问题?息才能回答这个问题?决策树的用途决策树的用途计数年龄收入学生信誉归类:买计算机?归类:买计算机?64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优
8、买32中高是良买63老中否优不买1 老中否优买谁在买计算机?谁在买计算机?年龄?学生?信誉?买青中老否是优良不买买买不买决策树的用途决策树的用途决策树算法决策树算法计数年龄收入学生信誉归类:买归类:买计算机?计算机?64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买谁在买计算机?谁在买计算机?年龄?学生?信誉?买青中老否是优良不买买买不买决策树的用途决策树的用途决策树算法决策树算法决策树算法决策树算法决策树的表示决策树的
9、表示决策树的基本组成部分:决策结点、分支和叶子。决策树的基本组成部分:决策结点、分支和叶子。年龄?学生?信誉?买青中老否是优良不买买买不买决策树中最上面的结点称为根结点。是整个决策树的开始。每个分支是一个新的决策结点,或者是树的叶子。每个决策结点代表一个问题或者决策.通常对应待分类对象的属性。每个叶结点代表一种可能的分类结果 在沿着决策树从上到下的遍历过程中,在每个结点都有一个测试。对每个结点上问题的不同测试输出导致不同的分枝,最后会达到一个叶子结点。这一过程就是利用决策树进行分类的过程,利用若干个变量来判断属性的类别ID3 决策树算法决策树算法 ID3算法主要针对属性选择问题。是决策树学习方
10、法中最具影响和最为典型的算法。该方法使用信息增益度选择测试属性。该方法使用信息增益度选择测试属性。当获取信息时,将不确定的内容转为确定的内容,因此信息伴着不确定性。从直觉上讲,小概率事件比大概率事件包含的信息量大。如果某件事情是“百年一见”则肯定比“习以为常”的事件包含的信息量大。如何度量信息量的大小?ID3 信息量大小的度量信息量大小的度量决策树算法决策树算法Shannon1948年提出的信息论理论。事件ai的信息量I(ai)可如下度量:其中p(ai)表示事件ai发生的概率。假设有n个互不相容的事件a1,a2,a3,.,an,它们中有且仅有一个发生,则其平均的信息量可如下度量:niiinii
11、napapaIaaaI12121)(1log)()(),.,()(1log)()(2iiiapapaIID3 信息量大小的度量信息量大小的度量决策树算法决策树算法niiiniinapapaIaaaI12121)(1log)()(),.,(上式,对数底数可以为任何数,不同的取值对应了熵的不同单位。通常取2,并规定当p(ai)=0时 =0)(1log)()(2iiiapapaIv信息增益信息增益 用来衡量给定的属性区分训练样例的能力,用来衡量给定的属性区分训练样例的能力,ID3算法在生成算法在生成 树的每一步使用树的每一步使用信息增益信息增益从候选属性中选从候选属性中选择属性择属性v用熵度量样例的
12、均一性用熵度量样例的均一性v信息增益信息增益v用熵度量样例的均一性用熵度量样例的均一性 熵刻画了任意样例集合熵刻画了任意样例集合 S 的纯度的纯度 给定包含关于某个目标概念的正反样例的样例集给定包含关于某个目标概念的正反样例的样例集S,那么那么 S 相对这个布尔型分类(函数)的熵为相对这个布尔型分类(函数)的熵为 信息论中对熵的一种解释:信息论中对熵的一种解释:熵熵确定了确定了要编码集合要编码集合S中任意成员的分类所需要的最少二进制位数;熵值中任意成员的分类所需要的最少二进制位数;熵值越大,需要的位数越多越大,需要的位数越多。更一般地,如果目标属性具有更一般地,如果目标属性具有c个不同的值,那
13、么个不同的值,那么 S 相对于相对于c个状态的分类的熵定义为个状态的分类的熵定义为v用信息增益度量熵的降低程度熵的降低程度 属性A 的信息增益,使用属性A分割样例集合S 而导致的熵的降低程度 Gain(S,A)是在知道属性在知道属性A的值后可以节省的二进制位数的值后可以节省的二进制位数 例子,注意是对当前样例集合计算上式()(,)()()vvv Values ASGain S AEntropy SEntropy SSv1、信息熵是用来衡量一个随机变量出现的期望值,一个变量的信息熵越大,那么它出现的各种情况也就越多,也就是包含的内容多,我们要描述它就需要付出更多的表达才可以,也就是需要更多的信息
14、才能确定这个变量。v2、信息熵是随机变量的期望。度量信息的不确定程度。信息的熵越大,信息就越不容易搞清楚(杂乱)。v3、一个系统越是有序,信息熵就越低;反之,一个系统越是混乱,信息熵就越高。信息熵也可以说是系统有序化程度的一个度量。v4、信息熵用以表示一个事物的非确定性,如果该事物的非确定性越高,你的好奇心越重,该事物的信息熵就越高。v5、熵是整个系统的平均消息量。信息熵是信息论中用于度量信息量的一个概念。一个系统越是有序,信息熵就越低;反之,一个系统越是混乱,信息熵就越高。v6、处理信息就是为了把信息搞清楚,实质上就是要想办法让信息熵变小。熵:表示随机变量的不确定性。条件熵:在一个条件下,随
15、机变量的不确定性。信息增益:熵-条件熵。表示在一个条件下,信息不确定性减少的程度。v例如:假设X(明天下雨)的信息熵为2(不确定明天是否下雨),Y(如果是阴天则下雨)的条件熵为0.01(因为如果是阴天就下雨的概率很大,信息就少了)信息增益=2-0.01=1.99。信息增益很大。说明在获得阴天这个信息后,明天是否下雨的信息不确定性减少了1.99,是很多的,所以信息增益大。也就是说阴天这个信息对下雨来说是很重要的。ID3 信息量大小的度量信息量大小的度量决策树算法决策树算法Gain(S,A)是属性)是属性A在集合在集合S上的信息增益上的信息增益Gain(S,A)=Entropy(S)-Entrop
16、y(S,A)Gain(S,A)越大,说明选择测试属性对分类提供的信息越多)越大,说明选择测试属性对分类提供的信息越多计数年龄收入学生信誉归类:买计算机?归类:买计算机?64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买决策树算法决策树算法计数年龄收入学生信誉归类:买计算机?归类:买计算机?64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是
17、良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第1步计算决策属性的熵步计算决策属性的熵决策属性“买计算机?”。该属性分两类:买/不买S1(买)=641 S2(不买)=383S=S1+S2=1024P1=641/1024=0.6260P2=383/1024=0.3740I(S1,S2)=I(641,383)=-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2)=0.9537决策树算法决策树算法计数年龄收入学生信誉归类:买计算机?归类:买计算机?64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买6
18、4老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第2步计算条件属性的熵步计算条件属性的熵条件属性共有4个。分别是年龄、收入、学生、信誉。分别计算不同属性的信息增益。决策树算法决策树算法计数年龄收入学生信誉归类:买计算机?归类:买计算机?64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第2-1步计算年龄的熵步计算年龄的
19、熵年龄共分三个组:青年、中年、老年青年买与不买比例为128/256S1(买)=128 S2(不买)=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2)=0.9183决策树算法决策树算法计数年龄收入学生信誉归类:买计算机?归类:买计算机?64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买
20、第第2-2步计算年龄的熵步计算年龄的熵年龄共分三个组:青年、中年、老年中年买与不买比例为256/0S1(买)=256 S2(不买)=0S=S1+S2=256P1=256/256P2=0/256I(S1,S2)=I(256,0)=-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2)=0决策树算法决策树算法计数年龄收入学生信誉归类:买计算机?归类:买计算机?64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1
21、老中否优买第第2-3步计算年龄的熵步计算年龄的熵年龄共分三个组:青年、中年、老年老年买与不买比例为257/127S1(买)=257 S2(不买)=127S=S1+S2=384P1=257/384P2=127/384I(S1,S2)=I(257,127)=-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2)=0.9157决策树算法决策树算法计数年龄收入学生信誉归类:买计算机?归类:买计算机?64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优
22、买32中高是良买63老中否优不买1 老中否优买第第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)决策树算法决策树算法计数年龄收入学生信誉归类:买计算机?归类:买计算机?64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青
23、中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第3步计算收入的熵步计算收入的熵收入共分三个组:高、中、低E(收入)=0.9361收入信息增益=0.9537-0.9361 =0.0176(2)决策树算法决策树算法计数年龄收入学生信誉归类:买计算机?归类:买计算机?64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第4步计算学生的熵步计算学生的熵学生共分二
24、个组:学生、非学生E(学生)=0.7811年龄信息增益=0.9537-0.7811 =0.1726 (3)决策树算法决策树算法计数年龄收入学生信誉归类:买计算机?归类:买计算机?64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第5步计算信誉的熵步计算信誉的熵信誉分二个组:良好,优秀E(信誉)=0.9048信誉信息增益=0.9537-0.9048 =0.0453 (4)决策树算法决策树算法计数年龄收入学生信誉归类:买计
25、算机?归类:买计算机?64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第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)决策树算法决策树算法计数年龄收入学生信誉归类:买计算机?归类
26、:买计算机?64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买年龄年龄青年中年老年买/不买买买/不买叶子决策树算法决策树算法计数年龄收入学生信誉归类:买计算机?归类:买计算机?64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买青年买与不买比例为128/256S1(买)=128 S2(不买)=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2)=0.9183决策树算法决策树算法计数年龄收入学生信誉归类:买计
27、算机?归类:买计算机?64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买如果选择收入作为节点分高、中、低平均信息期望(加权总和):E(收入)=0.3333*0+0.5*0.9183+0.1667*0=0.4592Gain(收入)=I(128,256)-E(收入)=0.9183 0.4592=0.4591I(0,128)=0 比例:128/384=0.3333I(64,128)=0.9183 比例:192/384=0.5I(64,0)=0比例:64/384=0.1667 注意决策树算法决策树算法计数年龄收入学生信誉归类:买计算归类:买计算机?机?64青高否良不买64青
28、高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买年龄年龄青年中年老年学生买信誉叶子否否是是优优良良买不买买/不买买叶子叶子叶子决策树算法决策树算法ID3 决策树建立算法决策树建立算法1 决定分类属性;2 对目前的数据表,建立一个节点N3 如果数据库中的数据都属于同一个类,N就是树叶,在树叶上 标出所属的类4 如果数据表中没有其他属性可以考虑,则N也是树叶,按照少 数服从多数的原则在树叶上标出所属类别5 否则,根据平均信息期望值E或GAIN值
29、选出一个最佳属性作 为节点N的测试属性6 节点属性选定后,对于该属性中的每个值:从N生成一个分支,并将数据表中与该分支有关的数据收集形 成分支节点的数据表,在表中删除节点属性那一栏 如果分支数据表非空,则运用以上算法从该节点建立子树。决策树算法决策树算法决策树的数据准备决策树的数据准备姓名姓名年龄年龄收入收入学生学生信誉信誉电话电话地址地址邮编邮编买计算机买计算机张三张三234000是是良良281-322-03282714 Ave.M77388买买李四李四342800否否优优713-239-78305606 Holly Cr78766买买王二王二701900否否优优281-242-322220
30、00 Bell Blvd.70244不买不买赵五赵五18900是是良良281-550-0544100 Main Street70244买买刘兰刘兰342500否否优优713-239-7430606 Holly Ct78566买买杨俊杨俊278900否否优优281-355-7990233 Rice Blvd.70388不买不买张毅张毅389500否否优优281-556-0544399 Sugar Rd.78244买买。原始表原始表决策树算法决策树算法计数年龄收入学生信誉归类:归类:买计算买计算机?机?64青 高否良不买64青 高否优不买128中 高否良买60老 中否良买64老 低是良买64老 低
31、是优不买64中 低是优买128青 中否良不买64青 低是良买。整理后的数据表整理后的数据表决策树的数据准备决策树的数据准备vData cleaning删除删除/减少减少noise,补填补填missing valuesvData transformation数据标准化(数据标准化(data normalization)数据归纳(数据归纳(generalize data to higher-level concepts using concept hierarchies)例如:年龄归纳为老、中、青三类例如:年龄归纳为老、中、青三类控制每个属性的可能值不超过七种控制每个属性的可能值不超过七种 (最好
32、不超过五种)(最好不超过五种)vRelevance analysis对于与问题无关的属性:删对于与问题无关的属性:删对于属性的可能值大于七种对于属性的可能值大于七种 又不能归纳的属性:删又不能归纳的属性:删决策树算法决策树算法决策树的数据准备决策树的数据准备决策树算法决策树算法处理连续属性值 决策树算法比较适合处理离散数值的属性。实际应用中属性是连续的或者离散的情况都比较常见。在应用连续属性值时,在一个树结点可以将属性Ai的值划分为几个区间。然后信息增益的计算就可以采用和离散值处理一样的方法。原则上可以将Ai的属性划分为任意数目的空间。C4.5中采用的是二元分割(Binary Split)。需
33、要找出一个合适的分割阈值。参考C4.5算法 Top 10 algorithms in data mining Knowledge Information System 2008 14:137决策树算法决策树算法ID3算法小结算法小结 ID3算法是一种经典的决策树学习算法,由Quinlan于1979年提出。ID3算法的基本思想是,以信息熵为度量,用于决策树节点的属性选择,每次优先选取信息量最多的属性,亦即能使熵值变为最小的属性,以构造一颗熵值下降最快的决策树,到叶子节点处的熵值为0。此时,每个叶子节点对应的实例集中的实例属于同一类。决策树算法决策树算法ID3算法实际应用算法实际应用-在电信行业应
34、用实例(在电信行业应用实例(1)通过ID3算法来实现客户流失的预警分析,找出客户流失的特征,以帮助电信公司有针对性地改善客户关系,避免客户流失 利用决策树方法进行数据挖掘,一般有如下步骤:数据预处理、决策树挖掘操作,模式评估和应用。电信运营商的客户流失有三方面的含义:一是指客户从一个电信运营商转网到其他电信运营商,这是流失分析的重点。二是指客户月平均消费量降低,从高价值客户成为低价值客户。三、指客户自然流失和被动流失。在客户流失分析中有两个核心变量:财务原因非财务原因、主动流失被动流失。客户流失可以相应分为四种类型:其中非财务原因主动流失的客户往往是高价值的客户。他们会正常支付服务费用,并容易
35、对市场活动有所响应。这种客户是电信企业真正需要保住的客户。决策树算法决策树算法ID3算法实际应用算法实际应用-在电信行业应用实例(在电信行业应用实例(2)数据预处理 数据挖掘的处理对象是大量的数据,这些数据一般存储在数据库系统中(该用户相关数据存储在其CRM中),是长期积累的结果。但往往不适合直接挖掘,需要做数据的预处理工作,一般包括数据的选择(选择相关的数据)、净化(消除冗余数据)、转换、归约等。数据预处理工作准备是否充分,对于挖掘算法的效率乃至正确性都有关键性的影响。该公司经过多年的电脑化管理,已有大量的客户个人基本信息(文中简称为客户信息表)。在客户信息表中,有很多属性,如姓名用户号码、
36、用户标识、用户身份证号码(转化为年龄)、在网时间(竣工时间)、地址、职业、用户类别、客户流失(用户状态)等等,数据准备时必须除掉表中一些不必要的属性,一般可采用面向属性的归纳等方法去掉不相关或弱相关属性。决策树算法决策树算法ID3算法实际应用算法实际应用-在电信行业应用实例(在电信行业应用实例(3)属性删除:将有大量不同取值且无概化操作符的属性或者可用其它属性来代替它的较高层概念的那些属性删除。比如客户信息表中的用户标识、身份证号码等,它们的取值太多且无法在该取值域内找到概化操作符,应将其删除,得到表1。表1 客户信息表年龄学历职业缴费方式在网时长费用变化率客户流失58大学公务员托收1310%
37、NO47高中工人营业厅缴费942%NO26研究生公务员充值卡263%YES28大学公务员营业厅缴费52.91%NO32初中工人营业厅缴费32.3%NO42高中无业人员充值卡2100%YES68初中无业人员营业厅缴费92.3%NO决策树算法决策树算法ID3算法实际应用算法实际应用-在电信行业应用实例(在电信行业应用实例(4)属性概化:用属性概化阈值控制技术沿属性概念分层上卷或下钻进行概化。文化程度分为3类:W1初中以下(含初中),W2高中(含中专),W3大学(专科、本科及以上);职业类别:按工作性质来分共分3类:Z1一Z3;缴费方式:托收:T1,营业厅缴费:T2,充值卡:T3。连续型属性概化为区
38、间值:表中年龄、费用变化率和在网时间为连续型数据,由于建立决策树时,用离散型数据进行处理速度最快,因此对连续型数据进行离散化处理,根据专家经验和实际计算信息增益,在“在网时长”属性中,通过检测每个划分,得到在阈值为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。表2 转化后的客户信息表
39、年龄学历职业缴费方式开户时间费用变化率客户流失N3W3Z1T1H2F1NON2W2Z2T2H2F2NON1W3Z1T3H1F2YESN1W3Z1T2H1F1NON1W1Z2T2H1F1NON2W2Z3T3H1F3YESN3W1Z3T1H2F1NO决策树算法决策树算法ID3算法实际应用算法实际应用-在电信行业应用实例(在电信行业应用实例(5)YESNO年 龄职 业YES缴费方式YESYESNOYSESNONO在网时长NOF1F2F3N1N2N3T1T2T3Z1Z2Z3H1H2费用变化率决策树算法决策树算法ID3算法实际应用算法实际应用-在电信行业应用实例(在电信行业应用实例(6)在图中,NO表示
40、客户不流失,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、
41、8、10、。、150偶数行所有列的数据)步骤2:生成决策树模型model-rpart(Species Sepal.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(分类正确的样本数除以总样本数)ta
42、ble(iris.test,5,iris.rp3)注释:iris.test,5的意思是取出测试集第5列的数据R语言中使用table(data)进行频数统计 iris.rp3 setosa versicolor virginica setosa 25 0 0 versicolor 0 24 1 virginica 0 3 22accuracy=(25+24+22)/75=94.67%步骤5:生成规则 asRules(model)v步骤1:生成训练集和测试集v生成训练集iris.train=iris2*(1:75)-1,(意思是返回原数据集1、3、5、7、8。、149奇数行行所有列的数据)v生成测
43、试集iris.test=iris2*(1:75),(意思是返回原数据集2、4、6、8、10、。、150偶数行所有列的数据)v步骤2:生成决策树模型vmodel-rpart(Species Sepal.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.rp3 setosa versicolor virginica setosa 25 0 0 versicolor 0 24 1 virginica 0 3 22accuracy=(25+24+22)/75=94.67%步骤5:生成规则 asRules(model)