国科大数据挖掘期末复习——聚类分析

聚类分析

将物理或抽象对象的集合进行分组以形成由相似的对象组成的多个类的过程被称为聚类。通过聚类生成的一组数据对象集合中包含彼此相似的对象，并且与其他集合中的对象相异。

聚类归类为无监督学习（unsupervised learning），即它不受预设的类别标签和训练数据集的限制。因此，在这种情况下，聚类算法主要通过对数据特征分析来完成任务的学习过程。而传统有监督学习则是基于已标记的数据进行建模和分类的任务。

数据挖掘对聚类的典型要求如下：

• 扩展性
• 处理不同属性类型的能力
• 识别具有任意形状的聚类结构
• 减少对领域知识的需求
• 处理噪声数据的能力
• 不受输入记录顺序的影响
• 高维空间中的聚类方法
• 基于约束条件的聚类方法
• 强调可解释性和可用性的方法

聚类分析中的数据类型

• 数据矩阵（Data matrix）：用p个变量来表现n个对象，（n 个对象*p 个属性）的矩阵

• 相异度矩阵（dissimilarity matrix）：记录n个对象之间两两的距离，并表现为一个n×n维的矩阵。其中d(i,j)用作衡量对象i与j之间相异性程度的度量工具。通常用非负数值来表示这种相异性程度：当两个对象越相似时（即i和j越接近），d(i,j)会趋近于零；相反地，在两个极端不同的情况下（即i与j差异显著时），d(i,j)则会呈现出较大的正值。
• d(i,j)用作衡量对象i与j之间相异性程度的度量工具。

区间标度（Interval-Scaled）变量

为了使度量值标准化, 可以采用将原始度量值归一化处理的方法。对于任意变量 f , 其度量值可通过以下方式归一化处理:

这里的 x1f,…,xnf 是 f 的 n 个度量值，mf 是 f 的平均值

在对数据进行了标准化处理后（进行了标准化处理），接下来需要计算各对象之间的差异度（相异度），其中的对象间差异程度则依据各对象间距离进行计算。

欧几里得距离（Euclidean distance） ：

曼哈顿距离（Manhattan distance） ：

以上两种距离度量方法均满足：

d(i,j)≥0,两个点之间的最小相似度指标值是非负数
d(i,i)=0,每个样本与其自身间的相似度指标值均为零
d(i,j)=* d(j,i),相似度指标函数满足对称性要求
d(i,j)≤* d(i,h)+* d(h,j),任意两点间的最小相似度指标不会超过通过中间点*h的距离之和

明考斯基距离（ Minkowski distance ）代表了欧几里得距离与曼哈顿距离的综合体现

q=1就是曼哈顿距离，q=2就是欧几里得距离

二元变量（binary variable）

一个二元变量只有两个状态：0 或 1，0 表示该变量为空，1 表示该变量存在。

如何计算二元变量的相似度呢？

假设所有二元变量具有相同的权重，则我们构建了一个2×2的可能性表格。在表格中：

• a表示对象i和j均取值为1的变量数量；
• b表示在对象i中取值为1而在对象j中取值为0的变量数量；
• c表示在对象i中取值为0而在对象j中取值为1的变量数量；
• d表示两者均为0时对应的变量数量。
  其中p等于a加b加c加d。

对称的二元变量和不对称的二元变量之间的区别是什么？

如果它的两个状态有相同的权重, 那么该二元变量是对称的，也就是两个取值 0 或 1 没有优先权。如果两个状态的输出不是同样重要，那么该二元变量是不对称的。例

对称的二元变量距离测量：

非对称二元变量的距离测量：

d(jack,mary)=(0+1)/(2+0+1)=0.33

d(jack,jim)=(1+1)/(1+1+1)=0.67

d(jim,mary)=(1+2)/(1+1+2)=0.75

这表明jim和mary不太可能患上相同类型的疾病，在他们的病历中记录了三个病例，并且jack和mary之间存在最大的差异性。

标称变量

标称变量是二元变量的推广，它可以具有多于两个的状态值。

如何计算标称变量所描述的对象之间的相异度？

这里的p是全部变量的数目，m是匹配数目（i和j取值相同的变量数目）

序数型变量

一个离散型顺序变量与标称变量在本质上相似，在于它们都具有有限的状态数目；然而，在这种情况下存在显著区别：顺序变量的状态是有序排列的，并且其值能够表示为顺序关系。

如何计算序数型变量所描述的对象之间的相异度？

通过将变量xif映射到相应的rif中（其中 rif ∈ {1,…,Mf}），实现对相应变量值的替代。
将所有变量的取值范围标准化至[0.0, 1.0]区间内以确保各变量具有相同的影响力。
经过计算后即可获得所需的结果。

比例标度型变量

如何计算用比例标度型变量描述的对象之间的相异度？

使用与处理区间标度变量相同的策略。然而这种方法通常不被视为理想的选择因为它可能导致量表的尺度发生偏移

对比例标度型变量进行对数变换

• 将 xif 看作连续的序数型数据，将其值作为区间标度的值来对待

后两种方法比较有效

混合型的变量

大多数真实存在的数据库通常会将对象表示为多种数据类型的综合。一般而言，在一个数据库系统中可能会同时支持包括以下六种基本数据类型：区间尺度测量、对称二元测量、非对称二元测量、命名类别、顺序量表以及比率量表。

那么，我们怎样计算用混合类型变量描述的对象之间的相异度？

该方法通过整合所有变量实现一次性聚类操作。该技术将不同类型的变量整合至单一相异性矩阵，并将其标准化为统一的数值范围[0.0, 1.0]。

待解

主要聚类方法的分类

划分方法（partitioning methods）：

给定一个包含 n 个对象或元组的数据集，在应用一种划分子系统地将数据划分为 k 个子集的情况下，默认情况下每个子集代表一个聚类（其中 k 的值不超过 n）。换句话说，在这种情况下它通过分组的方式将数据组织成 k 个类别，并且这些类别需要满足以下具体要求：

（1）每个组至少包含一个对象；

（2）每个对象必须属于且只属于一个组。

• k-means算法：每个簇由该簇中所有对象的均值来表示。
  • k-medoids算法：每个簇由与聚类中心最接近的一个实例来表示。

层级方法（hierarchical methods）通过层层划分的方式对给定数据集合进行分析与处理。这些层级方法具体来说，则根据这些层级如何形成而被划分为凝聚型或分裂型两大类。其中凝聚型方法通常采用自底向上的策略，在初始阶段将每个数据实例独立放置在一个小组别中，并通过不断聚合相近或相似的小组别直至最后只剩下一个大组别；而分裂型方法则采用自顶向下的策略，在初始阶段将所有数据实例整合到同一个簇中，并通过逐步分割实现最终对每个数据实例独立成组的目标；在上述两种主要分类的基础上还可能引入其他分类标准以进一步优化结果；同时为了满足不同场景的需求还可以设计多种不同的聚类策略；此外在实际应用过程中还需要考虑计算效率以及结果解释性等多个关键指标以确保算法的有效性和实用性

大多数划分方法主要依据对象间的距离来进行聚类操作；然而这些方法仅能识别具有规则形状的数据簇；随后又提出了一种新的聚类策略；该策略的核心理念在于：若某一邻域区域内所包含的对象或数据点数量达到预设阈值，则认为该区域属于同一类别；对于同一类别内的任一数据点，在指定范围内至少应包含一定数量的对象或数据点；这种技术有助于有效去除噪声数据并揭示更为复杂的簇结构

基于网格的方式：通过将对象空间划分为有限数量的单元格形成了一种分格布局。所有聚类操作均在该分格布局下执行。这种方法的优势在于其运算效率显著提高，并且其处理时间仅取决于每个维度上的分格数目。

基于模型的方法：每个簇都假设了一个特定的分布类型。该方法将数据样本分配到最佳匹配的那个簇中。通常会使用密度函数来估计每个簇的概率分布参数。该算法能够根据样本数据自动生成合适的聚类数量，并且能够自动识别噪声数据和其他孤立点，并因此生成稳健（robust）的分组结果。

划分方法（partitioning methos）

k-means算法

输入：簇的数目k和包含n个对象的数据库

输出：k个簇，使平方误差最小

• 随机选择n个样本作为初始质心
  repeat
  基于与当前质心的距离
  将所有样本分配至最近的质心所属簇
  计算并更新各簇的所有样本均值作为新的质心位置
  until 系统收敛为止

缺点：

• 仅当簇的中心或平均值得以明确说明时才可应用
• 必须预先确定参数k的具体数值
• 该算法无法有效处理含有噪声的数据集以及含有异常值的数据
• 该方法不适用于识别具有非凸边界形状的簇群或者处理大小悬殊的簇类问题

k-methods算法

此方法优化了k-means算法对异常值的敏感性。该算法不再以簇内所有对象的平均值作为基准点,而是选择位于簇中最中心的对象——medoid。该划分方式仍遵循基于所有对象与其对应基准点之间差异总和最小化的原则进行操作。

• 在每个簇中随机选取一个具有代表性的事物
• 其余的事物按照与其对应参考事物的距离远近程度归并至邻近的一组
• 通过将非核心事物（即位于各组中心附近的个体）取代原有的参考事物来进行优化处理

层次方法（Hierarchical Methods）

一个层次的聚类方法会将数据对象组织成一种层级式的树状结构。基于其分解方向是自底向上还是自顶向下进行划分后,层次聚类的方法还可以进一步区分为基于凝聚型（Agglomerative）或分裂型（Divisive）的操作步骤

一种纯粹的层次聚合法在应用过程中会受到以下局限性的影响：一旦发生一次合并或分割操作，就无法进行必要的修正。

这种自顶向下的策略最初将每个样本独立成一个簇，并随后将这些基本单元不断合并成逐渐扩大化的簇。此过程将持续进行直至所有样本归于同一个簇或特定终止条件达成。绝大多数层次聚类方法都遵循这一基本模式，在区分不同类别时它们的主要区别在于如何定义不同簇之间的相似性。

* 使用单链路和不相似矩阵
* 逐个合并差异度最小的节点

分裂层次聚类算法：该算法基于上层结构的方法与凝聚层次聚类方法不同，在其运行过程中最初将所有数据样本归为一个整体群集；随后逐步分割为越来越小的子群集；这一过程持续直至每个样本独立成群并满足特定终止条件；具体而言，在本算法中终止条件可能包括达到预设的最大类别数量或最小距离阈值等

* 恰恰与凝聚相反，逐渐分裂

BIRCH

它克服了凝聚聚类方法的两个困难：

• 可伸缩性
• 不能撤销先前所做的工作

BIRCH 通过聚类特征来概括一个簇，并采用聚类特征树(CF-树)来表示聚类的层次组织结构。

我们关注的是由n个d维空间中的数据点或对象组成的簇。其聚类特征（Clustering Feature缩写为CF）是一个三维向量的具体信息进行汇总与描述。具体而言, CF作为一个三维向量,包括三个基本参数:数目参数、均值向量以及方差信息三者

CF-树是一个高度平衡的树，它存储了层次聚类的聚类特征。

• 树中的每个非叶节点都具有后代，并称为"子节点"。
  • 每个非叶节点存储了其所有子节点CF值的总和。
  • 该模型包含两个关键参数：
    • 分支因子B：表示每个内部节点最多可拥有的子节点数量。
    • 阈值T：决定了叶子节点中子簇的最大直径。

BIRCH采用了多层次聚类技术：通过一次完整的数据集扫描就能获得良好效果，并通过一到多次额外扫描进一步优化聚类质量。该方法主要包含两个主要阶段：基于插入的层次化聚类方法配合初始数据点分布分析以及伴随进行的数据集平衡生长过程以维持树状结构的合理性

BIRCH算法会对数据库进行遍历扫描，并在内存中预先构建一个初始CF-树（即聚类树），这棵CF-树可视为数据多层次压缩的形式，在保留原有数据内在聚类结构的同时实现高效管理。
将对象插入到最近的叶条目（子簇）中。
如果插入操作完成后发现存储在叶子节点中的子簇直径超过预设阈值，则对该叶子节点以及可能存在的其他相关节点进行分裂处理。

BIRCH基于一种（特定的一种）聚类算法对CF树的叶节点进行聚类分析，并通过识别密度较低的数据区域将其作为离群数据予以剔除；而对于密度较高的区域，则将其进一步整合形成更大的数据集。

CURE

CURE采用了基于介于质心法与代表对象法之间的中间策略的新层次聚类方法。该算法并不使用单一质心或单独对象来表示一个簇，并是从数据空间中选取一定数量的有代表性的关键点来进行处理。

• 多个关键样本点能够通过CURE方法识别出任意形状的簇
• 不明显受离群数据的影响
• 在大型数据库系统中通常需要执行抽样处理并按特征划分区域

CURE算法核心：

• 从源数据对象中选取一个随机抽样 S
  • 将样本 S 分成若干块
  • 对各个分割后的区域执行局部聚类
  • 通过随机抽样去除孤立点；若某一群体生长速度缓慢，则将其移除
  • 对各个分割后的簇进行进一步的聚类分析
  • 并为每个数据点分配相应的簇标签

基于密度的方法（Density-Based Clustering Methods ）

该系统旨在识别任意形状的聚类结构，并提出了一种基于密度的新方法。这种方法将数据簇视为由低密度区域分隔开的高密度对象集合。

主要特点：

• 发现任意形状的团簇
• 消除噪声
• 需要密度参数作为终止条件
• 复杂度为O(n2)

两个参数：

• ε–邻域
• 最小数目 MinPts

当一个对象的ε–邻域满足不小于MinPts个的对象时，则称该对象为核心对象。

设有一个实体集合 D，在其中若 p 位于 q 的 ε-邻域内且 q 被认定为核心实体，则我们称实体 p 通过 q 实现了基于密度的直接可达性

假设存在一个对象链 P_1,P_2,\dots,P_n ，其中第一个节点 P_1 等于 Q ，最后一个节点 P_n 等于 P 。对于所有 i \in \{1,\dots,n\} 的节点 P_i \in D ，下一个节点 P_{i+1} 直接由 P_i 关于参数 \varepsilon 和 \text{MinPts} 达到密度连接，则目标点 P 通过参数 \varepsilon 和 \text{MinPts} 与源点 Q 密度相连。

如果对象集合 D 中有对象 o ，因为对象 p 和 q 是从 o 据据 \varepsilon 和 \text{MinPts} 密度可达的，则 p and q are density-connected with respect to \varepsilon and \text{MinPts}

DBSCAN算法

输入：

• D：一个包含n个对象的数据集
• ε：半径参数
• MinPts：邻域密度阈值

输出：基于密度的簇集合

基于网格的方法（Grid-Based Clustering Method ）

该聚类方法采用了多层次的空间划分技术。该技术将研究区域划分为有限数量的小区域，并通过层次化的空间划分构建了一个多分辨率的数据结构。这种设置使得所有的聚类操作都可以在统一的空间框架下完成。该方法的主要优势在于运行速度极快，并且其显著特点在于运行时间与数据量无关；其运行时间仅取决于每个维度方向上的划分数量以及层次深度等参数设置。

• STING：该算法通过网格单元内的统计信息实现了数据聚类。
• WaveCluster：该方法采用小波变换技术对数据进行分组。
• CLIQUE：该算法基于网格划分和密度概念，在高维数据空间中执行聚类操作。

STING(STatistical INformation Grid)

• 空间区域按照矩形网格划分
• 在较高层次的空间单元中设置较低层次的细分单元
• 对于每个网格单元属性特征进行统计信息预存：
  • 包括以下关键指标：
    • 计数项（count）
    • 平均指标（average value）
    • 标准差数值（standard deviation）
    • 极小数值（minimum value）
    • 极大数值（maximum value）
    • 分布类型（正态分布、均匀分布及无序分布类型）

根据对应低层单元多数的分布类型进行判断后，并通过设定一个阈值过滤标准来进行判断

统计查询方法 ：

• 采用自顶向下的策略来处理空间数据查询问题
• 从预设的一个图层起点出发，并基于有限单元格数量开始分析
• 对于每个待分析的空间单元体估算其置信区间范围
• 去除与分析目标无关的空间单元块以简化后续计算
• 处理完当前层次后逐步深入至相关子区域进行详细分析
• 重复上述步骤直至达到最底层的空间特征数据为止

特点 ：

• 当STING构建父单元时，并未考虑子单元与其相邻单元之间的相互关系。
• 其形成的区域呈现isothetic形态特征，在所有聚类边界中要么水平分布要么垂直排列。
• 该算法具有较高的效率：STING通过单次数据库扫描获取各单元统计信息。
• 由此产生的聚类时间复杂度为O(n)，其中n表示对象总数。
• 在层次结构建立完成后进行查询处理的时间复杂度为O(g)，其中g代表底层网格划分的数量。
• 基于网格划分的方法计算过程与查询无关。
• 这种网格架构便于并行计算以及实时更新。

孤立点分析（Outlier Analysis）

孤立点是什么？

常见存在一批数据对象不遵循一般的数据模式此类数据被称作离群点这些离群点与其他部分明显不同或存在不一致之处离群点可能由测量错误或操作错误引起值得注意的是这些离群点往往具有重要意义

目测方法：

基于统计的孤立点检测

统计方法对给定的数据集合构建了一个概率模型（如正态分布），随后通过不一致检验（discordancy test）识别孤立点。该检验基于数据集参数（如假设的概率分布）、分布参数（如均值和方差）以及预设的孤立点数量。

不一致性检测依赖于：

• 数据分布
• 两个假设
• 分布参数（如平均值，方差）
• 预期异常值的数量

缺点：

• 最大限度地来说,大多数检验工作都是专注于单个属性,而许多数据分析问题则要求能够在多维空间中识别孤立点。
• 统计方法需要对于数据集参数的知识,例如如数据分布情况等信息。
• 该算法需要接受参数设置

基于距离的孤立点检测

如果数据集合 S 中至少有 p 比例的对象与对象 o 的距离超过 d，则称对象 o 为基于距离的具有参数 p 和 d 的孤立点 DB(p,d)。换言之，在无需统计检验的情况下我们将基于距离的孤立点视为那些缺乏足够邻居的对象这里的邻居依据给定对象的距离来定义即依据给定对象的距离来确定相邻关系。相较于基于统计的方法而言基于距离的孤立点探测整合了多个标准分布不一致性的检验思路从而减少了计算量因为大量的计算通常是导致观察到分布适合某个标准分布并选择不一致性检验所必需的前提条件。

基于索引的算法 ：

给定一个数据集，在基于索引的方法中通常采用多维索引结构如R-tree或k-d树来进行范围查询以获取每个对象o在其指定半径d范围内的邻居。其中M定义为在d邻域内孤立点的最大对象数量。因此一旦某对象o检测到其邻居超过M个时就可判定该对象o为孤立点。

该算法在最坏情况下的时间复杂度为 O(k·n²)，其中 k 代表维数维度而 n 则表示数据集合中的对象数量。

缺点：在计算复杂度评估时仅局限于搜索时间这一方面，在估算时，并未考虑到构建索引这一本身就是一个计算密集型的任务。

基于单元的算法 ：

为了规避O(n²)的时间代价, 人们构建了基于单元的算法以处理存在于内存中的数据集合. 这种算法的总复杂度可表示为O(ck + n), 其中c代表与单元数量相关的常数, 而k表示维度.

• 将数据空间划分为网格单元，在每个划分中设置两个同心保护结构
  • 每个网格单元周围设置有两层保护结构
    • 第一层保护结构的厚度相当于一个网格单元的高度
    • 第二层保护结构的厚度为（2k₁）½减去一个单位长度

异常值检测：

• 在第一层的计算结果超过阈值M时，则表明该单元格内没有异常值。
• 当第二层的结果小于或等于阈值M时，则说明所有对象均为异常值。
• 反之，则需进一步检查该单元格内的每一个具体对象。

基于偏差的孤立点检测

该系统通过识别一组对象的关键属性来判定孤立点。与预期不符的对象被视为孤立点。

序列异常技术：通过从一组推测相似的对象中识别出不寻常的对象来模拟人类的异常识别机制

该算法通过从集合中选择一个子集合的序列来进行分析。对于每一个这样的子集合而言，在其内部计算并衡量其与序列中前一个相应位置上所对应的另一个子集之间的差异程度。