TuSimple Interview Questions

Implement the k-means clustering algorithm in python from scratch, given the following:

• A two-dimensional NumPy array data_points that is an arbitrary number of data points (rows) n and an arbitrary number of columns m.
• Number of k clusters k.
• The initial centroids value of the data points at each cluster initial_centroids.

Return a list of the cluster of each point in the original list data_points with the same order (as a integer).

Example

After clustering the points with two clusters, the points will be clustered as follows.

Note: There could be an infinite number of separating lines in this example.

Example

#Input
data_points = [(0,0),(3,4),(4,4),(1,0),(0,1),(4,3)]
k = 2
initial_centroids = [(1,1),(4,5)]


#Output 

k_means_clustering(data_points,k,initial_centroids) -> [0,1,1,0,0,1]