基于交互基函數(shù)的數(shù)據(jù)流聚類算法研究

黃承寧,李 莉,姜麗莉,徐平平

(1.南京工業(yè)大學(xué)浦江學(xué)院,江蘇 南京 211222;2.東南大學(xué) 信息科學(xué)與工程學(xué)院,江蘇 南京 210096)

0 引 言

數(shù)據(jù)流是一種潛在的海量、連續(xù)、快速的數(shù)據(jù)信息序列,引起了數(shù)據(jù)挖掘領(lǐng)域的極大關(guān)注和研究熱潮[1]。在人類生活的各個(gè)方面都存在數(shù)據(jù)流,如網(wǎng)絡(luò)媒體傳輸?shù)谋O(jiān)測(cè)信息、煤礦傳感器傳輸?shù)男畔?、網(wǎng)站信息、金融和證券公司產(chǎn)生的經(jīng)濟(jì)信息、天氣預(yù)報(bào)信息等。由于這種形式的數(shù)據(jù)海量且實(shí)時(shí)更新,傳統(tǒng)的聚類方法無(wú)法對(duì)其進(jìn)行處理,因此迫切需要新的聚類方法[2]。目前,已經(jīng)有很多數(shù)據(jù)流聚類方法被提出,不過(guò)均根據(jù)傳統(tǒng)數(shù)據(jù)的聚類算法擴(kuò)展而來(lái),且均沒(méi)有考慮到特征之間的關(guān)系。

該文提出將交互基函數(shù)(IBFs)引入數(shù)據(jù)流聚類,結(jié)合模糊ART算法,考慮特征的自交互與交叉交互,以相對(duì)較低的計(jì)算成本生成靈活決策邊界來(lái)找到最優(yōu)聚簇,實(shí)現(xiàn)了聚類高精度與低錯(cuò)誤率,提高了算法的數(shù)據(jù)流聚類質(zhì)量。

1 數(shù)據(jù)流聚類與自適應(yīng)諧振理論

1.1 數(shù)據(jù)流聚類

數(shù)據(jù)流具有內(nèi)在的特性,包括無(wú)限大小、時(shí)間順序和動(dòng)態(tài)變化。與傳統(tǒng)的數(shù)據(jù)挖掘相比,數(shù)據(jù)流挖掘只是在滿足單次通過(guò)、實(shí)時(shí)響應(yīng)、有界內(nèi)存和概念漂移檢測(cè)等約束條件下產(chǎn)生近似結(jié)果。

數(shù)據(jù)流(DS)定義為數(shù)據(jù)對(duì)象或樣本序列或?yàn)橐粋€(gè)帶有時(shí)間戳(Time Stamp)的多維數(shù)據(jù)點(diǎn)集合：DS={x1,x2,…,xn},其中xn為第n個(gè)到達(dá)的數(shù)據(jù)對(duì)象(實(shí)際應(yīng)用中n的取值可以為無(wú)限大[3-4])。其中每個(gè)數(shù)據(jù)點(diǎn)是一個(gè)d維的數(shù)據(jù)記錄,其到達(dá)時(shí)間為ti。

數(shù)據(jù)流聚類將DS中的相似對(duì)象劃分為一個(gè)或多個(gè)組(稱為“簇”,Cluster),劃分后,同一簇中的元素彼此相似,但相異于其他簇中的元素。

針對(duì)高維、動(dòng)態(tài)、實(shí)時(shí)的特點(diǎn),目前不少研究者都已經(jīng)提出了許多有效的數(shù)據(jù)流聚類算法,但數(shù)據(jù)流信息是不確定的,總是存在離群點(diǎn)且包含噪聲[5],傳統(tǒng)的聚類方法無(wú)法對(duì)其進(jìn)行處理,因此發(fā)現(xiàn)新的數(shù)據(jù)流聚類方法越來(lái)越迫切。

目前從實(shí)際應(yīng)用看,數(shù)據(jù)流聚類基本都面臨著許多共性問(wèn)題[6-7]：(1)內(nèi)存有限：數(shù)據(jù)流中的數(shù)量往往是龐大的,不可能在內(nèi)存和硬盤中存儲(chǔ)整個(gè)數(shù)據(jù)流;(2)一次掃描：因?yàn)榫薮蟮臄?shù)據(jù)量,傳統(tǒng)的掃描方法不再適用,在對(duì)數(shù)據(jù)的訪問(wèn)只能單次線性,也就是只按順序依次讀取一次,不能進(jìn)行隨機(jī)訪問(wèn);(3)實(shí)時(shí)響應(yīng)：大多數(shù)應(yīng)用程序要求快速響應(yīng),因此挖掘應(yīng)該是一個(gè)連續(xù)的在線過(guò)程;(4)概念漂移：數(shù)據(jù)分布經(jīng)常隨時(shí)間變化。目前典型的數(shù)據(jù)流聚類算法包括REPSTREAM,ACSC,G-Stream,MR-Stream,CellTree以及RPGStream等[8]。

1.2 自適應(yīng)諧振理論

自適應(yīng)諧振理論(ART)[9]是一種學(xué)習(xí)模型,它模擬人腦捕獲,識(shí)別和記憶有關(guān)對(duì)象和事件的信息,既是一種認(rèn)知理論,也是一種關(guān)于大腦如何在不斷變化的世界中快速學(xué)會(huì)分類、識(shí)別和預(yù)測(cè)物體和事件的神經(jīng)理論。該文提出的算法便是在模糊自適應(yīng)諧振理論基礎(chǔ)上引入交互基函數(shù)(IBFs)[10]擴(kuò)展進(jìn)行數(shù)據(jù)流聚類,從而提升聚類精度與質(zhì)量。

模糊自適應(yīng)諧振理論的體系結(jié)構(gòu)由用于接收輸入模式的輸入層F1和用于聚類的類別層F2組成[11],如圖1所示,輸入層F1包含的輸入向量被提交到網(wǎng)絡(luò),與識(shí)別層F2中各個(gè)類簇的權(quán)值向量進(jìn)行相似度比較并歸類。

圖1 模糊ART結(jié)構(gòu)

模糊ART使用模糊算法并引入一個(gè)“補(bǔ)編碼”[12]來(lái)解決“類別擴(kuò)散”問(wèn)題。模糊ART執(zhí)行步驟如下：

(1)類別選擇：對(duì)于每個(gè)輸入模式I,模糊ART根據(jù)選擇函數(shù)為識(shí)別層F2中的每個(gè)聚簇計(jì)算一個(gè)選擇值,并標(biāo)識(shí)具有最大值的聚簇為獲勝聚簇,第j個(gè)簇的選擇函數(shù)定義為：

(1)

(2)模板匹配：使用匹配函數(shù)Mj*評(píng)估輸入模式I與獲勝聚簇Cj*之間的相似性,該函數(shù)定義為：

(2)

如果獲勝聚簇Cj*滿足警戒標(biāo)準(zhǔn)Mj*≥ρ,會(huì)發(fā)生諧振,從而導(dǎo)致步驟3的中心學(xué)習(xí)。否則,將在其余聚類中選擇新的獲勝聚簇。如果沒(méi)有獲勝聚簇滿足警戒標(biāo)準(zhǔn),則將生成一個(gè)新的聚簇來(lái)對(duì)輸入模式進(jìn)行編碼。

(3)中心學(xué)習(xí)：如果Cj*滿足警戒標(biāo)準(zhǔn),其對(duì)應(yīng)的權(quán)重向量Wj*將通過(guò)函數(shù)進(jìn)行更新,定義為：

(3)

模糊ART中基于警戒準(zhǔn)則計(jì)算的簇的VR是由特征空間中與簇關(guān)聯(lián)的區(qū)域幾何定義的,它從幾何上解釋了模糊ART的警戒準(zhǔn)則,認(rèn)為落入VR的輸入模式與相應(yīng)的簇相似,而VR的形狀和功能行為則取決于補(bǔ)編碼的使用[13]。

2 基于交互基函數(shù)的數(shù)據(jù)流聚類

2.1 交互基函數(shù)

如前所述,用于訓(xùn)練的特征構(gòu)成了問(wèn)題的基礎(chǔ)向量。例如,當(dāng)特征數(shù)量p=2時(shí),搜索空間是由特征的正交軸形成的平面,每個(gè)特征都是一個(gè)基向量。三個(gè)特征形成三維基礎(chǔ),以此類推。如果把一個(gè)特征看作一個(gè)基向量,基函數(shù)就是一個(gè)變換。在最簡(jiǎn)單的情況下,基函數(shù)可以是等式：

f(X)=X

(4)

多項(xiàng)式函數(shù)的一個(gè)特殊情況,即當(dāng)a=1：

f(X)=Xa

(5)

f(X)=(1-X)a

(6)

也可以定義其它基函數(shù),例如指數(shù)：

f(X)=(eX)a

(7)

回歸分析中常用的是基函數(shù),它們具有改變回歸平面性質(zhì)的作用。例如,從恒等式到變量的平方的轉(zhuǎn)換具有將回歸線變?yōu)閽佄锞€的效果。但DTs(決策樹)[14]中基函數(shù)的使用并沒(méi)有同樣的效果?？紤]K個(gè)實(shí)函數(shù)bi的一般情況：R→R,i=1,2,…,K,稱{f1,f2,…,fK}為一組基函數(shù)。然后利用基函數(shù)得到的T個(gè)新特征擴(kuò)充p個(gè)特征集：

X*=(X1,…,Xp,Xp+1,…,Xp+T)

(8)

并且X*∈RP+T,Xp+i=fsi(Xji),i=1,2,…,T,si∈{1,2,…,K},ji∈{1,2,…,p}。

由于基函數(shù)在原基中仍然產(chǎn)生正交劃分,筆者的建議是在構(gòu)造X*時(shí)使用兩個(gè)或多個(gè)特征之間的交互信息。這些交互不同于自交互,可以通過(guò)一組D函數(shù)來(lái)識(shí)別,這些M函數(shù)通過(guò)基函數(shù)來(lái)再現(xiàn)特征變換的功能交互,這些交互函數(shù)被定義為：

hhi：Rpk→Rh

(9)

(b1(X1),b1(X2),…,bk(Xp))

(10)

此設(shè)置下,定義：

X*=(X1,…,Xp,Xp+1,…,Xp+D)

(11)

Xp+i=hi(b1(X1),b1(X2),…,bk(Xp))
i=1,2,…,D

(12)

通過(guò)將標(biāo)準(zhǔn)遞歸劃分方法應(yīng)用X*上,并考慮到特征之間的相互作用,在X上的投影將提供一個(gè)斜劃分(最終也可能是非線性的)。

IBFs提供的框架不僅允許誘導(dǎo)出斜劃分,還允許誘導(dǎo)出非線性決策邊界[16-17]。這是通過(guò)在數(shù)據(jù)集中特征生成的子空間X=(X1,X2,…,Xp)中投影方程hi(b1(X1),b1(X2),…,bk(Xp))=a來(lái)完成的。

2.2 基于交互基函數(shù)的數(shù)據(jù)流聚類算法

基于交互基函數(shù)的特性,在實(shí)驗(yàn)中將IBFs引入模糊ART,提出IBFs_ART算法,用于對(duì)數(shù)據(jù)流進(jìn)行聚類。通過(guò)對(duì)原始輸入特征進(jìn)行分?jǐn)?shù)階變換,誘導(dǎo)出單一的超參數(shù),在實(shí)現(xiàn)上比模糊ART更具靈活性,且進(jìn)一步提升聚類精度。

IBFs_ART算法通過(guò)分?jǐn)?shù)階交互基函數(shù)(IBFs)對(duì)模糊ART進(jìn)行了擴(kuò)展,提出了一種新的生成柔性決策邊界的策略。目標(biāo)是評(píng)估IBFs在IBFs_ART中的表現(xiàn)。當(dāng)樣本x={x1,x2,…,xd}即將到來(lái)時(shí),每個(gè)特征在[0,1]中被歸一化。對(duì)于IBFs,用d個(gè)新特征來(lái)擴(kuò)大d個(gè)特征的集合：

x*=(x1,x2,…,xd,xd+1,xd+2,…,x2d)

(13)

其中,使用自交互時(shí)x*∈R2d,xd+j=fp(xj),p∈{1,2,…,K}。使用交叉交互時(shí)xd+j=g1(f1(x1),f2(x2),…,fK(xd))。

考慮如下函數(shù)：

f1(xj)=(xj)a

(14)

f2(xj)=(1-xj)a

(15)

f3(xj)=(exj)a

(16)

(17)

IBFs_ART算法如下所示：

輸入：DS={x1,x2,…,xn}

輸出：節(jié)點(diǎn)集合C={c1,c2,…,cn}和權(quán)值W={Wc1,Wc2,…,Wcn}

(1)：for eachxn

(4)：使用公式1計(jì)算選擇函數(shù),求出活動(dòng)節(jié)點(diǎn)Λ(Λ∈C)

(5)：從活動(dòng)節(jié)點(diǎn)中查找獲勝聚簇J：J=argj∈Λmax(Tj)

(6)：使用公式2計(jì)算匹配函數(shù);

(7)：if獲勝聚簇J滿足Mj≥ρ

(8)：使用學(xué)習(xí)函數(shù)(3)更新獲勝聚簇J

(9)：else

(10)：類別J：Λ←Λ-J

(11)：if活動(dòng)節(jié)點(diǎn)Λ≠?then

(12)：返回執(zhí)行第5步

(13)：else

(14)：J=|C|+1

(15)：創(chuàng)建新的聚類：C←C∪J

(16)：初始化新的聚類：wj=I

(17)：end if

(18)：end if

(19)：end if

3 實(shí)驗(yàn)與結(jié)果

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

本次實(shí)驗(yàn)計(jì)算機(jī)配置為Inter Core i7-7500U 2.90 GHz處理器和4 GB內(nèi)存,Windows10 操作系統(tǒng),所有比較程序均在MATLAB上設(shè)計(jì)和運(yùn)行。

3.1.1 數(shù)據(jù)集

為了對(duì)聚類的有效性進(jìn)行更好的評(píng)價(jià),在實(shí)驗(yàn)中采用了人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集,見(jiàn)表1。

表1 數(shù)據(jù)集

Letter4由Java代碼https：//github.com/feldob/生成。它包括9 344個(gè)樣本,2個(gè)維度和7個(gè)類。

KddCup99來(lái)源于林肯實(shí)驗(yàn)室的一項(xiàng)入侵檢測(cè)評(píng)估項(xiàng)目,仿真各種不同的用戶類型、網(wǎng)絡(luò)流量和攻擊手段,記錄了9周內(nèi)TCP網(wǎng)絡(luò)連接和系統(tǒng)審計(jì)數(shù)據(jù)。包含約50萬(wàn)條連接記錄,這些記錄含1種正常的標(biāo)識(shí)類型和22種訓(xùn)練攻擊類型,共有23個(gè)類,每個(gè)連接記錄包含41個(gè)維度。

CoverType來(lái)源于某國(guó)家森林的四片荒野區(qū)域的觀測(cè)。共包含581 012條記錄,分為7種類型,每條觀測(cè)記錄包含54個(gè)維度。

Powersupply來(lái)源于意大利某電力公司的供電數(shù)據(jù),記錄兩個(gè)電能：來(lái)自主電網(wǎng)的電能和來(lái)自其他電網(wǎng)的電能。該流包含2015年至2018年三年供電記錄。數(shù)據(jù)變化主要來(lái)自季節(jié)、天氣、一天的時(shí)間(例如早晚),以及工作日和周末的差異。它由29 928個(gè)樣本,2個(gè)維度,24個(gè)類組成。

3.1.2 聚類評(píng)價(jià)指標(biāo)

為了評(píng)價(jià)算法性能,引入了三種評(píng)價(jià)指標(biāo)：

(1)Accuracy(purity)。

(18)

(2)NMI(normalized mutual information)。

NMI是一個(gè)量化兩個(gè)分布之間共享的統(tǒng)計(jì)信息的對(duì)稱度量,當(dāng)類簇標(biāo)簽和樣本類別之間存在一對(duì)一的映射時(shí),NMI值達(dá)到最大為1.0。A為真實(shí)聚簇A={A1,A2,…,Ak},B為通過(guò)某個(gè)聚類算法得到的聚簇B={B1,B2,…,Bh},C為混淆矩陣,C中的元素Cij表示既在A中又在B中的樣本個(gè)數(shù)。

(19)

其中,CA(CB)為聚簇A,B同時(shí)在矩陣C中的簇?cái)?shù)目,Ci.(C.j)為C中第i行的元素和;N為樣本個(gè)數(shù)。

(3)RI(rand index)。

RI(蘭德指數(shù))的計(jì)算公式為：

(20)

3.2 實(shí)驗(yàn)結(jié)果

首先評(píng)價(jià)IBFs_ART的聚類質(zhì)量,并從Acc,NMI和RI三個(gè)方面與G-Stream(警戒參數(shù)較多)以及模糊ART(Fuzzy ART,只有一個(gè)警戒參數(shù))進(jìn)行了比較。對(duì)于自交互,使用公式5～7,對(duì)于特征交互,使用以下三個(gè)函數(shù)：

(21)

(22)

(23)

每個(gè)算法重復(fù)實(shí)驗(yàn)10次,聚類結(jié)果如表2～4所示。通過(guò)實(shí)驗(yàn),發(fā)現(xiàn)取不同的ρ值,IBFs_ART算法從三個(gè)方面的評(píng)價(jià)幾乎都可以找到一個(gè)a值(選取1/2和1/4值),使其性能指標(biāo)均優(yōu)于模糊ART,且性能指標(biāo)得到不小提升,驗(yàn)證了IBFs_ART算法的優(yōu)越性。

表2 IBFs_ART和其他數(shù)據(jù)流聚類算法Acc比較結(jié)果

表3 IBFs_ART和其他數(shù)據(jù)流聚類算法NMI比較結(jié)果

表4 IBFs_ART和其他數(shù)據(jù)流聚類算法RI比較結(jié)果

續(xù)表4

通過(guò)實(shí)驗(yàn)評(píng)估了不同警戒參數(shù)ρ的IBFs_ART的性能,該參數(shù)控制了當(dāng)輸入樣本與類別發(fā)生共振時(shí),隨后是否允許該類別學(xué)習(xí)樣本。實(shí)驗(yàn)中選擇合理的警戒值ρ可以允許發(fā)現(xiàn)有用的簇,而不需要對(duì)許多敏感參數(shù)值進(jìn)行微調(diào)。圖2～5顯示了IBFs_ART在4個(gè)數(shù)據(jù)集上使用Acc,NMI和RI三個(gè)評(píng)價(jià)指標(biāo)展示警戒參數(shù)ρ的敏感性。

圖2 IBFs_ART對(duì)于Letter4數(shù)據(jù)集ρ的敏感性 圖3 IBFs_ART對(duì)于Kddcup99數(shù)據(jù)集ρ的敏感性

圖4 IBFs_ART對(duì)于CoverType數(shù)據(jù)集ρ的敏感性 圖5 IBFs_ART對(duì)于Powersupply數(shù)據(jù)集ρ的敏感性

通過(guò)實(shí)驗(yàn),首先評(píng)價(jià)了IBFs_ART的聚類質(zhì)量,并從Acc,NMI和RI三個(gè)方面將G-Stream以及模糊ART方法進(jìn)行了比較,并且IBFs_ART同時(shí)采用了自交互與交叉交互。其次,采用不同的警戒參數(shù)值進(jìn)行實(shí)驗(yàn),證明了警戒參數(shù)對(duì)算法的影響。大量的數(shù)據(jù)結(jié)果證明,IBFs_ART可以達(dá)到更好的聚類效果與更高性能。

4 結(jié)束語(yǔ)

數(shù)據(jù)流是一種潛在的海量、連續(xù)、快速的數(shù)據(jù)信息序列,引起了數(shù)據(jù)挖掘領(lǐng)域的極大關(guān)注和研究熱潮。而聚類又是數(shù)據(jù)挖掘的有效工具,因此數(shù)據(jù)流聚類無(wú)疑是數(shù)據(jù)流挖掘研究的重點(diǎn)。該文將交互基函數(shù)引入到模糊ART中,構(gòu)造IBFs_ART算法,經(jīng)過(guò)和原先算法的對(duì)比實(shí)驗(yàn),驗(yàn)證了該算法能夠提高聚類精度且只需要較低的計(jì)算成本,在Acc,NMI和RI三個(gè)方面都比傳統(tǒng)算法模型更好,且底層模糊ART遞增執(zhí)行聚類的過(guò)程并沒(méi)有改變,也就意味著IBFs_ART算法可以在任何算法中實(shí)現(xiàn),可用于數(shù)據(jù)流聚類算法的任何擴(kuò)展。