Data Mining

15

Multidimensional Scaling

Multidimensional scaling (MDS) aims at representing high-dimensional data in a low-dimensional space so that data can be visualized, analyzed, and interpreted in the low-dimensional space to uncover useful data patterns. This chapter describes MDS, software packages supporting MDS, and some applications of MDS with references.

15.1  Algorithm of MDS

We are given n data items in the p-dimensional space, x_i = (x_i1, …, x_ip), i = 1, …, n, along with the dissimilarity δ_ij of each pair of n data items, x_i and x_j, and the rank order of these dissimilarities from the least similar pair to the most similar pair:

${\text{δ}}_{i_1{j}_1}\le {\text{δ}}_{i_2{j}_2}\le \cdots \le {\text{δ}}_{i_M{j}_{M^{\prime }}}$

(15.1)

where M denotes the total number of different data pairs, and M = n(n