聚类分析

聚类分析：基本概念和算法

一、概念

聚类分析指将物理或抽象对象的集合分组成为由类似的对象组成的多个类的分析过程。在不同的应用领域，很多聚类技术都得到了发展，这些技术方法被用作描述数据，衡量不同数据源间的相似性，以及把数据源分类到不同的簇中。聚类分析将数据划分成有意义或有用的组（簇）。聚类分析仅根据在数据中发现的描述对象及其关系的信息，将数据对象分组。其目标是，组内的对象相互之间是相似的，而不同组中的对象是不同的。组内的相似性越大，组间差别越大，聚类就越好。

一个好的聚类方法要能产生高质量的聚类结果——簇，这些簇要具备以下两个特点：

高的簇内相似性； 低的簇间相似性。

聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现；聚类方法的好坏还取决于该方法是否能发现某些还是所有的隐含模式。

不同的聚类类型：

划分聚类（Partitional Clustering）：划分聚类简单地将数据对象集划分成不重叠的子集，使得每个数据对象恰在一个子集。

层次聚类（Hierarchical Clustering）：层次聚类是嵌套簇的集族，组织成一棵树。

互斥（重叠）聚类（exclusive clustering）：每个对象都指派到单个簇。

非互斥聚类（non-exclusive）：聚类用来反映一个对象.同时属于多个组（类）这一事实。例如：在大学里，一个人可能既是学生，又是雇员。

模糊聚类（fuzzy clustering）：每个对象以一个0（绝对不属于）和1（绝对属于）之间的隶属权值属于每个簇。换言之，簇被视为模糊集。

完全聚类（complete clustering）：完全聚类将每个对象指派到一个簇。

部分聚类（partial clustering）：部分聚类中数据集某些对象可能不属于明确定义的组。如：一些对象可能是离群点、噪声。

聚类分析是研究多要素事物分类问题的数量方法。基本原理是根据样本自身的属性，用数学方法按照某种相似性或差异性指标，定量地确定样本之间的亲疏关系，并按这种亲疏关系程度对样本进行聚类。常见的聚类分析方法有系统聚类法、动态聚类法和模糊聚类法等。 二、算法 （1）K均值

K均值算法表示以空间中k个点为中心进行聚类，对最靠近他们的对象归类。该算法的最大优势在于简洁和快速。劣势在于对于一些结果并不能够满足需要，因为结果往往需要随机点的选择非常巧合。

K均值对于需要进行聚类的数据有一个基本假设：对于每一个

cluster ，我们可以选出一个中心 点 (center)，使得该 cluster 中的所有的点到该中心点的距离小于到其他 cluster 的中心的距离。虽然实际情况中得到的数据并不 能保证总是满足这样的约束，但这通常已经是我们所能达到的最好的结果，而那些误差通常是固有存在的或者问题本身的不可分性造成的。例如下图所示的两个高斯 分布，从两个分布中随机地抽取一些数据点出来，混杂到一起，现在要让你将这些混杂在一起的数据点按照它们被生成的那个分布分开来：

由 于这两个分布本身有很大一部分重叠在一起了，例如，对于数据点 2.5 来说，它由两个分布产生的概率都是相等的，你所做的只能是一个猜测；稍微好一点的 情况是 2 ，通常我们会将它归类为左边的那个分布，因为概率大一些，然而此时它由右边的分布生成的概率仍然是比较大的，我们仍然有不小的几率会猜错。而 整个阴影部分是我们所能达到的最小的猜错的概率，这来自于问题本身的不可

分性，无法避免。因此，我们将 k-means 所依赖的这个假设看作是合理的。

基于这样一个假设，我们再来导出k-means 所要优化的目标函数：设我们一共有 N 个数据点需要分为 K 个 cluster ，k-means 要做的就是最小化

这个函数，其中Tnk在数据点n被归类到cluster k的时候为 1 ，否则为 0 。直接寻找Tnk和uk来最小化J并不容易，不过我们可以采取迭代的办法：先固定uk，选择最优的Tnk，很容易看出，只要将数据点归类到离他最近的那个中心就能保证J最小。下一步则固定

Tnk，再求最优的uk。将J对uk求导并令导数等于零，很容易得到J最小的时候uk应该满足：

=mean(xn),其中xn为属cluster 的点的坐标

亦即uk的值应当是所有cluster k中的数据点的平均值。由于每一次迭代都是取到J的最小值，因此J只会不断地减小（或者不变），而不会增加，这保证了 k-means 最终会到达一个极小值。虽然 k-means 并不能保证总是能得到全局最优解，但是对于这样的问题，像 k-means 这种复杂度的算法，这样的结果已经是很不错的了。

下面我们来总结一下 k-means 算法的具体步骤： 基本的K均值算法： 1.选择k个点作为初始的质心

2.repeat

3.将每个点指派到最近的质心，形成k个簇 4.重新计算每个簇的质心 5.until 质心不发生变化

二分k均值算法是基本k均值算法的直接k个簇。

它将所有点的集合分裂成两个簇，从这些簇中选取一个继续分裂，如此下去，直到产生k个簇。

k均值算法的优点与缺点： 优点：

算法简单； 适用于球形簇；

二分k均值等变种算法运行良好，不受初始化问题的影响。 缺点：

不能处理非球形簇、不同尺寸和不同密度的簇； 对离群点、噪声敏感。 （2）凝聚层次聚类

凝聚的层次聚类采用自底向上的策略，开始时把每个对象作为一个单独的簇，然后逐次对各个簇进行适当合并，直到满足某个终止条件。

本文来源：https://www.bwwdw.com/article/rgnt.html