草稿:最近鄰鏈算法

背景

對六個點進行層次聚類的示意圖。最頂端是六個待聚類的點，以下是它們形成的集群

數據分析中的許多問題都涉及聚類分析，也就是將關係相近的數據點組成集群。層次聚類是聚類分析的一種，所有的集群組成層狀或樹狀的結構，而不是數據點的嚴格劃分。有時候層次聚類相當於在多個尺度上同時進行聚類分析，也有時候待分析的數據本身就包含未知的樹狀結構，目標則是分析數據重建該種結構。這兩種情況都在生物分類學等領域有廣泛應用。相似性不同的生物形成了不同尺度的集群（即界、門、綱、目等）。分析當前時間點生物的多層次集群之餘，人們還致力於精確重建歷史上這些生物進化的過程，也就是演化樹。

算法

最近鄰鏈算法的動畫演示，使用Ward距離。黑點是數據點，灰色區域代表集群，藍色箭頭指向最近的相鄰節點，紅條代表當前的最近鄰鏈。為便於顯示，如果某次合併清空了當前的最近鄰鏈，就從剛剛合併的集群開始繼續算法

顧名思義，最近鄰鏈算法反覆更新集群組成的鏈條 A → B → C → ...，其中每個集群都是前一個的最近鄰，直到兩個集群互為最近鄰為止。

具體而言，算法步驟如下：

• 初始化剩餘集群的集合，由 n 個單個點的集群組成。
• 令 S 為一個空棧，用來存放當前集群。
• 只要剩餘集群數量大於1：
  • 如果 S 為空，任選一個剩餘集群加入 S。
  • 令 C 為 S 棧頂的集群。計算 C 到所有其他集群的距離，令 D 為其中最近的集群。
  • 如果 D 已在 S 中，則必然在 C 之前一位。將這兩個集群出棧且合併之。
  • 否則，如果 D 還不在 S 中，將之入棧。

如果一個集群可能有多個最近鄰，則該算法就需要附加規則來決定距離相同時的情況。例如，可以給每個集群任意編號，碰到多個最近鄰的情況時選擇編號最小的集群。此規則可以防止算法每次執行出現不一致的結果，否則 D 可能會過早加入棧中而出現環。

複雜度分析

該算法每次循環都會搜索一個集群的最近鄰，最後要麼向棧中加入一個集群，要麼彈出兩個集群。每個集群最多只會入棧一次、出棧一次，之後該集群就合併了，不再參與到算法中。進入過棧中的集群一共有 2n − 2 個：其中 n 個來自最開始的單個數據點形成的集群，n − 2 來自聚類過程中形成的集群，對應最終形成的二元樹的內部節點（不含根節點）。所以，算法一共進行 2n − 2 次入棧操作和 n − 1 次出棧操作。

每次循環還需要掃描最多 n − 1 個集群間距找出最近鄰。距離的計算和更新的總次數小於 3n²，所以算法的時間複雜度是 O(n²)。

該算法只用到了集合和棧來存放當前集群，所以空間複雜度相對輸入數據點的數量是線性的。

正確性

要保證該算法的正確性，每次將兩個集群出棧且合併後，必須保證棧中剩下的集群仍然形成最近鄰鏈。同時，也要保證算法產生的所有集群都和每次挑出最近兩個集群合併的貪心算法相同，而合併順序可以改變。隨著集群間距計算方式的改變，這些性質也會改變。

所以，算法的正確性取決於計算集群間距所用的距離函數的特性——可約性（reducibility）。該特性首次由Bruynooghe (1977)在研究早期的聚類算法時提出。如果一個貪心的層次聚類算法產生的任意三個集群 A、B、C 都滿足 A 和 B 互為最近鄰，且以下不等式成立，則稱集群間的距離函數 d 是可約的：

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

若距離函數可約且 E 的最近鄰是 C 或 D 中的一個，則合併集群 C 和 D 只會導致 E 的最近鄰改變。這將帶來兩個推論。首先，算法每一步中，棧 S 中的集群都構成合法的最近鄰鏈，因為一個最近鄰不再是最近的時候它會立刻出棧。

同時，如果貪心算法形成了集群 C 和 D，並且在某個時間點互為最近鄰，則它們接下來一直都互為最近鄰，直到被貪心算法合併。因此，該算法找到的每對互為最近鄰的集群都也是貪心算法所找到的，所以該算法和貪心算法得出的集群完全相同，雖然順序可能不同。

不同集群距離函數的應用

單連結

single-linkage或最近鄰聚類是凝聚層次聚類最古老的形式，其中不同集群的距離定義為兩個集群中的點之間的最小距離，故有以下關係成立：

$d(A\cup B,C)=\min(d(A,C),d(B,C)),$

其中可約性（見上文）的大於等於號可以取到等號。單連結聚類符合Lance–Williams公式，不過 γ 是負的，所以證明可約性更為困難。

和完全連結和平均連結類似，計算集群間距的難度使得單連結集群的時空複雜度都達到 O(n²)。不過，單連結集群另有更快的算法，即用普林姆算法計算集群距離的最小生成樹，將樹的邊權排序，由此來決定每次迭代合併哪兩個集群。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(n²) and space O(n), matching the best bounds that could be achieved with the nearest-neighbor chain algorithm for distances with constant-time calculations.

歷史

最近鄰鏈算法於1982年由Jean-Paul Benzécri和J. Juan提出並實現。他們的工作基於早前的層次聚類算法，後者也使用了互為最近鄰的集群對，但沒有用到最近鄰鏈。