01-12-2012, 02:35 PM
Spatial Fuzzy Clustering using EM and Markov Random Fields
1Spatial Fuzzy Clustering.pdf (Size: 149.43 KB / Downloads: 26)
Abstract
Methods are investigated in order to partition in kgroups a set of nmultivariate observation vectors
located at neighboring geographic sites; applications include image segmentation, ecological or soil data
cartography. In this perspective, the deterministic variant of the EMprocedure described in Zhang (1992)
for hiddenMarkov randomfields is shown to be equivalent to the optimization of a spatial fuzzy clustering
criterion using the so-called Neighborhood EM algorithm (Ambroise, Dang & Govaert 1997, Ambroise
1996). The obtained fuzzy partition can be interpreted as the (nk)posterior probabilities that the n
observations belong to the K groups, computed by an efficient iterative method based on the mean field
approximation principle. The resulting algorithm may be viewed as an extension of the k-means algorithm
to fuzzy clustering and spatial data.
Mixture models andMarkov random fields approaches.
When only the first goal is in order, i.e. when
the spatial informationis not used,mixturemodels and the Expectation-Maximization(EM) algorithm(Dempster,
Laird &Rubin 1977)may provide a relevant approach. Section 2 highlights this point, recallingHathaway’s
result, which established that applying the EMalgorithmto estimation for the parameters of a mixture is formally
equivalent to the alternative gradient optimizationof a fuzzy clustering criterion; this criterion contains
a “fuzzy” sum of within-cluster inertia (Hathaway 1986).
When both goals are considered, i.e. when a hypothesis of spatial smoothness of the partition has to be
accounted for, this note points out the relevance of EMandMarkov random fields.
CONCLUSION
graphic 4.a displays the log-likelihood of the mixture parameters estimated by NEM for values of ranging
from 0 to 1.4, and graphic 4.b displays the misclassification error for those values of . The following
observations can be made: when goes from 0 to the simulated value 1.1, the error decreases steadily from
19 % to 11 %, while the log-likelihood decreases, then stays at a steady level; when gets greater than 1.1,
the error starts rising abruptly again, and at the same time the log-likelihood drops sharply. Thus an optimal
value of might be suggested by the first sharp decrease of the log-likelihood of the mixture parameters.
This behavior could be observed on most of the simulated experiments, but no formal explanation of it could
be given yet.