BIRCH聚類分析法及其改進

(西北師范大學 甘肅 蘭州 730000)

一、引言

21世紀是數據引領的時代，信息技術高速發展，數據庫和信息傳播方式都高度發達。互聯網作為數據的載體已經被企業和個人廣泛的應用，計算機普及讓數據存儲變得尤為便捷，從國家統計部分發布的數據至網絡爬蟲數據，人們可以輕松獲得各項數據，但對大數據的分析方法依然較少，繁瑣數據處理的效率問題也備受人們關注。如何對所需數據包含的信息精準提煉和分析成為了目前研究的熱門。通常，一些計算機軟件可以自主地、迅速地對各項歷史數據歸納，進一步為生產決策提供指導信息。計算機處理是基于對數據挖掘的合理算法，但因為對處理環境的前提假設較多，致使各種教材內的算法應用于實際案例情況時還存在諸多不兼容。本文基于大數據環境下，介紹一種較為高效的BRICH(利用層次方法的平衡迭代規約和聚類)方法，并基于方法應用于實例中的合理性，提出對閾值適當修正的猜想。

二、BIRCH聚類算法介紹

(一)從聚類分析原理到BIRCH聚類法

聚類分析在統計學中有很大的應用，特別是在多元統計分析中的使用。聚類分析應用的領域也十分廣泛，在模式識別和數據挖掘這兩個領域中，聚類分析更是其核心內容。而在最近幾年的發展看來，聚類分析技術在數據挖掘這一研究方向中的生命力和創造力更顯得突出[1]。在過去的幾十年，許多聚類算法都得到了很大的發展,不同的標準決定聚類工作不同的算法,有時聚類相似度測量的平均值(重心)的對象在一個聚類中,或者每個聚類是由其中心附近的一個聚類的對象。在分層算法里，如BIRCH算法和CURE算法，它是生成一組被組織為分層樹的嵌套聚類。還有基于網格的算法，如STING、CLIQUE和Wave聚類是基于多層次網格結構的，在此基礎上執行所有聚類操作。在基于模型的算法(cob-web等)中，模型假設每個聚類都能找到最適合所有其他聚類的模型。基于密度的概念是一種常見的聚類方法，它基于這樣一種觀點，即形成一個密集區域的對象應該被分組到一個聚類中[2]。像DBSCAN、DENCLUE、CURD和OPTICS這樣的算法，在一個由低密度區域分隔的特征空間中搜索高密度區域。大多數聚類方法都需要設置用戶指定的參數或先前的知識來生成最佳結果。確定參數是一項艱巨的任務，但對聚類結果有重大影響。此外，對于許多實際的數據集來說，沒有精確地描述內部聚類結構的全局參數設置。BIRCH算法在處理高維復雜的大數據具有較大的優勢，它生成數據集的層次化分區，并確保聚類中兩個元素之間的最大距離小于給定的單個閾值，保證了算法的有效性和準確性[3]。

層次聚類算法主要有兩類，即由上到下的分裂層次聚類和由下到上的凝聚層次分類。BIRCH既包含了分裂層次聚類也包含了凝聚層次分類。它使用這種聚類特征(Clustering Feature 簡稱CF)和聚類特征樹(Clustering Feature Tree 簡稱CF-tree)兩個概念來進行一般的聚類描述。聚類特征樹概述了聚類的有用的信息,使得空間遠小于集合的元數據可以存儲在內存中,從而改善聚類大型數據集的算法在速度和可伸縮性，非常適合處理離散和連續屬性數據聚類問題，因此BIRCH算法常用來處理大數據的高質量聚類[4]。在BIRCH中，一個節點稱為聚類特征。它是一個或多個點的底層聚類的一小部分表示，其中足夠接近的點應該被視為一個群體。聚類特性被存儲為三個值的向量:CF=(n,LS,SS)。線性和(LS)，平方和(SS)，以及簇中所覆蓋的點數(n)。所有這些度量可以只使用基本的數學公式計算:

其中，R是每個樣本到聚類中心的平均距離，D是簇內兩兩樣本點的平均距離。R和D都反映了聚類的質量和準確程度。當然我們也可以計算任意兩個簇之間的距離：

如果除去聚類中點的數量，線性和就會標記該群集的中心。根據公式，可以迭代地計算這兩個值。樹中的任何聚類特征都可以通過添加其子聚類特征來計算:也就是說，聚類特征是可加的，對于兩個不相交的簇CF1和CF2，其聚類特征分別為CF1=(n1,LS1,SS1)和CF2=(n2,LS2,SS2),合并CF1和CF2后的簇的聚類特征是:

CF1+CF2=(n1+n2,LS1+LS2,SS1+SS2)

(二)聚類特征樹的生成和BIRCH算法的實現

聚類特征樹(CF樹)的生成是BIRCH聚類關鍵和基礎，具體操作步驟如下：

在最開始的時候，圖1左1只有一個樣本點被讀取，這里給定一個嶄新的三元組A，該三元組的n=1，因此在CF樹中將A納入新的CF根節點。

圖1 BRICH聚類過程圖

繼續讀取下一個樣本點，如圖1左2，若樣本點到A的距離小于給定閾值T的話，則與第一個樣本點同屬于一個CF，因此將其納入第一個中，此時新的三元組n=2；

圖1右2讀取的新樣本點到原有的CF距離大于閾值T，則不能納入原有的CF，此時創建新的三元組CF來包含新讀取的樣本，相應的根節點也變成了兩個聚類特征A和B；

圖1右1讀取下一個樣本點，該樣本點距離B的半徑小于閾值T，則納入B的聚類特征中；

圖2 BRICH聚類過程圖(續)

假設該CF樹的葉節點因子L=3，當葉節點已經存在3個的時候，有新樣本sc8被讀取后距離原有的葉節點LN1較近，如圖2左，判斷新樣本是否屬于原有的枝節點LN1，由于葉節點因子的限制L=3，也就是說該聚類特征的葉節點最大值為3，不能創建新的CF，此時只能分裂原有的葉節點LN1；

如何分裂原有的枝節點LN1呢？找出LN1里所有的CF，將其中距離最遠的兩個CF作為新的葉子節點的質心，然后將sc1、sc2、sc3、sc8重新歸納到兩個新的葉節點，即將LN1分為兩部分，如圖2中；

如果CF樹給定的枝節點因子B=3的話，此時葉節點的分裂會導致根節點超出最大限制，如圖2右，那么相應的根節點此時也需要分裂，方法同葉節點分裂一樣。

BIRCH聚類算法的實現分為四個階段。在第一階段中，讀取所有的樣本數據，初始CF樹是由枝節點平衡因子B、葉節點平衡因子L、閾值T所構建。第二階段是一個可選的階段，篩選初始的CF樹，去除了一些異常的聚類特征節點(通常是樣本點很少的CF)，因此初始的CF樹將會縮小。數據點的全局聚類是在初始CF樹，第二階段里較小的樹將在第三階段中執行。第三階段也是一個可選的階段，這里可以利用一些其他的聚類法(如K-MEANS聚類)對所有的聚類特征(CF)進行聚類，從該算法的第三階段中可以得到較高質量的聚類，也可以消除因樣本點讀取順序不同生成的不合理CF樹。如果需要繼續提高聚類的質量，那么在聚類過程中需要使用該算法的第四階段。在該過程中，掃描離群點，接受可以被聚類特征樹吸收的樣本點，舍棄不能被吸收的點。如果可以，則吸收它們。如果不可以，則刪除它們。而算法的核心步驟便是第一階段中聚類特征樹(CF樹)生成的過程，其它三個階段都是為了更好的去優化聚類，提高聚類的質量。

三、算法改進的猜想

為了從算法中獲得高質量的聚類，給定一個合適的閾值T是必需工作，閾值是BIRCH算法最重要的參數。通過調整閾值參數T，可以控制數的高度，即原數據集中的數據被壓縮的程度。基于BIRCH算法的聚類測試結果表明，該方法的時間要求相當依賴于閾值的參數和算法中最大的分支因子。如果閾值參數從最優值下降，那么BIRCH算法產生的集合的數量將呈指數增長。基于BIRCH算法的預聚類算法，聚類的指數增長也會使算法的成本增加。如果閾值參數大于最優值，然后增加的點數量增加，需要持續增加額外成本，表示集的葉節點是聚集的。也有學者提出了一種不同的方式中提出了一些優化算法優化關鍵參數(如分支系數、質量標準和選擇的分隔線)的BIRCH聚類算法,最后用動態方法在建立閾值中央點數據[5]。

單個閾值往往會表現出很多不足的地方，特別是在精度方面。當閾值很小的時候，大的聚類將根據閾值被劃分成許多聚類，另一方面由于使用不合適的閾值，增加的小型聚類可以合并成一個聚類并且吸收周圍的嘈雜的數據點[6]。在最特殊的情況下，聚類的大小和密度將會有所不同，從而得出結論，在BIRCH的CF樹中，所有CF項都沒有最佳的閾值。該算法在閾值為0時開始以最大的精度開始，并且隨著CF樹的規模大于可用內存，它會反復嘗試尋找合適的聚類大小。在算法中，每一個葉節點的所有條目必須滿足一個統一的閾值，并且在每個階段由不同的閾值重建CF樹。在聚類特征樹中使用的每一個聚類特征都是一個或多個點的底層聚類的一個小聚類表示。在大多數情況下，這些聚類的大小是不相等的，因此沒有一個最佳閾值適合用于構建整個CF樹及其CF條目,使用單一閾值在構建CF樹原始BIRCH算法將導致許多缺點。為了解決這個問題,是否可以提出一個改進的CF樹,使用多個不同的閾值的假設,閾值屬于一個特定的葉子CF條目,換句話說使用閾值的數量中CF樹就等于CF條目數量，和這些閾值不相等,將期間動態地改變聚類操作,這種方法會導致修改原來葉CF聚類結構。另外也可減少了聚類算法的空間和時間復雜度，能更好的將數據劃分為合適的簇，BIRCH算法更多的是考慮了簇內數據間對象的關系，而并沒有研究簇與簇之間的關系[7]。在復雜的實際應用中，重要的不僅是對相似數據的研究，更多的還是挖掘不同數據間的關系，這是數據挖掘的核心。因此，為了能更好的挖掘信息，對BIRCH算法的改進也可以采用多層次模式，即在第一次優化分類后，著重對大小懸殊較大的簇進行二次分析。在此過程中，即可再根據簇的大小以及內存的限制來選取不同的閾值。

四、結束語

本文主要是結合了實例來具體分析了BIRCH算法，對其基本原理有了深入的分析。傳統的BIRCH聚類算法有不足之處，因為其無法聚集任意形狀來控制直徑的星云簇的邊界。在此基礎上，從改變閾值T以及多層次分析數據方面提出了改進的意見。實驗表明，所提出的算法對任何形狀的聚類都具有高效和可擴展性，實現增量聚類，消除了噪聲。聚類應用的領域非常廣，在氣象分析、圖像處理、模式識別、食品檢驗、生物醫藥等眾多領域都廣泛應用。本文也提出了利用多閾值對BIRCH算法進行改進的方法，而不是基本的BIRCH算法中使用的閾值。目前來看傳統算法較多應用與低維度數據的處理，但在處理復雜的實際情況時，現有的算法有著很大的缺陷，因此高維數據的聚類分析是現階段聚類分析的研究熱點和難點。