Cluster analysis - Unweighted pair-group average

Clustering is a task of grouping a set of objects in such a way that the objects in the same class are similar to each other and the objects in different classes are distinct. Cluster analysis is employed in many fields such as machine learning, pattern recognition, image analysis, etc.

In this kata, your task is to implement a simple clustering technique called 'Unweighted pair-group average'. This method takes a set of 2D points and the desired number of final clusters. Initially, each point forms its own cluster. The most similar (least distant) clusters are iteratively merged until the target number of clusters is reached.

The distance metric between two clusters is defined as the average distance between all pairs of points from the two clusters. For example: 
```
Cluster 1: (0, 0), (0, 1)
Cluster 2: (4, 3)
Distance = (sqrt((0-4)^2 + (0-3)^2) + sqrt((0-4)^2 + (1-2)^2)) / 2
```

Input:
- ```points``` - a list of 2D points ```[(1, 1), (3, 5), (4, 4), (8, 2), (0, 1)]```
- ```n``` - the desired number of clusters

Output:
- list of clusters, each cluster is a list of points
- points in each cluster should be sorted in ascending order
- the list of clusters should also be sorted in ascending order

Example:
- ```cluster(3, [(1, 1), (3, 5), (4, 4), (8, 2), (0, 1)])```
- should return 
```[ [(0, 1), (1, 1)],
     [(3, 5), (4, 4)],
     [(8, 2)]
   ]
```
   
Notes:
- the coordinates ```(x, y)``` are chosen from interval ```<0, 1000>```
- ```0 < len(points) <= 100```
- ```0 < n <= len(points)```
- there is always only one unique solution
- there are no duplicate points in the input

Difficulty: introductory

Starter code:

def cluster(points, n):
	

Solutions:
from sklearn.cluster import KMeans

# Doesn't work for big tests, too bad
def cluster_kmeans(points, n):
    kmeans = KMeans(n_clusters=n)
    kmeans.fit(points)
    res = [[] for _ in range(n)]
    for i,p in zip(kmeans.labels_, points):
        res[i].append(p)
    return sorted(map(sorted, res))


from itertools import combinations, product, starmap
import numpy as np

memo_points = {}
def point_dist(p1, p2):
    key = (p1, p2) if p1 < p2 else (p2, p1)
    if not key in memo_points: memo_points[key] = np.linalg.norm(np.array(key[0]) - np.array(key[1]))
    return memo_points[key]

memo_clusters = {}
def cluster_dist(clusters):
    key = tuple(map(tuple, clusters))
    if not key in memo_clusters: memo_clusters[key] = np.mean(list(starmap(point_dist, product(*key))))
    return memo_clusters[key]

def cluster(points, n):
    clusters = [[p] for p in points]
    while len(clusters) > n:
        c1, c2 = min(combinations(clusters, 2), key=cluster_dist)
        c1.extend(c2)
        clusters.remove(c2)
    return sorted(map(sorted, clusters))

import math
import random

def cluster(points, n):
    def distance(c1, c2):
        s = 0
        for p1 in c1:
            for p2 in c2:
                s += math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)
        return float(s) / (len(c1) * len(c2))

    def closest(cs):
        min_dist, i1, i2 = float('inf'), -1, -1
        for i in range(len(cs)):
            for j in range(i+1, len(cs)):
                dist = distance(cs[i], cs[j])
                if dist < min_dist:
                    min_dist = dist
                    i1, i2 = i, j
        return i1, i2

    def merge(cs, i1, i2):
        cs[i1].extend(cs[i2])
        del cs[i2]

    clusts = [[x] for x in points]
    while len(clusts) > n:
        ind1, ind2 = closest(clusts)
        merge(clusts, ind1, ind2)
    for i in range(len(clusts)):
        clusts[i] = sorted(clusts[i])
    return list(sorted(clusts))

from statistics import mean
from itertools import product
from math import sqrt, inf


def distance_between_points(point1, point2):
    return sqrt((point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2)


def distance_between_clusters(cluster1, cluster2):
    return mean(
        distance_between_points(point1, point2) for (point1, point2) in product(cluster1, cluster2)
    )


def merge_clusters(cluster1, cluster2):
    return sorted([*cluster1, *cluster2])


def identificator(cluster):
    return (cluster[0], len(cluster))


def update_distances(clusters, distances):
    for cluster1 in clusters:
        for cluster2 in clusters:
            id1 = identificator(cluster1)
            id2 = identificator(cluster2)
            if id1 != id2 and distances.get((id1, id2)) is None:
                distance = distance_between_clusters(cluster1, cluster2)
                distances[(id1, id2)] = distance
                distances[(id2, id1)] = distance


def clear_unactual_distances(distances, cluster1, cluster2):
    old_ids = [identificator(cluster1), identificator(cluster2)]
    new_distances = {k: v for k, v in list(distances.items()) if k[0] not in old_ids and k[1] not in old_ids}
    return new_distances
                

def pop_minimal_distance_pair(clusters, distances):
    minimal_ids = None
    minimal_distance = 10_000_000
    for ids_pair, distance in list(distances.items()):
        if distance < minimal_distance:
            minimal_distance = distance
            minimal_ids = ids_pair
    cluster1 = next(cluster for cluster in clusters if identificator(cluster) == minimal_ids[0])
    cluster2 = next(cluster for cluster in clusters if identificator(cluster) == minimal_ids[1])
    clusters.remove(cluster1)
    clusters.remove(cluster2)
    return (cluster1, cluster2)
    
def cluster(points, n):
    clusters = [[point] for point in points]
    distances = {}
    while n != len(clusters):
        update_distances(clusters, distances)
        cluster1, cluster2 = pop_minimal_distance_pair(clusters, distances)
        new_cluster = merge_clusters(cluster1, cluster2)
        clusters.append(new_cluster)
        distances = clear_unactual_distances(distances, cluster1, cluster2)
    return sorted(clusters)


def dist_between_clusters(cluster1, cluster2):
    res = 0
    n = 0
    for point1 in cluster1:
        for point2 in cluster2:
            res += ((point1[0]-point2[0])**2 + (point1[1]-point2[1])**2) ** 0.5
            n += 1
    return res / n

def cluster(points, n):
    clusters = [[point] for point in points]
    
    while n < len(clusters):
        min_dist, min1, min2 = None, None, None
        for i, cluster1 in enumerate(clusters[:-1]):
            for j, cluster2 in enumerate(clusters[i+1:]):
                dist = dist_between_clusters(cluster1, cluster2)
                if min_dist is None or dist < min_dist:
                    min_dist, min1, min2 = dist, i, i+1+j
        clusters[min1].extend(clusters[min2])
        clusters.pop(min2)
    
    for i in range(len(clusters)):
        clusters[i].sort()
    clusters.sort()
    
    return clusters


from itertools import product

def distance(p1, p2):
    return ((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) ** 0.5


def cluster(points, n):
    lista = [[en] for en in points]
    while len(lista) > n:
        min_pair, min_dist = (0, 0), float('inf')
        for i in range(len(lista) - 1):
            for j in range(i + 1, len(lista)):
                dist = 0
                pairs = list(product(lista[i], lista[j]))
                for pair in pairs:
                    dist += distance(pair[0], pair[1])
                dist /= len(pairs)
                if dist < min_dist:
                    min_dist = dist
                    min_pair = (i, j)
        lista[min_pair[0]].extend(lista[min_pair[1]])
        del(lista[min_pair[1]])
    lista = [sorted(en) for en in lista]
    return sorted(lista, key=lambda x: x[0])

def dist(p1, p2):
    return ((p1[0]-p2[0])**2+(p1[1]-p2[1])**2)**0.5

def MeanDist(clus1, clus2):
    c = 0
    for p1 in clus1:
        for p2 in clus2:
            c += dist(p1, p2)
    return c/(len(clus1)*len(clus2))

from sklearn.cluster import KMeans
from collections import defaultdict
def cluster(points, n):
    if len(points) < 20:
        pred = KMeans(n_clusters=n).fit_predict(points)
        ans = defaultdict(list)
        for x, y in zip(pred, points):
            ans[x].append(y)
        res = [sorted(i) for i in list(ans.values())]
        res = sorted(res, key=lambda x: x[0][0])
        return res
    
    clus = [[p] for p in points]
    leng = len(clus)
    while leng > n:
        md = float('inf')
        for i in range(leng):
            for j in range(i+1, leng):
                d = MeanDist(clus[i], clus[j])
                if d < md:
                    md = d
                    c = [clus[i] + clus[j]]
                    curr = [i, j]
        temp = [x for i, x in enumerate(clus) if i not in curr]
        clus = temp + c
        leng = len(clus)
    res = [sorted(i) for i in clus]
    res = sorted(res, key=lambda x: x[0][0])
    return res


from itertools import product, combinations
from math import hypot

def euclid(p):
    (x1, y1), (x2, y2) = p
    return hypot(x1 - x2, y1 - y2)

def sim(pc):
    pc1, pc2 = pc
    return sum(map(euclid, product(pc1, pc2))) / (len(pc1) * len(pc2))

def cluster(points, n):
    res = [[p] for p in points]
    while len(res) > n:
        p0, p1 = min(combinations(res, 2), key = sim)
        res.remove(p0)
        res.remove(p1)
        res.append(p0 + p1)
    return sorted(map(sorted, res))

from math import hypot
from statistics import mean

def cluster(points, n):
    cs = [[p] for p in points]
    def key(ij):
        return mean(dist(p1, p2) for p1 in cs[ij[0]] for p2 in cs[ij[1]])
    while len(cs) > n:
        i, j = min(((i, j) for i in range(len(cs)) for j in range(i)), key=key)
        cs[i] += cs[j]
        del cs[j]
    return sorted(map(sorted, cs))

def dist(a, b):
    return hypot(a[0] - b[0], a[1] - b[1])

import math
import numpy as np
import itertools

def cluster(points, n):
    
    def get_cluster_distance(cluster1, cluster2):
        
        # function to find distance between a single pair
        def get_point_distance(coord_1, coord_2):
            x1, y1 = coord_1
            x2, y2 = coord_2
            return math.sqrt( ((x1 - x2)**2) + ((y1 - y2)**2) )
        
        distances = []
        for point_i in cluster1:
            for point_j in cluster2:
                distances.append(get_point_distance(point_i, point_j))
        
        return np.mean(distances)
        
    # Initiate list of all clusters, initially every point is a cluster (its own list)
    all_clusters = [[point] for point in points]
    
    # Main function
    while len(all_clusters) > n:
        distances = []
        for i, j in itertools.combinations([ _ for _ in range(len(all_clusters))], 2):
            distances.append([i, j, get_cluster_distance(all_clusters[i], all_clusters[j])])
        minimum_distance_pair = min(distances, key = lambda x:x[2])
        i, j, distance = minimum_distance_pair
        all_clusters[i] = all_clusters[i] + all_clusters.pop(j)
        
    # Sort points in each cluster
    for i in range(len(all_clusters)):
        all_clusters[i] = sorted(all_clusters[i])
    # Sort each cluster
    return sorted(all_clusters)