1 00:00:09,286 --> 00:00:10,914 Aside from transformations, 2 00:00:10,914 --> 00:00:15,179 the other family of unsupervised learning methods are the clustering methods. 3 00:00:16,810 --> 00:00:20,970 The goal of clustering is to find a way to divide up a data set into groups called 4 00:00:20,970 --> 00:00:22,170 clusters. 5 00:00:22,170 --> 00:00:26,280 So that groups with similar data instances are assigned to the same cluster, 6 00:00:26,280 --> 00:00:29,650 while very dissimilar objects are assigned to different clusters. 7 00:00:31,120 --> 00:00:35,543 If new data points were being added over time, some clustering algorithms could 8 00:00:35,543 --> 00:00:39,400 also predict which cluster a new data instance should be assigned to. 9 00:00:39,400 --> 00:00:41,215 Similar to classification, but 10 00:00:41,215 --> 00:00:45,830 without being able to train the clustering model using label examples in advanced. 11 00:00:48,105 --> 00:00:52,220 One of the most widely used clustering algorithms is called k-means clustering. 12 00:00:52,220 --> 00:00:57,050 K-means clustering finds k cluster centers in different 13 00:00:57,050 --> 00:01:00,600 regions of the feature space that it thinks represent very different groups. 14 00:01:02,160 --> 00:01:04,691 You need to specify the value of k ahead of time, 15 00:01:04,691 --> 00:01:06,985 which is one of the draw backs of k-means. 16 00:01:06,985 --> 00:01:10,854 For some problems, we may know the number of classes the data should fall into, but 17 00:01:10,854 --> 00:01:12,580 for many other tasks, we might not. 18 00:01:12,580 --> 00:01:20,680 K-means operates by first randomly picking locations for the k-cluster centers. 19 00:01:21,740 --> 00:01:23,790 Then it goes back and forth between two steps. 20 00:01:24,950 --> 00:01:29,780 In the first step, given the locations of existing cluster centers, it assigns 21 00:01:29,780 --> 00:01:33,860 each data point to a cluster center based on its distance from the center. 22 00:01:35,600 --> 00:01:38,080 In other words, it assigns each data point to the closest center. 23 00:01:39,690 --> 00:01:42,800 Then in the second step, it adjusts the locations of each cluster center. 24 00:01:43,820 --> 00:01:46,740 It does this by setting the new cluster center 25 00:01:46,740 --> 00:01:49,900 to the mean of the positions of all the data points in that cluster. 26 00:01:51,710 --> 00:01:54,760 Somewhat magically, after running this alternating process for 27 00:01:54,760 --> 00:01:58,180 a while, coherent clusters do start to form. 28 00:01:58,180 --> 00:02:01,870 And the cluster centers and the corresponding cluster assignment for 29 00:02:01,870 --> 00:02:05,200 each data point eventually settled down to something stable. 30 00:02:06,710 --> 00:02:10,720 Now one aspect of k means is that different random starting points for 31 00:02:10,720 --> 00:02:15,710 the cluster centers often result in very different clustering solutions. 32 00:02:15,710 --> 00:02:20,345 So typically, the k-means algorithm is run in scikit-learn with ten different 33 00:02:20,345 --> 00:02:22,610 random initializations. 34 00:02:22,610 --> 00:02:26,330 And the solution occurring the most number of times is chosen. 35 00:02:26,330 --> 00:02:27,730 Here is a step by step example. 36 00:02:28,830 --> 00:02:34,340 We first choose three locations in the space randomly to be the cluster centers. 37 00:02:35,860 --> 00:02:38,930 Then we assign each data point to the cluster with the nearest center. 38 00:02:40,890 --> 00:02:45,430 Now for each cluster, we compute the mean location of all points in the cluster and 39 00:02:45,430 --> 00:02:48,290 use that as the new cluster center for the next iteration. 40 00:02:49,550 --> 00:02:52,850 Here's the second iteration of the first and second steps. 41 00:02:54,554 --> 00:02:57,395 Eventually, after 20 or 50 or 100 steps, 42 00:02:57,395 --> 00:03:01,060 things settle down to converge on one solution, as shown here. 43 00:03:05,518 --> 00:03:10,849 K-means clustering is simple to apply in scikit learning. 44 00:03:12,360 --> 00:03:18,220 You import the k-means class from sklearn cluster create the k-means object 45 00:03:18,220 --> 00:03:23,260 set into value of k by specifying the n cluster parameter, and 46 00:03:23,260 --> 00:03:26,190 then calling the fit method on the dataset to run the algorithm. 47 00:03:28,170 --> 00:03:31,230 One distinction should be made here between clustering algorithms that can 48 00:03:31,230 --> 00:03:34,910 predict which center new data points should be assigned to, and 49 00:03:34,910 --> 00:03:36,595 those that cannot make such predictions. 50 00:03:36,595 --> 00:03:41,480 K-means supports the predict method, and so we can call the fit and 51 00:03:41,480 --> 00:03:42,840 predict methods separately. 52 00:03:44,220 --> 00:03:47,660 Later methods we'll look at like agglomerative clustering do not and 53 00:03:47,660 --> 00:03:51,050 must perform the fit and predict in a single step, as we'll see. 54 00:03:53,900 --> 00:03:58,243 Here's the output from the notebook code showing the result supplied 55 00:03:58,243 --> 00:04:02,303 to the fruits dataset, where we know the value of k ahead of time. 56 00:04:02,303 --> 00:04:05,407 Note that kmeans is very sensitive to the range of future values. 57 00:04:05,407 --> 00:04:09,579 So if your data has features with very different ranges, it's important to 58 00:04:09,579 --> 00:04:14,290 normalize using min-max scaling, as we did for some supervised learning methods. 59 00:04:17,600 --> 00:04:22,650 Because each cluster in k-means clustering is defined entirely by its center point, 60 00:04:22,650 --> 00:04:25,495 it can only capture fairly simple types of clusters. 61 00:04:25,495 --> 00:04:30,690 K-means clustering tends to work well when the data points form into groups 62 00:04:30,690 --> 00:04:35,630 of roughly the same size, with simple globular shapes that are well-separated. 63 00:04:35,630 --> 00:04:40,230 K-means will tend not to do well if the data forms long, 64 00:04:40,230 --> 00:04:41,780 irregular clusters, for example. 65 00:04:43,800 --> 00:04:47,060 Also the version k-means we saw here assumed that the data features 66 00:04:47,060 --> 00:04:49,040 were continuous values. 67 00:04:49,040 --> 00:04:51,990 However, in some cases we may have categorical features, 68 00:04:51,990 --> 00:04:53,619 where taking the mean doesn't make sense. 69 00:04:54,930 --> 00:04:55,500 In that case, 70 00:04:55,500 --> 00:04:59,650 there are variants of k-means that can use a more general definition of distance. 71 00:05:00,950 --> 00:05:05,770 Such as the k-medoids algorithm that can work with categorical features. 72 00:05:07,430 --> 00:05:11,090 A glommer of clustering refers to a family of clustering methods that work 73 00:05:11,090 --> 00:05:13,320 by doing an iterative bottom up approach. 74 00:05:14,390 --> 00:05:17,780 First, each data point is put into its own cluster of one item. 75 00:05:19,090 --> 00:05:22,171 Then, a sequence of clusterings are done where the most similar 76 00:05:22,171 --> 00:05:25,430 two clusters at each stage are merged into a new cluster. 77 00:05:25,430 --> 00:05:28,332 Then, this process is repeated until some stopping condition is met. 78 00:05:28,332 --> 00:05:32,839 In scikit-learn, the stopping condition is the number of clusters. 79 00:05:34,910 --> 00:05:38,826 Here's a visual example of how agglomerative clustering might proceed on 80 00:05:38,826 --> 00:05:41,570 a sample dataset until three clusters are reached. 81 00:05:42,850 --> 00:05:46,462 In Stage 1, each data point is in its own cluster, 82 00:05:46,462 --> 00:05:49,324 shown by the circles around the points. 83 00:05:49,324 --> 00:05:51,878 In Stage 2, the two most similar clusters, 84 00:05:51,878 --> 00:05:55,926 which at this stage amounts to defining the closest points are merged. 85 00:05:55,926 --> 00:05:59,834 And this process is continued, as denoted by the expanding and 86 00:05:59,834 --> 00:06:02,500 closed regions that denote each cluster. 87 00:06:04,253 --> 00:06:08,552 You can choose how the agglomerative clustering algorithm determines the most 88 00:06:08,552 --> 00:06:12,610 similar cluster by specifying one of several possible linkage criteria. 89 00:06:14,700 --> 00:06:20,480 In scikit-learn, the following three linkage criteria are available, ward, 90 00:06:20,480 --> 00:06:21,840 average, and complete. 91 00:06:23,940 --> 00:06:28,300 Ward's method chooses to merge the two clusters that give the smallest increase 92 00:06:28,300 --> 00:06:30,399 in total variance within all clusters. 93 00:06:31,650 --> 00:06:35,870 Average linkage merges the two clusters that have the smallest average distance 94 00:06:35,870 --> 00:06:36,710 between points. 95 00:06:38,070 --> 00:06:42,870 Complete linkage, which is also known as maximum linkage, merges the two clusters 96 00:06:42,870 --> 00:06:45,760 that have the smallest maximum distance between their points. 97 00:06:47,330 --> 00:06:50,690 In general, Ward's method works well on most data sets, and 98 00:06:50,690 --> 00:06:52,399 that's our usual method of choice. 99 00:06:53,620 --> 00:06:57,060 In some cases, if you expect the sizes of the clusters to be very different, for 100 00:06:57,060 --> 00:07:01,035 example, that one cluster is much larger than the rest. 101 00:07:01,035 --> 00:07:04,250 It's worth trying average and complete linkage criteria as well. 102 00:07:07,040 --> 00:07:09,880 To perform agglomerative clustering in scikit-learn, 103 00:07:09,880 --> 00:07:13,530 you import the agglomerative clustering class from sklearn cluster. 104 00:07:15,300 --> 00:07:19,450 When initializing the object, you specify the n clusters parameter 105 00:07:19,450 --> 00:07:22,990 that causes the algorithm to stop when it has reach that number of clusters. 106 00:07:24,510 --> 00:07:28,090 You call the fit predict method using the data set as input and 107 00:07:28,090 --> 00:07:31,480 they return the set of cluster assignments for the data points as shown here. 108 00:07:34,650 --> 00:07:37,270 One of the nice things about agglomerative clustering is that it 109 00:07:37,270 --> 00:07:41,730 automatically arranges the data into a hierarchy as an effect of the algorithm, 110 00:07:41,730 --> 00:07:42,860 reflecting the order and 111 00:07:42,860 --> 00:07:47,470 cluster distance at which each data point is assigned to successive clusters. 112 00:07:49,050 --> 00:07:53,190 This hierarchy can be useful to visualize using what's called a dendrogram, 113 00:07:53,190 --> 00:07:55,180 which can be used even with higher dimensional data. 114 00:07:56,900 --> 00:08:00,810 Here's the dendogram corresponding to the Ward's method clustering of the previous 115 00:08:00,810 --> 00:08:01,710 data set example. 116 00:08:03,550 --> 00:08:06,010 The data points are at the bottom and are numbered. 117 00:08:06,010 --> 00:08:09,370 The y axis represents cluster distance, namely, 118 00:08:09,370 --> 00:08:12,510 the distance that two clusters are apart in the data space. 119 00:08:13,710 --> 00:08:17,990 The data points form the leaves of the tree at the bottom, and the new node 120 00:08:17,990 --> 00:08:21,970 parent in the tree is added as each pair of successive clusters is merged. 121 00:08:23,460 --> 00:08:26,210 The height of the node parent along the y axis 122 00:08:26,210 --> 00:08:29,480 captures how far apart the two clusters were when they merged, 123 00:08:29,480 --> 00:08:33,200 with the branch going up representing the new merged cluster. 124 00:08:34,680 --> 00:08:38,720 Note that you can tell how far apart the merged clusters are by the length of each 125 00:08:38,720 --> 00:08:39,630 branch of the tree. 126 00:08:41,050 --> 00:08:45,570 This property of a dendogram can help us figure out the right number of clusters. 127 00:08:45,570 --> 00:08:50,620 In general, we want clusters that have highly similar items within each cluster, 128 00:08:50,620 --> 00:08:53,490 but that are far apart from other clusters. 129 00:08:53,490 --> 00:08:54,140 For example, 130 00:08:54,140 --> 00:08:59,540 we can see that going from three clusters to two happens at a fairly high Y value. 131 00:08:59,540 --> 00:09:03,320 Which means the clusters that were merged were a significant distance apart. 132 00:09:04,520 --> 00:09:06,810 We might want to avoid choosing two clusters and 133 00:09:06,810 --> 00:09:09,920 stick with three clusters that don't involve forcing a merge for 134 00:09:09,920 --> 00:09:12,180 clusters that have very dissimilar items in them. 135 00:09:13,566 --> 00:09:19,700 Scikit-learn doesn't provide the ability to plot dendrograms, but SciPy does. 136 00:09:19,700 --> 00:09:22,520 SciPy handles clustering a little differently than scikit-learn, but 137 00:09:22,520 --> 00:09:23,250 here is an example. 138 00:09:24,690 --> 00:09:29,059 We first import the dendrogram in word functions from the scipy.cluster 139 00:09:29,059 --> 00:09:30,740 hierarchy module. 140 00:09:30,740 --> 00:09:35,540 The word function returns an array that specifies the distances spanned during 141 00:09:35,540 --> 00:09:38,450 the agglomerative clustering. 142 00:09:38,450 --> 00:09:41,320 This word function returns a linkage array, 143 00:09:41,320 --> 00:09:44,580 which can then be passed to the dendogram function to plot the tree. 144 00:09:47,251 --> 00:09:51,943 Typically, making use of this hierarchy is most useful when the underlying data 145 00:09:51,943 --> 00:09:57,670 itself follows some kind of hierarchical process so the tree is easily interpreted. 146 00:09:57,670 --> 00:10:01,550 For example, hierarchical clustering is especially useful for genetic and 147 00:10:01,550 --> 00:10:06,520 other biological data where the levels represent stages of mutation or evolution. 148 00:10:08,390 --> 00:10:11,710 But there are other data sets where both k-means clustering and 149 00:10:11,710 --> 00:10:13,450 agglomerative clustering don't perform well. 150 00:10:14,660 --> 00:10:18,190 So we're now going to give an overview of a third clustering method called DBSCAN. 151 00:10:21,494 --> 00:10:23,677 DBSCAN is an acronym that stands for 152 00:10:23,677 --> 00:10:27,760 density-based spatial clustering of applications with noise. 153 00:10:29,260 --> 00:10:33,190 One advantage of DBSCAN is that you don't need to specify the number of clusters in 154 00:10:33,190 --> 00:10:33,739 advance. 155 00:10:35,300 --> 00:10:38,500 Another advantage is that it works well with datasets that have more complex 156 00:10:38,500 --> 00:10:39,400 cluster shapes. 157 00:10:40,420 --> 00:10:45,006 It can also find points that are outliers that shouldn't reasonably be assigned to 158 00:10:45,006 --> 00:10:45,800 any cluster. 159 00:10:45,800 --> 00:10:51,422 DBSCAN is relatively efficient and can be used for large datasets. 160 00:10:51,422 --> 00:10:54,947 The main idea behind DBSCAN is that clusters represent areas 161 00:10:54,947 --> 00:10:59,578 in the dataspace that are more dense with data points, while being separated by 162 00:10:59,578 --> 00:11:03,330 regions that are empty or at least much less densely populated. 163 00:11:04,780 --> 00:11:08,829 The two main parameters for DBSCAN are min samples and eps. 164 00:11:09,880 --> 00:11:13,570 All points that lie in a more dense region are called core samples. 165 00:11:14,680 --> 00:11:18,580 For a given data point, if there are min sample of other data points that 166 00:11:18,580 --> 00:11:23,570 lie within a distance of eps, that given data points is labeled as a core sample. 167 00:11:24,930 --> 00:11:30,520 Then, all core samples that are with a distance of eps units apart 168 00:11:30,520 --> 00:11:31,770 are put into the same cluster. 169 00:11:33,930 --> 00:11:37,420 In addition to points being categorized as core samples, 170 00:11:37,420 --> 00:11:41,920 points that don't end up belonging to any cluster are considered as noise. 171 00:11:41,920 --> 00:11:46,890 While points that are within a distance of eps units from core points, but 172 00:11:46,890 --> 00:11:49,949 not core points themselves, are termed boundary points. 173 00:11:52,570 --> 00:11:55,860 Here's an example of DBSCAN applied to a sample data set. 174 00:11:57,360 --> 00:11:59,241 As with the other clustering methods, 175 00:11:59,241 --> 00:12:02,150 DBSCAN is imported from the Scikit-Learn cluster module. 176 00:12:03,780 --> 00:12:06,078 And just like with a agglomerative clustering, 177 00:12:06,078 --> 00:12:09,670 DBSCAN doesn't make cluster assignments from new data. 178 00:12:09,670 --> 00:12:12,800 So we use the fit predict method to cluster and 179 00:12:12,800 --> 00:12:15,160 get the cluster assignments back in one step. 180 00:12:16,750 --> 00:12:21,242 One consequence of not having the right settings of eps and min samples for 181 00:12:21,242 --> 00:12:25,665 your particular dataset might be that the cluster memberships returned 182 00:12:25,665 --> 00:12:29,960 by DBSCAN may all be assigned the label -1, which indicates noise. 183 00:12:31,350 --> 00:12:34,190 Basically, the EPS setting does implicitly 184 00:12:34,190 --> 00:12:36,040 control the number of clusters that are found. 185 00:12:37,690 --> 00:12:41,315 With DBSCAN, if you've scaled your data using a standard scalar or 186 00:12:41,315 --> 00:12:45,860 min-max scalar to make sure the feature values have comparable ranges, 187 00:12:45,860 --> 00:12:49,260 finding an appropriate value for eps is a bit easer to do. 188 00:12:51,110 --> 00:12:55,590 One final note, make sure that when you use the cluster assignments from DBSCAN, 189 00:12:55,590 --> 00:12:59,596 you check for and handle the -1 noise value appropriately. 190 00:12:59,596 --> 00:13:01,760 Since this negative value might cause problems, for 191 00:13:01,760 --> 00:13:06,319 example, if the cluster assignment is used as an index into another array later on. 192 00:13:08,360 --> 00:13:11,690 Unlike supervised learning, where we have existing labels or 193 00:13:11,690 --> 00:13:15,900 target values to use for evaluating the effectiveness of the learning method, it 194 00:13:15,900 --> 00:13:20,540 can be difficult to evaluate unsupervised learning algorithms automatically. 195 00:13:20,540 --> 00:13:23,140 Since there's typically no ground truth to compare against. 196 00:13:24,490 --> 00:13:28,560 In some cases, as in the breast cancer example, we may have existing labels that 197 00:13:28,560 --> 00:13:32,990 can be used to evaluate the quality of the clusters by comparing the assignment of 198 00:13:32,990 --> 00:13:36,610 a data point to a cluster with the label assigned to the same data point. 199 00:13:37,830 --> 00:13:40,819 But there are many cases where labels are not available. 200 00:13:40,819 --> 00:13:45,023 In addition, in the case of clustering, for example, there's ambiguity, 201 00:13:45,023 --> 00:13:48,784 in a sense that there are typically multiple clusterings that could be 202 00:13:48,784 --> 00:13:50,969 plausibly assigned to a given data set. 203 00:13:50,969 --> 00:13:55,525 And none of them is obviously better than another unless we have some additional 204 00:13:55,525 --> 00:13:56,890 criteria. 205 00:13:56,890 --> 00:13:59,800 Such as, performance on the specific application task 206 00:13:59,800 --> 00:14:03,840 that does have an objective evaluation to use as a basis for comparison. 207 00:14:04,980 --> 00:14:09,031 For example, in cases where the results of the clustering are used as features for 208 00:14:09,031 --> 00:14:12,908 supervised learning, we could use the overall classifier accuracy gain from 209 00:14:12,908 --> 00:14:16,313 adding these clustering-based features as a measure of success for 210 00:14:16,313 --> 00:14:17,800 the underlying clustering. 211 00:14:19,520 --> 00:14:23,410 Another issue with evaluating clustering algorithms is that it can be hard to 212 00:14:23,410 --> 00:14:27,980 automatically interpret or label the meaning of the clusters that are found. 213 00:14:27,980 --> 00:14:31,120 And this is still a step that requires human expertise to judge.