数据挖掘概念与技术笔记（7）：聚类（1）

下图简单地总结了一些聚类方法的简单划分

基于划分的聚类

聚类分析最简单、最基本的版本是基于划分的聚类，它把对象组织成多个互斥的组或簇。为了使得问题说明简洁，我们假定簇个数作为背景知识给定，这个参数是划分方法的起点。

k-均值（k-mean） ：一种基于形心的技术

k均值算法非常简单，它用簇$C_i$的形心代表该簇。每次确定K个类别中心，然后将各个结点归属到与之距离最近的中心点所在的Cluster，然后将类别中心更新为属于各Cluster的所有样本的均值，反复迭代，直至类别中心不再发生变化或变化小于某阈值。 下面给出该算法的伪代码

• 优点：
  • 是解决聚类问题的一种经典算法，简单、快速
  • 对处理大数据集，该算法保持可伸缩性和高效率
• 缺点：
  • 必须事先给出K，而且对初值敏感，对于不同的初始值，结果可能不同
  • 只能发现球状Cluster，不适合于发现非凸形状的簇或者大小差别很大的簇
  • 对噪声和孤立点数据敏感，如簇中含有异常点，将导致均值偏离严重

如何确定k类

https://www.cnblogs.com/yan2015/p/5239970.html

k-中心点（k-mediods）：一种基于代表对象的技术

k-均值算法对离群点敏感，因为这种对象远离大多数数据，因此分配到一个簇时，它们可能严重地扭曲簇的均值。因此，提出了k-中心点算法，它挑选实际对象代表簇，每个簇使用一个代表对象。这个代表对象选择的规则是：选择簇内一个点到其他点的距离之和的最小代价值，作为新的中心点。

K-中心聚类算法计算的是某点到其它所有点的距离之和最小的点，通过距离之和最短的计算方式可以减少某些孤立数据对聚类过程的影响 。下面给出算法的伪代码

基于层次的聚类

尽管基于划分的聚类算法能够实现把数据集划分成指定数量的簇，但是在某些情况下，需要把数据集划分成不同层上的簇。层次聚类方法将数据组成层次结构或簇的”树”

基于层次的聚类算法（Hierarchical Clustering）可以是凝聚的（Agglomerative）或者分裂的（Divisive），取决于层次的划分是“自底向上”还是“自顶向下”。

• 自顶向下： 它把所有对象至于一个簇中开始，该簇是层次结构的根。然后，它把根上的簇划分为多个较小的子簇，并且递归地把这次簇划分成更小的簇，直到满足终止条件。常见的自顶向下的算法有K-means层次聚类算法。
• 自底向上：把数据集中的每个对象最为一个簇开始，迭代地把簇合并成为更大的簇，直到最终形成一个大簇，或者满足某个终止条件。基于自底向上算法有凝聚算法、BIRCH算法、CURE算法、变色龙算法等。

自顶向下算法

Hierarchical K-means算法

Hierarchical K-means算法是“自顶向下”的层次聚类算法，用到了基于划分的聚类算法那K-means，算法思路如下：

1. 首先，把原始数据集放到一个簇C，这个簇形成了层次结构的最顶层；
2. 使用K-means算法把簇C划分成指定的K个子簇$C_i，i=1,2,…,k$，形成一个新的层；
3. 对于步骤2所生成的K个簇，递归使用K-means算法划分成更小的子簇，直到每个簇不能再划分（只包含一个数据对象）或者满足设定的终止条件。

如下图，展示了一组数据进行了二次K-means算法的过程

Hierarchical K-means算法一个很大的问题是，一旦两个点在最开始被划分到了不同的簇，即使这两个点距离很近，在后面的过程中也不会被聚类到一起。

对于以上的例子，红色椭圆框中的对象聚类成一个簇可能是更优的聚类结果，但是由于橙色对象和绿色对象在第一次K-means就被划分到不同的簇，之后也不再可能被聚类到同一个簇。

自底向上算法

Agglomerative Clustering算法

相比于Hierarchical K-means算法存在的问题，Agglomerative Clustering算法能够保证距离近的对象能够被聚类到一个簇中，该算法采用的“自底向上”聚类的思路。

算法思路，对于数据集$D，D=x_1,x_2,…,x_n$：

1. 将数据集中的每个对象生成一个簇，得到簇列表$C，C=c_1,c_2,…,c_n$
   • a) 每个簇只包含一个数据对象：$c_i=x_i$；
2. 重复如下步骤，直到C中只有一个簇：
   • a) 从C中的簇中找到两个“距离”最近的两个簇：$\min D(ci,cj)$；
   • b) 合并簇$c_i$和$c_j$，形成新的簇$c_{ij}；
   • c) 从C中删除簇$c_i%和$c_j$，添加簇$c_{ij}

簇间距离计算

在上面描述的算法中涉及到计算两个簇之间的距离，对于簇$C_1$和$C_2$，计算$minD(C1,C2)$，有以下几种计算方式：

最小距离：

$$\min\ dist_{min}(C_i,C_j)=\min \mathop{\min} \limits_{p\in C_i,q\in C_j}\{|p-q|\}$$

两个簇之间最近的两个点的距离作为簇之间的距离，该方式的缺陷是受噪点影响大，容易产生长条状的簇。

最大距离：

$$\min\ dist_{max}(C_i,C_j)=\min \mathop{\max} \limits_{p\in C_i,q\in C_j}\{|p-q|\}$$

两个簇之间最远的两个点的距离作为簇之间的距离，采用该距离计算方式得到的聚类比较紧凑。

均值距离： $m_i$和$m_j$为簇内所有点的均值坐标

$$\min\ dist_{mean}(C_i,C_j)=\min |m_i-m_j|$$

平均距离：

$$\min\ dist_{avg}(C_i,C_j)=\min\ \frac{1}{n_in_j}\mathop{\sum}\limits_{p\in C_i,q\in C_j}\{|p-q|\}$$

一个例子

Agglomerative聚类算法的优点是能够根据需要在不同的尺度上展示对应的聚类结果，缺点同Hierarchical K-means算法一样，一旦两个距离相近的点被划分到不同的簇，之后也不再可能被聚类到同一个簇，即无法撤销先前步骤的工作。另外，Agglomerative性能较低，并且因为聚类层次信息需要存储在内存中，内存消耗大，不适用于大量级的数据聚类，下面介绍一种针对大数据量级的聚类算法BIRCH。

BIRCH算法：使用聚类特征树

BIRCH算法利用了一个树结构来帮助实现快速的聚类，这个数结构类似于平衡B+树，一般将它称之为聚类特征树(Clustering Feature Tree，简称CF Tree)。这颗树的每一个节点是由若干个聚类特征(Clustering Feature，简称CF)组成。从下图可以看看聚类特征树是什么样子的：每个节点包括叶子节点都有若干个CF，而内部节点的CF有指向孩子节点的指针，所有的叶子节点用一个双向链表链接起来。

在聚类特征树中，一个聚类特征CF是这样定义的：每一个CF是一个三元组，可以用（N，LS，SS）表示，其中N代表了这个CF中拥有的样本点的数量；LS代表了这个CF中拥有的样本点各特征维度的和向量，SS代表了这个CF中拥有的样本点各特征维度的平方和。 聚类特征本质上是定簇的统计汇总。使用聚类特征，我们可以很容易地推导出簇的许多有用的统计量，例如簇的形心$x_0$、半径R和直径D分别是

$$x_0=\frac{\sum_{i=1}^nx_i}{n}=\frac{LS}{n}$$ $$R=\sqrt{\frac{\sum_{i=1}^n(x_i-x_0)^2}{n}}$$ $$D=\sqrt{\frac{\sum_{i=1}^n\sum_{j=1}^n(x_i-x_j)^2}{n(n-1)}}=\sqrt{\frac{2nSS-2LS^2}{n(n-1)}}$$

其中，R是成员对象到形心的平均距离，D是簇中逐对对象的平均距离。R和D都反映了形心周围簇的紧凑程度。

此外，聚类特征是可加的，也就是说，对于两个不相交的簇$C_1$和$C_2$，其聚类特征分别是$CF_1[n_1,LS_1,SS_1]$和$CF_2 [n_2,LS_2,SS_2]，合并后的簇的聚类特征是

$$CF_1+CF_2=[n_1+n_2,LS_1+LS_2,SS_1+SS_2]$$

对于CF Tree，一般有几个重要参数，第一个参数是每个内部节点的最大CF数B，第二个参数是每个叶子节点的最大CF数L，第三个参数是针对叶子节点中某个CF中的样本点来说的，它是叶节点每个CF的最大样本半径阈值T，也就是说，在这个CF中的所有样本点一定要在半径小于T的一个超球体内。对于图中的CF Tree，限定了B=7， L=5， 也就是说内部节点最多有7个CF，而叶子节点最多有5个CF。

将所有的训练集样本建立了CF Tree，一个基本的BIRCH算法就完成了，对应的输出就是若干个CF节点，每个节点里的样本点就是一个聚类的簇。也就是说BIRCH算法的主要过程，就是建立CF Tree的过程。

聚类特征树CF Tree的生成

下面看看怎么生成CF Tree。先定义好CF Tree的参数： 即内部节点的最大CF数B， 叶子节点的最大CF数L， 叶节点每个CF的最大样本半径阈值T。

开始时CF Tree是空的，没有任何样本，我们从训练集读入第一个样本点，将它放入一个新的CF三元组A，这个三元组的N=1，将这个新的CF放入根节点，此时的CF Tree如下图：

现在继续读入第二个样本点，发现这个样本点和第一个样本点A在半径为T的超球体范围内，即他们属于一个CF，将第二个点也加入CF A,此时需要更新A的三元组的值。此时A的三元组中N=2。此时的CF Tree如下图：

此时读取第三个节点，结果发现这个节点不能融入刚才前面的节点形成的超球体内，也就是说，需要一个新的CF三元组B来容纳这个新的值。此时根节点有两个CF三元组A和B，此时的CF Tree如下图：

当来到第四个样本点时，发现和B在半径小于T的超球体，这样更新后的CF Tree如下图：

那个什么时候CF Tree的节点需要分裂呢？假设现在的CF Tree 如下图， 叶子节点LN1有三个CF， LN2和LN3各有两个CF。叶子节点的最大CF数L=3。此时一个新的样本点来了，发现它离LN1节点最近，因此开始判断它是否在sc1,sc2,sc3这3个CF对应的超球体之内，但是很不幸，它不在，因此它需要建立一个新的CF，即sc8来容纳它。问题是我们的L=3，也就是说LN1的CF个数已经达到最大值了，不能再创建新的CF了，怎么办？此时就要将LN1叶子节点一分为二了。

将LN1里所有CF元组中，找到两个最远的CF做这两个新叶子节点的种子CF，然后将LN1节点里所有CF sc1, sc2, sc3，以及新样本点的新元组sc8划分到两个新的叶子节点上。将LN1节点划分后的CF Tree如下图：

如果内部节点的最大CF数B=3，则此时叶子节点一分为二会导致根节点的最大CF数超了，也就是说，根节点现在也要分裂，分裂的方法和叶子节点分裂一样，分裂后的CF Tree如下图：

有了上面这一系列的图，相信大家对于CF Tree的插入就没有什么问题了，总结下CF Tree的插入：

• 1、从根节点向下寻找和新样本距离最近的叶子节点和叶子节点里最近的CF节点（判断新节点与NLN1和NLN2谁近一些，然后继续往下）
• 2、如果新样本加入后，这个CF节点对应的超球体半径仍然满足小于阈值T，则更新路径上所有的CF三元组，插入结束。否则转入3.
• 3、如果当前叶子节点的CF节点个数小于阈值L，则创建一个新的CF节点，放入新样本，将新的CF节点放入这个叶子节点，更新路径上所有的CF三元组，插入结束。否则转入4。
• 4、将当前叶子节点划分为两个新叶子节点，选择旧叶子节点中所有CF元组里超球体距离最远的两个CF元组，分布作为两个新叶子节点的第一个CF节点。将其他元组和新样本元组按照距离远近原则放入对应的叶子节点。依次向上检查父节点是否也要分裂，如果需要按和叶子节点分裂方式相同。

当然，真实的BIRCH算法除了建立CF Tree来聚类，其实还有一些可选的算法步骤的，现在我们就来看看 BIRCH算法的流程。

• 1） 将所有的样本依次读入，在内存中建立一颗CF Tree, 建立的方法参考上一节。
• 2）（可选）将第一步建立的CF Tree进行筛选，去除一些异常CF节点，这些节点一般里面的样本点很少。对于一些超球体距离非常近的元组进行合并
• 3）（可选）利用其它的一些聚类算法比如K-Means对所有的CF元组进行聚类，得到一颗比较好的CF Tree.这一步的主要目的是消除由于样本读入顺序导致的不合理的树结构，以及一些由于节点CF个数限制导致的树结构分裂。
• 4）（可选）利用第三步生成的CF Tree的所有CF节点的质心，作为初始质心点，对所有的样本点按距离远近进行聚类。这样进一步减少了由于CF Tree的一些限制导致的聚类不合理的情况。

从上面可以看出，BIRCH算法的关键就是步骤1，也就是CF Tree的生成，其他步骤都是为了优化最后的聚类结果。

优点

• 1) 节约内存，所有的样本都在磁盘上，CF Tree仅仅存了CF节点和对应的指针。
• 2) 聚类速度快，只需要一遍扫描训练集就可以建立CF Tree，CF Tree的增删改都很快。
• 3) 可以识别噪音点，还可以对数据集进行初步分类的预处理

缺点

• 1) 由于CF Tree对每个节点的CF个数有限制，导致聚类的结果可能和真实的类别分布不同.
• 2) 对高维特征的数据聚类效果不好。此时可以选择Mini Batch K-Means
• 3) 如果数据集的分布簇不是类似于超球体，或者说不是凸的，则聚类效果不好。

CURE算法

CURE（Clustering Using Representatives）是一种针对大型数据库的高效的聚类算法。基于划分的传统的聚类算法得到的是球状的，相等大小的聚类，对异常数据比较脆弱。CURE采用了用多个点代表一个簇的方法，可以较好的处理以上问题。并且在处理大数据量的时候采用了随机取样，分区的方法，来提高其效率，使得其可以高效的处理大量数据。

我们先看一下基于划分聚类算法的缺陷：

如上图所示，基于划分的聚类算法比如Hierarchical K-means聚类算法，不能够很好地区分尺寸差距大的簇，原因是K-means算法基于“质心”加一定“半径”对数据进行划分，导致最后聚类的簇近似“圆形”。

CURE算法核心的思想是使用一定数量的“分散的”点（scattered points）来代表一个簇（cluster），而不像是其他层次聚类算法中，只使用一个点，使得CURE算法有如下优势：

• 准确地识别任意形状的簇；
• 准确地识别尺寸差距大的簇；
• 很好地处理“噪点”

所以，CURE算法很好地解决了上面提到的聚类结果的缺陷，CURE算法主流程如下：

Pass 1

• 1、从总数据中随机选取一个样本；
• 2、利用层次聚类算法把这个样本聚类，形成最初的簇$C_i,(i=1,2,…,k)$；
• 3、选取“代表点”（representative pionts）;

①对于每个簇，选取代表点（比如4个），这些点尽量分散;

②按照固定的比例α（比如20%），把每个样本点向簇的“质心”收缩，生成代表点

$$\{p'_{i1},p'_{i2},p'_{i3},p'_{i4}\}$$

Pass 2

• 重新扫描所有的数据， 对于点p，找到距离p最近的簇，把它放到 “最近的簇”。简单来讲，是点p到簇$C_i$的距离为点p到簇$C_i$的四个“代表点 中最近的点之间的距离。

收缩系数α的取值不同，聚类结果也相应不同。当α趋于0时，所有的“代表点”都汇聚到质心，算法退化为基于“质心”的聚类；当α趋于1时，“代表点”完全没有收缩，算法退化为基于“全连接”的聚类，因此α值需要要根据数据特征灵活选取，才能得到更好的聚类结果

Chameleon变色龙算法：使用动态建模

Chameleon（变色龙）是一种层次聚类算法，它采用动态建模来确定一对簇之间的相似度。在Chameleon中，簇的相似性依据以下两点评估：1）簇中对象的连接情况 ；2）簇的邻近性。也就是说，如果两个簇的互连性都很高并且它们之间又靠得很近就将其合并。

整体算法流程：

1、创建KNN图，每个节点将其最相似的k个节点用一条边连接起来；

2、使用最大流算法或者最小割算法，将kNN图分隔成小图； 也就是说簇C被划分为子簇CiCi和$C_j$，使得把C二分成$C_i$和$C_j$而被切断的边的权重之和最小。

3、将小簇进行和并，找对最大的度量值$RC*RI^\alpha$的两个簇，合并条件是$RC*RI^\alpha$大于某个阈值，否则结束合并。RC和RI的一个基本思想是，点之间的链接越多，这些点越可能连接成一个簇，C表示一个簇，是点的集合，|C|是集合的大小，即点的个数, $EC(A,B)$表示两个簇之间的边的数量。

相似互连度$RI(C_i,C_j)$

$$RI(C_i,C_j)=\frac{|EC_{\{C_i,C_j\}}|}{\frac{1}{2}(|EC_{C_i}|+|EC_{C_j}|)}$$

相对接近度$RC(C_i,C_j)$

$$RC(C_i,C_j)=\frac{\overline S_{EC_{\{C_i,C_j\}}}}{\frac{|C_i|}{|C_i|+|C_j|} \overline S_{EC_{C_i}}+ \frac{|C_i|}{|C_i|+|C_j|} \overline S_{EC_{C_j}} }$$

其中，分子是连接$C_i$顶点和$C_j$顶点的边的平均权重，分母SECC是最小二分簇$C_i$（或$C_j$）的边的平均权重。