<jupyter_start><jupyter_text>K MEANS CLUSTERING  Unsupervised LearningAs we know, in Supervised Learning models, where we have both input and output and our goal is to create a logic associating input and the output. However sometimes you may deal only with inputs which may have no defined outputs. This is called Unsupervised Learning.For example,    Dimensionality Reduction (Ex: PCA, tSNE)    Clustering (Ex: K Means, Hierarchical Clustering, DBSCAN)etc.Here we'll be looking at the most basic clustering algorithm, K Means Clustering.   Theory  IntroductionK Means is one of the simplest well known unsupervised clustering algorithms. A cluster is a group of data points that are similar to each other in some way. Generally to find similarity, Euclidean distance between the features is used i.e, the data points which are closer to each other are more similar. In K means, K refers to number of clusters.The main goal of K means is to find K points and call these the center of the clusters. After that each data point is assigned to cluster whose center is closest to the data point. The K Means Algorithm is used to find these centers.> In this image, the data points have two features and are plotted on the X and Y axis. The different clusters are denoted by different colours. As we can see, the points belonging to same cluster are closer to each other.Image credits  AlgorithmLet $\{ v_1, v_2 \ldots v_m\}$ be $m$ data points that we need to cluster.Algorithm Steps:            Chose a suitable K value i.e, number of clusters.                 Randomly chose K cluster centers:        Randomly chose K data points and call them the cluster centers $\{C_1, C_2 \ldots C_K\}$.                Assign cluster to each data point:        For each data point $v_i$ find the closest cluster center to it and assign $v_i$ to that cluster. The closeness between two points is measured by the Euclidean distance between the two points.                Recalculate the cluster centers:        Each data point has been assigned to a single cluster in the previous step. Now for each cluster (say $C_j$), calculate the mean of all the data points that belong to $C_j$. Reassign $C_j$ to this mean i.e,        $$C_j = mean(\{v_i \ | \  v_i \in C_j\})$$                    Repeat the process from step 3 until maximum number of iterations is reached or cluster centers stop changing.    Since the final clusters depend on initially chosen cluster centers (which are chosen at random) the entire algorithm is applied multiple times to find the best results.  IntuitionIn the first step, we randomly chose K cluster centers. They are generally chosen as K random data points instead of random points in the entire space. After that, the algorithm moves the cluster centers closer and closer to the actual cluster centers in every iteration, until the cluster centers don't change anymore. However the final clusters will depend on initial random initialization and hence we run the algorithm multiple times to chose the best clusters.The following image shows K Means at various steps.> Image credits  EvaluationSince K Means is an unsupervised learning algorithm, we can't measure how well the algorithm performs by comparing it to a true value. So, the clusters are said to be good if the data points belonging to same cluster are close to each other and data points belonging to different clusters are far from each other.Therefore, a K Means model is evaluated using the sum of squared distances between every data point and its cluster center. The smaller the SSE (Sum of Squared Errors), the better the clustering. To find SSE, for each cluster find the sum of the squared distances between the data points that belong to that cluster and the cluster centers. Then add all these sums for the K clusters.To chose the best clustering, run the K Means algorithm multiple times and chose the cluster center initialization that gives the lowest SSE.  Chosing the best K ValueWe can also use the SSE to find the best K value using a method called the elbow method. To do this, plot the SSE (by SSE we mean SSE for the best clustering) against K values. The SSE drops as K value increases (in fact, SSE is 0 when K is equal to number of data points). So the K value for which there is a maximum drop in SSE is the best estimate for number of clusters. After this maximum drop, the curve seems to slowly flatten.    Note: Sometimes this method may not work as it might be difficult to identify the elbow point.> In this image K = 2 causes maximum drop in SSE. Also notice how the curve tends to slowly flatten after K = 2. This methid is called elbow method because the curve looks like a human arm and the optimal value is the elbow point.Image credits  Advantages and Disadvantages Advantages    It is fast and simple to understand.    Works really well when clusters are distinct. Disadvantages    Need to manually chose K value.    The algorithm may sometimes end up in local optima.    The algorithm does not works very well only for circular clusters.   ImplementationWe can implement K Means clustering using Scikit Learn.  Importing the libraries<jupyter_code>import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
sns.set()<jupyter_output><empty_output><jupyter_text>Creating the datasetAn artificial cluster dataset can be created using sklearn. Also one more thing to notice is that generally we don't do train test splits in clustering since we don't have any labels to test on.<jupyter_code>from sklearn.datasets import make_blobs

data,_ = make_blobs(200, n_features = 2, centers = 3, cluster_std = [1, 1.5, 2], random_state = 1234)
data.shape<jupyter_output><empty_output><jupyter_text>Let's plot the given data. First feature on X-axis and second feature on Y-axis.<jupyter_code>data
data[:,0]
sns.scatterplot(data[:,0], data[:,1])<jupyter_output><empty_output><jupyter_text>From the figure we can make out 3 clusters.  Creating the modelCreate a K Means clustering model using sklearn. After fitting the model, plot the data points and distinguish the clusters by color. Also plot the cluster centers.<jupyter_code>from sklearn.cluster import KMeans
kmeans= KMeans(n_clusters=2,init='k-means++')
y=kmeans.fit_predict(data)
centers = kmeans.cluster_centers_
plt.scatter(data[:,0], data[:,1],c=y,cmap='rainbow')
plt.scatter(centers[:, 0], centers[:, 1], c='black', s=200, alpha=0.5);<jupyter_output><empty_output><jupyter_text>ExperimentationThe KMeans class abstracts a lot of information. Try looking at all the attributes of the class and try changing them. For example, init is set to "k-means++" initially which intelligently choses initial clusters, try changing it to "random"; n_init is set to 10 by default which means the algorithm is run 10 times and the best one is chosen automatically, try changing it to 1 and run the model multiple times.Also here we know that K = 3 because this data is artificially generated. Try fitting the model for different K values and see how KMeans tries to fit for those K values.  Elbow plotSince this data is 2 dimensional we could easily figure out that there were 3 clusters. However in case of high dimensional data we can use an elbow plot to figure out the number of clusters.Plot an elbow plot for this data. (Hint: You can use sklearn to calculate SSE for each K value)<jupyter_code>distortions = []
K = range(1,10)
for k in K:
    kmeanModel = KMeans(n_clusters=k)
    kmeanModel.fit(data)
    distortions.append(kmeanModel.inertia_)    
plt.figure(figsize=(16,8))
plt.plot(K, distortions, 'bx-')
plt.xlabel('k')
plt.ylabel('Distortion')
plt.title('The Elbow Method showing the optimal k')
plt.show()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.04941634241245136, 'fraction_numerical': 0.00635538261997406, 'mean_word_length': 4.332641770401106, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 24, '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': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '473238', 'license': 'Apache-2.0', 'n_tokens_mistral': 2029, 'n_tokens_neox': 1916, 'n_words': 1158, 'path': 'UnsupervisedLearning/k-means clustering.ipynb', 'repo_name': 'XGBTrain5/01.ml-abhinand', 'size': '7710'}