一種基于勢(shì)能模型的數(shù)據(jù)流聚類(lèi)算法

舒 越 解 慶 劉永堅(jiān) 唐伶俐

(武漢理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 湖北 武漢 430070)

0 引 言

隨著信息技術(shù)不斷發(fā)展，信息的傳播效率不斷提高，各種信息充斥著整個(gè)世界，各種高效的智能化數(shù)據(jù)采集技術(shù)投入市場(chǎng)應(yīng)用，使信息數(shù)據(jù)的處理能力不斷增強(qiáng)，而如何更加精準(zhǔn)地從大量信息中挖掘出有價(jià)值的信息，是近些年學(xué)者們關(guān)注的重點(diǎn)之一[1]。隨著數(shù)據(jù)流的爆發(fā)增長(zhǎng)，比如金融數(shù)據(jù)、Web日志數(shù)據(jù)和視頻監(jiān)控?cái)?shù)據(jù)等，數(shù)據(jù)流挖掘引起了學(xué)者們的關(guān)注[2]。數(shù)據(jù)流[3]是一個(gè)連續(xù)不斷的數(shù)字信號(hào)序列，具有以下三個(gè)特性[4]。(1) 無(wú)限性：因?yàn)閿?shù)據(jù)流持續(xù)不斷地產(chǎn)生，因而數(shù)據(jù)點(diǎn)的數(shù)量是無(wú)限的，不能直接將其全部存儲(chǔ)到內(nèi)存中。(2) 動(dòng)態(tài)演變性：數(shù)據(jù)分布和特征隨時(shí)間推移而不斷變化。(3) 實(shí)時(shí)性：數(shù)據(jù)流實(shí)時(shí)產(chǎn)生，需要被實(shí)時(shí)處理。這些特點(diǎn)給數(shù)據(jù)流處理帶來(lái)了不小的挑戰(zhàn)[5-6]:由于數(shù)據(jù)流無(wú)法全部存儲(chǔ)在內(nèi)存中，對(duì)數(shù)據(jù)流只能掃描一次；由于數(shù)據(jù)流的動(dòng)態(tài)演變性，隨著時(shí)間的推移，數(shù)據(jù)可能發(fā)生變化，即“概念漂移”問(wèn)題；需要具有處理離群點(diǎn)的能力。

很多旨在解決數(shù)據(jù)流聚類(lèi)問(wèn)題的算法已經(jīng)被提出，其中大部分是基于傳統(tǒng)聚類(lèi)算法擴(kuò)展而來(lái)，如：K-means算法、DBSCAN算法和Affinity Propagation Clustering算法等，將這些傳統(tǒng)聚類(lèi)算法改進(jìn)適用于數(shù)據(jù)流聚類(lèi)。除此之外，很多數(shù)據(jù)流聚類(lèi)算法沿用在線/離線兩階段數(shù)據(jù)流聚類(lèi)框架[7]，在線階段旨在構(gòu)建概要數(shù)據(jù)結(jié)構(gòu)，離線階段根據(jù)這些概要數(shù)據(jù)結(jié)構(gòu)使用聚類(lèi)算法得到最終聚類(lèi)結(jié)果。由于大部分?jǐn)?shù)據(jù)流聚類(lèi)算法以距離作為相似度度量標(biāo)準(zhǔn)，這造成對(duì)噪點(diǎn)敏感的問(wèn)題，聚類(lèi)效果不理想。

針對(duì)這個(gè)問(wèn)題，本文提出一種基于勢(shì)能模型的層次聚類(lèi)算法PHAStream，該算法結(jié)合在線/離線兩階段數(shù)據(jù)流聚類(lèi)框架[7]和基于勢(shì)能模型的層次聚類(lèi)算法PHA[8]，在線階段采用融合勢(shì)能和距離的相似度度量標(biāo)準(zhǔn)更新微簇，判斷新到達(dá)數(shù)據(jù)點(diǎn)是否合并進(jìn)現(xiàn)有微簇或新建微簇，并每隔一定時(shí)間采取剪枝策略刪除過(guò)期的微簇，調(diào)整所有微簇的類(lèi)型；離線階段計(jì)算所有正常微簇的勢(shì)能，構(gòu)建邊緣加權(quán)樹(shù)和樹(shù)狀圖，得到最終聚類(lèi)結(jié)果。

本文的主要貢獻(xiàn)包括：(1) 使用一種新的概要數(shù)據(jù)結(jié)構(gòu)，它不僅記錄數(shù)據(jù)點(diǎn)屬性的統(tǒng)計(jì)信息、權(quán)重信息和時(shí)間戳信息，還有微簇之間的距離信息。它可以快速構(gòu)建距離矩陣，方便計(jì)算微簇的勢(shì)能，為后續(xù)基于勢(shì)能和距離的相似度度量標(biāo)準(zhǔn)和微簇聚類(lèi)提供基礎(chǔ)。(2) 以勢(shì)能和距離為相似度度量標(biāo)準(zhǔn)，在線階段判斷新到達(dá)數(shù)據(jù)點(diǎn)可能合并的微簇，然后根據(jù)勢(shì)能判斷是否合并進(jìn)該微簇或新建微簇。傳統(tǒng)以距離為相似度度量標(biāo)準(zhǔn)的方法中，新到達(dá)數(shù)據(jù)點(diǎn)是否合并進(jìn)微簇會(huì)受到噪點(diǎn)的干擾，以勢(shì)能和距離為相似度度量標(biāo)準(zhǔn)，可以減少噪點(diǎn)的干擾。(3) 將基于勢(shì)能的層次聚類(lèi)算法PHA改進(jìn)適用于數(shù)據(jù)流聚類(lèi)，可以減少噪點(diǎn)對(duì)聚類(lèi)的影響，提高聚類(lèi)效果。

1 相關(guān)工作

目前學(xué)術(shù)界對(duì)數(shù)據(jù)流聚類(lèi)算法的研究已經(jīng)取得不少成果，主要分為基于劃分的方法、基于層次的方法、基于密度的方法、基于網(wǎng)格的方法和基于模型的方法五種。

第一種是基于劃分的數(shù)據(jù)流聚類(lèi)方法，實(shí)踐操作較為簡(jiǎn)單，但必須在操作之前對(duì)聚類(lèi)簇的數(shù)量進(jìn)行設(shè)置，數(shù)據(jù)流的分布形態(tài)在初期階段很難明確，聚類(lèi)簇的數(shù)量很難得到準(zhǔn)確的評(píng)估和預(yù)測(cè)。比如，Youn等[9]提出使用滑動(dòng)窗口的基于劃分的數(shù)據(jù)流聚類(lèi)算法，該算法為每個(gè)窗口移動(dòng)生成集群，由于在所有更改的窗口上重復(fù)進(jìn)行聚類(lèi)，會(huì)造成內(nèi)存和計(jì)算時(shí)間方面的低效，所以此算法僅考慮窗口的插入和刪除元組。

第二種是基于層次的數(shù)據(jù)流聚類(lèi)方法，在數(shù)據(jù)的劃分方面以微簇為主。如CluStream算法[7]，該算法提出了在線/離線兩階段數(shù)據(jù)流聚類(lèi)框架，在線階段以增量的方式更新微簇，離線階段根據(jù)用戶(hù)要求，使用K-means算法對(duì)微簇進(jìn)行聚類(lèi)。該算法操作簡(jiǎn)單，但是基于距離的相似度度量使得其對(duì)噪點(diǎn)較為敏感。

第三種是基于密度的數(shù)據(jù)流聚類(lèi)方法，能夠?qū)崿F(xiàn)對(duì)任意形狀的數(shù)據(jù)流進(jìn)行劃分，但是在計(jì)算過(guò)程中需要設(shè)置大量初始參數(shù)。如DenStream算法[10]，該算法沿用在線/離線兩階段數(shù)據(jù)流聚類(lèi)框架，在線階段將新到達(dá)的數(shù)據(jù)點(diǎn)分配給距離它最近的微簇，進(jìn)行微聚類(lèi)，同時(shí)提出了核心微簇、潛在核心微簇和噪點(diǎn)微簇來(lái)區(qū)分正常微簇?cái)?shù)據(jù)、可能成為正常簇的微簇?cái)?shù)據(jù)和噪點(diǎn)數(shù)據(jù)；離線階段使用DBSCAN算法來(lái)聚類(lèi)。

第四種是基于網(wǎng)格的數(shù)據(jù)流聚類(lèi)方法，對(duì)聚類(lèi)數(shù)據(jù)的形狀沒(méi)有約束限制，但是網(wǎng)格粒度的大小對(duì)聚類(lèi)的質(zhì)量有較大影響。D-Stream算法[11]是基于網(wǎng)格的數(shù)據(jù)流聚類(lèi)算法之一，該算法沿用在線/離線兩階段數(shù)據(jù)流聚類(lèi)框架，在線階段將每個(gè)輸入的數(shù)據(jù)點(diǎn)映射到網(wǎng)格中，離線階段對(duì)這些密度網(wǎng)格進(jìn)行聚類(lèi)，并且取出稀疏的網(wǎng)格。張冬月等[12]提出基于網(wǎng)格耦合的數(shù)據(jù)流聚類(lèi)算法，該算法在聚類(lèi)過(guò)程中，不再片面地單獨(dú)處理網(wǎng)格，而是將每個(gè)網(wǎng)格之間的耦合關(guān)系納入考慮的范圍內(nèi)，網(wǎng)格之間的耦合關(guān)系可以更加精準(zhǔn)地表現(xiàn)數(shù)據(jù)點(diǎn)之間的相似度，從而提升聚類(lèi)質(zhì)量。

第五種是基于模型的數(shù)據(jù)流聚類(lèi)方法，需要大量的學(xué)科領(lǐng)域知識(shí)作為輔助，在使用中需要假設(shè)模型的支持。例如，朱穎雯等[13]提出的基于歐拉核的數(shù)據(jù)流聚類(lèi)算法，該算法首先采用歐拉核的方式，顯式地將數(shù)據(jù)點(diǎn)映射到同一維度的復(fù)數(shù)特征空間，接著在這個(gè)特征空間中使用GNG(Growing Neural Gas)模型進(jìn)行聚類(lèi)。

2 勢(shì)能模型

假設(shè)無(wú)窮遠(yuǎn)處的勢(shì)能為0，那么數(shù)據(jù)點(diǎn)xi來(lái)自數(shù)據(jù)點(diǎn)xj的勢(shì)能為：

(2)

在勢(shì)能模型中，只需要關(guān)注勢(shì)能的相對(duì)值，萬(wàn)有引力常數(shù)并沒(méi)有影響，所以為了方便計(jì)算，將G設(shè)置為1，并假設(shè)每個(gè)數(shù)據(jù)點(diǎn)的質(zhì)量為1，于是式(2)可改寫(xiě)為：

數(shù)據(jù)點(diǎn)xi的勢(shì)能，表示為來(lái)自其他所有數(shù)據(jù)點(diǎn)對(duì)它產(chǎn)生的勢(shì)能：

(4)

式中：N就是所有數(shù)據(jù)點(diǎn)的個(gè)數(shù)。

距離閾值ε的選取需要考慮數(shù)據(jù)點(diǎn)的分布，可以通過(guò)距離矩陣來(lái)進(jìn)行計(jì)算：

ε=mean(MinDi)/S

(6)

式中：MinDi表示數(shù)據(jù)點(diǎn)xi和其他數(shù)據(jù)點(diǎn)之間的最短距離;S為比例因子。由文獻(xiàn)[14]可知，取S=10時(shí)，模型可以達(dá)到較好的平衡狀態(tài)。

在勢(shì)能模型中，通常相似的數(shù)據(jù)點(diǎn)之間勢(shì)能的差值也比較小，距離也更近，基于勢(shì)能和距離的聚類(lèi)方法以該規(guī)律為基礎(chǔ)進(jìn)行設(shè)計(jì)。

3 基于勢(shì)能模型的數(shù)據(jù)流聚類(lèi)算法

本節(jié)詳細(xì)介紹基于勢(shì)能模型的數(shù)據(jù)流聚類(lèi)算法PHAStream，該算法結(jié)合在線/離線兩階段數(shù)據(jù)流聚類(lèi)框架和基于勢(shì)能模型的層次聚類(lèi)算法PHA，算法的流程如圖1所示。

圖1 PHAStream算法流程

3.1 PHAStream算法初始化階段

數(shù)據(jù)流是一段連續(xù)不斷的序列點(diǎn)X={X0,X1,…,Xn,…}，每個(gè)數(shù)據(jù)點(diǎn)到達(dá)的時(shí)間分別為T(mén)={t0,t1, …,tn,…}，每個(gè)數(shù)據(jù)點(diǎn)在數(shù)據(jù)空間中是一個(gè)d維向量。

考慮不同到達(dá)時(shí)間的數(shù)據(jù)點(diǎn)的重要性，對(duì)每個(gè)數(shù)據(jù)點(diǎn)加權(quán)，利用一個(gè)衰減系數(shù)來(lái)確定權(quán)重與時(shí)間的關(guān)系。使用式(7)來(lái)作為衰減函數(shù)，其中λ>0，并且t表示當(dāng)前時(shí)間戳tcurrent和該點(diǎn)到達(dá)的時(shí)間戳tarrival的差值，即t=tcurrent-tarrival。

w(t)=2-λt

(7)

在初始化階段，模型初始化參數(shù)并把時(shí)間戳t設(shè)置為0，對(duì)初始長(zhǎng)度的數(shù)據(jù)點(diǎn)使用PHA進(jìn)行聚類(lèi)，得到首批微簇。對(duì)于每個(gè)微簇，模型定義聚類(lèi)特征向量來(lái)記錄微簇的統(tǒng)計(jì)信息。借鑒StrDip算法[15]的聚類(lèi)特征向量，本文提出一種改進(jìn)的聚類(lèi)特征向量，主要由帶權(quán)重的微簇統(tǒng)計(jì)信息、微簇的權(quán)重和微簇之間的距離信息組成。距離信息可以快速構(gòu)建距離矩陣，進(jìn)而快速計(jì)算勢(shì)能。聚類(lèi)特征向量以這種形式定義: (CFx1,tl,weight,n,t0,dist_arr)。

(2)tl: 微簇中最后到達(dá)點(diǎn)的時(shí)間戳。

(4)n:微簇中所有數(shù)據(jù)點(diǎn)的個(gè)數(shù)。

(5)t0：微簇被創(chuàng)建的時(shí)間戳。

(6)dist_arr：當(dāng)前微簇中心點(diǎn)和所有微簇中心點(diǎn)(包括自己)的距離組成的數(shù)組。

基于聚類(lèi)特征向量，每個(gè)微簇的中心可以通過(guò)式(8)計(jì)算。

3.2 PHAStream算法在線階段

在線階段，對(duì)于每個(gè)新到達(dá)的數(shù)據(jù)點(diǎn)，尋找其可能合并的微簇，并判斷是否合并進(jìn)該微簇或者新建微簇，并更新聚類(lèi)特征向量，每隔固定時(shí)間采用剪枝操作，刪除過(guò)期的微簇并調(diào)整所有微簇的類(lèi)型。

(1) 尋找目標(biāo)微簇。當(dāng)模型接收到一個(gè)新數(shù)據(jù)點(diǎn)的時(shí)候，需要在現(xiàn)有微簇中找到與之最相似的微簇，即其最可能合并進(jìn)的目標(biāo)微簇。

由文獻(xiàn)[8，16]可知，在勢(shì)能場(chǎng)中，距離矩陣和勢(shì)能分別反映了數(shù)據(jù)點(diǎn)的局部和全局分布，同時(shí)可以發(fā)現(xiàn)同一個(gè)簇中的數(shù)據(jù)點(diǎn)，勢(shì)能差值小且相互距離更近，所以這里提出一個(gè)新的相似判斷標(biāo)準(zhǔn)pd值，如式(9)所示，來(lái)找到新數(shù)據(jù)點(diǎn)的“目標(biāo)微簇”。

pd[i]=abs(Φc-Φi)×distci

(9)

式中：Φc表示新到達(dá)數(shù)據(jù)點(diǎn)的勢(shì)能；Φi表示微簇i的勢(shì)能；distci表示新到達(dá)數(shù)據(jù)點(diǎn)和微簇i的距離，pd[i]則表示新到達(dá)數(shù)據(jù)點(diǎn)跟微簇i的勢(shì)能差絕對(duì)值和距離的乘積，因?yàn)橥粋€(gè)類(lèi)中的數(shù)據(jù)點(diǎn)，勢(shì)能差值小且相互距離越近，所以取pd[i]最小值時(shí)，微簇i是新到達(dá)數(shù)據(jù)點(diǎn)的“目標(biāo)微簇”。

(2) 微簇的合并準(zhǔn)則。當(dāng)找到目標(biāo)微簇之后，模型需要判斷新到達(dá)點(diǎn)需要合并到目標(biāo)微簇中，還是新建一個(gè)微簇。為此，需要設(shè)計(jì)一個(gè)合并準(zhǔn)則來(lái)進(jìn)行判斷。

由文獻(xiàn)[17]可知，一般情況下，由于數(shù)據(jù)集中噪點(diǎn)的數(shù)量是遠(yuǎn)小于正常數(shù)據(jù)點(diǎn)的數(shù)量，同時(shí)噪點(diǎn)的分布也相對(duì)稀疏，從數(shù)據(jù)點(diǎn)的概率分布特點(diǎn)和勢(shì)能大小分析可知，噪點(diǎn)的勢(shì)能相對(duì)正常數(shù)據(jù)點(diǎn)更大，從勢(shì)能角度，這一特點(diǎn)正是區(qū)別正常數(shù)據(jù)點(diǎn)和噪點(diǎn)的關(guān)鍵。如圖2所示[17]，是一個(gè)帶有噪點(diǎn)的數(shù)據(jù)集，將每個(gè)數(shù)據(jù)點(diǎn)的勢(shì)能按從小到大排序，如圖3所示[17]，會(huì)出現(xiàn)一個(gè)“拐點(diǎn)”C，這個(gè)C點(diǎn)被稱(chēng)為“勢(shì)能拐點(diǎn)”，“勢(shì)能拐點(diǎn)”之后的數(shù)據(jù)點(diǎn)被認(rèn)為是噪點(diǎn)。

圖2 含有噪點(diǎn)的數(shù)據(jù)集

圖3 勢(shì)能遞增圖

將“勢(shì)能拐點(diǎn)”作為一個(gè)新的合并準(zhǔn)則，來(lái)判斷新到達(dá)數(shù)據(jù)點(diǎn)是否合并進(jìn)“目標(biāo)微簇”。根據(jù)上述內(nèi)容，由于此時(shí)已經(jīng)可以求出每個(gè)微簇的勢(shì)能，將新到達(dá)的數(shù)據(jù)點(diǎn)構(gòu)成的微簇和其他所有微簇的勢(shì)能按從小到大的順序排列，構(gòu)成勢(shì)能遞增圖，根據(jù)式(10)找到當(dāng)前勢(shì)能場(chǎng)下的“勢(shì)能拐點(diǎn)”。如果新到達(dá)數(shù)據(jù)點(diǎn)微簇的勢(shì)能和“目標(biāo)微簇”的勢(shì)能均在“勢(shì)能拐點(diǎn)”之前，那么在當(dāng)前勢(shì)能場(chǎng)下，新到達(dá)數(shù)據(jù)點(diǎn)微簇和 “目標(biāo)微簇”均屬于正常數(shù)據(jù)點(diǎn)，所以將新到達(dá)數(shù)據(jù)點(diǎn)合并進(jìn)“目標(biāo)微簇”中。否則，以新到達(dá)的數(shù)據(jù)點(diǎn)新建一個(gè)微簇。

(Φi-Φi+1)×(Φi+1-Φi+2)≤0

(10)

(3) 更新微簇與新建微簇。根據(jù)微簇的合并準(zhǔn)則，當(dāng)新到達(dá)數(shù)據(jù)點(diǎn)和其目標(biāo)微簇的勢(shì)能都在“勢(shì)能拐點(diǎn)”之前時(shí)，那么就將新到達(dá)的數(shù)據(jù)點(diǎn)合并進(jìn)目標(biāo)微簇中；否則，以新到達(dá)數(shù)據(jù)點(diǎn)單獨(dú)成為一個(gè)微簇，構(gòu)建CF向量。

假設(shè)直到tc才有數(shù)據(jù)點(diǎn)x被吸收進(jìn)微簇i，并且i接收上一個(gè)點(diǎn)的時(shí)間戳為tl，那么帶有權(quán)重的微簇統(tǒng)計(jì)信息將以下列方式更新[15]:

weight=weight×2-λ(tc-tl)+1

(11)

CFx1=CFx1×2-λ(tc-tl)+x

(12)

通過(guò)式(11)和式(12)，可以快速地更新一個(gè)微簇新的權(quán)重weight和CFx1。

CF向量中的dist_arr屬性，記錄著當(dāng)前微簇和其他微簇之間的距離信息，雖然不是以增量的方式更新，但是更新的代價(jià)并不大，因?yàn)樵谛碌臄?shù)據(jù)點(diǎn)到達(dá)時(shí)，要么將新到達(dá)數(shù)據(jù)點(diǎn)合并進(jìn)某個(gè)微簇，要么以新到達(dá)的數(shù)據(jù)點(diǎn)新增一個(gè)微簇，如果處于檢查周期，那么就刪除過(guò)期微簇，期間這三種操作涉及個(gè)別微簇，或者只需要更新每個(gè)微簇dist_arr屬性中個(gè)別距離值。dist_arr屬性可以大大提高離線階段進(jìn)行聚類(lèi)的效率。

(4) 刪除微簇與調(diào)整微簇類(lèi)型。微簇隨著時(shí)間推移，會(huì)根據(jù)衰退函數(shù)改變權(quán)重，微簇的權(quán)重大于等于預(yù)設(shè)的權(quán)重閾值μ，則為正常微簇，反之，則為噪點(diǎn)微簇。

隨著時(shí)間的推移，數(shù)據(jù)流的分布可能發(fā)生變化，一些“正常微簇”可能很長(zhǎng)時(shí)間沒(méi)有接收新的數(shù)據(jù)點(diǎn)，變?yōu)椤霸朦c(diǎn)微簇”，這個(gè)現(xiàn)象我們稱(chēng)為“概念漂移”。所以需要每隔固定時(shí)間來(lái)檢查所有微簇的權(quán)重，假設(shè)一個(gè)“正常微簇”的原始權(quán)重恰好是μ，經(jīng)過(guò)Tg個(gè)時(shí)間戳，這個(gè)“正常微簇”剛好變?yōu)椤霸朦c(diǎn)微簇”，此時(shí)Tg就是“正常微簇”變?yōu)椤霸朦c(diǎn)微簇”的最小時(shí)間間隔[10，15]，即2-λTgμ+1=μ，求得：

為了節(jié)省PHAStream算法的運(yùn)行時(shí)間，每隔Tg個(gè)時(shí)間戳就采用一種剪枝策略：將權(quán)重足夠小的微簇刪除。通過(guò)式(14)來(lái)判斷一個(gè)微簇的權(quán)重是否足夠小[10,15]，微簇的權(quán)重下限定義如下：

到達(dá)檢查時(shí)間時(shí)，通過(guò)式(14)判斷是否存在需要?jiǎng)h除的微簇，如果存在需要?jiǎng)h除的微簇，那么需要更新那些未刪除微簇的dist_arr屬性，將每個(gè)dist_arr屬性中與刪除微簇相關(guān)的距離信息全部刪除。

3.3 PHAStream算法離線階段

當(dāng)有聚類(lèi)要求時(shí)，使用改進(jìn)的PHA(算法1)對(duì)所有“正常微簇”進(jìn)行聚類(lèi)，將每個(gè)微簇當(dāng)作一個(gè)數(shù)據(jù)點(diǎn)，假設(shè)每個(gè)數(shù)據(jù)點(diǎn)的質(zhì)量為1，那么每個(gè)微簇的質(zhì)量等于微簇中數(shù)據(jù)點(diǎn)的個(gè)數(shù)。將每個(gè)微簇的dist_arr屬性組合在一起，即此刻所有微簇的距離矩陣，根據(jù)勢(shì)能模型，即可求出每個(gè)微簇的勢(shì)能。為了實(shí)現(xiàn)所有數(shù)據(jù)點(diǎn)的聚類(lèi)，采用一種邊緣加權(quán)樹(shù)技術(shù)[8]，基于所有數(shù)據(jù)的勢(shì)能和距離對(duì)數(shù)據(jù)點(diǎn)進(jìn)行高效組織。將所有數(shù)據(jù)點(diǎn)中勢(shì)能最小的數(shù)據(jù)點(diǎn)當(dāng)作“根節(jié)點(diǎn)”，記為xroot。

算法1改進(jìn)的PHA

輸入：距離矩陣dist_matrix_arr, 質(zhì)量數(shù)組mass, 最終聚類(lèi)簇個(gè)數(shù)K。

輸出：聚類(lèi)標(biāo)簽clusterLabels。

1. 計(jì)算每個(gè)微簇的勢(shì)能，得到勢(shì)能數(shù)組Potential；

2. 構(gòu)建邊緣加權(quán)樹(shù)，并得到父節(jié)點(diǎn)數(shù)組parent和權(quán)重?cái)?shù)組weight；

3. 構(gòu)建樹(shù)狀圖，依次合并最相似的微簇，直至微簇個(gè)數(shù)等于最終聚類(lèi)簇個(gè)數(shù)K，得到聚類(lèi)標(biāo)簽clusterLabels；

4. 返回聚類(lèi)標(biāo)簽clusterLabels

對(duì)于每個(gè)數(shù)據(jù)點(diǎn)i，在所有其他數(shù)據(jù)點(diǎn)中勢(shì)能值小于或等于i的所有其他數(shù)據(jù)點(diǎn)中距i最近的數(shù)據(jù)點(diǎn)稱(chēng)為i的父節(jié)點(diǎn)[7]，并表示為parent[i]。

由式(15)可以找到各自數(shù)據(jù)點(diǎn)的父節(jié)點(diǎn)，其中將根節(jié)點(diǎn)xroot的父節(jié)點(diǎn)定義為它自己，邊緣加權(quán)樹(shù)中邊的權(quán)重，由數(shù)據(jù)點(diǎn)和其父節(jié)點(diǎn)之間的距離決定[7]，即：

weight[i]=disti,parent[i]

(16)

其中，根節(jié)點(diǎn)的權(quán)重是“無(wú)限大”。

可以通過(guò)以下步驟來(lái)構(gòu)建邊緣加權(quán)樹(shù)：(1) 根據(jù)勢(shì)能模型，求出所有數(shù)據(jù)點(diǎn)的勢(shì)能，并將所有數(shù)據(jù)點(diǎn)按勢(shì)能從小到大的順序排列；(2) 將所有數(shù)據(jù)點(diǎn)中具有勢(shì)能最低值的數(shù)據(jù)點(diǎn)設(shè)置為根節(jié)點(diǎn)xroot；(3) 根據(jù)數(shù)據(jù)點(diǎn)的勢(shì)能遞增順序，依次找到剩余數(shù)據(jù)點(diǎn)xi的父節(jié)點(diǎn)parent[i]，并且將剩余數(shù)據(jù)點(diǎn)與其父節(jié)點(diǎn)之間的距離記錄為weight[i]，然后加入到邊緣加權(quán)樹(shù)中；(4) 輸出最后構(gòu)成的邊緣加權(quán)樹(shù)。

3.4 PHAStream算法及復(fù)雜度分析

算法2是PHAStream算法的整體步驟，第1-4行是初始化階段，計(jì)算檢查時(shí)間Tg，使用PHA對(duì)初始長(zhǎng)度的數(shù)據(jù)點(diǎn)進(jìn)行聚類(lèi)，得到首批微簇并創(chuàng)建CF向量。第5-17行是PHAStream算法的在線階段，對(duì)于每個(gè)新到達(dá)的數(shù)據(jù)點(diǎn)x，如果數(shù)據(jù)點(diǎn)x和其目標(biāo)微簇均在勢(shì)能拐點(diǎn)之前，那么就將這個(gè)點(diǎn)合并進(jìn)其目標(biāo)微簇中，并更新其CF向量。否則，創(chuàng)建一個(gè)新的微簇和CF向量。每Tg個(gè)時(shí)間戳就檢查調(diào)整所有微簇的類(lèi)型，并采用剪枝策略刪除過(guò)期的微簇。第18-20行是PHAStream算法的離線階段，當(dāng)有聚類(lèi)要求時(shí)，根據(jù)所有正常微簇的dist_arr屬性構(gòu)建距離矩陣，計(jì)算勢(shì)能，構(gòu)建邊緣加權(quán)樹(shù)和樹(shù)狀圖，得到最終聚類(lèi)結(jié)果。

算法2PHAStream算入：數(shù)據(jù)流dataStream, 初始長(zhǎng)度initNumber, 初始聚類(lèi)個(gè)數(shù)q, 最終聚類(lèi)簇個(gè)數(shù)K, 權(quán)重μ, 衰變因數(shù)λ。

輸出：最終聚類(lèi)結(jié)果。

1. 初始化時(shí)間戳timestampt= 0；

2. 計(jì)算周期檢查時(shí)間Tg；

3. 使用PHA對(duì)初始長(zhǎng)度的數(shù)據(jù)點(diǎn)進(jìn)行聚類(lèi)，得到首批微簇；

4. 為每個(gè)微簇構(gòu)建CF向量，也稱(chēng)為微簇；

5. while (流數(shù)據(jù)未結(jié)束) do

6.t++；

7. for (每個(gè)新到達(dá)的數(shù)據(jù)點(diǎn)x) do

8. 尋找數(shù)據(jù)點(diǎn)x的目標(biāo)微簇i；

9. if (數(shù)據(jù)點(diǎn)x和目標(biāo)微簇i的勢(shì)能均在勢(shì)能拐點(diǎn)之前) then

10. 將數(shù)據(jù)點(diǎn)x合并進(jìn)目標(biāo)微簇i；

11. else

12. 新建一個(gè)微簇，并構(gòu)建CF向量；

13. end if

14. end for

15. if (到達(dá)檢查時(shí)間) then

16. 采用剪枝策略，并調(diào)整微簇類(lèi)型；

17. end if

18. if (當(dāng)有聚類(lèi)要求時(shí)) then

19. 使用改進(jìn)的PHA對(duì)所有正常微簇進(jìn)行聚類(lèi)；

20. end if

21. end while

PHAStream算法的在線階段，計(jì)算成本主要在尋找“目標(biāo)微簇”和合并準(zhǔn)則判斷。當(dāng)新到達(dá)數(shù)據(jù)點(diǎn)尋找“目標(biāo)微簇”時(shí)，需要遍歷一遍現(xiàn)有的微簇，計(jì)算現(xiàn)有微簇和新到達(dá)數(shù)據(jù)點(diǎn)的距離，并將此距離更新進(jìn)每個(gè)微簇的dist_arr屬性，時(shí)間復(fù)雜度為O(n)。合并準(zhǔn)則判斷時(shí)，根據(jù)每個(gè)微簇的dist_arr屬性可以構(gòu)成距離矩陣，進(jìn)而計(jì)算每個(gè)微簇的勢(shì)能，將每個(gè)微簇的勢(shì)能按從小到大排序，使用快速排序即可，時(shí)間復(fù)雜度為O(nlogn)。當(dāng)?shù)竭_(dá)檢查時(shí)間時(shí)，遍歷每個(gè)微簇檢查其權(quán)重，是否存在需要?jiǎng)h除的微簇，如果有，刪除這些微簇，并將剩余未刪除微簇中的dist_arr屬性進(jìn)行更新，刪除dist_arr屬性中與刪除微簇相關(guān)的距離信息，時(shí)間復(fù)雜度為O(n)。

PHAStream算法的離線階段，當(dāng)有聚類(lèi)要求時(shí)，根據(jù)每個(gè)微簇的dist_arr屬性可以構(gòu)成距離矩陣，將距離矩陣直接傳入PHA，節(jié)約初始階段計(jì)算距離矩陣的計(jì)算成本，接著構(gòu)建“邊緣加權(quán)樹(shù)”和“樹(shù)狀圖”，根據(jù)最終聚類(lèi)簇個(gè)數(shù)K得到最終聚類(lèi)結(jié)果，根據(jù)PHAStream算法的初始階段所述，此處的時(shí)間復(fù)雜度為O(n2)。

4 實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)環(huán)境

不失一般性，在所有實(shí)驗(yàn)中都規(guī)定每個(gè)時(shí)間戳只有1個(gè)數(shù)據(jù)點(diǎn)到達(dá)，并且到達(dá)的數(shù)據(jù)點(diǎn)經(jīng)過(guò)在線階段處理后，在指定時(shí)間戳陸續(xù)執(zhí)行聚類(lèi)。將本文算法效果與CluStream算法[6]、DenStream算法[10]、StrAP算法[18]和TEDA算法[19]進(jìn)行對(duì)比，算法實(shí)驗(yàn)平臺(tái)為：操作系統(tǒng)Ubuntu 18.04，Intel(R) Xeon(R) CPU E5-2673 v3 @ 2.40 GHz，內(nèi)存64 GB，Python版本3.7。

4.2 數(shù)據(jù)集描述

數(shù)據(jù)集采用KDD-CUP99數(shù)據(jù)集和一組真實(shí)空氣質(zhì)量數(shù)據(jù)集進(jìn)行測(cè)試。

KDD-CUP99數(shù)據(jù)集，一共有4 898 431個(gè)數(shù)據(jù)點(diǎn)，每個(gè)數(shù)據(jù)有41個(gè)維度，本實(shí)驗(yàn)選取34個(gè)連續(xù)屬性，使用前1%樣本數(shù)據(jù)集進(jìn)行測(cè)試，數(shù)據(jù)集總共有50 000條記錄，每隔5 000個(gè)數(shù)據(jù)點(diǎn)進(jìn)行一次聚類(lèi)測(cè)試。

真實(shí)空氣質(zhì)量數(shù)據(jù)集，選取北京市過(guò)去2016年1月1日到2019年12月31日，每天24個(gè)小時(shí)的空氣質(zhì)量數(shù)據(jù)，共有35 064條數(shù)據(jù)，其中無(wú)效數(shù)據(jù)有5 026條，故最終使用的有效數(shù)據(jù)為30 038條，每條數(shù)據(jù)具有7個(gè)屬性，只取PM2.5、PM10、CO、SO2、NO2、O3作為測(cè)試屬性，使用AQI作為分類(lèi)標(biāo)簽，如表1所示。每隔5 000個(gè)數(shù)據(jù)點(diǎn)進(jìn)行一次聚類(lèi)測(cè)試。

表1 空氣質(zhì)量數(shù)據(jù)集屬性

4.3 度量標(biāo)準(zhǔn)

本實(shí)驗(yàn)以聚類(lèi)質(zhì)量SSQ和聚類(lèi)純度Purity作為度量標(biāo)準(zhǔn)。聚類(lèi)質(zhì)量SSQ的定義如下：

SSQ=∑d(pi,ci)2

(17)

式中：pi是每個(gè)數(shù)據(jù)點(diǎn);ci是pi最近的聚類(lèi)微簇中心。即通過(guò)計(jì)算所有點(diǎn)到各自聚類(lèi)中心距離的平方和來(lái)衡量聚類(lèi)質(zhì)量SSQ，SSQ越小，說(shuō)明效果越好。

聚類(lèi)純度Purity的定義如下：

(18)

4.4 模型參數(shù)設(shè)置

本實(shí)驗(yàn)本文中所有試驗(yàn)的初始長(zhǎng)度initNumber均為500， 通過(guò)控制變量法，來(lái)對(duì)區(qū)分正常微簇和噪點(diǎn)微簇的權(quán)重μ、衰變因數(shù)λ、初始聚類(lèi)個(gè)數(shù)q和最終聚類(lèi)簇個(gè)數(shù)K進(jìn)行參數(shù)設(shè)置實(shí)驗(yàn)。由4.3節(jié)聚類(lèi)度量標(biāo)準(zhǔn)可知，SSQ越小越好，Purity越大越好，定義變量p來(lái)表示由SSQ和Purity總體反映的聚類(lèi)效果：

故變量p的值越小，聚類(lèi)效果越好，通過(guò)控制變量法，來(lái)進(jìn)行參數(shù)設(shè)置實(shí)驗(yàn)。

圖4至圖7分別是KDD-CUP99數(shù)據(jù)集對(duì)權(quán)重μ、衰變因數(shù)λ、初始聚類(lèi)個(gè)數(shù)q和最終聚類(lèi)簇個(gè)數(shù)K參數(shù)的聚類(lèi)效果對(duì)比圖。根據(jù)式(19)可知，p值越小越好，所以μ值、λ值、q值和K值分別在區(qū)間[1.7, 2.0]、 [0.1,0.15]、[325,450]、[5,15]之間取值為佳。綜合實(shí)驗(yàn)得出，當(dāng)μ=2.0，λ=0.13，q=400，K=15時(shí)聚類(lèi)效果最好。

圖4 KDD-CUP99數(shù)據(jù)集不同μ值聚類(lèi)效果對(duì)比圖

圖5 KDD-CUP99數(shù)據(jù)集不同λ值聚類(lèi)效果對(duì)比圖

圖6 KDD-CUP99數(shù)據(jù)集不同q值聚類(lèi)效果對(duì)比圖

圖7 KDD-CUP99數(shù)據(jù)集不同K值聚類(lèi)效果對(duì)比圖

圖8至圖11分別是空氣質(zhì)量數(shù)據(jù)集對(duì)權(quán)重μ、衰變因數(shù)λ、初始聚類(lèi)個(gè)數(shù)q和最終聚類(lèi)簇個(gè)數(shù)K參數(shù)的聚類(lèi)效果對(duì)比圖。根據(jù)式(19)可知，p值越小越好，所以μ值、λ值、K值分別在區(qū)間 [1.5, 1.9]、[0.6,0.8]、[5,9]之間取值為佳，由于q值波動(dòng)較大，所以在300、350、400、450這幾個(gè)值中選擇。綜合實(shí)驗(yàn)得出，當(dāng)μ=1.6，λ=0.6，q=400，K=6時(shí)聚類(lèi)效果最好。

圖8 空氣質(zhì)量數(shù)據(jù)集不同μ值聚類(lèi)效果對(duì)比圖

圖9 空氣質(zhì)量數(shù)據(jù)集不同λ值聚類(lèi)效果對(duì)比圖

圖10 空氣質(zhì)量數(shù)據(jù)集不同q值聚類(lèi)效果對(duì)比圖

圖11 空氣質(zhì)量數(shù)據(jù)集不同K值聚類(lèi)效果對(duì)比圖

4.5 聚類(lèi)質(zhì)量驗(yàn)證

圖12和圖13分別反映了五種數(shù)據(jù)流聚類(lèi)算法在KDD-CUP99數(shù)據(jù)集和空氣質(zhì)量數(shù)據(jù)集上的聚類(lèi)質(zhì)量。在KDD-CUP99數(shù)據(jù)集中，隨著數(shù)據(jù)點(diǎn)增多，CluStream算法和DenStream算法的SSQ值小幅度上升，StrAP算法一直保持穩(wěn)定的SSQ值，TEDA算法一開(kāi)始維持較低的SSQ值，后來(lái)開(kāi)始上升。PHAStream算法雖然處于小幅波動(dòng)，但是總體還是比其他四類(lèi)算法低1～3個(gè)數(shù)量級(jí)。

圖12 KDD-CUP99數(shù)據(jù)集聚類(lèi)質(zhì)量對(duì)比圖

圖13 空氣質(zhì)量數(shù)據(jù)集聚類(lèi)質(zhì)量對(duì)比圖

在空氣質(zhì)量數(shù)據(jù)集中，五種算法均保持穩(wěn)定的SSQ值，并且PHAStream算法一直具有更低的SSQ值。因?yàn)镾SQ值越低表示聚類(lèi)質(zhì)量越高，所以PHAStream算法具有更高的聚類(lèi)質(zhì)量。

4.6 聚類(lèi)純度驗(yàn)證

圖14和圖15分別反映了五種數(shù)據(jù)流聚類(lèi)算法在KDD-CIP99數(shù)據(jù)集和空氣質(zhì)量數(shù)據(jù)集上的聚類(lèi)純度。在KDD-CUP99數(shù)據(jù)集中，隨著數(shù)據(jù)點(diǎn)的增多，CluStream算法一開(kāi)始保持較高的聚類(lèi)純度，之后一直處于較低的水平，因?yàn)樵朦c(diǎn)的增多，CluStream算法是以距離為相似度度量，且對(duì)所有數(shù)據(jù)點(diǎn)進(jìn)行聚類(lèi)，故聚類(lèi)純度不理想。DenStream算法和StrAP算法一直維持較高且較為穩(wěn)定聚類(lèi)純度，TEDA算法總體維持較高的聚類(lèi)純度，PHAStream算法雖然在第20 000和第45 000個(gè)數(shù)據(jù)點(diǎn)時(shí)聚類(lèi)純度小幅降低，但是總體具有更好的聚類(lèi)純度。

圖14 KDD-CUP99數(shù)據(jù)集聚類(lèi)純度對(duì)比圖

圖15 空氣質(zhì)量數(shù)據(jù)集聚類(lèi)純度對(duì)比圖

在空氣質(zhì)量數(shù)據(jù)集中，CluStream算法和DenStream算法整個(gè)過(guò)程有小幅度波動(dòng)，但是兩者總體聚類(lèi)純度不高，StrAP算法聚類(lèi)純度較為穩(wěn)定，TEDA算法一開(kāi)始聚類(lèi)純度不高，但是隨著數(shù)據(jù)點(diǎn)的增多，聚類(lèi)純度基本與StrAP算法持平，PHAStream算法相對(duì)其他四種算法一直具有更高的聚類(lèi)純度，這得益于勢(shì)能場(chǎng)模型下，依據(jù)距離矩陣和勢(shì)能共同作為相似度度量，故PHAStream算法具有更高的聚類(lèi)純度。

4.7 抗噪性驗(yàn)證

為了驗(yàn)證本文算法的抗噪性，將空氣質(zhì)量數(shù)據(jù)集進(jìn)行適當(dāng)修改，改為含有5%左右噪點(diǎn)的數(shù)據(jù)集，各算法在此數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，并求出所有統(tǒng)計(jì)時(shí)刻的平均值來(lái)進(jìn)行前后對(duì)比。

由圖16和圖17可知，在加入5%左右的噪點(diǎn)后，CluStream算法在聚類(lèi)質(zhì)量和聚類(lèi)純度上相對(duì)其他幾種算法變化較大，這是由于CluStream算法是以距離作為相似度度量標(biāo)準(zhǔn)，對(duì)噪點(diǎn)較為敏感，本文的PHAStream算法使用勢(shì)能和距離來(lái)作為相似度度量標(biāo)準(zhǔn)，兩者分別反映了數(shù)據(jù)點(diǎn)的全局與局部分布，減少噪點(diǎn)的干擾，具有更好的聚類(lèi)效果。

圖16 聚類(lèi)質(zhì)量對(duì)比圖

圖17 聚類(lèi)純度對(duì)比圖

4.8 時(shí)間效率驗(yàn)證

圖18和圖19分別反映了五種數(shù)據(jù)流聚類(lèi)算法在KDD-CUP99數(shù)據(jù)集和空氣質(zhì)量數(shù)據(jù)集的執(zhí)行時(shí)間對(duì)比圖。PHAStream算法在整個(gè)階段中均保持更低的時(shí)間消耗，這得益于新的概要數(shù)據(jù)結(jié)構(gòu)中的dist_arr屬性和邊緣加權(quán)樹(shù)技術(shù)，當(dāng)有聚類(lèi)要求時(shí)，可以快速構(gòu)建距離矩陣，計(jì)算出勢(shì)能，進(jìn)而得到聚類(lèi)結(jié)果。

圖18 KDD-CUP99數(shù)據(jù)集時(shí)間效率對(duì)比圖

圖19 空氣質(zhì)量數(shù)據(jù)集時(shí)間效率對(duì)比圖

4.9 內(nèi)存消耗驗(yàn)證

圖20為五種數(shù)據(jù)流聚類(lèi)算法在KDD-CUP99數(shù)據(jù)集和空氣質(zhì)量數(shù)據(jù)集的內(nèi)存消耗對(duì)比圖。PHAStream算法相對(duì)于其他四種算法均消耗更多的內(nèi)存，這主要是因?yàn)槠涓乓獢?shù)據(jù)結(jié)構(gòu)中的dist_arr屬性，因?yàn)樵搶傩源鎯?chǔ)了微簇之間的距離信息。PHAStream算法雖然消耗了更多的內(nèi)存，但是在其他聚類(lèi)效果上表現(xiàn)更優(yōu)秀。

圖20 時(shí)間效率對(duì)比圖

5 結(jié) 語(yǔ)

本文提出一種基于勢(shì)能模型的數(shù)據(jù)流聚類(lèi)算法PHAStream，將基于勢(shì)能模型的層次聚類(lèi)算法PHA改造適用于數(shù)據(jù)流聚類(lèi)。相對(duì)于大部分以距離為相似度度量的數(shù)據(jù)流聚類(lèi)算法，本文的PHAStream算法以距離和勢(shì)能作為相似度度量，這兩者分別反映了所有數(shù)據(jù)點(diǎn)的局部和全局分布，減少噪點(diǎn)對(duì)聚類(lèi)的干擾。實(shí)驗(yàn)結(jié)果表明，該算法可以有效提高聚類(lèi)質(zhì)量、聚類(lèi)純度和時(shí)間效率。

在本文的研究中，需要人工設(shè)置最終聚類(lèi)簇個(gè)數(shù)。未來(lái)將考慮利用勢(shì)能自動(dòng)地確定聚類(lèi)簇，使得該數(shù)據(jù)流聚類(lèi)算法更高效。