《第七章-分类与预测(课堂PPT).ppt》由会员分享，可在线阅读，更多相关《第七章-分类与预测(课堂PPT).ppt（199页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据挖掘数据挖掘主讲：王名扬信息与计算机工程学院12引引 言言要挖掘知识的类型要挖掘知识的类型u概念描述：特征化和比较；u 关联规则；u 分类分类/预测；预测；u 聚类分析；u其他的数据挖掘任务。引引 言言根据现有的知识，我们得到了一些关于爬行动物和鸟类的信息，根据现有的知识，我们得到了一些关于爬行动物和鸟类的信息，我们能否对新发现的物种，比如动物我们能否对新发现的物种，比如动物A，动物，动物B进行分类？进行分类？动物种类动物种类体型体型翅膀数量翅膀数量脚的只数脚的只数是否产蛋是否产蛋是否有毛是否有毛类别类别狗中04否是爬行动物猪大04否是爬行动物牛大04否是爬行动物麻雀小22是是鸟类天鹅中2
2、2是是鸟类大雁中22是是鸟类动物A大02是无？动物B中22否是？324分类是数据挖掘中重要的任务分类是数据挖掘中重要的任务 v分类的目的是学会一个分类器（分类函数或模型），该分类器能把待分类的数据映射到给定的类别中。v分类可用于预测。从历史数据纪录中自动推导出对给定数据的推广描述，从而能对未来数据进行类预测。25分类方法的类型分类方法的类型v 从使用的主要技术上看，可以把分类方法归结为以下几种类型：基于距离的分类方法基于距离的分类方法决策树分类方法决策树分类方法贝叶斯分类方法贝叶斯分类方法。v 本章主要围绕这几种分类方法展开。第第 6 6 章章分类与预测分类与预测66 6.1.1 分分类类与与
3、预测预测的基本知的基本知识识6 6.2.2 基于距离的分基于距离的分类类算法算法6.3 6.3 决策决策树树分分类类方法方法6.4 6.4 贝贝叶斯分叶斯分类类方法方法6.5 6.5 规则归纳规则归纳方法方法*第第 6 6 章章76.1 6.1 分分类类和和预测预测的基本知的基本知识识l什么是分类？预测？什么是分类？预测？l分类和预测的基本问题分类和预测的基本问题81.1.分类？预测？分类？预测？910基本概念基本概念 u 分类和预测是两种数据分析的形式，可用于提取描述重要数据类的模型或预测未来的数据趋势：分类（分类（classification）：用于预测数据对象的分类标号分类标号（或离散离
4、散值），如，通过构造分类模型对银行贷款进行风险评估（安全或危险）；预测（预测（predication）：用于预测数据对象的连续取值连续取值，如，建立预测模型利用顾客收入与职业（参数）预测其可能用于购买计算机设备的支出大小。11数据分类过程数据分类过程数据分类是一个两步的过程：1 1）建立分类模型）建立分类模型：机器学习过程，通过某种分类算法对训练集进行训练，得到分类模型；“有指导的学习有指导的学习”、“有监督的学习有监督的学习”假定每个元组属于一个预定义的类，由一个称为类标号属性类标号属性的属性确定；训练数据集：为建立分类模型而被分析的数据元组。12分类过程的第一步：学习建模分类过程的第一步：
5、学习建模13数据分类过程数据分类过程数据分类是一个两步的过程：2 2）使用模型进行分类）使用模型进行分类：测试数据集：用于评估模型的预测准确率。模型在测试集上的准确率是正确被模型分类的测试样本所占的百分比。如认为模型的准确率可以接受，就可以用它来对类标号未知的数据元组或对象进行分类。14分类过程的第二步：分类测试分类过程的第二步：分类测试15分类过程示意图分类过程示意图有指导的有指导的学学习习 VS.无指导的学习无指导的学习u有指导有指导的学习（用于分类）训练样本的类标号已知；新数据使用训练数据集中得到的规则进行分类u无指导无指导的学习（用于聚类）训练样本的类标号未知；通过一系列的度量、观察，
6、试图确立数据中的类或聚类的存在1617数据预测数据预测u预测：预测：构造和使用模型评估无标号样本类，或评估给定样本可能具有的属性值或值区间u与分类区别：与分类区别：二者是两类主要的预测问题。分类是预测离散或标号值；预测是预测连续或有序值；观点：用预测法预测类标号为分类；用预测法预测连续值（一般用回归法）为预测。18示例示例背景：背景：假定已建立AllElectronics公司的邮寄清单数据库。邮寄清单用于分发介绍新产品和降价信息材料。数据库描述顾客的属性，包括姓名、年龄、收入、职业和信誉度，并按照顾客是否在该公司购买计算机进行分类。19示例示例分类模型：分类模型：假定新的顾客添加到数据库中，由
7、于向每位顾客分发促销材料费用很高，因此，可以根据数据库中已有顾客信息构建分类模型，用以预测需向哪些顾客分发材料。预测模型：预测模型：假定想预测在一个财政年度，一个顾客将在AllElectronics进行的主要的购买的数量，则可以构建一个预测模型。2.2.分类和预测的基本问题？分类和预测的基本问题？2021问题问题(1)(1)：数据准备：数据准备 1）准备分类和预测的数据）准备分类和预测的数据：数据的预处理v数据清理数据清理：噪声（平滑技术）；空缺值（统计手段）v相关性分析相关性分析（特征选择）：删除不相关和冗余属性，如银行贷款申请时填写的星期数，可能与贷款是否申请成功无关；v数据变换数据变换：
8、数据离散化（数据概化）：如属性“收入”的数值就可以被离散化为若干区间，如低、中等和高；数据规范化：将给定属性的值按比例缩放至较小的区间，如0,1。22问题问题(2)(2)：评估分类模型：评估分类模型 2）评估方法：）评估方法：对用于分类或预测的方法或模型进行评估v预测的准确率：模型正确预测未知对象类别或数值的能力；v速度：1）建立模型的时间；2）使用模型的时间v强壮性（鲁棒性）：处理噪声和空缺值的能力；v可伸缩（扩展）性：处理大型数据及构造模型的能力；v可理解性：模型的可理解能力；v规则的优越性：1）判定树的大小；2）分类规则的简洁性。6.2 6.2 基于距离的分基于距离的分类类算法算法l 基
9、本思想？基本思想？l 几种常见的距离分类算法？几种常见的距离分类算法？231.1.基于距离分类的基本思想基于距离分类的基本思想？24225基于距离的分类算法的思路基于距离的分类算法的思路q定义：给定一个数据库 D=t1，t2，tn和一组类C=C1，Cm。假定每个元组包括一些数值型的属性值：ti=ti1，ti2，tik，每个类也包含数值性属性值：Cj=Cj1，Cj2，Cjk，则分分类问题类问题是要分配每个是要分配每个ti到到满满足如下条件的足如下条件的类类Cj：sim(ti，Cj)=sim(ti，Ci)，CiC，CiCj，其中sim(ti，Cj)被称为相似性。226基于距离的分类算法的思路基于距
10、离的分类算法的思路q在实际的计算中往往用距离来表征：距离越近，相似性越大；距离越近，相似性越大；距离越距离越远远，相似性越小。，相似性越小。q如何度量距离？欧几里得距离；欧几里得距离；曼哈坦距离；曼哈坦距离；明考斯基距离；明考斯基距离；加加权权的明考斯基距离。的明考斯基距离。（一）欧几里得距离（一）欧几里得距离欧式距离由欧式距离由对应元素元素间差差值平方和的平方根所表示，即：平方和的平方根所表示，即：如何度量距离？如何度量距离？27（二）曼哈（二）曼哈顿距离距离对应元素元素间差差值绝对值的和表示，即：的和表示，即：欧几里得距离与曼哈顿距离的共同点：欧几里得距离与曼哈顿距离的共同点：(1)(1)
11、即距离是一个非负的数值即距离是一个非负的数值 (2)(2)自身的距离为自身的距离为0 (3)(3)即距离函数具有对称性即距离函数具有对称性 (4)(4)即距离函数满足三角不等式即距离函数满足三角不等式 如何度量距离？如何度量距离？28(三三)明可夫斯基距离明可夫斯基距离是欧几里得距离和曼哈是欧几里得距离和曼哈顿距离的概化距离的概化其中p是一个正整数：当p=1时，表示曼哈顿距离；当p=2时，表示欧几里得距离。(四四)加权的明可夫斯基距离加权的明可夫斯基距离如果如果对每一个每一个变量根据其重要性量根据其重要性赋予一个予一个权重，就得到加重，就得到加权的明考斯基的明考斯基距离。距离。如何度量距离？如
12、何度量距离？29230基于距离的分类算法的思路基于距离的分类算法的思路q在实际的计算中往往用距离来表征：距离越近，相似性越大；距离越近，相似性越大；距离越距离越远远，相似性越小。，相似性越小。q距离的计算方法有多种，最常用的是通过计算样本到每个类中心的距离来完成。231 基于距离的分类算法的一般性描述基于距离的分类算法的一般性描述q算法计算每个元组到各个类中心的距离类中心的距离，从而可以找出离它的最近的类中心，得到确定的类别标记。算法 基于距离的分类算法输入：每个类的中心C1，Cm；待分类的元组t。输出：输出类别c。（1）dist=；/距离初始化（2）FOR i:=1 to m DO（3）IF
13、 dis(ci，t)dist THEN BEGIN（4）c i；（5）distdist(ci，t)；（6）END.232基于距离的分类方法的直观解释基于距离的分类方法的直观解释（a）类定义）类定义（b）待分类样例）待分类样例（c）分类结果）分类结果33距离分类例题距离分类例题 例：例：C1=(3,3,4,2),C2=(8,5,-1,-7),C3=(-5,-7,6,10);请用基于距离的算法基于距离的算法给以下样本分类：A(5,5,0,0);B(5,5,-5,-5);C(-5,-5,5,5)34距离分类例题距离分类例题 欧几里得距离：欧几里得距离：d(A,C1)=(3-5)2+(3-5)2+(4
14、-0)2+(2-0)2)1/2=5.3;d(A,C2)=(8-5)2+(5-5)2+(-5-0)2+(-5-0)2)1/2=7.7;d(A,C3)=(-5-5)2+(-7-5)2+(5-0)2+(5-0)2)1/2=17.1显然应该将A划入C1类。342 2 几种常见的距离分类算法几种常见的距离分类算法？3536几种常见的距离分类算法几种常见的距离分类算法 u（1）k-近邻算法近邻算法；u（2）K-means算法（聚类）；算法（聚类）；u（3）K-mediods算法（聚类）。算法（聚类）。237（1）K-近近邻邻分分类类算法算法qK-近邻分类算法（K Nearest Neighbors，简称K
15、NN）通过计算每个训练数据到待分类元组的距离，取和待分类元组距离最近的K个训练数据，K个数据中哪个类别的训练数据占多数，则待分类元组就属于哪个类别。238（1）K-近近邻邻分分类类算法算法算法算法 4-2 K-近近邻邻分分类类算法算法输输入：入：训练训练数据数据T；近；近邻邻数目数目K；待分；待分类类的元的元组组t。输输出：出：输输出出类别类别c。（1）N=；（2）FOR each d T DO BEGIN（3）IF|N|K THEN（4）N=Nd；（5）ELSE（6）IF u N such that sim(t，u)sim(t，d)THEN BEGIN（7）N=N-u；（8）N=Nd；（9）
16、END（10）END（11）c=class to which the most uN.KNN的直的直观观解解释释1、定义的直观形式：、定义的直观形式：v找出与目标最接近的K个样本；v将目标划分到找出的K个样本中出现最频繁的类。2、K的直观形式：的直观形式：v以目标样本为中心；v划出一个刚好包含K个样本的圆；v当K增大时，圆半径增大。39KNN的直的直观观解解释释3、直观的例子、直观的例子v手写识别手写识别记录手写体特征；计算手写体与标准汉字的相似度；根据相似度（距离），找出K个备选集；选择一个正确汉字v人种识别人种识别欧洲人的鼻子、亚洲人的眼睛非洲人的肤色、亚洲人的头发40形象的例子形象的例子
17、KNN的分类思想的分类思想如果它走路像鸭子如果它走路像鸭子,叫声也像鸭子叫声也像鸭子,那么那么它它可能就是只鸭子可能就是只鸭子Training RecordsTest RecordCompute DistanceChoose k of the“nearest”records41KNN的特点的特点1、非参数统计方法v不需引入参数v回归分析是参数统计方法2、k的选择vK=1时，将待分类样本划入与其最接近的样本的类；vK=|X|时，仅根据训练样本进行频率统计，将待分类样本划入最多的类；vK需要合理选择，太小容易受干扰、太大增加计算复杂性3、算法的复杂度v维数灾难：当维数增加时，算法的复杂度会急剧增加
18、v一般采用降维处理426.3 6.3 决策决策树树分分类类算法算法l 决策树的基本概念？决策树的基本概念？l 决策树生成算法？决策树生成算法？l 剪枝方法？剪枝方法？l 提取分类规则？提取分类规则？431.1.决策树的基本概念？决策树的基本概念？44决策树基本概念决策树基本概念解决分类问题的一般方法解决分类问题的一般方法TIDA1A2A3类1Y100LN2N125SN3Y400LY4N415MN学习算法学习算法学习模型学习模型模型模型应用模型应用模型TIDA1A2A3类1Y100L？2N125S？3Y400L？4N415M？训练集（类标号已知）训练集（类标号已知）检验集（类标号未知）检验集（类
19、标号未知）归纳归纳推论推论4546基本概念基本概念 u 决策树（decision tree）：决策树是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策树对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。年龄？学生？信誉？买青中老否是优良不买买买不买47决策树的基本组成决策树的基本组成u 决策树的基本组成决策树是类似流程图的倒立的树型结构。最顶层节点为根节点根节点，是整个决策树的开始；树的每个内部节点内部节点表示在一个属性上的测试，其每个分支代表一个测试输出；树的每个叶节点叶节点代表一个类别。年龄？学生？信誉？买青中老否是优良不买买买不买
20、48基本概念基本概念 u决策树的生成包括两个过程：（1）树的建立首先所有训练样本都在根节点；依据所选的属性循环地划分样本。（2）树剪枝（tree pruning）：在决策树构造时，许多分支可能反映的是训练数据中的噪声或孤立点。树剪枝就是识别并消除这类分支，以提高在未知数据上分类的准确性。492.2.决策树的生成算法？决策树的生成算法？5051决策树的生成算法决策树的生成算法u基本的决策树生成算法是一个贪心算法，采用自上而下、分而自上而下、分而治之治之的递归方式来构造。u决策树上的各个分支是在对数据不断分组的过程中逐渐生长出来的。首先，选择一个属性作为根节点，然后把该属性的每一个可能的值作为子节
21、点，这样就把整个训练集分成了几个子集，根节点属性的每个取值都对应着一个子集，然后递归应用到每个子树上进行进一步划分，直到对所有数据的继续分组不再有意义时，决策树的生长过程宣告结束，此时便生成了一棵完整的决策树。其中，测试属性的选择测试属性的选择是构建决策树的关键环节，不同的决策树算法在此使用的技术都不尽相同。52决策树的生成算法决策树的生成算法注意：注意：u在决策树算法中，所有属性均为符号值，即离散值，因此若有取连续值的属性，必须首先进行离散化离散化。53决策树的生成算法决策树的生成算法常见的有如下几种决策树生成算法：u CLS;u ID3;u C4.5;u CART。（1）CLS（Conce
22、pt Learning System）算法）算法 CLS算法是早期的决策树学习算法。它是许多决策树学习算法的基础。CLS基本思想基本思想 从一棵空决策树开始，选择某一属性（分类属性）作为测试属性。该测试属性对应决策树中的决策结点。根据该属性的值的不同，可将训练样本分成相应的子集，如果该子集为空，或该子集中的样本属于同一个类，则该子集为叶结点，否则该子集对应于决策树的内部结点，即测试结点，需要选择一个新的分类属性对该子集进行划分，直到所有的子集都为空或者属于同一类。54人员眼睛颜色头发颜色所属人种1黑色黑色黄种人2蓝色金色白种人3灰色金色白种人4蓝色红色白种人5灰色红色白种人6黑色金色混血7灰色
23、黑色混血8蓝色黑色混血CLS算法算法55人员眼睛颜色头发颜色所属人种1黑色黑色黄种人2蓝色金色白种人3灰色金色白种人4蓝色红色白种人5灰色红色白种人6黑色金色混血7灰色黑色混血8蓝色黑色混血CLS算法算法-决策树的构建决策树的构建眼睛颜色眼睛颜色1,62,4,83,5,7黑色黑色蓝色蓝色灰色灰色不属于同一类，非叶结点不属于同一类，非叶结点56眼睛颜色眼睛颜色头发颜色头发颜色头发颜色头发颜色头发颜色头发颜色黑色黑色兰色兰色灰色灰色CLS算法算法黄种人黄种人1 混血混血6白种人白种人2 白种人白种人4 混血混血8 白种人白种人3 白种人白种人5混血混血7黑色黑色金色金色金色金色红色红色黑色黑色金色
24、金色红色红色黑色黑色57CLS算法算法1）生成一颗空决策树和一张训练样本属性集;2）若训练样本集T 中所有的样本都属于同一类，则生成结点T，并终止学习算法；否则3）根据某种策略某种策略从训练样本属性表中选择属性A 作为测试属性，生成测试结点A 4）若A的取值为v1,v2,vm，则根据A 的取值的不同，将T 划分成 m个子集T1,T2,Tm;5）从训练样本属性表中删除属性A;6）转步骤2,对每个子集递归调用CLS。58CLS算法存在的问题算法存在的问题q在步骤3中，根据某种策略从训练样本属性表中选择属性A作为测试属性，没有规定选择测试属性的标准和依据。q实践表明，测试属性集的组成以及测试属性的先
25、后对决策树的学习具有举足轻重的影响。举例：举例：下表为调查学生膳食结构和缺钙情况的关系，其中1表示包含食物，0表示不包含。59学生鸡肉猪肉牛肉羊肉鱼肉鸡蛋青菜番茄牛奶健康情况1011010101不缺钙2000011111不缺钙3111110100缺钙4110011001不缺钙5100111000缺钙6111001010缺钙7010001111不缺钙8010001111缺钙9010001111不缺钙10101111011不缺钙学生膳食结构和缺钙调查表学生膳食结构和缺钙调查表CLS算法存在的问题算法存在的问题60采用不同的测试属性及其先后顺序将会生成不同的决策树采用不同的测试属性及其先后顺序将会生
26、成不同的决策树鸡肉鸡肉猪肉猪肉猪肉猪肉牛肉牛肉牛肉牛肉牛肉牛肉不缺钙（不缺钙（2）缺钙（缺钙（3，6）不缺钙（不缺钙（4）不缺钙（不缺钙（10）缺钙（缺钙（5）不缺钙（不缺钙（1）鱼肉鱼肉缺钙（缺钙（5）不缺钙（不缺钙（7，9）是是否否是是否否否否否否否否否否否否是是是是是是是是是是CLS算法存在的问题算法存在的问题61牛奶牛奶不缺钙不缺钙（1，2，4，7，9，10）缺钙缺钙（3，5，6，8）v在上例中，显然生成的两种决策树的复杂性和分类意义相差很大.v由此可见，选择测试属性是决策树学习算法中需要研究的重要课题。CLS算法存在的问题算法存在的问题62（2）ID3算法算法qID3算法主要针对属性
27、选择问题，是决策树学习方法中最具影响和最为典型的算法。qID3使用信息增益度选择测试属性。使用信息增益度选择测试属性。q选择当前所有分割属性中，信息增益最大的属性作为测试属性，该属性最能消除不确定性。6364（2）ID3算法算法类比：生活工作中的决策（做/不做？）q我们总是倾向于选择最具有决定性意义的辅助条件进行判定。q如：打不打室外羽毛球？q是否刮风是最具有决定意义的因素。q如何度量信息量度量信息量的大小？65ID3 信息量大小的度量信息量大小的度量 Shannon在1948年提出的信息论理论中，指出事件ai的信息量I(ai)可如下度量：其中p(ai)表示事件ai发生的概率。假设有n个互不相
28、容的事件a1,a2,a3,.,an，则其平均的信息量可如下度量：66 上式中，对数底数可以为任何数，不同的取值对应了熵的不同单位。通常取2，并规定当p(ai)=0时，=0ID3 信息量大小的度量信息量大小的度量6768ID3-属性选择方法属性选择方法 设S为包含s个数据样本的集合，假定类别属性C具有m个不同值Ci(i=1,2,m)。设si是类Ci中的样本个数，则，对一个给定数据对象进行分类所需要的期望信息可由下式给出：其中，pi是任意样本属于类Ci的概率，按照si/S进行计算。Log函数是以2为底的函数。（6.1）H(x)=69（6.2）ID3-属性选择方法属性选择方法H(x/y)=70（6.
29、4）（6.3）ID3-属性选择方法属性选择方法I=H(X)-H(X/Y)71ID3-属性选择方法属性选择方法vGain(S,A)是属性A在集合S上的信息增益vGain(S,A)=Entropy(S)Entropy(S,A)vGain(S,A)越大，说明选择测试属性对分类提供的信息越多.ID3 属性属性选择选择方法方法72计数年龄收入学生信誉归类：买归类：买计算机？计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买
30、ID3算法示例算法示例v怎么建立决策树？怎么建立决策树？v谁是根节点？谁是根节点？v谁是下一层子节点谁是下一层子节点？为什么是它？为什么是它？73计数年龄收入学生信誉归类：买计算机归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第1步计算决策属性的熵步计算决策属性的熵决策属性决策属性“买计买计算机？算机？”该属性分两类：买/不买S1(买)=641 S2（不买）=383S=S1+S2=1024P1=64
31、1/1024=0.6260P2=383/1024=0.3740I(S1,S2)=I(641,383)=-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2)=0.9537ID3算法示例算法示例初始不初始不确定性确定性74计数年龄收入学生信誉归类：买计算机归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第2步计算条件属性的熵步计算条件属性的熵条件属性条件属性共有4个：分别是年龄
32、、收入、学生、信誉。分别计算不同属性的信息增益。ID3算法示例算法示例75计数年龄收入学生信誉归类：买计算机归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第2-1步步 计算年龄的熵计算年龄的熵年年龄龄共分三个组：青年、中年、老年1）青年：）青年：买与不买比例为128/256S1(买)=128 S2（不买）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(12
33、8,256)=-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2)=0.9183ID3算法示例算法示例76计数年龄收入学生信誉归类：买计算机归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第2-2步步 计算年龄的熵计算年龄的熵年龄共分三个组：青年、中年、老年2）中年：）中年：买与不买比例为256/0S1(买)=256 S2（不买）=0S=S1+S2=256P1=256/25
34、6P2=0/256I(S1,S2)=I(256，0)=-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2)=0ID3算法示例算法示例77计数年龄收入学生信誉归类：买计算机归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第2-3步计算年龄的熵步计算年龄的熵年龄共分三个组：青年、中年、老年3）老年：）老年：买与不买比例为125/127S1(买)=125 S2（不买）=127S=
35、S1+S2=252P1=125/252P2=127/252I(S1,S2)=I(125，127)=-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2)=0.9157ID3算法示例算法示例78计数年龄收入学生信誉归类：买计算机归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第2-4步步 计算年龄的熵计算年龄的熵年龄共分三个组：青年、中年、老年所占比例：青年组 384/1025
36、=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）ID3算法示例算法示例79计数年龄收入学生信誉归类：买计算机归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第3步步 计
37、算计算收入收入的熵的熵收入共分三个组：高、中、低E（收入）=0.9361收入信息增益=0.9537-0.9361 =0.0176 （2）ID3算法示例算法示例80计数年龄收入学生信誉归类：买计算机归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第4步步 计算计算学生学生的熵的熵学生共分二个组：学生、非学生E（学生）=0.7811年龄信息增益=0.9537-0.7811 =0.1726 （3）ID3算法
38、示例算法示例81计数年龄收入学生信誉归类：买计算机归类：买计算机？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）ID3算法示例算法示例82计数年龄收入学生信誉归类：买计算机归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低
39、是优不买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）ID3算法示例算法示例83计数年龄收入学生信誉归类：买计算机归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买年龄年龄
40、青年中年老年买/不买买买/不买叶子ID3算法示例算法示例84计数年龄收入学生信誉归类：买计算机归类：买计算机？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.9183ID3算法示例算法示例85计数年龄收入学生信誉归类：买计算机归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64
41、青中是优买如果选择收入收入作为节点分高、中、低平均信息期望（加权总和）：E(收入）=0.3333*0+0.5*0.9183+0.1667*0=0.4592Gain(收入)=I(128,256)-E(收入)=0.9183 0.4592=0.4591高：高：I(0,128)=0 比例:128/384=0.3333中：中：I(64,128)=0.9183 比例:192/384=0.5低：低：I(64,0)=0比例:64/384=0.1667 注意ID3算法示例算法示例86计数年龄收入学生信誉归类：买计归类：买计算机？算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买6
42、4老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买年龄年龄青年中年老年学生买信誉叶子否否是是优优良良买不买买/不买买叶子叶子叶子ID3算法示例算法示例87ID3算法实际应用算法实际应用-在电信行业应用实例（在电信行业应用实例（1）通过ID3算法来实现客户流失的预警分析，找出客户流失的特征，以帮助电信公司有针对性地改善客户关系，避免客户流失.利用决策树方法进行数据挖掘，一般有如下步骤：数据预数据预处理、决策树挖掘处理、决策树挖掘操作，模式评估和应用。88ID3算法实际应用算法实际应用-在电信行业应用
43、实例（在电信行业应用实例（1）v电信运营商的客户流失有三方面的含义：一是指客户从一个电信运营商转网到其他电信运营商，这是流失分析的重点；二是指客户月平均消费量降低，从高价值客户成为低价值客户。三指客户自然流失和被动流失。89ID3算法实际应用算法实际应用-在电信行业应用实例（在电信行业应用实例（1）v在客户流失分析中有两个核心变量：财务原因非财务原因、主动流失被动流失。v客户流失可以相应分为四种类型.v其中非财务原因主动流失非财务原因主动流失的客户往往是高价值的客户。他们会正常支付服务费用，并容易对市场活动有所响应。这种客户是电信企业真正需要保住的客户。90（1）数据）数据预处预处理理 数据挖
44、掘的处理对象是大量的数据，这些数据一般存储在数据库系统中（该用户相关数据存储在其CRM中），是长期积累的结果。但往往不适合直接挖掘，需要做数据的预处理工作，一般包括数据的选择(选择相关的数据)、净化(消除冗余数据)、转换、归约等。数据预处理工作准备是否充分，对于挖掘算法的效率乃至正确性都有关键性的影响。ID3算法实际应用算法实际应用-在电信行业应用实例（在电信行业应用实例（1）91（1）数据）数据预处预处理理 该公司经过多年的电脑化管理，已有大量的客户个人基本信息(文中简称为客户信息表)。在客户信息表中，有很多属性，如姓名用户号码、用户标识、用户身份证号码(转化为年龄)、在网时间（竣工时间）、
45、地址、职业、用户类别、客户流失（用户状态）等等，数据准备时必须除掉表中一些不必要的属性，一般可采用面向属性的归纳等方法去掉不相关或弱相关属性。ID3算法实际应用算法实际应用-在电信行业应用实例（在电信行业应用实例（1）921）属性删除：）属性删除：将有大量不同取值且无概化操作符的属性或者可用其它属性来代替它的较高层概念的那些属性删除。比如客户信息表中的用户标识、身份证号码等，它们的取值太多且无法在该取值域内找到概化操作符，应将其删除，得到表1。表1 客户信息表年龄学历职业缴费方式在网时长费用变化率客户流失58大学公务员托收1310%NO47高中工人营业厅缴费942%NO26研究生公务员充值卡2
46、63%YES28大学公务员营业厅缴费52.91%NO32初中工人营业厅缴费32.3%NO42高中无业人员充值卡2100%YES68初中无业人员营业厅缴费92.3%NOID3算法实际应用算法实际应用-在电信行业应用实例（在电信行业应用实例（1）932）属性概化：）属性概化：用属性概化阈值控制技术沿属性概念分层上卷或下钻进行概化。文化程度分为3类：W1初中以下(含初中)，W2高中(含中专)，W3大学(专科、本科及以上)；职业类别：按工作性质来分共分3类：Z1一Z3；缴费方式：托收：T1,营业厅缴费：T2,充值卡：T3。ID3算法实际应用算法实际应用-在电信行业应用实例（在电信行业应用实例（1）94
47、2）属性概化：）属性概化：连续型属性概化为区间值。表中年龄、费用变化率和在网时间为连续型数据，由于建立决策树时，用离散型数据进行处理速度最快，因此对连续型数据进行离散化处理.根据专家经验和实际计算信息增益，在“在网时长”属性中，通过检测每个划分，得到在阈值为5年时信息增益最大，从而确定最好的划分是在5年处，则这个属性的范围就变为5：H1,H2。而在“年龄”属性中，信息增益有两个锋值，分别在40和50处，因而该属性的范围变为40-50即变为青年，中年，老年：N1,N2,N3；费用变化率：指（当月话费近3个月的平均话费）/近3个月的平均话费）0，F1:0,则在事件B 已经发生的条件下，事件A发生的
48、条件概率：u联合概率：若对任意两事件A、B都有P(A)0，P(B)0,则：P(AB)=P(A)P(BA)=P(B)P(AB)u边际概率：若A1、A2构成互斥和完整的两个事件，A1和A2 中的一个出现是事件B发生的必要条件，则事件B的边际概率公式为（全概率公式）：P(B)=P(B A1)P(A1)+P(B A2)P(A2)148贝叶斯定理贝叶斯定理u贝叶斯定理是关于随机事件A和B的条件概率和边缘概率的一则定理。u通常，事件A在事件B发生的条件下的概率，与事件B在事件A发生的条件下的概率是不一样的，然而，这两者是有确定的关系的，贝叶斯定理就是这种关系的陈述。149贝叶斯定理贝叶斯定理由前面三个概率
49、公式可以得到贝叶斯公式：全概率：P(B)=P(B A1)P(A1)+P(B A2)P(A2)条件概率：条件概率：联合概率：P(AB)=P(A)P(BA)=P(B)P(AB)150贝叶斯定理贝叶斯定理两个事件的贝叶斯公式：u若A1、A2构成互斥和完整的两个事件，A1和A2 中的一个出现是事件B发生的必要条件，则两个事件的贝叶斯公式：151贝叶斯定理贝叶斯定理n个事件的贝叶斯 公式：u假定存在一个互斥和完整的事件A1,A2,An，Ai中的某一个出现是事件B发生的必要条件，则n个事件的贝叶斯公式：152贝叶斯定理贝叶斯定理在贝叶斯定理中，每个名词都有约定俗成的名称：uP(A)：事件A的先验概率或边缘
50、概率。“先验”指其不考虑任何B方面的因素。uP(AB)：事件A的后验概率，即已知B发生后A的条件概率。uP(BA)：事件B的后验概率，即已知A发生后B的条件概率。uP(B)：是事件B的先验概率或边缘概率。示例示例1 1背景：背景：办公室新来了一个雇员小王，小王是好人还是坏人，大家都在猜测。按人们的主观意识，一个人是好人还是坏人的概率均为0.5，坏人总是要做坏事，好人总是做好事，偶尔也会做一件坏事。一般好人做好事的概率是0.9，坏人做好事的概率是0.2.一天，小王做了一件好事，则小王是好人的概率有多大，小王究竟为好人还是坏人？153示例示例1 1154155 旅客搭乘飞机必须经电子仪器检查是否身