## 3 KMDS Method  
### Multidimensional Scaling (MDS) Method  
In most cases, although the sample data that people observe or collect are high-dimensional, they may only be low-dimensionally distributed and closely related to the learning task. Generally speaking, a good dimensionality reduction method can usually greatly reduce the computational cost while preserving most of the function information. Dimensionality reduction means transforming the original high-dimensional attribute space into a low-dimensional \"subspace\" through a certain mathematical transformation. Multidimensional scaling (MDS) [40; 41; 42; 43] can alleviate the problems associated with sparse sample data and the difficulty of distance calculations in high-dimensional situations. Different from the idea of linear dimensionality reduction, multidimensional scaling pays more attention to the internal characteristics of high-dimensional data. It focuses on preserving the \"similarity\" of information in the high-dimensional space, and the \"similarity\" is usually defined by the Euclidean distance. That is to say, the main idea of this work is to keep the distance between samples in the original space unchanged in the low-dimensional space. Assume that the distance matrix of \(m\) samples in the original space is matrix \(\mathbf{T}\in\mathbb{R}^{m\times m}\) (Equation (11)), where the element \(t_{ij}\) in the \(i\)-th row and \(j\)-th column is the distance from sample \(\boldsymbol{x}_{i}\) to sample \(\boldsymbol{x}_{j}\). \[\mathbf{T}=\left[ \begin{array}{cccc}t_{11}&t_{12}&\cdots&t_{1m}\\ t_{21}&t_{22}&\cdots&t_{2m}\\ \vdots&\vdots&\ddots&\vdots\\ t_{m1}&t_{m2}&\cdots&t_{mm}\end{array} \right]=\left[ \begin{array}{cccc}0& \|\boldsymbol{x}_{1}-\boldsymbol{x}_{2}\|&\cdots&\|\boldsymbol{x}_{1}- \boldsymbol{x}_{m}\|\\ \|\boldsymbol{x}_{2}-\boldsymbol{x}_{1}\|&0&\cdots&\|\boldsymbol{x}_{2}- \boldsymbol{x}_{m}\|\\ \vdots&\vdots&\ddots&\vdots\\ \|\boldsymbol{x}_{m}-\boldsymbol{x}_{1}\|&\|\boldsymbol{x}_{m}-\boldsymbol{ x}_{2}\|&\cdots&0\end{array} \right] \tag{11}\]  
The goal of dimensionality reduction is to obtain the representation \(\mathbf{Z}\in\mathbb{R}^{d^{\prime}\times m}\) of the sample in the \(d^{\prime}(d^{\prime}\leq d)\) dimensional space, and the Euclidean distance of any two samples in the \(d^{\prime}\) dimensional space is equal to the distance in the original space; that is, \(\|\boldsymbol{z}_{i}-\boldsymbol{z}_{j}\|=t_{ij}\). Let \(\mathbf{B}=\mathbf{Z}^{T}\mathbf{Z}\in\mathbb{R}^{m\times m}\), where \(\mathbf{B}\) is the inner product matrix of the sample data after dimensionality reduction, and the calculation formula of each element in \(\mathbf{B}\) is \(b_{ij}=\boldsymbol{z}_{i}^{T}\boldsymbol{z}_{j}\). Therefore, the relationship between \(\mathbf{T}\) and \(\mathbf{B}\) can be stated by Equation (12):  
\[ \begin{array}{l}t_{ij}^{2}=\|\boldsymbol{z}_{i}-\boldsymbol{z}_{j}\|^{2}\\ \phantom{t_{ij}^{2}=}=\|\boldsymbol{z}_{i}\|^{2}+\|\boldsymbol{z}_{j}\|^{2}-2 \boldsymbol{z}_{i}^{T}\boldsymbol{z}_{j}\\ \phantom{t_{ij}^{2}=}=b_{ii}+b_{jj}-2b_{ij}\end{array}  \tag{12}\]  
Center the sample \(\mathbf{Z}\) after dimensionality reduction; that is, \(\sum_{i=1}^{m}\boldsymbol{z}_{i}=0\) (\(0\in\mathbb{R}^{d^{\prime}}\) is a vector of all zeros). Obviously, the sum of all rows and the sum of all columns in matrix \(\mathbf{B}\) are both zero, i.e., \(\sum_{i=1}^{m}b_{ij}=\sum_{j=1}^{m}b_{ij}=0\). Under this condition, Equations (13)-(15) can be generated from Equation (12):  
\[ \begin{array}{l}\sum_{i=1}^{m}t_{ij}^{2}=\sum_{i=1}^{m}b_{ii}+\sum_{i=1}^{m }b_{jj}-2\sum_{i=1}^{m}b_{ij}\\ \phantom{t_{ij}^{2}=}=tr(\mathbf{B})+mb_{jj}\end{array}  \tag{13}\]\[\sum\limits_{j=1}^{m}t_{ij}^{2}=tr(\mathbf{B})+mb_{ii} \tag{14}\]  
\[\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{m}t_{ij}^{2}=2 mtr(\mathbf{B}) \tag{15}\]  
where the symbol \(tr(\cdot)\) refers to the trace of the matrix, and the trace of the inner product matrix \(\mathbf{B}\) is \(tr(\mathbf{B})=\sum\limits_{i=1}^{m}\left\|\mathbf{z}_{i}\right\|^{2}\).