聚类(Clustering)前置知识

Posted on

聚类

Background

如果我们相信聚集在一起，有较高相似性的簇一定有有趣的知识的话，那么聚类分析就是获得数据内部结构，发现簇的意义的方法。

在讨论聚类算法时，都是在无监督学习的框架下进行的，也就是已知的数据集是没有标签可以学习的。

Content

聚类的概念

聚类：将数据分为多个簇(Clusters)，使得在同一个簇内对象之间具有较高的相似度，而不同簇之间的对象差别较大。

聚类的任务

已知无标记样本集$D={\boldsymbol{x}{1},\boldsymbol{x}{2},\ldots,\boldsymbol{x}{m}}$,聚类的算法的任务就是划分样本集成$k$个互不相交的簇，集 $D$ 划分为 $k$​ 个不相交的簇：
$$
D=\bigcup{l=1}^kC_l，C_{l^{\prime}}\bigcap C_l=\varnothing ({l^{\prime}\neq l})
$$
对样本$\boldsymbol{x}{j}$,应有唯一的下标$\lambda_j\in{1,2,\ldots,k}$,使得$x_j\in C{\lambda_j}$；

聚类的结果可用包含 $m$ 个元素的簇标记向量$\lambda=(\lambda_1;\lambda_2;\ldots;\lambda_m)$​ 表示；

聚类的功能

聚类分析是获得数据内部结构的有效方法。通过观察聚类得到的每个簇的特点，可以集中对特定的某些簇作进一步分析。

聚类分析可以作为其它算法的预处理步骤；

聚类分析可以完成噪声点/孤立点的挖掘；

聚类的有效性指标

对于聚类任务，我们希望物以类聚，直观上有两个指标：

  • 「簇内相似度（intra-cluster similarity）」高
  • 「簇间相似度(inter-cluster similarity)」低

外部指标

对数据集 $D={\boldsymbol{x}_1,\boldsymbol{x}_2,\ldots,\boldsymbol{x}_m}$,聚类簇划分 $\mathcal{C}={C_1$, $C_2,\ldots,C_k}$, 参考模型簇划分为$C^={C_1^,C_2^,\ldots,C_s^}$令$\lambda$ 与$\lambda^$ 分别表示与$C$ 和$C^$​ 对应的簇标记向量.

对样本配对，一定是下面四种情况之一：
$$
\begin{gathered}
a= |SS|, SS={(\boldsymbol{x}{i},\boldsymbol{x}{j})\mid\lambda_{i}=\lambda_{j},\lambda_{i}^{}=\lambda_{j}^{},i<j)}\
b= |SD|, SD={(\boldsymbol{x}{i},\boldsymbol{x}{j})\mid\lambda_{i}=\lambda_{j},\lambda_{i}^{}\neq\lambda_{j}^{},i<j)} \
c= |DS|, DS={(\boldsymbol{x}{i},\boldsymbol{x}{j})\mid\lambda_{i}\neq\lambda_{j},\lambda_{i}^{}=\lambda_{j}^{},i<j)} \
d= |DD|, DD={(\boldsymbol{x}{i},\boldsymbol{x}{j})\mid\lambda_{i}\neq\lambda_{j},\lambda_{i}^{}\neq\lambda_{j}^{},i<j)}
\end{gathered}
$$
显然，$a+b+c+d=\binom{m}{2}$

  • Jaccard 系数(Jaccard Coefficient, JC)
    $$
    JC=\frac a {a+b+c}
    $$

  • FMI 指数(Fowlkes and Mallows Index, FMI)
    $$
    \mathrm{FMI}=\sqrt{\frac{a}{a+b}\cdot\frac{a}{a+c}} .
    $$

  • Rand指数(Rand Index, RI)
    $$
    RI= \frac{a+d}{a+b+c+d}
    $$

聚类算法的距离度量

四种方式：最小距离，最大距离，中心距离，平均距离
$$
\begin{aligned}
&dist_{min}(C_i,C_j) =\min_{p\in C_i,p^{\prime}\in C_j}{|p-p^{\prime}|} \
&dist_{max}(C_i,C_j) =\max_{p\in C_i,p^{\prime}\in C_j}{|p-p^{\prime}|} \
&dist_{mean}(C_i,C_j)=|m_i-m_j| \
& dist_{a\nu g}(C_i,C_j)=\frac1{n_in_j}\sum_{p\in C_i,p^{\prime}\in C_j}|p-p^{\prime}|
\end{aligned}
$$

聚类算法的分类

  • 基于划分的办法：K-Means, K-Medoids
  • 基于层次的办法：AGENS, DIANA
  • 基于密度的办法：DBSCAN
  • 基于网络的办法：STING