《数据挖掘分类课件ppt》由会员分享，可在线阅读，更多相关《数据挖掘分类课件ppt（107页珍藏版）》请在金锄头文库上搜索。
1、第三章第三章 分类方法分类方法 内容提要内容提要n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n实值预测 n与分类有关的问题 2024/8/11数据挖掘-分类课件ppt分类的流程 n根据现有的知识，我们得到了一些关于爬行动物和鸟类的信息，我们能否对新发现的物种，比如动物A，动物B进行分类？动物种类动物种类体型体型翅膀数量翅膀数量脚的只数脚的只数是否产蛋是否产蛋是否有毛是否有毛类别类别狗中04否是爬行动物猪大04否是爬行动物牛大04否是爬行动物麻雀小22是是鸟类天鹅中22是是鸟类大雁中22是是鸟类动物A大02是无？动物B中22否是？2024/8/12数据挖掘-分类
2、课件ppt分类的流程 n步骤一：将样本转化为等维的数据特征（特征提取）。n所有样本必须具有相同数量的特征n兼顾特征的全面性和独立性动物种类动物种类体型体型翅膀数量翅膀数量脚的只数脚的只数是否产蛋是否产蛋是否有毛是否有毛类别类别狗中04否是爬行动物猪大04否是爬行动物牛大04否是爬行动物麻雀小22是是鸟类天鹅中22是是鸟类大雁中22是是鸟类2024/8/13数据挖掘-分类课件ppt分类的流程 n步骤二：选择与类别相关的特征（特征选择）。n比如，绿色代表与类别非常相关，黑色代表部分相关，灰色代表完全无关动物种类动物种类体型体型翅膀数量翅膀数量脚的只数脚的只数是否产蛋是否产蛋是否有毛是否有毛类别类别
3、狗中0 04 4否否是爬行动物猪大0 04 4否否是爬行动物牛大0 04 4否否是爬行动物麻雀小2 22 2是是是鸟类天鹅中2 22 2是是是鸟类大雁中2 22 2是是是鸟类2024/8/14数据挖掘-分类课件ppt分类的流程 n步骤三：建立分类模型或分类器（分类）。n分类器通常可以看作一个函数，它把特征映射到类的空间上2024/8/15数据挖掘-分类课件ppt如何避免过度训练 n分类也称为有监督学习(supervised learning),与之相对于的是无监督学习(unsupervised learning),比如聚类。n分类与聚类的最大区别在于，分类数据中的一部分的类别是已知的，而聚类数
4、据的类别未知。n建立分类模型需要学习一部分已知数据，如果训练时间过长，或者预测模型参数太多而样本较少，将导致过度训练(overfitting)。2024/8/16数据挖掘-分类课件ppt如何避免过度训练 n避免过度训练最重要一点是，模型的参数量应远小于样本的数量。n应建立训练集(training set)和测试集(test set)。n训练集应用于建立分类模型n测试集应用于评估分类模型nK折叠交叉验证(K-fold cross validation)：将初始采样分割成K个子样本(S1，S2,.,Sk)，取K-1个做训练集，另外一个做测试集。交叉验证重复K次，每个子样本都作为测试集一次，平均K次
5、的结果，最终得到一个单一估测。2024/8/17数据挖掘-分类课件ppt分类模型的评估 n真阳性(T True P Positive)： 实际为阳性 预测为阳性n真阴性(T True NNegative)：实际为阴性 预测为阴性n假阳性(F False P Positive)： 实际为阴性 预测为阳性n假阴性(F False NNegative)：实际为阳性 预测为阴性n预测是否正确 预测结果n比如预测未知动物是鸟类还是爬行动物，阳性代表爬行动物，阴性代表非非爬行动物，请大家阐述 TP=10，TN=8，FN=3，FP=2是什么意义2024/8/18数据挖掘-分类课件ppt分类模型的评估 n灵敏
6、度(Sensitivity)： TP/(TP+FN)n也称为查全率(Recall)n数据集共有13只爬行动物，其中10只被正确预测为爬行动物，灵敏度为10/13n特异度(Specificity): TN/(TN+FP)n数据集有10只非爬行动物，其中8只被预测为非爬行动物，特异度为8/10n精度(Precision): TP/(TP+FP)n分类器预测了12只动物为爬行动物，其中10只确实是爬行动物，精度为10/12n准确率(Accuracy): (TP+TN)/(TP+TN+FN+FP)n数据集包含23只动物，其中18只预测为正确的分类，准确率为18/232024/8/19数据挖掘-分类课件
7、ppt分类模型的评估 n对于非平衡(unblanced)的数据集,以上指标并不能很好的评估预测结果。n非平衡的数据集是指阳性数据在整个数据集中的比例很小。比如，数据集包含10只爬行动物，990只爬行动物，此时，是否预测正确爬行动物对准确率影响不大。n更平衡的评估标准包括马修斯相关性系数(Matthews correlation coefficient)和ROC曲线。n马修斯相关性系数定义为2024/8/110数据挖掘-分类课件ppt分类模型的评估 nROC曲线通过描述真阳性率(TPR)和假阳性率(FPR)来实现，其中TPR=TP/(TP+FN), FPR=FP/(FP+TN)。n大部分分类器都
8、输出一个实数值(可以看作概率),通过变换阈值可以得到多组TPR与FPR的值。2024/8/111数据挖掘-分类课件ppt第三章第三章 分类方法分类方法 内容提要内容提要n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n实值预测 n与分类有关的问题 2024/8/112数据挖掘-分类课件ppt基于距离的分类算法的思路n定义定义4-2 4-2 给定一个数据库给定一个数据库 D D=t t1 1，t t2 2，t tn n 和一和一组类组类C C=C C1 1，C Cmm 。假定每个元组包括一些数。假定每个元组包括一些数值型的属性值：值型的属性值：t ti i=t ti
9、1 i1，t ti2i2，t tik ik ，每个类也包，每个类也包含数值性属性值：含数值性属性值：C Cj j=C Cj1 j1，C Cj2j2，C Cjk jk ，则分，则分类问题是要分配每个类问题是要分配每个t ti i到满足如下条件的类到满足如下条件的类C Cj 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在实际的计算中往往用在实际的计算中往往用距离距离来表征，距离越近，来表征，距离越近
10、，相似性越大，距离越远，相似性越小。相似性越大，距离越远，相似性越小。n距离的计算方法有多种，最常用的是通过计算每距离的计算方法有多种，最常用的是通过计算每个类的中心来完成。个类的中心来完成。2024/8/113数据挖掘-分类课件ppt 基于距离的分类算法的一般性描述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 BEG
11、IN（4）c i； （5）distdist(ci，t)； （6） END.2024/8/114数据挖掘-分类课件ppt基于距离的分类方法的直观解释（a）类定义（b）待分类样例（c）分类结果2024/8/115数据挖掘-分类课件ppt距离分类例题 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)2024/8/116数据挖掘-分类课件pptK-近邻分类算法nK-近邻分类算法（K Nearest Neighbors，简称KNN）通过计算每个训练数据到待
12、分类元组的距离，取和待分类元组距离最近的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
13、=class to which the most u N. 2024/8/117数据挖掘-分类课件pptKNN的例子姓名 性别 身高(米) 类别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中等n只使用身高做特征，K=3，对于样本应属于哪个类别？n仅使用同性别样本做训
14、练，K=3，对于样本应属于哪个类别？2024/8/118数据挖掘-分类课件ppt第三章第三章 分类方法分类方法 内容提要内容提要n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n实值预测 n与分类有关的问题 2024/8/119数据挖掘-分类课件ppt决策树表示与例子年龄年龄收收入入是否是否学生学生信用信用状况状况是否买是否买电脑电脑40中否一般是是40低是一般是是40低是良好否否3040低是良好是是=30中否一般否否=30低是一般是是年龄年龄？学生学生？是是信用信用？40否是良好一般是是否否是是否否2024/8/120数据挖掘-分类课件ppt决策树表示与例子n决
15、策树（Decision Tree）的每个内部结点表示一个属性（特征），每个分枝代表一个特征的一个（类）取值；n每个树叶结点代表类或类分布。n决策树分类方法采用自顶向下的递归方式，在决策树的内部结点进行属性的比较，从而判断从该结点向下的分枝，在决策树的叶结点得到结论。n从决策树的根到叶结点的一条路径就对应着一条规则，整棵决策树就对应着一组规则。n决策树分类模型的建立通常分为两个步骤：n决策树生成n决策树修剪2024/8/121数据挖掘-分类课件ppt决策树生成算法描述算法 4-3 Generate_decision_tree(samples, attribute_list) /*决策树生成算法*
16、/输入：训练样本samples，由离散值属性表示；输出：一棵决策树。（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
17、）设si是samples 中test_attribute =ai的样本的集合；/一个划分（8）IFIF si 为空 THENTHEN 回退到test_attribute的其它取值；（9）ELSEELSE 加上一个由Generate_decision_tree(si， attribute_list-test_attribute)返回的结点；2024/8/122数据挖掘-分类课件ppt决策树修剪算法n基本的决策树构造算法没有考虑噪声，因此生成的决策树完全与训练集拟合。在有噪声情况下，将导致过分拟合（Overfitting），即对训练数据的完全拟合反而使对现实数据的分类预测性能下降。n比如每个样本都
18、是一个叶子节点。n现实世界的数据一般不可能是完美的，可能缺值（Missing Values）；数据不完整；含有噪声甚至是错误的。n剪枝是一种克服噪声的基本技术，同时它也能使树得到简化而变得更容易理解。有两种基本的剪枝策略。2024/8/123数据挖掘-分类课件ppt决策树修剪算法n预先剪枝（Pre-Pruning）：在生成树的同时决定是继续对不纯的训练子集进行划分还是停机。n后剪枝（Post-Pruning）：是一种拟合+化简（fitting-and-simplifying）的两阶段方法。首先生成与训练数据完全拟合的一棵决策树，然后从树的叶子开始剪枝，逐步向根的方向剪。剪枝时要用到一个测试数据
19、集合（Tuning Set或Adjusting Set），如果存在某个叶子剪去后能使得在测试集上的准确度或其他测度不降低（不变得更坏），则剪去该叶子；否则停机。理论上讲，后剪枝好于预先剪枝，但计算复杂度大。2024/8/124数据挖掘-分类课件ppt决策树修剪算法n构造好的决策树的关键在于如何选择属性进行树的拓展。研究结果表明，一般情况下,树越小则树的预测能力越强。由于构造最小的树是NP-难问题，因此只能采取用启发式策略来进行。n属性选择依赖于各种对例子子集的不纯度（Impurity）度量方法，包括信息增益（Informatin Gain）、信息增益比（Gain Ratio）、Gini-ind
20、ex、距离度量（Distance Measure）、J-measure等。2024/8/125数据挖掘-分类课件pptID3算法nID3是一个著名决策树生成方法：n决策树中每一个非叶结点对应着一个非类别属性(特征)，树枝代表这个属性的值。一个叶结点代表从树根到叶结点之间的路径对应的记录所属的类别属性值。n每一个非叶结点都将与属性中具有最大信息量的非类别属性相关联。n采用信息增益来选择能够最好地将样本分类的属性。n对ID3算法采用如下方式讲解：n给出信息增益对应的计算公式；n通过一个例子来说明它的主要过程。2024/8/126数据挖掘-分类课件ppt信息增益的计算n设S是s个数据样本的集合，定义
21、m个不同类Ci（i=1，2，m），设si是Ci类中的样本的数量。对给定的样本S所期望的信息值由下式给出：其中pi是任意样本属于Ci的概率： si / s 。 例题：数据集有4个类，分别有8个，4个，2个，2个样本，求该数据集的信息值。问题：信息值的取值范围是什么？2024/8/127数据挖掘-分类课件ppt信息增益的计算例题：数据集有2个类，求该数据集的信息值。年龄年龄收收入入是否是否学生学生信用信用状况状况是否买是否买电脑电脑40中是良好是是40低是良好是是=30低是良好否否3040低是良好否否=30中否良好否否=30低是良好是是2024/8/128数据挖掘-分类课件ppt信息增益的计算n设
22、属性A具有个不同值a1, a2, , av ，可以用属性A将样本S划分为 S1, S2, , Sv ，设Sij 是Sj中Ci类的样本数，则由A划分成子集的熵由下式给出：n有A进行分枝将获得的信息增益可以由下面的公式得到： 使用属性后的信息值未使用属性的信息值2024/8/129数据挖掘-分类课件ppt信息增益的计算例题：数据集有2个类。使用是否学生作为属性，求该属性的信息增益。使用信用状况作为属性，求该属性的信息增益。年龄年龄收收入入是否是否学生学生信用信用状况状况是否买是否买电脑电脑40中是良好是是40低是良好是是=30低是良好否否3040低是良好否否=30中否良好否否=30低是良好是是20
23、24/8/130数据挖掘-分类课件pptID3算法的例子n选择信息增益最大的属性特征作为根节点。nGain(年龄)=0.342 Gain(收入)=0nGain(是否学生)=0.333 Gain(信用状况)=0年龄年龄收收入入是否是否学生学生信用信用状况状况是否买是否买电脑电脑40中是一般是是40低是一般是是=30低是良好否否3040低是良好否否=30中否良好否否=30低是一般是是年龄年龄？是是402024/8/131数据挖掘-分类课件pptID3算法的例子n对于=30的分支nGain(收入)=0.315 Gain(是否学生)=0.315 Gain(信用状况)=0.815n对于30 40的分支n
24、Gain(收入)=1 Gain(是否学生)=0 Gain(信用状况)=1年龄年龄收收入入是否是否学生学生信用信用状况状况是否买是否买电脑电脑=30高否良好否否=30中否良好否否=30低是一般是是=30低是良好否否3040低是良好否否3040高是一般是年龄？年龄？信用状况？信用状况？收入？收入？是是40否否是是是是否否良好一般高低2024/8/132数据挖掘-分类课件pptID3算法的性能分析nID3算法的假设空间包含所有的决策树，它是关于现有属性的有限离散值函数的一个完整空间。nID3算法在搜索的每一步都使用当前的所有训练样例，大大降低了对个别训练样例错误的敏感性。因此，通过修改终止准则，可以
25、容易地扩展到处理含有噪声的训练数据。2024/8/133数据挖掘-分类课件pptID3算法的性能分析nID3算法在搜索过程中不进行回溯。所以，它易受无回溯的爬山搜索中的常见风险影响：收敛到局部最优而不是全局最优。nID3算法只能处理离散值的属性。n信息增益度量存在一个内在偏置，它偏袒具有较多值的属性。例如，如果有一个属性为日期，那么将有大量取值，这个属性可能会有非常高的信息增益。假如它被选作树的根结点的决策属性则可能形成一颗非常宽的树，这棵树可以理想地分类训练数据，但是对于测试数据的分类性能可能会相当差。nID3算法增长树的每一个分支的深度，直到属性的使用无法导致信息增益。当数据中有噪声或训练
26、样例的数量太少时，产生的树会过渡拟合训练样例。n问题：ID3树可以导致过度拟合，那是否它一定能对训练集完全正确的分类呢？2024/8/134数据挖掘-分类课件pptC4.5算法对ID3的主要改进nC4.5算法是从ID3算法演变而来，除了拥有ID3算法的功能外，C4.5算法引入了新的方法和增加了新的功能：n用信息增益比例的概念；n合并具有连续属性的值；n可以处理具有缺少属性值的训练样本；n通过使用不同的修剪技术以避免树的过度拟合；nK交叉验证；n规则的产生方式等。2024/8/135数据挖掘-分类课件ppt信息增益比例的概念n信息增益比例是在信息增益概念基础上发展起来的，一个属性的信息增益比例用
27、下面的公式给出：其中假如我们以属性A的值为基准对样本进行分割的化，Splitl(A)就是前面熵的概念。 2024/8/136数据挖掘-分类课件ppt信息增益比例的计算例题：数据集有2个类。使用是否学生作为属性，求该属性的信息增益比例。使用年龄作为属性，求该属性的信息增益比例。讨论：信息增益和信息增益比例的差异在哪里？年龄年龄收收入入是否是否学生学生信用信用状况状况是否买是否买电脑电脑80低是良好是是2024/8/137数据挖掘-分类课件pptC4.5处理连续值的属性n对于连续属性值，C4.5其处理过程如下：n根据属性的值，对数据集排序；n用不同的阈值将数据集动态的进行划分；n取两个实际值中的中
28、点作为一个阈值；n取两个划分，所有样本都在这两个划分中；n得到所有可能的阈值、增益及增益比；n在每一个属性会变为取两个取值，即小于阈值或大于等于阈值。n简单地说，针对属性有连续数值的情况，则在训练集中可以按升序方式排列。如果属性A共有n种取值，则对每个取值vj（j=1，2，n），将所有的记录进行划分：一部分小于vj；另一部分则大于或等于vj 。针对每个vj计算划分对应的增益比率，选择增益最大的划分来对属性A进行离散化 。 2024/8/138数据挖掘-分类课件pptC4.5处理连续值的属性例题：使用C4.5算法将连续的属性(收入)转化为离散的类。n根据属性的值，对数据集排序；n取两个实际值中的
29、中点作为一个阈值；n取两个划分，所有样本都在这两个划分中；n得到所有可能的阈值、增益及增益比；n在每一个属性会变为取两个取值，即小于阈值或大于等于阈值。收入收入是否买是否买电脑电脑2500否否3000否否3200否否4050否否4865是是6770是是9800是是12000是是2024/8/139数据挖掘-分类课件pptC4.5处理连续值的属性例题：使用C4.5算法将连续的属性(收入)转化为离散的类。n选择增益最大的划分来对属性A进行离散化 。nGainRatio(划分：2750)=0.2nGainRatio(划分：3100)=0.39nGainRatio(划分：3625)=0.53nGain
30、Ratio(划分：4458)=1nGainRatio(划分：？)=0.53nGainRatio(划分：8285)=0.39nGainRatio(划分：10900)=0.2n收入小于4458合并为收入低n收入大于等于4458合并为收入高收入收入是否买是否买电脑电脑收入（离收入（离散化）散化）2500否3000否3200否4050否4865是6770是9800是12000是2024/8/140数据挖掘-分类课件pptC4.5的其他处理 nC4.5处理的样本中可以含有未知属性值，其处理方法是用最常用的值替代或者是将最常用的值分在同一类中。n具体采用概率的方法，依据属性已知的值，对属性和每一个值赋予一
31、个概率，取得这些概率，取得这些概率依赖于该属性已知的值。n规则的产生：规则的产生：一旦树被建立，就可以把树转换成if-then规则。n规则存储于一个二维数组中，每一行代表树中的一个规则，即从根到叶之间的一个路径。表中的每列存放着树中的结点。 2024/8/141数据挖掘-分类课件pptC4.5算法例子样本数据天气温度湿度风网球SunnyHot85falseNoSunnyHot90trueNoOvercast Hot78falseYesRainMild96falseYesRainCool80falseYesRainCool70trueNoOvercast Cool65trueYesSunnyMi
32、ld95falseNoSunnyCool70falseYesRainMild80falseYesSunnyMild70trueYesOvercast Mild90trueYesOvercast Hot75falseYesRainMild80trueNo（1）首先对湿湿度度进行属性离散化，针对上面的训练集合，通过检测每个划分而确定最好的划分在75处，则这个属性的范围就变为（75）。（2）计算目标属性打打网网球球分类的期望信息： （3）计算每个属性的GainRatio：2024/8/142数据挖掘-分类课件pptC4.5算法例子（4）选取最大的GainRatio，根据天气天气的取值，得到三个分枝。
33、（5）再扩展各分枝节点，得到最终的决策树（见课本图4-7 ）。问题：就天气=Sunny这一分支，请用C4.5算法构造决策树。样本数据天气温度湿度风网球SunnyHot85falseNoSunnyHot90trueNoSunnyMild95falseNoSunnyCool70falseYesSunnyMild70trueYes2024/8/143数据挖掘-分类课件ppt第三章第三章 分类方法分类方法 内容提要内容提要n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n实值预测 n与分类有关的问题 2024/8/144数据挖掘-分类课件ppt贝叶斯分类n定定义义4-4-
34、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 P(X |H)|H)代代表表假假设设H H成成立立的的情情况况下下，观观察察到到X X的的概概率率。P(H| P(H| X )X )是是后验概率后验概率，或称为或称为
35、X X发生后观测到发生后观测到H H的的条件概率条件概率。n例例如如，假假定定数数据据样样本本由由一一些些人人组组成成，假假定定X X表表示示头头发发颜颜色色，H H表表示示肤肤色色，则则P(H|X)P(H|X)反反映映当当我我们们看看到到X X是是黑黑色色时时，我我们们对对H H为为黄黄色色的的确确信程度。信程度。2024/8/145数据挖掘-分类课件ppt朴素贝叶斯分类的工作原理n观测到的样本具有属性 收入低 是学生 信用良好n现在的问题相当于比较两个条件概率的大小P(买电脑|收入低,是学生, 信用良好)P(不买电脑|收入低,是学生, 信用良好)收收入入是否是否学生学生信用信用状况状况是否
36、买是否买电脑电脑高否良好否否高是良好是是中是良好是是低是良好是是低否良好否否低否良好否否中否良好否否低是良好？2024/8/146数据挖掘-分类课件ppt朴素贝叶斯分类朴素贝叶斯分类的工作过程如下：朴素贝叶斯分类的工作过程如下：n(1) 每个数据样本用一个n维特征向量X= x1，x2，xn表示，分别描述对n个属性A1，A2，An样本的n个度量。n(2) 假定有m个类C1，C2，Cm，给定一个未知的数据样本X（即没有类标号），分类器将预测X属于具有最高条件概率（条件X下）的类。n也就是说，朴素贝叶斯分类将未知 的 样 本 分 配 给 类Ci（ 1im） 当 且 仅 当P(Ci|X) P(Cj|X
37、)，对任意的j=1，2，m，ji。收收入入是否是否学生学生信用信用状况状况是否买是否买电脑电脑高否良好否否高是良好是是中是良好是是低是良好是是低否良好否否低否良好否否中否良好否否低低是是良好良好？2024/8/147数据挖掘-分类课件ppt朴素贝叶斯分类(续)根据贝叶斯定理：根据贝叶斯定理： n由由于于P 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
38、 Ci i中的训练样本数，而中的训练样本数，而S S是训练样本总数。是训练样本总数。n因此问题就转换为计算因此问题就转换为计算P P( (X X| |C Ci i) )。 2024/8/148数据挖掘-分类课件ppt朴素贝叶斯分类(续)n给给定定具具有有许许多多属属性性的的数数据据集集，计计算算P P( (X X| |C Ci i) )的的计计算算量量可可能能非非常常大大且且不不易易计计算算。为为降降低低计计算算P P( (X X| |C Ci i) )的的难难度度，可可以以做做类条件独立的朴素假定。给给定定样样本本的的类类标标号号，假假定定属属性性值值相相互互条条件件独独立立，即即在在属属性
39、性间，不存在依赖关系。这样间，不存在依赖关系。这样nP(P(收入低收入低, ,是学生是学生, , 信用良好信用良好| |买电脑买电脑)=)= P(P(收收入入低低| |买买电电脑脑)*P()*P(是是学学生生| |买买电电脑脑)*P()*P(信信用用良良好好| |买电脑买电脑) ) 2024/8/149数据挖掘-分类课件ppt朴素贝叶斯分类(续) 其其中中概概率率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是离散属性，则是离散属性
40、，则P P( (x xk k| |C Ci i)=)=s sikik| |s si i，其中其中s sikik是在属性是在属性A Ak k上具有值上具有值x xk k的类的类C Ci i的训练样本数，而的训练样本数，而s si i是是C Ci i中的训练样本数。中的训练样本数。 n如果如果A Ak k是连续值属性，则通常假定该属性服从高斯分布。因是连续值属性，则通常假定该属性服从高斯分布。因而，而， 是高斯分布函数，是高斯分布函数， 而分别为平均值和标准差。而分别为平均值和标准差。 2024/8/150数据挖掘-分类课件ppt朴素贝叶斯分类(续)n例题：计算P(收入低|不买电脑)P(是学生|不
41、买电脑)P(信用良好|不买电脑)n假设 收入，是否学生，信用状况互相独立，计算 P(收入低，是学生，信用良好|不买电脑)收收入入是否是否学生学生信用信用状况状况是否买是否买电脑电脑高否良好否否高是良好是是中是良好是是低是良好是是低否一般否否低否良好否否中否良好否否低是良好？2024/8/151数据挖掘-分类课件ppt朴素贝叶斯分类(续)n对对未未知知样样本本X X分分类类，也也就就是是对对每每个个类类C Ci i，计计算算P(P(X X| |C Ci i)*P)*P( (C Ci i) )。样样本本X X被被指指派派到到类类C Ci i，当当且且仅仅当当P(P(C Ci i| |X X) )
42、P(P(C Cj j| |X X) )，11j jmm，j ji i，换换言言之之，X X被被指指派派到到其其P(P(X X| |C Ci i)*P()*P(C Ci i) )最大的类。最大的类。 2024/8/152数据挖掘-分类课件ppt朴素贝叶斯分类举例n数据样本有属性年龄，收入，是否学生和信用状况。类标号属性”是否买电脑“有两个不同值是，否。设C1对应于类”买电脑”；则C2对应于类”不买电脑”。n我们希望分类的未知样本为:X=（”年龄=30”，”收入=中”，”是学生”，”信用一般”）年龄年龄收收入入是否是否学生学生信用信用状况状况是否买是否买电脑电脑=30高否一般否否40中否一般是是4
43、0低是一般是是40低是良好否否3140 低是良好是是=30中否一般否否40中是一般是是40中否良好否否=30=30中中是是一般一般 ？2024/8/153数据挖掘-分类课件ppt朴素贝叶斯分类举例n我们需要最大化P(X|Ci)*P(Ci)，i=1，2。n每个类的先验概率P(Ci)可以根据训练样本计算：P(C1)=P(买电脑）=P(C2)=P(不买电脑）=n计算P(X|Ci)P（年龄=30,收入=中,是学生,信用一般|买电脑)P（年龄=30,收入=中,是学生,信用一般|不买电脑)年龄年龄收收入入是否是否学生学生信用信用状况状况是否买是否买电脑电脑=30高否一般否否40中否一般是是40低是一般是是
44、40低是良好否否3140 低是良好是是=30中否一般否否40中是一般是是40中否良好否否=30=30中中是是一般一般 ？2024/8/154数据挖掘-分类课件ppt朴素贝叶斯分类举例nP（年龄=30,收入=中,是学生,信用一般|买电脑)=P（年龄=30|买电脑)*P（收入=中|买电脑)*P（是学生|买电脑)*P（信用一般|买电脑)nP（年龄=30,收入=中,是学生,信用一般|不买电脑)=P（年龄=30|不买电脑)*P（收入=中|不买电脑)*P（是学生|不买电脑)*P（信用一般|不买电脑)年龄年龄收收入入是否是否学生学生信用信用状况状况是否买是否买电脑电脑=30高否一般否否40中否一般是是40低
45、是一般是是40低是良好否否3140 低是良好是是=30中否一般否否40中是一般是是40中否良好否否=30=30中中是是一般一般 ？2024/8/155数据挖掘-分类课件ppt朴素贝叶斯分类举例n假设属性之间独立P（年龄=30,收入=中,是学生,信用一般|买电脑)=0.222*0.444*0.667 *0.667=0.044；P（年龄P（X|不买电脑)，因此对于样本X，朴素贝叶斯分类预测为是。年龄年龄收收入入是否是否学生学生信用信用状况状况是否买是否买电脑电脑=30高否一般否否40中否一般是是40低是一般是是40低是良好否否3140 低是良好是是=30中否一般否否40中是一般是是40中否良好否否
46、=30=30中中是是一般一般 ？2024/8/156数据挖掘-分类课件ppt第三章第三章 分类方法分类方法 内容提要内容提要n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n基于规则的分类 n与分类有关的问题 2024/8/157数据挖掘-分类课件ppt使用IF-THEN规则分类n使用规则的分类法是使用一组IF-THEN规则进行分类。nIF 条件 THEN 结论n比如 IF (年龄20 AND 学生=是) THEN买电脑=是nIF的部分称为前提，THEN的部分称为规则的结论n规则可以用它的覆盖率和准确率来评价nncovers是条件(前提)覆盖的样本数，ncorre
47、ct是规则正确分类的样本数。2024/8/158数据挖掘-分类课件ppt使用IF-THEN规则分类n规则(收入=低)(信用状况良好)(是否买电脑=是)的覆盖率为3/8,而它测准确率为1/3。n规则(信用状况=良好)(是否买电脑=否)的覆盖率为7/8,而它测准确率为4/7。收收入入是否是否学生学生信用信用状况状况是否买是否买电脑电脑高否良好否否高是良好是是中是良好是是低是良好是是低否一般否否低否良好否否中否良好否否低是良好否否2024/8/159数据挖掘-分类课件ppt使用IF-THEN规则分类n如果一个规则R被一个样本X满足，则称规则R被X触发。n比如X =(年龄=18，是学生，信用良好) R
48、为 IF(年龄20 AND 学生=是) THEN买电脑=是 则X的类别为 买电脑n如果一个样本X同时触发了多个规则，我们需要制定解决冲突的策略。n规模序 激活具有最多属性测试的触发规则n规则序 将规则按重要性进行排序，按顺序进行促发n如果一个样本X无法促发任何规则n建立一个缺省或者默认规则2024/8/160数据挖掘-分类课件ppt使用决策树来提取规则n决策树的规则是互斥与穷举的n互斥意味着规则不会存在冲突，因此每个样本只能促发一个规则n穷举意味着一个样本总能促发一个规则n由于每个树叶对应一个一条规则，提取的规则并不比决策树简单。年龄？年龄？信用状况？信用状况？收入？收入？是是40否否是是是是
49、否否良好一般高低2024/8/161数据挖掘-分类课件ppt使用顺序覆盖算法的规则归纳n在提取规则时，一个现实的问题是是否需要对现有规则进行拓展，n IF (年龄20) THEN买电脑 是否需要拓展为 IF (年龄20 AND 学生=是) THEN买电脑n衡量规则好坏应同时考虑覆盖度与准确率n 准确率太低 覆盖度太低2024/8/162数据挖掘-分类课件ppt使用顺序覆盖算法的规则归纳n有两种衡量规则好坏的度量 FOIL_Gain的定义如下n分别对应于两个规则R与R。正在学习的类称为正样本(pos)，而其他类称为负样本(neg), pos(neg)为规则R覆盖的正负样本，而pos(neg)为规
50、则R覆盖的正负样本。2024/8/163数据挖掘-分类课件pptn判断规则(收入=低)(是否买电脑=否)是否需要拓展为规则(收入=低)(信用状况=良好)(是否买电脑=否)收收入入是否是否学生学生信用状信用状况况是否买电是否买电脑脑高否良好否否高是良好是是中是良好是是低是一般是是低否良好否否低否良好否否中否良好是是低是良好否否2024/8/164数据挖掘-分类课件ppt使用顺序覆盖算法的规则归纳n似然率统计量的的定义如下n其中m是分类的类别数。fi为满足规则的样本中属于类i的概率，ei为属于类i的期望(基准)概率。n似然率越高，说明规则越理想。2024/8/165数据挖掘-分类课件pptn分别计
51、算规则(收入=低)(是否买电脑=否)与规则(收入=低)(信用状况=良好)(是否买电脑=否)的似然率。收收入入是否学是否学生生信用状信用状况况是否买电是否买电脑脑高否良好否否高是良好是是中是良好是是低是一般是是低否良好否否低否良好否否中否良好是是低是良好否否2024/8/166数据挖掘-分类课件ppt 顺序覆盖算法n终止条件包括，类c没有样本或者返回的规则质量低于用户指定的阈值等。输入：D，类标记已知的样本的集合。 Att_vals,所有属性与它们可能值得集合。输出：IF-THEN规则的集合。 （1）Rule_set=；/规则的初始集为空集（2）FOR 每个类 c DO （3） repeat （
52、4） Rule=Learn_One_Rule(D,Att_vals,c);（5） 从D中删除Rule覆盖的样本； （6） untile 终止条件满足； （7） Rule_set=Rule_set+Rule; /将新规则添加到规则集（8）END FOR（9）返回Rule_Set2024/8/167数据挖掘-分类课件ppt使用顺序覆盖算法的规则归纳nRule_set=；n选择一个类“买电脑”；n选择一个包含一个属性的规则n(收入=低)“买电脑”n分别计算其它包含一个属性的规则的相对于已选择规则的FOIL_Gainn(收入=高)“买电脑”n(学生=是)“买电脑”n(学生=否)“买电脑”n(信用=良好
53、)“买电脑”n(信用=一般)“买电脑”收收入入是否学是否学生生信用状信用状况况是否买电是否买电脑脑高否一般否否高是一般是是高是良好是是高否良好是是低否一般是是低是良好否否低是良好否否低否一般否否2024/8/168数据挖掘-分类课件ppt使用顺序覆盖算法的规则归纳分别计算规则的Foil_gainn(收入=高)买电脑为1.74n(学生=是)买电脑为0n(学生=否)买电脑为0n(信用=良好)买电脑为0n(信用=一般)买电脑为0n选择Foil_gain最高的规则n(收入=高)买电脑收收入入是否学是否学生生信用信用状况状况是否买是否买电脑电脑高否一般否否高是一般是是高是良好是是高否良好是是低否一般是是
54、低是良好否否低是良好否否低否一般否否2024/8/169数据挖掘-分类课件ppt使用顺序覆盖算法的规则归纳n对最好的规则R进行拓展n(收入=高)买电脑n在规则R中添加一个属性，得到拓展以后的规则Rn(收入=高)(学生=是)n(收入=高)(学生=否)n(收入=高)(信用=良好)n(收入=高)(信用=一般)分别计算这些规则的相对于R的Foil_gain收收入入是否是否学生学生信用信用状况状况是否买是否买电脑电脑高否一般否否高是一般是是高是良好是是高否良好是是低否一般是是低是良好否否低是良好否否低否一般否否2024/8/170数据挖掘-分类课件ppt使用顺序覆盖算法的规则归纳n分别计算规则的Foil
55、_gainn(收入=高)(学生=是) 为0.84n(收入=高)(学生=否) 为-1.16n(收入=高)(信用=良好) 为0.84n(收入=高)(信用=一般) 为-1.16n选择Foil_gain最高的规则n(收入=高)(学生=是) n(收入=高)(信用=良好)n由于这两个规则准确率已经是100%，因此不用拓展收收入入是否是否学生学生信用信用状况状况是否买是否买电脑电脑高否一般否否高是一般是是高是良好是是高否良好是是低否一般是是低是良好否否低是良好否否低否一般否否2024/8/171数据挖掘-分类课件ppt使用顺序覆盖算法的规则归纳n将规则覆盖的样本从数据集D中删除，对剩下的正样本生成规则收收入
56、入是否是否学生学生信用信用状况状况是否买是否买电脑电脑高否一般否否低否一般是是低是良好否否低是良好否否低否一般否否2024/8/172数据挖掘-分类课件ppt使用顺序覆盖算法的规则归纳收收入入是否是否学生学生信用信用状况状况是否买是否买电脑电脑高否一般否否低是良好否否低是良好否否低否一般否否n选择另外一个类“不买电脑” (生成其它类的规则)；n选择一个包含一个属性的规则n(收入=低)“不买电脑”n分别计算其它包含一个属性的规则的相对于已选择规则的FOIL_Gainn(收入=高)“不买电脑”n(学生=是)“不买电脑”n(学生=否)“不买电脑”n(信用=良好)“不买电脑”n(信用=一般)“不买电脑
57、”2024/8/173数据挖掘-分类课件ppt第三章第三章 分类方法分类方法 内容提要内容提要n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n基于规则的分类n实值预测 2024/8/174数据挖掘-分类课件ppt实值预测分类：把样本分配到若干类之一(离散的)。n比如预测是普通员工、中层管理还是高级管理人员预测：预测样本的某个属性值(连续的)。n比如预测收入工作年限工作年限周工作时周工作时间间月薪月薪14025004483000540350074040008484500640？948？2024/8/175数据挖掘-分类课件ppt实值预测n 实值预测方法有两种n线性
58、回归和多元回归n非线性回归2024/8/176数据挖掘-分类课件ppt实值预测n在回归分析中，只包括一个自变量和一个因变量，且二者的关系可用一条直线近似表示，这种回归分析称为一元线性回归分析。nx=2,4,5,7,9; y=6,10,12,16,20;n如果回归分析中包括两个或两个以上的自变量，且因变量和自变量之间是线性关系，则称为多元线性回归分析。nx=(2,4),(4,0),(5,6),(7,1),(9,-3); y=10,4,17,9,3;2024/8/177数据挖掘-分类课件ppt一元线性回归模型n给n个随机样本(Yi,Xi,)，则Y与X的线性回归模型可以写为n其中 b0 ，b1是参数
59、n 是被称为误误差差项的随机变量,这是由于我们建立的线性回归模型可能是不完美的 工作年工作年限限月薪月薪12500430005350074000845006？9？2024/8/178数据挖掘-分类课件ppt线性回归模型的求解n回归模型的求解相当于求解 使得n一元线性回归分析的求解2024/8/179数据挖掘-分类课件ppt一元线性回归模型n例题：请建立右表的线性回归模型。 工作年工作年限限月薪月薪12500430005350074000845006？9？2024/8/180数据挖掘-分类课件ppt多元线性回归模型n给n个随机样本(Yi,Xi1,Xi2,.,Xip)，则Y与X的线性回归模型可以写
60、为n其中 b0 ，b1，b2 ，bn是参数n 是被称为误误差差项的随机变量,这是由于我们建立的线性回归模型可能是不完美的 工作年工作年限限周工作周工作时间时间月薪月薪240350044832005406500104058001248720018404300640？948？2024/8/181数据挖掘-分类课件ppt线性回归模型的求解n回归模型的求解相当于求解 使得n多元线性回归分析的求解其中X为2024/8/182数据挖掘-分类课件ppt AQ算法n多元回归模型的求解在许多软件中都可以得到，比如Matlab，SAS，SPSS，Weka等。2024/8/183数据挖掘-分类课件pptAQR算法有
61、关定义nAQR为每一个分类推导出一条规则，每一条规则形式如下：if then predict 。n在一个属性上的基本测试被称为一个Selector。下面是一些Selector的例子：或60。nAQR允许测试做=，。Selectors的合取被称为复合（Complex），Complexes之间的析取被称为覆盖（Cover）。如果一个表达式对某个样本为真，则我们称其为对这个样本的一个覆盖。这样，一个空Complex覆盖所有的样本，而一个空Cover不覆盖任何样本。n在AQR中，一个新样本被区分是看其属于哪个推导出来的规则。如果该样本只满足一条规则，则这个样本就属于这条规则；如果该样本满足多条规则，则
62、被这些规则所预测的最频繁的分类被赋予这条规则；如果该样本不属于任何规则，则其分类为样本集中最频繁的分类。2024/8/184数据挖掘-分类课件ppt 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）； /
63、产生一个能覆盖种子而同时排除所有反例的星（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，来排除所有的反例，产生覆盖种子的星。2024/8/185数据挖掘-分类课件ppt AQR算法描述(续)算法算法 4-6 STAR输入：种子SE
64、ED；反例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 n
65、ot 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 th
66、an or equal to user-defined maximum （maxstar）/*删除STAR中最坏的Complex直到STAR的大小等于或小于用户定义的最大数目maxstar*/（8）END（9）RETURN STAR. /*返回一系列覆盖SEED但不覆盖NEG的规则*/2024/8/186数据挖掘-分类课件pptAQR算法举例假设现有一个训练集，其包含两种属性：size （属性值：micro，tiny，mid，big，huge，vast）type （属性值：bicycle，motorcycle，car，prop，jet，glider）现有正例、反例样本分别如表4-6，表4-7所
67、示： 下面给出用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 = motorc
68、ycle 。 b ) 使EXTENSION为所有覆盖SEED但不覆盖ENEG的选择，则EXTENSION包括size= huge和type =bicycle，则又根据STAR=xy|xSTAR，yEXTENSION，因此，STAR= size=hugetype =bicycle 。 c ) 在这里定义maxstar为2，可不对STAR进行精简。 d ) 接着选取另一个被STAR中的复合覆盖的负样例ENEG，显然已经没有这样的负样例，因此，STAR= size=hugetype =bicycle 。从STAR（SEED，NEG）返回。反例样本size type classTiny motorcy
69、cle conventional transportation tiny car conventional transportation mid car conventional transportation micro jetfast planeTiny jetfast planeMid jetfast plane正例样本size type classHuge bicycle giant 2-wheelerHuge motorcycle giant 2-wheeler2024/8/187数据挖掘-分类课件pptAQR算法举例（5）BEST= size=hugetype =bicycle ，C
70、OVER = size=hugetype =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
71、，则又根据STAR=xy|xSTAR，yEXTENSION，因此，STAR= size=huge； c ) 接着选取另一个被STAR中的复合覆盖的负样例Eneg，显然已经没有这样的负样例，因此，STAR= size=huge； d ) 接着选取另一个被STAR中的复合覆盖的负样例ENEG，显然已经没有这样的负样例，因此，STAR= size=hugetype =bicycle 。从STAR（SEED，NEG）返回。（8）BEST=size=huge，将BEST添加到COVER中，COVER = size=hugetype =bicycle size=huge= size=huge。 （9）这时
72、，COVER已经覆盖到全部的正例，则算法结束。输出规则为gaint 2-wheelersize=huge。假设现有一个训练集，其包含两种属性：size （属性值：micro，tiny，mid，big，huge，vast）type （属性值：bicycle，motorcycle，car，prop，jet，glider）现有正例、反例样本分别如表4-6，表4-7所示： 反例样本size type classTiny motorcycle conventional transportation tiny car conventional transportation mid car conventi
73、onal transportation micro jetfast planeTiny jetfast planeMid jetfast plane正例样本size type classHuge bicycle giant 2-wheelerHuge motorcycle giant 2-wheeler2024/8/188数据挖掘-分类课件pptCN2算法描述nCN2使用一种基于噪音估计的启发式方法，使用这种方法可以不用对所有的训练样本进行正确的区分，但是规约出的规则在对新数据的处理上有很好的表现。算法算法 4-7 CN2输入：E /*E为训练样本*/输出：RULE_LIST /*返回一个覆盖
74、若干样例的规则*/（1） Let RULE_LIST be the empty list； /* 初始化RULES_LIST为空；*/（2） REPEAT（3） Let BEST_CPX be Find_Best_Complex（E）；/*寻找最佳的规则Find_Best_Complex（E）并将其结果放入BEST_CPX中；*/（4） IF BEST_CPX is not nil THEN BEGIN（5） Let E be the examples covered by BEST_CPX；/*令E为BEST_CPX覆盖的所有样例*/（6） Remove from E the example
75、s E covered by BEST_CPX； /*从训练样本E中除去E，即E=E-E；*/（7） Let C be the most common class of examples in E； /*令C为样本子集E中最频繁的分类标号；*/（8） Add the rule if BEST_CPX then class=C to the end of RULE_LIST；/*将规则if BEST_CPX then class=C添加到RULES_LIST中*/（9） END（10）UNTIL BEST_CPX is nil or E is empty. /*直到BEST_CPX为空或者训练样
76、本E为空*/（11）RETURN RULE_LIST算法CN2需要通过调用函数Find_Best_Complex，它的描述写成下面算法4-8。 2024/8/189数据挖掘-分类课件pptCN2算法描述(续)算法算法 4-8 Find_Best_Complex输入：E /*E为训练样本*/输出：BEST_CPX /*返回最佳的规则BEST_CPX */（1） Let the set STAR contain only the empty Complex； /*初始化集合STAR为空Complex；*/（2） Let BEST_CPX be nil； /*初始化BEST_CPX为空*/（3） L
77、et SELECTORS be the set of all possible Selectors； /*集合SELECTOR为所有可能的选择*/（4） WHILE STAR is not empty DO BEGIN（5） Let NEWSTAR be the set xy|xSTAR，yEXTENSION；/*令NEWSTAR= xy|xSTAR，yEXTENSION；*/（6） Remove all Complexes in NEWSTAR that are either in STAR or are null；/*从NEWSTAR中除去包括在STAR中的Complex或者为空的Comp
78、lex*/（7） FOR every complex Ci in NEWSTAR （8） IF Ci is statistically significant when tested on E and better than BEST_CPX according to user-defined criteria when tested on E /*如果Ci在统计上有意义，并且对训练集E测试后符合用户定义的条件且优于BEST_CPX*/（9） THEN replace the current value of BEST_CPX by Ci； /*将BEST_CPX替换为Ci*/（10） REP
79、EAT remove worst Complexes from NEWSTAR （11） UNTIL size of NEWSTAR is = user-defined maximum maxstar；/*逐步移去在NEWSTAR中最坏的complex直到NEWSTAR的大小等于或小于用户 定义的最大数目maxstar*/（12）Let STAR be NEWSTAR； /*令STAR=NEWSTAR*/（13）END（14）RETURN BEST_CPX。/*返回BEST_CPX*/ 2024/8/190数据挖掘-分类课件pptFOIL算法nFOIL学习系统已经被广泛地应用在逻辑规约领域。F
80、OIL是用来对无约束的一阶Horn子句进行学习。一个概念的定义是由一系列的子句组成，而其中每一个子句描述了一种证明一个样本是这个概念的实例的唯一方法。每个子句由一些文字的析取组成。nFOIL由一系列的外部定义的断言开始，其中之一被确定为当前学习的概念，而其他作为背景文字。FOIL从这些外部定义的断言中获取一系列包括文字的子句。nFOIL算法由一个空子句开始查找，其不断的向当前的子句中追加文字直到没有负样例被子句所覆盖。之后，FOIL重新开始一个子句的查找，直到所有的正样例均被已经生成的子句所覆盖。FOIL计算每一个外部定义断言的信息熵（Information Gain）和合法的变量（Legal
81、 Variabilization）用来决定哪一个文字添加到子句中。2024/8/191数据挖掘-分类课件ppt一阶Horn子句的主要术语n一阶Horn子句所涉及的主要术语有：n所有表达式由常量（如Mary、23或Joe）、变量（如x）、谓词（如在Female（Mary）中的Female和函数（如在age（Mary）中的age）组成；n项（Term）为任意常量、任意变量或任意应用到项集合上的函数。例如，Mary，x，age（Mary），age（x）；n文字（Literal）是应用到项集合上的任意谓词或其否定。例如，Female（Mary），Greater_than（age（Mary），20）；n
82、基本文字（Ground Literal）是不包括任何变量的文字；n负文字（Negative Literal）是包括否定谓词的文字；n正文字（Positive Literal）是不包括否定谓词的文字；n子句（Clause）是多个文字的析取式，M1Mn，其中所有变量是全程量化的；2024/8/192数据挖掘-分类课件ppt一阶Horn子句的表达nHorn子句是一个如下形式的表达式： H(L1Ln）。其中，H，L1，L2，Ln为正文字。H被称为Horn子句的头（Head）或推论（Consequent）。文字合取式L1L2.Ln被称为Horn子句的体（Body）或者先行词（Antecedents）。n
83、置换（Substitution）是一个将某些变量替换为某些项的函数。例如，置换x/3，y/z把变量x替换为项3并且把变量y替换为项z。给定一个置换和一个文字L，我们使用L代表应用置换到L得到的结果。2024/8/193数据挖掘-分类课件pptFOIL算法描述算法算法 4-9 4-9 FOIL （Target_predicate，Predicates，Examples）输入：Examples /*样本数据*/ Predicates /*断言集合*/ Target_predicate /*目标断言*/输出：规则（1） PosExamples中Target_predicate为Ture的成员；（2）
84、 NegExamples中Target_predicate为False的成员；（3） Learen_rules；（4） WHILE Pos不空DO BEGIN /*学习NewRule*/（5） NewRules没有前件的谓词Target_predicate规则；（6） NewRuleNegNeg；（7） WHILE NewRuleNeg不空 BEGIN /*增加新文字以特化NewRule*/（8） Candidate_literals对NewRule生成后选新文字，基于Predicates；（9） Best_literalargmax Foil_Gain （L，NewRule）； /*获取最佳
85、文字*/（10） 把Best_literal加入到NewRule的前件；（11） NewRuleNegNewRuleNeg中满足NewRule前件的子集（12） END；（13） Learned_rulesLearned_rules+NewRule；（14） PosPos-被NewRule覆盖的Pos成员（15） END；（16） 返回Learned_rules2024/8/194数据挖掘-分类课件pptFOIL算法介绍n FOIL中的候选特征化式的生成： 为生成当前规则的候选特征式，FOIL生成多个不同的新文字，每个可被单独地加到规则前件中。更精确地讲，假定当前规则为：P P( (x x1
86、1，x x2 2，x xk k) ) L L1 1L L其中，L1，Ln为当前规则前件中的文字，而P(x1，x2，xk)为规则头（或后件）。FOIL生成该规则的候选特征化式的方法是考虑符合下列形式的新文字Ln+1：n Q(v1，vr)，其中Q为在Predicates中出现的任意谓词名，并且vi既可 为新变量，也可为规则中已有的变量。vi中至少一个变量必须是当前规则中已有的。nEqual(xj，xk)，其中xj和xk为规则中已有的变量。n上述两种文字的否定。2024/8/195数据挖掘-分类课件pptFOIL算法介绍(续)n Foil_Gain Foil_Gain函数函数 n FOIL使用评估函
87、数以估计增加新文字的效用，它基于加入新文字前后的正例和反例的约束数目。更精确地讲，考虑某规则R和一个可能被加到R的规则体的后选文字L。令R为加入文字L到规则R后生成的规则。Foil_Gain(L，R)的值定义为：其中，p p0 0为规则为规则R R的正例约束数目，的正例约束数目，n n0 0为为R R的反例约束数目，的反例约束数目，p p1 1是规则是规则RR的正例约束数，的正例约束数，n n1 1为规则为规则RR的反例约束数的反例约束数目目。最后，t是在加入文字L到R后仍旧能覆盖的规则R的正例约束数目。当加入L引入了一个新变量到R中时，只要在R的约束中的某些约束扩展了原始的约束，它们仍然能被
88、覆盖。 2024/8/196数据挖掘-分类课件pptFOIL算法举例假设学习目标文字fathe(A，B)的规则集例子。训练数据包括下列简单的断言集合：Examples: /*样本数据*/positive: father(christopher，arthur) father(christopher，victoria)negative: father(penelope，arthur) father(christopher，penelope)Predicates: /断言集合male(christopher)，male(arthur)female(victoria)，female(penelope)
89、parent(christopher，arthur)，parent(christopher，victoria)parent(penelope，arthur)，parent(penelope，victoria)则根据FOIL算法：nPos=father(christopher，arthur)，father(christopher，victoria)；nNeg=father(penelope，arthur)， father(christopher，penelope)；nLearned_rules=；n当Pos不为空，则学习NewRulea) NewRule=father(A，B)；b) NewRu
90、leNeg= father(penelope，arthur)， father(christopher，penelope)；c) 当NewRuleNeg不为空，则增加特征化文字：由FOIL中的侯选特征化式的规则，根据father(A，B)可生成的侯选文字为：male(A)， not(male(A)， male(B)， not(male(B)，female(A)， not(female(A)， female(B)， not(female(B)，parent(A，A)， not(parent(A，A)， parent(B，B)， not(parent(B，B)，parent(A，B)， not(pa
91、rent(A，B)， parent(B，A)， not(parent(B，A)，parent(A，C)， not(parent(A，C)， parent(C，A)， not(parent(C，A)，parent(B，C)， not(parent(B，C)， parent(C，B)， not(parent(C，B)；因此，Candidate_literals= male(A)，male(B)，female(A)，female(B)，之后计算最佳文字Best_literal，具体计算过程如下表所示(p0=2，n0=2 )。2024/8/197数据挖掘-分类课件pptFOIL算法举例(续) 文字的获
92、益计算结果Testp1n1tGainmale(A)2120.83not(male(A)0100.00male(B)1110.00not(male(B)1110.00female(A)0100.00not(female(A)2120.83female(B)1110.00not(female(B)1110.00parent(A，A)0000.00not(parent(A，A)2220.00parent(A，B)2120.83not(parent(A，B)0100.00parent(B，B)0000.00not(parent(B，B)2220.00parent(B，A)0000.00not(pare
93、nt(B，A)2220.00parent(A，C)4420.00not(parent(A，C)0000.00parent(C，B)0000.00not(parent(C，B)2120.832024/8/198数据挖掘-分类课件pptFOIL算法举例(续)选择文字male(A) 添加到Best_literal，NewRule= father(A，B) male(A)，其覆盖两个正例和一个反例。NewRuleNeg改写为NewRuleNeg=father(penelope，arthur)，d) 当NewRuleNeg不为空，则增加特征化文字：则下一个文字应添加parent(A，B)。再将Best_
94、literal加为NewRule的前件，则NewRule= father (A，B) male(A)parent(A，B)；这时NewRuleNeg中的所有成员满足NewRule前件的子集，跳出内层循环。e) Learn_rules=Learn_rules+ father (A，B) male(A)parent(A，B) ；f) 再从Pos中减去被NewRules覆盖的成员；n这时Pos为空，算法结束。2024/8/199数据挖掘-分类课件ppt第三章第三章 分类方法分类方法 内容提要内容提要n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n规则归纳 n与分类有关
95、的问题 2024/8/1100数据挖掘-分类课件ppt分类数据预处理n分类的效果一般和数据的特点有关，有的数据噪声大，有的有空缺值，有的分布稀疏，有的字段或属性间相关性强，有的属性是离散的而有的是连续值或混合式的。目前普遍认为不存在某种方法能适合于各种特点的数据。因此，在分类以前需要做一些数据的预处理。n 数据清理数据清理n主要是消除或减少数据噪声和处理空缺值。 n 特征选择特征选择n从已知一组特征集中按照某一准则选择出有很好的区分特性的特征子集n或按照某一准则对特征的分类性能进行排序，用于分类器的优化设计。n 数据变换数据变换n就是通过平滑、聚集、数据概化、规范化、特征构造等手段将数据转化为
96、适合于挖掘的形式。2024/8/1101数据挖掘-分类课件ppt分类器性能的表示n分类器性能的表示方法类似信息检索系统的评价方法，可以采用OC曲线和ROC曲线、混淆矩阵等。n定义定义4-4 4-4 给定一个类Cj和一个数据库元组ti，ti可能被分类器判定为属于Cj或不属于Cj，其实ti本身可能属于Cj或不属于Cj，这样就会产生如下一些情况：n真正: 判定ti在Cj中，实际上的确在其中。n假正: 判定ti在Cj中，实际上不在其中。n真负: 判定ti不在Cj中，实际上不在其中。n假负: 判定ti不在Cj中，实际上的确在其中。n在上述定义的基础上，人们经常使用OC曲线和ROC曲线表示“假正”和“真正
97、”的关系。OC曲线通常用于通信领域来测试误报率。OC曲线的水平轴一般表示“假正”的百分比，另外一个轴表示“真正”的百分比。2024/8/1102数据挖掘-分类课件ppt分类器性能的表示（续）n混淆矩阵是另外一种表示分类准确率的方法。假定有m个类，混淆矩阵是一个 m*m 的矩阵，Ci，j表明了D中被分到类Cj但实际类别是Ci的元组的数量。显然地，最好解决方案是对角线以外的值为全零。混淆矩阵示例实 际 分 类矮中等高矮040中等053高0122024/8/1103数据挖掘-分类课件ppt分类器性能的评估n保持法和交叉验证是两种基于给定数据随机选样划分的、常用的评估分类方法准确率的技术。n（1 1）
98、保持法）保持法把给定的数据随机地划分成两个独立的集合：训练集和测试集。通常，三分之一的数据分配到训练集，其余三分之二分配到测试集。使用训练集得到分类器，其准确率用测试集评估。n（2 2）交叉验证）交叉验证先把数据随机分成不相交的n份，每份大小基本相等，训练和测试都进行n次。比如，如果把数据分成10份，先把第一份拿出来放在一边用作模型测试，把其他9份合在一起来建立模型，然后把这个用90%的数据建立起来的模型用上面放在一边的第一份数据做测试。这个过程对每一份数据都重复进行一次，得到10个不同的错误率。最后把所有数据放在一起建立一个模型，模型的错误率为上面10个错误率的平均。 2024/8/1104数据挖掘-分类课件ppt第三章第三章 分类方法分类方法 内容提要内容提要n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n规则归纳 n与分类有关的问题 2024/8/1105数据挖掘-分类课件pptThank you !2024/8/1106数据挖掘-分类课件ppt此课件下载可自行编辑修改，供参考！此课件下载可自行编辑修改，供参考！感谢你的支持，我们会努力做得更好！感谢你的支持，我们会努力做得更好！
