Discussion :

[klandah]

Bonjour,

J'ai un dataset de n données, où chaque donnée est représenté par un ensemble d'attributs que d’extrait à partir de la donnée. Généralement, les algorihmes de clustering ont besoin que les données soient de même dimensions (le même nombre d'attributs), c'est à dire, les données en entrées sont représentés par une matrice X de n*d (de "n" donnée, et chaque donnée a "d" attributs). Dans mon cas, j'ai préalablement extrait des attributs à partir de mes données, mais le nombre d'attributs extraits à partir de chaque donnée est différent (j'ai donc un dataset X où les données n'ont pas le même nombre d'attributs). Y'a il une façon quelconque de les adapter afin de les classer en utilisant des algorithmes de clustering classiques qui requiers que données en entrée soient de même dimensions (pour pouvoir calculer une distance entre eux).

Pour mieux comprendre, je précise que chaque donnée de mon dataset est une image contenant un mot manuscrit. J'extrais toujours "m" attributs à partir de chaque composante connexe (une sorte de pseudo-mots) du mot, donc si le mot contiens "c" composantes connexes, le nombre d'attributs extraits à partir de ce mot est d = m*c. Le nombre d'attributs extraits pour chaque donnée (mot) de mon dataset dépend donc de "c" (le nombre de composantes connexes que ce mot contiens) et "c" peut être différent d'un mot à un autre (même pour 2 mots de la même classe, mais bon moins souvent que 2 mots de classes différentes).

Merci d'avance,

[Aleph69]

Bonsoir,

un problème de clustering est posé dans un espace (vectoriel) et suppose donc que les données appartiennent à cet espace et soient par conséquent de même dimension. Il faut donc intervenir en amont, i.e. modifier le codage des données.

Si j'ai deux vecteurs de dimensions respectives n et m, avec n différent de m, comment puis-je les sommer? La réponse à cette question est : "la somme en question n'est pas définie" (cf la définition des espaces vectoriels si tu ne vois pas pourquoi). Il est possible qu'on te propose du bidouillage, par exemple du "padding", mais le pragmatisme ne doit pas prévaloir en sciences.

Ton problème de clustering est directement lié à ce problème de somme et adapter des algorithmes a une situation qui n'a pas lieu d'être n'est donc pas recommandée.

[klandah]

Bonsoir,

un problème de clustering est posé dans un espace (vectoriel) et suppose donc que les données appartiennent à cet espace et soient par conséquent de même dimension. Il faut donc intervenir en amont, i.e. modifier le codage des données.

Si j'ai deux vecteurs de dimensions respectives n et m, avec n différent de m, comment puis-je les sommer? La réponse à cette question est : "la somme en question n'est pas définie" (cf la définition des espaces vectoriels si tu ne vois pas pourquoi). Il est possible qu'on te propose du bidouillage, par exemple du "padding", mais le pragmatisme ne doit pas prévaloir en sciences.

Ton problème de clustering est directement lié à ce problème de somme et adapter des algorithmes a une situation qui n'a pas lieu d'être n'est donc pas recommandée.

Oui je comprends bien que les données à classer doivent normalement être de même dimensions, mais vous proposez quoi par rapport à ce que j'ai expliqué à la fin de mon premier poste ? i.e. une donnée est segmenté en "C" parties (C est souvent différent d'une donnée à une autre), et un nombre fixe "CONST" de features est extrait sur chaque partie. Et notez dans ce cas, qu'un padding des données n'est non seulement pas une bonne idée, mais ne réglera pas le problème, vu qu'il donnera lieu à une somme (ou distance ...) erroné entre deux vecteurs.
Notez que je ne peux pas vraiment changer la manière dont j'extrait ces valeurs (CONST valeurs fixes et de signification connu sont extraits sur chaque partie du mot qui représente presque une lettre) parceque c'est "la" façon de procéder dans le contexte de mots manuscrits. Notez aussi que ces données de dimensions C*CONST (C étant variable) peuvent être utilisés directement en entrée pour faire du clustering via un HMM (le modèle de markov caché tolère que le nombre de valeurs par donnée soit différent), mais bon ce n'est pas un HMM que je veux utiliser.

[pseudocode]

Il faudrait savoir si le nombre de composantes "c" est significatif, ou alors s'il est possible de fusionner/séparer arbitrairement les c*m valeurs afin d'obtenir un vecteur de taille quelconque "k".

Auquel cas, ca revient a "resampler" un signal de longueur "c" (composé de "m" canaux), afin d'obtenir un signal de longueur "k" (composé de "m" canaux). Et donc, de resampler chaque canal.

[klandah]

Il faudrait savoir si le nombre de composantes "c" est significatif, ou alors s'il est possible de fusionner/séparer arbitrairement les c*m valeurs afin d'obtenir un vecteur de taille quelconque "k".

Il est significatif, je ne peux pas fusionner/séparer arbitrairement les c*m valeurs.

Cependant, j'ai une autre question à laquelle si vous pouvez répondre, ça pourrait m'aider à régler le problème initiale:
Supposant que j'ai un dataset éparse, où chaque donnée est décrite par un vecteur de 1000 éléments, chaque élément de ce vecteur peut être soit 0 ou 1 (un vecteur contiendra plein de "zéros" et quelque "uns" éparpillés); Auriez-vous (connaitriez-vous) une fonction de distance qui sera convenable dans cette situation, pour les clusterer ?

[pseudocode]

Supposant que j'ai un dataset éparse, où chaque donnée est décrite par un vecteur de 1000 éléments, chaque élément de ce vecteur peut être soit 0 ou 1 (un vecteur contiendra plein de "zéros" et quelque "uns" éparpillés); Auriez-vous (connaitriez-vous) une fonction de distance qui sera convenable dans cette situation, pour les clusterer ?

Tout dépend de ta définition de ce qui est "proche" et "éloigné".

Sans plus d'information je dirais le "Dynamic Time Warping"...

[klandah]

Tout dépend de ta définition de ce qui est "proche" et "éloigné".
Sans plus d'information je dirais le "Dynamic Time Warping"...

Bon j'explique mieux alors. Comme déjà dit, je peux extraire m features à partir de chaque composante connexe contenu dans un mot. Pour régler le problème initiale, je compte faire un clustering de toutes les composantes connexes de tous les mots confondus. Disant qu'avec ça j'aurai 1000 représentants (de composantes connexes), soit C = [C1, C2, ..., C1000], où chaque Ci est un vecteur de m dimensions.
Il serait ensuite possible de classer les mots vis à vis des composantes connexes préalablement classé. Pour ce faire, chaque mot w sera représenté par un vecteur Xw = [x1, x2, ..., x1000], où chaque xi prend la valeur 1 si le mot contiens une composante connexe correspondant à Ci, 0 sinon, (en gros je prend chaque composante connexe du mot w et je cherche le représentant 'Ci' le plus proche d'elle, et je met 1 à la position i correspondante dans Xw, le reste sera à 0).
J'aurai donc un dataset représentatif des mots (chaque mot représenté par un vecteur binaire, où les 1 dans ce vecteurs représentent les composantes connexes de ce mot).

P.S. dans l'absolu, les mots qui sont identiques sont sensés avoir les mêmes composantes, mais ce n'est pas toujours le cas à cause de l'écriture manuscrite (si on a deux personnes qui écrivent un même mot, l'un peut laisser un espace entre deux lettres où normalement il ne faut pas le faire, même si c'est rare) ...

[pseudocode]

Le DTW reste un bon candidat pour ton problème.

[klandah]

Le DTW reste un bon candidat pour ton problème.

Supposons que j'utilise une distance de DTW (ou euclidienne ou Hamming ou tout autre distance) comment pourrai-je apprendre le vecteur représentant de chaque groupe de vecteurs. C'est à dire, disant que j'ai deux vecteurs 1= 0100100001100 et v2 = 0001100001100, ils sont proche d'un de l'autre vu qu'ils différent seulement en 2 éléments (à la 2eme et 3eme position), le problème c'est: que sera le vecteur représentant de v1 et v2 ? Comment ajuster (apprendre) les valeurs du vecteur qui devrait représenter v1 et v2 et tout autre vi proche d'eux ?

[pseudocode]

Supposons que j'utilise une distance de DTW (ou euclidienne ou Hamming ou tout autre distance) comment pourrai-je apprendre le vecteur représentant de chaque groupe de vecteurs. C'est à dire, disant que j'ai deux vecteurs 1= 0100100001100 et v2 = 0001100001100, ils sont proche d'un de l'autre vu qu'ils différent seulement en 2 éléments (à la 2eme et 3eme position), le problème c'est: que sera le vecteur représentant de v1 et v2 ? Comment ajuster (apprendre) les valeurs du vecteur qui devrait représenter v1 et v2 et tout autre vi proche d'eux ?

Tu ne pourrais pas prendre comme représentant le vecteur qui est "globalement" le plus proche de tous les autres vecteurs du groupe ?

Un truc du genre : Vr = ArgMin{ somme_i( distance(V,Vi) ) }

[Alexis.M]

Juste une petite remarque. Si tu veux faire du clustering basé sur une distance non euclidienne, tu devrais voir du côté des versions "kernelisées" des algorithmes comme kernel K-means.

Pour la distance de Hamming tu peux aussi directement appliquer ton algo sur ton vecteur binaire d'origine concaténé avec son complément, dans ce cas la distance euclidienne correspondante correspond à deux fois la distance de hamming