聚类算法（下）

聚类算法上中讲了大名鼎鼎的K-Means算法及其优化变种，在这篇中几种讲述两位两种不同思路的聚类算法。

层聚类算法

传统层聚类算法—AGNES和DIANA算法

层次聚类和K-Means的思路不太一样，它的思路有点像是决策树，按照层次进行分解，知道满足某种条件为止，传统的层次聚类分为自底而上，和自上而下两类：

• 凝聚的层次聚类: 这类算法是采用采用自底向上的策略，其中的代表便是AGNES算法(AGglomerative Nesting)，它的核心思想是：最初将每个对象作为一个簇，然后这些簇根据某些准则被一步一步合并，两个簇间的距离可以由这两个不同簇中距离最近的数据点的相似度来确定。聚类的合并过程反复进行直到所有的对象满足簇数目。
• 分裂的层次聚类： 和凝聚的层次聚类相反，这种是采用自顶向下的策略，代表算法为DIANA算法(Divisive Analysis)。其核心思想是：首先将所有对象置于一个簇中，然后按照某种既定的规则逐渐细分为越来越小的簇(比如最大的欧式 距离)，直到达到某个终结条件(簇数目或者簇距离达到阈值)。

在AGNES算法中都提到了，簇是根据某些原则进行分裂或者合并的，而这个原则就是簇间距离。计算簇间距离的方法有最小距离（SL聚类），最大距离（CL聚类）以及平均距离（AL聚类），具体的说明如下：

• 最小距离（SL聚类）

  选择两个聚簇中最近的两个样本之间的距离（Single/Word-Linkage）

  注：得到的模型容易形成链式结构

• 最大距离（CL聚类）

  选择两个聚簇中最圆的两个眼本的距离（Complete-Linkage）

  注：如果出现了异常值的话，那他们的构建很容易受这个异常值的影响。

• 平均距离（AL聚类）

  选择两个聚类中的平均值（Average-Linkage聚类算法）或者中值（Median-Linkage聚类法）

AGNES和DIANA算法优缺点如下：

1. 简单，理解容易。
2. 合并点/分裂点选择不太容易。
3. 合并/分类的操作不能进行撤销。
4. 由于执行效率较低$O(t*n^2)$，$t$为迭代次数，$n$为样本点数。

层次聚类优化算法

之前我们看到了传统的层次聚类算法，由于其执行效率太低，且不能动构建的的特点，显然不适合大数据集。于是我们在此基础上引入了BIRCH算法和CURE算法。

BIRCH算法

BIRCH (balanced iterative reducing and clustering using hierarchies) 算法，英文的全称翻译过来以后是平衡迭代削减聚类算法，其构成和我们考研数据结构中学过的B+树非常的类似，甚至很多特性都是相同的，具体的说它构建的树叫做CF（Cluster Feature）-Tree。

1. 节点，即簇的结构： 既然是树，那么就不得不提它的节点的结构了。在BIRCH构建CF树的过程中，每个节点等于说是存放了它之下所有节点的特征，于是他在节点中存放了如下的三部分数据。
   • N，指在这个节点中有多少个样本点。
   • LS，指的是这个节点中的样本相应特征的和。
   • SS，指的是这个节点中的样本相应特征的特征的平方和。
2. 节点之间，节点和子节点，以及叶子结点之间的关系 节点和其子节点是包含的关系，也就是父节点中的N，LS以及SS是其所有子节点的和。而相应的样本点的具体信息指包含在底层节点中（叶子结点的子节点），同时叶子结点构成一个单项链表，同时有一个指针指向其表头。这点的特性是同B+树高度一致的。
3. 最多子女个数，以及分裂判定 和B+树一样，对于树构建中的分叉个数是有限制的，这个限制需要提前给出，即分支因子。同时，值得注意的是，一般而言在构建节点簇的中心点的时候，一般选用第一个进入这个节点的样本点作为中心点，然后根据指定的该簇和中心点限定的距离，即类直径，其往往通过LS和SS算出。判断新入的点是否可以划入该簇，而分裂节点的时候，往往以这个初始点进行分割。 综上我们可以看出，BIRCH算法的本质其实就是动态的插入样本点，然后动态的根据规则构建一个类B+树。它的优点是动态建树且效率高是线性效率，即每个样本点都是一次性插入的，同时也节省内存，所以非常适合大数据集。不过遗憾的是它也是采用距离作为分类标准，故只适合分布呈凸形或者球形的数据集、且需要给定聚类个数和簇之间的相关参数，而这些对节点CF的限制可能导致簇类结果和真实不太一致。

注1：BIRCH不依赖给定的待分类簇数量K，但是给定了K值最好，若不一定K值，最终CF-Tree的叶子结点树木就是最终分类的簇的数目。

注2:BIRCH算法在训练大规模数据集的时候，和mini-batch K-Means相比，BIRCH算法更加适合类别数量K比较多的情况。

注3：由于类直径是通过LS和SS算出的，所以当特征维度超过20～30左右的时候，不建议使用该算法。

CURE算法（使用代表点的聚类法）

CURE（Clustering Using REpresentatives），该算法先把每个数据点看成一类，然后合并距离最近的类直至类个数为所要求的个数为止。但是和AGNES算法的区别是：取消了使用所有点，或用中心点+距离来表示一个类，而是从每个类中抽取固定数量、 分布较好的点作为此类的代表点，并将这些代表点乘以一个适当的收缩因子，使它们更加靠近类中心点。代表点的收缩特性可以调整模型可以匹配那些非球形的场景，而且收缩因子的使用可以减少噪音对聚类的影响。

CURE算法的优点是能够处理非球形分布的应用场景，同时彩娱乐随机抽样和分区的方式可以提高算法的执行效率。

密度聚类算法

密度聚类方法的指导思想是：只要样本点的密度大于某个阀值，则将该样本添加到最近的簇中。这类算法可以克服基于距离的算法只能发现凸聚类的缺点，可以发现任意形状的聚类，而且对噪声数据不敏感。不过这种计算的复杂度高，计算量大。 密度聚类算法的常用算法有DBSCAN和密度最大值算法。

DBSCAN算法

DBSCAN（Density-Based Spatial Clustering of Applications with Noise），将簇定义为密度相连的点的最大集合，能够将足够高密度的区域划分为簇，并且在具有噪声的空间数据上能够发现任意形状的簇。其核心思路是用一个点的ε邻域内的邻居点数衡量该点所在空间的密度，该算法可以找出形状不规则的cluster，而且聚类的时候事先不需要给定cluster的数量。

DBSCAN算法流程

它的算法流程如下：

• 如果一个点$x$的$\varepsilon$领域内包含m个对象，则创建一个x作为核心对象的新簇。
• 寻找并合并核心对象直接密度可达的对象
• 没有新点可以更新簇的时候，算法结束

注：

1. 每个簇至少包含一个核心对象；
2. 非核心对象可以是簇的一部分，构成簇的边缘；
3. 包含过少对象的簇被认为是噪声；
4. 最大的密度相连对象的集合C为密度聚类中的一个簇，它满足两个属性，Maximality和Connectivity，Maximality指的是若$x$属于C，$y$从$x$密度可达，那么$y$也属于C，Connectivity指的是，若$x$和$y$都属于C，那么$x$和$y$是密度相连的。

DBSCAN相关名词解释

其中提到的定义有$\varepsilon$领域，密度，MinPts，核心点，边界点，噪音点，直接密度可达，密度可达，密度相连。他们的解释如下：

• $\varepsilon$邻域($\varepsilon$ neighborhood）：给定对象在半径$\varepsilon$的区域。

• 密度(density)：在$\varepsilon$领域中的$x$的密度，是一个整数依赖于半径$\varepsilon$，$N_{\varepsilon}(X) $指的是半径内的点的个数。

  \[p(x) = |N_{\varepsilon}(X)|\]
• MinPts：指得是判定该点是不是核心点的时候使用的阀值，记为M
• 核心点（core point）：如果$p(x) \geq M$ ,那么称$x$为$X$的核心点，记由$X$中所有核心点构成的集合为$X_c$，并记$X_{nc}$ 表示由$X$中所有非核心点构成的集合。通俗的来说， 核心点是密度达到一定阀值的的点。
• 边界点（border point）：如果非核心点$x$的$\varepsilon$邻域中存在核心点，那么认为$x$为$X$的边界点。通俗来讲就是密度特别稠密的边缘地带，也就是簇的边缘部分。
• 噪音点（noise point）：集合中除了边界点和核心点之外的点都是噪音点，所有噪音点组成的集合叫做$X_{noi}$，显然这些点就是对应稀疏区域的点。
• 直接密度可达：这个是密度聚类中最重要的概念，它指的是给定一个对象集合 $X$，如果$y$是在$x$的$\varepsilon$邻域内，而且$x$是一个核心对象，可以说对象y从对象$x$出发是直接密度可达的
• 密度可达：如果存在一个对象链$p_1, p_2,…,p_m $ ，如果满足$p_{i+1}$是从$p_i$直接密度可达的，那么称$p_m$是从$p_1$密度可达的，简单的来说就像铁链环环相扣差不多。
• 密度相连：在集合$X$中，如果存在一个对象$o$，使得对象$x$和$y$是从$o$关于$\varepsilon$和$m$密度可达的，那么对象$x$和$y$是关于$\varepsilon$和$m$密度相连的。

DBSCAN算法优缺点

优点:

• 不需要事先给定cluster的数目
• 可以发现任意形状的cluster
• 能够找出数据中的噪音，且对噪音不敏感
• 算法只需要两个输入参数
• 聚类结果几乎不依赖节点的遍历顺序

缺点:

• DBSCAN算法聚类效果依赖距离公式的选取，最常用的距离公式为欧几里得距离。但是对于高维数据，由于维数太多，距离的度量已变得不是那么重要
• DBSCAN算法不适合数据集中密度差异很小的情况

MDCA密度最大值聚类算法

MDCA(Maximum Density Clustering Application)算法基于密度的思想引入划分聚类中，能够自动确定簇数量并发现任意形状的簇。另外MDCA一般不保留噪声，因此也避免了阈值选择不当情况下造成的对象丢弃情况。

注：MDCA的算法和AGNES非常相像，不同的是最初的初始簇确定是通过密度来确定的。

MDCA算法思路

MDCA算法核心一共分三步，划分、合并簇以及处理剩余节点三部分。

• 将数据集划分为基本簇：
  • 对数据集X选取最大密度点$P_{max}$ ，形成以最大密度点为核心的新簇$C_i$，按照距离排序计算出序列$S_{p_max}$,对序列的前M个样本数据进行循环判断，如果节点的密度大于等于$density_0$ ，那么将当前节点添加$C_i$中。
  • 循环处理剩下的数据集X，选择最大密度点$P_{max}$，并构建基本簇$C_{i+1}$，直到X中剩余的样本数据的密度均小于$deansity_0$。
• 使用凝聚层次聚类的思想，合并较近的基本簇，得到最终的簇划分：
  • 在所有簇中选择距离最近的两个簇进行合并，合并要求是：簇间距小于等于$dist_0$，如果所有簇中没有簇间距小于$dist_0$的时候，结束合并操作
• 处理剩余节点，归入最近的簇
  • 最常用、最简单的方式是：将剩余样本对象归入到最近的簇。

MDCA算法名词解释

最大密度点：如字面意思，就是密度最大的点，密度计算公式一般取DBSCAN算法中的密度计算公式。 有序序列$S_{p_{max}}$：根据所有对象与最大密度点的距离进行排序。

密度阈值$density_0$：当节点的密度值大于密度阈值的时候，认为该节点属于一个 比较固定的簇，在第一次构建基本簇的时候，就将这些节点添加到对应簇中，如果小于这个值的时候，暂时认为该节点为噪声节点。

簇间距离：对于两个簇C1和C2之间的距离，采用两个簇中最近两个节点之间的距离作为簇间距离。

M值：初始簇中最多数据样本个数