10
1
K-means is a standard unsupervised clustering algorithm, which, given a set of "points" and a number of clusters K, will assign each "point" to one of K clusters.
Pseudo-Code of K-means
Note that there are many variants of K-means. You have to implement the algorithm I am describing below. You may have some variation on the algorithm or use built-ins as long as you would get the same result as this algorithm given the same initial points.
In this challenge, all inputs will be points on the 2D plane (each point is represented by its coordinates in x and y).
Inputs: K, the number of clusters
P, the set of points
Choose K points of P uniformly at random
Each chosen point is the initial centroid of its cluster
Loop:
For each point in P:
Assign to the cluster whose centroid is the nearest (Euclidean distance)
In case of a tie, any of the tied cluster can be chosen
Recompute the centroid of each cluster:
Its x coordinate is the average of all x's of the points in the cluster
Its y coordinate is the average of all y's of the points in the cluster
Until the clusters don't change from one iteration to the next
Output: the set of clusters
Inputs and Outputs
- You may take K and P through
STDIN, or as a function argument, etc. - P and the points in P can be represented using any structure that is natural for set/lists in your language of choice.
- K is a strictly positive integer.
- You may assume that inputs are valid.
- There will always be at least K points in P.
- You may output the clusters to
STDOUT, return them from a function, etc. - The ordering of the clusters and the ordering inside the clusters is unimportant. -You can either return groups of points to represent clusters, or each point labeled with an identifier for the cluster (e.g. an integer).
Test cases
Since the resulting clusters depend on which points were initially chosen, you may not all get the same results (or the same result each time you run your code).
Therefore, only take the output as an example output.
Input:
K = 1
P = [[1,2.5]]
Output:
[[[1,2.5]]]
Input:
K = 3
P = [[4,8], [15,16], [23,42], [-13.37,-12.1], [666,-666]]
Output:
[[[666,-666]],[[-13.37,-12.1],[4,8]],[[15,16],[23,42]]]
Input:
K = 2
P = [[1,1], [1,1], [1,1]]
Output:
[[[1,1]],[[1,1],[1,1]]]
Scoring
This is code-golf, so the shortest answer in bytes wins.
Fatalize
Posted 2016-05-04T06:54:36.350
Reputation: 32 976
Are built-ins allowed when the results are indistinguishable from your algorithm? – Martin Ender – 2016-05-04T07:03:35.060
@MartinBüttner if you can justify that given the same initial points, it converges to the same result, yes. – Fatalize – 2016-05-04T07:07:44.773
Woud it also be acceptable to output labels of membership of a cluster for each point? (E.g. all points of the first cluster have label
1, all points of the second one have label2e.t.c) – flawr – 2016-05-04T11:03:39.597@flawr Yes, this is acceptable. – Fatalize – 2016-05-04T11:07:57.760
Degenerate test case:
K=2, P = [[1,1], [1,1], [1,1]]. – Peter Taylor – 2016-05-04T11:54:24.733