劣质数据上代价敏感决策树的建立∗

齐志鑫,王宏志,周 雄,李建中,高 宏

(哈尔滨工业大学 计算机科学与技术学院,黑龙江 哈尔滨 150001)

分类是数据挖掘和机器学习领域中常见的一类任务,该任务从训练数据中提取模型,再利用该模型预测未知的数据类别[1].目前,有很多用于完成分类任务的方法被提出,如决策树[2]、贝叶斯网[3]、神经网络[4]、基于实例的推理[5]等.在这些方法中,决策树凭借易解释、计算效率高、能够生成易理解的分类规则等优势得到了众多关注,并被广泛应用于分类任务中[6].

起初,大量决策树研究着眼于最大化分类准确率或最小化分类误差[7-9].然而,由于一个分类任务可能产生多种类型的代价,越来越多的研究工作关注于代价敏感决策树的建立[10-12].在目前研究的代价类型中,两种最常见的代价是误分类代价和测试代价[13].误分类代价是指一个属于类j的实例被误分类为类i的代价,而误分类所产生的代价常常是不均衡的.例如,将一个病人诊断为健康的代价往往比将一个健康的人诊断为病人的代价大很多.除了误分类代价,每一次测试也关联着相应的代价.例如在医疗诊断中,每一次血常规检测都存在一个相关联的代价[1].

现如今,随着数据量急剧增长,劣质数据的出现也愈发频繁[14].在建立代价敏感决策树时,训练数据集中的劣质数据会对分裂属性的选择和决策树结点的划分造成一定的影响.因此在进行分类任务前,需要提前对数据进行劣质数据清洗.然而在实际应用中,由于数据清洗工作所需要的时间和金钱代价往往很高,许多用户给出了自己可接受的数据清洗代价最大值,并要求将数据清洗的代价控制在这一阈值内[15].因此,除了误分类代价和测试代价以外,劣质数据的清洗代价也是代价敏感决策树建立过程中的一个重要因素.然而,现有代价敏感决策树建立的相关研究没有考虑数据质量问题.为了弥补这一空缺,本文将劣质数据的清洗代价纳入代价敏感决策树建立问题的考虑因素中,该问题带来了以下挑战.

(1) 由于清洗后的数据将用于建立代价敏感决策树,第 1个挑战是如何将代价敏感决策树的建立目标融合到数据清洗方法中;

(2) 由于不同用户设定的数据清洗代价阈值不同,不同数据集中劣质数据所占比率不同,第 2个挑战是针对不同的情况,如何选择最优的代价敏感决策树建立方法.

鉴于这两点挑战,本文从问题定义入手,将用户设定的数据清洗代价阈值纳入到代价敏感决策树建立的问题中.然后,针对这一问题给出融合数据清洗算法的代价敏感决策树建立方法.最后,测试改变用户设定的数据清洗代价阈值或改变数据集中劣质数据比率时不同方法的总代价、分类准确率和效率,从而得出不同情况下最优的代价敏感决策树建立方法.本文的主要贡献有以下几点.

(1) 研究了劣质数据上代价敏感决策树的建立问题,是目前首个考虑到代价敏感决策树建立过程中的数据质量问题的工作;

(2) 针对劣质数据上的代价敏感决策树建立问题,本文提出了 3种融合数据清洗算法的代价敏感决策树建立方法,即融合基于分裂属性收益的分步清洗算法的代价敏感决策树建立方法、融合基于分裂属性收益和清洗代价的一次性清洗算法的代价敏感决策树建立方法、融合基于分裂属性收益和清洗代价的分步清洗算法的代价敏感决策树建立方法;

(3) 本文通过大量实验验证了所提出的3种代价敏感决策树建立方法的总代价、分类准确率和分类效率,并给出了不同情况下最优的代价敏感决策树建立方法.

本文第 1节对代价敏感决策树建立问题相关的研究工作进行总结.第 2节对本文问题相关的定义进行介绍.第3节对本文提出的3种融合数据清洗算法的代价敏感决策树建立方法进行详细地阐述.第4节对本文的实验评估过程和实验结果进行讨论和分析,并给出实验结论.第 5节总结全文,并对未来值得关注的研究方向进行初步探讨.

1 相关工作

目前,代价敏感决策树建立问题的研究目标主要包括3种:第1种是最小化决策树的误分类代价;第2种是最小化决策树的测试代价;第 3种是最小化决策树的误分类代价和测试代价总和[13].本文选择的研究目标是第3种.

针对不同的问题目标,许多代价敏感决策树建立方法被提出.这些方法可以分为两大类.

· 第1类是采用贪心的方法来建立一棵单独的决策树,例如:CS-ID3算法[16]采用基于熵的选择方法在决策树建立过程中最小化代价,AUCSplit算法[17]在决策树建立之后最小化代价;

· 第2类是非贪心的方法,该方法生成多个决策树,例如遗传算法ICET[18]、将现有基于准确率的方法包装在一起的MetaCost算法[19].

按照时间顺序来看,Hunt等人首先发现了误分类和测试对人们的决策存在一定的影响,并提出了概念学习系统框架[20].随后,ID3算法[21]采用了概念学习系统框架的部分思想,并使用了信息论评估参数来选择特征.在信息论方法被提出后,许多在决策树建立过程中最小化代价的方法被陆续提出,如CS-ID3算法[16]、EG2算法[22].然后,在决策树建立后最小化代价的方法被提出,如 AUCSplit算法[17].之后,遗传方法如 ICET算法[18]、提升法如UBoost算法[23]、装袋法如MetaCost算法[19]等被提出.随后,多重结构的方法如LazyTree算法[24]、随机方法如ACT算法[25]、TATA算法[26]被陆续提出.

在最小化代价敏感决策树的误分类代价和测试代价的基础上,有研究着眼于包含其他限制因素的代价敏感决策树建立问题.例如:由于有些分类任务需要在规定的时间内完成,在时间限制下的代价敏感决策树建立方法被提出[1].有时用户会对分类任务的准确率提出预期的要求,因此面向用户需求的代价敏感决策树建立方法被提出[27].然而,目前并未有研究关注劣质数据上的代价敏感决策树建立.因此,本文将弥补这一空缺.

2 问题定义

本节将对劣质数据上代价敏感决策树建立问题的相关定义进行介绍.

2.1 决策树

决策树T具有树结构,是有向无环图的一个特例.决策树中包含根结点、内部结点和叶子结点的有限集合、连接两个结点的边的集合.图1是决策树的实例.

Fig.1 An instance of decision tree图1 决策树实例

如图1所示,ni表示第i个结点.如果ni是内部结点,那么该结点会关联着属性a(ni),a(ni)被称为在结点ni中被用到的测试属性.如果ni是叶子结点,那么该结点关联着一个类别标签值.本文用inter(T)表示T中所有内部结点的集合,用leaf(T)表示T中所有叶子结点的集合,Ti表示T中根为ni的子树.

本文用有序对(ni,nj)表示决策树中一条关联着结点ni和nj的边,其中,ni是nj的父结点.当ni是关联测试属性a(ni)的内部结点时,边(ni,nj)关联一个单独的值或一个值集合,这些值都是a(ni)可能的属性值.决策树中的一条路径是边的一个序列,本文用path(ni,nj)表示从ni到nj的路径.假设ni到nj之间的序列是n1,n2,…,nm,那么path(ni,nj)={(ni,n1),(n1,n2),…,(nm,nj)},本文用n(ni,nj)={n1,n2,n3,…,nm}表示从ni到nj的路径上所有中间结点的集合.

决策树分类器通过在训练数据集D上学习构建而成,dk表示D中的第k条记录.每条记录由属性值集合和类别标签构成.本文用a表示属性值集合,ax表示a中的第x个属性.表1是训练数据集的一个实例,每一条记录由ID、5个属性和1个类别标签组成.

Table 1 An instance of training dataset表1 训练数据集实例

本文用D(ni)表示D中属性值遵循path(root,ni)中边上属性值的记录集合,这说明D(ni)是满足path(root,ni)上所有测试的记录集合.D(root)表示整个训练数据集D,|D(ni)|表示D(ni)中的记录个数.根据表1中的训练数据集构建的决策树如图2所示.

Fig.2 Decision tree trained by Table 1图2 根据表1训练成的决策树

2.2 误分类代价和测试代价

误分类代价是指一个属于类j的实例被误分类为类i的代价.假设训练数据集中有m个类别,那么误分类代价矩阵可以用m×m的矩阵表示,见表2.本文用ClassCost(i,j)表示当一个实例属于类j时,将其误分类为类i的代价.从表2可知,ClassCost(T,T)=0,ClassCost(T,F)=10,ClassCost(F,T)=20,ClassCost(F,F)=0.

Table 2 A matrix of misclassification costs表2 误分类代价矩阵

当为叶子结点分配一个标签时,可能会导致该叶子结点关联的记录产生一定的误分类代价.因此,本文用ClassCost(ni,lj)表示给结点ni分配标签为lj的叶子结点时产生的误分类代价,即:

例如,对于表1中的训练数据,ClassCost(root,T)=0+10+10+0+0+10+10+10=50,ClassCost(root,F)=20+0+0+20+20+0+0+0=60.

本文用TestCost(ax)表示对属性ax进行测试所需要的代价,用ArrCost(ni,T)表示一条记录从T的根结点到达ni所需的总测试代价,即.表1中属性的测试代价见表3.从表3可知,ArrCost(n01,T)=4,ArrCost(n011,T)=4+6=10.

Table 3 TestCost of attributes表3 属性的测试代价

每一条记录都会经过从决策树根结点到叶子结点的测试,因此,结点ni中的记录到达ni所花费的总测试代价为ArrCost(ni,T)×|D(ni)|.此外,ni获得一个类别标签时会产生一定的误分类代价.本文用NodeCost(ni)表示误分类代价和测试代价的总代价.如果将结点ni作为一个叶子结点,则

例如,对于图2中的决策树,NodeCost(root)=50+0×8=50,NodeCost(n01)=20+4×3=32.

图2中其余结点的NodeCost值见表4.

Table 4 NodeCost of nodes表4 结点的NodeCost值

本文用TreeCost(T)表示决策树T的总代价,即.例如,图2中决策树的总代价为TreeCost(T)=NodeCost(n011+n012+n021+n022+n03)=10+20+14+7+8=59.

2.3 检测代价和修复代价

劣质数据清洗工作往往由错误检测和修复两部分组成[28].在对训练数据集进行清洗的过程中,首先需要对数据集中的劣质数据进行检测,然后针对检测到的劣质数据进行相应的修复.数据集中的每一个属性都对应着检测该属性值中可能存在的错误所需要花费的代价和修复该属性错误值所需要花费的代价.

本文用DetCost(ax)表示对属性ax中的每个值进行错误检测所需要花费的代价.因此,对属性ax中全部属性值进行劣质数据检测所需要的代价是DetCost(ax)×|ax|.如果检测到属性ax中的劣质数据个数为|Er(ax)|,那么对属性ax中的全部劣质数据值进行修复所需要的代价是Rep(ax)×|Er(ax)|,其中,Rep(ax)是修复属性ax中的每个劣质数据值所需要的代价.在本文中,xd表示属性ax中完成了劣质数据检测的属性值个数,xr表示属性ax中完成了劣质数据修复的属性值个数.然而在实际应用中,由于数据清洗工作所需要的时间和金钱代价往往很高,许多用户给出了自己可接受的数据清洗代价最大值.因此,本文用MaxCost表示用户可接受的数据清洗代价阈值,并将数据清洗的代价控制在这一阈值内.

2.4 劣质数据上代价敏感决策树建立问题

给定一个训练数据集、用户设定的数据清洗代价最大值、误分类代价矩阵、每个属性对应的测试代价、检测代价和修复代价,劣质数据上代价敏感决策树建立问题定义如下:基于训练数据集,建立一个代价敏感决策树,使得该决策树的误分类代价和测试代价总和最小,且清洗该数据集的检测代价和修复代价总和不超过用户设定的数据清洗阈值.

该问题的形式化描述是已知训练数据集D,数据清洗代价最大值MaxCost,误分类代价ClassCost(ni,lj),测试代价TestCost(ax),检测代价DetCost(ax)和修复代价,建立T,使得:

其中,

3 融合数据清洗算法的代价敏感决策树建立方法

为了解决劣质数据上代价敏感决策树的建立问题,本文提出了 3种融合数据清洗算法的代价敏感决策树建立方法,即融合基于分裂属性收益的分步清洗算法的代价敏感决策树建立方法、融合基于分裂属性收益和清洗代价的一次性清洗算法的代价敏感决策树建立方法和融合基于分裂属性收益和清洗代价的分步清洗算法的代价敏感决策树建立方法.本节将分别对这 3种代价敏感决策树建立方法进行阐述,并对各个方法的适用情况进行讨论.

3.1 融合基于分裂属性收益的分步清洗算法的代价敏感决策树建立方法

由于代价敏感决策树的建立目标是最小化误分类代价和测试代价的总和,因此可以将误分类代价和测试代价总和的减少程度作为决策树分裂属性选取的标准.本文定义了分裂属性收益的概念来表示误分类代价和测试代价总和的减少程度.

本文用Benefit(ax,ni)表示用属性ax分裂结点ni的收益,结点ni会被分裂为若干个孩子结点.分裂属性收益Benefit(ax,ni)定义为

例如在图2中,NodeCost(n01)=32,NodeCost(n011)=10,NodeCost(n012)=20.因此,Benefit(a2,n01)=32-(10+20)=2.

融合基于分裂属性收益的分步清洗算法的代价敏感决策树建立方法的过程如下:在决策树建立的每一步中,选择收益最大的分裂属性;先对该分裂属性中的值进行劣质数据检测和修复,再将该属性用于决策树的分裂过程中;当所花费的清洗代价达到用户设定的最大值后,不再对后续的分裂属性进行清洗,直接用于决策树的分裂过程中;当结点中所有记录所对应的类别标签相同,或没有分裂属性的收益为正值时不再对该结点进行分裂,将其标记为叶子结点,其类别标签为使得误分类代价最小的类别.

上述过程中,基于分裂属性收益的分步清洗算法见算法1.算法的输入是待清洗的训练数据集、用户给定的清洗代价阈值、数据集中每个属性对应的劣质数据检测代价和修复代价.首先,对根结点的分裂属性收益进行计算,选取收益最大的属性作为分裂属性(第1行～第5行).对该属性中的属性值进行劣质数据检测和修复,并计算剩余的清洗代价是否足够对训练数据集中该属性的全部属性值进行检测:如果足够,那么对该属性的所有属性值进行劣质数据检测(第 6行～第 9行);如果不足够,那么对该属性部分属性值进行检测(第 10行～第 14行).在检测出分裂属性中包含的劣质数据后,对劣质数据进行修复,并计算剩余的清洗代价是否足够对全部劣质数据进行修复:如果足够,那么对该属性中包含的所有劣质数据进行修复(第15行～第17行);如果不足够,那么对部分劣质数据进行修复(第18行～第21行).然后,继续为下一个结点寻找分裂属性并清洗(第22行).当清洗代价达到用户给定的阈值或决策树中全部结点都被清洗完毕后,返回清洗后的训练数据集(第23行).

算法1.基于分裂属性收益的分步清洗算法.

输入:训练数据集Dm×n,清洗代价阈值 MaxCost,每个属性x∈{1,2,…,n}的劣质数据检测代价Det(ax)和修复代价Rep(ax);

输出:清洗后的训练数据集Dm×n.

算法1的时间复杂度取决于决策树中的结点个数N、训练数据集中的属性个数n和记录个数m.假设劣质数据检测函数Detect(x)的时间复杂度为O(f(x)),劣质数据修复函数Repair(x)的时间复杂度为O(g(x)),当max(f(x),g(x))≥nlogn时,算法1的时间复杂度是O(Nmax(f(x),g(x)));当max(f(x),g(x))

融合基于分裂属性收益的分步清洗算法的代价敏感决策树建立方法尽可能地将代价敏感决策树中前几层的分裂属性进行清洗后再用于分裂过程.由于决策树中层次低的分裂结点重要性高于层数高的分裂结点,所以该方法保证了决策树结点分裂的有效性,有效降低了决策树的误分类代价和测试代价总和,使得决策树在后续的分类任务中受训练数据集中的劣质数据影响较小.然而,当用户设定的清洗代价阈值较小时,该方法可能会对清洗代价高的属性优先进行清洗,使得能够被清洗到的属性个数较少,从而导致在这种情况下,该方法对劣质数据的清洗效果不大.

3.2 融合基于分裂属性收益和清洗代价的一次性清洗算法的代价敏感决策树建立方法

为了解决融合基于分裂属性收益的分步清洗算法的代价敏感决策树建立方法所存在的问题,本文将数据清洗代价考虑到数据清洗算法中,希望选择收益高且清洗代价低的属性优先进行清洗.本文定义了收益与清洗代价比来平衡分裂属性收益和清洗代价这两个冲突的因素,即Benefit(ax,n0)/(Det(ax)+Rep(ax)),其中,Benefit(ax,n0)是属性ax在决策树根结点n0时的分裂属性收益,Det(ax)和Rep(ax)分别是对属性ax的每个属性值进行劣质数据检测和修复的代价.

融合基于分裂属性收益和清洗代价的一次性清洗算法的代价敏感决策树建立方法的过程如下:将训练数据集中的各个属性按照收益与清洗代价比进行排序,按照顺序进行一次性数据清洗.在每一次选择分裂属性时,对每个属性重新计算分裂属性收益Benefit(ax,n0),选择收益最大的属性作为分裂属性.当结点中所有记录所对应的类别标签相同,或没有分裂属性的收益为正值时停止对该结点的分裂,将其标记为叶子结点,其类别标签为使得误分类代价最小的类别.

上述过程中基于分裂属性收益和清洗代价的一次性清洗算法见算法 2.算法的输入是待清洗的训练数据集、用户给定的清洗代价阈值、数据集中每个属性对应的劣质数据检测代价和修复代价.首先,对每个属性在根结点的收益与清洗代价比从大到小排序(第1行～第4行).按照顺序选取属性进行劣质数据检测和修复(第5行、第6行).计算剩余的清洗代价是否足够对训练数据集中该属性的全部属性值进行检测:如果足够,那么对该属性的所有属性值进行劣质数据检测(第7行～第10行);如果不足够,那么对该属性部分属性值进行检测(第11行～第15行).在检测出分裂属性中包含的劣质数据后,对劣质数据进行修复,并计算剩余的清洗代价是否足够对全部劣质数据进行修复:如果足够,那么对该属性中包含的所有劣质数据进行修复(第16行～第18行);如果不足够,那么对部分劣质数据进行修复(第19行～第22行).然后,按照顺序对下一个属性进行清洗(第23行).当清洗代价达到用户给定的阈值或全部属性都被清洗完毕后,返回清洗后的训练数据集(第24行).

算法2.基于分裂属性收益和清洗代价的一次性清洗算法.

输入:训练数据集Dm×n,清洗代价阈值MaxCost,每个属性x∈{1,2,…,n}的劣质数据检测代价Det(ax)和修复代价Rep(ax);

输出:清洗后的训练数据集Dm×n.

算法 2的时间复杂度取决于训练数据集中的属性个数n和记录个数m.假设劣质数据检测函数Detect(x)的时间复杂度为O(f(x)),劣质数据修复函数Repair(x)的时间复杂度为O(g(x)),算法 2的时间复杂度是O(nlogn×max(f(x),g(x))).

融合基于分裂属性收益和清洗代价的一次性清洗算法的代价敏感决策树建立方法尽可能地优先清洗收益大且清洗代价小的属性.该方法提前将数据集中的劣质数据清洗完毕,使得在决策树建立过程中能够直接利用清洗后的属性收益选取分裂属性,很大程度上降低了劣质数据对决策树的影响.此外,该方法采用一次性清洗策略,与分步清洗策略相比节约了时间.然而,该方法一次性清洗到的属性不一定都会在后续的决策树建立过程中被选作分裂属性.因此,在劣质数据比例较大的情况下,该方法可能没有清洗到决策树建立过程中的某些分裂属性,导致数据清洗过程对分类任务的作用不大.

3.3 融合基于分裂属性收益和清洗代价的分步清洗算法的代价敏感决策树建立方法

为了解决融合基于分裂属性收益和清洗代价的一次性清洗算法的代价敏感决策树建立方法所存在的问题,本文提出了融合基于分裂属性收益和清洗代价的分步清洗算法的代价敏感决策树建立方法.该方法的过程如下:在决策树建立的每一步中,选择收益与清洗比最大的分裂属性;对该属性中的值进行劣质数据检测和修复,再将该属性用于决策树的分裂过程中;所花费的清洗代价达到了用户设定的代价阈值时,不再对后续的分裂属性进行清洗;结点中所有记录所对应的类别标签相同,或没有分裂属性的收益为正值时,停止对该结点的分裂,将其标记为叶子结点,其类别标签为使得误分类代价最小的类别.

上述过程中,基于分裂属性收益和清洗代价的分步清洗算法见算法3.算法的输入是待清洗的训练数据集、用户给定的清洗代价阈值、数据集中每个属性对应的劣质数据检测代价和修复代价.

首先,对根结点的收益与清洗代价比进行计算,选取比值最大的属性作为分裂属性(第1行～第5行).对该属性中的属性值进行劣质数据检测和修复,计算剩余的清洗代价是否足够对训练数据集中该属性的全部属性值进行检测:如果足够,那么对该属性的所有属性值进行劣质数据检测(第6行～第9行);如果不足够,那么对该属性部分属性值进行检测(第10行～第14行).在检测出分裂属性中包含的劣质数据后,对劣质数据进行修复,并计算剩余的清洗代价是否足够对全部劣质数据进行修复:如果足够,那么对该属性中包含的所有劣质数据进行修复(第15行～第17行);如果不足够,那么对部分劣质数据进行修复(第18行～第21行).然后,继续为下一个结点寻找分裂属性并清洗(第 22行).当清洗代价达到用户给定的阈值或决策树中全部结点都被清洗完毕后,返回清洗后的训练数据集(第23行).

算法3.基于分裂属性收益和清洗代价的分步清洗算法.

输入:训练数据集Dm×n,清洗代价阈值MaxCost,每个属性x∈{1,2,…,n}的劣质数据检测代价Det(ax)和修复代价Rep(ax);

输出:清洗后的训练数据集Dm×n.

算法3的时间复杂度取决于决策树中的结点个数N、训练数据集中的属性个数n和记录个数m.假设劣质数据检测函数Detect(x)的时间复杂度为O(f(x)),劣质数据修复函数Repair(x)的时间复杂度为O(g(x)),当max(f(x),g(x))≥nlogn时,算法3的时间复杂度是O(Nmax(f(x),g(x)));当max(f(x),g(x))

融合基于分裂属性收益和清洗代价的分步清洗算法的代价敏感决策树建立方法将收益大且清洗代价小的属性选为分裂属性并优先进行清洗.在决策树建立的每一步中,分裂属性被清洗完毕后再用于分裂.由于决策树中层数低的分裂结点重要性高于层数高的分裂结点,该方法保证了决策树结点分裂的有效性,有效降低了决策树的误分类代价和测试代价总和,使得决策树在后续的分类任务中受训练数据集中的劣质数据影响较小.

3.4 适用情况讨论和时间复杂度比较

当用户设定的数据清洗代价阈值较小时,融合基于分裂属性收益的分步清洗算法的代价敏感决策树建立方法可能会对清洗代价高的属性优先进行清洗,使得能够被清洗到的属性个数较少,对劣质数据的清洗效果不大.因此,该方法不适用于这种情况.而融合基于分裂属性收益和清洗代价的分步清洗算法的代价敏感决策树建立方法优先对收益大且清洗代价小的属性进行清洗,避免了优先清洗代价高的属性,保证了数据清洗的效果和决策树结点分裂的有效性.因此,该方法适用于这种情况.

当劣质数据比例较大时,融合基于分裂属性收益和清洗代价的一次性清洗算法的代价敏感决策树建立方法一次性清洗到的属性不一定都会在后续的决策树建立过程中被选作分裂属性.该方法可能没有清洗到决策树建立过程中的某些分裂属性,导致数据清洗过程对分类任务的作用不大.因此,该方法不适用于这种情况.而融合基于分裂属性收益和清洗代价的分步清洗算法的代价敏感决策树建立方法在决策树建立的每一步中选择分裂属性,将其清洗完毕后再用于分裂.该方法保证了数据清洗的效果和决策树结点分裂的有效性,有效降低了决策树的误分类代价和测试代价总和,使得决策树在后续的分类任务中受训练数据集中的劣质数据影响较小.因此,该方法适用于这种情况.

此外,为了方便读者选择最适合的数据清洗算法完成劣质数据上的代价敏感决策树建立,表5从时间复杂度方面对本文所提出的3种清洗算法进行了比较,时间复杂度分析的详细过程参见本文第3.1节～第3.3节.

Table 5 Comparison of time complexity of three algorithms表5 3种算法的时间复杂度比较

4 实验评估

为了验证所提出方法的性能,本文从3个方面对所提出的3种融合数据清洗算法的代价敏感决策树建立方法进行了测试:(1) 利用本文所提出的方法建立的代价敏感决策树用于分类时产生的误分类代价和测试代价总和;(2) 利用本文所提出的方法建立的代价敏感决策树的分类准确率;(3) 利用本文所提出的方法建立的代价敏感决策树的分类效率.

本实验使用的数据集是UCI公测集上的6个经典数据集,其基本信息见表6.在实验过程中,本文选用了劣质数据中的不一致数据进行实验,根据在不同数据集上定义的函数依赖,向训练数据集中人为注入错误.本实验采用10折交叉验证方法,随机生成训练集和测试集,并将在测试集上进行分类任务的结果取平均值作为最终的实验结果.

Table 6 Datasets information表6 数据集信息

所有实验均在因特尔i7CPU@2.4GHz,8GB内存,1TB硬盘的电脑上完成,所有算法均用Python语言编写.

本实验分别对以下4种代价敏感决策树进行了评估和比较.

(1) T1:随机对训练数据集中的劣质数据进行清洗,再根据分裂属性收益建立的代价敏感决策树;

(2) T2:采用融合基于分裂属性收益的分步清洗算法的代价敏感决策树建立方法建立的代价敏感决策树;

(3) T3:采用融合基于分裂属性收益和清洗代价的一次性清洗算法的代价敏感决策树建立方法建立的代价敏感决策树;

(4) T4:采用融合基于分裂属性收益和清洗代价的分步清洗算法的代价敏感决策树建立方法建立的代价敏感决策树.

4.1 分类任务产生的总代价

为了验证所提出的代价敏感决策树建立方法的有效性,本文对上述 4种代价敏感决策树用于分类任务时产生的误分类代价和测试代价总和(即TreeCost)进行了比较.首先,通过改变用户给定的清洗代价最大值,测试分类任务产生的总代价所发生的变化.实验结果如图3所示.

Fig.3 Comparison experiments varying MaxCost图3 改变MaxCost值时的对比实验

从图3中能够观察到,决策树T2和T4的总代价始终小于T1和T3,而T3的总代价往往小于T1.此外,从图3(a)、图3(d)～图3(f)中可以看出:当用户设定的清洗代价最大值MaxCost≤40%时,决策树T4的总代价小于T2;当 MaxCost>40%时,T2的总代价小于 T4.在图3(b)和图3(c)中,当 MaxCost≤50%时, T4的总代价小于 T2;当MaxCost>50%时,T2的总代价小于 T4.这是由于当用户给定的清洗代价较高时,只考虑分裂属性收益而不考虑清洗代价,也能够清洗到较多的分裂属性;而当用户给定的清洗代价较低时,如果不考虑属性对应的清洗代价,可能会优先清洗收益高但清洗代价也高的分裂属性,导致总清洗代价很快被用完,而能够被清洗的分裂属性却很有限,从而影响了代价敏感决策树的总代价.

因此可以得出结论:当用户设定的清洗代价最大值较小时,代价敏感决策树 T4的总代价最小,即采用融合基于分裂属性收益和清洗代价的分步清洗算法的代价敏感决策树建立方法建立的代价敏感决策树最优;当用户设定的清洗代价最大值较大时,代价敏感决策树T2的总代价最小,即采用融合基于分裂属性收益的分步清洗算法的代价敏感决策树建立方法建立的代价敏感决策树最优.

此外,没有进行数据清洗而直接构建的代价敏感决策树的总代价明显高于融合数据清洗方法构建的代价敏感决策树.由此可知,采用融合数据清洗的代价敏感决策树建立方法大幅度节省了误分类代价和测试代价.因此,数据清洗过程对于劣质数据上代价敏感决策树的建立是十分必要的.

然后,本文通过改变训练数据集中的错误率来评估分类任务产生的总代价所发生的变化.实验结果如图4所示.

Fig.4 Comparison experiments varying error rate图4 改变错误率时的对比实验

从图4中能够观察到:决策树T3和T4的总代价始终小于T1和T2,而T2的总代价往往小于T1.此外,从图4(a)、图4(c)～图4(e)中可以看出:当训练数据集中的错误率小于等于40%时,决策树T3的总代价小于T4;当错误率大于40%时,T4的总代价小于T3.在图4(b)和图4(f)中,当错误率小于等于30%时,T3的总代价小于T4;当错误率值大于30%时,T4的总代价小于T3.这是由于决策树T3用到的一次性清洗算法并不能保证清洗到的属性在建立决策树的过程中被选做分裂属性.在训练数据集错误率较高的时候,可能导致许多存在劣质数据的分裂属性并没有被清洗到,从而影响了代价敏感决策树分类时的总代价.

此外,通过图4可以看出:当错误率上升时,总代价也不断增大.这是由于训练数据集中的劣质数据增多,使得代价敏感决策树的结构更加复杂,结点数目增加,相应地,测试代价增大,总代价增大.

因此可以得出结论:当错误率较小时,代价敏感决策树 T3的总代价最小,即采用融合基于分裂属性收益和清洗代价的一次性清洗算法的代价敏感决策树建立方法建立的代价敏感决策树最优;当错误率较大时,代价敏感决策树T4的总代价最小,即采用融合基于分裂属性收益和清洗代价的分步清洗算法的代价敏感决策树建立方法建立的代价敏感决策树最优.

综上所述,当错误率较大,而用户设定的清洗代价最大值较小时,代价敏感决策树 T4的总代价最小,即采用融合基于分裂属性收益和清洗代价的分步清洗算法的代价敏感决策树建立方法建立的代价敏感决策树最优.

4.2 分类任务的准确率

为验证所提出的代价敏感决策树建立方法的有效性,本文对 4种代价敏感决策树的分类准确率进行了比较.实验结果见表7,其中,MaxCost为0%的情况表示没有对劣质数据进行清洗,直接构建代价敏感决策树.

Table 7 Experimental results of classification accuracy表7 分类准确率的实验结果

从表7可以看出,代价敏感决策树T1～ T4在分类准确率上相差极小.因此,在选择代价敏感决策树建立方法时,可以不必将分类准确率作为考虑因素.此外,没有进行数据清洗而直接构建的代价敏感决策树(即 MaxCost为0%)的分类准确率比融合数据清洗方法构建的代价敏感决策树至少低7.23%(根据表7中的平均值计算).由此可知,采用融合数据清洗的代价敏感决策树建立方法能够有效提高决策树的分类质量.因此,数据清洗过程对于劣质数据上代价敏感决策树的建立是十分必要的.

4.3 分类任务的效率

为了验证所提出的代价敏感决策树建立方法的有效性,本文对 4种代价敏感决策树的分类效率进行了比较.实验结果见表8.从表8可以看出,代价敏感决策树T1～T4在分类效率上相差极小.因此,在选择代价敏感决策树建立方法时,可以不必将分类效率作为考虑因素.

Table 8 Experimental results of classification efficiency (ms)表8 分类效率的实验结果 (毫秒)

Table 8 Experimental results of classification efficiency (Continued) (ms)表8 分类效率的实验结果(续) (毫秒)

综合上述实验,本文对所提出的 3种代价敏感决策树建立方法进行了充分地比较.根据实验结果,3种方法的具体适用情况见表9.

Table 9 Applicable conditions of three methods表9 3种方法的适用情况

5 结 论

本文研究了劣质数据上代价敏感决策树的建立问题.首先对决策树、误分类代价、测试代价、检测代价和修复代价等相关概念进行了介绍,并对本文的研究问题进行了定义;然后,本文提出了3种融合数据清洗算法的代价敏感决策树建立方法;最后,本文通过大量实验验证了 3种方法的总代价、分类准确率和分类效率,并给出了不同情况下最优的代价敏感决策树建立方法.