Pourquoi k-means ne donne-t-il pas le minimum global?

17

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?

Prateek Kulkarni
la source
4
Lorsqu'une fonction lisse a plusieurs minima locaux, alors chacun d'eux sera nécessairement un point critique (où toutes les dérivées partielles disparaîtront), donc votre algorithme est correct mais généralement inutile: vous pouvez obtenir une équation horriblement compliquée avec un nombre énorme de solutions (même infiniment nombreuses). Mais il y a un autre problème: comment savez-vous que la fonction objective k-means est même différenciable partout?
whuber
1
Je crois que lorsque je différencie partiellement la fonction objective par rapport à un centroïde, les points de l'amas d'un autre centroïde disparaissent dans la dérivée. Ainsi, le centroïde que nous pouvons obtenir ne minimisera que la somme des distances au carré de l'amas particulier.
Prateek Kulkarni
3
C'est en partie ça, mais cela n'explique pas vraiment le comportement. Plus important est le fait que l' attribution de points aux centroïdes est la grande partie de ce que fait k-means. (Une fois l'affectation effectuée, les centroïdes sont facilement calculés et il n'y a plus rien à faire.) Cette affectation est discrète : ce n'est pas quelque chose qui peut être différencié du tout. De plus, c'est combinatoire complexe: il existe façons d'assigner n points à k grappes. En effet, il n'est absolument pas nécessaire d'utiliser la descente de gradient pour trouver les centroïdes. O(nk)nk
whuber
Je suis d'accord, la partie affectation ne peut pas être directement mise sous forme mathématique. Ce n'est que par cette étape isolée que nous pouvons déplacer les centroïdes pour minimiser la fonction. Voici comment je regarde la descente de gradient: si, par une mauvaise initialisation, nous sommes près des minima locaux, la descente de gradient vous entraînera vers les minima locaux. Si vous êtes proche des minima globaux par une bonne initialisation, cela vous fera glisser vers le bas des minima globaux. Mais la façon dont ce mouvement est mis en correspondance avec les affectations de cluster est floue.
Prateek Kulkarni
La non-différentiabilité est surestimée: Leon Bottou a effectué un certain travail sur l'estimation des K-Means avec descente de gradient stochastique sur de très grands ensembles de données avec un certain succès. La non-différentiabilité ne pose pas là un problème aussi important que dans de nombreux problèmes dus aux nombreux points de données. (Par exemple, les réseaux convolutifs ne sont pas non plus différenciables localement mais fonctionnent quand même très bien, tout comme de nombreuses architectures de réseaux neuronaux avec la fonction de transfert linéaire rectifiée). La vraie raison ici est les minima multiples.
bayerj

Réponses:

10

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 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.μii{μi}pμip

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.

Peter
la source
Bien placé! Je vais marquer cela comme la réponse!
Prateek Kulkarni
4

Voici le problème que vous souhaitez résoudre:

minxi=1nj=1kxij||picj||2subject to:j=1kxij=1icj is the centroid of cluster jxij{0,1}i,j

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.xijijpicjijRdd

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 jjxij

cj=ixijpijixij

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:

minxi=1nj=1kxij||piyj||2subject to:j=1kxij=1ixij{0,1}i,jyjRdj

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:

  1. Assign some values to yj variables
  2. Fix the values for yj variables and find the optimal values for xij variables.
  3. Fix the values of xij variables, and find the optimal values for yj variables.

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 know xij (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.

Behrouz Babaki
la source
2

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:

Center1 = 1, Cluster1 = {1}
Center2 = 3, Cluster1 = {2,3,4}

Here the objective is 2. As a matter of fact this is a saddle point (try center1 = 1 + epsilon and center1 = 1 - epsilon)

Setting 1:

Center1 = 1.5, Cluster1 = {1,2}
Center2 = 3.5, Cluster1 = {3,4}

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}, setting cluster1={1,2} and cluster2={3,4,5} would results in the same objective value as cluster1={1,2,3} and cluster2={4,5}

Finally, what would happen if you choose

A = {1,2,3,4,6}
center1={2.5} cluster1={1,2,3,4} and 
center1={6} cluster1={6}

vs

center1={2} cluster1={1,2,3} and 
center1={5} cluster1={4,6}

?

user25611
la source
0

[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:

That's partly it, but does not really explain the behavior. Of more import is the fact that the assignment of points to centroids is the big part of what k-means is doing. (Once the assignment is made, the centroids are easily computed and there's nothing left to do.) That assignment is discrete: it's not something that can be differentiated at all.

It would be awesome if anybody has more to add.

Prateek Kulkarni
la source
0

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.

explorer
la source
Rather than Gaussian, I think you mean “unimodal”
Peter Leopold