基于交互基函數的數據流聚類算法研究

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

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

0 引 言

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

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

1 數據流聚類與自適應諧振理論

1.1 數據流聚類

數據流具有內在的特性,包括無限大小、時間順序和動態變化。與傳統的數據挖掘相比,數據流挖掘只是在滿足單次通過、實時響應、有界內存和概念漂移檢測等約束條件下產生近似結果。

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

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

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

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

1.2 自適應諧振理論

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

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

圖1 模糊ART結構

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

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

(1)

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

(2)

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

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

(3)

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

2 基于交互基函數的數據流聚類

2.1 交互基函數

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

f(X)=X

(4)

多項式函數的一個特殊情況,即當a=1：

f(X)=Xa

(5)

f(X)=(1-X)a

(6)

也可以定義其它基函數,例如指數：

f(X)=(eX)a

(7)

回歸分析中常用的是基函數,它們具有改變回歸平面性質的作用。例如,從恒等式到變量的平方的轉換具有將回歸線變為拋物線的效果。但DTs(決策樹)[14]中基函數的使用并沒有同樣的效果。考慮K個實函數bi的一般情況：R→R,i=1,2,…,K,稱{f1,f2,…,fK}為一組基函數。然后利用基函數得到的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}。

由于基函數在原基中仍然產生正交劃分,筆者的建議是在構造X*時使用兩個或多個特征之間的交互信息。這些交互不同于自交互,可以通過一組D函數來識別,這些M函數通過基函數來再現特征變換的功能交互,這些交互函數被定義為：

hhi：Rpk→Rh

(9)

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

(10)

此設置下,定義：

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

(11)

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

(12)

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

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

2.2 基于交互基函數的數據流聚類算法

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

IBFs_ART算法通過分數階交互基函數(IBFs)對模糊ART進行了擴展,提出了一種新的生成柔性決策邊界的策略。目標是評估IBFs在IBFs_ART中的表現。當樣本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))。

考慮如下函數：

f1(xj)=(xj)a

(14)

f2(xj)=(1-xj)a

(15)

f3(xj)=(exj)a

(16)

(17)

IBFs_ART算法如下所示：

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

輸出：節點集合C={c1,c2,…,cn}和權值W={Wc1,Wc2,…,Wcn}

(1)：for eachxn

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

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

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

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

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

(9)：else

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

(11)：if活動節點Λ≠?then

(12)：返回執行第5步

(13)：else

(14)：J=|C|+1

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

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

(17)：end if

(18)：end if

(19)：end if

3 實驗與結果

3.1 實驗環境

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

3.1.1 數據集

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

表1 數據集

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

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

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

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

3.1.2 聚類評價指標

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

(1)Accuracy(purity)。

(18)

(2)NMI(normalized mutual information)。

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

(19)

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

(3)RI(rand index)。

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

(20)

3.2 實驗結果

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

(21)

(22)

(23)

每個算法重復實驗10次,聚類結果如表2～4所示。通過實驗,發現取不同的ρ值,IBFs_ART算法從三個方面的評價幾乎都可以找到一個a值(選取1/2和1/4值),使其性能指標均優于模糊ART,且性能指標得到不小提升,驗證了IBFs_ART算法的優越性。

表2 IBFs_ART和其他數據流聚類算法Acc比較結果

表3 IBFs_ART和其他數據流聚類算法NMI比較結果

表4 IBFs_ART和其他數據流聚類算法RI比較結果

續表4

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

圖2 IBFs_ART對于Letter4數據集ρ的敏感性 圖3 IBFs_ART對于Kddcup99數據集ρ的敏感性

圖4 IBFs_ART對于CoverType數據集ρ的敏感性 圖5 IBFs_ART對于Powersupply數據集ρ的敏感性

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

4 結束語

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