Agglomerative and Divisive Hierarchical Clustering Explained | Data Science Training | Edureka Live

Key Takeaways

hey so today's topic is agglomerative and divisive hierarchical clustering so where we will understand the foundation about you know what is this all about and we'll go through it and the topics are these particularly we'll understand what is clustering and what is hierarchical listing the types of hierarchical testing we have then their applications and the advantages and disadvantages of it so we do have uh you know a different course which is related to this particular which actually covers the topic which we are discussing today this is called data science with certification training where the objective of this training is we don't assume people to be very good in Python so we want to put a foundation for them so your first second and these are numbers are nothing but the modules so up to four modules you will have completely a foundation up to three if I want to put it correctly you will have Foundation completely on all the python things which is needed that means we expect user to be you know uh to cover all the basics and the foundation required in order to do data science stuff as well as ml so we'll cover up to third module and once third module is over you can assume that you will be able to do good programming in Python that's where we start on data science related stuff which is your fourth fifth and fourth fifth modules then we will start your journey into the machine learning so the rest of it is machine learning and the topic which we are going to discuss is comes under the ninth module which is part of unsupervised learning so please check this course in case you are interested to enroll because this covers about the python which is actually must technology for today's world as well as the machine learning and data science which are like a key Concepts which are key Technologies in order to get uh you know into job market today so what is clustering so clustering is basically given a set of objects dividing them into groups is called clustering it's like your fear farming groups it's called clustering so to give you a very simple example if I have given you a bunch of vegetables let's say I have given you Tomatoes I have given you radish I have given you brinjal and if I ask you can you divide the vegetable according to their particular vegetable type what you will do you will separate all the brinjal into one particular bucket and you will actually separate radiation to separate one and the other vegetable also so what you are doing exactly you are actually dividing these set of objects which are nothing but vegetables here into different different groups on what basis you have done into different different groups if you closely observe you know how a brinjal looks like if I take one vegetable as an example and based on that vegetable you know which one is similar to it and based on that you actually pick all the vegetables which are closer to that and actually will form the buckets you will not include radish into that because radish looks different and it's not similar to the brinjal as such clustering is exactly that just that I have given you an example which is like a household what but whatever example I have mentioned this exactly fits to what I have said if you remember this example clustering is all about that so what actually is clustering then so clustering is part of unsupervised machine learning so when I say unsupervised machine learning there will not be any guidance to say what is correct or what is wrong your algorithm has to go and figure out things that is what unsupervised learning it is as simple as if you do not have a trainer and if you learn concepts by yourself that is called unsupervised learning self learning is an example of unsupervised learning if I talk in terms of studies and clustering is one of that which means here you will not have any guidance on what to do the algorithm goes and figure out and tells you something that's what it means by unsupervised learning I'm not going deep because that's not the key topic today but clustering understand it's part of unsupervised learning and what it does it just forms groups that groups are nothing but we will call cluster CR and how it forms go back to the vegetable example based on this similarity like if you take a vegetable example which I have mentioned each brinjal you know that other brinjals which look similar based on its color or based on its shape you know how the brinjal looks like so you know the similarity between that that's how you group it that's exactly what happens in clustering also in clustering what they do is when given a set of objects that could be your data set records whatever they know they take one particular object and based on that object they find out which objects are similar to that and how they find that similarity is using different different similarity images you can have euclidean similarity you can have euclidean measure you can have Manhattan measure or you have cosine similarity different different similarity for different different examples cosine similarities one we will popularly use for document clustering what not so for each use case based on I mean where it actually fits in you use different similarities that's the whole objective but generally since we humans are very much knowledge because we have been perceiving things for a long time we can easily recognize that means we can easily find the similar objects so and how it forms clusters if you see is like the way the clustering definition if you really look at a textbook it is like this clustering is nothing but forming a set of object into different clusters based on how much similar how based on in a way that the objects in the cluster will be very closer or very much similar then the objects in other cluster where they will be completely dissimilar or different that means in a cluster if you take the set of objects so if you consider this circle and these two as three objects and this circle and these two has two objects the objects in this trees to three objects in this cluster are very close that means they will have very much closer similarity compared to the objects in other cluster where they will be very much dissimilar which means what there will be the objective of always the clustering part is to minimize the similar to maximize the similarity between the objects in cluster and minimize the similarity between the objects in different clusters that's what the aim is and what are the algorithms that help you to Cluster the data is these are the ones K means DB scan main shift clustering hierarchical clusting and today's topic is all about hierarchical clustering so what exactly is hierarchicalistic so hierarchy means something like uh when you say in offices or corporate world or any business organization you have a hierarchy where there is a CEO underco there are directors or vice presidents under vice president there are directors and the directors there will be senior managers under senior managers there are managers under managers there are Again Estate managers understand manager there again tech leads other tech leads there are employees so if you see this is a hierarchy hierarchy is nothing but from a top level you keep on going until you touch the branch which is here in this case an individual employee I mean that is the hierarchy part hierarchical string exactly looks like that if you look at so you see this is hierarchical clustering actually and this one is also hierarchical trusting so where you start from top and keep you know you can see like this now what has actually hierarchical testing happened hierarchical clustering if you look at it actually forms something called um something called different it actually does something called a bottom-up clustering in again hierarchical string you have again two types of it one is agglomerative clustering another is divisible clustering agglomerative clustering follows something called bottom-up and divisive cluster follows something called top down I will tell you how it is so if you look at so this is Agnes which is called agglomerative clustering Agnes means agglomerative nested clustering why it is called agglomerative nested clustering is the way clustering happens in agglomerative clustering is first they will take let's say You have given 10 objects so first the what we're able to do is one object if they will take one object they will find out which is similar to it and whichever is similar to it they will form one group though two objects into one group now you are left with eight more objects now these two they will see for these two whatever is similar again there will be one more object coming in that means three so if you see these two forming into one or cluster the one cluster or group again you will see one more object which is similar there will be one more cluster so it keeps nesting like just like a concentric circles it keeps nesting and finally it will go to a point where all the points are merged into all the points are matched or you can say simply until there is a single cluster is obtained where it actually forms this contracts concentric Circle and that's the reason why it is called Agnes agglomerative nested clusting because if you see we keep nesting right two points again here will be one more Point again if you form one more group one more point so it keeps going like that so that's how accliminated clustering works and this is the reason why it is called bottom up clustering because you start from the lower hierarchy start from one object and keeps joining the points which are closer and finally goes to a point where only single is that that's why it is bottom up you start from one point and keeps going until all the all the objects are finished if I look it in a hierarchy actually in agglomerative clustering you start like this you start from the smallest point you see which two are similar you join them and which one is similar you join under that again these two which one is your owner you join into that again these two which is closer to what again so finally you will form one cluster where it is merged with all this button in a state structure that is called bottom of clustering so it is exactly like this so if you see you actually started with some category here to match these two people then these two people and these two people one cluster these two people another cluster finally this cluster and disk cluster will have similarity and this will form one cluster again this cluster will have similarity with n more people which is jobless so these two clusters will be similar and again these two clusters will be similar to this so there is one big cluster formed the same thing here also and finally you boil down to one place where everything is into one cluster that's how you go up so if you see you are going from bottom and up to a point where only single cluster is there to merge so you keep going up to like that that's why it is called bottom up approach or bottom up clustering now how the way it works is like this the same way I said like these are different different set of objects if you see they are individually separated earlier after that any step what would happen is the Clusters whichever is similar they will form different different clusters and they keep doing it until all these clusters are formed until all this different sub clusters formed into one single cluster that means these all some way or other will be merged into one single cluster select this you see finally these three are merged into one cluster these three into one book cluster now finally everything get boiled down into one cluster so if you see we are starting from a lowest level and going to a point where everything belong to one single cluster that's why it is called bottom-up approach and that's how agglomerative clustering works now coming to another hierarchical clustering which is called divisive clustering it works in the reverse way of what agglomerative cluster works division clustering uh so this is the way so for divisible clustering if you look at it's called Diana Diana is simply divisive analysis that's why it is called divisive clustering so it keeps dividing things so what it will do is it will start from Top it will not start from bottom it will start from top and keeps breaking things like one thing it will break into two different clusters and this cluster will be broken into two this cluster will be broken into two and this cluster if there is another separation it will keep going so from top to bottom if it comes that is called divisive cluster this is also hierarchy just the way it works is reverse order then what we have seen in agglomerative clustering see clustering continues until small groups of similar customers as a print so in the earlier the objective is agglomerative clustering keeps happening until everything becomes one single cluster whereas in this case the clustering keep and happening until there are small groups of small clusters are uptight so just the reverse thing so if you see here this is divisive clustering where if you remember in agglomerative clustering we started from here we went up to top that's why it is top down sorry bottom up whereas in regular division of clustering we start from top and we keeps breaking into things so that the small groups of clusters are formed it is top down so the way it works is let's say everything is considered if all the objects initially given it is considered as one single cluster and after that it will be broken into two clusters where the two clusters the items inside one cluster will be very much similar than the items in the other cluster then further they will be taken into again multiple clusters within that cluster again it will be boiled on into this cluster so finally if you see the small groups of clusters are operating that is the whole objective of deficit clustering so if you look at your agglomerative is like a bottom up your division is like top down from Top you will start and go down agglomerative you start from bottom and go up so now the question so now the question is we are talking about okay objects we are adding similar to objects we will put up in the one cluster and all but what is the similarity how what is the similarity like if you may if you see like the example the vegetable type example brinjal I have said since as a human we are intelligent we can easily identify it whereas in this case since these are all objects and in programming we have to implement we use some kind of similarity measures some kind of mathematical functions you can call it which actually help us to identify the similarity between these objects now that's what we are going to talk about it here now based on the similarity whether it is a single linkage or complete linkage you will have a similarity of plane by calculating the distance between the Clusters now like I mentioned earlier there are different cosine similarity similarity measures like euclidean Manhattan correlation cosine similarity all that and each one of them will be useful in one one situations like for document clustering if you want cosine stability is used so this is on single linkage where you see how to uh you know you see you try to understand if you want to Cluster the similarity between two clusters in single linkage you will identify one object with another whereas if you see complete linkage where this is what it happens the farthest one with the distance one in this cluster whereas this is again the centroid linkage centroid means the midpoint cluster prayer from that you will try to see what is the other centroid cluster in the other centroid object in the other cluster so that's how these types of clustering happens now what are the applications of hierarchical string so if you look at one application of hierarchical clustering is if you look at library research Library research is one of the good example of hierarchical clustering where let's say if I ask you to pick out Harry Potter Harry Potter book comes under something like a fantasy books if you look at library has set of books under setup books it will have different genre of books like fantasy entertainment food technology and all that so that is one hierarchy in that level again if you see under fantasy again fantasy again at different levels one fantasy could be pure scientific one fantasy could be pure something like a magic and all again you can have different Loops under that so again under that if you see maybe Harry Potter will fall under under fantasy all the magic things and all something like that or there could be another hierarchy for kids or adults something like that so if you see this particular structure completely gets into a hierarchical structure and for these applications a hierarchical agglomerative hierarchies clustering something like that really helps and each clustering also understand each clusting has its own disadvantages and advantages So based on the clustering you have to use the right one and there is no rule like this clustering works better or this clustering doesn't work better it all depends on the data set and the right set of algorithm you are using it now applications of hierarchy like a string if you look at you can use clustering in taxonomy uh which is like if you want to classify animal or plant kingdom based on their species or whatever this is for Animal Kingdom they are categorizing where for carnivorous they are categorizing into failure Leda and master Leda and Kennedy and again panthera meph status I mean these are all different different hierarchy if you look at so this is one application where you can identify a particular animal based on their species and get into that this is where you can apply hierarchical casting apart from that uh if you look at there is something called genes you might heard about genomes and all like how do people know that like for example you might have heard about covet right like kovid for example that's a kind of virus now how do they find the other virus or similar to covet again there this kind of clustering technique the similarity between this virus and that virus so all this technique will be used again even in this you might have seen they will conduct certain research and they will pick only certain animals in order to do research or certain kind of hybrid animals they want to produce so there also they do lot of similarity to understand what actually animal is fit for it and over all that all of that they actually apply some more other type of clustering there viral outbreaks like I said segmenting customers segmenting customers is like identifying customers based on their purchases that means let's say you are going to company uh websites where to buy something like it could be Amazon Flipkart and whenever you buy something and as a company head if I want to Target you how do I Target it can be it can be based on multiple parameters one parameter could be identifying all the customers who are actually doing a lot of uh sale a lot of buying in my website so that could be that I can put in one category called Allied customers because I want to treat them very good because they are giving a lot of business to Me Maybe another set of customers who are actually not very frequent but they are also giving good business to me so that is on time in terms of the revenue the business Revenue this customers are giving apart from that if you look at I can get into another category where identify customers based on their purchase choices when I say purchase choices I have to know like at what point I have to put certain products so that it can be sold I cannot put like for example a simple example is during festivals or Christmas if e-commerce if you see normal days e-commerce website will not be so much uh related to that festivals particularly if you see in India Diwali or in U.S Christmas these two festivals are very prominent in those particular countries now how do these companies know I have to put those products because they have studied that at this time these people will really going to buy and they actually Target customers in such a way so that those products are bought so the reason the the way the clustering applied there is they actually segment all the cluster customers who actually buy these products on during these festivals and whenever they go to their website they automatically personalize it when I say personalizing they don't need to search they will directly show hey you are searching for this product you see this it is already available something like that so to attract customer attention to buy the products that could be another category another category could be based on the choices you make when you're buying a web buying a particular product in a website something like every time you go to a website and you are a frequent visitor to website and let's say you're always buying cycles that means they will identify all the customers who buy similar uh kind of uh you know choices they have and they will also recommend you something which these guys like because the similarity between you and them is moreover similar there they are applying clustering at the same time they are recommending something which you might not be searching but the way the guesswork they have made is to because they have seen some other customers also have this similar choice so that's where also they apply clustering and finally they recommend that product using something called recommendation system all these Technologies are interlinked and they use it some way or other in order to identify the customers and similarly clustering Prime cities in the city so when it's a crime city like based on I mean you might have seen certain in city in country certain cities are identified like most uh you know uh crimes happening in that particular area or particularly even in the city you see one particular area we consider most of the crimes happen so how do you identify that it's based on the number of crimes happening it's based on the frequency of crimes happening that means what you are doing you are actually grouping that into a different cluster altogether so that also we can technologically identify that and phylogenetic trees it's more about identifying this protein Gene whatever and where they will identify which particular Gene is similar to the other Gene it could be in terms of animals it could be humans anything any species relation also you can easily derive using this clustering now what are the applications one thing it is easy to implement and understand if you look at hierarchical casting particularly agglomerative in agglomerative what we do we start from a single cluster and keeps merging clusters until we find everything is actually part of one single cluster that's what we do and here one more Advantage particularly with this agglomerative clustering whether it is a globality or divisive you don't need to give information about how many number of clusters you have to give that means you don't need to tell it about how many number of clusters or groups it has to generate we do have algorithms like k-means where you can input saying this many clusters I want but regardless of that if you don't give the algorithm can go by itself and identify and give you the number of clusters you want that is one thing why we can also call these algorithms unsupervised because you are not giving them any guidance of how many groups you can form if you leave them they can find out the number of clusters by themselves as well but certain times based on the data set knowledge or based on the problem domain understanding we do give some input saying I want this many groups or I want this many groups which is what we generally do in k-means clustering where the K means the input comes from the user and we will give that and you can also detect outlayers using this clustering because when you do clustering you can Auto automatically identify the ones which are not fitting into any of the groups that means they are the outliers like let's say even if I take numbers one two three four five let's say most of the numbers are falling between 1 to 10 and suddenly there is a num there are set of numbers who are between 90 to 100 now what will happen if I ask you to form a group of these numbers you will definitely come with 1 to 10 into one group 9 to 200 into another group because 90 to 100 has far more distance than this one to one ten numbers so we ourselves thinks that the 9 to 10 is like an outlier like something which you don't think most of these values fits in right outlays are like any value which is way more or Beyond than the trend of data are way more lesser than the actual data trade and that calls that can also be detected using Bliss questing method and it is deterministic and more predictable these algorithms let me see if there is a limitation given here yeah these are the limitations so agglomerative clusting even though they are very good when it comes to applying on large data sets these are not suitable enough and here one more problem is when you handle different size clusters when I say size clusters each cluster having the number of objects so that is also difficult here and these are very sensitive to outliers and noise that means if there are outlays or noise these can you can see some impact on these clustering methods so what generally people do because these algorithms have some kind of problems like this people mix up the algorithms what I mean by mix up the algorithms is agglomerative clustering since this has a problem so what people do is there is something called partitioning clustering they'll do something like a partitioning clustering before once the partition clustering gives the output based on the output they will apply another clustering algorithm so people actually mix up algorithm based on their use case just to give one real-time example which I have worked in my masters where we have created an algorithm a clustering algorithm using both partitioning and hierarchical because partitioning has a problem and hierarchical also has its own problem so what we actually derived or what we actually identified is if you actually mix up partitioning clustering with agglomerative hierarchical string it can be helpful in doing any kind of search it could be obtaining a book from a library when it's the data is in the form of hierarchy or in a web web in a web it can be obtaining uh it can be helpful to obtain a particular web page very very fast if there is a hierarchy already involved so these kind of cases when we actually apply the algorithm it actually completes in 25 percent of time that means let's say the normal time is one minute using whatever algorithm we have designed it will complete in 35 seconds not 25 seconds 15 seconds that means the time gets reduced because the way algorithm is applied it's different on the data and clusting if you see you can use it to apply on the web pages to identify the similar web pages and not only that if you see in Google search Google search also uses web disclosing where it will identify when you are searching for something based on your keyword it actually identifies which cluster it fits whether it's an entertainment or a fantasy or whatever it has its own identification methodology based on that it will actually pick up the track listing this all happens in order to reduce the search time for the user so there are different uh you know use cases and applications of these clustering so that's all I have thanks for your time see you bye