【机器学习】无监督学习 K-means(K-均值聚类算法）
2020-07-26 本文已影响0人
Geekero
任务
- 利用K-均值聚类算法对未标注数据分组
- 对聚类得到的簇进行后处理
- 二分K-均值聚类算法
思想
- 聚类算法几乎可以用于任何对象，簇内对象越相似，聚类效果越好。
- 相似度取决于相似度的计算方法，根据具体应用选择相似度的计算方法
- K-均值可以发现k个不同的簇，且每个簇的中心都采用簇中所含值的均值计算而成
- 簇识别给出簇类结果的含义。
- 聚类与分类最大区别在于，分类的目标事先知道，而聚类是未知的。聚类产生的结果与分类相同，只是类别没有预先定义。所以聚类算法也叫无监督分类。
缺点与改进
- 简单K-均值算法的一些缺陷，可以用二分K-均值算法（bisecting k-means）解决
一、K-均值聚类算法的构建
优缺点
优点：容易实现
缺点：可能收敛与局部最小值，在大规模数据集上收敛较慢
使用范围
数值型数据
构建步骤
给定数据集k个簇，每个簇通过其质心（centroid）,即簇中所有点的中心来描述
伪代码：
创建k个点作为起始质心（经常是随机选择）
当任意一个点的簇分配结果发生变化时：
对数据集中的每个数据点:
对每个质心：
计算质心与数据点之间的距离
将数据点分配到距离其最近的簇
对每一个簇，计算簇中所有点的均值，并将均值作为该簇的中心
编写辅助函数：
from numpy import *
"""
创建k个点作为起始质心（经常是随机选择）
当任意一个点的簇分配结果发生变化时：
对数据集中的每个数据点:
对每个质心：
计算质心与数据点之间的距离
将数据点分配到距离其最近的簇
对每一个簇，计算簇中所有点的均值，并将均值作为该簇的中心
"""
#辅助函数
def loadDataSet(fileName): #将文本文件转换成列表的列表格式
dataMat = []
fr = open(fileName)
for line in fr.readlines():
curLine = line.strip().split('\t')
fltLine = list(map(float, curLine))
dataMat.append(fltLine)
return dataMat
def distEclud(vecA, vecB): #计算两个向量之间的欧氏距离
return sqrt(sum(power(vecA - vecB, 2)))
def randCent(dataSet, k):
#构建一个包含k个随机质心的集合
#随机质心必须在整个数据集的边界之内
n = shape(dataSet)[1] #获得列数
centroids = mat(zeros((k, n))) #构建k行n列的质心
for j in range(n):
minJ = min(dataSet[:,j]) #获得数据集中每一个维（每列）的最小值
rangeJ = float(max(dataSet[:,j] - minJ)) #获得数据集中每一个维（每列）的取值范围
centroids[:,j] = minJ + rangeJ * random.rand(k,1) #生成[0, 1.0]之间的随机数
#通过取值范围和最小值，确保随机点在数据的边界之内
return centroids
测试运行：
In [66]: import kMeans
In [67]: from numpy import *
In [68]: datMat = mat(kMeans.loadDataSet('testSet.txt'))
In [69]: min(datMat[:,0])
Out[69]: matrix([[-5.379713]])
In [70]: min(datMat[:,1])
Out[70]: matrix([[-4.232586]])
In [71]: max(datMat[:,1])
Out[71]: matrix([[5.1904]])
In [72]: max(datMat[:,0])
Out[72]: matrix([[4.838138]])
In [73]: kMeans.randCent(datMat, 2)
Out[73]:
matrix([[ 0.50953466, -3.71200331],
[ 3.98163501, -2.66656359]])
In [74]: kMeans.distEclud(datMat[0], datMat[1])
Out[74]: 5.184632816681332
实现完整的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
while clusterChanged:
clusterChanged = False
for i in range(m): #对dataSet中的每个数据点
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
clusterAssment[i,:] = minIndex, minDist**2 #记录簇索引值与误差
print(centroids)
#最后，遍历所有质心并更新它们的取值
for cent in range(k):
#通过数组过滤，获得给定簇的所有点
ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]
centroids[cent,:] = mean(ptsInClust, axis=0) #计算所有点的均值，axis=0
return centroids, clusterAssment
运行：
In [83]: import importlib
In [84]: importlib.reload(kMeans)
Out[84]: <module 'kMeans' from 'D:\\Data\\File\\ML\\kMeans.py'>
In [85]: datMat = mat(kMeans.loadDataSet('testSet.txt'))
In [86]: myCentroids, clustAssing = kMeans.KMeans(datMat, 4)
[[ 1.00280717 0.11770989]
[-1.73165675 -3.43839335]
[ 2.55164274 -2.32833514]
[ 3.63722591 0.00961112]]
[[-0.93031861 2.9279739 ]
[-3.19984738 -2.96423548]
[ 2.7475792 -3.14066887]
[ 3.57953285 1.76429869]]
[[-1.94392522 2.96291883]
[-3.38237045 -2.9473363 ]
[ 2.72031426 -2.83200232]
[ 2.91014783 2.71954072]]
[[-2.46154315 2.78737555]
[-3.38237045 -2.9473363 ]
[ 2.80293085 -2.7315146 ]
[ 2.6265299 3.10868015]]
使用后处理来提高聚类性能
由于K-均值算法可能只收敛到局部最小值，而非全局最小值
聚类的目标是在保持簇数目不变的情况下，提高簇的质量
将具有最大SSE值的簇，划分为两个簇
可以将最大簇包含的点过滤出来，并且在这些点上再运行K-均值算法
为了保持簇总数不变，将某两个分错的簇的质心进行合并（两种量化的方法）
- ①合并最近的质心
通过计算所有质心之间的距离，然后合并距离最近的两个点 - ②合并两个使得SSE增幅最小的质心
合并两个簇，然后计算总SSE值。在所有可能的两个簇上重复这个处理过程，直到找到合并最佳的两个簇为止。
二、二分K-均值算法（bisecting K-means）
思想
- 将所有点看成一个簇
- 对该簇一分为二
- 选择可以最大程度降低SSE值的其中一个簇继续进行划分
- 上述基于SSE的划分过程不断重复，直到得到用户指定的簇数目为止
伪代码
将所有点看成一个簇
当簇数目小于k时：
对于每一个簇：
计算总误差
在给定的簇上面进行K-均值聚类（k=2）
计算该簇一分为二之后的总误差
选择使得误差最小的那个簇进行划分操作
另一种做法是选择SSE最大的簇进行划分操作，直到簇数目达到用户指定的数目为止
代码
def biKmeans(dataSet, k, distMeas=distEclud):
m = shape(dataSet)[0]
clusterAssment = mat(zeros((m,2)))
centroid0 = mean(dataSet, axis=0).tolist()[0] #计算整个数据集的质心
centList = [centroid0] #创建一个初始化簇，并使用一个列表来保存所有质心
for j in range(m): #遍历数据集，计算每个点到质心的误差值（距离的平方）
clusterAssment[j,1] = distMeas(mat(centroid0), dataSet[j,:])**2
# 尝试划分已有的每一个簇,寻找使得SSE降幅最大的那个簇,然后对其进行2-Means聚类划分
while (len(centList) < k):
lowestSSE = inf
for i in range(len(centList)):
#尝试划分每一个簇
ptsInCurrCluster = \
dataSet[nonzero(clusterAssment[:,0].A==i)[0],:] #选择每一个簇中的所有点，作为一个小的数据集
centroidMat, splitClustAss = \
kMeans(ptsInCurrCluster, 2, distMeas) #将该簇用kMeans一分为二，给出质心，分配的质心和误差值
sseSplit = sum(splitClustAss[:,1]) #计算这个簇划分成两个簇以后的误差的和
sseNotSplit = \
sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1]) #计算剩余未被划分的簇（剩余数据集）的误差的和
print("sseSplit, and sseNotSplit: ", sseSplit, sseNotSplit)
if (sseSplit + sseNotSplit) < lowestSSE: #如何该划分的SSE值最小，则本次划分被保存
bestCentToSplit = i
bestNewCents = centroidMat.copy()
bestClustAss = splitClustAss.copy() #该簇的划分情况
lowestSSE = sseSplit + sseNotSplit
#实际执行划分操作：把要划分的簇中的所有点的簇分配结果进行修正
bestClustAss[nonzero(bestClustAss[:,0].A == 1)[0],0] =\
len(centList) #新加簇的编号
bestClustAss[nonzero(bestClustAss[:,0].A == 0)[0],0] =\
bestCentToSplit #划分簇的编号
print('the bestCentToSplit is: ', bestCentToSplit)
print('the len of bestClustss is: ', len(bestClustAss))
#新的质心被添加到centList
centList[bestCentToSplit] = bestNewCents[0,:].tolist()[0] #将cluster0的簇的质心分配到原本簇的质心
centList.append(bestNewCents[1,:].tolist()[0]) #将cluster1的簇质心添加到centList
clusterAssment[nonzero(clusterAssment[:,0].A ==\
bestCentToSplit)[0], :] = bestClustAss #将原本被划分的簇，更新簇分配的结果
return mat(centList), clusterAssment
运行：
> importlib.reload(kMeans)
> datMat3=mat(kMeans.loadDataSet('testSet2.txt'))
> centList,myNewAssments = kMeans.biKmeans(datMat3,3)
sseSplit, and sseNotSplit: 570.7227574246755 0.0
the bestCentToSplit is: 0
the len of bestClustss is: 60
sseSplit, and sseNotSplit: 68.68654812621844 38.06295063565756
the bestCentToSplit is: 0
the len of bestClustss is: 40
sseSplit, and sseNotSplit: 22.971771896318412 68.68654812621844
the bestCentToSplit is: 1
the len of bestClustss is: 20
质心：
In [96]: centList
Out[96]:
matrix([[ 2.02712544, 3.50141167],
[-2.94737575, 3.3263781 ],
[ 3.67574036, 2.82216836],
[-0.45965615, -2.7782156 ]])
质心示意图：
import matplotlib.pyplot as plt
centroids_x = centList[:,0]
centroids_y = centList[:,1]
plt.scatter(centroids_x.tolist(),centroids_y.tolist(),
marker = 'x',
s=150, linewidths = 5,
zorder = 10,
c=['green', 'red','blue','black'])
聚类会收敛到全局最小值，原始的kMeans()函数偶尔会陷入·局部最小值
