| 基于分而治之的多维标度算法 |
| |
| 引用本文： | 屈太国,蔡自兴.基于分而治之的多维标度算法[J].模式识别与人工智能,2014(11). |
| |
| 作者姓名： | 屈太国 蔡自兴 |
| |
| 作者单位： | 中南大学 信息科学与工程学院 长沙410083 |
| |
| 基金项目： | 国家自然科学基金重大专项项目，国家自然科学基金面上项目，国家博士点基金项目 |
| |
| 摘 要： | 作为一种典型的多元统计分析方法,多维标度法(MDS)广泛应用于降维和可视化研究中.MDS从n个样本间的距离距阵出发,求取它们在低维欧氏空间的坐标.经典MDS算法(CMDS)的时间复杂度为Θ(n3),影响MDS的速度.文中基于分而治之的思想提出一种新的MDS算法.首先将距离矩阵沿对角线分成若干子矩阵,然后对每个子矩阵求解,最后通过正交变换和平移变换整合各子矩阵的解,从而得到原距离矩阵的全局解.该算法的结果与CMDS完全一致.当样本维数远小于样本个数时,其时间复杂度仅为Θ(nlgn).与CMDS算法相比,该算法的速度大大提高,从而使MDS可应用于更大规模数据集.
|
| 关 键 词： | 多维标度法 保距变换 分而治之 整合 |
A Divide-and-Conquer Based Multidimensional Scaling Algorithm |
| |
| QU Tai-Guo,CAI Zi-Xing.A Divide-and-Conquer Based Multidimensional Scaling Algorithm[J].Pattern Recognition and Artificial Intelligence,2014(11). |
| |
| Authors: | QU Tai-Guo CAI Zi-Xing |
| |
| Abstract: | |
| |
| Keywords: | Multidimensional Scaling Isometric Transformation Divide-and-Conquer Alignment |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
