高效的動態聚類

Question

我有一組單位間隔的數據點（即帶有數值的1維數據集）。我在線收到一些額外的數據點，而且某些數據點的值可能會動態變化。我正在尋找一種能夠有效處理這些問題的理想聚類算法。

我知道sequential k-means clustering應對新增實例，我想稍作修改就可以使用動態實例值（即首先從相應的集羣中取出修改的實例，然後更新集羣的平均值並最終給出修改後的實例作爲算法的輸入，就像添加一個看不見的實例一樣）。

我對使用k-means算法的擔憂是需要提供羣集數作爲輸入。我知道他們在空間複雜性方面擊敗了其他聚類算法（GAs，MSTs，Hierarchical Methods等）。老實說，我不確定，但也許我可以逃脫使用上述算法之一。即使我的數據集相對較大，單個維度的存在也讓我感到驚訝。

更具體地說，我的一個典型測試案例將包含大約10K-200K一維數據點。我想在一秒鐘之內完成羣集。假定值點的動態變化是平滑的，即相對較小。因此，能夠使用現有的解決方案（即，當價值改變或添加新的解決方案時能夠繼續聚集現有的解決方案）是非常優選的。

因此，所有的一切：

你能想到的算法，將提供計算效率和集羣WRT的準確度之間的甜蜜點。上面定義的問題？

是否有一些很好的啓發式算法可以預先自動計算K值？

Answer 1

由於您的數據集是一維的，因此您可以根據single-linkage clustering規則使用非常簡單高效的方式動態更新羣集。該規則規定，只要第一個簇中的一個點和第二個簇中的某個點低於某個預先指定的閾值距離，就會將2個簇合併爲1。

• 構建binary search tree包含您的初始點集。
• 讓一個初始的O（n）inorder通過這個BST，它以排序順序訪問節點，找到最初的一組簇：每當當前點和最後一個之間的距離小於閾值時，add它到以前的集羣，否則啓動一個新的集羣。
• 當動態地添加一個點X時，只需在BST中搜索其兩個鄰居L和R（兩邊各一個）並像往常一樣插入它。如果X-L <閾值，則X加入L的羣集;如果R-X <閾值，則X加入R的羣集;如果兩者都是真的，那麼L的聚類和R的聚類必須結合;如果沒有一個是真的，那麼X就形成了自己的新羣集。
• 當動態刪除一個點X時，如前所述找到它的鄰居L和R，並且如果它們當前屬於同一個集羣C，則檢查R-L> threshold。如果是，則從X向左（或向右）掃描，將每個點放入新簇中，直到找到不在C中的點。
• 移動等同於刪除後跟插入。

您可以記錄每個BST節點內的每個點屬於哪個集羣。或者，如果插入占主導地位，那麼使用union/find data structure可能會更快。

Answer 2

比BST（或決策樹）另一種方法是像BIRCH algorithm層次聚類這是非常適合大型數據集，並添加新的數據點到現有的集羣，也是它的性能是最好的