Discussion :

[Alikendarfen]

Bonjour,

Soit un ensemble de n éléments (n de l'ordre de quelques milliers).

Une distance est attribuée à chaque paire d'éléments (cela selon un calcul préalable lié à une notion de co occurrence de ces éléments).

Comment attribuer une position (x,y) dans le plan à ces éléments en respectant les contraintes de distances déjà définies (en faisant en sorte que les distances dans le plan correspondent aux distances précédemment définies) ?

Je ne sais pas si c'est possible de façon "exacte"... si ça n'est pas le cas, comment trouver la meilleure approximation (distances plus ou moins bien respectées) ?


Merci de votre concours !

[Alikendarfen]

ah... un ami a trouvé quelquechose : les réseaux (ou cartes) de Kohonen..

Je vérifie que ça colle avant de marquer "résolu".

[Alikendarfen]

Pas sur que Kohonen fonctionne...

J'ai besoin d'une bijection entre les entrées et les sorties... et je n'ai pas compris que Kohonen fonctionne en ce sens.

Les conseils d'un spécialiste seraient les bienvenus !!

[pseudocode]

Personnellement je regarderais du coté des techniques de "graph layout", en particulier les algos dynamiques du genre "force directed".

[Alikendarfen]

je suis en n3 sur ce type d'approche.

Pourtant ça fonctionne (testé) effectivement sur de petits nombres.

Mais mon objectif est de l'ordre de 20 000 objets...

Je me tape la tête contre les murs ?

[prgasp77]

Tu peux peut-être jeter un œil sur graphviz : un ensemble d'outils très sympathiques réalisant ce que tu cherches à faire ; il existe des biblios et des programmes tout-fait.

Bon courage.

[pseudocode]

Mais mon objectif est de l'ordre de 20 000 objets...

20 000 objets avec une contrainte de distance entre chaque pair d'objet, le tout en dimension 2... Sauf cas très particulier, il n'y aura aucune représentation exacte.

Et même en relâchant la contrainte d'exactitude, ca risque d'être sacrément illisible. Je pense qu'il faut revoir le besoin ou la finalité d'une telle représentation.

[Alikendarfen]

20 000 objets avec une contrainte de distance entre chaque pair d'objet, le tout en dimension 2... Sauf cas très particulier, il n'y aura aucune représentation exacte.

Et même en relâchant la contrainte d'exactitude, ca risque d'être sacrément illisible. Je pense qu'il faut revoir le besoin ou la finalité d'une telle représentation.

Je suis d'accord... mais le but n'est pas de faire un graphique lisible mais bien d'attribuer une position 2D.

Et oui, il y a des contraintes à relâcher nécessairement pour aboutir à quelque chose qui soit optimal dans l'ensemble...

Toujours pas trouvé de piste viable pour le moment (j'ai regardé l'outil indiqué par prgasp77 mais ils semblent indiquer une limite à 100 objets pour ce type de représentation).


Peut être une combinaison kmeans + force directed ?

[pseudocode]

Toujours pas trouvé de piste viable pour le moment (j'ai regardé l'outil indiqué par prgasp77 mais ils semblent indiquer une limite à 100 objets pour ce type de représentation).

Il y a des librairies comme OGDF qui savent gérer des gros volumes de données.

[Alikendarfen]

Bonsoir,

Je regarde vos dernières propositions. Merci de ces retours.

Pour info, sinon, j'ai écarté un peu trop vite Kohonen... j'avais mal compris le potentiel de l'approche...

J'ai fait seulement quelques tests (non complets) sur Kohonen. Mais pour information la convergence est plutôt très rapide (itérations couteuses, mais très peu d'itérations).

Et la répartition obtenue est très équilibrée (sorties homogènes en nombre d'entrées correspondantes). Ce qui n'est pas le cas (sur mes données) avec les k-means.

A suivre

[Alikendarfen]

j'oubliais... j'ai une question complémentaire

Toujours dans ce même contexte.

J'étudie la corrélation de données d'entrée D, D de dimension n.

Pour tout di, j'établis une probabilité de co occurrence pij avec tout autre dj.

J'ai donc un vecteur de probabilités associé à tout élément de D.

On peut également créer un "vecteur de distances" qui est la racine carrée de la somme des carrés des différences pi - pj (distance euclidienne en dimension n).

Pour tout élément, j'ai donc un vecteur de probabilités et un vecteur de distances.

Mais, là où je décroche c'est dans l'interprétation de ces vecteurs (vecteurs qui pourraient être utilisés dans les algos cités précédemment)...

A quoi correspondent-ils ?

Lequel apporte la meilleure "sémantique" pour comparer les proximités entre mes données ?

Ou bien sont-ils équivalents ?

[Alikendarfen]

Bonjour,


Pour info, Kohonen + Force directed (via un des outils cité) va probablement convenir après quelques tests.

Kohonen se révèle beaucoup plus efficace que k-means dans ma situation (meilleure convergence, meilleur équilibre des groupes créés).


Donc je marque "résolu".

Merci pour vos conseils.

[Alexis.M]

Tu as marqué la discussion comme résolue mais je me permets de te conseiller d'utiliser plutôt des techniques du genre:

- Multi-dimensional scaling
- Sammon's mapping
- Curvilinear Component Analysis (partie projection)

[Alikendarfen]

Merci Alexis de ces nouvelles propositions,

Je reprends les principales caractéristiques recherchées, si tu pouvais m'orienter dans les choix de solution après ça, ça serait .

- Nombre d'éléments à traiter : N = quelques dizaines de milliers

- Vecteur de caractéristiques pour chaque élément : N = quelques dizaines de milliers (ce vecteur est constitué en attribuant à chaque élément une valeur de corrélation avec chaque autre).

- Dégager des groupes d'éléments homogènes (ou les plus homogènes possible) en nombre d'éléments. Les éléments sont regroupés par proximité selon les vecteurs de corrélation.

- Mapper les groupes dans l'espace (plan 2D dans mon cas). Idéalement, ce mapping organise les groupes par proximité (deux groupes proches dans le plan correspondent à des éléments proches).
Et donc, l'espace pour cette projection (dans le plan) n'est pas celui des vecteurs caractéristiques des éléments.

- Offrir des temps de calcul raisonnables. Cible : de l'ordre de 30 minutes sur un bon pc standard.

- Être incrémental, décrémental : j'envisage de prendre en compte les éléments du problème sur une période glissante. Il y aura donc des éléments entrants et des éléments sortants. Si l'algo permet de (relativement) facilement faire ça, sans remettre totalement en cause les calculs précédents, ça serait un plus...


Merci par avance de ton (vos) retour(s) !

[Alexis.M]

voyons si j'ai bien compris:
- tu as des données sous forme d'une matrice de similarité S S(i,j) donne la similarité entre entre les élement i et j)
- tu veux trouver un mapping vers un espace de dimension 2 où les distance reflètent les similarités dans S.

Là où je ne suis pas, c'est où intervient la dimension temporelle ? Si les élements à comparer changent au cours du temps cela veux également dire que la manière dont tu représentes tes données change également non, puisque la représentation sous forme de matrice de similarité dépends justement des éléments présents ?

[Alikendarfen]

Là où je ne suis pas, c'est où intervient la dimension temporelle ? Si les élements à comparer changent au cours du temps cela veux également dire que la manière dont tu représentes tes données change également non, puisque la représentation sous forme de matrice de similarité dépends justement des éléments présents ?

L'idée est de mettre à jour graduellement les résultats, suivant l'évolution des données d'entrée.


Prenons un exemple théorique :

Imaginons que les données d'entrée soient des achats effectués par un ensemble de clients. Chaque client achète différents produits.

Dans ce cadre, les éléments d'entrée pourraient être les produits. Et les corrélations étudiées seraient que ces produits (par paires) aient été achetés ensemble ou par différents clients mais sur un laps de temps commun.

Au fil des jours, les corrélations changent (du fait des acheteurs ou du fait de l'offre). Mais une des difficultés est de ne pas connaitre a priori à quel moment elles changent (on souhaite trouver un procédé qui nécessite le minimum d'inputs externes).

Par contre, si on assimile la grille de sortie aux rayons d'un grand magasin, celle-ci est structurellement stable. Mais son implantation peut évoluer.



C'est d'ailleurs en partie à cause de ce dernier point que Kohonen avait retenu mon attention : on peut figer la structure des sorties et jouer sur "un rayon de corrélation" modulant l'impact de l'affectation d'un neurone en entrée sur la couche de sortie.

Maintenant, je suis un peu à la pèche pour trouver le bon algo ou la bonne méthode...

[Alexis.M]

L'idée est de mettre à jour graduellement les résultats, suivant l'évolution des données d'entrée.


Prenons un exemple théorique :

Imaginons que les données d'entrée soient des achats effectués par un ensemble de clients. Chaque client achète différents produits.

Dans ce cadre, les éléments d'entrée pourraient être les produits. Et les corrélations étudiées seraient que ces produits (par paires) aient été achetés ensemble ou par différents clients mais sur un laps de temps commun.

Au fil des jours, les corrélations changent (du fait des acheteurs ou du fait de l'offre). Mais une des difficultés est de ne pas connaitre a priori à quel moment elles changent (on souhaite trouver un procédé qui nécessite le minimum d'inputs externes).

Ok pour l'instance je suis à peu près. Je vais reformuler à ma façon. Tu disposes donc d'une matrice S qui te donnes la similarité au sens de la co-occurence (ou d'une mesure de corrélation) entre des élements (des produits par exemple). A priori la liste des produits peut-être fixe, mais la matrice S peut évoluer avec le temps.

Déjà à mon avis tu n'a pas le droit d'utiliser les lignes de la matrice S comme des points habituelles et de mesurer la distance euclidienne entre ces points. Par contre pour une mesure de similarité adaptée tu peux voir ta matrice S comme une matrice noyau (une matrice dont les éléments correspondent à quelque chose qui se comportent comme un produit scalaire). Sous certaines conditions (dont on pourra discuter si cela t'interresse), une mesure de distance peut être donnée par D(i,j) = S(i,i) + S(j,j) - 2 * S(i,j).

Le problème c'est que des algos types Kohonen ne sont pas applicables directements et qu'il faudra les adapter pour fonctionner en mode "noyau".

Par contre, si on assimile la grille de sortie aux rayons d'un grand magasin, celle-ci est structurellement stable. Mais son implantation peut évoluer.

Là par contre je ne suis plus. Es-tu en train de dire que tu aimerais trouver une sorte de mapping entre la position géométrique dans le magazin des produits et leur proximité en terme de corrélation ?

Dans ce cas en effet Kohonen paraît une bonne base de départ à ceci près que comme je l'ai dit plus haut tu ne peux pas utiliser les lignes de S comme des points de donnés. Mais il doit tout à fait être possible d'adapter l'algo où un autre sans structure prédéfinie tel que les cartes de Sammon.

Ces algos sont typiquement des algos "en ligne" donc il est tout à fait possible d'adapter les positions des unités de sortie au court du temps lorsque la matrice S évolue.

[Alikendarfen]

Merci de ce retour Alexis.

Que veux tu dire par :

Déjà à mon avis tu n'a pas le droit d'utiliser les lignes de la matrice S comme des points habituelles et de mesurer la distance euclidienne entre ces points. Par contre pour une mesure de similarité adaptée tu peux voir ta matrice S comme une matrice noyau (une matrice dont les éléments correspondent à quelque chose qui se comportent comme un produit scalaire). Sous certaines conditions (dont on pourra discuter si cela t'interresse), une mesure de distance peut être donnée par D(i,j) = S(i,i) + S(j,j) - 2 * S(i,j).

Et notamment, "pas le droit" dans cette citation ?

Ce qu'il se passe, c'est que j'ai vérifié Kohonen et que j'obtiens des résultats.... je ne sais pas s'ils sont les meilleurs possibles, mais ça fonctionne...

Au-delà de ça, je comprends bien ta remarque et me pose plein de questions sur cette notion de distance et sur sa sémantique (voir un de mes autres posts sur la question).

Le problème c'est que des algos types Kohonen ne sont pas applicables directements et qu'il faudra les adapter pour fonctionner en mode "noyau".

Là, je ne comprends pas du tout. Que veux tu dire par "en mode noyau" ?

Là par contre je ne suis plus. Es-tu en train de dire que tu aimerais trouver une sorte de mapping entre la position géométrique dans le magazin des produits et leur proximité en terme de corrélation ?

Non, c'est plutôt définir la position idéale dans le magasin pour que les produits les plus achetés ensemble soient proches physiquement (je précise que cette histoire de magasins n'est qu'une illustration que j'espère "parlante", mais pas du tout le domaine d'application cible : donc il ne faut pas y voir une cible absolue).

Dans ce cas en effet Kohonen paraît une bonne base de départ à ceci près que comme je l'ai dit plus haut tu ne peux pas utiliser les lignes de S comme des points de donnés. Mais il doit tout à fait être possible d'adapter l'algo où un autre sans structure prédéfinie tel que les cartes de Sammon.

Ces algos sont typiquement des algos "en ligne" donc il est tout à fait possible d'adapter les positions des unités de sortie au court du temps lorsque la matrice S évolue.

Je vois bien le lien entre matrice et ensemble de vecteurs. Mais je pense le truc en tant que "individus caractérisés" (donc une liste d'individus définis par un vecteur et pris en compte tous ensemble).
Cette distinction me semble importante (si ça compte mathématiquement ou algorithmiquement), car je ne cherche pas une transformation de signal, mais bien une projection d'éléments d'un espace vers un autre et leur segmentation.


Je n'ai pas encore eu le temps de comprendre complètement Sammons... mais je m'y penche...

Notamment, là où Kohonen crée un impact de l'affectation d'une entrée sur une sortie, il semble que Sammons induit une mesure corrective.
Mais au-delà des calculs (des formules utilisées) quelle est la différence réelle ?

[davcha]

Si tu as une matrice n x n de distances D (peut être vérifié par le fait que tu as une seule valeur propre positive), tu peux retrouver une position P des points qui respecte D ainsi :

J = I - e e^T / n
V E V^T = -0.5 J D J
P = V E^0.5

I: l'identité
e: le vecteur (1,1,1,...,1)^T
V, E: vecteurs et valeurs propres de ce qu'il y a à droite de l'égalité

Avec 20000 points... C'est un peu casse couille... Mais tu as peut-être la possibilité de le faire en plusieurs fois...

[Alexis.M]

Les cartes de Kohonen font en même temps deux choses différentes:
1) Elles effectuent une quantification vectorielle
2) Elles effectue un "mapping" entre les données dans leur espace de départ
et un placement dans un espace de dimension réduite.

Les algorithmes habituels de quantification vectorielle (classification) considèrent que les points sont donnés sous forme de vecteurs dans un espace Euclidien dans lequel ont peut calculer la distance:

d(x,y) = sqrt((x - y)' (x - y)) = sqrt( x' x + y' y - 2 * x' y )


Ici ce n'est pas le cas, ici ce que tu connais ce sont les similarités entre tes paires de points. C'est ce qui arrive si par exemple tu considères la matrice de Gram G de tes données, c'est à dire la matrice dont les éléments sont les produits scalaires des points pris deux à deux.

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

La fonction qui produit cette matrice est appelée un "noyau".

Lorsque tu ne disposes que de la matrice noyau (kernel en anglais), tu ne peux pas appliquer directement k-means ou Kohonen, il faut réecrire les algorithmes de manière à ne faire apparaître que les produits scalaires qui peuvent alors être remplacés par les élement de la matrice noyau. C'est ce que j'appelle "le mode noyau".

De la même façon que tu peux définir la distance à partir du produit scalaire, tu peux définir une distance à partir d'un noyau: d(x,y) = sqrt(k(x,x) + k(y,y) - 2 * k(x,y))

La méthode proposée par Davcha s'applique d'ailleurs tout à fait à la matrice noyau:

K = V E V^T
P = V E^1/2

Le problème de cette méthode à mon avis est qu'elle est n'est applicable si tu veux modifier la matrice K au cours du temps