Python中的等級聚類的凸殼

Question

我正在使用分層聚類來嘗試將已大幅度展開爲兩維的大量數據可視化。我想要做的是創建一個可視化對象，使我可以查看層次結構中不同高度的數據，將聚類渲染爲其構成點的凸包。這個問題最棘手的部分是我需要一個算法，可以有效地合併對羣集的凸包，當我向上移動層次結構時。我已經看到很多用於計算O（n log n）時間點的凸包的算法，但似乎在這種情況下利用問題的子結構會更有效率，但是我不完全確定如何。

編輯：

有關詳細信息，該數據結構是與聚類的原始點開始，然後說這點/簇被組合，以形成下一個簇的陣列。所以它有點像樹/指針結構，但包含在一個大的數組中。重要的部分是看看兩個組成羣集是什麼樣的超級羣集是有效的，但是獲取屬於羣集的所有點的集合是無效的。所以任何合理的算法都必須從下往上工作。

所以我們假設我們處於層次結構的某個位置，並且預先計算的層次結構表示聚類A和B被合併以產生聚類C.我們從底層開始，所以我們已經計算了因此我們只需要將它們組合起來就可以生成簇C的凸包。簇A的凸包實際上可以是單個點，一對或完整的多邊形。集羣B也是如此。因此，有幾種情況應該如何合併這些集羣以形成集羣C的凸包，但我敢打賭，有一種巧妙的解決方案，可能會將單例視爲與多邊形相同的方式。

最明顯的解決方案是用集合A和B的凸包的組合集合來計算凸包。但是我需要在100k點的層次結構上做這件事，所以我想知道是否有A和B.

編輯2的凸包結合更有效的方式：

  /----5 
    1---/ /\ 
/\ /B 8 
    2 A 3 C 6 /
    \/ \/
    4--------7 

好了，所以我試圖ASCII了我的意思的說明。 A羣的凸包爲1-2-3-4，B的凸包爲5-6-7-8，C的凸包爲1-2-4-7-8-5。據推測，集羣A和B在其外殼內包含額外的點，但這些顯然不可能成爲C的殼體的一部分，所以問題是確定將集羣A和B的殼體「拼接」以形成C的船體，基於點的座標。這是整個過程的歸納步驟。 （最終C將與D集合在一起，直到算法以最頂部的集羣結束，這個集羣的凸包就是所有點的凸包）。

Answer 1

我知道至少有兩個凸包合併算法--Toussaint的rotating calipers（本文的第5部分）和Preparata和Hong的bridging algorithm（請參閱本文的第3部分）。這兩種算法需要時間線性中H =ħ + H，其中ħ和ħ是船體的船體頂點的在第一和第二凸的數量分別。

Answer 2

有多種方法可以讓您在添加新點時「更新」凸包。另外一些凸包和Delauney三角剖分的方法已經很好地解決了，這應該很好地解決這個問題。看看s-hull算法。

但是，由於您正在討論層次聚類，因此在涉及到複雜性時，凸包可能是您最擔心的問題。

分層聚類不能很好地擴展到大數據集，因爲算法本質上通常是O(n^3)（使它們成爲實踐中仍然使用的最慢聚類算法之一）。因此，另外計算一些凸包應該是而不是可以產生很大的差別，因爲您的羣集更昂貴。您可能只需要一個快速，增量式的凸包算法實現。