K means clustering

Bonjour,

Je suis entrain d’implémenter l'algorithme K-means pour repartir une population de points en cluster cependant je rencontre quelques difficultés à la finaliser puisque j'obtiens aussi bien ça que ceci.
Du coup je me demande si la précision de l'algo fait que je n'obtiens pas tout le temps le bon graph ou si c'est parce que j'ai fait une erreur dans mon code.
Pour l'algorithme, je suis l’implémentation suivante:
1 - Random des centroids
2 - Affectation des points à chacun des centroids en utilisant la distance pour déterminer le centroid d'appartenance et calcul des nouveaux centroids
3 - Check si les anciens centroids et les nouveaux centroids sont differents.
4 - répétition de l'étape 2 et 3 jusqu’à ce que les anciens et nouveaux centroids soient les mêmes.

Merci

Ton implémentation est bonne. Les résultats que tu obtiens sont typiques de l'algorithme K-Means.

Comme indiqué dans le lien ci-dessus, tu peux grandement améliorer la segmentation en modifiant la méthode d'affectation des points :
- pour chaque cluster calcul du centre ET de la variance => modélisation d'une distribution gaussienne G(x)
- affectation d'un point selon sa probabilité d'appartenance aux gaussiennes => G1(x) > G2(x), alors x appartient au cluster 1

Si j'ai bien compris, une fois que j'ai ma densité de probabilité pour chacun des clusters, j'utilise la règle de Bayle qui va me donner une probabilité d'appartenance à un cluster ??

Citation:

---

Envoyé par Edisean

Si j'ai bien compris, une fois que j'ai ma densité de probabilité pour chacun des clusters, j'utilise la règle de Bayle qui va me donner une probabilité d'appartenance à un cluster ??

---

Si tu veux appliquer strictement la méthode "Expectation–maximization", oui c'est cela.

Sinon, tu peux simplement utiliser la loi de proba (calculée a l'itération précédente) comme distance, en lieu et place de la distance euclidienne.

Concernant Bayle, si je veux appliquer la règle à un point je dois bien faire:
dP(x).dP(y) /ensemble(dP(x).dP(y)) avec dP= densité de probabilité lié à un cluster ??

Merci pour tes réponses.

Citation:

---

Envoyé par Edisean

Concernant Bayle, si je veux appliquer la règle à un point je dois bien faire:
dP(x).dP(y) /ensemble(dP(x).dP(y)) avec dP= densité de probabilité lié à un cluster ??

Merci pour tes réponses.

---

Je suppose que tu as séparé la loi de proba en un produit de 2 lois orthogonales, une sur X et une sur Y. Auquel cas, oui c'est bien cela.

Bonjour,

tu peux également exploiter la disjonction des clusters pour exprimer ta densité de probabilité comme un mélange de lois et utiliser la propriété de Markov pour en simplifier l'expression. Il existe une interprétation probabiliste des k-moyennes qui est par exemple décrite dans le livre de Dreyfus et al. anciennement intitulé "Réseaux de neurones", qui s'appelle "Apprentissage statistique" dans sa dernière version, et qui est publié chez Eyrolles.