Title: Unified Spectral Clustering with Optimal Graph,
Abstract: Spectral clustering has found extensive use in many areas. Most traditional
spectral clustering algorithms work in three separate steps: similarity graph
construction; continuous labels learning; discretizing the learned labels by
k-means clustering. Such common practice has two potential flaws, which may
lead to severe information loss and performance degradation. First, predefined
similarity graph might not be optimal for subsequent clustering. It is
well-accepted that similarity graph highly affects the clustering results. To
this end, we propose to automatically learn similarity information from data
and simultaneously consider the constraint that the similarity matrix has exact
c connected components if there are c clusters. Second, the discrete solution
may deviate from the spectral solution since k-means method is well-known as
sensitive to the initialization of cluster centers. In this work, we transform
the candidate solution into a new one that better approximates the discrete
one. Finally, those three subtasks are integrated into a unified framework,
with each subtask iteratively boosted by using the results of the others
towards an overall optimal solution. It is known that the performance of a
kernel method is largely determined by the choice of kernels. To tackle this
practical problem of how to select the most suitable kernel for a particular
data set, we further extend our model to incorporate multiple kernel learning
ability. Extensive experiments demonstrate the superiority of our proposed
method as compared to existing clustering approaches.