k-means算法实现代码_k-means算法代码

本代码来自gihub地址。添加注释仅供理解。
这篇博客对k-means算法讲解比较详细。
K-means算法参考自《统计学习方法》

K-means算法：

• 输入：n个样本的集合
• 输出：样本集合的聚类

1. 初始化，随机取 k 个样本点作为初始聚类中心
2. 对样本进行聚类。对固定的类中心，计算样本到类中心距离，将每个样本指派到与其最近的中心的类中，构成聚类结果
3. 计算新的类中心。对聚类结果计算样本的均值，做为新的类中心
4. 如果迭代收敛或符合停止条件，停止迭代。否则，令 t = t + 1 ，返回 2步

算法实现：

# 小标注：无论是defaultdict还是{}，a.get() 如果key不存在都返回None。
# 对于defaultdict，a['b'] key不存在返回默认的[]；对于{}，a['b'] key不存在返回KeyError
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  # 记录所有点坐标的当前维度总和
        for p in points:
            dim_sum += p[dimension] # 所有点求和
        new_center.append(dim_sum / float(len(points))) # 计算当前维度的均值，并插入到中心点坐标中
    return new_center

# 输入点集列表data_set和已有的分配assignments (他们相同索引的元素是对应的)
# 计算每一个簇的中心点，返回k个新的中心
def update_centers(data_set, assignments):
    new_means = defaultdict(list) # 初始化字典
    centers = [] # 初始化中心点集合
    # zip() 函数用于将可迭代的对象作为参数，将对象中对应的元素打包成一个个元组，然后返回由这些元组组成的列表。
    # zip()函数形成的列表为：[[type,(x,y)],[type,(x,y)],[type,(x,y)],……,[type,(x,y)]]
    for assignment, point in zip(assignments, data_set):
        new_means[assignment].append(point)
    # 计算每一类元素的中心点，并添加到centers列表中
    for points in new_means.values():
        centers.append(point_avg(points))
    # 返回中心点集合
    return centers

# 输入所有点的集合data_points以及选取的K个中心点的集合centers
# 通过计算将每个节点分配给一个距离最短的中心点，并输出一个列表，存储有每个节点对应的中心的索引。
# 输出列表形式为：[center_index, center_index, center_index, ……, center_index]
# 对应的点集合为：[point1, point2, point3, ……, pointN]
# 这里data_points和assignments的长度是相等的
def assign_points(data_points, centers):
    assignments = []
    # 遍历点集，获取每一个点距离最近的中心点，并存储其索引。
    for point in data_points:
        shortest = float('inf')  # 最短距离，先初始化为正无穷大
        shortest_index = 0 # 最短距离对应的索引
        for i in range(len(centers)):
            val = distance(point, centers[i]) # 计算当前节点和中心点的距离
            # 找到距离当前节点最近的中心点
            if val < shortest:
                shortest = val
                shortest_index = i
        # 将距离当前节点最近的中心点索引存储到assignments列表中（该列表和存储所有点的列表data_points的索引是对应的！）
        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)

# 在节点范围内，随机选取k个点作为聚类中心并返回这k个点
def generate_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] # 节点第i维的值
            min_key = 'min_%d' % i # min_0,min_1,min_2,……,min_N
            max_key = 'max_%d' % i # max_0,max_1,max_2,……,max_N
            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

    # k为函数接收到的参数，表示要分成k类
    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]
            # uniform() 方法将随机生成下一个实数，它在 [x, y) 范围内
            rand_point.append(uniform(min_val, max_val))
        # 将生成的中点存储到中点列表中
        centers.append(rand_point)
    return centers

# 输入所有点集dataset以及聚类数目k，
def k_means(dataset, k):
    k_points = generate_k(dataset, k)  # 随机选出k个随机点作为中心
    assignments = assign_points(dataset, k_points) # 将所有点分配给距离最近的中心点
    print("initial assignments : %s" % (assignments))
    old_assignments = None
    # 迭代进行聚类，当两次聚类结果相同时，结束
    while assignments != old_assignments:
        new_centers = update_centers(dataset, assignments) # 根据当前的分配更新中心点
        old_assignments = assignments # 记录上一次分配结果
        assignments = assign_points(dataset, new_centers) # 将所有点分配给距离最近的中心点
    # 返回最终分类结果（一个存储对应中心点索引的队列）
    print("finial assignments : %s" % (assignments))
    return zip(assignments, dataset)


points = [
    [1, 2],
    [2, 1],
    [3, 1],
    [5, 4],
    [5, 5],
    [6, 5],
    [10, 8],
    [7, 9],
    [11, 5],
    [14, 9],
    [14, 14],
    ]
result = k_means(points, 3)
print (list(result))

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
'
运行
运行

运行结果：