判别多维标度特征学习_唐海涛.pdf

2023-05-10计算机应用,Journal of Computer Applications2023,43(5):1323-1329ISSN 1001-9081CODEN JYIIDUhttp：/判别多维标度特征学习唐海涛1，2，王红军1，2*，李天瑞1，2（1.西南交通大学 计算机与人工智能学院，成都 611756；2.综合交通大数据应用技术国家工程实验室（西南交通大学），成都 611756）（通信作者电子邮箱）摘要：传统多维标度方法学习得到的低维嵌入保持了数据点的拓扑结构，但忽略了低维嵌入数据类别间的判别性。基于此，提出一种基于多维标度法的无监督判别性特征学习方法判别多维标度模型（DMDS），该模型能在学习低维数据表示的同时发现簇结构，并通过使同簇的低维嵌入更接近，让学习到的数据表示更具有判别性。首先，设计了DMDS对应的目标公式，体现所学习特征在保留拓扑性的同时增强判别性；其次，对目标函数进行了推理和求解，并根据推理过程设计所对应的迭代优化算法；最后，在12个公开的数据集上对聚类平均准确率和平均纯度进行对比实验。实验结果表明，根据Friedman统计量综合评价DMDS在12个数据集上的性能优于原始数据表示和传统多维标度模型的数据表示，它的低维嵌入更具有判别性。关键词：判别性特征学习；多维标度法；降维；模糊聚类；迭代优化算法中图分类号：TP391.4 文献标志码：ADiscriminative multidimensional scaling for feature learningTANG Haitao1，2，WANG Hongjun1，2*，LI Tianrui1，2（1.School of Computing and Artificial Intelligence，Southwest Jiaotong University，Chengdu Sichuan 611756，China；2.National Engineering Laboratory of Integrated Transportation Big Data Application Technology（Southwest Jiaotong University），Chengdu Sichuan 611756，China）Abstract:Traditional multidimensional scaling method achieves low-dimensional embedding，which maintains the topological structure of data points but ignores the discriminability of the low-dimensional embedding itself.Based on this，an unsupervised discriminative feature learning method based on multidimensional scaling method named Discriminative MultiDimensional Scaling model（DMDS）was proposed to discover the cluster structure while learning the low-dimensional data representation.DMDS can make the low-dimensional embeddings of the same cluster closer to make the learned data representation be more discriminative.Firstly，a new objective function corresponding to DMDS was designed，reflecting that the learned data representation could maintain the topology and enhance discriminability simultaneously.Secondly，the objective function was reasoned and solved，and a corresponding iterative optimization algorithm was designed according to the reasoning process.Finally，comparison experiments were carried out on twelve public datasets in terms of average accuracy and average purity of clustering.Experimental results show that DMDS outperforms the original data representation and the traditional multidimensional scaling model based on the comprehensive evaluation of Friedman statistics，the low-dimensional embeddings learned by DMDS are more discriminative.Key words:discriminative feature learning;multidimensional scaling;dimensionality reduction;fuzzy clustering;iterative optimization algorithm0 引言 许多实际应用中获取到的数据通常具有很高的维度，如绝大多数的图片数据、文本数据和视频数据。高维数据中的冗余信息不仅会降低后续机器学习任务的性能，还会使后续机器学习任务花费更多算力和内存来处理这些数据，即维度灾难1。因此，利用特征学习或降维的方式，通过原始数据得到一个好的低维数据表示成为了许多学者的研究对象。在特征学习的过程中，低维的特征表示在消除原始数据冗余和噪声信息的同时，还要尽可能保留原始数据内在结构。特征学习还有其他许多的应用，包括信息检索2以及聚类3。在特征学习中，根据学习过程中是否使用数据的标注信息分为监督、半监督以及无监督的特征学习方法。经典的无监 督 特 征 学 习 方 法 有 主 成 分 分 析（Principal Component Analysis，PCA）4，它的核心思想是寻找一个正交的投影矩阵，使投影后的数据方差最大。半监督方法有半监督降维（Semi-Supervised Dimensionality Reduction，SSDR）5，它的原理是利用成对约束使低维数据表示更具有判别性。线性判文章编号：1001-9081（2023）05-1323-07DOI：10.11772/j.issn.1001-9081.2022030419收稿日期：2022-04-01；修回日期：2022-05-16；录用日期：2022-05-19。基金项目：国家重点研发计划项目（2020AAA0105101）；国家自然科学基金资助项目（61773324）。作者简介：唐海涛（1999），男，四川南充人，硕士研究生，CCF会员，主要研究方向：特征学习、聚类；王红军（1977），男，四川广安人，副研究员，博士，CCF高级会员，主要研究方向：机器学习、集成学习、数据挖掘；李天瑞（1969），男，福建莆田人，教授，博士，CCF杰出会员，主要研究方向：粗糙集、粒计算、云计算、数据挖掘。第 43 卷计算机应用别分析（Linear Discriminant Analysis，LDA）6是一种经典的有监督特征学习方法，它的思路是寻找一个正交的投影矩阵，使投影后同类中的样本尽可能接近，不同类别的样本尽可能远离。另一种划分方式是线性和非线性的特征学习。PCA和LDA都属于线性的特征学习，优势在于计算快速，并且当有新样本到来时，可以通过投影矩阵快速计算出新样本的数据表示。与 PCA 和 LDA 不同的是，基于流形学习的非线性特征学习则是让低维的数据表示尽可能保留原始数据的局部拓扑结构，比如局部线性嵌入（Locally Linear Embedding，LLE）7，该方法先学习到原始空间中每个样本与邻居间的局部线性关系，然后让数据的低维嵌入尽可能保留在原始空间中学习到的局部线性关系。多维标度法（MultiDimensional Scaling，MDS）8则更看重样本间的非相似度，该方法需要先得到样本的非相似度矩阵，然后寻找一个能够尽可能保持原始样本非相似度的低维嵌入。拉普拉斯特征映射（Laplacian Eigenmaps，LE）9也是流形学习的代表方法之一，它通过图的拉普拉斯矩阵使得原始空间中相近的样本在低维嵌入后也保持相近。非线性特征学习能够很好地发现数据内部潜在的流形结构，但是面临新样本问题10。也有不少算法在投影过程中尽可能保持局部拓扑结构，比如局部保持投影（Locality Preserving Projection，LPP）11和 近 邻 保 持 嵌 入（Neighborhood Preserving Embedding，NPE）12，就是分别在LE和LLE的基础上增加了投影矩阵。本文提出了一种基于多维标度法的无监督判别性特征学 习 方 法 判 别 多 维 标 度 模 型（Discriminative MultiDimensional Scaling model，DMDS）。该方法一方面使相似度低的样本在低维嵌入中远离，另一方面让相似度高的样本在低维嵌入中尽可能靠近其簇中心，从而使学习到的低维数据表示更具有判别性。该方法使用迭代更新算法求解，并且在 12个公开数据集进行对比实验。结果表明，经过该方法学习到的特征相较于原始空间和传统多维标度法13更具判别性。本文的主要工作包括：1）提出了DMDS及其对应的目标公式，该目标公式体现了所学习特征在保留拓扑性的同时能增强判别性；DMDS能在学习低维数据表示的同时发现簇结构，并使同簇的低维数据表示更接近。2）使用迭代优化方法近似求解目标函数，并根据推理过程设计了相应的算法。3）在 12个公开数据集上进行实验，评价指标采用聚类平均准确率和平均纯度，实验结果表明DMDS得到的低维嵌入更具有判别性。1 相关工作 为了更清晰地了解公式的物理意义，表1先总结了本文所使用的不同符号的含义。1.1多维度标度法给定原始数据矩阵X=x1，x2，xN Rn N，其中 n 和N分别表示原始样本的维度和个数；学习到的低维数据表示Y=y1，y2，yN Rl N，l表示低维数据表示的维度。MDS作为一种保持样本距离的特征学习方法，它的损失函数14为：Emds(Y)=12i=1N j=1Nsij(dij-d?ij)2（1）其中：dij表示原始数据点xi和xj的距离，d?ij表示对应的低维数据表示yi和yj的距离；S=sij RN N是一个非负对称的权重矩阵，sij越大，表示越希望d?ij接近dij。文献 9 中给出了两种权重构造方式：1）热核权重（heat kernel weight）：如果xi与xj或xj与xi近邻，则sij=exp-xi-xj22 t；否则sij=0。其中 t 是一个实数。2）0-1 权重：如果xi与xj或xj与xi近邻，则sij=1；否则sij=0。式（1）中的MDS是一种非线性的特征学习方法，得到的直接是低维数据表示 Y，如果有新的数据到来，它对应的低维数据表示不能直接获取。所以 Webb13将投影矩阵融入MDS，提出了带有投影矩阵的MDS（Projective MDS，PMDS），目标公式为：Epmds(W)=i=1Nj=1Nsi