Python 中怎么实现一个k-means 均值聚类算法,很多新手对此不是很清楚,为了帮助大家解决这个难题,下面小编将为大家详细讲解,有这方面需求的人可以来学习下,希望你能有所收获。
scikti-learn 将机器学习分为4个领域,分别是分类(classification)、聚类(clustering)、回归(regression)和降维(dimensionality reduction)。k-means均值算法虽然是聚类算法中比较简单的一种,却包含了丰富的思想内容,非常适合作为初学者的入门习题。
关于 k-means 均值聚类算法的原理介绍、实现代码,网上有很多,但运行效率似乎都有点问题。今天稍微有点空闲,写了一个不足20行的 k-means 均值聚类算法,1万个样本平均耗时20毫秒(10次均值)。同样的数据样本,网上流行的算法平均耗时3000毫秒(10次均值)。差距竟然达百倍以上,令我深感意外,不由得再次向 numpy 献上膝盖!
以下是我的代码,包含注释、空行总共26行,有效代码16行。
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) # 以子样本集的均值作为当前质心的位置
这是网上比较流行的 k-means 均值聚类算法代码,包含注释、空行总共57行,有效代码37行。
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
函数create_data_set(),用于生成测试数据。可变参数 cores 是多个三元组,每一个三元组分别是质心的x坐标、y坐标和对应该质心的数据点的数量。
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秒
效果如下:
看完上述内容是否对您有帮助呢?如果还想对相关知识有进一步的了解或阅读更多相关文章,请关注亿速云行业资讯频道,感谢您对亿速云的支持。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。