一種聯系數表達的位置不確定數據流聚類算法

史玲娟，黃德才

(浙江工業大學 計算機科學與技術學院，杭州 310023)

1 引 言

隨著信息技術的快速發展，數據流模型在互聯網數據傳輸、大型零售業銷售信息、無線傳感器網絡[1,2]等眾多領域中得到應用，并產生了大量不確定數據流.數據的不確定性主要由測量儀器誤差、外部干擾、數據丟失、數據集成等內在和外在因素造成數據不可靠、隨機、模糊、不完整等特性.

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

不確定數據流聚類算法是一個重要的研究課題，在學術界引起了眾多研究者的關注.最近有大量的數據流聚類研究項目，這些研究項目產生了許多成功的算法[4].

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

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

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

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

2 相關定義

本部分對本文所提出的算法中所用到的一些概念進行定義.

2.1 聯系數相關定義

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

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

u=a+bi

(1)

其中a稱為確定性聯系分量，b稱為不確定性聯系分量，a為實數，b為非負實數，(a,b)統稱為聯系數u的聯系分量，i∈[-1,1].

稱形如式(2)的數為三元聯系數，三元聯系數是聯系數的一般表達形式.

u=a+bi+cj

(2)

其中a稱為同聯系分量，b稱為異聯系分量，c稱為反聯系分量，a，b，c均為非負實數，i表示相異關系，j表示相反關系.

二元聯系數u=a+bi可以看作是當a+b+c=n(n為已知常數)且a，b，c均為非負實數時u=a+bi+cj的等價表達.

定義2.二元聯系數的四則運算[18].

1)二元聯系數加法運算

設u1=a1+b1i，u2=a2+b2i是兩個二元聯系數，則:

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

(3)

因為a1，a2是實數，所以(a1+a2)是實數.又因為b1，b2是非負數，所以(b1+b2)是非負數.因此，二元聯系數相加的結果依然是一個二元聯系數.

2)二元聯系數減法運算

設u1=a1+b1i，u2=a2+b2i是兩個二元聯系數，則:

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

(4)

易證，二元聯系數相減的結果依然是一個二元聯系數.

3)二元聯系數乘法運算

設u1=a1+b1i，u2=a2+b2i是兩個二元聯系數，則:

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

(5)

易證，二元聯系數相乘的結果依然是一個二元聯系數.

4)二元聯系數根式運算

設u=a+bi是一個二元聯系數且a非負，則:

(6)

易證，二元聯系數相乘的結果依然是一個二元聯系數.

定義3.聯系數的態勢[21].

態勢是指聯系數中各聯系份量大小關系所確定的系統狀態和趨勢.不同聯系數中聯系分量的大小關系規律可以用聯系數的態勢函數來描述.

1)二元聯系數的態勢

表1 u=a+bi的態勢函數表
Table 1 Situation function table of u=a+bi

聯系分量的大小關系態勢態勢函數shi(u)=aba>b同勢>1a=b均勢=1a

2)三元聯系數的態勢

若聯系數的態勢大于1，即a>c，則屬于同勢，同勢的情況下，b的值越小，同勢的等級越高.

若聯系數的態勢等于1，即a=c，則屬于均勢，均勢的情況下，b的值越小，均勢的等級越高.

若聯系數的態勢小于1，即a

如果用三元聯系數表示距離，那么同勢的情況表示距離傾向于更大的方向，且同勢時相同態勢值的聯系數，同勢等級越高，宏觀上距離越大;同理，反勢的情況表示距離傾向于更小的方向，且反勢時相同態勢值的聯系數，同勢等級越高，宏觀上距離越小;在均勢的情況下，表示距離傾向于中立，且均勢時相同態勢值的聯系數，均勢等級越高，宏觀上這種中立的傾向越大.

定義4.二元聯系數的偏聯系數[21].設u=a+bi是一個二元聯系數，則有:

偏同聯系數?+u：

(7)

偏反聯系數?-u：

(8)

全偏聯系數?u：

(9)

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

2.2 算法相關定義

定義7.不確定數據對象間的聯系距離.不確定數據對象X1,X2間的聯系距離表示為dis(X1,X2).

dis(X1,X2)=

(10)

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

(11)

由定義7可以得到結論1：

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

由定義8可以得到結論2：

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

(12)

微簇中心的不確定度同樣取一個標準差，定義為簇內各數據對象到微簇中心的期望距離平方和的均值的平方根.

(13)

定義11.不確定微簇半徑.微簇半徑由確定部分和不確定部分綜合得出.半徑取簇內各數據對象到微簇中心的平均距離.根據聯系數的運算法則，確定部分的值為R1，不確定部分的值為R2.

(14)

(15)

不確定數據對象與不確定微簇集合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).因此，距離聯系數可以擴展為a+b+c=maxset(c),p的三元聯系數.

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

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

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

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

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

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

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

3 UCNStream算法

UCNStream算法主要包括初始化、在線微簇維護算法和離線宏聚類算法三個部分.初始化階段利用初始的小規模數據集調整參數;在線部分利用不確定數據本身的特點構建和維護不確定微簇;離線階段進行基于密度的不確定數據宏聚類.算法主要步驟如下:

Step1.利用初始數據集，調整算法參數.

Step2.調用在線微簇維護算法，動態調整微簇的數量和微簇聚類特征.

Step3.提交聚類請求，進行宏聚類算法.

3.1 初始化算法

基于密度的聚類算法中，密度半徑ε和密度閾值μ是兩個非常重要的參數，通過對初始樣本數據進行分析，將這兩個參數自適應地初始化，參數初始化的部分包含兩步:

Step1.由于中心是局部密度較大且距離其他中心較遠的點，同時滿足這兩個條件的點稱為密度峰值，選用一個較小的截斷距離，利用密度峰值算法對初識數據集進行聚類，得到合理的簇間最小聯系距離，利用公式(11)計算其對應的宏觀距離，初始化微簇半徑ε為這個宏觀距離的一半.

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

Step2.1.取出ListData中最前的一個數據點p，構建以點p為中心，半徑為ε的微簇，微簇含有數據點數量n=1.

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

Step2.3.獲取數據點p到最近一個微簇的距離d，如果d≥2*ε，構建以點p為中心的微簇.否則標記這個數據點為待處理，轉Step 2.2.

Step2.4.依次取出ListData中標記為待處理的數據點p，如果數據點p落在已有的微簇半徑范圍內中，該微簇的數據點數量n增加1.否則，構建以點p為中心的微簇.

Step2.5.計算微簇中包含數據的平均個數，作為μ的取值.并將微簇中含有數據點數量大于μ的微簇作為初始的潛在核心微簇.

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

3.2 在線微簇維護算法

在線微簇聚類算法采用雙緩沖區，即潛在核心微簇緩沖區(BUFc)和離群微簇緩沖區(BUFo)，BUFc中更新并保存潛在核心微簇的聚類特征;BUFo中更新并保存離群微簇的聚類特征，當一個離群微簇成長為潛在核心微簇時，將該微簇的聚類特征轉存到BUFc中.令nc表示潛在核心微簇緩沖區內可保存微簇的最大值，no表示離群微簇緩沖區內可保存微簇的最大值，noc表示內存中限定的微簇數量最大值.

在線微簇維護算法分成在線聚類和在線緩沖區更新調整兩個部分.在線聚類算法根據不斷到達的數據對象更新微簇的聚類特征，在線緩沖區更新調整算法則定時檢查微簇是否存在度過低，并刪除那些存在度太低的不確定微簇.

在線聚類算法

Step1.對于每個到來的數據對象p，嘗試把數據對象放入距離態勢最小的潛在核心微簇.如果加入p后，微簇的宏觀半徑小于閾值ε，則確認p的分配，更新微簇聚類特征，轉Step 1.否則，轉Step 2.

Step2.嘗試把數據對象p放入距離態勢最小的離群微簇.如果加入p后，微簇的宏觀半徑小于閾值ε，則確認p的分配，繼續Step 2的子操作.否則，轉Step 3.

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

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

Step2.3.將這個微簇從離群微簇緩沖區轉存到潛在核心微簇緩沖區.轉Step 1.

Step3.檢查離群微簇緩沖區是否已滿.

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

Step3.2.為數據對象p建立新的離群微簇.

由上述過程可知，算法優先考慮吸收新數據對象，然后考慮創建新微簇，這樣能夠避免本應屬于某個現有微簇的數據對象占用內存微簇存儲資源和在后續聚類中進行微簇合并的多余操作，避免現有微簇因存在不確定度降低過快而過早被刪除.從Step 2的子操作可發現，本文及時更新由離群微簇成長而來的潛在核心微簇進入BUFc、維護在線聚類模型，使數據對象盡可能被潛在核心微簇吸收.

根據結論2易知核心微簇密度μ與潛在核心微簇密度βμ之間應滿足μ的關系，β取值應不小于1-2-λ，本文采用向上取值保留1-2-λ小數點后一位，得到潛在核心微簇最小密度參數βμ.

間隔時間Tp進行微簇的存在度檢查并更新微簇，微簇刪除機制算法過程如下.

在線緩沖區更新調整算法

Step1.檢測潛在核心微簇.

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

Step2.檢測離群微簇.

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

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

3.3 離線宏聚類算法

在離線聚類的過程中，收到聚類請求后，進行離線宏聚類.離線宏聚類使用潛在核心微簇緩沖區中的數據，根據密度可達定義進行宏聚類得到最終的聚類結果，這種方式可以在提前將離群點檢測剔除的基礎上處理任意形狀的微簇.

宏聚類算法

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

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

Step3.adjacentPoints列非空時，從adjacentPoints列取出一個潛在核心微簇p，否則，轉回Step 1.

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

Step5.標記p的歸屬簇為C，標記p為已處理微簇.從adjacentPoints列移除p，轉Step 3.

4 實驗與分析

4.1 計算復雜度分析

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

1)初始化部分的計算復雜度分析.

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

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

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

2)在線微簇維護部分的計算復雜度分析.

設數據流到達的數據量大小為n，微簇數量總和|C|，其中n隨時間不斷增長，|C|存在上限，且該上限是不隨數據對象數量變化的常量.在線微簇維護過程中，包含數據對象的分配問題和間隔時間Tp執行微簇刪除機制兩部分.

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

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

3)離線宏聚類部分的計算復雜度分析.

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

4)算法整體計算復雜度分析.

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

4.2 實驗環境

本實驗所用的計算機內存8GB DDR3，固態硬盤256GB，CPU為2.7 GHz Intel Core i5，操作系統采用MACOS Mojave.開發環境為IntelliJ IDEA ULTIMATE2017，編程語言選擇JAVA.

4.3 數據集和參數設置

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

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

為了更好地進行實驗分析，將UCNStream算法的聚類結果與UMicro算法和UIDMirco算法的聚類結果進行比較.由于UMicro算法和UIDMirco算法不是針對位置不確定數據設計的不確定數據流算法，特將位置不確定數據映射成為以上兩種算法中不確定數據的表達形式：對于UMicro算法，求取位置不確定數據對象每個維度的均值和標準差，不確定數據以均值向量和標準差向量記錄，不確定數據點之間的距離不考慮空間位置關系;對于UIDMirco算法，求取位置不確定數據對象在每個維度的取值范圍，不確定數據用區間數表示，不確定數據點之間的距離由區間數之間最小距離和最大距離決定.

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

在對屬性位置不確定數據流聚類結果評估時，由于實驗中使用的所有數據集都知道真正的類標簽，因此通過外部評價指標聚類的純度(purity)來評估聚類的質量.聚類的純度定義為：

(16)

4.4 聚類質量分析

使用聚類的純度purity作為聚類質量的評價指標，聚類的純度越高，聚類質量越好.實驗對UMicro、UIDMicro和UCNStream算法在不同數據規模下產生的處理時間進行對比，KDD CUP′99數據集上的實驗結果如圖1所示，Forest Coverage數據集上的實驗結果如圖2所示.

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

由上述結果可知，在對位置不確定數據集進行聚類時，相對于UMicro算法和UIDMicro算法，UCNStream算法有較高的聚類純度.在解決位置不確定數據流的聚類問題上具有優勢.

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

4.5 參數對聚類質量的影響

4.5.1 衰減系數λ對實驗結果的影響

衰減系數λ決定歷史信息對當前聚類的影響程度，實驗在真實數據集的基礎上使用不同的衰減系數λ產生不確定數據進行聚類.實驗得到的聚類純度隨衰減系數變化曲線如圖3所示.

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

由圖3可知，時間衰減系數對于兩個數據集有不同的影響，對于網絡入侵檢測數據集在衰減系數大于0.75后，聚類純度接近1，這是因為網絡入侵檢測數據集中大量的網絡攻擊連接在一定時間段連續進行，而后又呈現大量連續的正常連接數據，減小歷史數據對當前聚類結果的影響能得到更好的聚類效果.而Forest Coverage數據集中，時間衰減系數增大沒有使聚類的純度提升.因此，對于KDD CUP′99數據集，衰減系數取值在0.25以上較為合適，對于Forest Coverage數據集衰減系數在0.5以內有較好的聚類效果.綜合考慮，本文衰減系數取值為0.25.衰減系數的值要根據實際情況進行設定.

4.5.2 噪聲因子η對實驗結果的影響

噪聲因子η決定數據不確定性的程度，實驗在真實數據集的基礎上使用不同的噪聲因子產生不確定數據進行聚類.實驗得到的聚類純度隨噪聲因子變化曲線如圖4所示.

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

由圖4可知，聚類純度隨噪聲因子η的增大呈逐漸降低的趨勢.這是因為隨著噪聲因子η的增大，數據的不確定性程度變大，使得簇間相似度降低，因此，聚類純度降低.噪聲因子大于1時，對聚類純度產生明顯的影響.

5 總 結

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