@@ -0,0 +1,1341 @@
+from math import sqrt%0Afrom random import sample%0Afrom collections import defaultdict%0A%0A%0Adef sqr(a):%0A    return a*a%0A%0A%0Adef distance(a, b):%0A    if len(a) != len(b):%0A        raise ValueError('Vectors have different dimensions')%0A    return sqrt(sum(map(sqr, (x-y for x, y in zip(a, b)))))%0A%0A%0Adef allocate_clusters(vectors, centroids_indexes):%0A    clusters = defaultdict(list)%0A    for vector_index, vector in enumerate(vectors):%0A        centroid_index = min(centroids_indexes, key=lambda i: distance(vector, vectors%5Bi%5D))%0A        clusters%5Bcentroid_index%5D.append(vector_index)%0A    return clusters%0A%0A%0Adef get_centroid_index(vectors, members_indexes):%0A    current_cluster = (vectors%5Bi%5D for i in members_indexes)%0A    return min(members_indexes, key=lambda i: sum(map(sqr, (distance(vectors%5Bi%5D, x) for x in current_cluster))))%0A%0A%0Adef kmeans(vectors, clusters_count, centroids_indexes=None, max_iterations=100):%0A    clusters = None%0A    if centroids_indexes is None:%0A        centroids_indexes = sample(range(len(vectors)), clusters_count)%0A    for i in range(max_iterations):%0A        clusters = allocate_clusters(vectors, centroids_indexes)%0A        new_centroids = set(map(lambda x: get_centroid_index(vectors, x), clusters.values()))%0A        old_centroids = set(clusters.keys())%0A        if old_centroids == new_centroids:%0A            break%0A    return clusters%0A

Add k-means implementation