<jupyter_start><jupyter_text>K-means clustering -- isotropic data clusters, works ok! Here we're going to apply K-means clustering to various datasets. First with an algorithm written by hand, then using scikit-learn.<jupyter_code>import numpy as np 
import matplotlib.pyplot as plt
import matplotlib.cm as cm
from sklearn.datasets import make_blobs
from Kmeans_utils import *
from sklearn.cluster import KMeans

%matplotlib inline<jupyter_output><empty_output><jupyter_text>Get data Here we randomly generate some data using make_blobs() from scikit-learn. make_blobs() generates isotropic gaussian blobs and we know which data point belongs to which blob. We'll use K-means clustering to try to correctly predict the cluster assignments of each datapoint.<jupyter_code>nb_samples = 500
nb_feat = 2 #2D data, so we can visualise easily
K = 4 #number of centres

X, y = make_blobs(nb_samples, nb_feat, K, random_state = 6) #6
X = Norm_data(X)
#Visualise the data
colors = cm.rainbow(np.linspace(0, 1, K)) #colours for plotting
for i in range(K):
    plt.scatter(X[y==i,0], X[y==i,1], color = colors[i])<jupyter_output><empty_output><jupyter_text>Initialise cluster centroids<jupyter_code>#initialise cluster centres and error values
np.random.seed(0) #9 is bad one
clus_init = InitialiseCentres(K, X)
[err, err_prev] = [0, 1] #use some random values
clus = clus_init<jupyter_output><empty_output><jupyter_text>Perform the K-means clustering algorithm<jupyter_code>#The K-means algorithm
while (not np.isclose(err, err_prev, rtol = 1e-10)):
    #set error 
    err_prev = err

    #expectation step
    idx, err = Expectation(X, clus)

    #maximisation step
    clus = FindCenters(X, idx, K)<jupyter_output><empty_output><jupyter_text>Plot the data<jupyter_code>#show final cluster assignments
for j in range(K):
    plt.scatter(X[j == idx,0], X[j == idx,1], color = colors[j], s = 15)<jupyter_output><empty_output><jupyter_text>It looks like we did a pretty good job! Almost all data points are clustered correctly. What happens, however, if we initialise our cluster centroids in a different way? Below we repeat the process above, now with four different random initialisations.   Influence of initial centroid assignment What happens if we try out different centroid initialisations?<jupyter_code>#initialise cluster centres and error values
fig, axs = plt.subplots(2,2, figsize = (10, 10)); axs = axs.ravel()

seeds = [0, 2, 9, 10]
Store_err = np.zeros(len(seeds))

for i, seed in enumerate(seeds):
    #initialise
    np.random.seed(seed)
    clus = InitialiseCentres(K, X)
    [err, err_prev] = [0, 1]

    #The K-means algorithm
    while (not np.isclose(err, err_prev, rtol = 1e-10)):
        err_prev = err
        idx, err = Expectation(X, clus)
        clus = FindCenters(X, idx, K)
    Store_err[i] = err
    
    #show final cluster assignments
    for j in range(K):
        axs[i].scatter(X[j == idx,0], X[j == idx,1], color = colors[j], s = 15)
    axs[i].set_title('Seed %d, total error %.2f' % (seed, err))

axs[np.argmin(Store_err)].text(0.6,0.9, 'We will use this one!', 
                               horizontalalignment = 'center',
                               verticalalignment = 'center',
                               transform=axs[np.argmin(Store_err)].transAxes,
                               fontsize = 15, bbox=dict(facecolor='red', alpha=0.3))<jupyter_output><empty_output><jupyter_text>We see that some centroid initialisations lead to bad clustering. That's why it can be important to run the clustering algorithm several times and pick the one with the lowest final error (defined as the sum of distances from each point to its closest cluster centroid). In this case, this leads to the classification shown in the upper right figure.  Using scikit-learn Now we'll use the K-means clustering algorithm of scikit-learn. It gives a very similar answer to our own algorithm. The default cluster centroid initialisation of sklearn uses a smart way to speed up convergence.<jupyter_code>kmeans = KMeans(n_clusters = K)
kmeans.fit(X)
labels = kmeans.fit_predict(X)
for j in range(K):
    plt.scatter(X[labels ==j,0], X[labels ==j,1], color = colors[j], s = 15)<jupyter_output><empty_output><jupyter_text>Voronoi cells All the K-means algorithm is doing, is finding an optimal set of cluster centroids and assigning each datapoint to its closest cluster centroid. This algorithm will create a Voronoi diagram, which itself is a partitioning of a plane into regions based on distance to points in a specific subset of the plane. In a voronoi diagram a set of points (centroids) is specified and for each point there is a corresponding region consisting of all points closer to that seed than to any other. This is exactly what K-means is doing! We can show this by simply telling K-means to partition points randomly spread over the plane<jupyter_code>X = np.random.rand(10000,2) #random (x,y) points, in [[0,1], [0,1]]
K = 20

#Fit k-means
kmeans = KMeans(n_clusters = K)
kmeans.fit(X)
labels = kmeans.fit_predict(X)
colors = cm.rainbow(np.linspace(0, 1, K)) #colours for plotting
for j in range(K):
    plt.scatter(X[labels ==j,0], X[labels ==j,1], color = colors[j], s = 15)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09660175639557082, 'fraction_numerical': 0.014127529591447117, 'mean_word_length': 4.291919191919192, 'pattern_counts': {'":': 0, '<': 33, '<?xml version=': 0, '>': 33, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '288905', 'license': 'MIT', 'n_tokens_mistral': 1768, 'n_tokens_neox': 1658, 'n_words': 608, 'path': 'Kmeans_GMM/.ipynb_checkpoints/Isotropic_clusters_Kmeans-checkpoint.ipynb', 'repo_name': 'Hannemit/MachineLearning', 'size': '5238'}