K-means

Kmeans的优化版本，首先我们知道在kmeans正式聚类之前首先需要完成的就是初始化n个质心。同时，也正是因为这个原因，使得聚类算法存在着一个巨大的缺陷——收敛情况严重依赖于簇中心的初始化状况。试想一下，如果在初始化过程中很不巧的将个（或大多数）簇中心都初始化了到同一个簇中，那么在这种情况下聚类算法很大程度上都不会收敛到全局最小值。也就是说，当簇中心初始化的位置不得当时，聚类结果将会出现严重的错误。例子如下：

Kmeans++算法仅仅只是在初始化簇中心的方式上做了改进，其它地方同聚类算法一样。在初始化簇中心时的方法总结成一句话就是：逐个选取个簇中心，且离其它簇中心越远的样本点越有可能被选为下一个簇中心。 其具体做法如下：

①从数据集中随机（均匀分布）选取一个样本点作为第一个初始聚类中心;
②接着计算每个样本与当前已有聚类中心之间的最短距离，用表示；然后计算每个样本点被选为下一个聚类中心的概率，最后选择最大概率值所对应的样本点作为下一个簇中心；

即把每个样本点到第一个初始质心的距离算出来平方相加，然后用每个样本到该质心的距离数值除以这个平方和，离该质心越远，则数值越大，除后得出的概率也就越大。

③重复第②步，直到选择出个聚类中心；(也就是说Kmeans++仍然需要需要指定簇的个数，也证明了Kmeans++仅在初始化簇的步骤上和Kmeans不同)

需要注意的是sklearn中并没有Kmeans++这个包，而是被整合在了Kmeans的参数中：

init： 即初始值选择的方式，可以为完全随机选择’random’,优化过的’k-means++‘或者自己指定初始化的k个质心。一般建议使用默认的’k-means++’。

以下为可忽略的补充内容：** （没看过）
手撕Kmeans++

def InitialCentroid(x, K):
    c0_idx = int(np.random.uniform(0, len(x)))
    centroid = x[c0_idx].reshape(1, -1)  # 选择第一个簇中心
    k = 1
    n = x.shape[0]
    while k < K:
        d2 = []
        for i in range(n):
            subs = centroid - x[i, :]
            dimension2 = np.power(subs, 2)
            dimension_s = np.sum(dimension2, axis=1)  # sum of each row
            d2.append(np.min(dimension_s))
        new_c_idx = np.argmax(d2)
        centroid = np.vstack([centroid, x[new_c_idx]])
        k += 1
    return centroid
if __name__ == '__main__':
    x, y = make_data()
    K = len(np.unique(y))
    # y_pred = kmeans(x, y)
    y_pred = kmeanspp_visual(x,y,K)
    nmi = normalized_mutual_info_score(y, y_pred)
    print("NMI by ours: ", nmi)
    model = KMeans(n_clusters=K, init='k-means++')
    model.fit(x)
    y_pred = model.predict(x)
    nmi = normalized_mutual_info_score(y, y_pred)
    print("NMI by sklearn: ", nmi)
#结果：
NMI by ours:  0.9456935014894648
NMI by sklearn:  0.9456935014894648