BIRCH

BIRCH(Balanced Iterative Reducing and Clustering using Hierarchies)是一個綜合的層次聚類算法。它用到了聚類特徵(Clustering Feature, CF)和聚類特徵樹(CF Tree)兩個概念,用於概括聚類描述。聚類特徵樹概括了聚類的有用信息,並且占用空間較元數據集合小得多,可以存放在記憶體中,從而可以提高算法在大型數據集合上的聚類速度及可伸縮性

算法簡介

Zhang 等人提出了Birch(Blanced Iterative Reducing and Clustering) 算法來對大規 模數據集進行聚類。Birch 算法是一種非常有效的、傳統的層次聚類算法,該算法能夠用一 遍掃描有效地進行聚類,並能夠有效地處理離群點。Birch 算法是基於距離的層次聚類,綜 合了層次凝聚和疊代的重定位方法,首先用自底向上的層次算法,然後用疊代的重定位來改 進結果。[2]層次凝聚是採用自底向上策略,首先將每個對象作為一個原子簇,然後合併這些 原子簇形成更大的簇,減少簇的數目,直到所有的對象都在一個簇中,或某個終結條件被滿 足。

算法描述

核心思想

Birch 算法 的主要思想是:通過掃描資料庫,建立一個初始存放於記憶體中的聚類特徵樹, 然後對聚類特徵樹的葉結點進行聚類。它的核心是聚類特徵(CF)和聚類特徵樹(CF Tree)。 2.1.1 CF CF 是指三元組CF=(N,LS,SS),用來概括子簇信息,而不是存儲所有的數據點。 其中:N:簇中d 維點的數目; LS:N 個點的線性和;SS:N 個點的平方和。比如給定一 個由二維點組成的集合{(3,4),(2,6),(4,5)},那么: CF 結構概括了簇的基本信息,並且是高度壓縮的,它存儲了小於實際數據點的聚類信 息。[3]同時CF 的三元結構設定使得計算簇的半徑、簇的直徑、簇與簇之間的距離等非常容 易。

CF Tree

CF 樹 是一棵具有兩個參數的高度平衡樹,用來存儲層次聚類的聚類特徵。它涉及到兩 個參數分支因子和閾值。其中,分支因子B 指定子節點的最大數目,即每個非葉節點可以 擁有的孩子的最大數目。閾值T 指定存儲在葉節點的子簇的最大直徑,它影響著CF 樹的大 小。改變閾值可以改變樹的大小。CF 樹是隨著數據點的插入而動態創建的,因此該方法是 增量的。 CF 樹的構造過程實際上是一個數據點的插入過程[4],其步驟為:

(1) 從根節點root 開始遞歸往下,計算當前條目與要插入數據點之間的距離,尋找距 離最小的那個路徑,直到找到與該數據點最接近的葉節點中的條目。

(2) 比較計算出的距離是否小於閾值T,如果小於則當前條目吸收該數據點;反之,則 繼續第三步。

(3) 判斷當前條目所在葉節點的條目個數是否小於L,如果是,則直接將數據點插入作 為該數據點的新條目,否則需要分裂該葉節點。分裂的原則是尋找該葉節點中距離最遠的兩 個條目並以這兩個條目作為分裂後新的兩個葉節點的起始條目,其他剩下的條目根據距離最 小原則分配到這兩個新的葉節點中,刪除原葉節點並更新整個CF 樹。

當數據點無法插入時,這個時候需要提升閾值T 並重建樹來吸收更多的葉節點條目, 直到把所有數據點全部插入完畢。

在 CF 樹重建過程中,通過利用老樹的葉節點來重新構建一棵新樹,因而樹的重建過程 不需要訪問所有點,即構建CF 樹只需訪問數據一次就行

算法步驟

Birch 算法 主要分為以下兩個階段:

(1) 掃描資料庫,動態的建立一棵存放在記憶體的CF 樹。若記憶體不夠,則增大閾值,在 原樹基礎上構造一棵較小的樹。

(2) 對葉節點進一步利用一個全局性的聚類算法,改進聚類質量。 由於 CF 樹的葉節點代表的聚類可能不是自然的聚類結果,原因是給定的閾值限制了簇 的大小,並且數據的輸入順序也會影響到聚類結果。因此,需要對葉節點進一步利用一個全 局性的聚類算法,改進聚類質量。

相關詞條

相關搜尋

熱門詞條

聯絡我們