K-均值聚类算法

Poblog 07月02日 2018


随机确定k个初始点作为质心,然后将数据集中的每个点分配到一个簇中,完成之后,每个簇的质心更新为该簇所有点的平均值

随机初始点算法流程

dataSet:
[[ 1.658985  4.285136]
 ....
 [-4.905566 -2.91107 ]]

k:2  质心数

n:2 列数

centroids: 存放随机初始点
[[0. 0.]
 [0. 0.]]


 循环n次
   依次取每列的最小值
   j=0 :  minJ:[[-5.379713]]
   得到本列最小值最大值之间的差值
   10.217851

   np.random.rand(k,1) 随机生成k个0-1之间的值
   centroids[:,j] 利用随机数和差值得到第j列
   [[3.07023768 0.        ]
   [1.3933703  0.        ]]

   循环完毕得到速记点centroids
   

向量欧氏距离计算
第一个点 vecA:[[1.658985 4.285136]]
第二个点 vecB:[[-3.453687  3.424321]]

欧氏距离计算公式np.sqrt(sum(np.power(vecA - vecB, 2)))



K-均值聚类算法执行流程
dataSet:
[[ 1.658985  4.285136]
 ....
 [-4.905566 -2.91107 ]]

 k:4  聚类的个数

 m:80 数据点的个数

 clusterAssment: 存储结果举证,第0列是中心点索引,第一列是错误率
 [[0. 0.]
 ....
 [0. 0.]]

 centroids:随机k个中心质点
 [[ 1.89683426 -2.66038997]
 [-2.25164184  5.0519057 ]
 [ 4.594932    1.54778567]
 [ 3.43668905 -2.55423253]]

标识符聚类是否改变(循环的依据)
clusterChanged=True

循环每一个点
初始化
minDist:inf 记录当前点距离聚类点的最小距离
minIndex:-1 记录距离最小点的聚类点的索引号
   循环每一个中心点
     依次计算当前点和每个中心点的欧氏距离distJI:5.902401970011532
           找到最小点和最小点对应的聚类点的索引号

        判断是否聚类中心点发生变化,如果变化设置clusterChanged=True进行下一次循环

记录中心点的索引号和欧氏距离的平方
clusterAssment[i,:] = minIndex,minDist**2

 clusterAssment:
 [[ 3.         16.15115014]
 ....
 [ 0.          0.        ]]

上面的步骤计算完毕不再发生变化之后循环k次更新中心点(质心更新为该簇所有点的平均值)
 cent:0

 [[ 4.838138 -1.151539]
 ....
 [ 4.479332 -1.764772]]

 np.nonzero(clusterAssment[:,0].A==cent) 质心为当前中心点的所有点
 np.mean(ptsInClust,axis=0)   所有点的平均值为新的质心

 centroids:最终的质心
 [[ 2.80293085 -2.7315146 ]
 [-3.38237045 -2.9473363 ]
 [ 2.6265299   3.10868015]
 [-2.46154315  2.78737555]]
  
 clusterAssment:最终各个点所属的质心和欧氏距离平方
 [[2.00000000e+00 2.32019150e+00]
 ....
 [1.00000000e+00 2.32143993e+00]]