在机器学习中，有无监督学习、监督学习和半监督学习三种学习方式。在无监督学习中，有一个叫聚类的玩意，对于聚类，有很多算法，其中最简单的就是今天要讲的 k-means 了。
概述
k-means 的执行过程非常简单，主要分为以下几步：
- 选取 k 个中心点（通常是随机选取）。
- 计算每一个数据点和 k 个点的距离，如果该数据点到第 i 个中心点距离最短，那么这个数据点就被归到了第 i 类。
- 计算每一个聚类的质心，并将其设置为中心点。
- 重复 2、3，直到聚类不变或者达到迭代次数（简单来说就是收敛）。
下面我以 iris 数据集为例手动实现一下 k-means 算法的过程，为了方便把数据和基于数据的操作封装在一起，这里我使用面向对象的方法来实现。
初始化
iris 数据集总共有 5 个字段（5 列），150 条数据（150 行）。这 5 个字段中的每一个字段分别表示花萼长度、花萼宽度、花瓣长度、花瓣宽度、类别，类别总共有 3 种可能——Iris Setosa、Iris Versicolour 和 Iris Virginica。所以在该算法中我们应该选取 k = 3，知道这些我们先写一个框架应该不是什么难事。
代码语言：javascript复制class KMeans:
def __init__(self):
self.sepal_length_in_cm = []
self.sepal_width_in_cm = []
self.petal_length_in_cm = []
self.petal_width_in_cm = []
self.k = 3
# noinspection PyUnusedLocal
self.classes = [[]for i in range(self.k)]
self.centers = []
self.load()
self.choose_centers()
for i in range(100):
self.classify()
self.modify()
for i in range(len(self.classes)):
print(f'{i 1}:{self.centers[i]}')
print(self.classes[i])载入数据集
载入数据集很简单，一行一行读取数据集文件，然后每一行按照逗号分割，如果分割后的长度为 5，那么我们就把前 4 个放到对应的字段列表中，也就是上面的 self.sepal_length_in_cm，self.sepal_width_in_cm，self.petal_length_in_cm，self.petal_width_in_cm。
代码语言：javascript复制 def load(self):
dataset = open('iris.data').readlines()
for data in dataset:
data = data.split(',')
if len(data) == 5:
self.sepal_length_in_cm.append(float(data[0]))
self.sepal_width_in_cm.append(float(data[1]))
self.petal_length_in_cm.append(float(data[2]))
self.petal_width_in_cm.append(float(data[3]))选择中心点
中心点的选取是随机选取，但需要注意的是范围，确保所选择的点在数据集每一个特征分量对应的范围中，不可以超出这个范围。那么在选择中心点之前，我们需要计算每一个特征分量的最大值和最小值，然后在每一个分量范围中随机选一个值，接着把选取到的值组成一个元组（也就是一个点），并把该元组添加到列表 self.centers 中，重复选择步骤 self.k 次。
代码语言：javascript复制 def choose_centers(self):
min_sepal_length, max_sepal_length = min(self.sepal_length_in_cm), max(self.sepal_length_in_cm)
min_sepal_width, max_sepal_width = min(self.sepal_width_in_cm), max(self.sepal_width_in_cm)
min_petal_length, max_petal_length = min(self.petal_length_in_cm), max(self.petal_length_in_cm)
min_petal_width, max_petal_width = min(self.petal_width_in_cm), max(self.petal_width_in_cm)
for i in range(self.k):
sepal_length = min_sepal_length (max_sepal_length-min_sepal_length)*random()
sepal_width = min_sepal_width (max_sepal_width-min_sepal_width)*random()
petal_length = min_petal_length (max_petal_length-min_petal_length)*random()
petal_width = min_petal_width (max_petal_width-min_petal_width)*random()
self.centers.append((sepal_length, sepal_width, petal_length, petal_width))计算距离
计算距离很简单，这里使用 Δxi 的平方和来表示距离的平方，因为距离的平方越小，距离也就越小，所以没有必要开根号。
代码语言：javascript复制 @staticmethod
def calculate_distance(p1, p2):
return (p2[0]-p1[0])**2 (p2[1]-p1[1])**2 (p2[2]-p1[2])**2 (p2[3]-p1[3])**2分类
计算每一个数据点和 k 个点的距离，如果该数据点到第 i 个中心点距离最短，那么这个数据点就被归到了第 i 类。
代码语言：javascript复制 def classify(self):
for i in range(len(self.sepal_length_in_cm)):
p = (self.sepal_length_in_cm[i], self.sepal_width_in_cm[i], self.petal_length_in_cm[i],
self.petal_width_in_cm[i])
distances = []
for center in self.centers:
distances.append((self.calculate_distance(p, center), self.centers.index(center)))
min_distance = distances[0][0]
min_distance_center = distances[0][1]
for j in range(len(distances)):
if min_distance > distances[j][0]:
min_distance = distances[j][0]
min_distance_center = distances[j][1]
self.classes[min_distance_center].append(p)修正
当分类完成之后，我们需要修正中心点的位置。在修正中心点位置之前，我们来想一个问题：之前选择的中心点会不会没有数据被归到，也就是代表它的数据完全没有，换句话说就是该点是无效的？真的有可能，这样就只能让它重新选择中心点并归类，然后判断，一直循环，直到每个中心点都可以有数据代表它。
修正中心点很简单，我们只要计算每一个聚类的质心即可，质心的计算很简单，就是每一个分量的平均值组成的元组（点）。
代码语言：javascript复制 def modify(self):
while[]in self.classes:
self.centers = []
self.choose_centers()
self.classify()
for i in range(len(self.classes)):
x1, x2, x3, x4 = [], [], [], []
for c in self.classes[i]:
x1.append(c[0])
x2.append(c[1])
x3.append(c[2])
x4.append(c[3])
x1, x2, x3, x4 = sum(x1)/len(x1), sum(x2)/len(x2), sum(x3)/len(x3), sum(x4)/len(x4)
self.centers[i] = (x1, x2, x3, x4)下面直接给出该程序的完整源码。
代码语言：javascript复制from random import random
class KMeans:
def __init__(self):
self.sepal_length_in_cm = []
self.sepal_width_in_cm = []
self.petal_length_in_cm = []
self.petal_width_in_cm = []
self.k = 3
# noinspection PyUnusedLocal
self.classes = [[]for i in range(self.k)]
self.centers = []
self.load()
self.choose_centers()
for i in range(100):
self.classify()
self.modify()
for i in range(len(self.classes)):
print(f'{i 1}:{self.centers[i]}')
print(self.classes[i])
def load(self):
dataset = open('iris.data').readlines()
for data in dataset:
data = data.split(',')
if len(data) == 5:
self.sepal_length_in_cm.append(float(data[0]))
self.sepal_width_in_cm.append(float(data[1]))
self.petal_length_in_cm.append(float(data[2]))
self.petal_width_in_cm.append(float(data[3]))
def choose_centers(self):
min_sepal_length, max_sepal_length = min(self.sepal_length_in_cm), max(self.sepal_length_in_cm)
min_sepal_width, max_sepal_width = min(self.sepal_width_in_cm), max(self.sepal_width_in_cm)
min_petal_length, max_petal_length = min(self.petal_length_in_cm), max(self.petal_length_in_cm)
min_petal_width, max_petal_width = min(self.petal_width_in_cm), max(self.petal_width_in_cm)
for i in range(self.k):
sepal_length = min_sepal_length (max_sepal_length-min_sepal_length)*random()
sepal_width = min_sepal_width (max_sepal_width-min_sepal_width)*random()
petal_length = min_petal_length (max_petal_length-min_petal_length)*random()
petal_width = min_petal_width (max_petal_width-min_petal_width)*random()
self.centers.append((sepal_length, sepal_width, petal_length, petal_width))
@staticmethod
def calculate_distance(p1, p2):
return (p2[0]-p1[0])**2 (p2[1]-p1[1])**2 (p2[2]-p1[2])**2 (p2[3]-p1[3])**2
def classify(self):
for i in range(len(self.sepal_length_in_cm)):
p = (self.sepal_length_in_cm[i], self.sepal_width_in_cm[i], self.petal_length_in_cm[i],
self.petal_width_in_cm[i])
distances = []
for center in self.centers:
distances.append((self.calculate_distance(p, center), self.centers.index(center)))
min_distance = distances[0][0]
min_distance_center = distances[0][1]
for j in range(len(distances)):
if min_distance > distances[j][0]:
min_distance = distances[j][0]
min_distance_center = distances[j][1]
self.classes[min_distance_center].append(p)
def modify(self):
while[]in self.classes:
self.centers = []
self.choose_centers()
self.classify()
for i in range(len(self.classes)):
x1, x2, x3, x4 = [], [], [], []
for c in self.classes[i]:
x1.append(c[0])
x2.append(c[1])
x3.append(c[2])
x4.append(c[3])
x1, x2, x3, x4 = sum(x1)/len(x1), sum(x2)/len(x2), sum(x3)/len(x3), sum(x4)/len(x4)
self.centers[i] = (x1, x2, x3, x4)
if __name__ == '__main__':
KMeans()运行结果如图所示。
