<p><div><div><div><div data-show-faces="false" data-height="21" data-width="100" data-layout="button_count" data-send="true" data-href="https://www.r-bloggers.com/machine-learning-explained-kmeans/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="http://enhancedatascience.com/2017/10/24/machine-learning-explained-kmeans/"> Enhance Data Science</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<p>Kmeans is one of the most popular and simple algorithm to discover underlying structures in your data. The goal of kmeans is simple, split your data in k different groups represented by their mean. The mean of each group is assumed to be a good summary of each observation of this cluster.</p>
<h2>Kmeans Algorithm</h2>
<p>We assume that we want to split the data into k groups, so we need to find and assign k centers. How to define and find these centers?</p>
<p>They are the solution to the equation:  <span> <strong><img alt="min sum_{i}^N sum_{j}^K O_i^j||x_i-mu_j ||^2 " title="min sum_{i}^N sum_{j}^K O_i^j||x_i-mu_j ||^2 " src="http://s0.wp.com/latex.php?latex=min+%5Csum_%7Bi%7D%5EN%C2%A0%5Csum_%7Bj%7D%5EK+O_i%5Ej%7C%7Cx_i-%5Cmu_j+%7C%7C%5E2+&bg=ffffff&%23038;fg=000&%23038;s=0" class="latex"> </strong></span> where<strong> <span> <img alt="O_i^j = 1 " title="O_i^j = 1 " src="http://s0.wp.com/latex.php?latex=O_i%5Ej+%3D+1+&bg=ffffff&%23038;fg=000&%23038;s=0" class="latex"> </span>  </strong> if the observation<strong> i</strong> is assigned to the center <strong>j</strong> and<strong> 0</strong> otherwise.</p>
<p> </p>
<p>Basically, this equation means that we are looking for the k centers which will minimize the distance between them and the points of their cluster. This is an optimization problem, but since the function, we want to minimize is not convex and some variables are binary, it cannot be solved in classic ways with gradient descent.<br>
The usual way to solve it is the following:</p>
<ol>
<li>Initialize randomly the centers by selecting k-observations</li>
<li>While some convergence criterion is not met
<ol>
<li>Assign each observation to its closest center</li>
<li>Update each center. The new centers are the mean of the observation of each group.</li>
<li>Update the convergence criterion.</li>
</ol>
</li>
</ol>
<h2>K-means from scratch with R</h2>
<p>Now that we have the algorithm in pseudocode, let’s implement kmeans from scratch in R. First,we’ll create some toys data based on five 2D gaussian distributions.</p>
<pre>
require(MASS)
require(ggplot2)
set.seed(1234)
set1=mvrnorm(n = 300, c(-4,10), matrix(c(1.5,1,1,1.5),2))
set2=mvrnorm(n = 300, c(5,7), matrix(c(1,2,2,6),2))
set3=mvrnorm(n = 300, c(-1,1), matrix(c(4,0,0,4),2))
set4=mvrnorm(n = 300, c(10,-10), matrix(c(4,0,0,4),2))
set5=mvrnorm(n = 300, c(3,-3), matrix(c(4,0,0,4),2))
DF=data.frame(rbind(set1,set2,set3,set4,set5),cluster=as.factor(c(rep(1:5,each=300))))
ggplot(DF,aes(x=X1,y=X2,color=cluster))+geom_point()
</pre>
<p>On this dataset, Kmeans will work well since each distribution has a circular shape. Here are what the data look like:<br>
<img data-orig-file="https://i1.wp.com/enhancedatascience.com/wp-content/uploads/2017/10/Cluster_ex1_kmeans.png?fit=714%2C431" data-orig-size="714,431" data-medium-file="https://i1.wp.com/enhancedatascience.com/wp-content/uploads/2017/10/Cluster_ex1_kmeans.png?fit=300%2C181" data-attachment-id="2423" data-image-meta="{" data-image-description="" src="https://i1.wp.com/enhancedatascience.com/wp-content/uploads/2017/10/Cluster_ex1_kmeans.png?resize=500%2C250" data-permalink="http://enhancedatascience.com/2017/10/24/machine-learning-explained-kmeans/cluster_ex1_kmeans/" data-large-file="https://i1.wp.com/enhancedatascience.com/wp-content/uploads/2017/10/Cluster_ex1_kmeans.png?fit=640%2C386" alt="Cluster kmeans dataset1" data-image-title="Cluster kmeans dataset1" sizes="(max-width: 500px) 100vw, 500px" data-comments-opened="1" class="wp-image-2423" data-recalc-dims="1"></p>
<p>Now that we have a dataset, let’s inplement kmeans.</p>
<h3>Initialisation of the centroids</h3>
<p>The initialisation of the centroids is crucial and will change how the algorithm behave. Here, we will wimply takes K random points from the data.</p>
<pre>
#Centroids initialisation
  centroids=data[sample.int(nrow(data),K),]
##Stopping criteria initilisation. 
  current_stop_crit=10e10
##Vector where the assigned centers of each points will be saved
  cluster=rep(0,nrow(data))
##Has the alogrithm converged ?
  converged=F
  it=1
</pre>
<h3>Assigning points to their clusters</h3>
<p>At each iteration, every points will be assigned to its closest cluster. To do so, the euclidian distance between each points and each centers is computed, the lowest distance and the center for which it’s reached is saved.</p>
<pre>
###Iterating over observations
    for (i in 1:nrow(data))
    {
##Setting a high minimum distance
      min_dist=10e10
##Iterating over centroids
      for (centroid in 1:nrow(centroids))
      {
##Computing the L2 distance
        distance_to_centroid=sum((centroids[centroid,]-data[i,])^2)
##This centroid is the closest centroid to the point
        if (distance_to_centroid&lt;=min_dist)
        {
##The point is assigned to this centroid/cluster
          cluster[i]=centroid
          min_dist=distance_to_centroid
        }
      }
    }
</pre>
<h3>Centroids update</h3>
<p>Once each point has been assigned to the closest centroids, the coordinates of each centroid are updated. The new coordinates are the means of the observations which belongs to the cluster.</p>
<pre>
##For each centroid
    for (i in 1:nrow(centroids))
    {
##The new coordinates are the means of the point in the cluster
      centroids[i,]=apply(data[cluster==i,],2,mean)
    }
</pre>
<h3>Stopping criterion</h3>
<p>We do not want the algorithm to run indefinetely, hence we need a stopping criterion to stop the algorthm when we are close enough to a minimum. The criterion is simply that when the centroids stop moving, the algorithm should stop.</p>
<pre>
  while(current_stop_crit>=stop_crit &amp; converged==F)
  {
    it=it+1
    if (current_stop_crit&lt;=stop_crit)
    {
      converged=T
    }
    old_centroids=centroids
###Run previous step

####Recompute stop criterion
current_stop_crit=mean((old_centroids-centroids)^2)

</pre>
<h3>Complete function</h3>
<pre>
kmeans=function(data,K=4,stop_crit=10e-5)
{
  #Initialisation of clusters
  centroids=data[sample.int(nrow(data),K),]
  current_stop_crit=1000
  cluster=rep(0,nrow(data))
  converged=F
  it=1
  while(current_stop_crit>=stop_crit &amp; converged==F)
  {
    it=it+1
    if (current_stop_crit&lt;=stop_crit)
    {
      converged=T
    }
    old_centroids=centroids
    ##Assigning each point to a centroid
    for (i in 1:nrow(data))
    {
      min_dist=10e10
      for (centroid in 1:nrow(centroids))
      {
        distance_to_centroid=sum((centroids[centroid,]-data[i,])^2)
        if (distance_to_centroid&lt;=min_dist)
        {
          cluster[i]=centroid
          min_dist=distance_to_centroid
        }
      }
    }
    ##Assigning each point to a centroid
    for (i in 1:nrow(centroids))
    {
      centroids[i,]=apply(data[cluster==i,],2,mean)
    }
    current_stop_crit=mean((old_centroids-centroids)^2)
  }
  return(list(data=data.frame(data,cluster),centroids=centroids))
}
</pre>
<p>You can easily run the code to see your clusters:</p>
<pre>
res=kmeans(DF[1:2],K=5)
res$centroids$cluster=1:5
res$data$isCentroid=F
res$centroids$isCentroid=T
data_plot=rbind(res$centroids,res$data)
ggplot(data_plot,aes(x=X1,y=X2,color=as.factor(cluster),size=isCentroid,alpha=isCentroid))+geom_point()
</pre>
<p><img data-orig-file="https://i2.wp.com/enhancedatascience.com/wp-content/uploads/2017/10/Kmeans-final-cluster.png?fit=714%2C431" data-orig-size="714,431" data-medium-file="https://i2.wp.com/enhancedatascience.com/wp-content/uploads/2017/10/Kmeans-final-cluster.png?fit=300%2C181" data-attachment-id="2426" data-image-meta="{" data-image-description="" src="https://i2.wp.com/enhancedatascience.com/wp-content/uploads/2017/10/Kmeans-final-cluster.png?resize=640%2C386" data-permalink="http://enhancedatascience.com/2017/10/24/machine-learning-explained-kmeans/kmeans-final-cluster/" data-large-file="https://i2.wp.com/enhancedatascience.com/wp-content/uploads/2017/10/Kmeans-final-cluster.png?fit=640%2C386" alt="" data-image-title="Kmeans final clusters" sizes="(max-width: 640px) 100vw, 640px" data-comments-opened="1" class="wp-image-2426" data-recalc-dims="1"></p>
<h2>Exploring kmeans results</h2>
<p>Now let’s try the algorithm on two different datasets. First, on the 5 Gaussians distributions:<br>
<img data-orig-file="https://i1.wp.com/enhancedatascience.com/wp-content/uploads/2017/10/centroidsEvolution.gif?fit=480%2C480" data-orig-size="480,480" data-medium-file="https://i1.wp.com/enhancedatascience.com/wp-content/uploads/2017/10/centroidsEvolution.gif?fit=300%2C300" data-attachment-id="2425" data-image-meta="{" data-image-description="" src="https://i1.wp.com/enhancedatascience.com/wp-content/uploads/2017/10/centroidsEvolution.gif?resize=480%2C480" data-permalink="http://enhancedatascience.com/2017/10/24/machine-learning-explained-kmeans/centroidsevolution/" data-large-file="https://i1.wp.com/enhancedatascience.com/wp-content/uploads/2017/10/centroidsEvolution.gif?fit=480%2C480" alt="Evolution of centroids position in kmeans" data-image-title="Evolution of centroids position in kmeans" data-comments-opened="1" class="wp-image-2425" data-recalc-dims="1"><br>
The centroids move and split the data in clusters which are very close to the original ones. Kmeas is doing a great job here.<br>
Now, instead of having nice gaussian distributions, we will build three rings on into another.</p>
<pre>
##Building three sets
set1=data.frame(r=runif(300,0.1,0.5),theta=runif(300,0,360),set='1')
set2=data.frame(r=runif(300,1,1.5),theta=runif(300,0,360),set='2')
set3=data.frame(r=runif(300,3,5),theta=runif(300,0,360),set='3')
##Transformation in rings
data_2=rbind(set1,set2,set3)
data_2$x=data_2$r*cos(2*3.14*data_2$theta)
data_2$y=(data_2$r)*sin(2*3.14*data_2$theta)
</pre>
<p>The kmeans is performing very poorly on these new data. Actually, the euclidian distance is not adapted to this kind of problem, since the data are not in a circular shape.<br>
<img data-orig-file="https://i0.wp.com/enhancedatascience.com/wp-content/uploads/2017/10/Kmeans_ring.gif?fit=480%2C480" data-orig-size="480,480" data-medium-file="https://i0.wp.com/enhancedatascience.com/wp-content/uploads/2017/10/Kmeans_ring.gif?fit=300%2C300" data-attachment-id="2428" data-image-meta="{" data-image-description="" src="https://i0.wp.com/enhancedatascience.com/wp-content/uploads/2017/10/Kmeans_ring.gif?resize=480%2C480" data-permalink="http://enhancedatascience.com/2017/10/24/machine-learning-explained-kmeans/kmeans_ring/" data-large-file="https://i0.wp.com/enhancedatascience.com/wp-content/uploads/2017/10/Kmeans_ring.gif?fit=480%2C480" alt="" data-image-title="Kmeans on ring shaped data" data-comments-opened="1" class="wp-image-2428" data-recalc-dims="1"><br>
So before using kmeans, you should ensure that the data is in appropriate shapes, if not, you can apply transformations or change the distance you are using in the kmeans.</p>
<h2>The importance of a good initialisation</h2>
<p>The kmeans algorithm only looks for a local mimimum which is often not a global optimum. Hence, different initialisation can lead to very different results.<br>
<img data-orig-file="https://i2.wp.com/enhancedatascience.com/wp-content/uploads/2017/10/Centers_different_init.gif?fit=480%2C480" data-orig-size="480,480" data-medium-file="https://i2.wp.com/enhancedatascience.com/wp-content/uploads/2017/10/Centers_different_init.gif?fit=300%2C300" data-attachment-id="2429" data-image-meta="{" data-image-description="" src="https://i2.wp.com/enhancedatascience.com/wp-content/uploads/2017/10/Centers_different_init.gif?resize=480%2C480" data-permalink="http://enhancedatascience.com/2017/10/24/machine-learning-explained-kmeans/centers_different_init/" data-large-file="https://i2.wp.com/enhancedatascience.com/wp-content/uploads/2017/10/Centers_different_init.gif?fit=480%2C480" alt="Importance of initialisation for kmeans" data-image-title="Importance of initialisation for kmeans" data-comments-opened="1" class="wp-image-2429" data-recalc-dims="1"><br>
We ran the kmean algorithm over more than 60 different starting positions.As you can see, sometimes, the algorithm results in poor centroids due to an unlucky initialization. The solution to this is simply to run kmeans several times and to take the best centroids set. The quality of initialization can also be improved with <a rel="nofollow" href="https://en.wikipedia.org/wiki/K-means%2B%2B" target="_blank">kmeans ++</a>, the algorithm selects starting points which are less likely to perform poorly.</p>
<p>Want to learn more on Machine Learning ? Here is a selection of Machine Learning Explained posts:<br>
– <a rel="nofollow" href="http://enhancedatascience.com/2017/07/31/machine-learning-explained-dimensionality-reduction/" target="_blank">Dimensionality reduction</a><br>
– <a rel="nofollow" href="http://enhancedatascience.com/2017/07/19/machine-learning-explained-supervised-learning-unsupervised-learning-and-reinforcement-learning/" target="_blank">Supervised vs unsupervised vs reinforcement learning</a><br>
– <a rel="nofollow" href="http://enhancedatascience.com/2017/07/04/machine-learning-explained-regularization/" target="_blank">Regularization in machine learning</a></p>
<p>The post <a rel="nofollow" href="http://enhancedatascience.com/2017/10/24/machine-learning-explained-kmeans/" target="_blank">Machine Learning Explained: Kmeans</a> appeared first on <a rel="nofollow" href="http://enhancedatascience.com/" target="_blank">Enhance Data Science</a>.</p>
	<p>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="http://enhancedatascience.com/2017/10/24/machine-learning-explained-kmeans/"> Enhance Data Science</a></strong>.</div>
<hr>
<a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="https://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a rel="nofollow" href="https://www.r-project.org/" title="The R Project for Statistical Computing">R</a> news and <a rel="nofollow" href="https://www.r-bloggers.com/search/tutorial" title="R tutorials">tutorials</a> on topics such as: <a rel="nofollow" href="https://www.r-bloggers.com/search/data%20science" title="Data science">Data science</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data" title="Big Data">Big Data, <a rel="nofollow" href="https://www.r-users.com/" title="R jobs">R jobs</a>, visualization (<a rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2" title="ggplot and ggplot2 tutorials">ggplot2</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/boxplot" title="Boxplots using lattice and ggplot2 tutorials">Boxplots</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/map" title="Maps and gis">maps</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/animation" title="Animation in R">animation</a>), programming (<a rel="nofollow" href="https://www.r-bloggers.com/search/RStudio" title="RStudio IDE for R">RStudio</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/sweave" title="Sweave and literate programming">Sweave</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX" title="LaTeX in R">LaTeX</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/SQL" title="SQL and databases">SQL</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/eclipse" title="Eclipse IDE for R">Eclipse</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/git" title="git and github, Version Control System">git</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/hadoop" title="Large data in R using Hadoop">hadoop</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping" title="Web Scraping of google, facebook, yahoo, twitter and more using R">Web Scraping</a>) statistics (<a rel="nofollow" href="https://www.r-bloggers.com/search/regression" title="Regressions and ANOVA analysis tutorials">regression</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/PCA" title="principal component analysis tutorial">PCA</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/time+series" title="Time series">time series</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/trading" title="finance trading">trading</a>) and more...
<img alt="" width="1" src="http://feeds.feedburner.com/~r/RBloggers/~4/Kfyv3IL_Bos" height="1"></a></div>