Améliorer les variantes de K-Means

L'analyse de clustering est l'un des algorithmes de traitement des données les plus utilisés. Depuis plus d'un demi-siècle, K-means reste l'algorithme de clustering le plus populaire en raison de sa simplicité. Le clustering traditionnel K-means tente d'assigner n objets de données à k clusters en partant de centres initiaux aléatoires. Cependant, la plupart des variantes de K-means ont tendance à calculer la distance de chaque point de données à chaque centroïde de cluster pour chaque itération. Nous proposons une heuristique rapide pour surmonter ce goulot d'étranglement avec seulement une augmentation marginale de l'erreur quadratique moyenne (EQM). Nous observons qu'à travers toutes les itérations de K-means, un point de données ne change son appartenance qu'à un petit sous-ensemble de clusters. Notre heuristique prédit de tels clusters pour chaque point de données en examinant les clusters proches après la première itération de K-means. Nous augmentons les variantes bien connues de k-means comme Enhanced K-means et K-means with Triangle Inequality en utilisant notre heuristique pour démontrer son efficacité. Pour divers ensembles de données, notre heuristique permet d'accélérer jusqu'à 3 fois la vitesse de traitement par rapport aux variantes efficaces de k-means.