{"id":364,"date":"2013-12-06T15:10:19","date_gmt":"2013-12-06T20:10:19","guid":{"rendered":"http:\/\/homepages.uc.edu\/~yaozo\/wordpress\/?p=364"},"modified":"2013-12-06T15:10:19","modified_gmt":"2013-12-06T20:10:19","slug":"k-means-clustering","status":"publish","type":"post","link":"https:\/\/zhuoyao.net\/index.php\/2013\/12\/06\/k-means-clustering\/","title":{"rendered":"K-Means Clustering"},"content":{"rendered":"

The Algorithm<\/em><\/span>
\nK-means (MacQueen, 1967<\/a>) is one of the simplest unsupervised learning algorithms that solve the well known clustering problem. The procedure follows a simple and easy way to classify a given data set through a certain number of clusters (assume k clusters) fixed a priori. The main idea is to define k centroids, one for each cluster. These centroids shoud be placed in a cunning way because of different location causes different result. So, the better choice is to place them as much as possible far away from each other. The next step is to take each point belonging to a given data set and associate it to the nearest centroid. When no point is pending, the first step is completed and an early groupage is done. At this point we need to re-calculate k new centroids as barycenters of the clusters resulting from the previous step. After we have these k new centroids, a new binding has to be done between the same data set points and the nearest new centroid. A loop has been generated. As a result of this loop we may notice that the k centroids change their location step by step until no more changes are done. In other words centroids do not move any more.
\nFinally, this algorithm aims at minimizing an\u00a0objective function<\/em>, in this case a squared error function. The objective function<\/span><\/p>\n

\"\"\u00a0,<\/p>\n

where\u00a0\"\"\u00a0is a chosen distance measure between a data point\u00a0\"\"\u00a0and the cluster centre\u00a0\"\", is an indicator of the distance of the\u00a0n<\/em>\u00a0data points from their respective cluster centres.<\/span><\/p>\n

The algorithm is composed of the following steps:<\/span><\/p>\n

 <\/p>\n\n\n\n
\n
    \n
  1. Place K points into the space represented by the objects that are being clustered. These points represent initial group centroids.
    \n<\/span><\/em><\/li>\n
  2. Assign each object to the group that has the closest centroid.
    \n<\/em><\/span><\/li>\n
  3. When all objects have been assigned, recalculate the positions of the K centroids.
    \n<\/em><\/span><\/li>\n
  4. Repeat Steps 2 and 3 until the centroids no longer move. This produces a separation of the objects into groups from which the metric to be minimized can be calculated.<\/em><\/span><\/li>\n<\/ol>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    Although it can be proved that the procedure will always terminate, the k-means algorithm does not necessarily find the most optimal configuration, corresponding to the global objective function minimum. The algorithm is also significantly sensitive to the initial randomly selected cluster centres. The k-means algorithm can be run multiple times to reduce this effect.<\/span><\/p>\n

    K<\/span>-means is a simple algorithm that has been adapted to many problem domains. As we are going to see, it is a good candidate for extension to work with fuzzy feature vectors.<\/span><\/p>\n

    \n

    An example<\/em><\/span>
    \nSuppose that we have n sample feature vectors\u00a0x<\/strong>1<\/sub>,\u00a0x<\/strong>2<\/sub>, …,\u00a0x<\/strong>n<\/sub>\u00a0all from the same class, and we know that they fall into k compact clusters, k < n. Let\u00a0m<\/strong>i<\/sub>\u00a0be the mean of the vectors in cluster i. If the clusters are well separated, we can use a minimum-distance classifier to separate them. That is, we can say that\u00a0x<\/strong>\u00a0is in cluster i if ||\u00a0x<\/strong>\u00a0–\u00a0m<\/strong>i<\/sub>\u00a0|| is the minimum of all the k distances. This suggests the following procedure for finding the k means:<\/span><\/p>\n