基于锚点的快速无监督图嵌入

摘要：

图嵌入降维算法由于其有效性被广泛应用.传统图嵌入算法构造K-Nearest Neighbors(K-NN)图的计算复杂度至少为O(n2 d),其中n为样本数,d为样本维度.在数据量大的情况下,构造K-NN图将非常耗时,因为其计算复杂度与样本数的平方成正比,这将限制图嵌入算法在大规模数据集上的应用.为降低构图过程的计算复杂度,提出一种基于锚点的快速无监督图嵌入算法(Fast Unsupervised Graph Embedding Based on Anchors,FUGE).该算法首先从数据集中选取锚点(代表点),然后构造数据点-锚点相似度图,最后执行图嵌入分析.由于锚点数量远小于数据量,所提方法能有效地降低构图过程的计算复杂度;不同于使用核函数来构造相似度图,该算法直接通过数据点的近邻信息来学习数据点-锚点的相似度图,这进一步加快了构图过程.整个算法的计算复杂度为O(nd2+nmd),其中m为锚点数.在基准数据集上的大量实验证明了所提算法的有效性和高效性.

关键词：降维、图嵌入、锚点、K-means++、正交约束

所属期刊栏目：49

分类号：TP391(计算技术、计算机技术)

资助基金：国家自然科学基金;国家自然科学基金;国家自然科学基金;江西省自然科学基金;江西省自然科学基金;江西省教育厅科技计划

在线出版日期：2022-04-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：116-123