【数据挖掘笔记十一】高级聚类分析

11.高级聚类分析

11.1 基于概率模型的聚类

研究一个对象属于多个簇的聚类主题。

1）模糊簇

模糊集S是整体对象集X的一个子集，允许X中的每个对象都具有一个属于S的0到1之间的隶属度。给定对象的集合，一个簇就是对象的一个模糊集，这种簇就是模糊簇，一个聚类包含多个模糊簇。模糊聚类就是划分模糊簇的过程。对象隶属于模糊簇的隶属度，可以用对象与其被指派到的簇的中心之间的距离或相似度来衡量。由于一个对象可能参与多个簇，用隶属度加权的到簇中心的距离之和捕获对象拟合聚类的程度。误差平方和SSE可用来度量模糊聚类对数据集的拟合程度。模糊聚类也称为软聚类，允许一个对象属于多个簇，和传统的硬聚类强制每个对象互斥地仅属于一个簇不同。

2）基于概率模型的聚类

聚类分析的主要目标是识别潜在类别。
被视为聚类分析主题的数据集即为潜在类别可能具有的代表性实例集合。
通过聚类分析生成的簇群能够估计潜在类别。

从统计学角度来看，在数据空间中隐含的类别可被视为一个分布模型。该模型能够准确地描述这些特征，并被定义为概率簇。给定一个概率簇C，在其密度函数下属于数据空间中的每个实例o而言（即每个实例o属于数据空间中的一个点），f(o)表示的是该实例在C中出现的可能性大小。假设这些潜在的概率分布在某个已知的概率分布族中存在，并通过观测到的数据集（即观测到的数据）来推断出这些潜在的概率分布参数值。当存在多个这样的潜在的概率簇时，则意味着观察到的数据集是由这些不同的潜在的概率分布所生成的结果集合所构成。给定观测到的数据集D以及所需的聚类数目k（即所需划分成多少个群），基于某种概率模型来进行聚类分析的目标则是推导出最可能产生该观测到的数据集D的一组k个潜在的概率簇模型

数据生成的过程中, 每个观测样本都各自独立地经历两个阶段的生成: 首先, 在所有可能的簇集合中依据其概率分布随机选择一个簇; 然后, 根据选定簇所对应的概率密度函数进行采样以获得具体的数据点。

通过概率模型实现聚类等价于确定k个簇的概率密度函数参数。假设数据服从高斯分布，则需要计算各个簇的均值和方差。

3）期望最大化算法

基于概率模型的聚类以及模糊聚类都依赖于EM算法。可以将EM算法视为一种框架，在此框架下近似求解统计模型参数的最大似然或最大后验估计问题。当处理模糊分类问题或者基于概率模型的分类任务时，在初始参数集合的基础上应用EM算法进行迭代操作；当该过程无法进一步提升分类效果或者变化量小于设定阈值时，则认为该过程达到了收敛状态。

模糊聚类或基于概率模型的聚类的EM步骤：

第一：期望步，根据当前的模糊聚类或概率簇的参数，把对象指派到簇中；

在第二阶段的最大化步骤中, 识别新的聚类或参数, 并寻求使模糊聚类SSE达到最大值及其概率模型下聚类结果的最大可能性.

基于概率模型进行聚类分析，在选择合适的统计模型时需注意以识别潜在的簇结构。在应用Expectation-Maximization（EM）算法时，请注意其未必能达到全局最优解，并可能出现陷入局部最大值的情况。为了避免这种问题，在实际应用中常见做法包括采用不同的随机初始值以及反复运行EM过程寻找更好的结果。此外，在面对复杂的数据分布或者样本数量有限的情况下，请特别注意考虑计算开销的问题。

11.2 聚类高维数据

在高维数据空间中，基于传统方法的距离测量往往容易受到各个维度噪声的影响。与基于低维空间的传统聚类方法不同，在高维数据空间中发现的簇通常规模较小，并且构建适合于高 dimensional 数据聚类的有效模型应作为首要任务。

1）子空间聚类方法

该方法旨在探索不同子空间以实现聚类任务。在这些子空间内定义的一组对象称为簇，在此过程中这些对象彼此之间具有较高的相似度。计算这些对象之间的相似程度通常采用基于距离或其他度量标准的方法。

以相关性为基础的聚类方法中包含例如通过主成分析（PCA）提取一组相互独立的新维度。
随后，在这个新空间及其子空间中进行数据聚类。
此外，在处理图像特征时还可用到霍夫变换或者分形维度分析法等技术手段。

2）双聚类方法

双聚类技术在生物信息学领域及推荐系统中展现出广泛的应用前景。作为一种同时对数据对象及其属性进行聚类的技术，在实际应用中我们发现其结果形成一种称为双簇的特殊结构特征。这种结构特征主要表现为以下几个方面：其结果通常仅涉及少量样本集合属于同一簇；每个簇通常仅与少数属性相关联；每个样本对象可能同时归属于多个簇或者根本不参与任何簇；而每个属性也可能被多个簇所共享或者根本不被任何簇包含。基于此，在含有噪声的数据环境中识别出这种复杂的双层组织架构主要有两种主要途径：第一种基于最优化的方法通过迭代搜索机制寻找最优解，在每次迭代过程中都会筛选出当前具有最高显著性得分的最大子矩阵作为候选双簇单元直至满足用户设定的具体终止条件为止；由于这种方法往往面临较高的计算开销因此在实际操作中多采用贪心搜索策略以获得局部最优解并最终确定最终结果；这种贪心搜索算法中的代表方案是δ-簇算法；第二种基于枚举策略时会设定容错阈值来限制对噪声数据的敏感度并试图穷尽所有满足容错条件下的潜在候选双簇子矩阵集合最终筛选出最优方案；其中具有代表性的算法就是MaPle算法。

3）维归约方法和谱聚类

聚类高维数据的维归约方法是建立一个新的子空间而非依赖于原有数据空间。

谱聚类法基于这一核心概念，在数据处理过程中首先构建与数据样本之间相似度的矩阵；随后对生成的相似矩阵进行特征值和特征向量的计算；提取具有最大特征值的前k个主成分；接着将这些主成分作为新的低维空间中的坐标点进行分组；最后将聚类结果映射回原始的数据空间中以分析其分布情况。

11.3 聚类图和网络数据

通过在图与网络数据中实施聚类分析来获取具有重要价值的知识与信息。这些图与网络数据实例表明：它们提供了对象（顶点）以及它们之间的联系（边）。然而，在这些结构中缺乏明确的维度与属性定义。由于缺乏对维度与属性的明确定义，在此类结构上实施聚类分析面临着相似性度量与有效聚类模型设计的巨大挑战。

相似性度量采用测地距和基于随机游走的距离。

测地距离：图中两节点之间距离的一种简便衡量标准是两节点之间的最短路径长度。具体而言，在图中任意两节点间的测地距离等于它们之间最短路径所包含的边的数量。

2）SimRank算法基于随机游走及其所处的结构环境中的相似性。其轨迹是由一系列连续的随机移动组成的路径集合。在结构环境下两个节点之间相似性的直观体现是：当且仅当它们连接到具有相同或类似性质的其他节点时（即共享较多的质量邻居）。

图聚类即通过将图分割成多个片段来实现对数据进行组织与分类。每个分割后的片段即为一个簇体，在此过程中各簇内部顶点之间具有良好的连接性。而不同簇体之间的顶点则以较弱的方式相连。其中，
一个"割"定义为将一个完整的无向连通网络进行划分的过程，
其对应的"割集"即被切分出来的边集合，
而"割之大小"则由该边集合所包含的所有边的数量决定。
对于带权重网络而言，
其"大小"则等于相应边权重之和。
寻找最优稀疏割的问题在实际应用中面临计算资源消耗高昂、复杂网络结构以及数据维度较高和稀疏特性等挑战。
解决这一问题的方法可分为两类：
一类基于传统的聚类算法处理高维数据；
另一大类方法则专注于针对特定类型网络设计专门算法。

11.4 具有约束的聚类

聚类分析包括三个方面：具体来说，则涉及三个方面：第一是数据点或样本作为簇实例的对象；第二是将这些对象群定义为簇；第三则是衡量不同对象之间相似程度的标准。这些分析中所包含的限制条件则分为三种类型：第一种是作用于单个实例的限制条件；第二种是针对整个簇集合施加的限制条件；第三种则是用于衡量不同对象之间相似程度的标准。

实例上的约束包括：必须联系约束和不能联系约束。

簇上的约束使用簇的睡醒，说明对簇的要求。

相似性度量上的约束说明相似性计算必须遵守的要求。

具有约束的聚类方法，包括处理硬性约束和处理软性约束两种。

处理硬性约束的策略是，在聚类的指派过程中，严格遵守约束。

基于软性约束条件下的聚类被视为一个优化问题。每当出现违反软性约束的情况时，在受影响的数据集中施加惩罚。为了实现这一目标，我们定义了一个总目标函数，它整合了提高数据集内部相似度以及减少违背硬性限制的影响的程度。

11.5 小结

传统上，在进行聚类分析时（原文中的主语可能不够明确），每个数据点被严格地分配到单个簇中。
然而，在许多实际应用场景下（替代了"在很多应用中"），通常会采用模糊方法或概率模型来分配数据点至多个簇中的其中一个或多个。
模糊聚类算法以及基于概率模型的方法能够支持数据点同时归属于多个不同的簇群体。
为了衡量每个数据点与各个簇之间的关联程度（补充说明），划分矩阵被用来计算数据点对各个簇的隶属度值。

该聚类方法假设每个簇遵循一个参数化分布。通过将待处理的数据视为观测样本集合，我们可以推断出各个簇的参数。

3）基于观测对象属于多个概率分布类的前提假设下，在概念层面上说来，则每个观测对象都是独立生成的过程：首先被分配到某个特定的概率分布类中，并随后从该特定的概率密度函数中抽取样本。

4）期望最大化（EM）算法是一种框架性方法，在其运行过程中会逼近最大似然估计或统计模型参数的后验概率估计值。该算法不仅可以用于计算某些模糊聚类方法以及基于概率模型的聚类分析等任务。

5）面对聚类分析而言，在处理具有多个维度特征的数据时会遇到诸多难题。具体而言，则需要解决从大量特征中提取有效信息并构建相应的模型问题。此外，在实际应用中还需要探索有效的降维方法以提升算法效率与结果准确性。

在高维数据聚类中，主要采用两种策略：一是基于子空间的方法与二是基于降维的技术。其中包含但不限于以下几种具体实现方式：一是基于子空间搜索、二是基于相关性分析以及协同聚类技术。另外一种策略则是通过降维技术构建更低维度的空间模型，在此模型中进行数据分组。

7）双聚类方法能够一起对研究对象及其属性进行分析与分类。根据其特征表现形式，双簇可分为具有恒定值（constant）、行列恒定值（constant across rows/columns）、独立值（independent）以及随时间变化的独立值（time-dependent independent）等类型。其主要应用分为两类：一类是基于优化算法的方法（optimization-based），另一类是系统性枚举所有可能组合的枚举法（enumerative approach）。

8）谱聚类是一种维归约方法。其一般思想是使用相似矩阵构建新维。

9）聚类图及其网络数据在多个领域有广泛应用，在例如社会网络分析等场景中表现突出。这些挑战主要体现在如何衡量图内节点间的相似程度以及为图结构和网络数据开发有效的聚类方法等方面。

测地距离代表图中两个顶点之间最短路径上的边数。在社会网络这类图中，节点间的相似程度能够基于结构情境和随机游走的方法来评估。SimRank算法是一种基于结构情境与随机游走的技术来计算节点间相似性的方法。

图聚类等同于计算图割的结果。在图论中，最稀疏的割对应于最佳的聚类划分；此外，在网络分析中使用模块性指标来评估聚类的质量。

12）SCAN是一种图聚类算法，它搜索图，识别良连通的成分作为簇。

在具体应用丢聚类分析时，可以通过设定特定的约束来表征其要求或背景知识。这些聚类约束主要可以从三个层面进行划分：即实例层面、簇层面以及相似性度量层面的限制条件。其中，在实例层面的限制通常包括两种类型：一种是强制要求两个实例必须归为同一类别（必须联系约束），另一种则是禁止两个实例被归入同一类别（不能联系约束）。这些限制条件既可以表现为硬性要求（硬性约束），也可以表现为具有灵活性的条件（软性约束）。

14）硬性约束可以在聚类指派过程中通过严格遵守约束条件来强制执行。相比而言，在处理软性约束时需要解决一个优化问题，并且可以借助启发式算法来显著提高计算效率。