K*-means est un nouvel algorithme de clustering qui détermine automatiquement le nombre optimal de clusters sans avoir à spécifier le nombre k à l'avance ni à se fier à un seuil. Il trouve le nombre optimal de clusters k en les divisant et en les fusionnant selon le principe de longueur de description minimale, tout en optimisant la fonction objective k-means standard. Il démontre expérimentalement qu'il estime avec précision la valeur de k, qu'il surpasse les méthodes existantes et qu'il présente une excellente évolutivité. La convergence de l'algorithme est garantie et son temps d'exécution est similaire, voire plus rapide, à celui des méthodes existantes.
