## 3 KMDS Method
### Multidimensional Scaling (MDS) Method
Assume that the following Formulas (16)-(18) hold, Equation (19) can be obtained due to Equations (12)-(18):  
\[h_{1}=\frac{1}{m}\sum\limits_{j=1}^{m}t_{ij}^{2} \tag{16}\]  
\[h_{2}=\frac{1}{m}\sum\limits_{i=1}^{m}t_{ij}^{2} \tag{17}\]  
\[h_{3}=\frac{1}{m^{2}}\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{m}t_{ij}^{2} \tag{18}\]  
The inner product matrix \(\mathbf{B}\) can be obtained through the derivation of Equation (19) and the distance matrix \(\mathbf{T}\), which remains unchanged before and after dimensionality reduction. \[ \begin{split} b_{ij}&=-\frac{1}{2}\left(t_{ij}^{2}- b_{ii}-b_{jj}\right)\\ &=-\frac{1}{2}\left(t_{ij}^{2}-\frac{1}{m}\left(\sum\limits_{j=1 }^{m}t_{ij}^{2}-tr(\mathbf{B})\right)-\frac{1}{m}\left(\sum\limits_{i=1}^{m}t_{ij }^{2}-tr(\mathbf{B})\right)\right)\\ &=-\frac{1}{2}\left(t_{ij}^{2}-h_{1}-h_{2}+\frac{2}{m}tr(\mathbf{B} )\right)\\ &=-\frac{1}{2}\left(t_{ij}^{2}-h_{1}-h_{2}+h_{3}\right)\end{split}  \tag{19}\]  
The eigenvalue decomposition of matrix \(\mathbf{B}\) is performed in Equation (20) to complete the dimensionality reduction:  
\[\mathbf{B}=\mathbf{V}\mathbf{\Lambda}V^{T} \tag{20}\]  
where parameter \(\mathbf{\Lambda}=diag(\lambda_{1},\lambda_{2},\ldots,\lambda_{d})\) is the diagonal matrix composed of eigenvalues and \(\lambda_{1}\geq\lambda_{2}\geq\ldots\geq\lambda_{d}\), \(\mathbf{V}\) is the eigenvector matrix, since \(\mathbf{\Lambda}\) is a diagonal matrix, \(\mathbf{\Lambda}=\mathbf{\Lambda}^{T}\). According to Equation (12) and \(\mathbf{B}=\mathbf{Z}^{T}\mathbf{Z}\), the Equations (21) and (22) can be formed:  
\[\mathbf{B}=\mathbf{Z}^{T}\mathbf{Z}=\mathbf{V}\mathbf{\Lambda}\mathbf{V}^{T}=\mathbf{V}\sqrt{\mathbf{\Lambda} ^{T}}\sqrt{\mathbf{\Lambda}}\mathbf{V}^{T} \tag{21}\]  
\[Z=\sqrt{\mathbf{\Lambda}}V^{T} \tag{22}\]  
Assuming that there are \(d^{*}\) non-zero eigenvalues, they form a diagonal matrix \(\mathbf{\Lambda}_{*}=diag(\lambda_{1},\lambda_{2},\ldots,\lambda_{d^{*}})\) ). Let \(\mathbf{V}_{*}\) denote the corresponding eigenvector matrix, then \(\mathbf{Z}\) can be expressed as follows:  
\[\mathbf{Z}=\mathbf{\Lambda}_{*}^{1/2}\mathbf{V}_{*}^{T}\in\mathbb{R}^{d^{*}\times m} \tag{23}\]  
In practical applications, in order to reduce the dimensionality effectively, it is often only necessary that the distance in the space after dimensionality reduction is as close as possible to the distance in the original space, and does not have to be strictly equal. Next, arrange the \(d^{*}\) non-zero eigenvalues in order from largest to smallest (it is worth noting that the order has been arranged during eigenvalue decomposition in MATLAB), and take the first \(d^{\prime}\) (\(d^{\prime}<<d^{*}\)) eigenvalues as a low-dimensional diagonal matrix \(diag(\lambda_{1},\lambda_{2},\ldots,\lambda_{d^{\prime}})\). At this time, let \(\widetilde{\mathbf{V}}\) denote the corresponding eigenvector matrix, then \(\mathbf{Z}\) can be expressed by Equation (24):  
\[\mathbf{Z}=\widetilde{\mathbf{\Lambda}}^{1/2}\widetilde{\mathbf{V}}^{T}\in\mathbb{R}^{d^{ \prime}\times m} \tag{24}\]  
Based on the above analysis, the MDS method can be simply described in Algorithm 1. ```
Input: Distance matrix \(\mathbf{T}\in\mathbb{R}^{m\times m}\); low-dimensional space dimension \(d^{\prime}\). Output: Matrix \(\widetilde{\mathbf{V}}\widetilde{\mathbf{\Lambda}}^{1/2}\in\mathbb{R}^{m\times d}\). Process:
1: Calculate \(h_{1}\), \(h_{2}\) and \(h_{3}\) according to Equations (16)-(18);
2: Calculate the inner product matrix \(\mathbf{B}\) according to Equation (19);
3: Perform eigenvalue decomposition on inner product matrix \(\mathbf{B}\);
4: Take \(\widetilde{\mathbf{\Lambda}}\) as the diagonal matrix composed of \(d^{\prime}\) maximum eigenvalues, and \(\widetilde{\mathbf{V}}\) as the corresponding eigenvector matrix. ```  
**Algorithm 1** Multidimensional scaling (MDS) method