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

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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

模糊ART使用模糊算法并引入一個“補編碼”[12]來解決“類別擴散”問題。模糊ART執(zhí)行步驟如下：

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

(1)

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

(2)

如果獲勝聚簇Cj*滿足警戒標準Mj*≥ρ,會發(fā)生諧振,從而導致步驟3的中心學習。否則,將在其余聚類中選擇新的獲勝聚簇。如果沒有獲勝聚簇滿足警戒標準,則將生成一個新的聚簇來對輸入模式進行編碼。

(3)中心學習：如果Cj*滿足警戒標準,其對應(yīng)的權(quán)重向量Wj*將通過函數(shù)進行更新,定義為：

(3)

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

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

2.1 交互基函數(shù)

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

f(X)=X

(4)

多項式函數(shù)的一個特殊情況,即當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ù)的使用并沒有同樣的效果。考慮K個實函數(shù)bi的一般情況：R→R,i=1,2,…,K,稱{f1,f2,…,fK}為一組基函數(shù)。然后利用基函數(shù)得到的T個新特征擴充p個特征集：

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*時使用兩個或多個特征之間的交互信息。這些交互不同于自交互,可以通過一組D函數(shù)來識別,這些M函數(shù)通過基函數(shù)來再現(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)

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

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

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

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

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

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

(13)

其中,使用自交互時x*∈R2d,xd+j=fp(xj),p∈{1,2,…,K}。使用交叉交互時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é)點集合C={c1,c2,…,cn}和權(quán)值W={Wc1,Wc2,…,Wcn}

(1)：for eachxn

(4)：使用公式1計算選擇函數(shù),求出活動節(jié)點Λ(Λ∈C)

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

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

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

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

(9)：else

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

(11)：if活動節(jié)點Λ≠?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 實驗與結(jié)果

3.1 實驗環(huán)境

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

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

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

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

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

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

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

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

3.1.2 聚類評價指標

為了評價算法性能,引入了三種評價指標：

(1)Accuracy(purity)。

(18)

(2)NMI(normalized mutual information)。

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

(19)

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

(3)RI(rand index)。

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

(20)

3.2 實驗結(jié)果

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

(21)

(22)

(23)

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

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

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

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

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

4 結(jié)束語

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