聚类算法：原理、发展与评估

### 聚类算法：原理、发展与评估 #### 1. 流行聚类算法 ##### 1.1 密度峰值聚类（DPC） DPC 算法通过决策图帮助用户手动选择聚类中心，但在处理具有非均匀密度和尺度的聚类时，难以从决策图中突出的点里准确区分出真正的聚类中心。此外，DPC 根据最近的高密度邻居分配非中心点，若最高密度点分配错误，会引发“连锁反应”，影响周围区域的点。DPC 算法代码可在[此处](https://github.com/topics/density-peak-clustering)获取。 ##### 1.2 STING 算法 STING 算法将数据划分为矩形单元格网格，基于单元格的统计属性进行聚类，是一种基于网格的多分辨率聚类方法。其工作流程如下： 1. **数据划分**：将数据划分为矩形单元格网格，单元格大小由用户指定的参数控制聚类粒度。 2. **统计分析**：计算每个单元格的统计属性，如均值、标准差和特征间的相关系数。 3. **层次聚类**：使用层次聚类算法基于统计属性对单元格进行聚类，生成的树状图表示不同粒度级别的聚类层次。 4. **网格细化**：合并属于同一聚类的相邻单元格，用户可指定聚类中单元格的最小数量阈值来控制聚类粒度。 STING 算法的优点是能处理包含混合数据类型的大型数据集，识别任意形状和大小的聚类，并通过层次聚类自然地探索不同粒度的聚类结构。缺点是基于网格的划分可能导致聚类间出现人为边界，只能识别水平或垂直的聚类边界，且假设数据的统计属性足以捕捉潜在的聚类结构，这在某些情况下可能不成立。 ##### 1.3 谱聚类 谱聚类是图论中的流行技术，用于基于图中节点间的边识别节点社区。它利用数据相似性矩阵的谱进行降维，然后应用 k - 均值聚类。谱聚类的关键步骤如下： 1. **生成相似图**：根据对象间的成对相似性构建矩阵，常用高斯核函数定义亲和矩阵或邻接矩阵。 2. **计算拉普拉斯矩阵**：简单拉普拉斯矩阵定义为 $L = D - A$，其中 $D$ 是对角矩阵，测量每个节点的度。 3. **处理多类聚类问题**：用 $k$ 个特征向量表示图拉普拉斯矩阵，然后应用 k - 均值聚类、穷举搜索或离散化确定最终的聚类成员。 谱聚类的复杂度通常为二次或超二次，最近有研究将自编码器应用于拉普拉斯矩阵以获得特征向量提供的谱嵌入，或使用深度学习网络将输入数据直接映射到低维特征向量表示，再进行简单的聚类算法。谱聚类的代码示例可参考[这里](https://towardsdatascience.com/spectral-clustering-aba2640c0d5b)和[这里](https://github.com/lucianolorenti/SpectralClustering.jl)。