读sklearn源码学机器学习——kmeans聚类算法

题记：凌晨3点半的不眠，是这个时代太聒噪，还是内心的不安

kmeans知识体系

从代码中梳理知识体系

sklearn中kmeans源码

源码结构

kmeans算法属于cluster包的k_means.py文件。使用的过程中通过

from sklearn.cluster import Kmeans导入

在使用常规（不含大批量数据的情况下）kmeans算法的实现过程如上图所示，Kmeans主类，包含若干的内部函数（紫色所示），若干的外部函数（蓝色所示）。函数之间的调用关系如上面箭头所示。最核心的函数有：_k_init函数，提供算法的初始化信息，这个过程中牵扯到策略的选择；_kmeans_single_elkan，通过elkan策略的中心点选择；_kmeans_single_lloyd，通过EM策略的中心点选择。

kmeans关键点

1.初始聚类中心点的选择
2.聚类策略的选取（EM,elkn还是其他…）
3.聚类距离的计算

逐一回答

1、挑个简单的，距离的计算
可以发现在参数的设置过程中，以及运算过程中多次用到了样本之间距离的运算，距离的运算一般有以下几种。
闵可夫死及距离（Minkowski distance）

当p=2,就是我们常用的
欧式距离（euclidean distance）

当p=1,
曼哈顿距离、城市街区距离（Manhattan distance,city block distance）

样本间距离计算技巧

阅读源码中我发现，sklearn中的kmeans算法用的时欧氏距离，而且在样本间距离计算的时候直接用的矩阵进行计算，在一般情况下我们对于两个样本间距离的计算恐怕是这样：
比如我们想计算第一个样本与其他样本之间的距离，代码如下。

def normal():
    X=np.asmatrix([[1,2,3],[4,5,6],[7,8,9]])
    normalRes=[]
    for item in X:
        tolerent=X[np.newaxis, 0]-item[np.newaxis, 0]
        normalRes.append(np.einsum("ij,ij",tolerent,tolerent))
    normalDistance=np.sqrt(normalRes)
    return normalDistance

但是在源码中距离的计算实现逻辑是这样的：

def rowNorms(X):#对行每个元素取平方加和
    return np.einsum("ij,ij->i",X,X)
def newMethod(x,y):

    xx=rowNorms(x)[:,np.newaxis]
    yy=rowNorms(y)[np.newaxis,:]
    dot=np.dot(x,y.T)

    print(xx)
    print(yy)
    print(dot)
    res = xx + yy - 2 * dot
    return np.sqrt(res)
X=np.asmatrix([[1,2,3],[4,5,6],[7,8,9]])
print(newMethod(X[[0,1]],X))

运行结果：

[[ 0.          5.19615242 10.39230485]]

刚开始我觉得这样有点多次依据吧~然而很快发现了自己太年轻，比如我想实现第一个跟第二个样本，跟剩下样本的距离就可以：

print(newMethod(X[[0,1]],X))
[[ 0.          5.19615242 10.39230485]
 [ 5.19615242  0.          5.19615242]]

简直不能太方便，而且这种计算方法，直接矩阵操作，在时间和空间复杂度上都是非常好的。接下来附上推导过程：
参考：https://blog.csdn.net/IT_forlearn/article/details/100022244

这个方法用着是真的香
(凌晨4点钟，去睡觉，后面继续更新).

kmeans算法原理

留坑

kmeans算法初始化方法

留坑

kmeans算法改进

留坑