Skip to main content

Hierarchical clustering algorithm


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.

This article is organized as follows:
  • Introduction
  • Divisive and Agglomerative clustering
  • Agglomerative clustering
  • K means vs Hierarchical clustering
Introduction:

Hierarchical clustering is one of the most popular clustering algorithms. This algorithm builds a hierarchy of clusters. There are two different methods of hierarchical clustering, Divisive and Agglomerative. Please refer to the below image to get a sense of how hierarchical clusters look.

Hierarchical clustering

Divisive and Agglomerative clustering:

The divisive method is a top-down clustering method in which we assign all the data points to a single cluster. We divide the single cluster into two and we go on dividing the sub-clusters until we reach n clusters (each cluster having a single data point).

The agglomerative method is a bottom-up clustering method in which we assign all the data points to different clusters. Initially, we have n clusters each having a single data point. We combine clusters until all the data points belong to a single cluster.

Hierarchical clustering - Divisive vs Agglomerative methods

Our main focus of this article is Agglomerative hierarchical clustering method. Let’s discuss in depth.

Agglomerative clustering:

As I discussed before, this is a bottom-up method. If you observe the diagram, we start from down where all the data points are separate and as we go up we combine the data points into clusters until we get a single cluster. Let’s discuss the algorithm.
  1. Assign all data points into separate clusters (n clusters). To understand better, let’s assume n=6 and the data point is represented using an m dimensional vector.

  2. Find the most similar clusters (let’s say p1, p2). We combine them into a cluster. Initially, we had 6 clusters, now we have 5 clusters [(p1, p2), p3, p4, p5].

  3. Repeat step 2, (n-1) times. In this case, we repeat 5 times to get hierarchical clusters that were shown in the diagram.
Hierarchical clustering - Different k values

Here is the step by step process of hierarchical clustering for the example shown in diagram:
  1. [p1, p2, p3, p4, p5, p6] → 6 clusters
  2. [(p1, p2), p3, p4, p5, p6] → 5 clusters
  3. [(p1, p2), p3, (p4, p5), p6] → 4 clusters
  4. [(p1, p2, p3), (p4, p5), p6] → 3 clusters
  5. [(p1, p2, p3, p4, p5), p6] → 2 clusters
  6. [(p1, p2, p3, p4, p5, p6)] → 1 cluster
Hierarchical clustering k=3

Challenges:
There are two challenges here and you must have thought about those.
  • Which metric to use for calculating the similarity between two clusters?
  • How to calculate the similarity between clusters? There are many cases possible here. If each cluster has only one data point, we can easily calculate similarity. If we have 3 data points in a cluster, and you are calculating the similarity with another cluster having only one single data point. The solution is to represent a cluster with a single vector or data point.

Which metric to use?
We can use Euclidean distance or Manhattan distance as a metric to calculate the distance between the clusters. We have to choose a metric based on the use case.

How to calculate the similarity between clusters?
There are three different methods:
  • Single linkage: In single linkage hierarchical clustering, the distance between the two clusters is the shortest distance between two points (one point from the first cluster and the other from the second cluster). For example, you have 2 points in the first cluster and 3 points in the second cluster. There are 6 combinations. Now, calculate the distance between all combinations using the chosen metric. You have calculated 6 distances. The lowest number of the 6 numbers is the similarity between the two clusters.

  • Complete linkage: In complete-linkage hierarchical clustering, the distance between the two clusters is the longest distance between two points (one point from the first cluster and the other from the second cluster). Consider the above example, the largest number of the 6 numbers is the similarity between the two clusters.

  • Average linkage: In average linkage hierarchical clustering, the distance between the two clusters is the average distance between all combinations of points (one point from the first cluster and the other from the second cluster). Consider the above example, calculate the average of all the 6 numbers. The average number is the similarity between the two clusters.
Now, read the above 3 steps to connect all the dots and to understand the algorithm better.

K means vs Hierarchical clustering:

If you don’t know the K-means clustering algorithm, I highly suggest you refer to this blog.
  • If we run K-means multiple times, we get different results. But, hierarchical clustering gives you the same results even if we run the algorithm multiple times. This is because in K-means we initialize the cluster centroids randomly.

  • K-means can handle big data. It takes O(n). On the other side, hierarchical clustering cannot handle huge data because we have to calculate the distances between a huge number of combinations. The time complexity of hierarchical clustering is O(n^2).
There are many other clustering algorithms. You can read K-means and DBSCAN clustering algorithms as a next step.

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.

Comments

  1. Hello Abhishek, Why is it that Divisive Clustering is not more popular? And do you see some similarity in Divisive Clustering & Decision Tree?

    ReplyDelete

Post a Comment

Popular posts from this blog

Google Colab - Increase RAM upto 25GB

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

Skills required to become a Data Scientist

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

Top 35 frequently asked Data Science interview questions

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

My Data Science Journey and Suggestions - Part 1

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

Exploratory Data Analysis and Data Preprocessing steps

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

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

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

How to apply for a Data Science job?

Job search is one of the painful tasks. We have to invest a lot of time to get placed in one of the best companies, we were dreaming for. The demand for Data Scientists is increasing over the years, and we have to stand out of the crowd to get a job. In this post, I will guide you on “How to apply for a Data Science job?”. I have divided the blog post into the following: What are the skills required for a Data Science job? How to build a good Data Science profile/resume? What are the different ways of applying for a Data Science job? What are the skills required for a Data Science job? I have created a blog-post on “Skills required to become a Data Scientist”, last week. I would suggest going through the previous blog before you go to the next section. How to build a good Data Science profile/resume? After acquiring the necessary skills, it is required to maintain a good Data Science profile. Your presence on the social network makes a difference too. Some tips

Complete Data Science Pipeline

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

A year of experience as a Data Scientist

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):

Building ML Pipelines using Scikit Learn and Hyper Parameter Tuning

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