Chapter 1 - Introduction to Big Data Mining

1. What’s Big Data?

大数据是指那些规模巨大、增长迅速、类型多样，而传统数据处理工具难以有效处理的数据集合。
Big Data refers to datasets that are too large, fast, or diverse for traditional data-processing software to manage efficiently.

2. The 4Vs of Big Data（四个特性）

Volume（体量）：数据规模巨大（如 Walmart 每小时 2.5PB）；
Velocity（速度）：数据产生速度快（如传感器、社交平台）；
Variety（多样性）：数据形式丰富（文本、图像、音频、视频等）；
Veracity（真实性）：数据存在不确定性、缺失、噪声问题。

3. What’s Data Mining?

数据挖掘是从大量数据中自动发现有价值的模式和知识的过程。
Data mining is the process of automatically discovering useful patterns and knowledge from large volumes of data.

4. Main Tasks of Data Mining

任务	含义	示例
Association Rule Mining	发现项之间的共现模式	购物篮分析：买牛奶的人常买面包
Clustering	将数据无监督地分组	用户行为聚类、图像聚类
Classification / Prediction	用已有标签数据训练模型	AD 点击预测、客户流失预测
Outlier Detection	发现异常数据	信用卡欺诈检测、NBA球员分析（异常得分）

Chapter 2 - Subspace Learning

🌐 主题：应对高维问题 → 降维与子空间聚类

一、Curse of Dimensionality（维度灾难）

当数据维度（特征数）增加时，原有在低维空间中有效的方法会失效或性能急剧下降的现象。

数据量需求随维度呈指数增长；
高维数据中，大多数数据点之间距离相近；
分类器和聚类效果变差。

二、Dimensionality Reduction（降维）

将数据从高维空间映射到一个低维子空间，同时尽可能保留其结构/信息。

分为 线性方法 与 非线性方法：

① Linear Methods

📌 Principal component analysis PCA（主成分分析）

提取方差最大的方向作为主成分；
求协方差矩阵的特征向量。

数学目标：将高维数据投影到低维子空间，尽可能保留原始数据的方差（信息量）。

最大化 $w^T S w$，其中 $S$ 为协方差矩阵。

📌 Multidimensional scaling MDS（多维缩放）

目标是尽可能保留原始空间中 pairwise 距离；
对称矩阵变换 → 特征值分解。
MDS 是一种从距离矩阵中恢复坐标的方法，其目标是在低维空间中尽可能保留原始空间的距离关系，适用于降维与可视化。

对比项	PCA	MDS
输入	原始特征矩阵 $X$	样本间距离矩阵 $D$
保留信息	最大化投影后的方差	尽可能保留成对距离
本质	特征值分解协方差矩阵	特征值分解双中心化距离矩阵
是否支持非欧式距离	否	是（可扩展到任意距离）

② Nonlinear Methods

适合复杂的流形结构，不满足线性假设。

包括：

LLE（Locally Linear Embedding）：保持局部线性结构；
- LLE 是一种保留局部线性结构的非线性降维方法，通过保持每个点与邻居之间的重构权重，实现对高维流形的低维展开。
- 对于每个数据点：
  - 在高维空间中，找到其最近邻；
  - 学习这些邻居对它的线性重构权重；
  - 然后在低维空间中找到坐标，使这些重构权重仍然能线性重建该点。
    
    也就是说：
    
    保持“谁由谁重构出来”的关系结构不变。
Laplacian Eigenmap （LEM）：LEM 是一种基于图的降维方法，通过构造邻接图并最小化图拉普拉斯能量，寻找保留局部结构的低维嵌入。
- Laplacian Eigenmaps（LEM） 是一种基于图的流形学习方法，目标是：将高维数据降维到低维空间，同时保持原始数据点之间的局部邻接关系（图结构）。
  
  它本质上是：利用“图拉普拉斯矩阵”的特征值分解，把样本映射到低维空间。

方法	类型	保留结构	优点	缺点

LLE	非线性	局部线性结构	保局部重构关系	对噪声敏感
LEM	非线性	局部邻接图结构	图结构直观	无法处理新样本（不可扩展）

Isomap：ISOMAP 用测地距离（沿着流形表面最短路径）代替欧几里得距离。
- 经典 MDS 的非线性扩展。
- ISOMAP 是一种将测地距离作为相似度基础的非线性降维算法，能够在保持数据流形全局结构的同时将数据有效嵌入低维空间。
SNE（Stochastic Neighbor Embedding）：
- SNE 是一种概率模型驱动的降维算法，它的目标是：
  
  在低维空间中 保留样本之间的邻近概率关系。

三、Subspace Clustering（子空间聚类）

高维数据中，不同簇可能存在于不同的子空间中。

① Sparse Subspace Clustering (SSC)

思路：

利用稀疏表示表达点之间的从属关系；
每个样本用其他样本的线性组合表达，但只用同一子空间的点；

数学模型：

$\min |Z|_1 \quad \text{s.t. } X = XZ, \ \text{diag}(Z) = 0$

解释：

$X$ 是原始数据矩阵，$Z$ 是稀疏系数矩阵；
求出 $Z$ 后，将其作为邻接图输入谱聚类方法。

② Low-Rank Representation (LRR)

利用核范数约束使得 $Z$ 尽可能低秩，适用于存在全局结构的数据。

对比维度	SSC（稀疏子空间聚类）	LRR（低秩表示）
基本思想	每个点由同子空间内的少数点稀疏重构	所有数据整体表达为一个低秩表示
表达模型	$X = XZ, \quad \min \	Z\	_1$	$X = XZ, \quad \min \	Z\	_*$
优化目标	稀疏性（$\ell_1$范数）	低秩性（核范数）
矩阵特性	稀疏，具有 block-diagonal 结构	低秩，具有全局 block 结构
表示方式	局部：每个样本独立表达	全局：整体联合优化
抗噪性能	抗噪能力较弱，需扩展支持噪声	天然支持噪声建模（LRR+E）
适合情况	数据干净、子空间独立	数据含噪、子空间可能交叉
理论保证	若子空间独立、足够稀疏，则 Z 为 block-diagonal	对任意噪声类型，都能恢复子空间结构（有鲁棒性理论）
计算复杂度	多次解 Lasso，复杂度高但可并行	解核范数优化问题，复杂度大但有闭式解
输出相似图	( W =	Z
谱聚类	✔️（构图后使用）	✔️（同样构图后使用）
可扩展性	更适合小规模数据	扩展性弱，大规模数据需优化
代表算法	Elhamifar & Vidal, CVPR 2009	Liu et al., ICML 2010

SSC 中的 $Z$ 是列稀疏的，自然构成的图是“局部连通图”；

LRR 的 $Z$ 是低秩稠密的，构成的图是“块对角稠密图”；

方法	是否线性	保留结构	核心思想	是否监督	应用类型	适用情况
PCA	✅ 线性	全局方差结构	通过投影到最大方差方向实现降维	❌ 无监督	降维	特征间线性关系，数据协方差矩阵非奇异时效果好
MDS	✅ 线性（经典MDS）或非线性	欧氏距离	保持样本间的成对距离关系	❌ 无监督	降维，可视化	适用于距离信息已知或非结构化数据
LLE	❌ 非线性	局部线性结构	每个点用邻居线性重构，保持该结构进行降维	❌ 无监督	非线性降维	数据位于非线性流形上，局部结构信息明确
LEM	❌ 非线性	局部邻接结构	构造图，利用拉普拉斯矩阵做谱嵌入（Laplacian Eigenmap）	❌ 无监督	非线性降维	保留局部几何结构，适用于图结构或流形结构数据
Isomap	❌ 非线性	全局几何结构	用最短路径近似流形距离，再用MDS保持这些距离	❌ 无监督	流形学习、非线性降维	流形结构明显，需保留全局关系
SNE	❌ 非线性	局部概率结构	保持邻近点的概率分布，通过KL散度优化嵌入	❌ 无监督	可视化（如t-SNE）	高维数据可视化，重点保留邻近关系，常用于图像、文本
SSC	❌ 非线性	子空间结构	用稀疏线性组合表达样本，构建相似性图，再聚类	❌ 无监督	子空间聚类	多个低维子空间混合，高维稀疏性显著
LRR	❌ 非线性	子空间结构	求解全局低秩表示Z，适合多个子空间块结构	❌ 无监督	子空间聚类	存在多个独立子空间，噪声干扰或数据缺失较多时有效

✅ Chapter 3 - Hashing（哈希技术）详解

📌 主题核心：

在大规模高维数据中快速查找相似项，使用哈希压缩、加速搜索过程，替代传统“暴力”比对。

✅ 1. Why? 动机与背景

EN:
In large-scale data, similarity computation is expensive. Hashing techniques allow us to compress high-dimensional data and approximate similarity using compact hash values.

CN：
在大规模数据中，计算相似度（如 Jaccard、余弦、欧氏距离）开销很大。哈希技术能将高维数据压缩，通过短小的哈希值来近似相似度，从而显著加速查询过程。

✅ 2. k-shingles（或 k-grams）

EN:
Convert documents (or strings) into sets of contiguous substrings of length k, called k-shingles.
These sets can then be compared using set-based similarity measures like Jaccard.

CN：
将文档或字符串划分为长度为 $k$ 的连续子串集合，称为 k-shingles（k-gram 子串）。
转换为集合后，我们可以使用集合相似度（如 Jaccard）来比较它们。

字符串 abcde 的 2-shingles 是：

${\texttt{ab}, \texttt{bc}, \texttt{cd}, \texttt{de}}$

✅ 3. MinHash（最小哈希）：Jaccard 相似度近似计算

① Definition（定义）

📌 EN:

MinHash is a probabilistic hashing technique to estimate Jaccard similarity between sets.
It works by simulating random permutations of set elements and taking the minimum hashed index per set under each permutation.

📌 中文：

MinHash（最小哈希） 是一种用于近似计算两个集合之间 Jaccard 相似度 的概率型哈希方法。
它的核心思想是：模拟集合元素的随机排列，在每次排列中记录每个集合中第一个出现的元素的哈希值。

② Signature Matrix（签名矩阵）

📌 EN:

The signature matrix compresses a binary input matrix into a smaller integer matrix.

Rows: each hash function (or permutation);
Columns: each document or set;
Value: the index (row) of the first 1 under that hash function.

This matrix serves as a compact summary of the original data.

📌 中文：

签名矩阵 是将原始 0-1 输入矩阵压缩成较小的整数矩阵。

每一行对应一个哈希函数（或排列）；
每一列对应一个文档（或集合）；
每个值表示：在该哈希函数下，第一个在该文档中出现的特征（即为 1 的行）的哈希值。

它是文档的“压缩表示”，用于后续快速估算相似度。

③ Properties of Signature Matrix: Approximation（性质：近似性）

📌 EN:

The most surprising and powerful property of MinHash is:

The probability that two sets have the same MinHash value under a random hash function equals their Jaccard similarity.

$\Pr[h(C_1) = h(C_2)] = \frac{|C_1 \cap C_2|}{|C_1 \cup C_2|} = \text{Jaccard}(C_1, C_2)$

Therefore, the fraction of equal values between two columns in the signature matrix is an unbiased estimator of their Jaccard similarity.

📌 中文：

MinHash 最令人惊讶且有用的性质是：

两个集合在某个哈希函数下的 MinHash 值相等的概率，等于它们的 Jaccard 相似度。

$\Pr[h(C_1) = h(C_2)] = \text{Jaccard}(C_1, C_2)$

所以，我们只需要比较签名矩阵中两个列向量的相同值所占的比例，就可以近似地估计它们之间的 Jaccard 相似度。

解释 MinHash 是如何近似计算两个集合的 Jaccard 相似度的。

✅ 简洁英文答案 Simple English Answer：
MinHash uses hash functions to find the first row with 1 for each set. If two sets get the same value for a hash, they are similar in that hash. The more matches they have, the higher their estimated Jaccard similarity.

✅ 中文解释：
MinHash 用哈希函数找出每列第一个为1的行。如果两个集合在某个哈希函数下取值相同，就说明它们在这一部分相似。匹配次数越多，估算出的 Jaccard 相似度越高。

✅ 总结 Recap

模块	英文摘要	中文摘要
Definition	MinHash maps sets to compressed signatures for fast similarity estimation.	MinHash 将集合压缩为签名，用于快速估计相似度。
Signature Matrix	Stores the min hash value for each doc and hash function.	储存每个文档在每个哈希函数下的最小值，形成签名矩阵。
Property	Signature similarity ≈ Jaccard similarity.	签名相似度 ≈ Jaccard 相似度（概率等价）。

✅ 4. LSH（Locality Sensitive Hashing）：加速相似查找

🎯 Objective（目标）

📌 EN:

The goal of LSH is to quickly find similar items without comparing all item pairs.
It achieves this by ensuring that:

Similar items hash to the same bucket with high probability;
Dissimilar items hash to different buckets with high probability.

📌 中文：

LSH 的目标是：在不进行全对比的前提下，高效查找相似项。
具体来说：

如果两个数据点相似，它们被哈希到同一个桶的概率很高；
如果两个数据点不相似，它们被哈希到同一个桶的概率很低。

简要说明 LSH 如何通过 “band” 和 “row” 的概念找出相似对。

✅ 简洁英文答案 Simple English Answer：
LSH splits each signature into bands (groups of rows). It hashes each band. If two columns match in at least one band, they are candidate pairs.

✅ 中文解释：
LSH 把签名分成多个 band（每个包含几行），每个 band 单独哈希。只要两个列在某个 band 中哈希值相同，就认为它们是相似候选对。

🧠 Trick（技巧）

📌 EN:

LSH uses the “banding technique” to amplify differences between similar and dissimilar items.
The trick is to:

Split signature vectors into b bands of r rows;
Hash each band into buckets;
If any band is equal between two columns, consider them a candidate pair.

This creates a sharp S-shaped threshold for similarity matching.

📌 中文：

LSH 使用一个重要的技巧叫 “band 技术”，用来放大相似项和不相似项之间的差异。
技巧如下：

将每个签名向量（如 MinHash）分成 $b$ 个 band，每个 band 有 $r$ 行；
对每个 band 单独进行哈希，将其映射到桶中；
如果两个文档在某一个 band 中签名完全一致，就认为它们是候选相似对。

这种方法会产生一个 S 型概率曲线：

高于某个相似度阈值的项很容易被命中；
低于阈值的项几乎不会碰撞。

📊 数学解释

设两个文档的 Jaccard 相似度为 $s$，则它们在一个 band 中签名完全相同的概率为：

$s^r$

在所有 $b$ 个 band 中至少一个 band 相同的概率是：

$1 - (1 - s^r)^b$

这个函数是一个 S 型曲线，用于控制查全率与查准率的平衡。

✅ 小结 Recap

内容	英文	中文
Objective	Find similar pairs efficiently using hash buckets	用哈希桶高效找出相似项
Trick	Banding: split signature into bands and hash each	Band 技术：分段+哈希，对比部分而非全体
数学	Probability = $1 - (1 - s^r)^b$	遇到相似对的概率呈 S 型曲线

✅ 5. Find Similar Item

结合上面 MinHash + LSH，你可以：

在 O(1) 时间内找到与查询项落入同一桶的候选集；
再对这些候选集做准确比较，找最相似的 top-k；
复杂度从线性降低为亚线性（sub-linear），适合亿级数据场景。

✅ 6. Learn to Hash（学习哈希）

🎯 What is “Learn to Hash”?
📌 EN:
Instead of using handcrafted hash functions like MinHash or LSH, we can learn hash functions from data.
These data-driven methods are called learned hashing or data-dependent hashing.

📌 中文：
与手工设计的哈希函数（如 MinHash、LSH）不同，学习型哈希是指从数据中自动学习哈希函数，让哈希结果更加符合数据分布规律，也更适用于复杂结构（如图像、文本等）。

📌 方法一：Random Projection 随机投影
EN:
- Project high-dimensional vectors onto random hyperplanes;
- Use the sign of the projection to generate binary hash codes.
  
  For example, given a vector $x$ and random vector $w$ from $\mathcal{N}(0, I)$,
  the hash is defined as:
  $h(x) = \text{sign}(w^\top x)$
  中文：
- 将高维向量随机投影到某个超平面；
- 根据投影值的正负号来生成哈希码（0 或 1）；
  
  例如，给定向量 $x$ 和随机权重 $w$，哈希函数为：
  $h(x) = \text{sign}(w^\top x)$
  这是欧式空间中最常用的 LSH 方法之一，也可用于学习初始化。
📌 方法二：PCA Hashing 主成分哈希
EN:
- Use PCA (Principal Component Analysis) to find top directions of variance;
- Project data onto those directions and threshold the result to get hash bits.
  
  中文：
- 通过 PCA 选择数据最主要的变化方向（主成分）；
- 将样本在这些方向上的投影值做二值化处理，得到哈希码。
  
  这种方法相当于对数据先“白化”，然后对最重要的维度进行哈希，更符合数据本身的结构分布。
📌 方法三：Spectral Hashing 谱哈希
EN:
- Construct a graph based on data similarity；
- Use Laplacian Eigenmaps to compute embedding；
- Binarize the embedding coordinates to get hash bits.
  
  中文：
- 构建基于样本相似度的图结构；
- 用图拉普拉斯矩阵的特征向量（如 Laplacian Eigenmaps）嵌入到低维空间；
- 然后将嵌入坐标进行二值化生成哈希码。
  
  这是一种保留样本局部结构的学习哈希方法，常用于图像、文本语义嵌入。
✅ 总结对比表
| 方法 | 核心思想 | 英文 | 中文 |
| ————————- | ———————————————————- | ———————————————- | ————————————- |
| Random Projection | Sign of projection on random hyperplane | Random hyperplanes | 随机超平面投影并取符号 |
| PCA Hashing | Use top principal components | Principal component projections | 主成分方向上的投影二值化 |
| Spectral Hashing | Use graph structure and eigenmaps | Graph Laplacian & embedding | 图结构保持 + 谱嵌入二值化 |

------

## ✨ Why Learn to Hash?

### EN:

- Handcrafted hashes (e.g. MinHash) are generic, but not always optimal for specific data.
- Learned hashing adapts to the **data distribution**, **label structure**, or **semantic similarity**.

### 中文：

- 手动设计的哈希函数（如 MinHash）虽然通用，但不一定适合所有数据；
- 学习型哈希可以适应数据的**真实分布**、**语义结构**，效果通常更优。

🧾 总结表

技术	类型	特点	相似度形式
MinHash	基于集合	高效估计 Jaccard	集合相似度
LSH	基于哈希桶	查找加速，S型函数	多种距离
Random Projection	学习型	快速，适合欧式空间	cosine / L2
Spectral Hashing	学习型	保持局部结构	图距离
Deep Hashing	学习型	可扩展、表达力强	任意

✅ Chapter 4: Sampling（采样）

① Rejection Sampling 拒绝采样

📌 EN:

Rejection Sampling samples from a target distribution by generating samples from a simpler proposal distribution and rejecting some with probability.

RS: Sample from proposal $q(x)$, accept with probability $\frac{p(x)}{Mq(x)}$

📌 中文：

拒绝采样 是从目标分布 $p(x)$ 采样的一种方法：

先从一个易采样的提议分布 $q(x)$ 中采样；
以比例 $\frac{p(x)}{Mq(x)}$ 接受样本（M 是放缩常数）；

常用于低维、目标分布已知但难以采样时。

② Importance Sampling 重要性采样

📌 EN:

Importance Sampling (IS) estimates expectations under a target distribution $p(x)$ using samples from an easier distribution $q(x)$.

Formula:

$\mathbb{E}_p[f(x)] = \int f(x) p(x) dx = \int f(x) \frac{p(x)}{q(x)} q(x) dx$

Estimate:

$\frac{1}{N} \sum_{i=1}^N f(x_i) \frac{p(x_i)}{q(x_i)}$

📌 中文：

重要性采样 是用来自一个易采样分布 $q(x)$ 的样本，来估计在目标分布 $p(x)$ 下的期望：

用样本权重 $\frac{p(x)}{q(x)}$ 调整偏差；
可用于积分估计或期望估计；
与拒绝采样相比，更适合估计但不一定生成样本。

🔁 对比 RS vs IS：

项目	Rejection Sampling	Importance Sampling
目标	采样	估计期望
原理	接受-拒绝	重加权
是否丢弃样本	是	否
使用场景	小维度、采样为主	任意维度、期望估计为主

③ MCMC Sampling 马尔可夫链蒙特卡洛采样

MCMC：构造马尔可夫链来逼近目标分布，是复杂分布采样的通用方法。

基本思想（Basic Idea）：

📌 EN:

Build a Markov chain with the desired stationary distribution $p(x)$.
Run the chain long enough to let it converge, and sample from it.

📌 中文：

构造一个以 $p(x)$ 为平稳分布的马尔可夫链。
通过不断采样与跳转，最终从这个链中抽样，得到符合 $p(x)$ 分布的样本。

三种典型方法：

🔹 (a) Metropolis-Hastings (MH) 采样

构造跳转候选 $q(x’|x)$，接受概率为：

$\alpha = \min\left(1, \frac{p(x’)q(x|x’)}{p(x)q(x’|x)}\right)$

可接受非对称 proposal；
是 MCMC 中最通用的基础方法。

🔹 (b) Gibbs Sampling 吉布斯采样

每次采样一个变量，条件于其余变量；
是 MH 的特例，接受概率始终为 1；
更适合多变量模型如贝叶斯网络、LDA 等。
条件分布必须易采样

🔁 Gibbs Sampling vs MH：

特性	Metropolis–Hastings (MH)	Gibbs Sampling
本质类型	一般性的 MCMC 方法	MH 的特例
更新方式	提议 $x’$，通过接受率 $\alpha$ 决定是否接受	逐个维度直接从条件分布中采样，无拒绝
是否需要接受概率 $\alpha$	✅ 需要	❌ 不需要（恒为1）
条件分布可不可知？	条件分布可以未知	条件分布必须已知并能采样
维度更新策略	可整体更新、也可分量更新	通常是轮流更新每个变量维度（坐标更新）
样本接受率	通常 < 1，依赖提议分布	恒为 1
效率依赖因素	提议分布的选择（太差则接受率低）	变量相关性强时收敛慢
适用场景	适合一般复杂模型，灵活	适合已知条件分布的模型，如贝叶斯网络、LDA

✅ 总结 Recap（中英文对照）

方法	英文解释	中文解释
Rejection Sampling	Accept/reject samples from $q(x)$	从提议分布采样后以一定概率接受样本
Importance Sampling	Use weighted average to estimate	用权重调整估计目标分布下的期望
MCMC Sampling	Construct Markov chain → sample	构造马尔可夫链逼近目标分布再采样
MH 采样	Accept/reject proposal with α	使用接受率采样，通用灵活
Gibbs 采样	Sample each variable conditionally	条件采样，每步接受，适合多变量模型

📘 CH5. Data Stream Mining 数据流挖掘

✅ ① Challenges of DSM（数据流挖掘的挑战）

Single Pass Handling（单遍处理）

数据流是连续到达的，不能反复访问
每个数据点只能看一遍，没有“读第二次”的机会
要求算法实时、快速、一次性地处理新数据

Memory Limitation（内存限制）

数据量可能是“无限流”或极大规模
无法将所有数据完整保存在内存中
只能用摘要（summary）结构，如滑动窗口、微簇、直方图、Sketch 等

Low Time Complexity（低时间复杂度）

流速极快，每个样本处理时间必须非常短
要求算法在 O(1) 或 近似常数时间 内完成：
- 分类（如 VFDT）
- 聚类（如 Microcluster）
- 概念漂移检测（如 ADWIN）

Concept Drift（概念漂移）

数据分布可能随时间发生变化
表现为 $P(C|X)$ 或 $P(X)$ 随时间演化
如果不自适应，模型将“过时”，分类性能急剧下降
必须具备检测变化 + 模型更新能力

✅ ② What’s Concept Drift?（什么是概念漂移）

the concept drift means that the statistical properties of the target variable, which the model is trying to predict, change over time in unforeseen ways.the probability distribution changes.

本质：分布 $P(C|X)$ 发生变化，即：

类别标签条件概率随时间变化
比如垃圾邮件的判断标准不断演化

✅ ③ Concept Drift Detection（概念漂移检测）

⭐ A. Distribution-based 检测（分布检测法）

思路：比较新旧时间窗口数据的分布差异

Monitoring the change of data distributions between two fixed or adaptive windows of data.
方法：ADWIN、KLD、KS检验等
特点：模型无关、但对窗口大小敏感，难处理虚拟概念漂移

⭐ B. Error-rate-based 检测（误差检测法）

思路：模型性能下降 → 怀疑概念漂移

Capture concept drift based on the change of the classification performance.
方法：DDM、EDDM、PHT
特点：依赖学习器性能曲线，对噪声敏感，难处理逐渐概念漂移

✅ ④ Data Stream Classification（数据流分类）

核心方法：
- VFDT（Very Fast Decision Tree）
- CVFDT（Concept-adapting VFDT）
- SynchStream（基于代表样本流）

项目	VFDT	CVFDT	SynchStream
是否支持漂移	❌ 否	✅ 是	✅ 是（原型+漂移检测）
内存效率	✅ 高	⚠️ 中	✅ 较高（原型压缩）
结构复杂度	✅ 简单	⚠️ 中	❌ 高
分类策略	决策树	滑动窗口 + 决策树	KNN + 原型匹配
使用场景	静态数据流	漂移数据流	复杂动态场景，多概念检测

要求：
- 增量学习、在线更新
- 能适应概念漂移和内存限制

✅ ⑤ Open-set Problems（开放集问题）

指训练集和测试集可能不完全重合的类别空间

开放集问题是指：测试集中可能出现训练时从未见过的类别。
The open-set problem refers to the scenario where test data may include classes unseen during training.
在数据流中尤为严重（新类不断出现）
研究方向：新类检测、未知类识别

✅ ⑥ Data Stream Clustering（数据流聚类）

数据流聚类是指：对动态、连续到达的数据流进行实时、增量式的聚类分析。
Data Stream Clustering refers to the task of performing real-time, incremental clustering over dynamic and continuously arriving data streams.

数据流聚类通常分为两个阶段：
Clustering is typically done in two stages:

① 在线阶段（Online Phase）

Online Micro-clustering

利用微簇（Micro-Cluster）对数据流进行压缩表示
Use micro-clusters to summarize incoming data in real time
仅保存必要的统计信息（如数量、均值、方差）

② 离线阶段（Offline Phase）

Offline Macro-clustering

用户可根据查询/分析需求，使用 k-means 等算法对微簇进行宏观聚类
Based on the micro-clusters, run full clustering algorithms (e.g., k-means) periodically or upon request

⭐ A. Framework（数据流聚类框架）

典型流程：

在线阶段 Online Phase：用 Micro-cluster 汇总流数据

•Summarize the data into memory-efficient data structures
离线阶段 Offline Ohase ：对 Micro-cluster 聚类，生成宏观聚类结构

•Use a clustering algorithm to find the data partition

→ 对应框架如 CluStream（经典模型）

⭐ B. Microcluster（微簇）

是用于压缩原始数据流的统计单元

A Micro-Cluster is a set of individual data points that are close to each other and will be treated as a single unit in further offline Macro-clustering.
包含统计量：(N, LS, SS)（点数、线性和、平方和）
可以支持：
- 动态更新
- 多时间尺度快照（Pyramidal Time Frame）

你这张图总结的是第六章《Hadoop/Spark》的课程板书内容，下面我将其结构整理并用双语方式帮你讲解重点知识：

📘 CH6: Hadoop / Spark 概论

✅ 1. What’s Hadoop / Spark?

Hadoop / Spark 是什么？

Hadoop is a software framework for distributed processing of large datasets across large clusters of computers.

Hadoop 是一个用于在大规模计算机集群上对大数据集进行分布式处理的软件框架。

Spark 是 Hadoop 的后继者，支持 内存计算，速度更快，编程更灵活
Spark is a fast and flexible cluster computing system that improves over Hadoop with in-memory processing.

✅ 2. Design Principles of Hadoop

Hadoop 的设计原则

Need to process big data

Need to parallelize computation across thousands of nodes

Commodity hardware

Large number of low-end cheap machines working in parallel to solve a computing problem

Small number of high-end expensive machines

Automatic parallelization & distribution

Hidden from the end-user

Fault tolerance and automatic recovery

Nodes/tasks will fail and will recover automatically

Clean and simple programming abstraction

Users only provide two functions “map” and “reduce”

1
2
3

NameNode（管理元数据）
  ↑ Heartbeat（定期心跳通信）
DataNodes（存储实际数据块）

✅ 3. HDFS（Hadoop Distributed File System）

HDFS：分布式文件系统

将文件切分成多个 block 分布存储于多个 DataNode
NameNode 维护目录结构和文件索引
特点：大文件优化、写多读多、冗余副本容错

当然，下面是对 HeartBeat（心跳机制） 在 Hadoop 架构中的作用的详细解释，附带中英文双语对照，便于你用于复习或报告展示。

❤️ HeartBeat in Hadoop

Hadoop 中的心跳机制

📘 什么是 HeartBeat？

HeartBeat 是 DataNode 定期向 NameNode 发送的“存活信号”，用于告知其仍处于活跃状态。
HeartBeat is a periodic signal sent from a DataNode to the NameNode to indicate that it is alive and functioning.

🔧 为什么需要 HeartBeat？

Why is HeartBeat important?

在分布式系统中，节点可能因为故障掉线。为了保证系统能感知每个节点的健康状态，Hadoop 使用 HeartBeat：

功能	中英文说明
节点存活监测	NameNode 根据 HeartBeat 判断 DataNode 是否在线
→ Detects if a DataNode is alive
故障恢复触发	若超时未收到 HeartBeat，则认为 DataNode 故障，开始数据副本恢复
→ Triggers block replication if DataNode fails
任务调度辅助	Hadoop 可将 MapReduce 任务调度到“活跃的”DataNode 上执行
→ Used to aid in task assignment

⏱️ 默认心跳频率：

每 3 秒 发一次 HeartBeat（可配置）
Default is every 3 seconds
如果 超过 10 分钟未收到 → 该节点被视为失联
Considered dead if no heartbeat in 10 minutes (default)

🔄 HeartBeat 携带的信息

HeartBeat 不只是“我还活着”，还会携带如下信息：

信息项	英文说明
存储使用情况	Disk usage / free space
数据块报告	Which blocks the DataNode stores
节点负载	Load / CPU usage

🖼️ 工作流程图简化：

   +------------------+
   |     NameNode     |
   +--------+---------+
            ▲
HeartBeat   |   Block Reports
            |
   +--------▼--------+
   |     DataNode     |
   +------------------+

✅ 一句话总结：

HeartBeat 是保障 Hadoop 分布式存储高可用性的“生命信号机制”，负责节点健康监测与数据副本恢复。
HeartBeat is the vital mechanism in Hadoop that ensures fault detection and triggers recovery in the HDFS cluster.

✅ 4. MapReduce（计算框架）

MapReduce 计算模型

编程模式：将计算任务分成 Map 和 Reduce 两个阶段
Split → Map → Shuffle → Reduce → Output

📌 如何编写 Map/Reduce 函数？

How to Write Map/Reduce Function

Map 函数：提取键值对
Reduce 函数：对相同 key 的值集合进行聚合操作（如求和、计数等）

✅ 5. Spark 编程模型

Spark Programming Model

RDD（弹性分布式数据集） 是 Spark 的核心抽象
RDD = Resilient Distributed Dataset

🔹 两类操作：

类型 Type	说明 Description
Transformation	转换操作（惰性，lazy）
Action	行动操作（触发计算）

例如：

1
2
3

rdd = sc.textFile("data.txt")
rdd2 = rdd.map(lambda x: x.upper())  # Transformation
rdd2.count()                         # Action → 触发执行

✅ 6. MapReduce vs. Spark 对比

MapReduce 与 Spark 对比

比较项 Comparison	MapReduce	Spark
编程复杂度	高，需写 Map 和 Reduce	简洁，链式函数式编程
性能	慢，需反复读写磁盘	快，支持内存迭代处理
数据抽象	无	RDD、DataFrame
支持机器学习	弱（需外部框架）	强（MLlib 内置）

✅ 总结一句话：

Hadoop 提供了可靠的分布式数据存储和离线计算框架；Spark 在其基础上实现了高效的内存计算，适合更复杂的实时分析与机器学习任务。
Hadoop offers reliable storage and batch computing; Spark improves efficiency with in-memory processing and better developer APIs.

如你需要为 Spark RDD 模型画图、生成函数结构图，或者举几个 MapReduce 的实际例子，我可以继续为你补充！

Chapter 1 - Introduction to Big Data Mining

1. What’s Big Data?

2. The 4Vs of Big Data（四个特性）

3. What’s Data Mining?

4. Main Tasks of Data Mining

Chapter 2 - Subspace Learning

一、Curse of Dimensionality（维度灾难）

二、Dimensionality Reduction（降维）

① Linear Methods

📌 Principal component analysis PCA（主成分分析）

📌 Multidimensional scaling MDS（多维缩放）

② Nonlinear Methods

包括：

三、Subspace Clustering（子空间聚类）

① Sparse Subspace Clustering (SSC)

思路：

② Low-Rank Representation (LRR)

✅ Chapter 3 - Hashing（哈希技术）详解

📌 主题核心：

✅ 1. Why? 动机与背景

✅ 2. k-shingles（或 k-grams）

✅ 3. MinHash（最小哈希）：Jaccard 相似度近似计算

① Definition（定义）

📌 EN:

📌 中文：

② Signature Matrix（签名矩阵）

📌 EN:

📌 中文：

③ Properties of Signature Matrix: Approximation（性质：近似性）

📌 EN:

📌 中文：

✅ 总结 Recap

✅ 4. LSH（Locality Sensitive Hashing）：加速相似查找

🎯 Objective（目标）

📌 EN:

📌 中文：

🧠 Trick（技巧）

📌 EN:

📌 中文：

📊 数学解释

✅ 小结 Recap

✅ 5. Find Similar Item

✅ 6. Learn to Hash（学习哈希）

🎯 What is “Learn to Hash”?

📌 EN:

📌 中文：

📌 方法一：Random Projection 随机投影

EN:

中文：

📌 方法二：PCA Hashing 主成分哈希

EN:

中文：

📌 方法三：Spectral Hashing 谱哈希

EN:

中文：

✅ 总结对比表

🧾 总结表

✅ Chapter 4: Sampling（采样）

① Rejection Sampling 拒绝采样

📌 EN:

📌 中文：

② Importance Sampling 重要性采样

📌 EN:

📌 中文：

🔁 对比 RS vs IS：

③ MCMC Sampling 马尔可夫链蒙特卡洛采样

基本思想（Basic Idea）：

📌 EN:

📌 中文：

三种典型方法：

🔹 (a) Metropolis-Hastings (MH) 采样

🔹 (b) Gibbs Sampling 吉布斯采样

🔁 Gibbs Sampling vs MH：

✅ 总结 Recap（中英文对照）

📘 CH5. Data Stream Mining 数据流挖掘

✅ ① Challenges of DSM（数据流挖掘的挑战）

Single Pass Handling（单遍处理）

Memory Limitation（内存限制）

Low Time Complexity（低时间复杂度）

Concept Drift（概念漂移）