Clustering Exploration¶
- How does basic unsupervised clustering work?
- What are some issues with clustering that can be solved by smarter strategies?
- How can clustering be applied to image compression? (Cute dog pictures involved)
Code and visual answers to all of the above included below!
In [222]:
import numpy as np
import matplotlib.pyplot as plt
from PIL import Image
import pandas as pd
from sklearn.ensemble import RandomForestClassifier
from sklearn.cluster import SpectralClustering
from sklearn.metrics import accuracy_score
KMeans¶
In [233]:
%run kmeans
Simple Example With Two Distinct Clusters¶
- Vanilla kmeans works by randomly initializing a specified (k) number of centroids and then
- Assigning data points to their closest centroids
- Recomputing the centroids as the mean of the points belonging to each cluster
- Repeat the process until centroids don't change by some specified tolerance
- Here we show that regular kmeans is able to find the centers of two synthetically created clusters and assign points correctly
Create two clusters normally distributed about (0,0) and (4,4) respectively in two dimensions
In [3]:
group1 = np.random.normal(loc=[0,0], scale=[1,1], size=(100,2))
group2 = np.random.normal(loc=[4,4], scale=[1,1], size=(100,2))
In [4]:
X = np.vstack([group1,group2])
In [5]:
plt.scatter(X[:,0],X[:,1])
plt.show()
The results of our kmeans algorithm (setting number of clusters=2) shows that it easily finds the centers of each group
In [6]:
centroids, cluster_indexes = kmeans(X, k=2)
In [7]:
ax1 = plt.scatter(X[:,0], X[:,1], alpha=0.5, c=cluster_indexes)
ax2 = plt.scatter(centroids[:,0], centroids[:,1], marker='x', s=200, c='r', linewidths=8)
plt.show()
Confusing KMeans¶
- What if the clusters have different variances, or the wrong initialization centroids are chosen? Here we show that it can often produce different results with each iteration of running kmeans
In [8]:
group1 = np.random.normal(loc=[0,0], scale=[0.1,0.1], size=(100,2))
group2 = np.random.normal(loc=[0,2], scale=[0.5,0.5], size=(100,2))
group3 = np.random.normal(loc=(3,3), scale=[1,1], size=(200,2))
In [9]:
X = np.vstack([group1,group2,group3])
In [10]:
plt.scatter(X[:,0],X[:,1])
plt.show()
The above plot was created with three distinct clusters, some with higher variance. We see that depending on the random initialization of our clusters, kmeans can produce very different results, as shown in the two plots below
In [11]:
centroids_run1, cluster_indexes_run1 = kmeans(X, k=3)
#cluster_colors_run1 = cluster_colors(cluster_indexes_run1)
In [22]:
centroids_run2, cluster_indexes_run2 = kmeans(X, k=3)
#cluster_colors_run2 = cluster_colors(cluster_indexes_run2)
In [23]:
plt.figure(figsize=(12,5))
ax1 = plt.subplot(121)
ax1.scatter(X[:,0], X[:,1], alpha=0.5, c=cluster_indexes_run1)
ax1.scatter(centroids_run1[:,0], centroids_run1[:,1], marker='x', s=200, c='r', linewidths=8)
ax2 = plt.subplot(122)
ax2.scatter(X[:,0], X[:,1], alpha=0.5, c=cluster_indexes_run2)
ax2.scatter(centroids_run2[:,0], centroids_run2[:,1], marker='x', s=200, c='r', linewidths=8)
plt.show()
Fixing Intialization Issues with KMeans ++¶
- KMeans++ is an improved version of KMeans that address initialization issues by finding "smart" initial centroids before proceeding with the regular KMeans algorithm
- The first centroid is still chosen randomly, but every subsequent inital centroid (the remaining k-1 choices) is picked as the data point whose minimum distance to the existing centroids is maximized
In [27]:
kmeans_output, initial_centroids = kmeans_plus_plus(X, k=3)
In [28]:
centroids, cluster_indexes = kmeans_output
In [29]:
plt.figure(figsize=(12,6))
plt.scatter(X[:,0], X[:,1], alpha=0.3, c=cluster_indexes, label="_nolegend_")
plt.scatter(centroids[:,0], centroids[:,1], marker='x', s=200, c='red', linewidths=8)
plt.scatter(initial_centroids[:,0], initial_centroids[:,1], marker='x', s=200, c='black', linewidths=8)
plt.legend(['Final Centroids','Initial Centroids'])
plt.show()
Image Compression¶
- Thinking about each pixel in an image as a data point (1-D vector for greyscale, 3-D vector for RGB) we can use kmeans to to reduce the possible values taken on by pixels to just those defined by k centroids (a form of image compression)
Greyscale Image¶
In [30]:
dog_original = Image.open('dog.png')
In [31]:
dog_original
Out[31]:
In [32]:
h,w = dog_original.height, dog_original.width
Greyscale images only have one dimension so we convert our image into a single column array
In [33]:
X = np.array(dog_original).reshape(-1,1)
We are going to find four clusters in our image, thereby reduce our greyscale image from representation in 0-255 space, to only four values!
In [34]:
output, initial_centroids = kmeans_plus_plus(X, k=4)
centroids, cluster_indexes = output
Centroids can become floating point representations, but images require integer values
In [35]:
centroids = centroids.astype(np.uint8)
In [36]:
centroids
Out[36]:
Map every element of X to the centroid value of the cluster it belongs to
In [37]:
centroid_map = {i:centroid for i,centroid in enumerate(centroids)}
In [38]:
new_X = np.array([centroid_map[cluster_index] for cluster_index in cluster_indexes])
new_X = new_X.reshape((h,w))
dog_new = Image.fromarray(new_X, 'L')
The result? Art!
In [39]:
dog_new
Out[39]:
Color Image (Painting)¶
In [40]:
vangogh = Image.open('starry_night.jpg')
In [42]:
vangogh
Out[42]:
In [43]:
h,w = vangogh.height, vangogh.width
In [44]:
X = np.array(vangogh).reshape(-1,3)
In [51]:
output, initial_centroids = kmeans_plus_plus(X, k=5, tolerance=2)
In [52]:
centroids, cluster_indexes = output
In [53]:
centroids = centroids.astype(np.uint8)
In [54]:
centroid_map = {i:centroid for i,centroid in enumerate(centroids)}
In [55]:
new_X = np.array([centroid_map[cluster_index] for cluster_index in cluster_indexes])
new_X = new_X.reshape((h,w,3))
vangogh_new = Image.fromarray(new_X)
In [56]:
vangogh_new
Out[56]:
Color Image (Photo)¶
In [57]:
landscape = Image.open('landscape.jpg')
In [58]:
landscape
Out[58]:
In [59]:
h,w = landscape.height, landscape.width
In [60]:
X = np.array(landscape).reshape(-1,3)
In [67]:
output, initial_centroids = kmeans_plus_plus(X, k=8, tolerance=5)
In [68]:
centroids, cluster_indexes = output
In [69]:
centroids = centroids.astype(np.uint8)
In [70]:
centroid_map = {i:centroid for i,centroid in enumerate(centroids)}
In [71]:
new_X = np.array([centroid_map[cluster_index] for cluster_index in cluster_indexes])
new_X = new_X.reshape((h,w,3))
landscape_new = Image.fromarray(new_X)
In [72]:
landscape_new
Out[72]:
Spectral Clustering¶
- Goal: train a random forest on an unlabeled version of a breast-cancer dataset. Use the results to to compute a similarity/proximity matrix between data points that can then be fed into a spectral clustering algorithm. Compare the k=2 cluster results to the actual labels (Malignant or Benign)
In [284]:
cancer_data = pd.read_csv('cancer_data.csv')
cancer_data['label'] = cancer_data['diagnosis'].map({'M':1, 'B':0})
Since this is an unsupervised problem, we don't have labels. We train our random forest then is by creating a duplicate dataset where each column has been shuffled. We concatenate these two datasets and task the random forest to predict label = original or shuffled dataset
In [271]:
original = cancer_data.drop(columns=['id','diagnosis','Unnamed: 32','label'])
shuffled = original.copy()
In [272]:
for col in shuffled.columns:
np.random.shuffle(shuffled[col].values)
In [273]:
original['target'] = 1
shuffled['target'] = 2
combined_data = pd.concat([original, shuffled], axis=0)
In [279]:
X = combined_data.drop(columns=['target'])
y = combined_data['target']
rf = RandomForestClassifier(n_estimators=100, min_samples_leaf=3, max_features=0.8)
rf.fit(X, y)
Out[279]:
leaf_samples is a function that returns which data points of our original dataset end up in which leaf node (repeated for every tree in the random forest)
In [280]:
leafs = leaf_samples(rf, original.drop(columns=['target']))
Constructing the similarity matrix is then just a matter of incrementing the i,j entries in the matrix if they ever appeared in a leaf node together
In [281]:
similarity_matrix = np.zeros((len(original), len(original)))
for arr in leafs:
for i in range(len(arr)):
for j in range(len(arr)):
similarity_matrix[arr[i], arr[j]] +=1
In [282]:
cluster = SpectralClustering(n_clusters=2, affinity='precomputed')
cluster_preds = cluster.fit_predict(similarity_matrix)
Creating two clusters (correspoding hopefully to Malignant and Benign) via Spectral Clustering turns out to actually achieve 90% accuracy when compared with the true labels
In [285]:
accuracy_score(cancer_data['label'], cluster_preds)
Out[285]:
In [286]:
confusion_matrix(cancer_data['label'], cluster_preds)
Out[286]:
We can also see how our regular kmeans does at creating two clusters corresponding to our true lables. Accuracy is less than spectral clustering, but still achieves 85%
In [287]:
original_array = np.array(original.drop(columns=['target']))
centroids, cluster_indexes = kmeans(original_array, k=2)
In [288]:
accuracy_score(cancer_data['label'], cluster_indexes)
Out[288]:
In [ ]: