【数据挖掘笔记十】聚类分析：基本概念和方法

1）

10.聚类分析：基本概念和方法

聚类这一过程旨在将数据对象集划分为若干个组或簇。每个簇内的数据对象应具有较高的相似度特征，而与其他簇中的数据对象则表现出显著的差异性特征。评估相异性和相似性时，则会涉及对这些对象属性值的距离度量。

10.1 聚类分析

通过聚类分析将一组数据对象（或观测）划分为若干子集的过程被称为分析物点分组法的一种技术手段。当采用分析物点分组法时所获得的一系列互相关联且性质相似的对象群体合称为一个物点群（即所谓的"clus-ters"）。分层分析物点群的方法不仅能够帮助我们更好地理解数据分布规**律还能为后续深入研究特异性较强的物点群体提供有依据的数据支持。此外，在特征提取、属性子集选择以及分类任务中这些方法通常被用作前期处理步骤以提高模型性能和计算效率。此外，在特征提取、属性子集选择以及分类任务中这些方法通常被用作前期处理步骤以提高模型性能和计算效率。这些方法通常被用作前期处理步骤以提高模型性能和计算效率；而该方法属于无监督学习范畴并且已被广泛应用于多个领域包括模式识别图像处理以及生物信息学等学科领域

数据挖掘对聚类的要求主要体现在以下几个方面：首先要求具有良好的扩展性，能够处理多样化属性类型；其次能够识别不论形态如何变化的簇结构；此外还需要具备一定的领域知识背景需求，并且能够有效地处理噪声数据；再者支持增量式聚类过程且不受输入顺序的影响；同时具备多维数据处理能力以及约束式聚类方法基础；最后需要兼顾明确解释性和实用性。在比较各类别划分标准时，则主要关注簇间分离度、相似度测量标准以及整体上的空间结构特征。

聚类方法的特点：

划分策略（ prototype-based methods）：该方法通过识别相互排斥且呈球形分布的簇来组织数据；数据间的相似性主要通过距离度量来表征；每个簇可通过其均值向量或中心点来表征其核心位置；该策略特别适用于处理中等规模的数据集。

层次方法：聚类作为一个多层次的结构分解，并不能纠正错误的合并或划分过程；同时该方法能够整合其他技术和考虑对象之间的联系。

3）密度方法：能够识别具有任意形状的数据簇；数据簇在数据空间中表现为被低密度区域分隔开的密集区域；每个点在其邻域内至少要有一定数量的数据点存在；通常会去除那些异常的数据点。

4）网格方法：采用一种基于多分辨率的空间划分机制进行快速处理（通常不受数据体数量的影响），然而受网格尺寸的影响。

10.2 划分方法

分类策略将数据集合划分为k个子集，并将每个子集定义为一个簇类别。同一类别的样本之间具有较高的相似度，在此过程中表现出了较强的内部一致性；而不同类别之间的样本则表现出明显的差异性。

K-均值是一种以形心为中心的方法。
k-中心点则是一种以代表对象为基础的技术，在面对噪声数据和离群体时表现更为稳健。

10.3 层次方法

层次聚类方法通过构建层次结构或簇状树来组织数据对象。这些方法可分为凝聚型和分裂型两大类，在于它们基于不同的层次分解策略进行数据划分：凝聚型方法采用自底向上的方式逐步合并数据集中的对象形成簇；而分裂型方法则采用自顶向下的方式从整体数据集开始逐步分割成更小的簇群。

层次聚类采用自底向上的方法。我们首先让所有对象各自成为单独的一个集群（cluster），然后在此基础上逐步将这些集群进行合并直至所有对象最终归于同一层（layer）。其最终形成的单一集群即为整个层次结构的基础单元。在每一次合并操作中（iteration），它通过某种相似性度量识别出两个最接近的集群（cluster）并将它们结合在一起。在每次迭代过程中（step），其中每个集群至少包含一个数据点（data point），从而使得整个凝聚过程最多需要n次迭代步骤完成。

该层次聚类算法采用自顶向下的分层策略。将所有数据样本初始化为一个单一的初始聚类节点，并将其定位为层次结构中的顶层节点。随后对该初始节点进行分裂处理，在每次分裂操作中将其划分为若干子节点；接着对每个子节点反复执行分割操作直至满足收敛条件：即当每个最终节点要么仅包含单个样本点或其所属特征空间区域中的样本点具有高度相似性为止。

凝聚方法和分裂方法的核心问题都是度量两个簇之间的距离。

基于最小距离标准定义的是最近邻聚类方法；一旦两个簇之间的最小距离达到或超过预设阈值时，则视为单连接方法；基于最小距离度量构建层次结构的方法也被视为构造生成树的一种方法。

基于最远测度的最大距离的方法被称为最远邻聚类算法。当两个簇间的最大小组间距离超过预设阈限时，该过程被定义为全连接聚类方法。

最小与最大间距体现了簇间距离度量的关键两端，在分析聚类效果时往往会对离群数据表现得过于敏感。为了缓解这一缺陷，在计算簇间关系时通常会采用平均间距作为衡量标准。

通过平衡迭代归约与聚类技术的发展，为大规模数值数据的聚类提供了有效的解决方案。这种方法成功地将层次聚合与其他主流分类方法相结合，并克服了凝聚分类在可扩展性和不可逆性方面的局限。BIRCH算法基于两阶段分类策略，在每个阶段都利用中心描述符来概括簇的状态，并通过一种称为CF-Tree的数据结构来存储这些中心描述符形成的层次结构信息。每个簇的中心描述符CF被定义为一个三维向量（Cluster Feature），它代表了该簇中对象的基本统计特性参数值总和。通过使用中心描述符CF, 我们无需保存每个对象或点的具体细节信息, 这种特性使得BIRCH算法特别适合于处理高维空间中的大数据集问题。这些CF-Tree被设计为高度严格平衡的二叉搜索树结构, 并且支持在线增量更新机制以适应动态变化的数据环境

该变色龙模型采用动态建模策略实施多层次聚类过程。该方法基于动态建模评估簇间相似度。两个评估维度包括：簇内对象间的连接程度以及各簇间的邻近程度。当两个簇间的互连程度较高且相互靠近时，则进行合并操作。这一合并机制无需依赖外部预设模型框架，能够自主适应被合并簇内部特有的特征属性。该过程通过以下步骤实现：首先基于k近邻关系构建稀疏图谱；其次通过最小化边割的方式识别并分离出较小规模的子簇；最后利用层次聚类方法将凝聚后的子簇进一步组织成更高级别的集群结构。

层次聚类算法存在以下三点不足：首先，在确定合适的距离度量方面具有挑战性；其次，在面对数据中缺失属性值时难以有效处理；第三，在每一步骤中都依赖于贪心策略逐步构建聚类结构。而概率层次聚类方法则通过引入概率模型来度量簇之间的相似性关系，并克服了上述局限性。具体而言，在该方法中将待分析的数据视为由潜在生成模型产生的样本集合，并假设数据生成过程遵循典型的分布函数（如高斯分布或伯努利分布）等特性。通过参数估计的方法确定最符合观测数据的概率模型结构。值得注意的是，在这种框架下仅能输出一个最优的概率模型树结构作为最终结果，并不能充分反映由于数据特征可能导致的不同可能的层次结构情况。

10.4 基于密度的方法

划分子类法与层次聚类法主要适用于识别具有球形特征的数据群集体，并不能有效处理具有非球形结构的数据。若希望识别更为复杂的数据分布模式，则可将数据空间中的稠密区域视为由稀疏区域分隔开的独特集合体。基于此策略发展而来的密度聚类方法能够有效识别非球状形态的空间分布群体。

DBSCAN是一种利用空间分布特征识别密集区域的数据聚类方法。它通过分析样本间的密度差异性自动识别出具有较高密度的数据群组，并将这些群组组织成有意义的簇集体。该算法的核心在于设定合理的邻域半径以及至少需要多少个样本点来定义一个密集区域。通常这些数值需通过实验验证确定。

OPTICS通过基于点排序的方法识别聚类结构，并不显式地生成数据集聚类而是输出一种簇排序该排序是对所有分析对象的一种线性排列关系它代表了基于密度的聚类结构较稠密的簇中的对象在该排序中相互靠得较近这种排序等价于从较为宽泛的参数设置中得到的基于密度的聚类结果需要两个关键参数核心距离与可达距离

DENCLUE，一种基于一组密度分布函数的聚类算法。密度估计是根据一系列观测数据集来估计不可观测的概率密度函数。在基于密度聚类的背景下，不可观测的概率密度函数是待分析的所有可能的对象的总体的真实分布。观测数据集被看做取自该总体的一个随机样本。核密度估计，非参数密度估计方法，把每个观测对象都看做是周围区域中高概率密度的一个指示器，一个点上的概率密度依赖于从该点到观测对象的距离。一个簇是一个密度吸引点的集合X和一个输入对象的集合C，使得C中的每个对象都被分配到X中的一个密度吸引点，并且每对密度吸引点之间都存在一条其密度大于阈值的路径。

10.5 基于网格的方法

依据网格的空间分布特性进行的数据分析方法，在空间分析领域具有重要地位

STING（空间数据网格），一种基于网格划分实现多分辨率聚类的空间数据挖掘技术。该技术通过规则结构将输入对象的空间区域划分为矩形单元，并采用层次化方法对这些单元进行递归细分以满足不同分辨率的需求。每个高层次单元都会映射到多个较低层次的细分单元上。该系统不仅能够有效地实现空间数据的组织与管理，并且还能通过预先计算并存储起来的一系列统计参数（如均值、最大值和最小值）来支持快速的数据查询与分析功能。

CLIQUE是一种基于密度的空间聚类方法，在某种程度上类似于Apriori算法。该算法将数据属性空间划分为互不重叠的一维区间集合，并根据预先设定的密度阈值将数据对象的空间划分为若干个单位区域；如果某个单位区域内的对象数目超过该阈值，则称其为密集区域。在确定候选搜索范围时,C LIQUE算法主要利用密集区域在各个维度上的单调特性；这种特性源于频繁模式挖掘中所依赖的经验知识。

10.6 聚类评估

该方法的核心内容包括分析数据分布趋势、识别数据集的最优聚类数目以及评估聚类效果。

聚类趋势评估旨在确定给定数据集是否存在非随机结构,这些结构可能导致有意义的聚类. Hopkins's statistic measures the spatial randomness of variable distributions within a dataset. 该评估利用Hopkins's statistic to assess whether the data distribution exhibits uniformity.

在进行聚类分析时，选择合适的簇数旨在平衡数据集的可压缩性和分类精度。确定最优簇数通常依赖于数据分布特征以及用户设定的聚类分辨率要求。通过肘方法等评估指标能够帮助判断数据集更适合分成多少个子群。一般来说，在提升数据集划分成更多子群体时（即增加数据集划分成更多子群体会减少各子群内部点与质心距离平方之和），虽然每组内部点与质心的距离平方之和略微减少但这种变化可能变得微不足道；相反地，在过多分割的情况下（当子群过细时），虽然每组内部点与质心的距离平方之和略微减少但这种变化可能变得微不足道）。因此，在实际应用中需要权衡这些因素以选择最合适的分群数量

测定聚类质量有外在方法（监督方法）和内在方法（无监督方法）。

外在方法：基于以下四项标准评估聚类质量度量Q的有效性：同一簇内的同质性、完全性、碎布袋以及小簇保持性。BCubed算法不仅满足以下四个标准，在对给定数据集进行聚类分析时还能够有效计算每个数据对象对应的精确率与召回率值。精确率衡量了同一簇中与其他对象共享相同类别标签的比例，而召回率则表示在同一类别中被正确分组到同一簇中的比例。

2）内在方法：当缺少用于比较的标准数据集时，在没有外部基准可用的情况下，默认采用内在方法对聚类质量进行评估。该方法主要通过分析簇之间的分离程度以及各簇内部的紧密程度来进行评价。具体而言，则是基于数据集中对象之间相似性的量化分析来进行判断。其计算依据正是这一度量标准。

10.7 小结

簇被称为由相同属性的数据对象组成的集合体；其中同一簇内的数据对象具有高度相似性特征；而不同簇之间的数据则表现出明显的差异性特征；将一组物理或抽象的对象按照其属性或特征进行分类的过程被称为聚类分析。

聚类分析具有广泛的应用领域，在商务智能、图像模式识别、Web搜索引擎以及生物学等学科中均有重要应用，并且在安全领域也发挥着重要作用。聚类分析既可以作为独立的数据挖掘工具使用于获取数据分布信息，并且在检测的簇上运行其他数据挖掘算法时也可作为预处理阶段使用于运行其他数据挖掘算法的必要手段

3）聚类被视为数据挖掘中的一个重要且充满活力的领域，并与机器学习中的无监督学习技术紧密相连。

该方法具备良好的扩展性和广泛的应用潜力；它能够支持多种类型的数据处理；该算法特别擅长识别复杂形状的簇结构；同时该系统仅需有限量的领域先验知识即可运行；此外该方案还具有对噪声数据具有鲁棒性的能力；同时支持增量聚类过程；不受输入顺序影响；能够有效处理高维空间中的数据特征；允许在聚类过程中施加特定约束条件；并且其结果具有良好的解释性和应用价值

5）聚类方法基于划分标准等特征进行分类；簇之间的分离性影响分类效果；采用不同的相似性度量来衡量数据点之间的相似程度；聚类空间决定了算法在不同区域的表现；这些聚类方法主要包括划分法（如K-means）、层次法（如CURE）、密度法（如DBSCAN）和网格法（如STING）。

划分方法首先生成k个初始分区（initial partitions），其中参数k表示要构建的分区数量。随后运用迭代 relocation 技术（iterative relocation technique），旨在通过将对象从一个簇迁移到另一个簇来优化分区的质量（cluster quality）。常见的划分方法有K-Means, K-Medoids以及CLARANS算法。

7. 该层次方法用于构建给定数据对象集的层次分解结构。基于生成层次分解的方式不同, 层次方法主要可分为凝聚型(自底向上)和分裂型(自顶向下)两类。为了弥补合并或分裂过程中存在的僵硬性问题, 凝聚型层次方法可以通过以下途径来改善其聚类质量: 首先对每个层级中的对象连接关系进行深入分析(例如Chameleon算法), 或者采取分阶段策略, 即先将数据划分为小规模的微簇(Micro-clusters), 然后再应用其他聚类技术进行迭代优化, 在这些微簇基础上重新构建聚类结果(例如BIRCH算法)。

该方法通过概念化的方式实现数据聚类。
其依据包括邻域内样本的局部密度（如DBSCAN算法）以及自定义的核函数（如DENCLUE方法）来构建数据簇。
OPTICS算法是一种基于概念化方法的数据聚类技术，在其框架下形成的有序数据集能够逐步揭示潜在的模式结构。

9）通过基於栅格的方法将对象空间划分为有限数量的栅格单元并构建栅格架构，在栅格架构上执行数据分组和分类过程。
STING 是一种典型 的基於栅格划分方 法的例子；该算法 通过存储 在每个栅 格单元内 的统计数据来进行 数据分组和分类。
Clique 则 是一种針對 子空間進行 分群 的栅 核式架构 方法。

10）通过执行对数据集的聚类分析来估计其可行性，并对由所选聚类方法生成的结果质量进行评价。具体而言，在该任务中需要完成三项核心工作：一是通过分析数据分布特征识别潜在的分类趋势；二是根据数据特征确定最优的簇数量；三是量化评估不同划分标准下的分类效果。