沈鳳仙，朱穎雯

（三江學(xué)院計算機科學(xué)與工程學(xué)院，南京210012）

0 引言

近期硬件和軟件的發(fā)展生成大量的流數(shù)據(jù)，如網(wǎng)絡(luò)流[1]、圖形流[2]、短文本流[3]、數(shù)字流[4]、事件流[5]、語義概念流[6]、Web點擊流[7]。挖掘數(shù)據(jù)流是大數(shù)據(jù)分析[8]的基礎(chǔ)任務(wù)之一。而所有數(shù)據(jù)流挖掘任務(wù)中，數(shù)據(jù)流聚類[9-10]是研究熱點，其目的是在有限的計算資源下，有效地將以流方式到達的數(shù)據(jù)劃分為多個聚簇，且同時可捕獲概念漂移和觀察聚簇的演化。目前人們從不同角度設(shè)計了高效數(shù)據(jù)流聚類算法[11-12]，如捕捉與概念漂移相關(guān)的聚簇演化、處理高維數(shù)據(jù)流[13-14]、發(fā)現(xiàn)任意形狀的聚簇[15-16]等。根據(jù)其擴展的基聚類算法（傳統(tǒng)聚類算法）的不同，可將其分為5類：基于劃分的方法（STREAM?KM[17]）；基于層次的方法（CluStream[18]、HPStream[13]）；基于密度的方法（DenStream[19]、RepStream[20]、Str-FSFDP[11]、EDMStream[10]）；基于網(wǎng)格的方法（D-Stream[21]）；基于模型的方法（G-Stream[22]、RPGStream[23]）。其中雖然基于模型的數(shù)據(jù)流聚類方法包含了很多領(lǐng)域知識并強依賴于假設(shè)模型，但高效的模型不僅可以得到較優(yōu)的聚類結(jié)果還能挖掘聚簇結(jié)構(gòu)，例如：G-Stream和RPGStream算法均基于GNG（Growing Neural Gas）模型。解決數(shù)據(jù)流挖掘中的各類約束的同時可發(fā)現(xiàn)數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)，但因其基于GNG模型，超參數(shù)較多，調(diào)節(jié)參數(shù)對算法性能影響較大。故本文的直接動機是設(shè)計一個可在單機執(zhí)行、少參數(shù)、且適用于數(shù)據(jù)流的高效數(shù)據(jù)流聚類算法。

自適應(yīng)諧振網(wǎng)絡(luò)（ART）[24]是一個學(xué)習(xí)理論，可解決穩(wěn)定-可塑性困境。它啟發(fā)了許多神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，其共享機制（共振和復(fù)位）在系統(tǒng)控制下被警戒參數(shù)觸發(fā)。然而不同結(jié)構(gòu)在其內(nèi)部表示上的不同，限制了它們可以檢索的聚簇形狀。已存在許多利用多中心表示能力來捕獲任意形狀聚簇的聚類方法。例如：文獻[25]基于ART使用二次神經(jīng)元提出了層次結(jié)構(gòu)框架，而文獻[26]和[27]均基于模糊ART[28]、TopoART[29]及其變種[30-31]將多層ART與拓?fù)鋵W(xué)習(xí)結(jié)合。受分層警戒參數(shù)可生成復(fù)雜的ART系統(tǒng)（例如，用于混合模態(tài)學(xué)習(xí)[32]）的啟發(fā)，本文通過將雙警戒參數(shù)模糊自適應(yīng)諧振網(wǎng)絡(luò)（DVFA）用于數(shù)據(jù)流聚類，DVFA通過增加第二次警戒測試來增強模糊ART聚類的能力，使其在單一ART模塊中實現(xiàn)多中心表示，實現(xiàn)了在數(shù)據(jù)流中快速穩(wěn)定的增量學(xué)習(xí)。

1 相關(guān)工作：模糊ART

模糊ART是由一組可自適應(yīng)權(quán)值w連接的兩層神經(jīng)網(wǎng)絡(luò)：將輸入x歸一化和補編碼(x←[x,1-x],0≤xi≤1?i)后提交到F1層，識別的聚簇通過F2層神經(jīng)元節(jié)點表示。模糊ART由選擇參數(shù)（α>0）、學(xué)習(xí)率（β∈[0,1]）和警戒參數(shù)（ρ∈[0,1]）三者控制。聚類過程如下：

（1）輸入模式x提交到F1層，對F2層中的每個聚簇cj根據(jù)選擇函數(shù)計算選擇值Tj：

然后，選擇具有最大值的聚簇作為獲勝聚簇J：

（2）使用匹配函數(shù)v1對輸入模式x與獲勝聚簇J進行評估，v1定義為：

如果獲勝聚簇J滿足v1，則發(fā)生共振（resonance），引發(fā)中心學(xué)習(xí)。否則繼續(xù)在余下的聚簇中尋找一個獲勝聚簇并跳轉(zhuǎn)到2。

（3）如果所有獲勝聚簇均不能滿足v1，則創(chuàng)建一個新的聚簇來編碼這個輸入模式x。

2 基于雙警戒參數(shù)模糊自適應(yīng)諧振網(wǎng)絡(luò)的數(shù)據(jù)流聚類算法

2.1 雙警戒參數(shù)模糊自適應(yīng)諧振網(wǎng)絡(luò)（DVFA）

雙警戒模糊自適應(yīng)諧振網(wǎng)絡(luò)（DVFA）[33]由兩層警戒參數(shù)組成，分別調(diào)節(jié)數(shù)據(jù)壓縮和聚類相似度，即一個更緊的約束和一個更松的約束。兩個警戒參數(shù)分別是上界（ρUB∈[0,1]）和下界（0≤ρLB≤ρUB≤1），利用二元矩陣Mmap=[mr,c]將聚簇（行）映射到類別（列），類似于模糊ARTMAP[34]。該框架是一種多中心方法，使用單個ART模塊構(gòu)建了從聚簇到類別的多對一映射。這允許更好地捕獲數(shù)據(jù)分布，以便DVFA能夠檢索任意幾何形狀的聚簇。

2.2 基于雙警戒參數(shù)模糊自適應(yīng)諧振網(wǎng)絡(luò)的數(shù)據(jù)流聚類算法

設(shè)數(shù)據(jù)流DS為一個帶有時間戳（Time Stamp）的多維數(shù)據(jù)點集合，DS={x1,x2,...,xn}（實際應(yīng)用中n的取值可以為無限大），其中每個數(shù)據(jù)點是一個d維的數(shù)據(jù)記錄，其到達時間為ti。數(shù)據(jù)流聚類將數(shù)據(jù)DS中的相似對象劃分為一個或多個組（稱為“簇”，Cluster），劃分后，同一簇中的元素彼此相似，但相異于其他簇中的元素?；贒VFA的數(shù)據(jù)流算法DVFA_DS如下所示。

算法1.DVFA_DS算法

輸入：DS={x1,x2,x3...,}；

輸出：Mmap=[mr,c]及每個神經(jīng)元節(jié)點權(quán)值W={wc1,wc2,wc3,...}。

①for eachxi

②對輸入模式xi根據(jù)公式（1）～（4）選擇獲勝聚簇J。

③根據(jù)公式（5）對輸入模式xi與獲勝聚簇J進行v1評估，使用ρUB代替ρ。如果獲勝聚簇J滿足v1，則根據(jù)公式（6）對聚簇中心進行更新權(quán)值wJ。

④如果獲勝聚簇J不滿足v1，根據(jù)公式（5）使用ρLB代替ρ進行第2次測試v2。

（a）如果v2滿足，則創(chuàng)建一個新的聚簇I，并將其分配到與聚簇J相同的簇中，通過在Mmap中添加一個新的行I等于行J來實現(xiàn)，這個過程可以看作是“拆分”父聚簇。

（b）如果v2不滿足，則創(chuàng)建一個新的聚簇I，并拓展Mmap的行和列，對新的類別K進行如下編碼：

⑤end for

3 結(jié)語

本文將雙警戒參數(shù)模糊自適應(yīng)諧振網(wǎng)絡(luò)（DVFA）用于數(shù)據(jù)流聚類，研究了一種新的無監(jiān)督神經(jīng)網(wǎng)絡(luò)用于流數(shù)據(jù)穩(wěn)定在線聚類。DVFA通過在單個網(wǎng)絡(luò)中加入更嚴(yán)格（數(shù)據(jù)壓縮）和更寬松（聚類相似度）的兩個警戒參數(shù)，擴展模糊自適應(yīng)諧振網(wǎng)絡(luò)的能力，在聚簇和類別之間動態(tài)創(chuàng)建多對一映射，捕獲任意形狀的數(shù)據(jù)集并允許聚簇的多中心表示。數(shù)據(jù)流聚類性能超過模糊自適應(yīng)諧振網(wǎng)絡(luò)。