聚类分析

监督学习：有标签
无监督学习：给定数据，或者例子，但是没有标签

无监督学习可学习没有任何标签的聚类/群组，可应用于客户细分（即分组）、图像压缩、生物信息学。

另一类无监督学习：建模（模型的概率/参数）。例如学习翻译词典、语言的语法和社交图等。

聚类：通过对数据特征进行学习，将一组对象分组为类似对象的过程。

聚类算法

扁平算法：通常以一个随机的（部分的）划分开始
- 迭代优化：K均值聚类、基于模型的聚类
- 谱聚类
分层算法
- 从上到下：凝聚
- 从下到上：分裂

硬聚类和软聚类

硬聚类：每个数据只属于一个类

软聚类：一个数据可以属于多个类（概率），这对于创建可浏览层次结构等应用程序更有意义

谱聚类和K-均值算法已经写过，可以见Hc's blog: 聚类和主成分

这里再作稍许补充

参考高惠璇的《应用多元统计分析》，浙江大学mooc中所讲述的K-均值聚类其实为动态聚类中的按批修改法，按批修改法是当样本全部归类后才改变凝聚点。另一种自然的想法是对一个样品进行分类后，同时改变凝聚点，这就产生了逐个修改法，也被称作K-均值法。
距离的定义有很多，欧式距离适合空间数据，余弦距离适合文本数据。
谱聚类常使用离差平方和法（WARD），谱聚类不要求数据高斯分布，没有球形假设（K-均值）或椭圆形假设（EM聚类）。

后文详细介绍EM聚类

EM聚类：高斯混合模型（GMM）

假设数据从高斯混合分布（椭圆数据）产生，以一定的概率分配一个点到聚类中心，结果为分组的概率（软聚类）。

EM算法 $\mathbf{X}$ $\mathbf{Z}$ $\Theta$ $\Theta$ 做极大似然估计，则应最大化对数似然

LL(\Theta \mid \mathbf{X}, \mathbf{Z})=\ln P(\mathbf{X}, \mathbf{Z} \mid \Theta).

$\mathbf{Z}$ $\mathbf{Z}$ 计算期望，来最大化已观测数据的对数 “边际似然”(marginal likelihood)

LL(\Theta \mid \mathbf{X})=\ln P(\mathbf{X} \mid \Theta)=\ln \sum_{\mathbf{Z}} P(\mathbf{X}, \mathbf{Z} \mid \Theta).

$]$ 是常用的估计参数隐变量的利器，它是一种迭代式的方法，其基本想法是：

$\Theta$ $\mathbf{Z}$ $\mathrm{E}$ 步）；
$,$ $\mathbf{Z}$ $\Theta$ $\mathrm{M}$ 步 ) 。

$m$ 个样本

\begin{aligned} LL(\Theta \mid \mathbf{X}, \mathbf{Z})&=\ln P(\mathbf{X}, \mathbf{Z} \mid \Theta)=\sum_{i=1}^m\ln\sum_{z^{(i)}}P(x^{(i)},z^{(i)}|\Theta)\\&=\sum_{i=1}^m\ln\sum_{z^{(i)}}Q_i(z^{(i)})\frac{P(x^{(i)},z^{(i)}|\Theta)}{Q_i(z^{(i)})}\\&\geq\sum_{i=1}^m\sum_{z^{(i)}}Q_i(z^{(i)})\ln\frac{P(x^{(i)},z^{(i)}|\Theta)}{Q_i(z^{(i)})}. \end{aligned}

$Q_i$ $Z$ $Q_i(z^{(i)})=P(z^{(i)}|x^{(i)},\Theta)$ $\sum_{z^{(i)}}Q_i(z^{(i)})=1$ .

$\ln$ $f(E[X])\geq E[f(X)]$ $\frac{P(x^{(i)},z^{(i)}|\Theta)}{Q_i(z^{(i)})}$ 为常数，即

\frac{P(x^{(i)},z^{(i)}|\Theta)}{Q_i(z^{(i)})}=c.

而

\frac{P(x^{(i)},z^{(i)}|\Theta)}{Q_i(z^{(i)})}=\frac{P(x^{(i)},z^{(i)}|\Theta)}{P(z^{(i)}|x^{(i)},\Theta)}=P(x^{(i)}|\Theta),

$\Theta$ 固定的条件下为常数，因此等号成立。

由此，EM算法可以改写为

$\Theta$ $\mathbf{Z}$ $\mathrm{E}$ $Q_i(z^{(i)}):=P(z^{(i)}|x^{(i)},\Theta)$ $LL(\Theta \mid \mathbf{X},\mathbf{Z}):=\sum_{i=1}^m\sum_{z^{(i)}}Q_i(z^{(i)})\ln\frac{P(x^{(i)},z^{(i)}|\Theta)}{Q_i(z^{(i)})}$ ；
$\mathbf{Z}$ $\Theta$ $\mathrm{M}$ $\Theta:=\arg\max_\Theta LL(\Theta \mid \mathbf{X},\mathbf{Z})$ .

EM算法应用广泛，如训练HMM（Baum-Welch算法），学习贝叶斯网络的概率，EM-聚类，学习单词对齐语言翻译，学习微信好友网络等。

EM聚类

$Q_i(z^{(i)})$ $i\ (i\in\{1,...,m\})$ $z^{(i)}$ $\mathbf{X}$ $k$ $z^{(i)}\in\{1,...,k\}$ $\{\alpha_1,...,\alpha_k\}:=\alpha$ $\sum_{i=1}^k\alpha_i=1$ $\mathbf{X}$ $n$ $x\sim N(\mu,\Sigma)$ .

于是其概率密度函数为

p(x)=\frac{1}{(2\pi)^{n/2}|\Sigma|^{1/2}}\cdot\exp^{-\frac 1 2 (x-\mu)^\top\Sigma^{-1}(x-\mu)}.

$\mathbf Z=\{z^{(1)},...,z^{(m)}\}$ $z^{(i)}\in\{1,...,k\}$ $x^{(i)}$ $\Theta=\{\alpha,\Sigma,\mu\}$ .

根据EM算法

$\Theta$ $\mathbf{Z}$ $\mathrm{E}$ $x^{(i)}$ $z^{(i)}=j$ 的概率

\gamma_j^i=Q_i(z^{(i)}=j)=P(z^{(i)}=j|x^{(i)},\alpha,\mu,\Sigma)=\frac{\alpha_j\cdot P(x^{(i)}|\mu_j,\Sigma_j)}{\sum_{l=1}^k\alpha_l\cdot P(x^{(i)}|\mu_l,\Sigma_l)}.

参数的似然函数为

LL(\alpha,\mu,\Sigma \mid \mathbf{X},\mathbf{Z})=\sum_{i=1}^m\sum_{z^{(i)}}Q_i(z^{(i)})\ln\frac{P(x^{(i)},z^{(i)}|\alpha,\mu,\Sigma)}{Q_i(z^{(i)})}.

$\mathbf{Z}$ $\Theta$ $\mathrm{M}$ 步 )：

\{\alpha,\mu,\Sigma\}=\arg\max_{\{\alpha,\mu,\Sigma\}} LL(\alpha,\mu,\Sigma \mid \mathbf{X},\mathbf{Z}).

$\mu_j:=\displaystyle\frac{\sum_{i=1}^m\gamma_{j}^ix_i}{\sum_{i=1}^m\gamma_{j}^i}$ $\Sigma_j:=\displaystyle\frac{\sum_{i=1}^m\gamma_j^i(x_i-\mu_j)(x_i-\mu_j)^\top}{\sum_{i=1}^m\gamma_j^i}$ $\alpha_j=\displaystyle\frac 1 m \sum_{i=1}^m\gamma^i_j$ .

$x^{(i)}$ $z^{(i)}=\arg\max_{j=1,...,k}\gamma_j^i$ .