# Laplacian Eigenmaps Dimensionality Reduction Based on Clustering-Adjusted Similarity
## 2 Methodology
### Laplacian Eigenmap-Based Clustering-Adjusted Similarity  
Based on the clustering-adjusted similarity, we present the procedure of LE-CAS as follows, and the influence of our improved method is also shown in Figure 1.  
1. Carry out kernel \(k\)-means clustering on the original dataset \(\mathbf{X}\), the original data is clustered into \(k_{1}\) classes. During the clustering, we first use an nonlinear mapping function to map the instances from the original space \(\mathbb{R}^{n\times d}\) to a higher-dimensional space \(F\), and then clustering in this space. \[\phi:\mathbb{R}^{n\times d}\to F,x\rightarrow\phi(x)\] (6) The instances of the original space becomes \[\left[\phi\left(x_{1}\right);\cdots;\phi\left(x_{n}\right)\right]\] (7)On this basis, kernel clustering is to minimize the following criterion function, \(t_{i}^{\phi}\) is the class-mean of \(i\)-th cluster.  
\[J^{\phi}=\sum_{i=1}^{k_{1}}\sum_{p\in\mathcal{C}_{i}}\left\|\phi(p)-t_{i}^{\phi} \right\|^{2} \tag{8}\]  
\[t_{i}^{\phi}=\frac{1}{\left|\mathcal{C}_{i}\right|}\sum_{p\in\mathcal{C}_{i}} \phi(p) \tag{9}\]  
After clustering, we get the following groups:  
\[\mathcal{C}=\left\{\mathcal{C}_{1},\mathcal{C}_{2},\ldots,\mathcal{C}_{k_{1}}\right\} \tag{10}\]
2. Construct a graph with the edge weight between \(\mathbf{x}_{i}\) and \(\mathbf{x}_{j}\) specified as Equation (1) (\(\mathbf{x}_{i}\), \(\mathbf{x}_{j}\) are instances in \(\mathbf{X}\)). Set up edges between each point and its nearest \(k_{2}\) points via \(k\)NN method, \(k_{2}\) is a preset value. This graph will continue to be used in the following steps.
3. To determine the weight between points, which is different from typical LE method, the adjusted weight matrix \(\tilde{\mathbf{W}}_{ij}\) calculated according to Equation (11) before is selected as the final weight matrix of the previous graph. \(\sigma_{m}>0\) is Gaussian heat kernel width, \(\mathbf{u}_{h_{1}}\), \(\mathbf{u}_{h_{2}}\) represents the cluster centroids of the cluster which \(\mathbf{x}_{i}\) and \(\mathbf{x}_{j}\) belongs to. \(\mathbf{l}_{i}\), \(\mathbf{l}_{j}\) are indicative vectors. \[\tilde{\mathbf{W}}_{ij}=\left\{\begin{array}{c}\exp\left(-\frac{\left\| \mathbf{x}_{i}-\mathbf{x}_{j}\right\|^{2}}{\sigma_{m}^{2}}\right),\text{ if }\mathbf{l}_{i}= \mathbf{l}_{j}\\ \exp\left(-\frac{\left\|\mathbf{u}_{h_{1}}-\mathbf{u}_{h_{2}}\right\|^{2}}{ \sigma_{m}^{2}}\right)\times\exp\left(-\frac{\left\|\mathbf{x}_{i}-\mathbf{x} _{j}\right\|^{2}}{\sigma_{m}^{2}}\right),\text{ if }\mathbf{l}_{i}\
eq\mathbf{l}_{j}\end{array}\right.\] (11)
4. Construct graph Laplace matrix \(\mathbf{L}\), \(\mathbf{D}\) is a diagonal matrix with its \((i,i)\)-element equal to the sum of the \(i\) th row of \(\tilde{\mathbf{W}}_{ij}\) \[\mathbf{D}_{ii}=\sum_{j=1}^{n}\tilde{\mathbf{W}}_{ij}\] (12)  
\[\mathbf{L}=\mathbf{D}-\tilde{\mathbf{W}}_{ij} \tag{13}\]
5. The objective function of Laplace feature mapping optimization is as follows: \[\min\sum_{i,j}\left\|\mathbf{y}_{i}-\mathbf{y}_{j}\right\|^{2}\tilde{\mathbf{ W}}_{ij}\] \(\mathbf{y}_{i}\) and \(\mathbf{y}_{j}\) are the representation of instance \(i\), \(j\) in the target \(c\)-dimensional subspace \(\mathbf{Y}\). The objective function after transform is as follows: \[\min\text{trace}\left(\mathbf{Y}^{\text{T}}\mathbf{L}\mathbf{Y}\right),\text{ s.t. }\mathbf{Y}^{\text{T}}\mathbf{L}\mathbf{Y}=\mathbf{I}\] (14) Where the constraint function \(\text{ s.t. }\mathbf{Y}^{\text{T}}\mathbf{L}\mathbf{Y}=\mathbf{I}\) guarantees the optimization problem has solutions.
6. Do feature mapping, and calculate the eigenvectors and eigenvalues of \(\mathbf{L}\). The column vectors of \(\mathbf{Y}\) that minimize the formula are the eigenvectors corresponding to \(c\) minimum non-zero eigenvalues (including multiple roots) of the generalized eigenvalue problem. The smallest \(c\) eigenvectors which are correspond to the non-zero eigenvalues are used as the output after dimensionality reduction. \[\mathbf{L}\mathbf{y}=\lambda\mathbf{D}\mathbf{y}\] (15)