Clustering-watermelon-book

聚类任务简介

简单地说，就是要对一个n维向量元素的集合求一个划分，划分后的子集就是一类的（不相交的簇）。

对于数据集$D = {x_1,x_2,…,x_m}$，划分为k个不相交的集合$C_1, C_2, …, C_k$，若$x_i \in C_j$，则$\lambda_i = j$，其中$j \in {1,2,…,k}$，对应$\lambda_i$就是$x_i$的标签。聚类任务要做的是就是求出一个聚类结果$\lambda = (\lambda_1,\lambda_2,…,\lambda_m)$，其中$\lambda$为数据集的簇标记向量，第$i$个分量标记了$x_i$属于哪一个簇。

性能度量

怎样的聚类是好的：

簇内的样本尽量相似
簇间的样本尽量不同

外部指标

外部指标：将聚类结果和某个“参考模型”进行比较，称为外部指标

对于数据集$D = {x_1,x_2,…,x_m}$，使用聚类模型A，得到簇标记向量$\lambda$，另外使用参考聚类模型B，得到簇标记向量$\lambda^{*}$。

于是我们可以根据$\lambda_i$与$\lambda_j$相同与否的关系以及$\lambda^{}_i$
与$\lambda^{}_j$是否相同的关系定义如下集合。

$DD,DS,SD,SS$一共四个集合，这些集合中的元素类似$(x_i,x_j)$，是一个“向量对”，分别按照如下规则界定类似的向量对是否属于相应的集合

$x_i$与$x_j$在模型A、B的划分下都属于同一簇，则$(x_i,x_j) \in SS$
$x_i$与$x_j$在模型A、B的划分下都不属于同一簇，则$(x_i,x_j) \in DD$
$x_i$与$x_j$在模型A划分下属于同一簇，在B划分下不属于同一簇，则$(x_i,x_j) \in SD$
$x_i$与$x_j$在模型A划分下不属于同一簇，在B划分下属于同一簇，则$(x_i,x_j) \in DS$

D即different，S即same 这样就非常容易理解了

根据上面的集合，我们可以定义如下过度变量

$\lvert SS \rvert = a$
$\lvert SD \rvert = b$
$\lvert DS \rvert = c$
$\lvert DD \rvert = d$

进一步，我们定义常用于性能度量的第一组系数

JC系数 $JC = \frac{a}{a+b+c}$
FMI系数 $FMI = \sqrt{\frac{a}{a+b} \ast \frac{a}{a+c}}$
Rand指数 $RI = \frac{2(a+b)}{m(m-1)}$

这些性能指标的范围都是$[0,1]$，并且越大说明聚类效果越好
当然，前提是参考的模型是“正确”的

距离计算

闵可夫斯基距离

定义函数$dist(\cdot,\cdot)$，用于计算两个向量的距离。则它应该满足下述三个性质

非负性
对称性
直递性

常用的距离是闵可夫斯基距离

$dist_mk(x_i,x_j) = (\sum_{\mu = 1}^{n} \lvert x_{i\mu} - x_{j\mu} \rvert ^{p})^{\frac{1}{p}}$
显然当$p = 2$时即我们常用的欧氏距离，$p = 1$时为曼哈顿距离

有序属性和无序属性

在考虑属性之间的距离的时候，序十分重要。这里通过简单的例子引入有序和无序。属性值出自于能够直接计算距离的属性称为有序属性，例如属性定义域为${1,2,3}$，而不能的就是无序属性，例如${货车,西瓜,乐乐}$。

显然，闵可夫斯基距离是用于衡量有序属性的距离的。

VDM——衡量无序属性的距离

假设有$k$个样本簇，$m_\mu,a$表示在属性$\mu$上取值为$a$的样本的个数，$m_\mu,a,i$表示在第i个样本簇中，属性$\mu$取值为$a$的样本个数。定义VDM如下。

$VDM = \sum_{i=1}^{k} \lvert \frac{m_\mu,a,i}{m_\mu,a} - \frac{m_\mu,b,i}{m_\mu,b}\rvert ^{p}$

值得注意的是，这里衡量的只是无序属性的距离，而要衡量两个无序样本$x_i$与$x_j$的距离，即其中的各个属性（类比向量的分量）都是无序属性，我们应该对各个属性的$VDM$求和。

混合元素的距离

不失一般性，我们可以定义混合元素的距离如下：
$MinkovDM_p(x_i,x_j) = (\sum_{\mu=1}^{n_c} \lvert x_{i\mu} - x_{j\mu} \rvert ^{p} + \sum_{\mu=n_c+1}^{n} VDM_p(x_{i,\mu},x_{j,\mu}))^{\frac{1}{p}}$

其中$x_i,x_j$为混合属性的元素，$1到n_c$对应为有序属性，$n_c到n$对应为无序属性

内部指标

于是我们可以根据元素的不同（有序、无序、混合），选取我们需要的距离函数$dist(\cdot,\cdot)$，定义如下常用于刻画簇的性质的量

$\mu_i = \frac{1}{\lvert C \rvert} \sum_{1 \le i \le \lvert C \rvert} x_i, \mu = (\mu_1,\mu_2,…,\mu_m)$为簇$C$的中心点
$avg(C) = \frac{2}{\lvert C \rvert (\lvert C \rvert - 1)} \sum_{1 \le i < j \le \lvert C \rvert} dist(x_i,x_j)$ 簇$C$内样本间的平均距离
$diam(C) = max_{1 \le i < j \le \lvert C \rvert} dist(x_i,x_j)$ 簇$C$内样本间的最远距离
$d_{min}(C_i,C_j) = min_{x_i \in C_i,x_j \in C_j} dist(x_i,x_j)$ 簇$C_i$和簇$C_j$中最近样本的距离
$d_{cen}(C_i,C_j) = dist(\mu_i,\mu_j)$ 簇$C_i$和簇$C_j$的中心点距离

进一步我们定义一些内部指标如下。

$DBI = \frac{1}{k} \sum_{i=1}^{k} max_{j \ne i}(\frac{avg(C_i)+avg(C_j)}{d_{cen}(\mu_i,\mu_j)})$
$DI = min_{1 \le i \le k} { min_{j \ne i}(\frac{d_{min}(C_i,C_j)}{min_{1 \le l \le k} diam(C_i)}) }$

DB指数越小越好，Dunn指数越大越好

原型聚类

原型的概念对应的是空间中的点。原型聚类的前提是认为，数据集中的聚类结构可以通过一组原型来描述。而原型聚类要做的就是通过某些方法找出这组“原型”。常见的原型聚类算法的代表有k-means（k均值算法）、学习向量量化算法等等

在后续的blog中会记录我复现相关算法的过程