Visual Analysis of Multidimensional Data Using Fast MDS algorithm

摘要

We discuss here an improved multidimensional scaling (MDS) algorithm allowing for fast and accurate visualization of multidimensional clusters. Unlike in traditional approaches we use a natural heuristics - N-body solver - for extracting the global minimum of the multidimensional, multimodal and nonlinear "stress function". As was shown earlier, the method is very reliable avoiding stuck the solver in local minima. We focus on decreasing the time complexity of the algorithm from Ω(N~2) to O(N~2) by eliminating from computations most of distances, which are irrelevant in reproducing the real cluster structure in low dimensional spaces. This way we can speed up MDS algorithm significantly (even in order of magnitude for large datasets) allowing for interactive immersion into the data by immediate on-screen manipulation on different data representations.