数据挖掘--分类课件ppt

20:071第三章分类方法内容提要分类的基本概念与步骤基于距离的分类算法决策树分类方法贝叶斯分类实值预测与分类有关的问题20:072分类的流程根据现有的知识，我们得到了一些关于爬行动物和鸟类的信息，我们能否对新发现的物种，比如动物A，动物B进行分类？动物种类体型翅膀数量脚的只数是否产蛋是否有毛类别狗中04否是爬行动物猪大04否是爬行动物牛大04否是爬行动物麻雀小22是是鸟类天鹅中22是是鸟类大雁中22是是鸟类动物A大02是无？动物B中22否是？20:073分类的流程步骤一：将样本转化为等维的数据特征（特征提取）。所有样本必须具有相同数量的特征兼顾特征的全面性和独立性动物种类体型翅膀数量脚的只数是否产蛋是否有毛类别狗中04否是爬行动物猪大04否是爬行动物牛大04否是爬行动物麻雀小22是是鸟类天鹅中22是是鸟类大雁中22是是鸟类20:074分类的流程步骤二：选择与类别相关的特征（特征选择）。比如，绿色代表与类别非常相关，黑色代表部分相关，灰色代表完全无关动物种类体型翅膀数量脚的只数是否产蛋是否有毛类别狗中04否是爬行动物猪大04否是爬行动物牛大04否是爬行动物麻雀小22是是鸟类天鹅中22是是鸟类大雁中22是是鸟类20:075分类的流程步骤三：建立分类模型或分类器（分类）。分类器通常可以看作一个函数，它把特征映射到类的空间上iiniiiyxxxxf),......,,,(32120:076如何避免过度训练分类也称为有监督学习(supervisedlearning),与之相对于的是无监督学习(unsupervisedlearning),比如聚类。分类与聚类的最大区别在于，分类数据中的一部分的类别是已知的，而聚类数据的类别未知。建立分类模型需要学习一部分已知数据，如果训练时间过长，或者预测模型参数太多而样本较少，将导致过度训练(overfitting)。20:077如何避免过度训练避免过度训练最重要一点是，模型的参数量应远小于样本的数量。应建立训练集(trainingset)和测试集(testset)。训练集应用于建立分类模型测试集应用于评估分类模型K折叠交叉验证(K-foldcrossvalidation)：将初始采样分割成K个子样本(S1，S2,...,Sk)，取K-1个做训练集，另外一个做测试集。交叉验证重复K次，每个子样本都作为测试集一次，平均K次的结果，最终得到一个单一估测。20:078分类模型的评估真阳性(TruePositive)：实际为阳性预测为阳性真阴性(TrueNegative)：实际为阴性预测为阴性假阳性(FalsePositive)：实际为阴性预测为阳性假阴性(FalseNegative)：实际为阳性预测为阴性预测是否正确预测结果比如预测未知动物是鸟类还是爬行动物，阳性代表爬行动物，阴性代表非爬行动物，请大家阐述TP=10，TN=8，FN=3，FP=2是什么意义20:079分类模型的评估灵敏度(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/2320:0710分类模型的评估对于非平衡(unblanced)的数据集,以上指标并不能很好的评估预测结果。非平衡的数据集是指阳性数据在整个数据集中的比例很小。比如，数据集包含10只爬行动物，990只爬行动物，此时，是否预测正确爬行动物对准确率影响不大。更平衡的评估标准包括马修斯相关性系数(Matthewscorrelationcoefficient)和ROC曲线。马修斯相关性系数定义为20:0711分类模型的评估ROC曲线通过描述真阳性率(TPR)和假阳性率(FPR)来实现，其中TPR=TP/(TP+FN),FPR=FP/(FP+TN)。大部分分类器都输出一个实数值(可以看作概率),通过变换阈值可以得到多组TPR与FPR的值。20:0712第三章分类方法内容提要分类的基本概念与步骤基于距离的分类算法决策树分类方法贝叶斯分类实值预测与分类有关的问题20:0713基于距离的分类算法的思路定义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)被称为相似性。在实际的计算中往往用距离来表征，距离越近，相似性越大，距离越远，相似性越小。距离的计算方法有多种，最常用的是通过计算每个类的中心来完成。20:0714基于距离的分类算法的一般性描述算法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.20:0715基于距离的分类方法的直观解释（a）类定义（b）待分类样例（c）分类结果20:0716距离分类例题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)20:0717K-近邻分类算法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)THENBEGIN（7）N=N-{u}；（8）N=N∪{d}；（9）END（10）END（11）c=classtowhichthemostu∈N.20:0718KNN的例子姓名性别身高(米)类别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,女应属于哪个类别？20:0719第三章分类方法内容提要分类的基本概念与步骤基于距离的分类算法决策树分类方法贝叶斯分类实值预测与分类有关的问题20:0720决策树表示与例子年龄收入是否学生信用状况是否买电脑=30高否一般否30—40高否一般是40中否一般是40低是一般是40低是良好否30—40低是良好是=30中否一般否=30低是一般是年龄？学生？是信用？=3030—4040否是良好一般是否是否20:0721决策树表示与例子决策树（DecisionTree）的每个内部结点表示一个属性（特征），每个分枝代表一个特征的一个（类）取值；每个树叶结点代表类或类分布。决策树分类方法采用自顶向下的递归方式，在决策树的内部结点进行属性的比较，从而判断从该结点向下的分枝，在决策树的叶结点得到结论。从决策树的根到叶结点的一条路径就对应着一条规则，整棵决策树就对应着一组规则。决策树分类模型的建立通常分为两个步骤：决策树生成决策树修剪20:0722决策树生成算法描述算法4-3Generate_decision_tree(samples,attribute_list)/*决策树生成算法*/输入：训练样本samples，由离散值属性表示；输出：一棵决策树。（1）创建结点N；（2）IFsamples都在同一个类CTHEN返回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）IFsi为空THEN回退到test_attribute的其它取值；（9）ELSE加上一个由Generate_decision_tree(si，attribute_list-test_attribute)返回的结点；20:0723决策树修剪算法基本的决策树构造算法没有考虑噪声，因此生成的决策树完全与训练集拟合。在有噪声情况下，将导致过分拟合（Overfitting），即对训练数据的完全拟合反而使对现实数据的分类预测性能下降。比如每个样本都是一个叶子节点。现实世界的数据一般不可能是完美的，可能缺值（MissingValues）；数据不完整；含有噪声甚至是错误的。剪枝是一种克服噪声的基本技术，同时它也能使树得到简化而变得更容易理解。有两种基本的剪枝策略。20:0724决策树修剪算法预先剪枝（Pre-Pruning）：在生成树的同时决定是继续对不纯的训练子集进行划分还是停机。后剪枝（Post-Pruning）：是一种拟合+化简（fitting-and-simplifying）的两阶段方法。首先生成与训练数据完全拟合的一棵决策树，然后从树的叶子开始剪枝，逐步向根的方向剪。剪枝时要用到一个测试数据集合（TuningSet或AdjustingSet），如果存在某个叶子剪去后能使得在测试集上的准确度或其他测度不降低（不变得更坏），则剪去该叶子；否则停机。理论上讲，后剪枝好于预先剪枝，但计算复杂度大。20:0725决策树修剪算法构造好的决策树的关键在于如何选择属性进行树的拓展。研究结果表明，一般情况下,树越小则树的预测能力越强。由于构造最小的树是NP-难问题，因此只能采取用启发式策略来进行。属性选择依赖于各种对例子子集的不纯度（Impurity）度量方法，包括信息增益（InformatinGain）、信息增益比（GainRatio）、Gini-index、距离度量（DistanceMeasure）、J-measure等。20:0726ID3算法ID3是一个著名决策树生成方法：决策树中每一个非叶结点对应着一个非类别属性(特征)，树枝代表这个属性的值。一个叶结点代表从树根到叶结点之间的路径对应的记录所属的类别属性值。每一个非叶结点都将与属性中具有最大信息量的非类别属性相关联。采用信息增益来选择能够最好地将样本分类的属性。对ID3算法采用如下方式讲解：给出信息增益对应的计算公式；通过一个例子来说明它的主要过程。20: