主成分分析和聚类

主成分分析 PCA

根据散度（数据在某一特征中的分散程度）降低的顺序对特征进行排序，随后取前 $k$ 项；
计算原始 $n$ 维数据的散度值和协方差；
$cov (X_{i}, X_{j}) = E [(X_{i} - μ_{i}) (X_{j} - μ_{j})] = E [X_{i} X_{j}] - μ_{i} μ_{j}$
协方差矩阵可以被本征化，分解为一组本征向量和一组本征值，样本 $X$ 的最大方差位于最大本征值对应的本征向量上。
$M w_{i} = λ_{i} w_{i}$

K-Means 对聚类质心的初始位置的很敏感，可以多次运行算法，然后平均所有质心结果。

J (C) = \sum_{k = 1}^{K} \sum_{i \in C_{k}} ∥ x_{i} - μ_{k} ∥ \to min_{C}

D (k) = \frac{| J (C_{k}) - J (C_{k + 1}) |}{| J (C_{k - 1}) - J (C_{k}) |} \to min_{k}

不需要事先设置簇的数量
根据观测点之间的相似性来对数据进行聚类
相似性指标：负平方距离 $s (x_{i}, x_{j}) = - ∥ x_{i} - x_{j} ∥^{2}$
吸引度：样本 $x_{k}$ 适合作为 $x_{i}$ 的聚类中的的程度
$r_{i, k} \leftarrow s_{(} x_{i}, x_{k}) - max_{k^{'} \neq k} {a_{i, k^{'}} + s (x_{i}, x_{k}^{'})}$
归属度：样本 $x_{i}$ 选择 $x_{k}$ 作为聚类中心的合适程度
$a_{i, k} \leftarrow min (0, r_{k, k} + \sum_{i^{'} \notin {i, k}} max (0, r_{i^{'}, k})), i \neq k$ $a_{k, k} \leftarrow \sum_{i^{'} \neq k} max (0, r_{i^{'}, k})$

流程：
1. 首先将每个观测点都作为一个簇
2. 然后按降序对每两个簇中心之间距离进行排序
3. 取最近的两个相邻的簇并将它们合并为一个簇，然后重新计算簇中心
4. 重复步骤 2 和 3 ，直到所有观测点都合并到一个簇中
距离公式：
- 单连接
  $d (C_{i}, C_{j}) = min_{x_{i} \in C_{i}, x_{j} \in C_{j}} ∥ x_{i} - x_{j} ∥$
- 全连接
  $d (C_{i}, C_{j}) = max_{x_{i} \in C_{i}, x_{j} \in C_{j}} ∥ x_{i} - x_{j} ∥$
- 平均连接
  $d (C_{i}, C_{j}) = \frac{1}{n_{i} n_{j}} \sum_{x_{i} \in C_{i}} \sum_{x_{j} \in C_{j}} ∥ x_{i} - x_{j} ∥$
- 质心连接
  $d (C_{i}, C_{j}) = ∥ μ_{i} - μ_{j} ∥$
平均连接时间效率最高，不需要在每次合并后重算距离。
一般用树状图表示聚类过程

兰德指数
$RI = \frac{2 (a + b)}{n (n - 1)}$
其中， $n$ 是样本中数据点对数的数量、 $a$ 表示在真实标签与聚类结果中都是同类别的观测点对数、 $b$ 表示在真实标签与聚类结果中都是不同类别的观测点对数。
调整兰德指数
$ARI = \frac{RI - E [RI]}{max (RI) - E [RI]}$

其中， $K$ 是聚类结果、 $C$ 是原始数据。

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

其中， $a$ 是数据点与一个簇内其他观测点之间距离的平均值， $b$ 是观测点到最近簇的观测点的平均距离。