1.K-means算法

1.基本定义

K-means算法的思想很简单，对于给定的样本集合，按照样本之间的距离大小，将样本划分为K簇。让簇内的点尽量紧密的聚集在一起，而让簇间的距离尽量的大。
若用数学公式表达，即：假设簇划分为 $(C_1,C_2,...,C_k)$ ，则目标函数是：
$E = \sum_{i=1}^{k}\sum_{x \in C_i}||x-u_i||^2$
其中 $u_i$ 是簇 $C_i$ 的均值向量（也称为质心），表达式为：
$u_i = \frac{1}{|C_i|} \sum_{x \in C_i}x$
该问题是一个NP难问题，是无法直接求目标函数最小值的，因此只能使用启发式方法。

2.图示原理

K-means采用的启发式方法比较简单，用下组图（参考[1]）可以详细的表示：

图示

图a:设置K为2
图b:随机选择2个对象作为当前的质心，例如图中的红点和蓝点，分别求其余点与当前k个质心的距离，并标记每个点的类别为与该点距离最短的质心所属的类别。
图c：经过一轮计算后，得到每个点所属的类别。
图d：对已经新分类的每个簇，计算新的质心点。图中可见，已经有了新的红点和蓝点。
图e，f：重复图c，d的过程，最终得到k个质心。

3.实现

import numpy as np

# 计算两个向量的距离，用的是欧几里得距离
def get_dis(vecA, vecB):
    return np.linalg.norm(vecA - vecB)

# 随机生成初始的质心（ng的课说的初始方式是随机选K个点）
def randCent(dataSet, k):
    p = np.shape(dataSet)[1] # 维度p
    centroids = np.mat(np.zeros((k, p)))
    # k个簇心
    for j in range(p):
        minJ = min(dataSet[:, j])
        rangeJ = float(max(np.array(dataSet)[:, j]) - minJ)
        centroids[:, j] = minJ + rangeJ * np.random.rand(k, 1)
    return centroids

def kMeans(dataSet, k):
    n = np.shape(dataSet)[0] # N个
    p = np.shape(dataSet)[1]
    clusterAssment = np.mat(np.zeros((n,p))) # 记录每个点的簇心
    # 随机生成簇心
    centroids = randCent(dataSet, k)
    clusterChanged = True
    while clusterChanged:
        clusterChanged = False
        for i in range(n):  # 计算每个点簇心
            minDist = np.inf
            minIndex = -1
            for j in range(k): # 当前点跟k个簇心的距离,选最近的簇心为自己的簇心
                distJI = get_dis(centroids[j, :], dataSet[i, :])
                print("distJI = ",distJI)
                if distJI < minDist:
                    minDist = distJI
                    minIndex = j
            if clusterAssment[i, 0] != minIndex:
                clusterChanged = True # 循环标记
            clusterAssment[i, :] = (minIndex, minDist)
        for cent in range(k):
            ptsInClust = dataSet[np.nonzero(clusterAssment[:, 0].A == cent)[0]]  # matrix.A 将matrix转换为array
            centroids[cent, :] = np.mean(ptsInClust, axis=0)
    return centroids, clusterAssment

def main():
    # 1.随机生成几组数据（K = 2）
    data_coord = np.asarray(((3, 3), (4, 3), (5, 5), (4, 5), (5, 4), (3, 5), (21, 22), (18, 23), (20, 23)))
    dataMat = np.mat(data_coord)
    myCentroids, clustAssing = kMeans(dataMat, 2)
    print(myCentroids)

if __name__ == '__main__':
    main()

参考与致谢：
[1] K-Means聚类算法原理