基于双警戒参数模糊自适应谐振网络的数据流聚类

沈凤仙，朱颖雯

（三江学院计算机科学与工程学院，南京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通过在单个网络中加入更严格（数据压缩）和更宽松（聚类相似度）的两个警戒参数，扩展模糊自适应谐振网络的能力，在聚簇和类别之间动态创建多对一映射，捕获任意形状的数据集并允许聚簇的多中心表示。数据流聚类性能超过模糊自适应谐振网络。