K-Means聚类

k-means算法

方法概述

 k-means算法以k为参数，把n个对象分成k个簇，使簇内具有较高的相似度，而簇间的相似度较低。 其处理过程如下：

①　随机选择k个点作为初始的聚类中心；

②　对于剩下的点，根据其与聚类中心的距离，将其归入最近的簇

③　对每个簇，计算所有点的均值作为新的聚类中心

④　重复2、3直到聚类中心不再发生改变

实现过程

1. 导入相关包numpy\matplotl\math

from numpy import *
import numpy as np
import matplotlib.pyplot as plt
from math import sqrt
from numpy.lib.scimath import power

2. 读取数据

依次遍历数据的每一行，以“,”分割并将数据保存到**数组dataMat[]**中

3. 向量距离计算

使用欧式距离计算样本到中心的距离。对于样本 d 维样本 x 到中心 c 的欧式距离计算公式为：

4. 构建一个包含k个随机质心的集合

def randCent(dataSet, k):
  n = shape(dataSet)[1]  //数据特征个数(即数据维度)
//创建一个0矩阵，其中zeros为创建0填充的数组，mat是转换为矩阵，用于存放k个质心
  centroids = mat(zeros((k, n)))
  for i in range(n):  //遍历每个特征
    minI = min(dataSet[:, i])  //获取最小值
    rangeI = float(max(dataSet[:, i]) - minI)  //范围
    centroids[:, i] = minI + rangeI * random.rand(k, 1)  //最小值+范围*随机数
  return centroids

5. K均值聚类算法

dataSet:数据集

k:簇的个数

distMeas:距离计算

createCent:创建k个随机质心

关于距离计算方式与随机生成k个质心可以选择其他方法

def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):
  m = shape(dataSet)[0] # 数据数目
  clusterAssment = mat(zeros((m, 2)))  //储存每个点的簇分配结果，第一列记录簇索引，第二列记录误差，误差指当前点到簇质心的距离，可用于评估聚类的效果
  centroids = createCent(dataSet, k) //质心生成
  clusterChanged = True //标记变量，为True则继续迭代
  while clusterChanged:
    clusterChanged = False
//寻找最近的质心
    for i in range(m): # 遍历每个数据
      minDist = inf # 最小距离
      minIndex = -1 # 最小距离的索引
      for j in range(k): # 遍历每个质心
        distJI = distMeas(centroids[j, :], dataSet[i, :]) # 计算该点到每个质心的距离
        if distJI < minDist: # 与之前的最小距离比较
          minDist = distJI # 更新最小距离
          minIndex = j # 更新最小距离的索引
      //到此，便得到了该点到哪个质心距离最
      if clusterAssment[i, 0] != minIndex: # 如果之前记录的簇索引不等于目前最小距离的簇索引
        clusterChanged = True # 设置为True，继续遍历，直到簇分配结果不再改变为止
        clusterAssment[i, :] = minIndex, minDist ** //记录新的簇索引和误差
   print(centroids)

//更新质心的位置
    for cent in range(k):
     ptsInclust = dataSet[nonzero(clusterAssment[:, 0].A == cent)[0]] # 获取给定簇的所有点
      clusterAssment[:, 0].A == cent：表示clusterAssment第一列簇索引是否等于当前的簇
      nonzero：返回一个元祖，第一个元素为True所在的行，第二个元素为True所在的列，这里取为行，即取出给定簇的数据
      centroids[cent, :] = mean(ptsInclust, axis=0) # 然后计算均值，axis=0沿着列方向
return centroids, clusterAssment # 返回质心与点分配结果

//对数据进行可视化展示
marker = ['s', 'o', '^', '<','>','D','8']  # 散点图点的形状
color = ['b', 'm', 'y', 'g','c','k','r']  # 颜色X = np.array(datMat)  # 数据点
CentX = np.array(myCentroids)  # 质心点
Cents = np.array(clusterAssing[:, 0])  # 每个数据点对应的簇
for i, Centroid in enumerate(Cents):  # 遍历每个数据对应的簇，返回数据的索引即其对应的簇
  plt.scatter(X[i][0], X[i][1], marker=marker[int(Centroid[0])], c=color[int(Centroid[0])])  # 按簇画数据点
plt.scatter(CentX[:, 0], CentX[:, 1], marker='*', c='r')  # 画质心

plt.show()

调参的参数仅仅是簇数k取不同k值，观察结果:

1. 聚成两类：

2. 聚成三类：

3. 聚成四类：

4. 聚成五类

5. 聚成六类

6. 聚成7类

7. 设置簇的个数为8，观察发现数据还是分成7类，且分类效果并不好，有些数据密切分布。

综上，可以看到分类效果最好的是聚成7类，k的取值应为7。

总结

• K-Means的主要优点有：
  - 原理比较简单，实现也是很容易，收敛速度快。
  - 聚类效果较优。
  - 算法的可解释度比较强。
  - 主要需要调参的参数仅仅是簇数k。

• K-Means的主要缺点有：
  - K值的选取不好把握(改进：可以通过在一开始给定一个适合的数值给k，通过一次K-means算法得到一次聚类中心。对于得到的聚类中心，根据得到的k个聚类的距离情况，合并距离最近的类，因此聚类中心数减小，当将其用于下次聚类时，相应的聚类数目也减小了，最终得到合适数目的聚类数。可以通过一个评判值E来确定聚类数得到一个合适的位置停下来，而不继续合并聚类中心。重复上述循环，直至评判函数收敛为止，最终得到较优聚类数的聚类结果)。
  - 对于不是凸的数据集比较难收敛(改进：基于密度的聚类算法更加适合，比如DBSCAN算法)
  - 如果各隐含类别的数据不平衡，比如各隐含类别的数据量严重失衡，或者各隐含类别的方差不同，则聚类效果不佳。
  - 采用迭代方法，得到的结果只是局部最优。
  - 对噪音和异常点比较的敏感(改进1：离群点检测的LOF算法，通过去除离群点后再聚类，可以减少离群点和孤立点对于聚类效果的影响；改进2：改成求点的中位数，这种聚类方式即K-Mediods聚类（K中值）)。
  - 初始聚类中心的选择(改进1：k-means++;改进2：二分K-means）