一種中心權(quán)值流數(shù)據(jù)聚類(lèi)算法*

華 崢，杜 韜，曲守寧

（1.山東開(kāi)放大學(xué)，山東 濟(jì)南，250014；2.濟(jì)南大學(xué)，山東 濟(jì)南，250022）

0 引言

近年來(lái)，數(shù)據(jù)流挖掘在網(wǎng)絡(luò)監(jiān)測(cè)、交通流量監(jiān)控與管理、電力供應(yīng)管理與預(yù)測(cè)、Web 點(diǎn)擊流分析等領(lǐng)域有著巨大的應(yīng)用前景[1]。與傳統(tǒng)靜態(tài)數(shù)據(jù)集不同，數(shù)據(jù)流的聚類(lèi)分析提出了許多新的挑戰(zhàn)：關(guān)于自然簇的數(shù)量和形狀的先驗(yàn)知識(shí)難以獲取；要求算法具有高度的靈活性，可以實(shí)時(shí)捕獲任何形狀的聚類(lèi)；數(shù)據(jù)貢獻(xiàn)可能會(huì)隨時(shí)間不斷變化，并且變化越早，對(duì)集群的貢獻(xiàn)就越大[2]。

本文提出一種新的數(shù)據(jù)流聚類(lèi)方法中心加權(quán)數(shù)據(jù)流聚類(lèi)算法（Center-Weighted algorithm for clustering data Streams，CW-Stream）。該方法通過(guò)綜合考慮量自動(dòng)確定聚類(lèi)中心，并且為了提供一個(gè)更好的聚類(lèi)表征，通過(guò)中心權(quán)值的迭代學(xué)習(xí)過(guò)程，為聚類(lèi)中心分配權(quán)重。此外，為把握數(shù)據(jù)對(duì)象的完整狀態(tài)，本文方法以模糊隸屬度矩陣的形式保存數(shù)據(jù)對(duì)象的摘要信息，且中心權(quán)值的加入為模糊隸屬度帶來(lái)了方向性的特征。通過(guò)一系列在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)表明，CW-Stream 算法在聚類(lèi)的純度和效率等方面展現(xiàn)了良好的性能[3]。

1 聚類(lèi)算法

CW-Stream 算法為了把握數(shù)據(jù)流的瞬態(tài)特征，將中心權(quán)重與距離特征相結(jié)合，以完成對(duì)數(shù)據(jù)流環(huán)境的準(zhǔn)確描述，然后以模糊隸屬度矩陣的形式保存數(shù)據(jù)流的摘要信息。算法不斷重復(fù)上述迭代過(guò)程，直到數(shù)據(jù)流結(jié)束或者所有的數(shù)據(jù)點(diǎn)被全部遍歷為止。

1.1 中心加權(quán)系數(shù)

在算法的具體執(zhí)行過(guò)程中，一般關(guān)心的是當(dāng)前數(shù)據(jù)的聚類(lèi)情況，但如果對(duì)當(dāng)前數(shù)據(jù)流的信息不敏感，算法挖掘性能和挖掘結(jié)果的精度將大大降低[4]。為了避免歷史數(shù)據(jù)對(duì)更新數(shù)據(jù)造成較大的影響，本文算法創(chuàng)新性地提出了微簇中心權(quán)值的計(jì)算方法。微簇中心能夠表示數(shù)據(jù)流的聚類(lèi)形態(tài)，但由于歷史數(shù)據(jù)過(guò)多容易陷入局部最優(yōu)現(xiàn)象。歷史數(shù)據(jù)與當(dāng)前數(shù)據(jù)的數(shù)據(jù)特征相互補(bǔ)充，將過(guò)去時(shí)刻數(shù)據(jù)流隨時(shí)間延續(xù)的演化信息和新數(shù)據(jù)流融合起來(lái)，從而得到具有中心權(quán)值的最優(yōu)解[5]。

假設(shè)A={A1,A2,…,Ak}是一個(gè)有界的、全部有序的集合，相應(yīng)地，A=A1×A2×…×Ak}是一個(gè)k維數(shù)據(jù)空間。其中，xi=〈xi1,xi2,…,xik〉表示1 個(gè)數(shù)據(jù)點(diǎn)；xij表示數(shù)據(jù)點(diǎn)xi的第j維的值。C為整數(shù)，V=(v1,v2,…,vc)為C個(gè)聚類(lèi)中心[6]。

如果是第1 次聚類(lèi)請(qǐng)求，數(shù)據(jù)點(diǎn)xj(1)被劃分到C個(gè)聚類(lèi)中心vi(1)，更新后的聚類(lèi)中心的權(quán)值pi(1)即為第一個(gè)數(shù)據(jù)流中數(shù)據(jù)的權(quán)值和初始化聚類(lèi)中心權(quán)值之和，表示為：

式中：uij為數(shù)據(jù)點(diǎn)xj(1)，屬于聚類(lèi)中心vi(1)的模糊隸屬度；1 ≤i≤C；1 ≤j≤n。

之后，當(dāng)?shù)? 個(gè)數(shù)據(jù)流到達(dá)時(shí)，更新后的聚類(lèi)中心權(quán)值為第2 個(gè)數(shù)據(jù)流的數(shù)據(jù)項(xiàng)的權(quán)值和更新后的聚類(lèi)中心權(quán)值之和。因此，C個(gè)新的聚類(lèi)中心vi(2)的權(quán)值pi(2)表示為：

式中：qj(2)=1；pi(1)為聚類(lèi)中心vi(1)的權(quán)值；uij為數(shù)據(jù)點(diǎn)xj(2)屬于新的聚類(lèi)中心vi(2)的模糊隸屬度；uii為歷史聚類(lèi)中心vi(1)的模糊隸屬度。

同理，當(dāng)?shù)趖 個(gè)數(shù)據(jù)流到達(dá)時(shí)，算法將新到達(dá)的數(shù)據(jù)點(diǎn)xj(t)和前一時(shí)刻所得到的C個(gè)新的加權(quán)聚類(lèi)中心vi(t-1)，劃分成C個(gè)新的數(shù)據(jù)簇。由此可得，加權(quán)聚類(lèi)中心vi(t)的權(quán)值pi(t)可以表示為：

式中：qj(t)=1；pi(t-1)為聚類(lèi)中心vi(1)在(t-1)時(shí)刻的權(quán)值；uij為數(shù)據(jù)點(diǎn)xj(t)屬于新的聚類(lèi)中心vi(t)的模糊隸屬度；uii為歷史數(shù)據(jù)中心vi(t-1)的模糊隸屬度。

由此可見(jiàn)，后續(xù)更新的中心權(quán)值包含了前一次數(shù)據(jù)更新得到的中心權(quán)值和新增數(shù)據(jù)對(duì)象信息，然后通過(guò)不斷迭代將數(shù)據(jù)流隨著時(shí)間不斷演化的信息融合進(jìn)去。

1.2 基于中心權(quán)值的數(shù)據(jù)流微簇

為了減少歷史數(shù)據(jù)對(duì)最新數(shù)據(jù)的影響，將前一部分中的數(shù)據(jù)對(duì)象的權(quán)值在更新微簇中心點(diǎn)之前進(jìn)行衰減[7]。考慮到不同局部區(qū)域密度的歷史狀態(tài)，引入時(shí)態(tài)權(quán)重的概念，從而能夠識(shí)別各個(gè)局部密度隨時(shí)間的變化情況[8]。

設(shè)模糊隸屬度矩陣U是一個(gè)c×n的矩陣，其中c是需要聚類(lèi)的簇個(gè)數(shù)，n代表數(shù)據(jù)點(diǎn)的個(gè)數(shù)。uij表示第j個(gè)數(shù)據(jù)點(diǎn)xj屬于第i個(gè)聚類(lèi)中心vi的模糊隸屬度。對(duì)于每個(gè)數(shù)據(jù)點(diǎn)xj和簇Ci，都有0 ≤uij≤1。對(duì)于每個(gè)數(shù)據(jù)點(diǎn)xj，都有定義目標(biāo)函數(shù)為[9]：

通過(guò)Lagrange 乘子法得到的模糊隸屬度矩陣的定義為[10]：

其中，加權(quán)指數(shù)m(m≥1)控制隸屬度的影響，m的值越大，隸屬度的影響越大。而目標(biāo)函數(shù)J的值越小，表明聚類(lèi)質(zhì)量越好[11]。

每一個(gè)數(shù)據(jù)點(diǎn)xj(t)都賦予了1 個(gè)隨時(shí)間衰減的權(quán)值，以及前一時(shí)刻得到的C個(gè)加權(quán)聚類(lèi)中心vi(t-1)，加權(quán)聚類(lèi)中心vi(t-1)在(t-1)時(shí)刻的權(quán)值為pi(t-1)；由此可以得到t時(shí)刻算法的聚類(lèi)中心vi的迭代為：

可以看出在調(diào)節(jié)聚類(lèi)中心時(shí)，各個(gè)集群內(nèi)部的數(shù)據(jù)點(diǎn)之間盡量分布密集，不同的集群之間的分布盡量地遠(yuǎn)離。

1.3 算法的細(xì)節(jié)實(shí)現(xiàn)及初始化過(guò)程

數(shù)據(jù)點(diǎn)Xj的綜合考慮量γj的計(jì)算方法為：

式（7）中，局部密度ρj的定義為[12]：

χ(dij-dc)函數(shù)用以判斷xj距離xi是否小于距離閾值dc，表達(dá)式為：

數(shù)據(jù)點(diǎn)Xj到比它局部密度高的其它數(shù)據(jù)點(diǎn)的最小距離為：

算法使得所選的初始化聚類(lèi)中心盡可能地相互分離，聚類(lèi)中心位于不同類(lèi)簇，由此保證初始聚類(lèi)中心的多樣性[13]。

基于上述的描述，基于中心權(quán)值的聚類(lèi)算法的具體流程如下文所述。

輸入：數(shù)據(jù)流X=〈x1,x2,…,xn〉?RD

輸出：聚類(lèi)中心V={vj,1 ≤i≤C}和模糊隸屬度矩陣U={uij,1 ≤i≤C,1 ≤j≤D}。

2 實(shí)驗(yàn)分析

為了驗(yàn)證本文CW-Stream 算法的性能，使用兩種廣泛使用的真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)：KDD-CUP99數(shù)據(jù)集、Forest CoverType 數(shù)據(jù)集。

2.1 聚類(lèi)質(zhì)量評(píng)價(jià)

實(shí)驗(yàn)對(duì)CW-Stream 算法的聚類(lèi)效果進(jìn)行評(píng)估，同時(shí)與HPStream 算法和CAStream 算法進(jìn)行性能比較。本文采用平均聚類(lèi)純度來(lái)評(píng)價(jià)聚類(lèi)質(zhì)量，平均聚類(lèi)純度的定義如公式（11）所示[14]：

式中：K為簇的個(gè)數(shù)；為在微簇Ci中具有該微簇最主要類(lèi)標(biāo)號(hào)的數(shù)據(jù)點(diǎn)數(shù)；|Ci|為簇i中包含的所有數(shù)據(jù)點(diǎn)的個(gè)數(shù)。

實(shí)驗(yàn)中均經(jīng)過(guò)5 個(gè)單位時(shí)間，對(duì)每個(gè)單位時(shí)間內(nèi)新進(jìn)入的數(shù)據(jù)進(jìn)行聚類(lèi)，設(shè)置加權(quán)指數(shù)d=1.05。具體實(shí)驗(yàn)結(jié)果如表1 所示。

表1 聚類(lèi)質(zhì)量評(píng)價(jià)

從實(shí)驗(yàn)結(jié)果可以看出，CW-Stream 算法采用了前一時(shí)刻聚類(lèi)中心的權(quán)值來(lái)重新計(jì)算中心點(diǎn)的權(quán)值，減少了歷史數(shù)據(jù)對(duì)當(dāng)前數(shù)據(jù)的影響。HPStream 算法使用高維投影技術(shù)和衰減結(jié)構(gòu)來(lái)處理高維數(shù)據(jù)流，對(duì)高維數(shù)據(jù)流確實(shí)具有很好的健壯性。CAStream 算法采用子空間聚類(lèi)思想，對(duì)數(shù)據(jù)空間進(jìn)行了網(wǎng)格化處理，能夠有效地處理高維數(shù)據(jù)流。

2.2 Rand 指數(shù)

為了公正地對(duì)各個(gè)聚類(lèi)算法的性能做出合理評(píng)價(jià)，采用芮氏指標(biāo)（Rand Index，RI）對(duì)數(shù)據(jù)集進(jìn)行聚類(lèi)劃分和數(shù)據(jù)集實(shí)際劃分結(jié)果的一致性[15]，計(jì)算公式為：

式中：N為整個(gè)數(shù)據(jù)集中數(shù)據(jù)點(diǎn)的總個(gè)數(shù)。

本文算法的參數(shù)設(shè)置為d=1.05，λ=0.125，n=1 980，c=8。對(duì)于每個(gè)數(shù)據(jù)集，在實(shí)驗(yàn)中驗(yàn)證每種算法獨(dú)立運(yùn)行10 次，實(shí)驗(yàn)結(jié)果如表2 所示。

表2 Rand 指數(shù)比較

從表2 可以看出，相比HPStream 算法，CWStream 算法中加入了中心權(quán)值，充分考慮了數(shù)據(jù)流不斷演化的特點(diǎn)。HPStream 算法中需要用戶(hù)來(lái)指定平均聚類(lèi)維度，強(qiáng)行要求輸入固定的聚類(lèi)維數(shù)必然影響真實(shí)的聚類(lèi)形態(tài)分布。CAStream 算法在子空間中進(jìn)行數(shù)據(jù)流聚類(lèi)及其演化分析，對(duì)任意形狀分布的聚類(lèi)效果較好。

3 結(jié)語(yǔ)

數(shù)據(jù)流作為一種特殊的數(shù)據(jù)模型廣泛存在于多種應(yīng)用領(lǐng)域中，對(duì)數(shù)據(jù)流聚類(lèi)算法提出了挑戰(zhàn)。如難以自動(dòng)獲取簇的個(gè)數(shù)；難以發(fā)現(xiàn)任意形狀的簇等。因此，基于流式數(shù)據(jù)的有效處理和分析具有十分重要的意義。CW-Stream 算法劃分流式數(shù)據(jù)并進(jìn)行初始化處理，得到初始聚類(lèi)中心和微簇。引入中心權(quán)值，迭代更新數(shù)據(jù)流，同時(shí)考慮到模糊隸屬度矩陣的更新方向。實(shí)驗(yàn)表明，算法的精度滿(mǎn)足了數(shù)據(jù)流挖掘的要求。

在未來(lái)的工作中，將研究劃分?jǐn)?shù)據(jù)流的大小對(duì)最終聚類(lèi)結(jié)果的影響，改進(jìn)微簇結(jié)構(gòu)，進(jìn)一步提高聚類(lèi)質(zhì)量。此外，進(jìn)一步展開(kāi)相關(guān)方面的理論和實(shí)驗(yàn)說(shuō)明，從而更好地在實(shí)際問(wèn)題中展開(kāi)應(yīng)用。