王 鑫,陈建凯,翟俊海

(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等人提出的基于排序熵的单调决策树是目前处理连续值有序分类问题的有效方法之一。……