Spectral Clustering And Dimension Reduction Algorithms With Their Applications

In recent years, the data sets collected from many real application problems are often with high dimensionality, which causes the "curse of dimensionality" phenomenon. It is hard for us to discover the intrinsic laws of the data sets because of the high dimensionality. How to extract the meaningful information and low-dimensional representation from the original high-dimensional data has been the common focus of the researchers from the fields of pattern recognition, applied math and computer vision. Dimensionality reduction has been employed as an effective way to solve the problem. Also, spectral clustering is an important method for data mining. This thesis designs some new effective spectral clustering and dimensionality reduction algorithms and applies these new algorithms to image segmentation and face recognition. The main contributions of this thesis are as follows:1. To overcome the sensitivity of the scaling parameter in Gaussian kernel similarity measure in spectral clustering and the difficulty of selecting the scaling parameter, we firstly make a pre-clustering by using kernel fuzzy c-means clustering algorithm and obtain the partition matrix consisting of membership vector. Then, we design a novel similarity measure called kernel fuzzy similarity measure by using the inner product of membership vector. Moreover, we propose a kernel fuzzy similarity based spectral clustering algorithm. Finally, the experiments are conducted and the results show the proposed clustering algorithm can overcome both the sensitivity of scaling parameter of spectral clustering and the difficulty of selecting an appropriate scaling parameter.2. To handle the problems that the Euclidean distance measure cannot accurately express the complex distribution data and the result of spectral clustering is very sensitive to the scaling parameter, a novel similarity measure based on the manifold distance is proposed, where the geodesic distance replaces the traditional Euclidian distance to measure the similarity of data. On this basis, to overcome the drawbacks that K-means clustering in spectral mapping space is sensitive to initialization and is easy to trap into a local optimal solution, a novel simulated annealing spectral clustering is proposed. To test the effectiveness of the proposed algorithm, it is applied to image segmentation. The experimental results show the proposed algorithm can not only efficiently reduce the sensitivity of spectral clustering to the scaling parameter, but also can avoid trapping into local optimal solutions.3. With the increasing of data set scale, the computation amount of spectral clustering increases greatly and quickly. To tackle the problem, firstly, the single pixels are replaced by super-pixel regions by super-pixel segmentation algorithm. Then, an undirected weighted graph is constructed by using the proposed kernel fuzzy similarity measure. Based on this, a spectral clustering method is proposed and used to image segmentation. The experimental results demonstrate that the proposed method can not only improve the quality of the image segmentation, but also reduce the computational complexity for real-time image processing.4. To overcome the drawback of Discriminant Sparse Neighborhood Preserving Embedding (DSNPE) that the construction of its between-class scatter is too complexity, firstly, a new between-class scatter is constructed by preserving the sparse reconstructive relationship of mean face. Then, the objective function of dimension reduction is constructed by maximizing the between-class scatter and minimizing the sparse local compactness simultaneously. Moreover, an improved dimensionality reduction algorithm is proposed. The proposed algorithm can not only efficiently reduce the between-class scatter computation complexity of DSNPE, but also increase the discriminant power. Finally, the proposed algorithm is applied to face recognition and the experimental results show that the proposed algorithm achieves much higher recognition accuracy by comparing with other existing algorithms.