Clustering with DBSCAN, Clearly Explained!!!

Key Takeaways

dp scan clusters just like a person can statquest [Music] hello i'm josh starmer and welcome to statquest today we're going to talk about clustering with db scan and it's going to be clearly explained now imagine we collected weight and height measurements from a bunch of people and we plotted the people on a two-dimensional graph like this where we have weight on the x-axis the first dimension and height on the y-axis the second dimension by eye we can see two different clusters by identifying two different but relatively dense clumps of people in contrast these people that are far from everyone else look a little bit like outliers so by eye clustering this data is pretty easy however because these clusters are nested meaning the green cluster wraps around the blue cluster a relatively standard clustering method like k-means clustering might have difficulty identifying these two clusters instead because of the nesting a simple clustering method might get something weird like this where these points are assigned to the blue cluster even though they look like they belong to the green cluster so we need a clustering algorithm that can handle nested clusters also remember this two-dimensional graph only uses weight and height data but if we wanted to include each person's age we would have to add a third axis and now our graph is three-dimensional drawing a three-dimensional graph on a two-dimensional computer screen is awkward but possible however if we wanted to include four or more features we'd need to draw a four or more dimensional graph and that's not possible and if we can't draw and look at a four or more dimensional graph then we need a way to identify nested clusters that we cannot see by eye the good news is that there are clustering algorithms that can identify nested clusters in high dimensions one of these algorithms is called db scan and that's what we'll talk about today so let's go back to the original two-dimensional graph and see how db scan tries to mimic what we can easily do by eye now remember by eye we identify clusters by the densities of the points clusters are in high density regions and outliers tend to be in low density regions so let's see how dbscan uses the densities of the points to identify these two clusters bam now starting with the raw unclustered data the first thing we can do is count the number of points close to each point for example if we start with this red point and we draw an orange circle around it then we can see that the orange circle overlaps at least partially eight other points so the red point is close to eight other points note the radius of the orange circle is user defined so when using dbscan you may need to fiddle around with this parameter now this red point is close to five other points because the orange circle overlaps at least partially five other points this red point is close to six other points and this red point is close to seven other points this red point is only close to two other points and this red point is not close to any other point because the orange circle does not overlap anything else likewise for all the remaining points we count the number of close points now in this example we will define a core point to be one that is close to at least four other points note the number of close points for a core point is user defined so when using db scan you might need to fiddle with this parameter as well anyway these four points are some of the core points because their orange circles overlap at least four other points hooray but neither of these points are core points because their orange circles do not overlap four or more other points ultimately we can call all of these red points core points because they are all close to four or more other points and the remaining points are non-core now we randomly pick a core point and assign it to the first cluster next the core points that are close to the first cluster meaning they overlap the orange circle are all added to the first cluster then the core points that are close to the growing first cluster join it and extend it to other core points that are close by here we see two core points and one non-core point that are all close to the growing first cluster and at this point we only add the core points to the first cluster that said eventually we will add this non-core point but right now we are only adding core points ultimately all of the core points that are close to the growing first cluster are added to it and then used to extend it further bam note at this point every single point in the first cluster is a core point and because we can no longer add any more core points to the first cluster we add all of the non-core points that are close to the core points to the first cluster for example this point which is a non-core point is close to a core point in the first cluster so we add it to the first cluster however because this is not a core point we do not use it to extend the first cluster any further that means that this other non-core point which is close to the non-core point that was just made part of the first cluster will not be added to the first cluster because it is not close to a core point so unlike core points non-core points can only join a cluster they cannot extend it further now we add all of the non-core points that are close to core points in the first cluster to the first cluster and now we are done creating the first cluster double bam to summarize how the first cluster was formed we picked a random core point and it started the first cluster then neighboring core points joined and extended the first cluster [Laughter] and non-core points only joined the first cluster bam now because none of these core points are close to the first cluster they form a new second cluster because they are close to each other and the non-core points that are close to the second cluster are added to it lastly because all of the core points have been assigned to a cluster we're done making new clusters and any remaining non-core points that are not close to core points in either cluster are not added to clusters and called outliers and that is how the db scan algorithm works triple bam note as we just saw clusters are created sequentially that means if we had a non-core point close to both clusters then when we built the first cluster beep we would add this non-core point to the first cluster because it is close to a core point along with all of the other non-core points that were close and now that this point is part of the first cluster it is no longer eligible to be in any other cluster small bam now it's time for some shameless self-promotion if you want to review statistics and machine learning offline check out the statquest study guides at statquest.org there's something for everyone hooray we've made it to the end of another exciting stat quest if you like this stat quest and want to see more please subscribe and if you want to support statquest consider contributing to my patreon campaign becoming a channel member buying one or two of my original songs or a t-shirt or a hoodie or just donate the links are in the description below alright until next time quest on