消除随机一致性的互信息及决策树算法

钱宇华 ，王川杭 ，王婕婷

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

在决策过程中，当缺乏足够的证据或详细的知识时，可能会进行逻辑欠缺的随机猜测，当这些随机猜测可能与实际情况形成一致性，这种一致性称为随机一致性［1］。在机器学习领域，随机一致性广泛存在于分类、聚类、识别等任务中，它的存在会影响学习系统的泛化能力，损害模型的公平公正性以及可解释性［2］，在随机猜测与真实情况的分布相同时，这些缺点尤为明显。因此消除学习模型中的随机一致性成为机器学习领域中非常重要的问题。

随着人工智能这一技术的不断发展，当前数据逐渐呈现出规模方向大，样本数量少、维数较高等特点，在此情况下，机器学习算法与理论都得到了飞速的发展与革新。目前，机器学习领域中的分类算法是数据挖掘等领域的重要研究课题之一，在实际情况中也得到了广泛的应用。作为分类中的决策特征指标，信息熵能够很好地量化随机变量的不确定程度，从信息熵导出的互信息度量能够量化特征相对于类别的不确定性程度，它在特征选择算法中有着广泛的研究及应用［3］，同时在特征质量评估的特征选择［4］、评估切割集的离散化［5］及图像匹配［6］等方面也取得了很好的效果。信息熵在ID3和C4.5等决策树分类算法中起着基础性的作用，这些算法被广泛地使用于各种分类决策任务中。虽然信息熵在特征选择中能够取得很好的效果，但它偏向于选择取值较多的特征，这阻碍了它进行最优的特征选择。为了对这一问题进行校正，人们提出了信息增益比［7］，然而有时信息增益比也会偏向于取值较少的特征，这同样也不利于算法进行最优特征的选择。因此减小决策过程中特征取值多少对特征评价结果的影响，提高分类的准确率成为一个重要的问题。

决策树分类算法是传统机器学习中一种常见的分类算法，因其理论相较完善、学习能力较强，在分类、预测及特征评价等领域得到广泛应用。决策树算法起源于国外，20世纪后期CART 算法［8］、C4.5 算法［9］、ID3 算法［10］相继被提出。近年来，国内外诸多学者对决策树进行了改进，Wang等［11］提出了一种新的分割特征选择方法以解决ID3算法中多值属性倾向和计算量大的问题，此方法不足之处在于未用于连续数据的处理。Zhang和Zhou［12］在保证低错误率的前提下，将决策树的节点尽量简化，以提高算法的效率，但智能算法的设计目的都是算法设计者的个人判断，这些方法依然未解决算法学习过程中的随机一致性。

本文从消除随机一致性的角度出发，使用消除随机一致性的互信息作为特征选择的指标，并在此基础上将该指标扩展到ID3决策树，提出消除一致性的决策树算法AID3算法（Adjusted ID3 Algorithm）。实验证明，使用AID3算法消除了决策过程中的随机一致性，同时提高了分类的准确率，具有较高的实用性和有效性。

正文部分安排如下：第1节描述了信息熵相关的基础知识及其缺点；
第2节描述了消除随机一致性的互信息及其与信息增益，信息增益比的对比；
在第3节中，提出消除随机一致性的决策树算法并通过实验比较和分析了信息熵和调整后互信息在ID3算法的差异；
最终意见和结论在第4节中提供。

信息熵是信息论中度量信息不确定性程度的重要方法［13］，常被用来作为一个系统的信息含量的量化指标，从而可以进一步用来作为系统方程优化的目标或者参数选择的判据，已经广泛应用于机器学习任务中。文献［14］详细介绍了信息熵、信息增益及信息增益比等基础知识。

定义1 设Z是一个有限取值的离散随机变量，其概率分布为：

则随机变量Z的熵定义为：

信息熵是表示随机变量不确定性的度量，它首先定义了事件提供的信息量：事件发生的可能性越低，事件能提供的信息就越多［15］，熵越大，随机变量的不确定性就越大。

定义2 条件熵H（Z1|Z2）表示在已知随机变量Z2的条件下随机变量Z1的不确定性。随机变量Z2给定的条件下随机变量Z1的条件熵H（Z1|Z2），定义为Z2给定条件下Z1的条件概率分布的熵对Z2的数学期望：

当信息熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的信息熵与条件熵分别称为经验熵和经验条件熵。

定义3 特征A对训练数据集D的信息增益g（D，A），定义为集合D的经验熵H（D）与特征A给定条件下D的经验条件熵H（D|A）之差，即：

信息增益表示了属性之间的依赖程度，也就是属性之间的相关性。信息增益越大，条件熵 H（Z1|Z2）越小，属性 Z1和Z2相关性越小，当属性Z1和Z2相互独立时，条件熵H（Z1|Z2）等于零，信息增益最大。

定义4 设特征A有n个不同的取值｛a1，a2，…，an｝，根据特征A的取值将D划分为n个子集 D1，D2，…，Dn，|Di|为 Di中的样本个数。特征A对训练数据集D的信息增益比gR（D，A）定义为其信息增益g（D，A）与训练数据集D关于特征A的值的熵HA（D）：

n为特征A的取值个数。|D|表示训练数据集的样本容量，即样本个数。

定义5 设随机变量（Z1，Z2）的联合分布为p（z1，z2），边缘分布为 p（z1），p（z2），互信息 I（Z1，Z2）为联合分布 p（z1，z2）与边缘分布 p（z1）p（z2）的相对熵。

互信息也是用来衡量两个数据分布的吻合程度，反映了分类任务中的一致性。一般地，信息熵 H（Z1）与条件熵H（Z1|Z2）之差也称为互信息。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

使用信息增益作为特征评价指标，评价结果往往会偏向于选择取值较多的属性，而这些属性未必是最佳分类属性。虽然信息增益比能够对这一问题进行校正，由于C4.5并不是直接选择增益率最大的属性作为划分属性，而是之前先通过一遍筛选，把信息增益低于平均水平的属性剔除掉，之后从剩下的属性中选择信息增益率最高的，这样的话，相当于两方面都得到了兼顾。但有时信息增益比会偏向选择取值较少的属性，这也会影响特征选择的平均准确率。

为了消除信息增益在特征选择过程中的随机一致性，改进信息增益多值偏向的问题，本文引入调整互信息AMI（Adjusted Mutual Information，以下简称AMI）作为新的特征评价指标进行决策过程。

在聚类中，对于随机结果，互信息（Mutual Information，以下简称MI）并不能保证分数接近零，即对聚类结果的区分性不强，在聚类结果较差时MI依然能达到较高数值。为了实现“在聚类结果随机产生的情况下，指标应该接近零”，AMI被提出，它具有更高的区分度［16］。

2.1 调整互信息AMI

表1 混淆矩阵Table 1 Confusion matrix

文献［17-18］详细介绍了AMI的计算过程，首先给出调整互信息AMI的计算公式：

式中MI（D，A）表示数据样本集D与属性A之间的互信息，E［MI（D，A）］表示互信息的期望值。调整互信息从原本的互信息中减去期望值，再除以上界使得整个值归一化，其定义类似于聚类中调整兰德指数［16］。互信息为衡量随机变量之间相互依赖程度的度量，在分类中，有时即使两个变量的信息吻合程度较低，但互信息依然较高，导致分类结果不准确。调整互信息的作用在于能够更加准确分类，其取值范围为［-1，1］，值越大意味着分类结果与真实情况越吻合。

其次给出互信息MI（D，A），互信息的期望值 E［MI（D，A）］以及互信息最大值 max［MI（D，A）］的计算过程：

如表1所示，基于混淆矩阵，A的信息熵可表示为：

所有可能的决策特征与类标签之间的平均互信息值实际上是在相关联的表1的集合上的期望值：

其中∑nkm(·)表示遍及nkm所有可能的值，P{M|nkm，d，a}代表在所有随机广义超几何分布下以d和 a为边缘，第（i，j）项为 nij的表1的联合概率。

同时n服从参数为（N，dk，am）超几何分布，所以有：

2.2 AMI与信息增益的比较

为了验证AMI的有效性，给出例1和例2。

例1 表2给定了10个样本，每个样本都用两个属性A1和A2来评价，并对每一个样本做出决策。

表2 信息增益特征选择样例Table 2 Examples for feature selection of information gain

首先计算使用信息增益作为特征评价标准来选择最优特征。

对于训练数据集D，先计算经验熵H（D），由公式（2）有：

选择A1作为测试属性后，由公式（5）该属性对数据集D信息增益为：

选择A2作为测试属性后，由公式（5）该属性对数据集D信息增益为：

由于 g（D，A1）＞g（D，A2），因此选择特征A1作为最优特征进行分类。

使用信息增益作为特征选择标准对样本数据集进行分类，会选择特征A1作为分类特征，但此时样本分类正确率为70%。

然后计算使用AMI作为特征评价标准来选择最优特征。

计算属性A1对数据集D的AMI（D，A1）：

此时A1对应的混淆矩阵见表3。

表3 特征A1所对应混淆矩阵Table 3 Confusion matrix corresponding to feature A1

由公式（10），（14），（19）有：

计算属性 A2对数据集 D 的 AMI（D，A2）：A2对应的混淆矩阵见表4。

表4 特征A2所对应混淆矩阵Table 4 Confusion matrix corresponding to feature A2

由公式（10），（14），（19）有：

由于 AMI（D，A1）＜AMI（D，A2），因此选择特征A2作为最优特征进行分类。

使用AMI作为特征选择的指标，将选择A2作为分类特征，此时分类准确率为80%。AMI消除了特征决策过程中的随机一致性，解决了信息熵的多值偏向问题，提高了分类的准确率。

2.3 AMI与信息增益比的比较

例2 表5给定了10个样本，每个样本都用两个属性A1和A2来评价，并对每一个样本做出决策。

表5 信息增益比特征选择样例Table 5 Examples for feature selection of information gain ratio

首先计算使用信息增益比作为特征评价标准来选择最优特征。

对于训练数据集D，先计算经验熵H（D），由公式（2）有：

由公式（7），数据集D关于特征A1的值的熵HA（D）为：

由公式（6），A1对数据集D信息增益比gR（D，A1）为：

选择A2作为测试属性后，由公式（7）有数据集D关于特征A2的值的熵HA（D）为：

由公式（6），A2对数据集D信息增益比gR（D，A2）为：

由于 gR（D，A1）＜gR（D，A2），因此选择特征A2作为最优特征进行分类。

使用信息增益比作为的特征选择标准会选择特征A2作为分类特征，但此时样本分类正确率为80%。

然后计算使用AMI作为特征评价标准来选择最优特征。计算属性A1与数据集D之间的AMI（D，A1）：A1对应的混淆矩阵见表 6。

表6 特征A1所对应混淆矩阵Table 6 Confusion matrix corresponding to feature A1

由公式（10），（14），（19）有：

计算属性 A2对数据集 D 的 AMI（D，A2）：A2对应的混淆矩阵见表7。

表7 特征A2所对应混淆矩阵Table 7 Confusion matrix corresponding to feature A2

由公式（10），（14），（19）有：

由于 AMI（D，A1）＞ AMI（D，A2），因此选择特征A1作为最优特征进行分类。

使用AMI作为特征选择的指标，将选择A1作为分类特征，此时分类准确率为90%。AMI消除了特征决策过程中的随机一致性，解决了信息增益比偏向属性取值少的问题，提高了分类的准确率。

3.1 ID3算法及AID3算法

ID3（Iterative Dichotomiser 3）算法是一种决策树的分类算法，由Quinlan于1986年提出，该算法采用自顶向下的贪婪搜索策略遍历可能的决策空间，且不会回溯及再次考虑之前的选择。Quinlan以香农的信息论为基础，将信息熵作为选择测试属性的指标，构造决策树对训练数据集进行分类并对整体样本数据集进行预测分类。ID3算法的核心是在生成决策树时使用信息增益（即平均互信息量）作为训练样本集合的分裂度量标准。就得到如下的ID3算法生成决策树的基本步骤［14，20］：

输入：训练数据集D，可用于归纳的候选特征集attribute_list；

输出：决策树T；

1）创建一个结点N；

2）若该节点的所有样本都属于同一类C，则返回N作为叶结点并标记类别C，开始的根结点应用于所有训练样本并返回T；

3）若attribute_list为空，则返回N作为叶结点，并将该结点标记为其样本包含最多类别的类型，此时T为单结点树，返回T；

4）否则，从attribute_list中选择具有最大信息增益的特征test_attribute，用该特征标记结点N并返回T。

5）对于test_attribute的每一可能值ai，将结点N中包含的样本集分割，标记分割后的样本集中实例数最大的类，构建子节点，开始的根结点及子节点应用与所有训练样本，返回T；

6）s是在test_attribute=ai的条件下获得的样本集，若s为空，则用包含最多样本类型的类别标记相应的叶结点。否则将用返回值标记；

7）算法递归调用步骤1）～6），对剩余各子集继续进行划分，并生成新的决策树分支。

ID3算法使用信息增益选择测试属性会出现多偏向的问题，本文引入AMI，将原算法中的信息增益替换为AMI作为训练样本集合的分裂度量标准，并使用相同的算法结构提出消除随机一致性的决策树算法AID3算法（Adjusted ID3 Algorithm）。

3.2 决策树算法流程

使用决策树算法进行分类的流程图如图1所示。

图1 决策树算法流程图Fig.1 Flowchart of decision tree algorithm

算法说明：

1）数据预处理包括连续属性离散化和缺失值填充等环节。

2）算法是一个不断递归的过程，递归的终止条件为：结点内所有的样本均属于同一类别。整个过程通过不断选择测试属性，分裂训练样本数据集，生成结点，标记结点，再将结点加入决策树，最后输出决策树。

3.3 样例分析

如表8所示，样本数据集分别使用四个属性：穿衣指数、温度、湿度、风力来对天气舒适度进行划分，这四个属性将天气舒适度划分为分为舒适（正例）和不舒适（反例）两类［21］。

表8 样本数据集Table 8 Sample data set

下面分别采用ID3算法和AID3算法对样本数据集进行分类。

使用ID3算法对样本训练集进行分类，可得决策树如图2。由图2可以看出，ID3算法首先选择穿衣指数作为根节点的分类属性。但日常人们的穿衣指数是一种非常个性化的指标，与个人的实际情况有很大关系。如一般情况下身体虚弱的人会比健康的成年人穿得多一点，所以穿衣指数能够在一定程度上反映天气舒适度，但并不能成为决定天气舒适度的重要因素，即穿衣指数这一指标并不是决定天气舒适度最重要的分类属性，所以需要降低穿衣指数在分类中的权重，提高剩余特征即温度、湿度、风力在分类中的权重［17］。

图2 ID3算法生成的决策树Fig.2 Decision tree generated by ID3 algorithm

AID3算法得到的决策树如图3所示。相比图2及图3的决策树，ID3算法选择穿衣指数这一特征作为根节点的决策特征，但很明显穿衣指数这一特征的在分类过程中所占权重低于其他属性，这正是信息增益偏向取值较多特征的体现。而AID3算法进行分类时，降低了穿衣指数这一特征在分类中的所占权重，相对提高了其他特征：温度、湿度和风力在分类中的所占权重。这很好地解决了信息熵偏向于选择取值较多特征的缺点，并且与实际情况比较符合，进一步达到了预期的目的，得到了更加合理有效的分类规则。

图3 AID3算法生成的决策树Fig.3 Decision tree generated by AID3 algorithm

3.4 实验设置

实验选择UCI数据集中的9个分类数据集来验证算法的有效性，9个数据集的详细信息描述如表9所示。使用训练集建立决策树分类器，在每个数据集上进行50次实验对比，以此考察算法的平均性能，同时使用方差统计每种方法之间的稳定性，方差越小说明算法取得的性能值越好。

表9 实验数据集描述Table 9 Description of experimental data sets

3.5 实验结果及分析

实验过程中，ID3的训练时间复杂度为O（DMlog2N），其中N为训练集大小，M为样本集维度，D为树的分裂次数，AID3的训练时间复杂度为O（Mlog2N），AID3算法的时间复杂度低于ID3算法。图4表示在样本量分别为200，400，600，800，1000时不同算法在不同数据集的分类准确率。表10表示在相同的划分下即样本量都为1000时四种决策树算法在9个数据集上分类准确度的对比。表11表示各决策树算法的方差。

图4 不同算法的准确度对比Fig.4 Comparison of accuracy of different algorithms

表10 不同算法的准确度比较（%）Table 10 Comparison of accuracy of different algorithms（%）

表10与表11的数据表明，在9个数据集中使用AID3算法相对ID3算法、C4.5算法以及CART算法分类正确率整体提高，最多相较ID3算法提高了4.112%；
同时使用AID3算法进行分类整体方差都小于其他决策树分类算法。整体而言，AID3算法相较于其他决策树分类的方法，能够更好地消除随机一致性，取得较高的分类准确度。

表11 不同算法的方差比较Table 11 Comparison of variance of different algorithms

本文使用调整互信息作为消除随机一致性的特征决策指标，在一定程度上克服了信息熵的多值偏向问题。同时基于调整互信息的决策树不仅提升了传统ID3算法的性能，相比于其他的决策树算法，较好地提升了分类的准确度。在未来的工作中，还将进一步从理论上分析AMI解决多值偏向的原因。

猜你喜欢 互信息信息熵决策树 基于信息熵可信度的测试点选择方法研究军民两用技术与产品(2022年1期)2022-06-01一种针对不均衡数据集的SVM决策树算法成都信息工程大学学报(2019年3期)2019-09-25决策树和随机森林方法在管理决策中的应用电子制作(2018年16期)2018-09-26基于改进互信息和邻接熵的微博新词发现方法计算机应用(2016年10期)2017-05-12一种基于信息熵的雷达动态自适应选择跟踪方法雷达学报(2017年6期)2017-03-26基于决策树的出租车乘客出行目的识别中央民族大学学报（自然科学版）(2016年4期)2016-06-27基于互信息的贝叶斯网络结构学习北京信息科技大学学报(自然科学版)(2016年6期)2016-02-27联合互信息水下目标特征选择算法西北工业大学学报(2015年4期)2016-01-19基于增量式互信息的图像快速匹配方法弹箭与制导学报(2015年1期)2015-03-11基于信息熵的循环谱分析方法及其在滚动轴承故障诊断中的应用振动工程学报(2015年1期)2015-03-01