4. 层次方法

层次聚类方法（Hierarchical Method）可以分为算法方法、概率方法和贝叶斯方法。

4.1 算法方法

算法方法包括凝聚、分裂和多阶段方法，将数据对象看作确定性的，并根据对象之间的确定性距离计算簇。

（1）凝聚与分裂的层次聚类

凝聚的方法（自底向上的方法）

将每个对象作为单独的一组，然后逐次合并相近的对象或组，直到所有的组合并为一个组（层次的最顶层），或者满足某个终止条件

AGNES（Agglomerative NESting）

分裂的方法（自顶向下的方法）

将所有对象置于一个簇中，在每次相继迭代中，一个簇被划分成更小的簇，直到最终每个对象在单独的一个簇中，或者满足某个终止条件

DIANA（Divisive ANAlysis）

（2） 多阶段聚类

1）BIRCH（Balanced Iterative Reducing and Clustering using Hierarchies）

BIRCH算法为大量数值数据聚类设计，只需要单遍扫描数据集就能进行聚类，克服了凝聚聚类方法的两个困难：可伸缩性；不能撤销先前步骤所做的工作。

BIRCH使用聚类特征树（CF-Tree，Clustering Feature-Tree）来表示聚类的层次结构，每一个节点是由若干个聚类特征组成。

聚类特征本质是给定簇的统计汇总，定义如下

其中

聚类特征线性可加，对于两个不相交的簇C 1 和C 2 ，C F 1 = < n 1 , L S 1 , S S 1 >     C F 2 = < n 2 , L S 2 , L S 2 ，合并C 1 与C 2后的簇的聚类特征是

C F 1 + C F 2 = < n 1 + n 2 , L S 1 + L S 2 , S S 1 + S S 2 >

CF-树是一颗高度平衡的树，存储了层次聚类的聚类特征。有两个参数

分支因子B：每个非叶节点的子女的最大数目

阈值参数T：存储在树的叶节点中的子簇的最大直径（CF中的所有样本点一定要在半径小于T的一个超球体内）

B=7， L=5， 内部节点最多有7个CF，而叶子节点最多有5个CF。

Birch算法的两个阶段：

扫描数据库，建立一颗存放于内存的初始CF-Tree，可以被看做数据的多层压缩。

采用某个（选定的）聚类算法对CF-Tree的叶节点进行聚类，把稀疏的簇当做离群点删除，把稠密的簇合并为更大的簇。

2）Chameleon

Chameleon是一种采用动态建模的多阶段层次聚类。

簇的相似性依据如下两点评估:簇中对象的连接情况；簇的临近性。如果两个簇的互联性都很高并且他们之间又靠得很紧就将其合并。在发现高质量的任意形状簇方面具有更强的能力。（K近邻图：选择欧式距离最近的k个点为近邻点，得到近邻图）。

4.2 概率方法

概率层次聚类旨在通过使用概率模型度量簇之间的距离。把待聚类的数据对象看做要分析的基础数据生成机制的一个样本，或生成模型（Generative model）。

聚类的任务是使用待聚类观测数据对象，尽可能准确地估计该生成模型。

一般假定该数据的生成模型采用常见的分布函数，如高斯分布或伯努利分布，它们由参数确定，学习生成模型的任务就归结为找出使模型最佳拟合观测数据集的参数值。

5. 基于密度的方法

划分和层次方法旨在发现球形簇，难以发现任意形状的簇，如下图的S形簇和椭圆形簇。

基于密度的聚类方法把簇看做数据空间中被稀疏区域分开的稠密区域，可以发现任意形状的簇。

5.1 DBSCAN

DBSCAN（Density-Based Spatial Clustering of Application with Noise）找出核心对象，通过连接核心对象和它们的邻域，形成稠密区域作为簇。

ϵ-邻域:对象o oo的ϵ \epsilonϵ-邻域是以o oo为中心，以ϵ \epsilonϵ为半径的空间。

核心对象：如果一个对象的ϵ \epsilonϵ-邻域至少包含MinPts个对象，则该对象是核心对象（core object）。

聚类任务就是使用核心对象和他的邻域形成稠密区域，可以通过密度相连的闭包来发现连通的稠密区域作为簇。

密度直接可达（directly density-reachable）:对于核心对象p 和q ，p 是从q q（关于ϵ和M i n P t s MinPtsMinPts）直接密度可达的，如果p 在q 的ϵ 邻域内。

密度可达（density-reachable）:p 是从q （关于ϵ \epsilonϵ和MinPts）密度可达的，如果存在一个对象链条，p 1 , p 2 , . . . , p n 使得p 1 = q , p n = q ，并且对于p i ∈ D ( 1 ≤ i ≤ n ), p i + 1 是从p i 关于ϵ ϵ和MinPts直接密度可达的。

密度相连（denstiy-connected）:p 是从q （关于ϵ 和MinPts）密度相连的，如果存在一个对象q ∈ D ，使得对象p 1 和p 2都是从从q（关于ϵ 和MinPts）密度可达的。

令ϵ 为给定圆的半径，MinPts=3，则m , p , o , r 都是核心对象，因为ϵ 邻域内至少包含3个对象。

对象q是从m直接密度可达的；对象m 是从p 直接密度可达的，并且象p 也是从m 直接密度可达的。

对象q 是从p 密度可达的，但p 并不是从q 密度可达，因为q不是核心对象。

o、r 、s 都是密度相连的

5.2 OPTICS

DBSCAN把选择能产生可接受的聚类结果的参数值的责任留给用户，参数的设置通常依靠经验，大多数算法对这些参数值非常敏感；此外，现实的高维数据常常具有非常倾斜的分布，全局密度参数不能很好的刻画其内在的聚类结构。

OPTICS聚类分析方法，通过点排序识别聚类结构。它并不显式地产生数据集聚类，而是输出簇排序（cluster ordering）。这个排序是所有分析对象的线性表，并且代表了数据的基于密度的聚类结构，簇排序可以用了提取基本的聚类信息（如，簇中心或任意形状的簇），导出内在的聚类结构，提供聚类的可视化。

OPTICS与DBSCAN具有相同的时间复杂度，O ( n 2 ) ；如果使用空间索引，则O ( n l o g n )

6. 基于网格的方法

• 数据驱动：划分对象集并自动适应嵌入空间的数据分布（划分方法、层次方法、基于密度的方法）。
• 空间驱动：把嵌入空间划分成独立于输入对象的分布单元（基于网格的方法）。

基于网格的聚类方法使用一种多分辨率的网格数据结构，将对象空间量化成有限数目的单元，这些单元形成了网络结构，所有聚类操作都在该结构上进行。处理时间独立于数据对象数，仅依赖于量化空间中每一维上的单元数。

6.1 STING（STaticstical INformation Grid）

STING是一种基于网格的多分辨率的聚类技术，它将输入对象的空间区域划分成矩形单元。这种多层矩形单元对应不同级别的分辨率，并且形成一个层次结构；每个高层单元被划分为多个低一层的单元。关于每个网格单元的属性的统计信息（均值、最大值和最小值）被作为统计参数预先计算和存储。

STING的聚类质量取决于网格结构最底层的粒度。如果最底层的粒度很细，则处理代价会显著增加。如果粒度趋向于0，则趋向于DBSCAN的聚类结果。STING也可以看做基于密度的聚类方法。

6.2 CLIQUE（Clustering In QUEst）

CLIQUE是一种类似Apriori的子空间聚类方法，，用于发现，用于发现子空间中的基于密度的簇。它把每个维划分成不重叠的区间，从而把数据对象的整个嵌入空间划分成单元，使用密度阈值识别稠密单元和稀疏单元，一个单元是稠密的，如果映射到它的对象数超过该密度阈值。

CLIQUE识别候选搜索空间的主要策略是使用稠密单元关于维度的单调性。

7. 聚类评估

聚类评估估计在数据集上进行聚类的可能性和被聚类方法产生的结果质量。

7.1 估计聚类趋势

数据集上的聚类分析是有意义的，仅当数据中存在非随机结构。

霍普金斯统计量（Hopkins Statistic）：给定数据集D ，可以看做随机变量o 的一个样本，需要确定o 在多大程度上不同于数据空间的均匀分布。

Step1：均匀地从D 的空间中抽取n 个点，p 1 , p 2 , . . . , p n。对于每个点p i ( 1 ≤ i ≤ n ) 在D中的最近邻，令

Step2：均匀地从D DD的空间中抽取n 个点，q 1 , q 2 , . . . , q n对于每个点q i ( 1 ≤ i ≤ n )，找出q i  在D − q i中的最近邻，令

Step3: 计算

如果D 是均匀分布的，则 与 会很接近，H 约等于0.5；当D高度倾斜时， 将显著小于 ，H 接近于0。

如果H > 0.5 ，则D 不大可能具有统计显著的簇。

7.2 确定簇数

合适的簇数可以控制适当的聚类分析粒度，在聚类分析的可压缩性与准确性之间寻找好的平衡点。

简单经验方法：对于n个点的数据集，设置簇数为

肘方法（elbow method）：使用簇内方差和关于簇数的曲线的拐点。

使用信息准则或信息论的方法

通过交叉验证确定

7.3 测定聚类质量

• 外在方法（extrinsic method）：有可用的基准，比较聚类结果和基准，监督方法。
• 内在方法（intrinsic method）：没有基准可用，考虑簇的分离情况，无监督方法。

（1）外在方法

簇的同质性（cluster homogeneity）：聚类中的簇越纯，聚类越好。

簇的完全性（cluster completeness）：（根据基准）属于相同类别的对象分配到相同的簇。

碎布袋（rag bag）：把一个异种对象放入一个纯的簇中应该比放入碎布袋中受更大的处罚。

小簇保持性（small cluster preservation）：如果小的类别在聚类中被划分成小片，则这些小片可能成为噪声，即把小类别划分成小片比将大类别划分成小片更有害。

BCubed

设D = { o 1 , o 2 , . . . , o n } 是对象的集合，C 是其中一个聚类。设L ( o i ) ( 1 ≤ i ≤ n ) 是基准确定的o i 的类别，C ( o i ) 是C 中o i 的cluster_ID。两个对象o i 和o j ( 1 ≤ i , j ≤ n , i ≠ j ) 在聚类C 中的关系的正确性。

BCube精度反映同一个簇中有多少其他对象与该对象同属一个类别：

BCube召回率反映有多少同一类别的对象被分配在相同的簇

（2）内在方法

轮廓系数（silhouette coefficient）度量数据集对象之间的相似性。

数据集D = { o 1 , o 2 , . . . , o n }被划分为k kk个簇C 1 , . . . , C k

对于每个对象o ∈ D，计算o与所属簇的其他对象之间的平均距离：

o与不属于该簇的其他对象之间的最小平均距离：

对象o 的轮廓系数:

a(o)反映o所属簇的紧凑性，b ( o )反映o 与其他簇的分离程度。

轮廓系数的值在-1和1之间，当轮廓系数的值接近于1时表明包含a ( o ) 的簇是紧凑的，并且远离其他簇。

对于一个样本集合，轮廓系数是所有样本轮廓系数的平均值。

另外一个常用评估指标为Calinski-Harabaz Index：

其中，m为样本数，k 为类别数，B k 为类别之间的协方差矩阵，W k  为类别内部数据的协方差矩阵,t r为矩阵的迹。

类别内部数据的协方差越小越好，类别之间的协方差越大越好，Calinski-Harabasz分数会越高，聚类效果越好。

与轮廓系数的对比，Calinski-Harabasz Index的计算速度要快。