Discussion :

[DirtyBoy]

bonjour à tous

je veux faire une clusterisation de points en se basant sur leur intensité lumineuse.

je sais qu'il y a un réseaux de neurones capable de faire ça mais j'en connais pas les astuces.

si vous êtes expert ou experte dans ce sujet ; merci de me filer un coup de main.

ciao

[ToTo13]

Bonjour,

le clustering par réseaux de neurones s'appelle : les cartes de Kohonen.
Tu trouveras cela dans certaines bibliothèques.

Sinon en beaucoup moins compliqué, tu as les centres mobiles, K-means, nuées dynamiques, classification ascendante hiérarchique, ... Les trois premiers étant de la même famille.

Connais tu à l'avance le nombre de classe que tu souhaites trouver ?

[mamelouk]

hello,

je profite de ce sujet pour demander quels sont les algos de clustering qui existent lorsqu'on ne connait pas à l'avance le nombre de cluster que l'on veut.

(dans mon cas je ne travaille pas avec une image)

merci

[ToTo13]

Bonjour,

oulala...

c'est un problème complexe qui est toujours d'actualité en recherche
Je sais que certaines version des cartes de kohonen peuvent déterminer automatiquement un nombre de classe (apprentissage non supervisé).

Sinon on a plutôt tendance à faire plusieurs clusterings et on évalue le résultat de chacun (critère dépendant du problème).

[mamelouk]

ok merci

si ca reste compliqué, je passe. Je vais faire un simple grid clustering (en divisant ma zone en 100 case et un seuil sur chaque case), ca devrais etre assez rapide et satisfaisant

[ToTo13]

Tu peux très bien faire une méthode simple et tester les seuils (deuxième proposition).
Quel est ton problème exactement ?

[mamelouk]

mon problème c'est une map google avec plusieurs centaines (voir plusieurs milliers) de marqueurs, avec des concentration des points sur les villes

a ton avis qu'est ce que je pourrais trouver comme critère si j'applique des algos non supervisés? en pratique le nombre de villes dépend du niveau de zoom

[ToTo13]

Et je suppose que tu veux trouver le nombre de villes... :s
Le problème de la résolution n'en est pas vraiment un...

Je tenterai de faire un K-Means (ou autre) en faisant varier le nombre de classes (clusters) et en regardant le critère d'erreur intra-classe. Mais ce dernier sera minimal lorsque que tu donneras autant de clusters que de marqueurs sur ta carte , donc il faut contrebalancer avec une autre énergie... par exemple le nombre de clusters lui même (mais il faut le normer par rapport à l'erreur intra-classe).

Sinon une bonne solution serait de procéder par itération :
- tu choisis plusieurs nombres de clusters différents (mais très grand, porche du nombre de marqueurs) et tu effectues les clusterisations.
- tu calcules les formes fortes.
- tu regroupes certains marqueurs ensemble en fonction de ces formes fortes, ce qui permettra après quelques itérations de regrouper les marqueurs d'une même ville.
- tu t'arrêtes lorsque tu atteints une certaines stabilité.

[mamelouk]

critère d'erreur intra-classe.. ?

je veut bien que tu m'expliques, mais étant donné que je veut pas y passer la moitié du projet je vais rester sur mon grid clustering

[ToTo13]

L'erreur intra-classe c'est très simple

Erreur intra-classe <=> C'est la somme des distances entre chaque élément et le barycentre du cluster auquel il appartient.

Tu as une petit exemple de comment la calculer dans le code que j'ai donné pour les centres mobiles/K-Means.

[velkouby]

Une autre approche pour trouver une estimation du nombres de classes dans un ensemble de données, est d'en faire une analyse spectrale.
Tu définis une distance entre les points que tu veux clusteriser, puis tu calcules la matrice de distance. Ensuite, l'étude des valeurs singulières (SVD) de cette matrice peut te renseigner sur le nombre de classe dans tes données. Tu classe des valeurs singulières par ordre décroissant, et si un nombre de classe remarquable existe, tu le verras par un décrochage des valeurs singulière (à savoir que tout à coup leur valeurs chutes). Si c'est moins évident, tu peut prendre le parti de faire un seuil sur les valeurs sigulières, qui te déterminera le nombre de classes.
Une telle méthodes permet ensuite de se servir des vecteurs singuliés correspondant aux valeurs singulières retenues (les plus grande) comme centre d'initialisation de tes classes dans le clustering de la matrice de distance. (on peut appliquer un k-means à la matrice de distance)
Il y a tous les outils qu'il faut dans matlab pour faire ca. (svd() ou svds())

PS: le probleme de cette méthode est le calcul de la matrice de distance si la quantité de données est trop importante, car l'encombrement mémoire explose. Mais il existe des solutions...

[pseudocode]

J'en profite pour glisser ici un de mes algos préférés pour le Clustering : le Mean Shift

[Pg043]

Bonjour, je me permets d'ajouter une question en lien avec l'algo des kmeans. Quelqu'un connait-il un moyen d'obtenir les seuils en fonction des centres des clusters. J'utilise kmeans pour segmenter une image présentant un histogramme tri-modal.

Merci d'avance

[ToTo13]

Quelqu'un connait-il un moyen d'obtenir les seuils en fonction des centres des clusters.

De quels seuils parles tu exactement ?
Peut on avoir une image ?

[Pg043]

De quels seuils parles tu exactement ?
Peut on avoir une image ?

J'utilise sous matlab la fonction kmeans. Cette dernier effectue une segmentation de n classes sur l'image (en vecteur) que je lui passe en paramètre et retourne l'image (en vecteur) segmentée ainsi que les centres des clusters.

Moi je voudrais à partir de ces centres de clusters trouver les valeurs des seuils de segmentation pour mesurer l' "accuracy" de cette méthode...

Des idées ?

Merci

[ToTo13]

Bonjour,

on ne peut pas parler de seuil avec les k-means.
Tu lui passes les couleurs de tous les pixels et les k-means regroupent tous les pixels en N classes.
Ensuite, à la place de chaque pixels, tu mets le numéro du cluster correspondant.
Là, c'est ce qui est fait lors d'une segmentation par k-means.

Mais pour ce qui est de ton problème. Si tu es en niveaux de gris, pour un cluster donné, il te suffit de trouver le pixel ayant la valeur minimum et le pixel ayant la valeur maximum. Ainsi tu obtiendras les deux seuils d'appartenance à un cluster dont tu parles (si j'ai compris ton problème).
Mais sur des images couleurs, cela est plus complexe car il est lié à l'espace de représentation. Tu ne pourras pas déterminer des seuils du type : RougeMin, RougeMax, BleuMin, BleuMax, VertMin, VertMax. Si tu fais ce genre de calcul, tu auras sans doute des résultats erronés.
En revanche, tu peux calculer le diagramme de Voronoi en fonction des barycentres pour avoir les limites de chaque cluster.