QUAC: Quick unsupervised anisotropic clustering

• Completely unsupervised clustering algorithm for multidimensional data.
• Anisotropic—it does not assume spherical clusters or use isotropic kernels.
• Fast—an excellent tool for performing rapid cluster analysis on data—much faster than mean-shift.
• Excellent initialisation for a Gaussian mixture model.
• Qualitative and quantitative results show superiority over well-known methods in accuracy and speed.

We present a novel unsupervised algorithm for quickly finding clusters in multi-dimensional data. It does not make the assumption of isotropy, instead taking full advantage of the anisotropic Gaussian kernel, to adapt to local data shape and scale. We employ some little-used properties of the multivariate Gaussian distribution to represent the data, and also give, as a corollary of the theory we formulate, a simple yet principled means of preventing singularities in Gaussian models. The efficacy and robustness of the proposed method are demonstrated on both real and artificial data, providing qualitative and quantitative results, and comparing against the well known mean-shift and K-means algorithms.