目录

  • 一、算法公式讲解
  • 二、算法流程
  • 三、算法实现代码
  • 四、代码结果分析
  • 五、K-Means库函数
  • 六、K-Means算法时间复杂度

觉得有用的,一腚要先点赞后收藏!!!气死人了,40多个收藏0点赞!!

一、算法公式讲解

对于
n代表了x有n维，x上标j表示第j维的特征，下标i表示该向量是第i个样本

簇中心坐标为：（当然，这也是重新计算簇中心坐标的方法！！）
向量 ui= ( ui ( 1 ), ui ( 2 ), ⋅ ⋅ ⋅ , ui ( j ), ⋅ ⋅ ⋅ , ui ( n ))u_i=(u_i^{(1)} ,u_i^{(2)}, ···, u_i^{(j)},···,u_i^{(n)})ui​=(ui(1)​,ui(2)​,⋅⋅⋅,ui(j)​,⋅⋅⋅,ui(n)​)，然后标量

其中一个维度,这里比如说是第2个样本的第1维特征 u21 u_{2}^{1}u21​,我就到这个第二个簇里面把这个簇所有点第一特征求和得到sum，然后把总和sum除以这个簇的大小| C2 C_2{}C2​|(这个簇里面点的个数)，然后就得到第2簇的簇中心的第1维的特征（坐标）
比如第一簇的簇中心坐标：

u1= ( u1 ( 1 ), u1 ( 2 ), u1 ( 3 ))u_1=(u_1^{(1)} ,u_1^{(2)},u_1^{(3)})u1​=(u1(1)​,u1(2)​,u1(3)​)
属于第一簇的坐标有
x2= ( 1 , 2 , 3 )x_2=(1 ,2,3)x2​=(1,2,3)
x3= ( 4 , 5 , 6 )x_3=(4 ,5,6)x3​=(4,5,6)
x4= ( 7 , 8 , 9 )x_4=(7 ,8,9)x4​=(7,8,9)

则

u1= (1 + 4 + 73,2 + 5 + 83,3 + 6 + 93) = ( 4 , 5 , 6 )u_1=(\frac{1+4+7}{3} ,\frac{2+5+8}{3},\frac{3+6+9}{3} )=(4,5,6)u1​=(31+4+7​,32+5+8​,33+6+9​)=(4,5,6)

二、算法流程


K-means算法首先随机分布簇中心，然后计算簇中心并重新分簇为一个周期进行迭代，直到簇稳定为止，

三、算法实现代码

有Kmeans.py和kmeansSamples.txt两个文件，kmeansSamples.txt记录的是所有点的坐标，Kmeans.py描述算法实现
Kmeans.py文件如下

# -*- coding: utf-8 -*-import numpy as npimport matplotlib.pyplot as pltdef L2(vecXi, vecXj):'''计算欧氏距离para vecXi：点坐标，向量para vecXj：点坐标，向量retrurn: 两点之间的欧氏距离'''return np.sqrt(np.sum(np.power(vecXi - vecXj, 2)))def kMeans(S, k, distMeas=L2):'''K均值聚类para S：样本集，多维数组para k：簇个数para distMeas：距离度量函数，默认为欧氏距离计算函数return sampleTag：一维数组，存储样本对应的簇标记return clusterCents：一维数组，各簇中心retrun SSE:误差平方和'''print('k = ' , k)m = np.shape(S)[0] # 样本总数sampleTag = np.zeros(m)print('sampleTag.shape=',sampleTag)# 随机产生k个初始簇中心n = np.shape(S)[1] # 样本向量的特征数print('n = ' , n)clusterCents = np.mat([[-1.93964824,2.33260803],[7.79822795,6.72621783],[10.64183154,0.20088133]])#clusterCents = np.mat(np.zeros((k,n)))#for j in range(n):#minJ = min(S[:,j]) #rangeJ = float(max(S[:,j]) - minJ)#clusterCents[:,j] = np.mat(minJ + rangeJ * np.random.rand(k,1))sampleTagChanged = TrueSSE = 0.0while sampleTagChanged: # 如果没有点发生分配结果改变，则结束sampleTagChanged = FalseSSE = 0.0# 计算每个样本点到各簇中心的距离# m是样本总数for i in range(m):minD = np.infminIndex = -1# k是簇中心个数for j in range(k):# S样本集，clusterCents样本中心点d = distMeas(clusterCents[j,:],S[i,:])if d < minD:minD = dminIndex = jif sampleTag[i] != minIndex: sampleTagChanged = TruesampleTag[i] = minIndexSSE += minD**2print(clusterCents)plt.scatter(clusterCents[:,0].tolist(),clusterCents[:,1].tolist(),c='r',marker='^',linewidths=7)plt.scatter(S[:,0],S[:,1],c=sampleTag,linewidths=np.power(sampleTag+0.5, 2))plt.show()print(SSE)# 重新计算簇中心for i in range(k):ClustI = S[np.nonzero(sampleTag[:]==i)[0]]clusterCents[i,:] = np.mean(ClustI, axis=0)return clusterCents, sampleTag, SSEif __name__=='__main__':samples = np.loadtxt("kmeansSamples.txt")clusterCents, sampleTag, SSE = kMeans(samples, 3)#plt.scatter(clusterCents[:,0].tolist(),clusterCents[:,1].tolist(),c='r',marker='^')#plt.scatter(samples[:,0],samples[:,1],c=sampleTag,linewidths=np.power(sampleTag+0.5, 2))plt.show()print(clusterCents)print(SSE)

kmeansSamples.txt文件如下

8.764743691132109049e+00 1.497536962729086341e+014.545778445909218313e+00 7.394332431706460262e+005.661841772908352333e+00 1.045327224311696668e+016.020055532521467967e+00 1.860759073162559929e+011.256729723000295529e+01 5.506569916803323750e+004.186942275051188211e+00 1.402615035721461290e+015.726706075832996845e+00 8.375613974148174989e+004.099899279500291094e+00 1.444273323355928795e+012.257178930021525254e+00 1.977895587652345855e+004.669135451288612515e+00 7.717803834787531070e-018.121947597697801058e+00 7.976212807755792555e-017.972277764807800260e-02 -1.938666197338206221e+008.370047062442882435e+00 1.077781799178707622e+016.680973199869320922e+00 1.553118858170866545e+015.991946943553537963e+00 1.657732863976965021e+015.641990155271871643e+00 1.554671013661827672e+01-2.925147643580102041e+00 1.108844569740028163e+014.996949605297930752e+00 1.986732057663068707e+003.866584099986317025e+00 -1.752825909916766900e+002.626427441224858939e+00 2.208897582166075324e+015.656225833870900388e+00 1.477736974879376675e+01-3.388227926726261607e-01 5.569311423852095544e+001.093574481611491223e+01 1.124487205516641275e+014.650235760178413003e+00 1.278869502885029341e+018.498485127403823114e+00 9.787697108749913610e+007.530467091751554598e+00 8.502325665434069535e+006.171183705302398792e+00 2.174394049079376856e+01-9.333949569013078040e-01 1.594142490265068712e+00-6.377004909329702542e+00 3.463894089865578341e+007.135980906743346175e+00 1.417794597480970609e+01

四、代码结果分析

第一次迭代，簇中心分布不太合理（红色三角形代表簇中心）

第二次迭代，簇中心重新计算，因此簇中心分布比第一次更合理

第3次迭代

第四次迭代

五、K-Means库函数

KMeans(n_clusters=8, *, init=‘k-means++’, n_init=‘k-means++’, n_init=10,max_iter=300, tol=0.0001, verbose=0, random_state=None, copy_x=True, algorithm=‘auto’)
链接：Sklearn关于K-Means的API介绍
相关输人参数和返回值，在网站上有详细介绍，建议 直接看原版文档，这里仅介绍几个重要参数，其他内容不再赘述。

  • init 参数提供了三种产生筷中心的方法：“K-means++”指定产生较大间距的筷中心(2.1.4节)；“random”指定随机产生簇中心；由用户通过一个ndarrav 数组指定初始筷中心。
  • n_init 参数指定了算法运行次数，它在不指定初始筷中心时，通过多次运行算法，最终选择最好的结果作为输出。
  • max iter 参数指定了一次运行中的最大迭代次数。在大规模数据集中，算法往往要耗费大量的时间，可通过指定迭代次数来折中耗时和效果。
  • tol 参数指定了算法收敛的國值。在大规模数据集中，算法往往难以完全收敛，即达到连续两次相同的分筷需要耗费很长时间,可通过指定國值来折中耗时和最优目标。
  • algorithm 参数指定了是否采用elkan k-means 算法来简化距离计算。该算法比经典的k-means 算法在迭代速度方面有很大的提高。但该算法不适用于稀疏的样本数据。值“full”指定采用经典k-means 算法。值“ellkan”指定采用 elkan k-means 算法。值“auto”自动选择，在稠密数据时采用 elkan k-means 算法，在稀疏数据时采用经典k-means 算法。

六、K-Means算法时间复杂度

设样本总数为 m，分簇数为k。一次迭代过程中，以样本与簇中心的距离计算为基本运算,需要 m × km \times km×k。如果迭代次数为t（，则算法的时间复杂度是 O( m × k × tm \times k \times tm×k×t)。
算法运行不需要增长额外辅助空问，以样本和簇中心存储空间为基本空间,空间复杂度是0（ m + km+km+k）。
由于m,k,t可认为是常量,因此算法的时间复杂度和空间复杂度都可认为是线性的 O ( N )O(N)O(N) .