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

Abstract: Classical multidimensional scaling (CMDS) is a commonly used method for dimensionality reduction and data visualization. With the rapid growth in data size, the running time of CMDS increases dramatically. To speed up CMDS, this paper studies three fast algorithms, which are suitable for applications with different distance matrices. By selecting the pivots in advance, the unnecessary calculation of distance is avoided, therefore, a fast algorithm based on FastMap is put forward. Based on divide-and-conquer strategy, a new fast algorithm called dcMDS (divide-and-conquer based MDS) is proposed. By properly choosing landmark points, the LMDS (landmark multidimensional scaling) is ensured to get the same solution as that of CMDS. When the intrinsic dimension of the sample is far less than the sample size, these algorithms can obtain the same solutions as that of CMDS with high speed. The experimental results verify the consistency with CMDS and the efficiency of these fast algorithms.

Key words: classical multidimensional scaling, iLMDS, iFastMap, dcMDS