Thursday, April 21, 2011

K-Means Clustering in Map Reduce


K-Means clustering involve the following logical steps

1) Determine the value of k
2) Determine the initial k centroids
3) Repeat until converge
- Determine membership: Assign each point to the closest centroid
- Update centroid position: Compute new centroid position from assigned members

Determine the value of K
So the answer is specific to the problem domain.



Determine the initial K centroids





kmeans(data) {
  initial_centroids = pick(k, data)
  old_centroids = initial_centroids
  while (true){
    new_centroids = readFromS3()
    if change(new_centroids, old_centroids) < delta {
    } else {
      old_centroids = new_centroids
  result = readFromS3()
  return result



Complexity Analysis
closest_centroid(point, listOfCentroids) {
  bestCentroid = listOfCentroids[0]
  minDistance = INFINITY
  for each centroid in listOfCentroids {
    distance = dist(point, centroid)
    if distance < minDistance {
      minDistance = distance
      bestCentroid = centroid
  return bestCentroid


Canopy clustering provide such a partitioning mechanism.

Canopy Clustering



1) Create the canopy centers, with one scan
  • Keep a list of canopies, initially an empty list

2) Assign data points to the canopies, with another scan
  • Start with a list of canopies from last step
  • When done, each data point will look like


closest_centroid(point, listOfCentroids) {
  bestCentroid = listOfCentroids[0]
  minDistance = INFINITY
  for each cent in listOfCentroids {
    if (not point.myCanopy.intersects(cent.myCanopy)) {
    distance = dist(point, centroid)
    if distance < minDistance {
      minDistance = distance
      bestCentroid = centroid
  return bestCentroid


Gaurav Gupta said...


I am trying to implement k-means + canopy clustering algorithm for a class project on reuter news data set.

The question I had was after the canopy clustering step there could be say 10 canopy centers. Suppose in k-means algorithm k=5 , how would you merge the canopy centers to just 5.


Gaurav Gupta said...

Never mind my previous comment. Just realized that k-means runs over all the points as before over k randomly selected centroids. But the distance calculation is reduced in a way. So for example pt p is assigned to canopy m , and kmeans centroid n, then is p and n are not in canopy then we return a large value or disregard the centroid n.

Javed Anjum Sheikh said...

Thanks for wonderfull information. I would like to know about

Micah L. Abrams said...

Excellent article on k-means and canopy clustering. I'd like to use canopy clustering to speed up my own clustering implementations, but I'm concerned about performing a sensitivity analysis with the two thresholds, T1 and T2, every time I apply the algorithm to a new data set. Do you think it is possible to automate the selection of these two thresholds? Have you read any articles on the topic?

rohit said...

do you think the following might be useful to select T1 and T2 - sort the points by ascending distance from the canopy center and set T2 = upper threshold of first quartile and T1 = lower threshold of third quartile. So all points that are in the first quartile are removed from further canopy processing. That way the T1, T2 would be dynamically decided based on the distribution of points from the canopy center

jia said...

Hi all,,,
does any one have k-means algorithm code for c language...
please please do share it with me

Best regards

jia said...

Hi all...
I need a favour from u...
If any one has k-means code for C
can any one plz share it with me....
plz plz its urgent..

my email id is

Best regards

Anonymous said...

first of all, thank you perfect your information.
i must implemented k-means cluster in big data system.
but i have problem map reduce modeling.

this is very useful to me.

thank you very much :)

ChaRaN AuLakH said...

Hi guys

Does anybody have the code for k-means clustering for map locations?


Unknown said...

Hi guys, Excellent article...
I am trying to implement k means algorithm for clustering web users with similar interests or behavior for which i have extracted required data points.i want to implement it in mapreduce framework but i am very new to this concept can any one send the code for it so that i can analyze and understand the things
my emailid is