kmeans算法原理，如何选择k，如何选择初始点。

• 流程

1. 随机初始化k个中心点;
2. 计算所有样本到中心点的距离；
3. 比较每个样本到k个中心点的距离，将样本分类到距离最近的类别中；
4. k个类别组成的样本点重新计算中心点(如在每一个方向上计算均值)；
5. 重复2-4，直到中心点不再变化。

• 手撕kmeans

def Kmeans(dataSet, k, distMeas=distEclud, createCent=randCent):
    m = shape(dataSet)[0]  # 样本数m
    clusterAssment = mat(zeros([m, 2])) # m*2, 第一列记录样本属于哪一类,第二列记录样本到类中心点的距离
    centroids = createCent(dataSet, k)  # k*特征数,中心点的坐标
    clusterChanged = True
    
    while clusterChanged:
        clusterChanged = False
        
#         对每一个样本进行循环
        for i in range(m):
            
            # 计算样本距离每一个中心的距离,保留最小距离和归类
            minDist = float("inf")
            minIndex = -1
            for j in range(k):
                distIJ = distMeas(dataSet[i,:], centroids[j,:])
                if distIJ < minDist:
                    minDist = distIJ
                    minIndex = j
                    
            # 只要有一个样本的归类发生变化,标记就改为True(继续循环)
            if clusterAssment[i,0] != minIndex:
                clusterChanged = True
            
            # 把 归类和最小距离存到clusterAssment中
            clusterAssment[i,:] = minIndex, minDist**2
            
        # 每一轮打印中心点的坐标
        print(centroids)
        
        # 更新中心点坐标(根据样本的归类,求每一个分类的质心)
        for cent in range(k):
            pstInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]
            centroids[cent, :] = mean(pstInClust, axis=0)
            
    return centroids, clusterAssment

• kmeans++

  • 思想: 初始化的聚类中心距离尽可能地远
  • 对初始化进行优化
  • 流程
  1. 随机初始化一个中心
  2. 对于每个样本x，计算距离它最近的中心的距离D(x)，每个样本被选为中心点的概率为 。按照轮盘法选择出下一个中心点；
  3. 重复步骤2，直到选出所有的中心点。
     后面的步骤和之前的2-5一致。

• 选择k的方法

  1. 根据业务，比如希望把用户分层高中低三种；
  2. 观察法，对于低纬度数据适用；
  3. 手肘法
     所有样本点到它所存在的聚类中心点的距离之和，作为模型的衡量，
     计算
     越大， 会越小，观察画出来的图像是否有拐点，选择拐点处的;
  4. Gap Statistic
     
     均匀分布产生和原始样本一样多的随机样本，对随机样本做kmeans得到，重复多次可以获得，Gap statistic取最大值所对应的K就是最佳的K。

• 参考文献

1. kmeans++
2. K-means怎么选K?