Clustering Analysis in Python¶

Here you can find the Python code for the majority of the examples in Chapter 12. The seeds do not match R, so the toy point clouds will look different.

In [1]:
import numpy as np
import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import linkage, dendrogram
from scipy.spatial.distance import pdist, squareform
from sklearn.cluster import KMeans
from sklearn.neighbors import NearestNeighbors

$K$-means: one iteration on six points¶

In [2]:
rng = np.random.default_rng(3)
x = rng.normal(size=(6, 2))

C = rng.integers(0, 2, size=6)
means = np.vstack([x[C == k].mean(axis=0) for k in (0, 1)])

fig, axes = plt.subplots(1, 3, figsize=(10, 3))
for ax, title, labels, show_means in [
    (axes[0], "data", None, False),
    (axes[1], "random labels + means", C, True),
    (axes[2], None, None, False),
]:
    ax.scatter(x[:, 0], x[:, 1], c="black" if labels is None else labels, s=60)
    if show_means:
        ax.scatter(means[:, 0], means[:, 1], marker="x", s=80, c=["C0", "C1"])
    ax.set_title(title)
    ax.set_xticks([]); ax.set_yticks([])

# reassign each point to the nearest current mean, then recompute means
C_new = np.argmin(((x[:, None, :] - means[None, :, :]) ** 2).sum(axis=2), axis=1)
means_new = np.vstack([x[C_new == k].mean(axis=0) for k in (0, 1)])
axes[2].scatter(x[:, 0], x[:, 1], c=C_new, s=60)
axes[2].scatter(means_new[:, 0], means_new[:, 1], marker="x", s=80, c=["C0", "C1"])
axes[2].set_title("after one reassignment")
axes[2].set_xticks([]); axes[2].set_yticks([])
plt.tight_layout()
No description has been provided for this image

$K$-means: nstart / n_init¶

sklearn uses n_init for R's nstart. inertia_ is tot.withinss.

In [3]:
rng = np.random.default_rng(1)
mat = rng.normal(size=(50, 20))

wss_1 = KMeans(n_clusters=3, n_init=1, random_state=0).fit(mat).inertia_
wss_100 = KMeans(n_clusters=3, n_init=100, random_state=0).fit(mat).inertia_
wss_1, wss_100
Out[3]:
(823.1357223865327, 810.1777966590128)

Hierarchical clustering (complete linkage)¶

In [4]:
rng = np.random.default_rng(3)
x = rng.normal(size=(6, 2))

print(squareform(pdist(x, metric="euclidean")).round(3))

hc = linkage(x, method="complete")
dendrogram(hc, labels=np.arange(1, 7))
plt.title("complete linkage")
plt.tight_layout()
[[0.    2.566 3.42  4.679 6.558 2.854]
 [2.566 0.    0.939 2.461 4.097 0.289]
 [3.42  0.939 0.    1.567 3.563 0.692]
 [4.679 2.461 1.567 0.    3.738 2.249]
 [6.558 4.097 3.563 3.738 0.    3.834]
 [2.854 0.289 0.692 2.249 3.834 0.   ]]
No description has been provided for this image

Spectral clustering: four 1-D Gaussians¶

Unnormalized Laplacian with $w_{ij}=\exp(-\|x_i-x_j\|^2/4)$. NumPy's eigh returns eigenvalues in increasing order, so the smallest four are the first four columns (R's eigen() returns the largest first).

In [5]:
rng = np.random.default_rng(1)
n = 50
x = np.concatenate([
    rng.normal(0, 0.2, n),
    rng.normal(2, 0.2, n),
    rng.normal(4, 0.2, n),
    rng.normal(6, 0.2, n),
])

plt.hist(x, bins=100)
plt.title("four well-separated 1-D Gaussians")
plt.show()

D2 = squareform(pdist(x[:, None])) ** 2
W = np.exp(-D2 / 4)
d = W.sum(axis=1)
L = np.diag(d) - W

plt.imshow(W, origin="upper")
plt.title("RBF adjacency")
plt.colorbar()
plt.show()

evals, evecs = np.linalg.eigh(L)
plt.scatter(np.arange(1, 21), evals[:20], c=["red"] * 4 + ["steelblue"] * 16)
plt.ylabel("eigenvalues")
plt.show()

fig, axes = plt.subplots(1, 4, figsize=(12, 3))
for j, ax in enumerate(axes):
    ax.plot(evecs[:, j])
    ax.set_ylim(-0.15, 0.15)
    ax.set_title(f"eigenvector {j+1}")
plt.tight_layout()
No description has been provided for this image
No description has been provided for this image
No description has been provided for this image
No description has been provided for this image

Spectral clustering: $k$-NN graph and $L_{\mathrm{sym}}$¶

In [6]:
nn = NearestNeighbors(n_neighbors=10).fit(x[:, None])
idx = nn.kneighbors(return_distance=False)

W_knn = np.zeros((200, 200))
for i in range(200):
    W_knn[i, idx[i]] = 1
W_knn = np.maximum(W_knn, W_knn.T)

plt.imshow(W_knn, origin="upper")
plt.title("symmetric 10-NN adjacency")
plt.show()

d = W_knn.sum(axis=1)
dinv_sqrt = np.diag(1.0 / np.sqrt(d))
L_sym = np.eye(200) - dinv_sqrt @ W_knn @ dinv_sqrt

evals, evecs = np.linalg.eigh(L_sym)
plt.scatter(np.arange(1, 21), evals[:20], c=["red"] * 4 + ["steelblue"] * 16)
plt.ylabel("eigenvalues")
plt.show()

fig, axes = plt.subplots(1, 4, figsize=(12, 3))
for j, ax in enumerate(axes):
    ax.plot(evecs[:, j])
    ax.set_ylim(-0.15, 0.15)
    ax.set_title(f"eigenvector {j+1}")
plt.tight_layout()
plt.show()

cl = KMeans(n_clusters=4, n_init=100, random_state=0).fit(evecs[:, :4])
plt.scatter(x, cl.labels_, c=cl.labels_, marker="+")
plt.ylabel("cluster")
plt.xlabel("x")
No description has been provided for this image
No description has been provided for this image
No description has been provided for this image
Out[6]:
Text(0.5, 0, 'x')
No description has been provided for this image