简介
K-Means 算法是一种十分常见的聚类分析方法，可将数据分为指定的几个集群。下面简述一下算法步骤。
1.分配第一次中心
在数据中挑选几个点作为不同集群的中心，初次挑选的中心会影响最后的分组结果。如下图
2.计算属于不同中心的数据
通常使用距离作为判断依据，数据点属于离它最近的中心
3.移动中心
将属于同一个中心的数据化为一集群，计算集群的新中心。我选择集群的平均值中心作为新中心，并将原中心移动到新的中心。
4.迭代
重复 2 和 3 步。直到发现中心不再变化，完成。
具体实现
我使用 Python 简单实现了一个例子，实际使用过程中更倾向直接调用 SciPY 的现成实现。
生成随机数据
在这简单填充随机生成的数据进行测试。
1
2
3
4
|
k=0
date=np.random.randint(0,225,size=[100,2])
dateList=[datePoint(i[0],i[1],0) for i in date]
pointlist=[[random.randint(0,225),random.randint(0,225)] for i in range(k)]
|
k 为中心点个数；date为随机生成的数据；dateList 保存数据与其所属中心点；pointlist 是中心，使用随机数初始化。
1
2
3
4
5
6
7
|
class datePoint:
x=y=0
point=0
def __init__(self,X,Y,Point=0) -> None:
self.x=X
self.y=Y
self.point=Point
|
我定义了一个类 dateList 与datePoint.point来储存数据点与它所属的中心。
计算数据点所属的中心
1
2
3
4
5
6
7
|
def calPoint(dateList:list,pointList:list):
for i in dateList:
flag=10000000 #一个足够大的数字
for ii in range(len(pointList)):
if(flag>((i.x-pointList[ii][0])**2+(i.y-pointList[ii][1])**2)):
flag=(i.x-pointList[ii][0])**2+(i.y-pointList[ii][1])**2
i.point=ii
|
遍历每一个数据点，在第二个循环中检查每一个中心到该点的距离，选择最小的那个。这里使用了一个足够大的数字保证第一次计算的距离会小于这个假想的中心点。
移动中心点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
def change_point(dateList:list,pointList:list):
new_point_list=[[0,0] for i in range(k)]
nums_point=[0 for i in range(k)]
for i in dateList:
new_point_list[i.point][0]+=i.x
new_point_list[i.point][1]+=i.y
nums_point[i.point]+=1
for i in range(k):
pr=new_point_list[i]
pr[0]=int(pr[0]/nums_point[i])
pr[1]=int(pr[1]/nums_point[i])
if new_point_list!=pointList:
for i in range(k):
pointList[i][0]=new_point_list[i][0]
pointList[i][1]=new_point_list[i][1]
print(pointList)
return True
else:
return False
|
先定义了一个数组 new_point_list 来储存新计算的中心点，然后 nums_point 储存属于每一个中心点的数据个数以方便最后计算平均值。在我这个精度下，点取整数即可。最后一个 if 用于判断中心发生了改变，就返回 True 反之为 False.
一些收尾工作
1
2
3
|
while change_point(dateList,pointlist):
calPoint(dateList,pointlist)
print(pointlist)
|
不停的迭代 2 和 3 步，直到中心不再移动。最后输出结果即可。
参考
[1].https://aishack.in/tutorials/kmeans-clustering/