Discussion :

[davcha]

Un élément de la matrice distance D corresond à Dij^2 = Gii + Gjj - 2 * Gij

Cette matrice, construite à partir du produit scalaire, peut être remplacée par n'importe qu'elle matrice construite à partir d'une fonction qui à les même propriétés que le produit scalaire (en particulier la matrice résultante doit avoir toute ses valeurs propre positives ou nulles).

Petite précision, quand il parle de la matrice résultante qui doit être positive semi définie, il parle de G, pas de D.

[Alikendarfen]

Merci à tous deux de ces retours.

Je n'ai pas vos bases théoriques sur ces sujets, ce qui fait que j'ai du mal à comprendre les impacts.

Voici de manière plus détaillée comment j'ai procédé :

J'ai un ensemble d'éléments "ei". Il y a N ei.

A chaque ei, j'associe un vecteur V(ei) = [pij] de dimension N où pij = pji correspond à la probabilité de cooccurrence de ei et ej.

Ces éléments sont traduits en neurones d'entrée "ni" d'une carte de Kohonen.

Le vecteur V(ni) associé à ni est V(ei) normalisé V(ni) = V(ei) / sqrt( V(ei).V(ei) ).

La couche de sortie est composée de x neurones "si" (x inférieur à N). Chaque si a une position dans le plan et un vecteur V(si) de dimension N.

Initialement, les valeurs des V(si) sont tirées au hasard autour de la moyenne des V(ei). Puis les V(si) sont normalisés comme les V(ni).

Dans le déroulement de Kohonen, une entrée est associée à la sortie la plus proche en considérant la distance qui les sépare : sqrt( somme sur k des (V(ni)[k] - V(si)[k])² )


Après cela, il faut ajuster l'impact de l'affectation d'une entrée à une sortie, sur cette sortie et les sorties voisines (mais à la limite, c'est un autre aspect).


Donc si je vous comprends bien, cela n'est pas une bonne approche ?

[Alexis.M]

Le problème principal vient de ce que la représentation des données que tu utilises n'est pas compatible avec l'utilisation de la distance Euclidienne telle qu'elle est utilisée dans les cartes de Kohonen standard.

Notamment la distance Dij = sqrt( sum_k (V(ni)[k] - V(si)[k])^2 ), n'as sans doute pas de sens.

Tu as au moins de manière de traiter ton problème:

1) L'approche Noyau:

C'est, je pense, la manière la plus correcte de procéder. Elle consiste à considérer la matrice P des probabilités comme une matrice noyau (en vérifiant qu'elle est bien semi-définie positive) et à appliquer par exemple l'algorithme Kernel K-means pour effectuer la classification. La visualisation en 2D pouvant ensuite s'effectuer en appliquant les cartes de Sammon's par exemple. De cette façon, si tu modifies seulement un peu les valeurs des élements de P, tu dois pouvoir relancer l'algo des Kernel K-means puis celui des cartes de Sammon avec les valeurs précédemment trouvée ce qui devrait permettre de converger rapidement.

2) Ton approche.

Intuitivement je dirais que le principale problème de ton approche, au delà du fait que tu ignores que les V(ei)[j] sont déjà des mesures de similarité entre i et j, est qu'elle oublie que tu travailles au départ avec des probabilités. Une manière très simple de prendre cela en considération est de construire quelque chose qui ressemble à un histogramme un normalisant à 1 les lignes de P.

Pour décrire l'élément i, j'ai donc l'histogramme hi:

hi[j] = pij / ( sum_j pij)

De cette manière hi peut être vue comme une distribution de probabilités.
Le distance de Hellinger entre deux histogrammes est simplement calculée comme:

Dh(hi, hj) = sqrt( sum_k ( sqrt(hi[k]) - sqrt(hj[k]) )^2 )

alors que la distance euclidienne est:

De(hi, hj) = sqrt( sum_k ( hi[k] - hj[k] )^2 )

La différence consiste simplement à utiliser la racine carrée des éléments au lieu des éléments eux même.

En pratique la seule différence pour toi va consister à prendre:

V(ei)[j] = sqrt(pij)

Au lieu de

V(ei)[j] = pij

Mais la métrique de Hellinger utilisée aura au moins un sens pour des mesures de probabilités.

Mais encore une fois, à mon avis, il serait plus correct de considérer la matrice des pij de départ comme une matrice noyau et d'appliquer une méthode conçue pour travailler sur ce type de matrice.

[Alikendarfen]

Encore merci de ces explications et de ta patience Alexis !

Complément à mon post d'avant : je ne l'avais pas précisé mais mes pij = nombre d'occurrences de i avec j divisé par le nombre total de cas.

Mais le fond du truc est que je ne comprends pas le "sens" (la sémantique) de ce que tu expliques, au-delà de constater que je devrais utiliser une formule plutôt qu'une autre..

En quoi une distance est-elle plus légitime qu'une autre ? C'est dans tous les cas une façon "d'aplatir" une comparaison plus précise, n'est-ce pas ? De placer un élément dans le périmètre d'un autre.

D'autant que cette distance n'intervient que pour associer les entrées aux sorties (et non pas directement dans le calcul de l'impact de l'entrée sur la sortie).

Bref, c'est ce genre de choses que je ne comprends pas...


Si je ne me trompe pas, la distance de Hellinger aura tendance à accentuer les différences ou les proximités, par rapport à une distance euclidienne.
En cela, j'arrive à voir que cette distance pourrait être plus efficace... mais pas qu'elle soit plus "légitime" ?


Concernant les k-means, je l'ai essayé également, mais peut être pas avec les bonnes matrices/distances ? En tout cas, j'obtenais des résultats très différents, et notamment, j'avais des groupes d'éléments très inhomogènes (des points isolés pour la moitié des cas et un "amas" pour l'autre moitié).

[Alexis.M]

Kohonen, comme les K-means, comme beaucoup d'autres algorithmes sont basés sur la notion de distance. Pour que le résultat de l'algorithme est un sens il faut que la mesure de distance que tu utilises soit adaptée à tes données et des mesures de distance autres que la distance euclidiennes peuvent être mieux adaptée.

Imagine par exemple qu'il y a des différences d'échelle importantes entre les différentes composantes de tes vecteurs par exemple à cause du système d'unité choisi, tu vas peut être vouloir pondérer les différentes composantes de manière à ce qu'elles aient toutes la même variance par exemple.

Faire cela revient à utiliser une mesure de distance D(xi, xj)^2 = (xi - xj)'S^(-1)(xi - xj)

Où S est la matrice diagonale dont les éléments de la diagonale correspondent aux variances de chaque composante.

De manière équivalente tu peut prendre yi = S^(-1/2) xi, et ensuite simplement utiliser la distance Euclidienne sur yi.

Si les données sont issues d'un comptage provenant d'une loi aléatoire, on sait par avance par exemple que les valeurs les plus probables sont aussi celles pour lesquelles la variance attendue va être la plus importante, de l'ordre de ni si on a compté ni occurrences d'une valeur.

Pour mesurer la distance entre deux histogrammes, on utilise typiquement la distance du chi^2 D(hi,hj) = \sum_k (hi[k] - hj[k])^2 / (hi[k] + hj[k])
qui ressemble à la distance euclidienne mais où on divise chaque composante par l'estimation de la variance sur la variable (hi[k] - hj[k]).

Le problème de la distance du chi^2 c'est qu'elle est compliquée à utilisée car, par exemple, il n'existe pas de formule simple pour trouver le centroïde d'un nuage de point au sens de la distance du chi^2.

D'autres mesures de distance entre histogrammes sont possibles, notamment la distance de Hellinger qui a tendance à réduire les écarts entre les composantes les plus probables et les moins probables de l'histogramme et donc à diminuer les problèmes de variance. Cette distance à l'avantage de se confondre avec la distance Euclidienne si on prends la racine carrée des éléments de l'histogramme, ce qui est une propriété bien commode pour ensuite appliquer des méthodes basée sur cette distance.

La distance de Hellinger est plus légitime parce qu'elle est définie pour les histogrammes.