基于雙警戒參數模糊自適應諧振網絡的數據流聚類

沈鳳仙，朱穎雯

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

0 引言

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

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

1 相關工作：模糊ART

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

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

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

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

如果獲勝聚簇J滿足v1，則發生共振（resonance），引發中心學習。否則繼續在余下的聚簇中尋找一個獲勝聚簇并跳轉到2。

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

2 基于雙警戒參數模糊自適應諧振網絡的數據流聚類算法

2.1 雙警戒參數模糊自適應諧振網絡（DVFA）

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

2.2 基于雙警戒參數模糊自適應諧振網絡的數據流聚類算法

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

算法1.DVFA_DS算法

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

輸出：Mmap=[mr,c]及每個神經元節點權值W={wc1,wc2,wc3,...}。

①for eachxi

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

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

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

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

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

⑤end for

3 結語

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