Cluster Analysis 期末复习笔记：Basic + Advanced

以下笔记严格以两份课件为主线整理：Chapter 7 Cluster Analysis: Basic Concepts and Methods 与 Chapter 8 Cluster Analysis: Advanced Concepts and Algorithms 。我会把课件中的概念、算法、公式、优缺点、比较和图示结论全部纳入，并特别指出几处课件公式中可能影响考试理解的笔误。

重要程度：

★★★★★：核心公式 / 算法流程 / 高频比较，必须会
★★★★☆：重要概念与 failure mode
★★★☆☆：需要理解，可能出选择/简答
★★☆☆☆：背景、例子、延伸内容

0. 先建立整章“进化树” ★★★★★

这两章真正讨论的不是“有哪些 clustering algorithm”，而是一个更根本的问题：

没有标签时，什么叫“一个自然的 cluster”？
一旦我们选择了某种 cluster definition，又应该怎样高效找到它，并判断结果是否真的有意义？

整个知识体系可以整理成：

text

Cluster Analysis
│
├─ 1. 什么叫 cluster？
│   ├─ Well-separated
│   ├─ Prototype-based
│   ├─ Contiguity / connectivity-based
│   ├─ Density-based
│   └─ Objective/model-based
│
├─ 2. Prototype 路线
│   │
│   ├─ K-means
│   │   ├─ SSE objective
│   │   ├─ Assignment ↔ centroid update
│   │   └─ 问题：局部最优、初始化、形状/密度/尺寸限制
│   │
│   ├─ initialization improvement
│   │   ├─ multiple runs
│   │   ├─ K-means++
│   │   ├─ hierarchical initialization
│   │   └─ Bisecting K-means
│   │
│   ├─ Hard assignment 不够
│   │       ↓
│   ├─ Fuzzy C-means
│   │   └─ membership weight + fuzzifier
│   │
│   └─ “权重能否具有概率意义？”
│           ↓
│       Mixture Model + EM
│       ├─ distribution parameters
│       ├─ posterior responsibility
│       └─ covariance → elliptical clusters
│
├─ 3. Connectivity 路线
│   │
│   ├─ Hierarchical clustering
│   │   ├─ Single Link / MIN
│   │   ├─ Complete Link / MAX
│   │   ├─ Group Average
│   │   └─ Ward
│   │
│   └─ 问题：linkage 是 static criterion
│           ↓
│       Chameleon
│       ├─ sparse kNN graph
│       ├─ graph partitioning
│       └─ dynamic merging:
│           Relative Interconnectivity + Relative Closeness
│
├─ 4. Density 路线
│   │
│   ├─ DBSCAN
│   │   ├─ eps
│   │   ├─ MinPts
│   │   ├─ core / border / noise
│   │   └─ arbitrary shape + noise handling
│   │
│   └─ 问题：
│       ├─ varying densities
│       └─ high dimensionality
│
├─ 5. Density + efficiency / high-dimensional structure
│   │
│   ├─ Grid-based clustering
│   │
│   └─ Subspace clustering
│       └─ CLIQUE
│           ├─ grid
│           ├─ density threshold
│           └─ Apriori-style monotonic pruning
│
└─ 6. Evaluation
    ├─ Internal / Unsupervised
    │   ├─ SSE
    │   ├─ SSB
    │   ├─ Calinski-Harabasz
    │   ├─ Silhouette
    │   ├─ correlation
    │   └─ reordered similarity matrix
    │
    ├─ External / Supervised
    │   ├─ Entropy
    │   └─ Purity
    │
    └─ Statistical significance
        └─ 与 random-data null distribution 比较

这棵树是整两章最重要的“逻辑记忆框架”。

Part I. Cluster Analysis 的基本概念

1. Cluster Analysis 到底是什么？ ★★★★★

课件定义：

给定一组对象，把对象分成若干组，使得同一个组中的对象彼此相似，而不同组中的对象彼此不同。

理想上：

同时

因此 clustering 也可以理解为：

但要注意，这个名字只是帮助理解。与 supervised classification 最大区别在于：

classification 预先存在 class label；
clustering 中连“什么是正确的类”本身都是未知的。

这直接导致后面一个关键困难：

cluster 的定义具有 ambiguity。

课件第 6 页同一组数据可以合理解释成 2、4 或 6 个 cluster。

所以：

这也是为什么 clustering evaluation 会比 classification evaluation 困难得多。

2. Cluster Analysis 的两个主要用途 ★★★☆☆

2.1 Understanding

发现数据中的潜在结构。

课件例子：

document grouping；
功能相似的 genes / proteins；
价格波动相似的 stocks；
根据降水模式对澳大利亚区域进行聚类。

2.2 Summarization

用少量 cluster representations 替代大量数据点。

例如：

因此 clustering 本身也可以是一种 data reduction / summarization 技术。

3. Clustering 的不同组织形式 ★★★★☆

3.1 Partitional clustering

把数据划分为一组互不重叠的 subsets：

典型：

K-means
DBSCAN（虽然允许 noise，因此严格说是 partial clustering）

3.2 Hierarchical clustering

不是给出单一 partition，而是一组 nested clusters。

最终表现为一棵 hierarchical tree：

用 dendrogram 表示 merge / split sequence。

例如：

text

                 all points
                 /        \
              C1            C2
             / \           / \
           ... ...       ... ...

在不同高度切 dendrogram，就得到不同数量的 clusters。

这解释了 hierarchical clustering 一个重要优势：

不需要一开始指定唯一的。

课件第 9 页还用图示区分了 traditional 与 non-traditional hierarchical organization，但没有给出额外文字定义；考试重点仍然是 nested clusters 与 dendrogram。

4. Exclusive、Fuzzy、Partial、Complete ★★★★☆

这些术语很容易混。

类型	含义
Exclusive	一个 point 只属于一个 cluster
Non-exclusive	一个 point 可属于多个 clusters
Fuzzy	对每个 cluster 都有 membership weight
Complete	所有点必须被分到某个 cluster
Partial	可以有点不属于任何 cluster

Fuzzy clustering：

并满足：

其中：

：第个 data point；
：第个 cluster；
：对 cluster 的 membership。

Probabilistic clustering 与 fuzzy clustering 表面非常类似，但后面会看到：

fuzzy membership 是 optimization weight；
EM 中 membership 是概率意义明确的 posterior probability。

5. “Cluster”到底可以怎样定义？ ★★★★★

这是后续算法选择最重要的概念框架。

5.1 Well-separated cluster

要求 cluster 内任意一点与同 cluster 中所有点都比 cluster 外的点更接近。

形式化可以理解为：

这是非常强的定义。

5.2 Prototype-based cluster

核心思想：

一个点属于离它最近的 prototype 所代表的 cluster。

即：

prototype 经常就是 centroid：

K-means 正是这种 cluster notion。

适合：

compact；
globular；
centroid meaningful 的数据。

5.3 Contiguity / Connectivity / Graph-based cluster

要求一个 point 与 cluster 内至少一些点存在紧密连接。

相比 well-separated：

well-separated 要“和 cluster 内所有点都近”；
contiguity 只需要能通过局部邻接“连接起来”。

因此它可以形成：

text

●—●—●—●—●—●

即使最左和最右两个点距离很远，它们仍然可以因为 connectivity 属于同一 cluster。

Single-link hierarchical clustering 就体现了这种 notion。

5.4 Density-based cluster

定义：

cluster 是一个 high-density region，并由 low-density region 与其他 high-density regions 分离。

非常适合：

irregular shapes；
intertwined clusters；
noise；
outliers。

DBSCAN 是典型方法。

5.5 Objective-function-defined cluster

另外一种思路不是先给几何定义，而是：

理论上可以：

枚举所有 partitions；
计算每个 partition 的 goodness；
选择 objective 最优者。

但一般：

所以实际算法寻找近似解或 local optimum。

课件还区分：

hierarchical algorithms 通常使用 local objectives；
partitional algorithms 通常采用 global objectives。

另一个扩展是：

例如 mixture models：

假设数据来自多个 statistical distributions 的 mixture。

6. 输入数据本身会决定 clustering 的行为 ★★★★☆

课件强调 proximity / density measure 是 clustering 的核心。

影响 clustering 的数据属性包括：

dimensionality；
sparseness；
attribute type；
attribute scales；
special relationships，例如 autocorrelation；
distribution；
noise；
outliers；
不同 cluster 的 size；
density；
shape。

因此：

算法选择必须和“你认为什么叫 cluster”一起考虑。

Part II. K-means：Prototype-Based Clustering

7. K-means 基础算法 ★★★★★

K-means 是：

partitional；
prototype-based；
complete；
hard / exclusive；
要求预先指定。

给定：

初始化：

然后交替进行两个步骤。

7.1 Assignment Step

对每个点：

其中：

：被分配到的 cluster index；
：cluster 的 centroid。

直觉：

固定 centers 后，每个点独立选择使自己的 error 最小的 center。

7.2 Update Step

固定 cluster assignments 后：

即每个 cluster 的 arithmetic mean。

不断执行：

text

initialize centroids
       ↓
assignment
       ↓
update centroid
       ↓
assignment
       ↓
...
until convergence

停止条件：

centroid 不再变化；
或变化小于 threshold。

课件第 19–21 页给出了这一完整机制。

8. K-means 的目标函数：SSE ★★★★★

使用 Euclidean distance 时：

其中：

：cluster 数；
：第个 cluster；
：的 centroid；
：cluster 内的数据点。

SSE 越小：

9. 为什么 centroid 必须是 mean？ ★★★★★

这一点最好自己会推。

固定某个 cluster 后：

对求导：

令其为 0：

所以：

因此 mean 并不是拍脑袋选的：

它正是 squared Euclidean error 的最优 representative。

10. 为什么 K-means 会收敛？ ★★★★★

每次 iteration 包含两个步骤。

固定 centroid，优化 assignment

每个点选择最近 centroid：

所以 SSE 不增加。

固定 assignment，优化 centroid

mean 是当前 cluster SSE 的最优解。

所以 SSE 仍然不增加。

因此：

SSE 又满足：

因此目标值单调不增并有下界。注意：这本身只推出 SSE 值收敛，不足以单独证明算法在有限步停止；Lloyd K-means 的有限终止还要利用 assignment 的可能数有限、assignment 改变时 SSE 严格下降、确定性 tie-breaking，并处理 empty cluster。

但是：

只能保证到 local minimum。

课件第 22 页就展示了：

optimal K-means clustering；
sub-optimal clustering。

11. Initialization 为什么是 K-means 的核心痛点？ ★★★★★

因为 objective 是 non-convex。

不同初始 centroids：

课件第 23–29 页通过多个迭代图展示：

某些初始化最后能够自己“调整回来”，另一些不会。

11.1 课件中的 initialization probability

假设存在个真实 clusters，每个 cluster 有个点。

课件给出：

并写为：

例如：

得到：

也就是约：

这说明增大时，随机初始化刚好覆盖所有真实 cluster 的概率非常低。

严谨备注

课件这一计算实际上采用了独立抽取（有放回）或大样本近似。标准 K-means 初始化通常不会重复抽同一个 point；若从个点中无放回抽取个，严格概率为：

小样本时它不一定只“略有”区别。

但考试如果要求复述课件结论：

就是课件答案。

12. 如何缓解 initialization 问题？ ★★★★★

课件给出四条路线：

方法	核心思想
Multiple runs	多跑几次，选择最低 SSE
Widely separated centers	尽量选相互分离的 initial centroids
K-means++	更稳健地选分离的初始中心
Hierarchical initialization	用 hierarchical clustering 产生 seeds
Bisecting K-means	避免一次性随机放置全部 centers

13. K-means++ ★★★★☆

课件强调两个结论：

相比纯 random initialization，可能更慢；
但通常获得明显更好的 SSE。

同时给出了理论保证：

expected approximation ratio。

意思是其 expected objective 与最优 K-means objective 之间存在 logarithmic approximation guarantee。

课件没有详细展开完整 sampling algorithm，因此对期末而言最重要的是：

K-means++ = 更合理、更分散的 centroid initialization，解决 K-means 对初始化高度敏感的问题。

14. Bisecting K-means ★★★★☆

Bisecting K-means 是 K-means 的 variant，同时具有：

partitional interpretation；
hierarchical interpretation。

核心思想可以概括为：

text

all points
    ↓
split one cluster using K-means with K=2
   / \
  C1 C2
     ↓
select cluster to split again
     ↓
repeat

优点：

不需要同时随机初始化个 centers，因此不如标准 K-means 那么容易遭遇严重的 initialization failure。

课件第 32–33 页主要以定义与图示为主，没有进一步给出严格 split-selection criterion。

15. K-means 的结构性局限 ★★★★★

K-means 的问题并不只是 initialization。

课件明确列出了：

以及：

为什么？

因为 K-means 的 implicit geometry 是：

每个 cluster 用一个 center 表示，并通过离哪个 center 最近来划分空间。

这产生 Voronoi-style boundaries：

天然更适合 compact / roughly spherical clusters。

15.1 Differing sizes

大 cluster 的 points 数量多，对 SSE 的贡献也大。

算法可能为了降低大 cluster 的 SSE，而牺牲小 cluster。

15.2 Differing density

如果两个 cluster density 差别很大：

dense cluster 中 centroid 很稳定；
sparse cluster 中 points 分布范围大；

distance-to-center criterion 未必与真实 density structure 一致。

15.3 Non-globular shapes

比如：

text

(((((
     )))))

即使人类看到明显两个 curved clusters，单一 centroid 无法表达这种 structure。

15.4 Outlier sensitivity

centroid 是 arithmetic mean：

一个极端 outlier 可以显著移动 centroid。

课件给出的一个办法：

clustering 前删除 outliers。

16. 一种绕过 K-means shape limitation 的办法 ★★★☆☆

课件第 38–40 页给出：

先用较大的，把 natural cluster 分成很多 small clusters，再进行 post-processing，把属于同一 natural cluster 的小 cluster 合并。

即：

text

complex cluster
      ↓
over-clustering with K-means
      ↓
many local globular pieces
      ↓
post-processing merge
      ↓
complex natural cluster

这一思想实际上已经在向后面的 graph / hierarchical hybrid 方法靠近。

Part III. Hierarchical Clustering

17. 为什么需要 hierarchical clustering？ ★★★★★

K-means 强迫我们先选。

Hierarchical clustering 则生成：

最后由用户切 dendrogram。

两个主要优势：

不必事先假定唯一；
hierarchy 本身可能具有意义。

例如：

text

animal
 └─ dog
     └─ sheepdog

18. Agglomerative vs Divisive ★★★★★

Agglomerative：bottom-up

开始：

不断 merge 最近的两个 clusters。

直到：

只剩一个 cluster；
或只剩目标个 clusters。

Divisive：top-down

开始：

然后不断 split。

直到：

每个 point 独立；
或得到 clusters。

课件重点讲 Agglomerative。

19. Agglomerative clustering algorithm ★★★★★

基本算法：

text

1. Compute proximity matrix.
2. Let each data point be a cluster.
3. Repeat:
4.     Merge the two closest clusters.
5.     Update proximity matrix.
6. Until one cluster remains.

真正决定算法行为的是：

由此得到：

MIN / Single Link
MAX / Complete Link
Group Average
centroid distance
Ward's method

20. MIN / Single Link ★★★★★

定义：

两个 clusters 的距离 = 两个 clusters 之间最近一对 points 的距离。

形式化：

它实际上只依赖“一条 link”。

优点

因为只需要局部连接起来。

例如：

text

●—●—●—●—●

最终可以形成一个很长的 curved cluster。

缺点

一个 noise chain：

text

Cluster A ●
          ·
           ·
            ·
             ● Cluster B

可能把两个本应分开的 cluster 连在一起。

这就是经典 chaining effect。

21. MAX / Complete Link ★★★★★

定义：

两 clusters 的距离由最远的一对 points 决定。

相比 MIN：

一个孤立 bridging point 不容易使两个 cluster merge；
因此对 noise 更 robust。

优点

缺点

课件明确给出：

tends to break large clusters；
biased toward globular clusters。

因为它要求：

merge 后 cluster 内所有点之间都不能太远。

因此很长的 cluster 会被认为不够 cohesive。

22. Group Average ★★★★★

定义：

相当于综合两个 clusters 所有 cross-pair distances。

可以理解为：

课件称其为 MIN 与 MAX 的 compromise。

Strength

less susceptible to noise。

Limitation

biased towards globular clusters。

23. Ward's Method ★★★★★

Ward 不直接问：

最近的点是谁？

而问：

如果把两个 clusters 合并，SSE 会增加多少？

定义：

选择使 SSE increase 最小的一对 clusters。

课件指出：

less susceptible to noise；
biased toward globular clusters；
hierarchical analogue of K-means；
可以用于初始化 K-means。

23.1 Ward 的关键公式推导

对于两个 clusters：

size：
centroids：

合并后：

可以推出：

直觉非常重要：

Ward 同时考虑：

centroid distance；
cluster size。

因此它与 K-means 的 squared-error worldview 高度一致。

24. 四种 hierarchical linkage 总比较 ★★★★★

方法	Merge criterion	Shape tendency	Noise	核心问题
MIN / Single	最近 point pair	arbitrary / elongated	差	chaining
MAX / Complete	最远 point pair	globular	较好	breaks large clusters
Group Average	cross-pair average	globular	较好	compromise
Ward	minimum increase in SSE	globular	较好	K-means-like bias

一个非常好记的逻辑：

text

MIN：只怕“有没有一条桥”
MAX：怕“最远的人是不是太远”
Average：看整体关系
Ward：看 merge 之后 SSE 恶化多少

25. Hierarchical clustering 的计算复杂度 ★★★★☆

课件给出：

空间：

因为需要 proximity matrix。

朴素时间：

原因：

次 merge；
每次要搜索/update 接近的 matrix。

通过优化可降到：

这一复杂度也在 Chapter 8 的 MIN vs EM 比较中再次出现。

26. Hierarchical clustering 的根本 limitation ★★★★★

最重要的一条：

也就是 greedy irreversible decision。

其次：

没有直接最小化统一的 global objective；
sensitivity to noise；
不同 sizes；
non-globular shapes；
breaking large clusters。

注意：

不同 linkage 的问题不同。

不存在一个 linkage 全部解决。

Part IV. Density-Based Clustering 与 DBSCAN

27. Density-based clustering 的核心转变 ★★★★★

Prototype 方法问：

point 离哪个 center 最近？

Connectivity 方法问：

point 与哪些邻居连接？

Density-based 方法问：

这里是不是一个 high-density region？

因此：

这使得 centroid 不再是必要概念。

28. DBSCAN 的两个参数 ★★★★★

表示 neighborhood radius。

表示形成 dense neighborhood 所需的 minimum number of points。

定义：

29. Core / Border / Noise ★★★★★

Core point

如果：

那么是 core point。

课件特别强调：

counts the point itself。

也就是说自己也计入 MinPts。

Border point

不是 core：

但位于某个 core point 的 neighborhood 内。

Noise point

既不是：

core；
也不是 border。

即：

30. DBSCAN clustering mechanism ★★★★★

课件将算法概括为：

用 core points 形成 clusters，再将 border points 分给其 neighboring cluster。

可以理解为：

text

core -- core -- core -- core
  \       \
 border   border

isolated point → noise

core points 通过 density connectivity 形成 cluster backbone。

31. DBSCAN 为什么比 K-means 更适合 irregular shape？ ★★★★★

因为 DBSCAN 没有：

这个强假设。

只要 high-density region 能连续连接：

text

C-shaped
spiral-shaped
elongated

都可以成为 cluster。

课件给出的优点：

different shapes；
different sizes；
noise resistant。

32. DBSCAN 什么时候失败？ ★★★★★

课件明确指出两个问题。

32.1 Varying densities

如果一个 cluster 很 dense，一个很 sparse：

eps 太小：
- dense cluster OK；
- sparse cluster 被拆散/noise。
eps 太大：
- sparse cluster OK；
- dense regions 可能被错误连接。

因此：

32.2 High-dimensional data

维度升高后：

distance concentration；
neighborhood density distinction 变弱；
“附近”越来越难定义。

即 curse of dimensionality。

33. 如何选择 eps？k-distance plot ★★★★★

课件方法：

对每一个 point；
求其第个 nearest neighbor 的距离；
将所有这些距离排序；
画 k-distance curve。

cluster 内 points：

noise：

在：

text

dense region
       ______
      /
_____/ ← elbow

附近选择 eps。

核心就是找：

Part V. Clustering Evaluation

34. 为什么 clustering evaluation 特别重要？ ★★★★★

因为即使是 random data：

K-means 仍然能输出个 clusters；
complete-link 仍能产生 hierarchy；
DBSCAN 在某些参数下也能给出结构。

所以：

课件列出 evaluation 的四种目的：

avoid finding patterns in noise；
compare clustering algorithms；
compare two clusterings；
compare individual clusters。

35. Internal vs External Evaluation ★★★★★

Unsupervised / Internal index

不使用外部 label。

例如：

SSE；
Silhouette。

Supervised / External index

将 cluster labels 与 externally supplied class labels 比较。

例如：

Entropy；
Purity。

这里千万别混：

clustering algorithm 本身仍是 unsupervised。
只是 evaluation 阶段可以利用 ground-truth class label。

36. Cohesion 与 Separation ★★★★★

Cohesion

表示：

cluster 内 points 有多紧密。

课件用：

越小越好：

Separation

使用 between-cluster sum of squares：

其中：

：cluster centroid；
：整个 dataset centroid；
：cluster size。

越大：

通常 cluster separation 越好。

37. 为什么 SSE + SSB 是常数？ ★★★★★

有经典 decomposition：

其中：

完全由 dataset 本身决定。

课件第 83 页例子：

数据：

overall mean：

所以：

clusters：

means：

于是：

而：

因此：

仍然等于 SST。

结论：

对于固定数据集成立。

38. Graph-based cohesion / separation ★★★☆☆

如果使用 proximity graph：

Cohesion

cluster 内部 edge weights 之和：

Separation

cluster 和 cluster 外部 points 的 cross-edge weights：

具体“高/低哪个更好”需要看 edge weight 定义为 similarity 还是 distance。

39. Calinski-Harabasz Index ★★★★★

课件给出的公式：

其中：

：clusters 数；
：样本数；
：between-cluster variation；
：within-cluster variation。

理想情况：

且：

因此：

可以理解为：

并经过 degrees-of-freedom normalization。

40. Silhouette Coefficient ★★★★★

这是非常适合计算题的一条公式。

对于 point ：

Step 1：

point 与自己 cluster 内其他 points 的平均距离：

表示：

若是 singleton，没有可平均的其他点；通常约定该点的 silhouette 为，或仅对 cluster size 至少为 2 的点使用这条公式。

Step 2：

分别计算到其他每个 cluster 的平均距离，再取最小值：

即：

nearest alternative cluster。

Step 3：Silhouette

范围：

含义：

自己 cluster 内很近、其他 cluster 很远。

很好。

位于 cluster boundary。

反而离别的 cluster 更近：

很可能被 misclustered。

可以对整个 cluster 或 clustering 求平均 silhouette。

41. Correlation-based evaluation ★★★★☆

构建两个 matrices：

Proximity Matrix

表示 point 的 proximity。

Ideal Similarity Matrix

然后：

因为 matrices symmetric，只需使用：

个 unique pair entries。

若写完整 Pearson correlation：

符号为什么可能正也可能负？

如果是 similarity：

所以：

如果是 distance：

但 ideal similarity 是 1。

于是：

因此课件强调：

而不是盲目要求。

课件例子：

well-clustered：

random data：

Correlation evaluation 的 limitation

课件明确指出：

对某些 density-based / contiguity-based clusters 不好。

为什么？

一个 C-shape cluster 中：

两个点在 graph topology 上属于同 cluster；
但 Euclidean distance 可以非常大。

因此 pairwise distance correlation 不一定匹配真正 cluster notion。

42. Similarity Matrix Visual Inspection ★★★☆☆

把 points 根据 cluster labels reorder。

理想 clustering 会出现明显 block-diagonal structure：

text

████
████

     ████
     ████

          ███
          ███

随机数据得到的 cluster 通常：

blocks 不够 crisp。

这是一种可视化 cluster validity 方法。

43. 如何通过 SSE 估计正确的？ ★★★★★

随着增大：

一定不会上升（这里指给定下的全局最优值）。

实际把 K-means 分别随机初始化后运行，得到的是局部解，因此某次运行的可能反而高于某次运行的；实践中应多次初始化并比较。

极端情况下：

所以不能简单选 minimum SSE。

需要找：

即：

text

SSE
│\
│ \
│  \
│   \__
│      \____
└──────────── K
       ↑
     elbow

含义：

在 elbow 之前，增加 cluster 能显著减少 error；
elbow 之后，边际收益显著下降。

课件第 93 页也提醒：

对 complicated data，elbow 可能并不明显。

44. Entropy ★★★★★

这是 supervised / external evaluation。

对于 cluster ，令：

：cluster 中 points 数；
：其中属于 ground-truth class 的 points 数；
：ground-truth classes 数。

先计算：

cluster entropy：

整体 entropy：

其中：

：clusters 数；
：总 samples。

Interpretation

如果 cluster 完全由一种 class 构成：

则：

所以：

cluster 越混杂：

45. Purity ★★★★★

cluster ：

整体：

解释：

看每个 cluster 中占比最大的 true class 有多 dominant。

范围：

越高越好：

注意 purity 有一个典型 conceptual trap：

如果：

每个 point 一个 cluster，则：

所以不能单独依靠 purity 判断。

46. Statistical Significance of Clustering ★★★★★

这是 Chapter 7 最容易被忽略、但思想很重要的一部分。

问题：

假设一个 clustering index：

那么 10 到底：

good？
fair？
poor？

没有 reference distribution，就无法解释。

课件提出 statistical framework：

也就是构造 null distribution。

46.1 SSE example

真实 cohesive clusters：

课件生成 500 个 random datasets，每个：

100 points；
位于约；
都做成 3 clusters。

random SSE 大约落在：

真实数据的：

极端小。

因此：

这个 clustering 结果 unlikely under randomness，更有理由认为存在真实 structure。

46.2 Correlation example

同理，把 observed correlation 与 random datasets 的 correlation histogram 比较。

核心思想就是：

Chapter 7 最后的引用也强调：

clustering validation 是整个 cluster analysis 中最困难的部分之一。

Part VI. Advanced Prototype-Based Clustering

47. 为什么从 K-means 走向 Fuzzy C-means？ ★★★★★

K-means 假设：

一个点只能属于一个 cluster。

但现实中很多 point 位于：

cluster boundary；
overlapping categories；
ambiguous regions。

于是自然想：

48. 直接把 hard weight 放松为 continuous 为什么还不行？ ★★★★★

先从 generalized K-means objective：

约束：

如果只是：

能产生 fuzzy membership 吗？

答案：

48.1 课件例子

distances squared：

于是：

且：

代入：

得到：

这是一个 linear function。

所以 minimum 一定在 constraint interval 边界：

最终仍然是 hard assignment。

这一步是 Fuzzy C-means 的真正 motivation：

49. Fuzzy C-means：加入 fuzzifier ★★★★★

目标函数改为：

约束：

且：

称为：

控制 clustering 有多“fuzzy”。

Chapter 8 从这里开始把 K-means 的 hard prototype model 推广为 soft clustering。

50. Fuzzy C-means membership update 的推导 ★★★★★

固定 centers。

对于一个 point ，令：

优化：

subject to：

构造 Lagrangian：

求导：

因此：

于是：

normalize 后：

这就是课件第 8 页的 update formula。

51. fuzzifier 到底干什么？ ★★★★☆

看：

若：

则：

nearest centroid 会得到几乎全部 weight：

而增大：

距离差异被弱化：

更接近均匀：

52. Fuzzy example + 课件中的一个明显笔误 ★★★★★

仍然：

课件使用：

约束：

因此：

求导：

得到：

此时：

课件第 7 页写的是：

但：

违反前面明确规定的：

所以这里几乎可以确定是 slide typo。

正确应接近：

而课件给出的 minimum：

也与一致。

这一点期末计算时不要被 slide 的 0.36 带偏。

53. Fuzzy C-means centroid update：第二处值得注意的公式问题 ★★★★★

课件第 8 页打印为：

但是它前面定义的 objective 是：

严格对求导：

因此应得到：

也就是标准 Fuzzy C-means update。

所以课件中的 update-centroid 公式少了 exponent ，与其 own objective 不一致。

考试如果是：

“根据 objective 推导” → 应写；
“机械复述 slide” → 注意 slide 显示的是未加 power 的版本。

从数学严谨性而言：

54. Fuzzy C-means 算法总流程 ★★★★★

text

randomly initialize membership weights
subject to Σ_j w_ij = 1
              ↓
compute centroids
              ↓
update memberships according to distances
              ↓
compute centroids
              ↓
...
until convergence

与 K-means 的核心形式仍然是：

只是：

K-means：

FCM：

55. Fuzzy clustering 的 application ★★☆☆☆

课件给出 image segmentation，特别是：

fMRI；
MRI segmentation。

并列举了 modified fuzzy c-means applications，包括：

Gong et al. 2013 的 local-information + kernel metric FCM；
Ahmed et al. 2002 的 modified FCM for MRI bias field estimation / segmentation。

考试大概率知道“image segmentation 是 application”即可。

Part VII. Mixture Models 与 EM

56. 为什么从 Fuzzy 再走向 Mixture Models？ ★★★★★

Fuzzy C-means 的 membership：

本质仍然由一个人为设计的 objective 决定。

更进一步可以问：

能不能给 membership 一个真正的 statistical probability interpretation？

于是得到：

基本假设：

最常见：

但课件强调其他 distributions 也可以使用。

57. Mixture model 如何定义 cluster？ ★★★★★

假设：

个 distributions：

以及 cluster priors：

满足：

总体 density：

因此：

一个 cluster 不再只是一个 center，而是一整套 distribution parameters。

例如 Gaussian：

58. Gaussian density ★★★★★

一维 normal distribution 的标准形式：

其中：

：mean；
：standard deviation；
：variance。

只要估计：

就可以完整描述一维 Gaussian cluster。

在多维中则扩展成：

其中 covariance matrix 允许：

unequal axis lengths；
rotated ellipses；
correlated dimensions。

所以 Gaussian mixture 比 K-means 能表示更一般的 elliptical cluster。

59. EM 的核心结构 ★★★★★

Expectation-Maximization：

text

Initialize parameters
       ↓
E-step
compute probability that each point belongs to each distribution
       ↓
M-step
use these probabilities to re-estimate distribution parameters
       ↓
repeat until parameters stop changing

课件明确强调：

它的 structure 与 K-means 非常相似。

比较：

K-means	EM
nearest-center hard assignment	posterior probability
recompute mean	update distribution parameters
minimize SSE	maximize likelihood
hard	soft/probabilistic

60. E-step：Bayes Rule ★★★★★

posterior responsibility：

定义：

则：

这和 fuzzy membership 很像。

但区别：

而不是普通 optimization weight。

61. M-step：更新 mean ★★★★★

课件公式：

即：

这是 probability-weighted mean。

62. 更新 mixture weight / prior ★★★★★

课件：

即：

直觉：

cluster 的 prior proportion = dataset 中“有效属于该 cluster 的质量”占比。

63. 更新 variance ★★★★★

课件一维公式：

即：

多维对应 covariance：

后一个公式是课件的一维公式自然推广，课件第 18 页也明确把高维 complexity 归因于 covariance matrix。

64. EM 与 Fuzzy C-means 的关系 ★★★★★

二者的 centroid 更新形式很像：

FCM：

EM：

但：

FCM

人为 optimization membership。

EM

由：

likelihood；
cluster prior；
distribution parameters

共同决定。

所以：

65. 为什么 K-means 是 mixture model 的 special case？ ★★★★★

课件直接指出：

直观上，当 Gaussian components：

variance 相同；
covariance spherical；
mixture priors 相等；
posterior 趋于 hard assignment；

最大 posterior cluster 就几乎等于：

共同固定 spherical covariance 与相等 prior 时，MAP assignment 才等价于最近 centroid；若 prior 不同，决策边界会额外受 prior 项影响。此时 EM：

退化为：

即 K-means。

66. Mixture Model 相比 K-means 修复了什么？ ★★★★☆

K-means 只学习：

所以 K-means 的分区是 Euclidean Voronoi cells，并偏好以单个 centroid 为代表的 compact、近似球状结构；它们并非字面意义上的 spherical cluster：

Gaussian EM 还学习：

因此可以表达：

different spread；
elliptical shapes；
rotated axes；
some different densities。

这解释课件第 17 页 “dense and sparse clusters” 的例子：

分布模型可以通过 variance/covariance 表达不同 spread，而不是所有 cluster 都只用一个裸 centroid。

67. EM 的问题 ★★★★★

课件列出四类。

67.1 Slow convergence

67.2 Local maxima

所以 initialization 依旧重要。

课件建议 Gaussian mixture 经常：

use K-means to initialize。

67.3 Statistical assumptions

如果假设：

但真实数据不符合 distribution assumptions，model misspecification 会影响结果。

67.4 Parameter explosion in high dimension

对于 -dimensional Gaussian：

mean：

个参数。

full covariance：

虽然 symmetric 后 independent entries 是：

数量级仍然：

所以 EM：

而 K-means 只估计 mean：

这就是为什么高维下 full Gaussian mixture 更难估计。

68. Alternatives to EM ★★☆☆☆

课件只点名：

Method of moments；
Spectral methods；
MCMC；
other approaches。

没有展开算法。

因此期末大概率只需知道：

EM 并不是 mixture parameter estimation 的唯一方法。

Part VIII. Grid-Based 与 Subspace Clustering

69. 为什么从 DBSCAN 走向 Grid-Based？ ★★★★☆

DBSCAN 基本操作发生在：

grid-based clustering 把空间先 discretize：

然后 cluster cells 而非逐点分析。

因此：

70. Basic Grid-Based Algorithm ★★★★★

下面是帮助理解的通用 grid-based 流程（课件第 21 页只给出 grid-based 的概念；完整的课件 Algorithm 9.5 是后面的 CLIQUE）：

Step 1

Define grid cells。

Step 2

将 objects 分到对应 cells，并计算 cell density。

若：

可以把 density 理解为：

或 normalized version。

Step 3

删除：

的 cells。

Step 4

把 contiguous / adjacent dense cells 合并成 clusters。

即：

text

points
 ↓
grid
 ↓
count density
 ↓
remove sparse cells
 ↓
connected dense cells
 ↓
clusters

71. 为什么需要 Subspace Clustering？ ★★★★★

此前所有 clustering 基本默认：

且使用全部 dimensions。

但高维数据可能存在：

cluster A 只在 dimensions 有结构；
cluster B 只在有结构。

所以：

这就是 subspace clustering。

72. CLIQUE ★★★★★

CLIQUE 是：

它：

在不同 subspaces 中划分 equal-volume grid units；
计算每个 unit 包含 points 的 fraction；
density 超过 threshold 的 unit 为 dense；
contiguous dense units 构成 cluster。

若总点数：

unit 中：

则 density fraction 可以写：

dense condition：

73. CLIQUE 最大的 computational problem ★★★★★

个 dimensions 有：

量级 subspaces。

如果暴力枚举：

不可行。

怎么办？

引入：

74. CLIQUE 的 Apriori-style monotonicity ★★★★★

课件原理：

如果一组 points 在某个 -dimensional subspace 中都不能形成 dense cluster，那么在包含这些 dimensions 的任何 superspace 中也不可能形成 dense cluster。

逻辑形式：

反过来：

这和 frequent pattern mining 的 Apriori property 完全同构：

因此：

CLIQUE 用 low-dimensional dense cells 产生 high-dimensional candidates。

这是 Chapter 3/4 pattern mining 与 clustering 的一个重要知识连接。

75. CLIQUE Algorithm 9.5 ★★★★★

课件第 28 页完整流程：

1.

找到所有 1-D dense regions。

2. 3–4.

从 dense -D cells 生成 candidate dense -D cells。

5.

删除少于个 points 的 cells：

这里是 count threshold。

和前面的 fraction threshold 可以联系：

6.

7.

直到没有新的 candidate dense cells。

8.

取所有 adjacent high-density cells 的 union：

9.

用少量 inequalities 描述 cluster：

例如：

也就是说 CLIQUE 不仅找 cluster，还可以产生 compact subspace descriptions。

76. CLIQUE 可以发现 overlapping clusters ★★★★☆

因为不同 cluster 可能存在于不同 feature subsets：

同一个 point 可以同时参与不同 subspace structures。

所以课件特别指出：

77. CLIQUE limitations ★★★★★

课件明确四点。

1. Exponential time in dimensionality

Apriori pruning 只是减少，不消除 worst-case exponential behavior。

2. Too many dense low-dimensional units

如果 lower stages 产生大量 dense candidates：

3. Fixed density threshold

如果真实 clusters：

一个 global 很难兼顾。

这一 failure 与 DBSCAN global eps 问题本质类似：

4. Parameter selection

很难选择：

threshold；
grid interval length。

78. 一个需要特别说明的目录问题

Chapter 8 的 outline 明确列出了：

kernel-based: DENCLUE；
Jarvis-Patrick；
Shared Nearest Neighbor (SNN)。

但实际这份 59 页课件中：

CLIQUE 后直接进入 Graph-Based Clustering；
graph section 实质只展开 Chameleon；
没有 DENCLUE 的定义、公式或算法；
没有 Jarvis-Patrick 的算法页；
没有 SNN 的算法页。

因此这里不能从课件凭空补内容。

期末复习上可以记：

如果老师没有课堂另行补充，不应把它们和 Chameleon 放在同等复习优先级。

Part IX. Graph-Based Clustering 与 Chameleon

79. Graph-based clustering 的 general framework ★★★★★

先建立 proximity graph：

其中：

每个 point 是一个 vertex；
edge weight 表示两个 points 的 proximity。

很多 hierarchical algorithms 都能重新解释成 graph operation。

例如：

MIN

merge：

被 lowest-distance edge 连接的两个 subgraphs。

Group Average

merge：

average connectivity 高的两个 subgraphs。

最简单时：

80. 为什么 proximity graph 需要 sparsification？ ★★★★★

完整 proximity matrix：

有：

connections。

但大部分远距离 relationships 对 clustering 没什么用。

因此：

只保留最重要 connections。

课件给出了非常强的数字：

可以消除 proximity matrix 中超过 99% 的 entries。

带来：

processed data 大幅减少；
clustering time 大幅减少；
能处理更大 dataset；
clustering 结果可能更好。

为什么“更好”？

因为通常保留：

同时删除：

因此：

noise / outlier influence 减弱；
cluster boundaries 更清楚。

81. 为什么传统 hierarchical merging scheme 不够？ ★★★★★

这是 Chameleon 的直接 motivation。

传统 scheme 是 static：

MIN

永远只看：

Group Average

永远只看：

问题：

同样的 absolute distance / connectivity，在不同 cluster 自身结构下意义完全不同。

例如两个本身极度 dense 的 clusters：

text

very dense A   moderate link   very dense B

即使 cross-link 看起来不算小，相对其 internal density 可能仍然非常弱。

反之两个 sparse clusters：

text

sparse A -- moderate link -- sparse B

同样一条 link 可能已经非常强。

所以真正应该判断的是：

而不是绝对关系。

82. Chameleon 的核心思想：Dynamic Modeling ★★★★★

目标：

adapt to characteristics of the dataset to find natural clusters。

关键：

两个 clusters 是否应该 merge，不仅看：

absolute closeness；
absolute connectivity；

而看：

Relative Interconnectivity；
Relative Closeness。

83. Relative Interconnectivity (RI) ★★★★★

课件公式：

其中：

连接 clusters 的 kNN graph edges 的 total weight。

如果把 bisect：

minimum sum of cut-edge weights。

即自身的 internal connectivity strength。

类似地：

RI 的意义

如果：

意味着：

两个 cluster 连接强度与各自内部相当：

如果：

则：

说明两者更像独立 clusters。

因此：

84. Relative Closeness (RC) ★★★★★

课件公式：

其中：

；
；
：连接两 clusters 的 edges 的 average weight；
：bisect 时 cut edges 的 average weight；
：同理。

分母为什么 size weighted？

是两个 cluster size proportion。

因此 baseline internal closeness 更符合 merge 后 cluster 的 composition。

RC interpretation

表示：

两 clusters 之间的 closeness 与各自内部 closeness 相当。

适合 merge。

若：

表示：

cross-cluster points 远没有 cluster 内部那么 close。

不适合 merge。

85. RI 与 RC 为什么必须同时考虑？ ★★★★★

RI 测：

RC 测：

可以理解：

RI 更像 structural connectivity；
RC 更像 proximity strength。

仅靠一种都可能误判。

Chameleon 的关键不是单纯换了一个 linkage：

这就是 “dynamic modeling”。

86. Chameleon 完整 workflow ★★★★★

Preprocessing

构造：

一个 point 只连接自己的 nearest neighbors。

课件强调：

neighborhood dynamically captured，即使 local region 比较 sparse。

Phase 1：Graph partitioning

使用：

把 graph 分成很多 small, well-connected subclusters。

目标不是一开始就找到最终 clusters，而是保证：

即主要来自某个真实 cluster。

Phase 2：Hierarchical Agglomerative Merging

再对这些 subclusters 做 HAC。

但 merge rule 不再 static，而基于：

RI；
RC。

完整逻辑：

text

Data points
   ↓
k-NN graph
   ↓
sparsification
   ↓
multilevel graph partition
   ↓
many pure subclusters
   ↓
dynamic hierarchical merge
using RI + RC
   ↓
natural clusters

87. Chameleon 与 CURE 的课件实验图 ★★★☆☆

Chapter 8 p.42–48 连续比较了：

CHAMELEON；
CURE with fixed numbers of clusters，如 9、10、15。

图中数据包含：

elongated；
nested / curved；
differing densities；
differing sizes

等结构。

视觉结果的核心教学目的不是学习 CURE 算法——课件没有展开 CURE mechanism——而是展示：

Chameleon 依据 cluster 内部结构动态 merge，能比固定 static notion 更稳定地恢复复杂 natural clusters。

因此 CURE 在这份课件中主要是 experimental comparator，而不是考试算法主体。

Part X. 如何选择 Clustering Algorithm？

88. 先看 Data Characteristics ★★★★☆

Chapter 8 总结：

High dimensionality

可能需要：

Attribute types

包括：

binary；
discrete；
continuous；
asymmetric；
mixed type。

Scale differences

需要 normalization。

Dataset size

决定 scalability。

Noise / outliers

决定 robustness 需求。

Data space

非常重要的问题：

centroid 是否 meaningful？
density 是否 meaningful？

89. 再看 Cluster Characteristics ★★★★☆

需要考虑：

data distribution；
parametric or non-parametric；
shape：
- globular；
- arbitrary；
size differences；
density differences；
separation；
relationships among clusters；
subspace clusters。

90. 再看 Algorithm Characteristics ★★★★☆

课件给出四个：

最终算法选择可以按照：

text

Need taxonomy?
   ↓
hierarchical

Need flat partition?
   ↓
partitional

Centroid meaningful + globular?
   ↓
K-means / EM

Need probabilities / ellipses?
   ↓
EM

Arbitrary shape + noise?
   ↓
DBSCAN

Subspace structure?
   ↓
CLIQUE

Connectivity / complex topology?
   ↓
MIN / Chameleon

Part XI. 课件最后两个“大比较题”

这两组非常像期末简答题。

91. MIN vs EM Clustering ★★★★★

课件假设 EM 使用 Gaussian distributions。

维度	MIN / Single Link	EM
clustering type	hierarchical	partitional
complete?	yes	yes
cluster notion	graph / contiguity	prototype / model
poorly separated clusters	较差	往往能处理
arbitrary shapes	强	更偏 globular/elliptical
different sizes	强	可能困难
different densities	困难	往往可处理
subspace clusters	不支持	不支持
outliers	可处理	outlier 影响可能很强
noise	noise 可能 bridge clusters	可容忍一些 noise
data requirement	meaningful proximity	meaningful centroid/model
high dimension	合理 proximity 下可工作	covariance 参数
data type	proximity matrix 屏蔽底层 type	主要为 Euclidean，虽有扩展
distribution assumption	none	Gaussian assumption
time complexity		课件记作
deterministic	ties 外 deterministic	random init → non-deterministic
automatically find ?	no	no
parameters	构建树时通常不预设；最终切分仍要选 cut level	，possibly weights
mathematical view	graph model	optimization/model
order dependence	no	no

关于 EM 的

课件是在把：

；
；
iterations

看作 fixed constants 时只写对的 scaling。

更完整会是类似：

对于 full Gaussian covariance。

期末按 slide comparison：

即可。

92. DBSCAN vs K-means ★★★★★

维度	K-means	DBSCAN
type	partitional	partitional
complete	yes	no
cluster notion	prototype	density
	user specifies	automatically emerges
shape	globular	arbitrary
size	unequal size troublesome	handles different sizes
touching clusters	可分	touching high-density regions 会 merge
noise/outlier	poor	strong
requirement	meaningful centroid	meaningful density
high dimensional	某些高维数据仍可工作	poor
original design	Euclidean	Euclidean
distribution assumption	spherical-Gaussian-like	none
randomness	random init	课件视为 deterministic
parameters
time
formal objective	yes	no
relation to EM	special case	none

Advanced slides explicitly总结了这些差异。

课件把 DBSCAN 视为 deterministic。更精确地说，core point 所形成的 density-connected components 通常确定；但一个同时邻接多个 core clusters 的 border point，可能依处理顺序被分配到不同 cluster，因此完整 point-to-cluster 划分并非总是唯一。

关于 complexity 的考试口径

课件写：

这是固定 iterations 且 naive neighborhood search 下的简化。

因此考试优先记课件结论。

Part XII. 两章最重要的“方法演进逻辑”

93. Evolution 1：K-means → K-means++ / Bisecting K-means ★★★★★

K-means 的痛点

导致：

Fix

K-means++：

Bisecting K-means：

本质：

注意这一点。

它们没有解决：

non-globular；
varying density。

94. Evolution 2：K-means → Fuzzy C-means ★★★★★

Pain

Hard assignment：

无法表达 ambiguity。

Naive attempt

允许：

但 linear objective 仍然产生 boundary optimum：

Fix

加入：

使 objective curved：

从而产生：

的 interior optimum。

95. Evolution 3：Fuzzy C-means → Mixture/EM ★★★★★

Pain

FCM membership 是：

没有 distribution interpretation。

而 cluster 可能具有：

different variance；
elliptical geometry；
priors。

Fix

Mixture model：

membership 变成：

并通过 EM 学习：

mean；
variance/covariance；
prior。

因此：

96. Evolution 4：K-means → Hierarchical / DBSCAN ★★★★★

这里不是“优化 K-means”，而是：

彻底换 cluster definition。

K-means assumption

Connectivity

Density

所以 arbitrary shape 不是靠“把 K-means 调好”解决，而是需要：

这是整章最值得理解的 methodological lesson。

97. Evolution 5：Single/Group Average → Chameleon ★★★★★

Pain

传统 linkage：

只看 absolute relationship。

没有问：

这个 relationship 相对于 cluster 自己内部到底强不强？

Fix

Chameleon normalize by internal structure：

从：

变成：

98. Evolution 6：Full-space density → Grid → CLIQUE ★★★★★

Pain 1：point-level operations expensive

Grid：

降低操作粒度。

Pain 2：high-dimensional cluster 可能只存在于少数 dimensions

Subspace clustering：

Pain 3：所有 subspaces 是 exponential

CLIQUE 引入：

所以逻辑是：

text

density notion
   ↓
grid discretization
   ↓
search subspaces
   ↓
combinatorial explosion
   ↓
monotonic pruning

Part XIII. 最终公式总表 ★★★★★

建议考前最后直接看这一节。

内容	公式
K-means assignment
K-means centroid	$\displaystyle \mu_j=\frac1{
K-means SSE
Init probability（课件）
Single Link
Complete Link
Group Average	$\displaystyle D=\frac1{
Ward
DBSCAN core	$\displaystyle
SSB
Variance decomposition
CH
Silhouette
FCM objective
FCM constraint
FCM membership
FCM centroid（严格推导）
Gaussian
EM posterior
EM mean
EM prior
EM variance
CLIQUE density	$\displaystyle \rho(u)=
RI
RC
Entropy
Overall entropy
Purity
Overall purity

Part XIV. 期末最容易混淆的 15 个点 ★★★★★

K-means 收敛不等于 global optimum。
K-means++ 解决 initialization，不解决 arbitrary shape。
Single Link 能处理 non-globular shape，但容易 chaining。
Complete Link 更抗 noise，但偏好 globular cluster，且可能 break large cluster。
Ward 本质上是 hierarchical version of SSE/K-means thinking。
DBSCAN 的 MinPts 包括 point 自己。
DBSCAN 的 cluster number 不需要事先指定。
DBSCAN 是 partial clustering，因为允许 noise。
SSE 随增大自然下降，所以不能直接通过 minimum SSE 选。
Silhouette：接近 1 好，接近 0 boundary，负数可能 miscluster。
Correlation sign 取决于 proximity 是 similarity 还是 distance，重点看 magnitude。
仅把从放松到不会产生真正 fuzzy solution；需要。
Fuzzy membership ≠ EM posterior probability。
EM 能表示 ellipse 的关键不是 soft assignment，而是 covariance matrix。
CLIQUE 和 Apriori 的共同思想都是 monotonicity + candidate pruning。

Part XV. 这两份课件里需要警惕的两处公式问题

这是我特别建议你考试前圈出来的地方。

Fuzzy C-means p.7

课件写：

但同时要求：

所以明显不一致。

根据其 own objective：

且正好得到课件给出的：

所以第二个数应当接近：

而不是 0.36。

Fuzzy C-means p.8

课件 objective 是：

但 centroid update 打印成：

严格求导应为：

这两处都来自 Chapter 8 的 Fuzzy C-means 部分。

最后的考试级总框架

如果你在考场上突然忘了某种 clustering algorithm，可以先问自己三个问题：

然后你几乎能把整章重新推出来：

K-means：near same centroid → SSE → globular / initialization failure。
Hierarchical MIN：connected by nearest links → arbitrary shape → chaining/noise。
MAX：all points remain close → robust to noise → break elongated/large cluster。
Ward：merge with smallest SSE increase → K-means-like → globular bias。
DBSCAN：density connectivity → arbitrary shapes/noise → varying density/high-d failure。
FCM：soft distance membership → ambiguity → still prototype geometry。
EM：mixture distribution → posterior probability/covariance → assumptions + parameters + local maxima。
CLIQUE：dense grid cells in subspaces → solve irrelevant dimensions → exponential dimension search。
Chameleon：graph connectivity relative to internal structure → repair static linkage → dynamic RI/RC merging。
Evaluation：cohesion + separation + external agreement + statistical significance。

如果只剩最后一小时复习，优先顺序建议是：

其中真正应该做到“看到空白纸能完整写出来”的，是：K-means 的 SSE 与交替优化、Single/MAX/Average/Ward 的差异、DBSCAN 的 core-border-noise、SSE/SSB/CH/Silhouette、FCM membership 推导、EM 的 E/M 更新，以及 Chameleon 的 RI/RC。

高密度复习：Cluster Analysis

方法选择地图

方法	cluster notion	优势	主要限制
K-means	centroid / SSE	快、易解释	需；偏好 compact/近球状；怕 initialization/outlier
HAC	linkage hierarchy	不预设即可建 dendrogram	；切分层仍要选
DBSCAN	density connectivity	任意形状、能标 noise	/MinPts 敏感；变密度/高维困难
FCM	fuzzy membership	表达边界模糊	membership 不等于概率；受初值影响
GMM + EM	probabilistic components	covariance 可表达椭圆/不同 spread	假设与局部极值；参数多
Grid / CLIQUE	dense cells / subspace	高维子空间、速度依赖 grid	网格粒度敏感

必写公式

算法检查清单

K-means：assignment 和 centroid update 都使 SSE 不增；有限终止还须有限 assignment、严格改进/tie-handling 等条件。随不增，但独立随机运行的局部解不保证。
Linkage：MIN/single 易 chaining；MAX/complete 偏 compact；average 折中；Ward 每步最小化 SSE 增量。
DBSCAN：core 有至少 MinPts 邻域点；border 可达但非 core；noise 既非 core 也非 border。core components 通常确定，但多簇可达的 border assignment 可能依顺序。
Evaluation：cohesion 小、separation 大；internal 无 label，external 用 class label。singleton 的 silhouette 通常约定为 0。
EM：E-step 求 posterior ；M-step 更新。普通 K-means 是共同 fixed spherical covariance、equal priors 与 hard assignment 条件下的特例。

高频对比与课件陷阱

FCM 的是模糊归属度，GMM 的才是模型 posterior；两者不要等同。
课件 initialization 概率是有放回/近似；无放回时。
K-means 分区是 Euclidean Voronoi cells；“spherical Gaussian”只是带条件的模型解释。
grid-based 的通用流程与课件的 CLIQUE Algorithm 9.5 要分开记；HAC 建树不预设，但最终仍需要 cut level。

Cluster Analysis 期末复习笔记：Basic + Advanced ​

0. 先建立整章“进化树” ★★★★★ ​

Part I. Cluster Analysis 的基本概念 ​

1. Cluster Analysis 到底是什么？ ★★★★★ ​

2. Cluster Analysis 的两个主要用途 ★★★☆☆ ​

2.1 Understanding ​

2.2 Summarization ​

3. Clustering 的不同组织形式 ★★★★☆ ​

3.1 Partitional clustering ​

3.2 Hierarchical clustering ​

4. Exclusive、Fuzzy、Partial、Complete ★★★★☆ ​

5. “Cluster”到底可以怎样定义？ ★★★★★ ​

5.1 Well-separated cluster ​

5.2 Prototype-based cluster ​

5.3 Contiguity / Connectivity / Graph-based cluster ​

5.4 Density-based cluster ​

5.5 Objective-function-defined cluster ​

6. 输入数据本身会决定 clustering 的行为 ★★★★☆ ​

Part II. K-means：Prototype-Based Clustering ​

7. K-means 基础算法 ★★★★★ ​

7.1 Assignment Step ​

7.2 Update Step ​

8. K-means 的目标函数：SSE ★★★★★ ​

9. 为什么 centroid 必须是 mean？ ★★★★★ ​

10. 为什么 K-means 会收敛？ ★★★★★ ​

固定 centroid，优化 assignment ​

固定 assignment，优化 centroid ​

11. Initialization 为什么是 K-means 的核心痛点？ ★★★★★ ​

11.1 课件中的 initialization probability ​

严谨备注 ​

12. 如何缓解 initialization 问题？ ★★★★★ ​

13. K-means++ ★★★★☆ ​

14. Bisecting K-means ★★★★☆ ​

15. K-means 的结构性局限 ★★★★★ ​

15.1 Differing sizes ​

15.2 Differing density ​

15.3 Non-globular shapes ​

15.4 Outlier sensitivity ​

16. 一种绕过 K-means shape limitation 的办法 ★★★☆☆ ​

Part III. Hierarchical Clustering ​

17. 为什么需要 hierarchical clustering？ ★★★★★ ​

18. Agglomerative vs Divisive ★★★★★ ​

Agglomerative：bottom-up ​

Divisive：top-down ​

19. Agglomerative clustering algorithm ★★★★★ ​

20. MIN / Single Link ★★★★★ ​

优点 ​

缺点 ​

21. MAX / Complete Link ★★★★★ ​

优点 ​

缺点 ​

22. Group Average ★★★★★ ​

Strength ​

Limitation ​

23. Ward's Method ★★★★★ ​

23.1 Ward 的关键公式推导 ​

24. 四种 hierarchical linkage 总比较 ★★★★★ ​

25. Hierarchical clustering 的计算复杂度 ★★★★☆ ​

26. Hierarchical clustering 的根本 limitation ★★★★★ ​

Part IV. Density-Based Clustering 与 DBSCAN ​

27. Density-based clustering 的核心转变 ★★★★★ ​

28. DBSCAN 的两个参数 ★★★★★ ​

29. Core / Border / Noise ★★★★★ ​

Core point ​

Border point ​

Noise point ​

30. DBSCAN clustering mechanism ★★★★★ ​

31. DBSCAN 为什么比 K-means 更适合 irregular shape？ ★★★★★ ​

32. DBSCAN 什么时候失败？ ★★★★★ ​

32.1 Varying densities ​

32.2 High-dimensional data ​

33. 如何选择 eps？k-distance plot ★★★★★ ​

Part V. Clustering Evaluation ​

34. 为什么 clustering evaluation 特别重要？ ★★★★★ ​

35. Internal vs External Evaluation ★★★★★ ​

Unsupervised / Internal index ​

Supervised / External index ​

36. Cohesion 与 Separation ★★★★★ ​

Cohesion ​

Separation ​

Cluster Analysis 期末复习笔记：Basic + Advanced

0. 先建立整章“进化树” ★★★★★

Part I. Cluster Analysis 的基本概念

1. Cluster Analysis 到底是什么？ ★★★★★

2. Cluster Analysis 的两个主要用途 ★★★☆☆

2.1 Understanding

2.2 Summarization

3. Clustering 的不同组织形式 ★★★★☆

3.1 Partitional clustering

3.2 Hierarchical clustering

4. Exclusive、Fuzzy、Partial、Complete ★★★★☆

5. “Cluster”到底可以怎样定义？ ★★★★★

5.1 Well-separated cluster

5.2 Prototype-based cluster

5.3 Contiguity / Connectivity / Graph-based cluster

5.4 Density-based cluster

5.5 Objective-function-defined cluster

6. 输入数据本身会决定 clustering 的行为 ★★★★☆

Part II. K-means：Prototype-Based Clustering

7. K-means 基础算法 ★★★★★

7.1 Assignment Step

7.2 Update Step

8. K-means 的目标函数：SSE ★★★★★

9. 为什么 centroid 必须是 mean？ ★★★★★

10. 为什么 K-means 会收敛？ ★★★★★

固定 centroid，优化 assignment

固定 assignment，优化 centroid

11. Initialization 为什么是 K-means 的核心痛点？ ★★★★★

11.1 课件中的 initialization probability

严谨备注

12. 如何缓解 initialization 问题？ ★★★★★

13. K-means++ ★★★★☆

14. Bisecting K-means ★★★★☆

15. K-means 的结构性局限 ★★★★★

15.1 Differing sizes

15.2 Differing density

15.3 Non-globular shapes

15.4 Outlier sensitivity

16. 一种绕过 K-means shape limitation 的办法 ★★★☆☆

Part III. Hierarchical Clustering

17. 为什么需要 hierarchical clustering？ ★★★★★

18. Agglomerative vs Divisive ★★★★★

Agglomerative：bottom-up

Divisive：top-down

19. Agglomerative clustering algorithm ★★★★★

20. MIN / Single Link ★★★★★

优点

缺点

21. MAX / Complete Link ★★★★★

优点

缺点

22. Group Average ★★★★★

Strength

Limitation

23. Ward's Method ★★★★★

23.1 Ward 的关键公式推导

24. 四种 hierarchical linkage 总比较 ★★★★★

25. Hierarchical clustering 的计算复杂度 ★★★★☆

26. Hierarchical clustering 的根本 limitation ★★★★★

Part IV. Density-Based Clustering 与 DBSCAN

27. Density-based clustering 的核心转变 ★★★★★

28. DBSCAN 的两个参数 ★★★★★

29. Core / Border / Noise ★★★★★

Core point

Border point

Noise point

30. DBSCAN clustering mechanism ★★★★★

31. DBSCAN 为什么比 K-means 更适合 irregular shape？ ★★★★★

32. DBSCAN 什么时候失败？ ★★★★★

32.1 Varying densities

32.2 High-dimensional data

33. 如何选择 eps？k-distance plot ★★★★★

Part V. Clustering Evaluation

34. 为什么 clustering evaluation 特别重要？ ★★★★★

35. Internal vs External Evaluation ★★★★★

Unsupervised / Internal index

Supervised / External index

36. Cohesion 与 Separation ★★★★★

Cohesion

Separation