基于自适应图的降维方法

孙 慧, 卢 爽, 齐 妙

(东北师范大学 a. 人文学院; b. 信息科学与技术学院, 长春 130117)

0 引 言

随着社会的进步和科学水平的提高, 数据获取和存储技术得到了快速发展。在科学研究领域, 研究者越来越容易采集到各行各业的大量数据, 如生物数据、 人体行为[1]、 人脸图像以及高清晰医学图像等。这些数据作为信息的载体虽然蕴藏着大量有价值的信息, 但往往具有高维、 繁杂及非线性等特点, 不仅增加了大量的计算和存储量, 产生数据冗余, 增加数据分析的计算复杂度, 还会导致严重的维数灾难(Curse of Dimensionality)等问题。因此, 若要从高维数据中获取其本质的结构和内在的特征, 就需要对高维数据进行预先分析与处理, 提取有用信息的同时舍弃不相关的冗余信息, 即数据降维, 其实质是通过探索数据内部的关系结构, 将高维数据在不改变数据几何结构的情况下映射到低维空间, 去除噪音, 挖掘出隐藏在高维空间的低维本征表示, 便于后续处理。

目前, 已经提出很多针对高维数据的降维方法, 其主要分为线性降维和非线性降维。最经典的线性降维算法当属主成分分析(PCA: Principal Component Analysis)[2]以及线性判别分析(LDA: Linear Discriminant Analysis)[3]。这类算法具有坚实的理论基础(基于特定的统计分布假设), 易于执行和分析, 并被成功应用于许多实际问题中[4]。然而, 各领域所获得的真实数据更多表现为非线性结构, 传统的线性降维方法难于探索出固有的数据内部几何结构。为此, 近些年研究者们尝试了许多实现非线性降维的有效途径, 其中比较典型的算法包括核主成分分析(KPCA: Kernel Principal Component Analysis)[5]、 局部线性嵌入(LLE: Locally Linear Embedding)[6]、 等距映射ISOMAP(Isometric Feature Mapping)[7]和拉普拉斯特征值映射LE(Laplacian Eigenmaps)[8]等。尽管这些算法在一定程度上探索出了数据内部的几何结构, 但也存在着局限性。核化的降维方法通常依赖于某种隐式映射, 不易直观地理解其降维机理, 且核的选择目前仍无可靠的理论依据, 而流形学习往往会导致所谓的外样本(Out-of-Sample)问题[9,10]。

为避免外样本问题并提高流形学习在实际数据上的性能, He等[11]提出邻域保持嵌入(NPE: Neighborhood Preserving Embedding)和局部保持投影(LPP: Locality Preserving Projection)[12], 这两种算法分别是LLE算法和LE算法的线性改进形式。其中, NPE算法旨在保持原始高维数据的局部线性重构关系并通过线性逼近的方式寻找高维空间到低维空间之间的最优投影矩阵。LPP算法则是通过保持高维数据局部近邻关系不变, 从而获得最佳的投影方向。最近, 有研究表明[13], 很多现有的维数约简方法都可以被统一到图嵌入(Graph Embedding)的框架中, 如ISOMAP、 LLE、 LE、 LPP及NPE等维数约简算法, 它们都是通过构建图描述数据之间的某种联系及本质规律, 揭示数据的内在拓扑结构(如子空间或流形结构)。因此, 在基于图嵌入的维数约简方法中, 图的质量严重影响算法的性能, 构造一个优质图不仅能直观反映数据的几何结构信息, 而且有利于后续的维数约简任务。随着对图构建问题的深入研究, 研究者们提出了许多构图策略。其中, 传统的k近邻[12]和ε球邻域[14]准则是目前应用较为广泛的构图策略, 上述提到的LPP算法和NPE算法就是两个典型的基于k近邻准则定义图的维数约简算法。然而, 无论是构建k近邻图还是ε球邻域图, 都需要预先为所有样本确定相同的近邻参数k或邻域参数ε, 而在实际问题中, 参数值的选取比较困难； 另外, 每个样本的局部结构通常是不同的, 设置相同的近邻参数会使得到的图不能有效反映数据的本质结构[15]。

为了避免上述传统方法的局限性, 近年来还兴起了一些基于稀疏表示的图构建方法, 如： 样本依赖图(SG: Sample-dependent Graph)[16]、 稀疏保持投影(SPP: Sparsity Preserving Projections)[17]、 最小二乘回归(LSR: Least Squares Regression)[18]、 低秩表示(LRR: Low Rank Representation)[19]和图优化的局部保持投影(GoLPP: Graph-Optimized Locality Preserving Projections)[20]等。然而, 以上提到的基于图嵌入的维数约简算法都面临着各自的局限性, 总体而言, 建立高质量的图仍是机器学习和模式识别领域的重点研究问题[21,22]。

综合以上分析, 笔者提出一种基于自适应图的数据降维方法, 即DRAG(Dimensionality Reduction based on Adaptive Graphs), 该方法考虑了数据点周围的点分布信息, 自适应地寻找最近邻域大小。不同于传统的邻域选取方法, DRAG避免了基于参数和基于数据表示的图构建方法缺点, 并且考虑了噪声和局部信息, 获得了更稀疏更灵活的图。最后, 为了评估算法的性能, 笔者在几个常见数据库上进行了分类与聚类实验, 实验结果进一步证明了笔者方法的有效性。

1 基于自适应图的降维方法

首先, 研究了数据的自适应图的构建方法, 在此基础上, 将其融合至局部保持投影LPP方法进行有效降维。

1.1 自适应图的构建

现有流形学习方法所设定数据点的局部邻域数大多由人为给定, 且邻域的选取方式对降维嵌入的结果影响很大。基于此, 笔者引入文献[23]中的一种新的自适应关联图的构建方式, 此方式考虑数据点周围的点分布信息自适应地寻找最近邻域大小。其不同于传统选取邻域的方法, 此方法得到的各样本点邻域大小是不等的, 它是根据数据点的分布信息, 即样本点周围的疏密信息动态地获得最近邻域数。

给定高维空间样本集X=[x1,x2,…,xn]∈RD×n, 其中n为样本个数,D为样本维数。用线性关系X=XR重构原始数据X, 则根据文献[23]可得如下约束

(1)

如果把式(1)作为构建图的目标函数并不会得到最优结果, 因为针对某一数据样本点, 只有具有离其最近的重构表示所对应的数据样本点才会被判定为(Ai=1)的统一类簇, 而其他的数据样本点就会被判定为(Ai=0)的统一类簇。所以, 在

(2)

(3)

1.2 数据降维

下面利用自适应的关联图, 同时借鉴LPP(Locality Preserving Projection)算法的优点, 学习投影矩阵W, 从而达到降维目的。令Y=[y1,y2,…,yn]∈Rd×n,d≪D表示X的低维嵌入。假定存在线性变换yi=wTxi,yi∈Rd, 则最终的数据降维任务可以被公式化为如下形式

(4)

其中A为由式(3)获得的自适应的关联图。D为一个有序的对角矩阵,Dii=∑jAij, 元素Dii(与yi对应)的值越大,yi越重要。L是拉普拉斯矩阵,L=D-A。

这里的Aij实际上可以看作是惩罚因子, 即如果相邻的xi和xj被映射后的yi和yj相距很远, 目标函数会导致一个较大的惩罚因子。因此, 目标函数的最小化保证如果xi和xj距离很近, 则映射后的yi和yj距离也很近。式(4)最终可转化为广义特征值问题

minwTXLXTw; s.t.wTXLXTw=1

(5)

其中W是D×d的投影矩阵,Y是输出的低维数据集。

2 实验效果评价

为验证提出DRAG算法的有效性, 笔者将算法应用于几个常用的数据库, 进行了分类与聚类实验。同时还将笔者提出的DRAG算法与国内外较典型的维数约简方法(LPP[12]、 NPE[11]、 LSR-NPE[18]、 LRR-NPE[19]以及NDML(Nonparametric Discriminant Multi-manifold Learning)[24])进行了对比。

2.1 分类实验

首先, 在数据预处理阶段, 对图像进行归一化。然后, 为了避免小样本(SSS: Small Sample Size)[25]问题, 在实验前使用PCA算法对数据进行预处理。之后, 在每个数据库中分别选择l个样本作为训练样本, 余下的t个样本作为测试样本, 随机选取训练样本的过程重复执行10次。在所有涉及k近邻构图策略中的近邻参数k值设置为{3,5,7,9}, 并记录算法在4个参数下的最好结果。在对比算法中, 按照它们相应的参考文献设置它们的参数值。在提出的DRAG算法中, 设置3个权衡参数λ1,λ2和λ3的取值为{0.001,0.01,0.1,1,10,100,1 000}。为了加强算法的可靠性, 执行10次随机实验, 并记录10次实验的最高平均识别率。在实验中, 使用基于欧氏距离的最近邻分类器执行分类任务。

分类实验所用的数据集包括CMU PIE数据集和Extended YaleB数据集。具体信息如表1所示, 图 1为不同算法在两个数据集的分类对比结果。

表1 分类实验中所用数据集

a AR (l=7) b Extended YaleB (l=10)图1 不同算法在不同数据库上的分类识别率随特征维数的变化曲线Fig.1 Curves of recognition rates of different algorithms with the feature dimension

2.2 聚类实验

在聚类实验中, 同样要对每个数据库中的图像进行归一化处理, 并通过k均值算法对低维特征进行聚类。为了对比不同算法的性能, 采用聚类准确率(ACC: Accuracy)[26]作为评价标准, ACC的定义如下

/n

(6)

其中n表示聚类的样本总数,ci是第i个样本的真实类标签,li是通过k均值算法获得的第i个样本的标签, map()是将每个类标签li映射到相应的实际标签ci的映射函数。如果ci=map(li),σ(ci=map(li))的值为1, 否则值为0。从式(6)可以看出, ACC的值越大, 表明算法的聚类性能越好。然而, 由于k均值算法的性能受随机初始化影响, 因此执行20次随机初始化聚类实验, 并记录不同算法的平均聚类准确率以及相应的标准差。另外, 各个算法中参数的设置与分类实验相同, 这里不再赘述。

聚类实验所用的数据集包括ORL数据集和COIL 20数据集, 其具体信息如表2所示。图2为不同算法在两个数据集的聚类对比结果。

表2 聚类实验中所用数据集的介绍

由图1和图2中可以看出, 在分类实验和聚类实验中, 所有方法的识别性能在一定范围内都大体均随着子空间维数的增加而有明显的提高。其中LPP算法和NPE算法使用人为预定义的k近邻准则构图, 这对算法的性能有着一定的影响； LSR-NPE算法和LRR-NPE算法利用稀疏表示构图, 然而它们不能始终准确地描述输入数据的分布信息； 笔者提出的DRAG算法利用自适应的关联图执行降维, 考虑了样本点的局部信息和噪声信息, 有效利用了数据的本质结构, 提高了算法性能。因此, DRAG的分类和聚类最高识别率始终优于其他对比方法。

a ORL b COIL 20图2 不同算法在不同数据库上的聚类识别率随特征维数的变化曲线Fig.2 Curves of clustering accuracy of different algorithms with the feature dimension

3 结 语

笔者提出了一种基于自适应图的降维方法(DRAG), 以提高基于图的降维方法的分类和聚类的准确率。该方法旨在利用文献[23]中的思想去同时学习数据表示和它们的关联矩阵, 以得到自适应的最优图结构, 再结合LPP模型学习投影矩阵, 达到最终的数据降维的目的。在几个典型的数据集上做了分类和聚类实验, 实验结果表明提出DRAG方法的有效性。