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

• 作者: 杨辉 陶力宏 朱建勇 聂飞平
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 降维 图嵌入 锚点 K-means++ 正交约束
• 年，卷（期）: 2022,（4）
• 所属期刊栏目: 数据库&大数据&数据科学|Database & Big Data & Data Science
• 页码范围: 116-123
• 页数: 8页
• 分类号: TP391
• 语种: 中文
• DOI: 10.11896/jsjkx.210200098

摘要

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