一種聯(lián)系數(shù)表達(dá)的位置不確定數(shù)據(jù)流聚類算法

史玲娟，黃德才

(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州 310023)

1 引 言

隨著信息技術(shù)的快速發(fā)展，數(shù)據(jù)流模型在互聯(lián)網(wǎng)數(shù)據(jù)傳輸、大型零售業(yè)銷售信息、無線傳感器網(wǎng)絡(luò)[1,2]等眾多領(lǐng)域中得到應(yīng)用，并產(chǎn)生了大量不確定數(shù)據(jù)流.數(shù)據(jù)的不確定性主要由測(cè)量?jī)x器誤差、外部干擾、數(shù)據(jù)丟失、數(shù)據(jù)集成等內(nèi)在和外在因素造成數(shù)據(jù)不可靠、隨機(jī)、模糊、不完整等特性.

不確定數(shù)據(jù)流中的不確定數(shù)據(jù)模型一般可分為元組級(jí)(或存在級(jí))不確定性(TLU)模型和屬性級(jí)不確定性(ALU)模型.TLU描述了不確定元組存在的可能性概率，而不確定元組的屬性值是確定性的.因此，僅將表示元組存在概率的概率維度加入到TLU的元組模型中.屬性值的不確定性可以用ALU模型來描述[3]，已有的ALU模型通常有兩種形式：一種是在ALU模型中加入屬性值不確定性的分布函數(shù)，另一種是加入?yún)^(qū)間數(shù)(或者由區(qū)間數(shù)衍生而來的三角模糊數(shù)和梯形模糊數(shù))表示的屬性值不確定性.位置不確定數(shù)據(jù)屬于屬性級(jí)不確定性的研究范疇，但它是一種新的不確定數(shù)據(jù)類型，無法用已有的ALU模型準(zhǔn)確描述，因此需要研究新的模型來對(duì)其進(jìn)行合理描述.

不確定數(shù)據(jù)流聚類算法是一個(gè)重要的研究課題，在學(xué)術(shù)界引起了眾多研究者的關(guān)注.最近有大量的數(shù)據(jù)流聚類研究項(xiàng)目，這些研究項(xiàng)目產(chǎn)生了許多成功的算法[4].

針對(duì)存在級(jí)不確定數(shù)據(jù)流聚類問題，戴東波等[5]提出了P-Stream算法，基于不確定數(shù)據(jù)期望設(shè)置微簇核心，引入了強(qiáng)簇、過渡簇和弱簇的概念構(gòu)造“當(dāng)前簇”和“候選簇”兩層簇窗口，但其離群點(diǎn)的處理機(jī)制不夠完善，當(dāng)大量離群點(diǎn)涌入時(shí)，離群點(diǎn)形成的“候選簇”會(huì)直接替代“當(dāng)前簇”，從而影響最終的聚類質(zhì)量;張晨等[6]提出了Emicro算法，該方法采用概率表示元組存在級(jí)的不確定性，考慮了元組間的距離和元組的不確定性，利用微簇結(jié)構(gòu)存儲(chǔ)簇的統(tǒng)計(jì)信息，采用“核心微簇”緩沖區(qū)和“離群點(diǎn)微簇”緩沖區(qū)兩層聚類模型，但其離群點(diǎn)處理機(jī)制不夠完善，當(dāng)出現(xiàn)新的“離群點(diǎn)”時(shí)，采取立即將其刪除的策略會(huì)誤將代表新數(shù)據(jù)模型的初始數(shù)據(jù)刪除，從而影響聚類的質(zhì)量.Li等[7]提出了C_UStream算法，假定數(shù)據(jù)的存在概率已知，使用網(wǎng)格算法和滑動(dòng)窗口機(jī)制，然而網(wǎng)格劃分在處理高維數(shù)據(jù)會(huì)形成網(wǎng)格數(shù)據(jù)爆炸式增長(zhǎng)，滑動(dòng)窗口機(jī)制則忽略了歷史數(shù)據(jù)的影響.夏聰?shù)萚8]提出了基于近鄰傳播的演化數(shù)據(jù)流EAP-UStream算法，該算法假定數(shù)據(jù)在每個(gè)維度上有不同的存在概率并且此概率已知，提出不確定微簇關(guān)聯(lián)度的概念，并以此為基礎(chǔ)構(gòu)造不確定相似度矩陣，結(jié)合近鄰傳播思想實(shí)現(xiàn)不確定數(shù)據(jù)流演化聚類.離線聚類過程先在每個(gè)維度上進(jìn)行聚類，而后進(jìn)行聚類融合.鄭祺等[9]提出了基于引力相似度的Gmicro算法，該算法假定數(shù)據(jù)存在概率已知，在距離度量時(shí)綜合考慮元組之間的相似度與元組自身的不確定性，利用引力相似度為每個(gè)不斷到達(dá)的數(shù)據(jù)元組尋找可能歸屬的微簇.以上算法需要以數(shù)據(jù)存在概率已知為條件，且以上算法中的存在不確定性是不確定數(shù)據(jù)的固有屬性，不隨時(shí)間變化.針對(duì)流數(shù)據(jù)的特征，本文采用時(shí)間衰減的存在不確定性模型，即數(shù)據(jù)的存在級(jí)不確定性隨著時(shí)間增長(zhǎng)逐漸降低.

針對(duì)屬性級(jí)不確定數(shù)據(jù)流聚類問題，Aggarwal等提出了不確定數(shù)據(jù)流聚類算法UMicro[10]，該算法采用標(biāo)準(zhǔn)差表示不確定性信息，構(gòu)建了不確定數(shù)據(jù)聚類模型，將確定數(shù)據(jù)下的聚類特征CF結(jié)構(gòu)擴(kuò)展為ECF結(jié)構(gòu)，但是其聚類模型更新策略易導(dǎo)致錯(cuò)誤的聚類結(jié)果.其后，Aggarwal等又針對(duì)高維數(shù)據(jù)提出UPStreams[11]算法，該算法通過映射實(shí)現(xiàn)數(shù)據(jù)降維.Zhang等[12]提出LuMicro算法，通過使用信息熵概念度量元組的不確定屬性，并將其定義不確定度，聚類的目標(biāo)函數(shù)轉(zhuǎn)化為整體不確定度最低.羅清華等[13]提出UIDMicro算法，采用區(qū)間數(shù)方式表示不確定數(shù)據(jù)，實(shí)現(xiàn)多維不確定數(shù)據(jù)流聚類.算法在計(jì)算區(qū)間數(shù)的期望距離時(shí)復(fù)雜度較高，微簇半徑按照微簇中數(shù)據(jù)距離微簇中心點(diǎn)的期望來定義，對(duì)于新建的微簇，微簇中僅僅存在一個(gè)點(diǎn)或者少量數(shù)據(jù)點(diǎn)，微簇半徑的值受初始數(shù)據(jù)點(diǎn)影響大，進(jìn)而影響了實(shí)驗(yàn)結(jié)果.韓東紅等[14]提出滑動(dòng)窗口下基于密度的不確定數(shù)據(jù)流聚類算法USDENCLUE算法，定義了元組不確定指數(shù)和不確定度，通過尋找密度吸引點(diǎn)獲得微簇.另外韓東紅等[15]提出了一種同時(shí)考慮存在級(jí)和屬性級(jí)不確定的數(shù)據(jù)流處理方法，算法要求先在半監(jiān)督學(xué)習(xí)下獲得聚類后的簇特征，而后在線進(jìn)行分類.不適合演化性較強(qiáng)的數(shù)據(jù)流.

本文研究的屬性位置不確定數(shù)據(jù)是屬性級(jí)不確定數(shù)據(jù)中的一種，它區(qū)別于傳統(tǒng)的屬性級(jí)不確定數(shù)據(jù)，更加強(qiáng)調(diào)位置數(shù)據(jù)的空間關(guān)系.屬性位置不確定數(shù)據(jù)廣泛地存在于GIS(地理信息系統(tǒng))中[16].以上屬性級(jí)不確定數(shù)據(jù)流聚類算法在不確定數(shù)據(jù)相似度度量時(shí)，都沒有考慮不確定數(shù)據(jù)的空間位置關(guān)系.其算法對(duì)于屬性級(jí)不確定性的表達(dá)，大部分采取假定分布函數(shù)(高斯分布)的策略，通過數(shù)據(jù)樣本計(jì)算分布函數(shù)中的參數(shù)(高斯分布的期望和方差).但是真實(shí)數(shù)據(jù)的實(shí)際分布函數(shù)是很難獲得的[17].而文獻(xiàn)[13]中區(qū)間數(shù)在處理空間位置關(guān)系時(shí)，受到區(qū)間數(shù)本身性質(zhì)的影響，需要分別計(jì)算位置區(qū)間的上限和下限，由于區(qū)間數(shù)的兩端確定、中間不確定的特點(diǎn)，宏觀距離的取值需要人為設(shè)定參數(shù).王駿等[18]率先在數(shù)據(jù)規(guī)模固定的數(shù)據(jù)集上用聯(lián)系數(shù)巧妙地表示不確定數(shù)據(jù)對(duì)象，提出UCNDBSCAN算法.然而該算法中對(duì)象間距離衡量標(biāo)準(zhǔn)僅僅簡(jiǎn)單地運(yùn)用了聯(lián)系數(shù)態(tài)勢(shì)值理論，使用距離的確定性聯(lián)系分量加上二元距離聯(lián)系數(shù)態(tài)勢(shì)值表示不確定對(duì)象間的距離.本文專門重新定義了對(duì)象間的聯(lián)系距離，并利用偏聯(lián)系數(shù)的概念，求取距離的確定性聯(lián)系分量在不確定層次上發(fā)展而來的程度，進(jìn)而得到宏觀距離公式.并針對(duì)數(shù)據(jù)流在線聚類過程，將二元距離聯(lián)系數(shù)擴(kuò)展為三元距離聯(lián)系數(shù)，并運(yùn)用三元聯(lián)系數(shù)態(tài)勢(shì)理論衡量不確定數(shù)據(jù)對(duì)象與不確定微簇之間的距離關(guān)系.

本文針對(duì)位置不確定數(shù)據(jù)流，提出一種聯(lián)系數(shù)表達(dá)的不確定數(shù)據(jù)流聚類算法UCNStream.構(gòu)造了針對(duì)位置不確定性的新屬性不確定性數(shù)據(jù)表達(dá)模型，定義了不確定數(shù)據(jù)對(duì)象間的聯(lián)系距離，構(gòu)建了用于數(shù)據(jù)流在線處理的三元距離聯(lián)系數(shù)下不確定對(duì)象與微簇間距離位置的衡量標(biāo)準(zhǔn)，并運(yùn)用衰減函數(shù)對(duì)數(shù)據(jù)的存在不確定度進(jìn)行時(shí)間衰減.算法采用在線/離線兩級(jí)處理框架，在線階段使用潛在核心微簇緩沖區(qū)(BUFc)和離群微簇緩沖區(qū)(BUFo)構(gòu)成的雙緩沖區(qū)，利用微簇的存在不確定度，實(shí)現(xiàn)新的動(dòng)態(tài)調(diào)整微簇策略(離群微簇存在不確定度到達(dá)一定閾值時(shí)成長(zhǎng)為潛在核心微簇;微簇存在不確定度過低時(shí)說明微簇過期，進(jìn)行刪除).離線階段，根據(jù)密度可達(dá)等概念進(jìn)行聚類，可以發(fā)現(xiàn)任意形狀的簇.文章分析了算法的計(jì)算復(fù)雜性為線性復(fù)雜性，通過在實(shí)際數(shù)據(jù)集上與UMicro算法和UIDMicro算法的對(duì)比實(shí)驗(yàn)分析，實(shí)驗(yàn)結(jié)果表明，UCNStream算法的聚類結(jié)果在聚類純度方面優(yōu)于已有的算法，具有較好的聚類精度.

2 相關(guān)定義

本部分對(duì)本文所提出的算法中所用到的一些概念進(jìn)行定義.

2.1 聯(lián)系數(shù)相關(guān)定義

本文針對(duì)屬性位置不確定數(shù)據(jù)，提出一種聯(lián)系數(shù)表達(dá)的不確定數(shù)據(jù)表達(dá)方式.聯(lián)系數(shù)是集對(duì)分析SPA[19]這一新的軟計(jì)算方法中的重要概念之一，是處理數(shù)據(jù)不確定性的一種新的數(shù)學(xué)工具，在調(diào)度評(píng)估問題、聚類問題和人工智能領(lǐng)域[20]都有著越來越多的應(yīng)用.在位置不確定數(shù)據(jù)研究中，不確定對(duì)象宏觀位置的確定性和微觀上不確定對(duì)象樣本點(diǎn)位置的不確定性與集對(duì)分析理論契合.聯(lián)系數(shù)在屬性位置不確定數(shù)據(jù)的表達(dá)上具有優(yōu)勢(shì)[20]，首先，聯(lián)系數(shù)是中間確定兩端不確定的不確定數(shù)據(jù)模型，即聯(lián)系數(shù)是數(shù)據(jù)期望確定的，更符合位置不確定數(shù)據(jù)的特點(diǎn);其次，聯(lián)系數(shù)中不確定分量可以大于確定分量也能夠小于確定分量，在位置關(guān)系的表達(dá)上有更高的一致性;最后，聯(lián)系數(shù)除了兩端不確定之外，還有i的不確定信息，有更豐富的關(guān)于不確定的信息.

定義1.聯(lián)系數(shù)[18].稱形如式(1)的數(shù)為二元聯(lián)系數(shù).

u=a+bi

(1)

其中a稱為確定性聯(lián)系分量，b稱為不確定性聯(lián)系分量，a為實(shí)數(shù)，b為非負(fù)實(shí)數(shù)，(a,b)統(tǒng)稱為聯(lián)系數(shù)u的聯(lián)系分量，i∈[-1,1].

稱形如式(2)的數(shù)為三元聯(lián)系數(shù)，三元聯(lián)系數(shù)是聯(lián)系數(shù)的一般表達(dá)形式.

u=a+bi+cj

(2)

其中a稱為同聯(lián)系分量，b稱為異聯(lián)系分量，c稱為反聯(lián)系分量，a，b，c均為非負(fù)實(shí)數(shù)，i表示相異關(guān)系，j表示相反關(guān)系.

二元聯(lián)系數(shù)u=a+bi可以看作是當(dāng)a+b+c=n(n為已知常數(shù))且a，b，c均為非負(fù)實(shí)數(shù)時(shí)u=a+bi+cj的等價(jià)表達(dá).

定義2.二元聯(lián)系數(shù)的四則運(yùn)算[18].

1)二元聯(lián)系數(shù)加法運(yùn)算

設(shè)u1=a1+b1i，u2=a2+b2i是兩個(gè)二元聯(lián)系數(shù)，則:

u1+u2?(a1+a2)+(b1+b2)i

(3)

因?yàn)閍1，a2是實(shí)數(shù)，所以(a1+a2)是實(shí)數(shù).又因?yàn)閎1，b2是非負(fù)數(shù)，所以(b1+b2)是非負(fù)數(shù).因此，二元聯(lián)系數(shù)相加的結(jié)果依然是一個(gè)二元聯(lián)系數(shù).

2)二元聯(lián)系數(shù)減法運(yùn)算

設(shè)u1=a1+b1i，u2=a2+b2i是兩個(gè)二元聯(lián)系數(shù)，則:

u1-u2?(a1-a2)+(b1+b2)i

(4)

易證，二元聯(lián)系數(shù)相減的結(jié)果依然是一個(gè)二元聯(lián)系數(shù).

3)二元聯(lián)系數(shù)乘法運(yùn)算

設(shè)u1=a1+b1i，u2=a2+b2i是兩個(gè)二元聯(lián)系數(shù)，則:

u1*u2?(a1*a2)+(b1*b2)i

(5)

易證，二元聯(lián)系數(shù)相乘的結(jié)果依然是一個(gè)二元聯(lián)系數(shù).

4)二元聯(lián)系數(shù)根式運(yùn)算

設(shè)u=a+bi是一個(gè)二元聯(lián)系數(shù)且a非負(fù)，則:

(6)

易證，二元聯(lián)系數(shù)相乘的結(jié)果依然是一個(gè)二元聯(lián)系數(shù).

定義3.聯(lián)系數(shù)的態(tài)勢(shì)[21].

態(tài)勢(shì)是指聯(lián)系數(shù)中各聯(lián)系份量大小關(guān)系所確定的系統(tǒng)狀態(tài)和趨勢(shì).不同聯(lián)系數(shù)中聯(lián)系分量的大小關(guān)系規(guī)律可以用聯(lián)系數(shù)的態(tài)勢(shì)函數(shù)來描述.

1)二元聯(lián)系數(shù)的態(tài)勢(shì)

表1 u=a+bi的態(tài)勢(shì)函數(shù)表
Table 1 Situation function table of u=a+bi

聯(lián)系分量的大小關(guān)系態(tài)勢(shì)態(tài)勢(shì)函數(shù)shi(u)=aba>b同勢(shì)>1a=b均勢(shì)=1a

2)三元聯(lián)系數(shù)的態(tài)勢(shì)

若聯(lián)系數(shù)的態(tài)勢(shì)大于1，即a>c，則屬于同勢(shì)，同勢(shì)的情況下，b的值越小，同勢(shì)的等級(jí)越高.

若聯(lián)系數(shù)的態(tài)勢(shì)等于1，即a=c，則屬于均勢(shì)，均勢(shì)的情況下，b的值越小，均勢(shì)的等級(jí)越高.

若聯(lián)系數(shù)的態(tài)勢(shì)小于1，即a

如果用三元聯(lián)系數(shù)表示距離，那么同勢(shì)的情況表示距離傾向于更大的方向，且同勢(shì)時(shí)相同態(tài)勢(shì)值的聯(lián)系數(shù)，同勢(shì)等級(jí)越高，宏觀上距離越大;同理，反勢(shì)的情況表示距離傾向于更小的方向，且反勢(shì)時(shí)相同態(tài)勢(shì)值的聯(lián)系數(shù)，同勢(shì)等級(jí)越高，宏觀上距離越小;在均勢(shì)的情況下，表示距離傾向于中立，且均勢(shì)時(shí)相同態(tài)勢(shì)值的聯(lián)系數(shù)，均勢(shì)等級(jí)越高，宏觀上這種中立的傾向越大.

定義4.二元聯(lián)系數(shù)的偏聯(lián)系數(shù)[21].設(shè)u=a+bi是一個(gè)二元聯(lián)系數(shù)，則有:

偏同聯(lián)系數(shù)?+u：

(7)

偏反聯(lián)系數(shù)?-u：

(8)

全偏聯(lián)系數(shù)?u：

(9)

全偏聯(lián)系數(shù)也簡(jiǎn)稱偏聯(lián)系數(shù).其中偏同聯(lián)系數(shù)?+u刻畫了聯(lián)系數(shù)中確定性聯(lián)系分量a由原先處在b層次上正向發(fā)展而來的程度;偏反聯(lián)系數(shù)?-u刻畫了聯(lián)系數(shù)中不確定聯(lián)系分量b由原先處在b層次上負(fù)向發(fā)展而來的程度.

2.2 算法相關(guān)定義

定義7.不確定數(shù)據(jù)對(duì)象間的聯(lián)系距離.不確定數(shù)據(jù)對(duì)象X1,X2間的聯(lián)系距離表示為dis(X1,X2).

dis(X1,X2)=

(10)

dis(X1,X2)是一個(gè)聯(lián)系數(shù)，可以表示為dis(X1,X2)=udis=adis+bdisi.此時(shí)偏同聯(lián)系數(shù)?+u代表了距離確定聯(lián)系分量在不確定層次上正向發(fā)展的程度，而不確定數(shù)據(jù)距離計(jì)算的時(shí)候更加注重距離最小的情況，即確定聯(lián)系分量在不確定層次上反向發(fā)展的程度1-?+u.進(jìn)而，可以得到確定聯(lián)系分量在不確定層次上反向發(fā)展的距離adis′=adis*(1-?+u).本文用確定聯(lián)系分量減去確定聯(lián)系分量在不確定層次上反向發(fā)展的距離表示X1，X2的宏觀距離Dis(X1,X2).

(11)

由定義7可以得到結(jié)論1：

定義8.時(shí)間衰減.隨著不確定數(shù)據(jù)流的演化，每個(gè)數(shù)據(jù)對(duì)象的存在不確定度隨時(shí)間增長(zhǎng)呈現(xiàn)衰減趨勢(shì)，本文假定數(shù)據(jù)對(duì)象的存在不確定度初始值為1，使用時(shí)間衰減函數(shù)D(x,t)=2-λ(t-T(x))，衰減系數(shù)λ∈(0,1)，λ越大衰減程度越高.

由定義8可以得到結(jié)論2：

定義10.不確定微簇中心.不確定微簇UC的中心由微簇中心期望和微簇不確定度構(gòu)成，微簇中心的期望定義為在當(dāng)前微簇存在概率下的線性平均值:

(12)

微簇中心的不確定度同樣取一個(gè)標(biāo)準(zhǔn)差，定義為簇內(nèi)各數(shù)據(jù)對(duì)象到微簇中心的期望距離平方和的均值的平方根.

(13)

定義11.不確定微簇半徑.微簇半徑由確定部分和不確定部分綜合得出.半徑取簇內(nèi)各數(shù)據(jù)對(duì)象到微簇中心的平均距離.根據(jù)聯(lián)系數(shù)的運(yùn)算法則，確定部分的值為R1，不確定部分的值為R2.

(14)

(15)

不確定數(shù)據(jù)對(duì)象與不確定微簇集合set(C)={C1,C2,C3,…,Cm}之間，有不確定距離集合set(dis(p,C))={dis(p,C1),dis(p,C2),…,dis(p,Cm)}，存在不確定距離上界記做maxset(c),p=max(ap,cx+bp,cx).因此，距離聯(lián)系數(shù)可以擴(kuò)展為a+b+c=maxset(c),p的三元聯(lián)系數(shù).

不確定數(shù)據(jù)對(duì)象p與不確定微簇Cm間距離的三元聯(lián)系數(shù)表示為up,cm=ap,cm+bp,cmi+cp,cmj，其中c=maxset(c),p-ap,cm-bp,cm.

不確定數(shù)據(jù)對(duì)象p與不確定微簇Cm間的距離態(tài)勢(shì)GP(up,cm)=eap,cm-cp,cm，態(tài)勢(shì)值越小，距離越接近.

定義13.核心微簇(core-micro-cluster).將存在不確定度大于μ的潛在核心微簇定義為核心微簇.

定義14.潛在核心微簇(potential c-micro-cluster).將存在不確定度大于βμ的微簇定義為核心微簇.參數(shù)β∈(-1,1).

定義15.離群微簇(outlier micro-cluster).將存在不確定度不大于βμ的微簇定義為核心微簇.

定義16.直接密度可達(dá).不確定微簇UC1和UC2，其中UC1是核心微簇，UC1和UC2微簇中心的宏觀距離小于2ε，則稱UC1到UC2直接密度可達(dá).

定義17.間接密度可達(dá)微簇.不確定微簇UC1和UC2，其中UC1是核心微簇，存在一條核心微簇鏈UC1,…,UC2,則稱UC1到UC2間接密度可達(dá).

3 UCNStream算法

UCNStream算法主要包括初始化、在線微簇維護(hù)算法和離線宏聚類算法三個(gè)部分.初始化階段利用初始的小規(guī)模數(shù)據(jù)集調(diào)整參數(shù);在線部分利用不確定數(shù)據(jù)本身的特點(diǎn)構(gòu)建和維護(hù)不確定微簇;離線階段進(jìn)行基于密度的不確定數(shù)據(jù)宏聚類.算法主要步驟如下:

Step1.利用初始數(shù)據(jù)集，調(diào)整算法參數(shù).

Step2.調(diào)用在線微簇維護(hù)算法，動(dòng)態(tài)調(diào)整微簇的數(shù)量和微簇聚類特征.

Step3.提交聚類請(qǐng)求，進(jìn)行宏聚類算法.

3.1 初始化算法

基于密度的聚類算法中，密度半徑ε和密度閾值μ是兩個(gè)非常重要的參數(shù)，通過對(duì)初始樣本數(shù)據(jù)進(jìn)行分析，將這兩個(gè)參數(shù)自適應(yīng)地初始化，參數(shù)初始化的部分包含兩步:

Step1.由于中心是局部密度較大且距離其他中心較遠(yuǎn)的點(diǎn)，同時(shí)滿足這兩個(gè)條件的點(diǎn)稱為密度峰值，選用一個(gè)較小的截?cái)嗑嚯x，利用密度峰值算法對(duì)初識(shí)數(shù)據(jù)集進(jìn)行聚類，得到合理的簇間最小聯(lián)系距離，利用公式(11)計(jì)算其對(duì)應(yīng)的宏觀距離，初始化微簇半徑ε為這個(gè)宏觀距離的一半.

Step2.按照ε鄰域下局部密度和數(shù)據(jù)對(duì)象到其他簇中心最短距離的乘積大小，將初始數(shù)據(jù)集降序排列構(gòu)成數(shù)據(jù)隊(duì)列ListData.

Step2.1.取出ListData中最前的一個(gè)數(shù)據(jù)點(diǎn)p，構(gòu)建以點(diǎn)p為中心，半徑為ε的微簇，微簇含有數(shù)據(jù)點(diǎn)數(shù)量n=1.

Step2.2.依次取出ListData中最前的一個(gè)數(shù)據(jù)點(diǎn)p，直到ListData為空時(shí)轉(zhuǎn)Step 2.4.如果數(shù)據(jù)點(diǎn)p落在已有的微簇半徑范圍內(nèi)中，該微簇的數(shù)據(jù)點(diǎn)數(shù)量n增加1，重復(fù)Step 2.2.否則，轉(zhuǎn)Step 2.3.

Step2.3.獲取數(shù)據(jù)點(diǎn)p到最近一個(gè)微簇的距離d，如果d≥2*ε，構(gòu)建以點(diǎn)p為中心的微簇.否則標(biāo)記這個(gè)數(shù)據(jù)點(diǎn)為待處理，轉(zhuǎn)Step 2.2.

Step2.4.依次取出ListData中標(biāo)記為待處理的數(shù)據(jù)點(diǎn)p，如果數(shù)據(jù)點(diǎn)p落在已有的微簇半徑范圍內(nèi)中，該微簇的數(shù)據(jù)點(diǎn)數(shù)量n增加1.否則，構(gòu)建以點(diǎn)p為中心的微簇.

Step2.5.計(jì)算微簇中包含數(shù)據(jù)的平均個(gè)數(shù)，作為μ的取值.并將微簇中含有數(shù)據(jù)點(diǎn)數(shù)量大于μ的微簇作為初始的潛在核心微簇.

這個(gè)初始化的過程，既得到了初始的潛在核心微簇，也達(dá)到參數(shù)初始化的目的.克服了UIDMicro算法直接將最初的nmicro個(gè)數(shù)據(jù)分別生成微簇，進(jìn)行初始化當(dāng)前微簇窗口的不合理性.UIDMicro算法初始化得到的微簇窗口不具備微簇的代表性，將導(dǎo)致聚類初期微簇結(jié)構(gòu)頻繁地更新，微簇邊界值的判定條件無法形成.同時(shí)，參數(shù)選擇上優(yōu)于UIDMicro算法中給定微簇最低包含數(shù)據(jù)個(gè)數(shù)閾值的做法.初始化算法對(duì)后續(xù)的運(yùn)算過程和聚類結(jié)果都有積極的意義.

3.2 在線微簇維護(hù)算法

在線微簇聚類算法采用雙緩沖區(qū)，即潛在核心微簇緩沖區(qū)(BUFc)和離群微簇緩沖區(qū)(BUFo)，BUFc中更新并保存潛在核心微簇的聚類特征;BUFo中更新并保存離群微簇的聚類特征，當(dāng)一個(gè)離群微簇成長(zhǎng)為潛在核心微簇時(shí)，將該微簇的聚類特征轉(zhuǎn)存到BUFc中.令nc表示潛在核心微簇緩沖區(qū)內(nèi)可保存微簇的最大值，no表示離群微簇緩沖區(qū)內(nèi)可保存微簇的最大值，noc表示內(nèi)存中限定的微簇?cái)?shù)量最大值.

在線微簇維護(hù)算法分成在線聚類和在線緩沖區(qū)更新調(diào)整兩個(gè)部分.在線聚類算法根據(jù)不斷到達(dá)的數(shù)據(jù)對(duì)象更新微簇的聚類特征，在線緩沖區(qū)更新調(diào)整算法則定時(shí)檢查微簇是否存在度過低，并刪除那些存在度太低的不確定微簇.

在線聚類算法

Step1.對(duì)于每個(gè)到來的數(shù)據(jù)對(duì)象p，嘗試把數(shù)據(jù)對(duì)象放入距離態(tài)勢(shì)最小的潛在核心微簇.如果加入p后，微簇的宏觀半徑小于閾值ε，則確認(rèn)p的分配，更新微簇聚類特征，轉(zhuǎn)Step 1.否則，轉(zhuǎn)Step 2.

Step2.嘗試把數(shù)據(jù)對(duì)象p放入距離態(tài)勢(shì)最小的離群微簇.如果加入p后，微簇的宏觀半徑小于閾值ε，則確認(rèn)p的分配，繼續(xù)Step 2的子操作.否則，轉(zhuǎn)Step 3.

Step2.1.更新微簇聚類特征，如果更新微簇聚類特征后，離群微簇存在不確定度大于βμ，(說明這個(gè)離群微簇已經(jīng)成長(zhǎng)為一個(gè)潛在核心微簇)，進(jìn)入Step 2.2.否則，轉(zhuǎn)Step 1.

Step2.2.檢查潛在核心微簇緩沖區(qū)是否已滿，如果潛在核心微簇緩沖區(qū)已滿，則刪除潛在核心微簇緩沖區(qū)中存在不確定度最低的微簇.

Step2.3.將這個(gè)微簇從離群微簇緩沖區(qū)轉(zhuǎn)存到潛在核心微簇緩沖區(qū).轉(zhuǎn)Step 1.

Step3.檢查離群微簇緩沖區(qū)是否已滿.

Step3.1.如果離群微簇緩沖區(qū)已滿，則刪除離群微簇緩沖區(qū)中存在不確定度最低的微簇.

Step3.2.為數(shù)據(jù)對(duì)象p建立新的離群微簇.

由上述過程可知，算法優(yōu)先考慮吸收新數(shù)據(jù)對(duì)象，然后考慮創(chuàng)建新微簇，這樣能夠避免本應(yīng)屬于某個(gè)現(xiàn)有微簇的數(shù)據(jù)對(duì)象占用內(nèi)存微簇存儲(chǔ)資源和在后續(xù)聚類中進(jìn)行微簇合并的多余操作，避免現(xiàn)有微簇因存在不確定度降低過快而過早被刪除.從Step 2的子操作可發(fā)現(xiàn)，本文及時(shí)更新由離群微簇成長(zhǎng)而來的潛在核心微簇進(jìn)入BUFc、維護(hù)在線聚類模型，使數(shù)據(jù)對(duì)象盡可能被潛在核心微簇吸收.

根據(jù)結(jié)論2易知核心微簇密度μ與潛在核心微簇密度βμ之間應(yīng)滿足μ的關(guān)系，β取值應(yīng)不小于1-2-λ，本文采用向上取值保留1-2-λ小數(shù)點(diǎn)后一位，得到潛在核心微簇最小密度參數(shù)βμ.

間隔時(shí)間Tp進(jìn)行微簇的存在度檢查并更新微簇，微簇刪除機(jī)制算法過程如下.

在線緩沖區(qū)更新調(diào)整算法

Step1.檢測(cè)潛在核心微簇.

如果存在不確定度p.w<βμ，刪除這個(gè)微簇.

Step2.檢測(cè)離群微簇.

如果存在不確定度p.w<ξ，刪除這個(gè)微簇.

本文緩沖區(qū)的更新調(diào)整策略中，首先，針對(duì)新成長(zhǎng)的潛在核心微簇使用及時(shí)更新替換的方式;其次，針對(duì)存在不確定度過低的微簇，每隔Tp時(shí)間隔間進(jìn)行檢查.由于微簇模型穩(wěn)定，演化率低時(shí)新成長(zhǎng)的潛在核心微簇較少，此時(shí)及時(shí)更新替換的方式消耗資源很少;演化率高時(shí)新成長(zhǎng)的潛在核心微簇較多，及時(shí)更新替換使后續(xù)相應(yīng)的數(shù)據(jù)對(duì)象僅需在一個(gè)緩沖區(qū)進(jìn)行匹配，減少計(jì)算量.而存在不確定度過低的情況不需要實(shí)時(shí)檢查，周期檢查已經(jīng)可以達(dá)到相同的檢查效果.

3.3 離線宏聚類算法

在離線聚類的過程中，收到聚類請(qǐng)求后，進(jìn)行離線宏聚類.離線宏聚類使用潛在核心微簇緩沖區(qū)中的數(shù)據(jù)，根據(jù)密度可達(dá)定義進(jìn)行宏聚類得到最終的聚類結(jié)果，這種方式可以在提前將離群點(diǎn)檢測(cè)剔除的基礎(chǔ)上處理任意形狀的微簇.

宏聚類算法

Step1.取出一個(gè)未被處理的潛在核心微簇p，直到取完

Step2.如果p是核心微簇(p.w>μ)，標(biāo)記為已處理微簇，將與p直接密度可達(dá)的微簇加入到待處理adjacentPoints列中，以潛在核心微簇p創(chuàng)建簇C.否則，轉(zhuǎn)回Step 1.

Step3.adjacentPoints列非空時(shí)，從adjacentPoints列取出一個(gè)潛在核心微簇p，否則，轉(zhuǎn)回Step 1.

Step4.如果p是核心微簇(p.w>μ)，標(biāo)記p的歸屬簇為C，標(biāo)記p為已處理微簇.將與p直接密度可達(dá)的微簇加入到待處理adjacentPoints列中，從adjacentPoints列移除p，轉(zhuǎn)Step 3.否則，轉(zhuǎn)Step 5.

Step5.標(biāo)記p的歸屬簇為C，標(biāo)記p為已處理微簇.從adjacentPoints列移除p，轉(zhuǎn)Step 3.

4 實(shí)驗(yàn)與分析

4.1 計(jì)算復(fù)雜度分析

UCNStream算法主要包括初始化、在線微簇維護(hù)算法和離線宏聚類算法三個(gè)部分.下面分別計(jì)算這三個(gè)部分的計(jì)算復(fù)雜度并由此進(jìn)一步得到算法的整體計(jì)算復(fù)雜度.

1)初始化部分的計(jì)算復(fù)雜度分析.

設(shè)初始化階段使用的數(shù)據(jù)量大小為常量m0.使用密度峰值算法，通過計(jì)算位置不確定數(shù)據(jù)對(duì)象兩兩之間的距離并與取值較小的截?cái)嗑嚯x比較，獲取數(shù)據(jù)對(duì)象的局部密度、到其他微簇中心的最短距離，進(jìn)而根據(jù)密度峰值單遍掃描初始化數(shù)據(jù)集得到初步的聚類結(jié)果.密度峰值算法本身的計(jì)算復(fù)雜度為O(m02).

緊接著計(jì)算簇間最小距離，初始化微簇半徑ε，然后以ε作為參數(shù)重新聚類，根據(jù)聚類結(jié)果獲取局部密度參數(shù)和初始的潛在核心微簇，計(jì)算復(fù)雜度分別為O(m0)和O(m02).

因此，初始化部分整體的計(jì)算復(fù)雜度為O(m02).

2)在線微簇維護(hù)部分的計(jì)算復(fù)雜度分析.

設(shè)數(shù)據(jù)流到達(dá)的數(shù)據(jù)量大小為n，微簇?cái)?shù)量總和|C|，其中n隨時(shí)間不斷增長(zhǎng)，|C|存在上限，且該上限是不隨數(shù)據(jù)對(duì)象數(shù)量變化的常量.在線微簇維護(hù)過程中，包含數(shù)據(jù)對(duì)象的分配問題和間隔時(shí)間Tp執(zhí)行微簇刪除機(jī)制兩部分.

對(duì)于數(shù)據(jù)對(duì)象的分配問題，設(shè)數(shù)據(jù)對(duì)象和已有微簇之間的距離關(guān)系計(jì)算判斷數(shù)據(jù)對(duì)象如何分配所花費(fèi)時(shí)間為某個(gè)常數(shù)因子c1,則有T1(n)≤|C|*n*c1=O(n).

Tonline(n)=T1(n)+T2(n)，因此在線微簇維護(hù)部分的計(jì)算復(fù)雜度為O(n).

3)離線宏聚類部分的計(jì)算復(fù)雜度分析.

離線宏聚類對(duì)潛在核心微簇進(jìn)行聚類分析，潛在核心微簇的數(shù)量不超過常量|C|，算法需要掃描所有未處理的微簇和其直接密度可達(dá)的微簇，因此計(jì)算復(fù)雜度為O(|C|2).

4)算法整體計(jì)算復(fù)雜度分析.

算法整體的計(jì)算復(fù)雜度由上述三個(gè)部分組成，由于初始化部分的計(jì)算復(fù)雜度為O(m02)，在線微簇維護(hù)部分的計(jì)算復(fù)雜度為O(n)，離線宏聚類部分的計(jì)算復(fù)雜度為O(|C|2)，其中m0和|C|是給定常量，因此算法的整體計(jì)算復(fù)雜度為O(n)，呈現(xiàn)線性復(fù)雜度，符合數(shù)據(jù)流聚類算法在無限增長(zhǎng)的數(shù)據(jù)規(guī)模下聚類效率的要求.

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

本實(shí)驗(yàn)所用的計(jì)算機(jī)內(nèi)存8GB DDR3，固態(tài)硬盤256GB，CPU為2.7 GHz Intel Core i5，操作系統(tǒng)采用MACOS Mojave.開發(fā)環(huán)境為IntelliJ IDEA ULTIMATE2017，編程語言選擇JAVA.

4.3 數(shù)據(jù)集和參數(shù)設(shè)置

本實(shí)驗(yàn)采用數(shù)據(jù)流算法最為通用的兩個(gè)真實(shí)數(shù)據(jù)集:KDD CUP′99和Forest Coverage進(jìn)行實(shí)驗(yàn).KDD CUP′99是一個(gè)網(wǎng)絡(luò)入侵檢測(cè)數(shù)據(jù)集，數(shù)據(jù)模型的動(dòng)態(tài)演化比較明顯，數(shù)據(jù)集包含近500萬條傳輸控制協(xié)議(TCP)連接記錄，每條記錄對(duì)應(yīng)著一次正常連接或者22種網(wǎng)絡(luò)攻擊之一，同時(shí)每條TCP連接記錄中一共包括42個(gè)有效屬性，從中選擇34個(gè)連續(xù)屬性構(gòu)成實(shí)驗(yàn)數(shù)據(jù);Forest Coverage數(shù)據(jù)集一共包含581012條記錄，每條記錄有54個(gè)數(shù)值構(gòu)成的12個(gè)屬性值，對(duì)應(yīng)7個(gè)類，我們從中抽取10個(gè)數(shù)值型屬性作為聚類實(shí)驗(yàn)使用，以記錄的自然順序作為數(shù)據(jù)流的輸入順序.

數(shù)據(jù)的不確定化處理方式為:對(duì)數(shù)據(jù)的每一個(gè)屬性生成random[1,q]個(gè)對(duì)應(yīng)的子屬性值，每個(gè)子屬性值的取值為原先屬性值基礎(chǔ)上加入N(0,ηδ2)的高斯白噪聲.

為了更好地進(jìn)行實(shí)驗(yàn)分析，將UCNStream算法的聚類結(jié)果與UMicro算法和UIDMirco算法的聚類結(jié)果進(jìn)行比較.由于UMicro算法和UIDMirco算法不是針對(duì)位置不確定數(shù)據(jù)設(shè)計(jì)的不確定數(shù)據(jù)流算法，特將位置不確定數(shù)據(jù)映射成為以上兩種算法中不確定數(shù)據(jù)的表達(dá)形式：對(duì)于UMicro算法，求取位置不確定數(shù)據(jù)對(duì)象每個(gè)維度的均值和標(biāo)準(zhǔn)差，不確定數(shù)據(jù)以均值向量和標(biāo)準(zhǔn)差向量記錄，不確定數(shù)據(jù)點(diǎn)之間的距離不考慮空間位置關(guān)系;對(duì)于UIDMirco算法，求取位置不確定數(shù)據(jù)對(duì)象在每個(gè)維度的取值范圍，不確定數(shù)據(jù)用區(qū)間數(shù)表示，不確定數(shù)據(jù)點(diǎn)之間的距離由區(qū)間數(shù)之間最小距離和最大距離決定.

為了避免參數(shù)選擇的盲目性，實(shí)驗(yàn)中的相關(guān)參數(shù)設(shè)置參考文獻(xiàn)[10]和文獻(xiàn)[13]，并結(jié)合UCNStream算法的計(jì)算結(jié)果，進(jìn)行如下設(shè)置:數(shù)據(jù)流流速v=1000，噪聲因子η=1，對(duì)于UCNStream算法其他參數(shù)的取值情況分別為衰減系數(shù)λ=0.25，微簇緩沖區(qū)大小nc=200，no=20;對(duì)于UMicro算法其他參數(shù)設(shè)置分別為收納半徑閾值τ=3，權(quán)重比閾值0.02，微簇窗口大小nmicro=200;對(duì)于UIDMirco算法其他參數(shù)設(shè)置分別為收納半徑閾值τ=3，包含因子κ=1，當(dāng)前微簇窗口大小nmicro=200，候選微簇窗口大小為20，微簇最小密度閾值Th=4.

在對(duì)屬性位置不確定數(shù)據(jù)流聚類結(jié)果評(píng)估時(shí)，由于實(shí)驗(yàn)中使用的所有數(shù)據(jù)集都知道真正的類標(biāo)簽，因此通過外部評(píng)價(jià)指標(biāo)聚類的純度(purity)來評(píng)估聚類的質(zhì)量.聚類的純度定義為：

(16)

4.4 聚類質(zhì)量分析

使用聚類的純度purity作為聚類質(zhì)量的評(píng)價(jià)指標(biāo)，聚類的純度越高，聚類質(zhì)量越好.實(shí)驗(yàn)對(duì)UMicro、UIDMicro和UCNStream算法在不同數(shù)據(jù)規(guī)模下產(chǎn)生的處理時(shí)間進(jìn)行對(duì)比，KDD CUP′99數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果如圖1所示，F(xiàn)orest Coverage數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果如圖2所示.

圖1 KDD CUP′99數(shù)據(jù)集不同數(shù)據(jù)規(guī)模下算法聚類純度比較Fig.1 Purity for different clustering algorithms with different KDD CUP′99 data size

由上述結(jié)果可知，在對(duì)位置不確定數(shù)據(jù)集進(jìn)行聚類時(shí)，相對(duì)于UMicro算法和UIDMicro算法，UCNStream算法有較高的聚類純度.在解決位置不確定數(shù)據(jù)流的聚類問題上具有優(yōu)勢(shì).

圖2 Forest Coverage數(shù)據(jù)集不同數(shù)據(jù)規(guī)模下算法聚類純度比較Fig.2 Purity for different clustering algorithms with different Forest Coverage data size

4.5 參數(shù)對(duì)聚類質(zhì)量的影響

4.5.1 衰減系數(shù)λ對(duì)實(shí)驗(yàn)結(jié)果的影響

衰減系數(shù)λ決定歷史信息對(duì)當(dāng)前聚類的影響程度，實(shí)驗(yàn)在真實(shí)數(shù)據(jù)集的基礎(chǔ)上使用不同的衰減系數(shù)λ產(chǎn)生不確定數(shù)據(jù)進(jìn)行聚類.實(shí)驗(yàn)得到的聚類純度隨衰減系數(shù)變化曲線如圖3所示.

圖3 聚類純度隨時(shí)間衰減系數(shù)λ變化曲線Fig.3 Purity versus decay factor λ

由圖3可知，時(shí)間衰減系數(shù)對(duì)于兩個(gè)數(shù)據(jù)集有不同的影響，對(duì)于網(wǎng)絡(luò)入侵檢測(cè)數(shù)據(jù)集在衰減系數(shù)大于0.75后，聚類純度接近1，這是因?yàn)榫W(wǎng)絡(luò)入侵檢測(cè)數(shù)據(jù)集中大量的網(wǎng)絡(luò)攻擊連接在一定時(shí)間段連續(xù)進(jìn)行，而后又呈現(xiàn)大量連續(xù)的正常連接數(shù)據(jù)，減小歷史數(shù)據(jù)對(duì)當(dāng)前聚類結(jié)果的影響能得到更好的聚類效果.而Forest Coverage數(shù)據(jù)集中，時(shí)間衰減系數(shù)增大沒有使聚類的純度提升.因此，對(duì)于KDD CUP′99數(shù)據(jù)集，衰減系數(shù)取值在0.25以上較為合適，對(duì)于Forest Coverage數(shù)據(jù)集衰減系數(shù)在0.5以內(nèi)有較好的聚類效果.綜合考慮，本文衰減系數(shù)取值為0.25.衰減系數(shù)的值要根據(jù)實(shí)際情況進(jìn)行設(shè)定.

4.5.2 噪聲因子η對(duì)實(shí)驗(yàn)結(jié)果的影響

噪聲因子η決定數(shù)據(jù)不確定性的程度，實(shí)驗(yàn)在真實(shí)數(shù)據(jù)集的基礎(chǔ)上使用不同的噪聲因子產(chǎn)生不確定數(shù)據(jù)進(jìn)行聚類.實(shí)驗(yàn)得到的聚類純度隨噪聲因子變化曲線如圖4所示.

圖4 聚類純度隨噪聲因子η變化曲線Fig.4 Purity versus noise factor η

由圖4可知，聚類純度隨噪聲因子η的增大呈逐漸降低的趨勢(shì).這是因?yàn)殡S著噪聲因子η的增大，數(shù)據(jù)的不確定性程度變大，使得簇間相似度降低，因此，聚類純度降低.噪聲因子大于1時(shí)，對(duì)聚類純度產(chǎn)生明顯的影響.

5 總 結(jié)

針對(duì)位置不確定數(shù)據(jù)無法用現(xiàn)有的ALU模型描述，將位置不確定數(shù)據(jù)處理為普通的屬性級(jí)不確定數(shù)據(jù)時(shí)數(shù)據(jù)對(duì)象的位置關(guān)系不能良好體現(xiàn)的問題，本文提出一種聯(lián)系數(shù)表達(dá)的不確定數(shù)據(jù)流聚類算法UCNStream.通過實(shí)驗(yàn)展示和結(jié)果分析，該算法具有線性的計(jì)算復(fù)雜度，性能良好;充分利用位置不確定數(shù)據(jù)的特點(diǎn)，聚類精度高;實(shí)驗(yàn)中使用了數(shù)據(jù)集中數(shù)值屬性的部分，因此下一步的工作是分析分類屬性和混合屬性中位置不確定數(shù)據(jù)流的聚類問題.