聚类分析之 K均值_k均值聚类适用于什么样的数据

基于原型的聚类技术创建是数据对象的单层划分。最突出的是 K 均值 和 K 中心点。

• K 均值用质心定义原型，其中质心是一组点的均值。通常，K均值聚类用于 n 维连续空间中的对象。可以用于广泛的数据，因为它只需要对象之间的邻近性度量。
• K 中心点使用中心点定义原型，其中中心点是一组点中最有代表性的点。

基本 K 均值算法

1. 选取 K 个初始质心，其中 K 是用户指定的参数，即所期望的簇的个数。 每个点指派到最近的质心，而指派到一个质心的点集为一个簇。
2. 根据指派到簇的点，更新每个簇的质心。重复指派和更新步骤，直到簇不发生变化，或等价地，直到质心不发生变化。

指派点到最近的质心

为了将点指派到最近的质心，我们需要邻近性度量来量化所考虑的数据的“最近”概念。通常，对欧式空间中的点使用欧几里得距离，对文档用余弦相似性。对于给定的数据类型，可能存在多种适合的邻近性度量。

通常，K均值使用的相似性度量相对简单，因为算法要重复地计算每个点与每个质心的相似度，然而在某些情况下，如数据在低维欧几里得空间时，许多相似度的计算都有可能避免，因此显著地加快了 K均值算法的速度。 二分K 均值是另一种通过减少相似度计算量来加快 K 均值速度的方法。

质心和目标函数

K均值算法中， 质心可能随着数据邻近性度量和聚类目标不同而改变。聚类的目标通常用一个目标函数来表示，该函数依赖于点之间，或点到簇的质心的邻近性；如最小化每个点到最近质心的距离的平方。

选择初始质心

当质心随机初始化时， K均值的不同运行将产生不同的总 SSE（误差的平方和）。
dist 是欧几里得空间中两个对象之间的标准欧几里得距离

以上图为例。
上图左侧显示了一个聚类结果，三个簇的SSE 是全局最小的，而图右 显示了一个次最优聚类，它只有局部最小。

选择适当的初始质心是基本 K 均值过程的关键过程，常见的方法是随机地选取初始质心，但是簇的质量常常很差。

图 8-5与上图数据集相同，但是由于簇的初始位置不同，最终可以看到聚类并不是很好

如何处理随机初始化带来的问题？
处理选取初始质心问题的一种常用技术：多次运行，每次用一组不同的随机初始质心（即不断的试错，总能找到好的），然后选取具有最小SSE的簇集。

 该策略虽然简单，但是效果可能不好，这取决于数据集合寻找簇的个数。
1

上图如果对每个簇对（上下算一对）用两个初始质心，即使两个质心在一个簇中，，质心也会自己重新分布。从而找到真正的簇。
而换个方式，一个簇对用一个初始质心，另一对有三个，则两个真正的簇（即上下一个簇对）合并了，而另外一个分裂了。

随着簇的增加，至少一个簇对只有一个初始质心的可能性也逐步增大。在这种情况下，由于簇对相距较远， K 均值算法不能再簇对之间重新分布质心，这样只能得到局部最优。

随机选择初始质心存在的问题即使重复运行多次也不能克服

因此常常使用其他技术进行初始化，一种有效的方法是，取一个样本，并使用层次聚类技术对它聚类。从层次聚类中提取 K 个簇，并用这些簇的质心作为初始质心。

有效范围：（1）样本相对较小，例如数百到数千（因为层次聚类开销较大） （2） K 相对样本大小较小。

• 另一种选择初始质心的方法： 随机的选择第一个点，或去所有点的质心作为第一个点。然后，对于每个后继初始质心，选择离已经选取过的初始质心最远的点。从而保证不仅是随机的，也是散开的。
• 缺点： 可能选中离群点，而不是稠密区域中的点（很可能发生），而且求离当前初始质心集最远的点开销也非常大（需要遍历全部点吧），为了克服这个问题，通常将该方法用难于点样本，由于离群点很少，找出初始质心所需的计算量也大幅度减小，因为样本的大小常远小于点的个数。

时间复杂性和空间复杂性

K 均值的空间需求是适度的，因为只需要存放数据点和质心，具体来说，所需要的存储量为 O（m + K）n ,其中 m 是点数， n 是属性数， K 均值的时间需求基本上与数据点个数线性相关，具体需要时间为 O（I * K * m* n），其中 I 是收敛所需要的迭代次数。 I 通常很小，可以是有界的，因为大部分变化通常出现在前几次迭代。 因此，只要簇个数 K 显著小于 m ，则 K 均值的计算时间与 m 线性相关，并且是有效的和简单的。

1. 如何处理空簇： 如果所有的点在指派步骤都未分配到某个簇，就会得到空簇。 如果发生，需要选择一个替补质心。否则，平方误差偏大。

• 方法 1 ： 选择一个距离当前任何质心最远的点。这将消除当前对总平方误差影响最大的点。
• 方法 2 ： 另外是从具有最大 SSE 的簇中选择一个替补质心。这将分裂簇并降低聚类的总SSE，如果有多个空簇，则该过程重复多次。

2. 离群点： 使用平方误差标准时，离群点可能过度影响所发现的簇。具体的说，当存在离群点时，结果簇的质心（原型）可能不如没有离群点时那样有代表性，并且SSE也比较高，所以需要提前发现离群点并删掉它们是由用的，但有时，有一些聚类应用，不能删除离群点，当聚类用来压缩数据时，必须对每个点聚类。在某些情况下，明显的离群点可能是最令人感兴趣的点。

用后处理降低SSE

一种明显降低SSE的方法就是找出更多簇，即使用较大的 K，然后很多情况下我们既要降低SSE，但并不想增加簇的个数。
这是可能的，因为 K均值常常收敛于局部极小，可以使用多种技术来“修补” 结果簇，以便产生较小 SSE 的聚类。
策略是每一个簇，因为总 SSE 只不过是每个簇的 SSE 之和，通过在簇上进行诸如分裂和合并等操作，我们可以改变总 SSE ，一种常用的方法是交替地使用簇分裂和簇合并。在分裂阶段将簇分开，而在合并阶段将簇合并。用这种方法，常常可以避开局部最小。并且仍能够得到具有期望个数簇的聚类。

通过增加簇个数来降低总SSE策略：

• 分裂一个簇：通常选择具有最大 SSE 的簇，但是我们也可以分裂在特定属性上具有最大标准差的簇。
• 引进一个新的质心：通常选择离所有簇质心最远的点，如果我们记录每个点对SSE的贡献，则可以容易地确定最远的点，另一种方法是从所有的点或者最高SSE 的点中随机的选择。

通过减少簇个数来最小化总SSE的增长策略：

• 拆散一个簇，删除簇的对应质心，并将簇中的点重新指派到其他簇。理想情况下，被拆散的簇应当是使总 SSE 增加最少的簇。
• 合并两个簇：通常选择质心最接近的两个簇，尽管合并两个导致总 SSE 增加最少的簇 或许更好，分别称为质心方法和 Ward 方法。

增量地更新质心—在所有的点都指派到簇中之前就更新新的簇质心

注意，每步需要零次或两次簇质心更新，因为一个点或者转移到一个新的簇（两次更新），或者留在它的当前簇（零次更新）。使用增量更新策略确保不会产生空簇，因为所有的簇都从单个点开始，并且如果一个簇只有单个点，则该点总是被重新指派到相同的簇。

此外，使用增量更新，可以调整点的相对权值。
增量更新的另一个优点是使用不同于“最小化SSE”的目标。假设给定一个度量簇集的目标函数。当我们处理某个点时。我们可以对每个可能的簇指派计算目标函数的值，然后选择优化目标的簇指派。

缺点：增量地更新质心可能导致次序依赖性，即所产生的簇可能依赖于点的处理次序，此外，增量更新的开销也稍微大一些。

二分K均值

对基本 K 均值算法的直接补充，它基于一种简单思想；为了得到 K 个簇，将所有点的结合分裂成两个簇，从这些簇中选取一个继续分裂，如此直到产生 K 个簇。

二分 K 均值和初始化

如图所示：

• 迭代一： 找到了两个簇对
• 迭代二：分裂了最右边的簇对，
• 迭代三： 分裂了最左边的簇对

二分K均值不太受初始化的困扰，因为它执行力多次二分试验并选取了最小 SSE 的试验结果，还因为每步只有两个质心。

对于发现不同的簇类型， K 均值和它的变种都具有一些局限性。具体地说，当簇具有非球形形状或者具有不同尺寸或密度时， K均值很难检测到“自然”的簇。

K 均值的优点与缺点

• 优点： K 均值简单并且可以用于各种数据类型。它也相当有效，尽管常常多次运行，K 均值的某些变种比如二分 K 均值甚至更有效
• 缺点： K 均值并不适合所有的数据类型。它不能处理非球形簇、不同尺寸和不同密度的簇，尽管指定足够大的簇个数时它
  通常可以发现纯子簇，对包含离群点的数据进行聚类时， K 均值也有问题。
  ==K 均值 仅限具有中心（质心）概念的数据