基于簇特征的增量聚類算法*

姚琳燕， 錢雪忠， 樊 路

(江南大學 物聯網技術應用教育部工程研究中心，江蘇 無錫 214122)

0 引 言

隨著大數據時代的來臨，海量的數據存儲使得傳統聚類方式效率低下。Fisher D[1]在1987年提出了COBWEB算法，該算法除了增加對象之外，還涉及到集群重組。文獻[2,3]中討論了與數據庫動態方面有關的增量聚類，且廣泛應用于許多領域[4,5]。增量聚類不需要在主存內保留對象之間的相互距離，且算法相對于對象集合的大小和屬性數量可擴展[6]。

文獻[7]中的層次聚類算法——BIRCH首次提出了聚類特征(cluster feature,CF)的概念，在層次增量聚類算法中取得了較好的聚類效果。受此啟發，以提高準確率和時間復雜度為目標，分析K-means算法[8]和K最近鄰[9](K-nearest neighbour,KNN)的優缺點，本文提出了一種基于簇特征的增量聚類算法，并在此基礎上提出簇特征概念輔以KNN思想添加增量處理部分，提出一種基于簇特征的增量算法。

1 距離測量(定義一)

采用歐氏距離計算質心到數據點的距離，從點y到點m的距離為

(1)

2 基于簇特征的增量算法

為了減少迭代時間，避免算法陷入局部最優，本文提出最大距離法選取k個中心點，簇中心為c={c1,c2,…,ck}，1≤i≤k。

2.1 最大距離法選擇初始中心

1)將所有的數據放入data中，中心點集合c置空。隨機在Data中選取1個點作為第1個中心點，將該點放入c中，并將該點從Data中移除。

2)計算數據集Data中的所有點與隨機選取的中心點的距離，選擇距離最遠的點作為下一個中心點并放入c中,相應的從Data中移除該點。

3)若集合c的數量等于k，結束；否則，跳入步驟(2)。

2.2 簇特征

2.2.1 CF(定義二)

本文使用mi和Fi(q)作為簇特征，CF={mi，Fi(q)，Q}。其中，mi是簇ci的中心點，Fi(q)是簇ci中距離中心點最遠的q個最遠點，Q是距離中心點最遠的q個最遠點中距離新增數據最近的點。

增量數據會對聚類結果產生影響而不會對當前的集群產生廣泛的影響。數據更新之后，有3種可能性，加入已有簇，生成一個新簇或合并兩個已有簇，如圖1所示。

2.2.2 距離策略(定義三)

距離策略對于有效識別輸入數據點Δy的正確聚類是很重要的。 在本文提出的方法中，使用了不同的距離策略，利用平均值mi，最近鄰點Q和輸入數據點Δy3個點。在對數據集使用改進的K-means算法聚類之后，對于即將到來的點，根據簇特征，計算新增數據點與mi之間的歐氏距離Dim(Δy，mi)，q個最遠點中距離新增數據點最近的點Q和中心點mi之間的歐氏距離DQm(Q,mi)以及新增數據點與q個最遠點中距離新增數據點最近的點Q之間的歐氏距離DQi(Q，Δy)，計算D=Dim+DQm×DQi的值。

2.3 更新簇特征

將某個新增數據點添加到簇后，CF的更新對數據進一步的處理至為重要。為了更新CF，首先計算發生增量簇的平均值，并更新簇特征CF的第一個分量mi。然后，利用更新的平均值mi，對增量簇中的每個數據點計算歐氏距離ED。根據計算的距離測量對數據點進行排序，并從排序列表中選擇最新的q個最遠鄰居點，更新CF的第二個分量Fi，在下一個新增數據點進入時重新計算q個最遠鄰居點中距離新增數據點最近的點Q。

2.4 最近簇的合并

由于處理增量過程是每次處理一條增量數據，為了避免在增量過程中簇的數量過多形成非最優聚類結構，本文提出的方法在處理t個增量數據之后使用合并策略，使本文方法產生合理數量的簇。用于合并的過程描述為：

1)計算每個簇的平均值及和其他簇之間的歐氏距離；

2)選擇歐氏距離最小的兩個簇；

3)如果距離最小的兩個簇之間的距離小于某個閾值MT，則合并這兩個簇；

4)重新計算合并的新簇的平均值；

5)重復步驟(1)～步驟(3)，直到沒有簇可合并為止。

2.5 算法具體描述

輸入：靜態數據集data1，動態數據集data2，合并閾值MT，閾值NT，k，t，q

輸出：聚類結果re

參數：Δy為到來的新增數據點;CF為簇特征;D為歐氏距離;Fi(q)為q為最遠鄰居點;Q為距離新增數據最近的最遠鄰居點。

1)使用最大距離法選擇初始中心點

2)運行K-means(data1，K)算法

3)fori=1︰k

a.計算CF={mi，Fi(q)，Q}

4)for增量數據中的每個點Δy

b.fori=1︰k

計算距離Dim和DQm和DQi

c.如果D=Dim+DQm×DQi

c1.若k個點所屬簇所占比例最大的簇和i簇一致，則加入i簇

c2.若所占比例最大的簇與i簇不一致，計算所占比例最大的簇的D=Dim+DQm×DQi

若D

若大于等于NT，則加入i簇

d.如果不滿足步驟(c)則生成一個新簇

e.更新簇特征CF

f.在處理完t個增量數據后

f1.計算各個簇中心點之間的歐氏距離

f2.若簇中心點之間的距離小于閾值MT則將這兩個簇合并更新合并新簇的中心點，只有一個數據的簇作為噪聲點返回步驟(f1)

5)得到聚類結果re

3 實驗與結果分析

本文中所有的算法通過MATLAB工具實現并處理實驗結果，試驗環境為：CPU為Intel i3 3.7 GHz，內存為4 GB，Windows7系統。數據集：采用UCI真實數據集中的Iris數據集和Wine數據集。

實驗一為了將靜態數據集轉化成動態問題處理，本文將數據集分為2組。鳶尾花數據集——Iris，第一組的組成為35個第一類數據，35個第二類數據，30個第三類數據。剩余數據作為增量數據作為第二組。閾值NT=10，MT=4,k=3，q=5。Wine數據第一組選取第一類簇的38個數據，第二類簇的32個數據，第三類簇的24個數據，剩下的數據作為第二組增量數據。Iris數據集閾值NT=10，Wine數據集閾值NT=10×105，t=10。

以下表格中的數據都是通過重復運行20次去掉一個最大值，一個最小值,取平均值。實驗一結果如表1所示。

表1 Iris和Wine數據集實驗一結果

實驗結果表明，K-means算法針對Iris數據集相對DBSCAN等其他算法有比較好的聚類效果。由于IRIS數據集有兩類數據有重合，所以DBSCAN不能有效識別，準確率大大低于K-means算法。由于增量數據較少，本文提出的算法較已有的增量K-means算法效率有一定的提高，但不明顯。算法準確率也有較明顯的提升。而增量K-means(incremental K-means,In-K-means)雖然效率較高，但準確率有所欠缺。

Wine數據中，本文所提出的算法較傳統K-means算法和In-K-means算法的聚類準確率有所提高，但較Iris數據集的準確率提高程度略有降低。由于增量數據較少，效率提升也不明顯。而In-K-means雖然效率較高，但準確率有所欠缺。

實驗二將原始數據集中的3類樣本，取其中兩類作為初始聚類數據，另一類作為增量數據。為了驗證本文算法對噪聲點的識別能力，給Iris數據集添加人造數據10條。閾值NT=10，MT=4,k=3。噪聲數據參照文獻[8]，結果表明，本文算法能有效識別較遠噪聲點，識別噪聲10條，準確度90.67 %，且算法本身較穩定，聚類算法精度較高。

4 結束語

由以上實驗可以驗證本文提出的基于簇特征的增量聚類算法，對于增量數據有較好的聚類精度；在處理增量數據時，避免遍歷所有的數據，在一定程度上提高了算法效率，且增量數據越多，效果提升越明顯。但僅能識別球形簇且時間復雜度較高，應用于大型數據集處理較為麻煩，如何結合密度，使得算法能夠識別任意形狀的簇或者結合網格降低算法的時間復雜度，將是下一步將要研究的工作。