|
Does anyone know where I can find a demonstration that prove the convergence of the Fuzzy C-Means algorithm (or K-Means)? It could be also helpful a proof that those algorithms belong to the family of Expectation Maximization (EM) algorithms. |
|
These books were really helpful: -James C. Bezdek. Pattern Recognition with Fuzzy Objective Function Algorithms (1981) -Sadaaki Miyamoto, Hidetomo Ichihashi. Algorithms for Fuzzy Clustering Methods in - Means Clustering with Applications Springer(2008) |
|
For K-Means and EM you can look into Bishop's "Machine Learning and Pattern Recognition". Basically each step in K-Means improves the objective function. As there are only finitely many possible cluster assignments, it will even finish in a finite number of steps. I don't know about fuzzy C-Means but I guess that also has an objective function that you decrease in every step.
This answer is marked "community wiki".
Thanks for your reply. Fuzzy C-Means also minimize an objective function but I need the proof that the iterative algorithm converges to the minimum.
(Apr 16 '12 at 09:38)
JustGlowing
To the minimum? I'm not familiar with fuzzy C-Means but that seems unlikely. Probably it will converge to a local minimum. For EM you can view it as an alternating optimization of two convex functions. I would guess the same is true for fuzzy C-Means. This should be sufficient.
(Apr 16 '12 at 10:13)
Andreas Mueller
of course, it's always a local minimum.
(Apr 18 '12 at 05:01)
JustGlowing
|
