J'ai lu que l'algorithme k-means ne converge que vers un minimum local et non vers un minimum global. Pourquoi est-ce? Je peux logiquement penser à la façon dont l'initialisation pourrait affecter le clustering final et il existe une possibilité de clustering sous-optimal, mais je n'ai rien trouvé qui puisse le prouver mathématiquement.
Aussi, pourquoi k-means est-il un processus itératif? Ne pouvons-nous pas simplement différencier partiellement la fonction objectif par rapport aux centroïdes, l'assimiler à zéro pour trouver les centroïdes qui minimisent cette fonction? Pourquoi devons-nous utiliser la descente en pente pour atteindre le minimum pas à pas?
clustering
k-means
convergence
gradient-descent
minimum
Prateek Kulkarni
la source
la source
Réponses:
Vous pouvez voir k-means comme une version spéciale de l'algorithme EM, ce qui peut aider un peu.
Supposons que vous estimez une distribution normale multivariée pour chaque cluster avec la matrice de covariance fixée à la matrice d'identité pour tous, mais la moyenne variable où i est l'indice du cluster. De toute évidence, si les paramètres { μ i } sont connus, vous pouvez attribuer à chaque point p son cluster de vraisemblance maximale (c'est-à-dire le μ i pour lequel la distance à p est minimale). L'algorithme EM pour ce problème est presque équivalent à k-means.μi i {μi} p μi p
Inversement, si vous savez quels points appartiennent à quel cluster, vous pouvez estimer le optimal . La solution de forme fermée à ce (qui trouve un optimum global) dit essentiellement que pour trouver les modèles de probabilité maximum { μ i } vous intégrez sur toutes les affectations possibles de points à grappes. Étant donné que même avec seulement trente points et deux grappes, il existe environ un milliard de ces affectations possibles, cela est impossible à calculer.μi {μ^i}
Au lieu de cela, nous pouvons deviner les paramètres cachés (ou les paramètres du modèle) et répéter les deux étapes (avec la possibilité de se retrouver dans un maximum local). Si vous autorisez chaque cluster à prendre une responsabilité partielle pour un point, vous vous retrouvez avec EM, si vous attribuez simplement le cluster optimal, vous obtenez k-means.
Donc, résumé: en termes probabilistes, il existe une solution globale, mais elle vous oblige à parcourir tous les clusters possibles. Clairement, si vous avez une fonction objective, il en va de même. Vous pouvez parcourir toutes les solutions et maximiser la fonction objectif, mais le nombre d'itérations est exponentiel dans la taille de vos données.
la source
Voici le problème que vous souhaitez résoudre:
La variable binaire indique si le point i est ou non affecté au cluster j . Les symboles p i et c j désignent respectivement les coordonnées du i ème point et du centroïde du j ème cluster. Ils sont tous deux situés dans R d , où d est la dimensionnalité des points de données.xij i j pi cj i j Rd d
Le premier groupe de contraintes indique que chaque point doit être affecté à exactement un cluster. Le second groupe de contraintes (que nous n'avons pas défini mathématiquement) dit que les coordonnées du centroïde du cluster dépendent en fait des valeurs de x i j variables. On peut par exemple exprimer cette contrainte comme suit: c j = ∑ i x i j p i jj xij
Cependant, au lieu de traiter ces contraintes non linéaires, dans K-Means nous résolvons (approximativement) un problème différent qui a la même solution optimale que notre problème d'origine:
Instead of minimizing the distance to centroids, we minimize the distance to just any set of points that will give a better solution. It turns out that these points are exactly the centroids.
Now to solve this problem, we iterate in steps 2-3 of this algorithm, until convergence:
In each step the objective function improves (or remains the same when the algorithm converges), since the solution found in the previous step is in the search space of current step. However, since we are fixing some of the variables in each step, this is a local search procedure which does not guarantee optimality.
Luckily, the optimization problems in steps 2 and 3 can be solved in closed form. If we knowxij
(i.e. if we know to which cluster each point is assigned), the best values for yj variables are the centroids of clusters. If we know values for yj , obviously best choice for xij variables is to assign each point to the closest yj .
la source
A simple example might help..
Let us define the set of points to be clustered as
A = {1,2,3,4}
.Say you're trying to find 2 appropriate clusters for A (2-means). There are (at least) two different settings which satisfy the stationary condition of k-means.
Setting 1:
Here the objective is 2. As a matter of fact this is a saddle point (try
center1 = 1 + epsilon
andcenter1 = 1 - epsilon
)Setting 1:
here the objective is 1/4.
If k-means would be initialized as the first setting then it would be stuck.. and that's by no means a global minimum.
You can use a variant of previous example to create two different local minima. For
A = {1,2,3,4,5}
, settingcluster1={1,2}
andcluster2={3,4,5}
would results in the same objective value ascluster1={1,2,3}
andcluster2={4,5}
Finally, what would happen if you choose
vs
?
la source
[This was before @Peter answered]
After a small discussion (in the comments section), I feel I have to answer my own question.
I believe that when I partially differentiate the objective function with respect to one centroid, the points in the cluster of another centroid vanish in the derivative. So, the centroid we can get will minimize only the sum of squared distances of only the particular cluster.
@whuber adds:
It would be awesome if anybody has more to add.
la source
Everybody has explained everything, but I would like to add that if a sample data is not distributed as a Gaussian distribution then it can stuck to a local minima. In the K-means algorithm we are actually trying to get that.
la source