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