# Distributed k-means in Spark

I want to implement K-means algorithm in Spark. I am looking for a starting point and I found Berkeley's naive implementation. However, is that distributed?

I mean I see no mapreduce operations. Or maybe, when submitted in Spark, the framework actually makes the needed tricks under the hood to distribute the algorithm?

I also found that Spark shows mapreduce the exit and I am using Spark 1.6.

EDIT: This code produces a runtime error, check here.

In that link you posted, you can look at the python full solution here at the end and go through it to see what all is distributed. In short, some parts are distributed, like reading data from the file, but the very important parts like the distance computation are not.

Running down, we see:

sc = SparkContext("local[6]", "PythonKMeans")

This instantiates the context and creates a local cluster which the jobs will be submitted to

lines = sc.textFile(..)

This is still setting up. No operations have taken place yet. You can verify this by putting timing statements in the code

data = lines.map(lambda x: (x.split("#")[0], parseVector(x.split("#")[1])))

The lambda here will be applied to lines, so this operation will split the file in parallel. Note that the actual line also has a cache() at the end (see cache]). data is just a reference to the spark object in memory. (I may be wrong here, but I think the operation still doesn't happen yet)

count = data.count()

This forces the parallel computation to start, and the count to be stored. At the end, the reference data is still valid, and we'll use it for further computations. I'll stop with detailed explanations here, but wherever data is being used is a possible parallel computation. The python code itself is single threaded, and interfaces with the Spark cluster.

An interesting line is:

tempDist = sum(np.sum((centroids[x] - y) ** 2) for (x, y) in newCentroids.iteritems())

centroids is an object in python memory, as is newCentroids. So, at this point, all computations are being done in memory (and on the client, typically clients are slim, i.e. have limited capabilities, or the client is an SSH shell, so the computers resources are shared. You should ideally never do any computation here), so no parallelization is being used. You could optimize this method further by doing this computation in parallel. Ideally you want the python program to never directly handle individual points' $x$ and $y$ values.

• Great explanation, @Harsh! – Kyle. Feb 11 '16 at 2:04
• Tnx! So: We have our initial dataset, which is distributed (every node takes a subset of the dataset S). Then, every node computes distances (serially) and finds the new centroids for their respective S. Then what is happening? Every node continues running its local kmeans in its subset of the dataset or we split again the dataset to the nodes, but now we use the centroids computed in the previous iteration? – gsamaras Feb 12 '16 at 0:53

I don't know about that specific implementation, but we use the mllib k-means here at my work, to some degree of success. It is distributed and runs on Spark!

• Kyle yes I have seen that, but in my question I said: "I want to implement K-means algorithm in Spark". – gsamaras Feb 10 '16 at 23:07
• Ah. Sorry, I misread! – Kyle. Feb 10 '16 at 23:09
• It's OK Kyle, it's good info, thus my +1. I may explore the source code of mllib and compare it with the one I linked! I also updated my question, if that matters. – gsamaras Feb 10 '16 at 23:17
• No problem! That's a great place to start! – Kyle. Feb 10 '16 at 23:17
• And a big one too. I found this, looking into it now...github.com/apache/spark/tree/master/mllib/src/main/scala/org/… – gsamaras Feb 10 '16 at 23:22