数据挖掘课程复习

用于HITSZ 25春数据挖掘复习

概述

数据挖掘的含义

数据挖掘是从海量数据集中发现有趣的（非平凡的、隐含的、未被发现但有用的）模式、模型或知识的过程。

数据挖掘过程

知识发现的过程：
1. 数据预处理
1. 数据清洗
2. 数据集成
3. 数据选择
4. 数据变换
2. 数据挖掘
3. 模式/模型评估
4. 知识表示

数据挖掘的应用

数据分析与决策支持
- 客户画像、需求分析
- 交叉市场分析
风险分析与管理
- 竞争分析
- 风险评估
- 资产管理
- 资源规划
欺诈检测与异常模式挖掘
- 医疗、电信等

数据仓库

定义：数据仓库是面向主题的、集成的、随时间变化的、又相对稳定的数据集合，它支持管理层的决策过程
数据仓库的关键特征：

面向主题的：
- 数据仓库的数据是以分析的主题为中心构建的
集成的：
- 数据仓库的数据来自不同的数据源，需要按照统一的结构、格式、度量、语义进行数据处理，最后集成到数据仓库的主题
随时间变化的：
- 数据仓库的历史数据，需要随时间延长而增加（周期性更新）
- 数据仓库的综合数据，需要随时间延长而变化
相对稳定的：
- 数据仓库的数据主要用于支持决策，不会涉及频繁的修改与变化，主要是查询与分析。

数据特征分析与预处理

数据类型及其特征

记录：以「行 - 列」形式组织，含结构化和半结构化形态。
- 例如：关系表、数值矩阵、文本词频、交易项目集合
图和网络：由「节点（实体）+ 边（关系）」构成拓扑结构，聚焦实体间关联。
- 例如：如网页链接、社交关系、分子键
有序的：数据带时间/序列顺序，侧重“顺序依赖”与规律。
- 例如：视频帧的先后、时间序列趋势、交易/遗传序列的顺序
空间/图像/多媒体：含空间维度或多媒体形态，分析空间分布/内容特征。
- 例如：地图坐标、图像像素矩阵、视频帧序列

数据对象：

数据集由数据对象构成，数据对象又称之为样本、实例。

属性类型

定义：一个数据字段，表示一个数据对象的某个特征

分类：

标称属性: 与名称相关的值、分类或枚举属性 (定性的)
- 二元属性: 标称属性的一种特殊情况，只有2个状态的标称属性。
序数属性: 值有一个有意义的顺序 (定性的)
数值属性: 可度量的量 (定量的)
- 区间标度属性:
  - 在统一度量的尺度下
  - 值有序（e.g. 日历日期，温度计数据）
  - 没有固有0点
- 比率标度属性：
  - 具有固有零点，可以说一个值是一个值得多少倍
  - 举例：字数、体重、工作年限

数据的描述统计

数据离散特征： 均值、众数、最值、分位数、方差、离群点……
排序区间：
- 数据离散度：多个粒度上得分析
- 排序区间得盆图/分位数图分析

描述统计的图形显示： 箱型图、直方图、分位数图、散点图

数据可视化方法

数据可视化方法得分类：

基于像素的可视化技术
- 协方差矩阵的热力图
基于几何投影的可视化技术
- 直接可视化、散点图、透视地形、平行坐标
基于图标的可视化技术
- 脸谱图、人物画像图
基于分层的可视化技术
- 树状图、锥形树
可视化复杂数据与关系
- 标签云、线形图、饼图、结构图/流程图、怪图、系统进化图

测量数据的相似性和相异性

相似性： 度量数据的相似程度，越大越相似，通常范围在 [0,1]
相异性： (e.g. distance)，度量数据的差异，最小值通常为0 ，越大差异越大

相异度矩阵： 对角线为0的下三角矩阵，元素为对应对象之间的距离相异度矩阵矩阵

标称属性的邻近度量

得分匹配：

$$d(i,j) = \frac{p - m}{p}$$

其中 m 为相同变量数量，p 为变量总数。
独热编码：
具体而言即将名称或类别转化为独热编码，随后利用编码计算距离

二进制属性的度量

对称二元变量距离： $d(i,j) = \frac{r+s}{q+r+s+t}$

不对称二元变量距离： $d(i,j) = \frac{r+s}{q+r+s}$

Jaccard系数(不对称二元变量相似性)： $Sim_{Jaccard}(i,j) = \frac{q}{q+r+s}$

TIP: 解释一下这个对称的含义，关键在于0是否有意义对称的含义解释

例题：二进制属性的非对称相异性度量

数值属性的度量

闵可夫斯基距离公式：

$$D(X, Y) = \left( \sum_{i=1}^n |x_i - y_i|^p \right)^{\frac{1}{p}}$$

其中 p ≥ 1，是可调节的距离参数。

主要使用上述公式度量，其中有一些特例可以参照下图：闵可夫斯基距离公式特例

区间尺度与有序变量的度量

区间尺度：进行归一化或标准化处理随后计算闵可夫斯基距离
有序变量：使用排序代替值，并对排序值做最值归一化，随后计算闵可夫斯基距离

其他度量方法：

余弦相似度：

$$ \text{cos}(\theta) = \frac{\sum_{i=1}^{n} A_i B_i}{\sqrt{\sum_{i=1}^{n} A_i^2} \cdot \sqrt{\sum_{i=1}^{n} B_i^2}} $$

用于衡量两个向量方向的相似程度，常用于文本分类、推荐系统等。

KL 散度（Kullback-Leibler Divergence）：

$$ D_{KL}(P \parallel Q) = \sum_{i=1}^{n} p_i \log \frac{p_i}{q_i} $$

衡量两个概率分布之间的差异，常用于模型分布与目标分布之间的对比。

数据预处理

目的： 数据存在不完全、噪音、不一致的问题，高质量的数据挖掘依赖高质量的数据

数据预处理的主要任务：

数据清理： 异常值、缺失值、噪音
- 针对缺失值：删除整个样本、均值或聚类填充
- 针对异常值与噪音：通过分箱、聚类、回归去除
数据集成： 多个来源合到一起
数据变换： 归一化等操作
数据归约： 减小数据的冗余
- 维度规约：减少无用特征，或产生新的特征代替原来的
  - 决策树规约、PCA
- 数值规约：减小数据量，例如用模型参数+离群点代替原始数据
  - 线性回归、聚类
- 数据压缩
数据离散化和概念分层：
- 连续变量离散化
- 人为指定偏序关系

关联规则

关联规则挖掘概念

一种从事务数据集中发现项与项之间有趣关系的技术，形式为：

X ⇒ Y, X ∩ Y = ∅

支持度（Support）：

$$ \text{Support}(X \Rightarrow Y) = \frac{\text{包含 } X \cup Y \text{ 的事务数}}{\text{总事务数}} $$

置信度（Confidence）：

$$ \text{Confidence}(X \Rightarrow Y) = \frac{\text{Support}(X \cup Y)}{\text{Support}(X)} = P(Y|X) $$

提升度（Lift）：

$$ \text{Lift}(X \Rightarrow Y) =\frac{\text{Confidence}(X \Rightarrow Y)}{\text{Support}(Y)} = \frac{P(Y|X)}{P(Y)} $$

Lift > 1 表示正相关，=1 表示独立，<1 表示负相关。

频繁项集与其分类

频繁项集：

如果一个项集 X 的支持度满足：

Support(X) ≥ min_sup

则 X 是频繁项集。

闭频繁项集（Closed）：

项集 X 是闭的，当不存在一个超集 Y ⊃ X，使得：

Support(Y) = Support(X)

极大频繁项集（Maximal）：

项集 X 是极大的，当不存在一个超集 Y ⊃ X 是频繁的。

三者关系：

极大频繁项集 ⊆ 闭频繁项集 ⊆ 所有频繁项集；
闭项集压缩信息不丢失，极大项集压缩更彻底但不保留精确支持度。

关联规则基本模型

关联规则是指同时满足最小支持度和最小置信度阈值的规则，形式如下：

X ⇒ Y, X ∩ Y = ∅

挖掘流程：

找出所有频繁项集（满足 Support ≥ min_sup）；
从频繁项集中生成所有满足 Confidence ≥ min_conf 的规则。

只有同时满足这两个条件的规则，才被称为“强规则”。

📌 Apriori算法流程

Apriori 是一种经典的频繁项集挖掘算法，用于从大量事务数据中发现频繁项集和生成关联规则。

核心思想：Apriori原理

如果一个项集是频繁的，那么它的所有子集也一定是频繁的。

也就是说，如果某个项集不是频繁的，则其所有超集都不可能是频繁的，因此可以在搜索中直接剪枝，提升效率。

算法计算流程

步骤 1️⃣：扫描数据库，找出频繁 1 项集（L₁）

统计每个单项的支持度；
过滤出支持度 ≥ min_sup 的项；
得到频繁 1 项集集合 L₁。

步骤 2️⃣：由 L₁ 构造候选 2 项集（C₂）

连接步骤：将 L₁ 中的项两两组合生成 2 项候选项集；
剪枝步骤：剔除那些包含非频繁子集的候选项集；
重新扫描数据库统计每个候选项集的支持度；
保留支持度 ≥ min_sup 的项集，得到频繁 2 项集 L₂。

步骤 3️⃣：迭代构造更高阶项集 L₃、L₄…

从 L₂ 生成 C₃，再从中提取 L₃；
重复 连接-剪枝-计数 的过程；
直到某一轮没有产生新的频繁项集。

步骤 4️⃣：由频繁项集生成关联规则

对每个频繁项集 L，枚举其所有非空子集 S；
构造规则 S ⇒ (L−S)；
计算置信度（Confidence）：

$$ \text{Confidence}(S \Rightarrow T) = \frac{\text{Support}(S \cup T)}{\text{Support}(S)} $$

只保留满足 Confidence ≥ min_conf 的规则。

提高 Apriori 算法效率的方法

Apriori 算法在面对大规模数据时效率较低，以下是常用的几种优化策略：

Hash-based itemset counting（基于哈希的项集计数）
- 将候选项集映射到哈希桶中；
- 如果某个哈希桶中的计数低于最小支持度，则其对应的项集可直接剪枝；
- 作用：减少无效候选项集数量。
Transaction reduction（事务压缩）
- 每轮扫描后，删除不包含任何频繁项集的事务；
- 后续迭代无需再扫描这些事务；
- 作用：减少数据扫描量，提高效率。
Partitioning（划分策略）
- 将数据库划分为多个子集，分别挖掘局部频繁项集；
- 将局部频繁项集合并，再在全库中验证；
- 只需两次完整扫描，适合大数据和并行处理。
Sampling（采样）
- 从数据库中随机抽取部分事务作为样本；
- 在样本上挖掘频繁项集，再用全体数据验证；
- 优点：快速；缺点：可能漏掉边缘频繁项集。

关联规则的度量

除了上述说到的支持度、置信度、提升度以外，还有一些度量方式。这里主要是四种零不变性度量。

在关联规则中，某些度量值不受零事务（null transactions）影响，称为零不变性度量。

零事务：不包含任何待考察项集的事务；
零不变性：度量值只由 P(A|B) 和 P(B|A) 决定，与总事务数无关；

以下四种度量具有零不变性，且其值范围都在 [0,1]，值越大表示 A 与 B 的关联越紧密。

全置信度 $$ \text{all_confidence}(A, B) = \frac{\text{sup}(A \cup B)}{\max(\text{sup}(A), \text{sup}(B))} = \min(P(A|B), P(B|A)) $$
最大置信度 max_confidence(A,B) = max (P(A|B),P(B|A))
余弦置信度
$$ \text{cosine}(A, B) = \frac{P(A \cap B)}{\sqrt{P(A) \cdot P(B)}} = \sqrt{P(B|A) \cdot P(A|B)} $$
Kelu置信度
$$ \text{Kulc}(A, B) = \frac{1}{2} \left( P(A|B) + P(B|A) \right) $$

分类

模型评估方法

留出法：按照比例随机划分出训练集和测试集，多次随机抽样取均值
交叉验证：把数据划分为k份，每次选择一份作为测试集，重复k次，取均值
- 留一法：每份仅有一个样本
Bootstrap 自助法: 又放回的抽样m次作为训练集，没有被抽到的作为测试集

分类模型评估指标

混淆矩阵（Confusion Matrix）

实际/预测	正类（预测）	负类（预测）
正类（实际）	TP（真正例）	FN（假负例）
负类（实际）	FP（假正例）	TN（真负例）

TP：预测为正，实际为正
FP：预测为正，实际为负
FN：预测为负，实际为正
TN：预测为负，实际为负

指标：

准确率

$$ \text{Accuracy} = \frac{TP + TN}{TP + FP + FN + TN} $$

召回率

$$ \text{Recall} = \frac{TP}{TP + FN} $$

精确率

$$ \text{Precision} = \frac{TP}{TP + FP} $$

F1-Score

$$ \text{F1} = \frac{2 \cdot \text{Precision} \cdot \text{Recall}}{\text{Precision} + \text{Recall}} $$

F-beta

$$ \text{F1} = \frac{(1+\beta^2) \cdot \text{Precision} \cdot \text{Recall}}{\beta^2 \cdot \text{Precision} + \text{Recall}} $$

P-R 曲线（Precision-Recall Curve）
- 横轴：Recall（召回率）
- 纵轴：Precision（精确率）
- 通过不断调整分类阈值，绘制出一系列 (P, R) 点，形成一条曲线
ROC 曲线（Receiver Operating Characteristic）
- 横轴：FPR（假正率） = $\frac{FP}{FP + TN}$
- 纵轴：TPR（真正率） = 召回率 = $\frac{TP}{TP + FN}$
- 曲线下的面积（AUC）越接近 1，模型越好

🛠️ 决策树归纳算法的流程（以 ID3/C4.5/CART 为例）

输入训练集 D，每条样本有多个属性 + 类别标签。
判断停止条件：
- 样本全属于一个类别 → 生成叶节点，停止；
- 属性已用完，或样本不足 → 用多数类别作为叶节点标记。
选择最优划分属性 A：
- 使用某种划分指标（如信息增益、增益率、基尼指数）选择属性 A；
- 若无可用属性 → 直接创建叶节点。
按属性 A 的取值划分数据集：
- 对每个取值 a_i，将数据集划分为 D_i；
- 为每个子集创建分支子节点。
对子节点递归重复上述过程：
- 在子集 D_i 上继续构建子树。
形成整棵决策树：
- 直到所有子集都满足停止条件。

属性选择度量

有三种，分别为信息增益、增益率、基尼系数

信息增益（Information Gain）

信息增益是 ID3 算法使用的度量标准，它衡量的是：使用某个属性 A 对数据进行划分后，系统信息熵（混乱度）减少了多少。

公式：

$$ \text{Gain}(D, A) = Ent(D) - \sum_{v \in \text{Values}(A)} \frac{|D_v|}{|D|} \cdot Ent(D_v) $$

其中 $Ent(D) = -\sum_{i=1}^{m}p_i \text{log}_2 (p_i)$ 是原始数据集的熵；
D_v 表示属性 A 取值为 v 的子集；
值越大表示“划分后不确定性下降得越多”，越适合作为划分属性。

缺点：偏向于选择取值多的属性（比如身份证号），容易过拟合。

增益率（Gain Ratio）

为了解决信息增益偏好多值属性的问题，C4.5 算法引入了增益率：

$$ \text{GainRatio}(D, A) = \frac{\text{Gain}(D, A)}{IV(A)} $$

IV(A) 是 A 的“固有值信息”或“分裂信息”，可以理解为划分的复杂度。 $$ IV(A) = - \sum_{j=1}^{v}\frac{|D_j|}{D} \text{log}_2(\frac{|D_j|}{D}) $$
增益率在衡量信息增益的同时，惩罚属性值过多的划分，更加平衡。

基尼指数（Gini Index）

CART 算法采用基尼指数来衡量属性划分的纯净程度。基尼指数越小，表示子集越“纯”。

某个集合 D 的基尼指数定义为：

$$ \begin{align} Gini(D) &= 1 - \sum_{k=1}^{K} p_k^2 \\ Gini_{split}(D) &= \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2) \end{align} $$

p_k 表示属于第 k 类的概率；
当样本全属于一个类别时，Gini = 0；
每次选择能最小化划分后加权 Gini 的属性作为最优划分属性。

✅ 总结对比：

度量方式	使用算法	优点	缺点
信息增益	ID3	简单直观，计算熵有理论基础	偏向多值属性，可能过拟合
增益率	C4.5	纠正信息增益偏差，权衡复杂度	偏向取值较均匀的属性
基尼指数	CART	计算更快，适合二叉树构建	没有熵那样的理论解释

常见分类方法的主要思想

朴素贝叶斯分类（Naive Bayes Classification）

朴素贝叶斯是一种基于贝叶斯定理并假设属性之间相互条件独立的概率分类方法。

给定训练数据集 D，每个样本表示为一个 n 维属性向量：
X = (x₁,x₂,...,x_n)
假设总共有 m 个类别：C₁, C₂, ..., C_m
目标是确定输入 X 属于哪个类别，即计算后验概率最大的类别： Ĉ = arg max_{C_i}P(C_i∣X)
根据贝叶斯定理： $$ P(C_i \mid X) = \frac{P(C_i) \cdot P(X \mid C_i)}{P(X)} $$
因为 P(X) 对所有类别都相同，所以在分类时只需最大化分子部分： Ĉ = arg max_{C_i}P(C_i) ⋅ P(X∣C_i)
若假设特征条件独立，则有： $$ P(X \mid C_i) = \prod_{k=1}^{n} P(x_k \mid C_i) $$

Laplacian Correction（拉普拉斯校准）

为了解决0概率问题，引入 Laplacian 平滑（也叫 Add-One Smoothing），公式调整为：

$$ P(x_k \mid C_i) = \frac{N_{ik} + 1}{N_i + d} $$

N_ik：类别 C_i 中属性 A_k 取值为 x_k 的样本数
N_i：类别 C_i 的总样本数
d：属性 A_k 的可能取值数（即类别数）

这样，即使某个值从未出现（N_ik = 0），加 1 后也不会导致整个概率为 0。

KNN 分类（K-Nearest Neighbors）

KNN（K 近邻）是一种基于实例的非参数分类方法，核心思想是： “相似样本具有相似的类别。”

基本流程：

给定一个待分类样本，计算它与训练集中所有样本之间的距离（如欧几里得距离）；
选出距离最近的 K 个“邻居”；
让这些邻居“投票”，投票最多的类别即为预测结果。

逻辑回归（Logistic Regression）

逻辑回归是一种用于二分类任务的线性模型，其本质是学习一个函数，输出属于某一类别的概率。

基本思想：

给定输入特征 X = (x₁,x₂,...,x_n)，逻辑回归学习一个线性组合：

z = w^Tx + b
然后通过Sigmoid 函数将其映射到 [0,1] 范围，作为正类的概率：

$$ P(y = 1 \mid x) = \frac{1}{1 + e^{-z}} = \frac{1}{1 + e^{-(w^T x + b)}} $$
预测时，通常设置阈值 0.5，若 P ≥ 0.5 则预测为正类，否则为负类。
没有闭合解，通常使用梯度下架配合交叉熵损失求解（在训练数据上拟合）

神经网络

跳过

支持向量机（SVM）分类

支持向量机是一种二分类模型，通过寻找一个最佳分割超平面，将不同类别的数据点分开。

核心思想：

寻找一个最大间隔（Margin）的超平面，使得距离超平面最近的样本点（支持向量）距离最大化；
最大间隔有助于提高模型的泛化能力。

线性可分情况：

给定训练样本，SVM 找到一个线性超平面满足：

w^Tx + b = 0
并满足分类约束：

y_i(w^Tx_i+b) ≥ 1, i = 1, 2, …, n
目标是最大化间隔，即最小化 ∥w∥²。

线性不可分情况：

使用软间隔（Soft Margin），允许一定程度的分类错误，加入松弛变量 ξ_i；
目标函数变为：

$$ \min_{w,b} \frac{1}{2}\|w\|^2 + C \sum_{i=1}^n \xi_i $$
其中 C 控制误差惩罚强度。

非线性分类：

通过核函数（Kernel），将数据映射到高维空间，使其线性可分；
常用核函数包括：
- 线性核：K(x,z) = x^Tz
- 多项式核：K(x,z) = (x^Tz+c)^d
- 径向基函数核（RBF）：K(x,z) = exp (−γ∥x−z∥²)

集成方法（Ensemble Methods）

集成方法是将多个弱分类器组合成一个强分类器的技术，旨在提高模型的准确性和稳定性。

基本思想：

通过结合多个模型的预测结果，减少单个模型的偏差和方差；
常见方式包括投票（分类）或平均（回归）。

主要类型：

Bagging（Bootstrap Aggregating）
- 通过自助采样（有放回抽样）构建多个训练子集，训练多个模型；
- 预测时对多个模型结果投票或平均；
- 代表算法：随机森林（Random Forest）。
Boosting
- 逐步训练一系列弱分类器，每个分类器关注前一个分类器错误分类的样本；
- 通过加权组合提升整体性能；
- 代表算法：AdaBoost、Gradient Boosting、XGBoost。
Stacking（堆叠）
- 训练多个不同类型的基模型；
- 使用另一个模型（元学习器）学习如何组合基模型的输出。

聚类

聚类分析：将数据对象分为多个类或簇，类内对象相似，类间对象相异

基于划分的聚类方法

构造n个对象数据集D的划分，将其划分为k个列（所以需要给定K值的是基于划分方法的）

K-平均聚类算法

步骤：

选择一个含有随机选择样本的k个簇的初始划分，计算这些簇的质心
根据欧氏距离把剩余的每个样本分配到距离它最近的簇质心的划分
计算被分配到每个簇的样本的均值向量，作为新的簇的质心
重复2,3直到k个簇的质心点不再发生变化或平方误差准则最小
- 这里平方误差是说每个簇内样本到中心的平方误差的总和的总和

优点: - 相对有效性，复杂度为 O(knt)，其中 n 是对象数目, k 是簇数目, t 是迭代次数

缺点： - 需要预先指顶簇的数目k, - 不能处理噪音数据和孤立点(outliers) - 不适合用来发现具有非凸形状(non-convex shapes)的簇

K-中心点聚类算法

主要用于解决K-均值在异常值上的缺点

k-中心点算法流程: 1. 任意选取 k 个点作为中心点

按照与中心点最近的原则，将剩余点分配到当前最佳的中心点代表的类中
在每一类中，计算每个成员点对应的准则函数，选取准则函数最小时对应的点作为新的中心点
重复2-3的过程，直到所有的中心点点不再发生变化，或已达到设定的最大迭代次数

其中准则函数为，一类中，某个成员点和其他成员点的距离之和

优点： 当存在噪音和孤立点时, K-medoids 比 K-means 更健壮。 缺点： K-medoids 对于小数据集工作得很好, 但不能很好地用于大数据集，计算质心的步骤时间复杂度是O(n²)，运行速度较慢

PAM算法

是最早提出的k-中心点聚类算法

PAM算法流程：
1. 首先随机选择k个对象作为中心，把每个对象分配给离它最近的中心。
2. 对每个Medoid和非Medoid点(O(k(n−k)))，尝试交换它们的位置，计算新的聚类代价(O(n−k))。
3. 如果总的损失减少，则交换中心对象和非中心对象；如果总的损失增加，则不进行交换

优点： 当存在噪音和孤立点时, K-medoids 比 K-means 更健壮；
缺点： 同K-medoids，每轮复杂度O(k(n−k)²)

CLARA算法

不考虑整个数据集, 而是选择数据的一小部分作为样本

CLARA算法流程：
1. 从数据集中抽取一个样本集, 并对样本集使用PAM，划分为k个簇
2. 将其他未被抽到的样本划分到上述确定的簇中
3. 重复上述步骤，选择最好的聚类作为输出

优点: 可以处理的数据集比 PAM大

缺点: - 有效性依赖于样本集的大小 - 基于样本的好的聚类并不一定是整个数据集的好的聚类, 样本可能发生倾斜

CLARANS算法

输入参数：

数据集 D，样本个数 n
聚类数 k
每轮最大尝试次数 max_neighbor
总共执行的局部搜索次数 num_local

多次随机局部搜索（共执行 `num_local` 次）：

对于每次局部搜索：

随机选择初始的 k 个 Medoids
当前 Medoids 作为初始解，循环尝试邻居（即交换一个 Medoid 和一个非 Medoid）：
- 随机选择一个非 Medoid 点，与当前某个 Medoid 交换，得到一个“邻居解”
- 计算这个新解的聚类代价
- 如果代价降低，则更新当前解为这个新解
重复上述步骤，直到连续 max_neighbor 次尝试都没有找到更优解
记录该局部搜索中最好的解

最终输出：

在 num_local 次局部搜索中，选择代价最低的那个作为最终聚类结果

基于层次的聚类方法

层次的聚类方法将数据对象组成一棵聚类的树,可以进一步分为: - 凝聚的(agglomerative)层次聚类 (自底向上形成) - 分裂的(divisive)层次聚类 (自顶向下形成)

AGNES (Agglomerative Nesting)算法

算法流程：

初始化：计算包含每对样本间距离（如欧氏距离）的相似矩阵，把每个样本作为一个簇；
选择：使用相似矩阵查找最相似的两个簇；
- 两个簇间的相似度由这两个不同簇中距离最近的数据点对的相似度来确定－－单链接方法(Single-link)
更新：
- 将两个簇合并为一个簇，簇的个数通过合并被更新；
- 同时更新相似矩阵，将两个簇的两行（两列）距离用1行（1列）距离替换反映合并操作
重复：执行n-1次选择与更新；
结束：当所有样本都合并成一个簇或满足某个终止条件时，整个过程结束

DIANA (Divisive Analysis)算法

主要思想：采用自顶向下策略

首先将所有样本置于一个簇中；
然后逐渐细分为越来越小的簇，来增加簇的数目；
直到每个样本自成一个簇，或者达到某个终结条件。
例如达到了某个希望的簇的数目或两个最近的簇之间的距离超过了某个阈值。

BIRCH算法流程

BIRCH 是一种基于层次结构的聚类算法，适合大规模数据，使用 CF-Tree 来压缩数据并高效聚类。

关键数据结构：CF（Clustering Feature）

每个聚类用三元组表示：

CF = (N,LS,SS)

N：簇中点数
$\mathbf{LS} = \sum_{i=1}^N \mathbf{x}_i$（点坐标线性和）
$\mathbf{SS} = \sum_{i=1}^N \mathbf{x}_i^2$（点坐标平方和）

利用 CF 可快速计算簇的质心、半径和直径，无需访问原始点。

CF-Tree 结构

一种平衡树，类似 B+ 树
非叶节点存储子节点的 CF 信息
叶子节点存储实际的 CF 条目，每个 CF 表示一个子簇
叶子节点通过链表相连，支持顺序访问
主要参数：
- B：非叶节点最大子节点数
- L：叶子节点最大 CF 条目数
- 阈值 T：限制每个 CF 最大半径

算法流程

初始化：设定阈值 T、B、L，初始化空 CF-Tree。
逐点插入：
- 从根节点开始递归，找到距离点最近的叶子节点 CF。
- 尝试将点合并入该 CF，若合并后半径 ≤ T，更新 CF；否则新建 CF 条目。
节点分裂：
- 叶子节点 CF 条目数超过 L 时分裂：
  - 选择两个最远的 CF 条目作为种子，重新分配其余 CF 条目。
  - 生成两个叶子节点，更新父节点。
- 父节点子节点数超过 B 时递归分裂，直到根节点。
完成构建。
全局聚类（可选）：对叶子节点所有 CF 的质心进行聚类（如 K-Means）(在每个叶子节点的簇的层面再聚类)。

算法优缺点

优点：
- 只需一次扫描，速度快
- 数据压缩存储，节省内存
- 支持增量更新和大规模数据
缺点：
- 对异常点敏感
- 结果依赖阈值 T 选取

CURE算法简介（含抽样处理）

核心思想

用多个代表点描述簇的形状，避免用质心造成的误差
代表点收缩至簇中心以减少异常点影响
支持复杂簇结构，抗噪声能力强

算法流程

抽样（Sampling）
- 从大数据中随机抽取一个代表样本子集，减小计算量
初始聚类
- 对抽样数据，每个点看作一个簇，或者先用快速算法做粗聚类，得到初始簇集合
选择代表点
- 每个簇选固定数量的代表点（如距离簇质心较远的点）
收缩代表点
- 将代表点沿向簇中心的方向收缩一定比例（如20%-30%）
合并簇
- 计算簇间代表点的最小距离，合并距离最近的两个簇
重复步骤 3-5
- 直到满足聚类数或者其他停止条件
增量聚类（可选）
- 对未抽样的数据，将每个点分配到最近的簇中，实现全量数据聚类

特点

抽样减少计算量
代表点和收缩减少异常点影响
能处理非球形簇，结构复杂

ROCK 算法简介

ROCK（Robust Clustering using linKs）是一种基于邻居“链接”关系的层次聚类算法，特别适合处理类别数据和非球形簇。

关键概念

邻居（Neighbors）
如果两个数据点之间的相似度（例如 Jaccard 相似度）超过某个阈值 θ，则认为它们是邻居。
链接数（Link）
两个点的链接数是它们共同邻居的数量。链接数越大，说明两点越有可能属于同一个簇。
Jaccard 相似度
衡量两个集合相似度的指标，定义为它们交集的大小除以并集的大小，用来计算点之间的相似性。
好处度（Goodness Measure）
用于评估合并两个簇的合理性。
计算公式为：

$$ Goodness(C_i, C_j) = \frac{links(C_i, C_j)}{(size(C_i) + size(C_j))^{1 + 2f(\theta)} - size(C_i)^{1 + 2f(\theta)} - size(C_j)^{1 + 2f(\theta)}} $$

其中：
- links(C_i,C_j) 是两个簇间所有点对的链接数之和
- size(C) 是簇中点的数量
- f(θ) 是阈值相关的函数，用于调节合并力度

算法流程

计算邻居关系
- 对数据集中每对数据点计算相似度（如 Jaccard 相似度）。
- 如果相似度大于阈值 θ，则认为它们是邻居。
计算链接数
- 对每对数据点，统计它们共同邻居的数量，这个数量称为“链接数”。
初始化簇
- 将每个数据点作为一个单独的簇。
计算簇间好处度
- 根据簇间所有点对的链接数以及簇大小，计算两个簇合并的好处度（Goodness Measure）。
合并簇
- 选择好处度最高的两个簇进行合并。
重复合并
- 不断重复计算好处度和合并操作，直到达到预定的簇数或满足其他终止条件。

特点

适合类别数据和非球形簇
利用邻居链接捕捉复杂的结构关系
计算量较大，适合中小规模数据

CHAMELEON算法

CHAMELEON是一种基于图的层次聚类算法，能够自动发现不同形状和密度的簇，适用于复杂数据结构。它结合了动态模型和多阶段聚类，利用簇的内部连接性和相似性来决定合并策略。

核心思想

利用k-近邻图（k-NN Graph）表示数据点间的关系
通过度量簇间的相对连通性（Relative Connectivity）和相对相似性（Relative Closeness），决定簇是否合并
动态调整合并过程，适应簇的形状和密度差异

主要概念

k-近邻图
构建一个图，点为数据样本，边连接每个点的k个最近邻，边权反映点之间的相似度
相对连通性（Relative Connectivity, RC）
衡量两个簇间连接强度相对于它们内部连接的强度
相对相似性（Relative Closeness, RCl）
衡量两个簇之间的距离相对于它们各自的内部距离

算法流程

构建k-近邻图
- 计算数据点间的相似度，构造加权k-近邻图
初始聚类
- 使用图划分方法（如基于最小割的聚类）将数据划分成多个细粒度的小簇
计算簇间相似度
- 对每对簇计算相对连通性（RC）和相对相似性（RCl）
动态合并簇
- 根据RC和RCl的综合评价，选择合适的簇对进行合并
重复合并
- 直到满足预设的簇数或没有合适的簇对可以合并

特点

适应不同簇形状和密度
结合了局部结构和全局信息
适合处理复杂数据集，但计算复杂度较高

基于密度的聚类方法

密度的概念

1. ε-邻域（Epsilon Neighborhood）

给定一个点 p，其 ε-邻域 是所有与点 p 距离不超过 ε 的点的集合。
通俗地说，就是以点 p 为圆心，半径为 ε 的“圆”里有谁。

2. 核心对象（Core Object）

如果一个点的 ε-邻域内至少包含 MinPts（最小点数，包括它自己）个点，则称它为核心对象。
它说明该区域“密度足够大”。

3. 直接密度可达（Directly Density-Reachable, DDR）

如果点 p 在点 q 的 ε-邻域内，且 q 是核心对象，那么我们说：
点 p 是从点 q 直接密度可达的。
注意：只有从核心对象出发，才能有“直接密度可达”。

4. 密度可达（Density-Reachable）

如果存在一条由多个点组成的链 p₁, p₂, ..., p_n，使得：
- p₁ = q，p_n = p；
- 对于每对相邻点 p_i 和 p_i + 1，都有 p_i + 1 是从 p_i 直接密度可达的；
那么我们说：点 p 是从点 q 密度可达的。

这个关系是单向的：即 p 从 q 可达，不代表 q 从 p 可达。

5. 密度相连（Density-Connected）

如果存在某个点 o，使得：
- 点 p 和点 q 都是从 o 密度可达的；
那么我们说：点 p 和点 q 是密度相连的。

这个关系是对称的，用于判断是否属于同一个簇。

示例

DBSCAN算法

核心参数

ε（eps）：定义点的“邻域”范围
MinPts：最小邻居点数，决定一个点是否为“核心点”

算法流程

初始化状态
所有数据点标记为“未访问”。
从一个未访问点 p 开始：
- 计算 p 的 ε-邻域（记为 N_ε(p)）；
- 如果邻域内的点数 < MinPts：将 p 标记为噪声，跳过；
- 否则，将 p 作为核心点，创建一个新簇，将 N_ε(p) 中的所有点加入该簇。
扩展当前簇：
对刚加入簇的每个点 q（若未访问）执行：
- 标记 q 为已访问；
- 若 q 是核心点（其邻域内点数 ≥ MinPts）：
  - 将 N_ε(q) 中的所有点加入当前簇（即密度可达）；
- 否则（q 是边界点），保留在当前簇中，不继续扩展。
重复步骤 2~3
- 直到所有点都被访问。

DBSCAN 的输出

若干个簇（每个由核心点及其密度可达的点组成）
一些噪声点（不属于任何簇）

优点

不需要预先指定簇数
可发现任意形状的簇
可识别噪声点
对离群点不敏感

缺点

需要合适的 ε 和 MinPts
当数据密度差异较大时效果较差
高维数据中，距离不再可靠（维数灾难）

OPTICS算法

OPTICS（Ordering Points To Identify the Clustering Structure）是一种基于密度的聚类算法，解决了 DBSCAN 对参数敏感的问题。它不仅能发现不同密度的簇，还能输出数据的聚类结构排序，方便后续分析。

算法流程

初始化
- 给数据集中每个点设置状态为“未访问”。
- 给每个点设置可达距离 reachability_dist = ∞（表示未知）。
- 准备一个空的“输出顺序列表”（ordering），用于记录访问点的顺序。
遍历所有点
对数据集中的每个点 p：
- 如果 p 已经被访问过，跳过；
- 否则，开始处理 p：
访问点 p
- 将 p 标记为“已访问”。
- 计算 p 的核心距离 core_dist(p)：
  - 找出 p 的 ε-邻域中的所有点，排序后取第 MinPts 个最近邻点的距离作为核心距离。
  - 如果邻域内点数不足 MinPts，则 p 不是核心点，核心距离未定义。
- 把 p 加入输出顺序列表（ordering），此时 p 的可达距离保持为当前值（初始可能为无穷大）。
如果 p 是核心点
- 取 p 的 ε-邻域内所有未访问的点，放入一个优先队列（或类似结构），根据可达距离排序（距离越小优先）。
- 对这些邻居点 o：
  - 计算从 p 到 o 的可达距离：
    reachability_dist(o) = max (core_dist(p),dist(p,o))
  - 如果 o 当前的可达距离大于这个新值，则更新 o 的可达距离为新值，并将 o 加入优先队列。
- 依次从优先队列中取出可达距离最小的点 q，重复步骤 3 和 4，直到优先队列空。
继续处理剩余点
- 返回步骤 2，处理下一个未访问的点，直到所有点都被访问。

结果输出

一条有序的点列表，反映数据的密度聚类结构。
通过绘制 可达距离图（Reachability Plot），可以直观观察不同密度簇的分布和边界。

优点

不需要像 DBSCAN 那样对 ε 选取非常敏感。
能发现不同密度的簇。
输出的可达距离序列方便后续聚类分析。

基于网格的聚类方法

STING算法

STING 是一种基于网格（Grid-based）的聚类方法，通过将空间划分为不同层次的网格结构，并基于每个网格单元中的统计信息来进行聚类判断。

核心思想

将数据空间预先划分成多个固定大小的单元格（网格）。
构建一个多层次的网格索引结构（层次树），每一层网格的粒度逐渐增大（上层粒度粗，下层粒度细）。
每个网格单元保存统计信息，如：
- 对象数（count）
- 平均值（mean）
- 方差（variance）
- 最小值、最大值等

算法流程

构建网格结构
- 划分空间：将数据空间划分为若干固定大小的单元格。
- 构建多层结构，每层是上一层的粗粒度抽象。
统计每个单元格的属性
- 在数据预处理阶段，统计每个单元格内的数据统计量，并自底向上传递到上层节点（汇总统计）。
选择合适的层次作为分析起点
- 通常选择中间层开始，粒度适中，既不太粗也不太细。
过滤和合并网格单元
- 对目标查询区域内的单元格：
  - 如果统计指标满足某些条件（如密度高），则进一步下钻到下一层；
  - 否则停止，或直接排除该区域；
- 递归进行，直到达到最低层或不能再分。
输出聚类区域
- 最终，在最底层（最细的网格）里，把满足“高密度”的小单元格合并在一起，作为一个簇。
- 类似地，另一个位置的网格也可能形成另一个簇。

通俗例子

假设我们有一个二维空间，数据分布如下：

在左上角有一堆密集点
在右下角又有一堆密集点
其它区域是稀疏的

STING 做法：

初步划分整个区域为 4×4 网格，每个网格记录点的数量
找出有密集数据的几个网格,对这些网格再细分（下钻）

最终：

左上角细分后合并成“簇 A”
右下角细分后合并成“簇 B”
其它区域被排除，不属于任何簇

优点

高效：由于只操作统计摘要，而非原始数据，效率高。
可扩展性好：支持大规模数据集。
支持多层次分析：可以灵活选择不同粒度的层级进行聚类。

缺点

聚类结果依赖于网格划分的方式，不够灵活。
网格边界可能造成聚类割裂（称为边界效应）。

CLIQUE 算法（Clustering In QUEst）

CLIQUE 是一种 基于网格 + 子空间探索的聚类算法，专门用于发现高维数据中的密度簇。

核心思想

将每个维度划分为固定数量的等宽区间（网格单元格）。
构建所有可能的低维子空间，并在这些子空间中寻找密度足够高的网格单元。
利用 Apriori 原则：高维的密度区域必定由低维的密度区域组合而成。
通过递归方式找到所有“密度簇”所在的维度子空间，并形成聚类。

算法流程

空间划分
- 对每个维度划分为 ξ 个等宽区间（即网格单元）。
- 在 d 维空间中，初始共形成 ξ^d 个单位网格。
密度单元检测（初始在 1 维）
- 统计每个 1 维网格单元中的点数，若超过阈值 τ，称为“密度单元”。
子空间扩展（类似 Apriori）
- 逐步组合多个维度（如 2 维、3 维…）形成更高维的子空间。
- 只对在低维中都是“密度单元”的组合进行尝试，减少搜索空间。
聚类形成
- 将在所有子空间中找到的密度单元格相邻的部分连接起来，构成聚类。
- 可以用连通分量的方式将多个密度单元“连通”成一个簇。
输出聚类结果
- 返回所有簇的点集和对应的子空间（说明在哪些维度中形成簇）。
- CLIQUE 支持自动检测出 不同维度的簇结构，适合高维数据分析。

优点

能发现 任意维度子空间中的簇，适合处理高维稀疏数据；
网格结构使得它对噪声具有鲁棒性；
自动确定簇的数量和维度。

缺点

网格分辨率（ξ）选得不合适会影响聚类效果；
枚举所有子空间仍可能面临维度灾难，适合中等维度使用。

基于模型的聚类方法

EM 算法（Expectation-Maximization）

EM 是一种迭代优化算法，用于含有“隐藏变量”的概率模型，常用于估计最大似然参数。聚类中常用于 高斯混合模型（GMM）。

核心思想

数据可能来自多个概率分布（比如多个高斯分布），但我们不知道每个样本来自哪个分布。
EM 用“猜测 → 估计 → 更新”的方式迭代：
- E 步（期望步）：根据当前参数，估计每个样本来自各个分布的概率（软聚类）。
- M 步（最大化步）：根据上一步的估计，重新计算模型参数，使其更符合当前数据。

应用于聚类的流程（以 GMM 为例）

设数据集为 X = {x₁, x₂, ..., x_n}，假设它由 k 个高斯分布混合而成。

初始化参数
- 初始化每个分布的参数：均值 μ_k、协方差 Σ_k 和混合系数 π_k（即每个簇的概率）。
E 步（Expectation）
- 计算每个样本 x_i 属于每个簇 k 的后验概率（即“软分类”）： $$ \gamma_{ik} = P(z_i = k \mid x_i) = \frac{\pi_k \cdot \mathcal{N}(x_i \mid \mu_k, \Sigma_k)}{\sum_{j=1}^K \pi_j \cdot \mathcal{N}(x_i \mid \mu_j, \Sigma_j)} $$
M 步（Maximization）
- 用 E 步得到的“软分类”更新参数：
  - 更新均值： $$ \mu_k = \frac{\sum_{i=1}^n \gamma_{ik} x_i}{\sum_{i=1}^n \gamma_{ik}} $$
  - 更新协方差： $$ \Sigma_k = \frac{\sum_{i=1}^n \gamma_{ik} (x_i - \mu_k)(x_i - \mu_k)^T}{\sum_{i=1}^n \gamma_{ik}} $$
  - 更新混合系数： $$ \pi_k = \frac{1}{n} \sum_{i=1}^n \gamma_{ik} $$
判断是否收敛
- 如果对数似然函数变化很小，就停止迭代；否则回到 E 步。

简单例子（二维聚类）

假设你有一组二维数据（比如年龄 vs 收入），你猜它由两个高斯分布组成：

初始：
- 猜两个中心点和协方差
E 步：
- 对每个点，算它属于两个簇的概率（可能是 60% 属于 A，40% 属于 B）
M 步：
- 用这些概率更新两个高斯分布的参数（比如中心位置向有更多点的方向移动）
重复，直到稳定

特点

优点	缺点
能做“软聚类”	对初始值敏感，易陷入局部最优
能适用于复杂概率模型	假设数据满足特定分布（如高斯）
理论成熟，适用于密度估计、图像分割等	不适合非凸或非高斯的聚类结构

聚类的稳定性评估

使用 Jaccard 系数 + Bootstrap 评估聚类稳定性

步骤

原始聚类：
- 用你的聚类算法（如 KMeans、DBSCAN、GMM）对原始数据 D 做聚类，得到原始簇集合 C = {C1, C2, …, Ck}。
多次 bootstrap 重采样：
- 对 D 重采样 B 次，得到 D1, D2, …, DB。
- 每次都用相同聚类算法得到聚类结果 C1’, C2’, …, CB’。
计算每个原始簇 Cᵢ 的 Jaccard 稳定性：
- 对每次 bootstrap，找一个和 Cᵢ 最相似的簇 C’ᵢ（通常用最大 Jaccard 匹配）。
- 计算 Jaccard 指数： $$ J(C_i, C_i') = \frac{|C_i \cap C_i'|}{|C_i \cup C_i'|} $$
- 重复 B 次，得到 Cᵢ 的 Jaccard 系数分布。
聚类稳定性评估：
- 对每个簇，计算 Jaccard 系数的平均值或分布。
- 平均值高 → 表明该簇在不同样本下“经常出现”，稳定性好。

聚类质量外在评估方法

外部方法指的是存在类别划分的ground true，有以下几种方法。

纯度（Purity）：Matching-based methods

Purity 是一种 外部聚类评估指标，用于衡量聚类结果与真实标签（Ground Truth）之间的一致性程度。

Purity 的计算公式如下：

$$ \text{Purity} = \frac{1}{n} \sum_{i=1}^{k} \max_j |C_i \cap L_j| $$

公式说明：

n：样本总数
k：聚类簇的数量
C_i：第 i 个聚类簇
L_j：真实的第 j 类
|C_i∩L_j|：簇 C_i 中属于类 L_j 的样本数量

换句话说：
对于每个簇 C_i，我们找到出现最多的真实类别，把这部分样本视为“正确分类”。所有簇的最大匹配数相加，再除以总样本数 n，就是 Purity。

举例说明

假设有 10 个样本，聚类为 3 个簇，真实类别也有 3 类：

簇编号	类 A 数	类 B 数	类 C 数	总数
C1	3	2	0	5
C2	0	0	3	3
C3	0	1	1	2

计算每个簇中“最多的类别”：

C1 中最多是类 A（3 个）
C2 中最多是类 C（3 个）
C3 中最多的是类 B 或类 C（都为 1 个，任选）

所以：

$$ \text{Purity} = \frac{3 + 3 + 1}{10} = \frac{7}{10} = 0.7 $$

特点总结

取值范围：[0,1]，越高表示聚类越纯
优点：简单、直观，适合快速评估
缺点：对簇的数量敏感，簇数越多，Purity 越容易升高（比如每个点单独成簇则 Purity = 1）

条件熵（Conditional Entropy）：Information Theory-Based Methods

条件熵（Conditional Entropy）是信息论中的一个重要概念，衡量的是在已知一个随机变量（如聚类结果）情况下，另一个变量（如真实标签）的不确定性。

数学定义

设：

C：聚类结果，共有 k 个簇：C₁, C₂, …, C_k
L：真实类别，共有 r 个类：L₁, L₂, …, L_r

条件熵定义为：

$$ H(L|C) = - \sum_{i=1}^{k} P(C_i) \sum_{j=1}^{r} P(L_j|C_i) \log P(L_j|C_i) $$

其中：

P(C_i)：样本落在聚类簇 C_i 的概率
P(L_j|C_i)：在 C_i 中属于真实类别 L_j 的条件概率

直观理解

如果每个簇只包含一种真实标签，则 P(L_j|C_i) = 1，熵为 0，表示完全确定。
如果每个簇中标签很混乱（多类平均分布），则 P(L_j|C_i) 分布接近均匀，熵值更大。

因此：

条件熵越小，聚类结果与真实标签越一致。

归一化互信息(NMI): Information Theory-Based Methods

ormalized Mutual Information（归一化互信息）是一种衡量聚类结果与真实标签之间“共享信息量”的指标。它对 Mutual Information 进行了标准化，使得结果更具可比性。

Mutual Information (MI)

互信息用于衡量聚类结果 C 和真实分类 G 之间的关联程度：

$$ I(C, G) = \sum_{i=1}^{r} \sum_{j=1}^{k} p_{ij} \log \left( \frac{p_{ij}}{p_{C_i} \cdot p_{G_j}} \right) $$

其中：

p_ij 表示同时属于簇 C_i 和真实类 G_j 的样本比例；
p_{C_i} 是属于聚类簇 C_i 的样本比例；
p_{G_j} 是属于真实类别 G_j 的样本比例。

📌 说明：

如果聚类和真实标签完全无关（独立），则 p_ij = p_{C_i} ⋅ p_{G_j}，从而 I(C,G) = 0；
互信息没有上限，不适合直接比较不同数据集结果，因此需要归一化。

Normalized Mutual Information (NMI)

为了解决 MI 没有上界的问题，引入归一化互信息：

$$ \text{NMI}(C, G) = \frac{2 \cdot I(C, G)}{H(C) + H(G)} $$

或：

$$ \text{NMI}(C, G) = \frac{I(C, G)}{\sqrt{H(C) \cdot H(G)}} $$

其中：

H(C) 为聚类结果的熵；
H(G) 为真实标签的熵。

熵的定义为：

$$ H(C) = - \sum_{i=1}^{r} p_{C_i} \log p_{C_i} \quad , \quad H(G) = - \sum_{j=1}^{k} p_{G_j} \log p_{G_j} $$

NMI 特性

取值范围： [0,1]
NMI 越接近 1： 表示聚类结果越接近真实标签。
NMI = 0： 表示聚类与标签完全独立。
可用于不同聚类算法或数据集之间的结果对比。

基于成对对比

假设：

TP：同类同簇的对象对数量（True Positive）（预测同类，真实同类）
FP：不同类同簇的对象对数量（False Positive）（预测同类，真实不同）
FN：同类不同簇的对象对数量（False Negative）（预测不同，真实同类）
TN：不同类不同簇的对象对数量（True Negative）（预测不同，真实不同）
总对数：所有对象对数量 = $$\frac{n(n-1)}{2}$$

Jaccard系数

$$ \text{Jaccard} = \frac{TP}{TP + FP + FN} $$

只考虑正例（同簇）相关的三种情况，忽略TN。

Rand指数

$$ \text{Rand Index} = \frac{TP + TN}{TP + FP + FN + TN} $$

计算所有正确对的比例（同簇同类 + 不同簇不同类）。

Fowlkes-Mallows指数（FM）

定义为：

$$ \text{FM} = \sqrt{ \frac{TP}{TP + FP} \times \frac{TP}{TP + FN} } $$

即 precision 和 recall 的调和平均。

聚类质量内在评估方法

没有groundtrue, 直接评价同一簇的样本尽可能的相似，不同簇的样本尽可能不同的水平

轮廓系数 (Silhouette Coefficient)

对每个样本点计算：

a(i)：样本 i 与同簇内其它点的平均距离（簇内距离）
b(i)：样本 i 与最近的其他簇中所有点的平均距离（簇间距离）

轮廓系数定义为：

$$ s(i) = \frac{b(i) - a(i)}{\max\{a(i), b(i)\}} $$

s(i) 范围在 [−1,1]
越接近 1 表示该点聚类效果越好
聚类整体轮廓系数是所有点的平均值

DB指数 (Davies-Bouldin Index, DBI)

计算簇间的相似度，定义为：

$$ DBI = \frac{1}{k} \sum_{i=1}^k \max_{j \neq i} \left( \frac{S_i + S_j}{M_{ij}} \right) $$

S_i：簇 i 内所有点到簇中心的平均距离（簇内散度）
M_ij：簇 i 和簇 j 之间质心的距离（簇间距离）
DBI 越小表示聚类效果越好

Dunn指数 (Dunn Index, DI)

衡量簇间最小距离与簇内最大直径的比值，定义为：

$$ DI = \frac{\min_{i \neq j} d(C_i, C_j)}{\max_{1 \leq k \leq K} diam(C_k)} $$

d(C_i,C_j)：簇 i 和 j 之间的距离（通常取质心距离或最小点对距离）
diam(C_k)：簇 k 内最大距离（簇直径）
DI 越大表示聚类效果越好

离群点检测

离群点的基本概念与分类

离群点（Outlier）的基本概念

离群点是指数据集中明显偏离其他观测值的异常样本点。这些点通常表现为：

与大多数数据点差异较大
不符合数据的整体分布模式
可能是测量错误、数据录入错误，也可能是真实的罕见事件

离群点的识别对于数据清洗、异常检测和数据分析非常重要。

离群点的分类

全局点异常（Point Outlier）
- 单个样本点偏离整体数据分布，显著异常。
- 例如：一个人的身高为3米（明显偏离正常范围）。
上下文异常点（Contextual Outlier 或 Conditional Outlier）
- 数据点在某些上下文环境下表现异常，但在整体数据中未必异常。
- 例如：气温30℃在夏天正常，但冬天异常。
集体异常点（Collective Outlier）
- 一组数据点整体偏离正常行为，即使单个点看起来不异常。
- 例如：一段时间内网络异常流量的突然增长。

基于统计模型的概率测试 (Model-based)

基本思想
统计检测（Statistical-based Methods）属于模型驱动（Model-based）方法。其核心在于：
构建某种已知的概率分布模型（如正态分布），将显著偏离该分布的点识别为离群点（Outliers）。

常见方法

1. 单变量正态分布检测（Z-Score）

原理：

假设变量服从正态分布，计算每个点的 Z 分数：

$$ z = \frac{x - \mu}{\sigma} $$
设定一个阈值（如 |z| > 3），超出该范围的点被认为是离群点。

适用场景：

仅适用于一维数据。
要求数据接近正态分布。

2. Grubbs 检验（Grubbs’ Test）

原理：

检测一个数据集中的最大偏差值是否显著异常。
假设数据服从正态分布，计算最大/最小值与均值的偏差：

$$ G = \frac{ \max |x_i - \bar{x}| }{s} $$
然后与临界值比较（由 t 分布决定）。

特点：

适用于单个离群值检测。
每次只能检测一个异常点，需反复执行。

3. 马氏距离（Mahalanobis Distance）

原理：

多维数据的统计检测方法，考虑协方差之间的相关性。
对于样本点 x，其马氏距离定义为：

$$ D_M(x) = \sqrt{ (x - \mu)^T \Sigma^{-1} (x - \mu) } $$
根据卡方分布或者分位数法确定阈值，马氏距离大于阈值的点即为异常点。

优点：

考虑了变量间的相关性。
适合多维正态分布数据。

4. 参数混合模型（Parametric Mixture Models）

原理：

假设数据由多个分布混合而成（如双高斯分布：主群 + 异常群）。
使用 EM 算法估计每个点属于哪一类的概率：
- 若一个点对“正常类”的后验概率非常低，则判为异常。

适用场景：

异常点服从与主数据不同的分布。

5. 非参数方法

直方图法：将数据分箱，箱中频率低的区间被视为异常区域。
核密度估计（KDE）：
- 估计每个点的概率密度。
- 若某点处的密度估计极低，则为离群点。

优点：

无需分布假设。
适合非正态、非结构化分布。

优缺点总结

优点	缺点
✅ 理论基础扎实	❌ 对分布假设敏感（如必须服从正态分布）
✅ 可提供显著性水平（如p值）	❌ 不适用于高维数据（维度灾难）
✅ 易于解释	❌ 不适合数据分布复杂或有多个模式的情况

总结

统计检测方法适用于数据量不大、维度不高、且分布已知（或可合理假设为正态分布）的场景。如果数据维度高、分布未知或含有复杂结构，建议使用基于距离、密度或机器学习的方法进行异常检测。

基于深度的方法(Model-based)

基本思想

基于深度的离群点检测方法属于 模型驱动（Model-based） 方法，其核心思想是：

离群点通常远离“数据中心”，处在数据分布的边缘。

这些方法通过计算样本点的“深度”（depth）来判断其是否为离群点，深度越小，越靠近边界，越可能是离群点。

方法原理

构建数据层次结构（如多层凸包 Convex Hull）
- 将数据包裹在一个凸壳中，移除最外层样本点。
- 剩下的点构成“内层”。
- 重复该过程，形成类似洋葱结构的多层数据分布。
计算数据深度（Data Depth）
- 每个点所在的“层数”即为其深度（Depth）。
- 深度越小表示越外层，可能为异常点。
根据设定的深度阈值检测离群点
- 通常，设定一个最小深度阈值，如 depth ≤ 1。

典型方法

ISODEPTH（Isotonic Depth）
基于等深线估计数据密度，深度等高线越远的样本越异常。
FDC（Fast Depth Contours）
通过快速构造深度轮廓线（contours）以识别边界样本点。

优点与缺点

优点	缺点
✅ 无需对数据分布进行假设	❌ 主要适用于 2D 或 3D 空间，扩展性差
✅ 对离群点定位自然直观	❌ 计算复杂度高，特别是高维数据
✅ 可以可视化解释（特别是低维）	❌ 不适合大规模或高维数据场景

基于偏差的方法(Model-based)

基本思想

该方法属于 Model-based（模型驱动） 异常检测方法，核心思想为：

寻找能最大程度降低整体数据集“偏差”或“方差”的子集，认为这些样本是异常点。

正常数据应具有某种“紧凑”结构（如低方差）
异常点会“拉大”整体分布
删除某些点后，如果整体变得更“紧凑”，那么这些被删除的点很可能是离群点

典型方法：SF(I) 模型（Arning 等）

提出者：Arning, Agrawal 和 Raghavan (1996)
SF(I) 指标定义：

设数据集为 D，我们希望找出一个子集 I ⊆ D，其移除后会带来最大的信息压缩或方差降低。
- 定义一个目标函数：
  
  SF(I) = Var(D) − Var(D−I)
- 其中 Var(·) 表示数据集的方差或某种误差度量
- SF(I) 越大，说明 I 中的点是影响整体结构的“异常值”可能性越高

优点

✅ 概念直观：只需比较方差的变化即可判断是否为离群点
✅ 适用于任意类型数据（数值型、类别型、混合型）

缺点

❌ 计算复杂度极高：
- 在最坏情况下，需要检查所有可能的子集 I，即时间复杂度为 O(2ⁿ)
- 因此，需要借助启发式算法进行优化（如贪心、剪枝、局部搜索等）

基于距离的方法（Proximity-based）

基本思想

基于距离的异常检测方法属于 Proximity-based（基于邻近度） 方法，核心观点是：

异常点距离其邻居较远，邻域较为空旷
正常点的邻域内样本密集，距离较近

通过计算每个点与其周围点的距离，判断是否离群。

核心模型与指标

DB(ε, π)模型
设定一个半径阈值 ε 和邻居比例阈值 π。
如果一个点在半径 ε 内的邻居数量小于 π，则该点被判定为异常。
kNN距离评分
计算点 p 到其第 k 近邻的距离 d_k(p)。
距离越大，说明该点越孤立，异常可能性越大。
k-近邻图（kNN Graph）入度判断
构建一个图，点之间连接到最近的 k 个邻居。
统计某点被多少其他点作为邻居（入度）。入度低的点通常是离群点。
分辨率因子（ROF）
1. 定义分辨率层次
  设定一组分辨率阈值（如 ε₁ < ε₂ < ⋯ < ε_m），用于逐层分析数据结构。
2. 分辨率下邻域聚类
  对于每个分辨率阈值 ε_i：
  - 根据距离和阈值 ε_i 将数据点聚类。
  - 若两个点距离不超过 ε_i，则它们属于同一簇的邻居。
3. 计算聚类大小变化
  - 在不同分辨率 ε_i 下，记录每个数据点所在聚类的大小（即簇中点的数量）。
  - 观察聚类大小随分辨率变化的趋势。
4. 计算累积异常值因子（ROF）
  - 根据数据点在各分辨率层次聚类大小的变化，计算ROF值。
  - ROF值反映数据点在多层分辨率结构中“聚类稳定性”的变化情况。
  - 变化较大的点（ROF值较低）通常是异常点。
5. 异常点排序与选择
  - 根据ROF值对所有数据点排序。
  - 选择ROF值最低的前 k 个点作为异常值。

代表算法

ORCA
通过利用距离剪枝技术快速计算kNN距离，实现高效的异常检测。
- 特点
  利用三角不等式和剪枝技术，减少不必要的距离计算。
- 流程
  1. 计算数据集中点的kNN距离。
  2. 对于每个点，若kNN距离大于阈值，则标记为异常。
- 优势
  相比暴力计算，效率提升显著，适合大数据。
RBRP
基于空间分区的方法，先划分数据空间，再局部检测异常，降低计算复杂度。
- 思路
  先将数据空间划分成若干区域（分区），减少邻居搜索范围。
- 流程
  1. 对数据做空间划分。
  2. 在每个分区内局部计算kNN距离。
  3. 综合各分区结果，标记异常。
- 优势
  降低全局搜索复杂度，提升速度。
基于分区的算法
利用数据划分，将复杂问题分解，便于局部检测异常，适合大规模数据。
- 将数据空间划分成多个小块，分别检测异常。
- 适合高维数据或大规模数据集。
- 结合局部异常检测，能发现局部稀疏区域的异常。

优缺点

优点	缺点
灵活，能检测局部和全局异常点	受“维度灾难”影响，高维数据效果差
直观，易理解，适合多种数据类型	计算复杂度高，距离计算耗时较多
适用于多种数据分布，无需分布假设	需要合理选择参数，如 ε 和 k

基于密度的方法（Proximity-based）

基本思想

基于密度的方法通过比较一个点与其邻域的密度来判断是否异常：
- 如果某点的密度远低于周围点的密度，则可能是离群点。
- 通常基于 相对密度，更适用于具有不同密度的区域。

代表方法与简要流程

1. LOF（Local Outlier Factor）

思想：与邻居的局部密度相比，若某点显著稀疏则为离群点。

流程：

设定邻居数 k，计算每个点的 k-距离邻域。
计算每个点的 可达距离（Reachability Distance）： reach-dist_k(p,o) = max {k-dist(o), d(p,o)}
计算 局部可达密度（LRD）： $$ \text{LRD}_k(p) = \left( \frac{1}{|N_k(p)|} \sum_{o \in N_k(p)} \text{reach-dist}_k(p, o) \right)^{-1} $$
计算 LOF值： $$ \text{LOF}_k(p) = \frac{1}{|N_k(p)|} \sum_{o \in N_k(p)} \frac{\text{LRD}_k(o)}{\text{LRD}_k(p)} $$
LOF值越大，越可能是离群点。

2. COF（Connectivity-based Outlier Factor）

核心思想：

COF（连通性异常因子）是一种用于离群点检测的密度方法，旨在通过衡量数据点与其邻域之间的“连通性”强弱来判断是否为异常点。

正常点在局部区域连通性强；
异常点的连通性较弱，其与邻居之间的路径通常更长；
COF值越大，表示该点越可能是异常值。

基本定义：

k-最近邻（kNN）：点 p 的最近 k 个邻居集合，记作 N_k(p)。
SBN-Path（Set-based Nearest Path）：从点 p 到 N_k(p) 中所有点的“连通路径”。
链式距离（Chaining Distance）：从点 p 到每个邻居的连接路径的总距离。
平均链式距离（ac-dist）：点 p 的 SBN-Path 中所有路径长度的平均值。

算法流程：

寻找 k 个最近邻
对于数据集中的每个点 p，找到其 k 个最近邻组成集合 N_k(p)。
构建 SBN-Path 并计算链式距离
使用贪心策略，逐步从 p 开始连接未访问的邻居，形成一条连通路径，计算该路径的总长度。
计算平均链式距离
对于每个点 p，计算其平均链式距离（ac-dist）： $$ \text{ac-dist}(p) = \frac{1}{|N_k(p)|} \sum_{\text{链上每一步}} d(x_i, x_{i+1}) $$
计算 COF 值
计算点 p 的 COF 值： $$ \text{COF}(p) = \frac{\text{ac-dist}(p)}{\frac{1}{|N_k(p)|} \sum_{q \in N_k(p)} \text{ac-dist}(q)} $$ 如果 COF(p) ≫ 1，说明 p 的连通性显著弱于邻域点，是潜在异常值。
异常值排序与检测
将所有点按 COF 值降序排序，取前 n 个作为异常点。

3. INFLO（Influenced Outlierness）

算法动机：

LOF 的问题：在不同密度的簇之间没有明显边界时，LOF 可能将“稀疏簇内的正常点”错误地判为离群点。
INFLO 的改进思路：考虑对称的邻域关系，将“反向邻居”也纳入密度计算，更合理地估计点的局部密度。

核心概念：

k-近邻 (kNN)
- kNN(p)：点 p 的 k 个最近邻集合。
反向 k-近邻 (Reverse kNN)
- RkNN(p)：将 p 看作最近邻的所有其他点的集合，即 p 是这些点的 kNN 成员。
影响空间 (Influence Space)
- kIS(p) = kNN(p) ∪ RkNN(p)
- 表示“与点 p 存在双向邻近关系”的点集合。

密度定义：

点 p 的密度定义： $$ den(p) = \frac{1}{k\text{-distance}(p)} $$
- 即 p 到第 k 个最近邻的距离的倒数。

INFLO 值计算：

计算影响空间中每个点的密度：
对每个 o ∈ kIS(p)，计算：
$$ den(o) = \frac{1}{k\text{-distance}(o)} $$
计算 INFLO：
$$ INFLO(p) = \frac{1}{|kIS(p)|} \sum_{o \in kIS(p)} \frac{den(o)}{den(p)} $$

算法流程：

计算每个点的 kNN 和 RkNN，合并得到影响空间 kIS(p)；
根据 k-distance 计算每个点的密度 den(p)；
对每个点 p 计算其影响空间中点的平均密度，并与自身密度做比值，即计算 INFLO 值；
对所有点根据 INFLO 值排序，INFLO 值越大，离群可能性越高。

性质与解释：

若 INFLO(p) ≈ 1：p 处于某个密度一致的簇中；
若 INFLO(p) ≫ 1：p 密度显著低于影响空间中的其他点，可能是离群点。

优势：

可处理非均匀密度分布的数据
使密度评估更加对称、全面

4. LOCI（Local Correlation Integral）

基本思想：

与 LOF 类似，LOCI 判断一个点是否为异常值，依据是：该点的局部密度是否显著低于其邻域的平均密度。
区别在于：
- LOF 使用 kNN，LOCI 使用 ε-邻域
- LOF 固定尺度，LOCI 在 多个分辨率（granularities） 下做检测
目的是提高算法稳定性，并避免手动设定参数 k 或 ε。

核心定义：

ε-邻域
- N(p,ε) = {q ∣ dist(p,q) ≤ ε}
- 点 p 的 ε-邻域中包含所有与 p 距离不超过 ε 的点。
α·ε-邻域
- N(q,α⋅ε)：点 q 的缩放邻域，0 < α ≤ 1，常取 α = 0.5

局部密度计算：

点 p 的局部密度： $$ \text{den}(p, \varepsilon, \alpha) = \frac{1}{|N(p, \varepsilon)|} \sum_{q \in N(p, \varepsilon)} |N(q, \alpha \cdot \varepsilon)| $$
- 含义：点 p 的密度由其邻域中各点自身局部邻域大小的平均值决定。

异常度量：MDEF（Multi-granularity Deviation Factor）

定义： $$ \text{MDEF}(p, \varepsilon, \alpha) = 1 - \frac{|N(p, \alpha \cdot \varepsilon)|}{\text{den}(p, \varepsilon, \alpha)} $$
直观理解：
- 如果 p 的邻域密度远低于其邻域平均密度，MDEF 值较大 ⇒ 更可能是异常点。
- 如果 p 密度与邻域一致，则 MDEF ≈ 0 ⇒ 正常点。

标准差：σ_MDEF

σ_MDEF(p,ε,α) 表示局部密度的标准差，用于评估 MDEF 的显著性。
异常点判定规则：
- 若 MDEF(p,ε,α) > 3 ⋅ σ_MDEF，则判为异常点（基于 3σ 原则）。

算法流程：

遍历所有点
- 对数据集中每个点 p：
遍历多尺度（多个 ε 值）
- 设定多个 ε 分辨率（从小到大），逐个测试：
计算 ε-邻域和 α·ε-邻域大小
- N(p,ε) 和 N(q,α⋅ε)
计算密度、MDEF、σ_MDEF
- 得到 den(p,ε,α)
- 得到 MDEF(p,ε,α)
- 得到 σ_MDEF(p,ε,α)
判断异常点
- 若 MDEF(p,ε,α) > 3 ⋅ σ_MDEF，则在该分辨率下，p 是异常点。

LOCI Plot 可视化:

对某个点 p，可画出多尺度下的 LOCI 曲线，显示：
- |N(p,α⋅ε)|
- den(p,ε,α) ± 3σ 上下界
可用图表找出在哪些尺度下 p 被判定为异常点。

输出结果:

异常评分：MDEF 值，可排序。
异常标签：是否满足 MDEF > 3σ 的条件。
可解释图表：LOCI Plot 可展示异常发生的尺度

特点：

不依赖具体参数（如 k）
提供异常的置信度范围（MDEF）

特点总结

✅ 更适合处理不同密度区域
✅ 输出连续的异常评分，可排序选择异常点
❗ 参数敏感，如 k 或 ε 需合理设置
❗ 计算复杂度通常较高（如 O(n²)）

基于重构的方法(其他类型)

基本思想

假设数据可由一个简洁的模型有效表示或重构。
若某个数据点无法被模型很好重构（即重构误差高），则可能是异常点。

常见技术

1. 矩阵分解（Matrix Factorization）

代表方法： 奇异值分解（SVD）或主成分分析（PCA）
原理： 将原始高维数据映射到一个低维空间并重构，如果某个样本的重构误差较大，则可能是异常。
异常度计算： error(x) = ∥x − x̂∥₂ 其中 x̂ 是降维后的重构结果。

2. 码表压缩法（Codebook/Compression-based）

代表思想： 通过对数据压缩（如MDL理论），来衡量异常性。
核心假设： 正常数据可以被压缩得很好，而异常点不容易压缩，需要更长的编码长度。
典型方法：
- Lempel-Ziv 编码长度分析
- BZIP2/GZIP等压缩算法结合
异常度： 用编码长度 L(x) 表示，编码长度越长越异常。

3. 自编码器（Autoencoder）

结构： 包括编码器（Encoder）和解码器（Decoder），构建一个神经网络模型学习 x → x̂。
核心思想： 正常样本的重构误差较低，异常样本无法通过训练好的网络精确还原。
重构误差： Loss(x) = ∥x − x̂∥² 或 BCE(x,x̂)
改进变种：
- 稀疏自编码器（Sparse AE）
- 卷积自编码器（CAE）
- 变分自编码器（VAE）

优点

可捕捉数据的复杂非线性结构（特别是深度学习方法）
适合连续属性和高维数据场景

缺点

训练成本较高（尤其是深度网络）
类别型数据支持较差
可能需要较多超参数调整

高维方法（High-dimensional Approaches）

问题背景

在高维空间中，传统的距离或密度度量变得不可靠，容易出现“维数灾难”问题：

距离集中效应（所有点间距离趋于相同）
密度稀疏，难以定义邻域或聚类结构

常见解决方法

1. 降维 + 异常检测

核心思路： 先将高维数据压缩到低维，再在低维空间中进行异常检测。
常用模型：
- 自编码器（Autoencoder）
- OC-NN（One-Class Neural Network）
- DevNet（Deep Semi-Supervised Anomaly Detection）
流程：
1. 用神经网络学习高维数据的低维嵌入表示。
2. 在嵌入空间中使用距离、密度或边界方法识别异常点。

2. ABOD（Angle-Based Outlier Detection）

核心思想： 异常点与其它点形成的角度分布差异小。
解释：
- 正常点通常被“包围”，与其它点的角度变化小。
- 异常点在边缘，与其它点形成的向量夹角分布变化大。
计算方法： 对每个点 p，计算其与其它点对 (o_i,o_j) 构成的角度的方差： ABOD(p) = Variance(cos∠(p,o_i,o_j))
- 方差越大 → 越像正常点
- 方差越小 → 越可能是离群点

优点

适合高维数据（尤其是深度学习方法）
能挖掘复杂的非线性结构

缺点

算法复杂度高，训练和推理时间较长
可解释性较差（尤其是深度模型）

不会的都不考！

计算机 > 数据挖掘

#计算机 #数据挖掘

数据挖掘课程复习

https://gongzihang.github.io/BLOG/2025/06/11/数据挖掘课程复习/

作者

Zihang Gong

发布于

2025年6月11日

更新于

2025年6月12日

许可协议

Softmax的进化之旅上一篇

线性代数：矩阵与线性方程组下一篇

数据挖掘课程复习

概述

数据挖掘的含义

数据挖掘过程

数据挖掘的应用

数据仓库

数据特征分析与预处理

数据类型及其特征

数据对象：

属性类型

数据的描述统计

数据可视化方法

测量数据的相似性和相异性

标称属性的邻近度量

二进制属性的度量

例题：二进制属性的非对称相异性度量

数值属性的度量

区间尺度与有序变量的度量

其他度量方法：

余弦相似度：

KL 散度（Kullback-Leibler Divergence）：

数据预处理

数据预处理的主要任务：

关联规则

关联规则挖掘概念

支持度（Support）：

置信度（Confidence）：

提升度（Lift）：

频繁项集与其分类

频繁项集：

闭频繁项集（Closed）：

极大频繁项集（Maximal）：

三者关系：

关联规则基本模型

挖掘流程：

📌 Apriori算法流程

核心思想：Apriori原理

算法计算流程

步骤 1️⃣：扫描数据库，找出频繁 1 项集（L₁）

步骤 2️⃣：由 L₁ 构造候选 2 项集（C₂）

步骤 3️⃣：迭代构造更高阶项集 L₃、L₄…

步骤 4️⃣：由频繁项集生成关联规则

提高 Apriori 算法效率的方法

关联规则的度量

分类

模型评估方法

分类模型评估指标

🛠️ 决策树归纳算法的流程（以 ID3/C4.5/CART 为例）

属性选择度量

信息增益（Information Gain）

增益率（Gain Ratio）

基尼指数（Gini Index）

常见分类方法的主要思想

朴素贝叶斯分类（Naive Bayes Classification）

Laplacian Correction（拉普拉斯校准）

KNN 分类（K-Nearest Neighbors）

逻辑回归（Logistic Regression）

基本思想：

神经网络

支持向量机（SVM）分类

核心思想：

线性可分情况：

线性不可分情况：

非线性分类：

集成方法（Ensemble Methods）

基本思想：

主要类型：

聚类

基于划分的聚类方法

K-平均聚类算法

K-中心点聚类算法

PAM算法

CLARA算法

CLARANS算法

输入参数：

多次随机局部搜索（共执行 num_local 次）：

最终输出：

基于层次的聚类方法

AGNES (Agglomerative Nesting)算法

DIANA (Divisive Analysis)算法

多次随机局部搜索（共执行 `num_local` 次）：