聚类是一种运用广泛的探索性数据分析技术，人们对数据产生的第一直觉往往是通过对数据进行有意义的分组，通过对对象进行分组，使相似的对象归为一类，不相似的对象归为不同类。

在研究聚类算法原理以及应用聚类算法的时候，我们自己首先要明白，聚类算法并不总是有效，甚至是完全不合理的。我们称其为”聚类的悖论“，之所以会出现悖论，主要的原因是：

对于各种各样的聚类算法，有没有一些基本性质是独立于具体算法或任务的呢？很多人尝试对聚类提出一个公理化的定义，让我们讨论Kleninberg（2003）提出的尝试方法：

考虑一个聚类函数F，将任意有限域X及不相似函数d作为输入，返回X的一个划分

对任意的域集 X，不相似函数 d，以及任意的 a > 0，下式成立：

尺度不变性是一种非常自然的要求，因为如果聚类函数输出的结果依赖于测量点之间的距离测度单元，那将显得十分奇怪和不合理。

对任意的有限集 X 和划分 C = （C1，C2，....，Ck)（划分到非空子集），存在多种不相似函数 d 使得下式成立：

。

丰富性要求主要想说明聚类函数的输出是由函数 d 全权决定，也是一种十分直观的特征。

如果 d 和 d' 都是 X 上的不相似函数，对任一，根据 F（X，d）：

一致性要求是和聚类基本定义相关的要求，我们希望相似的点聚到一类，不相似的点分属不同类，因此共享同类的点更相似，已经分离的点不相似，聚类函数应当对之前的聚类决策有很强的“支撑”作用。

值得注意的是，Kleinberg在2003已经给出了下述“不可能”结论！

不存在一个函数F同时满足上述三种属性：尺度不变性，丰富性，一致性

但是，Kleninberg的“不可能”结论可以通过改变属性的限制范围来规避。即不用100%满足上述三条件

例如，如果讨论含固定数量参数的聚类函数，很自然地将丰富性改为 k-丰富性（即，将域划分到k个子集，这个限制比丰富性RI原则更松散一些）。k-均值聚类满足k-丰富性、尺度不变性和一致性，因此能够达到一致。或者可以放松一致性属性。

笔者思考：

给定一项任务，聚类函数的选取必须考虑该任务的特定属性（是否可以放松要求，又是否有一些地方是需要强要求）。没有统一的聚类解决方案，就像没有一种分类算法能够对每一项可学习任务都能学习（no free lunch定理）。和其他分类预测一样，聚类必须考虑特定任务的先验知识。

不同的算法有着不同的应用背景，有的适合大数据集，可以发现任意形状的聚类；有的算法思想简单直观，适用于小数据集。总的来说，算法都试图从不同途径实现对数据集进行高效、可靠的聚类。数据挖掘对聚类的典型要求包括：

当聚类对象由几百上升到几百万，我们希望最后的聚类结果的准确度能保持一致

有些聚类算法，其处理对象的属性的数据类型只能是数值类型，但是在实际应用场景中，我们往往会遇到其他类型的数据（例如二元数据），分类数据等等，虽然我们也可以在预处理数据时将这些其他类型的数据转换成数值型数据，但是在聚类效率上或者聚类准确度上往往会有折损

因为许多聚类算法是基于距离（例如欧式距离或曼哈顿距离）来量化实例对象之间的相似度的，基于这种方式，我们往往只能发现相似尺寸和密度的球状类簇或者凸形类簇。但是在很多场景下，类簇的形状可能是任意的

很多算法在分析过程中需要开发者提供一定的参数（例如期望的类簇K个数、类簇初始质心），这导致了聚类结果对这些参数是十分敏感的，这不仅加重了开发者的负担，也非常影响聚类结果的准确性

所谓的噪声数据，可以理解为影响聚类结果的干扰数据，这些噪声数据的存在会造成聚类结果的“畸变”，最终导致低质量的聚类

一些聚类算法不能将新加入的数据插入到已有的聚类结果，输入次序的敏感是指，对于给定的数据对象集合，以不同的次序提供输入对象时，最终产生的聚类结果的差异会比较大

有些算法只适合处理2维或者3维的数据，而对高维数据的处理能力很弱，因为在高维空间中数据的分布可能十分稀疏，而且高度倾斜。

在实际应用中可能需要在各种条件下进行聚类，因为同一个聚类算法，在不同的应用场景中所带来的聚类结果也是各异的，因此找到满足“特定约束”的具有良好聚类特性的数据分组是十分有挑战的。这里最困难的问题就在于如何是识别我们要解决的问题中隐含的“特定约束”具体是什么，以及该使用什么算法来最好的“适配”这种约束

我么希望得到的聚类结果都能用特定的语义、知识进行解释，和实际的应用场景相联系

聚类是将数据对象的集合分成相似的对象类的过程，使得同一个簇（或类）中的对象之间具有较高的相似性，而不同簇中的对象具有较高的相异性。

按照聚类的尺度，聚类方法可被分为以下三种：

信息瓶颈是由 Tishby，Pereira和 Bialek 提出的聚类技术，其概念来源于信息论。

用一个文本聚类的问题来解释这个概念，假设我们将每个文本表示为一个词袋，即，每个文档都是一个向量

其中 n 是字典的长度，当且仅当第 i 个词在文档中出现。给定一个有 m 个文档的集合，我们可以将 m 个文档的词袋表示理解为随机变量 x 的联合概率分布，指示文档的身份，以及一个随机变量 y，指示单词在词典中的身份。

根据这种解释，信息瓶颈是指：将聚类属性表示为另一个随机变量C（归纳到具体的类别 k 中）（其中 k 同样由方法确定）。一旦将 x，y，C 表述为随机变量，我们可以使用信息论中的方法来表示聚类目标。

信息瓶颈的目标是：

其中是两个随机变量的互信息，在每个点分属聚类的所有可能概率分布中求取极小值。

直观上讲，我们希望达到两个矛盾的目标。

解信息瓶颈准则下的最优化问题通常是非常困难的，解决方案思路上类似EM准则。

分类效用度量的是聚类算法将实例集分隔成聚类的总体质量。需要注意的是，分类效用不是以MDL为基础的，而是一个类似于定义在条件概率上的二次损失函数，它借助了信息论中互信息的一些思想理念。

我们来分析一下上面这个分类效用CU公式。

Relevant Link:

一种流行的聚类算法是首先对可能的聚类定义一个代价函数，聚类算法的目标是寻找一种使代价最小的划分。

在这类范例中，聚类任务转化为一个优化问题，目标函数是一个从输入（X，d）和聚类方案 C = （C1，C2，....，Ck）映射到正实数（即损失值）的函数。

给定这样一个目标函数，我们将其表示为 G，对于给定的一个输入（X，d），聚类算法的目标被定义为寻找一种聚类 C 使 G((X，d)，C) 最小。

其中，Ci 中心点被定义为：

所以上式也可以写成如下形式：

上述定义的损失函数，将聚类问题转换为了一个优化问题，但是要注意的是，理论和实际的工程化是存在一定的差距的。

k均值目标函数在实际的聚类应用中很常见。然而，事实证明寻找k均值（k-means）算法的最优解通常是计算不可行的（NP问题）。所以通常会用下面这种简单的迭代算法作为替代算法

因此，多数情况下，k均值聚类值得是这种算法的结果而不是最小化 k 均值目标函数的结果。

在学习具体的 K-means 算法细节之前，我们需要了解 K-means 原生存在的一些问题：

kMeans聚类算法是数据挖掘十大算法之一，算法需要接受参数 k（k 个初始聚类中心）(也可由算法随机产生指定)，即将数据集进行聚类的数目和k个簇的初始聚类“中心”，结果是同一类簇中的对象相似度最高，不同类簇中的数据相似度最低，其聚类过程可以用下图表示

如图所示，数据样本用圆点表示，每个簇的中心点用叉叉表示

聚类中心的个数K需要事先给定，但在实际中这个 K 值的选定是非常难以估计的，很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。有几种可能的策略可以缓解这种问题。

这个过程会是一个漫长的调试过程，我们通过设置一个[k, k+n]范围的K类值，然后逐个观察聚类结果，最终决定该使用什么K值对当前数据集是最佳的

在实际情况中，往往是对特定的数据集有对应一个最佳的K值，而换一个数据集，可能原来的K值效果就会下降。但是同一个项目中的一类数据，总体上来说，通过一个抽样小数据集确定一个最佳K值后，对之后的所有K值都能获得较好的效果。

另一种可能的方法是开始先找出很少几个聚类，然后决定是否值得将它们分裂。

我们可以选择k=2，执行k均值聚类直到它终止，然后考虑分裂每个聚类。

分裂聚类的一种方法是在变化最大的方向、距离聚类中心一个标准差的位置产生一个新的种子，随后在反方向、等距建立第二个种子。然后基于这两个新的种子，对聚类中的点进行k均值聚类。

聚类分裂暂时完成时，是否值得保留分裂，或者原来的聚类也是合理的？查看所有点离聚类中心距离的平方和是不合理的，因为量子子聚类的和一定是较小的。这个时候需要引入MDL原则，为每新建一个聚类引入惩罚。在分裂与聚类效果之间寻求最佳平衡。

刚开始时是原始数据，杂乱无章，没有label，看起来都一样，都是绿色的

Kmeans需要人为地确定初始聚类中心，不同的初始聚类中心可能导致完全不同的聚类结果。在实际使用中我们往往不知道我们的待聚类样本中哪些是我们关注的label，人工事先指定质心基本上是不现实的，在大多数情况下我们采取随机产生聚类质心这种策略

假设数据集可以分为两类，令K = 2，随机在坐标上选两个点，作为两个类的中心点(聚类质心)

这一步也非常直观，计算样本点和所有质心的“距离”，选取“距离”最小（argmin）的那个质心作为该样本所属的类别。

这里要注意的是，特征空间中两个实例点的距离是两个实例点相似程度的反映，高维向量空间点的距离求解，可以泛化为Lp距离公式，它在不同的阶次数中分为不同的形式

输出： 簇划分C.　

可以看到，DBSCAN在不断发现新的核心点的同时，还通过直接密度可达，发现核心点邻域内的核心点，并把这些邻域内的核心点都归纳到第 k 个聚类中。而噪音点没每轮 k 聚类中会被全局过滤不会参与下一轮启发式发现中，只有边界点在下一次跌打中会被再次尝试检验是否能够成为新聚类的核心点

Relevant Link: 

该算法是Alex Rodriguez和Alessandro Laio在Science上发表的《Clustering by fast search and find of density peaks》所提出的一种新型的基于密度的聚类算法。

该聚类算法的核心思想在于对聚类中心（cluster centers）的刻画上，算法认为聚类中心同时具有以下两个特点：

该算法的假设类簇（cluster centers）的中心由一些局部密度比较低的点围绕，并且这些点距离其他有高局部密度的点的距离都比较大。

对于样本集中的任何数据点s，可以定义两个值：局部密度ρi以及到高局部密度点的距离δi，这两个值仅仅取决于两点之间的距离dij。

包括 Cut-off kernel 和 Gaussian kernel 两种计算方式：

其中函数

参数称为截断距离（cutoff distance），需要在算法启动时显式指定。从该模型公式中可以看出，局部密度 ρi 表示的是样本集 S 中与数据点 xi 之间的的距离小于 dc 的数据点。

这里 dc 可以理解为一个边界阈值，dc 设置的越小，表示希望算法对聚类的敏感度越高，即在尽可能小的区域内发现聚类社区。

和 cut-off kernel一样，与 x 的距离小于 dc 的数据点越多，pi 的值越大。

对比上面两式可以看出，cut-off kernel为离散值，Gaussian kernel为连续值，因此，相对来说，Gaussian产生冲突（即不同的数据点具有相同的局部密度值）的概率更小

设表示数据点局部密度的一个降序排列下标序，即它满足：。

则可以定义：

这个公式非常优美，它定义了：

至此，对于 S 中的每一个数据点 Xi，可以通过进行抽象表征。考虑下图的例子，其中包含28个二维数据点，将二元对在平面上画出来。

我们看到，1号和10号数据点由于同时具有较大的局部密度和类间距离，于是从数据集中“脱颖而出（pop up）”了，而这两个数据点恰好是左图中数据集的两个聚类中心。

此外，26，27，28这三个数据点在原始数据集中是“离群点”，它们在右图中也很有特点：其局部密度很小，类间距离很大。

从直观上来理解，上面右图对确定聚类中心（cluster centers）有决定性作用，因此也将这种由对应的图称为决策图（decision graph）。

聚类中心确定之后，剩余点被分配给与其具有较高密度的最近邻居相同的类簇。与其他迭代优化的聚类算法不同，类簇分配在单个步骤中执行。

在聚类分析中, 通常需要确定每个点划分给某个类簇的可靠性。

在该算法中, 可以首先为每个类簇定义一个边界区域（border region）， 亦即划分给该类簇但是距离其他类簇的点的距离小于dc的点，这个区域中的点集可以认为是圈出了聚类中心的整体。然后为每个类簇找到其边界区域的局部密度最大的点，该类簇中所有局部密度大于该点的局部密度的点被认为是类簇核心的一部分（亦即将该点划分给该类簇的可靠性很大），其余的点被认为是该类簇的光晕， 亦即可以认为是噪音（outlier）。

图A表示点分布，其中包含非球形点集和双峰点集。B和C分别表示4000和1000个点按照A中模式的分布，其中点根据其被分配的不同类簇着色，黑色的点属于类簇光晕。D和E是对应的决策图，而F表示的是不同点量下不正确聚类点的比率，误差线代表平均值的标准差。

下图是分别利用点集和Olivetti脸部图片集的聚类结果

设待聚类数据集，其包含个cluster

值得注意的是，该聚类算法得到的聚类中心可以作为其他聚类算法（例如k-means）的初始聚类中心。

Relevant Link:

基于模型的方法给每个聚类假定一个模型（预先设定），然后寻找能够很好地满足这个模型的数据集。这样一个模型可能是数据点在空间中的密度分布函数或者其他。它的一个潜在的假定就是：

通常有两种尝试方向：统计方案；和神经网络方案

关于神经网络方案方面的讨论可以参阅我之前的一篇blog

Relevant Link:

为了缓解上述问题，一个更为理论性的统计学方法可以克服聚类问题的部分上述缺点。

从概率的角度看，聚类的目标是寻找给定数据的最有可能的集合。由于任何有限数量的证据都不足以对某件事做完全肯定的结论，所以实例甚至是训练实例也不能绝对地被分在这个聚类或那个聚类。而应当说实例都以一定的可能性分属于每个聚类。这有助于消除那些硬性而快速的判断方案引发的脆弱性。

统计聚类的基础是建立在一个称为有限混合（finite mixture）的统计模型上。

混合是指用k个概率分布代表k个聚类，控制聚类成员的属性值。换句话说，对某个具体实例，每个分布给出假设已知实例属于这个聚类，并且它有某组属性值集合的概率（即 P(v | C)）。

每个聚类都有不同的分布，任何具体实例”实际上“属于且只属于一个聚类，但不知道是哪个。最后，各个聚类并不是等可能的，存在某种反映它们相对总体数量的概率分布。

以一维情况为例，最简单的有限混合情况是在一个一维坐标轴上的数值属性，每个聚类都是一个高斯分布，但有不同的均值和方差。我们的目标是计算每个聚类的平均值和方差，以及聚类之间的总体分布。混合模型将几个正态分布组合起来，它的概率密度函数看起来就像一组连绵的山脉，每座山峰代表一个高斯分布。

一个二类混合模型

上图中有两个聚类A和B，每个都呈正态分布，

现在，想象所给的数据集没有类值，只有数据，要求确定模型的5个参数：（μA，σA，μB，σB，pA），这就是有限混合问题。

关于使用EM算法训练GMM模型的相关讨论，可以参阅另一篇文章。

如果5个参数一致，要找出某个给定实例来自每种分布的概率是很简单的。给定实例x，它属于聚类A的概率是：

这里，是聚类A的正态分布函数，即：

在做比较时，分母Pr[x]会被消除，只要比较分子大小即可。这和朴素贝叶斯分类是一样的，都是简单的贝叶斯定理的应用。

Relevant Link: