On Hölder fields clustering

Benoît Cadre (1) , Quentin Paris (1)

1 IRMAR - Institut de Recherche Mathématique de Rennes

In this paper, we study the $k$-means clustering scheme based on the observations of a phenomenon modelled by a sequence of random fields $X_1,\cdots,X_n$ taking values in a Hilbert space. In the $k$-means algorithm, clustering is performed by computing a Voronoi partition associated with centers that minimize an empirical criterion, called distorsion. The performance of the method is evaluated by comparing a theoretical distorsion of empirically optimal centers to the theoretical optimal distorsion. Our first result states that, provided the underlying distribution satisfies an exponential moment condition, an upper bound for the above performance criterion is $O(1/\sqrt n)$. Then, motivated by a broad range of applications and computational matters, we use a H\"{o}lder property shared by classical random fields in stochastic modelling to construct a numerically simple algorithm that computes empirical centers based on a discretized version of the data. With a judicious choice of the discretization, we are abble to recover the same performance than in the non-discretized case.

Mots clés: Clustering; k-means; Unsupervised learning; Random fields; Hilbert space; Empirical risk minimization

Domaines: Statistiques [math.ST]; Théorie [stat.TH]

Benoît Cadre, Quentin Paris. On Hölder fields clustering. Test, 2012, 21 (2), pp.301-316. ⟨10.1007/s11749-011-0244-4⟩. ⟨hal-00502677⟩