Pourquoi seule la valeur moyenne est utilisée dans la méthode de regroupement (K-means)?

8

Dans les méthodes de clustering telles que K-means , la distance euclidienne est la métrique à utiliser. Par conséquent, nous calculons uniquement les valeurs moyennes au sein de chaque cluster. Et puis des ajustements sont effectués sur les éléments en fonction de leur distance à chaque valeur moyenne.

Je me demandais pourquoi la fonction gaussienne n'est pas utilisée comme métrique? Au lieu d'utiliser xi -mean(X), nous pouvons utiliser exp(- (xi - mean(X)).^2/std(X).^2). Ainsi, non seulement la similitude entre les grappes est mesurée (moyenne), mais la similitude au sein de la grappe est également prise en compte (std). Est-ce également équivalent au modèle de mélange gaussien ?

C'est au-delà de ma question ici, mais je pense que le décalage moyen peut se poser la même question ci-dessus.

lennon310
la source
1
Ce fil peut être utile. stats.stackexchange.com/questions/76866/… Recherchez dans vos balises d'autres questions pertinentes.
DL Dahly du
@DLDahly Merci Dahly. Pouvons-nous considérer le GMM basé sur EM comme un moyen k pondéré (avec différents poids sur les variances)?
lennon310
Ce n'est pas comme ça que j'en penserais; je vois plutôt k-means comme un GMM où les variances sont contraintes d'être nulles.
DL Dahly

Réponses:

5

Il y a littéralement des milliers de variations de k-moyennes . Y compris l'affectation douce, la variance et la covariance (généralement appelées modélisation gaussienne des mélanges ou algorithme EM).

Cependant, je voudrais souligner quelques points:

  • K-means n'est pas basé sur la distance euclidienne. Il est basé sur la minimisation de la variance . Puisque la variance est la somme des distances euclidiennes au carré, l'affectation de variance minimale est celle qui a la plus petite euclidienne au carré, et la fonction de racine carrée est monotone. Pour des raisons d'efficacité, il est en fait plus intelligent de ne pas calculer la distance euclidienne (mais d'utiliser les carrés)

  • Si vous branchez une fonction de distance différente dans k-signifie, elle peut cesser de converger. Vous devez minimiser le même critère dans les deux étapes ; la deuxième étape consiste à recalculer les moyens. L'estimation du centre à l'aide de la moyenne arithmétique est un estimateur des moindres carrés et minimisera la variance. Puisque les deux fonctions minimisent la variance, les k-moyennes doivent converger. Si vous souhaitez assurer la convergence avec d'autres distances, utilisez PAM (partitionnement autour des médoïdes. Le médoïde minimise les distances intra-cluster pour les fonctions de distance arbitraires.)

Mais au final, k-means et toutes ses variations sont à mon humble avis plus une optimisation (ou plus précisément, un algorithme de quantification vectorielle ) qu'en réalité un algorithme d'analyse de grappe. Ils ne "découvriront" pas réellement la structure. Ils masseront vos données en k partitions. Si vous leur donnez des données uniformes, sans aucune structure au-delà du hasard, k-means trouvera toujours autant de "clusters" que vous voulez qu'il trouve. k-means est satisfait de renvoyer des résultats qui sont essentiellement aléatoires .

A QUIT - Anony-Mousse
la source
1
+1. Cependant, affirmer que K-means n'est pas un clustering semble être un point de vue trop radical, trop "d'exploration de données". Historiquement, K-means est une analyse de cluster de partitionnement classique. Le fait qu'il partitionne avec bonheur des données «non structurées» ne l'exclut pas du domaine du clustering: de nombreux types d'analyses peuvent être pour ainsi dire mal utilisés et donner des résultats stupides.
ttnphns
Encore un point: la place K-means is not based on Euclidean distancen'est pas assez claire dans votre réponse. Vous et moi avons eu des discussions à ce sujet dans le passé et j'ai montré que la minimisation de la variance est liée à la somme de l'euclidienne par paire intra-cluster d ^ 2.
ttnphns
J'énonce clairement la relation à la distance euclidienne via la variance. Le fait est que vous devez remplacer la variance par une mesure différente (puis choisir l'affectation et la mettre à jour en conséquence), ne pas échanger euclidienne et espérer que la moyenne reste toujours significative.
A QUIT - Anony-Mousse
Historiquement, k-means a été publié par Lloyd comme « moindres carrés quantification en PCM ». De même, Steinhaus avait le désir d'effectuer une quantification. Ce qui explique bien pourquoi SSQ est utilisé, car SSQ est l'erreur quadratique de la discrétisation. MacQueen mentionne l'analyse des clusters comme une application de l'algorithme, mais suggère d'utiliser une version modifiée de l'algorithme qui peut ajouter ou supprimer des clusters comme vous le souhaitez (à quel point cela commence réellement à être plus qu'une quantification).
A QUIT - Anony-Mousse
Le point que j'essaie de faire à la fin est de regarder la quantification vectorielle , pas seulement le "clustering", car récemment la recherche sur le clustering est dominée par le point de vue de l'exploration de données (et la plupart du temps non plus basé sur k-means ) . La quantification vectorielle peut être le terme de recherche bien meilleur (car beaucoup plus précis) .
A QUIT - Anony-Mousse
3

Il existe de nombreuses techniques de clustering différentes, et K-means n'est qu'une approche. Comme l'a commenté DL Dahly, les algorithmes EM peuvent être utilisés pour le clustering de la manière que vous avez décrite. Il convient de noter que la principale différence entre K-means et l'utilisation de EM avec un modèle de mélange guassien pour le clustering est la forme des clusters: le centroïde se rapprochera toujours de la moyenne des points du groupe, mais K-means donnera un amas sphérique alors qu'un noyau gaussien donnera un ellipsoïde.

Le clustering hiérarchique utilise une approche complètement différente. Le regroupement basé sur la densité est motivé par une heuristique similaire au regroupement basé sur la moyenne, mais donne évidemment des résultats différents. Il existe de nombreuses techniques de clustering qui ne considèrent aucune sorte de moyenne.

En réalité, le choix de l'algorithme est fonction du domaine du problème et de l'expérimentation (c'est-à-dire voir ce qui fonctionne).

David Marx
la source
Merci David. Je suppose que Hiérarchique donne des résultats différents de kmeans car les définitions de la distance entre deux grappes ne sont pas les mêmes. Il peut ne pas être facile de déterminer quelle métrique utiliser et si la variance doit être incluse. Il semble que différents groupes de personnes aient développé leurs propres paramètres sur leur propre problème. La méthode vient de donner un tel problème un bon résultat, mais il manquait de soutien théorique sur l'option des méthodes de clustering.
lennon310