I'm trying to apply k-means$\|$ clustering in PySpark.

According to this paper, there is an oversampling factor, $l$, that would affect the model's cost.

I couldn't find any parameter regarding oversampling factor in PySpark's k-means function. There is a parameter called initializationSteps but there is no proper definition for that.

Is there a way I could use oversampling factor in k-means function?


2 Answers 2


Based on the paper you set k but want to sample greater than k and apply the log calculation.

I would recommend using the foreach function. Where you could say foreach() apply further reach than k.

where the following aglo from the paper could be interpreted as follows.

Algorithm 2 k-means||(k, ) initialization.

1: C ← sample a point uniformly at random from X
2: ψ ← φX(C)
3: for O(log ψ) times do
4: C 0 ← sample each point x ∈ X independently with probability px =·d2(x,C) φX(C)
5: C ← C ∪ C0
6: end for
7: For x ∈ C, set wx to be the number of points in X closer to x than any other point inC
8: Recluster the weighted points in C into k clusters


get points of k = 2
points [(1,1),(1,2),(2,2)]

centroid is placed in middle for this example and

c1 = [(1,1),(1,2)]

This was achieved with the over sample of Euclid foreach() point that satisfies the over sampling requirement.

see example here which uses for each:

# Cluster the data into two classes using PowerIterationClustering
model = PowerIterationClustering.train(similarities, 2, 10)

model.assignments().foreach(lambda x: print(str(x.id) + " -> " + str(x.cluster)))

So you will need to write the distance into the lambda.(if you provide code easier to help you).

K distance = k distance on perimeter which is the bottom red line in diagram enter image description here

 .foreach(lambda x: kdistance[get average] + then check prob(k prime) of k)

share some code and sample data please


Hope this article will give you a headstart on the same.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.