Discussion :

[davcha]

Hello,

J'ai implémenté une une version améliorée de l'algorithme de Lloyd, il s'agit de k-means++.

J'ai bien pris soin de choisir des centroides initiaux différents les uns des autres (ça se fait automatiquement avec kmeans++).

Ce que je ne m'explique pas est que je perds des centroides au cours de l'exécution.
En fait, quand j'assigne les points aux centroides les plus proches, un des centroides peut, parfois, se retrouver sans aucun point attaché à lui. Ce qui est logiquement impossible, sauf si quelque chose m'échappe.

Quelqu'un a une explication ?

Code octave :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
% x: data points
% u: centroids
J = 0;
t = 0;
do{
	oJ = J;
	D = repmat(diag(x*x'), 1, size(u,1))
		+ repmat(diag(u*u')', size(x,1), 1)
		- 2*x*u';
	p = cvtcm(argmin(D));
	u = (p'*p)^-1*p*x;
	J = trace(p'*D);
}while(abs(oJ - J) > 1e-10 && (t++ < 100));

cvtcm est une fonction qui convertit un vecteur indicateur en matrice indicatrice.
voilà un exemple :
cvtcm([0,1,1,2,1,5]) =>
1 0 0 0
0 1 0 0
0 1 0 0
0 0 1 0
0 1 0 0
0 0 0 1

David

[Matthieu Brucher]

Ca ne me paraît pas impossible, c'est un des problèmes des kmeans !

[davcha]

Oui... J'aurais bien aimé au moins un exemple, parce que ça me parait vraiment étrange.

Mais bon, problème résolu, en tout cas, j'ai trafiqué l'algo pour que ça n'arrive plus.

[Aleph69]

Bonjour,

J'ai bien pris soin de choisir des centroides initiaux différents les uns des autres (ça se fait automatiquement avec kmeans++).

Ce que je ne m'explique pas est que je perds des centroides au cours de l'exécution.
En fait, quand j'assigne les points aux centroides les plus proches, un des centroides peut, parfois, se retrouver sans aucun point attaché à lui. Ce qui est logiquement impossible, sauf si quelque chose m'échappe.

Quelqu'un a une explication ?

Je vois deux causes possibles :
1. à l'initialisation aléatoire des centroïdes, un centroïde est vide dès la première phase d'affectation et le reste pendant tout le processus;
2. l'un des centroïdes n'est pas vide mais est relativement éloigné de ses individus tandis que les centroïdes voisins se rapprochent petit à petit de ses individus.

Pour le 2., je ne suis pas sûr que cela soit possible en 1d. En 2d, imagine le centroïde c d'un ensemble d'individus répartis sur un cercle. En d'autres termes, le centroïde est le centre du cercle. Soit r le rayon de ce cercle. Trace le cercle de centre c et de rayon 2*r. Maintenant, suppose qu'un individu x se trouve dans le disque de rayon 2*r mais sans être dans le disque de rayon r. La distance entre c et x est donc strictement supérieure à r. Maintenant trace la droite passant par c et x. Supposons qu'un centroïde c' se trouve au point d'intersection le plus proche de x entre la droite et le cercle de rayon 2*r. Alors la distance entre x et c' est inférieure à r. A la phase d'affectation :
1. tous les points du cercle de rayon r sont affectés à c;
2. x est affecté à c'.
A la mise à jour des centres :
1. c reste inchangé;
2. c' devient x;
Il te suffit ensuite de remarquer qu'il existe des points sur le cercle de rayon r qui sont plus proches de x que de c pour comprendre qu'un centroïde voisin (en l'occurrence c') peut venir voler des points à un autre centroïde. En particulier, si tous les individus affectés à c sont sur la partie du cercle plus proche de x que de c, alors le centroïde sera vide à la phase d'affectation suivante et c' contiendra tous les individus du problème. Ce n'est pas possible pour un seul couple (x,c') mais cela le devient à partir de 2 couples en les plaçant judicieusement.

[davcha]

Plus d'infos ici : A Modified k-means Algorithm to Avoid Empty Clusters.

Cela arrive même que on initialise les centroides "intelligemment", kmeans++, par exemple.
Je trouve ça toujours assez contre intuitif du coup.

[Alexis.M]

Le problème des "unités mortes" dans ce type d'algo est un problème courant, d'autant plus fréquent que les données sont très structurées (variété de faible
dimension) surtout avec une méthode en ligne telle que l'agorithme de LLoyd, il se peut en effet qu'une unité se retrouve à un moment donné en dehors du nuage de point. Au delà d'une initialisation "intelligente", certaines implémentations traîtent explicitement le problème en réinserrant les unités mortes aléatoirement dans le nuage de points (en réinitialisant aléatoirement sur un point de données).

Une autre approche inspirées des système biologiques consiste à inclure un critère de fatigue sur les unités/centroïdes de sorte que les unités souvent sollicités soit pénalisées.

Par ailleurs, d'autres algorithmes que K-means existent pour la quantification vectorielles. L'algorithme de Lloyd est une approche en ligne de l'agorithmes des k-means et peut etre vue comme un algorithme d'apprentissage compétitif de type "winner take all" (seule l'unité "gagnante" est adaptée), des algorithmes comme "neural gas" sont des algorithmes de type "winner take most" où plus d'une unité sont adaptées
à chaque itération.

A noter que les cartes de Kohonen, souvent utilisées pour faire de la quantification vectorielles ne devraient pas être utilisées si le but ultime n'est pas la visualisation.

[Matthieu Brucher]

Les cartes de Kohonen sont tout de même largement moins efficaces que des algorithmes tels que les k-means (les premiers retournent une ligne 1D, les seconds retournent un résultat nD). De manière générale, les algos à base de réseaux de neurones dans l'apprentissage de variétés sont à mon sens bien moins efficaces que le reste, même si la littérature associée pullule de ces algorithmes.

[Aleph69]

Bonjour,

Les cartes de Kohonen sont tout de même largement moins efficaces que des algorithmes tels que les k-means (les premiers retournent une ligne 1D, les seconds retournent un résultat nD).

Je ne comprends pas ce que tu veux dire. Les méthodes des centres mobiles et des k-moyennes sont en fait des cartes de Kohonen avec des fonctions de voisinage particulières.

[Alexis.M]

Après j'imagine que cela dépend de ce que l'on met sous l'appélation de cartes
de Kohonen.

Pour moi il s'agit, d'une méthode compétitive de quantification vectorielle en ligne de type "winner take most" où plus d'une unité (=neurone/centroid/vecteur code) est adaptée à chaque itération.

A chaque itération on présente un point de donnée et l'unité la plus proche est désignée comme gagnante. Celle si est donc déplacée de la même façon que dans l'algorithme de LLoyd généralisé.

Les autre unités sont adaptées également mais la longueur du pas d'adaptation dépend de la distance de l'unité considérée à l'unité gagnante selon une structure fixée a priori est indépendante de l'espace des données.
S'il s'agit souvent d'une grille, son nombre de dimension n'est pas forcément 1, elle est même souvent 2, pour permettre une visualisation des données.

Neural gas peut être vu comme une carte de Kohonen à 1 dimension mais où la grille est reconstruite à chaque itération (en triant les unités en fonction de leur distance à l'échantillon).

La raison d'être de ces structures de voisinage est de découpler le pas d'adaptation de la distance à l'échantillon afin d'éviter que toutes les unités ne convergent vers le barycentre du nuage de point.

Il n'est pas rare de trouver dans la littérature des utilisations des cartes de Kohonen pour faire de la quantification vectorielle (d'où ma remarque), mais, si la structure de grille n'est pas adatpée, la qualité de la quantification peut en être fortement dégradée.

En ce qui concerne Neural Gas, typiquement en phase finale de l'apprentissage le voisinage utilisé est tellement faible que seule le gagnant euclidien est adaptée et on tend donc vers le même comportement que l'algorithmes de LLoyd. Cet algorithme est réputé pour convergé plus vite
que l'agorithme de LLoyd est avec une erreur de reconstruction plus faible.

[Aleph69]

Salut Alexis,

Après j'imagine que cela dépend de ce que l'on met sous l'appélation de cartes
de Kohonen.

Pour moi il s'agit, d'une méthode compétitive de quantification vectorielle en ligne de type "winner take most" où plus d'une unité (=neurone/centroid/vecteur code) est adaptée à chaque itération.

En fait, seuls sont adaptés les vecteurs voisins du vecteur gagnant. Par conséquent, en prenant le rayon de voisinage suffisamment petit, typiquement égal à zéro, seul le vecteur gagnant est mis à jour. Mais bien sûr, il s'agit d'un cas très particulier.

[Matthieu Brucher]

Non, ça n'a strictement rien à voir. Les cartes de Kohonen sont des réseaux de neurones, pas les k-means (ça a fait partie de ma thèse, donc tu peux me faire confiance).

[Aleph69]

Bonjour Matthieu,

Non, ça n'a strictement rien à voir. Les cartes de Kohonen sont des réseaux de neurones, pas les k-means (ça a fait partie de ma thèse, donc tu peux me faire confiance).

Si tu as fait une thèse sur les réseaux de Kohonen, cela va être encore plus simple de te convaincre. Les formules de mise à jour de la version batch de l'algorithme de Kohonen s'obtiennent exactement de la même manière que celles de la méthode des centres mobiles/k-moyennes. La seule différence est que la fonction à minimiser est une erreur de quantification pondérée à l'aide de la fonction de voisinage. Ainsi, dans le cas particulier où ces poids valent tous un (rayon de convergence nul pour la fonction de voisinage en bulle), tu cherches à minimiser l'erreur de quantification standard des centres mobiles/k-moyennes. J'espère que ces quelques lignes te convaincront. Dans le cas contraire, je peux t'écrire la démonstration mathématique étape par étape avant que tu ne soutiennes, si ce n'est pas déjà fait bien sûr!

[Alexis.M]

Je tiens d'abord à préciser que j'avais confondu l'algorithme de Lloyd généralisé et sa version en ligne aussi connue sous le non d'apprentissage compétitif.

La version en ligne correspond simplement à l'optimisation de la fonction de
coup des k-means par une méthode de gradient stochastique.

Un seule point de donnée x est utilisé à chaque itération, et la valeur du gradient est approximée à partir du points courant seulement. Les coordonnées de l'unité la plus proche w* sont donc adaptées par

w* <- w* + alpha * (x - w*)

Ce qui correspond bien à la descente de gradient pour le point courant.

dans les cartes de Kohonen, chaque unité possède deux jeux de poids w et u. Les premiers (w) correspondent à l'espace des données et les deuxièmes (u) sont fixés à l'avance et correspondent souvent à une structure de grille dans ce que j'appelerai l'espace des unités.

La règle d'adaptation des coordonnées de chaque unité est:

w <- w + alpha * G(dist(u*, u)) * (x-w)

où G est une fonction décroissante de la distance entre l'unité courante
et l'unité gagnante (la plus proche de x) dans l'espace des unités (et pas dans l'espace des données).

Dans le cas où G est une dirac la règle d'adaptation est donc la même que dans la version en ligne de l'algorithme de LLoyd.

[Aleph69]

Salut Alexis,

Dans le cas où G est une dirac la règle d'adaptation est donc la même que dans la version en ligne de l'algorithme de LLoyd.

Super, on trouve la même chose!

[Matthieu Brucher]

Bonjour Matthieu,



Si tu as fait une thèse sur les réseaux de Kohonen, cela va être encore plus simple de te convaincre. Les formules de mise à jour de la version batch de l'algorithme de Kohonen s'obtiennent exactement de la même manière que celles de la méthode des centres mobiles/k-moyennes. La seule différence est que la fonction à minimiser est une erreur de quantification pondérée à l'aide de la fonction de voisinage. Ainsi, dans le cas particulier où ces poids valent tous un (rayon de convergence nul pour la fonction de voisinage en bulle), tu cherches à minimiser l'erreur de quantification standard des centres mobiles/k-moyennes. J'espère que ces quelques lignes te convaincront. Dans le cas contraire, je peux t'écrire la démonstration mathématique étape par étape avant que tu ne soutiennes, si ce n'est pas déjà fait bien sûr!

Le nombre d'algos où les équations sont les mêmes... Surtout quand il s'agit d'optimisation... (et en général, il y a souvent plusieurs manières d'arriver au même résultat)
Les cartes de Kohonen sont des réseaux de neurones, pas les k-means. Effectivement, je viens de voir qu'on peut en avoir des 2D ou 3d, mais ça reste des cartes discrètes où on place des éléments. Les k-means n'ont pas de centroïdes fixes les uns par rapport aux autres.
Les cartes de Kohonen sont utilisées pour de la réduction de dimension, c'est impossible à faire pour des k-means. C'est pas pour rien qu'on les enchaîne (quand on ne sait pas qu'on peut faire largement meilleur que les SOM).

En relisant vos messages, je crois que vous confondez l'algorithme des cartes auto-organisatrices telles que l'a décrit Kohonen, basé sur des réseaux de neurones, donnant dans un espace discret, avec les outils de réduction de dimension, dont les cartes font partie, mais qui permettent dans le cas général d'aller dans des espaces non quantisé. Parce que l'optimisation de tous ces outils est souvent réalisé de la même manière, seule la fonction de voisinage et de coût change, donc tout ce que vous dîtes est vrai dans ce cas général. Vous êtes sûr de votre définition des termes ?

[Aleph69]

Salut Matthieu,

Les k-means n'ont pas de centroïdes fixes les uns par rapport aux autres.

Sans remettre en cause ce que tu écris, je ne vois pas trop ce que tu entends par là. Si tu soulignes le fait que les centroïdes varient à chaque itération de la phase d'apprentissage, alors c'est exactement la même chose pour l'algorithme de Kohonen. Dans ce cas, je pense que tu confonds les unités de la carte, qui elles sont effectivement fixées sur une grille 1D/2D/3D, avec les prototypes qui eux jouent un rôle similaire aux centroïdes des k-means et varient dans un espace à p dimensions si p désigne le nombre de variables explicatives.

Vous êtes sûr de votre définition des termes ?

Oui, tu peux prendre pour référence le livre Self-Organizing Maps de Kohonen. Y sont présentés la version batch dont je t'ai parlé auparavant et la version stochastique dont Alexis a parlé. Si tu veux les numéros de chapitre/section/page, aucun souci.

[davcha]

En fait, les deux algorithmes sont des cas particuliers d'EM, non ?...

[Matthieu Brucher]

Sans remettre en cause ce que tu écris, je ne vois pas trop ce que tu entends par là. Si tu soulignes le fait que les centroïdes varient à chaque itération de la phase d'apprentissage, alors c'est exactement la même chose pour l'algorithme de Kohonen. Dans ce cas, je pense que tu confonds les unités de la carte, qui elles sont effectivement fixées sur une grille 1D/2D/3D, avec les prototypes qui eux jouent un rôle similaire aux centroïdes des k-means et varient dans un espace à p dimensions si p désigne le nombre de variables explicatives.

Ce que je veux dire, c'est que normalement, dans les SOM, la structure 1D/2D/3D/nD est conservée dans la carte de sortie. Ce n'est pas le cas des k-means. Les SOM font de la réduction de dimensionalité discrète, sans cette conservation de topologie, ils n'ont aucun intérêt (ou je confonds peut-être avec une autre version des SOM ? mais pourquoi parler de carte dans ce cas ?)

[Aleph69]

Oui, je suis d'accord avec toi : l'intérêt des cartes pour la visualisation est totalement perdu si on dégénère la fonction de voisinage en bulle en choisissant un rayon de voisinage nul (la fonction de Dirac dont parle Alexis). Je remarquais simplement que, dans ce cas dégénéré, on retrouve l'algorithme des k-moyennes. Il n'y a donc d'intérêt pratique que dans le cadre de la classification et/ou de la quantification vectorielle. Mais l'intérêt d'établir un lien entre l'algorithme de Kohonen et l'algorithme des k-moyennes est surtout théorique parce qu'on connaît beaucoup de propriétés de ce dernier. D'ailleurs, comme l'a remarqué davcha, les k-moyennes sont aussi un cas particulier de l'algorithme EM (@davcha : pour les réseaux de Kohonen, je ne sais pas si un tel lien existe mais c'est fort possible).

mais pourquoi parler de carte dans ce cas ?

Dans le cas dégénéré décrit plus haut, c'est effectivement un abus de langage car il n'y a pas de carte/grille : le rayon de voisinage étant choisi nul, il n'existe aucun lien de proximité entre les unités. On est dans le cadre d'une stratégie winner takes all.

[davcha]

Une recherche rapide sur google répond à la question concernant som/em.

C'est pas trop étonnant, vu la tête de l'algo em, d'ailleurs.

Après, il faut se méfier de ces "équivalences" théoriques de fonctions objectif ou autre...