高效聚类与社团发现算法：棒打鸳鸯法的革新

导言

基于距离或相似度对数据点进行聚类，作为应对众多自然与社会问题的有效工具，已吸引了广泛的关注。在多种聚类算法中，分层聚类展现出独特的优势。近日，电子科技大学周涛教授领导的研究团队在《Information Sciences》期刊上发表论文，提出了一种全新的层次聚类算法。该算法在多个领域的数据集上显示出了超越同类算法的显著能力，并在网络社团检测中展现出广泛的应用前景。

论文标题：

Hierarchical clustering supported by reciprocal nearest neighbors

论文链接：

https://www.sciencedirect.com/science/article/pii/S0020025520303157

图1：层次聚类算法结果的示意图

传统聚类算法普遍存在一些缺陷，例如需预先指定聚类数目（即必须事先确定要聚成多少类），并且即使获得聚类结果后，类别之间的关系仍不够明晰。层次聚类算法在这方面自然具备优势。该算法在最高层面视所有数据点为一个整体类别，随后从该类中逐步细分出多个一级子类，并进而分裂出若干二级子类，以此类推。这一过程无需预先设定聚类数量，且不同子类之间的组织结构相对清晰。图1展现了一个典型的层次聚类算法结果，从上到下可以自动生成不同分辨率的聚类结果，其间数据点间的亲疏关系也一目了然。在网络社团挖掘中，著名的Girvan-Newman算法即是此类层次聚类算法的典型代表，能够揭示不同尺度的网络组织结构。然而，层次聚类算法也存在显著缺点，如计算复杂度较高，易受噪音点影响等。

假设每个数据点都偏好与自己距离最近的数据点。如果从一个数据点 A 出发，依次追逐它所偏爱的对象。善意的预期是 A 偏好 B，而 B 也应偏好 A，但现实往往并非如此，许多情况下会形成链式关系，如 A->B->C->D->E 等，甚至出现复杂的循环关系，例如 A->B->C->D->A，甚至是 A->B->C->A。如果十分幸运，存在某对数据点 A 和 B 使得 A 偏好 B，且 B 也偏好 A，我们便将其视为一对“鸳鸯节点”（更准确的说法是“互为最近邻”）。

我们提出了一种新颖的层次聚类算法，其核心假设十分简洁且善意，即“互为最近邻”的数据点应归于同一类别。

图2：构建聚类子树的过程示意图

给定一组数据点并定义距离后，首先需构建聚类子树。初始时，所有数据点均为自由状态，未形成树状结构。我们从随机选择的一个自由数据点 A1 开始，依次找到其偏好的数据点 A2，再找到 A2 偏好的 A3……形成序列 A1、A2、A3、A4 等。如果在某个时刻出现 Ai=Ai-2（意即 Ai-2 与 Ai-1 形成一对鸳鸯），则可停止此过程。此时，A1 到 Ai-1 便构成了一个聚类子树，Ai-2 和 Ai-1 被定义为该子树的支撑节点。我们还需添加一个虚构的根节点，其位置为 Ai-2 和 Ai-1 的“中点”，并与两者相连，作为该聚类子树的代表点。如果序列 A1、A2、A3、A4……在遇到鸳鸯节点之前，碰到非自由节点（即已属某个聚类子树的节点），例如 A4 可能已有所属，则 A1、A2、A3 可自动附属到已存在子树上。如果构成的聚类子树形态“又瘦又高”，我们将进行剪枝处理，从而形成一些由孤立节点构成的特殊聚类子树，代表节点为自身（具体操作细节请参见原文[5]）。

图3：迭代过程示意图

如图3所示，在确定了聚类子树后，我们将这些聚类子树的代表点视作新的数据点，利用相同方法对这些新数据点进行聚类。以此类推，基于新数据点之间的距离，再次应用“互不打扰鸳鸯”的算法。通过迭代，我们得以获得整个层次聚类的结果。若数据点所在的距离空间并非欧几里得空间，则无法定义某种“中点”的位置（例如某个维度的特征为颜色，而距离为海明距离，此时定义绿色和粉色的中点较为困难），这时我们可以直接计算“中点”与“中点”之间的距离（具体推导见[5]），以确保算法有效实施。

在 n 个数据点的情况下，通过 K-D Tree[6] 可在 O(nlogn) 时间内找出所有最近邻，由此可以证明，该算法在最坏情况下时间复杂度不超过 O(nlogn)。简要推导如下：

我们基于两个标准数据集，UCI数据库和Olivetti图像数据集，对算法效果进行了测试，并将其与四种具有代表性的算法，即 GA[7]、CURE[8]、AP[9] 与 DD[10] 进行了比较。

占据优势。

对于当前从事大数据和人工智能研究的学生、学者和业界人员来说，特征工程和深度学习更受关注。然而，我个人对这个算法的青睐不仅在于其高效快速，更在于其背后简单而优美的假设：“最近邻的数据点应该属于同一类别”。此外，我推荐我和两位同学最近合著的数据挖掘科普书籍，希望大家能喜欢。

参考文献：周涛，《最简数据挖掘》