張 華，楊 磊

(1. 江南大學人工智能與計算機學院，江蘇 無錫 214000；2. 電子科技大學，四川 成都 611731)

1 引言

聚類是實現數據流挖掘的關鍵技術，本質就是將沒有類別標簽的樣本參考某種規(guī)則分成若干類，確保類內樣本相似性最大，類間樣本則達到最小相似度，屬于一種無監(jiān)督學習方式，可以作為獨立工具獲取數據分布情況。除此之外，聚類還可以當做其它算法的預處理步驟。在滑動窗口環(huán)境下，傳統(tǒng)聚類方法不能適應新的變化，因此對數據流聚類研究不斷進行，在傳統(tǒng)方法基礎上，相關學者提出下述算法。

文獻[1]提出基于分量屬性近鄰傳播的數據聚類方法。根據動態(tài)時間彎曲方法衡量多元時間序列數據整體距離，采用近鄰傳播聚類方法分析整體距離矩陣與分量近似距離矩陣，實現高質量聚類。仿真結構表明，該方法不但可以準確體現總體數據特征存在的關系，還能提高數據聚類效果。文獻[2]采用基于密度峰值的聚類算法構造了一個引導樹，并以粒度計算的方式將其轉化為胖節(jié)點引導樹，在聚類結果傳遞到新數據到達之間的時間間隔內，將混合數據的模糊神經網絡細化為具有固定脂肪節(jié)點數的新模糊神經網絡，通過混合?；ヂ錂C制實時維護當前數據流的FNLT，該方法顯示了良好的準確性和有效性。

上述兩種方法雖然可以適應數據流實時變化的特性，但是數據流聚類準確率較低，聚類效果不好。針對這些缺陷，本文提出基于密度梯度的滑動窗口數據流任意形狀聚類方法。由于任意形狀數據流具有不確定性，因此引入不確定概念衡量數據分布情況，最大程度降低不確定性對數據流聚類結果產生的影響，通過鄰近點密度搜索不動點，再由不動點和與其相鄰點組成最小聚類，對小類合并實現最終聚類任務。

2 密度梯度的滑動窗口數據流任意形狀聚類研究

2.1 數據流聚類基本要求探究

一系列持續(xù)并有順序的點構成序列x1，…，xi，…，xn，將其稱作數據流[3]。數據流不同于傳統(tǒng)數據集合，因此對其進行處理時必須符合下述條件：

1)實時性：實時且連續(xù)的輸出結果是數據流處理的最根本要求。如果不能很快處理到達數據流上的任一元組，則延時會不斷累積，最終降低聚類質量。在多數情況下數據流會隨環(huán)境的變化發(fā)生改變。

2)低空間復雜度：為確保聚類過程持續(xù)平穩(wěn)運行，數據流的空間復雜度要盡可能小。假定當前時間點數據流長度表示為N，則空間復雜度通常要求在ο(poly(logN))之內。這樣即可保證算法空間占用量的增長速度低于數據流自身規(guī)模增長速度[4]。

3)準確性：由于數據流規(guī)模大、速度快，針對某些復雜問題不能經過一次遍歷就能獲取準確結果。而數據流的處理方法最大特征就是能夠返回一個近似值，且該值較為準確[5]。算法的精準度通常取決于內存空間大小，假如具有更大內存空間時，算法準確性更高。

4)適應性：在某些應用中，數據流會發(fā)生較大變化，此種變化可能為流速變化，還可能是數據分布情況變化[6]。當外部環(huán)境發(fā)生改變時，需要結合數據流變化快速調節(jié)參數，從而提高數據流處理性能。

2.2 數據流的不確定性分析

由于任意形狀數據流具有不確定性，因此在聚類過程中要考慮不確定數據元組的屬性值，避免不確定性對聚類結果造成巨大影響。不確定數據流分布范圍較小的元組要比分布范圍大的元組存在更關鍵作用[7]。所以在聚類時，對于不同分布范圍的數據應該采用不同處理方式。

在對不確定數據進行處理時，如果其分布范圍較廣，則它對聚類結果會產生較大影響。為更加清楚的表示不確定性數據流元組信息，引入不確定指數與不確定度概念，可以反映數據分布范圍[8]。

數據不確定指數：假設某個具有s個實例的不確定數據e，e∈D?Rm。要使函數符合UI：D→R+條件，則函數UF表示為

UI(x)=FB(x)

(1)

式中，FB(x)存在多種計算公式，例如，方差評判方法如下所示

(2)

也可利用最大距離計算方法

(3)

根據數據的不確定指數即可獲得如下不確定度的定義。

數據不確定度：已知某個不不確定數據集合D?Rm，使其函數UD符合UD：D→R+，則該函數定義式如下

(4)

通過上述不確定指數與不確定度，綜合考慮數據流環(huán)境限制，則滑動窗口下聚類必須處理如下問題：及時保存有效數據摘要，保留有意義的歷史數據；可以滿足用戶在一定時間內的查詢需求[9]。

2.3 密度梯度下密度單元確定

2.3.1 核心密度單元

因為對半徑大小進行限制，核心密度單元數量通常高于聚簇的數量，這樣可以提高聚類準確度。此外，存在最小數量制約，因此核心密度單元數量低于數據流中點數量。

核心密度單元實質上指存在任意形狀聚簇的核心目標，在演化數據流中，密度單元是不斷改變的，可能變?yōu)楹诵拿芏葐卧?，也可能變?yōu)楣铝Ⅻc，尤其在數據分布變化較大時，變化情況更為明顯，因此，必須對候選密度單元進行分析。

2.3.2 候選密度單元

(5)

(6)

(7)

候選密度單元的作用是保留在變?yōu)楹诵拿芏葐卧暗臄祿畔?，因為其本身含有點數量少，所以計算量也相對較少，不會對增加系統(tǒng)操作負擔，但是也可以保留有效聚類信息，對最終聚類結果產生重要作用。

2.3.3 密度單元覆蓋

核心密度單元與候選密度單元都可以稱作微聚類，分別表示為：M1…Mp與C1…Cq，在滑動窗口大小為W前提下，該窗口中的數據集合表示為B，則具有如下性質

性質1：M∪C?B；

性質2：M1∩…∩Mp=Φ，C1∩…∩Cq=Φ；

性質3：對于?p∈D，則有?Mi∈M，p∈Mi或者?Ci∈C，p∈Ci。

符合上述性質的微聚類集合被稱作窗口下數據流的密度單元覆蓋。通過上述性質可以得出，任意窗口下數據流均存在核心密度單元與候選密度單元覆蓋。

2.4 密度梯度算法模型構建

點鄰域：將任意一個數據樣本點Q當做中心，與此點Q的d個最近鄰點是半徑覆蓋的點集，表示為：N(Q，d)。

密度點：將任意數據樣本點Q當做中心，與該點相距的d個最近鄰點平均距離表示此點密度，記為D(Q，d)。

在獲取密度過程中，由于度量是距離，則樣本點Q的密度越高，D(Q，d)的數值越低；反之數值越大。

不動點：將數據樣本Q作為中心，將距離此點第d個近鄰點距離當做半徑，其中鄰域范圍最大的點稱為不動點，描述為Kemel(Q，d)。

由于鄰域增加，由大密度不動點構成的聚類中點數不斷上升，而密度分布小的類中點數量持續(xù)減少，最后被大類合并。如果鄰域接近上限時，全部點將組成一個類，若鄰域為零時，任意一點都屬于不動點，單獨為一類。

d值大小會決定初始聚類后類的數量，所以d的取值成為聚類關鍵問題。d值越小，與其相對的初始聚類數量越多，且其中包括d取最大值時初始聚類的類中心。

邊界點：如果任意類Ci中樣本數據點Q的d近鄰域中的點分為兩個或更多的類，則稱這種點為類Ci的邊界點。全部邊界點集合記為Boader(Ci)。

將兩個聚類合并程度函數H(C1，C2)當做兩類合并的判斷依據，利用邊界點與各類中具有點數的熵值構建算法模型

(8)

式中，c1與c2分別表示C1、C2中包含的點數量，c代表C1、C2中具有的邊界點數量，如果邊界點數量是零，則合并程度函數值是+∞。

2.5 數據流任意形狀聚類實現

數據流演化過程通常分為三種情況：聚類消失、產生新聚類以及聚類中心點漂移。聚類演化示意圖如下所示：

圖1 聚類演化示意圖

結合上述構建的算法模型，能夠確定如下滑動窗口數據流任意形狀聚類步驟如下：

1)進行初始化處理，獲取密度分布情況

計算每個點的d近鄰，將d近鄰平均距離當做此點密度。

2)確定不動點，實現初始聚類

任意挑選一個沒有經過分類的樣本點Q，計算其d近鄰內最大密度點R，結合點R與點Q的密度分別在兩種情況下進行比較：

如果R點密度比Q點密度小，或者D(R，d)的值高于D(Q，d)，則Q點屬于一個不動點，對其賦予新的類別編號。

如果R點密度高于Q點密度，則需要根據R點聚類情況做出判定，假設此點類別號已經去頂，則可以將此點聚類號當做Q點類別號，反之需要獲取以點R當做起始點的不動點。

若尋找到對應的不動點后，對此路徑下全部點賦予類別號；進行循環(huán)操作直至全部點均被分類。

3)調節(jié)邊界點

在邊界點的d個近鄰點類別號中，通過多數表決手段選取該邊界點類別號：

(9)

公式中，f(x)表示x的聚類號。

4)獲取不同邊界點分布情況

對各類中邊界點分布特征進行統(tǒng)計，如果?R∈Cj，Q∈Boader(Ci)，并且R∈N(Q，d)，則有：

Num(NearCluster(Ci，Cj))+1

→Num(NearCluster(Ci，Cj))

(10)

式中，Num(NearCluster(Ci，Cj))表示Ci，Cj類間邊界點數量。

在聚類過程中分為下述兩種情況：如果給定聚類數，則根據合并程度函數大小進行排序，將擁有最小函數值的兩類合并，當符合要求或在任意兩類不存在相同邊界點時停止合并；在沒有給定聚類數情況下，同樣結合合并程度函數對其排列，在最小合并函數值高于給定值時，操作停止，反之合并擁有最小函數值的兩類，與此同時重新獲取和其它有關聯(lián)的近鄰類合并程度函數，并重復上述步驟，直至算法停止，完成數據流任意形狀聚類。

3 仿真研究

為驗證本文所提的基于密度梯度滑動窗口數據流聚類方法的有效性，通過Windows XP系統(tǒng)進行仿真。實驗環(huán)境為Intel Pentium 4處理器，8GB內存。實驗過程中構建8臺虛擬機，虛擬機參數設置情況如表1所示。

表1 虛擬機參數配置表

通過上述環(huán)境，根據虛擬機參數設置，繪制不確定數據密度吸引點，如圖2所示。

圖2 不確定數據密度吸引點

由上圖可以看出，從一個不確定數據出發(fā)，找到一個不確定數據密度吸引點的過程。每次它的梯度方向，都指向不確定數據稠密而且不確定數據密度大的區(qū)域，當某個不確定數據的梯度方向上數據的不確定密度值小于原先的數據點時，則停止計算數據的梯度，此時先前數據即為局部范圍內的密度最大點，即不確定數據密度吸引點。此時則稱不確定數據A是被不確定數據B密度吸引點吸引的。

為使仿真具有可比性，將本文方法與文獻[1]方法、文獻[2]方法進行對比。分別比較三種方法在聚類處理中的加速比、準確性以及滑動窗口敏感程度。對比結果分別如圖3所示。

圖3 不同方法加速比對比結果示意圖

從圖中可以看出，所提方法加速比呈線性變化趨勢，且始終高于其它方法。在數據流規(guī)模較小時，啟動和通信需要較長時間，隨著數據規(guī)模擴大，本文方法加速比性能逐漸提高，主要因為降低節(jié)點之間通信量。利用本文方法對滑動窗口數據流任意形狀聚類，如圖4所示。

圖4 聚類效果圖

由上圖4可以看出，這兩個子聚類能夠準確區(qū)分兩個類別，不會造成各聚類所覆蓋的區(qū)間重疊，同一位置的點被歸入不同的聚類的情況。

聚類結果通常使用準確性作為評價指標，Jaccard系數是常用評價方法之一，其計算公式為：

JC=

(11)

利用上述公式計算得出文獻[1]方法和本文方法的聚類準確性，結果如下所示：

圖5 不同方法聚類效果對比圖

由上圖可以看出，文獻[1]方法處理這個數據集的聚類問題效果較差，而本文所提算法成功地找出了數據的流形結構。具體聚類準確性結果如下。

表2 不同方法聚類準確性結果分析

由上表可知，隨著數據規(guī)模增加，文獻[1]方法的聚類準確性有所下降。但是所提方法下降趨勢并不明顯，這是由于該方法對不確定性進行分析，提高聚類精準度。

相似度矩陣是否理想直接關系到聚類結果的好壞，當相似性矩陣是分塊對角矩陣這一理想情形時，聚類算法可以得到完全正確的聚類結果。則本文方法和文獻[2]方法的相似度矩陣如圖6所示。

圖6 不同方法相似度矩陣

由上圖可知，顯然，文獻[2]方法距離矩陣塊對角分布不明顯，無法體現不同流形的區(qū)別，而經過核自適應映射后的流形距離測度得到的相似度矩陣顯示了明顯的分塊對角模式，較好地體現了整體樣本集的聚類信息。這是因為在確定每個密度單元時，都引入必須具備當前窗口數據這一關鍵約束條件，因此即使數據規(guī)模擴大也不會對聚類結果產生太多影響。

4 結論

數據流聚類問題始終是數據挖掘領域難點，本文在密度梯度基礎上對滑動窗口數據流任意形狀進行聚類。綜合分析不確定數據具體信息，減少對數據聚類影響，構建密度梯度模型，實現聚類。仿真結果表明，該方法聚類準確性高，加速比性能良好。但是在數據流中經常會有噪聲出現，其特性和演化的數據流相似，因此怎樣去除噪聲、區(qū)別噪聲與演化數據是今后研究的重要問題。