王 鑫,陈建凯,翟俊海

(1.河北大学数学与信息科学学院，河北 保定 071002；河北省机器学习与计算智能重点实验室，河北 保定 071002)

1 引言

有序分类也称单调性分类[1,2]，有着广泛的应用，如医疗大数据的病情诊断、银行客户贷款信用等级评价、网络检索大数据排序分类等。它所处理的数据特点是：特征值和决策类别都存在序关系，并且特征值较好的样例决策不应该被分到相对较坏的决策类别当中。从函数角度来定义，单调性分类可以看成是1个多变量的单调函数[3]，即给定任意2个变量X1,X2，如果有X1≤X2，则有f(X1)≤f(X2)成立。

构建单调决策树是机器学习中处理有序分类问题的重要方法之一。2000年Potharst等人[2]提出了生成单调决策树的算法和非单调决策树修复算法，对于多决策K类线性分类问题，该算法能生成1棵单调决策树。2003年Cao-Van等人[4,5]在有序集上构建了决策树生长学习算法。后来Kamp 等人[6]提出了一种新的决策树学习算法—等分分类树(Isotonic Classification Trees)。2008年Xia 等人[7]在经典决策树CART(Classification And Regression Tree)的基础上，把序信息引入到分裂规则，将度量准则由基尼不纯度(Gini Impurity)改为了排序不纯度(Rank Impurity)，并用于有序分类问题。2009年Kotlowski等人[8]提出了一种带有单调约束的分类规则学习机。2010年Jimnez 等人[9]介绍了一种新的算法——POTMiner。针对以上算法的局限性，Hu等人[10,11]在2009年提出了排序熵、排序互信息RMI(Rank Mutual Information)的概念，2011年又提出了一种新的构建有序决策的算法—基于排序熵的决策树REMT(Rank Entropy based Monotonic decision Tree)[11]。后来，在Hu等人的工作基础上改进的一些单调分类算法得了到推广，如文献[12，13]所提算法。

综上所述，Hu等人提出的基于排序熵的单调决策树是目前处理连续值有序分类问题的有效方法之一。然而现实生活中有序分类的数据特征往往以区间值形式存在，比如医疗诊断问题中的治疗视网膜脱落。视网膜病人症状特征有网脱范围、网脱时间和裂孔大小，现实调查数据显示这3个特征取值都为区间值，且带有偏序关系，治疗后效果假如分“正常”“好转”2个等级，那么这个问题就是带有序信息的区间值属性分类问题，这种带有序关系的区间值属性分类问题在模式识别领域被称为“区间值属性单调分类问题”。虽然文献[14-17]中提出的一些用于处理模糊集和区间值属性的决策树归纳算法得到了广泛推广，但目前关于区间值属性的单调分类研究文献仍然相对较少。

文献[13]中提出的区间值属性单调决策树算法IVMDT(Interval-Valued attributes based Monotonic Decision Tree)，是处理区间值属性单调分类问题的重要途径之一，但此算法没有考虑属性间的交互信息对构建决策树的影响，因此很有可能过度分类没有意义或意义很小的冗余属性。针对以上不足，本文提出了一种改进算法，区间值属性的单调决策树扩展算法EIVMDT(Extended Interval-Valued attributes based Monotonic Decision Tree),该算法考虑了区间值属性间的交互信息，分析了属性间的冗余对构建决策树及分类结果的影响。扩展算法核心思想：选取扩展属性时，在要求条件属性与决策属性的排序互信息值最大的同时，还要求同一分支上已被选取的条件属性的排序互信息值最小，这样可避免同一条件属性的重复选择。实验结果对比表明了此算法的有效性。

2 基本概念和性质

2.1 单调分类

所谓单调分类就是带有单调性约束条件的有序分类[18,19]。它是有序分类问题的一种特殊的情况，即假设条件属性与决策属性之间存在一种单调性约束条件的关系。

既然是有序分类，应该用一定的符号来描述其中的序关系。令U={x1,x2,…,xn}为样本集合，A是描述样本的属性集，D是样本的有序决策集。可以定义样本xi在属性a∈A和决策集D上的取值分别记为v(xi,a)和v(xi,D)，并且样本集中的对象就属性a和决策集D的有序关系可以用“≤”或“≥”来表示。比如,假设有v(xi,a)≥v(xj,a)或者v(xi,D)≥v(xj,D)成立，则可以看成样本xi在属性a或者D上不比xj差，也可以记作xi≥axj或者xi≥Dxj。相应地，也可以将v(xi,a)≤v(xj,a)或者v(xi,D)≤v(xj,D)，记作xi≤axj或者xi≤Dxj。

定义1给定数据集DT=〈U,A,D〉，样本集U中的任意样本xi∈U，决策集合D={d1,d2,…,dn}(d1

定义2给定数据集DT=〈U,A,D〉，条件属性集B⊆A。如果对于∀a∈B，xi,xj∈U，有：v(xi,a)=v(xj,a)⟹v(xi,D)=v(xj,D)，则DT在B上是一致的。

定义3给定数据集DT=〈U,A,D〉，条件属性集B⊆A。如果对于∀a∈B，xi,xj∈U，有：xi≤axj⟹xi≤Dxj，则数据集DT在B上是单调一致的。

另外，如果数据集在B上是单调一致的，那么一定是一致的。

定义4给定数据集DT=〈U,A,D〉,B⊆A,定义下面的集合:

可以得到如下的性质：

2.2 排序熵和排序信息

定义5[10]给定数据集DT=〈U,A,D〉，属性集为A,属性子集B⊆A，关于属性集B的前向和后向排序熵[10]的定义分别如式(1)和式(2)所示：

(1)

(2)

定义6[10]给定数据集DT=〈U,A,D〉，B⊆A,C⊆A，B和C在U上的前向排序互信息和后向排序互信息定义如式(3)和式(4)所示：

(3)

(4)

本质上，排序互信息反映了属性集B和属性集C的单调一致程度。而排序互信息RMI≤(B,D)或RMI≥(B,D)能反映出属性集B和决策集D之间单调一致程度。

2.3 可能度

(5)

3 区间值属性单调决策树算法的改进

3.1 区间值属性间的排序互信息

在2个属性的数据集中，比较2个属性之间的前向有序互信息在不同噪声下的变化趋势。取4个数据集噪声占比分别为0,20%,40%,80%,其分布图和每个数据集上的RMI值如图1所示，文中“RMI”代表前向有序互信息计算结果。分布图是在二维特征空间中的散点图，x轴和y轴分别表示对象的2个属性。从图1中可以看出，数据集中数据越分散，其排序互信息的值越小，其单调一致程度越弱、相关性越差。连续值属性间的排序互信息可以度量出属性间相关性或单调一致程度[12]，同样对于区间值属性间的交互信息，也可以度量属性间的相关程度。首先根据定义9和定义10比较区间值属性取值的大小，然后依据定义6计算区间值属性间前向排序互信息，从而度量出区间值属性间的相关性或者单调一致程度。

Figure 1 Datasets distribution of monotonicity with different noises图1 不同噪声下数据集单调程度分布

3.2 扩展属性选取

理想情况下，对于单调分类问题来说，特征子集中含有的特征应该和决策类集之间满足高度单调一致性，并且和子集内的其余特征不相关。在此条件下，构建单调决策树选取扩展属性的准则是条件属性和决策类别间的排序互信息值最大化[12]，如定义11所示。

定义11给定数据集DT=〈U,A,D〉，A为属性集，其中A={a1,a2,…,am}，任意属性ai(i=1,2,…,m)的取值为连续值或区间值，cj为属性ai的备选割点。选取属性ai和D之间的前向排序互信息，其最优分割节点的计算公式如式(6)所示：

(6)

然而在实际分类问题中，特征之间往往存在一定的相关性，特征之间的冗余性往往较大，这样以上启发式算法在特征选取时，往往会继续分类一些没有意义或者意义极小的冗余属性，增大决策树的宽度(规则数)、深度，影响决策树的预测准确率，所以在选取扩展特征时，考虑条件属性间最小冗余就尤其重要。因为排序熵是信息熵的推广，排序互信息也可以度量2个属性间的相关程度[10]，所以基于排序熵的最小互信息计算公式如式(7)所示：

(7)

综合式(6)和式(7)所示的2种约束，可以得出基于排序熵的属性间最大信息最小冗余准则可定义为：

k∈N

(8)

基于以上考虑条件属性间的相关性，构建区间值属性单调决策树过程中，扩展属性选取的启发式改进如式(9)所示：

(9)

3.3 区间值属性单调决策树扩展算法的设计

EIVMDT算法可归纳如下：

算法1区间值属性的单调决策树扩展算法

输入：区间值属性集；对应决策集；停止准则(若节点属性排序互信息小于ε,则停止分裂)。

输出：决策树结构体。

(2)只有1个样本x或只有1种类别，停止生长。

(3)分裂节点(叶节点、根节点除外)生成规则步骤如下：

(3.2)样本xk(1≤k≤N)在属性ai上的端点值由小到大进行排序并求中值，记为排序后属性ai的分割点cj；

(3.3)For 属性ai的每一个分割点cj:

(3.6)根据最佳分裂点c∧进行分叉，重复步骤(3.1)～(3.5)，递归地构建二叉树。如果节点属性排序互信息小于ε，停止生长，分叉结束。

4 实验及结果分析

为了验证扩展算法的有效性，分别在人工数据集和UCI标准数据集上应用了上述扩展算法，并与IVMDT算法(β=0)进行了比较，得出结论：

(1)对于属性之间排序互信息极小的数据集，无论参数β取何值，构建的决策树都是一样的。例如，UCI库中Car数据集中有33个样本，6个属性，4个类别，其区间值属性间的交互排序信息几乎接近于0。

(2)其它绝大部分数据集，区间值属性之间的交互信息大小不一，其实验过程及结果分析如下。

4.1 人工生成数据集上的实验结果

实验首先在人工生成的数据集上进行，人工生成的数据满足一定单调性，首先利用以下函数生成连续值属性的单调数据集。

(10)

其中,p1,p2,…,pn为[0,1]上满足均匀分布的n个随机变量，作为数据集的n个属性。实验中设定n=10，g1=1.2,g2=1.3,…,gn=2.1。函数值f(p1,p2,…,pn)均一化后被打散到k个区间[0，1/k],[1/k,2/k],…,[k-1/k,1]，每个区间包含的样本数量基本相同，并且属于同一类别，这样就生成了1个k类单调性分类数据集。

接下来在以上方法生成的4组人工数据集上进行实验，每次抽取不同数量的数据作为训练样本，要求每次都取到不同类别的数据，其它的数据作为测试样本，人工实验数据集基本信息如表1所示。为了测试参数β(β∈[0，1])对构建决策树的影响，从步长为0.1的等差序列{0,0.1,…,0.9,1}中选取β值，使用不同的β值分别构建决策树，以决策树宽度(规则数)、平均深度(规则的条件数)及测试精度作为评价指标。实验结果如表2所示。

Table 1 Basic information of the artificial datasets表1 人工数据集基本信息

4.2 UCI数据集上的实验结果

选取了4个具有代表性的UCI数据集进行实验，数据集基本信息如表3所示。对以上数据集分别随机抽取70%的数据作为训练样本，30%作为测试样本，取不同β值，分别进行实验(当β=0时，EIVMDT退化为IVMDT)，实验结果如表4所示。其中，Leaf为规则数,AD为规则的条件数,TA为测试精度。

从实验结果(表2和表4)可看出，EIVMDT算法至少可以找到1个最佳参数β，使所构建出的决策树比原算法构建的决策树宽度更窄、平均深度更小、测试精度更高。即考虑了区间值属性间的交互信息后，能避免同一条件属性的重复选择，可构建出更精简、更高效的决策树。

综上所述，虽然对于不同的区间值属性数据集，条件属性间的冗余性或单调一致程度不同，但是总能找到1个合适的参数β，使得EIVMDT所构建的单调决策树在主要指标方面优于IVMDT的(参数β=0时，EIVMDT退化为IVMDT)。

5 结束语

构建区间值属性单调决策树是解决区间值属性单调分类问题的有效途径之一。本文在IVMDT算法的基础上，分析了区间值属性之间的相关性对扩展属性的选取影响，提出了一种改进的区间

Table 4 Experimental results on UCI datasets表4 UCI数据集上的实验结果

Table 3 Basic information of the UCI datasets表3 UCI数据集基本信息

值属性单调决策树扩展算法，实验分析及结果表明，该改进算法所构建的决策树规模更小，预测效果更优。

改进的启发式算法中，用参数β来调整最大信息最小冗余，但是不存在1个固定的β取值，使得在不同的数据集上，都能得出最佳结果。因此，针对不同的数据集，研究分析参数的敏感性问题是下一步工作重点。此外，算法主要针对单调性区间值属性分类，对于部分单调性区间大数据分类问题还需进一步探讨。