Fuzzy clustering: the fuzzy c-means algorithm and points between clusters

K-means and its hard assignment, fuzzy c-means with memberships in all clusters, the fuzzifier m, the partition coefficient and the Xie–Beni index for choosing the number of clusters — and why outliers get high memberships.

13 minutes Matěj Žalmánek 2026-10-15

Series AI basics Part 36 of 52

Full series syllabus 52 of 83 topics published

What you will take away

How k-means works and what it keeps quiet about points on the boundary between clusters.
How fuzzy c-means computes memberships and centres, and what the fuzzifier m does.
How to choose the number of clusters and where fuzzy c-means fails.

Useful to know first: Fuzzy sets and membership functions: how to write down “somewhat warm”, Types of machine learning: supervised, unsupervised, semi-supervised and more

Clustering looks for groups in data that we know nothing about in advance: customers with similar shopping behaviour, regions of the same tissue in a magnetic resonance image, documents on a similar topic. The classic k-means algorithm assigns every point to exactly one group. But real data tend to have points on the boundary — a customer who shops a bit like a student and a bit like a parent, a pixel where the grey and white matter of the brain meet. Fuzzy clustering lets a point belong to several groups at once, to each of them a little.

It builds on the articles Fuzzy sets and membership functions and Types of machine learning, where clustering appeared as a typical unsupervised learning task.

1. Hard clustering: k-means

Definition — the k-means problem

Let d ≥ 1 and n ≥ 1 be natural numbers, x₁, …, x_n ∈ ℝ^d points and c ∈ ℕ, 1 ≤ c ≤ n, the number of clusters. An assignment is a mapping shluk : {1, …, n} → {1, …, c} that assigns to the point x_i the number of its cluster. For centres v₁, …, v_c ∈ ℝ^d and an assignment shluk the cost is

J(v₁, …, v_c, shluk) = ∑_i=1ⁿ ‖x_i − v_shluk(i)‖²,

where ‖·‖ is the Euclidean distance (next definition). The k-means problem is to find centres and an assignment for which J is as small as possible.

Lloyd's algorithm (an approximate solution of the k-means problem). Input: points x₁, …, x_n ∈ ℝ^d and the number of clusters c. Output: centres v₁, …, v_c and an assignment shluk. Steps:

As the initial centres choose c mutually distinct points from x₁, …, x_n (at random).
Assignment: for every i = 1, …, n choose shluk(i) ∈ argmin_{j ∈ {1, …, c}} ‖x_i − v_j‖²; if there are several nearest centres and the point’s current centre is among them, leave the point in its cluster.
Stopping: if the assignment has not changed since the previous pass, stop and return the centres and the assignment.
Centres: for every j = 1, …, c let S_j = {i : shluk(i) = j} and, if S_j ≠ ∅, set v_j = 1/|S_j| ∑_{i ∈ S_j} x_i (the mean of the cluster’s points; an empty cluster does not change its centre).
Continue with step 2.

In plain words

You place a few “flags” in the data. Every point joins the nearest one. Then each flag moves to the middle of its points. The points join the nearest flag again — and so on, until nothing changes. Every step decreases J, so the algorithm is sure to stop, though not necessarily at the best possible partition.

Definition — Euclidean distance

Let d ≥ 1 and x = (x₁, …, x_d), v = (v₁, …, v_d) ∈ ℝ^d. The Euclidean distance of the points x and v is the non-negative number

‖x − v‖ = √∑_r=1^d (x_r − v_r)².

In the plane (d = 2) it is the ordinary length of a line segment, for instance from the point M1 = (4.5, 2.5) to the centre of cluster A (1.73, 2.31) as fuzzy c-means finds it below: √2.77² + 0.19² ≈ 2.78. Clustering works with the square ‖·‖² — the square root goes away and distant points are penalised more.

def kmeans(X, c):
    V = c randomly chosen points from X           # initial centres
    while True:
        shluk = [argmin_j ‖x − V[j]‖² for x in X]  # assignment step
        if shluk did not change: return V, shluk
        for j in range(c):                         # centre step
            V[j] = mean of the points x with shluk(x) = j

Theorem — Lloyd's algorithm terminates

Let x₁, …, x_n ∈ ℝ^d, 1 ≤ c ≤ n, and let Lloyd's algorithm run according to the definition above (including the rule that on a tie the point stays in its cluster). Then

no assignment step and no centre step increases the value of J;
the algorithm stops after finitely many passes.

Proof: Assignment: each term ‖x_i − v_shluk(i)‖² is replaced by the smallest of all ‖x_i − v_j‖², so it does not increase. Centres: for a non-empty index set S of one cluster with mean x̄ = 1/|S| ∑_i∈S x_i and any v ∈ ℝ^d the decomposition

∑_i∈S ‖x_i − v‖² = ∑_i∈S ‖x_i − x̄‖² + |S| · ‖x̄ − v‖²

holds (the cross term 2 ∑ (x_i − x̄) · (x̄ − v) is zero because ∑ (x_i − x̄) = 0). The sum is therefore smallest for v = x̄. There are finitely many partitions of n points into c clusters and J strictly decreases with every change of assignment (on a tie we leave the point in its cluster), so no partition repeats. ∎

The theorem says nothing about whether the partition found is the one with the smallest J — only that the algorithm will not cycle.

Our data: three groups of 40 points — A at the bottom left, B on the right and C at the top —, four points on the boundary (M1–M4) and two outliers far from everything (O1, O2). K-means settled after four iterations:

k-means: every point belongs to exactly one cluster

It found the clusters well, but had to decide the boundary points: it put M1, M3 and M4 into B, M2 into A. Yet M3 lies almost exactly between B and C — k-means tells you nothing about that. And both outliers ended up in cluster C, as if they belonged to it just as much as its core.

2. Fuzzy c-means

Definition — fuzzy c-means (Dunn 1973, Bezdek 1981)

Let x₁, …, x_n ∈ ℝ^d be points, c ∈ ℕ, 2 ≤ c < n, the number of clusters and m ∈ ℝ, m > 1, the fuzzifier. A membership matrix is an n × c matrix U = (u_ij) (i = 1, …, n numbers the points, j = 1, …, c the clusters) that satisfies

u_ij ∈ [0, 1] for all i, j;
∑_j=1^c u_ij = 1 for every i — every point splits a total membership of 1 among the clusters;
0 < ∑_i=1ⁿ u_ij < n for every j — no cluster is empty and none swallows all points completely.

For a membership matrix U and centres V = (v₁, …, v_c) ∈ (ℝ^d)^c the cost is

J_m(U, V) = ∑_i=1ⁿ ∑_j=1^c u_ij^m ‖x_i − v_j‖².

Fuzzy c-means is the problem of finding U and V with the smallest cost J_m, and the following algorithm for solving it approximately. Input: the points, c, m, a tolerance ε > 0 and a maximum number of iterations. Output: U and V. Steps:

Choose initial centres v₁, …, v_c (e.g. c distinct random points).
Memberships: for all i, j compute d_ij = ‖x_i − v_j‖ (we assume d_ij > 0) and u_ij = 1/∑_k=1^c (d_ij/d_ik)^2/(m−1).
Stopping: if no u_ij has changed by ε or more since the previous pass, or the number of iterations is exhausted, stop (not after the first pass) and return U and V.
Centres: for every j = 1, …, c set v_j = ∑_i=1ⁿ u_ij^m x_i/∑_i=1ⁿ u_ij^m and continue with step 2.

Both computational steps follow from the optimality conditions (theorem below): each minimises J_m with the other group of variables fixed.

In plain words

Every point splits its single unit among all clusters — more to the one it is closer to. The centre of a cluster is a weighted mean of all points: points that belong to the cluster strongly pull it more, points from other clusters only slightly. The membership formula compares distances: if a point is twice as close to one centre as to the other, it gets (for m = 2) four times the membership.

J_m = ∑_i=1ⁿ ∑_j=1^c u_ij^m ‖x_i − v_j‖², ∑_j u_ij = 1

J_m: the total “cost” of the partition — the algorithm minimises it; it is small when points belong mainly to centres that are close to them
∑_i ∑_j: every point counts towards every cluster — unlike k-means, where only one cluster per point was taken
u_ij: the membership of point i in cluster j — the weight with which the distance enters the cost
^m: the fuzzifier — without the power (m = 1) it would pay to give the whole unit to the nearest centre and we would get k-means again; with m > 1 splitting pays off: a point equally far from two centres pays, for m = 2 and an even split, only (½² + ½²) · d² = ½d² instead of d²
‖x_i − v_j‖²: the squared distance — what it costs to keep the point “at” this centre; a distant centre comes out expensive
∑_j u_ij = 1: the constraint — without it the minimum would be trivial: all u_ij = 0 and zero cost

u_ij = 1/∑_k=1^c ( d_ij/d_ik )^2/(m−1)

u_ij: the new membership of point i in cluster j with the centres fixed
d_ij/d_ik: the ratio of distances — how many times farther centre j is than centre k; the ratio (not the difference) makes the result independent of the scale of the data
exponent 2/m − 1: how sharply the ratio decides — for m = 2 it is 2, so a centre twice as close gets four times as much; for m → 1 the exponent grows without bound and the nearest centre gets everything
∑_k: a comparison with all centres including j itself (the term k = j is 1) — thanks to this the memberships of a point add up to exactly 1

For m = 2 the formula simplifies to u_ij = 1/d_ij²/∑_k 1/d_ik²: the membership is proportional to the inverse square of the distance.

Theorem — where the two steps come from

Let x₁, …, x_n ∈ ℝ^d, c and m > 1 be as in the definition of fuzzy c-means. Then:

For fixed centres v₁, …, v_c for which all distances d_ij = ‖x_i − v_j‖ are positive, J_m attains its minimum over the set of matrices with u_ij ≥ 0 and ∑_j u_ij = 1 exactly at u_ij = 1/∑_k=1^c (d_ij/d_ik)^2/(m−1).
For a fixed matrix U in which ∑_i u_ij^m > 0 for every j, J_m attains its minimum over v₁, …, v_c ∈ ℝ^d exactly at v_j = ∑_i u_ij^m x_i/∑_i u_ij^m.

Proof. Memberships with the centres fixed. J_m is a sum over the points and each constraint concerns a single row of U, so it suffices to minimise, for one point i, ∑_j u_ij^m d_ij² subject to ∑_j u_ij = 1. The Lagrangian is L = ∑_j u_ij^m d_ij² − λ (∑_j u_ij − 1). From ∂L/∂u_ij = m u_ij^m−1 d_ij² − λ = 0 it follows that u_ij = (λ/m)^1/(m−1) · d_ij^−2/(m−1). Substituting into the sum constraint, the unknown λ cancels out and we are left with

u_ij = d_ij^−2/(m−1)/∑_k d_ik^−2/(m−1) = 1/∑_k (d_ij/d_ik)^2/(m−1).

The results are positive numbers, so the constraint u_ij ≥ 0 need not be enforced separately. The function u ↦ u^m d² is strictly convex on [0, 1] for m > 1 and d > 0, so this single stationary point is the minimum. (If a point lies exactly at a centre, d_ij = 0, it gets membership 1 in that cluster; our implementation handles this by never letting the distance drop below 10⁻¹².)

Centres with the memberships fixed. J_m is a convex quadratic function of v_j (strictly convex, because ∑_i u_ij^m > 0), and ∂J_m/∂v_j = −2 ∑_i u_ij^m (x_i − v_j) = 0 gives v_j = ∑_i u_ij^m x_i/∑_i u_ij^m. ∎

Each step therefore minimises J_m with the other group of variables fixed and cannot increase it — the same argument as for k-means. Bezdek et al. (1987, a correction of Bezdek's original 1980 theorem) showed that the sequence has its accumulation points at stationary points of J_m (not necessarily at the global minimum).

import numpy as np

def fcm(X, c, m=2.0, iteraci=100, eps=1e-5):
    U = np.random.dirichlet(np.ones(c), size=len(X))        # random memberships, row = 1
    for _ in range(iteraci):
        W = U ** m
        V = (W.T @ X) / W.sum(axis=0)[:, None]             # centres as weighted means
        D = np.linalg.norm(X[:, None, :] - V[None, :, :], axis=2) + 1e-12
        nove = 1 / ((D[:, :, None] / D[:, None, :]) ** (2 / (m - 1))).sum(axis=2)
        if np.abs(nove - U).max() < eps:
            return V, nove
        U = nove
    return V, U

3. Fuzzy c-means on our data

The colour of a point is now a mix of the cluster colours according to the memberships: a pure green point belongs only to A, a point “between” green and orange is partly in A and partly in B. The dotted lines show how the centres moved — the algorithm settled after nine iterations:

Fuzzy c-means (m = 2): colour is a mix by membership

Point	k-means	A	B	C
M1 (4.5, 2.5)	B	0.41	0.45	0.15
M2 (3.3, 4.5)	A	0.43	0.18	0.38
M3 (5.8, 5)	B	0.12	0.44	0.45
M4 (4.6, 4)	B	0.28	0.40	0.32

Now you can see what k-means kept quiet about. M1 is almost halfway between A and B; M3 is actually a hair more in C than in B, although k-means put it in B; and M4 in the middle of the triangle belongs a little to all three. Points in the cores of the clusters have a membership close to one in their own cluster. The centres came out practically the same as with k-means — fuzzy c-means does not change where the clusters are, but adds information about how surely each point belongs to them.

Example — memberships of the point M1 = (4.5, 2.5)

Centres after nine iterations: A ≈ (1.73, 2.31), B ≈ (7.12, 2.87), C ≈ (4.51, 7.11). For m = 2 the inverse squared distances are enough (colours as in the simplified formula for m = 2 in the caption above):

Cluster	`d`²	1/`d`²	`u` = 1/`d`²/0.3190
A	2.77² + 0.19² ≈ 7.72	0.1296	0.41
B	2.62² + 0.37² ≈ 7.03	0.1423	0.45
C	0.01² + 4.61² ≈ 21.25	0.0471	0.15
sum		0.3190	1.00

M1 is almost equally far from centres A and B (7.72 versus 7.03), and so it splits between them almost in half; C is three times farther (in squared terms), so it gets only the remainder.

4. The fuzzifier m

Definition — partition coefficient

Let n ≥ 1, c ≥ 2 and let U = (u_ij) be an n × c matrix with u_ij ∈ [0, 1] and ∑_j=1^c u_ij = 1 for every i (a membership matrix). The partition coefficient is the number

PC(U) = 1/n ∑_i=1ⁿ ∑_j=1^c u_ij².

It always holds that 1/c ≤ PC(U) ≤ 1, where

PC(U) = 1 if and only if the partition is hard: in every row one u_ij = 1 and the others are 0;
PC(U) = 1/c if and only if u_ij = 1/c for all i, j — every point belongs to all clusters equally.

(For every row ∑_j u_ij² ≤ ∑_j u_ij = 1 with equality only for the values 0 and 1, and by the Cauchy–Schwarz inequality ∑_j u_ij² ≥ 1/c (∑_j u_ij)² = 1/c with equality only for equal values.)

In plain words

A single number that says how “sharp” the partition is. For three clusters it lies between 1/3 (everything is blurred) and 1 (every point has a clear home).

PC = 1/n ∑_i ∑_j u_ij²

PC: the sharpness of the whole partition, a number from [1/c, 1]
1/n ∑_i: an average over the points — so that data sets of different sizes can be compared
∑_j u_ij²: the sharpness of a single point — the square “rewards” concentrated membership: (1, 0, 0) gives 1, (⅓, ⅓, ⅓) only ⅓; with the sum fixed at 1, the sum of squares is smallest when all parts are equal

The point M1 with memberships (0.41, 0.45, 0.15) contributes 0.41² + 0.45² + 0.15² ≈ 0.39; points from the cluster cores almost 1 — the average over all 126 points is 0.84.

Fuzzy c-means for m = 1.2, 2 and 5

For m close to 1, fuzzy c-means approaches k-means: the partition coefficient is 0.98 and point M4 belongs to B with 0.79. For m = 2 the coefficient is 0.84 and for m = 5 only 0.42 — the colours blend and even a point from the core of cluster A has a membership of only 0.45 in A. For m → ∞ all memberships would tend to 1/3. The most common choice is m = 2: soft enough for the boundary points to show, and sharp enough for the clusters to stay distinct.

Example — a point twice as close to one of two centres

A point is at distance 1 from centre 1 and at distance 2 from centre 2. In the membership formula the term k = 1 equals 1 and the term k = 2 has the ratio 1/2, so u₁ = 1/1 + (1/2)^2/(m−1) (colours as in the formula for u_ij above):

m = 1.2: exponent 10, u₁ = 1/1 + 1/1,024 ≈ 0.999 — practically a hard assignment,
m = 2: exponent 2, u₁ = 1/1 + 1/4 = 0.8,
m = 5: exponent 0.5, u₁ = 1/1 + 0.707 ≈ 0.586,
m → ∞: exponent → 0, (1/2)⁰ = 1 and u₁ → 1/2.

In general: for m → 1⁺ the exponent 2/m − 1 goes to infinity, the ratios d_ij/d_ik < 1 go to zero and those > 1 to infinity, so the nearest centre gets 1 and the others 0 (k-means). For m → ∞ the exponent goes to zero, all c terms of the sum tend to 1 and u_ij → 1/c.

5. How many clusters?

The number of clusters has to be given to the algorithm. When we do not know it, we run the algorithm for different c and compare the quality of the partitions. The partition coefficient and the Xie–Beni index are useful for this.

Definition — Xie–Beni index

Let x₁, …, x_n ∈ ℝ^d, c ≥ 2, m > 1, U = (u_ij) an n × c membership matrix and v₁, …, v_c ∈ ℝ^d mutually distinct centres (typically the result of fuzzy c-means). The Xie–Beni index is the number

XB(U, V) = ∑_i=1ⁿ ∑_j=1^c u_ij^m ‖x_i − v_j‖²/n · min_{j ≠ k} ‖v_j − v_k‖².

The denominator is positive because the centres are distinct. Xie and Beni (1991) introduced the index with exponent 2 (i.e. for m = 2); with a general m it is commonly used in the same form. When comparing partitions, the one with the smaller XB is better.

In plain words

The numerator measures how tightly the points sit around their centres; the denominator, how far apart the two nearest centres are. A good partition has compact clusters that are far from each other.

XB = ∑_i ∑_j u_ij^m ‖x_i − v_j‖²/n · min_{j ≠ k} ‖v_j − v_k‖²

XB: the ratio of the spread within clusters to the distance between them — smaller is better
∑ ∑ u_ij^m ‖x_i − v_j‖²: compactness — exactly the value of J_m that the algorithm minimised
n: the number of points — turns the numerator into an average per point, so that the index does not grow with the size of the data
min_{j ≠ k} ‖v_j − v_k‖²: separation — the nearest pair of centres decides; J_m alone only decreases as clusters are added, and this term penalises a partition that splits one real cluster into two close ones

Example — the Xie–Beni index for c = 3

When the algorithm finishes, J₂ ≈ 166.73. Squared distances between the centres: A–B ≈ 29.4, A–C ≈ 30.8, B–C ≈ 24.79 (B and C are the nearest). For n = 126 points (colours as in the formula above):

XB = 166.73/126 · 24.79 = 166.73/3,124 ≈ 0.053.

Number of clusters `c`	2	3	4	5	6
Partition coefficient (larger is better)	0.745	0.841	0.748	0.661	0.609
Xie–Beni index (smaller is better)	0.228	0.053	0.298	0.682	0.529

Both measures agree on the three clusters we put into the data. With real data such agreement cannot be taken for granted, and the measures are more a guide than a verdict.

6. Where fuzzy c-means fails

Look at the outliers: O1 at the top right has membership 0.45 in C and 0.39 in B; O2 at the top left even 0.58 in C. Yet they belong to no cluster. The blame lies with the constraint ∑_j u_ij = 1: a point has to give its unit away to someone, even when it is far from everyone. Membership here means “whom it is closest to” rather than “how well it belongs here”.

Example — why O2 = (0.2, 9.5) “belongs” to C

Squared distances to the centres: A ≈ 54.07, B ≈ 91.88, C ≈ 24.29. So even the nearest centre, C, is 4.9 away — more than six times the standard deviation of 0.8 with which the cluster points are scattered around their centres. By the formula for m = 2 (colours as in the caption of the formula for u_ij) the reciprocals 1/54.07 ≈ 0.0185, 1/91.88 ≈ 0.0109 and 1/24.29 ≈ 0.0412 give the sum 0.0706 and the memberships

u_A = 0.0185/0.0706 ≈ 0.26, u_B = 0.0109/0.0706 ≈ 0.15, u_C = 0.0412/0.0706 ≈ 0.58.

The formula sees only the ratios of the distances, not their size: the farther the point lay, the closer the ratios would get to 1 and the memberships to 1/3 — but they would never go to zero.

Definition — possibilistic c-means (Krishnapuram and Keller, 1993)

Let x₁, …, x_n ∈ ℝ^d, c ≥ 1, m > 1, v₁, …, v_c ∈ ℝ^d centres, d_ij = ‖x_i − v_j‖ and η₁, …, η_c > 0 parameters chosen in advance (usually estimated from the result of fuzzy c-means). Possibilistic c-means looks for an n × c matrix U = (u_ij) with u_ij ∈ [0, 1] — without the constraint ∑_j u_ij = 1 — and centres that minimise the cost

J(U, V) = ∑_i=1ⁿ ∑_j=1^c u_ij^m d_ij² + ∑_j=1^c η_j ∑_i=1ⁿ (1 − u_ij)^m.

The second term prevents the trivial solution U = 0. With the centres fixed, the minimum is at

u_ij = 1/1 + (d_ij²/η_j)^1/(m−1),

and the centres are computed as in fuzzy c-means. η_j is the “radius” of cluster j: a point at distance d² = η_j has membership 1/2, and for m = 2 a point with d² = 9η_j only 1/1 + 9 = 0.1. The membership now depends on the distance to a single centre, not on the ratio to the others — an outlier gets small values everywhere.

Possibilistic c-means (Krishnapuram and Keller, 1993) removes the sum constraint — an outlier then gets small memberships in all clusters.
Cluster shape. Euclidean distance produces round clusters. The Gustafson–Kessel algorithm (1979) gives each cluster its own distance matrix and finds elongated ellipses too.
Initial position. Just like k-means, it can end up in a worse local minimum — in practice it is run several times from different starts.

7. Fuzzy clustering in practice

Medical images. Segmenting magnetic resonance images of the brain into grey matter, white matter and cerebrospinal fluid is a classic application: a pixel on the boundary between tissues really does contain both.
Customer segmentation. A customer can belong partly to several groups, and marketing can take that into account.
A probabilistic relative. Gaussian mixtures trained with the EM algorithm also assign points to clusters “softly” — but by probability, not by membership. The results tend to be similar; the interpretation differs exactly as described in the article on fuzzy logic and probability.
Embeddings. Texts turned into vectors by a language model can be clustered the same way; the soft assignment then reveals documents that lie between topics.

8. Summary

K-means assigns every point to exactly one cluster and says nothing about the points on the boundary.
Fuzzy c-means looks for memberships u_ij that sum to 1 and centres as weighted means; it alternates two simple steps.
On our data it found the same centres as k-means and also showed that the points M1–M4 belong to two or three clusters at once.
The fuzzifier m controls how soft the partition is; the partition coefficient and the Xie–Beni index help choose the number of clusters.
The sum-to-1 constraint gives outliers high memberships; possibilistic variants fix this.

Want to get hands-on? Have an AI agent run fuzzy c-means on the pixel colours of one of your own photos and colour it by cluster — and look at which pixels lie “between” colours.

Do you see it differently? Write to support@coden-app.com.

Fuzzy clustering: the fuzzy c-means algorithm and points between clusters

1. Hard clustering: k-means

2. Fuzzy c-means

3. Fuzzy c-means on our data

4. The fuzzifier m

5. How many clusters?

6. Where fuzzy c-means fails

7. Fuzzy clustering in practice

8. Summary

An Agent on your computer, driven from your phone