Un problème fondamental en analyse de données est de partitionner, en aveugle, des données en K groupes distincts. Ce partitionnement peut être l'objectif final (découverte de "communautés" dans les données) ou une étape intermédiaire permettant de réduire la dimension et/ou la complexité algorithmique lors de l'apprentissage.
Nous illustrerons à travers divers modèles probabilistes simples, comment ce partitionnement peut être réalisé à l'aide d'un algorithme de minimisation convexe, pour des vitesses de séparation optimales. Nous expliquerons aussi comment cet algorithme est relié à deux algorithmes standards pour le partitionnement: Kmeans et le spectral clustering.