聚类
距离函数
对于点 $\mathbfit x=(x_1,\ldots x_n)^T$
- 欧式距离 Euclidean distance $\lVert\mathbfit x\rVert_2=\sqrt{\sum\lvert x_i\rvert^2}$
- 标准欧氏距离 Standard Euclidean distance $\sqrt{\sum\dfrac{(x_i-y_i)^2}{V_i}}$
$V_i$ 为第 $i$ 个观测量的方差 - 曼哈顿距离 Manhattan distance $\lVert\mathbfit x\rVert_1=\sum\lvert x_i\rvert$
- infinity norm $\lVert\mathbfit x\rVert_\infty=\max x_i$
- p 阶 Minkowski distance $\lVert\mathbfit x-\mathbfit y\rVert_p$
- 均值 $\mathbfit\mu=(\mu_1,\ldots\mu_n)^T$ , 协方差矩阵 $\mathbf\Sigma_{n\times n}$, $\sigma_{ij}=\mathrm{cov}(x_i, y_j)$. 协方差矩阵计算的是不同维度之间的协方差. 马哈拉诺比斯距离 Mahalanobis distance $D_M(\mathbfit{x})=\sqrt{(\mathbfit{x}-\mathbfit{\mu})^T\Sigma^{-1}(\mathbfit{x}-\mathbfit{\mu})}$
对于相同分布的 $\mathbfit{x}$ 和 $\mathbfit{y}$, $d(\mathbfit{x},\mathbfit{y})=\sqrt{(\mathbfit{x}-\mathbfit{y})^TS^{-1}(\mathbfit{x}-\mathbfit{y})}$ - 余弦相似性 Cosine similarity $\cos{\theta}=\dfrac{x⋅y}{\lVert x\rVert\lVert y\rVert}$
余弦距离 cosine distance $1-\cos{\theta}=1-\dfrac{x⋅y}{\lVert x\rVert_2\lVert y\rVert_2}$ - Correlation distance $1-\dfrac{(\mathbfit x-\bar x)(\mathbfit y-\bar y)}{\lVert\mathbfit x-\bar x\rVert_2\lVert\mathbfit y-\bar y\rVert_2}$
$\bar{x}$ 为 $\mathbfit{x}$ 的均值 - Hamming distance 信息论中，两个等长字符串之间的汉明距离 Hamming distance: 两个字符串对应位置的不同字符的个数
- Jensen-Shannon distance $\sqrt{\dfrac{D(p‖m)+D(q‖m)}2}$
- Chebyshev distance $\underset i\max \lvert x_i-y_i\rvert$
- Canberra distance $\sum_{i}\dfrac{\lvert x_i-y_i\rvert}{\lvert x_i\rvert+\lvert y_i\rvert}$
- Bray-Curtis distance $\dfrac{\sum_{i}\lvert x_i-y_i\rvert}{\sum_{i}\lvert x_i+y_i\rvert}$
- 对于逻辑变量 $\mathbfit{x}, \mathbfit{y}$ 由 $0,1$ 组成, $n_{ij}$ 表示 $x_k=i, y_k=j$ 的个数
- Jaccard distance $1-\dfrac{(n_{10}+n_{01})}{n_{11}+n_{10}+n_{01}}$
- Yule distance $1-\dfrac{2n_{10}n_{01}}{n_{11}n_{00}+n_{10}n_{01}}$
- Dice distance $1-\dfrac{n_{10}+n_{01}}{2n_{11}+n_{10}+n_{01}}$
- Kulsinski distance $1-\dfrac{n_{10}+n_{01}-n_{11}+n}{n_{10}+n_{01}+n}$
- Rogers-Tanimoto distance $1-\dfrac{2(n_{10}+n_{01})}{n_{11}+n_{00}+2(n_{10}+n_{01})}$
- Russell-Rao distance $1-\dfrac{n-n_{11}}{n}$
- Sokal-Michener distance $1-\dfrac{2(n_{10}+n_{01})}{n_{11}+n_{00}+2(n_{10}+n_{01})}$
聚类算法
层次聚类 hierarchical clustering
连接函数, 对于 cluster $u,\ v$, $u$ 由 $s,\ t$ 组成
- single linkage $\min(\textrm{dist}(u[i],v[j]))$
Nearest Point Algorithm - complete linkage $\max(\textrm{dist}(u[i],v[j]))$
- average linkage $\dfrac{1}{\lvert u\rvert\ast\lvert v\rvert}\sum_{ij} d(u[i],v[j])$
$\lvert u\rvert$ 为 $u$ 的基数 cardinality, 包含的点数
UPGMA algorithm, Unweighted Pair Group Method with Arithmetic Mean - weighted linkage $\dfrac{\textrm{dist}(s,v)+\textrm{dist}(t,v)}2$
WPGMA, Weighted Pair Group Method with Arithmetic Mean - centroid linkage cluster 距离用形心的距离来算
UPGMC - median linkage cluster 距离用形心距离来算, 新的形心为旧的两个形心的形心
WPGMC - ward linkage $\sqrt{\dfrac{\lvert v\rvert+\lvert s\rvert}{\lvert v\rvert+\lvert s\rvert+\lvert t\rvert}d(v,s)^2+\dfrac{\lvert v\rvert+\lvert t\rvert}{\lvert v\rvert+\lvert s\rvert+\lvert t\rvert}d(v,t)^2-\dfrac{\lvert v\rvert}{\lvert v\rvert+\lvert s\rvert+\lvert t\rvert}d(v,s)^2}$
基于密度: DBSCAN, OPTICS
中心聚类 centroid-based clustering
- $k$-means
确定聚 $k$ 类 $a_1,\ \ldots a_k$, 随机选择 $k$ 个聚类中心 $\mathbfit c_i$ , 计算每个观测量到聚类中心的距离并分类到最小距离的类中, 对每个类重新计算形心 $\mathbfit c_i=\dfrac{1}{\lvert a_i\rvert}\sum_{\mathbfit x\in a_i}\mathbfit{x}$, 循环分类并计算形心
会使得 cluster 内平方误差最小 $\sum_{i=1}^k\sum_{x\in a_i}\lVert\mathbfit x-\mathbfit c_i\rVert_2^2$ 最小
文档参考 - $k$-medoids
medoids 为观测量中的点.
会使得 cluster 内误差和最小 $\sum_{i=1}^k\sum_{x\in a_i}\lVert\mathbfit x-\mathbfit c_i\rVert_2$ 最小
Distribution-based clustering
Gaussian mixture model 高斯混合模型
对于多维正态分布数据 $\varphi(x\vert\theta)=\dfrac{1}{(2\pi)^\frac{D}{2}\lvert\Sigma\rvert^\frac{1}{2}}\exp{-\dfrac{(x-\mu)\Sigma^{-1}(x-\mu)}{2}}$
高斯混合模型概率分布 $P(x\vert\theta)=\sum_{i=1}^{k}{\alpha_i\varphi(x\vert\theta_i)}$
确定 $k$ 个子高斯模型, 对每个子模型的 $\theta_i(\mu_i,\ \sigma_i,\ \alpha_i)$ 进行迭代. $\alpha_i$ 表示子模型的权重.
- 初始化参数
- E-step
\(\gamma_{ji}=\frac{\alpha_i\varphi(x_j\vert\theta_i)}{\sum_{i=1}^{k}{\alpha_i\varphi(x_j\vert\theta_i)}}\) 表示第 $j$ 个观测来自子模型 $i$ 的可能性 - M-step 迭代
\(\begin{align*}\mu_i=&\frac{\sum_{j=1}^{n}{\gamma_{ji}x_j}}{\sum_{j=1}^{n}\gamma_{ji}}\\ \sigma_i=&\frac{\sum_{j=1}^{n}{\gamma_{ji}(x_j-\mu_i)(x_j-\mu_i)^\mathrm{T}}}{\sum_{j=1}^{n}\gamma_{ji}}\\ \alpha_i=&\frac{\sum_{j=1}^{n}\gamma_{ji}}{n}\end{align*}\)
Density-based clustering
1. DBSCAN, Density-Based Spatial Clustering of Applications with Noise
定义半径 $\varepsilon$, 数目 minPts
core point：在 $\varepsilon$ 内含有超过 MinPts 的点
reachable point：存在路径 $(p_1,\ \ldots,\ p_n,\ q)$, 前 $n$ 个点为核心点, 同时 $r(p_i,\ p_{i+1})<\varepsilon$, 则 $q$ is reachable from $p_1$
noise point 噪音点：既不是核心点也不是 reachable point
density-connected: 存在点 $o$ 使得 $p$ and $q$ are reachable from $o$
cluster 属性:
cluster 内的所有点相互 density connected
若某个点可以被 cluster 内的点 reachable, 则该点在 cluster 内
2. OPTICS, Ordering points to identify the clustering structure
添加了两个参量
\({\textrm{core-dist}}_{\varepsilon\textrm{,\ MinPts}}(p)=\begin{cases}null\textrm{, 非 core point}\\\textrm{第MinPts小的距离}\end{cases}\)
\({\textrm{reachability-dist}}_{\varepsilon\textrm{,\ MinPts}}(o,p)=\begin{cases}null\textrm{, 非 core point}\\\max(\textrm{core-dist}_{\varepsilon\textrm{,\ MinPts}}(p), \textrm{dist}(p,o))\end{cases}\)