什麼是STREAM？

STREAM 是一種針對 k-均值問題的單遍常數因子近似演算法。k-均值問題是將 N 個數據點聚類成 k 個簇或組，使得點與其所屬簇中心之間的平方誤差和 (SSQ) 最小化。其思想是將相似的點分配到同一個簇中，而這些點與其他簇中的點不同。

在流資料模型中，資料點只能檢視一次，並且記憶體和時間有限。它可以實現高質量的聚類，STREAM 演算法以 m 個點的桶（或批次）處理資料流，每個桶都適合主記憶體。

對於每個桶 b_i，STREAM 將桶中的點聚類成 k 個簇。然後，它透過僅保留關於 k 箇中心的資訊來總結桶資訊，每個簇中心都按分配給其簇的點數加權。

然後，STREAM 丟棄點，只保留中心資訊。由於已經收集了足夠的中心，因此對加權中心進行聚類以生成另一組 O(k) 個簇中心。重複此過程，以便在每一層最多保留 m 個點。這種方法產生了一種單遍、O(kN) 時間、O(N^ε) 空間（對於某個常數 ε < 1）的常數因子近似演算法，用於資料流 k-均值。

STREAM 改變了具有確定區域和時間的質量 k-均值聚類。但是，它既沒有處理記錄的演變也沒有處理時間粒度。聚類可能會被流中較舊、過時的資料所支配。簇的特徵會隨著評估它們的時刻和測量它們的時間範圍而變化。

例如，使用者可能需要測試上週、上個月或去年出現的叢集。這些可能是不同的。因此，資料流聚類演算法還必須支援以互動方式計算使用者定義時間段內叢集的靈活性。

CluStream 是一種基於使用者指定的線上聚類查詢的演變資料流聚類演算法。它將聚類過程分為線上和離線元件。

線上元件使用微簇計算並存儲關於資料流的彙總統計資訊，並執行微簇的增量線上計算和維護。離線元件進行宏觀聚類，並使用儲存的彙總統計資訊解決多個使用者問題，這取決於傾斜時間框架模型。

基於歷史和當前流資料資訊對簇演變資料流進行聚類，採用傾斜時間框架模型（如漸進對數模型），根據資料的近期性儲存不同粒度級別的一組微簇的快照。

Ginni

更新於：2022年2月17日

328 次瀏覽

啟動您的職業生涯

完成課程獲得認證

開始學習