Question

K-Means聚类若干问题

Answer 1

1 K-Means聚类收敛性怎么证明？一定会收敛？？？

2 聚类中止条件：迭代次数、簇中心变化率、最小平方误差MSE？？？

3 聚类初值的选择，对聚类结果的影响？？？（K-Means对初值是敏感的）

4 肘部选择法——确定聚类数K

没有所谓最好的选择聚类数的方法，通常是需要根据不同的问题，人工进行选择的。选择的时候思考我们运用 K-均值算法聚类的动机是什么，然后选择能最好服务于该目的标聚类数。当人们在讨论，选择聚类数目的方法时，有一个可能会谈及的方法叫作“肘部法则”。 关于“肘部法则”，我们所需要做的是改变 K 值，也就是聚类类别数目的总数 。我们 用一个聚类来运行 K 均值聚类方法。这就意味着，所有的数据都会分到一个聚类里，然后计算成本函数J，K 代表聚类种类 。

我们可能会得到一条类似于这样的曲线。像一个人的肘部。这就是“肘部法则”所做的，让我们来看这样一个图，看起来就好像有一个很清楚的肘在那儿。好像人的手臂，如果你伸出你的胳膊，那么这就是你的肩关节、肘关节、手。这就是“肘部法则”。你会发现这种模式，它的畸变值会迅速下降，从 1 到 2，从 2 到 3 之后，你会在 3 的时候达到一个肘点。在此之后，畸变值就下降的非常慢，看起来就像使用 3 个聚类来进行聚类是正确的，这是因为 那个点是曲线的肘点，畸变值下降得很快 ，K 等于 3 之后就下降得很慢，那么我们就选 K 等于 3。 当你应用“肘部法则”的时候，如果你得到了一个像上面这样的图，那么这将是一种用来选择聚类个数的合理方法。

uk是第k 个类的重心位置。成本函数是各个类畸变程度（distortions）之和。每个类的畸变程度等于该类重心与其内部成员位置距离的平方和。若类内部的成员彼此间越紧凑则类的畸变程度越小，反之，若类内部的成员彼此间越分散则类的畸变程度越大。求解成本函数最小化的参数就是一个重复配置每个类包含的观测值，并不断移动类重心的过程。

importnumpyasnpimportmatplotlib.pyplotaspltfromsklearn.clusterimportKMeansfromscipy.spatial.distanceimportcdistx = np.array([1,2,3,1,5,6,5,5,6,7,8,9,7,9])y = np.array([1,3,2,2,8,6,7,6,7,1,2,1,1,3])data = np.array(list(zip(x, y)))# 肘部法则 求解最佳分类数# K-Means参数的最优解也是以成本函数最小化为目标# 成本函数是各个类畸变程度（distortions）之和。每个类的畸变程度等于该类重心与其内部成员位置距离的平方和# 画肘部图aa=[]K = range(1,10)forkinrange(1,10):    kmeans=KMeans(n_clusters=k)    kmeans.fit(data)    aa.append(sum(np.min(cdist(data, kmeans.cluster_centers_,'euclidean'),axis=1))/data.shape[0])plt.figure()plt.plot(np.array(K), aa,'bx-')plt.show()# 绘制散点图及聚类结果中心点plt.figure()plt.axis([0,10,0,10])plt.grid(True)plt.plot(x, y,'k.')kmeans = KMeans(n_clusters=3)kmeans.fit(data)plt.plot(kmeans.cluster_centers_[:,0], kmeans.cluster_centers_[:,1],'r.')plt.show()

5 K-Means优缺点及适用范围

K值需要预先给定，属于预先知识，很多情况下K值的估计是非常困难的，对于像计算全部微信用户的交往圈这样的场景就完全的没办法用K-Means进行 。对于可以确定K值不会太大但不明确精确的K值的场景，可以进行迭代运算，然后 找出Cost Function最小时所对应的K值，这个值往往能较好的描述有多少个簇类 。

K-Means算法对 初始选取的聚类中心点是敏感的 ，不同的随机种子点得到的聚类结果完全不同

K-Means算法 并不是适用所有的样本类型 。它 不能处理非球形簇、不同尺寸和不同密度的簇 。

K-Means算法对离群点的数据进行聚类时，K均值也有问题，这种情况下，离群点检测和删除有很大的帮助。（ 异常值对聚类中心影响很大，需要离群点检测和剔除 ）

5.K-Means算法对噪声和离群点敏感，最重要是结果不一定是全局最优，只能保证局部最优。

6 从K-Means 到 Gaussian Mixture Model

数据表示

在 k-means 中，我们用单个点来对 cluster 进行建模，这实际上是一种最简化的数据建模形式。这种用点来对 cluster 进行建模实际上就已经假设了各 cluster 的数据是呈圆形（或者高维球形）分布的。但在实际生活中，很少能有这种情况。 所以在 GMM 中，我们使用一种更加一般的数据表示，也就是高斯分布。

数据先验

在 k-means 中，我们假设各个 cluster 的先验概率是一样的，但是各个 cluster 的数据量可能是不均匀的。举个例子，cluster A 中包含了10000个样本，cluster B 中只包含了100个。那么对于一个新的样本，在不考虑其与 A B cluster 相似度的情况，其属于 cluster A 的概率肯定是要大于 cluster B的。 在 GMM 中，同样对数据先验进行了建模。

相似度衡量

在 k-means 中，我们通常采用 欧氏距离来衡量样本与各个 cluster 的相似度 。这种距离实际上假设了数据的 各个维度对于相似度的衡量作用是一样的 。 但在 GMM 中，相似度的衡量使用的是后验概率

通过引入协方差矩阵，我们就可以对各维度数据的不同重要性进行建模。

数据分配

在 k-means 中，各个 样本点只属于与其相似度最高的那个cluster ，这实际上是一种 hard clustering 。 在 GMM 中则使用的是后验概率来对各个cluster 按比例分配，是一种 fuzzy clustering 。

Hierarchical Clustering 与 K-Means 和 GMM 这一派系的聚类算法不太相同：

K-Means 与 GMM 更像是一种 top-down 的思想，它们首先要解决的问题是，确定 cluster 数量，也就是 k 的取值。在确定了 k 后，再来进行数据的聚类。

Hierarchical Clustering 则是一种 bottom-up 的形式，先有数据，然后通过不断选取最相似的数据进行聚类。

K-Means业界用得多的原因之一就是 收敛快 ，现在还能通过分布式计算加速，别的原因有调参就一个K。

链接：https://www.jianshu.com/p/cc74c124c00b

来源：