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.
Réponses:
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 .
la source
K-means is not based on Euclidean distance
n'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.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).
la source