  Clustering is the problem of separating a set of objects into groups (called
clusters) so that objects within the same cluster are more similar to each
other than to those in different clusters. Spectral clustering is a now
well-known method for clustering which utilizes the spectrum of the data
similarity matrix to perform this separation. Since the method relies on
solving an eigenvector problem, it is computationally expensive for large
datasets. To overcome this constraint, approximation methods have been
developed which aim to reduce running time while maintaining accurate
classification. In this article, we summarize and experimentally evaluate
several approximation methods for spectral clustering. From an applications
standpoint, we employ spectral clustering to solve the so-called attrition
problem, where one aims to identify from a set of employees those who are
likely to voluntarily leave the company from those who are not. Our study sheds
light on the empirical performance of existing approximate spectral clustering
methods and shows the applicability of these methods in an important business
optimization related problem.
