其他
不足 20 行 Python 代码，高效实现 k-means 均值聚类算法！
以下文章来源于CSDN ，作者许文武
作者 | 许文武
责编 | 刘静
出品 | CSDN 博客
1import numpy as np
2
3def kmeans_xufive(ds, k):
4 """k-means聚类算法
5
6 k - 指定分簇数量
7 ds - ndarray(m, n)，m个样本的数据集，每个样本n个属性值
8 """
9
10 m, n = ds.shape # m：样本数量，n：每个样本的属性值个数
11 result = np.empty(m, dtype=np.int) # m个样本的聚类结果
12 cores = np.empty((k, n)) # k个质心
13 cores = ds[np.random.choice(np.arange(m), k, replace=False)] # 从m个数据样本中不重复地随机选择k个样本作为质心
14
15 while True: # 迭代计算
16 d = np.square(np.repeat(ds, k, axis=0).reshape(m, k, n) - cores)
17 distance = np.sqrt(np.sum(d, axis=2)) # ndarray(m, k)，每个样本距离k个质心的距离，共有m行
18 index_min = np.argmin(distance, axis=1) # 每个样本距离最近的质心索引序号
19
20 if (index_min == result).all(): # 如果样本聚类没有改变
21 return result, cores # 则返回聚类结果和质心数据
22
23 result[:] = index_min # 重新分类
24 for i in range(k): # 遍历质心集
25 items = ds[result==i] # 找出对应当前质心的子样本集
26 cores[i] = np.mean(items, axis=0) # 以子样本集的均值作为当前质心的位置 1import numpy as np
2
3# 加载数据
4def loadDataSet(fileName):
5 data = np.loadtxt(fileName,delimiter='\t')
6 return data
7
8# 欧氏距离计算
9def distEclud(x,y):
10 return np.sqrt(np.sum((x-y)**2)) # 计算欧氏距离
11
12# 为给定数据集构建一个包含K个随机质心的集合
13def randCent(dataSet,k):
14 m,n = dataSet.shape
15 centroids = np.zeros((k,n))
16 for i in range(k):
17 index = int(np.random.uniform(0,m)) #
18 centroids[i,:] = dataSet[index,:]
19 return centroids
20
21# k均值聚类
22def kmeans_open(dataSet,k):
23
24 m = np.shape(dataSet)[0] #行的数目
25 # 第一列存样本属于哪一簇
26 # 第二列存样本的到簇的中心点的误差
27 clusterAssment = np.mat(np.zeros((m,2)))
28 clusterChange = True
29
30 # 第1步 初始化centroids
31 centroids = randCent(dataSet,k)
32 while clusterChange:
33 clusterChange = False
34
35 # 遍历所有的样本（行数）
36 for i in range(m):
37 minDist = 100000.0
38 minIndex = -1
39
40 # 遍历所有的质心
41 #第2步 找出最近的质心
42 for j in range(k):
43 # 计算该样本到质心的欧式距离
44 distance = distEclud(centroids[j,:],dataSet[i,:])
45 if distance < minDist:
46 minDist = distance
47 minIndex = j
48 # 第 3 步：更新每一行样本所属的簇
49 if clusterAssment[i,0] != minIndex:
50 clusterChange = True
51 clusterAssment[i,:] = minIndex,minDist**2
52 #第 4 步：更新质心
53 for j in range(k):
54 pointsInCluster = dataSet[np.nonzero(clusterAssment[:,0].A == j)[0]] # 获取簇类所有的点
55 centroids[j,:] = np.mean(pointsInCluster,axis=0) # 对矩阵的行求均值
56
57 return clusterAssment.A[:,0], centroids 1def create_data_set(*cores):
2 """生成k-means聚类测试用数据集"""
3
4 ds = list()
5 for x0, y0, z0 in cores:
6 x = np.random.normal(x0, 0.1+np.random.random()/3, z0)
7 y = np.random.normal(y0, 0.1+np.random.random()/3, z0)
8 ds.append(np.stack((x,y), axis=1))
9
10 return np.vstack(ds) 1import time
2import matplotlib.pyplot as plt
3
4k = 4
5ds = create_data_set((0,0,2500), (0,2,2500), (2,0,2500), (2,2,2500))
6
7t0 = time.time()
8result, cores = kmeans_xufive(ds, k)
9t = time.time() - t0
10
11plt.scatter(ds[:,0], ds[:,1], s=1, c=result.astype(np.int))
12plt.scatter(cores[:,0], cores[:,1], marker='x', c=np.arange(k))
13plt.show()
14
15print(u'使用kmeans_xufive算法，1万个样本点，耗时%f0.3秒'%t)
16
17t0 = time.time()
18result, cores = kmeans_open(ds, k)
19t = time.time() - t0
20
21plt.scatter(ds[:,0], ds[:,1], s=1, c=result.astype(np.int))
22plt.scatter(cores[:,0], cores[:,1], marker='x', c=np.arange(k))
23plt.show()
24
25print(u'使用kmeans_open算法，1万个样本点，耗时%f0.3秒'%t)
测试结果如下：
1PS D:\XufiveGit\CSDN\code> py -3 .\k-means.py
2使用kmeans_xufive算法，1万个样本点，耗时0.0156550.3秒
3使用kmeans_open算法，1万个样本点，耗时3.9990890.3秒☞只因写了一段爬虫，公司 200 多人被抓！☞为什么我现在不建议你买 5G 手机？｜CSDN博文精选
☞三年一跳槽、拒绝“唯学历”，火速 Get 这份程序员求生指南！
☞确认！语音识别大牛Daniel Povey将入职小米，曾遭霍普金斯大学解雇，怒拒Facebook
☞【又是一波重点】深度解析服务器科普知识 ｜ CSDN博文精选
☞“国家队”入局! 中移动、银联等宣布区块链服务网络(BSN)正式内测！
☞行！嘀嗒不甘第二