Centroid-Based Clustering with αβ-Divergences

Abstract

Centroid-based clustering is a widely used technique within unsupervised learning algorithms in many research fields. The success of any centroid-based clustering relies on the choice of the similarity measure under use. In recent years, most studies focused on including several divergence measures in the traditional hard k-means algorithm. In this article, we consider the problem of centroid-based clustering using the family of α β -divergences, which is governed by two parameters, α and β . We propose a new iterative algorithm, α β -k-means, giving closed-form solutions for the computation of the sided centroids. The algorithm can be fine-tuned by means of this pair of values, yielding a wide range of the most frequently used divergences. Moreover, it is guaranteed to converge to local minima for a wide range of values of the pair ( α , β ). Our theoretical contribution has been validated by several experiments performed with synthetic and real data and exploring the ( α , β ) plane. The numerical results obtained confirm the quality of the algorithm and its suitability to be used in several practical applications.

Keywords: centroid-based clustering; k-means algorithm; musical genre clustering; unsupervised classification; αβ-divergence.

Figure 1

Analysis of the convergence region of the $\alpha \beta$-k-means algorithm. The region in blue shows the convex cone that guarantee the convergence of the algorithm to a local minimum for any dataset. Blue lines represent the boundaries of the convergence region for some values of the function ${exp}_{1-\alpha }\left(\frac{1}{\beta -1}\right)$.

Figure 2

Generative models for dataset used in experiment 1. Each of the four mixture models have three components of Gaussian, Log-Gaussian, Poisson, and Binomial distribution, respectively.

Figure 3

Average ACC obtained with the right centroid $\alpha \beta$-k-means algorithm for four different datasets.

Figure 4

Average ACC obtained with the left-centroid $\alpha \beta$-k-means algorithm for four different datasets.

Figure 5

Performance of the $\alpha \beta$-k-means algorithm in terms of accuracy for DFT-based descriptors considering $K=3$ classes and $K=5$ classes.

Figure 6

Performance of the $\alpha \beta$-k-means algorithm in terms of accuracy for acoustic descriptors considering K = 3 classes and K = 5 classes.

Figure 7

Performance of the $\alpha \beta$-k-means algorithm in terms of average accuracy over 50 trials for two UCI datasets: Iris and Wine.