基于模糊优势互补互信息的有序决策树算法

王雅辉，钱宇华，3*，刘郭庆

（1.山西大学大数据科学与产业研究院，太原 030006；2.山西大学计算机与信息技术学院，太原 030006；3.计算智能与中文信息处理教育部重点实验室（山西大学），太原 030006）

0 引言

有序分类是一种特殊的分类问题，其样本的属性具有线性结构，类别取值D={ω1，ω2，…，ωc}之间存在偏序关系ω1≺ω2≺…≺ωc［1］。如在员工绩效考核问题中，将贡献度、技能水平、绩效作为绩效考核的3 个重要指标，其得分显然存在序关系；员工绩效考核的评定等级为“优秀，良好，合格，基本合格”，它们之间存在优劣次序。该问题的属性（贡献度，技能水平，绩效）与类别（评定等级）之间存在这样的单调性约束：当一名员工在贡献度、技能水平、绩效这3 个属性上的得分都高于其他员工时，该员工的评定等级一定高于其他员工。处理有序分类任务的关键在于从训练集中学习并生成单调的规则集，并利用属性和类别之间的单调依赖关系来指导样本的分类。有序分类问题在医疗诊断［2］、个人信誉评定［3］、欺诈公司判定［4］等许多领域都有广泛应用。

决策树算法是一种重要的分类和回归方法，具有分类速度快、准确率高、可读性强等特点，被广泛应用于医学诊断、数据挖掘等任务中。在决策树的构建过程中通常使用一个函数作为评价指标来选择和评估特征，根据选择的特征将每个节点中的样本划分为更细的子集。作为评价指标常用的函数有基尼指数（Gini index）、卡方系数、信息增益、信息增益比等。将传统的决策树算法应用到有序分类任务时存在以下两方面问题：

1）传统的决策树算法无法反映训练数据中的序结构。由香农熵计算得到的信息增益及信息增益比在著名的决策树算法ID3（Iterative Dichotomiser 3）及C4.5 中起着重要作用。实验表明，在构建决策树时，使用香农熵的变形及由香农熵诱导出的互信息作为选择特征的评价指标时的性能优于Gini 和Dependency 度量，但香农熵无法反映有序分类任务中训练数据的序结构，即给定一个单调的数据集，学习到的规则集可能是非单调的规则集。该结果限制了传统决策树分类算法在有序分类任务中的应用。

2）传统的决策树分类算法无法学习不精确知识。传统的决策树分类算法在假设样本的属性和类别取值确定的前提下，使用特征选择函数建立一棵清晰树。当对象类别划分不清晰时会引起模糊性、不确定性，在很多情况下，人类推理和概念构造的知识都是模糊而非精确的，具有精确特征描述的清晰决策树无法自动获取系统中的不精确知识。

针对上述问题，本文提出基于模糊优势互补互信息的有序分类决策树构建算法。Liang 等［5］提出互补熵的概念，互补熵的信息增益函数具有补集的性质，因此能全面反映信息系统的信息含量，同时互补熵是一个模糊熵，能够度量信息系统的随机不确定性和模糊性不确定性。本文使用由互补熵诱导出的互补互信息，由于互补互信息无法学习数据集中的序关系，本文将等价类转化为优势集，使用优势集表示数据集中的序结构，同时引入模糊集的计算，形成模糊优势集。在模糊优势集及互补互信息的基础上提出模糊优势互补互信息，并使用模糊优势互补互信息作为评价和选择属性的度量指标设计有序分类决策树算法。该算法能有效学习到数据集中的单调性规则集，并获取数据集中模糊不确定性知识。

1 相关工作

有序分类又称为单调性分类，或多标准决策分析［6］。目前，对有序分类问题的研究越来越受到学者们的重视，用于分类任务的粗糙集［7］、支持向量机［8］、神经网络［9］、集成决策树［10］等算法被改进后用于有序分类任务。Zhu等11］提出基于神经网络的有序分类算法，该算法是一个以单调关系为约束、以最小化训练误差为目的的二次规划方法。Cardoso 等［12］提出的large-margin方法将一个k分类问题简化为k个二分类问题，再使用支持向量机和神经网络对二分类问题进行求解。实验结果表明，上述方法对有序分类任务有效，但由于神经网络和支持向量机对领域专家来说很难理解，因此上述方法的可解释性较低。Tang等［13］假设相似度高的样本对具有相同的序关系，并以此来指导有序分类任务。Gonzalez 等［14］提出基于单调约束的集成剪枝算法，该算法的目的是在单调性模型的构建与分类精度间进行折中。Pinto Da Costa等［15］将k分类问题简化为k-1个二分类问题后使用一般的分类方法学习这些二分类问题，但该算法在建模过程中没有考虑单调性约束条件。

决策树归纳学习算法是一种分类速度快、高效且易于理解的学习方法，代表性算法有ID3［16］、CART（Classification And Regression Tree）［17］等。传统的决策树学习算法没有考虑单调性约束条件，因此对于给定的相同数据，可能会产生不同的决策树。基于以上问题，从单调数据集中提取单调的规则集已成为机器学习和决策分析领域的研究热点。很多学者针对决策树学习算法做出了改进，使其能够抽取数据中的单调规则集从而应用于有序分类任务中。Feelders等［18］提出了一系列剪枝技术，通过剪枝可以使非单调的决策树变成单调的决策树；Verbeke等［19］提出单调有序规则归纳算法，并与决策树归纳算法结合用于有序分类任务；Xia等［20］提出的Ranking Impurity方法将CART 中使用的基尼指数扩展到有序分类任务上。上述算法虽然可以从数据中提取序信息，但是给定一个单调的训练数据集时，构造出来的决策树依然不一定是单调的决策树。对于数值数据的有序分类问题，Hu等［21］提出单调决策树算法，该算法在香农熵的基础上引入序的关系提出排序熵的概念，在一定程度上解决了单调性和泛化能力之间的冲突。在排序熵的基础上设计了基于有序排序熵的单调决策树（Rank Entropy based Monotonic decision Tree，REMT）算法，该算法被应用于故障程度诊断［22］中。REMT 算法能学习到简单且易于理解的规则集，但得到的精度相对有限。许行等［23］设计采样策略来构造决策树算法，该策略考虑了数据集中的单调一致性的特点，可以避免非单调数据的噪声影响。

2 信息熵

香农引入热力学中熵的概念来度量一个系统的不确定性，香农熵及其变形被广泛用来度量信息系统的混乱程度，著名的决策树算法ID3、C4.5 都使用了香农信息熵作为特征选择的评价指标。香农熵定义如下：

定义1给定样本集U及属性集A，B⊆A是一个属性子集，得到一组等价类：U/IND={X1，X2，…，Xn}。关于属性子集B的互补熵定义为：

与香农熵使用对数变换不同，互补熵从信息增益的补集出发，能全面度量信息系统的信息含量。与香农熵类似，根据互补熵可以诱导出互补互信息的定义。互补互信息不仅度量了信息系统中两组等价类的一致性，还度量了两组等价类的补集的一致性。因此，互补互信息比由香农熵诱导出的互信息能更加全面有效地评估属性的重要性。互补熵和互补互信息的定义如下。

定义2给定样本集U及属性集A，B⊆A是一个属性子集，得到一组等价类：U/IND={X1，X2，…，Xm}。关于属性子集B的互补熵定义为：

其中：表示等价类Xi的补集；|Xi|/|U|表示等价类Xi在样本集U中发生的概率；||/|U|表示等价类Xi的补集在样本集U中发生的概率。

定义3给定样本集U及属性集A，B⊆A是一个属性子集，决策集D={Y1，Y2，…，Yn}，属性子集B和决策集D之间的互补互信息定义为：

3 模糊优势互补互信息

3.1 优势集

传统的决策树算法学习到的是数据集中的一致性，即具有相同属性取值的样本应分为同一类，而有序分类任务的分类器将拥有好的属性取值的样本分在好的类别中。从互补互信息的定义来看，其建立在等价类的基础上，对于含有顺序信息的信息系统而言，互补互信息无法学习数据集中的序结构并保持特征和类别之间的单调一致性，无法有效度量序信息系统的不确定性。因此互补互信息无法直接用于有序分类任务。优势粗糙集是处理有序分类问题的有效方法，可以从有序数据集中抽取有序的分类规则，因此，本文使用优势集表示数据中的序关系。优势集定义如下：

定义4给定样本集U及属性集A，x为样本集中的一个样本，a∈A是样本的一个属性，关于样本x的优势集定义如下：

下面使用例1来说明优势集的计算方法及作用。

例1 如表1 所示，给出10 个样本，a为样本的属性，决策集D={1，2，3}。以样本x4为例，根据式（4）和指示函数可以得到两个清晰的集合

表1 例1中十个有序分类样本Tab.1 Ten ordinal classification samples in example 1

3.2 模糊优势集

模糊数学是研究模糊现象的学科，所研究的事物概念本身是模糊而非清晰的，具有模糊性的概念无法用精准的标准来衡量，即一个对象是否属于这个概念难以确定，如不能用人的头发数量来划分“秃”与“不秃”。因此不能用取值为0～1的指示函数表示一个样本是否属于某个模糊集合。描述一个样本与模糊集合之间的关系时可以用［0，1］区间上的实数进行度量，即隶属度。隶属函数是用来表征模糊集合的数学工具，描述元素u与集合U上一个模糊集合的隶属关系。本文使用隶属函数对优势集进行计算，形成模糊优势集。模糊优势集定义如下。

定义5给定样本集合U及属性集A，xi为样本集中的一个样本，a∈A是样本的一个属性，关于样本xi的模糊优势集定义如下：

其中，rji和sji由隶属函数计算得到，所用隶属函数如式（6）所示：

rji和sji的计算方法如下：

使用模糊优势集表示数据的序关系时，不仅可以得到a(x) ≤a(y)或a(x) ≥a(y)，还可以得到a(x)与a(y)之间相差的程度。

例1中样本x4的模糊优势集合为：

3.3 模糊优势互补互信息

在互补互信息及模糊优势集的基础上，本文提出模糊优势互补互信息，模糊优势互补互信息定义如下：

定义6给定样本集U及属性集合A，B∈A，C∈A，则B和C的模糊优势互补互信息定义为：

使用下面的例子说明模糊优势集的作用及模糊优势互补互信息的有效性。

例2 给出5个样本进行有序分类任务，样本有a1和a2两个属性，属性a1取值离散，取值范围为{1，2，3}，属性a2取值连续，决策集D={1，2，3}，样本数据如表2所示。

表2 例2中有序分类任务Tab.2 Ordinal classification task in example 2

对于表2 中给出的数据样本，首先使用式（2）分别计算按属性a1和a2划分数据集时的互补熵：

通过计算可以得到E(a1；D)=E(a2；D)，说明若使用互补熵作为划分数据集的评价指标，则用属性a1或属性a2划分数据集的分类结果一样好。再使用式（8）分别计算属性a1和a2与决策集D之间的模糊优势互补互信息，计算结果如下：

从计算中得出FACMI>(a1；D) (a2；D)，说明若使用模糊优势互补互信息作为评价指标来指导数据集的划分时，使用属性a2来划分数据集的分类结果更好。使用模糊优势互补互信息作为评价指标，分别使用属性a1和a2划分数据集的划分结果图1所示。

图1 按属性a1或a2划分数据集Fig.1 Dividing dataset by attributes a1 or a2

从图1可以看出，根据属性a1划分数据集时，分类任务的准确率为80%，根据属性a2划分数据集时，分类任务的准确率为100%，说明使用属性a2划分数据集的结果更好，这符合使用模糊优势互补互信息的计算结果。使用模糊优势互补互信息作为评价指标来指导决策树的构建是有效的且效果优于使用互补熵作为评价指标的分类结果。

3.4 有序分类决策树的构建

本文对互补互信息进行了拓展，使用优势集来度量数据的序关系，并引入模糊集对优势集进行计算以形成模糊优势集，提出了模糊优势互补互信息。本节使用模糊优势互补互信息作为启发式来构建有序分类决策树，设计基于模糊优势互补互信息的有序决策树（Fuzzy Advantage Complementary Mutual Information based decision tree，FACMI）算法并分析算法的时间复杂度和空间复杂度。

3.4.1 FACMI算法

FACMI算法的伪代码如下。

FACMI 算法将模糊优势互补互信息作为分裂准则，节点选择划分数据集的分裂属性时，根据模糊优势互补互信息选择与类标签单调一致性高的属性，这样能够充分利用先验知识来生成更简单、泛化能力更强的树。

FACMI算法首先判断决策树当前节点中的样本个数和类别个数，若当前节点中只有一个样本或只有一个类别，则决策树停止生长，否则开始划分该节点：

1）计算现有特征对数据集的模糊优势互补互信息（FACMI），对每个特征Ai的每个可能取值cj计算Ai=cj时的模糊优势互补互信息。

2）在所有属性及其所有切分点中，选择FACMI 值最大的属性及其对应的切分点作为最优属性A及最优切分点c*，若属性A对数据集的模糊优势互补互信息FACMI(A)小于阈值threshold，则决策树停止生长；否则，根据最优属性及最优切分点将该节点的样本分裂到两个子节点中。

3）对两个子节点递归的调用步骤1）和2），直到满足停止条件时算法运行结束。

3.4.2 算法性能分析

FACMI 算法的时间复杂度和空间复杂度分为两部分，其中，N为数据集中的样本个数，M为样本属性个数，Split为所有属性取值个数的平均值，D为决策树高度：

1）时间复杂度。构建决策树的时间复杂度为O(NMD)，计算模糊优势互补互信息的时间复杂度为O(N2)。

2）空间复杂度。构建决策树的时间复杂度为O(N+M*Split)，计算模糊优势互补互信息的时间复杂度为O(N)。

4 实验与结果分析

为了验证本文提出的基于模糊优势互补互信息的有序分类决策树（FACMI）算法的有效性，分别在5个人工数据以及9个现实数据上进行实验，将FACMI 算法与经典的决策树分类算法进行比较。

实验设备为1 台配置为3.60 GHz-4 核GPU、8 GB 内存的计算机，实验平台为Matlab R2020a，实验参数threshold设置为0.01。

4.1 评价指标

本文实验在每个数据集上进行五折交叉验证，使用平均绝对误差（Mean Absolute Error，MAE）度量决策树算法的分类能力，MAE定义为：

其中：N表示测试集样本数量，yi表示样本xi的实际类标签表示样本xi在分类器上的预测类标签。

4.2 人工数据实验

本节实验测试FACMI 算法在人工数据集上的分类性能，使用式（10）［21］生成单调数据集：

其中：x1和x2为取值范围在[0，1]区间且满足均匀分布的两个随机变量，作为数据集的两个属性；将函数值f(x1，x2)归一化后进行离散化：D∈{0，1/k，2/k，…，1}，其中k为类别个数，由此得到k类单调分类问题。

4.2.1 人工数据集上样本数量对算法性能影响

本节实验使用人工数据集测试样本数量对FACMI 算法分类性能的影响，并与经典决策树算法CART、使用改进之前的互补互信息作为评价指标的决策树分类算法（Information Entropy，IE）以及有序决策树算法（Rank Tree，RT）［20］进行对比。所用数据集由式（10）生成，样本数量为1 000，类别个数k=4，其散点图如图2（b）所示。

图2 人工数据集Fig.2 Synthetic datasets

4.2.2 人工数据集上样本数量对算法性能影响

实验中随机抽取4～36个样本作训练集，保证每次抽取时4个类别的样本都能取到，其余样本作测试集。随着样本数量的增加，分别计算3个算法的平均绝对误差。实验重复100次，取绝对误差的平均值作为实验结果，实验结果如图3所示。

图3 人工数据集上的平均绝对误差Fig.3 Mean absolute errors on synthetic datasets

从图3 可以看出，在4 分类单调分类任务上，样本数量越多，各算法的分类误差越低，4 个分类算法的分类能力越接近，FACMI 算法始终获得最低的分类误差。样本数量越少FACMI 算法的优势越明显。实验结果表明FACMI 与其他算法相比能更好地反映数据中的序关系并指导样本分类。

4.2.3 人工数据集上样本类别数量对算法性能影响

本节实验使用人工数据集测试数据类别数量对分类器分类性能的影响。根据式（10）生成数据集，类别个数分别为k=2，4，6，8，10。使用生成的数据集分别在FACMI、CART、ID3、C4.5、使用改进前的互补互信息作为评价指标的决策树算法（IE）以及有序决策树RT 算法［20］上进行实验。将MAE 作为分类算法性能的评价指标。实验重复100次，取100次实验的平均MAE作为最终的实验结果，如表3所示。

表3 不同类别数量数据集上的平均绝对误差Tab.3 Mean absolute errors on datasets with different category numbers

从表3 中可以看出，在单调分类任务上，样本类别数量越多各算法的绝对误差越大。FACMI算法在不同类别数量的单调分类任务上的分类性能都优于其余算法，表明FACMI 算法在人工构造的单调分类任务上是有效的。类别个数为10 时，FACMI算法的分类误差与其余算法的分类误差相差最大。

4.3 现实数据集实验

除人工数据外，本文还在表4 所示的9 个数据集上验证FACMI 算法的有效性。9 个数据集中的数据收集于现实生活中的应用场景，能更好地测试FACMI 算法在现实应用问题中的泛化性能，其中，Diabetes、Segement、Squash 数据集来自Weka（https：//www.cs.waikato.ac.nz/ml/weka/），其余6 个为UCI（http：//archive.ics.uci.edu/ml/datasets.php）数据集。Car为符号型数据集，Diabetes、Segment、Balance 为既包含符号型也包含数值型特征的数据集，其余5 个为数值型数据。在构建有序分类决策树时，需要保持特征取值和决策集之间的单调一致性，即特征取值与决策集之间呈正相关。因此，在使用9 个现实数据集训练有序决策树之前，需要对数据集进行预处理，将单调递减的特征通过计算其取值的倒数转换为单调递增的特征。

表4 九个现实数据集的基本信息Tab.4 Basic information of nine real datasets

4.3.1 现实数据集上样本数量对算法性能的影响

本节实验使用现实数据集测试样本数量对FACMI 分类性能的影响。对每一个数据集取不同的样本个数，分别计算在FACMI、经典的决策树算法CART、ID3、C4.5、IE 以及RT 算法［20］上的平均绝对误差（MAE）。使用五折交叉验证，实验重复100 次，取平均MAE 作为最终的实验结果。实验结果如图4所示。

图4 不同样本数量在不同数据集上的平均绝对误差Fig.4 Mean absolute errors with different sample sizes on different datasets

从实验结果可以看出，在现实的单调分类任务上，随着样本数量的增加，6 个算法的平均绝对误差呈下降趋势，FACMI算法的误差始终低于其余5 个算法。样本量越少，FACMI 算法与其余5 个算法的误差相差越大。在Wine、Wine Quality、EEG 数据集上，各算法的分类性能相近，在Balance、Segment以及Squash 这5 个数据集上，FACMI 算法的优势更加明显。从图4 中可以看出，在Segment、Squash 数据集上，样本数量对FACMI算法分类性能的影响与其余算法相比相对较小。实验结果表明，FACMI算法在现实单调分类任务上是有效的。

4.3.2 现实数据集上算法性能

本节实验使用数据集中的全部数据测试FACMI 算法的分类能力，将FACMI 算法与经典决策树算法、RT 算法［20］及REMT（Rank Entropy based Monotonic decision Tree）［21］进行对比。使用平均绝对误差度量算法的分类性能。每个数据集中80%的数据用作训练集，其余样本为测试集，在每个数据集上进行五折交叉验证，实验重复100次，取平均MAE作为实验结果。7个算法在9个现实数据集上的分类误差如表5所示。

表5 九个现实数据集上的平均绝对误差Tab.5 Mean absolute errors on 9 real datasets

根据实验结果，在现实单调分类任务上，除Breast、Wine Quality、Segment 数据集外，FACMI 算法分类能力都优于其他算法。在Segment、Banlance、Car这3个数据集上，FACMI算法的损失明显低于其余6 个算法。每个数据集上分类能力最好的算法已用加粗突出显示。

4.4 传统非有序分类任务上算法性能

本节实验测试FACMI 算法在传统的非有序分类任务上的分类性能。使用表4 中未被单调化预处理过的9 个数据集作为非有序任务数据集，将FACMI 算法与传统决策树算法、RT算法进行对比。使用平均绝对误差度量算法性能，在数据集上使用五折交叉验证，取100 次实验的平均MAE 作为实验结果，如表6所示。

表6 非有序任务上的平均绝对误差Tab.6 Mean absolute errors of non-ordinal tasks

根据表6 中实验结果可以看出，除数据集Wine 和Wine Quality 外，FACMI 算法在其余数据集上取得最低的平均绝对误差。

对比表5和表6，FACMI算在非有序分类任务上的损失高于在有序分类任务上的损失，由此可得，相较于非有序分类任务，FACMI算法在有序分类任务上的性能更好。

4.5 结果分析

从上述实验结果中可以看出，在人工数据集和现实数据集上，本文提出的FACMI 算法的分类能力与其余算法相比相对较好。这是因为该算法考虑了特征取值与决策集之间的单调关系：不仅度量了特征与决策集之间的单调关系，还度量了每个特征取值的补集与决策集之间的单调关系，因此该算法从数据中获得了更多的先验知识。FACMI算法将样本的特征值模糊化后再处理，有利于学习数据中的不精确知识，获得更多的有效信息指导样本的分类。

5 结语

有序分类是决策分析中的一类重要任务，该任务利用从样本属性和决策集中学到的序关系来指导样本分类。高效且分类速度快的决策树算法在一般分类任务中应用广泛，决策树算法中评价指标的选择对决策树算法的性能有一定影响。许多决策树算法使用香农熵作为评价指标，但香农熵无法表示数据中的序关系且无法度量数据的模糊性，因此在有序分类任务上性能相较一般分类任务而言较差。互补熵能弥补香农熵非模糊熵的性质，本文使用由互补熵诱导出的互补互信息作为决策树评价指标，用优势集表示数据中的序信息，并引入模糊集将清晰树推广为模糊树，提出了基于模糊优势互补互信息的有序分类决策树算法。实验结果表明，该算法在有序分类任务上的分类能力优于经典决策树。在监督学习中，训练数据所对应的标签质量对于学习效果至关重要。如果学习时使用噪声标签，可能会训练不出有效的预测模型。但是由于人类认知限制、自然因素限制、成本限制等原因，噪声往往是不可避免的。在接下来的工作中，我们将考虑通过FACMI 算法与标签噪声过滤方法［22-24］相结合，以进一步提高FACMI算法的分类性能，增强分类器的鲁棒性。