大体流程描述一下

1. 随机选择k个点作为中心点
2. 分簇：利用定义好的距离（可以是欧式或者其他）对比每个点到k个点哪个近，则为哪个簇
3. 更新：将第k个簇取平均得到新的中心点
4. 循环23步骤直到中心点不变（可以设定收敛的最小误差或者设置迭代轮数）

不同距离度量方式

• 欧几里得距离
• 曼哈顿距离

• 余弦距离

  
  距离公式选择

如何选取k

• 手肘法
  核心指标是SSE误差平方和，外面是对k求和，里面是对簇求和，求和内容是每个样本和他所属簇的均值的差的平方。核心思想就是随着聚类数k增大，样本划分更加精细，SSE会越来越小，曲线呈现下降趋势，找到一个点是骤降的，即下降幅度最大，也即是最后是在手肘地方
• Gap Static
  不需要像上述手肘一样还需要画出来去判断，只需计算值，当这个值最大时，它所对应的k就是最好的，方便批量化作业
• 根据业务选取

优缺点

优点

• 时间复杂度低，NKt，样本数乘以簇数乘以迭代轮数，接近线性

缺点

• 对数值敏感（因此需要做预处理、归一化处理），对异常值敏感（因此需要做离散点处理）
• k难以选取
• 局部最优

个人理解是，比如说下图，感觉是三个类，但由于随机初始化问题，有两个初始点分一起了，而本来应该被分成两个类的，到最后可能合并成一个类了，也即是没有分到最优）

理解.png

从文字上理解就是，当初始值选定后，会有个初始的簇，每次更新，簇只会进行很小的移动，因为均值无法跳出初始簇的范围就像你给定初始形状，我们只是在初始形状上进行增减，自然很难得到全局最好的簇。

• 聚类效果依赖于中心初始化

优化

k-means++ （对初始值选择改进）

假设已经选取了n个初始聚类中心，则在选择n+1个聚类中心时，距离当前n个聚类中心越远的点会有更好的概率被选择为第n+1类聚类的中心。聚类中心当然是互相隔离的越远越好，之后的算法步骤同于k-means。（第一个点仍然是随机初始化）

ISODATA（对k值选择改进）

K值大小不确定时可以使用该算法。当遇到海量数据无法准确估计出k时。增加两个操作，分裂操作，对应着增加k；合并操作，对应着减少k

Mini Batch Kmeans

在传统算法中，要计算所有样本点到所有质心的距离，如果样本量非常大，比如达到10w以上，将会非常耗时，此时minibatch kmeans应运而生。大体思想是利用样本的一部分，也即是一个batch size的batch来做kmeans，类似神经网络，一般多跑几次mini batch

核函数

面对非凸的数据分布，可能需要引入核函数来优化，这是核聚类方法的一种，主要思想是通过一个非线性映射将输入控件映射到高维特征空间再来进行聚类

与KNN区别

• kmeans无监督KNN有监督
• kmeans有明显的训练过程，而KNN基本不需要训练，找到最近k个点即可

与EM联系

上述kmeans流程实际上用公式表示出来，如下：

k指的是第k个类，J就是目标函数，要最小，第二个公式是用来计算属于哪个簇，第三个公式是用来计算质心
假设当前J未收敛，则首先可以固定每个类的质心，调整样本所属类别来让J减少；同样固定簇类，则可以来调整质心来使函数减小，这就是EM的思想。

EM思想：
E步计算隐变量z期望
M步最大化

两者联系，Kmeans等价于用EM算法求解以下含隐变量的最大似然问题，（c就是取的k，从1到K）。
E步求上述给定x和mui下c的条件概率期望，这里条件概率可以定义为如果分到最小类则为1，到其他类距离比最小的大，则为0。求期望也即是使P概率最大化。相当于先固定好了质心mui，然后将每个点找到离它最近的簇c。
M步，更新mui参数，此时是每个簇c已确定，对应于kmeans里更新聚类中心。

手撕代码

# 参考代码
# https://www.cnblogs.com/lunge-blog/p/11657415.html
# https://blog.csdn.net/orangefly0214/article/details/86538865
def distance(x1,x2):
    return np.sqrt(np.sum(np.power(x1-x2,2)))
def kmeans(x,k=3,epochs=500,delta = 1e-3):
    # 随机初始化k个质心
    index = np.random.randint(0,len(x),size=k)
    centers = x[index]
    # 用来存放分类结果  放簇索引 
    clusters = np.array([-1]*len(x)) # 用array是为了方便后续操作
    step = 1
    flag = True
    while flag:
        if step>epochs:
            return centers,clusters
        # 分配簇
        for i in range(len(x)):
            minindex = -1
            mindist = float('inf')
            for j in range(k):
                dist = distance(x[i],centers[j])
                if dist<mindist:
                    mindist = dist
                    minindex = j
            clusters[i] = minindex
        # 更新中心
        count = 0 # 判断是否需要停止
        for j in range(k):
            old = centers[j]
            new = np.mean(x[clusters==j],axis=0)
            if distance(new,old)>delta:
                centers[j] = new
            else:
                count += 1
        # 判断是否需要继续
        if count == k:
            flag = False
        step += 1
    return centers,clusters
# 举例
x=np.random.randint(0,50,size=100)
y=np.random.randint(0,50,size=100)
z=np.array(list(zip(x,y)))
import matplotlib.pyplot as plt
%matplotlib inline
plt.scatter(x,y)

样本点.png

centers,clusters = kmeans(z,5)
plt.scatter(z[:,0],z[:,1],c=clusters)

聚类后.png

核心参考：

• https://blog.csdn.net/WangZixuan1111/article/details/98970139
• 百面机器学习
• Pinard https://www.cnblogs.com/pinard/p/6164214.html
• https://www.cnblogs.com/rong86/p/3517573.html
• http://blog.sina.com.cn/s/blog_df7f38100102xel6.html