基于密度梯度的滑動(dòng)窗口數(shù)據(jù)流任意形狀聚類

張 華，楊 磊

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

1 引言

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

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

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

2 密度梯度的滑動(dòng)窗口數(shù)據(jù)流任意形狀聚類研究

2.1 數(shù)據(jù)流聚類基本要求探究

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

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

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

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

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

2.2 數(shù)據(jù)流的不確定性分析

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

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

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

UI(x)=FB(x)

(1)

式中，F(xiàn)B(x)存在多種計(jì)算公式，例如，方差評判方法如下所示

(2)

也可利用最大距離計(jì)算方法

(3)

根據(jù)數(shù)據(jù)的不確定指數(shù)即可獲得如下不確定度的定義。

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

(4)

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

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

2.3.1 核心密度單元

因?yàn)閷Π霃酱笮∵M(jìn)行限制，核心密度單元數(shù)量通常高于聚簇的數(shù)量，這樣可以提高聚類準(zhǔn)確度。此外，存在最小數(shù)量制約，因此核心密度單元數(shù)量低于數(shù)據(jù)流中點(diǎn)數(shù)量。

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

2.3.2 候選密度單元

(5)

(6)

(7)

候選密度單元的作用是保留在變?yōu)楹诵拿芏葐卧暗臄?shù)據(jù)信息，因?yàn)槠浔旧砗悬c(diǎn)數(shù)量少，所以計(jì)算量也相對較少，不會(huì)對增加系統(tǒng)操作負(fù)擔(dān)，但是也可以保留有效聚類信息，對最終聚類結(jié)果產(chǎn)生重要作用。

2.3.3 密度單元覆蓋

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

性質(zhì)1：M∪C?B；

性質(zhì)2：M1∩…∩Mp=Φ，C1∩…∩Cq=Φ；

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

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

2.4 密度梯度算法模型構(gòu)建

點(diǎn)鄰域：將任意一個(gè)數(shù)據(jù)樣本點(diǎn)Q當(dāng)做中心，與此點(diǎn)Q的d個(gè)最近鄰點(diǎn)是半徑覆蓋的點(diǎn)集，表示為：N(Q，d)。

密度點(diǎn)：將任意數(shù)據(jù)樣本點(diǎn)Q當(dāng)做中心，與該點(diǎn)相距的d個(gè)最近鄰點(diǎn)平均距離表示此點(diǎn)密度，記為D(Q，d)。

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

不動(dòng)點(diǎn)：將數(shù)據(jù)樣本Q作為中心，將距離此點(diǎn)第d個(gè)近鄰點(diǎn)距離當(dāng)做半徑，其中鄰域范圍最大的點(diǎn)稱為不動(dòng)點(diǎn)，描述為Kemel(Q，d)。

由于鄰域增加，由大密度不動(dòng)點(diǎn)構(gòu)成的聚類中點(diǎn)數(shù)不斷上升，而密度分布小的類中點(diǎn)數(shù)量持續(xù)減少，最后被大類合并。如果鄰域接近上限時(shí)，全部點(diǎn)將組成一個(gè)類，若鄰域?yàn)榱銜r(shí)，任意一點(diǎn)都屬于不動(dòng)點(diǎn)，單獨(dú)為一類。

d值大小會(huì)決定初始聚類后類的數(shù)量，所以d的取值成為聚類關(guān)鍵問題。d值越小，與其相對的初始聚類數(shù)量越多，且其中包括d取最大值時(shí)初始聚類的類中心。

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

將兩個(gè)聚類合并程度函數(shù)H(C1，C2)當(dāng)做兩類合并的判斷依據(jù)，利用邊界點(diǎn)與各類中具有點(diǎn)數(shù)的熵值構(gòu)建算法模型

(8)

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

2.5 數(shù)據(jù)流任意形狀聚類實(shí)現(xiàn)

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

圖1 聚類演化示意圖

結(jié)合上述構(gòu)建的算法模型，能夠確定如下滑動(dòng)窗口數(shù)據(jù)流任意形狀聚類步驟如下：

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

計(jì)算每個(gè)點(diǎn)的d近鄰，將d近鄰平均距離當(dāng)做此點(diǎn)密度。

2)確定不動(dòng)點(diǎn)，實(shí)現(xiàn)初始聚類

任意挑選一個(gè)沒有經(jīng)過分類的樣本點(diǎn)Q，計(jì)算其d近鄰內(nèi)最大密度點(diǎn)R，結(jié)合點(diǎn)R與點(diǎn)Q的密度分別在兩種情況下進(jìn)行比較：

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

如果R點(diǎn)密度高于Q點(diǎn)密度，則需要根據(jù)R點(diǎn)聚類情況做出判定，假設(shè)此點(diǎn)類別號已經(jīng)去頂，則可以將此點(diǎn)聚類號當(dāng)做Q點(diǎn)類別號，反之需要獲取以點(diǎn)R當(dāng)做起始點(diǎn)的不動(dòng)點(diǎn)。

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

3)調(diào)節(jié)邊界點(diǎn)

在邊界點(diǎn)的d個(gè)近鄰點(diǎn)類別號中，通過多數(shù)表決手段選取該邊界點(diǎn)類別號：

(9)

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

4)獲取不同邊界點(diǎn)分布情況

對各類中邊界點(diǎn)分布特征進(jìn)行統(tǒng)計(jì)，如果?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類間邊界點(diǎn)數(shù)量。

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

3 仿真研究

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

表1 虛擬機(jī)參數(shù)配置表

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

圖2 不確定數(shù)據(jù)密度吸引點(diǎn)

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

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

圖3 不同方法加速比對比結(jié)果示意圖

從圖中可以看出，所提方法加速比呈線性變化趨勢，且始終高于其它方法。在數(shù)據(jù)流規(guī)模較小時(shí)，啟動(dòng)和通信需要較長時(shí)間，隨著數(shù)據(jù)規(guī)模擴(kuò)大，本文方法加速比性能逐漸提高，主要因?yàn)榻档凸?jié)點(diǎn)之間通信量。利用本文方法對滑動(dòng)窗口數(shù)據(jù)流任意形狀聚類，如圖4所示。

圖4 聚類效果圖

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

聚類結(jié)果通常使用準(zhǔn)確性作為評價(jià)指標(biāo)，Jaccard系數(shù)是常用評價(jià)方法之一，其計(jì)算公式為：

JC=

(11)

利用上述公式計(jì)算得出文獻(xiàn)[1]方法和本文方法的聚類準(zhǔn)確性，結(jié)果如下所示：

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

由上圖可以看出，文獻(xiàn)[1]方法處理這個(gè)數(shù)據(jù)集的聚類問題效果較差，而本文所提算法成功地找出了數(shù)據(jù)的流形結(jié)構(gòu)。具體聚類準(zhǔn)確性結(jié)果如下。

表2 不同方法聚類準(zhǔn)確性結(jié)果分析

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

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

圖6 不同方法相似度矩陣

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

4 結(jié)論

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