1、2022年6月16日星期四1大数据分析与数据挖掘大数据分析与数据挖掘分类方法分类方法 内容提要内容提要n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n规则归纳 n与分类有关的问题 2022年6月16日星期四2分类是数据挖掘中重要的任务 n分类的目的是学会一个分类器（分类函数或模型），该分类器能把待分类的数据映射到给定的类别中。n分类可用于预测。从利用历史数据纪录中自动推导出对给定数据的推广描述，从而能对未来数据进行类预测。n分类具有广泛的应用，例如医疗诊断、信用卡系统的信用分级、图像模式识别等。n分类器的构造依据的方法很广泛：n统计方法：包括贝叶斯法和非参数法等
2、。n机器学习方法：包括决策树法和规则归纳法。n神经网络方法。n其他，如粗糙集等（在前面绪论中也介绍了相关的情况）。2022年6月16日星期四3分类方法的类型n从使用的主要技术上看，可以把分类方法归结为四种类型：n基于距离的分类方法n决策树分类方法n贝叶斯分类方法n规则归纳方法。n本章将择选一些有代表性的方法和算法来介绍这四类分类方法。2022年6月16日星期四4分类问题的描述n定义定义4-1 4-1 给定一个数据库 D=t1，t2，tn和一组类 C=C1，Cm，分类问题是去确定一个映射 f: DC，使得每个元组ti被分配到一个类中。一个类Cj 包含映射到该类中的所有元组，即Cj = ti |
3、f(ti) = Cj，1 i n， 而且ti D。n例如，把学生的百分制分数分成A、B、C、D、F五类，就是一个分类问题： D是包含百分制分数在内的学生信息， C=A、B、C、D、F。n解决分类问题的关键是构造一个合适的分类器：从数据库到一组类别集的映射。一般地，这些类是被预先定义的、非交叠的。2022年6月16日星期四5数据分类的两个步骤1 1建立一个模型，描述预定的数据类集或概念集建立一个模型，描述预定的数据类集或概念集n数据元组也称作样本、实例或对象。n为建立模型而被分析的数据元组形成训练数据集。n训练数据集中的单个元组称作训练样本，由于提供了每个训练样本的类标号，因此也称作有指导的学习
4、。n通过分析训练数据集来构造分类模型，可用分类规则、决策树或数学公式等形式提供。n2 2使用模型进行分类使用模型进行分类n首先评估模型（分类法）的预测准确率。n如果认为模型的准确率可以接受，就可以用它对类标号未知的数据元组或对象进行分类。2022年6月16日星期四6第三章第三章 分类方法分类方法 内容提要内容提要n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n规则归纳 n与分类有关的问题 2022年6月16日星期四7基于距离的分类算法的思路n定义定义4-2 4-2 给定一个数据库给定一个数据库 D D=t t1 1，t t2 2，t tn n 和一和一组类组类C
5、 C=C C1 1，C Cmm 。假定每个元组包括一些数。假定每个元组包括一些数值型的属性值：值型的属性值：t ti i=t ti1 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，
6、C Cj j) )被称为相似性。被称为相似性。n在实际的计算中往往用在实际的计算中往往用距离距离来表征，距离越近，来表征，距离越近，相似性越大，距离越远，相似性越小。相似性越大，距离越远，相似性越小。n距离的计算方法有多种，最常用的是通过计算每距离的计算方法有多种，最常用的是通过计算每个类的中心来完成。个类的中心来完成。2022年6月16日星期四8 基于距离的分类算法的一般性描述n算法 4-1通过对每个元组和各个类的中心来比较，从而可以找出他的最近的类中心，得到确定的类别标记。算法算法 4-1 基于距离的分类算法输入：每个类的中心C1，Cm；待分类的元组t。 输出：输出类别c。 （1）dist
7、=；/距离初始化（2）FOR i:=1 to m DO （3） IF dis(ci，t)dist THEN BEGIN（4）c i； （5）distdist(ci，t)； （6） END.2022年6月16日星期四9基于距离的分类方法的直观解释（a）类定义（b）待分类样例（c）分类结果2022年6月16日星期四10K-近邻分类算法nK-近邻分类算法（K Nearest Neighbors，简称KNN）通过计算每个训练数据到待分类元组的距离，取和待分类元组距离最近的K个训练数据，K个数据中哪个类别的训练数据占多数，则待分类元组就属于哪个类别。算法算法 4-2 K-近邻分类算法输入： 训练数据T；
8、近邻数目K；待分类的元组t。 输出： 输出类别c。 （1）N=；（2）FOR each d T DO BEGIN（3） IF |N|K THEN（4） N=Nd； （5） ELSE（6） IF u N such that sim(t，u)sim(t，d) THEN BEGIN （7） N=N-u；（8） N=Nd；（9） END（10）END（11）c=class to which the most uN. 2022年6月16日星期四11K-means算法：n根据聚类中的均值进行聚类划分：输入输入：聚类个数k以及包含n个数据对象的数据库。输出输出：满足方差最小标准的k个聚类。2022年6月16
9、日星期四12处理流程：n（1）从n个数据对象任意选择k个对象作为初始聚类中心。n（2）循环流程（3）到（4），直到每个聚类不再发生变化为止。n（3）根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离，并根据最小距离重新对相应对象进行划分。n（4）重新计算每个有变化聚类的均值（中心对象）。2022年6月16日星期四13k-均值算法标准n均方误差：kiCpiimpE12)(2022年6月16日星期四14聚类的分析过程聚类的分析过程 2022年6月16日星期四15n坐标表示坐标表示5 5个点个点X1,X2,X3,X4,X5X1,X2,X3,X4,X5作为一作为一个聚类分析的二维样本
10、：个聚类分析的二维样本：X1X1（0,20,2），），X2X2（0,00,0），），X3X3（1.5,01.5,0），），X4X4（5,05,0），），X5X5（5,25,2）。假设要求的簇的数量）。假设要求的簇的数量k=2k=2。对这对这5 5个点进行分类。个点进行分类。2022年6月16日星期四16k-均值算法的性能分析：n优点：nK-均值算法是解决聚类问题的一种典型算法，这种算法简单、快速；n对处理大型数据集，该算法是相对可伸缩的和高效的；n算法尝试找出使平方误差函数值最小的k个划分。当结果簇是密集的，而簇与簇之间区别明显时，效果是较好的。2022年6月16日星期四17k-均值算法的性能
11、分析：（续）n缺点：nK-均值算法只有在簇的平均值在被定义的情况下才能使用。n要求用户事先必须拿出k，而且对初值不敏感，对于不同的初始值，可能会导致不同的聚类结果；n不适合于发现非凸面形状的簇，或者大小差别很大的簇；n对于“噪声”与孤立点数据是敏感的，少量的该类数据能够对平均值产生极大影响。2022年6月16日星期四18K-mediods算法：n根据聚类中的中心对象进行划分：输入输入：聚类个数k以及包含n个数据对象的数据库。输出输出：满足基于各聚类中心对象的方差最小标准的k个聚类。PAM(Partitioning Around MedoidsPAM(Partitioning Around Me
12、doids围绕中心点划围绕中心点划分分) )2022年6月16日星期四19处理流程：n（1）从n个数据对象任意选择k个对象作为初始聚类中心代表。n（2）循环流程（3）到（5），直到每个聚类不再发生变化为止。n（3）依据每个聚类的中心代表对象以及各对象与这些中心对象间距离，并根据最小距离重新对相应对象进行划分。n（4）任意选择一个非中心对象，计算其与中心对象交换的整个成本S。n（5）若S为负值则交换非中心对象与中心对象以构成新聚类的k个中心对象。2022年6月16日星期四20为了判定一个非代表对象Oh是否是当前一个代表对象Oi的好的替代。对于每一个非中心点对象Oj，下面的四种情况被考虑：n假设O
13、i被Oh代替作为新的中心点，Oj当前隶属于中心点对象Oi。如果Oj离某某个中心点Om最近，im，那么Oj被重新分配给Om；n假设Oi被Oh代替作为新的中心点，Oj当前隶属于中心点对象Oi。如果Oj离这这个新的中心点Oh最近，那么Oj被分配给Oh；n假设Oi被Oh代替作为新的中心点，但是Oj当前隶属于另一个中心点对象Om， im。如果Oj依然依然离Om最近，那么对象的隶属不发生变化；n假设Oi被Oh代替作为新的中心点，但是Oj当前隶属于另一个中心点对象Om， im。如果Oj离这个新的中心点Oh最近，那么Oi被重新分配给Oh。2022年6月16日星期四21n总代价定义：n其中Cjih表示Oj在Oi
14、被Oh代替后产生的代价。njjihihCTC12022年6月16日星期四22代价的计算公式：nOI与Om是两个原中心点，Oh将代替Oi作为新的中心点。代价函数的计算方式如下：n第一种情况： Oj当前隶属于Oi，但Oh替换Oi后Oj被重新分配给Om，则代价函数为：Cjih=d(j,m)-d(j,i)n第二种情况：Oj当前隶属于Oi，但Oh替换Oi后Oj被重新分配给Oh，则代价函数为：Cjih=d(j,h)-d(j,i)n第三种情况：Oj当前隶属于另一个中心点对象Om， im，但Oh替换Oi后Oj的隶属不发生变化，则代价函数为：Cjih=0n第四种情况： Oj当前隶属于另一个中心点对象Om， im
15、，但Oh替换Oi后Oj被重新分配给Oh，则代价函数为：Cjih=d(j,h)-d(j,m)2022年6月16日星期四23+Oi P Oj + + Orandom+Oi Oj + P + Orandom用图1表示如下：2022年6月16日星期四24+Oi P Oj + + Orandom+Oi Oj + + P Orandom2022年6月16日星期四25例：加入空间中有五个点A,B,C,D,E如图所示，各点之间的距离关系如下表，根据所给的数据进行分类。ABCDEABCDEA01223B10243C22015D24103E335302022年6月16日星期四26解：n第一步：建立阶段：加入从5个
16、对象中随机抽取的2个中心点为A,B，则样本被划分为A,C,D与B,E;n第二步 交换阶段：假定中心点A,B分别被非中心点C,D,E替换，计算代价TCAC,TCAD,TCAE,TCBC,TCBD,TCBE;2022年6月16日星期四27计算TCAC如下：n当A被C替换后，看A是否发生变化：A不再是一个中心点，C称为新的中心点，属于第一种情况。因为A离B比A离C近，A被分配到B中心点代表的簇： CAAC=d(A,B)-d(A,A)=1n当A被C替换后，看B是否发生变化：属于第三种情况。当A被C替换以后，B不受影响： CBAC=02022年6月16日星期四28计算TCAC如下(续 )n当A被C替换后
17、，看C是否发生变化：C原先属于A中心点所在的簇，当A被C替换以后，C是新中心点符合图1中的第二种情况： CCAC=d(C,C)-d(C,A)=-2n当A被C替换后，看D是否发生变化：D原先属于A中心点所在的簇，当A被C替换以后，离D最近的中心点是C，符合图1 的第二种情况： CDAC=d(D,C)-d(D,A)=-12022年6月16日星期四29计算TCAC如下(续 )n当A被C替换后，看E是否发生变化：E原先属于B中心点所在的簇，离E最近的中心点是B，符合图1 的第三种情况： CEAC=0n因此TCAC=-22022年6月16日星期四30算法的性能分析：nK-中心点算法消除了k-平均算法对于
18、孤立点的敏感性；n当存在“噪声”与孤立点数据时，k-中心点方法比k-平均方法更健壮，这是因为中心点不像平均值那么容易被极端数据影响，但是，k-中心点方法的执行代价比k-平均方法高；n算法必须指定聚类的数目k，k的取值对聚类质量有重大影响；nK-中心点算法对于小的数据非常有效，但对于大数据集效率不高。2022年6月16日星期四31KNN的例子姓名性别 身高(米)类别Kristina女 1.6 矮Jim男 2 高Maggie女 1.9 中等Martha女 1.88 中等Stephanie女 1.7 矮Bob男 1.85 中等Kathy女 1.6 矮Dave男 1.7 矮Worth男 2.2 高St
19、even男 2.1 高Debbie女 1.8 中等Todd男 1.95 中等Kim女 1.9 中等Amy女 1.8 中等Wynette女 1.75 中等2022年6月16日星期四32KNN的例子“高度”用于计算距离，K=5，对分类。 对T前K=5个记录，N=、和。对第6个记录d=，得到N=、和。对第7个记录d=，得到N=、和。对第8个记录d=，得到N=、和。对第9和10个记录，没变化。对第11个记录d=，得到N=、和。对第12到14个记录，没变化。对第15个记录d=，得到N=、和。 最后的输出元组是、和。在这五项中，四个属于矮个、一个属于中等。最终KNN方法认为Pat为矮个。 。2022年6月
20、16日星期四33第三章第三章 分类方法分类方法 内容提要内容提要n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n规则归纳 n与分类有关的问题 2022年6月16日星期四34决策树表示与例子n决策树（Decision Tree）的每个内部结点表示在一个属性上的测试，每个分枝代表一个测试输出，而每个树叶结点代表类或类分布。树的最顶层结点是根结点。n buys_computer的决策树示意 2022年6月16日星期四35n决策树的各部分是: 根: 学习的事例集. 枝: 分类的判定条件. 叶: 分好的各个类. 2022年6月16日星期四36决策树分类的特点n决策树分类方
21、法采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分枝，在决策树的叶结点得到结论。所以从决策树的根到叶结点的一条路径就对应着一条合取规则，整棵决策树就对应着一组析取表达式规则。n基于决策树的分类算法的一个最大的优点就是它在学习过程中不需要使用者了解很多背景知识（这同时也是它的最大的缺点），只要训练例子能够用属性-结论式表示出来，就能使用该算法来学习。n决策树分类模型的建立通常分为两个步骤：n决策树生成n开始，数据都在根节点n递归的进行数据分片n决策树修剪。n去掉一些可能是噪音或者异常的数据2022年6月16日星期四37决策树生成算法描述算法算法 4
22、-3 Generate_decision_tree(samples, attribute_list) /*决策树生成算法*/输入：训练样本samples，由离散值属性表示；候选属性的集合attribute_list。输出：一棵决策树。（1） 创建结点N；（2） IF samples 都在同一个类C THEN 返回N 作为叶结点，以类 C标记；（3） IF attribute_list为空 THEN 返回N作为叶结点，标记为samples中最普通的类；/多数表决（4） 选择attribute_list中具有最高信息增益的属性test_attribute；（5） 标记结点N为test_attrib
23、ute；（6） FOR each test_attribute中的已知值ai 由结点N长出一个条件为test_attribute=ai的分枝；（7）设si是samples 中test_attribute =ai的样本的集合；/一个划分（8）IF si 为空 THEN 加上一个树叶，标记为samples中最普通的类；（9）ELSE 加上一个由Generate_decision_tree(si， attribute_list-test_attribute)返回的结点；2022年6月16日星期四38决策树生成算法描述n构造好的决策树的关键在于如何选择好的属性进行树的拓展。研究结果表明，一般情况下或具
24、有较大概率地说，树越小则树的预测能力越强。由于构造最小的树是NP-难问题，因此只能采取用启发式策略来进行。n属性选择依赖于各种对例子子集的不纯度（Impurity）度量方法，包括信息增益（Informatin Gain）、信息增益比（Gain Ratio）、Gini-index、距离度量（Distance Measure）、J-measure、G统计、2统计、证据权重（Weight of Evidence）、最小描述长度（MLP）、正交法（Ortogonality Measure）、相关度（Relevance）和 Relief等。2022年6月16日星期四39决策树修剪算法n基本的决策树构造算
25、法没有考虑噪声，因此生成的决策树完全与训练例子拟合。在有噪声情况下，将导致过分拟合（Overfitting），即对训练数据的完全拟合反而使对现实数据的分类预测性能下降。n现实世界的数据一般不可能是完美的，可能缺值（Missing Values）；数据不完整；含有噪声甚至是错误的。n剪枝是一种克服噪声的基本技术，同时它也能使树得到简化而变得更容易理解。有两种基本的剪枝策略：n预先剪枝（Pre-Pruning）：在生成树的同时决定是继续对不纯的训练子集进行划分还是停机。n后剪枝（Post-Pruning）：是一种拟合+化简（fitting-and-simplifying）的两阶段方法。首先生成与训
26、练数据完全拟合的一棵决策树，然后从树的叶子开始剪枝，逐步向根的方向剪。剪枝时要用到一个测试数据集合（Tuning Set或Adjusting Set），如果存在某个叶子剪去后能使得在测试集上的准确度或其他测度不降低（不变得更坏），则剪去该叶子；否则停机。理论上讲，后剪枝好于预先剪枝，但计算复杂度大。n剪枝过程中一般要涉及一些统计参数或阈值（如停机阈值）。要防止过分剪枝（Over-Pruning）带来的副作用。2022年6月16日星期四40ID3算法nID3是Quinlan提出的一个著名决策树生成方法：n决策树中每一个非叶结点对应着一个非类别属性，树枝代表这个属性的值。一个叶结点代表从树根到叶结
27、点之间的路径对应的记录所属的类别属性值。n每一个非叶结点都将与属性中具有最大信息量的非类别属性相关联。n采用信息增益来选择能够最好地将样本分类的属性。n为了聚焦重点，将对ID3算法采用如下方式讲解：n伪代码详细描述见课本；n给出信息增益对应的计算公式；n通过一个例子来说明它的主要过程。2022年6月16日星期四41信息增益的计算n设S是s个数据样本的集合，定义m个不同类Ci（i=1，2，m），设si是Ci类中的样本数。对给定的样本S所期望的信息值由下式给出：其中pi是任意样本属于Ci的概率： si / s 。 n设属性A具有个不同值a1, a2, , av ，可以用属性A将样本S划分为 S1,
28、 S2, , Sv ，设sij 是Sj中Ci类的样本数，则由A划分成子集的熵由下式给出： n有A进行分枝将获得的信息增益可以由下面的公式得到：miiimppsssI1221)(log),.,()s,.,s( Iss.sE(A)mjjvjmjj111E(A)s,.,s ,I(sGain(A)m212022年6月16日星期四42例：表1为一个商场顾客数据库。例：表1为一个商场顾客数据库ageincomestudentcredit_ratingbuys_computer=30highnofairno40mediumnofairyes40lowyesfairyes40lowyesexcellentno
29、3140lowyesexcellentyes=30mediumnofairno40mediumyesfairyes40mediumnoexcellentnon样本集合的类别属性为：样本集合的类别属性为：”buy_computerbuy_computer”2022年6月16日星期四432022年6月16日星期四44ID3算法n1.概念提取算法CLS 1) 初始化参数C=E,E包括所有的例子,为根. 2) IF C中的任一元素e同属于同一个决策类则创建一个叶子 节点YES终止. ELSE 依启发式标准,选择特Fi=V1,V2,V3,Vn并创建 判定节点 划分C为互不相交的N个集合C1,C2,C3,
30、Cn； 3) 对任一个Ci递归. 2022年6月16日星期四45ID3算法n1) 随机选择C的一个子集W (窗口). 2) 调用CLS生成W的分类树DT(强调的启发式标准在后). 3) 顺序扫描C搜集DT的意外(即由DT无法确定的例子). 4) 组合W与已发现的意外,形成新的W. 5) 重复2)到4),直到无例外为止.2022年6月16日星期四46启发式标准:n只跟本身与其子树有关,采取信息理论用熵来量度. 熵是选择事件时选择自由度的量度,其计算方法为 P = freq(Cj,S)/|S|; INFO(S)= - SUM( P*LOG(P) ) ; SUM()函数是求j从1到n和. Gain(
31、X)=Info(X)-Infox(X); Infox(X)=SUM( (|Ti|/|T|)*Info(X); 为保证生成的决策树最小,ID3算法在生成子树时,选取使生成的子树的熵(即Gain(S)最小的的特征来生成子树. 2022年6月16日星期四47ID3算法对数据的要求n1. 所有属性必须为离散量. 2. 所有的训练例的所有属性必须有一个明确的值. 3. 相同的因素必须得到相同的结论且训练例必须唯一. 2022年6月16日星期四48ID3算法例子样本数据warm_bloodedfeathersfurswimslays_eggs11100120001131100141100151001061
32、0100 假设目标分类属性是lays_eggs，计算Gain(lays_eggs)： warm_blooded=1， warm_blooded=0，类似的，Gain(feathers)=0.459；Gain(fur)=0.316；Gain(swims)=0.044。971. 0)( 2 321,112111ssIss，0)( 0 122,122212ssIss，0.809)(61)(65)(22,1221,11ssIssIedwarm_bloodE189062log6264log64)24()(2221.IssI，162. 0)()()(2,1edwarm_bloodEssIedwarm_bl
33、oodGain由于feathers在属性中具有最高的信息增益，所以它首先被选作测试属性。并以此创建一个结点，数据集被划分成两个子集。2022年6月16日星期四49ID3算法例子（续）n根据feathers的取值，数据集被划分成两个子集n对于feathers=1的所有元组，其目标分类属性=lays_eggs均为1。所以，得到一个叶子结点。 n对于feathers=0的右子树，计算其他属性信息增益：nGain(Gain(warm_bloodedwarm_blooded)=)=0.9180.918nGain(Gain(furfur)=0.318)=0.318nGain(Gain(swimsswims
34、)=0.318)=0.318n根据warm_blooded的取值，左右子树均可得到叶子结点，结束。2022年6月16日星期四50ID3算法的性能分析nID3算法的假设空间包含所有的决策树，它是关于现有属性的有限离散值函数的一个完整空间。所以ID3算法避免了搜索不完整假设空间的一个主要风险：假设空间可能不包含目标函数。nID3算法在搜索的每一步都使用当前的所有训练样例，大大降低了对个别训练样例错误的敏感性。因此，通过修改终止准则，可以容易地扩展到处理含有噪声的训练数据。nID3算法在搜索过程中不进行回溯。所以，它易受无回溯的爬山搜索中的常见风险影响：收敛到局部最优而不是全局最优。nID3算法只能
35、处理离散值的属性。n信息增益度量存在一个内在偏置，它偏袒具有较多值的属性。例如，如果有一个属性为日期，那么将有大量取值，这个属性可能会有非常高的信息增益。假如它被选作树的根结点的决策属性则可能形成一颗非常宽的树，这棵树可以理想地分类训练数据，但是对于测试数据的分类性能可能会相当差。nID3算法增长树的每一个分支的深度，直到恰好能对训练样例完美地分类。当数据中有噪声或训练样例的数量太少时，产生的树会过渡拟合训练样例。2022年6月16日星期四51C4.5算法对ID3的主要改进nC4.5算法是从ID3算法演变而来，除了拥有ID3算法的功能外，C4.5算法引入了新的方法和增加了新的功能：n用信息增益
36、比例的概念；n合并具有连续属性的值；n可以处理具有缺少属性值的训练样本；n通过使用不同的修剪技术以避免树的过度拟合；nK交叉验证；n规则的产生方式等。2022年6月16日星期四52信息增益比例的概念n信息增益比例是在信息增益概念基础上发展起来的，一个属性的信息增益比例用下面的公式给出：其中假如我们以属性A的值为基准对样本进行分割的化，Splitl(A)就是前面熵的概念。 )()()(ASplitIAGainAGainRatio)(log)(12jvjjppASplitI2022年6月16日星期四53C4.5处理连续值的属性n对于连续属性值，C4.5其处理过程如下：n根据属性的值，对数据集排序；
37、n用不同的阈值将数据集动态的进行划分；n当输出改变时确定一个阈值；n取两个实际值中的中点作为一个阈值；n取两个划分，所有样本都在这两个划分中；n得到所有可能的阈值、增益及增益比；n在每一个属性会变为取两个取值，即小于阈值或大于等于阈值。n简单地说，针对属性有连续数值的情况，则在训练集中可以按升序方式排列。如果属性A共有n种取值，则对每个取值vj（j=1，2，n），将所有的记录进行划分：一部分小于vj；另一部分则大于或等于vj 。针对每个vj计算划分对应的增益比率，选择增益最大的划分来对属性A进行离散化 。 2022年6月16日星期四54C4.5的其他处理 nC4.5处理的样本中可以含有未知属性
38、值，其处理方法是用最常用的值替代或者是将最常用的值分在同一类中。n具体采用概率的方法，依据属性已知的值，对属性和每一个值赋予一个概率，取得这些概率，取得这些概率依赖于该属性已知的值。n规则的产生：规则的产生：一旦树被建立，就可以把树转换成if-then规则。n规则存储于一个二维数组中，每一行代表树中的一个规则，即从根到叶之间的一个路径。表中的每列存放着树中的结点。 2022年6月16日星期四55C4.5算法例子样本数据OutlookTemperatureHumidityWindPlayTennisSunnyHot85falseNoSunnyHot90trueNoOvercastHot78fal
39、seYesRainMild96falseYesRainCool80falseYesRainCool70trueNoOvercastCool65trueYesSunnyMild95falseNoSunnyCool70falseYesRainMild80falseYesSunnyMild70trueYesOvercastMild90trueYesOvercastHot75falseYesRainMild80trueNo（1）首先对Humidity进行属性离散化，针对上面的训练集合，通过检测每个划分而确定最好的划分在75处，则这个属性的范围就变为（75）。（2）计算目标属性PlayTennis分类的
40、期望信息： （3）计算每个属性的GainRatio：（4）选取最大的GainRatio，根据Outlook的取值，将三分枝。（5）再扩展各分枝节点，得到最终的决策树（见课本图4-7 ）。 940. 0145log145149log149)5 , 9(),(2221 IssI0.0483 Humidity)GainRatio(0.0248 e)TemperaturGainRatio(049. 0)(156. 0577. 12467. 0)(；windyGainRatioOutlookGainRatio2022年6月16日星期四56例2n银行在处理一批客户的信贷活动中，确定是否对具备贷款条件的客户
41、发放贷款，存在决策分析问题。在客户信息表中去一些不必要的属性，保留收入、客户年龄、信誉度、贷款期限和准予贷款5个属性，样本数据集如下表：2022年6月16日星期四572022年6月16日星期四582022年6月16日星期四592022年6月16日星期四602022年6月16日星期四61第三章第三章 分类方法分类方法 内容提要内容提要n分类的基本概念与步骤 n基于距离的分类算法 n决策树分类方法 n贝叶斯分类 n规则归纳 n与分类有关的问题 2022年6月16日星期四62n贝叶斯分类是统计学的分类方法，其分析方法的特点是使用概率来表示所有形式的不确定性，学习或推理都用概率规则来实现；n朴素贝叶斯
42、分类：假定一个属性值对给定类的影响独立于其他属性的值；n贝叶斯网络：是用来表示变量间连接概率的图形模式,它提供了一种自然的表示因果信息的方法,用来发现数据间的潜在关系。2022年6月16日星期四63对分类方法进行比较的有关研究结果表明：简单贝叶斯分类器（称为基本贝叶斯分类器）在分类性能上与决策树和神经网络都是可比的。在处理大规模数据库时，贝叶斯分类器已表现出较高的分类准确性和运算性能。基本贝叶斯分类器假设一个指定类别中各属性的取值是相互独立的。这一假设也被称为：类别条件独立，它可以帮助有效减少在构造贝叶斯分类器时所需要进行的计算量。2022年6月16日星期四64贝叶斯分类n定义定义4-2 4-
43、2 设设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(H)P(H)是先验概率是先验概率，或称或称H H的先验概率。的先验概率。P(X |H)P(X |H)代表假设代表假设H H成立的情况下，观察到成立的情况下，观察到X
44、X的概率。的概率。P(H| X )P(H| X )是后验概率是后验概率，或或称条件称条件X X下下H H的后验概率。的后验概率。n例如，假定数据样本域由水果组成，用它们的颜色和形状例如，假定数据样本域由水果组成，用它们的颜色和形状来描述。假定来描述。假定X X表示红色和圆的，表示红色和圆的，H H表示假定表示假定X X是苹果，则是苹果，则P(H|X)P(H|X)反映当我们看到反映当我们看到X X是红色并是圆的时，我们对是红色并是圆的时，我们对X X是是苹果的确信程度。苹果的确信程度。n贝叶斯分类器对两种数据具有较好的分类效果：一种是完贝叶斯分类器对两种数据具有较好的分类效果：一种是完全独立的数
45、据，另一种是函数依赖的数据。全独立的数据，另一种是函数依赖的数据。)()()|()|(XPHPHXPXHP2022年6月16日星期四65朴素贝叶斯分类n朴素贝叶斯分类的工作过程如下：朴素贝叶斯分类的工作过程如下：n(1)(1) 每个数据样本用一个每个数据样本用一个n n维特征向量维特征向量X X= = x x1 1，x x2 2，x xn n 表示，分别描述对表示，分别描述对n n个属性个属性A A1 1，A A2 2，A An n样本的样本的n n个个度量。度量。n(2) (2) 假定有假定有mm个类个类C C1 1，C C2 2，C Cmm，给定一个未知的数据给定一个未知的数据样本样本X
46、X（即没有类标号），分类器将预测即没有类标号），分类器将预测X X属于具有最高后属于具有最高后验概率（条件验概率（条件X X下）的类。也就是说，朴素贝叶斯分类将下）的类。也就是说，朴素贝叶斯分类将未知的样本分配给类未知的样本分配给类C Ci i（11i imm）当且仅当当且仅当P P( (C Ci i| |X X) ) P P( (C Cj j| |X X) )，对任意的对任意的j j=1=1，2 2，mm，j ji i。这样，最大化这样，最大化P P( (C Ci i| |X X) )。其其P P( (C Ci i| |X X) )最大的类最大的类C Ci i称为最大后验假定。根据贝称为最大
47、后验假定。根据贝叶斯定理叶斯定理)()()|()|(XPCPCXPXCPiii2022年6月16日星期四66朴素贝叶斯分类(续)n(3)(3) 由于由于P P( (X X) )对于所有类为对于所有类为常数常数，只需要，只需要P P( (X X| |C Ci i) )* *P P( (C Ci i) )最大最大即可。如果即可。如果C Ci i类的先验概率未知，则通常假定这些类是等类的先验概率未知，则通常假定这些类是等概率的，即概率的，即P P( (C C1 1)=)=P P( (C C2 2)=)=P P( (C Cmm) )，因此问题就转换为因此问题就转换为对对P P( (X X| |C Ci
48、 i) )的最大化（的最大化（P P( (X X| |C Ci i) )常被称为给定常被称为给定C Ci i时数据时数据X X的似的似然度，而使然度，而使P P( (X X| |C Ci i) )最大的假设最大的假设C Ci i称为称为最大似然假设最大似然假设）。否）。否则，需要最大化则，需要最大化P P( (X X| |C Ci i) )* *P P( (C Ci i) )。注意，类的先验概率可以注意，类的先验概率可以用用P(P(C Ci i)=)=s si i/ /s s计算，其中计算，其中s si i是类是类C Ci i中的训练样本数，而中的训练样本数，而s s是训是训练样本总数练样本总
49、数。n(4)(4) 给定具有许多属性的数据集，计算给定具有许多属性的数据集，计算P P( (X X| |C Ci i) )的开销可能的开销可能非常大。为降低计算非常大。为降低计算P P( (X X| |C Ci i) )的开销，可以做的开销，可以做类条件独立的类条件独立的朴素假定朴素假定。给定样本的类标号，假定属性值相互条件独立，。给定样本的类标号，假定属性值相互条件独立，即在属性间，不存在依赖关系。这样即在属性间，不存在依赖关系。这样 )|()|(1inkkiCxPCXP2022年6月16日星期四67朴素贝叶斯分类(续) 其中概率其中概率P P( (x x1 1| |C Ci i) )，P
50、P( (x x2 2| |C Ci i) )，P P( (x xn n| |C Ci i) )可以由训练样本估值。可以由训练样本估值。n如果如果A Ak k是离散属性，则是离散属性，则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是连续值属性，则通常假定该属性服从高斯分布。因而，是连续值属性，则通常假定该属性服从高斯分布。因而， 是高斯分布函数，
