{"id":8259,"date":"2020-06-06T01:03:33","date_gmt":"2020-06-06T01:03:33","guid":{"rendered":"https:\/\/www.thecoderschool.com\/?p=8259"},"modified":"2022-10-13T20:49:56","modified_gmt":"2022-10-13T20:49:56","slug":"advanced-machine-learning-techniques-k-means-clustering-algorithm","status":"publish","type":"post","link":"https:\/\/www.thecoderschool.com\/blog\/advanced-machine-learning-techniques-k-means-clustering-algorithm\/","title":{"rendered":"Advanced Machine Learning Techniques: K-Means Clustering Algorithm"},"content":{"rendered":"

By Camille D., Age 17<\/strong><\/p>\n

K-means clustering<\/b> is one of the most widely used and straightforward machine learning algorithms. Its goal is to find groups or <\/span>clusters<\/b> within a set of data, the number of which is denoted by <\/span>k<\/span><\/i>. It is an iterative algorithm that partitions a dataset into subgroups such that the subgroups don\u2019t overlap and each data point only has only one unique subgroup. Each cluster has a <\/span>centroid<\/b>, or its own arithmetic mean of all of its data points. Centroids can be used to label new data.<\/span><\/p>\n

K-means clustering allows the user to find groups that have been created organically, rather than groups defined before the data comes up, making k-means an <\/span>unsupervised machine-learning algorithm<\/b>. The value of <\/span>k<\/span><\/i> itself, however, must be pre-defined.<\/span><\/p>\n

\"\"<\/p>\n

Some applications of k-means clustering can be defining personalities based on interests, determining characteristics of images based on stages or categories of a disease, and dividing by activities on a mobile application or a website.<\/span><\/p>\n

The two inputs to the algorithm are the value for <\/span>k<\/span><\/i> and the dataset. Centroids are first initialized by shuffling the dataset and then randomly selecting <\/span>k<\/span><\/i> data points to be centroids for each cluster. The algorithm then follows two iterative steps:<\/span><\/p>\n

1. Data, centroid assignment<\/p>\n

\"\"<\/p>\n

2. Centroid updating<\/p>\n

    \n
  1. <\/li>\n<\/ol>\n

    \"\"<\/p>\n

    Steps one and two are repeated until a terminal case is met (there is no change to the centroids, assignments of data points to clusters isn\u2019t changing).<\/span><\/p>\n

    Something to note about choosing the value of <\/span>k<\/span><\/i> is that we can use something called the <\/span>Elbow Method<\/b>. For example, start by running k-means on a dataset for a range of values of <\/span>k<\/span><\/i> (i.e. 2 to 10), and for each value of <\/span>k<\/span><\/i>, calculate the <\/span>sum of squared error<\/span><\/a> (average within-cluster distance to centroid). If we were to plot the SSE for each value of <\/span>k<\/span><\/i> on a line plot, and we detect an inflection point, we would use the value of <\/span>k<\/span><\/i> at which that inflection point occurs. Here is an example of such a plot, showing the ideal value for <\/span>k<\/span><\/i>:<\/span><\/p>\n

    \"\"<\/p>\n

    An example of k-means is as follows: suppose we have four objects that each have two attributes, and we want to group these objects into <\/span>k = 2<\/span><\/i> clusters based on the two attributes.<\/span><\/p>\n

    \"\"<\/p>\n

    We can represent these as coordinates in an attribute space below:<\/span><\/p>\n

    \"\"<\/p>\n

    Suppose we want to use Object A and B as the centroids. Thus, the coordinates of the centroids are (2, 3) and (1, 4).<\/span><\/p>\n

    \"\"<\/p>\n

    Next, use Euclidean distance to calculate the cluster centroid to each individual object. We will obtain a distance matrix at iteration 0:<\/span><\/p>\n

    \"\"<\/p>\n

    Each column of this matrix represents the objects successively. The first row represents that object\u2019s distance to Object A on the plot, and the second represents that object\u2019s distance to Object B on the plot. Next, we do the actual clustering based on the minimum distance. We will define two clusters for each centroid as <\/span>C<\/span>1<\/span> and <\/span>C<\/span>2<\/span>. For example, since Object A\u2019s distance to itself is obviously smaller than Object B\u2019s distance to Object A, Object A will belong to the <\/span>C<\/span>1<\/span>.<\/span><\/p>\n

    Let\u2019s define a new Group matrix, where the columns again correspond to each object, but their values will be assigned to either 0 or 1 based on whether they are in <\/span>C<\/span>1<\/span>or <\/span>C<\/span>2<\/span>. The rows correspond to each cluster successively.<\/span><\/p>\n

    \"\"<\/p>\n

    Now that we have assigned data points to their clusters, we can compute the new centroids. Since <\/span>C<\/span>2<\/span> has only one member, which is Object B (1, 4) itself, the centroid will remain (1, 4). <\/span>C<\/span>1<\/span>, however, has three members, so its new centroid will be the average coordinate of its three members: <\/span><\/p>\n

    \"\"<\/p>\n

    We continue these two steps until the terminal case is reached, which, in this case, occurs when the number of elements in <\/span>C<\/span>1<\/span> is equal to the number of elements in <\/span>C<\/span>2<\/span>.<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"

    By Camille D., Age 17 K-means clustering is one of the most widely used and straightforward machine learning algorithms. Its goal is to find groups or clusters within a set of data, the number of which is denoted by k. It is an iterative algorithm that partitions a dataset into subgroups such that the subgroups … <\/p>\n

    Continue reading “Advanced Machine Learning Techniques: K-Means Clustering Algorithm”<\/span><\/a><\/p>\n","protected":false},"author":6,"featured_media":8272,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[64,69],"class_list":["post-8259","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-coder-blog","tag-about-thecoderschool","tag-student-showcase","entry"],"_links":{"self":[{"href":"https:\/\/www.thecoderschool.com\/blog\/wp-json\/wp\/v2\/posts\/8259","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.thecoderschool.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.thecoderschool.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.thecoderschool.com\/blog\/wp-json\/wp\/v2\/users\/6"}],"replies":[{"embeddable":true,"href":"https:\/\/www.thecoderschool.com\/blog\/wp-json\/wp\/v2\/comments?post=8259"}],"version-history":[{"count":1,"href":"https:\/\/www.thecoderschool.com\/blog\/wp-json\/wp\/v2\/posts\/8259\/revisions"}],"predecessor-version":[{"id":11831,"href":"https:\/\/www.thecoderschool.com\/blog\/wp-json\/wp\/v2\/posts\/8259\/revisions\/11831"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.thecoderschool.com\/blog\/wp-json\/wp\/v2\/media\/8272"}],"wp:attachment":[{"href":"https:\/\/www.thecoderschool.com\/blog\/wp-json\/wp\/v2\/media?parent=8259"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.thecoderschool.com\/blog\/wp-json\/wp\/v2\/categories?post=8259"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.thecoderschool.com\/blog\/wp-json\/wp\/v2\/tags?post=8259"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}