K-MEANS

                                                

This blog post will provide you with a comprehensive overview of K-means, exploring the theory behind this probabilistic algorithm and demonstrating its implementation using Python libraries. Dive in to uncover the advantages and disadvantages of K-means, as well as its real-world applications across various domains. With that, enjoy your journey in QDO!

WHAT IS K-MEANS

                            

K-means is an unsupervised machine learning algorithm primarily used for clustering tasks. It aims to partition a dataset into a specified number of clusters , where each data point belongs to the cluster with the nearest mean, which serves as the "centroid" of that cluster. The algorithm starts by randomly initializing $k$ centroids, and each data point is assigned to the nearest centroid, forming temporary clusters. After all points are assigned, the centroids are recalculated as the mean of the points within each cluster. This process of assignment and centroid recalculation iterates until the centroids stabilize or until a set number of iterations is reached.

Concept of random forest

Lets say we want to cluster all the genes and we have all the data of the gene plotted on the line

We start by selecting 3 random data points as our initial cluster point

Next, we cluster the remaining data base on the distance to the cluster point

Next, we find the center point/mean for each cluster and the whole process repeats again

The variance of each cluster is presented to us and the whole process repeats until the variance no longer changes

The number ok k-means can be best determine through the elbow method below in which we plot the number of clusters and reduction in variation for each of the clusters. 

From the graph above, we can observe that the increment in the reduction in variation had decreased after the 3rd cluster. Hence, the ideal number for k in this situation is 3.

Implementation of k-means in python

Importing libraries 

from sklearn.datasets import load_iris

Loading dataset

iris = load_iris()

Applying the model

from sklearn.cluster import KMeans

kmeans = KMeans(n_clusters=3, random_state=0)

Get prediction result

KModel = kmeans.fit(iris.data)

Get prediction accuracy

import pandas as pd

pd.crosstab(iris.target, KModel.labels_)

col_0	0	1	2
row_0
0	0	50	0
1	47	0	3
2	14	0	36

Parameters that you can tune in k-means

Number of Clusters (k):

• This is the number of groups you want to create. Choosing the right $k$ is important for meaningful clusters. Common methods to find the best $k$ include:
  • Elbow Method: Plot the total distance between points and their cluster centers for different values of $k$. The "elbow" point, where improvements slow down, suggests a good $k$.
  • Silhouette Score: A score that shows how distinct and well-separated your clusters are; higher scores are better.

Starting Points (Initialization Method):

• The algorithm starts by choosing $k$ initial "centroid" points. Choosing good starting points helps K-means find better clusters:
  • Random: Picks starting points randomly, which can sometimes lead to poor results.
  • k-means++: Selects starting points that are far apart, giving better results more consistently.

Maximum Iterations:

• This sets the maximum number of times K-means can adjust the clusters. This can be helpful if the algorithm is taking too long, allowing it to stop early after a set number of tries.

Convergence Tolerance:

• This controls when the algorithm should stop adjusting clusters. If the centroids barely move between adjustments, the algorithm will stop. Smaller values mean the algorithm will keep fine-tuning for longer, which can improve results but also takes more time.

Number of Runs (n_init):

• K-means can be run multiple times with different starting points to find the best grouping. The final result is chosen as the one with the lowest total distance between points and their cluster centers. More runs can improve results, but also take longer.

Algorithm Variant:

• Different versions of K-means handle data slightly differently to improve speed:
  • Standard K-means: The most common and straightforward method.
  • Optimized K-means (like Elkan’s): Uses shortcuts to speed things up, especially helpful with large, high-dimensional data.

Advantages and disadvantages of k-means

Advantages

• Simple and Fast:

  • K-means is easy to understand and implement. It’s also computationally efficient, especially on large datasets, making it suitable for real-time applications.

• Works Well with Convex Clusters:

  • K-means is effective when clusters are spherical and of similar size, often producing clear, well-separated clusters under these conditions.

• Scalable:

  • K-means can handle large datasets and can be scaled with parallel or mini-batch versions, making it useful for big data.

Disadvantages

• Sensitive to Initial Choices:

  • The initial placement of centroids can significantly affect the final clusters, sometimes leading to suboptimal results. Different initializations can produce different outcomes.

• Requires Specification of $k$:

  • You need to specify the number of clusters ($k$) in advance, which isn’t always straightforward and can lead to trial and error or require additional methods to estimate the best $k$.

• Assumes Spherical Clusters:

  • K-means assumes clusters are roughly circular and evenly sized, so it struggles with complex shapes or clusters of very different sizes, leading to poor performance in these cases.

Implementation of k-means in real life

1. Customer Segmentation

• Amazon, Walmart, and other retailers use K-means clustering to segment customers based on their purchase behavior, demographics, browsing history, and spending patterns. By identifying clusters of customers with similar characteristics, these companies can create targeted marketing campaigns, personalize recommendations, and improve customer engagement. This segmentation helps retailers better understand their customer base, tailor product offerings, and optimize inventory based on customer preferences in different segments.

2. Image Compression

• Companies like Google and Instagram may use K-means for image compression. K-means can reduce the number of colors in an image by clustering similar colors together, which lowers file size without significantly sacrificing image quality. By compressing images effectively, tech companies reduce storage space and improve load times, which is especially important for mobile app performance and data efficiency.

3. Anomaly Detection in Network Security

• Banks, like JPMorgan Chase, and cybersecurity firms use K-means clustering to detect unusual patterns in network traffic or user behavior. K-means can help identify clusters of "normal" behavior, so outliers (potential security threats) stand out more clearly. This clustering approach helps detect fraud, identify potential breaches, and monitor irregular activities, which are critical for preventing financial losses and protecting sensitive data.