Adaptive Nonparametric Clustering
Kirill Efimov, Larisa Adamyan, Vladimir Grigor'evich Spokoiny · IEEE Transactions on Information Theory · 2019
This paper presents a new approach to non-parametric cluster analysis called adaptive weights' clustering. The method is fully adaptive and does not require to specify the number of clusters or their structure. The clustering results are not sensitive to noise and outliers, and the procedure is able to recover different clusters with sharp edges or manifold structure. The method is also scalable and computationally feasible. Our intensive numerical study shows a state-of-the-art performance of the method in various artificial examples and applications to text data. The idea of the method is to identify the clustering structure by checking at different points and for different scales on departure from local homogeneity. The proposed procedure describes the clustering structure in terms of weights wij, and each of them measures the degree of local inhomogeneity for two neighbor local clusters using statistical tests of “no gap” between them. The procedure starts from very local scale, and then, the parameter of locality grows by some factor at each step. We also provide a rigorous theoretical study of the procedure and state its optimal sensitivity to deviations from local homogeneity.