机器学习笔记（七）k-Means

零、写在前面

参考资料：

• 《机器学习》周志华
• 《机器学习实战》Peter Harrington
• 斯坦福 CS 229 吴恩达
• 漫谈 Clustering (1): k-means

一、算法原理

k-Means是一种十分简单的算法，一张图就可以解释清楚。

算法流程（上图k=2）：

图a 原始数据
图b 随机选取k个点作为类别中心
图c 对于每个原始数据的点，把它归为最近的类别中心的那一类
图d 计算每簇点的平均值，将类别中心移至均值点
图e 对于每个原始数据的点，把它归为最近的类别中心的那一类
图f 计算每簇点点的平均值，将类别中心移至均值点
循环至收敛

二、收敛性

考虑平方误差：

E=∑ik∑x∈ci||x−μi||22其中μi是第i簇的均值点$$\begin{gathered} E=\sum _i^k\sum _{x\in c_i}||x-{\mu }_i|{|}_2^2 \\ 其中{\mu }_i是第i簇的均值点 \end{gathered}$$

上面的误差可以衡量聚类结果的好坏。

实际上，k-Means算法的循环中，先固定均值向量不动，改变x的类别，再固定类别不动，改变均值向量。而每一步‘固定——改变’步骤，改变都是在做argmin（归为最近的类别中心的那一类、将类别中心移至均值点，都是尽可能地降低平方误差E）。也就是说，这一算法实际上是对平方误差E，用做坐标下降法求极值。每一步都是argmin可以保证在聚类过程中平方误差E是单调递减的，这也就确保了收敛性。

三、局部极小值

虽然保证了收敛性，但是所优化的误差函数E并不是凸函数，也就是说如果初始化不佳，k-Means有陷入局部极小值的风险。

初始化：

陷入局部极小：

如何解决？因为是随机初始化，再运行几次就好了。

四、实现

以下是ready-to-use的二维k-Means的python代码，使用时只需更改前两行。

from numpy import *
import matplotlib.pyplot as plt

k=2
dataMat = [[1,1],[1.5,2],[3,3],[3.5,3]]

def distEclud(vecA, vecB):
    return sqrt(sum(power(vecA - vecB, 2))) #la.norm(vecA-vecB)

def randCent(dataSet, k):
    n = shape(dataSet)[1]
    centroids = mat(zeros((k,n)))#create centroid mat
    for j in range(n):#create random cluster centers, within bounds of each dimension
        minJ = min(dataSet[:,j])
        rangeJ = float(max(dataSet[:,j]) - minJ)
        centroids[:,j] = mat(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)))#create mat to assign data points 
                                      #to a centroid, also holds SE of each point
    centroids = createCent(dataSet, k)
    clusterChanged = True
    while clusterChanged:
        clusterChanged = False
        for i in range(m):#for each data point assign it to the closest centroid
            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
        for cent in range(k):#recalculate centroids
            ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]#get all the point in this cluster
            centroids[cent,:] = mean(ptsInClust, axis=0) #assign centroid to mean 
    return centroids, clusterAssment

dataMat = mat(dataMat)
myCentroids, clustAssing = kMeans(dataMat,k)

x_c, y_c = zeros(k), zeros(k)
x, y = zeros(len(dataMat)), zeros(len(dataMat))

for i in range(k):
    x_c[i] = myCentroids[i,0]
    y_c[i] = myCentroids[i,1]

for i in range(len(dataMat)):
    x[i] = dataMat[i,0]
    y[i] = dataMat[i,1]

c = zeros(len(dataMat))
for i in range(len(clustAssing)): c[i] = int(clustAssing[i,0])

plt.scatter(x_c, y_c,marker='x',c = 'black')
plt.scatter(x,y,c = c)
plt.show()

运行结果：

x为聚类中心，不同颜色为不同的簇。