Que faire avec centroïdes rassis en K-means

Question

Quand je lance Kmeans sur mon jeu de données, je remarque que certains centroïdes deviennent obsolètes dans la ils ne sont plus le plus proche barycentre à tout moment après une itération. En ce moment je sautais ces centroïdes rassis dans ma prochaine itération parce que je pense que ces centroïdes ne représentent plus un ensemble utile des données, mais je voulais savoir s'il existe d'autres moyens raisonnables pour faire face à ces centres de gravité.

Answer 1

k-means ne trouve que des optima locaux. Ainsi, un mauvais numéro de cluster ou simplement un état d'équilibre aléatoire dans les forces d'attraction pourrait conduire à vider les grappes. Techniquement k-means ne prévoit pas de procédure pour cela, mais vous pouvez enrichir l'algorithme sans problème.

Il existe deux approches que je trouve utiles:

• supprimer le cluster rassis, choisissez une instance aléatoire de votre ensemble de données et de créer un nouveau cluster avec barycentre égal au point aléatoire choisi
• supprimer le cluster rassis, choisissez le point le plus éloigné éloigné de tout autre centroïdes, créez un nouveau cluster avec barycentre en ce point

Les deux procédures peuvent conduire à temps de marche indéfinie, mais si le nombre de ce genre d'ajustements est fini (et le plus souvent il est) qu'elle convergera sans problème. Pour vous protéger du temps de fonctionnement infini vous pouvez définir une limite supérieure pour le nombre de Réglages .

La procédure elle-même est pas pratique si vous avez un énorme ensemble de données d'un grand nombre de grappes. Le temps d'exécution peut est devenu prohibitif.

Une autre procédure pour diminuer les chances pour que cela se produise est d'utiliser une meilleure procédure d'initialisation, comme k-means ++ . En fait, la deuxième suggestion est une idée de k-means ++ . Il n'y a aucune garantie, cependant.

Enfin une note concernant la mise en œuvre. Si vous ne pouvez pas modifier le code de l'algorithme pour apporter ces améliorations à la volée, votre seule option qui me vient à l'esprit est de commencer une nouvelle procédure de regroupement où vous initialisez les positions barycentre pour les clusters non périmés, et suivre les procédures pour grappes obsolètes.