ISLR读书笔记二十：聚类分析（Clustering）
前言
上一篇讲到的 PCA 旨在发现能较好代表高维空间的低维空间，而这篇要讲的聚类分析（Clustering）则旨在发现具有相同或类似性质的子空间。常见的聚类方法有：K均值聚类（K-means clustering）和分层聚类（hierarchical clustering）。
K均值聚类
K均值聚类将原空间划分成
K
K
K 个不相交的子空间，其出发点是使得每个空间内数据尽可能地靠近，即方差尽可能地小。
minimize
C
1
,
…
,
C
K
{
∑
k
=
1
K
W
(
C
k
)
}
\underset{C_{1}, \ldots, C_{K}}{\operatorname{minimize}}\left\{\sum_{k=1}^{K} W\left(C_{k}\right)\right\}
C1,…,CKminimize{k=1∑KW(Ck)}
如果按欧式距离来计算的话，那么
W
(
C
k
)
W(C_k)
W(Ck) 可以取
W
(
C
k
)
=
1
∣
C
k
∣
∑
i
,
i
′
∈
C
k
∑
j
=
1
p
(
x
i
j
−
x
i
′
j
)
2
W\left(C_{k}\right)=\frac{1}{\left|C_{k}\right|} \sum_{i, i^{\prime} \in C_{k}} \sum_{j=1}^{p}\left(x_{i j}-x_{i^{\prime} j}\right)^{2}
W(Ck)=∣Ck∣1i,i′∈Ck∑j=1∑p(xij−xi′j)2
这里
∣
C
k
∣
|C_k|
∣Ck∣ 指第
k
k
k 个类（cluster）的数据个数。
那么此时即解决如下优化问题：
minimize
C
1
,
…
,
C
K
{
∑
k
=
1
K
1
∣
C
k
∣
∑
i
,
i
′
∈
C
k
∑
j
=
1
p
(
x
i
j
−
x
i
′
j
)
2
}
\underset{C_{1}, \ldots, C_{K}}{\operatorname{minimize}}\left\{\sum_{k=1}^{K}\frac{1}{\left|C_{k}\right|} \sum_{i, i^{\prime} \in C_{k}} \sum_{j=1}^{p}\left(x_{i j}-x_{i^{\prime} j}\right)^{2}\right\}
C1,…,CKminimize⎩⎨⎧k=1∑K∣Ck∣1i,i′∈Ck∑j=1∑p(xij−xi′j)2⎭⎬⎫
直接计算该优化问题是复杂的，但是可以用如下算法得到一个比较好的局部最优解：
- 对每一个观测数据，随机分配 1 1 1 到 K K K，作为初始聚类。
- 进行如下迭代直到停止：
（a）对于每一个类，计算其中心（centroid），即该类所有数据的均值。
（b）将每一个观测数据分配给距离它最近的中心所属的类。
分层聚类
K均值聚类的一个缺点在于需要事先确定参数 K K K 的值。而分层聚类可以有效地避免这一问题。其主要思想是自底向上（bottom-up）地生成一个系统树图（dendrogram）。
系统树图
系统树图大致的思想是将一些类似的叶子（leaves）融合（fuse）成枝干（branches），再将类似的枝干进行融合，直至最终融合成一棵树，然后选择合适的树高，进行分类。
算法
其算法思想很简单：先把每一个观测数据分别作为一类，成为系统树图的底部，然后每次将两个最相似的类进行融合，直至最终成为一个单独的类。
这里用连接（linkage），来定义两个类之间的相异性（dissimilarity）。常见的连接有 Complete，Single，Average，Centroid。
| 连接 | 描述 |
|---|---|
| Complete | A类中的数据与B类中的数据的最大相异性 |
| Single | A类中的数据与B类中的数据的最小相异性 |
| Average | A类中的数据与B类中的数据的平均相异性 |
| Centriod | A类数据的中心与B类数据的中心的相异性 |
Average，complete，single是统计学家最常用的，Centriod 常用于基因组学（genomics）。
选择不同的连接，会产生不同的系统树图。
算法如下：
- 把 n n n 个观测数据独自看成一个类，总共 n n n 类
- 对于
i
=
n
,
n
−
1
,
⋯
,
2
:
i=n,n-1,\cdots,2:
i=n,n−1,⋯,2:
（a）找出 i i i 个类中每两个类之间的连接最紧密的，将其融合。两个类之间的连接反映了系统树图中融合位置的高度。
（b）计算剩余 i − 1 i-1 i−1 个类每两个类之间的连接。
相异性测度的选择
相异性测度通常可以选择欧式距离或相关性距离（correlation-based distance）。两者高度相关时，相关性距离小，反之则大。不同的相异性测度的选择，对最终结果也会有很大影响。
其他考虑
在进行聚类分析时，还需要考虑一下问题：
- 原始数据是否要进行标准化？
- 如果进行分层聚类，选择什么相异性测度？选择什么连接？在系统树图的哪里进行分类？
- K均值聚类问题如何选择 K K K
- 聚类是否反映了真实的分类？是否有价值？