## 3 Machine Learning Techniques for Data Preprocessing
### Data Cluster Analysis  
#### 3.2.1 k-Nearest-Neighbor  
Cluster analysis refers to the process of dividing a given data set into several groups based on the similarity or the distance between two samples without prior information, and it is beneficial to further explore and mine the essence of the data [43]. Spectral clustering is a popular clustering method based on graph theory. The cluster task is achieved by clustering the eigenvectors of the Laplacian matrix for the sample set [44]. It can be explained that the core of spectral clustering is to map the points from high-dimensional space to low-dimensional space, and some clustering algorithms are used in low-dimensional space. A similarity matrix is an important index in spectral clustering, and it is constructed according to the distance metric among all points [45]. In the spectral clustering algorithm, the similarity between two points with a short distance is relatively high, otherwise the similarity is relatively low. The similarity matrix can be built up through three ways: \(\varepsilon\)-neighborhood graph, k-nearest-neighbor graph and fully connected graph [46]. Among these three manners, \(\varepsilon\)-neighborhood graph and fully connected graph probably lose more information, which leads to less accurate results. In contrast, the k-nearest-neighbor graph generally has a precise calculation result. Meanwhile, it is simple and easy to realize [47].  
The first step of spectral clustering is to establish a weighted graph \(G=(\
u,\varepsilon)\), where \(\
u\) is the set of \(n\) nodes and \(\varepsilon\) is a collection of edges among nodes. Let \(\widetilde{\mathbf{A}}=(\widetilde{\mathbf{a}}_{1},\widetilde{\mathbf{a}}_{2},\ldots \widetilde{\mathbf{a}}_{n})\). The \(i\)-th node corresponds to the processed observation vector \(\widetilde{\mathbf{a}}_{i}\). Constructing the similarity graph is the most crucial task for spectral clustering. Among the existing approaches, the k-nearest-neighbor graph is generally recommended as the first choice. Next, we introduce the construction process of the similarity matrix based on the k-nearest-neighbor graph.  
In a manifold space, there exists an approximate liner relationship among the adjacent points. Under this circumstance, the distance between \(\widetilde{\mathbf{a}}_{i}\) and \(\widetilde{\mathbf{a}}_{j}\) is calculated by \(d_{ij}=\left\|\widetilde{\mathbf{a}}_{i}-\widetilde{\mathbf{a}}_{j}\right\|_{2}\), where \(\left\|\cdot\right\|_{2}\) is the \(l_{2}\)-norm of a vector. Given \(\widetilde{\mathbf{a}}_{i}\), we first compute \(n-1\) distances \(\{d_{i1},d_{i2},\ \ldots,d_{i,i-1},d_{i,i+1},\ldots,d_{im}\}\) and then sort them by the increasing order. Therefore, k nearest neighbors of \(\widetilde{\mathbf{a}}_{i}\) can be found according to k smallest distances. On this basis, we build up a similarity graph G: if \(\widetilde{\mathbf{a}}_{i}\) is one of k nearest neighbors for \(\widetilde{\mathbf{a}}_{i}\) or \(\widetilde{\mathbf{a}}_{j}\) is one of k-nearest-neighbors for \(\widetilde{\mathbf{a}}_{j}\), then an edge is added between the \(i\)-th and the \(j\)-th nodes and the weight \(s_{ij}\) is set to \(1\); otherwise, no edge exists and \(s_{ij}=0\). Eventually, the similarity matrix \(\mathcal{S}=\left(s_{ij}\right)_{n\times n}\) is obtained and it is symmetrized by \(s_{ij}\leftarrow\max\{s_{ij},s_{ji}\}\).