不完备数据集的邻域容差互信息选择集成分类算法

李丽红 ,董红瑶 ,刘文杰 ,李宝霖 ,代 琪

（1.华北理工大学理学院，唐山，063210；2.河北省数据科学与应用重点实验室，华北理工大学，唐山，063210；3.唐山市工程计算重点实验室，华北理工大学，唐山，063210；4.华北理工大学人工智能学院，唐山，063210；5.中国石油大学（北京）自动化系,北京，102249；6.首钢矿业公司职工子弟学校，唐山，064404）

在大数据时代，数据具有不确定性、动态更新、不完备性等特点.其中，数据挖掘领域常用的UCI 数据库中有40%左右的数据集是不完备的.针对不完备数据集的分类问题，可以通过简单删除法或者填充法将不完备数据集进行处理，再用完备的数据集做进一步的分类，但这种方法不能保证数据是否为随机缺失，从而对分类精度产生影响［1］.尽管近年来对不完备数据集的研究逐渐增多，但目前不完备数据集中的大部分分类算法是针对只含有离散属性值的数据集设计的［2］.然而，有一种常见的情况是数据集为既含有离散型属性又含有连续型属性的混合形式，如从商业、医疗、银行、人口普查和生物科学中收集的数据，都是混合型的.对于医学数据，除了血压和血糖等连续型属性外，还包括性别和是否对某种药物过敏等离散型属性，人口普查收入数据包括职业、教育水平和婚姻状况等离散型属性，以及年龄、工资和每周工作时间等连续型属性.针对连续型属性值通常采用离散化的计算方式将连续型数值直接转化为离散型数值，这样会带来信息损失，从而影响分类准确率［3］.所以学者提出了直接处理不完备混合型数据集的方式，如利用相容关系［4］、限制邻域关系［5］和邻域容差关系［6］等，不同的数据结构采用不同的逼近机制和粒化方式构建粒空间再进行下一步数据操作［7］.对于不完备混合型信息系统的分类问题，为进一步提升其分类性能，将集成分类方法引入研究.

目前针对不完备混合型信息系统的集成分类算法研究较少.Krause and Polikar［8］首次提出Learn+MF 集成算法处理不完备数据集的分类问题，子分类器在随机特征子集上进行训练，这种方法相对复杂，效率较低.因为集成分类算法针对不完备数据集的分类问题具有较好的冗余性而且适用性广，它不会因为对数据集假设不当使最终构建的模型产生偏差，而且可以充分利用数据集的信息，所以，用集成算法处理不完备数据集的问题相继被提出［9］.Chen et al［10］与吕靖和舒礼莲［11］提出一种基于不完备数据集的不完备特征组合的集成框架，该方法不需要任何关于缺失数据的假设，但没有考虑不同特征子集重要程度的差异.在一般集成框架的基础上，通过考虑特征重要度，提出了多粒度集成方法（Multi-Granularity Integration Method，MGNE）［12］，然而，对于含有大量不完整样本的数据集，该方法性能有待提高，同时，随着缺失值数量的增加，这些算法非常耗时.为克服传统集成学习技术的高计算成本的不足，集成剪枝是一种常见提升性能的方法［13-15］.Yan et al［16］针对不完备数据集提出一种选择性神经网络集成分类算法，与传统神经网络集成算法在保证精度的前提下相比，提高了算法效率.并且针对不完备混合数据集的分类问题，传统的集成分类算法在赋予各个子分类器权重时，仅考虑数据集中所含样本的多少和属性的维数，并没有考虑不同属性或属性组合对最终分类结果的贡献度.因此，如何有效地衡量不完备混合系统中属性对分类结果的贡献度，从而更加合理地计算基分类的权重提高分类的准确率有待进一步完善和解决.

针对上述问题，根据当前利用集成分类算法和粗糙粒化思想处理不完备混合数据的不足及优势，本文提出基于邻域容差互信息的选择集成分类算法（Neighborhood Tolerance Mutual Information Selection Ensemble Classification Algorithm，NTMISECA）.首先定义邻域容差互信息，并详细描述基于邻域容差互信息选择集成分类算法的思想和步骤，然后介绍验证该算法采用的实验数据的详细信息与仿真环境，最后对实验结果进行讨论和总结以及阐述未来研究的工作重点.

1 基本原理

1.1 不完备混合型信息系统

定义1［17］设一个混合型信息系统为S=(U，A).其中，U为信息系统的论域，A=C∪D称为信息系统的属性集合，C=Cd∪Cc称为信息系统的条件属性集合，D称为信息系统的决策属性集合.这里的Cd为条件属性值是离散型数值，Cc为条件属性值是连续型数值.

若∃x∈U，x在属性a(a∈A)上的取值未知，通常用“*”表示，即a(x)=*，那么此时S称为不完备混合型信息系统.

1.2 粒计算粒计算主要目的在于通过对问题的粒化分解，使复杂问题得以简单处理，体现问题处理的多维度、多视角、多层次的思想［18］.通过研究粒的产生、粒的性质以及粒化方式，提出数据处理的数学方法，支撑模型的建立，实现计算机程序化处理.

一个本质性问题是基于粒计算理论对信息进行粒化，不同的粒化方法可以获得不同的粒层信息，粒空间的结构直接决定目标的求解效率.常用的粒化方法依据二元关系，如等价关系、相似关系、领域关系、优势关系等，同一类样本分配到同一个信息粒中［19-23］.一般地，存在两类造粒过程，如功能造粒和关系造粒.如果该构造过程完全基于样本属性，称为功能粒化；如果粒化过程基于样本之间的关系，称为关系粒化.在粒化过程中，若给定多个不同的粒化规则，从多角度、多层次可以得到各不相同的粒层.本文针对不完备混合数据集，利用邻域容差关系对数据集粒化处理.

定义2［24］（邻域容差关系）设S=(U，A)为不完备混合型信息系统，A=C∪D，设B⊆C为属性子集，且B=Bd∪Bc.其中，Bd表示属性子集中属性值为离散值，Bc表示属性子集中属性值为连续值.设邻域为δ，则在不完备混合信息系统S下，根据属性子集B确定的邻域容差关系为：

其中，Δa(x，y)和Δb(x，y)分别表示对于离散属性和连续属性对象x与对象y之间的距离度量.那么对于∀x∈U，关于的邻域类定义如下.

1.3 信息论Shannon［25］首次在通信领域提出信息熵的概念，来衡量一个给定的随机事件所包含信息量的大小.信息熵常被用来作为一个系统信息量的量化指标和属性的分辨力，也是信息系统中相关性度量的一种常见手段.

互信息是信息论中一种有用的信息度量，可以用来直接衡量两个变量之间拥有多少相同的信息量.它可以看成一个随机变量包含另一个随机变量的信息量，也可以看成一个随机变量确定的情况下另一个随机变量减少的不确定性.

定义3（互信息）若有随机变量X和随机变量Y，随机变量X和随机变量Y之间的互信息I(X，Y)表示如下：

其中，H(X)，H(Y)，H(X，Y)分别表示变量X的信息熵、变量Y的信息熵、变量X和Y的联合信息熵.

若两个随机变量之间的互信息越大，则说明拥有的共同信息越多.反之，这两个随机变量之间拥有的共同信息越少.如果有多个随机变量X1，X2，…，Xn和随机变量Y，那么这组随机变量集合与随机变量Y之间的互信息定义为：

其中，H(X1，X2，…，Xn)，H(Y)，H(X1，X2，…，Xn，Y)分别为变量X1，X2，…，Xn的联合熵，变量Y的信息熵，变量X1，X2，…，Xn，Y的联合熵.

定义4［24］（邻域容差信息熵）给定不完备混合型信息系统S=(U，A)，B⊆A，邻域半径为δ，且定义B的邻域容差信息熵为：

定义5［24］（邻域容差联合熵）给定S=(U，A)为不完备混合型信息系统，A=C∪D，B1，B2⊆C，设邻域半径为δ，并 且则B1和B2的邻域容差联合熵记为：

如果设U/NTD={NTD(x1)，NTD(x2)，…，NTD(x|U|)}，对于任意B⊆C，D和B的邻域容差联合熵记为：

1.4 集成学习目前，一般认为集成学习的研究始于1990 年，Hansen 和Salamon 首次提出用神经网络作为基分类器进行集成，使用该方法可以简单地通过训练多个神经网络将其结果进行结合，从而对比单个神经网络算法能显著提高学习系统的泛化能力［23］.在Hansen 和Salamon 之后集成学习得到了广泛的研究.

与采用单个学习器的机器学习方法不同，集成学习方法通过训练多个基学习器，并将训练结果结合考虑来解决一个问题.通常集成学习也称为多分类器系统或基于委员会的学习.一个集成系统由多个基学习器构成，而基学习器由基学习算法在训练数据上训练获得，如神经网络、决策树、朴素贝叶斯或其他学习算法.虽然传统基分类器的种类繁多，但其分类精度有待提高且容易出现过拟合等.故集成学习方法很受关注.通常，集成学习具有比基学习器更高的预测准确率及更强的泛化能力［6］.图1 表示一个通用的集成学习框架.

图1 一个通用的集成学习框架Fig.1 A general purpose integrated learning framework

2 基于邻域容差互信息的选择集成分类算法

2.1 问题提出互信息可以衡量两个离散变量之间拥有相同信息量的差异程度，同样可以度量离散属性集X与离散属性集Y之间的相关程度.与条件熵不同的是，属性集X与属性集Y的互信息越大表明其相关性越大，反之，属性集X与属性集Y的互信息越小表明其相关性越小.对于既含有离散型属性又含有连续型属性的不完备混合型信息系统，引入邻域容差关系，将邻域容差关系和互信息结合，定义邻域容差互信息的概念来衡量不同属性或属性组合与类别属性之间拥有共同信息量的多少，为使最终的加权投票结果更加合理，改进基分类器的预测权重，提出基于邻域容差互信息的选择集成分类算法.

2.2 算法思想类比邻域容差条件熵的相关理论，给出邻域容差互信息的相关定义.

证明根据定义4 得：

定义7（邻域容差互信息）设U/NTD={NTD(x1)，NTD(x2)，…，NTD(x|U|)}，对于任意B⊆C，D和B的邻域容差互信息记为：

证明若B1⊆B2，则NTB2(xi)⊆NTB1(xi).那么，

对于不完备混合型信息系统，邻域容差互信息可以用来衡量两个变量X和Y之间共同拥有信息量的多少.若变量X和变量Y之间邻域容差互信息越小，那么变量X和变量Y所包含的共同信息越少.极端情况下，当变量X和变量Y之间的邻域容差互信息为0 时，则说明这两个变量是独立的，彼此之间没有任何共同信息.若变量X和变量Y之间的邻域容差互信息越大，那么变量X和变量Y所包含的共同信息越多，此时变量X和变量Y关系密切，其中一个变量变化会对另一个变量产生较大影响.

同样，如果类别属性对于条件属性的邻域容差互信息越大，那么它们的相关程度越大，则它们之间一一映射的程度越高.反之，类别属性和条件属性的邻域容差互信息越小，就有理由认为它们之间近似一一映射的程度很低，则说明条件属性和类别属性之间的相关程度较小.特别地，如果条件属性和类别属性之间的邻域容差互信息为0，表明条件属性即便存在，也无法对最终类别的预测提供任何有效信息.

所以针对不完备混合型信息系统的分类问题，对于既含有缺失的离散型属性又含有缺失的连续型属性的样本可以通过引入邻域容差关系进行处理，结合互信息理论，定义邻域容差互信息来衡量条件属性对于类别属性的重要度，再利用粒化思想和集成分类算法提出基于邻域容差互信息的选择集成分类算法.

利用邻域容差互信息衡量缺失属性对决策分类结果的贡献度，在一个完整的数据集上计算缺失属性与类别属性的邻域容差互信息，属性对类别的贡献程度越大，其作为条件的邻域容差互信息越大；对决策分类结果的贡献度越小，作为条件的邻域容差互信息越小.使用邻域容差互信息、信息粒大小和基分类器的预测准确率来衡量由此信息粒构建的分类器的权重，比仅使用属性维数来衡量基分类器预测的权重更加科学，定义的权重公式如下：

其中，wi为第i个基分类器的预测赋予的权值，acci表示第i个基分类器的准确率，|Grai|表示第i个信息粒的大小，NTIi表示第i个信息粒的缺失属性集合对应类别属性的邻域容差互信息.

2.3 算法流程基于邻域容差互信息的选择集成分类训练流程图如图2 所示.基于邻域容差互信息的选择集成分类算法具体步骤如下.

图2 基于邻域容差互信息的选择集成分类训练流程图Fig.2 Selective integrated classification training flow chart based on neighborhood tolerance mutual information

步骤1.根据不完备混合型数据集中的缺失属性对样本进行粒化处理，即把数据集中缺失属性值相同的样本划分到同一信息粒，最终得到若干信息粒.

步骤2.为了提高预测准确率，充分利用含有缺失属性的数据信息，进行最大化信息粒.首先再次遍历原始数据集，将那些信息粒不含有缺失属性集以及含有缺失属性集的信息粒的属性集合包含在某个信息粒的属性集合中时，把此类信息粒中包含的样本的缺失属性集设置为该信息粒的缺失属性集，形成最大化信息粒.

步骤3.首先根据定义划分邻域容差类，根据式（5）计算邻域容差信息熵，根据式（7）计算邻域容差联合熵，最后以缺失属性包括连续属性和离散属性作为已知条件，在完整的信息粒上根据式（10）计算基于类别属性的邻域容差互信息.

步骤4.在各个最大化信息粒上，以非缺失属性作为输入，以BP 算法为基分类器的集成分类算法进行集成学习，得到若干个分类预测模型.

步骤5.使用各个信息粒缺失属性相应的邻域容差互信息、信息粒的大小和子分类器的精度，根据式（10）计算各个子分类器的权值.

步骤6.进行预测.假设预测数据集中样本的缺失属性集是某个信息粒的缺失属性集的子集，则可将该样本与这些信息粒相对应的属性集作为对应的子分类器的输入，经过训练后得出该样本在这些子分类器上的预测类别，然后再根据这些基分类器的分析结果，按照步骤5 的权值公式进行加权集成，得到最终预测结果.

例给出不完备混合型数据集，如表1 所示，设置阈值δ为0.5（阈值过大或过小都会影响粒度的划分.若阈值过大，划分的粒会很粗；若阈值过小，会导致划分的粒度较细，失去划分粒层的意义，加大计算难度.合理阈值设置为0.4～0.6，所以选择0.5 作为阈值）.计算条件属性集与类别属性的邻域容差互信息.

表1 不完备混合型数据集Table 1 Incomplete mixed data set

根据表中不完备混合数据集的定义以及缺失模式的定义，样本x1，x4，x5无缺失值，样本x2的缺失属性为{a4}，x3的缺失属性为{a2，a3}，x6的缺失属性为{a3，a4}.

按照缺失属性进行划分，则Granule={{x1，x4，x5}，{x2}，{x3}，{x6}}.不含缺 失属性，则X1={x1，x4，x5}.缺失属性{a4}，把不含缺失属性的样本去掉属性a4，则X2={x1，x2，x4，x5}.缺失属性{a2，a3}，把不含缺失属性的样本去掉属性a2，a3，则X3={x1，x3，x4，x5}.若缺失属性{a3，a4}，把不含缺失属性的 样本去掉属 性a3，a4，把缺失属性{a4}的样本去掉属性a3，则X4={x1，x2，x4，x5，x6}.

首先根据决策属性D划分邻域容差类：

根据所有条件属性C={a1，a2，a3，a4}划分邻域容差类：

根据条件属性a1划分邻域容差类：

根据条件属性a2划分邻域容差类：

根据条件属性a3划分邻域容差类：

根据条件属性a4划分邻域容差类：

根据条件属性a1和条件属性a2划分邻域容差类：

根据条件属性a1和条件属性a3划分邻域容差类：

根据条件属性a1和条件属性a4划分邻域容差类：

根据式（9）计算单个属性的邻域容差互信息：

根据式（9）计算属性集合的邻域容差互信息：

3 仿真实验与性能分析

基于Python 实现算法仿真，验证所提算法的可行性和有效性.实验设备的基本信息如下.系统环境：CPU Intel i7-10750H；RAM：18 GB；操作系统：Windows 10 专业版；解释器：Python 3.7.10.在3.1 中简要介绍实验使用的数据集和对比方法的基本信息.实验结果在3.2 中给出并详细分析实验结果.3.3 给出非参数统计检验的实验结果，验证与对比算法之间的统计学差异.

3.1 实验设置从UCI 数据库和爱数科公共数据库中选取七个公开获取的数据集进行实验验证，表2 为实验数据集的详细信息，其中有一个数据集只包含离散属性，一个数据集只包含连续型数据，三个数据集具有混合型属性.此外，对于数据 集E-commerce transportation 和Shill Bidding，真实获取的数据集为完备数据集，但为了验证算法的可行性，通过从原始数据集中随机选择5%和10%的已知样本特征值转变为缺失值，形成四个人工不完备数据集.

表2 数据集的详细信息Table 2 Details of the data set

为了降低由于数据划分带来的随机性，采用十折交叉验证的均值作为模型的最终得分.在所提方法中，采用BP 神经网络作为集成分类算法的基分类器，学习率为0.1，隐藏层神经元个数为15，迭代训练次数为15.本实验使用的对比算法包括：极限梯度提升机（XGBoost）、随机森林（RF）、梯度提升树（GBDT）、自适应Boosting（AdaBoost）和Stacking.需要注意的是，实验使用的分类器均采用Scikit-learn 学习库的默认参数进行实验.

3.2 实验结果与分析

表3 至表6 给出部分数据集通过实验得到的以各个信息粒缺失属性作为条件关于类别属性的邻域容差互信息，其中信息粒缺失属性按照缺失属性从少到多表示.当所有属性都为离散型属性时，邻域容差关系即为容差关系，例如Mushroom数据集，不含有连续型属性，此时阈值设为0，其缺失属性为一个.

表3 Housing loan 数据集缺失属性的邻域容差互信息Table 3 Neighborhood tolerance mutual information for missing attributes of Housing loan data set

表4 Adult 数据集缺失属性的邻域容差互信息Table 4 Neighborhood tolerance mutual information for missing attributes of Adult data set

表5 Credit 数据集缺失属性的邻域容差互信息Table 5 Neighborhood tolerance mutual information for missing attributes of Credit data set

表6 Water quality 数据集缺失属性的邻域容差互信息Table 6 Neighborhood tolerance mutual information for missing attributes of Water quality data set

由表3 至表6 可以看出，对于同一数据集信息粒中不同的缺失属性集合作为条件的类别属性的邻域容差互信息是不同的，数据集中缺失属性集合包含元素的数量与计算类别属性的邻域容差互信息是无关的.对于没有缺失属性的数据集，认为其丢失了一个与类属性无关的条件属性，则邻域容差互信息为0.若以信息粒缺失属性集合为条件的类别属性的邻域容差互信息较大，说明此缺失属性集合对决策类别的贡献率较大以及携带的信息量较大，对最终的决策类别较为重要.对于表3 的Housing loan 数据集，第二个属性比第七个属性邻域容差互信息大，则认为第七个属性对类属性的影响更大，那么对于缺失第二个属性的预测结果不如缺失第七个属性的预测结果可信度高.根据实验过程分析对于基分类器的预测准确率与信息粒包含样本的多少是高度相关的，所以预测准确率出现很高或很低的情况.因此，在定义基分类器的权重时，充分考虑其邻域容差条件熵，基分类器准确率以及信息粒的大小会更加合情合理，最终加权集成的分类器预测更加准确，构建的集成分类算法也更具有普适性.

对于处理不完备混合型数据的集成分类算法，最为典型的是XGBoost 算法，可以直接处理不完备数据集.由表7 的实验结果可以看出，对于不完备混合型数据集的分类问题使用邻域容差互信息选择集成分类算法得到的分类结果的准确率普遍要高于传统的XGBoost 算法的准确率，其中对于Housing loan数据集，用定义的权重公式（10）预测准确率比XGBoost 算法高6.1666%，但对于Adult 数据集，本节提出的算法预测准确率要高于XGBoost 算法，由于Adult 数据集缺失属性较少，用插补法处理后使用随机森林、GBDT、Ada-Boost、Stacking 算法预测准确率要高一些.对于其他数据集，本节提出的算法比传统集成分类算法预测准确率也高，例如，对于Housing loan 数据集，准确率比GBDT 高9.9232%，对于Credit 数据集，准确率比AdaBoost 高6.0379%等.所以本节提出的基于邻域容差互信息的选择集成分类算法对于解决不完备混合型数据集的分类问题提供了新的思路，在公开的不完备混合数据集上的实验结果证实了本节所提算法的有效性和可行性.

表7 不同分类器预测不同数据集准确率的对比Table 7 The accuracy comparison of different classifiers prediciting different datasets

3.3 非参数统计检验为了进一步验证提出的NTMISECA 方法与其他对比方法之间的性能差异，使用Friedman 排名和Holm′s 事后检验方法，在所有实验数据集上，验证模型之间的统计学差异，结果如表8 所示.

表8 所有分类器的Friedman 排名和事后检验结果Table 8 Friedman rankings and postmortem results for all classifiers

根据表8 的非参数统计结果，可以发现提出的方法的Friedman 排名明显优于其他分类方法.但是，根据常用的显著性差异度量标准（p＜0.05），提出的方法与使用的对比方法不存在显著的统计学差异，即提出的方法在所有数据集上的性能与对比方法是相近的，差异并不明显.

在实验使用的对比集成学习方法中，均使用决策树作为模型的基分类器，而在提出的NTMISECA 方法中，使用神经网络作为基分类器.神经网络是一种适用性很强的分类方法，适用于大部分数据集，但是，神经网络对模型的参数很敏感，可以使用经典的参数优化方法或搜索方法选择最优的参数.此外，在基分类器的参数调整方面与使用决策树的模型仍然存在差距.然而，提出的NTMISECA 是一种基于粒计算的集成学习框架，其基分类器可以根据实际需要调整.因此，也可以使用单一弱分类器或弱集成学习方法，从而有效地提高提出的方法的分类性能和泛化能力.

4 结论

本章根据粒计算的基本思想，利用集成学习的优势，将邻域容差理论和互信息理论结合，提出一种解决不完备混合型信息系统的分类问题的集成算法，即基于邻域容差互信息的选择集成分类算法.利用传统集成算法对不完备数据集进行分类在权衡各个基分类器的权重时仅考虑数据的维度和属性的多少是不够科学的，不同的属性对类别的贡献程度也是不一样的，所以提出邻域容差互信息的概念来衡量.然后根据粒计算的思想按照缺失属性将数据集划分为不同的信息粒，为充分利用数据信息，将信息粒最大化，并用集成算法训练出基分类器，利用信息粒的大小、邻域容差互信息和基分类器预测准确率来定义基分类器的权重，再次实现加权集成投票.实验表明该算法普遍比传统的集成分类算法预测准确率高.

本文所选用数据集全部为静态数据集，对于动态不完备混合型数据集如何设计集成分类算法，并且对于集成学习算法训练时间会比较长，如何进一步减少预测时间，提升预测效率也是一个值得研究的问题.