K-means 学习笔记
前言
K-means 算法是最为经典的基于划分的聚簇方法，是经典数据挖掘算法之一。简单的说就是在没有任何监督信号的情况下将数据分为 K 份的一种方法, 也就是分门别类。
K-means 算法
算法原理
基本思想:
给定 K 值和 K 个初始类中心点，把每个点分到离其最近的类中心点所代表的类中，所有点分配完毕之后，根据一个类内的所有点重新计算该类的中心点（平均值），然后再迭代的进行分配点和更新类中心点的步骤，直至类中心点的变化很小，或者达到指定的迭代次数。
对一个样本集
这里每个 x 都有 m 个维度的属性, 我们想要将其划分为 k 个聚类
首先，我们从样本集 D 中随机获取 k 个样本作为初始类中心点
然后计算每一个对象到每一个聚类中心的欧式距离:
其中，m 为样本点的纬度属性
依次比较每一个对象到每一个聚类中心的距离，将对象分配到距离最近的聚类中心的类簇中，得到 k 个类
类中心就是类内所有对象在各个维度的均值，其计算公式如下
其中,
为第 k 个聚类的中心，
为第 k 个聚类中元素的个数。
总的来说，K-means 算法的基本思想还是容易理解的，主要流程可以分为如下几步：
- 选择聚类的个数 K
- 任意产生 k 个聚类, 然后确定聚类中心（或者直接生成 K 个中心）
- 把每个数据点分配到离它最近的中心点
- 再迭代计算新聚类的新中心
- 重复以上步骤直到满足收敛要求
效果展示如下：
算法实现
代码语言：javascript复制import numpy as np
import matplotlib.pyplot as plt
# 加载数据
def loadDataSet(file):
dataSet = np.loadtxt(file, delimiter='t')
return dataSet
# 计算欧式距离
def euclDistance(x, y):
return np.sqrt(np.sum((x - y) ** 2)) # 计算欧氏距离
# 初始化 k 个聚类中心
def getCenter(dataSet, k):
# 行，列大小
m, n = dataSet.shape
# 初始化 k 个聚类中心
center = np.zeros((k, n))
for i in range(k):
# 产生 k 个 [0, m) 的数
index = int(np.random.uniform(0, m))
center[i, :] = dataSet[index, :]
return center
# k均值聚类
def KMeans(dataSet, k):
m = np.shape(dataSet)[0] # 行的数目
# 第一列存样本属于哪一类，初始为 0
# 第二列存样本的到类的中心点的误差
clusterAssment = np.mat(np.zeros((m, 2))) # 创建 m 行 2 列的矩阵
clusterChange = True # 记录样本的点类是否发生变化
# 第1步 初始化center
center = getCenter(dataSet, k)
# 如果上一次迭代过程中仍有样本点的类别发生变化，则继续计算
while clusterChange:
clusterChange = False
# 遍历所有的样本（行数）
for i in range(m):
minDist = np.inf
minIndex = -1
# 第2步 找出离样本点最近的质心
# 遍历所有质心
for j in range(k):
# 计算该样本到质心的欧式距离
distance = euclDistance(center[j, :], dataSet[i, :])
if distance < minDist:
minDist = distance # 更新最短距离
minIndex = j # 更新离该样本最近的中心
# 第 3 步：更新每一行样本所属的类
# 如果样本类别发生变化
if clusterAssment[i, 0] != minIndex:
clusterChange = True
# 更新类别以及误差
clusterAssment[i, :] = minIndex, minDist**2
# 第 4 步：更新质心
# 遍历每一个类
for j in range(k):
# .A 将矩阵转化为数组
# nonzero(a) 返回数组a中非零元素的索引值数组
pointsInCluster = dataSet[np.nonzero(
clusterAssment[:, 0].A == j)[0]] # 获取类所有的点
center[j, :] = np.mean(pointsInCluster, axis=0) # 对矩阵的行求均值
print("Congratulations,cluster complete!")
return center, clusterAssment
def showCluster(dataSet, k, center, clusterAssment):
m, n = dataSet.shape
if n != 2:
print("数据不是二维的")
return 1
mark = ['or', 'ob', 'og', 'ok', '^r', ' r', 'sr', 'dr', '<r', 'pr']
if k > len(mark):
print("k值太大了")
return 1
# 绘制所有的样本
for i in range(m):
markIndex = int(clusterAssment[i, 0])
plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex])
mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', ' b', 'sb', 'db', '<b', 'pb']
# 绘制质心
for i in range(k):
plt.plot(center[i, 0], center[i, 1], mark[i])
plt.show()
dataSet = loadDataSet("test.txt")
k = 4
center, clusterAssment = KMeans(dataSet, k)
showCluster(dataSet, k, center, clusterAssment)
优缺点
- 原理比较简单，实现也是很容易，收敛速度快
- 算法的可解释度比较强
- 聚类中心的个数 K 需要事先给定，但在实际中 K 值的选定是非常困难的
- k-means 算法需要随机地确定初始聚类中心，不同的初始聚类中心可能导致完全不同的聚类结果。
K-means 算法
上面我们提到 k-means 算法需要随机地确定初始聚类中心，不同的初始聚类中心可能导致完全不同的聚类结果。对于这个问题，K-means 算法进行了优化。
算法原理
K-means 算法初始化聚类中心的策略也非常简单，流程如下：
- 从数据集中随机选择一个点作为第一个聚类中心
- 计算每个样本与最近一个聚类中心的距离, 距离越大表示被选取作为聚类中心的概率越大
- 用轮盘法选出下一个聚类中心
- 重复上述过程，直到选择出 k 个聚类中心
- 执行标准的 K-means 算法
效果展示如下：
算法实现
代码语言：javascript复制# 样本点到最近的聚类中心的距离
def getClosestDist(data, center):
min_dist = np.inf
m = np.shape(center)[0] # 当前已经初始化的聚类中心的个数
for i in range(m):
# 计算样本点与每个聚类中心之间的距离
d = euclDistance(center[i, :], data)
# 选择最短距离
if min_dist > d:
min_dist = d
return min_dist
# 初始化 k 个聚类中心
def getCenterPlusPlus(dataSet, k):
m, n = dataSet.shape
# 初始化 k 个聚类中心
center = np.zeros((k, n))
# 1、随机选择一个样本点为第一个聚类中心
index = np.random.randint(0, m)
center[0, :] = dataSet[index, :]
# 初始化一个距离的序列
d = [0.0 for _ in range(m)]
for i in range(1, k):
sum_all = 0
for j in range(m):
# 2、对每一个样本找到最近的聚类中心点
d[j] = getClosestDist(dataSet[j, ], center[0:i, ])
# 将所有的最短距离相加
sum_all = d[j]
# 3、用轮盘法选出下一个聚类中心
# 取得sum_all之间的随机值
sum_all *= np.random.random()
for j, dis in enumerate(d):
sum_all -= dis
if sum_all > 0:
continue
# 选择新的聚类中心
center[i, :] = dataSet[j, :]
break
return center参考资料
- Kmeans 聚类算法详解
- k-means 聚类算法原理及 python3 实现
