Kmeans算法的Python实现(内附python教程分享)
Kmeans聚类
K-means算法是很典型的基于距离的聚类算法,采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。该算法认为簇是由距离靠近的对象组成的,因此把得到紧凑且独立的簇作为最终目标。动图来源.k个初始类聚类中心点的选取对聚类结果具有较大的影响,因为在该算法第一步中是随机的选取任意k个对象作为初始聚类的中心,初始地代表一个簇。该算法在每次迭代中对数据集中剩余的每个对象,根据其与各个簇中心的距离将每个对象重新赋给最近的簇。当考察完所有数据对象后,一次迭代运算完成,新的聚类中心被计算出来。如果在一次迭代前后,J的值没有发生变化,说明算法已经收敛。
算法步骤:
- 创建k个点作为起始支点(随机选择)
- 当任意一个簇的分配结果发生改变的时候
- 对数据集的每个数据点
- 对每个质心
- 计算质心与数据点之间的距离
- 将数据分配到距离其最近的簇
- 对每一簇,计算簇中所有点的均值并将其均值作为质心
iris
我们用非常著名的iris数据集。
from sklearn import datasets iris = datasets.load_iris() X, y = iris.data, iris.target data = X[:,[1,3]] # 为了便于可视化,只取两个维度 plt.scatter(data[:,0],data[:,1]);
iris
欧式距离
计算欧式距离,我们需要为每个点找到离其最近的质心,需要用这个辅助函数。
def distance(p1,p2): """ Return Eclud distance between two points. p1 = np.array([0,0]), p2 = np.array([1,1]) => 1.414 """ tmp = np.sum((p1-p2)**2) return np.sqrt(tmp) distance(np.array([0,0]),np.array([1,1])) 1.4142135623730951
随机质心
在给定数据范围内随机产生k个簇心,作为初始的簇。随机数都在给定数据的范围之内dmin + (dmax - dmin) * np.random.rand(k)实现。
def rand_center(data,k): """Generate k center within the range of data set.""" n = data.shape[1] # features centroids = np.zeros((k,n)) # init with (0,0).... for i in range(n): dmin, dmax = np.min(data[:,i]), np.max(data[:,i]) centroids[:,i] = dmin + (dmax - dmin) * np.random.rand(k) return centroids centroids = rand_center(data,2) centroids array([[ 2.15198267, 2.42476808], [ 2.77985426, 0.57839675]])
k均值聚类
这个基本的算法只需要明白两点。
- 给定一组质心,则簇更新,所有的点被分配到离其最近的质心中。
- 给定k簇,则质心更新,所有的质心用其簇的均值替换
当簇不在有更新的时候,迭代停止。当然kmeans有个缺点,就是可能陷入局部最小值,有改进的方法,比如二分k均值,当然也可以多计算几次,去效果好的结果。
def kmeans(data,k=2): def _distance(p1,p2): """ Return Eclud distance between two points. p1 = np.array([0,0]), p2 = np.array([1,1]) => 1.414 """ tmp = np.sum((p1-p2)**2) return np.sqrt(tmp) def _rand_center(data,k): """Generate k center within the range of data set.""" n = data.shape[1] # features centroids = np.zeros((k,n)) # init with (0,0).... for i in range(n): dmin, dmax = np.min(data[:,i]), np.max(data[:,i]) centroids[:,i] = dmin + (dmax - dmin) * np.random.rand(k) return centroids def _converged(centroids1, centroids2): # if centroids not changed, we say 'converged' set1 = set([tuple(c) for c in centroids1]) set2 = set([tuple(c) for c in centroids2]) return (set1 == set2) n = data.shape[0] # number of entries centroids = _rand_center(data,k) label = np.zeros(n,dtype=np.int) # track the nearest centroid assement = np.zeros(n) # for the assement of our model converged = False while not converged: old_centroids = np.copy(centroids) for i in range(n): # determine the nearest centroid and track it with label min_dist, min_index = np.inf, -1 for j in range(k): dist = _distance(data[i],centroids[j]) if dist < min_dist: min_dist, min_index = dist, j label[i] = j assement[i] = _distance(data[i],centroids[label[i]])**2 # update centroid for m in range(k): centroids[m] = np.mean(data[label==m],axis=0) converged = _converged(old_centroids,centroids) return centroids, label, np.sum(assement)
由于算法可能局部收敛的问题,随机多运行几次,取最优值
best_assement = np.inf best_centroids = None best_label = None for i in range(10): centroids, label, assement = kmeans(data,2) if assement < best_assement: best_assement = assement best_centroids = centroids best_label = label data0 = data[best_label==0] data1 = data[best_label==1]
如下图,我们把数据分为两簇,绿色的点是每个簇的质心,从图示效果看,聚类效果还不错。
fig, (ax1,ax2) = plt.subplots(1,2,figsize=(12,5)) ax1.scatter(data[:,0],data[:,1],c='c',s=30,marker='o') ax2.scatter(data0[:,0],data0[:,1],c='r') ax2.scatter(data1[:,0],data1[:,1],c='c') ax2.scatter(centroids[:,0],centroids[:,1],c='b',s=120,marker='o') plt.show()
最后,想学习Python的小伙伴们!
请关注+私信回复:“学习”就可以拿到一份我为大家准备的Python学习资料!
pytyhon学习资料
python学习资料
相关推荐
jiayuqicz 2020-04-25
kunfeifeifei 2018-02-12
阿艾辣悟叩德 2017-12-21
路漫 2020-05-30
从早忙到晚的闲人 2020-04-13
Happyunlimited 2019-11-09
YUAN 2019-06-25
learningCV 2017-04-12
诗眼天涯 2018-02-23
lzujiangge 2018-02-23
assastor 2018-02-23
香帅 2013-05-25