Application: Clustering can be used for finding features that will be useful later for categorization; Image segmentation

Method: take mean of group as centroid → group by finding nearest centroid and joining it

Stop Criteria: small re-assignment; small change of centroid; small decrease of sum of squared error, $SSE=\sum_i \sum_x dist^2(pt_{i,x},centroid_i)$

Find K: Elbow method, Silhouette method

Clustering quality: maximize inter-cluster distance(isolution), minimize intra-cluster distance(compactness)

Cons: sensitive to outliers

convergence: note that SSE is decresing

from sklearn.cluster import KMeans
import matplotlib.pyplot as plt

# Unlabled training data
data = np.array([[19, 15, 39], [67, 19, 14], [35, 24, 35], [60, 30, 4], [65, 38, 35],
[49, 42, 52], [70, 46, 56], [70, 49, 55], [57, 54, 51], [68, 59, 55],
[23, 62, 41], [65, 63, 52], [27, 67, 56], [47, 71, 9], [57, 75, 5],
[43, 78, 17], [56, 79, 35], [40, 87, 13], [37, 97, 32], [34, 103, 23]])

init_centroids = np.array([[70, 46, 56], [27, 67, 56], [37, 97, 32]])
kmeans = KMeans(n_clusters=3, init=init_centroids, n_init=1, max_iter = 4)
kmeans.fit(data)
labels = kmeans.predict(data) # Predict the closest cluster each sample in data belongs to
centroids = kmeans.cluster_centers_ # Get resulting centroids

fig = plt.figure(figsize = (10,10)) # Figure width = 10 inches, height = 10 inches
ax = fig.gca(projection=’3d’) # Defining 3D axes so that we can plot 3D data into it
# Get boolean arrays representing entries with labels = 0, 1, and 2
a = np.array(labels == 0); b = np.array(labels == 1); c = np.array(labels == 2)
# Plot centroids with color = black, size = 50 units, transparency = 20%, and put label "Centroids"
ax.scatter(centroids[:,0], centroids[:,1], centroids[:,2],
c="black", s=50, alpha=0.8, label="Centroids")
# Plot data in the different clusters (1st in red, 2nd in green, 3rd blue)
ax.scatter(data[a,0], data[a,1], data[a,2], c="red", s=40, label="1st Cluster")
ax.scatter(data[b,0], data[b,1], data[b,2], c="green", s=40, label="2nd Cluster")
ax.scatter(data[c,0], data[c,1], data[c,2], c="blue", s=40, label="3rd Cluster")
ax.legend() # Show legend
ax.set_xlabel("Age") # Put x-axis label "Age"
ax.set_ylabel("Income (K)") # Put y-axis label "Income (K)"
ax.set_zlabel("Expense Score (1-100)") # Put z-axis label "Expense Score (1-100)"
ax.set_title("Customer Segmentation - K-Means Clustering") # Put figure title

class KCluster:
    def __init__(self, k, X, ndim=2):
        self.k = k
        self.ndim = ndim
        self.centroid = X[np.random.randint(0, len(X), size=(k, ))]
    def run(self, X):
        diff = self.centroid.reshape(self.k, 1, self.ndim) - X.reshape(1, X.shape[0], self.ndim)
        dist=np.linalg.norm(diff,axis=2)
				output = np.argmin(dist,axis=0)
        for i in range(self.k):
            self.centroid[i] = np.mean( X[ output==i ], axis=0)
        return output

def SSE(X, y, k, centroids):
    sse = 0
    for i in range(X.shape[0]):
      sse+= np.sum( (X[i]-centroids[y[i]])**2 )
    return sse