Pourquoi k-means n'est-il pas optimisé en utilisant la descente de gradient?

14

Je sais que k-means est généralement optimisé à l'aide de la maximisation des attentes . Cependant, nous pourrions optimiser sa fonction de perte de la même manière que nous optimisons les autres!

J'ai trouvé des articles qui utilisent réellement la descente de gradient stochastique pour les moyennes k à grande échelle, mais je n'ai pas pu obtenir de réponse à ma question.

Alors, quelqu'un sait pourquoi? Est-ce parce que la maximisation des attentes converge plus rapidement ? A-t-il une garantie particulière? Ou est-ce une raison historique ?

elsonidoq
la source
L'étape de maximisation grimpe déjà le gradient de vraisemblance (conditionnel aux valeurs choisies par l'étape d'attente), n'est-ce pas?
David J. Harris
@ DavidJ.Harris Je ne pense pas que l'OP conteste que l'EM se comporte comme il le fait, mais en demandant pourquoi une méthode semble être largement utilisée et une autre méthode moins utilisée. Votre commentaire ne semble pas expliquer directement pourquoi EM pourrait être préféré.
Glen_b -Reinstate Monica
1
Salut @ DavidJ.Harris, c'est comme Glen_b, je comprends que les deux algorithmes optimisent soit la vraisemblance (EM) soit la vraisemblance logarithmique (descente de gradient). Après avoir creusé dans google et amis, je suis arrivé à ce lien papier pour savoir si cette question est abordée. Si je n'ai pas manqué de comprendre, l'EM arrive à une meilleure solution que la descente en pente.
elsonidoq
Quelle est la fonction objective pour k-means à optimiser? Est-il différentiable?
Vladislavs Dovgalecs
3
Il est facilement différenciable dans les paramètres (moyennes de cluster) mais sûrement pas dans les affectations de cluster (qui sont des variables indicatrices multinomiales)?
Ruben van Bergen

Réponses:

7

Comme l'OP le mentionne, il est possible de résoudre les k-moyennes en utilisant la descente de gradient, ce qui peut être utile dans le cas de problèmes à grande échelle.

Il existe certainement des raisons historiques pour la prévalence des algorithmes de style EM pour résoudre les k-moyennes (c'est-à-dire l'algorithme de Lloyd). L'algorithme de Lloyd est si populaire que les gens l'appellent parfois «l'algorithme k-means», et peuvent même ignorer qu'il existe d'autres approches. Mais cette popularité n'est pas imméritée.

Bottou et Bengio (1995) ont montré que l'algorithme de Lloyd équivaut à optimiser la fonction de coût k-moyennes en utilisant la méthode de Newton. Dans les problèmes d'optimisation généraux, les méthodes de second ordre comme la méthode de Newton peuvent converger plus rapidement que les méthodes de premier ordre comme la descente de gradient car elles exploitent les informations sur la courbure de la fonction objectif (et pas les méthodes de premier ordre). Dans une expérience sur le célèbre ensemble de données Iris, ils ont montré que l'algorithme de Lloyd convergeait en effet plus rapidement que la descente de gradient. Il serait intéressant de voir cette comparaison sur une plus grande variété d'ensembles de données.

Les références:

Bottou et Bengio (1995) . Propriétés de convergence des algorithmes k-means.

user20160
la source
2

Le clustering K-means n'est pas supervisé, et la technique non supervisée la plus proche qui utilise EM est le clustering basé sur un modèle (modèles de mélange gaussiens, GMM). Un problème gênant avec le clustering basé sur un modèle GMM se produit lorsque de nombreuses fonctionnalités sont corrélées, ce qui provoque une quasi-singularité dans la matrice de covariance (corrélation) basée sur les fonctionnalités. Dans cette situation, la fonction de vraisemblance devient instable, les indices de condition atteignant l'infini, entraînant la rupture complète de GMM.

Ainsi, abandonnez l'idée de EM et kNN - car elle est basée sur des matrices de covariance (corrélation) pour une analyse non supervisée. Votre demande d'optimisation ressemble étroitement à la cartographie de Sammon et à l'échelle multidimensionnelle métrique et non métrique (MDS) classique. La cartographie des saumons est basée sur des dérivatifs-itératifs, tandis que diverses formes de MDS sont généralement des compositions d'itérations ou des étapes uniques, qui peuvent néanmoins être optimisées lors d'une opération matricielle en une étape.

En repensant à votre demande: la réponse est: cela a déjà été fait dans la cartographie Sammon.

JoleT
la source