数据挖掘分类专题培训课件.ppt

,Click to edit Master,Click to edit Master text styles Click to edit Master Click to edit Master,Second level,Third level,Fourth level,Fifth level,*,DMKD Sides By MAO,*,Click to edit Master,Click to edit Master text styles Click to edit Master Click to edit Master,Second level,Third level,Fourth level,Fifth level,*,DMKD Sides By MAO,*,Click to edit Master,Click to edit Master text styles Click to edit Master Click to edit Master,Second level,Third level,Fourth level,Fifth level,*,DMKD Sides By MAO,*,数据挖掘分类,分类的流程,根据现有的知识，我们得到了一些关于爬行动物和鸟类的信息，我们能否对新发现的物种，比如动物A，动物B进行分类？,2025/5/23 周五,2,分类的流程,步骤一：将样本转化为等维的数据特征（特征提取）。,所有样本必须具有相同数量的特征,兼顾特征的全面性和独立性,2025/5/23 周五,3,分类的流程,步骤二：选择与类别相关的特征（特征选择）。,比如，绿色代表与类别非常相关，黑色代表部分相关，灰色代表完全无关,2025/5/23 周五,4,分类的流程,步骤三：建立分类模型或分类器（分类）。,分类器通常可以看作一个函数，它把特征映射到类的空间上,2025/5/23 周五,5,如何避免过度训练,分类,也称为,有监督学习,(supervised learning),与之相对于的是无监督学习(unsupervised learning),比如聚类。,分类与聚类的最大区别在于，分类数据中的一部分的类别是已知的，而聚类数据的类别未知。,建立分类模型需要学习一部分已知数据，如果训练时间过长，或者预测模型参数太多而样本较少，将导致,过度训练,(overfitting)。,2025/5/23 周五,6,如何避免过度训练,避免过度训练最重要一点是，,模型的参数量应远小于样本的数量,。,应建立,训练集,(training set)和,测试集,(test set)。,训练集应用于建立分类模型,测试集应用于评估分类模型,K折叠交叉验证,(K-fold cross validation)：将初始采样分割成K个子样本(S,1,，S,2,.,S,k,)，取K-1个做训练集，另外一个做测试集。交叉验证重复K次，每个子样本都作为测试集一次，平均K次的结果，最终得到一个单一估测。,2025/5/23 周五,7,分类模型的评估,真阳性(,T,rue,P,ositive)：实际为阳性 预测为阳性,真阴性(,T,rue,N,egative)：实际为阴性 预测为阴性,假阳性(,F,alse,P,ositive)：实际为阴性 预测为阳性,假阴性(,F,alse,N,egative)：实际为阳性 预测为阴性,预测是否正确 预测结果,比如预测未知动物是鸟类还是爬行动物，阳性代表爬行动物，阴性代表,非,爬行动物，请大家阐述 TP=10，TN=8，FN=3，FP=2是什么意义,2025/5/23 周五,8,分类模型的评估,灵敏度,(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/23,2025/5/23 周五,9,分类模型的评估,对于非平衡(unblanced)的数据集,以上指标并不能很好的评估预测结果。,非平衡的数据集是指阳性数据在整个数据集中的比例很小。比如，数据集包含10只爬行动物，990只爬行动物，此时，是否预测正确爬行动物对准确率影响不大。,更平衡的评估标准包括,马修斯相关性系数,(Matthews correlation coefficient)和,ROC曲线,。,马修斯相关性系数,定义为,2025/5/23 周五,10,分类模型的评估,ROC曲线通过描述真阳性率(TPR)和假阳性率(FPR)来实现，其中TPR=TP/(TP+FN),FPR=FP/(FP+TN)。,大部分分类器都输出一个实数值(可以看作概率),通过变换阈值可以得到多组TPR与FPR的值。,2025/5/23 周五,11,第三章 分类方法,内容提要,分类的基本概念与步骤,基于距离的分类算法,决策树分类方法,贝叶斯分类,实值预测,与分类有关的问题,2025/5/23 周五,12,基于距离的分类算法的思路,定义,4-2,给定一个数据库,D,=,t,1,，,t,2,，,，,t,n,和一组类,C,=,C,1,，,，,C,m,。假定每个元组包括一些数值型的属性值：,t,i,=,t,i1,，,t,i2,，,，,t,ik,，每个类也包含数值性属性值：,C,j,=,C,j1,，,C,j2,，,，,C,jk,，则分类问题是要分配每个,t,i,到满足如下条件的类,C,j,：,sim,(,t,i,，,C,j,)=,sim,(,t,i,，,C,l,),，,C,l,C,，,C,l,C,j,，,其中,sim,(,t,i,，,C,j,),被称为相似性。,在实际的计算中往往用,距离,来表征，距离越近，相似性越大，距离越远，相似性越小。,距离的计算方法有多种，最常用的是通过计算每个类的中心来完成。,2025/5/23 周五,13,基于距离的分类算法的一般性描述,算法,4-1,通过对每个样本和各个类的中心来比较，从而可以找出他的最近的类中心，得到确定的类别标记。,算法,4-1,基于距离的分类算法,输入：每个类的中心,C,1,，,，,C,m,；待分类的元组,t,。,输出：输出类别,c,。,（,1,）,dist=,；,/,距离初始化,（,2,）,FOR i:=1 to m DO,（,3,）,IF,dis,(,c,i,，,t,)dist THEN BEGIN,（,4,）,c,i,；,（,5,）,distdist(,c,i,，,t,),；,（,6,）,END.,2025/5/23 周五,14,基于距离的分类方法的直观解释,（,a,）类定义,（,b,）待分类样例,（,c,）分类结果,2025/5/23 周五,15,距离分类例题,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),2025/5/23 周五,16,K-,近邻分类算法,K-,近邻分类算法（,K Nearest Neighbors,，简称,KNN,）通过计算每个训练数据到待分类元组的距离，取和待分类元组距离最近的,K,个训练数据，,K,个数据中哪个类别的训练数据占多数，则待分类元组就属于哪个类别。,算法,4-2 K-,近邻分类算法,输入：训练数据,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.,2025/5/23 周五,17,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.7,3,中等,只使用身高做特征，K=3，对于样本应属于哪个类别？,仅使用同性别样本做训练，K=3，对于样本应属于哪个类别？,2025/5/23 周五,18,第三章 分类方法,内容提要,分类的基本概念与步骤,基于距离的分类算法,决策树分类方法,贝叶斯分类,实值预测,与分类有关的问题,2025/5/23 周五,19,决策树表示与例子,年龄,？,学生,？,是,信用,？,40,否,是,良好,一般,是,否,是,否,2025/5/23 周五,20,决策树表示与例子,决策树,（,Decision Tree,）的每个内部结点表示一个属性（特征），每个分枝代表一个特征的一个（类）取值；,每个树叶结点代表类或类分布。,决策树分类方法采用自顶向下的递归方式，在决策树的内部结点进行属性的比较，从而判断从该结点向下的分枝，在决策树的叶结点得到结论。,从决策树的根到叶结点的一条路径就对应着一条规则，整棵决策树就对应着一组规则。,决策树分类模型的建立通常分为两个步骤：,决策树生成,决策树修剪,2025/5/23 周五,21,决策树生成算法描述,算法,4-3 Generate_decision_tree(samples,attribute_list)/*,决策树生成算法*,/,输入：训练样本,samples,，由离散值属性表示；输出：一棵决策树。,（,1,）创建结点,N,；,（,2,）,IF,samples,都在同一个类,C,THEN,返回,N,作为叶结点，以类,C,标记；,（,3,）,IF,attribute_list,为空,THEN,返回,N,作为叶结点，标记为,samples,中最普通的类；,/,多数表决,（,4,）选择,attribute_list,中具有最高,信息增益,的属性,test_attribute,；,（,5,）标记结点,N,为,test_attribute,；,（,6,）,FOR,test_attribute,的每个取值,a,i,由结点,N,长出一个条件为,test_attribute=,a,i,的分枝；,（,7,）设,s,i,是,samples,中,test_attribute=,a,i,的样本的集合；,/,一个划分,（,8,）,IF,s,i,为空,THEN,回退到test_attribute的其它取值；,（,9,）,ELSE,加上一个由,Generate_decision_tree(,s,i,，,attribute_list-test_attribute),返回的结点；,2025/5/23 周五,22,决策树修剪算法,基本的决策树构造算法没有考虑噪声，因此生成的决策树完全与训练集拟合。在有噪声情况下，将导致过分拟合（,Overfitting,），即对训练数据的完全拟合反而使对现实数据的分类预测性能下降。,比如每个样本都是一个叶子节点。,现实世界的数据一般不可能是完美的，可能缺值（,Missing Values,）；数据不完整；含有噪声甚至是错误的,。,剪枝,是一种克服噪声的基本技术，同时它也能使树得到简化而变得更容易理解。有两种基本的剪枝策略。,2025/5/23 周五,23,决策树修剪算法,预先剪枝,（Pre-Pruning）：在生成树的同时决定是继续对不纯的训练子集进行划分还是停机。,后剪枝,（Post-Pruning）：是一种拟合+化简（fitting-and-simplifying）的两阶段方法。首先生成与训练数据完全拟合的一棵决策树，然后从树的叶子开始剪枝，逐步向根的方向剪。剪枝时要用到一个测试数据集合（Tuning Set或Adjusting Set），如果存在某个叶子剪去后能使得在测试集上的准确度或其他测度不降低（不变得更坏），则剪去该叶子；否则停机。理论上讲，后剪枝好于预先剪枝，但计算复杂度大。,2025/5/23 周五,24,决策树修剪算法,构造好的决策树的关键在于,如何选择属性,进行树的拓展。研究结果表明，一般情况下,树越小则树的预测能力越强。由于构造最小的树是NP-难问题，因此只能采取用启发式策略来进行。,属性选择依赖于各种对例子子集的,不纯度,（Impurity）度量方法，包括信息增益（Informatin Gain）、信息增益比（Gain Ratio）、Gini-index、距离度量（Distance Measure）、J-measure等。,2025/5/23 周五,25,ID3,算法,ID3,是一个著名决策树生成方法：,决策树中每一个,非叶结点,对应着一个非类别,属性,(特征)，,树枝,代表这个,属性的值,。一个,叶结点,代表从树根到叶结点之间的路径对应的记录所属的,类别属性,值。,每一个非叶结点都将与属性中具有最大信息量的非类别属性相关联。,采用信息增益来选择能够最好地将样本分类的属性,。,对,ID3,算法采用如下方式讲解：,给出信息增益对应的计算公式；,通过一个例子来说明它的主要过程。,2025/5/23 周五,26,信息增益的计算,设,S,是,s,个数据样本的集合，定义,m,个不同类,C,i,（,i=1,，,2,，,，,m,），设,s,i,是,C,i,类中的样本的数量。对给定的样本,S,所期望的,信息值,由下式给出：,其中,p,i,是任意样本属于,C,i,的概率：,s,i,/s,。,例题：数据集有4个类，分别有8个，4个，2个，2个样本，求该数据集的信息值。,问题：信息值的取值范围是什么？,2025/5/23 周五,27,信息增益的计算,例题：数据集有2个类，求该数据集的信息值。,2025/5/23 周五,28,信息增益的计算,设属性A具有个不同值a,1,a,2,a,v,，可以用属性A将样本S划分为 S,1,S,2,S,v,，设,S,ij,是Sj中Ci类的样本数，则由A划分成子集的熵由下式给出：,有A进行分枝将获得的信息增益可以由下面的公式得到：,使用属性,后的信息值,未使用属性,的信息值,2025/5/23 周五,29,信息增益的计算,例题：数据集有2个类。,使用,是否学生,作为属性，求该属性的信息增益。,使用,信用状况,作为属性，求该属性的信息增益。,2025/5/23 周五,30,ID3算法的例子,选择信息增益最大的属性特征作为根节点。,Gain(年龄)=0.342 Gain(收入)=0,Gain(是否学生)=0.333 Gain(信用状况)=0,年龄,？,？,？,是,40,2025/5/23 周五,31,ID3算法的例子,对于,=,30的分支,Gain(收入)=0.315 Gain(是否学生)=0.315 Gain(信用状况)=0.815,对于30,40的分支,Gain(收入)=1 Gain(是否学生)=0 Gain(信用状况)=1,年龄？,信用状况？,收入？,是,40,否,是,是,否,良好,一般,高,低,2025/5/23 周五,32,ID3,算法的性能分析,ID3,算法的假设空间包含所有的决策树，它是关于现有属性的有限离散值函数的一个完整空间。,ID3,算法在搜索的每一步都使用当前的所有训练样例，大大降低了对个别训练样例错误的敏感性。因此，通过修改终止准则，可以容易地扩展到处理含有噪声的训练数据。,2025/5/23 周五,33,ID3,算法的性能分析,ID3算法在搜索过程中不进行回溯。所以，它易受无回溯的爬山搜索中的常见风险影响：,收敛到局部最优而不是全局最优,。,ID3算法只能处理,离散值的属性,。,信息增益度量存在一个内在偏置，它,偏袒具有较多值的属性,。例如，如果有一个属性为日期，那么将有大量取值，这个属性可能会有非常高的信息增益。假如它被选作树的根结点的决策属性则可能形成一颗非常宽的树，这棵树可以理想地分类训练数据，但是对于测试数据的分类性能可能会相当差。,ID3算法增长树的每一个分支的深度，直到,属性的使用无法导致信息增益,。当数据中有噪声或训练样例的数量太少时，产生的树会过渡拟合训练样例。,问题,：ID3树可以导致过度拟合，那是否它一定能对训练集完全正确的分类呢？,2025/5/23 周五,34,C4.5,算法对,ID3,的主要改进,C4.5,算法是从,ID3,算法演变而来，除了拥有,ID3,算法的功能外，,C4.5,算法引入了新的方法和增加了新的功能：,用信息增益,比例,的概念；,合并具有,连续属性,的值；,可以处理具有缺少属性值的训练样本；,通过使用不同的修剪技术以避免树的过度拟合；,K,交叉验证；,规则的产生方式等。,2025/5/23 周五,35,信息增益比例的概念,信息增益比例,是在信息增益概念基础上发展起来的，一个属性的信息增益比例用下面的公式给出：,其中,假如我们以属性,A,的值为基准对样本进行分割的化，,Splitl(A),就是前面熵的概念。,2025/5/23 周五,36,信息增益比例的计算,例题：数据集有2个类。,使用,是否学生,作为属性，求该属性的信息增益比例。,使用,年龄,作为属性，求该属性的信息增益比例。,讨论：信息增益和信息增益比例的差异在哪里？,2025/5/23 周五,37,C4.5,处理连续值的属性,对于连续属性值，,C4.5,其处理过程如下：,根据属性的值，对数据集排序；,用不同的阈值将数据集动态的进行划分；,取两个实际值中的中点作为一个阈值；,取两个划分，所有样本都在这两个划分中；,得到所有可能的阈值、增益及增益比；,在每一个属性会变为取两个取值，即小于阈值或大于等于阈值。,简单地说，针对属性有连续数值的情况，则在训练集中可以按升序方式排列。如果属性,A,共有,n,种取值，则对每个取值,v,j,（,j=1,，,2,，,n,），将所有的记录进行划分：一部分小于,v,j,；另一部分则大于或等于,v,j,。针对每个,v,j,计算划分对应的增益比率，选择增益最大的划分来对属性,A,进行离散化。,2025/5/23 周五,38,C4.5处理连续值的属性,例题：使用C4.5算法将连续的属性(收入)转化为离散的类。,根据属性的值，对数据集排序；,取两个实际值中的中点作为一个阈值；,取两个划分，所有样本都在这两个划分中；,得到所有可能的阈值、增益及增益比；,在每一个属性会变为取两个取值，即小于阈值或大于等于阈值。,2025/5/23 周五,39,C4.5处理连续值的属性,例题：使用C4.5算法将连续的属性(收入)转化为离散的类。,选择增益最大的划分来对属性A进行离散化。,GainRatio(划分：2750)=0.2,GainRatio(划分：3100)=0.39,GainRatio(划分：3625)=0.53,GainRatio(划分：4458)=1,GainRatio(划分：？)=0.53,GainRatio(划分：8285)=0.39,GainRatio(划分：10900)=0.2,收入小于4458合并为收入低,收入大于等于4458合并为收入高,2025/5/23 周五,40,C4.5,的其他处理,C4.5,处理的样本中可以含有未知属性值，其处理方法是用最常用的值替代或者是将最常用的值分在同一类中。,具体采用概率的方法，依据属性已知的值，对属性和每一个值赋予一个概率，取得这些概率，取得这些概率依赖于该属性已知的值。,规则的产生：,一旦树被建立，就可以把树转换成,if-then,规则。,规则存储于一个二维数组中，每一行代表树中的一个规则，即从根到叶之间的一个路径。表中的每列存放着树中的结点。,2025/5/23 周五,41,C4.5,算法例子,样本数据,天气,温度,湿度,风,网球,SunnyHot85falseNo,SunnyHot90trueNo,OvercastHot78falseYes,RainMild96falseYes,RainCool80falseYes,RainCool70trueNo,OvercastCool65trueYes,SunnyMild95falseNo,SunnyCool70falseYes,RainMild80falseYes,SunnyMild70trueYes,OvercastMild90trueYes,OvercastHot75falseYes,RainMild80trueNo,（,1,）首先对,湿度,进行属性离散化，针对上面的训练集合，通过检测每个划分而确定最好的划分在,75,处，则这个属性的范围就变为,（,75,）,。,（,2,）计算目标属性,打网球,分类的期望信息：,（,3,）计算每个属性的,GainRatio,：,2025/5/23 周五,42,C4.5,算法例子,（4）选取最大的GainRatio，根据,天气,的取值，得到三个分枝。,（5）再扩展各分枝节点，得到最终的决策树（见课本图4-7）。,问题：就天气=Sunny这一分支，请用C4.5算法构造决策树。,样本数据,天气,温度,湿度,风,网球,SunnyHot85falseNo,SunnyHot90trueNo,SunnyMild95falseNo,SunnyCool70falseYes,SunnyMild70trueYes,2025/5/23 周五,43,第三章 分类方法,内容提要,分类的基本概念与步骤,基于距离的分类算法,决策树分类方法,贝叶斯分类,实值预测,与分类有关的问题,2025/5/23 周五,44,贝叶斯分类,定义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为黄色的确信程度。,2025/5/23 周五,45,朴素贝叶斯分类的工作原理,观测到的样本具有属性,收入低 是学生 信用良好,现在的问题相当于比较两个条件概率的大小,P(买电脑|收入低,是学生,信用良好),P(不买电脑|收入低,是学生,信用良好),2025/5/23 周五,46,朴素贝叶斯分类,朴素贝叶斯分类的工作过程如下：,(1)每个数据样本用一个,n,维特征向量,X,=,x,1,，,x,2,，,x,n,表示，分别描述对,n,个属性,A,1,，,A,2,，,A,n,样本的,n,个度量。,(2)假定有,m,个类,C,1,，,C,2,，,C,m,，,给定一个未知的数据样本,X,（,即没有类标号），分类器将预测,X,属于具有最高条件概率（条件,X,下）的类。,也就是说，朴素贝叶斯分类将未知的样本分配给类Ci（1im）当且仅当P(Ci|X)P(Cj|X)，对任意的j=1，2，m，ji。,2025/5/23 周五,47,朴素贝叶斯分类,(,续,),根据贝叶斯定理：,由于,P,(,X,),对于所有类为,常数,，只需要,P,(,X,|,C,i,)*,P,(,C,i,),最大即可。,注意，类的先验概率可以用P(C,i,)=S,i,/S计算，其中S,i,是类C,i,中的训练样本数，而S是训练样本总数。,因此问题就转换为计算,P,(,X,|,C,i,),。,2025/5/23 周五,48,朴素贝叶斯分类,(,续,),给定具有许多属性的数据集，计算,P,(,X,|,C,i,),的计算量可能非常大且不易计算。为降低计算,P,(,X,|,C,i,),的难度，可以做,类条件独立的朴素假定,。给定样本的类标号，假定,属性值相互条件独立,，即在属性间，不存在依赖关系。这样,P(收入低,是学生,信用良好|买电脑)=,P(收入低|买电脑)*P(是学生|买电脑)*P(信用良好|买电脑),2025/5/23 周五,49,朴素贝叶斯分类,(,续,),其中概率,P,(,x,1,|,C,i,)，,P,(,x,2,|,C,i,)，,P,(,x,n,|,C,i,),可以由训练样本估值。,如果,A,k,是离散属性，则,P,(,x,k,|,C,i,)=,s,ik,|,s,i,，,其中,s,ik,是在属性,A,k,上具有值,x,k,的类,C,i,的训练样本数，而,s,i,是,C,i,中的训练样本数。,如果,A,k,是连续值属性，则通常假定该属性服从高斯分布。因而，,是高斯分布函数，而分别为平均值和标准差。,2025/5/23 周五,50,朴素贝叶斯分类(续),例题：计算,P(收入低|不买电脑),P(是学生|不买电脑),P(信用良好|不买电脑),假设 收入，是否学生，信用状况互相独立，计算,P(收入低，是学生，信用良好|不买电脑),2025/5/23 周五,51,朴素贝叶斯分类,(,续,),对未知样本,X,分类，也就是对每个类,C,i,，,计算,P(,X,|,C,i,)*P(,C,i,)。,样本,X,被指派到类,C,i,，,当且仅当,P(,C,i,|,X,)P(,C,j,|,X,)，1,j,m,，,j,i,，,换言之，,X,被指派到其,P(,X,|,C,i,)*P(,C,i,),最大的类。,2025/5/23 周五,52,朴素贝叶斯分类举例,数据样本,有,属性,年龄,，,收入,，,是否学生,和,信用状况,。类标号属性,”,是否买电脑,“,有两个不同值,是,，,否,。设,C,1,对应于类,”,买电脑,”,；,则,C,2,对应于类,”不买电脑”,。,我们希望分类的未知样本为:,X=（,”年龄,=30”，,”收入=中,”，,”是学生,”，,”信用一般”,）,2025/5/23 周五,53,朴素贝叶斯分类举例,我们需要最大化P(X|C,i,)*P(C,i,)，i=1，2。,每个类的先验概率,P(C,i,),可以根据训练样本计算,：,P(C,1,)=P(买电脑）=,P(C,2,)=P(不买电脑）=,计算,P(X|Ci),P（年龄=30,收入=中,是学生,信用一般|买电脑),P（年龄=30,收入=中,是学生,信用一般|不买电脑),2025/5/23 周五,54,朴素贝叶斯分类举例,P（年龄=30,收入=中,是学生,信用一般|买电脑)=,P（年龄=30|买电脑)*,P（收入=中|买电脑)*,P（是学生|买电脑)*,P（信用一般|买电脑),P（年龄=30,收入=中,是学生,信用一般|,不,买电脑)=,P（年龄=30|不买电脑)*,P（收入=中|不买电脑)*,P（是学生|不买电脑)*,P（信用一般|不买电脑),2025/5/23 周五,55,朴素贝叶斯分类举例,假设属性之间独立,P（年龄=30,收入=中,是学生,信用一般|买电脑)=0.222*0.444*0.667*0.667=0.044；,P（年龄P（X|不买电脑)，因此对于样本X，朴素贝叶斯分类预测为,是,。,2025/5/23 周五,56,第三章 分类方法,内容提要,分类的基本概念与步骤,基于距离的分类算法,决策树分类方法,贝叶斯分类,基于规则的分类,与分类有关的问题,2025/5/23 周五,57,使用IF-THEN规则分类,使用规则的分类法是使用一组IF-THEN规则进行分类。,IF,条件,THEN,结论,比如,IF,(年龄20,AND,学生=是),THEN,买电脑=是,IF的部分称为前提，THEN的部分称为规则的结论,规则可以用它的,覆盖率,和,准确率,来评价,n,covers,是条件(前提)覆盖的样本数，n,correct,是规则正确分类的样本数。,2025/5/23 周五,58,使用IF-THEN规则分类,规则(收入=低),(信用状况良好),(是否买电脑=是)的覆盖率为3/8,而它测准确率为1/3。,规则(信用状况=良好)(是否买电脑=否)的覆盖率为7/8,而它测准确率为4/7。,2025/5/23 周五,59,使用IF-THEN规则分类,如果一个规则R被一个样本X满足，则称规则R被X触发。,比如X=(年龄=18，是学生，信用良好),R为,IF,(年龄20,AND,学生=是),THEN,买电脑=是,则X的类别为,买电脑,如果一个样本X同时触发了多个规则，我们需要制定解决冲突的策略。,规模序,激活具有最多属性测试的触发规则,规则序,将规则按重要性进行排序，按顺序进行促发,如果一个样本X无法促发任何规则,建立一个缺省或者默认规则,2025/5/23 周五,60,使用决策树来提取规则,决策树的规则是互斥与穷举的,互斥,意味着规则不会存在冲突，因此每个样本只能促发一个规则,穷举,意味着一个样本总能促发一个规则,由于每个树叶对应一个一条规则，提取的规则并不比决策树简单。,年龄？,信用状况？,收入？,是,40,否,是,是,否,良好,一般,高,低,2025/5/23 周五,61,使用顺序覆盖算法的规则归纳,在提取规则时，一个现实的问题是是否需要对现有规则进行拓展，,IF(年龄20)THEN买电脑,是否需要拓展为,IF(年龄,。,AQR,允许测试做,=,，,，,，,。,Selectors,的合取被称为复合（,Complex,），,Complexes,之间的析取被称为覆盖（,Cover,）。如果一个表达式对某个样本为真，则我们称其为对这个样本的一个覆盖。这样，一个空,Complex,覆盖所有的样本，而一个空,Cover,不覆盖任何样本。,在,AQR,中，一个新样本被区分是看其属于哪个推导出来的规则。如果该样本只满足一条规则，则这个样本就属于这条规则；如果该样本满足多条规则，则被这些规则所预测的最频繁的分类被赋予这条规则；如果该样本不属于任何规则，则其分类为样本集中最频繁的分类。,2025/5/23 周五,84,AQR,算法描述,算法,4-5 AQR,输入：正例样本,POS,；,反例样本,NEG,。,输出：覆盖,COVER,。,（,1,）,COVER=,；,/,初始化,COVER,为空集,（,2,）,WHILE COVER does not cover all positive examples in POS DO BEGIN,（,3,）,Select a SEED,；,/,选取一个种子,SEED,，例如没有被,COVER,覆盖的一个正样例,（,4,）,Call procedure STAR,（,SEED,，,NEG,）；,/,产生一个能覆盖种子而同时排除所有反例的星,（,5,）,Select the best Complex BEST from the STAR according to user-defined criteria,；,/*,从星中选取一个最好的复合*,/,（,6,）,Add BEST as an extra disjuct to COVER/*,把最好的复合与,COVER,合取，形成新的,COVER*/,（,7,）,END,（,8,）,RETURN COVER.,在算法,AQR,中调用了过程,STAR,，来排除所有的反例，产生覆盖种子的星。,2025/5/23 周五,85,AQR,算法描述,(,续,),算法,4-6,STAR,输入：种子,SEED,；反例,NEG,。,输出：星,STAR,。,（,1,）初始化,STAR,为空,Complex,（,2,）,WHILE one or more Complexes in STAR covers some negative examples in NEG BEGIN /*,如果,STAR,中的一个或多个,Complex,覆盖,NEG,中的负样例*,/,（,3,）,Select a negative example Eneg covered by a Complex in STAR,；,/*,选取一个被,STAR,中的,Complex,覆盖的负样例*,/,（,4,）,Let EXTENSION be all Selectors that cover SEED but not ENEG,；,/*,令,EXTENSION,为那些覆盖,SEED,但不覆盖,ENEG,的,Selectors,；*,/,（,5,）,Let STAR be the set xy|xSTAR,，,yEXTENSION,；,/*,令,STAR=xy|xSTAR,，,yEXTENSION,；*,/,（,6,）,Remove all Complexes in STAR subsumed by other Complexes in STAR,；,/*,从,STAR,中除去被其他,Complexes,所包含的,Complexes,；*,/,（,7,）,Remove the worst Complexes from STAR UNTIL size of STAR is less than or equal to user-defined maximum,（,maxstar,）,/*,删除,STAR,中最坏的,Complex,直到,STAR,的大小等于或小于用户定义的最大数目,maxstar*/,（,8,）,END,（,9,）,RETURN STAR./*,返回一系列覆盖,SEED,但不覆盖,NEG,的规则*,/,2025/5/23 周五,86,AQR,算法举例,假设现有一个训练集，其包含两种属性：,size,（属性值：,micro,，,tiny,，,mid,，,big,，,huge,，,vast,）,type,（属性值：,bicycle,，,motorcycle,，,car,，,prop,，,jet,，,glider,）,现有正例、反例样本分别如表,4-6,，表,4-7,所示：,下面给出用,AQR,算法对,giant 2-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=xy|xSTAR,，,yEXTENSION,，因此，,STAR=size=huge,type=bicycle,。,c),在这里定义,maxstar,为,2,，可不对,STAR,进行精简。,d),接着选取另一个被,STAR,中的复合覆盖的负样例,ENEG,，显然已经没有这样的负样例，因此，,STAR=size=huge,type=bicycle,。,从,STAR,（,SEED,，,NEG,）返回。,反例样本,size typ