Improved spectral clustering using three-way decisions

Spectral clustering is an unsupervised machine learning algorithm that groups similar data points into clusters. The method generally works by modeling pair-wise data points as input similarity matrices, and then performs their eigen-decomposition. Clustering is then carried out from this high-dimensional representation by utilizing spectral properties. Here, several eigen-points are mapped and merged to a lower dimensional sub-space iteratively. In contrast to traditional methods, spectral clustering is well poised to solve problems involving complex patterns. However, the approach is sensitive to outliers, measurement errors, or perturbations in the original data. These then appear in the form of increased levels of spectral noise, especially in the higher ordered eigen-vectors. Consequently, the application of pre-processing and noise reduction techniques are important for its performance. In this article, we address this issue by introducing a three-way decision based approach to spectral clustering in order to make it insensitive to noise. Three-way decisions are classically applied to problems involving uncertainty and follow a ternary classification system involving actions of acceptance, rejection, and non-commitment. The proposed approach is tested on various standard datasets for verification and validation purposes. Results on the basis of these datasets demonstrate that the proposed approach outperforms classical spectral clustering by an average of 30%.