什么是稀疏化？

对于m个数据点，m x m的邻近矩阵可以定义为一个密集图，其中每个节点都与其他一些节点连接，并且一些节点组之间的边的权重遵循它们的成对邻近性。尽管每个对象都与其他每个对象具有一定的相似性，但对于大多数数据集而言，对象与少量对象非常相似，而与大多数其他对象相似性较弱。

此特性可用于对邻近图（矩阵）进行稀疏化，方法是在开始实际聚类过程之前，将一些低相似性（高差异性）值设置为0。例如，可以通过将所有相似性（差异性）低于（高于）定义阈值的链接除以某个值，或者仅保留指向点k个最近邻的链接来实现稀疏化。此方法创建了所谓的k近邻图。

稀疏化的益处如下：

数据大小减小——需要处理以对数据进行聚类的数据量极大地减少了。稀疏化可以去除邻近矩阵中超过99%的条目。因此，可以管理的问题规模得到了提高。

聚类效果可能更好——稀疏化方法保留了对象与其最近邻的链接，同时减少了与更远对象的连接。这符合最近邻原则，即对象的最近邻属于与该对象本身相同的类（聚类）。这减少了噪声和异常值的影响，并提高了聚类之间的区分度。

可以使用图划分算法——在稀疏图的最小割划分启发式算法方面已经进行了大量工作，尤其是在并行计算领域和集成电路设计领域。邻近图的稀疏化使其能够使用图划分算法进行聚类阶段，例如Opossum和Chameleon需要图划分。

邻近图的稀疏化必须被视为实际聚类算法之前的原始步骤。最佳稀疏化可以使邻近矩阵分解成与所需聚类相关的连通元素，但在实践中，这种情况很少出现。

单个边连接两个聚类，或者单个聚类被分成多个不连通的子聚类的情况是很常见的。事实上，当Jarvis-Patrick和SNN使用基于密度的聚类时，可以看出稀疏邻近图会被修改以产生新的邻近图。这个新的邻近图可以再次进行稀疏化。聚类算法使用所有这些预处理过程的结果作为邻近图。

Ginni

更新于：2022年2月14日

482 次浏览

完成课程获得认证