快速多维标度算法研究

摘要：

经典多维标度法(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

所属期刊栏目：12

分类号：TP301.6(计算技术、计算机技术)

资助基金：The National Natural Science Foundation of China under Grant Nos.91220301,61273314,61175064

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

页数：共10页

页码：671-680