Skip to main content

K means clustering algorithm

Written by Abhishek mamidi, on

Clustering is one of the techniques used to group the objects such that similar objects are in the same cluster. The objects in the same cluster are similar and vice versa. Clustering is widely used in the industry to solve problems. For example, if we have a lot of documents and we want to cluster them based on its domain. We can use clustering to group similar documents.

I will give you a real life example. You have 10 apples, 10 oranges and 10 bananas. All the fruits are mixed and finally you have 30 fruits. You want to separate them into apples, oranges and bananas. What would you do? Based on the color and shape, you will recognize the fruit and you can easily separate them. You have used features like shape and color of the fruit to separate them. Similarly, we create features for documents and cluster them if any two documents are similar.

This article assumes that you have discovered the features from the objects and you are ready with the features. In this article, I will discuss a simple and popular clustering algorithm “K means clustering” to cluster the data/features. Let’s get started.

K means
Source: Google Images

K means algorithm:

Let’s say we have 1000 data points and each data point is a m dimensional vector. For easy visualization, assume that m is 2. If you can visualize, you have 1000 data points that are plotted on a 2D plot.
  1. Firstly, select the number of clusters(K) that you want. This can be chosen based on your domain knowledge or the best K can be automatically calculated. We will discuss this in the end.

  2. After selecting K, randomly select K data points from the data. These are your initial cluster centroids. We will update the cluster centroids until we get a good set of clusters. Hold for a minute, you will understand how to update them.

  3. Take a data point and calculate the distance from each cluster centroid. You will get K distances. Assign the current point to the cluster which has the minimum distance. Similarly, assign all the points to one of the clusters based on the distance. Distance metric can be Euclidean distance.

  4. Now, you have K clusters and each point is assigned to one of the clusters. But, these are not the final clusters. Using the current assignment, calculate the cluster centroids using the data points that are assigned to each cluster. We have updated the cluster centroids.

  5. Repeat the above points 3 and 4 until you don’t see much variance in the cluster centroids. After repeating the above steps for some iterations, you will observe that the centroids will become stable and don't change much.
We have separated the data points into K clusters. Sometimes, the second step of selecting the random cluster centroids may not be good. It completely depends on our luck. So, it’s better to do the entire process multiple times.

One of the main disadvantages of K-means clustering algorithm is K. We have to select the number of clusters before hand. This is really a difficult task for us. To find the optimal K, we can use the Elbow method which helps us to identify the number of clusters.

How to choose the number of clusters (k)?
  • We apply the K-means algorithm for different values of k. But, how to compare them? We need a single value metric to compare the best number of clusters.

  • For each k, we calculate the sum of squared distances within each cluster and add them. To explain it better, take all the data points in the cluster and calculate distance from the centroid of that cluster. Do the same thing for each cluster and add them. Finally, for each k, we have calculated Sum of squared distances.

  • Plot Sum of squared distances for each k. At some k, you will observe a bend in the plot which is the optimal k you are searching for. Please refer to the below plot.
Source: Google Images

Now, you have understood how K means clustering algorithm work. As a next step from here, you can read DBSCAN clustering algorithm, which is also one of the most popular clustering algorithms.

Thank you so much for reading my blog and supporting me. Stay tuned for my next article. If you want to receive email updates, don’t forget to subscribe to my blog. If you have any queries, please do comment in the comment section below. I will be more than happy to help you. Keep learning and sharing!!

Follow me here:
GitHub: https://github.com/Abhishekmamidi123
LinkedIn: https://www.linkedin.com/in/abhishekmamidi/
Kaggle: https://www.kaggle.com/abhishekmamidi
If you are looking for any specific blog, please do comment in the comment section below.
Labels:

Comments

  1. farenochsnerNovember 7, 2022 at 7:31 PM

    One of the best combo options is FOX Bet’s on-line on line casino, which is contained contained in the FOX Bet PA sportsbook app and offers each sports betting and on-line on line casino options in Pennsylvania. Contrary to in style perception, the best on-line casinos offer far more than just slots. There is an effective customer support environment with phone and e-mail options obtainable. The site also contains a live chat service, however https://thekingofdealer.com/jumbo-casino/ only registered gamers can entry it.

    ReplyDelete
  2. balerdullmannNovember 9, 2022 at 4:51 PM

    Stadium desk video games have video stations with stay dealers additionally out there at some places. The pace of other players impacts the general game pace for video and stadium 토토사이트 gaming. Some have $1 9/6 Double Double Bonus, 15/9 Deuces Wild and 9/5 Jacks or Better. There is broad variety|all kinds} of high quality $1 and $5 video poker video games at Lady Luck.

    ReplyDelete

Post a Comment

Popular posts from this blog

Google Colab - Increase RAM upto 25GB

Written by Abhishek mamidi, on
Google colab is a free jupyter notebook that is hosted on Google cloud servers. We can use CPU, GPU and TPU for free. It helps you to write and execute your code. You can directly access this through your browser. If you want to use Google Cloud/AWS, it requires hell lot of setup. You have to spin a cluster, create a notebook and then use it. But, Google colab will be readily available for you to use it. You can also install libraries from the notebook itself. These notebooks are very useful for training large models and processing huge datasets. Students and developers can make use of this because it’s very difficult for them to afford GPUs and TPUs. I was trying to run a memory heavy job. The notebook crashed. Then, I came to know how I can increase the RAM. So, I thought of sharing it in my blog. There are some constraints with the notebook. You can run these notebooks for not more than 12 hours and you can use only 12 GB RAM. There is no direct method or button t
20 comments
Read more

Skills required to become a Data Scientist

Written by Abhishek mamidi, on
Data Science is one of the hottest areas in the 21st century. We can solve many complex problems using a huge amount of information. The way electricity has changed the world, information helps us to make our lives easier and comfortable. Every second, an enormous amount of data is being generated. The data may be in the form of text, image, speech or tabular. As there is a lot of growth in the field of Data Science, in recent years, most of the companies have started building their own Data Science teams to get benefited from the information they have. This has created a lot of opportunities and demand for Data Science in different domains. For the next 5+ years, this demand would continue to increase. If we have the right skills, companies are ready to offer salaries more than the market standards. So, this is the right time to explore and gain skills which enables you to enter into this field. We have discussed the importance and demand for data science in the market. Let’s disc
20 comments
Read more

Top 35 frequently asked Data Science interview questions

Written by Abhishek mamidi, on
Interviews are very stressful. We should prepare for the worse. So, we have to plan accordingly in order to crack them. In this blog, you will get to know the type of questions that will be asked during the interview. It also depends on the experience level and the company too. This blog is mainly focused on entry-level Data Science related jobs. If you haven’t read my previous blog-posts, I highly recommend you to go through them: Skills required to become a Data Scientist How to apply for a Data Science job? First of all, you must be thorough with your resume, mainly your Internship experience and academic projects. You will have at least one project discussion round. Take mock interviews and improve your technical and presentation skills, which will surely help in the interviews. Based on my experience, I have curated the topmost 35 frequently asked Data Science questions during the interviews. Explain the Naive Bayes classifier? In case of Regression, how do y
19 comments
Read more

My Data Science Journey and Suggestions - Part 1

Written by Abhishek mamidi, on
I always wanted to share my detailed Data Science journey. So, I have divided the whole journey from BTech first year to final year into 3 parts. I will share everything, without leaving a single detail, starting from my projects, internships to getting a job. You can follow the path that I have followed if you like my journey or create your own path. In 2015, I got a seat in Electronics and Communication Engineering (ECE), IIIT Sri City through IIT JEE Mains. Because of my rank in JEE Mains, I couldn’t get into the Computer Science department. I wanted to shift to Computer Science after my first year, but couldn’t due to some reasons. In our college, we have only two branches, CSE and ECE. For the first three semesters, the syllabus was the same for both the departments except for a few courses. This helped me to explore Computer Science. In the first 3 semesters, I took Computer Programming, Data Structures, Algorithms, Computer Organization, Operation Systems courses, wh
9 comments
Read more

Exploratory Data Analysis and Data Preprocessing steps

Written by Abhishek mamidi, on
Exploratory Data Analysis is the foremost step while solving a Data Science problem. EDA helps us to solve 70% of the problem. We should understand the importance of exploring the data. In general, Data Scientists spend most of their time exploring and preprocessing the data. EDA is the key to building high-performance models. In this article, I will tell you the importance of EDA and preprocessing steps you can do before you dive into modeling. I have divided the article into two parts: Exploratory Data Analysis Data Preprocessing Steps Exploratory Data Analysis Exploratory Data Analysis(EDA) is an art. It’s all about understanding and extracting insights from the data. When you solve a problem using Data Science, it is very important to have domain knowledge. This helps us to get the insights better according to the business problem. We can find the magic features from the data, which boost the performance. We can do the following with EDA. Get comfortable with
13 comments
Read more

Building ML Pipelines using Scikit Learn and Hyper Parameter Tuning

Written by Abhishek mamidi, on
Data Scientists often build Machine learning pipelines which involves preprocessing (imputing null values, feature transformation, creating new features), modeling, hyper parameter tuning. There are many transformations that need to be done before modeling in a particular order. Scikit learn provides us with the Pipeline class to perform those transformations in one go. Pipeline serves multiple purposes here (from documentation ): Convenience and encapsulation : You only have to call fit and predict once on your data to fit a whole sequence of estimators. Joint parameter selection : You can grid search over parameters of all estimators in the pipeline at once (hyper-parameter tuning/optimization). Safety : Pipelines help avoid leaking statistics from your test data into the trained model in cross-validation, by ensuring that the same samples are used to train the transformers and predictors. In this article, I will show you How to build a complete pi
11 comments
Read more

SHAP - An approach to explain the output of any ML model (with Python code)

Written by Abhishek mamidi, on
Can we explain the output of complex tree models? We use different algorithms to improve the performance of the model. If you input a new test datapoint into the model, it will produce an output. Did you ever explore which features are causing to produce the output? We can extract the overall feature importance from the model, but can we get which features are responsible for the output? If we use a decision tree, we can at least explain the output by plotting the tree structure. But, it’s not easy to explain the output for advanced tree-based algorithms like XGBoost, LightGBM, CatBoost or other scikit-learn models. To explain the output for the above algorithms, researches have come up with an approach called SHAP. SHAP (SHapley Additive exPlanations) is a unified approach to explain the output of any machine learning model. SHAP connects game theory with local explanations, uniting several previous methods and representing the only possible consistent and locally accurate ad
2 comments
Read more

Latent Dirichlet Allocation - LDA (With Python code)

Written by Abhishek mamidi, on
Latent Dirichlet Allocation, also known as LDA, is one of the most popular methods for topic modelling. Using LDA, we can easily discover the topics that a document is made of. LDA assumes that the documents are a mixture of topics and each topic contain a set of words with certain probabilities. For example, consider the below sentences: Apple and Banana are fruits. I bought a bicycle recently. In less than two years, I will buy a bike. The colour of the apple and bicycle are red. The output of LDA would look like this: Topic 1 : 0.7*apple + 0.3*banana Topic 2 : 0.6*bicycle + 0.4*bike Sentence 1 : [(Topic 1, 1), (Topic 2, 0)] Sentence 2 : [(Topic 1, 0), (Topic 2, 1)] Sentence 3 : [(Topic 1, 0.5), (Topic 2, 0.5)] Please note that the above probabilities are made up numbers for intuition. To extract the topics and probability of words using LDA, we should decide the number of topics (k) beforehand. Based on that, LDA discovers the topic distribution of docum
6 comments
Read more

A year of experience as a Data Scientist

Written by Abhishek mamidi, on
On June 3rd 2019, I joined ZS Associates as a Data Scientist after graduating from IIIT SriCity. It was my first job and was very happy to get placed as a Data Scientist through lateral hiring. If you haven’t read my Data Science journey, please read it here :) After joining, I had some awesome moments that I never experienced since childhood. I got a chance to stay in a 4 star or 5 star hotel multiple times. I got a chance to travel by flight. I travelled to Pune, Delhi and Bangalore. I saw Vizag, Pune, Delhi and Bangalore airports in less than six months. I loved it. A few office parties, outings during Diwali and New year celebrations. Above are some of the moments that I can never forget in my life. My first job allowed me to experience these first time moments. Enjoying life is more important than anything. If you don’t enjoy your life, you cannot achieve anything big. Okay, let’s go into the main topic in detail. Me (inner voice during BTech):
30 comments
Read more

Complete Data Science Pipeline

Written by Abhishek mamidi, on
Data Science is not just modelling. To extract value out from Data Science, it needs to be integrated with business and deploy the product to make it available for the users. To build a Data Science product, it needs to go through several steps. In this article, I will discuss the complete Data Science pipeline. Steps involved in building a Data Science product: Understanding the Business problem Data Collection Data Cleaning Exploratory Data Analysis Modelling Deployment Let us discuss each step in detail. Understanding the business problem: We use Data Science to solve a problem. Without understanding the problem, we can’t apply data science and solve it. Understanding the business is very important in building a data science product. The model which we build completely depends on the problem we are solving. If the requirement is different, we need to adjust our algorithm such that it solves the problem. For example, if we are build
10 comments
Read more