数据挖掘--分类ppt课件

《数据挖掘--分类ppt课件》由会员分享，可在线阅读，更多相关《数据挖掘--分类ppt课件（106页珍藏版）》请在金锄头文库上搜索。

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

2、0/7/6,.,5,分类的流程,步骤三：建立分类模型或分类器（分类）。 分类器通常可以看作一个函数，它把特征映射到类的空间上,2020/7/6,.,6,如何避免过度训练,分类也称为有监督学习(supervised learning),与之相对于的是无监督学习(unsupervised learning),比如聚类。 分类与聚类的最大区别在于，分类数据中的一部分的类别是已知的，而聚类数据的类别未知。 建立分类模型需要学习一部分已知数据，如果训练时间过长，或者预测模型参数太多而样本较少，将导致过度训练(overfitting)。,2020/7/6,.,7,如何避免过度训练,避免过度训练最重要一点是

3、，模型的参数量应远小于样本的数量。 应建立训练集(training set)和测试集(test set)。 训练集应用于建立分类模型 测试集应用于评估分类模型 K折叠交叉验证(K-fold cross validation)：将初始采样分割成K个子样本(S1，S2,.,Sk)，取K-1个做训练集，另外一个做测试集。交叉验证重复K次，每个子样本都作为测试集一次，平均K次的结果，最终得到一个单一估测。,2020/7/6,.,8,分类模型的评估,真阳性(True Positive)： 实际为阳性 预测为阳性 真阴性(True Negative)：实际为阴性 预测为阴性 假阳性(False Posit

4、ive)： 实际为阴性 预测为阳性 假阴性(False Negative)：实际为阳性 预测为阴性 预测是否正确 预测结果 比如预测未知动物是鸟类还是爬行动物，阳性代表爬行动物，阴性代表非爬行动物，请大家阐述 TP=10，TN=8，FN=3，FP=2是什么意义,2020/7/6,.,9,分类模型的评估,灵敏度(Sensitivity)： TP/(TP+FN) 也称为查全率(Recall) 数据集共有13只爬行动物，其中10只被正确预测为爬行动物，灵敏度为10/13 特异度(Specificity): TN/(TN+FP) 数据集有10只非爬行动物，其中8只被预测为非爬行动物，特异度为8/10

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

6、correlation coefficient)和ROC曲线。 马修斯相关性系数定义为,2020/7/6,.,11,分类模型的评估,ROC曲线通过描述真阳性率(TPR)和假阳性率(FPR)来实现，其中TPR=TP/(TP+FN), FPR=FP/(FP+TN)。 大部分分类器都输出一个实数值(可以看作概率),通过变换阈值可以得到多组TPR与FPR的值。,2020/7/6,.,12,第三章 分类方法 内容提要,分类的基本概念与步骤 基于距离的分类算法 决策树分类方法 贝叶斯分类 实值预测 与分类有关的问题,2020/7/6,.,13,基于距离的分类算法的思路,定义4-2 给定一个数据库 D=t1

7、，t2，tn和一组类C=C1，Cm。假定每个元组包括一些数值型的属性值：ti=ti1，ti2，tik，每个类也包含数值性属性值：Cj=Cj1，Cj2，Cjk，则分类问题是要分配每个ti到满足如下条件的类Cj： sim(ti，Cj)=sim(ti，Cl) ，ClC，ClCj， 其中sim(ti，Cj)被称为相似性。 在实际的计算中往往用距离来表征，距离越近，相似性越大，距离越远，相似性越小。 距离的计算方法有多种，最常用的是通过计算每个类的中心来完成。,2020/7/6,.,14,基于距离的分类算法的一般性描述,算法 4-1通过对每个样本和各个类的中心来比较，从而可以找出他的最近的类中心，得到确

8、定的类别标记。,算法 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.,2020/7/6,.,15,基于距离的分类方法的直观解释,（a）类定义,（b）待分类样例,（c）分类结果,2020/7/6,.,16,距离分类例题,C1=(3,3,4,2), C2=(8,5,-1,-7), C3=(-5,-7,6,10); 请用基于距离的算法给以下样本分类

9、： (5,5,0,0) (5,5,-5,-5) (-5,-5,5,5),2020/7/6,.,17,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 su

10、ch 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.,2020/7/6,.,18,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

11、 男 1.82中等 Kim 女 1.7中等 Amy 女 1.75中等 Wynette 女 1.73中等,只使用身高做特征，K=3，对于样本应属于哪个类别？ 仅使用同性别样本做训练，K=3，对于样本应属于哪个类别？,2020/7/6,.,19,第三章 分类方法 内容提要,分类的基本概念与步骤 基于距离的分类算法 决策树分类方法 贝叶斯分类 实值预测 与分类有关的问题,2020/7/6,.,20,决策树表示与例子,年龄？,学生？,是,信用？,=30,3040,40,否,是,良好,一般,是,否,是,否,2020/7/6,.,21,决策树表示与例子,决策树（Decision Tree）的每个内部结点表

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

13、决策树。 （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的每个取值ai 由结点N长出一个条件为test_attribute=ai的分枝； （7）设si是samples 中test_attribute =ai的样本的集合

14、；/一个划分 （8）IF si 为空 THEN 回退到test_attribute的其它取值； （9）ELSE 加上一个由Generate_decision_tree(si， attribute_list-test_attribute)返回的结点；,2020/7/6,.,23,决策树修剪算法,基本的决策树构造算法没有考虑噪声，因此生成的决策树完全与训练集拟合。在有噪声情况下，将导致过分拟合（Overfitting），即对训练数据的完全拟合反而使对现实数据的分类预测性能下降。 比如每个样本都是一个叶子节点。 现实世界的数据一般不可能是完美的，可能缺值（Missing Values）；数据不完整；

15、含有噪声甚至是错误的。 剪枝是一种克服噪声的基本技术，同时它也能使树得到简化而变得更容易理解。有两种基本的剪枝策略。,2020/7/6,.,24,决策树修剪算法,预先剪枝（Pre-Pruning）：在生成树的同时决定是继续对不纯的训练子集进行划分还是停机。 后剪枝（Post-Pruning）：是一种拟合+化简（fitting-and-simplifying）的两阶段方法。首先生成与训练数据完全拟合的一棵决策树，然后从树的叶子开始剪枝，逐步向根的方向剪。剪枝时要用到一个测试数据集合（Tuning Set或Adjusting Set），如果存在某个叶子剪去后能使得在测试集上的准确度或其他测度不降低

16、（不变得更坏），则剪去该叶子；否则停机。理论上讲，后剪枝好于预先剪枝，但计算复杂度大。,2020/7/6,.,25,决策树修剪算法,构造好的决策树的关键在于如何选择属性进行树的拓展。研究结果表明，一般情况下,树越小则树的预测能力越强。由于构造最小的树是NP-难问题，因此只能采取用启发式策略来进行。 属性选择依赖于各种对例子子集的不纯度（Impurity）度量方法，包括信息增益（Informatin Gain）、信息增益比（Gain Ratio）、Gini-index、距离度量（Distance Measure）、J-measure等。,2020/7/6,.,26,ID3算法,ID3是一个著名决策树生成方法： 决策树中每一个非叶结点对应着一个非类别属性(特征)，树枝代表这个属性的值。一个叶结点代表从树根到叶结点之间的路径对应的记录所属的类别属性值。 每一个非叶结点都将与属性中具有最大信息量的非类别属性相关联。 采