目前的心得是聚类算法的性能最重要的是如何衡量相似性

相似性度量方式

闵科夫斯基距离

$dist=(\sum^n_{i=1}|x_i-y_i|^p)^{1/p}$
当p=1时，为曼哈顿距离，p=2时，为欧式距离， $p\rightarrow \infty$ 时，为切比雪夫距离

马氏距离(协方差距离)

$D_M(x)=\sqrt{(s-\mu)\sum^{-1}(x-\mu)}$
其中 $\mu$ 为x的均值， $\sum$ 为x的协方差阵，此类方法考虑了各种特性的相似性。

编辑距离：

可用于字符串的相似性度量，如给定两个字符串，从第一个转换为第二个所需要的最小编辑操作称为编辑距离，最主要的操作是插入，删除和替换，具体的迭代公式为
$dp[i][j]= \begin{cases} 0 \qquad & i=j=0\\ j \qquad & i=0,j>0\\ i \qquad & i>0,j=0\\ min(dp[i][j-1]+1, dp[i-1][j]+1,dp[i-1][j-1]) \qquad & S_1(i)=S_2(j)\\ min(dp[i][j-1]+1, dp[i-1][j]+1,dp[i-1][j-1]+ 1) \qquad & S_1(i)\neq S_2(j)\\ \end{cases}$

动态时间规整距离(DTW)

基本思想是找到所有密度相连的点构成一类，但是需要人为确定参数 $\epsilon$ 和MinPts

$S\in R^{n}, Q\in R^{m}$ ，想要找到最优的弯曲路径，使得S和Q之间的距离最短，有效的弯曲路径必须符合给出的这三个要求：

边界性：满足起始点一致，即 $p_1=(1,1),p_k=(n,m)$ ;
单调性：对于给定的 $p_k=(i,j)$ 和 $p_{k+1}=(i^*,j^*)$ ，满足 $i^*\geq i, j^* \geq j$ ;
连续性：对于给定的 $p_k=(i,j)$ 和 $p_{k+1}=(i^*,j^*)$ ，满足 $i^*\leq i+1, j^* \geq j+1$ .

Shaped Based Distance（基于相关性的距离）

首先定义
$R_{\omega-n}(S,Q)= \begin{cases} \sum^{n-k}_{l=1}s_{l+k}q_l \qquad & k > 0\\ R_{-k}(\vec{y}, \vec x) \qquad & k < 0 \end{cases}$
$CC_{\omega}(S,Q)=R_{\omega-n}(S,Q), \omega \in \{1,2,...,2l-1\}$
则最终距离的计算表达为
$SBD(S,Q)=1-max_\omega(\frac{CC_\omega(S,Q)}{\sqrt{R_0(S,S)R_0(Q,Q)}})$

聚类方式

常见的聚类方式可以分为四类：基于密度(Density based)，基于原型(prototype-based)，层次聚类(hierarchical clustering)，基于模型(Model-based)的聚类。

基于密度的聚类：

基本概念：参数
- $\epsilon$ 域：对于给定的数据点，距离此数据点距离小于 $\epsilon$ 的范围
- 核心对象：如果某点的 $\epsilon$ 域中包含至少MinPts个点，则此数据点为核心对象
- 密度直达：若 $x_j$ 在 $x_i$ 的 $\epsilon$ 域内，且 $x_i$ 为核心对象，则称 $x_j$ 由 $x_i$ 密度直达
- 密度可达：若存在一个序列 $s_1,s_2,...,s_n$ ，且满足 $s_{i+1}$ 可由 $s_i$ 密度直达，则称 $s_n$ 可由 $s_1$ 密度可达
- 密度相连：若 $x_j,x_k$ 均由 $x_i$ 密度可达，则称 $x_j$ 与 $x_k$ 密度相连
DBSCAN算法就是要找到所有密度相连的点，构成一个类DBSCAN算法可以对任意形状的点进行聚类，这是基于原型的聚类无法达到的。

#  INPUT: 样本集D={x_1,x_2,...,x_m} 参数 epsilon MinPts
初始化核心对象集合： Omega为空集
for j in range(m):
  确定样本x_j的epsilon域中包含的点个数
  若个数大于MinPts，那么将x_j加入到Omega中去
初始化聚类簇个数：k=0
初始化为访问样本集合： Gamma=D
while Omega != None:
  记录当前为访问样本集合： Gamma_old = Gamma
  随机选取一个核心对象o，初始化队列 Q=<o>
  Gamma = Gamma \ {o}
  while Q != None:
    取出队列Q中的首个样本q；
    如果q是核心对象，对应的集合为N
      令Delta = N与Gamma的交集
      将Delta中的样本加入到队列Q
      Gamma = Gamma\{Delta}
k = k+1,生成聚类簇 C_k = Gamma_old \ Gamma
Omega = Omega \ {C_k}

基于原型的聚类

Kmeans算法

基本想法是不断迭代更新中心点，直至中心点不变为止

优点是原理简单，但是却对于聚类的形状有一定限制，而且需要人为确定参数k

学习向量量化(Learning Vector Quantization)算法

基本思想是随机选取样本，找到与之最近的样本，看类别是否一致来对原型向量进行更新

LVQ算法伪代码

最核心的点在于：对于找到距离最近的原型向量，如果对应的标记,为原型向量的label，则采用更新上图中的更新公式，此时得到的与之间的距离为：

因此，更新之后更加接近于,倘若对应标签不等，则会更加原理.

基于模型的聚类-Mixture of Gaussian

基本概念：
- 多元高斯分布: $\mu$ 为n维均值向量， $\Sigma\in R^{n\times n}$ 为协方差阵
  $p(x)=\frac{1}{(2\pi)^{n/2}|\Sigma|^{1/2}}e^{-0.5 *(x-\mu)^T\Sigma^{-1}(x-\mu)}$
- 混合高斯分布：
  $p_M(x)=\sum^k_{i=1}\alpha_ip(x|\mu_i,\Sigma_i)$
  满足 $\sum^k_{i=1}\alpha_i=1$
- 假设 $D={x_1,x_2,...,x_m}$ 为高斯混合分布产生的数据，随机变量 $z_j\in range(k)$ 表示生成样本 $x_j$ 的混合成分，则 $P(z_j=i)=\alpha_i$ ,根据Bayes公式，有
  $p_M(z_j=i|x_j)=\frac{P(z_j=i)p_M(x_j|z_j=i)}{P_M(x_j)}=\frac{\alpha_ip(x_j|\mu_i,\Sigma_i)}{\sum^k_{l=1}alpha_ip(x_j|\mu_l,\Sigma_l)}$
  上式表述了样本 $x_j$ 由第i个高斯混合成分生成的后验概率，记作 $\gamma_{ji}$ 。
  Gaussian混合聚类将样本分为k类，每个样本 $x_j$ 的标记 $\lambda_j=argmax_{i\in range(k)}\gamma_{ji}$
  如果想要求解模型参数 $\mu_i,\Sigma_i,\alpha_i$ ，可采用极大似然法
  $LL(D)=ln(\Pi^m_{j=1}p_M(x_j))=\sum^m_{j=1}ln(\sum^k_{i=1}\alpha_ip(x_j|\mu_i,\Sigma_i))$
  由 $\frac{\partial LL(D)}{\partial \mu_i}=0, \frac{\partial LL(D)}{\partial \Sigma_i}=0$ 可以得到：
  $\mu_i=\frac{\sum^m_{j=1}\gamma_{ji}x_j}{\sum^m_{j=1}\gamma_{ji}}$
  $\Sigma_i=\frac{\sum^m_{i=1}\gamma_{ji}(x_j-\mu_i)(x_j-\mu_i)^T}{\sum^m_{j=1}\gamma_{ji}}$
  对于混合系数，采用Lagrange乘子法， $LL(D)+\lambda(\sum^k_{i=1}\alpha_i-1)$ ，对于 $\alpha_i$ 求导，最终得到
  $\alpha_i=\frac{1}{m}\sum^m_{i=1}\gamma_{ji}$