Fuzzy C-Means (FCM) Clustering & Subtractive Clustering Overview

Introduction to FCM

Fuzzy C-Means (FCM) is a clustering technique that allows data points to belong to more than one cluster by introducing a membership matrix. It minimizes the following objective function:

\[J_m = \sum_{i=1}^N \sum_{j=1}^C u_{ij}^m \|x_i - c_j\|^2\]

where:

• $ N $: Number of data points
• $ C $: Number of clusters
• $ u_{ij} $: Degree of membership of $ x_i $ in cluster $ j $
• $ c_j $: The centroid of cluster $ j $
• $ m $: Fuzziness parameter (usually $ m = 2 $)

---

FCM Algorithm Steps

1. Initialize the number of clusters $ C $, fuzziness parameter $ m $, and the membership matrix $ U $ randomly so that the sum of the memberships for each sample is 1.

2. Compute cluster centers using the membership matrix:

   \[c_j = \frac{\sum_{i=1}^N u_{ij}^m x_i}{\sum_{i=1}^N u_{ij}^m}\]

3. Update the membership matrix:

   \[u_{ij} = \frac{1}{\sum_{k=1}^C \left( \frac{\|x_i - c_j\|}{\|x_i - c_k\|} \right)^{2/(m-1)}}\]

4. Repeat steps 2 and 3 until the membership matrix stabilizes (changes are below a threshold).

---

Python Implementation

Here is a simple implementation using NumPy:

import numpy as np

def initialize_U(n, c):
    U = np.random.rand(n, c)
    U = U / np.sum(U, axis=1, keepdims=True)
    return U

def update_centers(X, U, m):
    um = U ** m
    centers = um.T @ X / np.sum(um, axis=0)[:, None]
    return centers

def update_U(X, centers, m):
    dist = np.linalg.norm(X[:, None, :] - centers[None, :, :], axis=2)
    dist = np.fmax(dist, np.finfo(np.float64).eps)  # Avoid division by zero
    exp = 2 / (m - 1)
    denom = np.sum((dist[:, :, None] / dist[:, None, :]) ** exp, axis=2)
    U = 1 / denom
    return U

def fcm(X, c, m=2, max_iter=100, tol=1e-5):
    n = X.shape[0]
    U = initialize_U(n, c)
    for i in range(max_iter):
        centers = update_centers(X, U, m)
        U_new = update_U(X, centers, m)
        if np.linalg.norm(U - U_new) < tol:
            break
        U = U_new
    return centers, U

if __name__ == "__main__":
    from sklearn.datasets import make_blobs
    X, _ = make_blobs(n_samples=200, centers=3, n_features=2, random_state=42)
    centers, U = fcm(X, c=3)
    print("Cluster centers:\n", centers)

For practical work, you can use existing libraries such as scikit-fuzzy:

import skfuzzy as fuzz
import numpy as np

X = np.random.rand(2, 200)
cntr, u, u0, d, jm, p, fpc = fuzz.cluster.cmeans(
    X, c=3, m=2, error=0.005, maxiter=1000)

MATLAB Implementation

Below is a basic MATLAB implementation:

function [centers, U] = fcm(X, c, m, max_iter, tol)
    if nargin < 3, m = 2; end
    if nargin < 4, max_iter = 100; end
    if nargin < 5, tol = 1e-5; end
    n = size(X, 1);
    U = rand(n, c);
    U = U ./ sum(U, 2);
    for iter = 1:max_iter
        um = U .^ m;
        centers = (um' * X) ./ sum(um)';
        dist = pdist2(X, centers);
        dist(dist==0) = eps;
        denom = sum((dist(:,:,ones(1,c)) ./ permute(dist(:,:,ones(1,c)),[1 3 2])).^(2/(m-1)), 3);
        U_new = 1 ./ denom;
        if norm(U_new - U, 'fro') < tol
            break;
        end
        U = U_new;
    end
end

% X = rand(200,2);
% [centers, U] = fcm(X, 3);

Applications

• Image Segmentation: Pixels are clustered based on intensity/color, useful in medical image analysis.
• Market Segmentation: Customers can belong to multiple segments with different degrees.
• Document Clustering: Texts can have partial membership in several topics.

---

Subtractive Clustering

Subtractive Clustering is a fast, density-based clustering algorithm often used as a pre-processing step for fuzzy clustering methods, such as the Fuzzy C-Means (FCM). It is especially suitable when the number and initial locations of clusters are unknown.

The main idea of subtractive clustering is to consider each data point as a potential cluster center, and then evaluate the “density” of data points around it. Points with high density are more likely to be cluster centers. The algorithm iteratively selects the highest-density point as a cluster center and then reduces (“subtracts”) the density of data points in its neighborhood, ensuring that subsequent cluster centers are not too close to previous ones.

Subtractive Clustering Steps

1. Density Calculation For each data point $ x_i $, compute its density measure $ D_i $ as:

   \[D_i = \sum_{j=1}^N \exp\left(-\frac{\|x_i - x_j\|^2}{(r_a/2)^2}\right)\]
   • $ N $: Number of data points
   • $ r_a $: Neighborhood radius (user-defined, e.g. 0.5 times the data range)

2. Select First Cluster Center:
   Find the data point with the highest density $ D_{c_1} $ and designate it as the first cluster center.

3. Subtraction For all data points, reduce their density by:

   \[D_j = D_j - D_{c_1} \exp\left(-\frac{\|x_j - x_{c_1}\|^2}{(r_b/2)^2}\right)\]
   • $ r_b > r_a $: A radius (often 1.5 times $ r_a $) that defines neighborhood for density reduction.

4. Repeat: Choose the next point with the highest remaining density as a new cluster center, reduce densities, and repeat until the density of the next potential center falls below a threshold.

5. Result: The selected centers are the initial cluster centers, which can be used for further clustering (e.g., as FCM’s initial centers).

Limitations

• Results depend on the choice of parameters $ r_a $, $ r_b $, and density threshold.
• Not robust to highly variable density within the data.

MATLAB Example

MATLAB’s Fuzzy Logic Toolbox provides subclust for subtractive clustering:

X = rand(200,2);
ra = 0.5; % Radius
[center, sig] = subclust(X, ra);
scatter(X(:,1), X(:,2), 20, 'b'); hold on;
scatter(center(:,1), center(:,2), 80, 'r', 'filled');