{"id":234,"date":"2020-02-23T10:26:00","date_gmt":"2020-02-23T10:26:00","guid":{"rendered":"http:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/?p=234"},"modified":"2021-11-08T10:27:21","modified_gmt":"2021-11-08T10:27:21","slug":"model-based-clustering","status":"publish","type":"post","link":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/2020\/02\/23\/model-based-clustering\/","title":{"rendered":"Model-based clustering"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">Today&#8217;s post is based on a Masterclass given to the STOR-i cohort by Brendan Murphy from University College Dublin.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Clustering<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">In data science, <strong>clustering<\/strong> is the process of grouping objects into groups, or <strong>clusters<\/strong>, such that members of the same cluster are more &#8216;similar&#8217; to each other than they are to members of different clusters.<\/p>\n\n\n\n<figure class=\"wp-block-gallery columns-2 is-cropped wp-block-gallery-1 is-layout-flex wp-block-gallery-is-layout-flex\"><ul class=\"blocks-gallery-grid\"><li class=\"blocks-gallery-item\"><figure><img loading=\"lazy\" decoding=\"async\" width=\"949\" height=\"796\" src=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/wp-content\/uploads\/sites\/8\/2020\/04\/Fig1A-1.png\" alt=\"\" data-id=\"236\" data-full-url=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/wp-content\/uploads\/sites\/8\/2020\/04\/Fig1A-1.png\" data-link=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/?attachment_id=236\" class=\"wp-image-236\" srcset=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/wp-content\/uploads\/sites\/8\/2020\/04\/Fig1A-1.png 949w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/wp-content\/uploads\/sites\/8\/2020\/04\/Fig1A-1-300x252.png 300w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/wp-content\/uploads\/sites\/8\/2020\/04\/Fig1A-1-768x644.png 768w\" sizes=\"auto, (max-width: 949px) 100vw, 949px\" \/><\/figure><\/li><li class=\"blocks-gallery-item\"><figure><img loading=\"lazy\" decoding=\"async\" width=\"949\" height=\"796\" src=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/wp-content\/uploads\/sites\/8\/2020\/04\/Fig1B.png\" alt=\"\" data-id=\"237\" data-full-url=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/wp-content\/uploads\/sites\/8\/2020\/04\/Fig1B.png\" data-link=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/?attachment_id=237\" class=\"wp-image-237\" srcset=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/wp-content\/uploads\/sites\/8\/2020\/04\/Fig1B.png 949w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/wp-content\/uploads\/sites\/8\/2020\/04\/Fig1B-300x252.png 300w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/wp-content\/uploads\/sites\/8\/2020\/04\/Fig1B-768x644.png 768w\" sizes=\"auto, (max-width: 949px) 100vw, 949px\" \/><\/figure><\/li><\/ul><figcaption class=\"blocks-gallery-caption\">Example of some data with two clusters before (left) and after clustering (right). It is clear that the members of the red cluster are much more similar (i.e. closer) to each other than they are to members of the blue cluster, and vice versa.<\/figcaption><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Many common clustering methods (e.g. <a href=\"https:\/\/en.wikipedia.org\/wiki\/K-means_clustering\">k-means<\/a> or <a href=\"https:\/\/en.wikipedia.org\/wiki\/Hierarchical_clustering\">hierarchical clustering<\/a>) are based off a metric known as the <strong>distance<\/strong> or <strong>dissimilarity<\/strong> between the points (an example of this distance is simply the straight Euclidean distance between the points). This is then used in a number of different ways to assign points to clusters &#8211; for example, in k-means clustering, each point is assigned to the cluster with the closest mean.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">While these methods are very popular, they do suffer from drawbacks. Without assuming a model generating these points, it is hard to claim with certainty that future observations will fall into the same clusters. In addition, some of these algorithms can&#8217;t properly deal with many frequently repeated observations.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Model-based clustering<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Professor Murphy&#8217;s Masterclass instead presented a framework for clustering continuous data known as a <strong>Gaussian Mixture Model<\/strong>. This is a form of clustering which assumes that the data comes from a particular probability model.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The model is based on 3 general assumptions:<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>We know the number of clusters before we start<\/li><li>Each observation in the data as a certain probability of belonging to each cluster.<\/li><li>The observations within each cluster follow a normal distribution (with the appropriate dimension)<\/li><\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">These assumptions leave us with two problems to solve when fitting the model:<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>What are the means and covariances of each of the clusters?<\/li><li>Which cluster does each observation belong to?<\/li><\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">It is clear that these two problems are related. The mean and variance of a cluster will depend on which observations are assigned to it, and the cluster an observation should be assigned to will depend on that clusters mean and variance. Fortunately, there is a way to simulataneous solve both problems using the <strong>Expectation-Maximisation (EM) Algorithm.<\/strong> The algorithm works by repeated performing an E-step, which assigns each observation to it&#8217;s most likely cluster, and an M-step, which then updates the cluster means and variances based on the assigned observations.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">An example &#8211; Iris dataset<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">For a simple example, we will look at clustering different subspecies of iris flowers, based on the length and width of their petals and sepals.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/wp-content\/uploads\/sites\/8\/2020\/04\/FlowerPic.png\" alt=\"\" class=\"wp-image-240\" width=\"364\" height=\"373\" srcset=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/wp-content\/uploads\/sites\/8\/2020\/04\/FlowerPic.png 676w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/wp-content\/uploads\/sites\/8\/2020\/04\/FlowerPic-293x300.png 293w\" sizes=\"auto, (max-width: 364px) 100vw, 364px\" \/><figcaption>Don&#8217;t worry, I didn&#8217;t know what sepals were either.<\/figcaption><\/figure><\/div>\n\n\n\n<p class=\"wp-block-paragraph\">This is a famous data set consisting of 150 observations of 3 different subspecies of iris flowers &#8211; Setosa, Versicolor and Virginica (see <a href=\"https:\/\/en.wikipedia.org\/wiki\/Iris_flower_data_set\">here<\/a> for more information on the dataset, including a link to the data itself). I applied the EM algorithm to the data (Professor Murphy kindly left us some code that does this, but the &#8220;mclust&#8221; package in R also does this). The gif below nicely shows how the algorithm classifies observations and updates the cluster.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"480\" height=\"480\" src=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/wp-content\/uploads\/sites\/8\/2020\/04\/TestGif2.gif\" alt=\"\" class=\"wp-image-239\" \/><\/figure><\/div>\n\n\n\n<p class=\"wp-block-paragraph\">As nice as the above picture looks, the big question is how accurate is the classifier? That is, how well do our clusters match up with the true different subspecies? As shown in the table below, we nailed it on the Setosa. And we did classify all the Versicolor together. Unfortunately, the algorithm couldn&#8217;t really distinguish between Versicolor and Virginica. 39 out of 50 Virginica observations were classified as Versicolor. However, it is also worth noting that this dataset is notorious hard to classify, particularly between these two subspecies.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><\/td><td>Cluster 1 (red)<\/td><td>Cluster 2 (blue)<\/td><td>Cluster 3 (green)<\/td><\/tr><tr><td>Setosa<\/td><td>50<\/td><td>0<\/td><td>0<\/td><\/tr><tr><td>Versicolor<\/td><td>0<\/td><td>0<\/td><td>50<\/td><\/tr><tr><td>Virginica<\/td><td>0<\/td><td>11<\/td><td>39<\/td><\/tr><\/tbody><\/table><figcaption>Accuracy of our clusters against the true subspecies. It can be seen that the Setosa flowers were all perfectly clustered, but the majority of the Virginica were mis-classified as Versicolor.<\/figcaption><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">Extensions and further work<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">We&#8217;ve barely scratched the surface of Gaussian Mixture Models. Professor Murphy has done extensive work on the different covariance possible covariance structures between clusters (e.g. if you assume all clusters have equal covariance matrices, or simply different scales, or can be whatever you would like). And that&#8217;s not even covering classifying with categorical variables, which can be done using <strong>Latent Class Analysis<\/strong>. Even taking Gaussian Mixture Models as presented here, you still need to assume the number clusters. While this can be determined using model selection criteria such as BIC, there is still much work to be done in this area.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Today&#8217;s post is based on a Masterclass given to the STOR-i cohort by Brendan Murphy from University College Dublin. Clustering&hellip;<\/p>\n","protected":false},"author":6,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[1],"tags":[19,20,5],"class_list":["post-234","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-clustering","tag-gaussian-mixture-models","tag-statistics"],"_links":{"self":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/wp-json\/wp\/v2\/posts\/234","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/wp-json\/wp\/v2\/users\/6"}],"replies":[{"embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/wp-json\/wp\/v2\/comments?post=234"}],"version-history":[{"count":5,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/wp-json\/wp\/v2\/posts\/234\/revisions"}],"predecessor-version":[{"id":304,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/wp-json\/wp\/v2\/posts\/234\/revisions\/304"}],"wp:attachment":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/wp-json\/wp\/v2\/media?parent=234"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/wp-json\/wp\/v2\/categories?post=234"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/hamish-thorburn\/wp-json\/wp\/v2\/tags?post=234"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}