ISLR读书笔记二十：聚类分析（Clustering）_综合

聚类分析

前言
K均值聚类
分层聚类
- 系统树图
- 算法
- 相异性测度的选择
其他考虑

前言

上一篇讲到的 PCA 旨在发现能较好代表高维空间的低维空间，而这篇要讲的聚类分析（Clustering）则旨在发现具有相同或类似性质的子空间。常见的聚类方法有：K均值聚类（K-means clustering）和分层聚类（hierarchical clustering）。

K均值聚类

K均值聚类将原空间划分成 $K$ 个不相交的子空间，其出发点是使得每个空间内数据尽可能地靠近，即方差尽可能地小。
$minimize?C1,…,CK{∑k=1KW(Ck)}\underset{C_{1}, \ldots, C_{K}}{\operatorname{minimize}}\left\{\sum_{k=1}^{K} W\left(C_{k}\right)\right\}$
如果按欧式距离来计算的话，那么 $W(C_k)$ 可以取
$W(Ck)=1∣Ck∣∑i,i′∈Ck∑j=1p(xij?xi′j)2W\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}$
这里 $C_k|$ 指第 $k$ 个类（cluster）的数据个数。
那么此时即解决如下优化问题：
$minimize?C1,…,CK{∑k=1K1∣Ck∣∑i,i′∈Ck∑j=1p(xij?xi′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\}$
直接计算该优化问题是复杂的，但是可以用如下算法得到一个比较好的局部最优解：

对每一个观测数据，随机分配 $1$ 到 $K$ ，作为初始聚类。
进行如下迭代直到停止：
（a）对于每一个类，计算其中心（centroid），即该类所有数据的均值。
（b）将每一个观测数据分配给距离它最近的中心所属的类。

分层聚类

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$ 类
对于 $i=n,n?1,?,2:i=n,n-1,\cdots,2:$
（a）找出 $i$ 个类中每两个类之间的连接最紧密的，将其融合。两个类之间的连接反映了系统树图中融合位置的高度。
（b）计算剩余 $i ? 1$ 个类每两个类之间的连接。

相异性测度的选择

相异性测度通常可以选择欧式距离或相关性距离（correlation-based distance）。两者高度相关时，相关性距离小，反之则大。不同的相异性测度的选择，对最终结果也会有很大影响。

其他考虑

在进行聚类分析时，还需要考虑一下问题：

原始数据是否要进行标准化？
如果进行分层聚类，选择什么相异性测度？选择什么连接？在系统树图的哪里进行分类？
K均值聚类问题如何选择 $K$
聚类是否反映了真实的分类？是否有价值？