数据挖掘分类(课堂PPT)课件(PPT 106页).pptx

1、第三章第三章 分类方法分类方法 内容提要内容提要n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n实值预测 n与分类有关的问题 2022-7-311.第1页，共106页。分类的流程 n根据现有的知识，我们得到了一些关于爬行动物和鸟类的信息，我们能否对新发现的物种，比如动物A，动物B进行分类？2022-7-312.第2页，共106页。分类的流程 n步骤一：将样本转化为等维的数据特征（特征提取）。n所有样本必须具有相同数量的特征n兼顾特征的全面性和独立性2022-7-313.第3页，共106页。分类的流程 n步骤二：选择与类别相关的特征（特征选择）。n比如，绿色代表与

2、类别非常相关，黑色代表部分相关，灰色代表完全无关2022-7-314.第4页，共106页。分类的流程 n步骤三：建立分类模型或分类器（分类）。n分类器通常可以看作一个函数，它把特征映射到类的空间上iiniiiyxxxxf),.,(3212022-7-315.第5页，共106页。如何避免过度训练 n分类也称为有监督学习(supervised learning),与之相对于的是无监督学习(unsupervised learning),比如聚类。n分类与聚类的最大区别在于，分类数据中的一部分的类别是已知的，而聚类数据的类别未知。n建立分类模型需要学习一部分已知数据，如果训练时间过长，或者预测模型参数

3、太多而样本较少，将导致过度训练(overfitting)。2022-7-316.第6页，共106页。如何避免过度训练 n避免过度训练最重要一点是，模型的参数量应远小于样本的数量。n应建立训练集(training set)和测试集(test set)。n训练集应用于建立分类模型n测试集应用于评估分类模型nK折叠交叉验证(K-fold cross validation)：将初始采样分割成K个子样本(S1，S2,.,Sk)，取K-1个做训练集，另外一个做测试集。交叉验证重复K次，每个子样本都作为测试集一次，平均K次的结果，最终得到一个单一估测。2022-7-317.第7页，共106页。分类模型的评估

4、 n真阳性(T True P Positive)：实际为阳性 预测为阳性n真阴性(T True NNegative)：实际为阴性 预测为阴性n假阳性(F False P Positive)：实际为阴性 预测为阳性n假阴性(F False NNegative)：实际为阳性 预测为阴性n预测是否正确 预测结果n比如预测未知动物是鸟类还是爬行动物，阳性代表爬行动物，阴性代表非非爬行动物，请大家阐述 TP=10，TN=8，FN=3，FP=2是什么意义2022-7-318.第8页，共106页。分类模型的评估 n灵敏度(Sensitivity)：TP/(TP+FN)n也称为查全率(Recall)n数据集共

5、有13只爬行动物，其中10只被正确预测为爬行动物，灵敏度为10/13n特异度(Specificity):TN/(TN+FP)n数据集有10只非爬行动物，其中8只被预测为非爬行动物，特异度为8/10n精度(Precision):TP/(TP+FP)n分类器预测了12只动物为爬行动物，其中10只确实是爬行动物，精度为10/12n准确率(Accuracy):(TP+TN)/(TP+TN+FN+FP)n数据集包含23只动物，其中18只预测为正确的分类，准确率为18/232022-7-319.第9页，共106页。分类模型的评估 n对于非平衡(unblanced)的数据集,以上指标并不能很好的评估预测结果

6、。n非平衡的数据集是指阳性数据在整个数据集中的比例很小。比如，数据集包含10只爬行动物，990只爬行动物，此时，是否预测正确爬行动物对准确率影响不大。n更平衡的评估标准包括马修斯相关性系数(Matthews correlation coefficient)和ROC曲线。n马修斯相关性系数定义为2022-7-3110.第10页，共106页。分类模型的评估 nROC曲线通过描述真阳性率(TPR)和假阳性率(FPR)来实现，其中TPR=TP/(TP+FN),FPR=FP/(FP+TN)。n大部分分类器都输出一个实数值(可以看作概率),通过变换阈值可以得到多组TPR与FPR的值。2022-7-3111

7、.第11页，共106页。第三章第三章 分类方法分类方法 内容提要内容提要n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n实值预测 n与分类有关的问题 2022-7-3112.第12页，共106页。基于距离的分类算法的思路n定义定义4-2 4-2 给定一个数据库给定一个数据库 D D=t t1 1，t t2 2，t tn n 和一和一组类组类C C=C C1 1，C Cmm。假定每个元组包括一些数。假定每个元组包括一些数值型的属性值：值型的属性值：t ti i=t ti1 i1，t ti2i2，t tik ik，每个类也包，每个类也包含数值性属性值：含数值性属性值

8、：C Cj j=C Cj1 j1，C Cj2j2，C Cjk jk，则分，则分类问题是要分配每个类问题是要分配每个t ti i到满足如下条件的类到满足如下条件的类C Cj j：simsim(t ti i，C Cj j)=)=simsim(t ti i，C Cl l)，C Cl lC C，C Cl lC Cj j，其中其中simsim(t ti i，C Cj j)被称为相似性。被称为相似性。n在实际的计算中往往用在实际的计算中往往用距离距离来表征，距离越近，来表征，距离越近，相似性越大，距离越远，相似性越小。相似性越大，距离越远，相似性越小。n距离的计算方法有多种，最常用的是通过计算每距离的计算

9、方法有多种，最常用的是通过计算每个类的中心来完成。个类的中心来完成。2022-7-3113.第13页，共106页。基于距离的分类算法的一般性描述n算法 4-1通过对每个样本和各个类的中心来比较，从而可以找出他的最近的类中心，得到确定的类别标记。算法算法 4-1 基于距离的分类算法输入：每个类的中心C1，Cm；待分类的元组t。输出：输出类别c。（1）dist=；/距离初始化（2）FOR i:=1 to m DO（3）IF dis(ci，t)dist THEN BEGIN（4）c i；（5）distdist(ci，t)；（6）END.2022-7-3114.第14页，共106页。基于距离的分类方法

10、的直观解释（a）类定义（b）待分类样例（c）分类结果2022-7-3115.第15页，共106页。距离分类例题 nC1=(3,3,4,2),C2=(8,5,-1,-7),C3=(-5,-7,6,10);请用基于距离的算法给以下样本分类：(5,5,0,0)(5,5,-5,-5)(-5,-5,5,5)2022-7-3116.第16页，共106页。K-近邻分类算法nK-近邻分类算法（K Nearest Neighbors，简称KNN）通过计算每个训练数据到待分类元组的距离，取和待分类元组距离最近的K个训练数据，K个数据中哪个类别的训练数据占多数，则待分类元组就属于哪个类别。算法算法 4-2 K-近邻

11、分类算法近邻分类算法输入：输入：训练数据训练数据T；近邻数目；近邻数目K；待分类的元组；待分类的元组t。输出：输出：输出类别输出类别c。（1）N=；（2）FOR each d T DO BEGIN（3）IF|N|K THEN（4）N=N d；（5）ELSE（6）IF u N such that sim(t，u)sim(t，d)THEN BEGIN（7）N=N-u；（8）N=N d；（9）END（10）END（11）c=class to which the most u N.2022-7-3117.第17页，共106页。KNN的例子姓名 性别 身高(米)类别Kristina女 1.6 矮Jim

12、男 2高Maggie 女 1.83高Martha 女 1.88高Stephanie女 1.7矮Bob 男 1.85中等Kathy 女 1.6矮Dave 男 1.7矮Worth 男 2.2高Steven 男 2.1 高Debbie 女 1.8高Todd 男 1.82中等Kim 女 1.7中等Amy 女 1.75中等Wynette 女 1.73中等n只使用身高做特征，K=3，对于样本应属于哪个类别？n仅使用同性别样本做训练，K=3，对于样本应属于哪个类别？2022-7-3118.第18页，共106页。第三章第三章 分类方法分类方法 内容提要内容提要n分类的基本概念与步骤 n基于距离的分类算法 n决

13、策树分类方法 n贝叶斯分类 n实值预测 n与分类有关的问题 2022-7-3119.第19页，共106页。决策树表示与例子年龄年龄？学生学生？是是信用信用？40否是良好一般是是否否是是否否2022-7-3120.第20页，共106页。决策树表示与例子n决策树（Decision Tree）的每个内部结点表示一个属性（特征），每个分枝代表一个特征的一个（类）取值；n每个树叶结点代表类或类分布。n决策树分类方法采用自顶向下的递归方式，在决策树的内部结点进行属性的比较，从而判断从该结点向下的分枝，在决策树的叶结点得到结论。n从决策树的根到叶结点的一条路径就对应着一条规则，整棵决策树就对应着一组规则。n

14、决策树分类模型的建立通常分为两个步骤：n决策树生成n决策树修剪2022-7-3121.第21页，共106页。决策树生成算法描述算法 4-3 Generate_decision_tree(samples,attribute_list)/*决策树生成算法*/输入：训练样本samples，由离散值属性表示；输出：一棵决策树。（1）创建结点N；（2）IFIF samples 都在同一个类C THENTHEN 返回N 作为叶结点，以类 C标记；（3）IFIF attribute_list为空 THENTHEN 返回N作为叶结点，标记为samples中最普通的类；/多数表决（4）选择attribute_l

15、ist中具有最高信息增益的属性test_attribute；（5）标记结点N为test_attribute；（6）FORFOR test_attribute的每个取值ai 由结点N长出一个条件为test_attribute=ai的分枝；（7）设si是samples 中test_attribute=ai的样本的集合；/一个划分（8）IFIF si 为空 THENTHEN 回退到test_attribute的其它取值；（9）ELSEELSE 加上一个由Generate_decision_tree(si，attribute_list-test_attribute)返回的结点；2022-7-3122.

16、第22页，共106页。决策树修剪算法n基本的决策树构造算法没有考虑噪声，因此生成的决策树完全与训练集拟合。在有噪声情况下，将导致过分拟合（Overfitting），即对训练数据的完全拟合反而使对现实数据的分类预测性能下降。n比如每个样本都是一个叶子节点。n现实世界的数据一般不可能是完美的，可能缺值（Missing Values）；数据不完整；含有噪声甚至是错误的。n剪枝是一种克服噪声的基本技术，同时它也能使树得到简化而变得更容易理解。有两种基本的剪枝策略。2022-7-3123.第23页，共106页。决策树修剪算法n预先剪枝（Pre-Pruning）：在生成树的同时决定是继续对不纯的训练子集进

17、行划分还是停机。n后剪枝（Post-Pruning）：是一种拟合+化简（fitting-and-simplifying）的两阶段方法。首先生成与训练数据完全拟合的一棵决策树，然后从树的叶子开始剪枝，逐步向根的方向剪。剪枝时要用到一个测试数据集合（Tuning Set或Adjusting Set），如果存在某个叶子剪去后能使得在测试集上的准确度或其他测度不降低（不变得更坏），则剪去该叶子；否则停机。理论上讲，后剪枝好于预先剪枝，但计算复杂度大。2022-7-3124.第24页，共106页。决策树修剪算法n构造好的决策树的关键在于如何选择属性进行树的拓展。研究结果表明，一般情况下,树越小则树的预测

18、能力越强。由于构造最小的树是NP-难问题，因此只能采取用启发式策略来进行。n属性选择依赖于各种对例子子集的不纯度（Impurity）度量方法，包括信息增益（Informatin Gain）、信息增益比（Gain Ratio）、Gini-index、距离度量（Distance Measure）、J-measure等。2022-7-3125.第25页，共106页。ID3算法nID3是一个著名决策树生成方法：n决策树中每一个非叶结点对应着一个非类别属性(特征)，树枝代表这个属性的值。一个叶结点代表从树根到叶结点之间的路径对应的记录所属的类别属性值。n每一个非叶结点都将与属性中具有最大信息量的非类别属

19、性相关联。n采用信息增益来选择能够最好地将样本分类的属性。n对ID3算法采用如下方式讲解：n给出信息增益对应的计算公式；n通过一个例子来说明它的主要过程。2022-7-3126.第26页，共106页。信息增益的计算n设S是s个数据样本的集合，定义m个不同类Ci（i=1，2，m），设si是Ci类中的样本的数量。对给定的样本S所期望的信息值由下式给出：其中pi是任意样本属于Ci的概率：si/s。例题：数据集有4个类，分别有8个，4个，2个，2个样本，求该数据集的信息值。问题：信息值的取值范围是什么？miiimppsssI1221)(log),.,(2022-7-3127.第27页，共106页。信息

20、增益的计算例题：数据集有2个类，求该数据集的信息值。2022-7-3128.第28页，共106页。信息增益的计算n设属性A具有个不同值a1,a2,av，可以用属性A将样本S划分为 S1,S2,Sv，设Sij 是Sj中Ci类的样本数，则由A划分成子集的熵由下式给出：n有A进行分枝将获得的信息增益可以由下面的公式得到：)s,.,s(Iss.sE(A)mjjvjmjj111E(A)s,.,s,I(sGain(A)m21使用属性后的信息值未使用属性的信息值2022-7-3129.第29页，共106页。信息增益的计算例题：数据集有2个类。使用是否学生作为属性，求该属性的信息增益。使用信用状况作为属性，求

21、该属性的信息增益。2022-7-3130.第30页，共106页。ID3算法的例子选择信息增益最大的属性特征作为根节点。Gain(年龄)=0.342 Gain(收入)=0Gain(是否学生)=0.333 Gain(信用状况)=0年龄年龄？是是402022-7-3131.第31页，共106页。ID3算法的例子对于=30的分支Gain(收入)=0.315 Gain(是否学生)=0.315 Gain(信用状况)=0.815对于30 40的分支Gain(收入)=1 Gain(是否学生)=0 Gain(信用状况)=1年龄？年龄？信用状况？信用状况？收入？收入？是是40否否是是是是否否良好一般高低2022-

22、7-3132.第32页，共106页。ID3算法的性能分析nID3算法的假设空间包含所有的决策树，它是关于现有属性的有限离散值函数的一个完整空间。nID3算法在搜索的每一步都使用当前的所有训练样例，大大降低了对个别训练样例错误的敏感性。因此，通过修改终止准则，可以容易地扩展到处理含有噪声的训练数据。2022-7-3133.第33页，共106页。ID3算法的性能分析nID3算法在搜索过程中不进行回溯。所以，它易受无回溯的爬山搜索中的常见风险影响：收敛到局部最优而不是全局最优。nID3算法只能处理离散值的属性。n信息增益度量存在一个内在偏置，它偏袒具有较多值的属性。例如，如果有一个属性为日期，那么将

23、有大量取值，这个属性可能会有非常高的信息增益。假如它被选作树的根结点的决策属性则可能形成一颗非常宽的树，这棵树可以理想地分类训练数据，但是对于测试数据的分类性能可能会相当差。nID3算法增长树的每一个分支的深度，直到属性的使用无法导致信息增益。当数据中有噪声或训练样例的数量太少时，产生的树会过渡拟合训练样例。n问题：ID3树可以导致过度拟合，那是否它一定能对训练集完全正确的分类呢？2022-7-3134.第34页，共106页。C4.5算法对ID3的主要改进nC4.5算法是从ID3算法演变而来，除了拥有ID3算法的功能外，C4.5算法引入了新的方法和增加了新的功能：n用信息增益比例的概念；n合并

24、具有连续属性的值；n可以处理具有缺少属性值的训练样本；n通过使用不同的修剪技术以避免树的过度拟合；nK交叉验证；n规则的产生方式等。2022-7-3135.第35页，共106页。信息增益比例的概念n信息增益比例是在信息增益概念基础上发展起来的，一个属性的信息增益比例用下面的公式给出：其中假如我们以属性A的值为基准对样本进行分割的化，Splitl(A)就是前面熵的概念。)()()(ASplitIAGainAGainRatio)(log)(12jvjjppASplitI2022-7-3136.第36页，共106页。信息增益比例的计算例题：数据集有2个类。使用是否学生作为属性，求该属性的信息增益比例

25、。使用年龄作为属性，求该属性的信息增益比例。讨论：信息增益和信息增益比例的差异在哪里？2022-7-3137.第37页，共106页。C4.5处理连续值的属性n对于连续属性值，C4.5其处理过程如下：n根据属性的值，对数据集排序；n用不同的阈值将数据集动态的进行划分；n取两个实际值中的中点作为一个阈值；n取两个划分，所有样本都在这两个划分中；n得到所有可能的阈值、增益及增益比；n在每一个属性会变为取两个取值，即小于阈值或大于等于阈值。n简单地说，针对属性有连续数值的情况，则在训练集中可以按升序方式排列。如果属性A共有n种取值，则对每个取值vj（j=1，2，n），将所有的记录进行划分：一部分小于v

26、j；另一部分则大于或等于vj。针对每个vj计算划分对应的增益比率，选择增益最大的划分来对属性A进行离散化。2022-7-3138.第38页，共106页。C4.5处理连续值的属性例题：使用C4.5算法将连续的属性(收入)转化为离散的类。根据属性的值，对数据集排序；取两个实际值中的中点作为一个阈值；取两个划分，所有样本都在这两个划分中；得到所有可能的阈值、增益及增益比；在每一个属性会变为取两个取值，即小于阈值或大于等于阈值。2022-7-3139.第39页，共106页。C4.5处理连续值的属性例题：使用C4.5算法将连续的属性(收入)转化为离散的类。选择增益最大的划分来对属性A进行离散化。Gain

27、Ratio(划分：2750)=0.2GainRatio(划分：3100)=0.39GainRatio(划分：3625)=0.53GainRatio(划分：4458)=1GainRatio(划分：？)=0.53GainRatio(划分：8285)=0.39GainRatio(划分：10900)=0.2收入小于4458合并为收入低收入大于等于4458合并为收入高2022-7-3140.第40页，共106页。C4.5的其他处理 nC4.5处理的样本中可以含有未知属性值，其处理方法是用最常用的值替代或者是将最常用的值分在同一类中。n具体采用概率的方法，依据属性已知的值，对属性和每一个值赋予一个概率，取

28、得这些概率，取得这些概率依赖于该属性已知的值。n规则的产生：规则的产生：一旦树被建立，就可以把树转换成if-then规则。n规则存储于一个二维数组中，每一行代表树中的一个规则，即从根到叶之间的一个路径。表中的每列存放着树中的结点。2022-7-3141.第41页，共106页。C4.5算法例子样本数据天气温度湿度风网球SunnyHot85falseNoSunnyHot90trueNoOvercast Hot78falseYesRainMild96falseYesRainCool80falseYesRainCool70trueNoOvercast Cool65trueYesSunnyMild95f

29、alseNoSunnyCool70falseYesRainMild80falseYesSunnyMild70trueYesOvercast Mild90trueYesOvercastHot75falseYesRainMild80trueNo（1）首先对湿度湿度进行属性离散化，针对上面的训练集合，通过检测每个划分而确定最好的划分在75处，则这个属性的范围就变为（75）。（2）计算目标属性打网球打网球分类的期望信息：（3）计算每个属性的GainRatio：940.0145log145149log149)5,9(),(2221 IssI0.0483)GainRatio(0.0248)GainRati

30、o(049.0)(GainRatio156.0577.12467.0)(GainRatio湿度；温度；风；天气2022-7-3142.第42页，共106页。C4.5算法例子（4）选取最大的GainRatio，根据天气天气的取值，得到三个分枝。（5）再扩展各分枝节点，得到最终的决策树（见课本图4-7）。问题：就天气=Sunny这一分支，请用C4.5算法构造决策树。样本数据天气温度湿度风网球SunnyHot85falseNoSunnyHot90trueNoSunnyMild95falseNoSunnyCool70falseYesSunnyMild70trueYes2022-7-3143.第43页，

31、共106页。第三章第三章 分类方法分类方法 内容提要内容提要n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n实值预测 n与分类有关的问题 2022-7-3144.第44页，共106页。贝叶斯分类n定义定义4-4-3 3 设设X X是类标号未知的数据样本。设是类标号未知的数据样本。设H H为某种假定，如数据样为某种假定，如数据样本本X X属于某特定的类属于某特定的类C C。对于分类问题，我们希望确定对于分类问题，我们希望确定P(H|X)P(H|X)，即给定观测数据样本即给定观测数据样本X X，假定假定H H成立的概率。贝叶斯定理给出了如下成立的概率。贝叶斯定理给出

32、了如下计算计算P(H|X)P(H|X)的简单有效的方法的简单有效的方法:nP(X|H)P(X|H)代表假设代表假设H H成立的情况下，观察到成立的情况下，观察到X X的概率。的概率。P(H|X)P(H|X)是是后验概率后验概率，或称为或称为X X发生后观测到发生后观测到H H的的条件概率条件概率。n例如，假定数据样本由一些人组成，假定例如，假定数据样本由一些人组成，假定X X表示头发颜色，表示头发颜色，H H表示肤色，则表示肤色，则P(H|X)P(H|X)反映当我们看到反映当我们看到X X是黑色时，我们对是黑色时，我们对H H为黄色的确信程度。为黄色的确信程度。)()()|()()()|(XP

33、HPHXPXPXHPXHP2022-7-3145.第45页，共106页。朴素贝叶斯分类的工作原理n观测到的样本具有属性 收入低 是学生 信用良好n现在的问题相当于比较两个条件概率的大小P(买电脑|收入低,是学生,信用良好)P(不买电脑|收入低,是学生,信用良好)2022-7-3146.第46页，共106页。朴素贝叶斯分类朴素贝叶斯分类的工作过程如下：朴素贝叶斯分类的工作过程如下：n(1)每个数据样本用一个n维特征向量X=x1，x2，xn表示，分别描述对n个属性A1，A2，An样本的n个度量。n(2)假定有m个类C1，C2，Cm，给定一个未知的数据样本X（即没有类标号），分类器将预测X属于具有最

34、高条件概率（条件X下）的类。n也就是说，朴素贝叶斯分类将未知的样本分配给类Ci（1im）当且仅当P(Ci|X)P(Cj|X)，对任意的j=1，2，m，ji。2022-7-3147.第47页，共106页。朴素贝叶斯分类(续)根据贝叶斯定理：根据贝叶斯定理：由于由于P P(X X)对于所有类为对于所有类为常数常数，只需要，只需要P P(X X|C Ci i)*P P(C Ci i)最大即可。最大即可。注意，类的先验概率可以用注意，类的先验概率可以用P(CP(Ci i)=S)=Si i/S/S计算，其中计算，其中S Si i是类是类C Ci i中的中的训练样本数，而训练样本数，而S S是训练样本总数

35、。是训练样本总数。因此问题就转换为计算因此问题就转换为计算P P(X X|C Ci i)。)()()|()()()|(XPHPHXPXPXHPXHP2022-7-3148.第48页，共106页。朴素贝叶斯分类(续)给定具有许多属性的数据集，计算给定具有许多属性的数据集，计算P P(X X|C Ci i)的计算的计算量可能非常大且不易计算。为降低计算量可能非常大且不易计算。为降低计算P P(X X|C Ci i)的的难度，可以做难度，可以做类条件独立的朴素假定。给定样本。给定样本的类标号，假定的类标号，假定属性值相互条件独立属性值相互条件独立，即在属性，即在属性间，不存在依赖关系。这样间，不存在

36、依赖关系。这样P(P(收入低收入低,是学生是学生,信用良好信用良好|买电脑买电脑)=)=P(P(收入低收入低|买电脑买电脑)*P(P(是学生是学生|买电脑买电脑)*P(P(信用良好信用良好|买电脑买电脑)|()|(1inkkiCxPCXP2022-7-3149.第49页，共106页。朴素贝叶斯分类(续)其中概率其中概率P P(x x1 1|C Ci i)，P P(x x2 2|C Ci i)，P P(x xn n|C Ci i)可以由训练样本估值。可以由训练样本估值。n如果如果A Ak k是离散属性，则是离散属性，则P P(x xk k|C Ci i)=)=s sikik|s si i，其中其

37、中s sikik是在属性是在属性A Ak k上具有值上具有值x xk k的类的类C Ci i的训练样本数，而的训练样本数，而s si i是是C Ci i中的训练样本数。中的训练样本数。n如果如果A Ak k是连续值属性，则通常假定该属性服从高斯分布。因而，是连续值属性，则通常假定该属性服从高斯分布。因而，是高斯分布函数，是高斯分布函数，而分别为平均值和标准差。而分别为平均值和标准差。22)(21),()|(iiiiicckccckikxexgCxP),(iicckxgiicc,2022-7-3150.第50页，共106页。朴素贝叶斯分类(续)n例题：计算P(收入低|不买电脑)P(是学生|不买电

38、脑)P(信用良好|不买电脑)假设 收入，是否学生，信用状况互相独立，计算 P(收入低，是学生，信用良好|不买电脑)2022-7-3151.第51页，共106页。朴素贝叶斯分类(续)对未知样本对未知样本X X分类，也就是对每个类分类，也就是对每个类C Ci i，计算计算P(P(X X|C Ci i)*P(P(C Ci i)。样本样本X X被指派到类被指派到类C Ci i，当且仅当当且仅当P(P(C Ci i|X X)P()P(C Cj j|X X)，11j jmm，j ji i，换言之，换言之，X X被指派到其被指派到其P(P(X X|C Ci i)*P(P(C Ci i)最大的类。最大的类。2

39、022-7-3152.第52页，共106页。朴素贝叶斯分类举例数据样本有属性年龄，收入，是否学生和信用状况。类标号属性”是否买电脑“有两个不同值是，否。设C1对应于类”买电脑”；则C2对应于类”不买电脑”。我们希望分类的未知样本为:X=（”年龄=30”，”收入=中”，”是学生”，”信用一般”）2022-7-3153.第53页，共106页。朴素贝叶斯分类举例我们需要最大化P(X|Ci)*P(Ci)，i=1，2。每个类的先验概率P(Ci)可以根据训练样本计算：P(C1)=P(买电脑）=P(C2)=P(不买电脑）=计算P(X|Ci)P（年龄=30,收入=中,是学生,信用一般|买电脑)P（年龄=30,

40、收入=中,是学生,信用一般|不买电脑)2022-7-3154.第54页，共106页。朴素贝叶斯分类举例P（年龄=30,收入=中,是学生,信用一般|买电脑)=P（年龄=30|买电脑)*P（收入=中|买电脑)*P（是学生|买电脑)*P（信用一般|买电脑)P（年龄=30,收入=中,是学生,信用一般|不买电脑)=P（年龄=30|不买电脑)*P（收入=中|不买电脑)*P（是学生|不买电脑)*P（信用一般|不买电脑)2022-7-3155.第55页，共106页。朴素贝叶斯分类举例假设属性之间独立P（年龄=30,收入=中,是学生,信用一般|买电脑)=0.222*0.444*0.667*0.667=0.044

41、；P（年龄P（X|不买电脑)，因此对于样本X，朴素贝叶斯分类预测为是。2022-7-3156.第56页，共106页。第三章第三章 分类方法分类方法 内容提要内容提要n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n基于规则的分类 n与分类有关的问题 2022-7-3157.第57页，共106页。使用IF-THEN规则分类n使用规则的分类法是使用一组IF-THEN规则进行分类。nIF 条件 THEN 结论n比如 IF(年龄20 AND 学生=是)THEN买电脑=是nIF的部分称为前提，THEN的部分称为规则的结论n规则可以用它的覆盖率和准确率来评价nncovers是

42、条件(前提)覆盖的样本数，ncorrect是规则正确分类的样本数。|)covarage(RcoversDncoverscorrect)accuracy(Rnn2022-7-3158.第58页，共106页。使用IF-THEN规则分类规则(收入=低)(信用状况良好)(是否买电脑=是)的覆盖率为3/8,而它测准确率为1/3。规 则(信 用 状 况=良好)(是否买电脑=否)的覆盖率为7/8,而它测准确率为4/7。2022-7-3159.第59页，共106页。使用IF-THEN规则分类n如果一个规则R被一个样本X满足，则称规则R被X触发。n比如X=(年龄=18，是学生，信用良好)R为 IF(年龄20 A

43、ND 学生=是)THEN买电脑=是 则X的类别为 买电脑如果一个样本X同时触发了多个规则，我们需要制定解决冲突的策略。规模序 激活具有最多属性测试的触发规则规则序 将规则按重要性进行排序，按顺序进行促发如果一个样本X无法促发任何规则建立一个缺省或者默认规则2022-7-3160.第60页，共106页。使用决策树来提取规则决策树的规则是互斥与穷举的互斥意味着规则不会存在冲突，因此每个样本只能促发一个规则穷举意味着一个样本总能促发一个规则由于每个树叶对应一个一条规则，提取的规则并不比决策树简单。年龄？年龄？信用状况？信用状况？收入？收入？是是40否否是是是是否否良好一般高低2022-7-3161.

44、第61页，共106页。使用顺序覆盖算法的规则归纳n在提取规则时，一个现实的问题是是否需要对现有规则进行拓展，n IF(年龄20)THEN买电脑 是否需要拓展为 IF(年龄20 AND 学生=是)THEN买电脑n衡量规则好坏应同时考虑覆盖度与准确率n 准确率太低 覆盖度太低2022-7-3162.第62页，共106页。使用顺序覆盖算法的规则归纳有两种衡量规则好坏的度量 FOIL_Gain的定义如下n分别对应于两个规则R与R。正在学习的类称为正样本(pos)，而其他类称为负样本(neg),pos(neg)为规则R覆盖的正负样本，而pos(neg)为规则R覆盖的正负样本。)log(logFoil_G

45、ain22negposposnegpospospos2022-7-3163.第63页，共106页。判断规则(收入=低)(是否买电脑=否)是否需要拓展为规则(收入=低)(信用状况=良好)(是否买电脑=否)log(logFoil_Gain22negposposnegpospospos2022-7-3164.第64页，共106页。使用顺序覆盖算法的规则归纳n似然率统计量的的定义如下n其中m是分类的类别数。fi为满足规则的样本中属于类i的概率，ei为属于类i的期望(基准)概率。n似然率越高，说明规则越理想。miiiieff1)log(2_RatioLikelihood2022-7-3165.第65页，

46、共106页。分 别 计 算 规 则(收 入=低)(是否买电脑=否)与规则(收入=低)(信用状况=良好)(是否买电脑=否)的似然率。miiiieff1)log(2_RatioLikelihood2022-7-3166.第66页，共106页。顺序覆盖算法n终止条件包括，类c没有样本或者返回的规则质量低于用户指定的阈值等。输入：D，类标记已知的样本的集合。Att_vals,所有属性与它们可能值得集合。输出：IF-THEN规则的集合。（1）Rule_set=；/规则的初始集为空集（2）FOR 每个类 c DO（3）repeat（4）Rule=Learn_One_Rule(D,Att_vals,c);（

47、5）从D中删除Rule覆盖的样本；（6）untile 终止条件满足；（7）Rule_set=Rule_set+Rule;/将新规则添加到规则集（8）END FOR（9）返回Rule_Set2022-7-3167.第67页，共106页。使用顺序覆盖算法的规则归纳Rule_set=；选择一个类“买电脑”；选择一个包含一个属性的规则(收入=低)“买电脑”分别计算其它包含一个属性的规则的相对于已选择规则的FOIL_Gain(收入=高)“买电脑”(学生=是)“买电脑”(学生=否)“买电脑”(信用=良好)“买电脑”(信用=一般)“买电脑”)log(logFoil_Gain22negposposnegpos

48、pospos2022-7-3168.第68页，共106页。使用顺序覆盖算法的规则归纳分别计算规则的Foil_gain(收入=高)买电脑为1.74(学生=是)买电脑为0(学生=否)买电脑为0(信用=良好)买电脑为0(信用=一般)买电脑为0选择Foil_gain最高的规则(收入=高)买电脑2022-7-3169.第69页，共106页。使用顺序覆盖算法的规则归纳对最好的规则R进行拓展(收入=高)买电脑在规则R中添加一个属性，得到拓展以后的规则R(收入=高)(学生=是)(收入=高)(学生=否)(收入=高)(信用=良好)(收入=高)(信用=一般)分别计算这些规则的相对于R的Foil_gain2022-7

49、-3170.第70页，共106页。使用顺序覆盖算法的规则归纳分别计算规则的Foil_gain(收入=高)(学生=是)为0.84(收入=高)(学生=否)为-1.16(收入=高)(信用=良好)为0.84(收入=高)(信用=一般)为-1.16选择Foil_gain最高的规则(收入=高)(学生=是)(收入=高)(信用=良好)由于这两个规则准确率已经是100%，因此不用拓展2022-7-3171.第71页，共106页。使用顺序覆盖算法的规则归纳将规则覆盖的样本从数据集D中删除，对剩下的正样本生成规则2022-7-3172.第72页，共106页。使用顺序覆盖算法的规则归纳选择另外一个类“不买电脑”(生成其

50、它类的规则)；选择一个包含一个属性的规则(收入=低)“不买电脑”分别计算其它包含一个属性的规则的相对于已选择规则的FOIL_Gain(收入=高)“不买电脑”(学生=是)“不买电脑”(学生=否)“不买电脑”(信用=良好)“不买电脑”(信用=一般)“不买电脑”2022-7-3173.第73页，共106页。第三章第三章 分类方法分类方法 内容提要内容提要n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n基于规则的分类n实值预测 2022-7-3174.第74页，共106页。实值预测分类：把样本分配到若干类之一(离散的)。比如预测是普通员工、中层管理还是高级管理人员预测：