集成聚类系列（二）：常用的聚类算法及聚类算法评价指标

作者: 人工智能遇见磐创 | 来源:发表于2019-08-02 11:22 被阅读2次

1. 典型聚类算法

1.1. 基于划分的方法

代表：kmeans算法
指定k个聚类中心 $\left(c_{1}, c_{2}, c_{3} \cdots c_{k}\right)$
$d\left(c_{j}, x_{i}\right)$ （计算数据点与初始聚类中心的距离）
$x_{i} \in c_{j}$ （对于数据点 $\mathcal{x}_{i}$ ，找到最近的 $\mathcal{c}_{i}$ (聚类中心)，将 $\mathcal{x}_{i}$ 分配到 $\mathcal{c}_{i}$ 中）
$c_{j}^{old} \rightarrow c_{j}^{n e w}$ (更新聚类中心点， $c_{j}^{new}$ 是新类别数值的均值点)
$D=\sum_{i=1}^{n}\left[\min _{j=1 \cdots K} d\left(x_{i}, c_{j}\right)^{2}\right]$ （计算每一类的偏差）
$D_{r}-D_{r+1}<\varepsilon_{0}$ 返回 $\left(c_{1}, c_{2}, \cdots c_{k}\right)$
$D_{r}-D_{r+1} \geq \varepsilon_{0}$ 返回第二步

1.2. 基于层次的方法

代表：CURE算法
每个样本作为单独的一个类别 $\left(c_{1}, c_{2}, c_{3} \cdots c_{k}\right)$
$d\left(c_{v}, c_{k}\right)=\min _{\forall c, c_{\ell} \in s}\left\{d\left(c_{i}, c_{j}\right), \forall i, j \in\{1,2, \cdots n\}\right\}$
合并 $c_{v}$ , $c_{k}$ 为 $c_{vk}$
遍历完本次样本，合并成新的类别后，若存在多个类别，则返回第二步
遍历完本次样本，合并成新的类别后，若所有样本为同一类别，跳出循环，输出每层类别

1.3. 基于网格的方法

代表：STING算法
将数据集合X划分多层网格结构，从某一层开始计算
查询该层网格间的属性值，计算属性值与阈值的关系，判定网格间的相关情况，不相关的网格不作考虑
如果网格相关，则进入下一层的相关区域继续第二步，直到下一层为最底层
返回相关网格结果

1.4. 基于密度的方法

代表：DBSCAN算法
输入数据集合X，随机选取一点，并找出这个点的所有高密度可达点
遍历此点的所有 $\varepsilon$ 邻域内的点，并寻找这些密度可达点，判定某点 $\varepsilon-$ 邻域内的点，并寻找这些点密度可达点，判定某点的 $\varepsilon-$ 邻域内的点数是否超过阈值点数，超过则构成核心点
扫描数据集，寻找没有被聚类的数据点，重复第二步
输出划分的类，并输出异常值点（不和其他密度相连）

1.5. 神经网络的方法

代表：SOM算法
数据集合 $\left[x_{1}, x_{2}, \cdots x_{n}\right]$ ，权重向量为 $\left[w_{1}, w_{2}, \cdots w_{n}\right]$ ， $\left\|x_{i}\right\|=\left(\sum_{i=1}^{d} x_{n}^{2}\right)^{1 / 2}$ ，归一化处理 $\hat{w}_{j}=\frac{w_{j}}{\left\|w_{j}\right\|}, \quad \hat{x}_{i}=\frac{x_{i}}{\left\|x_{i}\right\|}$
寻找获胜的神经元，找到最小距离，对于每一个输入数据，找到与之最相匹配的节点
令 $S_{j, I(x)}$ 为 $\mathrm{I}(x)$ 为 $j$ 的距离，更新权重： $T_{j, I(x)}=\exp \left(-S_{j, l(x)} / 2 \sigma^{2}\right)$
更新临近节点， $w(t+1)=w(t)+\eta(t) T_{j, l(x)}(t)\left(x_{i}-w_{j i}\right)$ ，其中 $\eta(t)$ 代表学习率

1.6. 基于图的聚类方法

代表：谱聚类算法
计算邻接矩阵 $A=\left[\begin{array}{ccc}{A_{11}} & {\cdots} & {A_{1 n}} \\ {\vdots} & {\ddots} & {\vdots} \\ {A_{n 1}} & {\cdots} & {A_{n n}}\end{array}\right]$ ，度矩阵 $D_{n}=\sum_{j=1}^{n} A_{j}$ ， $D=\left[\begin{array}{ccc}{D_{11}} & {\cdots} & {D_{1 n}} \\ {\vdots} & {\ddots} & {\vdots} \\ {D_{n 1}} & {\cdots} & {D_{n n}}\end{array}\right]$
计算拉普拉及矩阵 $L=D-A$
计算归一化拉普拉斯矩阵 $L=I-D^{1 / 2} \cdot A \cdot D^{1 / 2}$
计算 $L$ 的特征值和特征向量 $Q$
对Q矩阵进行 $K-means$ 聚类，得到聚类结果

2. 聚类算法的评价指标

一个好的聚类方法可以产生高品质簇，是的簇内相似度高，簇间相似度低。一般来说，评估聚类质量有两个标准，内部质量评价指标和外部评价指标。

2.1. 内部质量评价标准

内部评价指标是利用数据集的属性特征来评价聚类算法的优劣。通过计算总体的相似度，簇间平均相似度或簇内平均相似度来评价聚类质量。评价聚类效果的高低通常使用聚类的有效性指标，所以目前的检验聚类的有效性指标主要是通过簇间距离和簇内距离来衡量。这类指标常用的有CH（Calinski-Harabasz）指标等

2.1.1. CH指标

CH指标定义为：
$C H(K)=\frac{\operatorname{tr}(B) /(K-1)}{\operatorname{tr}(W) /(N-K)}$
其中 $\operatorname{tr}(B)=\sum_{j=1}^{k}\left\|z_{j}-z\right\|^{2}$ 表示类间距离差矩阵的迹， $\operatorname{tr}(W)=\sum_{j=1}^{k} \sum_{x_{i} \in z_{k}}\left\|x_{i}-z_{j}\right\|^{2}$ 表示类内离差矩阵的迹， $z$ 是整个数据集的均值， $z_{j}$ 是第 $j$ 个簇 $c_{j}$ 的均值， $N$ 代表聚类个数， $K$ 代表当前的类。 $CH(K)$ 值越大，聚类效果越好， $CH$ 主要计算簇间距离与簇内距离的比值

2.1.2. 簇的凝聚度

簇内点对的平均距离反映了簇的凝聚度，一般使用组内误差平方（SSE）表示：
$S S E=\sum_{i=1}^{r} \sum_{j=1}^{n_{i}}\left(X_{i j}-\overline{X}_{i}\right)^{2}, \quad \overline{X}_{i}=\frac{1}{n_{i}} \sum_{j=1}^{n_{i}} X_{i j}, i=1,2, \ldots, r$

2.1.3. 簇的邻近度

簇的邻近度用组间平方和（SSB）表示，即簇的质心 $C_{i}$ 到簇内所有数据点的总平均值 $c$ 的距离的平方和

2.2. 外部质量评价标准

外部质量评价指标是基于已知分类标签数据集进行评价的，这样可以将原有标签数据与聚类输出结果进行对比。外部质量评价指标的理想聚类结果是：具有不同类标签的数据聚合到不同的簇中，具有相同类标签的数据聚合相同的簇中。外部质量评价准则通常使用熵，纯度等指标进行度量。

2.2.1. 熵：

簇内包含单个类对象的一种度量。对于每一个簇，首先计算数据的类分布，即对于簇 $i$ ，计算簇 $i$ 的成员属于类 $j$ 的概率
$p_{i j}=\frac{m_{i j}}{m_{i}}$
其中 $m_{i}$ 表示簇 $i$ 中所有对象的个数，而 $m_{ij}$ 是簇 $i$ 中类 $j$ 的对象个数。使用类分布，用标准公式：
$e_{i}=-\sum_{j=1}^{K} p_{i j} \log _{2} p_{i j}$
计算每个簇 $i$ 的熵，其中K是类个数。簇集合的总熵用每个簇的熵的加权和计算即：
$e=\sum_{i=1}^{K} \frac{m_{i}}{m} e_{i}$
其中 $K$ 是簇的个数，而 $m$ 是簇内数据点的总和