Code
import numpy as np
import scipy as sp
import matplotlib.pyplot as plt
import pandas as pd
import sklearn.datasets as sk_data
from sklearn.cluster import KMeans
import seaborn as snsHierarchical Clustering
Moving away from strict partitions
- Today we will look at a fairly different approach to clustering.
- So far, we have been thinking of clustering as finding a partition of our dataset.
- That is, a set of nonoverlapping clusters, in which each data item is in one cluster.
- However, in many cases, the notion of a strict partition is not as useful.
Example
How Many Clusters?
How many clusters would you say there are here?
Code
X_rand, y_rand = sk_data.make_blobs(
n_samples=[100, 100, 250, 70, 75, 80],
centers = [[1, 2], [1.5, 1], [3, 2], [1.75, 3.25], [2, 4], [2.25, 3.25]],
n_features = 2,
center_box = (-10.0, 10.0),
cluster_std = [.2, .2, .3, .1, .15, .15],
random_state = 0
)
df_rand = pd.DataFrame(np.column_stack([X_rand[:, 0], X_rand[:, 1], y_rand]), columns = ['X', 'Y', 'label'])
df_rand = df_rand.astype({'label': 'int'})
df_rand['label3'] = [{0: 0, 1: 0, 2: 1, 3: 2, 4: 2, 5: 2}[x] for x in df_rand['label']]
df_rand['label4'] = [{0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 3}[x] for x in df_rand['label']]
df_rand['label5'] = [{0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 3}[x] for x in df_rand['label']]
# kmeans = KMeans(init = 'k-means++', n_clusters = 3, n_init = 100)
# df_rand['label'] = kmeans.fit_predict(df_rand[['X', 'Y']])
df_rand.plot('X', 'Y', kind = 'scatter',
colorbar = False, figsize = (6, 6))
plt.axis('square')
plt.axis('off')
plt.show()
Three clusters?
Code
df_rand.plot('X', 'Y', kind = 'scatter', c = 'label3', colormap='viridis',
colorbar = False, figsize = (6, 6))
plt.axis('square')
plt.axis('off')
plt.show()
Four clusters?
Code
df_rand.plot('X', 'Y', kind = 'scatter', c = 'label4', colormap='viridis',
colorbar = False, figsize = (6, 6))
plt.axis('square')
plt.axis('off')
plt.show()
Five clusters?
Code
df_rand.plot('X', 'Y', kind = 'scatter', c = 'label5', colormap='viridis',
colorbar = False, figsize = (6, 6))
plt.axis('square')
plt.axis('off')
plt.show()
Six clusters?
Code
df_rand.plot('X', 'Y', kind = 'scatter', c = 'label', colormap='viridis',
colorbar = False, figsize = (6, 6))
plt.axis('square')
plt.axis('off')
plt.show()
Code
df_rand.plot('X', 'Y', kind = 'scatter', c = 'label', colormap='viridis',
colorbar = False, figsize = (4, 4))
plt.axis('square')
plt.axis('off')
plt.show()
This dataset shows clustering on multiple scales.
To fully capture the structure in this dataset, two things are needed:
- Capturing the differing clusters depending on the scale
- Capturing the containment relations – which clusters lie within other clusters
These observations motivate the notion of hierarchical clustering.
In hierarchical clustering, we move away from the partition notion of \(k\)-means,
and instead capture a more complex arrangement that includes containment of one cluster within another.
Note: GMMs relax the partitioning notion further!
Hierarchical Clustering Example
Hierarchical Clustering Example
Inspired by Hastie & Tibshirani lecture.
Code
import matplotlib.pyplot as plt
import numpy as np
# Create 5 points with labels
points = {
'A': (1.2, 5.2),
'B': (2.7, 4.2),
'C': (2, 6),
'D': (5, 3),
'E': (4, 2)
}
# Create the scatter plot
plt.figure(figsize=(6, 6))
for label, (x, y) in points.items():
plt.scatter(x, y, s=100, alpha=0.7)
plt.annotate(label, (x, y), xytext=(5, 5), textcoords='offset points',
fontsize=12, fontweight='bold')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.title('2D Scatter Plot with 5 Labeled Points')
plt.grid(True, alpha=0.3)
plt.xlim(0, 7)
plt.ylim(0, 7)
plt.show()
- Goal: Combine closest points/clusters into a new cluster
- Use distance metric to define closeness
- So-called bottom-up approach or agglomerative clustering
- Which 2 points are closest?
Example, cont.
Code
import matplotlib.pyplot as plt
import numpy as np
from matplotlib.patches import Ellipse
# Create 5 points with labels (same as before)
points = {
'A': (1.2, 5.2),
'B': (2.7, 4.2),
'C': (2, 6),
'D': (5, 3),
'E': (4, 2)
}
# Create the scatter plot
plt.figure(figsize=(6, 6))
for label, (x, y) in points.items():
plt.scatter(x, y, s=100, alpha=0.7)
plt.annotate(label, (x, y), xytext=(5, 5), textcoords='offset points',
fontsize=12, fontweight='bold')
# Draw an ellipse around points A and C where A and C are the foci
A_x, A_y = points['A']
C_x, C_y = points['C']
# Calculate the distance between foci (A and C)
focal_distance = np.sqrt((C_x - A_x)**2 + (C_y - A_y)**2)
# Calculate center of ellipse (midpoint between foci)
center_x = (A_x + C_x) / 2
center_y = (A_y + C_y) / 2
# Calculate the angle of the major axis
angle = np.degrees(np.arctan2(C_y - A_y, C_x - A_x))
# Set semi-major axis (a) and semi-minor axis (b)
# For an ellipse: c = sqrt(a^2 - b^2) where c is half the focal distance
# We'll set a = focal_distance/2 + padding, then calculate b
a = focal_distance/2 + 0.4 # semi-major axis with padding
c = focal_distance/2 # half the focal distance
b = np.sqrt(a**2 - c**2) # semi-minor axis
# Create and add the ellipse
ellipse = Ellipse((center_x, center_y), 2*a, 2*b, angle=angle,
facecolor='none', edgecolor='red', linewidth=2, linestyle='--')
plt.gca().add_patch(ellipse)
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.title('2D Scatter Plot - First Cluster (A & C)')
plt.grid(True, alpha=0.3)
plt.xlim(0, 7)
plt.ylim(0, 7)
plt.show()
- Now we want to combine either the next closest pair of points or the point closest to a cluster
- How do we measure closeness of points to clusters?
- Or clusters to clusters?
Example, cont. (Part 2)
Code
import matplotlib.pyplot as plt
import numpy as np
from matplotlib.patches import Ellipse
# Create 5 points with labels (same as before)
points = {
'A': (1.2, 5.2),
'B': (2.7, 4.2),
'C': (2, 6),
'D': (5, 3),
'E': (4, 2)
}
# Create the scatter plot
plt.figure(figsize=(6, 6))
for label, (x, y) in points.items():
plt.scatter(x, y, s=100, alpha=0.7)
plt.annotate(label, (x, y), xytext=(5, 5), textcoords='offset points',
fontsize=12, fontweight='bold')
# Draw an ellipse around points A and C where A and C are the foci
A_x, A_y = points['A']
C_x, C_y = points['C']
# Calculate the distance between foci (A and C)
focal_distance = np.sqrt((C_x - A_x)**2 + (C_y - A_y)**2)
# Calculate center of ellipse (midpoint between foci)
center_x = (A_x + C_x) / 2
center_y = (A_y + C_y) / 2
# Calculate the angle of the major axis
angle = np.degrees(np.arctan2(C_y - A_y, C_x - A_x))
# Set semi-major axis (a) and semi-minor axis (b)
# For an ellipse: c = sqrt(a^2 - b^2) where c is half the focal distance
# We'll set a = focal_distance/2 + padding, then calculate b
a = focal_distance/2 + 0.4 # semi-major axis with padding
c = focal_distance/2 # half the focal distance
b = np.sqrt(a**2 - c**2) # semi-minor axis
# Create and add the ellipse for A and C
ellipse1 = Ellipse((center_x, center_y), 2*a, 2*b, angle=angle,
facecolor='none', edgecolor='red', linewidth=2, linestyle='--')
plt.gca().add_patch(ellipse1)
# Draw an ellipse around points E and D where E and D are the foci
E_x, E_y = points['E']
D_x, D_y = points['D']
# Calculate the distance between foci (E and D)
focal_distance_ED = np.sqrt((D_x - E_x)**2 + (D_y - E_y)**2)
# Calculate center of ellipse (midpoint between foci)
center_x_ED = (E_x + D_x) / 2
center_y_ED = (E_y + D_y) / 2
# Calculate the angle of the major axis
angle_ED = np.degrees(np.arctan2(D_y - E_y, D_x - E_x))
# Set semi-major axis (a) and semi-minor axis (b)
a_ED = focal_distance_ED/2 + 0.4 # semi-major axis with padding
c_ED = focal_distance_ED/2 # half the focal distance
b_ED = np.sqrt(a_ED**2 - c_ED**2) # semi-minor axis
# Create and add the ellipse for E and D
ellipse2 = Ellipse((center_x_ED, center_y_ED), 2*a_ED, 2*b_ED, angle=angle_ED,
facecolor='none', edgecolor='blue', linewidth=2, linestyle='--')
plt.gca().add_patch(ellipse2)
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.title('2D Scatter Plot - Two Clusters (A&C, E&D)')
plt.grid(True, alpha=0.3)
plt.xlim(0, 7)
plt.ylim(0, 7)
plt.show()
- Assume D and E are the next closest pair of points
- Now which cluster is B closest to?
Example, cont. (Part 3)
Code
import matplotlib.pyplot as plt
import numpy as np
from matplotlib.patches import Ellipse
# Create 5 points with labels (same as before)
points = {
'A': (1.2, 5.2),
'B': (2.7, 4.2),
'C': (2, 6),
'D': (5, 3),
'E': (4, 2)
}
# Create the scatter plot
plt.figure(figsize=(6, 6))
for label, (x, y) in points.items():
plt.scatter(x, y, s=100, alpha=0.7)
plt.annotate(label, (x, y), xytext=(5, 5), textcoords='offset points',
fontsize=12, fontweight='bold')
# Draw an ellipse around points A and C where A and C are the foci
A_x, A_y = points['A']
C_x, C_y = points['C']
# Calculate the distance between foci (A and C)
focal_distance = np.sqrt((C_x - A_x)**2 + (C_y - A_y)**2)
# Calculate center of ellipse (midpoint between foci)
center_x = (A_x + C_x) / 2
center_y = (A_y + C_y) / 2
# Calculate the angle of the major axis
angle = np.degrees(np.arctan2(C_y - A_y, C_x - A_x))
# Set semi-major axis (a) and semi-minor axis (b)
# For an ellipse: c = sqrt(a^2 - b^2) where c is half the focal distance
# We'll set a = focal_distance/2 + padding, then calculate b
a = focal_distance/2 + 0.4 # semi-major axis with padding
c = focal_distance/2 # half the focal distance
b = np.sqrt(a**2 - c**2) # semi-minor axis
# Create and add the ellipse for A and C
ellipse1 = Ellipse((center_x, center_y), 2*a, 2*b, angle=angle,
facecolor='none', edgecolor='red', linewidth=2, linestyle='--')
plt.gca().add_patch(ellipse1)
# Draw an ellipse around points E and D where E and D are the foci
E_x, E_y = points['E']
D_x, D_y = points['D']
# Calculate the distance between foci (E and D)
focal_distance_ED = np.sqrt((D_x - E_x)**2 + (D_y - E_y)**2)
# Calculate center of ellipse (midpoint between foci)
center_x_ED = (E_x + D_x) / 2
center_y_ED = (E_y + D_y) / 2
# Calculate the angle of the major axis
angle_ED = np.degrees(np.arctan2(D_y - E_y, D_x - E_x))
# Set semi-major axis (a) and semi-minor axis (b)
a_ED = focal_distance_ED/2 + 0.4 # semi-major axis with padding
c_ED = focal_distance_ED/2 # half the focal distance
b_ED = np.sqrt(a_ED**2 - c_ED**2) # semi-minor axis
# Create and add the ellipse for E and D
ellipse2 = Ellipse((center_x_ED, center_y_ED), 2*a_ED, 2*b_ED, angle=angle_ED,
facecolor='none', edgecolor='blue', linewidth=2, linestyle='--')
plt.gca().add_patch(ellipse2)
# Draw a circle around points A, B, and C
A_x, A_y = points['A']
B_x, B_y = points['B']
C_x, C_y = points['C']
# Calculate the center of the circle (centroid of the three points)
center_x_ABC = (A_x + B_x + C_x) / 3
center_y_ABC = (A_y + B_y + C_y) / 3
# Calculate the radius as the maximum distance from center to any of the three points
dist_A = np.sqrt((A_x - center_x_ABC)**2 + (A_y - center_y_ABC)**2)
dist_B = np.sqrt((B_x - center_x_ABC)**2 + (B_y - center_y_ABC)**2)
dist_C = np.sqrt((C_x - center_x_ABC)**2 + (C_y - center_y_ABC)**2)
radius_ABC = max(dist_A, dist_B, dist_C) + 0.3 # Add some padding
# Create and add the circle
circle = plt.Circle((center_x_ABC, center_y_ABC), radius_ABC,
facecolor='none', edgecolor='green', linewidth=2, linestyle='--')
plt.gca().add_patch(circle)
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.title('2D Scatter Plot - Three Clusters')
plt.grid(True, alpha=0.3)
plt.xlim(0, 7)
plt.ylim(0, 7)
plt.show()
- We’ll talk about measuring distances between clusters shortly
- But let’s just say that B is closest to the cluster A, C, E and forms a new cluster
- and then finally…
Example, cont. (Part 4)
Code
import matplotlib.pyplot as plt
import numpy as np
from matplotlib.patches import Ellipse
# Create 5 points with labels (same as before)
points = {
'A': (1.2, 5.2),
'B': (2.7, 4.2),
'C': (2, 6),
'D': (5, 3),
'E': (4, 2)
}
# Create the scatter plot
plt.figure(figsize=(6, 6))
for label, (x, y) in points.items():
plt.scatter(x, y, s=100, alpha=0.7)
plt.annotate(label, (x, y), xytext=(5, 5), textcoords='offset points',
fontsize=12, fontweight='bold')
# Draw an ellipse around points A and C where A and C are the foci
A_x, A_y = points['A']
C_x, C_y = points['C']
# Calculate the distance between foci (A and C)
focal_distance = np.sqrt((C_x - A_x)**2 + (C_y - A_y)**2)
# Calculate center of ellipse (midpoint between foci)
center_x = (A_x + C_x) / 2
center_y = (A_y + C_y) / 2
# Calculate the angle of the major axis
angle = np.degrees(np.arctan2(C_y - A_y, C_x - A_x))
# Set semi-major axis (a) and semi-minor axis (b)
# For an ellipse: c = sqrt(a^2 - b^2) where c is half the focal distance
# We'll set a = focal_distance/2 + padding, then calculate b
a = focal_distance/2 + 0.4 # semi-major axis with padding
c = focal_distance/2 # half the focal distance
b = np.sqrt(a**2 - c**2) # semi-minor axis
# Create and add the ellipse for A and C
ellipse1 = Ellipse((center_x, center_y), 2*a, 2*b, angle=angle,
facecolor='none', edgecolor='red', linewidth=2, linestyle='--')
plt.gca().add_patch(ellipse1)
# Draw an ellipse around points E and D where E and D are the foci
E_x, E_y = points['E']
D_x, D_y = points['D']
# Calculate the distance between foci (E and D)
focal_distance_ED = np.sqrt((D_x - E_x)**2 + (D_y - E_y)**2)
# Calculate center of ellipse (midpoint between foci)
center_x_ED = (E_x + D_x) / 2
center_y_ED = (E_y + D_y) / 2
# Calculate the angle of the major axis
angle_ED = np.degrees(np.arctan2(D_y - E_y, D_x - E_x))
# Set semi-major axis (a) and semi-minor axis (b)
a_ED = focal_distance_ED/2 + 0.4 # semi-major axis with padding
c_ED = focal_distance_ED/2 # half the focal distance
b_ED = np.sqrt(a_ED**2 - c_ED**2) # semi-minor axis
# Create and add the ellipse for E and D
ellipse2 = Ellipse((center_x_ED, center_y_ED), 2*a_ED, 2*b_ED, angle=angle_ED,
facecolor='none', edgecolor='blue', linewidth=2, linestyle='--')
plt.gca().add_patch(ellipse2)
# Draw a circle around points A, B, and C
A_x, A_y = points['A']
B_x, B_y = points['B']
C_x, C_y = points['C']
# Calculate the center of the circle (centroid of the three points)
center_x_ABC = (A_x + B_x + C_x) / 3
center_y_ABC = (A_y + B_y + C_y) / 3
# Calculate the radius as the maximum distance from center to any of the three points
dist_A = np.sqrt((A_x - center_x_ABC)**2 + (A_y - center_y_ABC)**2)
dist_B = np.sqrt((B_x - center_x_ABC)**2 + (B_y - center_y_ABC)**2)
dist_C = np.sqrt((C_x - center_x_ABC)**2 + (C_y - center_y_ABC)**2)
radius_ABC = max(dist_A, dist_B, dist_C) + 0.3 # Add some padding
# Create and add the circle
circle = plt.Circle((center_x_ABC, center_y_ABC), radius_ABC,
facecolor='none', edgecolor='green', linewidth=2, linestyle='--')
plt.gca().add_patch(circle)
# Draw an ellipse around all 5 points
all_x = [points[label][0] for label in points.keys()]
all_y = [points[label][1] for label in points.keys()]
# Calculate center of ellipse (centroid of all points)
center_x_all = np.mean(all_x)
center_y_all = np.mean(all_y)
width_all, height_all = 3.2, 7
angle_all = 40
print(width_all, height_all, angle_all, center_x_all, center_y_all)
# Create and add the ellipse around all points
ellipse_all = Ellipse((center_x_all, center_y_all), width_all, height_all, angle=angle_all,
facecolor='none', edgecolor='purple', linewidth=3, linestyle='-')
plt.gca().add_patch(ellipse_all)
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.title('2D Scatter Plot - Final Cluster (All Points)')
plt.grid(True, alpha=0.3)
plt.xlim(0, 7)
plt.ylim(0, 7)
plt.show()3.2 7 40 2.98 4.08
- We combine all points into a single cluster
Example: Dendrogram
Code
import matplotlib.pyplot as plt
import numpy as np
from matplotlib.patches import Ellipse
from scipy.cluster.hierarchy import dendrogram, linkage
from scipy.spatial.distance import pdist
# Create 5 points with labels (same as before)
points = {
'A': (1.2, 5.2),
'B': (2.7, 4.2),
'C': (2, 6),
'D': (5, 3),
'E': (4, 2)
}
# Create figure with two subplots
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12, 6))
# First subplot: Scatter plot with clusters
for label, (x, y) in points.items():
ax1.scatter(x, y, s=100, alpha=0.7)
ax1.annotate(label, (x, y), xytext=(5, 5), textcoords='offset points',
fontsize=12, fontweight='bold')
# Draw an ellipse around points A and C where A and C are the foci
A_x, A_y = points['A']
C_x, C_y = points['C']
# Calculate the distance between foci (A and C)
focal_distance = np.sqrt((C_x - A_x)**2 + (C_y - A_y)**2)
# Calculate center of ellipse (midpoint between foci)
center_x = (A_x + C_x) / 2
center_y = (A_y + C_y) / 2
# Calculate the angle of the major axis
angle = np.degrees(np.arctan2(C_y - A_y, C_x - A_x))
# Set semi-major axis (a) and semi-minor axis (b)
a = focal_distance/2 + 0.4 # semi-major axis with padding
c = focal_distance/2 # half the focal distance
b = np.sqrt(a**2 - c**2) # semi-minor axis
# Create and add the ellipse for A and C
ellipse1 = Ellipse((center_x, center_y), 2*a, 2*b, angle=angle,
facecolor='none', edgecolor='red', linewidth=2, linestyle='--')
ax1.add_patch(ellipse1)
# Draw an ellipse around points E and D where E and D are the foci
E_x, E_y = points['E']
D_x, D_y = points['D']
# Calculate the distance between foci (E and D)
focal_distance_ED = np.sqrt((D_x - E_x)**2 + (D_y - E_y)**2)
# Calculate center of ellipse (midpoint between foci)
center_x_ED = (E_x + D_x) / 2
center_y_ED = (E_y + D_y) / 2
# Calculate the angle of the major axis
angle_ED = np.degrees(np.arctan2(D_y - E_y, D_x - E_x))
# Set semi-major axis (a) and semi-minor axis (b)
a_ED = focal_distance_ED/2 + 0.4 # semi-major axis with padding
c_ED = focal_distance_ED/2 # half the focal distance
b_ED = np.sqrt(a_ED**2 - c_ED**2) # semi-minor axis
# Create and add the ellipse for E and D
ellipse2 = Ellipse((center_x_ED, center_y_ED), 2*a_ED, 2*b_ED, angle=angle_ED,
facecolor='none', edgecolor='blue', linewidth=2, linestyle='--')
ax1.add_patch(ellipse2)
# Draw a circle around points A, B, and C
A_x, A_y = points['A']
B_x, B_y = points['B']
C_x, C_y = points['C']
# Calculate the center of the circle (centroid of the three points)
center_x_ABC = (A_x + B_x + C_x) / 3
center_y_ABC = (A_y + B_y + C_y) / 3
# Calculate the radius as the maximum distance from center to any of the three points
dist_A = np.sqrt((A_x - center_x_ABC)**2 + (A_y - center_y_ABC)**2)
dist_B = np.sqrt((B_x - center_x_ABC)**2 + (B_y - center_y_ABC)**2)
dist_C = np.sqrt((C_x - center_x_ABC)**2 + (C_y - center_y_ABC)**2)
radius_ABC = max(dist_A, dist_B, dist_C) + 0.3 # Add some padding
# Create and add the circle
circle = plt.Circle((center_x_ABC, center_y_ABC), radius_ABC,
facecolor='none', edgecolor='green', linewidth=2, linestyle='--')
ax1.add_patch(circle)
# Draw an ellipse around all 5 points
all_x = [points[label][0] for label in points.keys()]
all_y = [points[label][1] for label in points.keys()]
# Calculate center of ellipse (centroid of all points)
center_x_all = np.mean(all_x)
center_y_all = np.mean(all_y)
width_all, height_all = 3.2, 7
angle_all = 40
# Create and add the ellipse around all points
ellipse_all = Ellipse((center_x_all, center_y_all), width_all, height_all, angle=angle_all,
facecolor='none', edgecolor='purple', linewidth=3, linestyle='-')
ax1.add_patch(ellipse_all)
ax1.set_xlabel('Feature 1')
ax1.set_ylabel('Feature 2')
ax1.set_title('Clusters at Different Levels')
ax1.grid(True, alpha=0.3)
ax1.set_xlim(0, 7)
ax1.set_ylim(0, 7)
# Second subplot: Dendrogram
# Prepare data for hierarchical clustering
points_array = np.array(list(points.values()))
point_labels = list(points.keys())
# Calculate linkage matrix
linkage_matrix = linkage(points_array, method='ward')
# Create dendrogram
dendrogram(linkage_matrix, labels=point_labels, ax=ax2,
leaf_rotation=0, leaf_font_size=12)
ax2.set_title('Hierarchical Clustering Dendrogram')
ax2.set_xlabel('Points')
ax2.set_ylabel('Distance')
plt.tight_layout()
plt.show()
Example: Dendrogram Explained
Code
import matplotlib.pyplot as plt
import numpy as np
from matplotlib.patches import Ellipse
from scipy.cluster.hierarchy import dendrogram, linkage
from scipy.spatial.distance import pdist
# Create 5 points with labels (same as before)
points = {
'A': (1.2, 5.2),
'B': (2.7, 4.2),
'C': (2, 6),
'D': (5, 3),
'E': (4, 2)
}
# Create figure with two subplots
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(6, 3))
# First subplot: Scatter plot with clusters
for label, (x, y) in points.items():
ax1.scatter(x, y, s=100, alpha=0.7)
ax1.annotate(label, (x, y), xytext=(5, 5), textcoords='offset points',
fontsize=12, fontweight='bold')
# Draw an ellipse around points A and C where A and C are the foci
A_x, A_y = points['A']
C_x, C_y = points['C']
# Calculate the distance between foci (A and C)
focal_distance = np.sqrt((C_x - A_x)**2 + (C_y - A_y)**2)
# Calculate center of ellipse (midpoint between foci)
center_x = (A_x + C_x) / 2
center_y = (A_y + C_y) / 2
# Calculate the angle of the major axis
angle = np.degrees(np.arctan2(C_y - A_y, C_x - A_x))
# Set semi-major axis (a) and semi-minor axis (b)
a = focal_distance/2 + 0.4 # semi-major axis with padding
c = focal_distance/2 # half the focal distance
b = np.sqrt(a**2 - c**2) # semi-minor axis
# Create and add the ellipse for A and C
ellipse1 = Ellipse((center_x, center_y), 2*a, 2*b, angle=angle,
facecolor='none', edgecolor='red', linewidth=2, linestyle='--')
ax1.add_patch(ellipse1)
# Draw an ellipse around points E and D where E and D are the foci
E_x, E_y = points['E']
D_x, D_y = points['D']
# Calculate the distance between foci (E and D)
focal_distance_ED = np.sqrt((D_x - E_x)**2 + (D_y - E_y)**2)
# Calculate center of ellipse (midpoint between foci)
center_x_ED = (E_x + D_x) / 2
center_y_ED = (E_y + D_y) / 2
# Calculate the angle of the major axis
angle_ED = np.degrees(np.arctan2(D_y - E_y, D_x - E_x))
# Set semi-major axis (a) and semi-minor axis (b)
a_ED = focal_distance_ED/2 + 0.4 # semi-major axis with padding
c_ED = focal_distance_ED/2 # half the focal distance
b_ED = np.sqrt(a_ED**2 - c_ED**2) # semi-minor axis
# Create and add the ellipse for E and D
ellipse2 = Ellipse((center_x_ED, center_y_ED), 2*a_ED, 2*b_ED, angle=angle_ED,
facecolor='none', edgecolor='blue', linewidth=2, linestyle='--')
ax1.add_patch(ellipse2)
# Draw a circle around points A, B, and C
A_x, A_y = points['A']
B_x, B_y = points['B']
C_x, C_y = points['C']
# Calculate the center of the circle (centroid of the three points)
center_x_ABC = (A_x + B_x + C_x) / 3
center_y_ABC = (A_y + B_y + C_y) / 3
# Calculate the radius as the maximum distance from center to any of the three points
dist_A = np.sqrt((A_x - center_x_ABC)**2 + (A_y - center_y_ABC)**2)
dist_B = np.sqrt((B_x - center_x_ABC)**2 + (B_y - center_y_ABC)**2)
dist_C = np.sqrt((C_x - center_x_ABC)**2 + (C_y - center_y_ABC)**2)
radius_ABC = max(dist_A, dist_B, dist_C) + 0.3 # Add some padding
# Create and add the circle
circle = plt.Circle((center_x_ABC, center_y_ABC), radius_ABC,
facecolor='none', edgecolor='green', linewidth=2, linestyle='--')
ax1.add_patch(circle)
# Draw an ellipse around all 5 points
all_x = [points[label][0] for label in points.keys()]
all_y = [points[label][1] for label in points.keys()]
# Calculate center of ellipse (centroid of all points)
center_x_all = np.mean(all_x)
center_y_all = np.mean(all_y)
width_all, height_all = 3.2, 7
angle_all = 40
# Create and add the ellipse around all points
ellipse_all = Ellipse((center_x_all, center_y_all), width_all, height_all, angle=angle_all,
facecolor='none', edgecolor='purple', linewidth=3, linestyle='-')
ax1.add_patch(ellipse_all)
ax1.set_xlabel('Feature 1')
ax1.set_ylabel('Feature 2')
ax1.set_title('Clusters at Different Levels')
ax1.grid(True, alpha=0.3)
ax1.set_xlim(0, 7)
ax1.set_ylim(0, 7)
# Second subplot: Dendrogram
# Prepare data for hierarchical clustering
points_array = np.array(list(points.values()))
point_labels = list(points.keys())
# Calculate linkage matrix
linkage_matrix = linkage(points_array, method='ward')
# Create dendrogram
dendrogram(linkage_matrix, labels=point_labels, ax=ax2,
leaf_rotation=0, leaf_font_size=12)
ax2.set_title('Hierarchical Clustering Dendrogram')
ax2.set_xlabel('Points')
ax2.set_ylabel('Distance')
plt.tight_layout()
plt.show()
- In the dendrogram, the vertical axis is the distance between the clusters
- The horizontal axis is the points
- The clusters are merged from the bottom up
Example: Dendrogram cont.
Code
import matplotlib.pyplot as plt
import numpy as np
from matplotlib.patches import Ellipse
from scipy.cluster.hierarchy import dendrogram, linkage
from scipy.spatial.distance import pdist
# Create 5 points with labels (same as before)
points = {
'A': (1.2, 5.2),
'B': (2.7, 4.2),
'C': (2, 6),
'D': (5, 3),
'E': (4, 2)
}
# Create figure with two subplots
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(6, 3))
# First subplot: Scatter plot with clusters
for label, (x, y) in points.items():
ax1.scatter(x, y, s=100, alpha=0.7)
ax1.annotate(label, (x, y), xytext=(5, 5), textcoords='offset points',
fontsize=12, fontweight='bold')
# Draw an ellipse around points A and C where A and C are the foci
A_x, A_y = points['A']
C_x, C_y = points['C']
# Calculate the distance between foci (A and C)
focal_distance = np.sqrt((C_x - A_x)**2 + (C_y - A_y)**2)
# Calculate center of ellipse (midpoint between foci)
center_x = (A_x + C_x) / 2
center_y = (A_y + C_y) / 2
# Calculate the angle of the major axis
angle = np.degrees(np.arctan2(C_y - A_y, C_x - A_x))
# Set semi-major axis (a) and semi-minor axis (b)
a = focal_distance/2 + 0.4 # semi-major axis with padding
c = focal_distance/2 # half the focal distance
b = np.sqrt(a**2 - c**2) # semi-minor axis
# Create and add the ellipse for A and C
ellipse1 = Ellipse((center_x, center_y), 2*a, 2*b, angle=angle,
facecolor='none', edgecolor='red', linewidth=2, linestyle='--')
ax1.add_patch(ellipse1)
# Draw an ellipse around points E and D where E and D are the foci
E_x, E_y = points['E']
D_x, D_y = points['D']
# Calculate the distance between foci (E and D)
focal_distance_ED = np.sqrt((D_x - E_x)**2 + (D_y - E_y)**2)
# Calculate center of ellipse (midpoint between foci)
center_x_ED = (E_x + D_x) / 2
center_y_ED = (E_y + D_y) / 2
# Calculate the angle of the major axis
angle_ED = np.degrees(np.arctan2(D_y - E_y, D_x - E_x))
# Set semi-major axis (a) and semi-minor axis (b)
a_ED = focal_distance_ED/2 + 0.4 # semi-major axis with padding
c_ED = focal_distance_ED/2 # half the focal distance
b_ED = np.sqrt(a_ED**2 - c_ED**2) # semi-minor axis
# Create and add the ellipse for E and D
ellipse2 = Ellipse((center_x_ED, center_y_ED), 2*a_ED, 2*b_ED, angle=angle_ED,
facecolor='none', edgecolor='blue', linewidth=2, linestyle='--')
ax1.add_patch(ellipse2)
# Draw a circle around points A, B, and C
A_x, A_y = points['A']
B_x, B_y = points['B']
C_x, C_y = points['C']
# Calculate the center of the circle (centroid of the three points)
center_x_ABC = (A_x + B_x + C_x) / 3
center_y_ABC = (A_y + B_y + C_y) / 3
# Calculate the radius as the maximum distance from center to any of the three points
dist_A = np.sqrt((A_x - center_x_ABC)**2 + (A_y - center_y_ABC)**2)
dist_B = np.sqrt((B_x - center_x_ABC)**2 + (B_y - center_y_ABC)**2)
dist_C = np.sqrt((C_x - center_x_ABC)**2 + (C_y - center_y_ABC)**2)
radius_ABC = max(dist_A, dist_B, dist_C) + 0.3 # Add some padding
# Create and add the circle
circle = plt.Circle((center_x_ABC, center_y_ABC), radius_ABC,
facecolor='none', edgecolor='green', linewidth=2, linestyle='--')
ax1.add_patch(circle)
# Draw an ellipse around all 5 points
all_x = [points[label][0] for label in points.keys()]
all_y = [points[label][1] for label in points.keys()]
# Calculate center of ellipse (centroid of all points)
center_x_all = np.mean(all_x)
center_y_all = np.mean(all_y)
width_all, height_all = 3.2, 7
angle_all = 40
# Create and add the ellipse around all points
ellipse_all = Ellipse((center_x_all, center_y_all), width_all, height_all, angle=angle_all,
facecolor='none', edgecolor='purple', linewidth=3, linestyle='-')
ax1.add_patch(ellipse_all)
ax1.set_xlabel('Feature 1')
ax1.set_ylabel('Feature 2')
ax1.set_title('Clusters at Different Levels')
ax1.grid(True, alpha=0.3)
ax1.set_xlim(0, 7)
ax1.set_ylim(0, 7)
# Second subplot: Dendrogram
# Prepare data for hierarchical clustering
points_array = np.array(list(points.values()))
point_labels = list(points.keys())
# Calculate linkage matrix
linkage_matrix = linkage(points_array, method='ward')
# Create dendrogram
dendrogram(linkage_matrix, labels=point_labels, ax=ax2,
leaf_rotation=0, leaf_font_size=12)
ax2.set_title('Dendrogram with Splits')
ax2.set_xlabel('Points')
ax2.set_ylabel('Distance')
# Add horizontal dashed red line at y=4 to show split level
ax2.axhline(y=4, color='red', linestyle='--', linewidth=2, alpha=0.8)
plt.tight_layout()
# Save the plot as a png image (uncomment to save)
# plt.savefig('figs/L08-dendrogram.png')
plt.show()
- We can now split the dendrogram at a certain level to get a clustering
Hierarchical Clustering
A hierarchical clustering produces a set of nested clusters organized into a tree.
A hierarchical clustering is visualized using a dendrogram
- A tree-like diagram that records the containment relations among clusters.
Strengths of Hierarchical Clustering
Hierarchical clustering has a number of advantages:
- Encodes many different clusterings.
- It does not itself decide on the correct number of clusters.
- A clustering is obtained by “cutting” the dendrogram at some level.
- You can make this crucial decision yourself, by inspecting the dendrogram.
- You can obtain a (somewhat) arbitrary number of clusters.
Another advantage
Another advantage is that the dendrogram may itself correspond to a meaningful structure, for example, a taxonomy.
Yet another advantage
- Many hierarchical clustering methods can be performed using either similarity (proximity) or dissimilarity (distance) metrics.
- This can be very helpful!
- Techniques like \(k\)-means rely on a specific way of measuring similarity or distance between data points.
Compared to \(k\)-means
Another aspect of hierachical clustering is that it can handle certain cases better than \(k\)-means.
Because of the nature of the \(k\)-means algorithm, \(k\)-means tends to produce:
- Roughly spherical clusters
- Clusters of approximately equal size
- Non-overlapping clusters
In many real-world situations, clusters may not be round, they may be of unequal size, and they may overlap.
Hence we would like clustering algorithms that can work in those cases also.
In-Class Exercise
Create a hierarchical cluster and dendogram for this data.
Code
import matplotlib.pyplot as plt
import numpy as np
from matplotlib.patches import Ellipse
from scipy.cluster.hierarchy import dendrogram, linkage
from scipy.spatial.distance import pdist
# Create 5 points with labels (same as before)
points = {
'A': (3.4, 6.1),
'B': (1.8, 2.3),
'C': (4.6, 4.9),
'D': (1.6, 5.6),
'E': (2.9, 1.7)
}
# Create figure with two subplots
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(10, 5))
# First subplot: Scatter plot with clusters
for label, (x, y) in points.items():
ax1.scatter(x, y, s=100, alpha=0.7)
ax1.annotate(label, (x, y), xytext=(5, 5), textcoords='offset points',
fontsize=12, fontweight='bold')
ax1.set_xlabel('Feature 1')
ax1.set_ylabel('Feature 2')
ax1.set_title('Clusters at Different Levels')
ax1.grid(True, alpha=0.3)
ax1.set_xlim(0, 7)
ax1.set_ylim(0, 7)
# Create empty axis with 5 evenly spaced ticks
ax2.set_xlim(0, 4)
ax2.set_ylim(0, 1)
ax2.set_xticks([0, 1, 2, 3, 4])
ax2.set_xticklabels([])
ax2.set_yticks([0, 0.25, 0.5, 0.75, 1])
ax2.set_yticklabels([])
ax2.set_title('Dendogram')
ax2.set_xlabel('Points')
ax2.set_ylabel('Distance')
plt.tight_layout()
# Save the plot as a png image (uncomment to save)
# plt.savefig('figs/L08-dendrogram.png')
plt.show()
Hierarchical Clustering Algorithms
Hierarchical Clustering Algorithms
There are two main approaches to hierarchical clustering: “bottom-up” and “top-down.”
Agglomerative Clustering (“bottom-up”):
- Start by defining each point as its own cluster
- At each successive step, merge the two clusters that are closest to each other
- Repeat until only one cluster is left.
Divisive Clustering (“top-down”):
- Start with one, all-inclusive cluster
- At each step, find the cluster split that creates the largest distance between resulting clusters
- Repeat until each point is in its own cluster.
Some key points
- Agglomerative techniques are by far the more common.
- The key to both of these methods is defining the distance between two clusters.
- Different definitions for the inter-cluster distance yield different clusterings.
To illustrate the impact of the choice of cluster distances, we’ll focus on agglomerative clustering.
Hierarchical Clustering Algorithm Inputs
- Input data as either
- 2-D sample/feature matrix
- 1D condensed distance matrix – upper triangular of pairwise distance matrix flattened
- The cluster linkage method (single, complete, average, ward, …)
- The distance metric (Euclidean, manhattan, Jaccard, …)
Hierarchical Clustering Algorithm Output
An \((n-1,4)\) shaped linkage matrix.
Where each row is [idx1, idx2, dist, sample_count] is a single step in the clustering process and
idx1 and idx2 are indices of the cluster being merged, where
- indices \(\{ 0...n-1 \}\) refer to the original data points and
- indices \(\{n, n+1, ...\}\) refer to each new cluster created
And sample_count is the number of original data samples in the new cluster.
Linkage Matrix Example
Let’s calculate and display the linkage matrix for our 5 data points A-E:
Code
# Create 5 points with labels (same as before)
points = {
'A': (1.2, 5.2),
'B': (2.7, 4.2),
'C': (2, 6),
'D': (5, 3),
'E': (4, 2)
}
# Prepare data for hierarchical clustering
points_array = np.array(list(points.values()))
point_labels = list(points.keys())
# Calculate linkage matrix using Ward's method
linkage_matrix = linkage(points_array, method='ward')
print("Linkage Matrix for 5 data points A-E:")
print("Format: [idx1, idx2, distance, sample_count]")
print("=" * 50)
print(linkage_matrix)
print("=" * 50)
# Display with labels for better understanding
print("\nInterpretation:")
print(f"Row 0: Merge points 0 and 2 (A and C) at distance {linkage_matrix[0,2]:.2f}")
print(f"Row 1: Merge points 3 and 4 (D and E) at distance {linkage_matrix[1,2]:.2f}")
print(f"Row 2: Merge point 1 (B) with cluster 5 (A&C) at distance {linkage_matrix[2,2]:.2f}")
print(f"Row 3: Merge cluster 6 (A&B&C) with cluster 7 (D&E) at distance {linkage_matrix[3,2]:.2f}")Linkage Matrix for 5 data points A-E:
Format: [idx1, idx2, distance, sample_count]
==================================================
[[0. 2. 1.13137085 2. ]
[3. 4. 1.41421356 2. ]
[1. 5. 2.05588586 3. ]
[6. 7. 5.66085977 5. ]]
==================================================
Interpretation:
Row 0: Merge points 0 and 2 (A and C) at distance 1.13
Row 1: Merge points 3 and 4 (D and E) at distance 1.41
Row 2: Merge point 1 (B) with cluster 5 (A&C) at distance 2.06
Row 3: Merge cluster 6 (A&B&C) with cluster 7 (D&E) at distance 5.66
Hierarchical Clustering Algorithm Explained
- Initialization
- Start with each data point as its own cluster.
- Calculate the distance matrix if not provided
- Iterative Clustering
- At each step, the two closest clusters (according to linkage method and distance metric) are merged into a new cluster.
- The distance between new cluster and the remaining clusters is added
- Repeat previous two steps until only one cluster remains.
Defining Cluster Proximity
Given two clusters, how do we define the distance between them?
Here are three natural ways to do it.
Cluster Proximity – Single-Linkage
Single-Linkage: the distance between two clusters is the distance between the closest two points that are in different clusters.
\[ D_\text{single}(i,j) = \min_{x, y}\{d(x, y) \,|\, x \in C_i, y \in C_j\} \]
Cluster Proximity – Complete-Linkage
Complete-Linkage: the distance between two clusters is the distance between the farthest two points that are in different clusters.
\[ D_\text{complete}(i,j) = \max_{x, y}\{d(x, y) \,|\, x \in C_i, y \in C_j\} \]
Cluster Proximity – Average-Linkage
Average-Linkage: the distance between two clusters is the average distance between all pairs of points from different clusters.
\[ D_\text{average}(i,j) = \frac{1}{|C_i|\cdot|C_j|}\sum_{x \in C_i,\, y \in C_j}d(x, y) \]
Cluster Proximity Example
Notice that it is easy to express the definitions above in terms of similarity instead of distance.
Here is a set of 6 points that we will cluster to show differences between distance metrics.
Code
plt.figure(figsize=(6,4))
pt_x = [0.4, 0.22, 0.35, 0.26, 0.08, 0.45]
pt_y = [0.53, 0.38, 0.32, 0.19, 0.41, 0.30]
plt.plot(pt_x, pt_y, 'o', markersize = 10, color = 'k')
plt.ylim([.15, .60])
plt.xlim([0.05, 0.70])
for i in range(6):
plt.annotate(f'{i}', (pt_x[i]+0.02, pt_y[i]-0.01), fontsize = 12)
plt.axis('on')
plt.xticks([])
plt.yticks([])
plt.show()
We can calculate the distance matrix
Code
X = np.array([pt_x, pt_y]).T
from scipy.spatial import distance_matrix
labels = ['p0', 'p1', 'p2', 'p3', 'p4', 'p5']
D = pd.DataFrame(distance_matrix(X, X), index = labels, columns = labels)
D.style.format('{:.2f}')| p0 | p1 | p2 | p3 | p4 | p5 | |
|---|---|---|---|---|---|---|
| p0 | 0.00 | 0.23 | 0.22 | 0.37 | 0.34 | 0.24 |
| p1 | 0.23 | 0.00 | 0.14 | 0.19 | 0.14 | 0.24 |
| p2 | 0.22 | 0.14 | 0.00 | 0.16 | 0.28 | 0.10 |
| p3 | 0.37 | 0.19 | 0.16 | 0.00 | 0.28 | 0.22 |
| p4 | 0.34 | 0.14 | 0.28 | 0.28 | 0.00 | 0.39 |
| p5 | 0.24 | 0.24 | 0.10 | 0.22 | 0.39 | 0.00 |
Single-Linkage Clustering
Code
import scipy.cluster
import scipy.cluster.hierarchy as hierarchy
Z = hierarchy.linkage(X, method='single', metric='euclidean')
hierarchy.dendrogram(Z)
plt.show()
Single Linkage Clustering Advantages
Single-linkage clustering can handle non-elliptical shapes.
Here we use SciPy’s fcluster to form flat custers from hierarchical clustering.
Code
X_moon_05, y_moon_05 = sk_data.make_moons(random_state = 0, noise = 0.05)
Z = hierarchy.linkage(X_moon_05, method='single')
labels = hierarchy.fcluster(Z, 2, criterion = 'maxclust')
plt.scatter(X_moon_05[:, 0], X_moon_05[:, 1], c = [['b','g'][i-1] for i in labels])
plt.axis('off')
plt.show()
Single-Linkage can find different sized clusters:
Code
X_rand_lo, y_rand_lo = sk_data.make_blobs(n_samples=[20, 200], centers = [[1, 1], [3, 1]], n_features = 2,
center_box = (-10.0, 10.0), cluster_std = [.1, .5], random_state = 0)
Z = hierarchy.linkage(X_rand_lo, method='single')
labels = hierarchy.fcluster(Z, 2, criterion = 'maxclust')
plt.scatter(X_rand_lo[:, 0], X_rand_lo[:, 1], c = [['b','g'][i-1] for i in labels])
# plt.title('Single-Linkage Can Find Different-Sized Clusters')
plt.axis('off')
plt.show()
Single Linkage Disadvantages
Single-linkage clustering can be sensitive to noise and outliers.
The results can change drastically on even slightly more noisy data.
Code
X_moon_10, y_moon_10 = sk_data.make_moons(random_state = 0, noise = 0.1)
Z = hierarchy.linkage(X_moon_10, method='single')
labels = hierarchy.fcluster(Z, 2, criterion = 'maxclust')
plt.scatter(X_moon_10[:, 0], X_moon_10[:, 1], c = [['b','g'][i-1] for i in labels])
# plt.title('Single-Linkage Clustering Changes Drastically on Slightly More Noisy Data')
plt.axis('off')
plt.show()
And here’s another example where we bump the standard deviation on the clusters slightly.
Code
X_rand_hi, y_rand_hi = sk_data.make_blobs(n_samples=[20, 200], centers = [[1, 1], [3, 1]], n_features = 2,
center_box = (-10.0, 10.0), cluster_std = [.15, .6], random_state = 0)
Z = hierarchy.linkage(X_rand_hi, method='single')
labels = hierarchy.fcluster(Z, 2, criterion = 'maxclust')
plt.scatter(X_rand_hi[:, 0], X_rand_hi[:, 1], c = [['b','g'][i-1] for i in labels])
plt.axis('off')
plt.show()
Complete-Linkage Clustering
Code
Z = hierarchy.linkage(X, method='complete')
hierarchy.dendrogram(Z)
plt.show()
Complete-Linkage Clustering Advantages
Produces more-balanced clusters – more-equal diameters
Code
X_moon_05, y_moon_05 = sk_data.make_moons(random_state = 0, noise = 0.05)
Z = hierarchy.linkage(X_moon_05, method='complete')
labels = hierarchy.fcluster(Z, 2, criterion = 'maxclust')
plt.scatter(X_moon_05[:, 0], X_moon_05[:, 1], c = [['b','g'][i-1] for i in labels])
plt.axis('off')
plt.show()
Code
Z = hierarchy.linkage(X_rand_hi, method='complete')
labels = hierarchy.fcluster(Z, 2, criterion = 'maxclust')
plt.scatter(X_rand_hi[:, 0], X_rand_hi[:, 1], c = [['b','g'][i-1] for i in labels])
plt.axis('off')
plt.show()
Less susceptible to noise:
Code
Z = hierarchy.linkage(X_moon_10, method='complete')
labels = hierarchy.fcluster(Z, 2, criterion = 'maxclust')
plt.scatter(X_moon_10[:, 0], X_moon_10[:, 1], c = [['b','g'][i-1] for i in labels])
plt.axis('off')
plt.show()
Complete-Linkage Clustering Disadvantages
Some disadvantages for complete-linkage clustering are:
- Sensitivity to outliers
- Tendency to compute more compact, spherical clusters
- Computationally intensive for large datasets.
Average-Linkage Clustering
Code
Z = hierarchy.linkage(X, method='average')
hierarchy.dendrogram(Z)
plt.show()
Average-Linkage Clustering Strengths and Limitations
Average-Linkage clustering is in some sense a compromise between Single-linkage and Complete-linkage clustering.
Strengths:
- Less susceptible to noise and outliers
Limitations:
- Biased toward elliptical clusters
Average-Linkage Clustering Strengths and Limitations, cont.
Produces more isotropic clusters.
Code
Z = hierarchy.linkage(X_moon_10, method='average')
labels = hierarchy.fcluster(Z, 2, criterion = 'maxclust')
plt.scatter(X_moon_10[:, 0], X_moon_10[:, 1], c = [['b','g'][i-1] for i in labels])
plt.axis('off')
plt.show()
Average-Linkage Clustering Strengths and Limitations, cont.
More resistant to noise than Single-Linkage.
Code
Z = hierarchy.linkage(X_rand_hi, method='average')
labels = hierarchy.fcluster(Z, 2, criterion = 'maxclust')
plt.scatter(X_rand_hi[:, 0], X_rand_hi[:, 1], c = [['b','g'][i-1] for i in labels])
plt.axis('off')
plt.show()
All Three Compared
Ward’s Distance
Finally, we consider one more cluster distance.
Ward’s distance asks “What if we combined these two clusters – how would clustering improve?”
To define “how would clustering improve?” we appeal to the \(k\)-means criterion.
So:
Ward’s Distance between clusters \(C_i\) and \(C_j\) is the difference between the total within cluster sum of squares for the two clusters separately, compared to the within cluster sum of squares resulting from merging the two clusters into a new cluster \(C_{i+j}\):
\[ D_\text{Ward}(i, j) = \sum_{x \in C_i} (x - c_i)^2 + \sum_{x \in C_j} (x - c_j)^2 - \sum_{x \in C_{i+j}} (x - c_{i+j})^2 \]
where \(c_i, c_j, c_{i+j}\) are the corresponding cluster centroids.
Ward’s Distance continued
In a sense, this cluster distance results in a hierarchical analog of \(k\)-means.
As a result, it has properties similar to \(k\)-means:
- Less susceptible to noise and outliers
- Biased toward elliptical clusters
Hence it tends to behave more like average-linkage hierarchical clustering.
Hierarchical Clustering in Practice
In Practice
Now we’ll look at doing hierarchical clustering in practice.
We’ll use 1/10th of the synthetic data set from the beginning of this lecture.
scipy has a comprehensive set of clustering tools.
Code
X, y = sk_data.make_blobs(
n_samples=[10, 10, 25, 7, 7, 8],
centers = [[1, 2], [1.5, 1], [3, 2], [1.75, 3.25], [2, 4], [2.25, 3.25]],
n_features = 2,
center_box = (-10.0, 10.0),
cluster_std = [.2, .2, .3, .1, .15, .15],
random_state = 0
)
df_rand = pd.DataFrame(np.column_stack([X[:, 0], X[:, 1], y]), columns = ['X', 'Y', 'label'])
df_rand.plot('X', 'Y', kind = 'scatter',
colorbar = False, figsize = (5, 5))
plt.axis('square')
plt.axis('off')
plt.show()
In Practice, cont.
Let’s run hierarchical clustering on our synthetic dataset.
Try the other linkage methods and see how the clustering and dendrogram changes.
# linkages = ['single','complete','average','weighted','ward']
Z = hierarchy.linkage(X, method = 'single')And draw the dendrogram.
Code
R = hierarchy.dendrogram(Z)
Hierarchical Clustering – Newsgroups
Once again we’ll use the “20 Newsgroup” data provided as example data in sklearn. Experiment with different metrics.
Load three of the newsgroups.
Code
from sklearn.datasets import fetch_20newsgroups
categories = ['comp.os.ms-windows.misc', 'sci.space','rec.sport.baseball']
news_data = fetch_20newsgroups(subset = 'train', categories = categories)Vectorize the data.
Code
from sklearn.feature_extraction.text import TfidfVectorizer
vectorizer = TfidfVectorizer(stop_words='english', min_df = 4, max_df = 0.8)
data = vectorizer.fit_transform(news_data.data).todense()
data.shape(1781, 9409)Code
# linkages are one of 'single','complete','average','weighted','ward'
#
# metrics can be ‘braycurtis’, ‘canberra’, ‘chebyshev’, ‘cityblock’, ‘correlation’, ‘cosine’,
# ‘dice’, ‘euclidean’, ‘hamming’, ‘jaccard’, ‘kulsinski’, ‘mahalanobis’, ‘matching’,
# ‘minkowski’, ‘rogerstanimoto’, ‘russellrao’, ‘seuclidean’, ‘sokalmichener’, ‘sokalsneath’,
# ‘sqeuclidean’, ‘yule’.
Z_20ng = hierarchy.linkage(data, method = 'ward', metric = 'euclidean')
plt.figure(figsize=(14,4))
R_20ng = hierarchy.dendrogram(Z_20ng, p=4, truncate_mode = 'level', show_leaf_counts=True)
Selecting the Number of Clusters
Let’s flatten the hierarchy to different numbers clusters and calculate the Silhouette Score.
Code
import sklearn.metrics as metrics
max_clusters = 20
s = np.zeros(max_clusters+1)
for k in range(2, max_clusters+1):
clusters = hierarchy.fcluster(Z_20ng, k, criterion = 'maxclust')
s[k] = metrics.silhouette_score(np.asarray(data), clusters, metric = 'euclidean')
plt.plot(range(2, len(s)), s[2:], '.-')
plt.xlabel('Number of clusters')
plt.ylabel('Silhouette Score')
plt.show()/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: divide by zero encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: overflow encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: invalid value encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: divide by zero encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: overflow encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: invalid value encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: divide by zero encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: overflow encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: invalid value encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: divide by zero encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: overflow encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: invalid value encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: divide by zero encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: overflow encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: invalid value encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: divide by zero encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: overflow encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: invalid value encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: divide by zero encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: overflow encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: invalid value encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: divide by zero encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: overflow encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: invalid value encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: divide by zero encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: overflow encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: invalid value encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: divide by zero encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: overflow encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: invalid value encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: divide by zero encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: overflow encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: invalid value encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: divide by zero encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: overflow encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: invalid value encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: divide by zero encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: overflow encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: invalid value encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: divide by zero encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: overflow encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: invalid value encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: divide by zero encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: overflow encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: invalid value encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: divide by zero encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: overflow encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: invalid value encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: divide by zero encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: overflow encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: invalid value encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: divide by zero encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: overflow encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: invalid value encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: divide by zero encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: overflow encountered in matmul
ret = a @ b
/Users/tgardos/Source/courses/ds701/DS701-Course-Notes/.venv/lib/python3.10/site-packages/sklearn/utils/extmath.py:203: RuntimeWarning: invalid value encountered in matmul
ret = a @ b
We see a first peak at 5.
Top terms per cluster when we flatten to a depth of 5.
Code
k = 5
clusters = hierarchy.fcluster(Z_20ng, k, criterion = 'maxclust')
for i in range(1,k+1):
items = np.array([item for item,clust in zip(data, clusters) if clust == i])
centroids = np.squeeze(items).mean(axis = 0)
asc_order_centroids = centroids.argsort()#[:, ::-1]
order_centroids = asc_order_centroids[::-1]
terms = vectorizer.get_feature_names_out()
print(f'Cluster {i}:')
for ind in order_centroids[:10]:
print(f' {terms[ind]}')
print('')Cluster 1:
space
nasa
edu
henry
gov
alaska
access
com
moon
digex
Cluster 2:
ax
max
b8f
g9v
a86
145
1d9
pl
2di
0t
Cluster 3:
edu
com
year
baseball
article
writes
cs
team
game
university
Cluster 4:
risc
instruction
ghhwang
csie
set
nctu
cisc
tw
reduced
mq
Cluster 5:
windows
edu
file
dos
com
files
card
drivers
driver
use
Comparison of Linkages
Scikit-Learn has a very nice notebook and plot, copied here, that shows the different clusters resulting from different linkage methods.
Recap
Clustering Recap
This wraps up our partitional Cluster topics. We covered:
- What the clustering problem is
- An overview of the \(k\)-means clustering algorithm including initialization with \(k\)-means++
- Visualization techniques such as Multi-Dimensional Scaling
- Cluster evaluation with (Adjusted) Rand Index and Silhouette Coefficient
- Using evaluation to determine number of clusters
- Hierarchical Clustering with different methods and metrics
- Looked at applications of clustering on various types of synthetic data, image color quantization, newsgroup clustering