<jupyter_start><jupyter_text>K Means Clustering  IntroductionThe goal of this tutorial is to teach you how the K-Means Clustering Algorithm (also sometimes referred to as Lloyd's algorithm) works. Clustering is an important data science topic and K-Means is a good and easy to understand algorithm that clusters data efficiently. The K-Means algorithm is implemented in both scipy and sklearn, so I'll give an example on how to use the function implemented in scipy. Unfortunately a one-line function call and a couple of import statements  provides a very unsatisfactory black-box explanation, so I'll also break down my implementation and go through step by step how it works to assist in understanding the algorithm.  Why do we want to Cluster?The goal of clustering is to group together objects in ways that make them similar. While its easy to find ways to classify different objects, grouping different objects of the same time is less intuitive. For example its easy to group different kinds of plants, but its hard to group different plants of a specific kind. To explain why clustering is useful I'm going to give an example. Assume you're the father of six children. The amount they eat and their QPA are shown below:![Image of Table](https://i.gyazo.com/1c193fd43ad2ba7f4bf117a9a3760eb9.png)You cluster your data and find that their are two groups of children, those that eat more and have higher grades, and those that don't eat enough and have low grades. Because your children should be eating enough and have a high QPA, you start a new initiative in your house to increase their calorie intake. As a result, your children's grades go up and you feel like a good father.While this example is a bit idealistic, the point is that being able to look at groups of data rather than individual data may be useful. K-Means clustering is an algorithm that clusters your data into K different groups.  How K-Means Clustering works Preliminary ThingsTo start off we'll need to import some of the libraries we'll use to both implement and run the algorithm.<jupyter_code>import scipy.spatial
import scipy.cluster
import numpy
import pandas<jupyter_output><empty_output><jupyter_text>We imported scipy.spatial because that gives us a distance function, and scipy.cluster because this has a good implementation of kmeans. Numpy was imported just for some minor formatting and pandas was imported just to make reading the data easier.Moving from here, we need to gather some data from somewhere.<jupyter_code>#Import data and manipulate it
df = pandas.read_csv("Data.txt")
data = numpy.array(df)
d = len(data[0])
print df.head()
print data[0:5]<jupyter_output>StoreTime  FoodTime  MoneySpent
0   5.517744  3.121328         212
1  10.374635  3.093572          35
2   5.347070  3.677584         267
3   0.557013  0.225849           0
4   8.938141  8.466370           9
[[  5.51774379e+00   3.12132849e+00   2.12000000e+02]
 [  1.03746350e+01   3.09357176e+00   3.50000000e+01]
 [  5.34707025e+00   3.67758407e+00   2.67000000e+02]
 [  5.57013081e-01   2.25849452e-01   0.00000000e+00]
 [  8.93814131e+00   8.46637004e+00   9.00000000e+00]]<jupyter_text>On my computer, I've generated some made up data about a fictional shopping mall and I import it here. Each row corresponds to a customer, the first column is the number of hours they spent in stores, the second column is the number of hours they spent in the food court, and the third column is how much money they spent. I also manipulate it into a form that makes it nicer to manipulate and put it into a form that scipy is more comfortable in using. In addition, I declare a value $d$ that corresponds to the number of numeric columns of the data, or the dimension of each row. Description of the AlgorithmThe goal of the algorithm is to cluster the data into k different groups. Each group will be determined by a mean (hence the name K-Means). The data in each group is the data thats closest to that group's mean, so each piece of data is compared to all the means before clustering it. The data is all vectorized, so subtracting two vectors from each other doesn't yield a nice scalar distance that we can nicely compare. As a result we use the standard euclidean distance to get the distance from one point to another.The euclidean distance is given by the formula: ![Image of ED](http://mines.humanoriented.com/classes/2010/fall/csci568/portfolio_exports/mvoget/similarity/euclidean_formula.png)Scipy conveniently implements this below is an example of this.<jupyter_code>u = [3.0, 4.0, 5.0]
v = [1.0, 7.0, 8.5]
print scipy.spatial.distance.euclidean(u,v)<jupyter_output>5.02493781056<jupyter_text>So the distance between u and v is 5.024937810560445.So to formalize K-Means more, the goal of the algorithm is to find means $m_1 ... m_k$ so that when we cluster $x_1 ... x_n$ each with dimension $d$ into sets $S_1 ... S_k$ with a mean $m_i$ corresponding to the $S_i$; the value: $$ \sum_{i=1}^{k} \sum\nolimits_{x \in S_i} Dist(m_i, x) $$is minimized. If you don't understand this don't worry, just think of each $x_i$ as a row in our data and each $S_i$ as a cluster, so were trying to minimize the overall distance between each row and its corresponding mean.The actual algorithm takes in the data matrix and a variable k, and consists of three steps, two of which are repeated until a stabile state is reached. We already initialized the data matrix, so I'm going to initialize k to 5 in the following step.  The number itself is arbitrary; we could've chosen any integer.<jupyter_code>k = 5<jupyter_output><empty_output><jupyter_text>Now onto the algorithm. Initial Assignment StepThe first time the algorithm is run, an initial k-means have to be generated. In later steps, these means will be swapped out with means that are calculated, so in reality our choice of initial means isn't that important. A simple way to do this is to just pick k different distinct rows.In code this looks like:<jupyter_code>def initial_assignment_step(data, k):
    mean_indices = random.sample(range(len(data)), k)
    means = []
    for x in mean_indices:
        means.append(data[x])
    assert(len(means) == k)
    #Note that len(means) = k, this is because we have K means!
    return means

initial_means = initial_assignment_step(data,k)
initial_means = numpy.array(map(list,initial_means))
print initial_means
#this map is just for legibility<jupyter_output>[[  10.22455901    2.20833011   66.        ]
 [   5.51774379    3.12132849  212.        ]
 [   6.20949545    2.5277507    21.        ]
 [   5.75583542    3.67822151  257.        ]
 [   4.46315823    3.72946159   93.        ]]<jupyter_text>Now that we can get k initial means, we can move onto doing the real stuff.  Assignment StepIn this step we're going to assign each vector in our data matrix to a mean, and then put that vector in the corresponding means group. If a vector is equidistant between two means, we just pick one arbitrarily. This isn't really that important, so I'm just going to choose the lesser mean. In code this looks like:<jupyter_code>def assignment_step(data, k, means):
    Groups = []
    for j in range(k):
        Groups.append([])
    for x in data:
        lowestDist = 0.0
        currentDist = 0.0
        index = 0
        for (i, m) in enumerate(means):
            if i == 0:
                lowestDist = scipy.spatial.distance.euclidean(x,m)
            else:
                currentDist = scipy.spatial.distance.euclidean(x,m)
                if currentDist < lowestDist:
                    lowestDist = currentDist
                    index = i
        Groups[index].append(x)
        
    return Groups

initial_groups = assignment_step(data,k,initial_means)
for x in initial_groups:
    print map(list,x[0:2])
#this is done just for legibility reasons<jupyter_output>[[4.84035004363, 3.9495744520899998, 48.0], [10.163285175499999, 4.1809467493800003, 45.0]]
[[5.5177437886099998, 3.12132848685, 212.0], [4.2502543348300001, 3.8210388844599996, 159.0]]
[[10.374634955599999, 3.0935717611699998, 35.0], [0.55701308055999998, 0.22584945181499999, 0.0]]
[[5.34707025195, 3.6775840680599998, 267.0], [7.7967448707000004, 4.3251014556800005, 279.0]]
[[3.6996544916199996, 3.3593513017400003, 109.0], [4.46436971363, 1.3606990424300001, 120.0]]<jupyter_text>Essentially we just iterate through the data, comparing the row of data to each mean, then taking the one with the least distance and assigning the row of data to that mean.This is a form of clustering, as all of the data is sorted into groups. However with K-means, we want to minimize the overall distance, and because of the arbitrary way we chose our initial means, theres a decent chance the data is poorly grouped on the first run. For example if we randomly chose all the "largest" values of our data, (ie all the values with the maximum distance from 0) we would have most of the data belonging to maybe one or two groups, and a couple groups that are practically empty. For this reason the next step is necessary: Update StepNow were going to update the previous means with the mean of each group. For mathematical/statistical reasons that are beyond the scope of this tutorial, this also provies an effective minimization of the overall distance after a while. Again we have vectors and not scalars, so the summing and dividing done in calculating the mean of the group will have to be done over the vector. Doing this is shown in the code block below:<jupyter_code>def update_step(data, k, means, Groups):
    new_means = []
    for i,group in enumerate(Groups):
        total = [0.0]*d
        new_average = [0.0]*d
        for x in group:
            total = numpy.add(total, x)
        if len(group) != 0:
            new_average = numpy.divide(total, len(group))
        else:
            new_average = means[i]      
        new_means.append(new_average)
    return new_means

updated = update_step(data,k,imeans,igroups)
updated = numpy.array(map(list,updated))
print updated
#again this is just for legibility<jupyter_output>[[   4.9065641     2.22294779   55.95804196]
 [   3.11526665    1.34345171    8.61363636]
 [   6.56309741    3.211719    115.23021583]
 [   7.43706805    3.50358388  168.31775701]
 [   9.04262588    5.13114479  301.36290323]]<jupyter_text>Now again, we have a new set of means, so we can cluster the data again and repeat the assignment step. This gives us more groups to recalculate the means of and we can repeat this proccess ad infinum. But it's probably more useful to have our code terminate at some point. Observe that each step of the proccess better minimizes the overall distance created by the groups. This means that our code will eventually stop updating the means when its found the optimal means to cluster by. This can be observed when the means stop updating after the update step. Because we've found the optimal means in this case, we tell our code to stop and return the groups when this has happened.To summarize, if our codes last update step changed the means, then repeat the assignment step with the new means. If it didn't update the means, then just terminate and return the groups.  Compiling all of the steps and adding this at the end, this looks like:<jupyter_code>def K_Means(Data, k):
    means = initial_assignment_step(Data, k)
    Converge = False
    while(not Converge):
        Converge = True
        groups = assignment_step(Data, k, means)
        new_means = update_step(Data, k, means, groups)
        for x in range(k):
            for y in range(d):
                if new_means[x][y] != means[x][y]:
                    Converge = False
                    break
            if not Converge:
                break
        if not Converge:
            means = new_means
    return means

final_means = K_Means(data, k)
final_means = numpy.array(map(list,final_means))
print final_means
#this map is just to increase legibility<jupyter_output>[[   8.72154309    4.46323827  275.75      ]
 [   7.53850042    3.68237143  174.16949153]
 [   5.87301089    2.72322091   89.32046332]
 [  10.03701529    7.09422004  412.35294118]
 [   3.65325761    1.60738179   19.88888889]]<jupyter_text>Analyzing this, we can see that there are 5 groups of people, and the relationship between time spent in the mall and money spent seems to be linear. We could then decided to perform a linear regression test, and perhaps alter our mall to make people want to spend more time in it.Also note that K-means returns the means to center by instead of the groups. This is because looking at means is a lot easier than looking at all of elements of the groups. If we wanted the groups, we could just run:<jupyter_code>final_groups = assignment_step(data,k,final_means)
for x in final_groups:
    print map(list,x[0:2])<jupyter_output>[[5.34707025195, 3.6775840680599998, 267.0], [7.7967448707000004, 4.3251014556800005, 279.0]]
[[5.5177437886099998, 3.12132848685, 212.0], [4.2502543348300001, 3.8210388844599996, 159.0]]
[[3.6996544916199996, 3.3593513017400003, 109.0], [4.46436971363, 1.3606990424300001, 120.0]]
[[11.582370178900002, 7.9798539898600005, 399.0], [10.9156570504, 3.2662977305099998, 355.0]]
[[10.374634955599999, 3.0935717611699998, 35.0], [0.55701308055999998, 0.22584945181499999, 0.0]]<jupyter_text>And retrieve the groups of those means.Everything we just did was an implementation of the K-means algorithm. However the reason I showed the implementation was to explain how the algorithm worked. In reality, if one needed to use the algorithm, they could just use the scipy implementation. This is shown below.<jupyter_code>whiteData = scipy.cluster.vq.whiten(data)
means = scipy.cluster.vq.kmeans(whiteData,k)
whiteKMeans = K_Means(whiteData,k)
print means
print numpy.array(map(list,whiteKMeans))<jupyter_output>(array([[ 2.76577608,  2.4747515 ,  2.86300917],
       [ 2.49716964,  0.85819445,  1.40533603],
       [ 0.4596895 ,  0.22888238,  0.17316674],
       [ 1.33239881,  0.81885774,  0.68065887],
       [ 2.68194495,  2.52826367,  0.83683654]]), 0.73861273601569377)
[[ 2.65857428  0.82905551  1.38494161]
 [ 2.73951891  2.44772531  2.94778629]
 [ 2.77149105  2.62234841  0.94186971]
 [ 1.45301811  0.9512388   0.82986899]
 [ 0.5643769   0.27033836  0.21752513]]<jupyter_text>The scipy implementation requires the data to be whitened first. This is essentially just taking all the data and normalizing it around a certain mean. This just makes the data easier to work with and speeds up the K-Means algorithm.In addition, the scipy implementation returns an additional value called the distortion, this is something I didn't really cover, but its basically the difference between the means of the second to last and last iteration of the algorithm.Also, you'll notice minor differences in the means of our implementation and the means of the scipy implementation. This is because the scipy implementation has a cap on the number of iterations, increasing this cap yields means that are closer to our uncapped version. Due to the unbounded iterations, my algorithm is slower but it produces a lower minimum. Below is the calculated minimum of the scipy implementation and my implementation. As you can see, allowing the algorithm to run unbounded gives you a very small decrease in the minimum, so in general its not usually worth it.<jupyter_code>def Minimization(data,k,means):
    Groups = assignment_step(data,k,means)
    minimin = 0.0
    for i,group in enumerate(Groups):
        for x in group:
            minimin += scipy.spatial.distance.euclidean(x,means[i])
    return minimin  

print Minimization(data,k,means[0])
print Minimization(data,k,whiteKMeans)<jupyter_output>124313.465044
124240.149273<jupyter_text>Alternatively if you want to increase the number of iterations, or be less strict with the distortion before termination, you could run:<jupyter_code>iters300 =  scipy.cluster.vq.kmeans(whiteData,k,iter = 300)
iters500 = scipy.cluster.vq.kmeans(whiteData,k,iter = 500)
HighThresh = scipy.cluster.vq.kmeans(whiteData,k,thresh = 1.0)
print iters300
print iters500
print HighThresh<jupyter_output>(array([[ 1.33282289,  0.85382657,  0.72719083],
       [ 0.47512432,  0.23061185,  0.17704085],
       [ 2.69864945,  2.39321051,  2.85467586],
       [ 2.70302495,  2.5618893 ,  0.90708191],
       [ 2.57680938,  0.78137645,  1.3206238 ]]), 0.73771246681950631)
(array([[ 2.57443115,  0.74056347,  1.24181101],
       [ 2.68821411,  2.33526385,  2.84169914],
       [ 1.33317507,  0.88242158,  0.74957913],
       [ 2.73432911,  2.57479862,  0.95058634],
       [ 0.48859565,  0.23763605,  0.1829261 ]]), 0.73764362617046331)
(array([[ 0.61176075,  0.28801172,  0.25212836],
       [ 2.80169878,  2.60797752,  1.04213226],
       [ 2.43557925,  0.56669169,  0.99467786],
       [ 2.69771285,  2.13856165,  2.80485918],
       [ 1.40471746,  1.18201807,  0.89632452]]), 0.75133401190072224)
{'fraction_non_alphanumeric': 0.07459510580446861, 'fraction_numerical': 0.131457619103913, 'mean_word_length': 3.73921568627451, 'pattern_counts': {'":': 0, '<': 40, '<?xml version=': 0, '>': 39, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 4, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '12', 'dir': 'jupyter-structured-clean-dedup', 'id': '429028', 'license': 'MIT', 'n_tokens_mistral': 6653, 'n_tokens_neox': 5216, 'n_words': 2112, 'path': '2016/tutorial_final/146/KMeansClustering.ipynb', 'repo_name': 'zeromtmu/practicaldatascience.github.io', 'size': '16918'}