Lecture 23 : Part 2 - Machine Learning Algorithms-XVI

[Music] students now welcome back to this second part of this lecture and here we're talking about most of the things about Hier ecal clustering so please uh keep your attention on this so so far we have discussed about K means clustering and these are nothing but centroid approaches we guess the Central Point first in all this K means clustering whatever we discuss in the Blackboard in the board white board as well as here is basically it assumes the cent of each clusters that's a key problem of this so now then assign the point to the cluster based on the nearest neighbor distances now in case of hierarchical approaches We Begin assuming that each point is a cluster itself why do you do that and you know this mainly because we don't want to assign P assign or guess number of clusters at the beginning so after we assume every point is a cluster by itself we repeatedly Marge the nearby clusters using some measure of how close these clusters are it can be again distance or how good a cluster is resulting cluster how good a cluster the resting groups would be or a distance actually that's nothing but a distance so finally we apply the centroid concept but we have no assumptions at the beginning so in kin algorithm we choose the K cluster centroid first we pick that and assign point to the cluster by picking these distances like here suppose you have case two and you have to assign one 2 3 4 5 in that order that's what it is so then you have you decide there will be two clusters K so what you do we have one cluster here same thing here so you can see here we have designed one cluster there at the beginning then what happened then you measure this put the centers one Center here measure distance from one and three they become one cluster and then you can put another points here and see two and four are big to the Clusters instead of that if you have case two then we can put this Center here and you can see the distance will be similar then you have two clusters but you know assuming that may be wrong but you can clearly see there are three clusters here that's the problem of C's clustering so C clustering per forms is best if the data are well separated when data points are overlapped this clustering is not suitable and it is faster as compared to other compared to other clustering it provides strong coupling between the data points and C cluster do not provide any clear information regarding the quality of the Clusters these are all problems that's why C in clusters cannot be used forless and you know what you do in that first you initialize the K cluster conent Ides that ini assume that it's mu1 mu2 mu3 that's what you have done mu K and then repeat the distance calculations that's what we do and keep on doing the iterative things very simple elegant faster technique but the problem is this so you have to have a cluster assignment steps and cluster updating steps these are the two steps in the python modeling you will do that so these are the issues first you have to initialize and then you can split the data but having located the centroid of cluster then we can easily assign the data points so in comparison hierarchical clustering is a connectivity based clustering models that groups of data points together that are close to each other based on the measure of similarity or distance remember this so assumptions that assumption is that the that point that are close to each other are more similar related then the data points further away after that you create a dendrogram a tree like structure all of you know dendroides dendrogram is basically D structure Tre like structures which can give the information of hierarchy High relationship indiv data points are located at the bottom of the Dums while the largest clusters which include all the data points are look at the top very simple tree have a stem and the stem has other branches exactly same way so if you want to gener at different clber clusters then you can dis slice even dendrograms at different heights let's do that okay let's see that this is what is there are different subjects right I have not written that let's talk about subjects agriculture biology physics computer science space so you look at this this is taken from y.com agriculture can have dairy scops forestry Agronomy biology can be have botan cell biology Evolution biology physics can be many things I put only magnetism relativity computer science can be AI other courses are H also space can be craft or missions so how many are there 30 30 hierarchies are there right you can clearly see that if you make it properly so what you have done if you go back to here so it's like a dendrogram a Tre like structure and individual P points are look at the bottom of this drram right here you see individual transport the bottom of the dendrogram and largest clusters are put at the top what is that largest cluster lar clust is subjects that's put the top and you to generate these different number of clusters dendogram can be sliced you can slice the dendograms you can slice here you can slice here right you can slice it up and get a slice means this this is one slice if you want to generate slice here it is like this right this is called slice so basically it builds a tree based hierarchical taxonomy from a set of documents remember the basic approach is very simple recursive applications of partitional clustering this is basically taking a Rec animal can be vertebrate invertebrate vertebrates are fish reptile alpian okay mammals inverti bites can be warm insect crustacean then you can divide Fe into different categories different categories like that so that's what it is is built on basically tree based structure and recursive applications of parition L casting is used another one let's talk about all topics all topics can be anything right in the world but we have decided to make only fashion and sports and the sports you are interested in soccer and Tennis fashion two companies gusi and lacost right so you can build these clusters like that high clusters so hierarchy may be more nature it can be more natural different users might care about different levels of granity or different kinds of prunings okay you can cut it up use that so what is dendrogram then to give it very perspectives okay dendam is basically nothing but cutting the dendogram in Des level so this is B tree like structures okay that's what you should think about it it's a tree like structures so how do you do this uh uh G generation all these things we'll talk about a little bit before that let us talk about what are the two different types of clustering possible Hier clustering possible one is called agglomerated clustering so agative clustering other is called DBP clustering what is agative clustering it is also known as a bottom up clustering so there's a bottom up and top down so HSC is basically a bottom up clustering approach structure that is more informative than unstructured set of clusters return by flat clustering remember what is flat clustering right you don't remember so let us go back to Flat clustering again sometime we forget basically flat clustering is nothing but K means clustering type it starts with random partioning and then do it reply so what does it say here if I go back here h a structure that is more informative than the unstructured set of class clusters returned by flat clustering flat clustering give you set of clusters but that is less informative than HSC so therefore this clustering algorithm does not require us to specify PR pacify the number of clusters you don't require you can have every data point as one cluster bottom algorithm treats each data as a single turn cluster at the outset and then s successively agerate players of clusters are found in comparison HDC High divisive clustering is a top- down approach this algorithm does not require again to P specify number of clusters but top down cluster requires a method of splitting the Clusters that contains whole data so here you are basically splitting the top data from the top to bottom and this is every time this can be done by splitting cluster recursively until we have achieved the single turn clusters that's what so you split it up in case of top down in case of bottom approach you do it basically treats every data as a cluster just like a nanomaterial Ser have a top down and bottom approach in bottom approach you start with each molecule Join one by one and form a nanomaterials similarly here also a bottom approach each data point is consider single CL clusters at the beginning then successfully we can aerate the Clusters pair of clusters that's why it is called a bottom of approach start with a very bottom level atom level and then you join them together alate the sport atoms to form a clusters but in case of HDC uh this is a top down so basically you split the cluster that contain the whole data and proceeds by splitting the cluster securely okay so let's uh little bit talk about high how these Hier clusters work step one of high cluster is basically create is data point of single clusters correct let's talk let me go back to the board and talk about that so Step One is very simple in case of high clustering Step One is basically treat every treat every data remember we are discussing about h a okay agerate T every data [Music] points is data point as what single clust stke that's what is your first job so theose you have data point like this so each each data point is considered as a cluster single clusters then steps two what we do it steps to take two closes closest data points and March Marge to form one cluster so there will be now now n minus 1 clusters because one you have taken two together so let me explain you that let's take this two okay let me use different color red is pattern let's take this two these two are closest data point so March them into one clusters okay so that's what it is that's the steps two what is step three step three is very simple again take two closer clusters closest clusters two closest clusters and March them together to form another cluster what is in terms of that so I'll do again that let's talk about this two that's the step three correct so very easy to understand not very difficult the step four four step four is what repeat step three basically what you're doing repeating step two again and again repeat step three until only one cluster is left right that's what you do that's what you do so what you do is very simple here then so first we remove this we have done the repetition of step three so that you have only one clust only one data point statement right so then we are done almost so you have one more step what is that step step five step five is the last step what is the step five once all the cluster combine into big cluster develop the dendrogram once all clusters are combined develop the dendogram I discuss about dendogram there nothing but a d leg structure so these are the five steps you should do not more than that you can clearly see so these five steps are required so you have to develop a dendrogram and dendrogram is something which is which is giving you the nature of clusters right we have discussed about dendrograms quite a lot so few more important things we need to talk about it what is the measure of distance between the Clusters okay the closest distance between two points basically what is close the measure of distance the VAR types of ways to means to calculate the distances okay so you could clearly see now here how we me The Distance by meing the closest distance between these two points correct that's what you're doing but there are many ways of determining the distances possible let's talk about that because these are the algorithms first one is know as a single lineage so we'll discuss about that part little bit so I remove this hope you have taken down whatever written the different steps so how measure distance because that's what it is so there are different kinds of ways of distance first one is known as a single cluster single lineage sorry what is it if if you this is a shorted distance between the closest data points of the Clusters let's talk about this picture so let's talk about this this one clusters these are another clusters so you can clearly see the distance of this point and this point this is the closest distance a shorted distance so it talks about shortest distance between the closest points of the cluster okay that's what we have done we consider this point and this point these are the closest points and find the distance between this is single lineage one one link only that's why I single lineage distance that's what is more important and widely used second one is what is known as a complete linkage sorry this is not a link lineage linkage I'm making a mistake linkage then you can have a complete linkage second one what is it it is the Fest farthest distance between the two points so farthest distance so if I have to draw the same thing here this is one cluster then another clusters this is talking about the farthest distance right so this point and this point that's what it is for the distance between the two points of the two different clusters it it is one of the popular very popular linkage methods so remember what we doing when you want to form this high hierarchal hierarchal you know clusters we can either do a single linkage or you know further dist linkage that means they are part of two different uh you know hierarchies in the dendron structure you can have also have much more complex things possible so let's talk about that you can have centroid linkage also possible centroid that is very simple what we discussed already so let me just draw it so this is the centroid let's say of this cluster this is Center of this clusters this distance what is called Central linkage so these are a different linkage we used in the to get the dendron okay am I clear so by using these different kinds of linkage one can find the dendrin okay remember the clustering was done as we discuss already considering the each point as a cluster and do that so HSC basically works on that so once you have done that then you can easily form the dendron nicely you can easily form the dendron structures that's the key thing about in hierarchical clusters so as you know the hierarchical HSC starts with each dot as a this is a DOT basically not DOT in a separate cluster and then repeatedly join the closest pair and history of merging how we are merging the forms from the the tree or the dendrons instuctions in hierarchy so we we have talked about it both these top down and the bottom of approach again I'm telling you in top down which is nothing but divisive approach you partition the data into two groups first then do and do it again and again right just like in nanometal synthesis you TR a chalk break into pieces pieces pieces pieces to you achieve the nanomaterial same thing you do here okay you have the whole data partition into two groups and bottom of approach basically starts with every points in one cluster and then you march actually the closest data points so remember these aspects well I I just wanted to tell you the the mechanism of distance to finish it up again so normally we use equum distance but you have already seen we can use Manhattan we can use you know minus key or we can use even quadratic G Square many other distance Ty matrixes in the literature so what you have learned uh in in today lecture is quite a lot right you learned the kin algorithm and hierarchal algorithm now if I go back uh different kinds of algorithms yes so we have discussed about CID based algorithms Conn based algorithms densi has similarity like Cent algorithm so basically it finds groups based on the density of data points then dity is number think number density how many data points are there per unit area per unit volume that's what is used that's much easy to measure right you can count and find out the volume find out the area and do that so what needs to be done in the next class is basically this distribution ver clustering okay we'll talk about a little bit in 5 10 minutes in the next lecture about distribution of clustering and then we move ahead so with this let me stop here I hope you'll enjoy uh this kind of descriptions of mathematics and the you know geometrical things to understand the whole clustering thank you [Music] [Music] [Music]