1
$\begingroup$

Question

In Bezdek's [1] treatment of FCM (details below) after setting up the model and explaining you can't solve it directly/with usual gradient methods, he then says he uses Picard's method to find a local minima by iterating. But there's no explicit mention of how to handle the inequality constraints (1) $u_{ji} \geq 0$ and (2) $\sum_i^n u_{ji} > 0 $.

For (1) it'd seem that the update rule for the $u_{ij}$ make them always positive.

For (2) I'd say that since in the update rule the $u_{ij}$ depend on inverse distances, they should be greater than 0 (at least in theory, numerically of course it can happen), so their sum should't be either.

Q1) Nonetheless, it is unclear to me if this is the case, and if so it seems sloppy that there's no mention of it.

Q2) Also, the Bezdek's paper [2] on alternative optimization (AO) doesn't mention Picard's method, although it does say that AO is the method used in FCM, while the original paper does not mention AO(!). From what I've read Piccard is a way to solve differential equations (finding a fixed point) and AO is a way to obtain local optima of some kinds of functions with convergence guarantees. Are they the same thing, ie, is AO a special case of Picard? [3] seems to imply they are, but Bezdek's got me a bit confused, and I myself don't see the equivalence/relationship between the two.

Q3) Finally, Bezdek mentions in [1] that the case where $m=1$ in FCM yields a discrete set of solutions. Why is that, since the $u_{ij}$ are still reals?

Background

(following Bezdek[1]) Fuzzy C-Means is a soft clustering algorithm that given $n$ examples $\mathbf{x_i} \in R^d$, tries to find:

  1. c cluster centers $\mathbf{c_j}$, and
  2. Fuzzy assignments or membership $u_{ji}$ of each example $\mathbf{x_i}$ to each cluster $j$ (whose center is $\mathbf{c_j}$)

That minimize:

$E(\mathbf{C},\mathbf{U},\mathbf{X})=\sum_j^c \sum_i^n u_{ji}^m d_{ij}^2$, where $d_{ij}= ||\mathbf{c_j}-\mathbf{x_i}||$ ($||\cdot||$ is usually the euclidean norm)

($\mathbf{C},\mathbf{U},\mathbf{X}$ are matrices containing the center, the fuzzy assignments and the dataset, respectively)

Fuzzy assignments $u_{ji}$ are restricted so that:

  1. For every example the membership to each cluster is normalized, ie, columns of $\mathbf{U}$ sum to 1:

$\sum_j^c u_{ji} = 1 \forall i$

  1. No cluster is empty:

$\sum_i^n u_{ji} > 0 \forall j$

Because of the inequality constraints the lagrangian can't be used to solve explicitly for u and c. Therefore, Bezdek says he uses Picard's method (which apparently is the same as Alternative Optimization [3]) to do a sort of em/kmeans algorithm where he starts with an initial estimation for the means, and fixing them obtains the optimal fuzzy assigments for those means, and then the other way around until convergence, which he proves by showing that E always decreases with that scheme.

The optimization criterias for obtaining $\mathbf{U}$ when $\mathbf{C}$ is known and viceversa seems to be derived by partial differentiation of the lagrangian:

$L(\mathbf{U},\mathbf{C},\mathbf{X},\mathbf{\Lambda})= E(\mathbf{U},\mathbf{C},\mathbf{X}) + \sum_i^n \lambda_i (\sum_j^c u_{ji} - 1) $

where the added term deals with the equality constraints $\sum_j^c u_{ji} = 1$.

References

[1] Bezdek et al, The Fuzzy C-Means Clustering Algorithm

[2] Bezdek et al, Some notes on alternative optimization

[3] Rough Fuzzy Image Analysis: Foundations and Methodologies

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.