俗话说的好：“物以类聚，人以群分”，今天我们要讲的聚类算法很大程度上可以印证此话。聚类是一种非监督学习，什么是非监督学习？与之前学习的分类和回归不同（监督学习），监督学习是有有label标签的，而非监督学习没有。
我们再回到聚类上，聚类是把相似的对象归到同一簇中，有点像全自动分类。聚类的应用场景有很多，例如在电商行业，通过用户的购买历史进行聚类，针对不同的用户群体推送不同的广告。
K-Means聚类算法
算法流程
K-Means聚类首先随机确定 K 个初始点作为质心（这也是K-Means聚类的一个问题，这个K值的不合理选择会使得模型不适应和解释性差）。然后将数据集中的每个点分配到一个簇中， 具体来讲，就是为每个点找到距其最近的质心（这里算的为欧式距离，当然也可以使用其他距离）， 并将其分配该质心所对应的簇；这一步完成之后，每个簇的质心更新为该簇所有点的平均值；重复上述过程直到数据集中的所有点都距离它所对应的质心最近时结束。
算法伪代码
创建 k 个点作为起始质心（随机选择）
当任意一个点的簇分配结果发生改变时（不改变时算法结束）
对数据集中的每个数据点
对每个质心
计算质心与数据点之间的距离
将数据点分配到距其最近的簇
对每一个簇, 计算簇中所有点的均值并将均值作为质心
实现代码
from numpy import *
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):
n = shape(dataSet)[1]
centroids = mat(zeros((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)
return centroids
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):
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)
return centroids, clusterAssment
聚类结果如图：
缺陷
K-Means算法可能偶尔会陷入局部最小值（局部最优的结果，但不是全局最优的结果），如图所示。
出现这个问题有很多原因，可能是k值取的不合适，可能是距离函数不合适，可能是最初随机选取的质心靠的太近，也可能是数据本身分布的问题。
二分K-Means 聚类算法
为了解决K-Means算法的问题，提出了二分 K-Means 聚类算法。该算法首先将所有点作为一个簇，然后将该簇一分为二。之后选择其中一个簇继续进行划分，选择哪一个簇进行划分取决于对其划分时候可以最大程度降低 SSE（平方和误差）的值。上述基于 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
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)
sseSplit = sum(splitClustAss[:,1])
sseNotSplit = sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1])
print("sseSplit, and notSplit: ",sseSplit,sseNotSplit)
if (sseSplit + sseNotSplit) < lowestSSE:
bestCentToSplit = i
bestNewCents = centroidMat
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 bestClustAss is: ', len(bestClustAss))
centList[bestCentToSplit] = bestNewCents[0,:].tolist()[0]
centList.append(bestNewCents[1,:].tolist()[0])
clusterAssment[nonzero(clusterAssment[:,0].A == bestCentToSplit)[0],:]= bestClustAss
return mat(centList), clusterAssment
结果如图所示：
K-Means算法优缺点
- 优点：容易实现
- 缺点：可能陷入局部最优解
