改进PM-MD的分类器集成①

吴立凡,何振峰

(福州大学 数学与计算机科学学院,福州 350116)

Hub[1]指一些经常出现在其他数据点的最相邻列表中的数据点,它是随着维度的增加而出现的,这种现象一般称为Hubness 现象[2].Hubness 是高维空间数据分布的一个固有性质,对高维数据分析产生了显著的影响[2],受影响的方法和任务包括贝叶斯建模,近邻预测和搜索,神经网络等等[2].比如,Hubness 的出现会直接影响到KNN 分类的准确性[3],这是因为：Hub 在相应的距离空间中传播其编码信息过于广泛,而非Hub 携带的信息基本上丢失,导致这些距离空间不能很好地反映类信息[4].

为了减少Hubness 的负面影响,有两类(共五种)降Hubness 的分类器策略应用于数据转换以提高KNN 分类精度：其中第一类策略(二次距离策略)将距离矩阵换算到二次距离(NICDM[1]、MP[1]),第二类策略(线性换算策略)直接应用于数据向量(CENT[3]、MINMAX[5]、ZSCORE[5]).第一类策略中：NICDM 是将Hubness 问题与使最近邻关系对称的方法联系起来,它需要得到每个数据点的局部邻域,因此并不适用于非常大的数据库；MP 是一种无监督的将任意的距离函数转换成概率相似性(距离)测量的方法,适用于非常大的数据库,并且支持多个距离空间的简单组合.实验表明NICDM 和MP 显著的减少了Hubness,提高了KNN分类精度,还增强了近邻的稳定性[1,6]；但是,NICDM和MP 适用于中心性和内在维度较高的数据集,否则性能不稳定[1].第二类策略中：CENT 是将特征空间的原点移到数据中心,可用于内积相似空间以减少Hubness(其中每个样本和中心的相似性在CENT 后等于零),但它并不是适用于所有数据集,它成功的必要条件是Hub 与数据中心点有着高相似度[1]；而MINMAX和ZSCORE 则是应用很广泛的数据标准化方法,MINMAX 是对原始数据进行线性变换,适用于原始数据的取值范围已经确定的情况；ZSCORE 基于原始数据的均值和标准差进行数据的标准化,适用于最大值和最小值未知的情况,或有超出取值范围的离群数据的情况.

在本文中对这两类策略进行多分类器集成,由于不同的分类器提供了关于被分类的对象的补充信息,因此多分类器系统可以获得比整体中任何单一的分类器更好的分类精度.本文中的集成采用了一种计算特征空间分类器竞争力的名为PM-MD[7]的方法.在该方法中,首先使用KNN 的验证对象来确定分类对象x点的决策表,决策表提供了被识别对象属于指定类的机会.在概率模型中,决策表的自然概念是基于x点上的类的后验概率.接下来,将决策表与分类器所产生的响应(支持向量或判别函数的值)进行比较,并根据相似性规则[8]计算分类器的分类竞争力：对决策表的响应越接近,分类器的竞争力就越强[9,10].

本文的第1 部分介绍两类降Hubness 策略(共五种),第2 部分介绍PM-MD 集成的方法并对第1 部分的策略进行集成,第3 部分介绍对PM-MD 集成进行改进的部分,第4 部分对实验结果进行分析.

(1)两类降Hubness 策略

1)二次距离策略

① NICDM

NICDM (Non-Iterative Contextual Dissimilarity Measure)用K近邻的平均距离来重新换算距离,相比于利用K近邻距离来重新换算距离,这将返回更稳定的换算数据.NICDM 通过式(1)得到二次距离：

其中,µx表 示x最近邻的平均距离,µy同理.NICDM 倾向于通过换算的数据点x和y的局部距离统计数据使得近邻关系更加对称[6].

② MP

相互接近(Mutual Proximity)通过将两个对象之间的距离转换为一个相互接近的距离来重新解释原始的距离空间,使得两个共享最近邻的对象之间的距离就更紧密了,而不共享最近邻的对象则相互排斥.在n个对象集合中,计算一个给定距离dx,y可以归结为简单地计算出j与x和y之间大于dx,y的距离[1]：

式(2)中,MP 是计算点x和y的相似度,通过计算1-MP将相似度变成了二次距离[6].

2)线性换算策略

① CENT

定心(Centering)将特征空间的原点转移到数据中心它是一种去除数据中观测偏差的经典方法,但直到最近才被确定为减少Hubness 的方法.

式(3)中simCENT(x;q)是计算相似度,需要通过计算1-simCENT(x;q)将相似度变成了距离.

② MINMAX

在MINMAX 算法里,原始数据是线性变化的.MINMAX 使用式(4)将v值进行映射到v′：

将xmin和xmax定义为样本中变量的最小值和最大值,MINMAX 将在[xmin,xmax]区间的训练样本映射到[0,1].

③ ZSCORE

ZSCORE 通过式(5)将v值进行映射到v′：

其中,和 σx分别为训练集中变量值的均值和标准差.在映射之后,平均值将为0,标准差将为1.

(2)集成方法

本文采用的PM-MD 是一种全新的计算特征空间中分类器能力的集成方法,被集成的方法为第一章中提到的5 种策略：NICDM、MP、MINMAX、ZSCORE、CENT.PM-MD 方法是由两个方法结合起来：PM 方法(Potential function Method)和MD 方法(Max-max Distance).PM-MD 的特色在于对验证集的不同使用,在PM-MD 中验证集是用来评估测试点的类支持向量的,并且在PM 中使用K近邻来确定测试点的决策表,最后在MD 中由类支持向量与决策表的相似性决定分类器的竞争力[7].

集成流程的图示如图1,本文采用的是5 种降Hubness 策略和KNN 分类,也可以采用其他策略和分类方法.

1)类支持向量

分类器ψl相当于一个从特征度量空间x⊆Rdim到一个类标签集合M={1,2,···,m}的函数.对于每个数据点x,分类器 ψl经过该分类器的数据转换后通过KNN找到x的K近邻从而生成相应的类支持向量：

2)根据PM 计算决策表

决策表 ω (x)=[ω1(x),ω2(x),···,ωM(x)]提供了数据点x属于指定类的机会,其中

用PM 方法通过K近邻计算数据点x的决策表的步骤如下：

① 计算一个非负势函数H(x,xk)[11],其值随着x和xk之间距离增大而快速减少(xk为来自验证集的数据对象)：

② 根据上一步得到的势函数计算决策表 ωj(x),它是x属于第j类的机会的衡量：

其中,NK(x)为验证集V中的数据点x的K近邻集合,xk为来自验证集的数据对象,jk为相应的类标签.

3)根据MD 计算分类器竞争力

分类器竞争力c(ψl|x)用来衡量分类器ψl在数据点x的分类能力,它随着支持向量dl(x)和 决策表ω (x)的距离dist[ω(x),dl(x)]的增大而减少.

图1 结合降Hubness 过程的分类器集成框架

根据MD 方法计算分类器竞争力步骤如下：

① 令j为分类器 ψl在数据点x产生的类支持向量的最优值的类编号,即dl j(x)=maxk∈M(dlk(x))；同理,令i为决策表ω (x)在数据点x产生的最优值的类编号.

则支持向量dl(x)和 决策表ω (x)的距离定义如下：

假设类支持向量为dl(x)=[0.1,0.4,0.2,0.3],决策表为ω(x)=[0.2,0.1,0.2,0.5] ,则dl j(x)=0.4,j=2 ,ωi(x)=0.5,i=4.所以距离计算如下：

② 根据上一步得到的距离计算竞争力c(ψl|x)：

4)组合投票以及最后分类精度的计算

对于测试数据点x,其最后的分类结果 ψ (x)是由分类器组合中的每个分类器产生的类支持向量(式(6))结合其对应的分类器竞争力(式(11))组合投票得出来的：

其中,T为分类器的个数.

最后的分类精度是对测试集V中的每个测试数据点进行分类,然后计算正确分类的数据点数占总点数的比例：

其中,m(x)为x的真实类标签,m(x)∈M.

将所有属于测试集V的数据点的result(x)相加后除以测试集V的数据点总个数num便可得到最终的分类精度Result.

(3)改进PM-MD

原PM-MD 中式(7)采用高斯势函数将欧氏距离||x-xk||映射到(0,1)之间,但当数据集的内在维度较高时不同样本距离经过高斯势函数转换后会非常地趋于0,这会弱化距离所带来的不同类的区别.如图2,图2(d)MINMAX 的距离均值较大,大部分样本距离采用高斯势函数会得到趋于0 的结果,这样会使得MINMAX 分类效果变弱,从而影响集成效果；这个情况在文献[7]的表3所给实验结果中也可以体现出来,当数据集的内在维度较高时(如Ionosphere 和Spam等)PM-MD 的分类结果往往不是很好.

根据PM-MD 不适用于高维数据集的情况下,本文提出将直接采用欧氏距离计算决策表.

将PM 进行改进：

所对应的决策表公式：

(4)实验结果

实验中共选用12 个UCI 数据集[12]进行测试.经过10 轮十折交叉验证,取100 个结果的准确率均值.12 个UCI 数据集测试结果(表1)表明：

1)单一分类器并不适用于所有情况(比如NICDM在数据集seeds 效果最优但在数据集mammographic_masses 效果很差),PM-MD 集成中和分类器的优劣,在一定程度上可以获得比整体中任何单一的分类器更好的分类精度.

图2 数据集Dermatology 在各个分类器中得到的距离箱线图

2)对于一些存在较大异常值的数据集(比如Pima_indians_diabetes),PM-MD 集成之后比起单一分类器有着更优的精度,由此可见对于存在大量较大异常值的数据集,PM-MD 集成获得了比任何单一分类器要更高的分类精度.

3)对于一些不仅存在较大异常值还存在较小异常值的数据集(比如wine),集成后的分类效果明显优于

大部分单一分类器分类效果,也明显优于原始分类结果.

4)改进后的PM-MD 在一定程度上具有比PMMD 更精确的分类效果(比如数据集Liver),由此可见改进后的PM-MD 确实提升了PM-MD 的分类效果.

5)NICDM、CNET、MINMAX、ZSCORE 的复杂度都为O (n2),MP 的复杂度为O (n3),故PM-MD 的复杂度为O (n3).

表1 实验结果

(5)结论与展望

Hubness 现象是维度灾难的一个方面,hub 的出现严重降低了分类器的性能.本文结合了五种降Hubness 策略以减少Hubness 的影响,由于每种策略所适用范围的差异,为此采用了PM-MD 方式进行集成以扩大适用范围.并针对PM-MD 不适用于高维数据集的问题提出改进,直接将欧氏距离直接用于计算决策表.实验结果表明,PM-MD 获得了比单一分类器要高的分类精度的同时扩大了适用范围,改进后的PMMD 获得了更高的分类精度.目前研究主要关注于噪声较小的高维数据分类,未来我们将致力于通过有效分类器集成以解决噪声较大的数据集的分类问题.

1 Schnitzer D,Flexer A,Schedl M,et al.Local and global scaling reduce hubs in space.Journal of Machine Learning Research,2012,13(1)：2871-2902.

2 Zhai TT,He ZF.Instance selection for time series classification based on immune binary particle swarm optimization.Knowledge-Based Systems,2013,49：106-115.[doi：10.1016/j.knosys.2013.04.021]