from collections import defaultdict
from random import uniform
from math import sqrt
def point_avg(points):
dimensions = len(points[0])
new_center = []
for dimension in range(dimensions):
dim_sum = 0 # dimension sum
for p in points:
dim_sum += p[dimension]
# average of each dimension
new_center.append(dim_sum / float(len(points)))
return new_center
def update_centers(data_set, assignments):
new_means = defaultdict(list)
centers = []
for assignment, point in zip(assignments, data_set):
new_means[assignment].append(point)
for points in new_means.values():
centers.append(point_avg(points))
return centers
def assign_points(data_points, centers):
assignments = []
for point in data_points:
shortest =float('inf') # positive infinity
shortest_index = 0
for i in range(len(centers)):
val = distance(point, centers[i])
if val < shortest:
shortest = val
shortest_index = i
assignments.append(shortest_index)
return assignments
def distance(a, b):
"""
"""
dimensions = len(a)
_sum = 0
for dimension in range(dimensions):
difference_sq = (a[dimension] - b[dimension]) ** 2
_sum += difference_sq
return sqrt(_sum)
def generate_k(data_set, k):
"""
给定“data_set”，它是一个数组数组，
找出每个坐标的最小值和最大值，一个范围。
在范围之间生成“k”个随机点。
返回范围内随机点的数组。
"""
centers = []
dimensions = len(data_set[0])
min_max = defaultdict(int)
for point in data_set:
for i in range(dimensions):
val = point[i]
min_key = 'min_%d' % i
max_key = 'max_%d' % i
if min_key not in min_max or val < min_max[min_key]:
min_max[min_key] = val
if max_key not in min_max or val > min_max[max_key]:
min_max[max_key] = val
for _k in range(k):
rand_point = []
for i in range(dimensions):
min_val = min_max['min_%d' % i]
max_val = min_max['max_%d' % i]
rand_point.append(uniform(min_val, max_val))
centers.append(rand_point)
return centers
def k_means(dataset, k):
k_points = generate_k(dataset, k)
assignments = assign_points(dataset, k_points)
old_assignments = None
while assignments != old_assignments:
new_centers = update_centers(dataset, assignments)
old_assignments = assignments
assignments = assign_points(dataset, new_centers)
for each in zip(assignments, dataset):
print(each)
data = [[0.697, 0.460, 1],
[0.774, 0.376, 1],
[0.634, 0.264, 1],
[0.608, 0.318, 1],
[0.556, 0.215, 1],
[0.430, 0.237, 1],
[0.481, 0.149, 1],
[0.437, 0.211, 1],
[0.666, 0.091, 0],
[0.243, 0.267, 0],
[0.245, 0.057, 0],
[0.343, 0.099, 0],
[0.639, 0.161, 0],
[0.657, 0.198, 0],
[0.360, 0.370, 0],
[0.593, 0.042, 0],
[0.719, 0.103, 0],
[0.359, 0.188, 0],
[0.339, 0.241, 0],
[0.282, 0.257, 0],
[0.748, 0.232, 0],
[0.714, 0.346, 1],
[0.483, 0.312, 1],
[0.478, 0.437, 1],
[0.525, 0.369, 1],
[0.751, 0.489, 1],
[0.532, 0.472, 1],
[0.473, 0.376, 1],
[0.725, 0.445, 1],
[0.446, 0.459, 1]]
k_means(data, 4)