聚类

Background

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

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

Content

聚类的概念

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

聚类的任务

已知无标记样本集,聚类的算法的任务就是划分样本集成个互不相交的簇，集 划分为 ​ 个不相交的簇：

对样本,应有唯一的下标,使得；

聚类的结果可用包含 个元素的簇标记向量​ 表示；

聚类的功能

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

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

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

聚类的有效性指标

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

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

外部指标

对数据集 ,聚类簇划分 , , 参考模型簇划分为令 与 分别表示与 和​ 对应的簇标记向量.

对样本配对，一定是下面四种情况之一：

显然，

• Jaccard 系数(Jaccard Coefficient, JC)

• FMI 指数(Fowlkes and Mallows Index, FMI)

• Rand指数(Rand Index, RI)

聚类算法的距离度量

四种方式：最小距离，最大距离，中心距离，平均距离

聚类算法的分类

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