快速多维标度算法研究

来源：计算机科学与探索杂志2018年第4期北京时间：

作者：屈太国，蔡自兴

单位：1. 衡阳师范学院 计算机科学与技术学院，湖南 衡阳 4210022. 智能信息处理与应用湖南省重点实验室，湖南 衡阳 4210023. 中南大学 信息科学与工程学院，长沙 410083

摘要：经典多维标度法（classical multidimensional scaling，CMDS）是一种常用的数据降维和可视化方法。随着数据规模的扩大，CMDS的运算时间急剧增加。为了提高CMDS的计算速度，研究了3种适用于不同距离矩阵的快速算法。通过预先确定枢轴，减少了不必要的距离计算，提出了一种基于FastMap的快速算法。基于分而治之策略，提出了一种新的算法dcMDS（divide-and-conquer based MDS）。通过合理地选择标志点集，确保LMDS（landmark multidimensional scaling）能得到与CMDS一致的解。当样本内在维数远小于样本个数时，这些算法都能得到与CMDS完全一致的解，并且在速度上有大幅提高。实验证实了这3种算法与CMDS的一致性以及高效性。

关键词：经典多维标度法,iLMDS,iFastMap,dcMDS