Name: Towards AI Legal Name: Towards AI, Inc. Description: Towards AI is the world's leading artificial intelligence (AI) and technology publication. Read by thought-leaders and decision-makers around the world. Phone Number: +1-650-246-9381 Email: [email protected]
228 Park Avenue South New York, NY 10003 United States
Website: Publisher: https://towardsai.net/#publisher Diversity Policy: https://towardsai.net/about Ethics Policy: https://towardsai.net/about Masthead: https://towardsai.net/about
Name: Towards AI Legal Name: Towards AI, Inc. Description: Towards AI is the world's leading artificial intelligence (AI) and technology publication. Founders: Roberto Iriondo, , Job Title: Co-founder and Advisor Works for: Towards AI, Inc. Follow Roberto: X, LinkedIn, GitHub, Google Scholar, Towards AI Profile, Medium, ML@CMU, FreeCodeCamp, Crunchbase, Bloomberg, Roberto Iriondo, Generative AI Lab, Generative AI Lab Denis Piffaretti, Job Title: Co-founder Works for: Towards AI, Inc. Louie Peters, Job Title: Co-founder Works for: Towards AI, Inc. Louis-François Bouchard, Job Title: Co-founder Works for: Towards AI, Inc. Cover:
Towards AI Cover
Logo:
Towards AI Logo
Areas Served: Worldwide Alternate Name: Towards AI, Inc. Alternate Name: Towards AI Co. Alternate Name: towards ai Alternate Name: towardsai Alternate Name: towards.ai Alternate Name: tai Alternate Name: toward ai Alternate Name: toward.ai Alternate Name: Towards AI, Inc. Alternate Name: towardsai.net Alternate Name: pub.towardsai.net
5 stars – based on 497 reviews

Frequently Used, Contextual References

TODO: Remember to copy unique IDs whenever it needs used. i.e., URL: 304b2e42315e

Resources

Unlock the full potential of AI with Building LLMs for Productionβ€”our 470+ page guide to mastering LLMs with practical projects and expert insights!

Publication

All About K-Means Clustering
Latest

All About K-Means Clustering

Last Updated on May 30, 2022 by Editorial Team

Author(s): Akash Dawari

Originally published on Towards AI the World’s Leading AI and Technology News and Media Company. If you are building an AI-related product or service, we invite you to consider becoming an AI sponsor. At Towards AI, we help scale AI and technology startups. Let us help you unleash your technology to the masses.

In this article we will understand a clustering algorithm by answering the following question:

  1. What is clustering?
  2. What are the real-world applications of clustering?
  3. How does K-means Clustering work?
  4. How can we find the value ofΒ K?
  5. What are the advantages and disadvantages of K-Means Clustering?
  6. How to implement K-Means Clustering?

What is Clustering?

The classic definition willΒ be:

β€œClustering is an unsupervised machine learning technique which finds certain patterns/structures in the unlabeled data to segregate them into different groups, according to their properties.”

To understand the definition let's take an example: In a library, the books are organized in a particular way so that when an individual look for a specific book, he/she could find it. So, to organize these books, they are grouped together by their similar properties. This technique of grouping different elements by their similar properties and behavior is known as clustering.

What are the real-world applications of clustering?

Different clustering techniques are used to solve the real-world challenges faced in day-to-day life. Some of the applications are asΒ follows:

  • For customer segmentation: You can cluster your customers based on their purchases, their activity on your website, and so on. This is useful to understand who your customers are and what they need, so you can adapt your products and marketing campaigns to each segment. For example, this can be useful in recommender systems to suggest content that other users in the same clusterΒ enjoyed.
  • For data analysis: When analyzing a new dataset, it is often useful to first discover clusters of similar instances, as it is often easier to analyze clusters separately.
  • As a dimensionality reduction technique: Once a dataset has been clustered, it is usually possible to measure each instance’s affinity with each cluster (affinity is any measure of how well an instance fits into a cluster). Each instance’s feature vector x can then be replaced with the vector of its cluster affinities. If there are k clusters, then this vector is k dimensional. This is typically much lower-dimensional than the original feature vector, but it can preserve enough information for further processing.
  • For anomaly detection (also called outlier detection): Any instance that has a low affinity to all the clusters is likely to be an anomaly. For example, if you have clustered the users of your website based on their behavior, you can detect users with unusual behavior, such as an unusual number of requests per second, and so on. Anomaly detection is particularly useful in detecting defects in manufacturing, or for fraud detection.
  • For semi-supervised learning: If you only have a few labels, you could perform clustering and propagate the labels to all the instances in the same cluster. This can greatly increase the number of labels available for a subsequent supervised learning algorithm and thus improve its performance.
  • For search engines: For example, some search engines let you search for images that are similar to a reference image. To build such a system, you would first apply a clustering algorithm to all the images in your database: similar images would end up in the same cluster. Then when a user provides a reference image, all you need to do is to find this image’s cluster using the trained clustering model, and you can then simply return all the images from thisΒ cluster.
  • To segment an image: By clustering pixels according to their color, then replacing each pixel’s color with the mean color of its cluster, it is possible to reduce the number of different colors in the image considerably. This technique is used in many object detection and tracking systems, as it makes it easier to detect the contour of eachΒ object.

How does K-means Clustering work?

K-Means is a clustering approach in which the data is grouped into K distinct non-overlapping clusters based on their distances from the K centers. The value of K needs to be specified first and then the algorithm assigns the points to exactly oneΒ cluster.

Algorithm:

  1. Randomly assign KΒ centers.
  2. Calculate the distance of all the points from all the K centers and allocate the points to the cluster based on the shortest distance. The model’s inertia is the mean squared distance between each instance and its closest centroid. The goal is to have a model with the lowestΒ inertia.
  3. Once all the points are assigned to clusters, recompute the centroids.
  4. Repeat steps 2 and 3 until the locations of the centroids stop changing and the cluster allocation of the points becomes constant.

The algorithm of K-Means Clustering is pretty straightforward. So, now let's visualize what we have discussed in the algorithm so to better understand it.

The first step is to assign the value of k. The value of k indicates the number of groups we want to segregate ourΒ data.

The res dots are k-centroids

Here we have assigned the value of k = 3. This means we have generated three random centroids based on which we segregate ourΒ data.

The second step Now we have to calculate the distance of every data point with respect to each centroid, we have introduced. Then select the nearest centroids and assign aΒ group.

The third step is to recalculate the coordinates of the centroids we have introduced. This step can be done by calculating the mean of the points which are assigned to the respective centroid.

The fourth step is to repeat the step second and third until the coordinates of the centroids stopΒ moving.

So, the final output will look likeΒ this:

So, we have also visualized the core intuition of k-means clustering. But there is still one question we have to answer how can we decide the value of k. so, let's seeΒ how?

How can we find the value ofΒ K?

The value of K can be found with the help of one method which is The Elbow-Method. Let see now what Is this elbow method allΒ about.

This method is based on the relationship between the within-cluster sum of squared distances(WCSS Or Inertia) and the number of clusters. It is observed that first with an increase in the number of clusters WCSS decreases steeply and then after a certain number of clusters the drop in WCSS is not that prominent. The point after which the graph between WCSS and the number of clusters becomes comparatively smother is termed the elbow and the number of clusters at that point is the optimum number of clusters as even after increasing the clusters after that point the variation is not decreased byΒ much.

What are the advantages and disadvantages of K-Means Clustering?

Advantages:

  1. This algorithm is very easy to understand and implement.
  2. This algorithm is efficient, Robust, andΒ Flexible
  3. If data sets are distinct and spherical clusters, then give the bestΒ results

Disadvantages:

  1. This algorithm needs prior specification for the number of cluster centers that is the value ofΒ K.
  2. It cannot handle outliers and noisy data, as the centroids get deflected
  3. It does not work well with a very large set of datasets as it takes huge computational time.

How to implement K-Means Clustering?

The implementation of K-Means Clustering is very easy, just have to follow the algorithm which we have discussed above.

NOTE: The below k-means code is from scratch. I did not use scikit-learn library to build theΒ code.

First, let’s import the import packages from python to getΒ started.

Now, create a toyΒ dataset.

visualize our toyΒ dataset

Step-1: Initialize the value of K i.e. create 5 random centroids

Visualize the centroids.

Step 2: calculate the distance of every data point to the centroids and assign the nearest centroid.

Visualize the data and how they are grouped with the centroids.

Step 3: calculate the mean for every group and assign it to the centroid to create new centroids.

Visualize the new centroids.

Step 4: Now just repeat the 2nd and 3rd step until centroids stop changing.

Visualize the final clustering.

link of the notebook used in thisΒ article:

Articles_Blogs_Content/K-Means Clustering.ipynb at main Β· Akashdawari/Articles_Blogs_Content

Like and Share if you find this article helpful. Also, follow me on medium for more content related to Machine Learning and Deep Learning.


All About K-Means Clustering was originally published in Towards AI on Medium, where people are continuing the conversation by highlighting and responding to this story.

Join thousands of data leaders on the AI newsletter. It’s free, we don’t spam, and we never share your email address. Keep up to date with the latest work in AI. From research to projects and ideas. If you are building an AI startup, an AI-related product, or a service, we invite you to consider becoming aΒ sponsor.

Published via Towards AI

Feedback ↓