数据挖掘-分类课件

第三章分类方法

内容提要分类的基本概念与步骤

基于距离的分类算法决策树分类方法贝叶斯分类实值预测与分类有关的问题2023/11/291数据挖掘--分类分类的流程根据现有的知识，我们得到了一些关于爬行动物和鸟类的信息，我们能否对新发现的物种，比如动物A，动物B进行分类？动物种类体型翅膀数量脚的只数是否产蛋是否有毛类别狗中04否是爬行动物猪大04否是爬行动物牛大04否是爬行动物麻雀小22是是鸟类天鹅中22是是鸟类大雁中22是是鸟类动物A大02是无？动物B中22否是？2023/11/292数据挖掘--分类分类的流程步骤一：将样本转化为等维的数据特征（特征提取）。所有样本必须具有相同数量的特征兼顾特征的全面性和独立性动物种类体型翅膀数量脚的只数是否产蛋是否有毛类别狗中04否是爬行动物猪大04否是爬行动物牛大04否是爬行动物麻雀小22是是鸟类天鹅中22是是鸟类大雁中22是是鸟类2023/11/293数据挖掘--分类分类的流程步骤二：选择与类别相关的特征（特征选择）。比如，绿色代表与类别非常相关，黑色代表部分相关，灰色代表完全无关动物种类体型翅膀数量脚的只数是否产蛋是否有毛类别狗中04否是爬行动物猪大04否是爬行动物牛大04否是爬行动物麻雀小22是是鸟类天鹅中22是是鸟类大雁中22是是鸟类2023/11/294数据挖掘--分类分类的流程步骤三：建立分类模型或分类器（分类）。分类器通常可以看作一个函数，它把特征映射到类的空间上2023/11/295数据挖掘--分类如何避免过度训练分类也称为有监督学习(supervisedlearning),与之相对于的是无监督学习(unsupervisedlearning),比如聚类。分类与聚类的最大区别在于，分类数据中的一部分的类别是已知的，而聚类数据的类别未知。建立分类模型需要学习一部分已知数据，如果训练时间过长，或者预测模型参数太多而样本较少，将导致过度训练(overfitting)。2023/11/296数据挖掘--分类如何避免过度训练避免过度训练最重要一点是，模型的参数量应远小于样本的数量。应建立训练集(trainingset)和测试集(testset)。训练集应用于建立分类模型测试集应用于评估分类模型K折叠交叉验证(K-foldcrossvalidation)：将初始采样分割成K个子样本(S1，S2,...,Sk)，取K-1个做训练集，另外一个做测试集。交叉验证重复K次，每个子样本都作为测试集一次，平均K次的结果，最终得到一个单一估测。2023/11/297数据挖掘--分类分类模型的评估真阳性(TruePositive)：实际为阳性预测为阳性真阴性(TrueNegative)：实际为阴性预测为阴性假阳性(FalsePositive)：实际为阴性预测为阳性假阴性(FalseNegative)：实际为阳性预测为阴性预测是否正确预测结果比如预测未知动物是鸟类还是爬行动物，阳性代表爬行动物，阴性代表非爬行动物，请大家阐述TP=10，TN=8，FN=3，FP=2是什么意义2023/11/298数据挖掘--分类分类模型的评估灵敏度(Sensitivity)：TP/(TP+FN)也称为查全率(Recall)数据集共有13只爬行动物，其中10只被正确预测为爬行动物，灵敏度为10/13特异度(Specificity):TN/(TN+FP)数据集有10只非爬行动物，其中8只被预测为非爬行动物，特异度为8/10精度(Precision):TP/(TP+FP)分类器预测了12只动物为爬行动物，其中10只确实是爬行动物，精度为10/12准确率(Accuracy):(TP+TN)/(TP+TN+FN+FP)数据集包含23只动物，其中18只预测为正确的分类，准确率为18/232023/11/299数据挖掘--分类分类模型的评估对于非平衡(unblanced)的数据集,以上指标并不能很好的评估预测结果。非平衡的数据集是指阳性数据在整个数据集中的比例很小。比如，数据集包含10只爬行动物，990只爬行动物，此时，是否预测正确爬行动物对准确率影响不大。更平衡的评估标准包括马修斯相关性系数(Matthewscorrelationcoefficient)和ROC曲线。马修斯相关性系数定义为2023/11/2910数据挖掘--分类分类模型的评估ROC曲线通过描述真阳性率(TPR)和假阳性率(FPR)来实现，其中TPR=TP/(TP+FN),FPR=FP/(FP+TN)。大部分分类器都输出一个实数值(可以看作概率),通过变换阈值可以得到多组TPR与FPR的值。2023/11/2911数据挖掘--分类第三章分类方法

内容提要分类的基本概念与步骤基于距离的分类算法决策树分类方法贝叶斯分类实值预测与分类有关的问题2023/11/2912数据挖掘--分类基于距离的分类算法的思路定义4-2给定一个数据库D={t1，t2，…，tn}和一组类C={C1，…，Cm}。假定每个元组包括一些数值型的属性值：ti={ti1，ti2，…，tik}，每个类也包含数值性属性值：Cj={Cj1，Cj2，…，Cjk}，则分类问题是要分配每个ti到满足如下条件的类Cj：sim(ti，Cj)>=sim(ti，Cl)，

Cl∈C，Cl≠Cj，其中sim(ti，Cj)被称为相似性。在实际的计算中往往用距离来表征，距离越近，相似性越大，距离越远，相似性越小。距离的计算方法有多种，最常用的是通过计算每个类的中心来完成。2023/11/2913数据挖掘--分类

基于距离的分类算法的一般性描述算法4-1通过对每个样本和各个类的中心来比较，从而可以找出他的最近的类中心，得到确定的类别标记。算法4-1基于距离的分类算法输入：每个类的中心C1，…，Cm；待分类的元组t。输出：输出类别c。（1）dist=∞；//距离初始化（2）FORi:=1tomDO（3） IFdis(ci，t)<distTHENBEGIN（4） c←i；（5） dist←dist(ci，t)；（6） END.2023/11/2914数据挖掘--分类基于距离的分类方法的直观解释（a）类定义（b）待分类样例（c）分类结果2023/11/2915数据挖掘--分类距离分类例题C1=(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)2023/11/2916数据挖掘--分类K-近邻分类算法K-近邻分类算法（KNearestNeighbors，简称KNN）通过计算每个训练数据到待分类元组的距离，取和待分类元组距离最近的K个训练数据，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.

2023/11/2917数据挖掘--分类KNN的例子姓名 性别身高(米) 类别 Kristina 女1.6矮 Jim 男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

中等只使用身高做特征，K=3，对于样本<kate,1.8,女>应属于哪个类别？仅使用同性别样本做训练，K=3，对于样本<kate,1.8,女>应属于哪个类别？2023/11/2918数据挖掘--分类第三章分类方法

内容提要分类的基本概念与步骤基于距离的分类算法决策树分类方法

贝叶斯分类实值预测与分类有关的问题2023/11/2919数据挖掘--分类决策树表示与例子年龄收入是否学生信用状况是否买电脑<=30高否一般否30—40高否一般是>40中否一般是>40低是一般是>40低是良好否30—40低是良好是<=30中否一般否<=30低是一般是年龄？学生？是信用？<=3030—40>40否是良好一般是否是否2023/11/2920数据挖掘--分类决策树表示与例子决策树（DecisionTree）的每个内部结点表示一个属性（特征），每个分枝代表一个特征的一个（类）取值；每个树叶结点代表类或类分布。决策树分类方法采用自顶向下的递归方式，在决策树的内部结点进行属性的比较，从而判断从该结点向下的分枝，在决策树的叶结点得到结论。从决策树的根到叶结点的一条路径就对应着一条规则，整棵决策树就对应着一组规则。决策树分类模型的建立通常分为两个步骤：决策树生成决策树修剪2023/11/2921数据挖掘--分类决策树生成算法描述算法4-3Generate_decision_tree(samples,attribute_list)/*决策树生成算法*/输入：训练样本samples，由离散值属性表示；输出：一棵决策树。（1）创建结点N；（2）IF

samples

都在同一个类C

THEN

返回N

作为叶结点，以类C标记；（3）IFattribute_list为空THEN

返回N作为叶结点，标记为samples中最普通的类；//多数表决（4）选择attribute_list中具有最高信息增益的属性test_attribute；（5）标记结点N为test_attribute；（6）FORtest_attribute的每个取值ai由结点N长出一个条件为test_attribute=ai的分枝；（7）设si是samples中test_attribute=ai的样本的集合；//一个划分（8）IF

si为空THEN

回退到test_attribute的其它取值；（9）ELSE

加上一个由Generate_decision_tree(si，attribute_list-test_attribute)返回的结点；2023/11/2922数据挖掘--分类决策树修剪算法基本的决策树构造算法没有考虑噪声，因此生成的决策树完全与训练集拟合。在有噪声情况下，将导致过分拟合（Overfitting），即对训练数据的完全拟合反而使对现实数据的分类预测性能下降。比如每个样本都是一个叶子节点。现实世界的数据一般不可能是完美的，可能缺值（MissingValues）；数据不完整；含有噪声甚至是错误的。剪枝是一种克服噪声的基本技术，同时它也能使树得到简化而变得更容易理解。有两种基本的剪枝策略。2023/11/2923数据挖掘--分类决策树修剪算法预先剪枝（Pre-Pruning）：在生成树的同时决定是继续对不纯的训练子集进行划分还是停机。后剪枝（Post-Pruning）：是一种拟合+化简（fitting-and-simplifying）的两阶段方法。首先生成与训练数据完全拟合的一棵决策树，然后从树的叶子开始剪枝，逐步向根的方向剪。剪枝时要用到一个测试数据集合（TuningSet或AdjustingSet），如果存在某个叶子剪去后能使得在测试集上的准确度或其他测度不降低（不变得更坏），则剪去该叶子；否则停机。理论上讲，后剪枝好于预先剪枝，但计算复杂度大。2023/11/2924数据挖掘--分类决策树修剪算法构造好的决策树的关键在于如何选择属性进行树的拓展。研究结果表明，一般情况下,树越小则树的预测能力越强。由于构造最小的树是NP-难问题，因此只能采取用启发式策略来进行。属性选择依赖于各种对例子子集的不纯度（Impurity）度量方法，包括信息增益（InformatinGain）、信息增益比（GainRatio）、Gini-index、距离度量（DistanceMeasure）、J-measure等。2023/11/2925数据挖掘--分类ID3算法ID3是一个著名决策树生成方法：决策树中每一个非叶结点对应着一个非类别属性(特征)，树枝代表这个属性的值。一个叶结点代表从树根到叶结点之间的路径对应的记录所属的类别属性值。每一个非叶结点都将与属性中具有最大信息量的非类别属性相关联。采用信息增益来选择能够最好地将样本分类的属性。对ID3算法采用如下方式讲解：给出信息增益对应的计算公式；通过一个例子来说明它的主要过程。2023/11/2926数据挖掘--分类信息增益的计算设S是s个数据样本的集合，定义m个不同类Ci（i=1，2，…，m），设si是Ci类中的样本的数量。对给定的样本S所期望的信息值由下式给出：其中pi是任意样本属于Ci的概率：si

/s。例题：数据集有4个类，分别有8个，4个，2个，2个样本，求该数据集的信息值。问题：信息值的取值范围是什么？2023/11/2927数据挖掘--分类信息增益的计算例题：数据集有2个类，求该数据集的信息值。年龄收入是否学生信用状况是否买电脑<=30高否良好否30—40高是良好是>40中是良好是>40低是良好是<=30低是良好否30—40低是良好否<=30中否良好否<=30低是良好是2023/11/2928数据挖掘--分类信息增益的计算设属性A具有个不同值{a1,a2,…,av}，可以用属性A将样本S划分为{S1,S2,…,Sv}，设Sij是Sj中Ci类的样本数，则由A划分成子集的熵由下式给出：有A进行分枝将获得的信息增益可以由下面的公式得到：

使用属性后的信息值未使用属性的信息值2023/11/2929数据挖掘--分类信息增益的计算例题：数据集有2个类。使用是否学生作为属性，求该属性的信息增益。使用信用状况作为属性，求该属性的信息增益。年龄收入是否学生信用状况是否买电脑<=30高否良好否30—40高是良好是>40中是良好是>40低是良好是<=30低是良好否30—40低是良好否<=30中否良好否<=30低是良好是2023/11/2930数据挖掘--分类ID3算法的例子选择信息增益最大的属性特征作为根节点。Gain(年龄)=0.342Gain(收入)=0Gain(是否学生)=0.333Gain(信用状况)=0年龄收入是否学生信用状况是否买电脑<=30高否良好否30—40高是一般是>40中是一般是>40低是一般是<=30低是良好否30—40低是良好否<=30中否良好否<=30低是一般是年龄？？？是<=3030—40>402023/11/2931数据挖掘--分类ID3算法的例子对于<=30的分支Gain(收入)=0.315Gain(是否学生)=0.315Gain(信用状况)=0.815对于30—40的分支Gain(收入)=1Gain(是否学生)=0Gain(信用状况)=1年龄收入是否学生信用状况是否买电脑<=30高否良好否<=30中否良好否<=30低是一般是<=30低是良好否30—40低是良好否30—40高是一般是年龄？信用状况？收入？是<=3030—40>40否是是否良好一般高低2023/11/2932数据挖掘--分类ID3算法的性能分析ID3算法的假设空间包含所有的决策树，它是关于现有属性的有限离散值函数的一个完整空间。ID3算法在搜索的每一步都使用当前的所有训练样例，大大降低了对个别训练样例错误的敏感性。因此，通过修改终止准则，可以容易地扩展到处理含有噪声的训练数据。2023/11/2933数据挖掘--分类ID3算法的性能分析ID3算法在搜索过程中不进行回溯。所以，它易受无回溯的爬山搜索中的常见风险影响：收敛到局部最优而不是全局最优。ID3算法只能处理离散值的属性。信息增益度量存在一个内在偏置，它偏袒具有较多值的属性。例如，如果有一个属性为日期，那么将有大量取值，这个属性可能会有非常高的信息增益。假如它被选作树的根结点的决策属性则可能形成一颗非常宽的树，这棵树可以理想地分类训练数据，但是对于测试数据的分类性能可能会相当差。ID3算法增长树的每一个分支的深度，直到属性的使用无法导致信息增益。当数据中有噪声或训练样例的数量太少时，产生的树会过渡拟合训练样例。问题：ID3树可以导致过度拟合，那是否它一定能对训练集完全正确的分类呢？2023/11/2934数据挖掘--分类C4.5算法对ID3的主要改进C4.5算法是从ID3算法演变而来，除了拥有ID3算法的功能外，C4.5算法引入了新的方法和增加了新的功能：用信息增益比例的概念；合并具有连续属性的值；可以处理具有缺少属性值的训练样本；通过使用不同的修剪技术以避免树的过度拟合；K交叉验证；规则的产生方式等。2023/11/2935数据挖掘--分类信息增益比例的概念信息增益比例是在信息增益概念基础上发展起来的，一个属性的信息增益比例用下面的公式给出：其中假如我们以属性A的值为基准对样本进行分割的化，Splitl(A)就是前面熵的概念。

2023/11/2936数据挖掘--分类信息增益比例的计算例题：数据集有2个类。使用是否学生作为属性，求该属性的信息增益比例。使用年龄作为属性，求该属性的信息增益比例。讨论：信息增益和信息增益比例的差异在哪里？年龄收入是否学生信用状况是否买电脑<=20高否良好否20—30高是良好是30—40中是良好是40—50低是良好是50—60低否良好否60—70低否良好否70—80中否良好否>80低是良好是2023/11/2937数据挖掘--分类C4.5处理连续值的属性对于连续属性值，C4.5其处理过程如下：根据属性的值，对数据集排序；用不同的阈值将数据集动态的进行划分；取两个实际值中的中点作为一个阈值；取两个划分，所有样本都在这两个划分中；得到所有可能的阈值、增益及增益比；在每一个属性会变为取两个取值，即小于阈值或大于等于阈值。简单地说，针对属性有连续数值的情况，则在训练集中可以按升序方式排列。如果属性A共有n种取值，则对每个取值vj（j=1，2，┄，n），将所有的记录进行划分：一部分小于vj；另一部分则大于或等于vj。针对每个vj计算划分对应的增益比率，选择增益最大的划分来对属性A进行离散化。2023/11/2938数据挖掘--分类C4.5处理连续值的属性例题：使用C4.5算法将连续的属性(收入)转化为离散的类。根据属性的值，对数据集排序；取两个实际值中的中点作为一个阈值；取两个划分，所有样本都在这两个划分中；得到所有可能的阈值、增益及增益比；在每一个属性会变为取两个取值，即小于阈值或大于等于阈值。收入是否买电脑2500否3000否3200否4050否4865是6770是9800是12000是2023/11/2939数据挖掘--分类C4.5处理连续值的属性例题：使用C4.5算法将连续的属性(收入)转化为离散的类。选择增益最大的划分来对属性A进行离散化。GainRatio(划分：2750)=0.2GainRatio(划分：3100)=0.39GainRatio(划分：3625)=0.53GainRatio(划分：4458)=1GainRatio(划分：？)=0.53GainRatio(划分：8285)=0.39GainRatio(划分：10900)=0.2收入小于4458合并为收入低收入大于等于4458合并为收入高收入是否买电脑收入（离散化）2500否3000否3200否4050否4865是6770是9800是12000是2023/11/2940数据挖掘--分类C4.5的其他处理C4.5处理的样本中可以含有未知属性值，其处理方法是用最常用的值替代或者是将最常用的值分在同一类中。具体采用概率的方法，依据属性已知的值，对属性和每一个值赋予一个概率，取得这些概率，取得这些概率依赖于该属性已知的值。规则的产生：一旦树被建立，就可以把树转换成if-then规则。规则存储于一个二维数组中，每一行代表树中的一个规则，即从根到叶之间的一个路径。表中的每列存放着树中的结点。2023/11/2941数据挖掘--分类C4.5算法例子样本数据天气

温度

湿度

风

网球Sunny Hot 85 false NoSunny Hot 90 true NoOvercast Hot 78 false YesRain Mild 96 false YesRain Cool 80 false YesRain Cool 70 true NoOvercast Cool 65 true YesSunny Mild 95 false NoSunny Cool 70 false YesRain Mild 80 false YesSunny Mild 70 true YesOvercast Mild 90 true YesOvercast Hot 75 false YesRain Mild 80 true No（1）首先对湿度进行属性离散化，针对上面的训练集合，通过检测每个划分而确定最好的划分在75处，则这个属性的范围就变为{（<=75，>75）}。（2）计算目标属性打网球分类的期望信息：

（3）计算每个属性的GainRatio：

2023/11/2942数据挖掘--分类C4.5算法例子（4）选取最大的GainRatio，根据天气的取值，得到三个分枝。（5）再扩展各分枝节点，得到最终的决策树（见课本图4-7）。问题：就天气=Sunny这一分支，请用C4.5算法构造决策树。样本数据天气

温度

湿度

风

网球Sunny Hot 85 false NoSunny Hot 90 true NoSunny Mild 95 false NoSunny Cool 70 false YesSunny Mild 70 true Yes2023/11/2943数据挖掘--分类第三章分类方法

内容提要分类的基本概念与步骤基于距离的分类算法决策树分类方法贝叶斯分类实值预测与分类有关的问题2023/11/2944数据挖掘--分类贝叶斯分类定义4-3设X是类标号未知的数据样本。设H为某种假定，如数据样本X属于某特定的类C。对于分类问题，我们希望确定P(H|X)，即给定观测数据样本X，假定H成立的概率。贝叶斯定理给出了如下计算P(H|X)的简单有效的方法:P(X|H)代表假设H成立的情况下，观察到X的概率。P(H|X)是后验概率，或称为X发生后观测到H的条件概率。例如，假定数据样本由一些人组成，假定X表示头发颜色，H表示肤色，则P(H|X)反映当我们看到X是黑色时，我们对H为黄色的确信程度。2023/11/2945数据挖掘--分类朴素贝叶斯分类的工作原理观测到的样本具有属性收入低是学生信用良好现在的问题相当于比较两个条件概率的大小P(买电脑|收入低,是学生,信用良好)P(不买电脑|收入低,是学生,信用良好)收入是否学生信用状况是否买电脑高否良好否高是良好是中是良好是低是良好是低否良好否低否良好否中否良好否低是良好？2023/11/2946数据挖掘--分类朴素贝叶斯分类朴素贝叶斯分类的工作过程如下：(1)

每个数据样本用一个n维特征向量X={x1，x2，……，xn}表示，分别描述对n个属性A1，A2，……，An样本的n个度量。(2)假定有m个类C1，C2，…，Cm，给定一个未知的数据样本X（即没有类标号），分类器将预测X属于具有最高条件概率（条件X下）的类。也就是说，朴素贝叶斯分类将未知的样本分配给类Ci（1≤i≤m）当且仅当P(Ci|X)>P(Cj|X)，对任意的j=1，2，…，m，j≠i。收入是否学生信用状况是否买电脑高否良好否高是良好是中是良好是低是良好是低否良好否低否良好否中否良好否低是良好？2023/11/2947数据挖掘--分类朴素贝叶斯分类(续)根据贝叶斯定理：

由于P(X)对于所有类为常数，只需要P(X|Ci)*P(Ci)最大即可。注意，类的先验概率可以用P(Ci)=Si/S计算，其中Si是类Ci中的训练样本数，而S是训练样本总数。因此问题就转换为计算P(X|Ci)。

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

其中概率P(x1|Ci)，P(x2|Ci)，……，P(xn|Ci)可以由训练样本估值。如果Ak是离散属性，则P(xk|Ci)=sik|si，其中sik是在属性Ak上具有值xk的类Ci的训练样本数，而si是Ci中的训练样本数。

如果Ak是连续值属性，则通常假定该属性服从高斯分布。因而，

是高斯分布函数，而分别为平均值和标准差。

2023/11/2950数据挖掘--分类朴素贝叶斯分类(续)例题：计算P(收入低|不买电脑)P(是学生|不买电脑)P(信用良好|不买电脑)假设收入，是否学生，信用状况互相独立，计算P(收入低，是学生，信用良好|不买电脑)收入是否学生信用状况是否买电脑高否良好否高是良好是中是良好是低是良好是低否一般否低否良好否中否良好否低是良好？2023/11/2951数据挖掘--分类朴素贝叶斯分类(续)对未知样本X分类，也就是对每个类Ci，计算P(X|Ci)*P(Ci)。样本X被指派到类Ci，当且仅当P(Ci|X)>P(Cj|X)，1≤j≤m，j≠i，换言之，X被指派到其P(X|Ci)*P(Ci)最大的类。

2023/11/2952数据挖掘--分类朴素贝叶斯分类举例数据样本有属性年龄，收入，是否学生和信用状况。类标号属性”是否买电脑“有两个不同值{是，否}。设C1对应于类”买电脑”；则C2对应于类”不买电脑”。我们希望分类的未知样本为:X=（”年龄<=30”，”收入=中”，”是学生”，”信用一般”）年龄收入是否学生信用状况是否买电脑<=30高否一般否<=30高否良好否31—40高否一般是>40中否一般是>40低是一般是>40低是良好否31—40低是良好是<=30中否一般否<=30低是一般是>40中是一般是<=30中是良好是31—40中否良好是31—40高是一般是>40中否良好否<=30中是一般？？？2023/11/2953数据挖掘--分类朴素贝叶斯分类举例我们需要最大化P(X|Ci)*P(Ci)，i=1，2。每个类的先验概率P(Ci)可以根据训练样本计算：P(C1)=P(买电脑）=P(C2)=P(不买电脑）=计算P(X|Ci)P（"年龄<=30","收入=中","是学生","信用一般"|买电脑)P（"年龄<=30","收入=中","是学生","信用一般"|不买电脑)年龄收入是否学生信用状况是否买电脑<=30高否一般否<=30高否良好否31—40高否一般是>40中否一般是>40低是一般是>40低是良好否31—40低是良好是<=30中否一般否<=30低是一般是>40中是一般是<=30中是良好是31—40中否良好是31—40高是一般是>40中否良好否<=30中是一般？？？2023/11/2954数据挖掘--分类朴素贝叶斯分类举例P（"年龄<=30","收入=中","是学生","信用一般"|买电脑)=P（"年龄<=30"|买电脑)*P（"收入=中"|买电脑)*P（"是学生"|买电脑)*P（"信用一般"|买电脑)P（"年龄<=30","收入=中","是学生","信用一般"|不买电脑)=P（"年龄<=30"|不买电脑)*P（"收入=中"|不买电脑)*P（"是学生"|不买电脑)*P（"信用一般"|不买电脑)年龄收入是否学生信用状况是否买电脑<=30高否一般否<=30高否良好否31—40高否一般是>40中否一般是>40低是一般是>40低是良好否31—40低是良好是<=30中否一般否<=30低是一般是>40中是一般是<=30中是良好是31—40中否良好是31—40高是一般是>40中否良好否<=30中是一般？？？2023/11/2955数据挖掘--分类朴素贝叶斯分类举例假设属性之间独立P（"年龄<=30","收入=中","是学生","信用一般"|买电脑)=0.222*0.444*0.667*0.667=0.044；P（"年龄<=30","收入=中","是学生","信用一般"|不买电脑)=0.600*0.400*0.200*

0.400=0.019；P（X|买电脑)>P（X|不买电脑)，因此对于样本X，朴素贝叶斯分类预测为"是"。年龄收入是否学生信用状况是否买电脑<=30高否一般否<=30高否良好否31—40高否一般是>40中否一般是>40低是一般是>40低是良好否31—40低是良好是<=30中否一般否<=30低是一般是>40中是一般是<=30中是良好是31—40中否良好是31—40高是一般是>40中否良好否<=30中是一般？？？2023/11/2956数据挖掘--分类第三章分类方法

内容提要分类的基本概念与步骤基于距离的分类算法决策树分类方法贝叶斯分类基于规则的分类

与分类有关的问题2023/11/2957数据挖掘--分类使用IF-THEN规则分类使用规则的分类法是使用一组IF-THEN规则进行分类。IF条件THEN结论比如IF(年龄<20AND学生=是)THEN买电脑=是IF的部分称为前提，THEN的部分称为规则的结论规则可以用它的覆盖率和准确率来评价ncovers是条件(前提)覆盖的样本数，ncorrect是规则正确分类的样本数。2023/11/2958数据挖掘--分类使用IF-THEN规则分类规则(收入=低)^(信用状况良好)(是否买电脑=是)的覆盖率为3/8,而它测准确率为1/3。规则(信用状况=良好)(是否买电脑=否)的覆盖率为7/8,而它测准确率为4/7。收入是否学生信用状况是否买电脑高否良好否高是良好是中是良好是低是良好是低否一般否低否良好否中否良好否低是良好否2023/11/2959数据挖掘--分类使用IF-THEN规则分类如果一个规则R被一个样本X满足，则称规则R被X触发。比如X=(年龄=18，是学生，信用良好)R为IF(年龄<20AND学生=是)THEN买电脑=是则X的类别为买电脑如果一个样本X同时触发了多个规则，我们需要制定解决冲突的策略。规模序激活具有最多属性测试的触发规则规则序将规则按重要性进行排序，按顺序进行促发如果一个样本X无法促发任何规则建立一个缺省或者默认规则2023/11/2960数据挖掘--分类使用决策树来提取规则决策树的规则是互斥与穷举的互斥意味着规则不会存在冲突，因此每个样本只能促发一个规则穷举意味着一个样本总能促发一个规则由于每个树叶对应一个一条规则，提取的规则并不比决策树简单。年龄？信用状况？收入？是<=3030—40>40否是是否良好一般高低2023/11/2961数据挖掘--分类使用顺序覆盖算法的规则归纳在提取规则时，一个现实的问题是是否需要对现有规则进行拓展，IF(年龄<20)THEN买电脑是否需要拓展为IF(年龄<20AND学生=是)THEN买电脑衡量规则好坏应同时考虑覆盖度与准确率准确率太低覆盖度太低2023/11/2962数据挖掘--分类使用顺序覆盖算法的规则归纳有两种衡量规则好坏的度量FOIL_Gain的定义如下分别对应于两个规则R与R'。正在学习的类称为正样本(pos)，而其他类称为负样本(neg),pos(neg)为规则R覆盖的正负样本，而pos'(neg')为规则R'覆盖的正负样本。2023/11/2963数据挖掘--分类判断规则(收入=低)(是否买电脑=否)是否需要拓展为规则(收入=低)^(信用状况=良好)(是否买电脑=否)收入是否学生信用状况是否买电脑高否良好否高是良好是中是良好是低是一般是低否良好否低否良好否中否良好是低是良好否2023/11/2964数据挖掘--分类使用顺序覆盖算法的规则归纳似然率统计量的的定义如下其中m是分类的类别数。fi为满足规则的样本中属于类i的概率，ei为属于类i的期望(基准)概率。似然率越高，说明规则越理想。2023/11/2965数据挖掘--分类分别计算规则(收入=低)(是否买电脑=否)与规则(收入=低)^(信用状况=良好)(是否买电脑=否)的似然率。收入是否学生信用状况是否买电脑高否良好否高是良好是中是良好是低是一般是低否良好否低否良好否中否良好是低是良好否2023/11/2966数据挖掘--分类

顺序覆盖算法终止条件包括，类c没有样本或者返回的规则质量低于用户指定的阈值等。输入：D，类标记已知的样本的集合。Att_vals,所有属性与它们可能值得集合。输出：IF-THEN规则的集合。（1）Rule_set={}；//规则的初始集为空集（2）FOR每个类cDO

（3） repeat（4）Rule=Learn_One_Rule(D,Att_vals,c);（5） 从D中删除Rule覆盖的样本；（6）untile终止条件满足；（7） Rule_set=Rule_set+Rule;//将新规则添加到规则集（8）ENDFOR（9）返回Rule_Set2023/11/2967数据挖掘--分类使用顺序覆盖算法的规则归纳Rule_set={}；选择一个类“买电脑”；选择一个包含一个属性的规则(收入=低)

“买电脑”分别计算其它包含一个属性的规则的相对于已选择规则的FOIL_Gain(收入=高)“买电脑”(学生=是)

“买电脑”(学生=否)

“买电脑”(信用=良好)

“买电脑”(信用=一般)

“买电脑”收入是否学生信用状况是否买电脑高否一般否高是一般是高是良好是高否良好是低否一般是低是良好否低是良好否低否一般否2023/11/2968数据挖掘--分类使用顺序覆盖算法的规则归纳分别计算规则的Foil_gain(收入=高)"买电脑"为1.74(学生=是)"买电脑"为0(学生=否)"买电脑"为0(信用=良好)"买电脑"为0(信用=一般)"买电脑"为0选择Foil_gain最高的规则(收入=高)"买电脑"收入是否学生信用状况是否买电脑高否一般否高是一般是高是良好是高否良好是低否一般是低是良好否低是良好否低否一般否2023/11/2969数据挖掘--分类使用顺序覆盖算法的规则归纳对最好的规则R进行拓展(收入=高)"买电脑"在规则R中添加一个属性，得到拓展以后的规则R'(收入=高)^(学生=是)(收入=高)^(学生=否)(收入=高)^(信用=良好)(收入=高)^(信用=一般)分别计算这些规则的相对于R的Foil_gain收入是否学生信用状况是否买电脑高否一般否高是一般是高是良好是高否良好是低否一般是低是良好否低是良好否低否一般否2023/11/2970数据挖掘--分类使用顺序覆盖算法的规则归纳分别计算规则的Foil_gain(收入=高)^(学生=是)为0.84(收入=高)^(学生=否)为-1.16(收入=高)^(信用=良好)为0.84(收入=高)^(信用=一般)为-1.16选择Foil_gain最高的规则(收入=高)^(学生=是)

(收入=高)^(信用=良好)由于这两个规则准确率已经是100%，因此不用拓展收入是否学生信用状况是否买电脑高否一般否高是一般是高是良好是高否良好是低否一般是低是良好否低是良好否低否一般否2023/11/2971数据挖掘--分类使用顺序覆盖算法的规则归纳将规则覆盖的样本从数据集D中删除，对剩下的正样本生成规则收入是否学生信用状况是否买电脑高否一般否低否一般是低是良好否低是良好否低否一般否2023/11/2972数据挖掘--分类使用顺序覆盖算法的规则归纳收入是否学生信用状况是否买电脑高否一般否低是良好否低是良好否低否一般否选择另外一个类“不买电脑”(生成其它类的规则)；选择一个包含一个属性的规则(收入=低)

“不买电脑”分别计算其它包含一个属性的规则的相对于已选择规则的FOIL_Gain(收入=高)“不买电脑”(学生=是)

“不买电脑”(学生=否)

“不买电脑”(信用=良好)

“不买电脑”(信用=一般)

“不买电脑”2023/11/2973数据挖掘--分类第三章分类方法

内容提要分类的基本概念与步骤基于距离的分类算法决策树分类方法贝叶斯分类基于规则的分类实值预测

2023/11/2974数据挖掘--分类实值预测分类：把样本分配到若干类之一(离散的)。比如预测是普通员工、中层管理还是高级管理人员预测：预测样本的某个属性值(连续的)。比如预测收入工作年限周工作时间月薪14025004483000540350074040008484500640？948？2023/11/2975数据挖掘--分类实值预测实值预测方法有两种线性回归和多元回归非线性回归2023/11/2976数据挖掘--分类实值预测在回归分析中，只包括一个自变量和一个因变量，且二者的关系可用一条直线近似表示，这种回归分析称为一元线性回归分析。x={2,4,5,7,9};y={6,10,12,16,20};如果回归分析中包括两个或两个以上的自变量，且因变量和自变量之间是线性关系，则称为多元线性回归分析。x={(2,4),(4,0),(5,6),(7,1),(9,-3)};y={10,4,17,9,3};2023/11/2977数据挖掘--分类一元线性回归模型给n个随机样本(Yi,Xi,)，则Y与X的线性回归模型可以写为其中b0

，b1是参数

是被称为误差项的随机变量,这是由于我们建立的线性回归模型可能是不完美的

工作年限月薪12500430005350074000845006？9？2023/11/2978数据挖掘--分类线性回归模型的求解回归模型的求解相当于求解β使得一元线性回归分析的求解2023/11/2979数据挖掘--分类一元线性回归模型例题：请建立右表的线性回归模型。

工作年限月薪12500430005350074000845006？9？2023/11/2980数据挖掘--分类多元线性回归模型给n个随机样本(Yi,Xi1,Xi2,...,Xip)，则Y与X的线性回归模型可以写为其中b0

，b1，b2，，bn是参数

是被称为误差项的随机变量,这是由于我们建立的线性回归模型可能是不完美的

工作年限周工作时间月薪240350044832005406500104058001248720018404300640？948？2023/11/2981数据挖掘--分类线性回归模型的求解回归模型的求解相当于求解β使得多元线性回归分析的求解其中X为2023/11/2982数据挖掘--分类AQ算法多元回归模型的求解在许多软件中都可以得到，比如Matlab，SAS，SPSS，Weka等。2023/11/2983数据挖掘--分类AQR算法有关定义AQR为每一个分类推导出一条规则，每一条规则形式如下：if<cover>thenpredict<class>。在一个属性上的基本测试被称为一个Selector。下面是一些Selector的例子：<Cloudy=yes>或<Temp>60>。AQR允许测试做{=，≤，≥，≠}。Selectors的合取被称为复合（Complex），Complexes之间的析取被称为覆盖（Cover）。如果一个表达式对某个样本为真，则我们称其为对这个样本的一个覆盖。这样，一个空Complex覆盖所有的样本，而一个空Cover不覆盖任何样本。在AQR中，一个新样本被区分是看其属于哪个推导出来的规则。如果该样本只满足一条规则，则这个样本就属于这条规则；如果该样本满足多条规则，则被这些规则所预测的最频繁的分类被赋予这条规则；如果该样本不属于任何规则，则其分类为样本集中最频繁的分类。2023/11/2984数据挖掘--分类AQR算法描述算法4-5AQR输入：正例样本POS；反例样本NEG。输出：覆盖COVER。（1）COVER=Φ；//初始化COVER为空集Φ（2）WHILECOVERdoesnotcoverallpositiveexamplesinPOSDOBEGIN（3）SelectaSEED；/选取一个种子SEED，例如没有被COVER覆盖的一个正样例（4）CallprocedureSTAR（SEED，NEG）；//产生一个能覆盖种子而同时排除所有反例的星（5）SelectthebestComplexBESTfromtheSTARaccordingtouser-definedcriteria；/*从星中选取一个最好的复合*/（6）AddBESTasanextradisjucttoCOVER/*把最好的复合与COVER合取，形成新的COVER*/（7）END（8）RETURNCOVER.在算法AQR中调用了过程STAR，来排除所有的反例，产生覆盖种子的星。2023/11/2985数据挖掘--分类AQR算法描述(续)算法4-6

STAR输入：种子SEED；反例NEG。输出：星STAR。（1）初始化STAR为空Complex（2）WHILEoneormoreComplexesinSTARcoverssomenegativeexamplesinNEGBEGIN/*如果STAR中的一个或多个Complex覆盖NEG中的负样例*/（3）SelectanegativeexampleEnegcoveredbyaComplexinSTAR；/*选取一个被STAR中的Complex覆盖的负样例*/（4）LetEXTENSIONbeallSelectorsthatcoverSEEDbutnotENEG；/*令EXTENSION为那些覆盖SEED但不覆盖ENEG的Selectors；*/（5）LetSTARbetheset{x∧y|x∈STAR，y∈EXTENSION}；/*令STAR={x∧y|x∈STAR，y∈EXTENSION}；*/（6）RemoveallComplexesinSTARsubsumedbyotherComplexesinSTAR；/*从STAR中除去被其他Complexes所包含的Complexes；*/（7）RemovetheworstComplexesfromSTARUNTILsizeofSTARislessthanorequaltouser-definedmaximum（maxstar）/*删除STAR中最坏的Complex直到STAR的大小等于或小于用户定义的最大数目maxstar*/（8）END（9）RETURNSTAR./*返回一系列覆盖SEED但不覆盖NEG的规则*/2023/11/2986数据挖掘--分类AQR算法举例假设现有一个训练集，其包含两种属性：size（属性值：micro，tiny，mid，big，huge，vast）type（属性值：bicycle，motorcycle，car，prop，jet，glider）现有正例、反例样本分别如表4-6，表4-7所示：下面给出用AQR算法对giant2-wheeler类的规则进行获取过程，具体步骤如下：（１）COVER={}。（２）空cover不覆盖任何样本，进入循环。（３）一开始COVER并没有覆盖任何正例，假定从正例中选取的SEED为{size=huge，type=bicycle}。（４）调用STAR（SEED，NEG）去产生一个覆盖SEED但不包含NEG的STAR集合；初始化STAR为空，即STAR={}。空的complex覆盖所有样例，STAR覆盖多个负样例，进入循环。

a)选取一个被STAR中的复合覆盖的负样例ENEG，假定被选取的是Eneg={size=tiny，type=motorcycle}。

b)使EXTENSION为所有覆盖SEED但不覆盖ENEG的选择，则EXTENSION包括size=huge和type=bicycle，则又根据STAR={x∧y|x∈STAR，y∈EXTENSION}，因此，STAR={size=huge

type=bicycle}。c)在这里定义maxstar为2，可不对STAR进行精简。d)接着选取另一个被STAR中的复合覆盖的负样例ENEG，显然已经没有这样的负样例，因此，STAR={size=huge

type=bicycle}。从STAR（SEED，NEG）返回。反例样本sizetypeclassTinymotorcycleconventionaltransportationtinycarconventionaltransportationmidcarconventionaltransportationmicrojetfastplaneTinyjetfastplaneMidjetfastplane正例样本sizetypeclassHugebicyclegiant2-wheelerHugemotorcyclegiant2-wheeler2023/11/2987数据挖掘--分类AQR算法举例（5）BEST={size=huge

type=bicycle}，COVER={size=huge

type=bicycle}。

（6）显然COVER不能覆盖所有的正例，从正例中选取另一个SEED={size=huge，type=motorcycle}。（7）调用STAR（SEED，NEG）去产生一个覆盖SEED但不包含NEG的STAR集合。初始化STAR为空，即STAR={}；空的complex覆盖所有样例，所以STAR覆盖负样例，进入循环；

a)假定被选取的是Eneg={size=tiny，type=motorcycle}；

b)使EXTENSION为所有覆盖SEED但不覆盖Eneg的选择，则EXTENSION包括size=huge，则又根据STAR={x∧y|x∈STAR，y∈EXTENSION}，因此，STAR={size=huge}；c)接着选取另一个被STAR中的复合覆盖的负样例Eneg，显然已经没有这样的负样例，因此，STAR={size=huge}；d)接着选取另一个被STAR中的复合覆盖的负样例ENEG，显然已经没有这样的负样例，因此，STAR={size=huge

type=bicycle}。从STAR（SEED，NEG）返回。（8）BEST={size=huge}，将BEST添加到COVER中，COVER={size=huge

type=bicycle

size=huge}={size=huge}。（9）这时，COVER已经覆盖到全部的正例，则算法结束。输出规则为gaint2-wheeler

size=huge。假设现有一个训练集，其包含两种属性：size（属性值：micro，tiny，mid，big，huge，vast）type（属性值：bicycle，motorcycle，car，prop，jet，glider）现有正例、反例样本分别如表4-6，表4-7所示：反例样本sizetypeclassTinymotorcycleconventionaltransportationtinycarconventionaltransportationmidcarconventionaltransportationmicrojetfastplaneTinyjetfastplaneMidjetfastplane正例样本sizetypeclassHugebicyclegiant2-wheelerHugemotorcyclegiant2-wheeler2023/11/2988数据挖掘--分类CN2算法描述CN2使用一种基于噪音估计的启发式方法，使用这种方法可以不用对所有的训练样本进行正确的区分，但是规约出的规则在对新数据的处理上有很好的表现。算法4-7CN2输入：E/*E为训练样本*/输出：RULE_LIST/*返回一个覆盖若干样例的规则*/（1）LetRULE_LISTbetheemptylist；/*初始化RULES_LIST为空；*/（2）REPEAT（3）LetBEST_CPXbeFind_Best_Complex（E）；/*寻找最佳的规则Find_Best_Complex（E）并将其结果放入BEST_CPX中；*/（4）IFBEST_CPXisnotnilTHENBEGIN（5）LetE’betheexamplescoveredbyBEST_CPX；/*令E’为BEST_CPX覆盖的所有样例*/（6）RemovefromEtheexamplesE′coveredbyBEST_CPX；/*从训练样本E中除去E’，即E=E-E’；*/（7） LetCbethemostcommonclassofexamplesinE’；/*令C为样本子集E’中最频繁的分类标号；*/（8）Addtherule‘ifBEST_CPXthenclass=C’totheendofRULE_LIST；/*将规则‘ifBEST_CPXthenclass=C’添加到RULES_LIST中*/（9）END（10）UNTILBEST_CPXisnilorEisempty./*直到BEST_CPX为空或者训练样本E为空*/（11）RETURNRULE_LIST算法CN2需要通过调用函数Find_Best_Complex，它的描述写成下面算法4-8。2023/11/2989数据挖掘--分类CN2算法描述(续)算法4-8Find_Best_Complex输入：E/*E为训练样本*/输出：BEST_CPX/*返回最佳的规则BEST_CPX*/（1）LetthesetSTARcontainonlytheemptyComplex；/*初始化集合STAR为空Complex；*/（2）LetBEST_CPXbenil；/*初始化BEST_CPX为空*/（3）LetSELECTORSbethesetofallpossibleSelectors；/*集合SELECTOR为所有可能的选择*/（4）WHILESTARisnotemptyDOBEGIN（5） LetNEWSTARbetheset{x∧y|x∈STAR，y∈EXTENSION}；/*令NEWSTAR={x∧y|x∈STAR，y∈EXTENSION}；*/（6） RemoveallComplexesinNEWSTARthatareeitherinSTARorarenull；/*从NEWSTAR中除去包括在STAR中的Complex或者为空的Complex*/（7） FOReverycomplexCiinNEWSTAR（8）IFCiisstatisticallysignificantwhentestedonEandbetterthanBEST_CPX accordingtouser-definedcriteriawhentest