数据挖掘--分类课件ppt（经典实用）

1、2021-5-3数据挖掘-分类课件ppt1 第三章第三章 分类方法分类方法 内容提要内容提要 n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n实值预测 n与分类有关的问题 2021-5-3数据挖掘-分类课件ppt2 分类的流程 n根据现有的知识，我们得到了一些关于爬行动物和鸟类的信息， 我们能否对新发现的物种，比如动物A，动物B进行分类？ 动物种动物种 类类 体型体型翅膀数量翅膀数量脚的只数脚的只数是否产是否产 蛋蛋 是否有毛是否有毛类别类别 狗中04否是爬行动物 猪大04否是爬行动物 牛大04否是爬行动物 麻雀小22是是鸟类 天鹅中22是是鸟类 大雁中22是是

2、鸟类 动物A大02是无？ 动物B中22否是？ 2021-5-3数据挖掘-分类课件ppt3 分类的流程 n步骤一：将样本转化为等维的数据特征（特征提取）。 n所有样本必须具有相同数量的特征 n兼顾特征的全面性和独立性 动物种动物种 类类 体型体型翅膀数量翅膀数量脚的只数脚的只数是否产是否产 蛋蛋 是否有毛是否有毛类别类别 狗中04否是爬行动物 猪大04否是爬行动物 牛大04否是爬行动物 麻雀小22是是鸟类 天鹅中22是是鸟类 大雁中22是是鸟类 2021-5-3数据挖掘-分类课件ppt4 分类的流程 n步骤二：选择与类别相关的特征（特征选择）。 n比如，绿色代表与类别非常相关，黑色代表部分相关，

3、灰 色代表完全无关 动物种动物种 类类 体型体型翅膀数量翅膀数量脚的只数脚的只数是否产是否产 蛋蛋 是否有毛是否有毛类别类别 狗中0 04 4否否是爬行动物 猪大0 04 4否否是爬行动物 牛大0 04 4否否是爬行动物 麻雀小2 22 2是是是鸟类 天鹅中2 22 2是是是鸟类 大雁中2 22 2是是是鸟类 2021-5-3数据挖掘-分类课件ppt5 分类的流程 n步骤三：建立分类模型或分类器（分类）。 n分类器通常可以看作一个函数，它把特征映射到类的空间 上 iiniiiyxxxxf),.,(321 2021-5-3数据挖掘-分类课件ppt6 如何避免过度训练 n分类也称为有监督学习(su

4、pervised learning), 与之相对于的是无监督学习(unsupervised learning),比如聚类。 n分类与聚类的最大区别在于，分类数据中的一 部分的类别是已知的，而聚类数据的类别未知。 n建立分类模型需要学习一部分已知数据，如果 训练时间过长，或者预测模型参数太多而样本 较少，将导致过度训练(overfitting)。 2021-5-3数据挖掘-分类课件ppt7 如何避免过度训练 n避免过度训练最重要一点是，模型的参数量应 远小于样本的数量。 n应建立训练集(training set)和测试集(test set)。 n训练集应用于建立分类模型 n测试集应用于评估分类模

5、型 nK折叠交叉验证(K-fold cross validation)：将初始 采样分割成K个子样本(S1，S2,.,Sk)，取K-1个做 训练集，另外一个做测试集。交叉验证重复K次， 每个子样本都作为测试集一次，平均K次的结果， 最终得到一个单一估测。 2021-5-3数据挖掘-分类课件ppt8 分类模型的评估 n真阳性(T True P Positive)： 实际为阳性 预测为阳性 n真阴性(T True NNegative)：实际为阴性 预测为阴性 n假阳性(F False P Positive)： 实际为阴性 预测为阳性 n假阴性(F False NNegative)：实际为阳性 预测

6、为阴性 n预测是否正确 预测结果 n比如预测未知动物是鸟类还是爬行动物，阳性代表爬 行动物，阴性代表非非爬行动物，请大家阐述 TP=10， TN=8，FN=3，FP=2是什么意义 2021-5-3数据挖掘-分类课件ppt9 分类模型的评估 n灵敏度(Sensitivity)： TP/(TP+FN) n也称为查全率(Recall) n数据集共有13只爬行动物，其中10只被正确预测为爬行动物， 灵敏度为10/13 n特异度(Specificity): TN/(TN+FP) n数据集有10只非爬行动物，其中8只被预测为非爬行动物，特 异度为8/10 n精度(Precision): TP/(TP+FP

7、) n分类器预测了12只动物为爬行动物，其中10只确实是爬行动 物，精度为10/12 n准确率(Accuracy): (TP+TN)/(TP+TN+FN+FP) n数据集包含23只动物，其中18只预测为正确的分类，准确率 为18/23 2021-5-3数据挖掘-分类课件ppt10 分类模型的评估 n对于非平衡(unblanced)的数据集,以上指标并不能很好的 评估预测结果。 n非平衡的数据集是指阳性数据在整个数据集中的比例很 小。比如，数据集包含10只爬行动物，990只爬行动物， 此时，是否预测正确爬行动物对准确率影响不大。 n更平衡的评估标准包括马修斯相关性系数(Matthews corr

8、elation coefficient)和ROC曲线。 n马修斯相关性系数定义为 2021-5-3数据挖掘-分类课件ppt11 分类模型的评估 nROC曲线通过描述真阳性率(TPR)和假阳性率(FPR)来实 现，其中TPR=TP/(TP+FN), FPR=FP/(FP+TN)。 n大部分分类器都输出一个实数值(可以看作概率),通过变 换阈值可以得到多组TPR与FPR的值。 2021-5-3数据挖掘-分类课件ppt12 第三章第三章 分类方法分类方法 内容提要内容提要 n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n实值预测 n与分类有关的问题 2021-5-3数

9、据挖掘-分类课件ppt13 基于距离的分类算法的思路 n定义定义4-2 4-2 给定一个数据库给定一个数据库 D D=t t1 1，t t2 2，t tn n 和一和一 组类组类C C=C C1 1，C Cm m 。假定每个元组包括一些数 。假定每个元组包括一些数 值型的属性值：值型的属性值：t ti i=t ti1 i1，t ti2 i2， ，t tik ik ，每个类也包，每个类也包 含数值性属性值：含数值性属性值：C Cj j=C Cj1 j1，C Cj2 j2， ，C Cjk jk ，则分，则分 类问题是要分配每个类问题是要分配每个t ti i到满足如下条件的类到满足如下条件的类C C

10、j 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距离的计算方法有多种，最常用的是通过计算每距离的计算方法有多种，最常用的是通过计算每 个类的中心来完成。个类的中心来完成。 2021-5-3数据挖掘-分类课件ppt14 基于距离的分类算

11、法的一般性描述 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. 2021-5-3数据挖掘-分类课件ppt15 基于距离的分类方法的直观解释 （a）类定义 （b）待分类样例（c）分类结果 2021-5-3数据挖掘-分类课件ppt1

12、6 距离分类例题 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) 2021-5-3数据挖掘-分类课件ppt17 K-近邻分类算法 nK-近邻分类算法（K Nearest Neighbors，简称KNN）通过 计算每个训练数据到待分类元组的距离，取和待分类元组 距离最近的K个训练数据，K个数据中哪个类别的训练数据 占多数，则待分类元组就属于哪个类别。 算法算法 4-2 K-近邻分类算法近邻分类算法 输入：输入： 训练数据训练数据T；近邻数目；近邻

13、数目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. 2021-5-3数据挖掘-分类课件ppt18 KNN的例子 姓名 性别 身高(米) 类别 Kristina女 1.6 矮 Jim 男 2

14、高 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，对 于样本应属于哪个类 别？ 2021-5-3数据挖掘-分类课件ppt19 第三章第三章 分类方法分类方法 内容提要内容提要 n分类的基本

15、概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n实值预测 n与分类有关的问题 2021-5-3数据挖掘-分类课件ppt20 决策树表示与例子 年龄年龄收收 入入 是否是否 学生学生 信用信用 状况状况 是否买是否买 电脑电脑 40中否一般是是 40低是一般是是 40低是良好否否 3040低是良好是是 =30中否一般否否 =30低是一般是是 年龄年龄？ 学生学生？是是信用信用？ 40 否是良好 一般 是是否否是是否否 2021-5-3数据挖掘-分类课件ppt21 决策树表示与例子 n决策树（Decision Tree）的每个内部结点表示一 个属性（特征），每个分枝代表一个特征

16、的一个 （类）取值； n每个树叶结点代表类或类分布。 n决策树分类方法采用自顶向下的递归方式，在决 策树的内部结点进行属性的比较，从而判断从该 结点向下的分枝，在决策树的叶结点得到结论。 n从决策树的根到叶结点的一条路径就对应着一条 规则，整棵决策树就对应着一组规则。 n决策树分类模型的建立通常分为两个步骤： n决策树生成 n决策树修剪 2021-5-3数据挖掘-分类课件ppt22 决策树生成算法描述 算法 4-3 Generate_decision_tree(samples, attribute_list) /* 决策树生成算法*/ 输入：训练样本samples，由离散值属性表示；输出：一棵

17、决策树。 （1） 创建结点N； （2） IFIF samples 都在同一个类C THENTHEN 返回N 作为叶结点，以类 C标记； （3） IFIF attribute_list为空 THENTHEN 返回N作为叶结点，标记为samples中最 普通的类；/多数表决 （4） 选择attribute_list中具有最高信息增益的属性test_attribute； （5） 标记结点N为test_attribute； （6） FORFOR test_attribute的每个取值ai 由结点N长出一个条件为 test_attribute=ai的分枝； （7）设si是samples 中test_at

18、tribute =ai的样本的集合；/一个划分 （8）IFIF si 为空 THENTHEN 回退到test_attribute的其它取值； （9）ELSEELSE 加上一个由Generate_decision_tree(si， attribute_list- test_attribute)返回的结点； 2021-5-3数据挖掘-分类课件ppt23 决策树修剪算法 n基本的决策树构造算法没有考虑噪声，因此生成 的决策树完全与训练集拟合。在有噪声情况下， 将导致过分拟合（Overfitting），即对训练数据的 完全拟合反而使对现实数据的分类预测性能下降。 n比如每个样本都是一个叶子节点。 n现

19、实世界的数据一般不可能是完美的，可能缺值 （Missing Values）；数据不完整；含有噪声甚至 是错误的。 n剪枝是一种克服噪声的基本技术，同时它也能使 树得到简化而变得更容易理解。有两种基本的剪 枝策略。 2021-5-3数据挖掘-分类课件ppt24 决策树修剪算法 n预先剪枝（Pre-Pruning）：在生成树的同时决定 是继续对不纯的训练子集进行划分还是停机。 n后剪枝（Post-Pruning）：是一种拟合+化简 （fitting-and-simplifying）的两阶段方法。首先生 成与训练数据完全拟合的一棵决策树，然后从树 的叶子开始剪枝，逐步向根的方向剪。剪枝时要 用到一个

20、测试数据集合（Tuning Set或Adjusting Set），如果存在某个叶子剪去后能使得在测试集 上的准确度或其他测度不降低（不变得更坏）， 则剪去该叶子；否则停机。理论上讲，后剪枝好 于预先剪枝，但计算复杂度大。 2021-5-3数据挖掘-分类课件ppt25 决策树修剪算法 n构造好的决策树的关键在于如何选择属性进行树 的拓展。研究结果表明，一般情况下,树越小则树 的预测能力越强。由于构造最小的树是NP-难问题， 因此只能采取用启发式策略来进行。 n属性选择依赖于各种对例子子集的不纯度 （Impurity）度量方法，包括信息增益 （Informatin Gain）、信息增益比（Gain

21、 Ratio）、 Gini-index、距离度量（Distance Measure）、J- measure等。 2021-5-3数据挖掘-分类课件ppt26 ID3算法 nID3是一个著名决策树生成方法： n决策树中每一个非叶结点对应着一个非类别属性(特征)， 树枝代表这个属性的值。一个叶结点代表从树根到叶结 点之间的路径对应的记录所属的类别属性值。 n每一个非叶结点都将与属性中具有最大信息量的非类别 属性相关联。 n采用信息增益来选择能够最好地将样本分类的属性。 n对ID3算法采用如下方式讲解： n给出信息增益对应的计算公式； n通过一个例子来说明它的主要过程。 2021-5-3数据挖掘-分

22、类课件ppt27 信息增益的计算 n设S是s个数据样本的集合，定义m个不同类Ci（i=1， 2，m），设si是Ci类中的样本的数量。对给定的样本S 所期望的信息值由下式给出： 其中pi是任意样本属于Ci的概率： si / s 。 例题：数据集有4个类，分别有8个，4个，2个，2个样本， 求该数据集的信息值。 问题：信息值的取值范围是什么？ m i iim ppsssI 1 221 )(log),.,( 2021-5-3数据挖掘-分类课件ppt28 信息增益的计算 例题：数据集有2个类，求该 数据集的信息值。 年龄年龄收收 入入 是否是否 学生学生 信用信用 状况状况 是否买是否买 电脑电脑 4

23、0中是良好是是 40低是良好是是 =30低是良好否否 3040低是良好否否 =30中否良好否否 =30低是良好是是 2021-5-3数据挖掘-分类课件ppt29 信息增益的计算 n设属性A具有个不同值a1, a2, , av ，可以用属性A将样 本S划分为 S1, S2, , Sv ，设Sij 是Sj中Ci类的样本数，则由 A划分成子集的熵由下式给出： n有A进行分枝将获得的信息增益可以由下面的公式得到： )s,.,s( I s s.s E(A)mjj v j mjj 1 1 1 E(A)s,.,s ,I(sGain(A)m21 使用属性 后的信息值 未使用属性 的信息值 2021-5-3数据

24、挖掘-分类课件ppt30 信息增益的计算 例题：数据集有2个类。 使用是否学生作为属性，求 该属性的信息增益。 使用信用状况作为属性，求 该属性的信息增益。 年龄年龄收收 入入 是否是否 学生学生 信用信用 状况状况 是否买是否买 电脑电脑 40中是良好是是 40低是良好是是 =30低是良好否否 3040低是良好否否 =30中否良好否否 =30低是良好是是 2021-5-3数据挖掘-分类课件ppt31 ID3算法的例子 n选择信息增益最大的属性特征作为根节点。 nGain(年龄)=0.342 Gain(收入)=0 nGain(是否学生)=0.333 Gain(信用状况)=0 年龄年龄收收 入入

25、 是否是否 学生学生 信用信用 状况状况 是否买是否买 电脑电脑 40中是一般是是 40低是一般是是 =30低是良好否否 3040低是良好否否 =30中否良好否否 =30低是一般是是 年龄年龄？ ？是是 40 2021-5-3数据挖掘-分类课件ppt32 ID3算法的例子 n对于=30的分支 nGain(收入)=0.315 Gain(是否学生)=0.315 Gain(信用状况)=0.815 n对于30 40的分支 nGain(收入)=1 Gain(是否学生)=0 Gain(信用状况)=1 年龄年龄收收 入入 是否是否 学生学生 信用信用 状况状况 是否买是否买 电脑电脑 =30高否良好否否 =

26、30中否良好否否 =30低是一般是是 =30低是良好否否 3040低是良好否否 3040高是一般是 年龄？年龄？ 信用状况？信用状况？收入？收入？是是 40 否否是是是是否否 良好一般高低 2021-5-3数据挖掘-分类课件ppt33 ID3算法的性能分析 nID3算法的假设空间包含所有的决策树，它是关于现有属 性的有限离散值函数的一个完整空间。 nID3算法在搜索的每一步都使用当前的所有训练样例，大 大降低了对个别训练样例错误的敏感性。因此，通过修改 终止准则，可以容易地扩展到处理含有噪声的训练数据。 2021-5-3数据挖掘-分类课件ppt34 ID3算法的性能分析 nID3算法在搜索过程

27、中不进行回溯。所以，它易受无回溯 的爬山搜索中的常见风险影响：收敛到局部最优而不是全 局最优。 nID3算法只能处理离散值的属性。 n信息增益度量存在一个内在偏置，它偏袒具有较多值的属 性。例如，如果有一个属性为日期，那么将有大量取值， 这个属性可能会有非常高的信息增益。假如它被选作树的 根结点的决策属性则可能形成一颗非常宽的树，这棵树可 以理想地分类训练数据，但是对于测试数据的分类性能可 能会相当差。 nID3算法增长树的每一个分支的深度，直到属性的使用无 法导致信息增益。当数据中有噪声或训练样例的数量太少 时，产生的树会过渡拟合训练样例。 n问题：ID3树可以导致过度拟合，那是否它一定能对

28、训练 集完全正确的分类呢？ 2021-5-3数据挖掘-分类课件ppt35 C4.5算法对ID3的主要改进 nC4.5算法是从ID3算法演变而来，除了拥有ID3算 法的功能外，C4.5算法引入了新的方法和增加了 新的功能： n用信息增益比例的概念； n合并具有连续属性的值； n可以处理具有缺少属性值的训练样本； n通过使用不同的修剪技术以避免树的过度拟合； nK交叉验证； n规则的产生方式等。 2021-5-3数据挖掘-分类课件ppt36 信息增益比例的概念 n信息增益比例是在信息增益概念基础上发展起来 的，一个属性的信息增益比例用下面的公式给出： 其中 假如我们以属性A的值为基准对样本进行分割

29、的化， Splitl(A)就是前面熵的概念。 )( )( )( ASplitI AGain AGainRatio )(log)( 1 2j v j j ppASplitI 2021-5-3数据挖掘-分类课件ppt37 信息增益比例的计算 例题：数据集有2个类。 使用是否学生作为属性，求 该属性的信息增益比例。 使用年龄作为属性，求该属 性的信息增益比例。 讨论：信息增益和信息增益 比例的差异在哪里？ 年龄年龄收收 入入 是否是否 学生学生 信用信用 状况状况 是否买是否买 电脑电脑 80低是良好是是 2021-5-3数据挖掘-分类课件ppt38 C4.5处理连续值的属性 n对于连续属性值，C4

30、.5其处理过程如下： n根据属性的值，对数据集排序； n用不同的阈值将数据集动态的进行划分； n取两个实际值中的中点作为一个阈值； n取两个划分，所有样本都在这两个划分中； n得到所有可能的阈值、增益及增益比； n在每一个属性会变为取两个取值，即小于阈值或大于等 于阈值。 n简单地说，针对属性有连续数值的情况，则在训练集中可 以按升序方式排列。如果属性A共有n种取值，则对每个取 值vj（j=1，2，n），将所有的记录进行划分：一部分 小于vj；另一部分则大于或等于vj 。针对每个vj计算划分 对应的增益比率，选择增益最大的划分来对属性A进行离 散化 。 2021-5-3数据挖掘-分类课件ppt

31、39 C4.5处理连续值的属性 例题：使用C4.5算法将连续的属性(收入) 转化为离散的类。 n根据属性的值，对数据集排序； n取两个实际值中的中点作为一个阈值； n取两个划分，所有样本都在这两个划分中； n得到所有可能的阈值、增益及增益比； n在每一个属性会变为取两个取值，即小于阈值或 大于等于阈值。 收入收入是否买是否买 电脑电脑 2500否否 3000否否 3200否否 4050否否 4865是是 6770是是 9800是是 12000是是 2021-5-3数据挖掘-分类课件ppt40 C4.5处理连续值的属性 例题：使用C4.5算法将连续的属性 (收入)转化为离散的类。 n选择增益最大

32、的划分来对属性A进行离散 化 。 nGainRatio(划分：2750)=0.2 nGainRatio(划分：3100)=0.39 nGainRatio(划分：3625)=0.53 nGainRatio(划分：4458)=1 nGainRatio(划分：？)=0.53 nGainRatio(划分：8285)=0.39 nGainRatio(划分：10900)=0.2 n收入小于4458合并为收入低 n收入大于等于4458合并为收入高 收入收入是否买是否买 电脑电脑 收入（离收入（离 散化）散化） 2500否 3000否 3200否 4050否 4865是 6770是 9800是 12000是

33、2021-5-3数据挖掘-分类课件ppt41 C4.5的其他处理 nC4.5处理的样本中可以含有未知属性值，其处理 方法是用最常用的值替代或者是将最常用的值分 在同一类中。 n具体采用概率的方法，依据属性已知的值，对属性和每 一个值赋予一个概率，取得这些概率，取得这些概率依 赖于该属性已知的值。 n规则的产生：规则的产生：一旦树被建立，就可以把树转换成 if-then规则。 n规则存储于一个二维数组中，每一行代表树中的一个规 则，即从根到叶之间的一个路径。表中的每列存放着树 中的结点。 2021-5-3数据挖掘-分类课件ppt42 C4.5算法例子 样本数据 天气温度湿度风网球 SunnyHo

34、t85falseNo SunnyHot90trueNo Overcast Hot78falseYes RainMild96falseYes RainCool80falseYes RainCool70trueNo Overcast Cool65trueYes SunnyMild95falseNo SunnyCool70falseYes RainMild80falseYes SunnyMild70trueYes Overcast Mild90trueYes Overcast Hot75falseYes RainMild80trueNo （1）首先对湿度湿度进行属性离散 化，针对上面的训练集合，通过

35、 检测每个划分而确定最好的划分 在75处，则这个属性的范围就变 为（75）。 （2）计算目标属性打网球打网球分类 的期望信息： （3）计算每个属性的GainRatio： 940. 0 14 5 log 14 5 14 9 log 14 9 )5 , 9(),( 2221 IssI 0.0483 )GainRatio( 0.0248 )GainRatio( 049. 0)(GainRatio 156. 0 577. 1 2467. 0 )(GainRatio 湿度 ；温度 ；风 ；天气 2021-5-3数据挖掘-分类课件ppt43 C4.5算法例子 （4）选取最大的GainRatio，根 据天气

36、天气的取值，得到三个分 枝。 （5）再扩展各分枝节点，得到 最终的决策树（见课本图4- 7 ）。 问题：就天气=Sunny这一分支， 请用C4.5算法构造决策树。 样本数据 天气温度湿度风网球 SunnyHot85falseNo SunnyHot90trueNo SunnyMild95falseNo SunnyCool70falseYes SunnyMild70trueYes 2021-5-3数据挖掘-分类课件ppt44 第三章第三章 分类方法分类方法 内容提要内容提要 n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n实值预测 n与分类有关的问题 2021-5-

37、3数据挖掘-分类课件ppt45 贝叶斯分类 n定义定义4-4-3 3 设设X X是类标号未知的数据样本。设是类标号未知的数据样本。设H H为某种假定，为某种假定， 如数据样本如数据样本X X属于某特定的类属于某特定的类C C。对于分类问题，我们希望对于分类问题，我们希望 确定确定P(H|X)P(H|X)，即给定观测数据样本即给定观测数据样本X X，假定假定H H成立的概率。成立的概率。 贝叶斯定理给出了如下计算贝叶斯定理给出了如下计算P(H|X)P(H|X)的简单有效的方法的简单有效的方法: : nP(X |H)P(X |H)代表假设代表假设H H成立的情况下，观察到成立的情况下，观察到X X

38、的概率。的概率。P(H| P(H| X )X )是是后验概率后验概率，或称为或称为X X发生后观测到发生后观测到H H的的条件概率条件概率。 n例如，假定数据样本由一些人组成，假定例如，假定数据样本由一些人组成，假定X X表示头发颜色，表示头发颜色，H H表示表示 肤色，则肤色，则P(H|X)P(H|X)反映当我们看到反映当我们看到X X是黑色时，我们对是黑色时，我们对H H为黄色的确为黄色的确 信程度。信程度。 )( )()|( )( )( )|( XP HPHXP XP XHP XHP 2021-5-3数据挖掘-分类课件ppt46 朴素贝叶斯分类的工作原理 n观测到的样本具有属性 收入低

39、是学生 信用良好 n现在的问题相当于比较两 个条件概率的大小 P(买电脑|收入低,是学生, 信 用良好) P(不买电脑|收入低,是学生, 信用良好) 收收 入入 是否是否 学生学生 信用信用 状况状况 是否买是否买 电脑电脑 高否良好否否 高是良好是是 中是良好是是 低是良好是是 低否良好否否 低否良好否否 中否良好否否 低是良好？ 2021-5-3数据挖掘-分类课件ppt47 朴素贝叶斯分类 朴素贝叶斯分类的工作过程如下：朴素贝叶斯分类的工作过程如下： n(1) 每个数据样本用一个n维特 征向量X= x1，x2，xn表 示，分别描述对n个属性A 1， A2，An样本的n个度量。 n(2) 假

40、定有m个类C1，C2， Cm，给定一个未知的数据样本X （即没有类标号），分类器将 预测X属于具有最高条件概率 （条件X下）的类。 n也就是说，朴素贝叶斯分类将 未 知 的 样 本 分 配 给 类 C i （1im）当且仅当P(Ci|X) P(Cj|X)，对任意的j=1，2， m，ji。 收收 入入 是否是否 学生学生 信用信用 状况状况 是否买是否买 电脑电脑 高否良好否否 高是良好是是 中是良好是是 低是良好是是 低否良好否否 低否良好否否 中否良好否否 低低是是良好良好？ 2021-5-3数据挖掘-分类课件ppt48 朴素贝叶斯分类(续) 根据贝叶斯定理：根据贝叶斯定理： n由于由于P

41、P( (X X) )对于所有类为对于所有类为常数常数，只需要，只需要P P( (X X| |C Ci i) )* *P P( (C Ci i) )最大最大 即可。即可。 n注意，类的先验概率可以用注意，类的先验概率可以用P(CP(Ci i)=S)=Si i/S/S计算，其中计算，其中S Si i是类是类 C Ci i中的训练样本数，而中的训练样本数，而S S是训练样本总数。是训练样本总数。 n因此问题就转换为计算因此问题就转换为计算P P( (X X| |C Ci i) )。 )( )()|( )( )( )|( XP HPHXP XP XHP XHP 2021-5-3数据挖掘-分类课件ppt

42、49 朴素贝叶斯分类(续) n给定具有许多属性的数据集，计算给定具有许多属性的数据集，计算P P( (X X| |C Ci i) )的计算的计算 量可能非常大且不易计算。为降低计算量可能非常大且不易计算。为降低计算P P( (X X| |C Ci i) )的的 难度，可以做难度，可以做类条件独立的朴素假定。给定样本。给定样本 的类标号，假定的类标号，假定属性值相互条件独立属性值相互条件独立，即在属性，即在属性 间，不存在依赖关系。这样间，不存在依赖关系。这样 nP(P(收入低收入低, ,是学生是学生, , 信用良好信用良好| |买电脑买电脑)=)= P( P(收入低收入低| |买电脑买电脑)

43、)* *P(P(是学生是学生| |买电脑买电脑) )* *P(P(信用良好信用良好 | |买电脑买电脑) ) )|()|( 1 i n k ki CxPCXP 2021-5-3数据挖掘-分类课件ppt50 朴素贝叶斯分类(续) 其中概率其中概率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 sik ik| |s si i， ，其中其中s sik ik

44、是在属性 是在属性A Ak k 上具有值上具有值x xk k的类的类C Ci i的训练样本数，而的训练样本数，而s si i是是C Ci i中的训练样本数。中的训练样本数。 n如果如果A Ak k是连续值属性，则通常假定该属性服从高斯分布。因是连续值属性，则通常假定该属性服从高斯分布。因 而，而， 是高斯分布函数，是高斯分布函数， 而分别为平均值和标准差。而分别为平均值和标准差。 2 2 )( 2 1 ),()|( i i i ii c ck c cckik x exgCxP ),( ii cck xg ii cc , 2021-5-3数据挖掘-分类课件ppt51 朴素贝叶斯分类(续) n例题

45、：计算 P(收入低|不买电脑) P(是学生|不买电脑) P(信用良好|不买电脑) n假设 收入，是否学生，信 用状况互相独立，计算 P(收入低，是学生，信用 良好|不买电脑) 收收 入入 是否是否 学生学生 信用信用 状况状况 是否买是否买 电脑电脑 高否良好否否 高是良好是是 中是良好是是 低是良好是是 低否一般否否 低否良好否否 中否良好否否 低是良好？ 2021-5-3数据挖掘-分类课件ppt52 朴素贝叶斯分类(续) n对 未 知 样 本对 未 知 样 本X X分 类 ， 也 就 是 对 每 个 类分 类 ， 也 就 是 对 每 个 类C C i i ， 计 算计 算 P(P(X X|

46、 |C Ci i) )* *P(P(C Ci i) )。样本样本X X被指派到类被指派到类C Ci i，当且仅当当且仅当P(P(C Ci i| |X X) ) P(P(C C j j| |X X) )， ，11j jmm，j ji i，换言之，换言之，X X被指派到其被指派到其 P(P(X X| |C Ci i) )* *P(P(C Ci i) )最大的类。最大的类。 2021-5-3数据挖掘-分类课件ppt53 朴素贝叶斯分类举例 n数据样本有属性年龄，收 入，是否学生和信用状况。 类标号属性”是否买电脑 “有两个不同值是，否。 设C1对应于类”买电脑”； 则C2对应于类”不买电 脑”。 n

47、我们希望分类的未知样本 为: X=（”年龄=30”，”收 入=中”，”是学生”，” 信用一般”） 年龄年龄收收 入入 是否是否 学生学生 信用信用 状况状况 是否买是否买 电脑电脑 =30高否一般否否 40中否一般是是 40低是一般是是 40低是良好否否 3140 低是良好是是 =30中否一般否否 40中是一般是是 40中否良好否否 =30=30中中是是一般一般 ？ 2021-5-3数据挖掘-分类课件ppt54 朴素贝叶斯分类举例 n我们需要最大化 P(X|Ci)*P(Ci)，i=1，2。 n每个类的先验概率P(Ci)可 以根据训练样本计算： P(C1)=P(买电脑）= P(C2)=P(不买电

48、脑）= n计算P(X|Ci) P（年龄=30,收入=中, 是学生,信用一般|买电 脑) P（年龄=30,收入=中, 是学生,信用一般|不买 电脑) 年龄年龄收收 入入 是否是否 学生学生 信用信用 状况状况 是否买是否买 电脑电脑 =30高否一般否否 40中否一般是是 40低是一般是是 40低是良好否否 3140 低是良好是是 =30中否一般否否 40中是一般是是 40中否良好否否 =30=30中中是是一般一般 ？ 2021-5-3数据挖掘-分类课件ppt55 朴素贝叶斯分类举例 nP（年龄=30,收入=中 ,是学生,信用一般|买 电脑)= P（年龄=30|买电脑)* P（收入=中|买电脑)*

49、 P（是学生|买电脑)* P（信用一般|买电脑) nP（年龄=30,收入=中 ,是学生,信用一般|不 买电脑)= P（年龄=30|不买电脑)* P（收入=中|不买电脑)* P（是学生|不买电脑)* P（信用一般|不买电脑) 年龄年龄收收 入入 是否是否 学生学生 信用信用 状况状况 是否买是否买 电脑电脑 =30高否一般否否 40中否一般是是 40低是一般是是 40低是良好否否 3140 低是良好是是 =30中否一般否否 40中是一般是是 40中否良好否否 =30=30中中是是一般一般 ？ 2021-5-3数据挖掘-分类课件ppt56 朴素贝叶斯分类举例 n假设属性之间独立 P（年龄=30,收

50、入=中, 是学生,信用一般|买电 脑)=0.222*0.444*0.667 *0.667=0.044； P（年龄P（X|不买电 脑)，因此对于样本X，朴素 贝叶斯分类预测为是。 年龄年龄收收 入入 是否是否 学生学生 信用信用 状况状况 是否买是否买 电脑电脑 =30高否一般否否 40中否一般是是 40低是一般是是 40低是良好否否 3140 低是良好是是 =30中否一般否否 40中是一般是是 40中否良好否否 =30=30中中是是一般一般 ？ 2021-5-3数据挖掘-分类课件ppt57 第三章第三章 分类方法分类方法 内容提要内容提要 n分类的基本概念与步骤 n基于距离的分类算法 n决策树

51、分类方法 n贝叶斯分类 n基于规则的分类 n与分类有关的问题 2021-5-3数据挖掘-分类课件ppt58 使用IF-THEN规则分类 n使用规则的分类法是使用一组IF-THEN规则进行 分类。 nIF 条件 THEN 结论 n比如 IF (年龄20 AND 学生=是) THEN买电脑=是 nIF的部分称为前提，THEN的部分称为规则的结论 n规则可以用它的覆盖率和准确率来评价 nncovers是条件(前提)覆盖的样本数，ncorrect是规则 正确分类的样本数。 | )covarage(R covers D n covers correct )accuracy(R n n 2021-5-3数

52、据挖掘-分类课件ppt59 使用IF-THEN规则分类 n规则(收入=低)(信用状况 良好)(是否买电脑=是) 的覆盖率为3/8,而它测准 确率为1/3。 n规 则 ( 信 用 状 况 = 良 好)(是否买电脑=否)的 覆盖率为7/8,而它测准确 率为4/7。 收收 入入 是否是否 学生学生 信用信用 状况状况 是否买是否买 电脑电脑 高否良好否否 高是良好是是 中是良好是是 低是良好是是 低否一般否否 低否良好否否 中否良好否否 低是良好否否 2021-5-3数据挖掘-分类课件ppt60 使用IF-THEN规则分类 n如果一个规则R被一个样本X满足，则称规则R被 X触发。 n比如X =(年龄

53、=18，是学生，信用良好) R为 IF(年龄20 AND 学生=是) THEN买电脑=是 则X的类别为 买电脑 n如果一个样本X同时触发了多个规则，我们需要 制定解决冲突的策略。 n规模序 激活具有最多属性测试的触发规则 n规则序 将规则按重要性进行排序，按顺序进行促发 n如果一个样本X无法促发任何规则 n建立一个缺省或者默认规则 2021-5-3数据挖掘-分类课件ppt61 使用决策树来提取规则 n决策树的规则是互斥与 穷举的 n互斥意味着规则不会存 在冲突，因此每个样本 只能促发一个规则 n穷举意味着一个样本总 能促发一个规则 n由于每个树叶对应一个 一条规则，提取的规则 并不比决策树简单

54、。 年龄？年龄？ 信用状况？信用状况？收入？收入？是是 40 否否是是是是否否 良好一 般 高低 2021-5-3数据挖掘-分类课件ppt62 使用顺序覆盖算法的规则归纳 n在提取规则时，一个现实的问题是是否需要对现 有规则进行拓展， n IF (年龄20) THEN买电脑 是否需要拓展为 IF (年龄 20 AND 学生=是) THEN买电脑 n衡量规则好坏应同时考虑覆盖度与准确率 n 准确率太低 覆盖度太低 2021-5-3数据挖掘-分类课件ppt63 使用顺序覆盖算法的规则归纳 n有两种衡量规则好坏的度量 FOIL_Gain的定义如下 n分别对应于两个规则R与R。正在学习的类称为正样 本

55、(pos)，而其他类称为负样本(neg), pos(neg)为规则 R覆盖的正负样本，而pos(neg)为规则R覆盖的正负 样本。 )log(logFoil_Gain2 2 negpos pos negpos pos pos 2021-5-3数据挖掘-分类课件ppt64 n判断规则(收入=低)(是否 买电脑=否) 是否需要拓展为 规则(收入=低)(信用状况=良 好)(是否买电脑=否) 收收 入入 是否是否 学生学生 信用状信用状 况况 是否买电是否买电 脑脑 高否良好否否 高是良好是是 中是良好是是 低是一般是是 低否良好否否 低否良好否否 中否良好是是 低是良好否否 )log(logFoil

56、_Gain2 2 negpos pos negpos pos pos 2021-5-3数据挖掘-分类课件ppt65 使用顺序覆盖算法的规则归纳 n似然率统计量的的定义如下 n其中m是分类的类别数。fi为满足规则的样本中属于 类i的概率，ei为属于类i的期望(基准)概率。 n似然率越高，说明规则越理想。 m i i i i e f f 1 )log(2_RatioLikelihood 2021-5-3数据挖掘-分类课件ppt66 n分 别 计 算 规 则 ( 收 入 = 低)(是否买电脑=否) 与规则 (收入=低)(信用状况=良 好)(是否买电脑=否) 的似然率。 收收 入入 是否学是否学 生生

57、 信用状信用状 况况 是否买电是否买电 脑脑 高否良好否否 高是良好是是 中是良好是是 低是一般是是 低否良好否否 低否良好否否 中否良好是是 低是良好否否 m i i i i e f f 1 )log(2_RatioLikelihood 2021-5-3数据挖掘-分类课件ppt67 顺序覆盖算法 n终止条件包括，类c没有样本或者返回的规则质量 低于用户指定的阈值等。 输入：D，类标记已知的样本的集合。 Att_vals,所有属性与它们可能值得集合。 输出：IF-THEN规则的集合。 （1）Rule_set=；/规则的初始集为空集 （2）FOR 每个类 c DO （3） repeat （4）

58、Rule=Learn_One_Rule(D,Att_vals,c); （5） 从D中删除Rule覆盖的样本； （6） untile 终止条件满足； （7） Rule_set=Rule_set+Rule; /将新规则添加到规则集 （8）END FOR （9）返回Rule_Set 2021-5-3数据挖掘-分类课件ppt68 使用顺序覆盖算法的规则归纳 nRule_set=； n选择一个类“买电脑”； n选择一个包含一个属性的 规则 n(收入=低)“买电脑” n分别计算其它包含一个属 性的规则的相对于已选择 规则的FOIL_Gain n(收入=高)“买电脑” n(学生=是)“买电脑” n(学生=否

59、)“买电脑” n(信用=良好)“买电脑” n(信用=一般)“买电脑” 收收 入入 是否学是否学 生生 信用状信用状 况况 是否买电是否买电 脑脑 高否一般否否 高是一般是是 高是良好是是 高否良好是是 低否一般是是 低是良好否否 低是良好否否 低否一般否否 )log(logFoil_Gain2 2 negpos pos negpos pos pos 2021-5-3数据挖掘-分类课件ppt69 使用顺序覆盖算法的规则归纳 分别计算规则的Foil_gain n(收入=高)买电脑为1.74 n(学生=是)买电脑为0 n(学生=否)买电脑为0 n(信用=良好)买电脑为0 n(信用=一般)买电脑为0

60、n选择Foil_gain最高的规则 n(收入=高)买电脑 收收 入入 是否学是否学 生生 信用信用 状况状况 是否买是否买 电脑电脑 高否一般否否 高是一般是是 高是良好是是 高否良好是是 低否一般是是 低是良好否否 低是良好否否 低否一般否否 2021-5-3数据挖掘-分类课件ppt70 使用顺序覆盖算法的规则归纳 n对最好的规则R进行拓展 n(收入=高)买电脑 n在规则R中添加一个属性， 得到拓展以后的规则R n(收入=高)(学生=是) n(收入=高)(学生=否) n(收入=高)(信用=良好) n(收入=高)(信用=一般) 分别计算这些规则的相对于R 的Foil_gain 收收 入入 是否