Discussion :

[Alikendarfen]

Bonjour,

Je suis en train d'implémenter un flame clustering. Cette implémentation se base sur ce que j'ai pu trouver sur internet, essentiellement ces deux liens :
- Wikipedia http://en.wikipedia.org/wiki/FLAME_clustering
- Cette implémentation en C (je code de mon coté en C#) : https://code.google.com/p/flame-clus...e/#svn%2Ftrunk

Dans l'ensemble, tout va bien, mais je souhaiterais avoir quelques conseils sur le forum :

- Calcul des distances :
Ca consomme beaucoup de mémoire et donc je souhaite limiter les données maintenues aux seuls plus proches voisins. Ca n'est pas un problème technique en soit, mais point suivant...

- Les k plus proches voisins :
Deux aspects ici.
Le premier : si deux voisins sont à même distance est-ce qu'ils ne comptent que pour 1 parmi les k ?
Le second : si la réponse à la question précédente est oui, je risque avoir tous les individus en tant que voisins en vis à vis de chaque individu (cela en fonction du problème traité)... et donc retomber sur le problème de consommation mémoire évoqué ci-dessus.

- L'itération :
Wikipedia indique deux choses :
Etapes 2.1.1 et 2.1.2 : "... with fixed and full ..."
Etape 2.2 : "Then the fuzzy memberships of all type 3 objects are updated by a converging iterative procedure called..."

Et le code C (si je l'ai bien décrypté) semble n'itérer que sur ce que wikipedia appelle "the rest".

Quelle est la bonne approche, dans la pratique ?


Merci de vos retours,

[souviron34]

Salut

Juste une petite remarque en passant (je ne suis pas le plus compétent pour le sujet sur ce forum) :

- Calcul des distances :
Ca consomme beaucoup de mémoire et donc je souhaite limiter les données maintenues aux seuls plus proches voisins. Ca n'est pas un problème technique en soit, mais point suivant...

L'algo calcule des vraies distances... Tu n'en as pas besoin, si je ne m'abuse... Il me semble que c'est uniquement utilisé comme point de comparaison... Dans ce cas, le carré est équivalent, et tu évites des calculs de racine carrée partout (ce qui est très lourd).

Par contre, pour la mémoire, je n'ai pas d'idées comme ça, à moins de rentrer dans le code et l'algo...

[Alikendarfen]

Merci Souviron pour ce conseil.

Oui la distance ne sert que temporairement pour la sélection des k plus proches voisins.

Mais sinon, mon premier cadre d'application n'utilise pas du tout une distance euclidienne. La "distance" ou plutôt valeur que j'utilise est basée sur le nombre d'éléments communs ou non communs entre deux ensembles et sur le nombre d'occurrences des éléments de ces ensembles par rapport à la population globale.

Edit :
pour bien préciser cependant, le point concernant la mémoire est surtout dépendant du point d'après concernant les k plus proches voisins.

[souviron34]

ok pas de pbe.. Je remarque juste dans le code C qu'il y a des sqrt partout... et qu'elles me semblent toutes inutiles (mais je ne suis pas rentré dans l'algo)...

[Alikendarfen]

ok pas de pbe.. Je remarque juste dans le code C qu'il y a des sqrt partout... et qu'elles me semblent toutes inutiles (mais je ne suis pas rentré dans l'algo)...

Je suis d'accord. J'ai utilisé le code C essentiellement pour approfondir ma compréhension de l'article de wikipedia, mais mon implémentation est totalement différente sur pas mal de points.

Notamment, le calcul de la distance entre deux éléments est une fonction paramètre externe à l'algo dans ma version.

[ToTo13]

Le premier : si deux voisins sont à même distance est-ce qu'ils ne comptent que pour 1 parmi les k ?

Non, je ne vois pas pourquoi ils compteraient pour 1. Si les deux points sont les plus proches, ils sont donc les 2 plus proches voisins et non l'unique plus proche voisin.

[Alikendarfen]

Merci Toto13,

Je me posais cette question parce que mon premier cadre d'application travaille sur des valeurs discrètes en terme de "distances".

Du coup, j'ai des situations ou la distance ne comprend finalement qu'un petit nombre de valeurs différentes.

Et donc, selon toi, quelle influence cela peut-il avoir sur l'algo ? (le fait qu'un élément à distance d soit maintenu parmi les voisins alors qu'un autre voisin à la même distance d ne l'est pas)

[souviron34]

(le fait qu'un élément à distance d soit maintenu parmi les voisins alors qu'un autre voisin à la même distance d ne l'est pas)

Un bug ?

Si la distance est la même, alors ils doivent tous les 2 être gardés, non ? Qu'est-ce qui te permettrait/autoriserait à en éliminer un plutôt qu'un autre ?

[Alikendarfen]

Un bug ?

Si la distance est la même, alors ils doivent tous les 2 être gardés, non ? Qu'est-ce qui te permettrait/autoriserait à en éliminer un plutôt qu'un autre ?

C'est bien la question que je me pose !! Mais après ça, je n'arrive pas à voir/comprendre précisément l'impact sur la convergence de l'algo...

[souviron34]

Dans TA version (que je ne connais pas) n'y aurait-il pas un pbe avec des "<=" à la place de "<" ou inversement des ">=" à la place des ">" ?

Dans la verson C, je vois beaucoup de "petits" problèmes pouvant amener à ça :

• Des divisions de float avec des (m+1) ou des m , qui, bien qu'à priori puissent être promues au type de l'élément de gauche, sont souvent dans les faits des divisions ntières, sauf si on caste la valeur
  
  
• Des mélanges doubles/floats, avec des additions de floats stockées dans des doubles sans cast, ce qui laissent présager des "arrondis" quelque peu tendancieux
  
  
• Des usages de EPSILON indifférement pour des floats ou des doubles, alors que il y a 2 valeurs distinctes (FLT_EPSILON et DBL_EPSILON), une pour chaque cas. Et donc tester une inégalité pour en déduire quelque chose avec ça est hautement sujet à caution...
  
  
• Et ça, c'est vraiment en "survolant" le code...

[Alikendarfen]

Dans TA version (que je ne connais pas) n'y aurait-il pas un pbe avec des "<=" à la place de "<" ou inversement des ">=" à la place des ">" ?[/LIST]

Ben écoute, non... et à la limite ça n'est pas trop le truc : il arrive que des voisins soient à la même distance d'un autre et c'est tout.

Ma question, c'était plutôt de connaitre l'impact sur le résultat de l'algo entre :
- prendre strictement les k premiers (peu importe les égalités)
- ou bien garder tous les voisins à même distance, dans la limite de k distances distinctes


(ps : je n'ai pas posté ce sujet pour une histoire de bug)