聚类算法综述

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

相似性度量方式

闵科夫斯基距离

$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}$

伪代码

Gaussian of Mixture Clustering

基于层次的聚类

基本思想是自底而上或自顶而下的策略，如AGNES首先将每个点作为一个类簇，然后在算法中运行每一步找到距离最近的两个聚类簇进行合并，直至达到预设的聚类簇个数

层次聚类算法

参考自周志华《机器学习》

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,456评论 5赞 477
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,370评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,337评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,583评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,596评论 5赞 365
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,572评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,936评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,595评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,850评论 1赞 297
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,601评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,685评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,371评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,951评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,934评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,167评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 43,636评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,411评论 2赞 342