| |
Abstract:
Despite many empirical successes of
spectral clustering
methods -- algorithms that cluster points using eigenvectors of
matrices derived from the data -- there are several unresolved
issues. First, there are a wide variety of algorithms that use
the eigenvectors in slightly different ways. Second, many of
these algorithms have no proof that they will actually compute a
reasonable clustering. In this paper, we present a simple
spectral clustering algorithm that can be implemented using a few
lines of Matlab. Using tools from matrix perturbation theory, we
analyze the algorithm, and give conditions under which it can be
expected to do well. We also show surprisingly good experimental
results on a number of challenging clustering problems.
|
