{"id":359,"date":"2013-12-06T15:04:53","date_gmt":"2013-12-06T20:04:53","guid":{"rendered":"http:\/\/homepages.uc.edu\/~yaozo\/wordpress\/?p=359"},"modified":"2013-12-06T15:04:53","modified_gmt":"2013-12-06T20:04:53","slug":"fuzzy-c-means-clustering","status":"publish","type":"post","link":"https:\/\/zhuoyao.net\/index.php\/2013\/12\/06\/fuzzy-c-means-clustering\/","title":{"rendered":"Fuzzy C-Means Clustering"},"content":{"rendered":"

The Algorithm<\/em><\/span>
\nFuzzy c-means (FCM) is a method of clustering which allows one piece of data to belong to two or more clusters. This method (developed by\u00a0Dunn in 1973<\/a>\u00a0and improved by\u00a0Bezdek in 1981<\/a>) is frequently used in pattern recognition. It is based on minimization of the following objective function:<\/span><\/p>\n

\"\"\u00a0\u00a0\u00a0\u00a0\u00a0,\u00a0\u00a0\u00a0\u00a0\u00a0\"\"<\/p>\n

where\u00a0m<\/em>\u00a0is any real number greater than 1,\u00a0uij<\/sub><\/em>\u00a0is the degree of membership of\u00a0xi<\/sub><\/em>\u00a0in the cluster\u00a0j<\/em>,\u00a0xi<\/sub><\/em>\u00a0is the\u00a0i<\/em>th of d-dimensional measured data,\u00a0cj<\/sub><\/em>\u00a0is the d-dimension center of the cluster, and ||*|| is any norm expressing the similarity between any measured data and the center.
\n<\/span>Fuzzy partitioning is carried out through an iterative optimization of the objective function shown above, with the update of membership\u00a0uij<\/sub><\/em>\u00a0and the cluster centers\u00a0cj<\/sub><\/em>\u00a0by:<\/span><\/p>\n

\"\"\u00a0\u00a0\u00a0\u00a0\u00a0,\u00a0\u00a0\u00a0\u00a0\u00a0\"\"<\/p>\n

This iteration will stop when\u00a0\"\", where\u00a0\"\"\u00a0is a termination criterion between 0 and 1, whereas\u00a0k<\/em>\u00a0are the iteration steps. This procedure converges to a local minimum or a saddle point ofJm<\/sub><\/em>.
\n<\/span>The algorithm is composed of the following steps:<\/span><\/p>\n\n\n\n
\n
    \n
  1. Initialize U=[uij<\/sub>] matrix, U(0)
    \n<\/sup><\/em><\/span><\/li>\n
  2. At k-step: calculate the centers vectors C(k)<\/sup>=[cj<\/sub>] with U(k)\n

    <\/sup><\/span><\/em>\"\"
    \n<\/span><\/em><\/li>\n

  3. Update U(k)<\/sup>\u00a0, U(k+1)\n

    <\/sup><\/span><\/em>\"\"
    \n<\/span><\/em><\/li>\n

  4. If || U(k+1)<\/sup>\u00a0– U(k)<\/sup>||<\"\"\u00a0then STOP; otherwise return to step 2.<\/span><\/em><\/li>\n<\/ol>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    Remarks<\/span><\/strong>
    \nAs already told, data are bound to each cluster by means of a Membership Function, which represents the fuzzy behaviour of this algorithm. To do that, we simply have to build an appropriate matrix named U whose factors are numbers between 0 and 1, and represent the degree of membership between data and centers of clusters.
    \nFor a better understanding, we may consider this simple mono-dimensional example. Given a certain data set, suppose to represent it as distributed on an axis. The figure below shows this:<\/span><\/p>\n

    \"\"<\/p>\n

    Looking at the picture, we may identify two clusters in proximity of the two data concentrations. We will refer to them using \u2018A\u2019 and \u2018B\u2019. In the first approach shown in this tutorial – the k-means algorithm – we associated each datum to a specific centroid; therefore, this membership function looked like this:<\/span><\/p>\n

    \"\"<\/p>\n

    In the FCM approach, instead, the same given datum does not belong exclusively to a well defined cluster, but it can be placed in a middle way. In this case, the membership function follows a smoother line to indicate that every datum may belong to several clusters with different values of the membership coefficient.<\/span><\/p>\n

    \"\"<\/p>\n

    In the figure above, the datum shown as a red marked spot belongs more to the B cluster rather than the A cluster. The value 0.2 of \u2018m\u2019 indicates the degree of membership to A for such datum. Now, instead of using a graphical representation, we introduce a matrix U whose factors are the ones taken from the membership functions:<\/span><\/p>\n

    \"\"\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\"\"<\/span><\/p>\n

    (a)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0(b)<\/span><\/p>\n

    The number of rows and columns depends on how many data and clusters we are considering. More exactly we have C = 2 columns (C = 2 clusters) and N rows, where C is the total number of clusters and N is the total number of data. The generic element is so indicated:\u00a0uij<\/sub><\/em>.
    \nIn the examples above we have considered the k-means (a) and FCM (b) cases. We can notice that in the first case (a) the coefficients are always unitary. It is so to indicate the fact that each datum can belong only to one cluster. Other properties are shown below:<\/span><\/p>\n