快速多维标度算法研究*
屈太国1,2+，蔡自兴3
1.衡阳师范学院计算机科学与技术学院，湖南衡阳421002
2.智能信息处理与应用湖南省重点实验室，湖南衡阳421002
3.中南大学信息科学与工程学院，长沙410083
Research on Fast Algorithms of Classical Multidimensional Scaling ﹡
QU Taiguo 1,2+,CAI Zixing 3
1.College of Computer Science and Technology,Hengyang Normal University,Hengyang,Hunan 421002,China
2.Hunan Provincial Key Laboratory of Intelligent Information Processing and Application,Hengyang,Hunan 421002,China
3.School of Information Science and Engineering,Central South University,Changsha 410083,China
+Corresponding author:E-mail:qutaiguo88@https://www.doczj.com/doc/923762549.html,
QU Taiguo,CAI Zixing.Research on fast algorithms of classical multidimensional scaling.Journal of Fron-tiers of Computer Science and Technologye,2018,12(4)：671-680.
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
*The National Natural Science Foundation of China under Grant Nos.91220301,61273314,61175064(国家自然科学基金).Received 2017-03,Accepted 2017-05.
CNKI 网络出版:2017-05-09,https://www.doczj.com/doc/923762549.html,/kcms/detail/11.5602.TP.20170509.1052.004.html
ISSN 1673-9418CODEN JKYTA8
Journal of Frontiers of Computer Science and Technology
1673-9418/2018/12(04)-0671-10
doi:10.3778/j.issn.1673-9418.1703010E-mail:fcst@https://www.doczj.com/doc/923762549.html, https://www.doczj.com/doc/923762549.html, Tel:+86-10-89056056万方数据