Introduction to Fuzzy C-Means
Learn fuzzy c-means clustering algorithms.
In k-means, the boundaries between clusters are hard or crisp (that is, a data point either belongs to a cluster or not). Fuzzy c-means, also known as fuzzy k-means, extend k-means by fuzzifying the boundaries, that is, allowing data points to simultaneously belong to many clusters with varying degrees of membership. As such, a data point, for example, may have 40% membership with Cluster 1 and 60% membership with Cluster 2. Such clusters are called soft or fuzzy, as there are no concrete boundary lines between them.
Assumptions and target cluster type
The key extension of fuzzy c-means over k-means is that it utilizes fuzzy clusters instead of crisp ones. Its assumptions and implications are the same as those of k-means (that is, it still looks for spherical-shaped clusters).
Method
We will adopt the description of this algorithm from Yen and Langari (1999) on Fuzzy logic. Similar to k-means, the inputs of FCM are:
- The input dataset,
- The distance function with
x
andy
being data points in D (optional). - The number of clusters,
- A convergence threshold .
- The fuzziness parameter , which controls how fuzzy the clusters will be. The higher is, the fuzzier the clusters (more details follow).
Usually, is set to be the Euclidean distance function.
FCM follows the following steps mentioned below.
Step 1: Initialization
Select K initial centroids, represented as mean vectors . These centroids can be selected randomly or with prior knowledge.
Step 2: Cluster membership computation
For all clusters , the memberships of each data point are computed as follows:
where
- is between and
- and denote the distance between and clusters
Note here that is the exponent fuzzy membership and is a parameter in the objective function, and denotes the fuzziness of the cluster. As approaches , the membership values degrade to either or (i.e., the membership to the closest cluster will approach and others will approach ).
In the above equation is proportional to ,with
acting as a normalization term.
When goes to infinity, the exponent approaches . Thus, the term approaches . This means it doesn’t matter which cluster is closer to —all memberships will be almost the same. This is what extreme fuzziness looks like: every point has similar membership to every cluster, regardless of their proximity. On the other hand, as goes to , the term grows exponentially with the inverse of the distance toward infinity. Through normalization, the distance to the closest cluster will greatly outweigh the rest, thus making for very crisp boundaries.
Step 3: Centroid update
Cluster centroids are recomputed as weighted means of their members, taking into account the membership :
where
- are points in dataset ,
- is the centroid of cluster
j
, and - $μ_{c_j} (x) is the membership degree of in cluster .
Step 4: Cluster membership re-computation
The cluster membership values of each data point in D are recomputed after the centroid update using the cluster membership equation.
Step 5: Stability checking and termination
This equation checks whether the difference between the centroid of a cluster over all clusters doesn’t change more than a specific threshold set as an input. If it’s below that threshold, then it’s deemed converged and the algorithm terminates. Otherwise, go back to Step 3.
Hyperparameter tuning
The key parameter to tune for fuzzy c-means is the number of clusters . While the fuzziness parameter m could be a target for tuning, it usually suffices to fix , unless there’s some domain knowledge to set it otherwise. The distance metric is often set to Euclidean distance.
A practical example of applying FCM
In the lab Fuzzy c-means of the chapter, we show how to use FCM to cluster the player data in the DOTAlicous
dataset. The usage of FCM here is almost identical to k-means, except with a different function: fanny
instead of k-means
. In first, we also clean and normalize the data. Then, we will call the fanny method. Please follow the second lab to understand the practical aspect of applying the appropriate methods.
After applying fuzzy c-means, we can inspect the memberships by printing the membership degrees for each centroid. The following table shows the result, where each row corresponds to one data point labeled by its unique row name (B, B.1, N, B.2, etc.), and each column indicates the membership to the corresponding centroids (that is, centroid 1, 2, 3, or 4). The membership values on each row should sum up to 1.
Get hands-on with 1200+ tech skills courses.