|
Abstract:
|
Convex clustering has recently gained popularity due to computational advances and useful heuristics that have rendered it practical. While it confers many advantages over traditional clustering methods, it is also limited in the face of high-dimensional data. Not only does the Euclidean measure of fit have less discriminating power, but pairwise affinity terms that rely on k-nearest neighbors (k-NN) become poorly specified. Attempts at sparse convex clustering also suffer from the latte. We introduce feature weights to the convex clustering objective to be optimized jointly. The resulting problem remains well-behaved as a biconvex problem, and admits fast algorithms with convergence guarantees and finite-sample bounds on prediction error. Importantly, it performs feature selection that is driven adaptively by learned clustering information. As the weights change the effective feature space throughout the algorithm, affinities based on k-NN can be recomputed across iterations, largely removing the strong dependence on carefully tuned heuristics to find appropriate affinities beforehand. We thoroughly validate the algorithm on real and simulated data.
|
