一、算法介绍

聚类属于无监督学习，K-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。
k个初始类聚类中心点的选取对聚类结果具有较大的

二 基本概念

无监督学习

三 实现过程

算法过程如下：
1）从N个文档随机选取K个文档作为质心
2）对剩余的每个文档测量其到每个质心的距离，并把它归到最近的质心的类
3）重新计算已经得到的各个类的质心
4）迭代2～3步直至新的质心与原质心相等或小于指定阈值，算法结束

四、应用场景

五、优缺点

1、优点

1.收敛太慢
2.算法复杂度高O(nkt)
3.不能发现非凸形状的簇，或大小差别很大的簇
4.需样本存在均值（限定数据种类）
6.需先确定k的个数
7.对噪声和离群点敏感
8.最重要是结果不一定是全局最优，只能保证局部最优。

2、缺点

1.收敛太慢
2.算法复杂度高O(nkt)
3.不能发现非凸形状的簇，或大小差别很大的簇
4.需样本存在均值（限定数据种类）
6.需先确定k的个数
7.对噪声和离群点敏感
8.最重要是结果不一定是全局最优，只能保证局部最优。

六、常见问题

1、K如何确定

kmenas算法首先选择K个初始质心，其中K是用户指定的参数，即所期望的簇的个数。这样做的前提是我们已经知道数据集中包含多少个簇，但很多情况下，我们并不知道数据的分布情况，实际上聚类就是我们发现数据分布的一种手段，这就陷入了鸡和蛋的矛盾。如何有效的确定K值，这里大致提供几种方法，若各位有更好的方法，欢迎探讨。
1.与层次聚类结合
经常会产生较好的聚类结果的一个有趣策略是，首先采用层次凝聚算法决定结果粗的数目，并找到一个初始聚类，然后用迭代重定位来改进该聚类。
2.稳定性方法
稳定性方法对一个数据集进行2次重采样产生2个数据子集，再用相同的聚类算法对2个数据子集进行聚类，产生2个具有k个聚类的聚类结果，计算2个聚类结果的相似度的分布情况。2个聚类结果具有高的相似度说明k个聚类反映了稳定的聚类结构，其相似度可以用来估计聚类个数。采用次方法试探多个k，找到合适的k值。
3.系统演化方法
系统演化方法将一个数据集视为伪热力学系统，当数据集被划分为K个聚类时称系统处于状态K。系统由初始状态K=1出发，经过分裂过程和合并过程，系统将演化到它的稳定平衡状态Ki，其所对应的聚类结构决定了最优类数Ki。系统演化方法能提供关于所有聚类之间的相对边界距离或可分程度，它适用于明显分离的聚类结构和轻微重叠的聚类结构。
4.使用canopy算法进行初始划分
基于CanopyMethod的聚类算法将聚类过程分为两个阶段 Stage1、聚类最耗费计算的地方是计算对象相似性的时候，CanopyMethod在第一阶段选择简单、计算代价较低的方法计算对象相似性，将相似的对象放在一个子集中，这个子集被叫做Canopy，通过一系列计算得到若干Canopy，Canopy之间可以是重叠的，但不会存在某个对象不属于任何Canopy的情况，可以把这一阶段看做数据预处理； Stage2、在各个Canopy内使用传统的聚类方法(如K-means)，不属于同一Canopy 的对象之间不进行相似性计算。从这个方法起码可以看出两点好处：首先，Canopy 不要太大且Canopy之间重叠的不要太多的话会大大减少后续需要计算相似性的对象的个数；其次，类似于K-means这样的聚类方法是需要人为指出K的值的，通过Stage1得到的Canopy个数完全可以作为这个K值，一定程度上减少了选择K的盲目性。
其他方法如贝叶斯信息准则方法（BIC）可参看《一种基于贝叶斯信息准则的k均值聚类方法》。

2、初始质心的选取

选择适当的初始质心是基本kmeans算法的关键步骤。常见的方法是随机的选取初始质心，但是这样簇的质量常常很差。处理选取初始质心问题的一种常用技术是：多次运行，每次使用一组不同的随机初始质心，然后选取具有最小SSE（误差的平方和）的簇集。这种策略简单，但是效果可能不好，这取决于数据集和寻找的簇的个数。
第二种有效的方法是，取一个样本，并使用层次聚类技术对它聚类。从层次聚类中提取K个簇，并用这些簇的质心作为初始质心。该方法通常很有效，但仅对下列情况有效：（1）样本相对较小，例如数百到数千（层次聚类开销较大）；（2）K相对于样本大小较小
第三种选择初始质心的方法，随机地选择第一个点，或取所有点的质心作为第一个点。然后，对于每个后继初始质心，选择离已经选取过的初始质心最远的点。使用这种方法，确保了选择的初始质心不仅是随机的，而且是散开的。但是，这种方法可能选中离群点。此外，求离当前初始质心集最远的点开销也非常大。为了克服这个问题，通常该方法用于点样本。由于离群点很少（多了就不是离群点了），它们多半不会在随机样本中出现。计算量也大幅减少。
第四种方法就是上面提到的canopy算法。

3、距离的度量

常用的距离度量方法包括：欧几里得距离和余弦相似度。两者都是评定个体间差异的大小的。欧几里得距离度量会受指标不同单位刻度的影响，所以一般需要先进行标准化，同时距离越大，个体间差异越大；空间向量余弦夹角的相似度度量不会受指标刻度的影响，余弦值落于区间[-1,1]，值越大，差异越小。但是针对具体应用，什么情况下使用欧氏距离，什么情况下使用余弦相似度？
从几何意义上来说，n维向量空间的一条线段作为底边和原点组成的三角形，其顶角大小是不确定的。也就是说对于两条空间向量，即使两点距离一定，他们的夹角余弦值也可以随意变化。感性的认识，当两用户评分趋势一致时，但是评分值差距很大，余弦相似度倾向给出更优解。举个极端的例子，两用户只对两件商品评分，向量分别为(3,3)和(5,5)，这两位用户的认知其实是一样的，但是欧式距离给出的解显然没有余弦值合理。[6]

4、质心的计算

对于距离度量不管是采用欧式距离还是采用余弦相似度，簇的质心都是其均值，即向量各维取平均即可。对于距离对量采用其它方式时，这个还没研究过。

5、算法停止条件

一般是目标函数达到最优或者达到最大的迭代次数即可终止。对于不同的距离度量，目标函数往往不同。当采用欧式距离时，目标函数一般为最小化对象到其簇质心的距离的平方和，如下：

K-means算法简介及常见问题

当采用余弦相似度时，目标函数一般为最大化对象到其簇质心的余弦相似度和，如下：

K-means算法简介及常见问题

6、空聚类的处理

如果所有的点在指派步骤都未分配到某个簇，就会得到空簇。如果这种情况发生，则需要某种策略来选择一个替补质心，否则的话，平方误差将会偏大。一种方法是选择一个距离当前任何质心最远的点。这将消除当前对总平方误差影响最大的点。另一种方法是从具有最大SSE的簇中选择一个替补的质心。这将分裂簇并降低聚类的总SSE。如果有多个空簇，则该过程重复多次。另外，编程实现时，要注意空簇可能导致的程序bug。

七、总结

K-means也是聚类算法中最简单的一种了，因此存在的问题也是非常多，可以继续学习自动聚类已经可以改进后算法。
改进算法诸如k-means++等

附录一

基于numpy实现的算法程序

# -*- coding: utf-8 -*-
from numpy import *
import time
import matplotlib.pyplot as plt


# 计算距离
def euclDistance(vector1, vector2):
    return sqrt(sum(power(vector2 - vector1, 2)))


#
def initCentroids(dataSet, k):
    numSamples, dim = dataSet.shape
    centroids = zeros((k, dim))
    for i in range(k):
        index = int(random.uniform(0, numSamples))
        centroids[i, :] = dataSet[index, :]
    return centroids


# 聚类
def kmeans(dataSet, k):
    numSamples = dataSet.shape[0]
    clusterAssment = mat(zeros((numSamples, 2)))
    clusterChanged = True

    #获取初始聚类中心
    centroids = initCentroids(dataSet, k)

    # 不断迭代，指导聚类中点没有变化
    while clusterChanged:
        clusterChanged = False
        for i in range(numSamples):
            minDist = 100000.0
            minIndex = 0
            for j in range(k):
                #计算出距离
                distance = euclDistance(centroids[j, :], dataSet[i, :])
                #求出最短的聚类点
                if distance < minDist:
                    minDist = distance
                    minIndex = j

            # 如果该点聚类有变化，则重新赋值
            if clusterAssment[i, 0] != minIndex:
                clusterChanged = True
                clusterAssment[i, :] = minIndex, minDist ** 2

        # 更新聚类中心点
        for j in range(k):
            pointsInCluster = dataSet[nonzero(clusterAssment[:, 0].A == j)[0]]
            centroids[j, :] = mean(pointsInCluster, axis=0)

    print('聚类完毕')
    return centroids, clusterAssment

#展示数据
def showCluster(dataSet, k, centroids, clusterAssment):
    numSamples, dim = dataSet.shape
    if dim != 2:
        print("Sorry! I can not draw because the dimension of your data is not 2!")
        return 1

    mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']
    if k > len(mark):
        print("Sorry! Your k is too large! please contact Zouxy")
        return 1

    # draw all samples
    for i in range(numSamples):
        markIndex = int(clusterAssment[i, 0])
        plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex])

    mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '<b', 'pb']
    # draw the centroids
    for i in range(k):
        plt.plot(centroids[i, 0], centroids[i, 1], mark[i], markersize=12)

    plt.show()


if __name__ == '__main__':
    print("加载数据")
    dataSet = []
    fileIn = open('data\\testData.txt')
    for line in fileIn.readlines():
        lineArr = line.strip().split(' ')
        dataSet.append([float(lineArr[0]), float(lineArr[1])])

    #转化为矩阵
    dataSet = mat(dataSet)
    k = 4
    centroids, clusterAssment = kmeans(dataSet, k)
    # 最后结果
    print(centroids)
    print("显示数据")
    showCluster(dataSet, k, centroids, clusterAssment)

附录二

基于scikit实现的算法程序

# -*- coding: utf-8 -*-
from sklearn.cluster import KMeans
from sklearn.cluster import KMeans
from sklearn.cluster import MiniBatchKMeans
import matplotlib.pyplot as plt
import numpy as np
#展示数据
def showCluster(dataSet, k, clusterAssment):
    dataSet = np.array(dataSet)

    numSamples= np.shape(dataSet)[0]
    dim = np.shape(dataSet)[1]
    if dim != 2:
        print("Sorry! I can not draw because the dimension of your data is not 2!")
        return 1

    mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']
    if k > len(mark):
        print("")
        return 1

    # draw all samples
    for i in range(numSamples):
        markIndex = int(clusterAssment[i])
        plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex])

    plt.show()


if __name__ == '__main__':
    print("加载数据")
    dataSet = []
    fileIn = open('data\\testData.txt')
    for line in fileIn.readlines():
        lineArr = line.strip().split(' ')
        dataSet.append([float(lineArr[0]), float(lineArr[1])])


    #转化为矩阵
    k = 2
    # centroids = KMeans(n_clusters=k, random_state=9).fit_predict(dataSet)
    clusterAssment = MiniBatchKMeans(n_clusters=k, batch_size=200, random_state=9).fit_predict(dataSet)
    # # 最后结果
    print(clusterAssment)
    # print("显示数据")
    showCluster(dataSet, k, clusterAssment)

附录三

基于tensorflow实现的算法程序

# -*- coding: utf-8 -*-
import tensorflow as tf
import matplotlib.pyplot as plt
import numpy as np

K = 4 # 类别数目
MAX_ITERS = 1000 # 最大迭代次数
# MAX_ITERS = 2 # 最大迭代次数
N = 200 # 样本点数目

centers = [[-2, -2], [-2, 1.5], [1.5, -2], [2, 1.5]] # 簇中心

print("1、加载数据")
dataSet = []
fileIn = open('data\\testData.txt')
for line in fileIn.readlines():
    lineArr = line.strip().split(' ')
    dataSet.append([float(lineArr[0]), float(lineArr[1])])

N = len(dataSet)

# print("2、数据归一化")
# print(dataSet[0])
# # dataSet = np.mat(dataSet)
# # print(dataSet[0])

#展示数据
def showCluster(dataSet, k, clusterAssment):
    dataSet = np.array(dataSet)

    numSamples= np.shape(dataSet)[0]
    dim = np.shape(dataSet)[1]
    if dim != 2:
        print("Sorry! I can not draw because the dimension of your data is not 2!")
        return 1

    mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']
    if k > len(mark):
        print("")
        return 1

    # draw all samples
    for i in range(numSamples):
        markIndex = int(clusterAssment[i])
        plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex])

    plt.show()

# 计算类内平均值函数
def clusterMean(data, id, num):
    # 第一个参数是tensor，第二个参数是簇标签，第三个是簇数目
    total = tf.unsorted_segment_sum(data, id, num)
    count = tf.unsorted_segment_sum(tf.ones_like(data), id, num)
    return total/count

# 构建graph
points = tf.Variable(dataSet)
cluster = tf.Variable(tf.zeros([N], dtype=tf.int64))
# 将原始数据前k个点当做初始中心
centers = tf.Variable(tf.slice(points.initialized_value(), [0, 0], [K, 2]))

# 复制操作，便于矩阵批量计算距离
repCenters = tf.reshape(tf.tile(centers, [N, 1]), [N, K, 2])
repPoints = tf.reshape(tf.tile(points, [1, K]), [N, K, 2])
# 计算距离
sumSqure = tf.reduce_sum(tf.square(repCenters-repPoints), reduction_indices=2)
# 寻找最近的簇中心
bestCenter = tf.argmin(sumSqure, axis=1)
# 检测簇中心是否还在变化
change = tf.reduce_any(tf.not_equal(bestCenter, cluster))
# 计算簇内均值
means = clusterMean(points, bestCenter, K)
# 将粗内均值变成新的簇中心，同时分类结果也要更新
with tf.control_dependencies([change]):
    # 复制函数
    update = tf.group(centers.assign(means), cluster.assign(bestCenter))

with tf.Session() as sess:
    sess.run(tf.initialize_all_variables())
    changed = True
    iterNum = 0
    while changed and iterNum < MAX_ITERS:
        iterNum += 1
        # 运行graph
        [changed, _] = sess.run([change, update])
        [centersArr, clusterArr] = sess.run([centers, cluster])

    print(clusterArr)
    print(centersArr)
    showCluster(dataSet, K, clusterArr)
        # # 显示图像
        # fig, ax = plt.subplots()
        # ax.scatter(dataSet.transpose()[0], dataSet.transpose()[1], marker='o', s=100, c=clusterArr)
        # plt.plot()
        # plt.show()

附录四

测试数据

 1.658985 4.285136
 -3.453687 3.424321
 4.838138 -1.151539
 -5.379713 -3.362104
 0.972564 2.924086
 -3.567919 1.531611
 0.450614 -3.302219
 -3.487105 -1.724432
 2.668759 1.594842
 -3.156485 3.191137
 3.165506 -3.999838
 -2.786837 -3.099354
 4.208187 2.984927
 -2.123337 2.943366
 0.704199 -0.479481
 -0.392370 -3.963704
 2.831667 1.574018
 -0.790153 3.343144
 2.943496 -3.357075
 -3.195883 -2.283926
 2.336445 2.875106
 -1.786345 2.554248
 2.190101 -1.906020
 -3.403367 -2.778288
 1.778124 3.880832
 -1.688346 2.230267
 2.592976 -2.054368
 -4.007257 -3.207066
 2.257734 3.387564
 -2.679011 0.785119
 0.939512 -4.023563
 -3.674424 -2.261084
 2.046259 2.735279
 -3.189470 1.780269
 4.372646 -0.822248
 -2.579316 -3.497576
 1.889034 5.190400
 -0.798747 2.185588
 2.836520 -2.658556
 -3.837877 -3.253815
 2.096701 3.886007
 -2.709034 2.923887
 3.367037 -3.184789
 -2.121479 -4.232586
 2.329546 3.179764
 -3.284816 3.273099
 3.091414 -3.815232
 -3.762093 -2.432191
 3.542056 2.778832
 -1.736822 4.241041
 2.127073 -2.983680
 -4.323818 -3.938116
 3.792121 5.135768
 -4.786473 3.358547
 2.624081 -3.260715
 -4.009299 -2.978115
 2.493525 1.963710
 -2.513661 2.642162
 1.864375 -3.176309
 -3.171184 -3.572452
 2.894220 2.489128
 -2.562539 2.884438
 3.491078 -3.947487
 -2.565729 -2.012114
 3.332948 3.983102
 -1.616805 3.573188
 2.280615 -2.559444
 -2.651229 -3.103198
 2.321395 3.154987
 -1.685703 2.939697
 3.031012 -3.620252
 -4.599622 -2.185829
 4.196223 1.126677
 -2.133863 3.093686
 4.668892 -2.562705
 -2.793241 -2.149706
 2.884105 3.043438
 -2.967647 2.848696
 4.479332 -1.764772
 -4.905566 -2.911070