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: EASY

Starter code:
def cluster(points, n):
	

Solutions:
from sklearn.cluster import KMeans

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 = 10000000
	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):

		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)
	all_clusters = [[point] for point in points]
	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)
	for i in range(len(all_clusters)):
		all_clusters[i] = sorted(all_clusters[i])
	return sorted(all_clusters)