《数据挖掘基础及其应用》课件第4章

第4章分类I:概念与决策树算法4.1引言4.2决策树4.3决策树原理与构建4.4补充算法4.5过拟合/欠拟合4.6分类准确性评估本章小结

4.1引言

4.1.1分类的定义简单地说,分类(CategorizationorClassification)就是按照某种标准给对象贴标签(Label),再根据标签进行区分归类,而聚类是指事先没有“标签”而通过某种成团分析找出事物之间存在聚集性原因的过程。

这两者的区别是:分类是事先定义好类别,且类别数不变,分类器需要由人工标注的训练样本学习得到,属于有指导学习范畴;聚类则没有事先预定的类别,类别数不确定,分类器不需要人工标注和预先训练,类别在聚类过程中自动生成。分类适合类别或分类体系已经确定的场合,如按照国图分类法分类图书;聚类则适合不存在分类体系、类别数不确定的场合,一般作为某些应用的前端,如多文档文摘、搜索引擎结果后聚类(元搜索)等。

分类的目的是学习一个分类函数或分类模型(也常常称作分类器),该模型能把数据库中的数据项映射到给定类别中的某一个类中。要构造分类器,需要有一个训练样本数据集

作为输入。训练集由一组数据库记录或元组构成,每个元组是一个由有关字段(又称属性或特征)值组成的特征向量。

定义4.1通过对训练集(已知类别属性的数据)进行学习构建一个函数,利用这个函数可以尽可能准确地对测试集(未知类别属性的数据)数据对象进行预测,把这样的一个过程称为分类。分类的基本流程如图4-1所示,包含输入训练数据、分类模型的训练、输出类别信息三部分。图4-1分类的基本流程

分类问题的目标是构建分类器或分类函数;分类问题的三大要素是训练集、测试集、模型。训练集与测试集的区别:训练集数据对象的类别属性值已知,而测试集数据对象的

类别属性未知。

分类模型根据其应用目的不同,可分为描述性模型与预测性模型。描述性模型通常作为解释性工具,用于区分不同类中的对象。

具体来说,分类技术(分类)是一种根据输入数据建立分类模型的系统方法,包括学习过程、模型构建、模型测试三个关键的步骤,其中要求所学习的模型能够很好地反映输入数

据,同时也要对测试集数据进行准确的预测。图4-2展示的是一个完整的分类算法流程。图4-2典型的分类算法流程

4.1.2分类的应用

分类是一种应用非常广泛的数据挖掘技术,应用的例子也很多。例如,根据信用卡支付历史记录,来判断具备哪些特征的用户往往具有良好的信用;根据某种病症的诊断记录,来分析哪些药物组合可以带来良好的治疗效果。这些过程的一个共同特点是:根据数据的某些属性,来估计一个特定属性的值。

例如在信用分析案例中,根据用户的“年龄”“性别”“收入水平”“职业”等属性的值,来估计该用户“信用度”属性的值应该取“好”还是“差”。在这个例子中,所研究的属性“信用度”是一个离散属性,它的取值是一个类别值,这种问题在数据挖掘中被称为分类。还有一种问题,例如根据股市交易的历史数据估计下一个交易日的大盘指数,这里所研究的属性“大盘指数”是一个连续属性,它的取值是一个实数,这种问题在数据挖掘中被称为预测。

4.1.3分类算法

不同的应用背景,所获取的数据类型与任务不同,分类算法就有不同的分组。可通过不同层次对分类算法进行分组。按照机器学习的类型,将分类算法分成有监督学习的分类与无监督学习的分类;按照类别属性是连续还是离散取值,分类算法可分为分类器算法与回归分析;按照类别属性的取值多少,分为二分类算法或多分类算法等。典型的分类算法包括决策树、神经网络、SVM、贝叶斯、KNN、深度学习,它们各自的优点和缺点如表4-1所示。

4.2决策树

决策树(DecisionTree)是一类常见的分类方法,其目的是通过训练集获取一个分类模型用以对新示例进行分类。分类任务可以通过一系列的问答方式进行,如“当前样本属于正类吗?”通过答案对分类的走向进行“决策”或“判定”。顾名思义,决策树是基于树结构进行决策的,这恰恰是人类面临决策问题时一种自然的处理机制。例如,校园中小猫和小狗的匹配问题,如图4-3所示。图4-3动物匹配问题的决策树

决策树分类算法包含两大关键技术问题:

①决策树定义与工作流程;

②决策树构建原理。

决策树又称为判定树,是应用于分类的一种树结构,其每个内部节点代表对某一属性的一次测试,每条边代表一个针对测试的判断,叶节点代表最终的分类结果。给定一棵决

策树,决策过程需要从树的根节点出发,将待测数据与决策树中的特征节点进行比较,并按照比较结果选择下一个比较分支,直到叶节点成为最终的决策结果。

定义4.2决策树是一种树形结构的分类器,由节点和有向边构成,节点有内部节点和叶节点,内部节点代表一个特征或者属性判定条件,叶节点代表分类结果。

节点是一棵决策树的主体。其中,没有父节点的节点称为根节点,如图4-4中的节点“有房”;没有子节点的节点称为叶节点。从根节点到每个叶节点的路径对应了一个判定测

试序列。决策树学习的目的是产生一棵泛化能力强,即处理未见示例能力强的决策树,其基本流程遵循简单且直观的“分而治之”(Divide-and-Conquer)策略,如算法4.1所示。

显然,决策树的生成是一个递归过程。在决策树基本算法中,有三种情形会导致递归返回:①当前节点包含的样本全属于同一类别,无须划分;②当前属性集为空,或是所有样本在所有属性上取值相同,无须划分;③当前节点包含的样本集合为空,不能划分。在第②种情形下,我们把当前节点标记为叶节点,并将其类别设定为该节点所包含样本最多的类别;在第③种情形下,同样把当前节点标记为叶节点,但将其类别设定为其父节点所含样本最多的类别。注意这两种情形的处理实质不同:情形②是利用当前节点的后验分布,而情形③则是把父节点的样本分布作为当前节点的先验分布。

问题1:决策树的关键词是什么?

决策树三大要素包括:

•树状结构;

•非叶节点代表属性;

•叶节点代表类别。

问题2:决策树预测的关键是什么?

第二个关键问题是:给定决策树,如何对测试集中的数据对象进行预测,并为人们提供决策依据。决策树可以用来回答是和否问题,通过树形结构将各种情况组合都表示出来,每个分支表示一次选择(选择是还是否),直到所有选择都进行完毕,最终给出正确答案。

定义4.3决策树预测是指沿从根节点到叶节点的路径进行查找,即从根节点出发,根据属性取值寻找下一个节点,并重复上述过程,直到当前节点为叶节点。叶节点对应的值即为该数据对象的属性类别,如图4-4所示。图4-4

决策树预测过程示意图

由图4-4可以看出,决策树预测通过三个步骤完成:

①从根节点出发;

②根据根节点属性值进入下一个非叶节点;

③进入叶节点,叶节点中的值就是该数据对象的类别(即最终决策)。

4.3决策树原理与构建

4.3.1算法原理通过4.2节决策树的定义和工作流程可知,要构建决策树,需要解决三方面的问题:①如何选择特征;②如何对特征进行分支;③决策树修剪。

构建决策树的难点如下:

(1)给定训练数据集,如何来选择特征作为根节点?如图4-5所示,如何解决特征重要性刻画问题和什么是特征的重要性两个问题。图4-5决策树构建难点之一:特征选择困难

(2)给定特征,如何判断分支和分支数?

一旦上述两个难点问题得到解决,就可以利用递归方式构建决策树。通过将训练记录相继划分成纯度更高的子集,以递归方式建立决策树,如图4-6所示。图4-6基于图4-5的训练数据,匈牙利算法流程示意图

问题3:对于一个完整的决策树算法,需要解决的问题是什么?

•如何选择特征?

•特征如何分支?

•最佳分支如何获取?

•算法如何终

4.3.2分支原则

假设特征已经选定(后续讨论),该如何解决特征分支问题?如何合理地对已选择的特征进行分支需要考虑两方面的因素,包括特征属性取值、多分类/二分类,具体内容如图4-7所示。图4-7特征分支分类

1.标量特征分支问题

标量数据只有不同特征之间的区别,无大小。给定车型特征,其取值为标量,例如,车型(Cartype)特征包括豪华型(Luxury)、家用型(Family)、运动型(Sports)。

由于标量的取值为离散的,所以可采用不同的值作为一个分支。车型特征可分为三个分支,如图4-8所示,其中每种车型为一个分支。该情况下,多分带来的优点是:①简单,易于实现;②可解释性强。但多分同样也有一定的缺点:当标量取值过多时,会导致子节点过多;特征的取值数过多时,分类的准确性极低。图4-8车型特征的三分支情况

为了克服该缺陷,可以采用二分情况,如图4-9所示。但车型特征的二分支情况存在一些缺点:当特征的取值过多时,组合模式呈指数级增长。图4-9车型特征的二分支情况

2.序数特征分支问题

序数数据的特征既有大小,也有顺序。给定车尺寸特征,其取值为序数数据。例如,车尺寸(CarSize)特征包括大型(Large)、中型(Medium)、小型(Small)。

由于序数数据的取值为离散的,所以可采用不同的值作为一个分支。与车型特征的三分支情况相同,采用三分支对车尺寸特征进行分割,如图4-10所示,其中每种尺寸类型一个分支。该情况下,多分带来的优点是:①简单,易于实现;②可解释性强。但它同样也有一定的缺点:分支数过多,导致过拟合,影响准确性。图4-10车尺寸特征的三分支情况

为了克服该缺陷,可以采用二分情况。图4-9中所涉及的二分支策略不适合序数数据的二分支要求,主要原因是标量数据仅考虑大小,不考虑顺序关系,而序数数据要求分支同时考虑大小和顺序关系。对序数数据而言,进行二分支时,不能破坏顺序关系,如图4-11所示。图4-11车尺寸特征的二分支情况

根据图4-11,对于车尺寸特征的二分支情况,可以合理划分为以下三种:

•{小型,中型},{大型},划分合理;

•{小型},{中型,大型},划分合理;

•{小型,大型},{中型},划分错误,破坏数据的顺序性。

3.实数/区间特征分支问题

实数/区间取值范围都是连续的。因此,基于标量数据与序数数据的二分/多分的技术和方法不适用于实数数据。离散化是连续特征进行分支的方式,如给定个人收入(Taxable

Incomes)特征,可以通过选取不同的阈值进行二分支和多分支,如图4-12所示。图4-12个人收入的分支情况

4.3.3最优划分

如何判断最优划分,具体包括:

①多分还是二分的选择?

②二分/多分条件下,多种方案如何选择最优?

例如图4-13中,如何判断和量化二分、三分、多分的优劣性?其中C0表示第0类中的数据对象数,C1表示第1类中的数据对象数。图4-13不同特征的分支情况

图4-14所示为图4-13的两种分类结果。可知,左侧结果不能有效地区分两类,而右侧结果可以区分两类,因此左边同质性低/纯度低,右边同质性高/纯度高。即隶属于同一类的数据对象越多,同质性越高。图4-14-两种不同的分类结果

那么,如何量化同质性/纯度?一旦有了量化标准,可

以选择最优的划分,一般而言,随着划分过程的不断进行,

我们希望决策树的分支节点所包含的样本尽可能属于同一类别,即节点的“纯度”(Purity)越来越高。划分的原则是:导致最大同质性/纯度变化的划分为最优划分,如图4-15所示。图4-15基于同质性/纯度标准的最优划分示意图

目前通用的度量方式有三种:Gini系数(基尼系数)、信息增益与最大错误率。

1.Gini系数

Gini系数是经济学里的一个概念,它是美国经济学家阿尔伯特·赫希曼根据劳伦茨曲线所定义的判断收入分配公平程度的指标。Gini系数是一个比值,是国际上用来综合考察

居民内部收入分配差异状况的一个重要分析指标。

回归分类树(ClassificationandRegressionTree,CART)使用“基尼系数”(GiniIndex)来选择划分属性。

定义4.4(Gini系数)给定决策树中的某个节点t,其对应一组数据对象,统计该组数据中第j类数据对象所占有的比例,表示为P(j|t),则Gini系数定义为

问题5:Gini系数的性质是什么?

提示:利用数据示例引导学生分析、理解Gini系数的基本性质。Gini系数的基本性质如下:

•取值范围是[0,0.5];

•最小取值是0,对应所有的数据对象都隶属于一个类别;

•最大取值是0.5,对应所有的数据对象都均匀分布在每个类别上;

•值越小,纯度越高。

图4-16显示了二元分类问题中不同二元分布问题的Gini系数的计算,相应的Gini系数结果列于表4-2中。图4-16Gini系数计算

问题6:Gini系数可以选择最佳划分,是否可以决定特征可分?

决策树算法追求更高的准确性以及高度的同质性,一个特征是否可分,取决于同质性/纯度是否提高,如图4-17所示。图4-17基于纯度/同质性决定特征是否划分

问题7:Gini系数可以选择最佳划分,是否可以选择二分与多分?

二分还是多分,取决于同质性/纯度是否提高,如图4-18所示。图4-18基尼系数可有效地解决特征分支问题与最优分支

结论:我们在候选属性集合中,选择那个使得划分后Gini系数最小的属性作为最优划分属性。

也可得出结论:特征是否多分/二分,选择Gini系数最小时所对应的划分。

考虑图4-19所示的例子,图4-20是图4-19对应的离散化的结果,其中“年收入≤v”用来划分拖欠欠款分类问题的训练记录。用穷举方法确定v的值,将N个记录中所有属性值都作为候选划分点,对每个候选v,都要扫描一次数据集,统计年收入大于和小于v的记录数,然后计算每个候选的Gini系数,并从中选择具有最小值的候选划分点。图4-19Gini系数如何选取实数最优的阈值图4-20图4-19对应的Gini系数结果

2.信息增益

定义4.5(信息熵)“信息熵”(InformationEntropy)是度量样本集合纯度最常用的一种指标。假定当前样本集合D中第k类样本所占的比例为pk(k=1,2,…,|y|),则D的信息熵定义为

Ent(D)的值越小,则D的纯度越高。信息熵的基本性质如下:

•取值范围是[0,1];

•最小取值是0,对应所有的数据对象都隶属于一个类别;

•最大取值是1,对应所有的数据对象都均匀分布在每个类别上;

•熵越小,纯度越高。

类似地,我们可以计算出采用其他两个特征“性别”和“月收入”作为根节点的信息增益分别为

显然,特征“性别”的信息增益最大,于是将其选为划分属性。如图4-21所示,16个样本被按照性别特征分成了两组,“性别=女性”组有9个样本,其中1人购车;“性别=男性”组有7个样本,其中3人购车。图4-21基于“性别”特征对根节点进行划分

然后,决策树算法将对每个分支节点进行进一步的划分。对“性别=女性”组和“性别=男性”组,采用与上面相同的方法分别计算两组样本上如果再采用“年龄”或“月收入”作为划分属性所得的信息增益。结果发现,对于“性别=男性”组,采用“年龄”特征后信息增益最大,为0.9852;而对于“性别=女性”组,采用“月收入”作为特征后信息增益最大,为0.688。这样就可以分别用这两个特征构建决策树下一级的节点,最终得到的决策树如图4-22所示。图4-22表4-3数据生成的判断客户是否购车的决策树

问题8:决策树构建过程中节点的纯度一定是越高越好吗?

实际上,纯度并非越高越好,例如图4-23中最右侧的决策树,其每个节点下面的Gini系数都达到最优,但是这种方式未必是最好的。图4-23在决策树中是否纯度越高越好?

实际上,信息增益准则对可取值数目较多的属性有所偏好,为减少这种偏好可能带来的不利影响,著名的C4.5决策树算法不直接使用信息增益,而是使用“增益”(Gain

Ratio)来选择最优划分属性。采用与式(4-3)相同的符号表示,增益率定义为

其中

称为属性a的“固定值”(IntrinsicValue)。属性a的可能取值数目越多(即V越大),则IV(a)的值通常会越大。显然,对于表4-3汽车销售的例子,也可以使用这种决策对“年龄”和“月收入”进行处理,选出当前数据下最优的划分方案。

需注意的是,增益率准则对可能取值数目较少的属性有所偏好。因此,C4.5算法并不是直接选择增益率最大的候选划分属性,而是使用了一个启发式:先从候选划分属性中找出信息增益高于平均水平的属性,再从中选择增益率最高的。

3.最大错误率(MaximumErrorRate)

定义4.6(最大错误率)给定决策树中的某个节点t,其对应一组数据对象,统计该组数据中第j类数据对象所占有的比例,表示为p(j|t),则最大错误率定义为

类似于Gini系数、信息增益,可利用数据来分析最大错误率的基本性质。最大错误率的基本性质如下:

•取值范围是[0,1];

•最小取值是0,对应所有的数据对象都隶属于一个类别;

•最大取值是1-1/n,对应所有的数据对象都均匀分布在每个类别上;

•错误率越小,纯度越高。

课堂练习示例:图4-24给出了最大错误率不纯性度量方法的计算实例。图4-24-最大错误率不纯性度量方法计算实例

问题9:Gini系数、信息熵、最大错误率的区别是什么?

图4-25展示了二元分类问题不纯性度量值的比较,可以看出,不同的不纯性度量是一致的。三种量化方式的区别是:①Gini系数与信息熵是连续的,而最大错误率是不连续的;②都是在p=0.5时取值最大;③两端时取值最小。图4-26具体展示了三种量化方式的区别。其中最大错误率不发生变化,为

Gini系数改进了结果。

因此以Gini系数为划分准则更准确。图4-25Gini系数、信息熵、最大错误率之间的比较图4-26Gini系数、信息熵、最大错误率实例对比

4.4

补充算法

4.4.1ID3算法任何一个决策树算法,其核心步骤都是为每一次分裂确定一个分裂属性,即究竟按照哪一个属性来把当前数据集划分为若干个子集,从而形成若干个“树枝”。ID3算法以“信息增益”为度量来选择分裂属性。哪个属性在分裂中产生的信息增益最大,就选择该属性作为分裂属性。ID3算法是一个从上到下、分而治之的归纳过程。

ID3算法的核心是:在决策树各级节点上选择分裂属性时,通过计算信息增益来选择属性,以使得在每一个非叶节点进行测试时,能获得关于被测试样本最大的类别信息。其具体方法是:检测所有的属性,选择信息增益最大的属性产生决策树节点,由该属性的不同取值建立分支,再对各分支的子集递归调用该方法建立决策树节点的分支,直到所有子集仅包括同一类别的数据为止,最后得到一棵决策树。它可以用来对新的样本进行分类,如算法4.2所示。

ID3算法的缺点也很突出,具体包括以下几点:

(1)ID3算法对训练样本质量的依赖性很强。

(2)ID3算法只能处理分类属性(离散属性),不能处理连续属性(数值属性)。

(3)ID3算法生成的决策树是一棵多叉树,分支的数量取决于分裂属性有多少个不同的取值,这不利于处理分裂属性取值数目较多的情况。因此,目前流行的决策树算法大多采用二叉树模型。

(4)ID3算法不包含对树的修剪,无法对决策树进行优化。

4.4.2C4.5算法

1.用信息增益率来选择属性

假设要选择有n个输出的检验,把训练样本集T分区成子集{T1,T2,T3,…,Tn}。假如S是任意样本集,设freq(Ci,T)代表S中属于类Ci的样本数量,S表示集S中的样本数量。最初的ID3算法用增益标准来选择需要检验的属性,即基于信息论中熵的概念。

下面的关系式可以计算出集合T的信息熵:

2.可以处理连续数值型属性

最优分割点是从候选分割点选取出来的,有两种生成候选分割点的方式:

(1)对连续属性排序,在每两个相邻的连续属性之间,以它们的均值作为分割点。因此,对于N条数据记录,将会有N-1个分割点。

(2)对连续属性排序,在分类结果产生变化的两组数据之间确定分割点,这样可以有效地减少计算量。

3.采用后剪枝方法修剪决策树

该方法使用训练样本集本身来估计剪枝前后的误差,从而决定是否确定要剪枝。方法中使用的公式为

式中:N是实例的数量;f=E/N为观察到的误差率(其中E为N个实例中分类错误的个数);q为真实的误差率;c为置信度(C4.5算法的一个输入参数,默认值为0.25);z为对应于置信度c的标准差,其值可根据c的设定值通过查正态分布表得到。通过该公式即可计算出真实误差率q的一个置信度上限,用此上限为该节点误差率e做一个悲观的估计:

4.对于缺失值的处理

对于缺失值数据我们需要解决两个问题:①如何在属性值缺失的情况下进行划分属性选择?②给定划分属性,若样本在该属性上的值缺失,如何对样本进行划分?

优点:C4.5算法采用信息增益率作为选择分支属性的标准,克服了ID3算法中信息增益选择属性时偏向选择取值多的属性的不足,并能够完成对连续属性离散化处理,还能够对不完整数据进行处理。C4.5算法属于基于信息论的方法,它以信息论为基础,以信息熵和信息增益度为衡量标准,从而实现对数据的归纳分类。

缺点:在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的效率低。此外,C4.5只适合于能够驻留于内存的数据集,当训练集无法在内存中容纳时,程序将无法运行。

4.5过拟合/欠拟合

4.5.1定义分类包括两大关键技术:分类器构建与分类器评估。前面介绍的都是分类器的构建,下面主要介绍分类器评估方法。分类器模型的评估涉及如何有效地选择评价指标的问题。通常来说,偏差和方差是两个典型的指标。偏差是指忽略了多少数据,即预测出来的数据与真实值的差距;而方差是指模型对数据的依赖程度,即预测出来的数据的分散程度。

假设使用g来代表预测值(这里我们把它看成是随机变量,即不同数据学习得到的模型),f代表真实值,=E(g)代表算法的期望预测(如可以用不同的数据集D1,D2,…,DK来

得到则有

借助偏差和方差可以有效地评价一个分类器。一个过拟合的模型具有高方差和低差。而反过来则被称为欠拟合,即不是过于密切地跟踪训练数据,而是一个不合适的模型忽略了训练数据的训练,并且无法学习输入和输出之间的潜在关系。如图4-27所示为过拟合与欠拟合示意图。分类器过拟合/欠拟合最直观的定义为:

过拟合:模型在训练样本下效果很好,但预测时表现不好的情况;

欠拟合:模型在训练和预测时表现都不好的情况。

导致过拟合/欠拟合的原因大致有:数据噪声导致不能很好地对训练数据集进行学习;样本量过小,导致学习不足,不能很好地泛化到测试数据集;过度追求纯度,导致对训练数据集过分学习,分类效果不佳。图4-27过拟合与欠拟合示意图(每个示例的过拟合/欠拟合情况均有标注)

4.5.2规避策略

通常来说,有几种方式分别从不同的方面来解决过拟合问题,如表4-4所示。

理想决策算法满足如下三个标准:

(1)叶节点数最少;

(2)叶节点深度最小。

决策树剪枝的基本策略有“预剪枝”(Prepruning)和“后剪枝”(Postpruning)。预剪枝是指在决策树生成过程中,对每个节点在划分前先进行评估,若当前节点的划分不能带来决策树泛化性能提升,则停止划分并将当前节点标记为叶节点;后剪枝则是先从训练集生成一棵完整的决策树,然后自底向上地对非叶节点进行考察,若将该节点对应的子树替换

为叶节点能带来决策树泛化性能的提升,则将该子树替换为叶节点。

1.预剪枝

首先讨论预剪枝。在决策树生长过程中需要决定某些节点是否继续分支或直接作为叶节点。若某些节点被判断为叶节点,则该分支停止生长。用于判断决策树停止的方法一般有三种:

(1)数据划分法。

(2)阈值法。

(3)信息增益的统计显著性分析法。

由上总结预剪枝的主要原则如下:

•定义一个高度,当决策树达到该高度时就停止决策树的生长;

•达到某个节点的示例具有相同的特征向量,即使这些示例不属于同一类,也可以停止决策树的生长;

•定义一个阈值,当达到某个节点的示例个数小于阈值时停止决策树的生长;

•定义一个阈值,计算每次扩张对系统性能的增益,通过比较信息增益值与该阈值的大小来决定是否停止决策树的生长。

图4-28给出了预剪枝算法示意图。

2.后剪枝

与预剪枝不同,后剪枝(Postpruning)首先构造完整的决策树,再对其进行修剪。其核心思想是对一些分支进行合并,它从叶节点出发,如果消除具有相同父节点的叶节点后不会导致信息熵的明显增加,则取消执行,并以其父节点作为新的叶节点。如此不断地从叶节点往上进行回溯,直到合并操作不再需要为止。相比于预剪枝,这种方法更常用,因为在预剪枝方法中精确地估计何时停止树增长很困难。１

常用的后剪枝规则包含三种:

(1)减少分类错误的修剪法。

(2)最小代价与复杂性的折中。

(3)最小描述长度(MinimalDescriptionLength,MDL)准则。

由上总结后剪枝的主要方法如下:

•Reduced-ErrorPruning(REP,错误率降低剪枝);

•Pesimistic-ErrorPruning(PEP,悲观错误剪枝);

•Cost-ComplexityPruning(CCP,代价复杂度剪枝);

•Error-BasedPruning(EBP,基于错误的剪枝)。

图4-29给出了后剪枝算法示意图,乐观估计条件下都不剪掉,悲观估计下不剪左边剪右边。图4-29后剪枝算法示意图

3.缺失值处理方法

现实任务中常会遇到不完整样本,也就是说样本的某些属性值缺失。例如由于诊测成本、隐私保护等因素,患者的医疗数据在某些属性上的取值(如HIV测试结果)未知;尤其

是在属性数目较多的情况下,往往会有大量样本出现缺失值。如果简单地放弃这些不完整样本,只使用无缺失值样本进行学习,显然是对数据极大的浪费。

数据属性值缺失有多种情况:

(1)树节点中包括缺失特征值的记录,影响其不纯性计算;

(2)父节点中包括缺失特征值的记录,影响该记录如何分配到子节点;

(3)测试记录中包括缺失特征值的记录,影响测试记录的分类。

针对问题(1)纯度计算问题,采用数据完整的样本数来估计信息增益,如图4-30所示。图4-30数据缺失导致纯度计算问题

针对问题(2)纯度计算问题,采用父节点的值来估计信息增益,如图4-31所示。图4-31利用父节点的取值解决数据分类问题

针对问题(3)测试记录中包括缺失特征值的记录,影响测试记录的分类,通过不同样本所占有的比例分别对子节点进行赋权,利用概率方式进行估计与计算,如图4-32所示。图4-32利用概率赋权方式解决子节点分配问题

4.其他处理方法

解决过拟合问题除了上面提到的方法外,还有决策边界、树复制、数据分割等。多种解决过拟合问题的方法与策略的优点和缺点如表4-5所示。

4.6分类准确性评估

4.6.1准确性混淆矩阵(ConfusionMatrix)也称误差矩阵,是表示精度评价的一种标准格式,用n行n列的矩阵形式来表示。具体评价指标有总体精度、制图精度、用户精度等,这些精度指标从不同的侧面反映了图像分类的精度。在人工智能中,混淆矩阵是可视化工具,特别用于监督学习,在无监督学习中一般称作匹配矩阵。

以分类模型最简单的二分类为例,对于这种问题,我们的模型最终需要判断样本的结果是0还是1,或者说是阳性(Positive)还是阴性(Negative)。通过样本的采集,能够直接

知道真实情况下,哪些数据的结果是positive,哪些数据的结果是negative。同时,我们通过用样本数据得到分类模型的结果,也可以通过模型预测知道这些数据哪些是positive,

哪些是negative。因此,我们能够得到四个基础指标,它们被称为一级指标(最底层指标):

•真实值是Positive,模型预测是Positive的数量(TruePositive=TP);

•真实值是Positive,模型预测是Negative的数量(FalseNegative=FN);

•真实值是Negative,模型预测是Nositive的数量(FalsePositive=FP);

•真实值是Negative,模型预测是Negative的数量(TrueNegative=TN)。

将这四个指标一起呈现在表格中,就能得到如图4-33所示的一个矩阵,我们称它为混淆矩阵。图4-33二分类问题混淆矩阵

说明:混淆矩阵的每一