具有强化学习策略的决策树算法

于安池,储茂祥,杨永辉,董 秀

(1.辽宁科技大学 电子与信息工程学院,辽宁 鞍山 114000;2.烟台汽车工程职业学院 汽车工程系,山东 烟台 265500)

随着大数据时代的来临,技术的不断提升,各领域对数据的处理要求越来越高。对于医疗、银行等领域,不平衡数据的研究尤为重要。决策树[1]作为数据挖掘领域的重要算法之一,具有效率高、只需要一次构建、可反复使用、每一次预测的最大计算次数不超过决策树深度的优点,但是决策树在处理各类样本数量不平衡的数据集时,特征选择标准偏向样本数目更多的特征,导致负类的分类准确率降低。

在对不平衡数据进行分类时,主要存在的问题是数据集本身的不平衡性和传统决策树算法的局限性。数据层面体现在数据集样本数目的不平衡。对于一些情况而言,负类包含的信息更为重要,分类器不能够充分训练负类样本,造成负类的准确度下降。在算法层面,分类器为了使准确率最大,会误分更多的负类样本,牺牲了负类的分类准确度。国内外的学者对于不平衡数据的分类问题做了大量改进。文献[2]针对不平衡数据的处理方法进行了总结和整理,主要分为在数据层面、特征层面和算法层面的改进方法;文献[3]通过提高负类权重的方法,将代价敏感与属性选择标准相结合,提出一种代价敏感决策树方法;文献[4]提出C4.5+δ、均匀分布熵和改进分布熵函数3种针对不平衡数据的改进决策树方法;文献[5]提出基于区间值属性的单调决策树;文献[6]在建立代价敏感决策树的基础上对劣质数据进行清洗;文献[7]采用级联的思想,将多个AdaBoost决策树集成,组合成级联决策树;文献[8]提出一种基于欧式距离计算距离权值的改进C4.5算法;文献[9]将犹豫模糊集理论与决策树算法结合,提出一种改进的模糊决策树算法。

综上所述,将强化学习方法引进决策树算法的研究很少。文献[10]提出一种基于强化学习累积回报策略的改进决策树算法,取得了很好的效果。但是,该方法使负类在属性选择时提高权重,会牺牲掉一部分正类的准确度。本文借鉴强化学习中马尔可夫决策过程,对决策树算法进行优化,通过标准化互信息和马修斯相关系数2个平衡的评价指标加权,对决策树每次的分裂过程进行奖励,刺激它获取更大的奖励。。

1 C4.5算法原理

决策树是一种采用贪心算法,自上而下递归构造的类似于流程图的树结构,每一个从根节点到叶子节点的分支为一种分类规则,其内部节点为选择的特征,叶子节点存放的是类标号。决策树常用的算法有ID3算法、C4.5算法等。C4.5算法具体步骤如下:

(1)设S为样本集,样本个数为n,样本集S中有m个类别Dj(j=1,2,…,m),dj为Dj类的样本个数。则数据集的类别信息熵Ent(S)表示为:

(1)

(2)设特征a有k个离散值{a1,a2,…,ak},根据特征a的离散值将数据集D分成k个子数据集{S1,S2,…,Sk},其中Si是S中特征为aj的数据集。如果特征aj被选为当前节点,那么用特征aj对当前样本进行划分。Sij为子集Si中属于Dj类的个数,则按特征aj划分数据集的条件信息熵为:

(2)

(3)由(1)式和(2)式可得,特征A划分前后的信息熵之差为信息增益,表达式为:

Gain(S,A)=Ent(S)-Ent(S|a)

(3)

(4)按照特征A划分后的信息增益率为:

(4)

其中特征A的分裂信息为:

虽然C4.5算法具有很多的优势,但是在处理不平衡数据上仍有不足,当数据集不平衡时,为了更高的准确率,信息增益率在选择特征时会偏向数据更多的类别,而在一些情况下如医疗诊断、电信诈骗等,负类的信息往往更为重要。

2 基于强化学习策略的改进

传统的C4.5算法选用信息增益率作为特征选择的标准,而面对不平衡数据集时,选择结果会偏向正类,造成负类分类精度降低,然而这些负类往往更为重要。如果有监督学习希望分类器正确地对实例分类,那么强化学习的目标是每一个行动都要为最终的目标——最大化长期回报努力,即获得最多的累计奖励。强化学习模型主要包含状态、动作、行动和奖励4个元素。与一般的马尔科夫过程不同,马尔科夫决策过程考虑了动作,即系统下一个状态不仅和当前的状态有关,也和当前采取的动作有关。根据马尔可夫决策过程量化每一个特征对实现最终目标贡献的价值,这个过程就是使负类样本被正确分类时实现价值最大化。这个过程用价值函数来衡量,本文将价值函数和信息增益率相结合作为新的特征选择策略,并对每一层决策树的价值函数进行计算,使得决策树达到最优化。

2.1 价值函数

为了解决不平衡数据的分类问题,本文引入2个价值函数:

(1)标准化互信息[11-12](Normalized Mutual Information,NMI)可以用来衡量预测结果与真实结果的相似度。NMI通常用于检测网络划分结果与真实划分结果之间的差异,并计算正确率。互信息提供的是特征和类别之间的绝对信息量,不能真实反映特征集相对于类别集整体的表达能力,这是因为它在实践中随着特征集和类别集的自身规模变化而变化。NMI针对H(X)和H(Y)的整体大小进行标准化处理,以消除H(X)和H(Y)大小的影响,使其能精确的反映出这些变化。

(2) 马修斯相关系数[13](Matthews Correlation Coefficient,MCC) 主要用于衡量二分类问题,其综合考虑了混淆矩阵大小的比率得分。它是一个比较均衡的指标,对于样本不平衡情况下也可以使用。MCC的取值范围在[-1,1],取值为1表示预测的结果与实际结果完全一致,取值为0表示预测的结果还不如随机预测的结果,-1表示预测结果与实际的结果完全不一致。可以看出,MCC本质上是描述预测结果与实际结果之间的相关系数。

这2个价值函数都是平衡指标,用来提高负类的权重,使负类的准确率提高。

2.2 特征选择标准

传统的决策树构造方法都是在决策树完全构建好后再对其分类效果进行评价的。为了获得高的准确率,传统决策树的结果会偏向样本数多的类别。为此,本文将强化学习的思想引入,每个特征的标准化互信息和马修斯相关系数加权,并与信息增益率相结合作为新的特征选择标准AS。

(1)设2个类别(X,Y)的联合分布为p(i,j),即各类别判断正确的样本数占总样本数的概率;设边缘分布分别为p(i),即在预测结果中各类别样本数占总样本数的概率;设互信息MI(X,Y)是联合分布p(i,j)与边缘分布乘积p(i)p(j)的相对熵。

(5)

(6)

(2)设TP为真负类的数量,TN为真正类的数量,FP为假负类的数量,FN为假正类的数量。根据混淆矩阵得出CMCC为:

(7)

其中:N为样本个数;W=(TP+FN)/N;V=(TP+FP)/N。

(3)根据(6)式、(7)式,可以得到一个新的价值函数f:

f=ωCMCC+(1-ω)CNMI

(8)

其中,ω为权重。

(4)新的特征选择标准AS定义为:

AS=(2Gain-ratio-1)f

(9)

改进后算法的基本流程如下：

(1)输入训练集S,特征集A。

(2)若S=∅,则返回决策树T。

(3)若训练集S中所有样本都属于同一个类别,则T为单节点树,并将该类别作为该节点的类标记,返回T。

(4)若特征集A为空集,则T为单节点树,并将S中样本数最多的类别作为类标记,返回T。

(5)根据(9)式计算S中各特征的AS,选择AS最大的特征,作为该节点的分裂特征。

(6)对于第i个节点,将作为新的训练集,对当前特征以外的特征进行递归调用步骤(2)～步骤(5)。

(7)输出决策树T。

改进后决策树算法流程如图1所示。

图1 决策树改进算法流程

3 实验结果及分析

3.1 实验数据

本实验采用UCI公开数据集中7个不平衡的数据集进行测试,见表1所列。本文实验平台为Matlab R2016b。

表1 实验数据集

3.2 实验结果

本文分别对传统的C4.5算法、基于强化学习改进的C4.5算法(CRDT)以及本文提出的基于马尔可夫决策过程的MCC决策树算法和NMI决策树算法进行测试,分别比较预测的负类准确率、正类准确率以及总体准确率。对比结果分别见表2～表4所列,如图2～图4所示。

图2 负类准确率对比

图3 正类准确率对比

图4 整体准确率对比

表2 负类准确率

表3 正类准确率

表4 整体准确率

本文测试的基于标准化互信息的改进决策树算法和基于马修斯相关系数的改进决策树算法的效果不太稳定。对于数据集2、4、6、7,MCC方法在保证整体准确率的基础上,提高了负类的准确率。数据集为3、5时，NMI方法对于负类准确率提升效果更好。与以上2种方法比较,将2个价值函数加权后的改进决策树算法效果最好。

将本文加权后的改进决策树算法与传统的C4.5算法和基于强化学习的改进决策树算法比较,这种算法对于负类的分类效果以及整体的分类效果均有显著提高。由于提高了负类在分类中的权重,导致数据集1、2对正类的分类效果有所下降。综上所述,本文改进后的决策树算法对于不平衡数据的分类效果比原有算法有所提升。

4 结 论

本文针对不平衡数据分类精度不高的问题,提出了一种基于马尔可夫决策过程的决策树算法。通过标准化互信息和马修斯相关系数2个平衡的价值函数加权,使负类的权重提高。利用当前状态的价值函数作为下一个状态的属性选择标准,对决策树算法进行优化。对比实验结果,非平衡数据的负类分类准确率及整体准确率均得到显著提高。今后将进一步研究新算法的工作效率,并将算法推广到实际应用。