聚类算法的分类
聚类算法有很多种分法，体系也很大，这里举例几种分法：
基于划分的聚类：聚类目标是使得类内的点足够近，类间的点足够远，常见的如k-means及其衍生算法
基于密度的聚类：当邻近区域的密度超过某个阈值，则继续聚类，如DBSCAN; OPTICS
层次聚类：这个下面会具体介绍到，包括合并的层次聚类，分裂的层次聚类，实际上可以看作是二叉树的生成和分裂过程。下面会介绍实际应用中常用的HDBSCAN
基于图的聚类： 通过建图来进行聚类，这是聚类算法中的大头，很多较新的聚类算法都有图聚类的思想。这篇文章会介绍以Chinese Whisper，谱聚类两大具有代表性的图聚类算法
基于GCN（图神经网络）的聚类：实际上这个本质上也是基于图的聚类，然而基于GCN的聚类算法会有深度学习中的训练的概念，而传统的聚类算法则是通过人工设定阈值来决定的，所以这里也分开列了一类， 这篇文章会介绍《Learning to Cluster Faces on Affinity Graph》、CDP两篇论文的思想
Kmeans聚类
一般步骤：
1、选择k个点，作为初始类别中心，即簇中心，一般随机选择点
2、计算所有点到类中心的距离，并归到最近的类
3、根据分类情况，重新计算类中心，重复上述步骤，直到收敛
Kmeans聚类有以下几个 特点：
- 需要提前确定k值
- 对初始质心点敏感
- 对异常数据敏感
- 对团状数据点区分度好，对于带状不好
层次聚类
层次聚类(Hierarchical Clustering)是聚类算法的一种，通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中，不同类别的原始数据点是树的最低层，树的顶层是一个聚类的根节点。创建聚类树有自下而上合并和自上而下分裂两种方法。
自底向上的合并算法
层次聚类的合并算法通过计算两类数据点间的相似性，对所有数据点中最为相似的两个数据点进行组合，并反复迭代这一过程。简单的说层次聚类的合并算法是通过计算每一个类别的数据点与所有数据点之间的距离来确定它们之间的相似性，距离越小，相似度越高。并将距离最近的两个数据点或类别进行组合，生成聚类树。
如何计算两个类数据间的距离，有三种方式：
Single Linkage：方法是将两个组合数据点中距离最近的两个数据点间的距离作为这两个组合数据点的距离。这种方法容易受到极端值的影响。
Complete Linkage：将两个组合数据点中距离最远的两个数据点间的距离作为这两个组合数据点的距离。可能由于其中的极端值距离较远而无法组合在一起。
Average Linkage：计算两个组合数据点中的每个数据点与其他所有数据点的距离。将所有距离的均值作为两个组合数据点间的距离。这种方法计算量比较大，但结果比前两种方法更合理
; 图的聚类cdp
CDP本质是学习一个metric，也就是对样本对（pairs）进行判断。如下图，CDP首先使用多个人脸识别模型构建成一个委员会（committee）， committee中每个成员对基础模型中相连的pairs提供包括 关系（是否是neighbor）、相似度、局部结构等信息（其他相邻节点的相似度），然后使用一个多层感知机（MLP）来整合这些信息并作出预测（即这个pair是否是同一个人）。这个过程可以类比成一个投票的过程，committee负责考察一个候选人（pair）的各方面信息，将信息汇总给MLP进行决定。最后将所有的positive pairs组成一个新的graph称为consensus-driven graph。在此graph上使用简单的连通域搜索并动态剪枝即可快速得到聚类。由于MLP需要使用一部分有标签的数据来训练得到，所以CDP是一种基于有监督的metric的聚类方法
补充知识
1、构图方式，base model（一般为要部署的模型），及committee model都是不同的特征提取模型，他们构图的方式是，利用相似度的朴素构图思想（可参考另一博客的hnsw章节），而gcn、infomap等算法是暴力构图
2、MLP输入输出：base model输出的pairs是图中连接的所有节点对，committee中每个成员对基础模型中相连的pairs提供包括关系（是否是neighbor）、相似度、局部结构等信息（其他相邻节点的相似度这些都是输入；输出则是该pairs到底该不该连（应该还有相似度？）
cdp参考链接
cdp参考链接
Original: https://blog.csdn.net/henyaoyuancc/article/details/122670786
Author: henyaoyuancc
Title: 聚类算法总结
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/550756/
转载文章受原作者版权保护。转载请注明原作者出处！