blob: 7799f3d732cb6e8d050a205e304ec92e40ac8701 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
import math
import random as rand
def l2_pairwise_distance(v1, v2):
"""Euclidean distance from each point in v1 to each point in v2
Args:
v1: list of point 1
v2: list of point 2
Returns:
distance matrix between each point in v1 and v2
"""
nrow = len(v1)
ncol = len(v2)
dist_mat = [[0 for _ in range(ncol)] for _ in range(nrow)]
for i in range(nrow):
for j in range(ncol):
dist_mat[i][j] = math.sqrt((v1[i] - v2[j]) ** 2)
return dist_mat
def calculate_error(k_means_matrix):
"""Calculate the sum of distance from each point to its nearest cluster center
Args:
k_means_matrix: distance matrix of point to cluster center
Returns:
Sum of distance from each point to its nearest cluster center
"""
return sum([min(dist) for dist in k_means_matrix])
def k_means(x_input, n_cluster=3, n_iter=100, n_tries=10):
"""Perform 1-D k-means clustering on a list of numbers x_input
Args:
x_input: list of numbers
n_cluster: number of clusters
n_iter: number of iterations
Returns:
centers: list of n_cluster elements containing the cluster centers
min_dist_idx: list of len(x_input) elements containing the nearest cluster center's id
error_value: sum of all distance from each point to its nearest cluster center
"""
results = []
for _ in range(n_tries):
error_value = 0
rand.seed(None)
centers = sorted([rand.uniform(0.0, 100.0) for i in range(n_cluster)])
min_dist_idx = [0] * len(x_input)
i = 0
while i < n_iter:
failed = False
dist_mat = l2_pairwise_distance(x_input, centers)
error_value = calculate_error(dist_mat)
min_dist_idx = [dist.index(min(dist)) for dist in dist_mat]
centers = [0] * n_cluster
count = [0] * n_cluster
for j in range(len(x_input)):
centers[min_dist_idx[j]] += x_input[j]
count[min_dist_idx[j]] += 1
for j in range(n_cluster):
if count[j] == 0:
centers = sorted([rand.uniform(0.0, 100.0) for i in range(n_cluster)])
failed = True
break
if failed:
i = 0
continue
for j in range(n_cluster):
centers[j] = centers[j] / count[j]
i += 1
results.append((centers, min_dist_idx, error_value))
return min(results, key=lambda x: x[2])
|
