跳转到内容

草稿:最近邻链算法

维基百科,自由的百科全书

背景

[编辑]
对六个点进行层次聚类的示意图。最顶端是六个待聚类的点,以下是它们形成的集群

数据分析中的许多问题都涉及聚类分析,也就是将关系相近的数据点组成集群。层次聚类是聚类分析的一种,所有的集群组成层状或树状的结构,而不是数据点的严格划分。有时候层次聚类相当于在多个尺度上同时进行聚类分析,也有时候待分析的数据本身就包含未知的树状结构,目标则是分析数据重建该种结构。这两种情况都在生物分类学等领域有广泛应用。相似性不同的生物形成了不同尺度的集群(即界、门、纲、目等)。分析当前时间点生物的多层次集群之余,人们还致力于精确重建历史上这些生物进化的过程,也就是演化树[1]

算法

[编辑]
最近邻链算法的动画演示
最近邻链算法的动画演示,使用Ward距离。黑点是数据点,灰色区域代表集群,蓝色箭头指向最近的相邻节点,红条代表当前的最近邻链。为便于显示,如果某次合并清空了当前的最近邻链,就从刚刚合并的集群开始继续算法

顾名思义,最近邻链算法反复更新集群组成的链条 ABC → ...,其中每个集群都是前一个的最近邻,直到两个集群互为最近邻为止。[2]

具体而言,算法步骤如下:[2][3]

  • 初始化剩余集群的集合,由 n 个单个点的集群组成。
  • S 为一个空,用来存放当前集群。
  • 只要剩余集群数量大于1:
    • 如果 S 为空,任选一个剩余集群加入 S
    • CS 栈顶的集群。计算 C 到所有其他集群的距离,令 D 为其中最近的集群。
    • 如果 D 已在 S 中,则必然在 C 之前一位。将这两个集群出栈且合并之。
    • 否则,如果 D 还不在 S 中,将之入栈。

如果一个集群可能有多个最近邻,则该算法就需要附加规则来决定距离相同时的情况。例如,可以给每个集群任意编号,碰到多个最近邻的情况时选择编号最小的集群。此规则可以防止算法每次执行出现不一致的结果,否则 D 可能会过早加入栈中而出现环。[4]

复杂度分析

[编辑]

该算法每次循环都会搜索一个集群的最近邻,最后要么向栈中加入一个集群,要么弹出两个集群。每个集群最多只会入栈一次、出栈一次,之后该集群就合并了,不再参与到算法中。进入过栈中的集群一共有 2n − 2 个:其中 n 个来自最开始的单个数据点形成的集群,n − 2 来自聚类过程中形成的集群,对应最终形成的二叉树的内部节点(不含根节点)。所以,算法一共进行 2n − 2 次入栈操作和 n − 1 次出栈操作。[2]

每次循环还需要扫描最多 n − 1 个集群间距找出最近邻。距离的计算和更新的总次数小于 3n2,所以算法的时间复杂度是 O(n2)[2]

该算法只用到了集合和栈来存放当前集群,所以空间复杂度相对输入数据点的数量是线性的。[2]

正确性

[编辑]

要保证该算法的正确性,每次将两个集群出栈且合并后,必须保证栈中剩下的集群仍然形成最近邻链。同时,也要保证算法产生的所有集群都和每次挑出最近两个集群合并的贪心算法相同,而合并顺序可以改变。随着集群间距计算方式的改变,这些性质也会改变。[2]

所以,算法的正确性取决于计算集群间距所用的距离函数的特性——可约性(reducibility)。该特性首次由Bruynooghe (1977)在研究早期的聚类算法时提出。[5]如果一个贪心的层次聚类算法产生的任意三个集群 ABC 都满足 AB 互为最近邻,且以下不等式成立,则称集群间的距离函数 d 是可约的:[2]

d(AB, C) ≥ min(d(A,C), d(B,C)).

若距离函数可约且 E 的最近邻是 CD 中的一个,则合并集群 CD 只会导致 E 的最近邻改变。这将带来两个推论。首先,算法每一步中,栈 S 中的集群都构成合法的最近邻链,因为一个最近邻不再是最近的时候它会立刻出栈。[2]

同时,如果贪心算法形成了集群 CD,并且在某个时间点互为最近邻,则它们接下来一直都互为最近邻,直到被贪心算法合并。因此,该算法找到的每对互为最近邻的集群都也是贪心算法所找到的,所以该算法和贪心算法得出的集群完全相同,虽然顺序可能不同。[2]

不同集群距离函数的应用

[编辑]

单链接

[编辑]

single-linkage英语Single-linkage clustering或最近邻聚类是凝聚层次聚类最古老的形式[6],其中不同集群的距离定义为两个集群中的点之间的最小距离,故有以下关系成立:

其中可约性(见上文)的大于等于号可以取到等号。单链接聚类符合Lance–Williams公式[7][6],不过 γ 是负的,所以证明可约性更为困难。

和完全链接和平均链接类似,计算集群间距的难度使得单链接集群的时空复杂度都达到 O(n2)。不过,单链接集群另有更快的算法,即用普林姆算法计算集群距离的最小生成树,将树的边权排序,由此来决定每次迭代合并哪两个集群。Within Prim's algorithm, each successive minimum spanning tree edge can be found by a 线性搜索 through an unsorted list of the smallest edges connecting the partially constructed tree to each additional vertex. This choice saves the time that the algorithm would otherwise spend adjusting the weights of vertices in its 优先队列. Using Prim's algorithm in this way would take time O(n2) and space O(n), matching the best bounds that could be achieved with the nearest-neighbor chain algorithm for distances with constant-time calculations.[8]

历史

[编辑]

最近邻链算法于1982年由Jean-Paul Benzécri英语Jean-Paul Benzécri[9]和J. Juan[10]提出并实现。他们的工作基于早前的层次聚类算法,后者也使用了互为最近邻的集群对,但没有用到最近邻链。[5][11]

参考文献

[编辑]
  1. ^ Gordon, Allan D., Hierarchical clustering, Arabie, P.; Hubert, L. J.; De Soete, G. (编), Clustering and Classification, River Edge, NJ: World Scientific: 65–121, 1996, ISBN 9789814504539 .
  2. ^ 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 Murtagh, Fionn, A survey of recent advances in hierarchical clustering algorithms (PDF), The Computer Journal, 1983, 26 (4): 354–359, doi:10.1093/comjnl/26.4.354可免费查阅 .
  3. ^ Murtagh, Fionn, Clustering in massive data sets, Abello, James M.; Pardalos, Panos M.; Resende, Mauricio G. C. (编), Handbook of massive data sets, Massive Computing 4, Springer: 513–516, 2002, Bibcode:2002hmds.book.....A, ISBN 978-1-4020-0489-6 .
  4. ^ Sedgewick, Robert, Figure 20.7, Algorithms in Java, Part 5: Graph Algorithms 3rd, Addison-Wesley: 244, 2004, ISBN 0-201-36121-3 .
  5. ^ 5.0 5.1 Bruynooghe, Michel, Méthodes nouvelles en classification automatique de données taxinomiqes nombreuses, Statistique et Analyse des Données, 1977, 3: 24–42 .
  6. ^ 6.0 6.1 引用错误:没有为名为lance-williams的参考文献提供内容
  7. ^ 引用错误:没有为名为mirkin的参考文献提供内容
  8. ^ Gower, J. C.; Ross, G. J. S., Minimum spanning trees and single linkage cluster analysis, Journal of the Royal Statistical Society, Series C, 1969, 18 (1): 54–64, JSTOR 2346439, MR 0242315 .
  9. ^ Benzécri, J.-P., Construction d'une classification ascendante hiérarchique par la recherche en chaîne des voisins réciproques, Les Cahiers de l'Analyse des Données, 1982, 7 (2): 209–218 
  10. ^ Juan, J., Programme de classification hiérarchique par l'algorithme de la recherche en chaîne des voisins réciproques, Les Cahiers de l'Analyse des Données, 1982, 7 (2): 219–225 .
  11. ^ de Rham, C., La classification hiérarchique ascendante selon la méthode des voisins réciproques, Les Cahiers de l'Analyse des Données, 1980, 5 (2): 135–144 .