{"id":221,"date":"2017-12-20T16:44:00","date_gmt":"2017-12-20T15:44:00","guid":{"rendered":"https:\/\/kindsonthegenius.com\/blog\/2017\/12\/20\/what-is-k-means-in-clustering-in-machine-learning\/"},"modified":"2020-08-22T10:27:33","modified_gmt":"2020-08-22T08:27:33","slug":"what-is-k-means-in-clustering-in-machine-learning","status":"publish","type":"post","link":"https:\/\/kindsonthegenius.com\/blog\/what-is-k-means-in-clustering-in-machine-learning\/","title":{"rendered":"What is K-Means in Clustering in Machine Learning?"},"content":{"rendered":"<div style=\"color: #555555; font-size: 18px; line-height: 30px; text-align: justify;\">\n<div style=\"font-family: 'segoe ui';\">\n<p>We are going to explain the basic concept of k-means clustering and the k-means clustering algorithm.<\/p>\n<div style=\"clear: both; text-align: center;\"><a style=\"margin-left: 1em; margin-right: 1em;\" href=\"https:\/\/1.bp.blogspot.com\/-fHdsJ8Q5TFU\/WjqTHcKqZ-I\/AAAAAAAAAic\/_tVg-_c5XjcU96uWkMlzvkJ-yY3kyx2JgCLcBGAs\/s1600\/K-Means-Clustering-In-Machine-Learning.jpg\"><img decoding=\"async\" loading=\"lazy\" src=\"https:\/\/1.bp.blogspot.com\/-fHdsJ8Q5TFU\/WjqTHcKqZ-I\/AAAAAAAAAic\/_tVg-_c5XjcU96uWkMlzvkJ-yY3kyx2JgCLcBGAs\/s320\/K-Means-Clustering-In-Machine-Learning.jpg\" width=\"320\" height=\"176\" border=\"0\" data-original-height=\"657\" data-original-width=\"1194\" \/><\/a><\/div>\n<p><b>Table of Content<\/b><\/p>\n<ul>\n<li><a href=\"#t1\">What is K-Means Clustering<\/a><\/li>\n<li><a href=\"#t2\">How it Works<\/a><\/li>\n<li><a href=\"#t3\">Steps in K-Means Clustering<\/a><\/li>\n<li><a href=\"#t4\">Assignment of Clusters<\/a><\/li>\n<li><a href=\"#t5\">Understanding the Formula<\/a><\/li>\n<li><a href=\"#t6\">More Explanation of the K-Means Algorithm<\/a><\/li>\n<li><a href=\"#t7\">Example of K-Means Clustering<\/a><\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h3 id=\"t1\">1. What is k-Means Clustering<\/h3>\n<p>It is a clustering method that tends to partition your data into partitions called clusters. Let&#8217;s say you have you have n data points, the k-means algorithms would assign each of the data point to the cluster with the nearest mean.<\/p>\n<p>Note: the k in k-means represents the number of clusters, that is k clusters.<\/p>\n<p>&nbsp;<\/p>\n<h3 id=\"t2\">2. How it works<\/h3>\n<p>Suppose we have a set of observations <i><span style=\"font-family: 'times' , 'times new roman' , serif;\">{x<sub>1<\/sub>, x<sub>2<\/sub>,&#8230; x<sub>n<\/sub>}<\/span><\/i> which consists in a set of N random variable <i><span style=\"font-family: 'times' , 'times new roman' , serif;\">x<\/span><\/i> (x is a D d-dimensional real vector). The goal is to partition the data set\u00a0 into some number K of clusters, where the value of K is known.<br \/>\nA cluster is a group of data points whose inter-point distances are minimal when compare with distance to points outside the cluster.<br \/>\nThe first step is to find the <i><span style=\"font-family: 'times' , 'times new roman' , serif;\">m<sub>k<\/sub>,<\/span><\/i> for <i><span style=\"font-family: 'times' , 'times new roman' , serif;\">k = 1,&#8230;, K,<\/span><\/i> in which <i><span style=\"font-family: 'times' , 'times new roman' , serif;\">m<sub>k<\/sub> <\/span><\/i>is the mean associated to the <i><span style=\"font-family: 'times' , 'times new roman' , serif;\">k<sub>th<\/sub><\/span><\/i> cluster.<br \/>\nWe now assign each of the data points to clusters, such that the sum of squares of the distances of each data\u00a0 point to its closest mean <span style=\"font-family: 'times' , 'times new roman' , serif;\">m<sub>k<\/sub><\/span> is\u00a0 minimum.<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<h3 id=\"t3\">3. Steps of the k-Means Algorithm<\/h3>\n<p><b>Step 1:<\/b> For\u00a0 each unit, x, in the input space, place it in the cluster whose current centroid it is nearest to.<br \/>\n<b>Step 2: <\/b>After all points have been assigned (x1,&#8230;xn), adjust the locations of the centroids of the k clusters<br \/>\n<b>Step 3:<\/b> Reassign all the points to their nearest centroid<br \/>\n<b>Repeat steps 2 and 3 until convergence<\/b><br \/>\nConvergence occurs when the points not move between clusters and the centroids are stabilized<\/p>\n<p>This algorithm would become clearer when we consider an example later in this article.<br \/>\nLet&#8217;s now look at a little more details on how the clusters are assigned<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<h3 id=\"t4\">4. Assignment of Clusters<\/h3>\n<p>(based on &#8220;Pattern Recognition and Machine Learning&#8221; by Christopher M. Bishop)<br \/>\nFor each data point <span style=\"font-family: 'times' , 'times new roman' , serif;\">x<sub>n<\/sub><\/span>, we would use a corresponding set of binary variables we denoted as <span style=\"font-family: 'times' , 'times new roman' , serif;\">r<sub>nk<\/sub> ={0,1}<\/span> where <span style=\"font-family: 'times' , 'times new roman' , serif;\">k =1,&#8230;,K.<\/span><br \/>\n<span style=\"font-family: 'times' , 'times new roman' , serif;\">r<sub>nk<\/sub> <\/span>describes which of the K clusters the data point x<sub>n<\/sub> is assigned to. If r<sub>nk<\/sub> is assigned to k, then<span style=\"font-family: 'times' , 'times new roman' , serif;\"> r<sub>nk<\/sub> = 1<\/span> and<span style=\"font-family: 'times' , 'times new roman' , serif;\"> r<sub>nj<\/sub> = 0 <\/span>for j not equal to k.<\/p>\n<p>Note the the two superscript in\u00a0\u00a0 indicates that there would be two loops:<br \/>\n<b>Loop 1(1-N)<\/b>: Iterate through all the data points<br \/>\n<b>Loop 2(1-K):<\/b> Iterate through all the cluster<\/p>\n<p>Now, for each iteration, you need to calculate a value for J which is called the distortion measure and is given by the sum of squares function:<\/p>\n<hr \/>\n<div style=\"text-align: center;\"><\/div>\n<hr \/>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<h3 id=\"t5\">5. Lets try to understand this formula<\/h3>\n<p>First note that this <u><span style=\"color: #0000ee;\">formula<\/span> <\/u>is sometimes called distortion measure since it represent how much each data point say x<sub>k<\/sub> is separated from the mean m<sub>k<\/sub> of that cluster.<br \/>\nIn other words, J represents the sum of squares of the distance of each data point to its assigned vector m<sub>k<\/sub>.<\/p>\n<div style=\"clear: both; text-align: center;\"><a style=\"margin-left: 1em; margin-right: 1em;\" href=\"https:\/\/1.bp.blogspot.com\/-XLLMbsgdlpY\/WjpTU1KeV7I\/AAAAAAAAAiA\/uXBrYQjTdkED8OY1LPEZgT9fEXgNRU2awCLcBGAs\/s1600\/k-Means%2BEquation.jpg\"><img decoding=\"async\" loading=\"lazy\" src=\"https:\/\/1.bp.blogspot.com\/-XLLMbsgdlpY\/WjpTU1KeV7I\/AAAAAAAAAiA\/uXBrYQjTdkED8OY1LPEZgT9fEXgNRU2awCLcBGAs\/s320\/k-Means%2BEquation.jpg\" width=\"320\" height=\"84\" border=\"0\" data-original-height=\"186\" data-original-width=\"703\" \/><\/a><\/div>\n<ul>\n<li>N is to total number of data points,<\/li>\n<li>K is the number of clusters<\/li>\n<li>x<sub>n<\/sub> is the vector of measurement n<\/li>\n<li>m<sub>k<\/sub> is the mean for cluster k<\/li>\n<li>r<sub>nk<\/sub> is an indicator variable that indicates whether to assign x<sub>n<\/sub> to k<\/li>\n<\/ul>\n<p>We need to determine the value of {r<sub>nk<\/sub>} and mk that gives the least value of J.<br \/>\nThis is achieved by the use of k-Means Algorithm<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<h3 id=\"t6\">6. More Explanation of the k=Means Algorithm<\/h3>\n<p>This algorithm is an iterative procedure involving steps:<br \/>\nInput set of points <span style=\"font-family: 'times' , 'times new roman' , serif;\">x<sub>1<\/sub>,&#8230;x<sub>n<\/sub><\/span><br \/>\nChoose a value for K<br \/>\nPlace <span style=\"font-family: 'times' , 'times new roman' , serif;\">m<sub>1<\/sub>,&#8230;, m<sub>k<\/sub><\/span>(let&#8217;s call this centroid) are random locations within your data space<br \/>\nRepeat the following steps until convergence<br \/>\nfor each point x<\/p>\n<ul>\n<li>find the nearest centroid, c<sub>j<\/sub> (compute the distance\u00a0 between xi, compute the distance between x<sub>i<\/sub> and m<sub>j<\/sub> for every centroid m<sub>j<\/sub>, and pick the cluster with the minimum distance)<\/li>\n<li>find the nearest centroid<\/li>\n<li>assign this point x<sub>j<\/sub> to the cluster of the nearest centroid<\/li>\n<\/ul>\n<p>For each cluster\u00a0 j = 1,&#8230;, K, and recompute the centroid position<\/p>\n<ul>\n<li>Take all the data points that fall into this cluster<\/li>\n<li>new centroid c<sub>j<\/sub> = mean of all points x<\/li>\n<li>assign to cluster j in the previous step<\/li>\n<\/ul>\n<p>Stop when none of the cluster assignments change<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<h3 id=\"t7\">7. Example of k-Means Clustering<\/h3>\n<p>The example below is based on<br \/>\nK = 2 and N = 14<br \/>\nTake some time to examine the progression through the steps and make sure you understand how it works<\/p>\n<\/div>\n<div style=\"clear: both; text-align: center;\"><a style=\"clear: left; float: left; margin-bottom: 1em; margin-right: 1em;\" href=\"https:\/\/3.bp.blogspot.com\/-m6JxX6jcMaI\/WjqS6mylURI\/AAAAAAAAAiY\/jF0YX4FwObEPLkDTq8tzvTNop6g2voKjQCLcBGAs\/s1600\/K-Means-Clustering-In-Machine-Learning_1.jpg.png\"><img decoding=\"async\" loading=\"lazy\" src=\"https:\/\/3.bp.blogspot.com\/-m6JxX6jcMaI\/WjqS6mylURI\/AAAAAAAAAiY\/jF0YX4FwObEPLkDTq8tzvTNop6g2voKjQCLcBGAs\/s400\/K-Means-Clustering-In-Machine-Learning_1.jpg.png\" width=\"400\" height=\"210\" border=\"0\" data-original-height=\"757\" data-original-width=\"1436\" \/><\/a><\/div>\n<div style=\"font-family: 'segoe ui';\">\n<p>&nbsp;<\/p>\n<div style=\"clear: both; text-align: center;\"><a style=\"margin-left: 1em; margin-right: 1em;\" href=\"https:\/\/3.bp.blogspot.com\/-_LI_9tJDnzQ\/WjqS6YSKXpI\/AAAAAAAAAiQ\/jjA8xv9_YqUmFrHeNI2qWhiXaY4E-7BkwCLcBGAs\/s1600\/K-Means-Clustering-In-Machine-Learning_2.jpg\"><img decoding=\"async\" loading=\"lazy\" src=\"https:\/\/3.bp.blogspot.com\/-_LI_9tJDnzQ\/WjqS6YSKXpI\/AAAAAAAAAiQ\/jjA8xv9_YqUmFrHeNI2qWhiXaY4E-7BkwCLcBGAs\/s400\/K-Means-Clustering-In-Machine-Learning_2.jpg\" width=\"400\" height=\"228\" border=\"0\" data-original-height=\"811\" data-original-width=\"1412\" \/><\/a><\/div>\n<p>&nbsp;<\/p>\n<div style=\"clear: both; text-align: center;\"><a style=\"margin-left: 1em; margin-right: 1em;\" href=\"https:\/\/4.bp.blogspot.com\/-591sicezyw4\/WjqS6vwE1oI\/AAAAAAAAAiU\/mmiNMHYVu8Qt2JX35oJh_cv0_nC59nfGQCLcBGAs\/s1600\/K-Means-Clustering-In-Machine-Learning_3.jpg\"><img decoding=\"async\" loading=\"lazy\" src=\"https:\/\/4.bp.blogspot.com\/-591sicezyw4\/WjqS6vwE1oI\/AAAAAAAAAiU\/mmiNMHYVu8Qt2JX35oJh_cv0_nC59nfGQCLcBGAs\/s400\/K-Means-Clustering-In-Machine-Learning_3.jpg\" width=\"400\" height=\"210\" border=\"0\" data-original-height=\"768\" data-original-width=\"1460\" \/><\/a><\/div>\n<\/div>\n<\/div>\n<p><ins style=\"display: block; text-align: center;\" data-ad-client=\"ca-pub-7041870931346451\" data-ad-format=\"fluid\" data-ad-layout=\"in-article\" data-ad-slot=\"8227894917\"><\/ins><br \/>\n<ins style=\"display: block; text-align: center;\" data-ad-client=\"ca-pub-7041870931346451\" data-ad-format=\"fluid\" data-ad-layout=\"in-article\" data-ad-slot=\"8227894917\"><\/ins><\/p>\n","protected":false},"excerpt":{"rendered":"<p>We are going to explain the basic concept of k-means clustering and the k-means clustering algorithm. Table of Content What is K-Means Clustering How it &hellip; <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_mi_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0},"categories":[15,11,16],"tags":[],"_links":{"self":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/221"}],"collection":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/comments?post=221"}],"version-history":[{"count":3,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/221\/revisions"}],"predecessor-version":[{"id":1049,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/221\/revisions\/1049"}],"wp:attachment":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/media?parent=221"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/categories?post=221"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/tags?post=221"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}