基于連通距離和連通強度的BIRCH改進(jìn)算法

樊仲欣 王興 苗春生

摘 要：為解決利用層次方法的平衡迭代規(guī)約和聚類（BIRCH）算法聚類結(jié)果依賴于數(shù)據(jù)對象的添加順序，且對非球狀的簇聚類效果不好以及受簇直徑閾值的限制每個簇只能包含數(shù)量相近的數(shù)據(jù)對象的問題，提出一種改進(jìn)的BIRCH算法。該算法用描述數(shù)據(jù)對象個體間連通性的連通距離和連通強度閾值替代簇直徑閾值，還將簇合并的步驟加入到聚類特征樹的生成過程中。在自定義及iris、wine、 pendigits數(shù)據(jù)集上的實驗結(jié)果表明，該算法比多閾值BIRCH、密度改進(jìn)BIRCH等現(xiàn)有改進(jìn)算法的聚類準(zhǔn)確率更高，尤其在大數(shù)據(jù)集上比密度改進(jìn)BIRCH準(zhǔn)確率提高6個百分點，耗時降低61%。說明該算法能夠適用于在線實時增量數(shù)據(jù)，可以識別非球形簇和體積不均勻簇，具有去噪功能，且時間和空間復(fù)雜度明顯降低。

關(guān)鍵詞：層次聚類;在線算法;BIRCH;聚類特征;聚類特征樹

中圖分類號：TP312

文獻(xiàn)標(biāo)志碼：A

文章編號：1001-9081（2019）04-1027-05

Abstract： Focusing on the issues that clustering results of Balanced Iterative Reducing and Clustering using Hierarchies （BIRCH） depend on the adding order of data objects， BIRCH has poor clustering effect on non-convex clusters， and each cluster of BIRCH can only contain a similar number of data objects because of the cluster diameter threshold， an improved BIRCH algorithm was proposed. In this algorithm， the cluster diameter threshold was replaced by connectivity distance and intensity threshold which described the connectivity between the data objects， and cluster merging step was added into the generation of cluster feature tree. Experimental result on custom and iris， wine， pendigits datasets show that the proposed algorithm has higher clustering accuracy than the existing improved algorithms such as multi-threshold BIRCH and density-improved BIRCH; especially on large datasets， the proposed algorithm has accuracy increased by 6 percentage points and running time reduced by 61% compared to density-improved BIRCH. The proposed algorithm can be applied to online real-time incremental data processing and identify non-convex clusters and clusters with uneven volume， has denoising function and significantly reduces time-complexity and space-complexity.

Key words： hierarchical clustering; on-line algorithm; Balanced Iterative Reducing and Clustering using Hierarchies （BIRCH）; Cluster Feature （CF）; Cluster Feature Tree （CF Tree）

0?引言

利用層次方法的平衡迭代規(guī)約和聚類（Balanced Iterative Reducing and Clustering using Hierarchies， BRICH）算法[1]是具有代表性的分層聚類算法，該算法的特點在于在線實時運行，計算流程簡單，算法時間空間效率高，且可識別噪聲。

該算法通過構(gòu)建一個聚類特征樹（Cluster Feature Tree， CF Tree），樹中每個節(jié)點的聚類特征向量如下：CF=（N，LS，SS）

其中：N是簇中對象數(shù)目;LS是N個對象線性和∑Ni=1xi;SS是N個對象平方和∑Ni=1xi2。

合并兩個簇只需要兩個聚類特征向量算術(shù)相加即可，而計算簇距離、簇直徑只需要用到（N，LS，SS）這三個值就足夠了。但該算法的缺點在于結(jié)果依賴于數(shù)據(jù)對象的加入順序，

對非球狀的簇和對高維數(shù)據(jù)聚類效果不好，而且受簇直徑閾值T的限制，每個簇只能包含數(shù)量相近的數(shù)據(jù)對象。

在最初的BIRCH算法的基礎(chǔ)上，后期有不少學(xué)者對其進(jìn)行了改進(jìn)。邵峰晶等[2-3]提出了動態(tài)閾值及多閾值T的方法，解決了各簇的數(shù)據(jù)對象數(shù)量差距大時使用統(tǒng)一T值導(dǎo)致的問題，并引入了分割因子的概念消除了簇分裂中的不確定性。仰孝富[4]提出了文本聚類算法TCBIBK（Text Clustering algorithm Based on Improved BIRCH and K-nearest neighbor），在BIRCH聚類前先做K近鄰劃分的數(shù)據(jù)預(yù)處理，以提高聚類精度。曾曉迪等[5-6]則采用了二次聚類的辦法，在BIRCH的聚類基礎(chǔ)上再對各簇用K中心點（K-mediods）[7]、K均值（K-means）[8]等算法進(jìn)行聚類，實現(xiàn)了發(fā)現(xiàn)任意形狀簇的功能目標(biāo)。韋相等[9-10]為了解決非球形簇的聚類問題，直接改進(jìn)了BIRCH算法，先建立起多閾值的多棵聚類特征樹代表各個簇，再合并樹，用具有噪聲的基于密度的聚類（Density-Based Spatial Clustering of Applications with Noise， DBSCAN）方法[11]、高斯混合模型（Gaussian Mixture Model， GMM）[12]、K-means或譜聚類（Spectral Clustering）[13-14]等方法進(jìn)行全局聚類。

上述各種BIRCH聚類改進(jìn)算法均存在一些問題：動態(tài)閾值和多閾值T的方法不能突破球形簇限制;聚類預(yù)處理和二次聚類方法則都是結(jié)合多種已有算法，并未對BIRCH算法進(jìn)行本質(zhì)性的提升，且不適用于在線實時數(shù)據(jù);而建立多棵聚類特征樹的方法其算法比較繁瑣，時間空間復(fù)雜度高，且由于需要全局聚類，部分算法還需要根據(jù)具體應(yīng)用選擇聚類方式。

因此，本文提出一種改進(jìn)的BIRCH算法（簡稱連通改進(jìn)BIRCH），該算法使用描述數(shù)據(jù)對象個體間連通性的連通距離和連通強度閾值替代簇直徑T，同時還將簇合并的步驟加入到聚類特征樹的生成過程中，以解決上述問題。

1?算法原理

本文借鑒了DBSCAN中區(qū)域半徑Eps和鄰域?qū)ο髷?shù)閾值MinPts的概念，對BIRCH算法進(jìn)行了如下幾點改進(jìn)：1）將簇直徑閾值T改為簇的連通距離閾值D和連通強度閾值I。

2）將聚類特征向量由CF=（N，LS，SS）改為CF=（N），同時在每個數(shù)據(jù)對象中增加一個數(shù)據(jù)項M，M為數(shù)據(jù)對象的模的平方。

3）每個新增的數(shù)據(jù)對象不再是先加入最近的簇再依據(jù)簇直徑閾值分裂聚類特征樹節(jié)點，而是直接依據(jù)連通距離D和連通強度I，將新加入的數(shù)據(jù)對象和已有的若干簇合并，或者將新數(shù)據(jù)對象直接作為新簇加入聚類特征樹，再像BIRCH算法那樣分裂節(jié)點最終生成聚類特征樹。簡而言之，就是將原來BIRCH算法的簇分裂變?yōu)榇叵群喜⒃俜至训乃惴ā?/p>

1.1?連通距離閾值D和連通強度閾值I

定義1?連通距離。連通距離即兩個簇之間最接近的數(shù)據(jù)對象的距離，該距離用歐氏距離：dis=（x1-y1）2+…+（xn-yn）2，x1x2…xn和y1y2…yn分別為兩個數(shù)據(jù)對象的向量表示。

定義2?連通距離閾值。連通距離閾值即判斷兩個簇是否連通的閾值，如兩個簇間的連通距離小于等于連通距離閾值則為連通的簇，反之則為不連通的簇。

定義3?連通強度。連通強度即連通距離閾值范圍內(nèi)的數(shù)據(jù)對象個數(shù)。

定義4?連通強度閾值。連通強度閾值即判斷兩個簇是否為強連通的閾值，如兩個簇間的連通強度大于等于連通強度閾值則為強連通簇（或稱為簇核），反之則為弱連通簇（或稱為干擾點）。

使用連通距離閾值D和連通強度閾值I代替簇直徑閾值T，該方法具有可以發(fā)現(xiàn)任意形狀簇和排除干擾點干擾這兩大優(yōu)點。首先，使用連通距離只描述簇中數(shù)據(jù)對象個體間的連通性，而不像簇直徑描述的是簇中數(shù)據(jù)對象的整體范圍體積，因此可以通過該連通性發(fā)現(xiàn)任意形狀簇，且適用于簇與簇數(shù)據(jù)對象數(shù)量差距大的情況。其次，現(xiàn)實情況中的數(shù)據(jù)集往往因為主觀的和客觀的各種原因而存在干擾點，使得數(shù)據(jù)的聚類達(dá)不到理想的效果，所以為了排除干擾，需要定義連通強度將簇中數(shù)據(jù)對象最密集的部位（即簇核）給篩選出來作為強連通簇，而被篩選掉的數(shù)據(jù)對象則是弱連通簇或干擾點，干擾點并不一定就是必須去除掉的噪點，因為在很多情況下干擾點確實是客觀存在的，因此應(yīng)將其作為簇的非簇核部分重新合并入簇中，但在合并入簇的過程中如果干擾點與簇核的距離大于連通距離閾值D，則可以確定此干擾點為噪點。

1.2?聚類特征向量融入到數(shù)據(jù)對象中

由于連通距離和連通強度描述的是數(shù)據(jù)對象個體間連通性的參數(shù)，因此BIRCH算法原有CF聚類特征向量中的LS和SS聚類特征（用于計算簇心和簇直徑）便不再需要，取而代之的是計算簇與簇之間任意兩個數(shù)據(jù)對象距離的參數(shù)，該參數(shù)在計算簇與簇最近距離時需要用到。

根據(jù)三角形余弦定理，已知兩邊邊長AL和BL及兩邊夾角θ求第三邊邊長CL：

那么現(xiàn)以坐標(biāo)原點O和向量a、b為三角形的三個頂點，則用向量c的模表示a和b間的距離，其值為：

其中：a、b為向量的模，由此公式可知只要有數(shù)據(jù)對象的模和內(nèi)積就可以求出距離，因此在每個數(shù)據(jù)對象中增加一個數(shù)據(jù)項：模平方M=（a12+a22+…+an2）。該數(shù)據(jù)項可以優(yōu)化距離的計算，每次加入新的數(shù)據(jù)對象時就算好M的值存儲下來，后面計算任意數(shù)據(jù)對象到該數(shù)據(jù)對象的距離就主要計算一下內(nèi)積就可以求出結(jié)果。

1.3?聚類特征樹的簇先合并再分裂

簇分裂的算法和BIRCH相同，在此不再敷述，而增加的簇合并的算法結(jié)合連通距離作為簇聚類的限制參數(shù)，可以避免數(shù)據(jù)加入順序隨機(jī)導(dǎo)致的聚類結(jié)果隨機(jī)。因為簇直徑隨著數(shù)據(jù)加入順序的不同，其值的變化方式也是不同的，當(dāng)其變化曲線為上凸形狀時就有可能會將同一個簇的數(shù)據(jù)對象分割到不同簇中，而BIRCH算法的簇只能分裂不能合并，因此無法在加入一個可以連通各簇的數(shù)據(jù)對象時進(jìn)行簇的合并，所以需要采取簇先合并然后再分裂節(jié)點生成聚類特征樹的算法解決這個問題。

2?算法流程及實現(xiàn)

算法流程步驟分為三步（如圖1，其中D為連通距離閾值，I為連通強度閾值）：步驟1?數(shù)據(jù)預(yù)處理及簇的合并生成。預(yù)處理除了要讀取連通距離閾值D、連通強度閾值I、葉子節(jié)點分支因子L、非葉子節(jié)點分支因子B這四個預(yù)置聚類參數(shù)以外，還要不斷地讀取在線聚類數(shù)據(jù)，并在每次讀取時對新加數(shù)據(jù)對象追加一個數(shù)據(jù)項M，M=數(shù)據(jù)對象的模的平方。

步驟2?篩選強連通簇插入聚類特征樹，該步驟和BIRCH算法分裂節(jié)點生成聚類特征樹的流程一樣，在此不再贅述。

步驟3?弱連通簇并入強連通簇并輸出聚類特征樹，該步驟需要將先前篩選出的非簇核部分重新合并入簇中，合并的方式使用最近距離的概念，依次從弱連通簇的列表中找出距離聚類特征樹底層各個簇核最近的一個弱連通簇，將其加入到最近距離的那個簇核之中，直到所有弱連通簇全部加入完畢為止，但是距離大于閾值D的弱連通簇為噪點不加入。最后，輸出聚類特征樹底層簇的數(shù)據(jù)對象數(shù)量N及各個數(shù)據(jù)對象，還有聚類特征樹其余各層的N值及各層間的父子節(jié)點隸屬關(guān)系，作為當(dāng)前數(shù)據(jù)的在線聚類結(jié)果。

3?時間空間復(fù)雜度

對于BIRCH算法，其在給定數(shù)據(jù)占用內(nèi)存空間為MEM時的空間復(fù)雜度為O（MEM），本文算法的空間復(fù)雜度為O（MEM+MEM/d），其中d表示數(shù)據(jù)維度。

BIRCH算法加入數(shù)據(jù)對象的時間復(fù)雜度為O（dNB（1+logBMP））[1]。

本文算法時間復(fù)雜度為O（BIRCH）+O（HN+kHN）+O（sn），其中：HN為已加入的數(shù)據(jù)對象個數(shù)，k為與新加數(shù)據(jù)對象距離在閾值D內(nèi)的數(shù)據(jù)個數(shù)，sn為強連通簇所有數(shù)據(jù)對象個數(shù)。增加的O（HN+kHN）和O（sn）為圖1步驟一和步驟三的時間復(fù)雜度，考慮到數(shù)據(jù)密集時k值會比較大，因此本文算法主要時間復(fù)雜度為O（BIRCH）+O（kHN）。

4?聚類應(yīng)用

本文算法使用Windows7 64位專業(yè)版操作系統(tǒng)和Eclipse Luna Service Release 2（4.4.2）編程軟件基于一臺CPU Inter core i5-4570 3.2GHz，內(nèi)存8GB的PC上實現(xiàn)。

為驗證其有效性，使用五個數(shù)據(jù)集比較本文算法（連通改進(jìn)BIRCH）與BIRCH以及多閾值BIRCH[2]、密度改進(jìn)BIRCH[9]這四種在線實時運行算法的聚類結(jié)果。數(shù)據(jù)集1為自定義數(shù)據(jù)集：2維3050個數(shù)據(jù)對象，呈大小簇分布，帶有噪點;數(shù)據(jù)集2為自定義數(shù)據(jù)集：2維400個數(shù)據(jù)對象，呈環(huán)形和圓形分布;數(shù)據(jù)集3為iris數(shù)據(jù)集：4維150個數(shù)據(jù)對象;數(shù)據(jù)集4為wine均一化后數(shù)據(jù)集：13維178個數(shù)據(jù)對象;數(shù)據(jù)集5為pendigits數(shù)據(jù)集：16維10992個數(shù)據(jù)對象。最后三組數(shù)據(jù)集均來源于加州大學(xué)歐文分校機(jī)器學(xué)習(xí)庫（University of California Irvine Machine Learning Repository）[15]。在iris、wine和pendigits數(shù)據(jù)集中，每個數(shù)據(jù)點的類標(biāo)簽都是已知的，因此可以充分利用準(zhǔn)確率來評價算法的聚類質(zhì)量。

令A(yù)D表示數(shù)據(jù)集中的數(shù)據(jù)個數(shù)，CD表示AD中被正確劃分的數(shù)據(jù)個數(shù)，則準(zhǔn)確率為Correct_rate=CD/AD*100%。

從圖2可看出，對于具有大小簇以及包含噪點的非球形數(shù)據(jù)集1：BIRCH算法無法分割出大小簇及噪點;多閾值BIRCH算法雖然分割出了大小簇，但由于其識別非球形簇的能力很有限，所以圖中的弧形簇被分割了開來且不能識別噪點;密度改進(jìn)和連通改進(jìn)BIRCH算法則解決了這些問題，可以分割大小簇，識別弧形簇，以及去噪點。圖3的數(shù)據(jù)集2含有更加不易識別的環(huán)形簇，但密度改進(jìn)和連通改進(jìn)BIRCH算法依舊表現(xiàn)良好，可以將環(huán)形簇分割出來，而多閾值BIRCH算法則表現(xiàn)一般，BIRCH算法效果最差。值得一提的是，上述BIRCH和多閾值BIRCH算法的聚類結(jié)果具有一定隨機(jī)性，因為其結(jié)果依賴于數(shù)據(jù)的加入先后順序，而密度改進(jìn)和連通改進(jìn)BIRCH算法則解決了這一問題。

使用UCI數(shù)據(jù)集對上述四種BIRCH聚類算法進(jìn)行測試，結(jié)果如表1，其中：參數(shù)B（非葉子節(jié)點分支因子）與L（葉子節(jié)點分支因子）對所有算法及數(shù)據(jù)集的取值均為2，表中僅列出取值不一樣的參數(shù)。

從表1可看出：BIRCH算法耗時最短，但在大數(shù)據(jù)集上的準(zhǔn)確率也是最低的;多閾值BIRCH準(zhǔn)確率有所提高;密度改進(jìn)BIRCH和連通改進(jìn)BIRCH則準(zhǔn)確率提升比較明顯但同時耗時也增加不少，而其中連通改進(jìn)BIRCH算法則在大數(shù)據(jù)集上明顯更優(yōu)一些，其在pendigits數(shù)據(jù)集上的運行準(zhǔn)確率比密度改進(jìn)BIRCH提高6個百分點，且耗時減少55.2s，降低了密度改進(jìn)BIRCH算法61%的耗時量。連通改進(jìn)BIRCH算法在功能上和密度改進(jìn)BIRCH算法接近，但是耗時明顯較短。原因如下：密度改進(jìn)BIRCH由于構(gòu)建了多棵聚類特征樹所以首先在空間復(fù)雜度上明顯高于連通改進(jìn)BIRCH。其次，密度改進(jìn)BIRCH中用Eps和MinPts代替了聚類特征樹的簇直徑T，而加入數(shù)據(jù)對象時“代表點密度增加，當(dāng)它變成核心點后，還要掃描所有核心點聚類特征樹，歸入鄰近核心點”[9]，

這就相當(dāng)于連通改進(jìn)算法流程（見圖1）的步驟一中n>I為否的情況（其耗時等于本文算法的主要增加時間復(fù)雜度O（kHN）），考慮到兩種算法前后增加的計算過程，尤其是密度改進(jìn)算法還有多次合并多棵聚類特征樹的分裂節(jié)點、更新聚類特征值等較為復(fù)雜的操作，所以可見連通改進(jìn)BIRCH算法耗時更短且實現(xiàn)更為簡單。

5?結(jié)語

本文針對BIRCH及其現(xiàn)有改進(jìn)算法在不能在線實時運行、只能聚類球形簇、聚類結(jié)果依賴于數(shù)據(jù)對象的添加順序、每個簇只能包含數(shù)量相近的數(shù)據(jù)對象、算法時間空間復(fù)雜度高等方面存在的一個或若干個問題，提出了可以解決上述問題的改進(jìn)算法。本文連通改進(jìn)BIRCH算法融合了DBSCAN算法區(qū)域半徑和鄰域?qū)ο髷?shù)閾值的概念，用其代替簇直徑閾值T，并且采用簇先合并再分裂的方法，提高了BIRCH算法的適用范圍和運行性能。時間空間復(fù)雜度及實驗結(jié)果表明，該算法在損失有限的運算時間和存儲空間的前提下可以有效地提高聚類準(zhǔn)確率，并且在處理大數(shù)據(jù)集時依然具有不錯的性能表現(xiàn)。

參考文獻(xiàn)（References）

[1] ZHANG T， RAMAKRISHNAN R， LINVY M. BIRCH： an efficient data clustering method for very large databases[C]// SIGMOD 1996： Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data. New York： ACM， 1996： 103-114.

[2] 邵峰晶， 張斌， 于忠清.多閾值BIRCH聚類算法及其應(yīng)用[J]. 計算機(jī)工程與應(yīng)用， 2004， 41（12）： 174-176. （SHAO F J， ZHANG B， YU Z Q. BIRCH clustering algorithm with mult_threshold[J]. Computer Engineering and Applications， 2004， 41（12）： 174-176.）

[3] 蔣盛益， 李霞. 一種改進(jìn)的BIRCH聚類算法[J]. 計算機(jī)應(yīng)用， 2009， 29（1）： 293-296. （JIANG S Y， LI X. Improved BIRCH clustering algorithm[J]. Journal of Computer Applications， 2009， 29（1）： 293-296.）

[4] 仰孝富.基于BIRCH改進(jìn)算法的文本聚類研究[D]. 北京： 北京林業(yè)大學(xué)， 2013： 22-29. （YANG X F. Research of text clustering based on improved BIRCH[D]. Beijing： Beijing Forestry University， 2013： 22-29.）

[5] 曾曉迪.一種基于K-mediods改進(jìn)BIRCH的大數(shù)據(jù)聚類方法[D]. 昆明： 云南財經(jīng)大學(xué)， 2014： 27-31. （ZENG X D. A big data clustering method based on K-mediods improved BIRCH[D]. Kunming： Yunnan University of Finance and Economics， 2014： 27-31.）

[6] 鄒杰濤， 趙方霞， 汪海燕.基于加權(quán)相似性的聚類算法[J]. 數(shù)學(xué)的實踐與認(rèn)知， 2011， 47（16）： 118-124. （ZOU J T， ZHAO F X， WANG H Y. Clustering algorithm based on weighted similarity[J]. Mathematics in Practice and Theory， 2011， 47（16）： 118-124.）

[7] HUANG Z X. A fast clustering algorithm to cluster very large categorical data sets in data mining[EB/OL]. [2018-05-10]. http：//www.vladestivill-castro.net/teaching/kdd.d/readings.d/huang97 fast.pdf.

[8] MACQUEEN J. Some methods for classification and analysis of mul-tivariate observations[C]// Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. Berkeley： University of California Press， 1967， 1： 281-297.

[9] 韋相.基于密度的改進(jìn)BIRCH聚類算法[J]. 計算機(jī)工程與應(yīng)用， 2013， 49（10）： 201-205. （WEI X. Improved BIRCH clustering algorithm based on density[J]. Computer Engineering and Applications， 2013， 49（10）： 201-205.）

[10] MADAN S， DANA K J. Modified Balanced Iterative Reducing and Clustering using Hierarchies （m-BIRCH） for visual clustering[J]. Pattern Analysis and Applications， 2016， 19（4）： 1023-1040.

[11] ESTER M， KRIEGEL H， SANDER J， et a1. A density-based algorithm for discovering clusters in large spatial databases with noise[C]// Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. Menlo Park， CA： AAAI Press， 1996： 226-231.

[12] AWWAD B， HASAN S， GAN J Q. Sequential EM for unsupervised adaptive Gaussian mixture model based classifier[C]// MLDM 2009： Proceedings of the 6th International Conference on Machine Learning and Data Mining in Pattern Recognition， LNAI 5632. Berlin： Springer， 2009： 96-106.

[13] LAUER F， SCHNORR C. Spectral clustering of linear subspaces for motion segmentation[C]// Proceedings of the 2009 IEEE 12th International Conference on Computer Vision. Piscataway， NJ： IEEE， 2009： 678-685.

[14] NG A Y， JORDAN M I， WEISS Y. On spectral clustering： analysis and an algorithm[EB/OL]. [2018-05-10]. http：//papers.nips.cc/paper/2092-on-spectral-clustering-analysis-and-an-algorithm.pdf.

[15] MERZC J， MERPHY P. UCI repository of machine learning data-bases[DB/OL]. [2018-03-19]. http：//archive.ics.uci.edu/ml/index.php.