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倾向于通过换算的数据点x和y的局部距离统计数据使得近邻关系更加对称^[6].

② MP

相互接近(Mutual Proximity)通过将两个对象之间的距离转换为一个相互接近的距离来重新解释原始的距离空间, 使得两个共享最近邻的对象之间的距离就更紧密了, 而不共享最近邻的对象则相互排斥. 在n个对象集合中, 计算一个给定距离 ${d_{x,y}}$ 可以归结为简单地计算出j与x和y之间大于 ${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是计算点x和y的相似度, 通过计算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找到x的K近邻从而生成相应的类支持向量:

${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)$ 代表数据点x的K近邻中第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中的数据点x的K近邻集合, ${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)]$ 的增大而减少.

根据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) 对于一些存在较大异常值的数据集(比如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})$ .

(5) 结论与展望

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