{"id":443,"date":"2017-01-15T16:22:16","date_gmt":"2017-01-16T00:22:16","guid":{"rendered":"http:\/\/konukoii.com\/blog\/?p=443"},"modified":"2017-01-15T23:44:12","modified_gmt":"2017-01-16T07:44:12","slug":"5-min-tutorial-k-means-clustering-in-python","status":"publish","type":"post","link":"https:\/\/konukoii.com\/blog\/2017\/01\/15\/5-min-tutorial-k-means-clustering-in-python\/","title":{"rendered":"5-Min Tutorial: K-Means Clustering In Python"},"content":{"rendered":"Reading Time: <\/span> 4<\/span> minutes<\/span><\/span>

K-Means Clustering is a common machine learning tool that allows to separate data into \"clusters\" (groups). Intuitively, you can imagine plotting each datapoint into a field (could be 2-D,3-D, or n-D field) and then looking at which points are close to which, trying to distinguish groups.<\/p>\n

In one of my previous\u00a0projects in which we analyzed\u00a0Spam in Soundcloud<\/a> we actually used K-Means to group together similar types of users. This allowed us to more clearly separate and see groups of musicians, fans, and spam.<\/p>\n

Understanding the algorithm<\/strong><\/span><\/h5>\n

The K-Means algorithm is actually surprisingly intuitive and simple, yet very powerful.<\/p>\n

Take a look at the animation below (sorce:\u00a0David Runyan<\/a>), as you read through the algorithmic steps.<\/p>\n

    \n
  1. Select number of clusters (refereed to as K) and randomly assign the center points of this clusters anywhere near your dataset points.<\/li>\n
  2. Update Cluster Assignments: For each point in the dataset, find which is the closest cluster and assign that point to it.<\/li>\n
  3. Update Cluster Center: For each point in a given cluster, find the average center between them all and choose that to be the new cluster center.<\/li>\n
  4. Repeat step 2 and 3 until the cluster centers are no longer changing. Convergence tends to be surprisingly quick for most datasets.<\/li>\n<\/ol>\n
    \"K-Means
    K-Means Clustering Visualized - Credit: David Runyan<\/figcaption><\/figure>\n
    Coding the algorithm<\/strong><\/span><\/h5>\n

    The first thing we will do is define a distance function. In our case a simple Euclidean Distance function will be more than enough. Notice that we want to allow for any number of dimensions.<\/p>\n

    \r\n#Euclidian Distance between two d-dimensional points\r\ndef eucldist(p0,p1):\r\n    dist = 0.0\r\n    for i in range(0,len(p0)):\r\n        dist += (p0[i] - p1[i])**2\r\n    return math.sqrt(dist)\r\n<\/pre>\n
    Next, we want to code the actual K-Means algorithm. Initially we will designate an max # of iterations and randomly choose centers for the clusters. I like choosing a random datapoint as my center, as it makes things simpler.<\/p>\n
    \r\n#K-Means Algorithm\r\ndef kmeans(k,datapoints):\r\n\r\n    # d - Dimensionality of Datapoints\r\n    d = len(datapoints[0]) \r\n    \r\n    #Limit our iterations\r\n    Max_Iterations = 1000\r\n    i = 0\r\n    \r\n    cluster = [0] * len(datapoints)\r\n    prev_cluster = [-1] * len(datapoints)\r\n    \r\n    #Randomly Choose Centers for the Clusters\r\n    cluster_centers = []\r\n    for i in range(0,k):\r\n        new_cluster = []\r\n        #for i in range(0,d):\r\n        #    new_cluster += [random.randint(0,10)]\r\n        cluster_centers += [random.choice(datapoints)]\r\n\r\n        #Sometimes The Random points are chosen poorly and so there ends up being empty clusters\r\n        #In this particular implementation we want to force K exact clusters.\r\n        #To take this feature off, simply take away "force_recalculation" from the while conditional.\r\n        force_recalculation = False\r\n<\/pre>\n
    We will now start the clustering loop, which will only end if we reach Max_iterations or when our clusters stop changing.<\/p>\n
    \r\n    while (cluster != prev_cluster) or (i > Max_Iterations) or (force_recalculation) :\r\n        \r\n        prev_cluster = list(cluster)\r\n        force_recalculation = False\r\n        i += 1\r\n<\/pre>\n
    Next, for every point in the field we will find which is the closest cluster center to it and have it align itself with it.<\/p>\n
    \r\n        #Update Point's Cluster Alligiance\r\n        for p in range(0,len(datapoints)):\r\n            min_dist = float("inf")\r\n            \r\n            #Check min_distance against all centers\r\n            for c in range(0,len(cluster_centers)):\r\n                \r\n                dist = eucldist(datapoints[p],cluster_centers[c])\r\n                \r\n                if (dist < min_dist):\r\n                    min_dist = dist  \r\n                    cluster[p] = c   # Reassign Point to new Cluster\r\n<\/pre>\n
    Then we will update the cluster's center position. This is done by taking the average position of all the points in the given cluster. Notice that if we find a cluster which has 0 members, we force the center to randomly move to a new spot. (This is done because we want to enforce the number of centers to be k, and once a cluster has no members, there is no way to add new members to it.)<\/p>\n
    \r\n        #Update Cluster's Position\r\n        for k in range(0,len(cluster_centers)):\r\n            new_center = [0] * d\r\n            members = 0\r\n            for p in range(0,len(datapoints)):\r\n                if (cluster[p] == k): #If this point belongs to the cluster\r\n                    for j in range(0,d):\r\n                        new_center[j] += datapoints[p][j]\r\n                    members += 1\r\n            \r\n            for j in range(0,d):\r\n                if members != 0:\r\n                    new_center[j] = new_center[j] \/ float(members) \r\n                \r\n                #This means that our initial random assignment was poorly chosen\r\n                #Change it to a new datapoint to actually force k clusters\r\n                else: \r\n                    new_center = random.choice(datapoints)\r\n                    force_recalculation = True\r\n                    print "Forced Recalculation..."\r\n                    \r\n            \r\n            cluster_centers[k] = new_center\r\n<\/pre>\n
    Finally we can now use our program by simply feeding it a list of datapoints. Notice that these datapoints can be tuples of whatever size one would want. Also you can enforce the number of k clusters too.<\/p>\n
    \r\n#TESTING THE PROGRAM#\r\nif __name__ == "__main__":\r\n    #2D - Datapoints List of n d-dimensional vectors. (For this example I already set up 2D Tuples)\r\n    #Feel free to change to whatever size tuples you want...\r\n    datapoints = [(3,2),(2,2),(1,2),(0,1),(1,0),(1,1),(5,6),(7,7),(9,10),(11,13),(12,12),(12,13),(13,13)]\r\n\r\n    k = 2 # K - Number of Clusters\r\n      \r\n    kmeans(k,datapoints) \r\n<\/pre>\n
    Complete Code<\/span><\/strong><\/h5>\n
    This was a fun little script that was surprisingly useful for\u00a0a couple of homeworks and project that I did last quarter and I thought I would share with you guys. Hopefully you have found this small write-up useful, and as always feel free to contact me with any questions. Cheers!<\/p>\n