Discussion :

[wildthing]

bonjour,
je travaille avec les k-means pour la segmentation d'images et je rencontre quelque chose qui me semble un peu bizarre ; je calcule à chaque itération la fonction objectif mais je remarque que celle-ci peut augmenter, est ce normal ???? n'est elle pas sensée uniquement décroître ???

[Franck Dernoncourt]

quelle est ta fonction objectif?

[wildthing]

et bien c'est la fonction à minimiser classique du kmeans; la somme des distance des centre des clusters aux points

[davcha]

Normalement, k-means converge de façon monotone, donc oui, ça ne fait que décroître.

Si tu nous montrait un peu le type de données que tu as, et ta procédure ?

[wildthing]

voici mon code en pièce jointe, il est en c++. ça fait un bon moment que je me casse tète dessus, tout me semble concorder avec le coté théorique mais il peut arriver que la fonction à minimiser augmente d'une itération à une autre. pour l'instant je n'utilise que l'intensité de l'image dans mes vecteurs

[davcha]

C'est la fête du memory leak ton code...

[wildthing]

ahhh, j'ai oublié de préciser que je débute en c++, mon code est donc loin d'etre parfait, mais qu'en est il pour le problème principal!!!!?

[davcha]

A vue de nez, j'ai pas regardé précisément dans le détail, mais il semblerait que ta réinitialisation aléatoire de clusters vides pose problème.

Si je ne me trompe pas, tu te retrouves avec des points qui overlappent sur plusieurs clusters.
Tu ferais mieux de totalement zapper cette partie. Elle n'est généralement même pas implémentée ou discutée dans les papiers de recherche sur le sujet.

[wildthing]

mais le traitement concernant les clusters vides n'arrive que très rarement dans mes tests. Est ce que vous auriez une démo ou une implémentation de de kmeans histoire de tenter de comprendre mes résultats

[ToTo13]

Même s'il y a des clusters vides, cela n'affecte en rien le fait que la fonction de coût (plutôt qu'énergie me semble t-il) doivent systématiquement décroitre.

Tu as un exemple java basique dans la rubrique contribuez.

[wildthing]

merci toto. j'avais oublié de dire que l'année passée j'avais programmé le Fuzzy-C-Means en JAVA et que j'ai rencontré exactement le même problème de fonction objectif qui s’accroît

[Alexis.M]

A priori il est normal que ta fonction de coût puisse croître au moment où tu ré-initialise les vecteurs-code orphelins mais seulement à ce moment là.

[Alexis.M]

Pour revenir à la réinitialisation des vecteurs-codes orphelins, si tes données sont très structurées (dimension intrinsèque faible par rapport à la dimension brute) tu risques de réinitialiser sans arrêt car tes nouveau vecteurs codes seront toujours orphelins. Une solution (toujours discutable) consiste à réinitialiser le vecteur code sur un des points de données.

Sinon si tu veux un peu de déboggage il serait sympa de donner un exemple prêt à compiler pour pouvoir le faire tourner car (ne le prend pas mal) ton code est un peu abscons.

[Alexis.M]

Tu t'es trompé de fonction de coût. La fonction de coût optimisé par l'algo correspond à la somme des erreurs quadratiques (carré de la distance au centroide) et non la somme des distances.

Or les deux ne croissent pas dans la même direction. Par exemple prenons deux vecteurs qui contiennent pour deux points la distance euclidienne à un autre point:

v1 : [1.0,0.0]
v2 : [0.9,0.15]

SumDistances(v1) = 1.0
SumDistances2(v1) = 1.0

SumDistances(v2) = 1.05
SumDistances2(v2) = 0.8325

Dans un cas la fonction de coût a augmenté dans l'autre elle à diminué

[wildthing]

comment est ce que j'ai pu passer à coté d'un truc pareil... un grand merci à toi Alexis tu es effectivement un membre très éclairé ;, ça fonctionne parfaitement maintenant, encore merci

[Franck Dernoncourt]

D'où ma première question.