,

(湖南大学 信息科学与工程学院,长沙 410082)

0 概述

随着数据采集技术的发展和互联网的深入,应用领域中的数据越来越呈现高维化趋势。相较于低维数据,各种机器学习方法和任务在高维数据上会面临严重的挑战,例如:数量众多的特征属性之间存在大量冗余和相关性,明显违背贝叶斯建模的基本独立性假设[1];维数增加所带来的样本间距离的集中化,减弱了各种距离指标反映相似性差异的有效性,使得包括k最近邻(k-Nearest Neighbor,kNN)分类和聚类等不能有效地应用于高维数据[2]。这些在数据挖掘和机器学习领域由高维特征空间所带来的各种困难与挑战,统称为维数灾难。

文献[3]探索维数灾难的一个新方向:Hubness。假设Nk(x)为数据集D中样本x出现在其他样本的k最近邻列表中的次数,Hubness现象指在高维数据空间中Nk(x)的分布呈现明显的右偏态,即一些样本点,或非常频繁地作为其他样本的k最近邻(hubs),或很少成为其他样本的k最近邻(anti-hubs)。在文献[3]之后,一些Hubness-aware的kNN和聚类方法相继被提出,都从Hubness这一全新的角度切入解决方法在应对高维数据时的低效性问题。然而,上述方法都没有考虑一个普遍存在的情形:在现实中,许多高维数据往往也是类不平衡的,如文本分类、生物医疗和图像分类等。由于标准的机器学习方法通常以最小化训练错误为目标,少数类样本的稀少使得从不平衡数据中学习的分类器往往忽略少数类的概念信息,从而趋向将所有未知样本预测为大数类[4-5]。……