计算机系统应用  2019, Vol. 28 Issue (4): 157-162   PDF    
改进PM-MD的分类器集成
吴立凡, 何振峰     
福州大学 数学与计算机科学学院, 福州 350116
摘要:Hub会对高维数据分析产生显著消极影响, 现有研究分别采用了五种降Hubness策略以提高分类效果, 但单个降Hubness策略适用范围有限. 为解决这一问题, 提出对五种降Hub分类器进行基于PM-MD的集成, PM-MD集成是通过KNN确定分类对象的决策表以及通过分类器得到分类对象的类支持向量, 最后通过比较决策表和类支持向量的相似性计算分类器的竞争力权重. 由于PM-MD在处理高维数据集时高斯势函数存在弱化距离导致区分度不足的倾向, 因此提出了采用欧氏距离直接计算决策表以提高分类精度. 在12个UCI数据集上的实验结果表明: PM-MD不仅获得更好且稳定的分类结果, 而改进后的PM-MD则进一步提高了分类精度.
关键词: PM-MD    分类器    集成    Hubness    高维    
Improved PM-MD Classifier Integration
WU Li-Fan, HE Zhen-Feng     
School of Mathematics and Computing Science, Fuzhou University, Fuzhou Fujian 350116, China
Foundation item: Natural Science Foundation of Fujian Province (2018J01794)
Abstract: Hubs have a significant negative impact on high-dimensional data analysis. The current research uses five kinds of Hubness strategies to improve the classification effect, but each strategy has a limited scope of application. In order to solve this problem, PM-MD-based integration is proposed for the Hubness-based classifiers. The PM-MD integration determines a decision profile of the classification object through KNN and determines a class support vector of the classification object through the classifier. Finally, the competitiveness of the classifier integration is evaluated by comparing the similarity between the decision profile and the class support vector. When PM-MD dealing with high-dimensional data sets, because the Gaussian potential function tends to reduce the distance which leads to a lack of discrimination, it is proposed to use Euclidean distance to directly calculate the decision profile to improve the classification accuracy. The experimental results on 12 UCI datasets show that PM-MD obtains sound and stable classification results, and the improved PM-MD further improves the classification accuracy.
Key words: PM-MD     classifier     integration     Hubness     high dimensions    

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)得到二次距离:

$NICDM({d_{x,y}}) = \frac{{{d_{x,y}}}}{{\sqrt {{\mu _x}{\mu _y}} }}$ (1)

其中, ${\mu _x}$ 表示x最近邻的平均距离, ${\mu _y}$ 同理. NICDM倾向于通过换算的数据点xy的局部距离统计数据使得近邻关系更加对称[6].

② MP

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

$MP({d_{x,y}}) = \frac{{|{{\{ j:}}{{{d}}_{x,j}}{{ > }}{{{d}}_{x,y}}{{\} }} \cap {{\{ j:}}{{{d}}_{y,j}}{{ > }}{{{d}}_{y,x}}{{\} }}|}}{n}$ (2)

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

2) 线性换算策略

① CENT

定心(Centering)将特征空间的原点转移到数据中心 $c = (\frac{1}{{|D|}})\sum\nolimits_{x \in D} x $ , 它是一种去除数据中观测偏差的经典方法, 但直到最近才被确定为减少Hubness的方法.

$si{m^{CENT}}(x;q) \equiv < x - c,q - c > $ (3)

式(3)中 $si{m^{CENT}}(x;q)$ 是计算相似度, 需要通过计算 $1 - si{m^{CENT}}(x;q)$ 将相似度变成了距离.

② MINMAX

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

$v' = \frac{{v - {x_{\min }}}}{{{x_{\max }} - {x_{\min }}}}$ (4)

${x_{\min }}$ ${x_{\max }}$ 定义为样本中变量的最小值和最大值, MINMAX将在[ ${x_{\min }}$ , ${x_{\max }}$ ]区间的训练样本映射到[0, 1].

③ ZSCORE

ZSCORE通过式(5)将v值进行映射到 $v'$ :

$v' = \frac{{v - \overline x }}{{{\sigma _x}}}$ (5)

其中, $\overline x $ ${\sigma _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) 类支持向量

分类器 ${\psi _l}$ 相当于一个从特征度量空间 $x \subseteq {R^{\dim }}$ 到一个类标签集合 $M = \{ 1,2,\cdots,m\} $ 的函数. 对于每个数据点x, 分类器 ${\psi _l}$ 经过该分类器的数据转换后通过KNN找到xK近邻从而生成相应的类支持向量:

${d_l}(x) = [{d_{l1}}(x),{d_{l2}}(x),\cdots,{d_{lm}}(x)]$ (6)

其中, ${d_{lj}}(x) \geqslant 0,\sum\nolimits_{j \in M} {{d_{lj}}(x) = 1} $ , ${d_{lj}}(x)$ 代表数据点xK近邻中第j类的比重.

2) 根据PM计算决策表

决策表 $\omega (x) = [{\omega _1}(x),{\omega _2}(x),\cdots,{\omega _M}(x)]$ 提供了数据点x属于指定类的机会, 其中 ${\omega _j}(x) \geqslant 0,\sum\nolimits_{j \in M} {{\omega _j}(x) = 1} $ .

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

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

$H(x,{x_k}) = \exp ( - ||x - {x_k}||)$ (7)

② 根据上一步得到的势函数计算决策表 ${\omega _j}(x)$ , 它是x属于第j类的机会的衡量:

${\omega _j}(x) = \frac{{\sum\nolimits_{{x_k} \in {{{N}}_K}(x):{j_k} = j} {\exp ( - ||x - {x_k}||)} }}{{\sum\nolimits_{j \in M} {\sum\nolimits_{{x_k} \in {{{N}}_K}(x):{j_k} = j} {\exp ( - ||x - {x_k}||)} } }}$ (8)

其中, ${N_K}(x)$ 为验证集V中的数据点xK近邻集合, ${x_k}$ 为来自验证集的数据对象, ${{\rm{j}}_k}$ 为相应的类标签.

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

分类器竞争力 $c({\psi _l}|x)$ 用来衡量分类器 ${\psi _l}$ 在数据点x的分类能力, 它随着支持向量 ${d_l}(x)$ 和决策表 $\omega (x)$ 的距离 $dist[\omega (x),{d_l}(x)]$ 的增大而减少.

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

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

① 令j为分类器 ${\psi _l}$ 在数据点x产生的类支持向量的最优值的类编号,即 ${d_{lj}}(x) = {\max _{k \in M}}({d_{lk}}(x))$ ; 同理, 令i为决策表 $\omega (x)$ 在数据点x产生的最优值的类编号.

则支持向量 ${d_l}(x)$ 和决策表 $\omega (x)$ 的距离定义如下:

$dist[\omega (x),{d_l}(x)] = |{d_{lj}}(x) - {\omega _j}(x)| + |{d_{li}}(x) - {\omega _i}(x)|$ (9)

假设类支持向量为 ${d_l}(x) = [0.1,0.4,0.2,0.3]$ , 决策表为 $\omega (x) = [0.2,0.1,0.2,0.5]$ , 则 ${d_{lj}}(x) = 0.4,j = 2$ , ${\omega _i}(x) = $ $0.5,i = 4$ . 所以距离计算如下:

$dist[\omega (x),{d_l}(x)] = |0.4 - 0.1| + |0.3 - 0.5| = 0.5$

② 根据上一步得到的距离计算竞争力 $c({\psi _l}|x)$ :

$c({\psi _l}|x) = 1{\rm{ - }}\frac{{|{d_{lj}}(x) - {\omega _j}(x)| + |{d_{li}}(x) - {\omega _i}(x)|}}{2}$ (10)

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

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

${D_j}(x) = \sum\limits_{l = 1}^T {c({\psi _l}|x){d_{l,j}}(x)} $ (11)

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

$\psi (x) = i \Leftrightarrow {D_i}(x) = \mathop {\max }\limits_{j \in M} {D_j}(x)$ (12)

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

$result(x) = \left\{ \begin{gathered} 1,\;\;\psi (x) = = m(x) \\ 0,\;\;\psi (x)! = m(x) \\ \end{gathered} \right.$ (13)

其中, $m(x)$ x的真实类标签, $m(x) \in M$ .

$Result = \sum\nolimits_{x \in A} {result(x)} /num$ (14)

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

(3) 改进PM-MD

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

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

将PM进行改进:

$H(x,{x_k}) = ||x - {x_k}||$ (15)

所对应的决策表公式:

${\omega _j}(x) = \frac{{\displaystyle\sum\nolimits_{{x_k} \in {{{N}}_K}(x):{j_k} = j} {||x - {x_k}||} }}{{\displaystyle\sum\nolimits_{j \in M} {\sum\nolimits_{{x_k} \in {{{N}}_K}(x):{j_k} = j} {||x - {x_k}||} } }}$ (16)

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

5) NICDM、CNET、MINMAX、ZSCORE的复杂度都为 ${\rm{O}}({n^2})$ , MP的复杂度为 ${\rm{O}}({n^3})$ , 故PM-MD的复杂度为 ${\rm{O}}({n^3})$ .

表 1 实验结果

(5) 结论与展望

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

参考文献
[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
[3]
Hara K, Suzuki I, Shimbo M, et al. Localized centering: Reducing Hubness in large-sample data. Proceedings of the 29th AAAI Conference on Artificial Intelligence. Austin, TX, USA. 2015. 2645–2651.
[4]
Feldbauer R, Flexer A. A comprehensive empirical comparison of hubness reduction in high-dimensional spaces. Knowledge and Information Systems, 2018, 1-30. DOI:10.1007/s10115-018-1205-y
[5]
Cao H X, Stojkovic I, Obradovic Z. A robust data scaling algorithm to improve classification accuracies in biomedical data. BMC Bioinformatics, 2016, 17: 359. DOI:10.1186/s12859-016-1236-x
[6]
Feldbauer R, Flexer A. Centering versus scaling for Hubness reduction. Proceedings of the 25th International Conference on Artificial Neural Networks. Barcelona, Spain. 2016. 175–183.
[7]
Kurzynski M, Trajdos P. On a new competence measure applied to the dynamic selection of classifiers ensemble. Proceedings of the 20th International Conference on Discovery Science. Kyoto, Japan. 2017. 93–107.
[8]
Duda RO, Hart PE, Stork DG. Pattern Classification. New York: Wiley-Interscience, 2001.
[9]
Kurzynski M. On a new competence measure applied to the combining multiclassifier system. International Journal of Signal Processing Systems, 2016, 4(3): 185-191. DOI:10.18178/ijsps.4.3.185-191
[10]
Kurzynski M, Krysmann M, Trajdos P, et al. Multiclassifier system with hybrid learning applied to the control of bioprosthetic hand. Computers in Biology and Medicine, 2016, 69: 286-297. DOI:10.1016/j.compbiomed.2015.04.023
[11]
Meisel WS. Potential functions in mathematical pattern recognition. IEEE Transactions on Computers, 1969, C-18(10): 911-918. DOI:10.1109/t-c.1969.222546
[12]
Lichman M. UCI Machine Learning Repository. University of California. School of Information and Computer Science. http://archive.ics.uci.edu/ml, [2013-04-04].