第4章分类方法(new)-数据挖掘课件.ppt

《第4章分类方法(new)-数据挖掘课件.ppt》由会员分享，可在线阅读，更多相关《第4章分类方法(new)-数据挖掘课件.ppt（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、分类的基本概念与步骤 基于距离的分类算法 决策树分类方法 贝叶斯分类 规则归纳 与分类有关的问题 n分类是数据挖掘中重要的任务分类是数据挖掘中重要的任务 分类的目的是学会一个分类器（分类函数或模型），该分分类的目的是学会一个分类器（分类函数或模型），该分类器能把待分类的数据映射到给定的类别中。类器能把待分类的数据映射到给定的类别中。分类可用于预测。从利用历史数据记录中自动推导出对给分类可用于预测。从利用历史数据记录中自动推导出对给定数据的推广描述，从而能对未来数据进行类预测。定数据的推广描述，从而能对未来数据进行类预测。分类具有广泛的应用，例如医疗诊断、信用卡系统的信用分类具有广泛的应用，例如

2、医疗诊断、信用卡系统的信用分级、图像模式识别等。分级、图像模式识别等。分类器的构造依据的方法很广泛：分类器的构造依据的方法很广泛：统计方法：包括贝叶斯法和非参数法等。统计方法：包括贝叶斯法和非参数法等。机器学习方法：包括决策树法和规则归纳法。机器学习方法：包括决策树法和规则归纳法。神经网络方法。神经网络方法。其他，如粗糙集等（在前面绪论中也介绍了相关的情况）。其他，如粗糙集等（在前面绪论中也介绍了相关的情况）。分类的基本概念与步骤分类的基本概念与步骤n分类方法的类型分类方法的类型从使用的主要技术上看，可以把分类方法归结为从使用的主要技术上看，可以把分类方法归结为四种类型：四种类型：基于距离的分

3、类方法基于距离的分类方法决策树分类方法决策树分类方法贝叶斯分类方法贝叶斯分类方法规则归纳方法。规则归纳方法。本章将选择一些有代表性的方法和算法来介绍这本章将选择一些有代表性的方法和算法来介绍这四类分类方法。四类分类方法。n分分类问题类问题的描述的描述定定义义4-1给给定一个数据定一个数据库库D=t1，t2，tn和一和一组类组类C=C1，Cm，分，分类问题类问题是去确定一个映射是去确定一个映射f:DC，使，使得每个元得每个元组组ti被分配到一个被分配到一个类类中。一个中。一个类类Cj 包含映射到包含映射到该该类类中的所有元中的所有元组组，即，即Cj=ti|f(ti)=Cj，1in，而且，而且ti

4、 D。例如，把学生的百分制分数分成例如，把学生的百分制分数分成A A、B B、C C、D D、E E五类，五类，就是一个分类问题：就是一个分类问题：D是包含是包含百分制分数在内的学生信百分制分数在内的学生信息，息，C=A A、B B、C C、D D、E E。解决分类问题的关键是构造一个合适的解决分类问题的关键是构造一个合适的分类器分类器：从数据：从数据库到一组类别集的映射。一般地，这些类是被预先定义库到一组类别集的映射。一般地，这些类是被预先定义的、非交叠的。的、非交叠的。看个例子。给定一个顾客信用信息的数据库，可以根据顾看个例子。给定一个顾客信用信息的数据库，可以根据顾客的信誉度（优良或相当

5、好）来识别顾客。首相需要学习客的信誉度（优良或相当好）来识别顾客。首相需要学习分类规则，之后分析现有顾客数据学习得到的分类规则可分类规则，之后分析现有顾客数据学习得到的分类规则可以被用来预测新的或未来顾客的信誉度。以被用来预测新的或未来顾客的信誉度。nameageincome Credit_ratingSandyJonesBillleeCourtneyfoxSusanlakeClairephipsAndrebeau3030314040403140lowlowhighmedmedhighfairexcellentexcellentfairfairexcellent训练数据训练数据Ifage=“3

6、140”andincome=highThencredit_rating=excellent分类规则分类规则分类算法分类算法利用训练集进行学习利用训练集进行学习nameageincome Credit_ratingFrankJonesAnneYeeSylviaCrest40304130highhighlowfairexcellentfair测试数据测试数据分类规则分类规则新数据新数据JohnHenri 3041highexcellent评估分类规则评估分类规则分类分类评估分类规则：评估分类规则：用测试数据评估规则的准确率，如果准确率用测试数据评估规则的准确率，如果准确率可以接受，则规则可以用于新

7、数据的分类可以接受，则规则可以用于新数据的分类n基于距离的分类算法的思路基于距离的分类算法的思路定义定义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)，ClC，ClCj，其中其中sim(ti，Cj)被称为相似性。被称为相似性。在实际的计算

8、中往往用距离来表征，距离越近，相似性越大，距在实际的计算中往往用距离来表征，距离越近，相似性越大，距离越远，相似性越小。离越远，相似性越小。距离的计算方法有多种，最常用的是通过计算每个类的中心来完距离的计算方法有多种，最常用的是通过计算每个类的中心来完成。成。基于距离的分类算法基于距离的分类算法p基于距离的分类方法的直观解释基于距离的分类方法的直观解释基于距离的分类方法的直观解释基于距离的分类方法的直观解释例：例：有有A，B，C三个类；有三个类；有18个待分类的样例；通过计算每个类代表区个待分类的样例；通过计算每个类代表区域的中心来确定每个类的分类中心域的中心来确定每个类的分类中心CA，CB，

9、CC；通过计算待分类的样；通过计算待分类的样例到每个分类中心的距离就可以找出最相似的类。例到每个分类中心的距离就可以找出最相似的类。（a）类定义）类定义（b）待分类样例）待分类样例（c）分类结果）分类结果nk-近邻分类算法近邻分类算法k-近邻分类算法（近邻分类算法（kNearestNeighbors，简称，简称kNN）通过）通过计算每个训练数据到待分类元组的距离，取与待分类元组计算每个训练数据到待分类元组的距离，取与待分类元组距离最近的距离最近的k个训练数据，个训练数据，k中哪个类别训练数据占多数，中哪个类别训练数据占多数，则待分类元组就属于哪个类别。则待分类元组就属于哪个类别。算法算法4-2

10、k-近邻分类算法输入：训练数据T；近邻数目k；待分类的元组t。输出：输出类别c。（1）N=；（2）FOReachd TDOBEGIN（3）IF|N|kTHEN（4）N=Nd；（5）ELSE（6）IFu Nsuchthatsim(t，u)sim(t，d)THENBEGIN（7）N=N-u；（8）N=Nd；（9）END（10）END（11）c=classtowhichthemostuN.pkNN的例子的例子对第对第8个记录个记录d=，得到，得到N=、和和。对第对第9和和10个记录，没变化。个记录，没变化。对第对第11个记录个记录d=，得到，得到N=、和和。对第对第12到到14个记录，没变化。个记录

11、，没变化。对第对第15个记录个记录d=，得到，得到N=、和和。最后的输出元组是最后的输出元组是姓名性别身高(米)类别Kristina女1.6矮Dave男1.7矮Kathy女1.6矮Wynette女1.75中等Stephanie女1.7矮在这五项中，四个属于矮个、一个属于中等。最终在这五项中，四个属于矮个、一个属于中等。最终k kNNNN方法认为方法认为PatPat为矮个。为矮个。决策树分类的特点决策树分类的特点决策树分类方法采用自顶向下的递归方式，在决策树的内决策树分类方法采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较并根据不同的属性值判断从该结部结点进行属性值的比较并根据不同的属

12、性值判断从该结点向下的分枝，在决策树的叶结点得到结论。所以从决策点向下的分枝，在决策树的叶结点得到结论。所以从决策树的根到叶结点的一条路径就对应着一条合取规则，整棵树的根到叶结点的一条路径就对应着一条合取规则，整棵决策树就对应着一组析取表达式规则。决策树就对应着一组析取表达式规则。基于决策树的分类算法的一个最大的优点就是它在学习过基于决策树的分类算法的一个最大的优点就是它在学习过程中不需要用户了解很多背景知识（这同时也是它的最大程中不需要用户了解很多背景知识（这同时也是它的最大的缺点），只要训练例子能够用属性的缺点），只要训练例子能够用属性-结论式表示出来，结论式表示出来，就能使用该算法来学习

13、。就能使用该算法来学习。决策树分类模型的建立通常分为两个步骤：决策树分类模型的建立通常分为两个步骤：决策树生成决策树生成决策树修剪。决策树修剪。n决策树生成算法决策树生成算法决策树生成算法决策树生成算法算法Generate_decision_tree(samples,attribute_list)/*决策树生成算法*/输入：训练样本samples，由离散值属性表示；候选属性的集合attribute_list。输出：一棵决策树。（1）创建结点N；（2）IFsamples都在同一个类CTHEN返回N作为叶结点，以类C标记；（3）IFattribute_list为空THEN返回N作为叶结点，标记为s

14、amples中最普通的类；/多数表决（4）选择attribute_list中具有最高信息增益的属性test_attribute；（5）标记结点N为test_attribute；（6）FOReachtest_attribute中的已知值ai由结点N长出一个条件为test_attribute=ai的分枝；（7）设si是samples中test_attribute=ai的样本的集合；/一个划分（8）IFsi为空THEN加上一个树叶，标记为samples中最普通的类；（9）ELSE加上一个由Generate_decision_tree(si，attribute_list-test_attribute)

15、返回的结点；n 决策树修剪算法决策树修剪算法基本的决策树构造算法没有考虑噪声，因此生成的基本的决策树构造算法没有考虑噪声，因此生成的决策树完全与训练例子拟合。在有噪声情况下，将决策树完全与训练例子拟合。在有噪声情况下，将导致过分拟合导致过分拟合,即对训练数据的完全拟合反而使对现即对训练数据的完全拟合反而使对现实数据的分类预测性能下降。实数据的分类预测性能下降。现实世界的数据一般不可能是完美的，可能某些属现实世界的数据一般不可能是完美的，可能某些属性字段上缺值、数据不完整、不准确、含有噪声甚性字段上缺值、数据不完整、不准确、含有噪声甚至是错误的。至是错误的。剪枝是一种克服噪声的基本技术，同时它也

16、能使树剪枝是一种克服噪声的基本技术，同时它也能使树得到简化而变得更容易理解。得到简化而变得更容易理解。有两种基本的剪枝策略：有两种基本的剪枝策略：预先剪枝：在生成树的同时决定是继续对不纯的训练子集进行划分还预先剪枝：在生成树的同时决定是继续对不纯的训练子集进行划分还是停机。是停机。后剪枝：是一种拟合后剪枝：是一种拟合+化简（化简（fitting-and-simplifying）的两阶段方法。）的两阶段方法。step1:生成与训练数据完全拟合的一棵决策树生成与训练数据完全拟合的一棵决策树;step2:从树的叶子开始剪枝，逐步向根的方向剪。剪枝时要用到一个从树的叶子开始剪枝，逐步向根的方向剪。剪枝

17、时要用到一个测试数据集合（测试数据集合（TuningSet或或AdjustingSet）。如果存在某个叶子剪）。如果存在某个叶子剪去后能使得在测试集上的准确度或其他测度不降低（不变得更坏），去后能使得在测试集上的准确度或其他测度不降低（不变得更坏），则剪去该叶子；否则停机。则剪去该叶子；否则停机。理论上讲，后剪枝好于预先剪枝，但计算复杂度大。理论上讲，后剪枝好于预先剪枝，但计算复杂度大。剪枝过程中一般要涉及一些统计参数或阈值（如停机阈值）。剪枝过程中一般要涉及一些统计参数或阈值（如停机阈值）。要防止过分剪枝（要防止过分剪枝（Over-Pruning）带来的副作用。）带来的副作用。nID3算法算

18、法pID3是是J.R.Quinlan提出的一个著名决策树生成方法：提出的一个著名决策树生成方法：决策树中每一个非叶结点对应着一个非类别属性，决策树中每一个非叶结点对应着一个非类别属性，树枝代表这个属性的值。一个叶结点代表从树根树枝代表这个属性的值。一个叶结点代表从树根到叶结点之间的路径对应的记录所属的类别属性到叶结点之间的路径对应的记录所属的类别属性值。值。每一个非叶结点都将与属性中具有最大信息量的每一个非叶结点都将与属性中具有最大信息量的非类别属性相关联。非类别属性相关联。采用信息增益来选择能够最好地将样本分类的属采用信息增益来选择能够最好地将样本分类的属性。性。n信息增益的计算信息增益的计

19、算 信息增益基于信息论中熵的概念。信息增益基于信息论中熵的概念。ID3ID3总是选择具有最高总是选择具有最高信息增益的属性作为当前结点的测试属性。该属性使得对结信息增益的属性作为当前结点的测试属性。该属性使得对结果划分的样本分类所需的信息量最小。这种信息论方法使得果划分的样本分类所需的信息量最小。这种信息论方法使得对一个对象分类所需的期望测试数目达到最小对一个对象分类所需的期望测试数目达到最小,并尽量确保找并尽量确保找到一棵简单的数来刻画相关的信息。到一棵简单的数来刻画相关的信息。设设S是是s个数据样本的集合，假定类标号属性具有个数据样本的集合，假定类标号属性具有m个不个不同的值同的值,定义定

20、义m个不同类个不同类Ci（i=1，2，m），设），设si是是Ci类中类中的样本数。对给定的样本的样本数。对给定的样本S所期望的信息值由下式给出：所期望的信息值由下式给出：其中其中pi是任意样本属于是任意样本属于Ci的概率：的概率：si/s。设属性设属性A具有具有v个不同值个不同值a1,a2,av，可以用属性，可以用属性A将样本将样本S划分为划分为v个子集个子集S1,S2,Sv，其中：，其中：Sj包含包含S中这样一些中这样一些样本，它们在样本，它们在A上具有上具有aj的值。如果的值。如果A作为测试属性，则这作为测试属性，则这些子集对应有包含集合些子集对应有包含集合S的结点生长出来的分支。的结点生

21、长出来的分支。设设sij是是Sj中中Ci类的样本数，则由类的样本数，则由A划分成子集的熵由下式给划分成子集的熵由下式给出：出：其中，期望信息：其中，期望信息：ID3算法例子样本数据样本数据warm_bloodedfeathersfurswimslays_eggs123456101111101100000001010010111100例子中有例子中有6个样本个样本,5个属性个属性,每个属性取值为每个属性取值为0或或1。假设目标分类属性是假设目标分类属性是lays_eggs，有，有4个样本取值为个样本取值为1，2个样本取个样本取值为值为0。为计算每个属性的信息增益，首先计算样本按为计算每个属性的信

22、息增益，首先计算样本按lays_eggslays_eggs分类所需的期望分类所需的期望信息：信息：类似的，类似的，Gain(feathers)=0.459；Gain(fur)=0.316；Gain(swims)=0.044。这种划分的信息增益是：这种划分的信息增益是：接下来计算每个属性的熵。观察接下来计算每个属性的熵。观察warm_bloodedwarm_blooded的每个样本值的分布：的每个样本值的分布：当当warm_blooded=1warm_blooded=1时，有时，有3 3个个lays_eggslays_eggs =1=1，2 2个个lays_eggslays_eggs =0=0，

23、即：，即：当当warm_blooded=0warm_blooded=0时，有时，有1 1个个lays_eggslays_eggs =1=1，0 0个个lays_eggslays_eggs =0=0，即：，即：因此，如果样本按因此，如果样本按warm_blooded划分，对一个给定的样本分类对应划分，对一个给定的样本分类对应的熵为：的熵为：由于由于feathers在在属性中具有最高的信息增益，所以它首先属性中具有最高的信息增益，所以它首先被选作测试属性。并以此创建一个结点，数据集被划分成被选作测试属性。并以此创建一个结点，数据集被划分成两个子集。两个子集。100110011001 Warm_bl

24、oodedfurswimslay_eggsT1=0Feathers？001110101100 Warm_bloodedfurswimslay_eggsT2=1ID3算法的性能分析算法的性能分析ID3算法的假设空间包含所有的决策树，它是关于现有属性的有限离算法的假设空间包含所有的决策树，它是关于现有属性的有限离散值函数的一个完整空间。所以散值函数的一个完整空间。所以ID3算法避免了搜索不完整假设空间算法避免了搜索不完整假设空间的一个主要风险：假设空间可能不包含目标函数。的一个主要风险：假设空间可能不包含目标函数。ID3算法在搜索的每一步都使用当前的所有训练样例，大大降低了对算法在搜索的每一步都使

25、用当前的所有训练样例，大大降低了对个别训练样例错误的敏感性。因此，通过修改终止准则，可以容易地个别训练样例错误的敏感性。因此，通过修改终止准则，可以容易地扩展到处理含有噪声的训练数据。扩展到处理含有噪声的训练数据。ID3算法在搜索过程中不进行回溯。所以，它易受无回溯的爬山搜索算法在搜索过程中不进行回溯。所以，它易受无回溯的爬山搜索中的常见风险影响：收敛到局部最优而不是全局最优。中的常见风险影响：收敛到局部最优而不是全局最优。ID3算法只能处理离散值的属性。算法只能处理离散值的属性。信息增益度量存在一个内在偏置，它偏袒具有较多值的属性。例如，信息增益度量存在一个内在偏置，它偏袒具有较多值的属性。

26、例如，如果有一个属性为日期，那么将有大量取值，这个属性可能会有非常如果有一个属性为日期，那么将有大量取值，这个属性可能会有非常高的信息增益。假如它被选作树的根结点的决策属性则可能形成一颗高的信息增益。假如它被选作树的根结点的决策属性则可能形成一颗非常宽的树，这棵树可以理想地分类训练数据，但是对于测试数据的非常宽的树，这棵树可以理想地分类训练数据，但是对于测试数据的分类性能可能会相当差。分类性能可能会相当差。ID3算法增长树的每一个分支的深度，直到恰好能对训练样例完美地算法增长树的每一个分支的深度，直到恰好能对训练样例完美地分类。当数据中有噪声或训练样例的数量太少时，产生的树会过渡拟分类。当数据

27、中有噪声或训练样例的数量太少时，产生的树会过渡拟合训练样例。合训练样例。C4.5算法对算法对ID3的主要改进的主要改进C4.5算法是从算法是从ID3算法演变而来，除了拥有算法演变而来，除了拥有ID3算法算法的功能外，的功能外，C4.5算法引入了新的方法和增加了新的算法引入了新的方法和增加了新的功能：功能：用信息增益比例的概念；用信息增益比例的概念；合并具有连续属性的值；合并具有连续属性的值；可以处理具有缺少属性值的训练样本；可以处理具有缺少属性值的训练样本；通过使用不同的修剪技术以避免树的过度拟合；通过使用不同的修剪技术以避免树的过度拟合；K交叉验证；交叉验证；规则的产生方式等。规则的产生方式

28、等。p合并具有连续值的属性合并具有连续值的属性，对于连续属性值，对于连续属性值，C4.5其处理过程如下：其处理过程如下：根据属性的值，对数据集排序；根据属性的值，对数据集排序；用不同的阈值将数据集动态的进行划分；用不同的阈值将数据集动态的进行划分；当输出改变时确定一个阈值；当输出改变时确定一个阈值；取两个实际值中的中点作为一个阈值；取两个实际值中的中点作为一个阈值；取两个划分，所有样本都在这两个划分中；取两个划分，所有样本都在这两个划分中；得到所有可能的阈值、增益及增益比；得到所有可能的阈值、增益及增益比；在每一个属性会变为取两个取值，即小于阈值或大于在每一个属性会变为取两个取值，即小于阈值或

29、大于等于阈值。等于阈值。简单地说，针对属性有连续数值的情况，则在训简单地说，针对属性有连续数值的情况，则在训练集中可以按升序方式排列。如果属性练集中可以按升序方式排列。如果属性A共有共有n种种取值，则对每个取值取值，则对每个取值vj（j=1，2，n），将所），将所有记录进行划分：一部分小于有记录进行划分：一部分小于vj；一部分则大于或；一部分则大于或等于等于vj。针对每个。针对每个vj计算划分对应的增益比率，选计算划分对应的增益比率，选择增益最大的划分对属性择增益最大的划分对属性A进行离散化进行离散化。p处理含有未知属性值的训练样本处理含有未知属性值的训练样本处理含有未知属性值的训练样本处理含

30、有未知属性值的训练样本 C4.5处理的样本中可以含有未知属性值，其处理方法是处理的样本中可以含有未知属性值，其处理方法是用最常用的值替代或者是将最常用的值分在同一类中。用最常用的值替代或者是将最常用的值分在同一类中。具体采用概率的方法，依据属性已知的值，对属性和每具体采用概率的方法，依据属性已知的值，对属性和每一个值赋予一个概率，取得这些概率，取得这些概率依一个值赋予一个概率，取得这些概率，取得这些概率依赖于该属性已知的值。赖于该属性已知的值。p规则的产生规则的产生 一旦树被建立，就可以把树转换成一旦树被建立，就可以把树转换成if-then规则。规则存规则。规则存储于一个二维数组中，每一行代表

31、树中的一个规则，即储于一个二维数组中，每一行代表树中的一个规则，即从根到叶之间的一个路径。表中的每列存放着树中的结从根到叶之间的一个路径。表中的每列存放着树中的结点。点。C4.5C4.5算法例子算法例子算法例子算法例子样本数据样本数据OutlookTemperatureHumidityWindPlayTennisSunnyHot85falseNoSunnyHot90trueNoOvercastHot78falseYesRainMild96falseYesRainCool80falseYesRainCool70trueNoOvercastCool65trueYesSunnyMild95false

32、NoSunnyCool70falseYesRainMild80falseYesSunnyMild70trueYesOvercastMild90trueYesOvercastHot75falseYesRainMild80trueNolOutlook(Outlook(离散属性离散属性)lTemperature(Temperature(离散属性离散属性)lHumidity(Humidity(连续属性连续属性)lWind(Wind(离散属性离散属性)lPlayTennisPlayTennis(类别属性类别属性)（1）首先对首先对Humidity进行属性离散化，针对上面的训练集合，通过检进行属性离散化，

33、针对上面的训练集合，通过检测每个划分而确定最好的划分在测每个划分而确定最好的划分在75处，则这个属性的范围就变为处，则这个属性的范围就变为（75）。（2）计算目标属性）计算目标属性Humidity分类的期望信息：分类的期望信息：接下来计算属性接下来计算属性Outlook的的SplitI值值:对于对于Outlook=Sunny,Outlook=Sunny,有有对于对于Outlook=Sunny,Outlook=Sunny,有有对于对于Outlook=Sunny,Outlook=Sunny,有有对于决策属性对于决策属性PlayTennisPlayTennis来说来说,计算计算OutlookOutl

34、ook属性每个分布的期望信息属性每个分布的期望信息 选取最大的选取最大的GainRatio，根据，根据Outlook的取值，可以得到三的取值，可以得到三个分支。再扩展各分枝节点，得到最终的决策树。个分支。再扩展各分枝节点，得到最终的决策树。因此因此,可得到可得到OutlookOutlook属性的熵属性的熵:对应的信息增益为对应的信息增益为:最后得到信息增益比例为最后得到信息增益比例为:0.0483Humidity)GainRatio(=0.0248e)TemperaturGainRatio(=；049.0)(=；windyGainRatio同理同理,可计算出可计算出TemperatureHum

35、idityWindPlayTennisHot75falseNoHot75trueNoMild75falseNoCool75falseYesMild75trueYesTemperatureHumidityWindPlayTennisMild75falseYesCool75falseYesCool75trueNoMild75falseYesMild75trueNoTemperatureHumidityWindPlayTennisHot75falseYesCool75trueYesMild75trueYesHot75falseYes=RainOutlook？=Sunny=OvercastT1T3T2

36、对于第一棵子树，对于第一棵子树，1Humidity)GainRatio(=0.244e)TemperaturGainRatio(=；0206.0)(=；windyGainRatio，选择，选择HumidityHumidity作为决策属性，得到两个叶结点。作为决策属性，得到两个叶结点。对于第二棵子树，所有样本都属于同一类（对于第二棵子树，所有样本都属于同一类（PlayTennis=YesPlayTennis=Yes），），直接得到叶结点直接得到叶结点对于第三棵子树，对于第三棵子树，0.446 Humidity)GainRatio(=0.0206e)TemperaturGainRatio(=；.1

37、)(=；windyGainRatio，选择，选择WindWind作为决策属性，得到两个叶结点。作为决策属性，得到两个叶结点。=RainOutlook？=Sunny=OvercastT1T3T2YesYesYesYesNoNoWind？=true=falseYesYesNoNoHumidity？7575最终生成的决策树最终生成的决策树:贝叶斯方法提供了一种概率手段贝叶斯方法提供了一种概率手段,基于如下的假定基于如下的假定:待考察的量遵循某概率分布待考察的量遵循某概率分布,且可根据这些概率及且可根据这些概率及已观察到的数据进行推理已观察到的数据进行推理,以作出最优的决策。这以作出最优的决策。这个分

38、析过程开始是先给出一个待分析数据集的概个分析过程开始是先给出一个待分析数据集的概率分布。因为这个概率分布是没有考虑任何数据率分布。因为这个概率分布是没有考虑任何数据而给出的，所以称而给出的，所以称先验分布。这个新的数据集将先验分布。这个新的数据集将先验分布修正后得到后验分布。先验分布修正后得到后验分布。贝叶斯理论提供贝叶斯理论提供了一种计算假设概率的方法了一种计算假设概率的方法,基于假设的先验概率基于假设的先验概率,给定假设下观察到不同数据的概率以及观察到的给定假设下观察到不同数据的概率以及观察到的数据本身先验概率和后验概率。数据本身先验概率和后验概率。贝叶斯分类贝叶斯分类定定义义设设X是是类

39、类标标号号未未知知的的数数据据样样本本。设设H为为某某种种假假定定，如如数数据据样样本本X属属于于某某特特定定的的类类C。对对于于分分类类问问题题，我我们们希希望望确确定定P(H|X)，即即给给定定观观测测数数据据样样本本X，假假定定H成成立立的的概概率率。贝贝叶叶斯斯定定理理给给出出了了如如下下计计算算P(H|X)的简单有效的方法的简单有效的方法:P(H)是是先先验验概概率率，或或称称H的的先先验验概概率率。P(X|H)代代表表假假设设H成成立立的的情情况况下下，观观察察到到X的的概概率率。P(H|X)是是后验概率后验概率，或称条件或称条件X下下H的后验概率。的后验概率。例例如如，假假定定数

40、数据据样样本本域域由由水水果果组组成成，用用它它们们的的颜颜色色和和形形状状来来描描述述。假假定定X表表示示红红色色和和圆圆的的，H表表示示假假定定X是是苹苹果果，则则P(H|X)反反映映当当我我们们看看到到X是是红红色色并并是是圆圆的的时时，我我们们对对X是是苹果的确信程度。苹果的确信程度。贝贝叶叶斯斯分分类类器器对对两两种种数数据据具具有有较较好好的的分分类类效效果果：一一种种是是完完全全独独立立的的数数据据，另另一一种种是是函函数数依赖的数据。依赖的数据。朴素贝叶斯分类朴素贝叶斯分类朴素贝叶斯分类的工作过程如下：朴素贝叶斯分类的工作过程如下：(1)假假设设有有一一组组m个个元元素素的的样

41、样本本S=S1,S2,Sm（训训练练样样本本集集），其其中中每每个个数数据据样样本本Si用用一一个个n维维特特征征向向量量X=x1,x2,xn表示，分别与样本属性表示，分别与样本属性A1,A2,An相对应。相对应。(2)假假定定有有k个个类类C1,C2,Ck，每每个个样样本本属属于于其其中中一一个个类类。给给定定一一个个数数据据样样本本X（它它的的类类是是未未知知的的），可可以以用用最最高高的的后后验验概概率率（条条件件X下下）来来预预测测X的的类类。也也就就是是说说，朴朴素素贝贝叶叶斯斯分分类类将将未未知知的的样样本本分分配配给给类类Ci（1ik）当当且且仅仅当当P(Ci|X)P(Cj|X)

42、，对对任任意意的的j=1，2，k，ji。这这样样，最最大大化化P(Ci|X)。其其P(Ci|X)最最大大的的类类Ci称称为为最最大大后后验验假假定定。根根据据贝贝叶斯定理叶斯定理(3)由由于于P(X)对对于于所所有有类类为为常常数数，只只需需要要P(X|Ci)*P(Ci)最最大大即即可可。如如果果Ci类类的的先先验验概概率率未未知知，则则通通常常假假定定这这些些类类是是等等概概率率的的，即即P(C1)=P(C2)=P(Ck)，因因此此问问题题就就转转换换为为对对P(X|Ci)的的最最大大化化（P(X|Ci)常常被被称称为为给给定定Ci时时数数据据X的的似似然然度度，而而使使P(X|Ci)最最大

43、大的的假假设设Ci称称为为最最大大似似然然假假设设）。否否则则，需需要要最最大大化化P(X|Ci)*P(Ci)。注注意意，类类的的先先验验概概率率可可以以用用P(Ci)=si/m计计算算，其其中中si是是类类Ci中中的的训训练练样样本本数数，而而m是训练样本总数是训练样本总数。(4)给给定定具具有有许许多多属属性性的的数数据据集集，计计算算P(X|Ci)的的开开销销可可能能非非常常大大。为为降降低低计计算算P(X|Ci)的的开开销销，可可以以做做类类条条件件独独立立的的朴朴素素假假定定（零零假假设设），假假定定样样本本属属性性值值之之间间条条件件独独立立，即即在在属属性性间间，不不存存在在依依

44、赖赖关关系系。利利用用这这个个假假定定，可可以以用用下下式式来来计计算算P(X|Ci)其中其中xt是样本是样本X的属性值，概率的属性值，概率P(xt|Ci)可由训练样本集来可由训练样本集来估算。估算。(5)对对未未知知样样本本X分分类类，也也就就是是对对每每个个类类Ci，计计算算P(X|Ci)*P(Ci)。样样本本X被被指指派派到到类类Ci，当当且且仅仅当当P(Ci|X)P(Cj|X)，1jm，ji，换换言言之，之，X被指派到其被指派到其P(X|Ci)*P(Ci)最大的类。最大的类。例：已知例：已知7个四元样本训练数据集个四元样本训练数据集样本样本属性属性1（A1）属性属性2（A2）属性属性3

45、（A3）类类（C）11211200113212241212501216222271031预测新样本预测新样本X=1，2，2，C=？；对于每个样本，；对于每个样本，A1，A2，A3是输入元，是输入元，C是输出分类是输出分类在在本本例例中中，仅仅有有两两个个类类，C=1或或C=2，故故只只需需找找出出P(X|Ci)*P(Ci)（i=1，2）中的最大值。）中的最大值。先计算每个类的先验概率先计算每个类的先验概率P(Ci):P(C=1)=4/7=0.5714;P(C=2)=3/7=0.4286用训练集计算所给新样本用训练集计算所给新样本X=1，2，2，C=？的每个属性值的每个属性值的条件概率的条件概率

46、P(Xt|Ci):P(A1=1|C=1)=2/4=0.50;P(A1=1|C=2)=1/3=0.33P(A2=2|C=1)=1/4=0.25;P(A2=2|C=2)=2/3=0.66P(A3=2|C=1)=1/4=0.25;P(A3=2|C=2)=2/3=0.66在零假设下在零假设下,条件概率条件概率P(X|Ci)为为:P(X|C=1)=P(A1=1|C=1)*P(A2=2|C=1)*P(A3=2|C=1)=0.03125P(X|C=2)=P(A1=1|C=2)*P(A2=2|C=2)*P(A3=2|C=2)=0.14375最后最后,用相应的条件概率用相应的条件概率P(X|Ci)乘以先验概率乘

47、以先验概率P(Ci):P(C1|X)P(X|C=1)*P(C=1)=0.03125*0.5714=0.0179P(C2|X)P(X|C=2)*P(C=2)=0.14375*0.4286=0.0616最大值为最大值为P(C2|X)=0.0616,于是预测新样本于是预测新样本X=1，2，2，C=？属于类属于类C=2。朴素贝叶斯分类举例Ageincomestudentcredit_ratingbuy_computer1=30HighNoFairNo240MediumNoFairYes540LowYesFairYes640LowYesExcellentNo73140LowYesExcellentYes

48、8=30MediumNoFairNo940MediumYesFairYes11=30MediumYesExcellentYes123140MediumNoExcellentYes133140HighYesFairYes14=30MediumNoExcellentNo数据样本用属性数据样本用属性age，income，student和和credit_rating描述。描述。类标号属性类标号属性buys_computer具有两个不同值（即具有两个不同值（即yes，no）。）。设设C1对应于类对应于类yes，而而C2对应于类对应于类“no”。希望分类的未知样本为希望分类的未知样本为:X=(=30，me

49、dium，yes，fair，C=?)。朴素贝叶斯分类举例(1)需要最大化需要最大化P(X|Ci)*P(Ci)，i=1，2。每个类的先验概率每个类的先验概率P(Ci)可以根据训练样本计算：可以根据训练样本计算：P(buys_computer=”yes”)=9/14=0.643，P(buys_computer=”no”)=5/14=0.357。(2)为计算为计算P(X|Ci)，i=1，2，我们计算下面的条件概率：我们计算下面的条件概率：P(age=30|buys_computer=”yes”)=2/9=0.222，P(age=30”|buys_computer=”no”)=3/5=0.600，P(

50、income=”medium”|buys_computer=”yes”)=4/9=0.444，P(income=”medium”|buys_computer=”no”)=2/5=0.400，P(student=”yes”|buys_computer=”yes”)=6/9=0.677，P(student=”yes”|buys_computer=”no”)=1/5=0.200，P(credit_rating=”fair”|buys_computer=”yes”)=6/9=0.667P(credit_rating=”fair”|buys_computer=”no”)=2/5=0.400。(3)假设条