第七章 分类与预测

《数据挖掘》主讲：王名扬信息与计算机工程学院2引言—要挖掘知识的类型概念描述：特征化和比较；关联规则；

分类/预测；聚类分析；其他的数据挖掘任务。引言根据现有的知识，我们得到了一些关于爬行动物和鸟类的信息，我们能否对新发现的物种，比如动物A，动物B进行分类？动物种类体型翅膀数量脚的只数是否产蛋是否有毛类别狗中04否是爬行动物猪大04否是爬行动物牛大04否是爬行动物麻雀小22是是鸟类天鹅中22是是鸟类大雁中22是是鸟类动物A大02是无？动物B中22否是？31一月20234分类是数据挖掘中重要的任务分类的目的是学会一个分类器（分类函数或模型），该分类器能把待分类的数据映射到给定的类别中。分类可用于预测。从历史数据纪录中自动推导出对给定数据的推广描述，从而能对未来数据进行类预测。31一月20235分类方法的类型从使用的主要技术上看，可以把分类方法归结为以下几种类型：基于距离的分类方法决策树分类方法贝叶斯分类方法。本章主要围绕这几种分类方法展开。

第6章分类与预测6.1分类与预测的基本知识6.2基于距离的分类算法6.3决策树分类方法6.4贝叶斯分类方法6.5规则归纳方法*

第6章6.1分类和预测的基本知识什么是分类？预测？分类和预测的基本问题1.分类？预测？10基本概念分类和预测是两种数据分析的形式，可用于提取描述重要数据类的模型或预测未来的数据趋势：分类（classification）：用于预测数据对象的分类标号（或离散值），如，通过构造分类模型对银行贷款进行风险评估（安全或危险）；预测（predication）：用于预测数据对象的连续取值，如，建立预测模型利用顾客收入与职业（参数）预测其可能用于购买计算机设备的支出大小。11数据分类过程数据分类是一个两步的过程：1）建立分类模型：机器学习过程，通过某种分类算法对训练集进行训练，得到分类模型；“有指导的学习”、“有监督的学习”假定每个元组属于一个预定义的类，由一个称为类标号属性的属性确定；训练数据集：为建立分类模型而被分析的数据元组。12分类过程的第一步：学习建模13数据分类过程数据分类是一个两步的过程：2）使用模型进行分类：测试数据集：用于评估模型的预测准确率。模型在测试集上的准确率是正确被模型分类的测试样本所占的百分比。如认为模型的准确率可以接受，就可以用它来对类标号未知的数据元组或对象进行分类。14分类过程的第二步：分类测试15分类过程示意图有指导的学习VS.无指导的学习有指导的学习（用于分类）训练样本的类标号已知；新数据使用训练数据集中得到的规则进行分类无指导的学习（用于聚类）训练样本的类标号未知；通过一系列的度量、观察，试图确立数据中的类或聚类的存在17数据预测预测：构造和使用模型评估无标号样本类，或评估给定样本可能具有的属性值或值区间与分类区别：二者是两类主要的预测问题。

分类是预测离散或标号值；预测是预测连续或有序值；观点：用预测法预测类标号为分类；用预测法预测连续值（一般用回归法）为预测。18示例背景：假定已建立AllElectronics公司的邮寄清单数据库。邮寄清单用于分发介绍新产品和降价信息材料。数据库描述顾客的属性，包括姓名、年龄、收入、职业和信誉度，并按照顾客是否在该公司购买计算机进行分类。19示例分类模型：

假定新的顾客添加到数据库中，由于向每位顾客分发促销材料费用很高，因此，可以根据数据库中已有顾客信息构建分类模型，用以预测需向哪些顾客分发材料。预测模型：

假定想预测在一个财政年度，一个顾客将在AllElectronics进行的主要的购买的数量，则可以构建一个预测模型。2.分类和预测的基本问题？21问题(1)：数据准备1）准备分类和预测的数据：数据的预处理数据清理：噪声（平滑技术）；空缺值（统计手段）相关性分析（特征选择）：删除不相关和冗余属性，如银行贷款申请时填写的星期数，可能与贷款是否申请成功无关；数据变换：数据离散化（数据概化）：如属性“收入”的数值就可以被离散化为若干区间，如低、中等和高；数据规范化：将给定属性的值按比例缩放至较小的区间，如[0,1]。22问题(2)：评估分类模型2）评估方法：对用于分类或预测的方法或模型进行评估预测的准确率：模型正确预测未知对象类别或数值的能力；速度：1）建立模型的时间；2）使用模型的时间强壮性（鲁棒性）：处理噪声和空缺值的能力；可伸缩（扩展）性：处理大型数据及构造模型的能力；可理解性：模型的可理解能力；规则的优越性：1）判定树的大小；2）分类规则的简洁性。6.2基于距离的分类算法基本思想？

几种常见的距离分类算法？1.基于距离分类的基本思想？31一月202325基于距离的分类算法的思路定义：给定一个数据库D={t1，t2，…，tn}和一组类C={C1，…，Cm}。假定每个元组包括一些数值型的属性值：ti={ti1，ti2，…，tik}，每个类也包含数值性属性值：Cj={Cj1，Cj2，…，Cjk}，则分类问题是要分配每个ti到满足如下条件的类Cj：

sim(ti，Cj)>=sim(ti，Ci)，Ci∈C，Ci≠Cj，其中sim(ti，Cj)被称为相似性。31一月202326基于距离的分类算法的思路在实际的计算中往往用距离来表征：距离越近，相似性越大；距离越远，相似性越小。如何度量距离？欧几里得距离；曼哈坦距离；明考斯基距离；加权的明考斯基距离。（一）欧几里得距离欧式距离由对应元素间差值平方和的平方根所表示，即：

如何度量距离？（二）曼哈顿距离对应元素间差值绝对值的和表示，即：

欧几里得距离与曼哈顿距离的共同点：

(1)即距离是一个非负的数值

(2)自身的距离为0

(3)即距离函数具有对称性

(4)即距离函数满足三角不等式如何度量距离？(三)明可夫斯基距离

是欧几里得距离和曼哈顿距离的概化其中p是一个正整数：当p=1时，表示曼哈顿距离；当p=2时，表示欧几里得距离。(四)加权的明可夫斯基距离

如果对每一个变量根据其重要性赋予一个权重，就得到加权的明考斯基距离。如何度量距离？31一月202330基于距离的分类算法的思路在实际的计算中往往用距离来表征：距离越近，相似性越大；距离越远，相似性越小。距离的计算方法有多种，最常用的是通过计算样本到每个类中心的距离来完成。31一月202331基于距离的分类算法的一般性描述算法计算每个元组到各个类中心的距离，从而可以找出离它的最近的类中心，得到确定的类别标记。算法基于距离的分类算法输入：每个类的中心C1，…，Cm；待分类的元组t。输出：输出类别c。（1）dist=∞；//距离初始化（2）FORi:=1tomDO（3） IFdis(ci，t)<distTHENBEGIN（4） c←i；（5） dist←dist(ci，t)；（6） END.31一月202332基于距离的分类方法的直观解释（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-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类。2几种常见的距离分类算法？36几种常见的距离分类算法

（1）k-近邻算法；

（2）K-means算法（聚类）；

（3）K-mediods算法（聚类）。31一月202337（1）K-近邻分类算法K-近邻分类算法（KNearestNeighbors，简称KNN）通过计算每个训练数据到待分类元组的距离，取和待分类元组距离最近的K个训练数据，K个数据中哪个类别的训练数据占多数，则待分类元组就属于哪个类别。31一月202338（1）K-近邻分类算法算法4-2K-近邻分类算法输入：训练数据T；近邻数目K；待分类的元组t。输出：输出类别c。（1）N=；（2）FOReachd∈TDOBEGIN（3）IF|N|≤KTHEN（4）N=N∪{d}；（5）ELSE（6） IF

u∈Nsuchthatsim(t，u)〈sim(t，d)THEN

BEGIN（7） N=N-{u}；（8） N=N∪{d}；（9） END（10）END（11）c=classtowhichthemostu∈N.

KNN的直观解释1、定义的直观形式：找出与目标最接近的K个样本；将目标划分到找出的K个样本中出现最频繁的类。2、K的直观形式：以目标样本为中心；划出一个刚好包含K个样本的圆；当K增大时，圆半径增大。KNN的直观解释3、直观的例子手写识别记录手写体特征；计算手写体与标准汉字的相似度；根据相似度（距离），找出K个备选集；选择一个正确汉字人种识别欧洲人的鼻子、亚洲人的眼睛非洲人的肤色、亚洲人的头发形象的例子KNN的分类思想如果它走路像鸭子,叫声也像鸭子,那么它可能就是只鸭子TrainingRecordsTestRecordComputeDistanceChoosekofthe“nearest”recordsKNN的特点1、非参数统计方法不需引入参数回归分析是参数统计方法2、k的选择K=1时，将待分类样本划入与其最接近的样本的类；K=|X|时，仅根据训练样本进行频率统计，将待分类样本划入最多的类；K需要合理选择，太小容易受干扰、太大增加计算复杂性3、算法的复杂度维数灾难：当维数增加时，算法的复杂度会急剧增加一般采用降维处理6.3决策树分类算法

决策树的基本概念？决策树生成算法？剪枝方法？提取分类规则？1.决策树的基本概念？决策树基本概念解决分类问题的一般方法TIDA1A2A3类1Y100LN2N125SN3Y400LY4N415MN学习算法学习模型模型应用模型TIDA1A2A3类1Y100L？2N125S？3Y400L？4N415M？训练集（类标号已知）检验集（类标号未知）归纳推论46基本概念

决策树（decisiontree）：决策树是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策树对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。年龄？学生？信誉？买青中老否是优良不买买买不买47决策树的基本组成

决策树的基本组成决策树是类似流程图的倒立的树型结构。最顶层节点为根节点，是整个决策树的开始；树的每个内部节点表示在一个属性上的测试，其每个分支代表一个测试输出；树的每个叶节点代表一个类别。年龄？学生？信誉？买青中老否是优良不买买买不买48基本概念决策树的生成包括两个过程：（1）树的建立首先所有训练样本都在根节点；依据所选的属性循环地划分样本。（2）树剪枝（treepruning）：在决策树构造时，许多分支可能反映的是训练数据中的噪声或孤立点。树剪枝就是识别并消除这类分支，以提高在未知数据上分类的准确性。492.决策树的生成算法？51决策树的生成算法基本的决策树生成算法是一个贪心算法，采用自上而下、分而治之的递归方式来构造。决策树上的各个分支是在对数据不断分组的过程中逐渐生长出来的。首先，选择一个属性作为根节点，然后把该属性的每一个可能的值作为子节点，这样就把整个训练集分成了几个子集，根节点属性的每个取值都对应着一个子集，然后递归应用到每个子树上进行进一步划分，直到对所有数据的继续分组不再有意义时，决策树的生长过程宣告结束，此时便生成了一棵完整的决策树。其中，测试属性的选择是构建决策树的关键环节，不同的决策树算法在此使用的技术都不尽相同。52决策树的生成算法注意：在决策树算法中，所有属性均为符号值，即离散值，因此若有取连续值的属性，必须首先进行离散化。53决策树的生成算法常见的有如下几种决策树生成算法：

CLS;ID3;C4.5;CART。（1）CLS（ConceptLearningSystem）算法

CLS算法是早期的决策树学习算法。它是许多决策树学习算法的基础。

CLS基本思想

从一棵空决策树开始，选择某一属性（分类属性）作为测试属性。该测试属性对应决策树中的决策结点。根据该属性的值的不同，可将训练样本分成相应的子集，如果该子集为空，或该子集中的样本属于同一个类，则该子集为叶结点，否则该子集对应于决策树的内部结点，即测试结点，需要选择一个新的分类属性对该子集进行划分，直到所有的子集都为空或者属于同一类。人员眼睛颜色头发颜色所属人种1黑色黑色黄种人2蓝色金色白种人3灰色金色白种人4蓝色红色白种人5灰色红色白种人6黑色金色混血7灰色黑色混血8蓝色黑色混血CLS算法人员眼睛颜色头发颜色所属人种1黑色黑色黄种人2蓝色金色白种人3灰色金色白种人4蓝色红色白种人5灰色红色白种人6黑色金色混血7灰色黑色混血8蓝色黑色混血CLS算法-决策树的构建眼睛颜色[1,6][2,4,8][3,5,7]黑色蓝色灰色不属于同一类，非叶结点眼睛颜色头发颜色头发颜色头发颜色黑色兰色灰色CLS算法黄种人[1]混血[6]白种人[2]白种人[4]混血[8]白种人[3]白种人[5]混血[7]黑色金色金色红色黑色金色红色黑色CLS算法1）

生成一颗空决策树和一张训练样本属性集;2）

若训练样本集T中所有的样本都属于同一类，则生成结点T，并终止学习算法；否则3）

根据某种策略从训练样本属性表中选择属性A作为测试属性，

生成测试结点A4）

若A的取值为v1,v2,…,vm，

则根据A的取值的不同，将T划分成m个子集T1,T2,…,Tm;5）

从训练样本属性表中删除属性A;6）

转步骤2,对每个子集递归调用CLS。CLS算法存在的问题在步骤3中，根据某种策略从训练样本属性表中选择属性A作为测试属性，没有规定选择测试属性的标准和依据。实践表明，测试属性集的组成以及测试属性的先后对决策树的学习具有举足轻重的影响。举例：下表为调查学生膳食结构和缺钙情况的关系，其中1表示包含食物，0表示不包含。学生鸡肉猪肉牛肉羊肉鱼肉鸡蛋青菜番茄牛奶健康情况1011010101不缺钙2000011111不缺钙3111110100缺钙4110011001不缺钙5100111000缺钙6111001010缺钙7010001111不缺钙8010001111缺钙9010001111不缺钙10101111011不缺钙学生膳食结构和缺钙调查表CLS算法存在的问题采用不同的测试属性及其先后顺序将会生成不同的决策树鸡肉猪肉猪肉牛肉牛肉牛肉不缺钙（2）缺钙（3，6）不缺钙（4）不缺钙（10）缺钙（5）不缺钙（1）鱼肉缺钙（5）不缺钙（7，9）是否是否否否否否否是是是是是CLS算法存在的问题牛奶不缺钙（1，2，4，7，9，10）缺钙（3，5，6，8）在上例中，显然生成的两种决策树的复杂性和分类意义相差很大.由此可见，选择测试属性是决策树学习算法中需要研究的重要课题。CLS算法存在的问题（2）ID3算法ID3算法主要针对属性选择问题，是决策树学习方法中最具影响和最为典型的算法。ID3使用信息增益度选择测试属性。选择当前所有分割属性中，信息增益最大的属性作为测试属性，该属性最能消除不确定性。64（2）ID3算法类比：生活工作中的决策（做/不做？）我们总是倾向于选择最具有决定性意义的辅助条件进行判定。如：打不打室外羽毛球？是否刮风是最具有决定意义的因素。如何度量信息量的大小？ID3–信息量大小的度量Shannon在1948年提出的信息论理论中，指出事件ai的信息量I(

ai)可如下度量：其中p(ai)表示事件ai发生的概率。假设有n个互不相容的事件a1,a2,a3,….,an，则其平均的信息量可如下度量：上式中，对数底数可以为任何数，不同的取值对应了熵的不同单位。通常取2，并规定当p(ai)=0时，=0ID3–信息量大小的度量68ID3-属性选择方法设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.4）（6.3）ID3-属性选择方法I=H(X)-H(X/Y)71ID3-属性选择方法Gain(S,A)是属性A在集合S上的信息增益Gain(S,A)=Entropy(S)

–Entropy(S,A)Gain(S,A)越大，说明选择测试属性对分类提供的信息越多.ID3–属性选择方法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买ID3算法示例怎么建立决策树？谁是根节点？谁是下一层子节点？为什么是它？计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第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.9537ID3算法示例初始不确定性计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第2步计算条件属性的熵条件属性共有4个：分别是年龄、收入、学生、信誉。分别计算不同属性的信息增益。ID3算法示例计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第2-1步计算年龄的熵年龄共分三个组：

青年、中年、老年1）青年：买与不买比例为128/256S1(买)=128S2（不买）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9183ID3算法示例计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第2-2步计算年龄的熵年龄共分三个组：

青年、中年、老年2）中年：买与不买比例为256/0S1(买)=256S2（不买）=0S=S1+S2=256P1=256/256P2=0/256I(S1,S2)=I(256，0)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0ID3算法示例计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第2-3步计算年龄的熵年龄共分三个组：

青年、中年、老年3）老年：买与不买比例为125/127S1(买)=125S2（不买）=127S=S1+S2=252P1=125/252P2=127/252I(S1,S2)=I(125，127)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9157ID3算法示例计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买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）ID3算法示例计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第3步计算收入的熵收入共分三个组：高、中、低E（收入）=0.9361收入信息增益=0.9537-0.9361=0.0176（2）ID3算法示例计数年龄收入学生信誉归类：买计算机？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算法示例计数年龄收入学生信誉归类：买计算机？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算法示例计数年龄收入学生信誉归类：买计算机？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）ID3算法示例计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买年龄青年中年老年买/不买买买/不买叶子ID3算法示例计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买青年买与不买比例为128/256S1(买)=128S2（不买）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9183ID3算法示例计数年龄收入学生信誉归类：买计算机？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.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算法示例计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买年龄青年中年老年学生买信誉叶子否是优良买不买买/不买买叶子叶子叶子ID3算法示例ID3算法实际应用-在电信行业应用实例（1）

通过ID3算法来实现客户流失的预警分析，找出客户流失的特征，以帮助电信公司有针对性地改善客户关系，避免客户流失.利用决策树方法进行数据挖掘，一般有如下步骤：数据预处理、决策树挖掘操作，模式评估和应用。ID3算法实际应用-在电信行业应用实例（1）电信运营商的客户流失有三方面的含义：一是指客户从一个电信运营商转网到其他电信运营商，这是流失分析的重点；二是指客户月平均消费量降低，从高价值客户成为低价值客户。三指客户自然流失和被动流失。ID3算法实际应用-在电信行业应用实例（1）在客户流失分析中有两个核心变量：财务原因／非财务原因、主动流失／被动流失。客户流失可以相应分为四种类型.其中非财务原因主动流失的客户往往是高价值的客户。他们会正常支付服务费用，并容易对市场活动有所响应。这种客户是电信企业真正需要保住的客户。（1）数据预处理

数据挖掘的处理对象是大量的数据，这些数据一般存储在数据库系统中（该用户相关数据存储在其CRM中），是长期积累的结果。但往往不适合直接挖掘，需要做数据的预处理工作，一般包括数据的选择(选择相关的数据)、净化(消除冗余数据)、转换、归约等。数据预处理工作准备是否充分，对于挖掘算法的效率乃至正确性都有关键性的影响。ID3算法实际应用-在电信行业应用实例（1）（1）数据预处理

该公司经过多年的电脑化管理，已有大量的客户个人基本信息(文中简称为客户信息表)。在客户信息表中，有很多属性，如姓名用户号码、用户标识、用户身份证号码(转化为年龄)、在网时间（竣工时间）、地址、职业、用户类别、客户流失（用户状态）等等，数据准备时必须除掉表中一些不必要的属性，一般可采用面向属性的归纳等方法去掉不相关或弱相关属性。ID3算法实际应用-在电信行业应用实例（1）1）属性删除：

将有大量不同取值且无概化操作符的属性或者可用其它属性来代替它的较高层概念的那些属性删除。比如客户信息表中的用户标识、身份证号码等，它们的取值太多且无法在该取值域内找到概化操作符，应将其删除，得到表1。

表1客户信息表年龄学历职业缴费方式在网时长费用变化率客户流失58大学公务员托收1310%NO47高中工人营业厅缴费942%NO26研究生公务员充值卡263%YES28大学公务员营业厅缴费52.91%NO32初中工人营业厅缴费32.3%NO42高中无业人员充值卡2100%YES68初中无业人员营业厅缴费92.3%NOID3算法实际应用-在电信行业应用实例（1）2）属性概化：用属性概化阈值控制技术沿属性概念分层上卷或下钻进行概化。文化程度分为3类：W1初中以下(含初中)，W2高中(含中专)，W3大学(专科、本科及以上)；职业类别：按工作性质来分共分3类：Z1一Z3；缴费方式：托收：T1,营业厅缴费：T2,充值卡：T3。ID3算法实际应用-在电信行业应用实例（1）2）属性概化：连续型属性概化为区间值。表中年龄、费用变化率和在网时间为连续型数据，由于建立决策树时，用离散型数据进行处理速度最快，因此对连续型数据进行离散化处理.根据专家经验和实际计算信息增益，在“在网时长”属性中，通过检测每个划分，得到在阈值为5年时信息增益最大，从而确定最好的划分是在5年处，则这个属性的范围就变为｛<=5,>5：H1,H2｝。而在“年龄”属性中，信息增益有两个锋值，分别在40和50处，因而该属性的范围变为{<=40,>40-<=50,>50}即变为{青年，中年，老年：N1,N2,N3}；费用变化率：指（（当月话费－近3个月的平均话费）/近3个月的平均话费）×％>0，F1:<＝30%，F2：30%-99%,F3:＝100%变为｛F1,F2,F3｝。

ID3算法实际应用-在电信行业应用实例（1）表2转化后的客户信息表年龄学历职业缴费方式开户时间费用变化率客户流失N3W3Z1T1H2F1NON2W2Z2T2H2F2NON1W3Z1T3H1F2YESN1W3Z1T2H1F1NON1W1Z2T2H1F1NON2W2Z3T3H1F3YESN3W1Z3T1H2F1NOID3算法实际应用-在电信行业应用实例（1）YESNO年龄职业YES缴费方式YESYESNOYSESNONO在网时长NOF1F2F3N1N2N3T1T2T3Z1Z2Z3H1H2费用变化率

在图中，NO表示客户不流失，YES表示客户流失。从图可以看出，客户费用变化率为100%的客户肯定已经流失；而费用变化率低于30%的客户；即每月资费相对稳定的客户一般不会流失，费用变化率在30%～99%的客户有可能流失，其中年龄在40～50岁之间的客户流失的可能性非常大，而年龄低于40岁的客户，用充值卡缴费的客户和在网时间较短的客户容易流失；年龄较大的客户，则工人容易流失。ID3算法实际应用-在电信行业应用实例（1）ID3算法小结ID3算法是一种经典的决策树学习算法，由Quinlan于1979年提出。ID3算法的基本思想是，以信息熵为度量，用于决策树节点的属性选择，每次优先选取信息量最多的属性，亦即能使熵值变为最小的属性，以构造一棵熵值下降（不确定性降低）最快的决策树，到叶子节点处的熵值为0。此时，每个叶子节点对应的实例集中的实例属于同一类。ID3算法小结优点：算法简单；易于理解缺点：偏向分割属性中取值多的一个；只能处理离散属性；ID3不包括树剪枝，易受噪声和波动影响；不易对变化的数据集进行学习。（3）C4.5算法ID3缺点1：偏向分割属性中取值多的一个原因：分割属性取值越多，每个值对应的子集规模越小。极限情况下，每个子集内只有一个单元（行），则它的信息增益必然最高（对不确定的消除达到最大）。例如，用身份证号区别“是否相亲成功”，显然没有任何意义，但是确实符合ID3算法。解决方法：引入增益比例101“相亲”（3）C4.5算法多取值个数非常多的情况？104对取值个数非常少的情况如何？105G(X,Y)106C4.5算法如，只有一个取值的情况排除取值个数很多的情况107108对取值按照由小到大的顺序排序：109110111112113114115116117118119融合（4）CART算法CART：ClassificationandRegressionTree分类回归树采用基于最小距离的基尼指数估计函数；生成二叉树。121122123124125126127128用测试集2.决策树剪枝？1301311321333.提取分类规则？135由决策树提取分类规则决策树所表示的分类知识可以被抽取出来，并用IF-THEN的分类规则的形式表示。

从决策树的根节点到任一个叶节点所形成的一条路径构成一条分类规则。

其中，沿着决策树的一条路径所形成的属性-值对形成分类规则的前件（IF部分）的一个合取项；叶节点所标记的类别构成规则的后件（THEN部分）。IF-THEN分类规则表达方式易于被人理解，尤其是当决策树较大时，优势更加突出。136示例137示例1386.4贝叶斯分类方法贝叶斯定理？朴素贝叶斯分类？贝叶斯信念网络？1.贝叶斯定理？141贝叶斯分类方法（Bayes）贝叶斯分类是统计学分类方法，可预测类别所属的概率，如：一个数据对象属于某个类别的概率。

贝叶斯分类的基础是贝叶斯定理。

贝叶斯定理（Bayestheorem）：是概率论中的一个结果，跟随机变量的条件概率以及边缘（条件）概率分布有关。142在实际中，人们常会根据不确定性信息作出推理和决策，此时往往需要对各种结论出现的概率进行估计，这类推理称为概率推理。

贝叶斯推理的问题是条件概率推理问题。贝叶斯分类方法（Bayes）143概率论基本知识回顾概率论是研究随机性或不确定性等现象的数学。更精确的说，是用来模拟实验在同一环境下会产生不同结果的情状。随机事件；事件间的关系；概率定义；条件概率。144（1）随机事件随机实验：随机实验是一个可观察结果的人工或自然的过程，其产生的结果可能不止一个，且不能事先确定会产生什么结果。样本空间：样本空间是一个随机实验的全部可能出现的结果的集合，通常记作Ω，Ω中的点（即一个可能出现的实验结果）称为样本点，通常记作ω。随机事件：随机事件是一个随机实验的一些可能结果的集合，是样本空间的一个子集。常用大写字母A,B,C,…表示。145（2）事件间的关系146（3）概率定义定义：设Ω为一个随机实验的样本空间，对Ω上的任意事件A，规定一个实数与之对应，记为P(A)，满足以下三条基本性质，称为事件A发生的概率：147（4）条件概率条件概率：设A、B是两个随机事件，且P(B)>0,则在事件B已经发生的条件下，事件A发生的条件概率：联合概率：若对任意两事件A、B都有P(A)>0，P(B)>0,则：P(AB)=P(A)P(B\A)=P(B)P(A\B)边际概率：若A1、A2构成互斥和完整的两个事件，A1和A2

中的一个出现是事件B发生的必要条件，则事件B的边际概率公式为（全概率公式）：P(B)=P(B\A1)P(A1)+P(B\A2)P(A2)148贝叶斯定理贝叶斯定理是关于随机事件A和B的条件概率和边缘概率的一则定理。通常，事件A在事件B发生的条件下的概率，与事件B在事件A发生的条件下的概率是不一样的，然而，这两者是有确定的关系的，贝叶斯定理就是这种关系的陈述。149贝叶斯定理由前面三个概率公式可以得到贝叶斯公式：全概率：P(B)=P(B\A1)P(A1)+P(B\A2)P(A2)条件概率：联合概率：P(AB)=P(A)P(B\A)=P(B)P(A\B)150贝叶斯定理两个事件的贝叶斯公式：若A1、A2构成互斥和完整的两个事件，A1和A2

中的一个出现是事件B发生的必要条件，则两个事件的贝叶斯公式：151贝叶斯定理n个事件的贝叶斯公式：假定存在一个互斥和完整的事件A1,A2,…,An，Ai中的某一个出现是事件B发生的必要条件，则n个事件的贝叶斯公式：152贝叶斯定理在贝叶斯定理中，每个名词都有约定俗成的名称：P(A)：事件A的先验概率或边缘概率。“先验”指其不考虑任何B方面的因素。P(A\B)：事件A的后验概率，即已知B发生后A的条件概率。P(B\A)：事件B的后验概率，即已知A发生后B的条件概率。P(B)：是事件B的先验概率或边缘概率。示例1背景：办公室新来了一个雇员小王，小王是好人还是坏人，大家都在猜测。按人们的主观意识，一个人是好人还是坏人的概率均为0.5，坏人总是要做坏事，好人总是做好事，偶尔也会做一件坏事。一般好人做好事的概率是0.9，坏人做好事的概率是0.2.一天，小王做了一件好事，则小王是好人的概率有多大，小王究竟为好人还是坏人？示例1155旅客搭乘飞机必须经电子仪器检查是否身上携带金属物品。如果携带金属，仪器会发出声音的概率是97%，但身上无金属物品仪器会发出声音的概率是5%。

已知一般乘客身上带有金属物品的概率是30%，若某旅客经过仪器检查时发出声音，请问他身上有金属物品的概率是多少？

2023/1/31示例21562023/1/31解：设C1=“有金属物”，X=“仪器会发声”，则157贝叶斯分类设X为一个类别未知的数据样本，设H为某种假设，如：数据样本X属于某特定的类C。对于分类问题，我们希望确定P(H\X)，即给定观测数据样本X，假定H成立的概率。贝叶斯分类

设x∈Ω是一个类别未知的数据样本，cj为某个类别，若数据样本x属于一个特定的类别cj，那么分类问题就是决定P(cj|x)，即在获得数据样本x时，确定x的最佳分类。

先验概率P(cj)P(cj|x)=P(x|cj)P(cj)P(x)

后验概率P(x|cj)

后验概率P(cj|x)贝叶斯分类先验概率P(cj)

P(cj)为类cj的先验概率(priorprobability)，它反映了我们所拥有的关于cj是正确分类的背景知识。通常可以用样例中属于cj的样例数|cj|比上总样例数|D|来近似，即:

后验概率P(x|cj)指的是当已知类别为cj的条件下，样本x出现的概率。后验概率P(x|cj)若设x=<a1,a2…am>，且属性值相互条件独立，即在属性间，不存在依赖关系，则P(x|cj)=P(a1,a2…am|

cj)后验概率P(cj|x)

即给定数据样本x时cj成立的概率，而这正是我们所感兴趣的。

P(cj|x

)被称为C的后验概率（posteriorprobability），因为它反映了在得到数据样本x后cj成立的置信度.贝叶斯分类计算Pmax

(ci|x)=maxP(cj|x)j∈(1,|C|)则Pmax

(ci|x)称为最大后验概率，并将x分到ci类中.2.朴素贝叶斯分类？朴素贝叶斯分类的工作过程（1）每个数据样本X用一个n维特征向量：X={x1,x2,…,xn}表示，分别描述对n个属性(A1,A2,…,An)的具体取值；（2）假定共有m个不同类别，C1,C2,…,Cm。给定一个类别未知的数据样本X，分类法将在已知X情况下，将X赋于后验概率最大的那个类别。即，朴素贝叶斯分类将类别未知的样本X归属到类别Ci，当且仅当：即，最大化P(Ci\X)。其中的类别Ci称为最大后验假定。根据贝叶斯定理，有：朴素贝叶斯分类的工作过程（3）由于P(X)对于所有的类别均是相同的，因此只需要计算P(X\Ci)P(Ci)取最大即可。如果各类别的先验概率未知，通常假定这些类是等概率的，即：P(C1)=P(C2)=…=P(Cm)。这样变成只需要对P(X\Ci)求最大，否则就要P(X\Ci)P(Ci)取最大。否则，一般可以通过P(Ci)=si/s进行估算，其中si为训练样本集合中类别Ci的个数，s为整个训练样本集合的大小。朴素贝叶斯分类的工作过程（4）对于包含多个属性的数据集，直接计算P(X\Ci)的运算量是非常大的。为实现对P(X\Ci)的有效估算，朴素贝叶斯分类通常假设各属性是相互独立的，即在属性间，不存在依赖关系，则对于给定的类别Ci

，有：而P(x1\Ci),P(x2\Ci),…,P(xn\Ci)的值，可以由训练样本集进行估算。具体处理如下：朴素贝叶斯分类的工作过程1）如果Ak是符号属性，则P(xk\Ci)=sik/si，：其中sik为训练样本中类别为Ci且属性Ak取值vk的样本数，si为训练样本中类别为Ci的样本数。朴素贝叶斯分类的工作过程朴素贝叶斯分类的工作过程（5）为预测一个未知样本X的类别，对每个类Ci，计算P(X\Ci)P(Ci)。则，样本X被指派到类Ci，当且仅当：P(X\Ci)P(Ci)>P(X\Cj)P(Cj),朴素贝叶斯分类的效果研究表明，与决策树和神经网络分类器相比，贝叶斯分类器在某些情况下具有更好的分类效果。但必须满足某些假定条件，如要求各属性间是相互独立的。172示例示例背景：

给定与决策树归纳相同的训练数据集，希望使用朴素贝叶斯分类预测未知样本的类标号。基本信息：1）数据样本用age,income,student,credit-rating描述。类标号属性buys_comp