聚类 Cluster

聚类算法评价指标
聚类性能度量可以分为两类：

• 一类是将聚类结果与某个“参考模型”进行比较，称为“外部指标”(external index)
• 一类是直接考察聚类结果而不利用任何参考模型，称为“内部指标”(internal index)

对于
外部指标
对数据集D={x1,x2,...,xm}$D=\{x_1,x_2,...,x_m\}$，假定通过聚类算法将样本局为C={C1,C2,...Ck}$C=\{C_1,C_2,...C_k\}$，将参考模型给出的簇划分为C∗={C∗1,C∗2,...,C∗S}$C_{\ast }=\{C_1^{\ast },C_2^{\ast },...,C_S^{\ast }\}$。

相应的，另λ$\lambda$与λ∗${\lambda }^{\ast }$分别表示与C$C$和C∗$C^{\ast }$对应的簇标记向量。将样本两两配对考虑，有如下定义：

其中：
集合S1$S_1$表示包含了在C$C$中属于相同的簇并且在C∗$C^{\ast }$中也属于相同的簇的样本；
集合S2$S_2$表示包含了在C$C$中属于相同的簇但在C∗$C^{\ast }$中不属于相同的簇的样本；
……以此类推……

对每个样本对(xi,xj)(i<j)$(x_i,x_j)(i<j)$仅能出现在一个集合中，因此有

基于以上定义，对无监督聚类算法的聚类结果有如下性能度量指标：

• Jaccard系数(accard Coefficient，JCI)
  JCI=aa+b+c$$JCI=\frac{a}{a+b+c}$$
  所有属于同一类的样本对，同时在C$C$,C∗$C^{\ast }$中隶属于同一类的样本对的比例。
• FM指数(Fowlkes and Mallows Index，FMI)
  FMI=aa+b·aa+c‾‾‾‾‾‾‾‾‾‾‾‾‾‾√$$FMI=\sqrt{\frac{a}{a+b}·\frac{a}{a+c}}$$
  在C$C$中属于同一类的样本对中，同时属于C$C$和C∗$C^{\ast }$的样本对的比例为p1$p_1$；在C∗$C^{\ast }$中属于同一类的样本对中，同时属于C$C$和C∗$C^{\ast }$的样本对的比例为p2$p_2$，FMI就是p1$p_1$和p2$p_2$的几何平均。
• Rand指数(Rand Index，RI)
  RI=2(a+d)m(m−1)$$RI=\frac{2(a+d)}{m(m-1)}$$
  很显然，上述性能度量指标的取值都在[0,1]$[0,1]$之间，并且取值越大越好。
  -

内部指标
对于聚类结果C={C1,C2,...,Ck}$C=\{C_1,C_2,...,C_k\}$，作如下定义：

其中
avg(C)$avg(C)$表示质心，|C|$|C|$表示簇内样本的个数，即|C|=k$|C|=k$；
diam(C)$diam(C)$表示簇C$C$内样本之间的最大距离；
dmin(Ci,Cj)$d_{min}(C_i,C_j)$表示簇Ci$C_i$与簇Cj$C_j$之间的最小距离；
dist(xi,xj)$dist(x_i,x_j)$用于计算两个样本之间的距离；
μ$\mu$代表簇C$C$的样本中心。

基于上述定义，得到如下考量聚类性能的内部指标：

• DB指数( Davies-Bouldin Index，DBI)
  DBI=1kmaxj≠i(avg(Ci)+avg(Cj)dcen(μi,μj))$$DBI=\frac{1}{k}\underset{j\ne i}{max}(\frac{avg(C_i)+avg(C_j)}{d_{cen}({\mu }_i,{\mu }_j)})$$
  DBI的值越小越好
• Dunn指数(Dunn Index，DI)
  DI=min1⩽i⩽k{minj≠i(dmin(Ci,Cj)max1⩽l⩽kdiam(Cl))}$$DI=\underset{1⩽i⩽k}{min}\{\underset{j\ne i}{min}(\frac{d_{min}(C_i,C_j)}{\underset{1⩽l⩽k}{max}diam(C_l)})\}$$
  DI的值越大越好

距离度量
聚类算法的一个重要的度量目标是表示两个样本点之间的相似程度：距离越近，相似程度越高；距离越远，相似程度越低。

常用的距离度量方式：

1. 闵可夫斯基距离；
2. 欧氏距离；
3. 曼哈顿距离；
4. 切比雪夫距离；
5. 余弦距离

其中最重要的是闵可夫斯基距离，闵可夫斯基距离是一类距离的定义。

对于n$n$维空间中的两个点x(x1,x2,...,xn)$x(x_1,x_2,...,x_n)$和y(y1,y2,...,yn)$y(y_1,y_2,...,y_n)$，x$x$、y$y$两点之间的闵可夫斯基距离表示为：

其中p$p$是一个可变参数。

• 当p=1$p=1$时，称为 曼哈顿距离
  dxy=∑k=1n|xk−yk|$$d_{xy}=\sum _{k=1}^n|x_k-y_k|$$
• 当p=2$p=2$时，称为 欧式距离
  dxy=∑k=1n(xk−yk)2‾‾‾‾‾‾‾‾‾‾‾‾⎷$$d_{xy}=\sqrt{\sum _{k=1}^n(x_k-y_k{)}^2}$$
• 当p=∞$p=\mathrm{\infty }$时，称为 切比雪夫距离

K-Means算法
对给定的样本集D={x1,x2,...,xm}$D=\{x_1,x_2,...,x_m\}$，k均值算法根据聚类结果划分C={C1,C2,...,Ck}$C=\{C_1,C_2,...,C_k\}$
最小化平方误差：

其中ui=1|Ci|∑x∈Cix$u_i=\frac{1}{|C_i|}\sum _{x\in C_i}x$是类Ci$C_i$的均值向量。

MSE刻画了簇类样本围绕簇均值向量的紧密程度，越小代表样本距簇均值中心越靠近。

但最优化上式的值是一个NP难的问题，因为要精确地找到它的最优解需要对样本集D$D$的所有划分情况进行一一列举。

因此，K-Means算法最终采用的是贪心的策略，通过迭代优化的方式来近似求解最优MES值。

算法流程如下：
有样本集D={x1,x2,...,xm}$D=\{x_1,x_2,...,x_m\}$，最终聚类的类别数k$k$，最大迭代轮数n$n$，前后两次迭代计算出的类标中心的距离ϵ$ϵ$

1、随机选择k$k$个样本点作为类标中心

2、计算每个样本点到所有类标中心点的距离；

3、将所有样本点划分到距离最近的类标中心所在的类标；

4、重新计算每个类的类标中心；

5、重复步骤2-4，直到两次迭代计算出的类标中心不发生变化或发生的变化小于ϵ$ϵ$或者达到指定的最大迭代次数n$n$。

密度聚类算法之 DBSCAN
基于密度的聚类(Density_Based Clustering)方法主要考虑的是样本分布的紧密程度，这里的紧密程度主要是用样本间的距离来衡量的。

通常情况下，密度聚类算法从样本密度的角度来考察样本之间的可连续性，并基于可连续性样本不断地扩展簇以获得最终的聚类结果。

DBSCAN是一种著名的密度聚类算法，它基于一组”领域”参数(ϵ,mps$ϵ,mps$)来刻画样本分布的紧密程度。

对给定样本集D={x1,x2,...,xm}$D=\{x_1,x_2,...,x_m\}$进行如下定义：

• ϵ$ϵ$ 领域
  对于样本集D$D$中的样本点xi$x_i$，它的ϵ$ϵ$领域定义为与xi$x_i$距离不大于ϵ$ϵ$的样本的集合，即
  Nϵ(xi)={x∈D|dist(x,xi)⩽ϵ}$$N_{ϵ}(x_i)=\{x\in D|dist(x,x_i)⩽ϵ\}$$
• 核心对象
  如果样本x$x$的ϵ$ϵ$领域内至少包含mps$mps$个样本，即
  |Nϵ(xi)|⩾mps$$|N_{ϵ}(x_i)|⩾mps$$
  则称x$x$为核心对象
• 密度直达
  如果xi$x_i$是一个核心对象，并且xj$x_j$位于它的ϵ$ϵ$领域内
  ,那么我们称xj$x_j$与xi$x_i$密度直达
• 密度可达
  对于任意两个不同的样本点xi$x_i$与xj$x_j$，如果存在样本序列p1,p2,...pn$p_1,p_2,...p_n$，其中p1=xi、pn=xj$p_1=x_i、p_n=x_j$，且pi+1$p_{i+1}$由pi，i=1,2,...,n−1$p_i，i=1,2,...,n-1$密度直达，则称xi$x_i$与xj$x_j$密度可达。
• 密度相连
  对于任意的两个不同样本点xi$x_i$与xj$x_j$，如果存在第三个样本点xk$x_k$使得xi$x_i$与xj$x_j$均由xk$x_k$密度可达，则称xi$x_i$与xj$x_j$密度相连。
  
  其中：
  红点表示核心对象；黑色圆圈表示核心对象的ϵ$ϵ$领域；绿色箭头表示密度直达；绿色箭头的连线表示密度相连；绿色连线上任意两点都是密度可达。

基于以上概念的定义，那么DBSCAN中簇的定义就十分简单了：
由密度可达关系导出的最大密度相连的样本合集，即为我们最终聚类的一个簇。

形式化的定义如下：给定领域参数(ϵ,mps)$(ϵ,mps)$，簇C⊆D$C\subseteq D$的非空样本子集有如下性质：

• 连接性(Connectivity)
  对任意样本xi∈C$x_i\in C$与xj∈C$x_j\in C$有xi$x_i$与xj$x_j$密度相连；
• 最大性(Maximality)
  xi∈C$x_i\in C$，且xj$x_j$由xi$x_i$有zj∈C$z_j\in C$

找出簇样本合集：
DBSCAN方法任意选择一个没有类别的核心对象作为种子(Seed)，然后找到所有这个核心对象的密度可达样本集合，即为一个聚类簇。
接着继续选择另一个没有类别的核心对象去寻找密度可达的样本合集，这样就得到了另一个聚类簇。
不断循环下去，直到使用核心对象都有类别为止。

算法形式化的描述如下：

层次聚类算法之 AGNES
层次聚类（Hierarchical Clustering）是聚类算法家族中的重要的成员，它通过合并和分裂构建树状的类簇。对数据的划分主要有两种方式： 自顶向下 的分裂和 自底向上 的聚合。每棵树的根是一个聚集所有样本的独有的类。

AGNES是一种采用自底向上聚合策略的层次聚类算法。它先将数据集中的每个样本看成是一个初始的聚类簇，然后在算法运行的每一步中找出距离最近的两个簇进行合并。该过程不断重复，直至达到预设的聚类簇的个数。

因此，这里的关键又是如何计算两个聚类簇之间的距离。

关于计算两个聚类簇Ci、Cj$C_i、C_j$之间的距离，有如下四个定义式：

在具体的应用中，为了防止噪声点的影响，一般选择后两种距离度量方法。

AGNES聚类算法的形式化描述如下：