{"id":1856,"date":"2019-07-31T06:24:37","date_gmt":"2019-07-31T06:24:37","guid":{"rendered":"http:\/\/kusuaks7\/?p=1461"},"modified":"2024-07-24T16:44:49","modified_gmt":"2024-07-24T16:44:49","slug":"an-introduction-to-big-data-clustering","status":"publish","type":"post","link":"https:\/\/www.experfy.com\/blog\/bigdata-cloud\/an-introduction-to-big-data-clustering\/","title":{"rendered":"An Introduction to Big Data: Clustering"},"content":{"rendered":"\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tINTRODUCTION\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tClustering is a Machine Learning technique that involves the grouping of data points. Given a set of data points, we can use a clustering algorithm to classify each data point into a specific group. In theory, data points that are in the same group should have similar properties and\/or features, while data points in different groups should have highly dissimilar properties and\/or features. Clustering is a method of unsupervised learning and is a common technique for statistical data analysis used in many fields.\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tThere are many different clustering models:\n
    \n \t
  • Connectivity models based on connectivity distance.<\/li>\n \t
  • Centroid models based on central individuals and distance.<\/li>\n \t
  • Density models based on connected and dense regions in space.<\/li>\n \t
  • Graph-based models based on cliques and their relaxations.<\/li>\n<\/ul>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\tIn this article, I will walk through 3 models: k-means (centroid), hierarchical (graph), and DBSCAN (density).\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t

    1\u200a\u2014\u200aK-MEANS CLUSTERING<\/h2><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\tThe simplest clustering algorithm is k-means, which is a centroid-based model. Shown in the images below is a demonstration of the algorithm.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\tWe start out with k initial \u201cmeans\u201d (in this case, k = 3), which are randomly generated within the data domain (shown in color).\u00a0k<\/em>\u00a0clusters are then created by associating every observation with the nearest mean. The partitions here represent the Voronoi diagram generated by the means. The centroid of each of the\u00a0k<\/em>\u00a0clusters becomes the new mean. Steps 2 and 3 are repeated until convergence has been reached.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\tThe pseudocode of k-means clustering is shown here:\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\tExample<\/strong>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\tThere are 9 points, including (1, 2), (1, 3), (2, 3), (2, 4), (4, 6), (5, 6), (6, 6), (6, 8), (7, 7). We will create 2 random centroids in the orange X marks at coordinates (2,8) (centroid 1) and (8, 1) (centroid 2). We will choose k = 2 and use the Manhattan distance to calculate the distance between points and the centroids. We would have the following results of the centroid distances:\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\tSo data point (1, 2) is 7 units away from centroid 1 and 8 units away from centroid 2; data point (1, 3) is 6 units away from centroid 1 and 9 units away from centroid 2; data point (2, 3) is 5 units away from centroid 1 and 8 units away from centroid 2, and so on. Using this data, we can subsequently update our centroids. Remember that the old centroids are (2, 8) and (8, 1), we have the new centroids as (4, 5) and (2, 2) as demonstrated by the green X marks.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\tIf we keep calculating the Manhattan distance of each data point with respect to these 2 new centroids, we\u2019ll end up with another table results:\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\tUsing this data we can update our old centroids in orange X marks from (4, 5) and (2, 2) to new centroids in green X marks from (6, 7) and (1, 3), respectively.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\tFinally, we repeat this whole process one more time to get the results table.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\tAt this time, our new centroids overlap with old centroids at (6, 7) and (1, 3). Thus, the algorithm stops.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\tWhen choosing hyper-parameter k (the number of clusters), we need to be careful to avoid\u00a0overfitting<\/strong>. This occurs when our model is too closely tied to our training data. Usually, a simpler model is better to avoid overfitting.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\tThe correct choice of\u00a0k<\/em>\u00a0is often ambiguous, with interpretations depending on the shape and scale of the distribution of points in a data set and the desired clustering resolution of the user. In addition, increasing\u00a0k<\/em>\u00a0without penalty will always reduce the amount of error in the resulting clustering, to the extreme case of zero error if each data point is considered its own cluster (i.e., when\u00a0k <\/em>equals the number of data points,\u00a0n<\/em>). Intuitively then,\u00a0the optimal choice of<\/em>\u00a0k\u00a0will strike a balance between maximum compression of the data using a single cluster, and maximum accuracy by assigning each data point to its own cluster<\/em>. If an appropriate value of\u00a0k<\/em>\u00a0is not apparent from prior knowledge of the properties of the data set, it must be chosen somehow. There are several categories of methods for making this decision.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\tThe\u00a0sum of squared errors<\/strong>\u00a0is a good evaluation metric to choose the number of clusters. It is calculated based on the equation below. Essentially, we want to choose k such that we can minimize SSE.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\tThe average\u00a0silhouette<\/strong>\u00a0of the data is another useful criterion for assessing the natural number of clusters. The silhouette of a data instance is a measure of how closely it is matched to data within its cluster and how loosely it is matched to data of the neighboring cluster, i.e. the cluster whose average distance from the datum is lowest. A silhouette close to 1 implies the datum is in an appropriate cluster, while a silhouette close to \u22121 implies the datum is in the wrong cluster. Optimization techniques such as genetic algorithms are useful in determining the number of clusters that give rise to the largest silhouette. It is also possible to re-scale the data in such a way that the silhouette is more likely to be maximized at the correct number of clusters.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\tThus, the average silhouette value is 0.72.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t

    2\u200a\u2014\u200aHIERARCHICAL CLUSTERING<\/h2><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\tBroadly speaking there are two ways of clustering data points based on the algorithmic structure and operation, namely agglomerative and divisive.\n
      \n \t
    • Agglomerative:<\/strong>\u00a0An agglomerative approach begins with each observation in a distinct (singleton) cluster, and successively merges clusters together until a stopping criterion is satisfied.<\/li>\n \t
    • Divisive:<\/strong>\u00a0A divisive method begins with all patterns in a single cluster and performs splitting until a stopping criterion is met.<\/li>\n<\/ul>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
      \n\t\t\t\t
      \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
      \n\t\t\t\t
      \n\t\t\t\t\t\t\t\t\tHierarchical clustering is an instance of the agglomerative or bottom-up approach, where we start with each data point as its own cluster and then combine clusters based on some similarity measure.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
      \n\t\t\t\t
      \n\t\t\t\t\t\t\t\t\tThe key operation in hierarchical agglomerative clustering is to repeatedly combine the two nearest clusters into a larger cluster. There are three key questions that need to be answered first:\n
        \n \t
      • How do you represent a cluster of more than one point?<\/li>\n \t
      • How do you determine the \u201cnearness\u201d of clusters?<\/li>\n \t
      • When do you stop combining clusters?<\/li>\n<\/ul>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
        \n\t\t\t\t
        \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
        \n\t\t\t\t
        \n\t\t\t\t\t\t\t\t\tBefore applying hierarchical clustering let\u2019s have a look at its working:\n
          \n \t
        1. It starts by calculating the distance between every pair of observation points and store it in a distance matrix.<\/li>\n \t
        2. It then puts every point in its own cluster.<\/li>\n \t
        3. Then it starts merging the closest pairs of points based on the distances from the distance matrix and as a result, the amount of clusters goes down by 1.<\/li>\n \t
        4. Then it recomputes the distance between the new cluster and the old ones and stores them in a new distance matrix.<\/li>\n \t
        5. Lastly, it repeats steps 2 and 3 until all the clusters are merged into one single cluster.<\/li>\n<\/ol>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
          \n\t\t\t\t
          \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
          \n\t\t\t\t
          \n\t\t\t\t\t\t\t\t\tIn hierarchical clustering, you categorize the objects into a hierarchy similar to a tree-like diagram which is called a\u00a0dendrogram<\/em><\/strong>. The distance of split or merge (called height) is shown on the top line of the dendrogram below.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
          \n\t\t\t\t\t\t
          \n\t\t\t\t\t
          \n\t\t\t
          \n\t\t\t\t\t\t
          \n\t\t\t\t
          \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
          \n\t\t\t\t
          \n\t\t\t\t\t\t\t\t\tIn the left figure, at first\u00a0goat <\/em><\/strong>and\u00a0kid<\/em><\/strong>\u00a0are combined into one cluster, say cluster 1, since they were the closest in distance followed by\u00a0chick<\/em><\/strong>\u00a0and\u00a0duckling<\/em><\/strong>, say cluster 2. After that\u00a0turkey <\/em><\/strong>was merged in cluster 2, followed by another cluster of\u00a0duck<\/em><\/strong>\u00a0and\u00a0goose<\/em><\/strong>. We found another cluster consisting of\u00a0lamb<\/em><\/strong>\u00a0and\u00a0sheep<\/em><\/strong>, merging that into cluster 1. We keep repeating this until the clustering process stops.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
          \n\t\t\t\t
          \n\t\t\t\t\t\t\t\t\tThere are several ways to measure the distance between clusters in order to decide the rules for clustering, and they are often called Linkage Methods. Some of the common linkage methods are:\n
            \n \t
          • Complete-linkage<\/strong>: calculates the maximum distance between clusters before merging.<\/li>\n \t
          • Single-linkage<\/strong>: calculates the minimum distance between the clusters before merging. This linkage may be used to detect high values in your dataset which may be outliers as they will be merged at the end.<\/li>\n \t
          • Average-linkage<\/strong>: calculates the average distance between clusters before merging.<\/li>\n \t
          • Centroid-linkage<\/strong>: finds the centroid of cluster 1 and centroid of cluster 2, and then calculates the distance between the two before merging.<\/li>\n<\/ul>\nThe choice of linkage method entirely depends on you and there is no hard and fast method that will always give you good results. Different linkage methods lead to different clusters.\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\tExample<\/strong>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\tThe following example traces a hierarchical clustering of distances in miles between US cities. The method of clustering is\u00a0single-link.\u00a0<\/em>Let\u2019s say we have the input distance matrix below:\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\tThe nearest pair of cities is BOS and NY, at distance 206. These are merged into a single cluster called \u201cBOS\/NY\u201d. Then we compute the distance from this new compound object to all other objects. In single link clustering, the rule is that the distance from the compound object to another object is equal to the shortest distance from any member of the cluster to the outside object. So the distance from \u201cBOS\/NY\u201d to DC is chosen to be 233, which is the distance from NY to DC. Similarly, the distance from \u201cBOS\/NY\u201d to DEN is chosen to be 1771.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\tAfter merging BOS with NY:\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\tThe nearest pair of objects is BOS\/NY and DC, at distance 223. These are merged into a single cluster called \u201cBOS\/NY\/DC\u201d. Then we compute the distance from this new cluster to all other clusters, to get a new distance matrix.\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\t\nAfter merging DC with BOS\/NY:\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\tNow, the nearest pair of objects is SF and LA, at distance 379. These are merged into a single cluster called \u201cSF\/LA\u201d. Then we compute the distance from this new cluster to all other objects, to get a new distance matrix.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\tAfter merging SF with LA:\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\tNow, the nearest pair of objects is CHI and BOS\/NY\/DC, at distance 671. These are merged into a single cluster called \u201cBOS\/NY\/DC\/CHI\u201d. Then we compute the distance from this new cluster to all other clusters, to get a new distance matrix.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\t\nAfter merging CHI with BOS\/NY\/DC:\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\tNow, the nearest pair of objects is SEA and SF\/LA, at distance 808. These are merged into a single cluster called \u201cSF\/LA\/SEA\u201d. Then we compute the distance from this new cluster to all other clusters, to get a new distance matrix.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\tAfter merging SEA with SF\/LA:\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\tNow, the nearest pair of objects is DEN and BOS\/NY\/DC\/CHI, at distance 996. These are merged into a single cluster called \u201cBOS\/NY\/DC\/CHI\/DEN\u201d. Then we compute the distance from this new cluster to all other clusters, to get a new distance matrix.\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\tAfter merging DEN with BOS\/NY\/DC\/CHI:\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\tNow, the nearest pair of objects is BOS\/NY\/DC\/CHI\/DEN and SF\/LA\/SEA, at distance 1059. These are merged into a single cluster called \u201cBOS\/NY\/DC\/CHI\/DEN\/SF\/LA\/SEA\u201d. Then we compute the distance from this new compound object to all other objects, to get a new distance matrix.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\tAfter merging SF\/LA\/SEA with BOS\/NY\/DC\/CHI\/DEN:\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t

            3\u200a\u2014\u200aDBSCAN<\/h2><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\tDBSCAN is an instance of density-based clustering models, in which we group points with similar density. It does a great job of seeking areas in the data that have a high density of observations, versus areas of the data that are not very dense with observations. DBSCAN can sort data into clusters of varying shapes as well, another strong advantage. DBSCAN works as such:\n
              \n \t
            • Divides the dataset into\u00a0n<\/em>\u00a0dimensions.<\/li>\n \t
            • For each point in the dataset, DBSCAN forms an\u00a0n-dimensional<\/em>\u00a0shape around that data point and then counts how many data points fall within that shape.<\/li>\n \t
            • DBSCAN counts this shape as a\u00a0cluster.<\/em>\u00a0DBSCAN iteratively expands the cluster, by going through each individual point within the cluster, and counting the number of other data points nearby.<\/li>\n<\/ul>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
              \n\t\t\t\t
              \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
              \n\t\t\t\t
              \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
              \n\t\t\t\t
              \n\t\t\t\t\t\t\t\t\tIllustrated in the graphic above, the\u00a0epsilon<\/em>\u00a0is the radius given to test the distance between data points. If a point falls within the\u00a0epsilon<\/em>\u00a0distance of another point, those two points will be in the same cluster. Furthermore, the\u00a0minimum number of points needed<\/em>\u00a0<\/em><\/strong>is set to 4 in this scenario. When going through each data point, as long as DBSCAN finds 4 points within\u00a0epsilon <\/em>distance of each other, a cluster is formed.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
              \n\t\t\t\t
              \n\t\t\t\t\t\t\t\t\tDBSCAN does\u00a0NOT<\/em>\u00a0necessarily categorize every data point and is therefore terrific with handling outliers in the dataset. Let’s examine the graphic below:\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
              \n\t\t\t\t
              \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
              \n\t\t\t\t
              \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
              \n\t\t\t\t
              \n\t\t\t\t\t\t\t\t\tThe left image depicts a more traditional clustering method, such as K-Means, that does not account for multi-dimensionality. Whereas the right image shows how DBSCAN can contort the data into different shapes and dimensions in order to find similar clusters. We also notice in the right image, that the points along the outer edge of the dataset are not classified, suggesting they are outliers amongst the data.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
              \n\t\t\t\t
              \n\t\t\t\t\t\t\t\t\tAnd that\u2019s the end of this post on clustering! I hope you found this helpful and get a good grasp of the basics of clustering.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"

              INTRODUCTIONClustering is a Machine Learning technique that involves the grouping of data points. Given a set of data points, we can use a clustering algorithm to classify each data point into a specific group. In theory, data points that are in the same group should have similar properties and\/or features, while data points in different<\/p>\n","protected":false},"author":86,"featured_media":3480,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"content-type":"","footnotes":""},"categories":[187],"tags":[95],"ppma_author":[1842],"class_list":["post-1856","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-bigdata-cloud","tag-big-data-amp-technology"],"authors":[{"term_id":1842,"user_id":86,"is_guest":0,"slug":"james-le","display_name":"James Le","avatar_url":"https:\/\/secure.gravatar.com\/avatar\/?s=96&d=mm&r=g","user_url":"","last_name":"Le","first_name":"James","job_title":"","description":"James Le is a Software Developer with experiences in Product Management and Data Analytics. He played a pivotal role in the operation of a start-up organization at Denison University."}],"_links":{"self":[{"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/posts\/1856","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/users\/86"}],"replies":[{"embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/comments?post=1856"}],"version-history":[{"count":4,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/posts\/1856\/revisions"}],"predecessor-version":[{"id":36947,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/posts\/1856\/revisions\/36947"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/media\/3480"}],"wp:attachment":[{"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/media?parent=1856"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/categories?post=1856"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/tags?post=1856"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/ppma_author?post=1856"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}