3.1 Chapter Introduction
Clustering, the task of discovering natural groupings based on the input data
patterns, has been one of the most active research topics in machine learning and
knowledge discovery. As a powerful unsupervised data analysis technique, clustering
is especially desirable for modeling large datasets because the tedious and often
inconsistent manual classification and labeling process can be avoided. While many
traditional clustering algorithms have been developed over the past few decades
[74] [42], some popular ones that emerged over the last decade generate promising
results on various challenging tasks. Among them, spectral clustering [109] [126]
[157] [25] [16] [146] demonstrates excellent performance to detect clusters with
complex shapes and complicated input space distributions.