一、聚类算法的简介
聚类算法是一种典型的无监督学习算法，主要用于将相似的样本自动归到一个类别中。聚类算法与分类算法最大的区别是：聚类算法是无监督的学习算法，而分类算法属于监督的学习算法。
在聚类算法中根据样本之间的相似性，将样本划分到不同的类别中，对于不同的相似度计算方法，会得到不同的聚类结果，常用的相似度计算方法有欧式距离法。
二、K-Means算法的概述
K-Means聚类的目的是将n个观测值划分为k个类，使每个类中的观测值距离该类的中心（类均值）比距离其他类中心都近。
事先确定常数k，常数k意味着最终的聚类类别数，首先随机选定初始点为质心，并通过计算每一个样本与质心之间的相似度(这里为欧式距离)，将样本点归到最相似的类中，接着，重新计算每个类的质心(即为类中心)，重复这样的过程，知道质心不再改变，最终就确定了每个样本所属的类别以及每个类的质心。
由于每次都要计算所有的样本与每一个质心之间的相似度，故在大规模的数据集上，K-Means算法的收敛速度比较慢。
三、K-Means算法的流程
1、初始化常数K，随机选取初始点为质心
2、重复计算一下过程，直到质心不再改变
（1）计算样本与每个质心之间的相似度，将样本归类到最相似的类中
（2）重新计算质心
3、输出最终的质心以及每个类
四、K-Means算法的实现
1、K-Means算法实现代码如下：
import numpy as np
import matplotlib.pyplot as plt
'''
算法思想大致为：先从样本集中随机选取 𝑘 个样本作为簇中心，并计算所有样本与这 𝑘 个“簇中心”的距离，对于每一个样本，
将其划分到与其距离最近的“簇中心”所在的簇中，对于新的簇计算各个簇的新的“簇中心”。
根据以上描述，我们大致可以猜测到实现kmeans算法的主要三点：
（1）簇个数 𝑘 的选择
（2）各个样本点到“簇中心”的距离
（3）根据新划分的簇，更新“簇中心”
'''
def loadDataSet(filename):
'''
读取数据集
Args:
filename: 文件名
Returns:
dataMat: 数据样本矩阵
'''
dataMat = []
with open(filename, 'rb') as f:
for line in f:
# 读取的字节流需要先解码成utf-8再处理
eles = list(map(float, line.decode('utf-8').strip().split('\t')))
dataMat.append(eles)
return dataMat
def distEclud(vecA, vecB):
'''
计算两向量的欧氏距离
Args:
vecA: 向量A
vecB: 向量B
Returns:
欧式距离
'''
return np.sqrt(np.sum(np.power(vecA-vecB,2)))
def randCent(dataSet, k):
'''
随机生成k个聚类中心
Args:
dataSet: 数据集
k: 簇数目
Returns:
centroids: 聚类中心矩阵
'''
m, _ = dataSet.shape
# 随机从数据集中选几个作为初始聚类中心
centroids = dataSet.take(np.random.choice(80,k), axis=0)
return centroids
def kMeans(dataSet, k, maxIter=5):
'''
K-Means
Args:
dataSet: 数据集
k: 聚类数
Returns:
centroids: 聚类中心
clusterAssment: 点分配结果
'''
# 随机初始化聚类中心
centroids = randCent(dataSet, k)
init_centroids = centroids.copy()
m, n = dataSet.shape
# 点分配结果：第一列指明样本所在的簇，第二列指明该样本到聚类中心的距离
clusterAssment = np.mat(np.zeros((m, 2)))
# 标识聚类中心是否仍在变化
clusterChanged = True
# 直至聚类中心不再变化
iterCount = 0
while clusterChanged and iterCount < maxIter:
iterCount += 1
clusterChanged = False
# 分配样本到簇
for i in range(m):
# 计算第i个样本到各个聚类中心的距离
minIndex = 0
minDist = np.inf
for j in range(k):
dist = distEclud(dataSet[i, :], centroids[j, :])
if dist < minDist:
minIndex = j
minDist = dist
# 任何一个样本的类簇分配发生变化则认为变化
if clusterAssment[i, 0] != minIndex:
clusterChanged = True
clusterAssment[i, :] = minIndex, minDist ** 2
# 刷新聚类中心：移动聚类中心点到所有簇的均值位置
for cent in range(k):
# 通过数组过滤得到簇中的点
# matrix.A 是将matrix-->array
ptsInCluster = dataSet[np.nonzero(clusterAssment[:, 0].A == cent)[0]]
if ptsInCluster.shape[0] > 0:
# 计算均值并移动
centroids[cent, :] = np.mean(ptsInCluster, axis=0)
return centroids, clusterAssment, init_centroids
if __name__ == '__main__':
dataMat = np.mat(loadDataSet('./testSet.txt'))
m, n = np.shape(dataMat)
set_k = 4
centroids, clusterAssment, init_centroids = kMeans(dataMat, set_k)
clusterCount = np.shape(centroids)[0]
# 我们这里只设定了最多四个簇的样式，所以前面如果set_k设置超过了4，后面就会出现index error
patterns = ['o', 'D', '^', 's']
colors = ['b', 'g', 'y', 'black']
fig = plt.figure()
title = 'kmeans with k={}'.format(set_k)
ax = fig.add_subplot(111, title=title)
for k in range(clusterCount):
# 绘制聚类中心
ax.scatter(centroids[k, 0], centroids[k, 1], color='r', marker='+', linewidth=20)
# 绘制初始聚类中心
ax.scatter(init_centroids[k, 0], init_centroids[k, 1], color='purple', marker='*', linewidth=10)
for i in range(m):
# 绘制属于该聚类中心的样本
ptsInCluster = dataMat[np.nonzero(clusterAssment[:, 0].A == k)[0]]
ax.scatter(ptsInCluster[:, 0].flatten().A[0], ptsInCluster[:, 1].flatten().A[0], color=colors[k],
marker=patterns[k])
plt.show()
效果图.png
2、sklearn中K-Means算法实现代码如下：
from sklearn.cluster import KMeans
import numpy as np
import matplotlib.pyplot as plt
def loadDataSet(filename):
'''
读取数据集
Args:
filename: 文件名
Returns:
dataMat: 数据样本矩阵
'''
dataMat = []
with open(filename, 'rb') as f:
for line in f:
# 读取的字节流需要先解码成utf-8再处理
eles = list(map(float, line.decode('utf-8').strip().split('\t')))
dataMat.append(eles)
return dataMat
dataMat = np.mat(loadDataSet('./testSet.txt'))
kmeans = KMeans(init='random', n_clusters=4, random_state=0).fit(dataMat)
centroids = kmeans.cluster_centers_
clusterAssment = kmeans.labels_
m, n = np.shape(dataMat)
set_k = 4
clusterCount = np.shape(centroids)[0]
# 我们这里只设定了最多四个簇的样式，所以前面如果set_k设置超过了4，后面就会出现index error
patterns = ['o', 'D', '^', 's']
colors = ['b', 'g', 'y', 'black']
fig = plt.figure()
title = 'kmeans with k={}'.format(set_k)
ax = fig.add_subplot(111, title=title)
for k in range(clusterCount):
# 绘制聚类中心
ax.scatter(centroids[k, 0], centroids[k, 1], color='r', marker='+', linewidth=20)
for i in range(m):
# 绘制属于该聚类中心的样本
ptsInCluster = dataMat[np.nonzero(clusterAssment == k)[0]]
ax.scatter(ptsInCluster[:, 0].flatten().A[0], ptsInCluster[:, 1].flatten().A[0], color=colors[k],
marker=patterns[k])
plt.show()
分类效果图.png
