大规模数据聚类中模糊自适应谐振理论的研究与应用

朱颖雯

摘  要： 大规模社交媒体数据的复杂性要求将聚类技术扩展到大规模数据，使其能够在很少的经验设置下自动识别数据聚簇。文章研究和讨论了模糊自适应谐振理论（Fuzzy Adaptive Resonance Theory）算法，其具有线性计算复杂性，仅使用一个单一参数，且对参数设置具有鲁棒性，可以产生更好的聚类结果。真实数据集上的实验结果表明，该算法在大规模数据聚类中取得了可比较的性能和更快的速度，而且也不需要预先定义聚簇个数。

关键词： 大规模数据; 聚类; 自适应谐振理论; 模糊自适应谐振理论

中图分类号：TP391          文献标识码：A     文章编号：1006-8228（2020）10-24-05

Abstract： The large scale and complex nature of social media data raises the need to scale clustering techniques to big data and make them capable of automatically identifying data clusters with few empirical settings. In this paper， the Fuzzy ART algorithm （Fuzzy Adaptive Resonance Theory） is studied; it has linear computational complexity， uses a single parameter， i.e.， the vigilance parameter to identify data clusters， and is robust to modest parameter settings. Experiments on real data sets show that Fuzzy ART can achieve better or comparable performance and much faster speed than the state-of-the-art clustering algorithms， without need for predefining the number of clusters.

Key words： large scale data; data clustering; adaptive resonance theory; fuzzy adaptive resonance theory

0 引言

社交网站的流行导致在线多媒体文档急剧增加，例如图片、博客等。近年来，聚类网络多媒体数据已成为社交网络社群识别[1-2]，集体行为分析[3]，基础主题发现[4-5]的热点。社交媒体数据通常规模很大，涵盖不同主题内容，因此很难评估基础主题的个数和数据的模式分布，需要现有的聚类方法扩展到大规模数据，通过一些经验设置（如聚簇个数）自动识别数据聚簇。

大多广泛使用的聚类方法如K-Means、谱聚类、矩阵分解均需要设置聚簇个数。方法一般可分为两类：聚类趋势分析方法[6-8]和聚类验证方法[9-14]。第一种方法通过模式的相邻关系来确定数据集中的聚簇个数，第二种方法通过评估不同聚簇的结构。这两种方法都很慢，均无法扩展到大规模数据。不需要预先定义聚簇个数的方法有基于层次的聚类方法[15-17]，基于遗传的聚类方法[18-19]，基于密度的聚类方法[20-21]，基于近邻传播的方法（AP）[22]和自适应谐振理论（ART）[23-27]。而层次和遗传方法类似于聚类验证方法，其他算法通常具有O（n2）的时间复杂度，且需要一个或多个参数来形成聚簇，这使得它们的性能对这些参数的设置非常敏感。

为了聚类大规模数据，不设置聚簇个数且具有高聚类精度，本文讨论和研究了模糊自适应谐振理论（Fuzzy ART）算法，它是ART算法的变体，其具有线性计算复杂性，仅使用一个单一参数，且对参数设置具有鲁棒性，可以产生更好的聚类结果。

1 相关研究

1.1 聚类趋势分析

聚类趋势分析的目的是聚类前确定数据集中的聚簇个数。主要聚焦于研究模式的相异度矩阵。趋势视觉评估（VAT）[6]对模式的相异矩阵进行重新排序，形成一个重新排序的不相似图像（RDI），通过计算对角线像素上的黑色块来识别聚簇的个数。聚类计数提取（CCE）[7]和暗块提取（DBE）[8]可客观识别聚簇的个数取代人工计数。CCE使用过滤的RDI的非对角线像素值构造直方图，簇的个数等于直方图中峰值的个数。而DBE采用矩阵变换的方法，将RDI的所有像素值投影到主对角线轴上从而获得投影信号，簇的个数等于信号中主要峰值的个数。

1.2 聚类验证

聚类验证是通过评估生成的不同聚类结构质量来找到最佳聚簇。考虑到聚簇归属机制的不同，聚类验证可以分为硬聚类[28]（一个模式属于一个聚簇）和模糊聚类[9]（一个模式具有所有聚簇的模糊隶属度）。硬聚类方法遵循以下原则。①验证指标。基于簇内紧密度和簇间分离度对不同聚簇个数生成的不同簇的质量进行评价[10，13]。②将不同聚簇的验证指标值绘制为关于聚簇个数的函数，最佳聚簇个数位于极端值或弯头值[11，29]。③通过子采样和添加随机噪声等工具扭曲给定数据集产生多数据集。再对每个数据集进行聚类，以确定最佳的聚簇个数[14]。已有的模糊聚类验证方法[9，12]通常使用模糊c均值作为基本算法，并对生成的聚类质量进行评估，以确定最佳聚簇个数。

2 模糊自适应谐振网络

自组织神经网络是人工智能领域应用最为广泛的一种学习模型。为解决大部分神经网络模型遭遇的“稳定性-弹性问题”，美国Boston大学的S.Grossberg和G.A.Carpenter于1976年提出了一种无监督竞争型神经网络模型，即自适应谐振理论网络ART（Adaptive Resonance Theory）[30]，可在稳定原有模式类的前提下，学习新的模式。ART模拟了人类大脑如何捕捉、识别、记忆关于事物和事件的信息。随着理论不断完善，有大量基于ART改进的无监督学习模型被提出，如ART1[23]、ART2[25]、ART2-A[26]、ART3[27]和模糊ART（Fuzzy ART）[24]。模糊ART通过在类别空间实时搜索和匹配现有聚簇增长式的逐步处理每一个输入模式。其中警戒参数用于约束在同一个聚簇中的模式的最小相似度。当输入模式与现有聚簇都不相似时，生成一个新的聚簇来编码这个新模式。模糊ART已被改进用于解决图像和文本挖掘问题，如Web文档管理，基于标记的Web图像组织，图像-文本关联和異构数据聚类。模糊ART适用于大规模数据聚类。

模糊ART模型由输入层F1和识别层F2组成，如图1所示。输入层为输入向量I，识别层由一些节点向量组成，代表各个聚簇。在F1层，输入向量被提交到网络，与F2层各个聚簇向量的权值进行相似度比较并归类。

⑴ 输入向量（Input Vectors）：设[I=x]表示输入层F1的输入模式。[x=（x1，…，xm）]，[xi∈[0，1]]（i=1，…，m）。通过补编码（complement coding），x与它的补向量[x=1-x]共同构成了[I=（x，x）]。

⑵ 权值向量（Weight Vectors）：设wj表示识别层F2中第j个类[cj=（j=1，…，J）]的权值。

⑶ 参数（Parameters）：模糊ART随着3个参数动态改变，它们分别是选择参数[α>0]，学习参数[β∈[0，1]]，以及警戒参数[ρ∈[0，1]]。

模糊ART聚类过程包含3个关键步骤：

步骤1：类别选择（Category Choice）。对每个输入模式I，模糊ART对识别层F2中的每个聚簇根据选择函数计算选择值，并选择具有最大值的聚簇作为获胜聚簇cj*。第j个聚簇cj的选择函数定义为：

3 实验结果分析

为了验证本文算法的有效性，我们在2个真实大规模数据集上进行了实验。使用的计算机配置为Intel Core i5-6300U 2.4GHz处理器和8G内存，Windows 10操作系统，所有程序均在MATLAB R2015a上设计和运行。为了对各种聚类算法的精度进行评价，我们引入了3项评价指标：（a）Accuracy（Acc） [31]，（b）Normalized Mutual Information（NMI） [31]，（c）Rand index（RI）[31]。Acc度量了聚簇的纯度，Acc越大表明聚类纯度越高。其取值范围在0到1之间。归一化互信息NMI是一个量化两个分布之间共享统计信息的对称策略。当聚簇标签和真实样本类别一对一映射时NMI值到达最大值1.0。[RI∈[0，1]]，当两个算法划分完全一致时RI=1。

3.1 数据集

为了对模糊ART算法的聚类有效性进行评价，实验中我们使用了2个真实数据集，表1给出数据集的相关信息。

KddCup99与CoverType均来自UCI。KddCup99数据集最早来源于MIT 林肯实验室的一项入侵检测评估项目， 记录了9 周内TCP 网络连接和系统审计数据， 仿真各种不同的用户类型、网络流量和攻击手段。这些原始数据包含约500000条连接记录的训练集。每个连接记录包含41个属性，这些连接记录含1种正常的标识类型normal和22种训练攻击类型，共23个类别。CoverType数据集来源于US Geological Survey（USGS）和US Forest Service （USFS）对位于Roosevelt国家森林的四片荒野区域的观测。数据集中包含581012条记录， 这些记录最终被分为7种类型。每条观测记录包含54个地质学和地理学属性。

3.2 聚类性能

我们评估了模糊ART的聚类性能，警戒参数r取0.85，每个算法重复实验10次。聚类结果如表2所示。

从表2中，我们可以发现模糊ART在两个大规模数据集上均取得了较高的Acc、NMI和Rand指数。

3.3 警戒参数r的变化

图2显示了模糊ART在2个数据集上随警戒参数r的变化聚类性能的变化。从图中可以看出：①CoverType数据集上聚类纯度Acc随参数r的增大，到达一定值后有所下降;②2个数据集上NMI和Rand指数都随参数r的增大稳步增长。

3.4 运行时间

圖3显示了2个数据集上模糊ART的运行时间。从中可以看出，模糊ART的执行时间都随着数据量的增加而增加。研究表明，模糊ART算法对大规模数据的处理效率更高。

4 总结

本文讨论和研究了模糊自适应谐振理论（Fuzzy ART）算法，其具有线性计算复杂性，仅使用一个单一参数，且对参数设置具有鲁棒性，可产生更好的聚类结果。特别适用于大规模数据聚类。真实数据集上的实验结果表明，该算法在大规模数据聚类中取得了很好的性能和更快的速度，而且也不需要预先定义聚簇个数。未来的研究方向是如何自动调整模糊ART算法中的警戒参数用于提高聚类性能。

参考文献（References）：

[1] S. Papadopoulos， Y. Kompatsiaris， A. Vakali， and P.Spyridonos， "Community detection in social media，" Data Mining Knowl. Discovery，2012.24（3）：515-554

[2] L. Meng and A.-H.Tan， "Community discovery in social networks via heterogeneous link association and fusion".in Proc. SIAM Int. Conf. Data Mining，2014：803-811

[3] L. Tang and H. Liu， "Scalable learning of collective behavior based on sparse social dimensions，" in Proc. ACM Int. Conf. Inf. Knowl.Manage.，2009：1107-1116

[4] A.-H. Tan， H.-L.Ong， H. Pan， J. Ng， and Q.-X.Li，"Towards personalised Web intelligence，" Knowl. Inf. Syst.，2004.6（5）：595-616

[5] L. Meng and A.-H.Tan， "Semi-supervised hierarchical clustering for personalized Web image organization，" in Proc. Int. Joint Conf. Neural Netw.，2012.6：251-258

[6] J. C. Bezdek and R. J. Hathaway， "VAT： A tool for visual assessment of （cluster） tendency，" in Proc. Int. Joint Conf. Neural Netw.，2002.5：2225-2230

[7] I. J. Sledge， J. M. Huband， and J. C. Bezdek， "（Automatic）cluster count extraction from unlabeled data sets，" in Proc. Int. Conf. Fuzzy Syst. Knowl. Discovery，2008.10：3-13

[8] L. Wang， C. Leckie， K. Ramamohanarao， and J. Bezdek，"Automatically determining the number of clusters in unlabeled data sets，" IEEE Trans. Knowl. Data Eng.，2012.21（3）：335-350

[9] W. Wang and Y. Zhang， "On fuzzy cluster validity indices，"Fuzzy Sets Syst.，2007.158（19）：2095-2117

[10] J. Liang， X. Zhao， D. Li， F. Cao， and C. Dang， "Determining the number of clusters using information entropy for mixed data，" Pattern Recognit.，2012.45（6）：2251-2265

[11] C. A. Sugar and G. M. James， "Finding the number of clusters in a dataset： An information-theoretic approach，" J. Amer. Statist. Assoc.，2003.98（463）：750-763

[12] H. Sun， S. Wang， and Q. Jiang， "FCM-based model selection algorithms for determining the number of clusters，" Pattern Recognit.，2004.37（10）：2027-2037

[13] R. Kothari and D. Pitts， "On finding the number of clusters，" Pattern Recognit.Lett.，1999.20（4）：405-416

[14] J.-S. Lee and S. Olafsson， "A meta-learning approach for determining the number of clusters with consideration of nearest neighbors" Inf. Sci.，2013.232（5）：208-224

[15] M. J. Li， M. K. Ng， Y.-M. Cheung， and J. Z. Huang，"Agglomerative fuzzy K-means clustering algorithm with selection of number of clusters，" IEEE Trans. Knowl. Data Eng.，2008.20（11）：1519-1534

[16] Y. Leung， J.-S.Zhang， and Z.-B. Xu， "Clustering by scale-space filtering，" IEEE Trans. Pattern Anal. Mach. Intell.，2000.22（12）：1396-1410

[17] H. Yan， K. Chen， L. Liu， and J. Bae， "Determining the best K for clustering transactional datasets： A coverage density-based approach，" Data Knowl. Eng.，2009.68（1）：28-48

[18] S. Bandyopadhyay and S. Saha， "A point symmetry-based clustering technique for automatic evolution of clusters，" IEEE Trans. Knowl. Data Eng.，2008.20（11）：1441-1457

[19] S. Bandyopadhyay， "Genetic algorithms for clustering and fuzzy clustering，"Wiley Interdiscipl. Rev.， Data Mining Knowl. Discovery，2011.1（6）：524-531

[20] H.-P. Kriegel， P. Kr?ger， J. Sander， and A. Zimek，"Density-based clustering，"Wiley Interdiscipl. Rev.， Data Mining Knowl. Discovery，2011.1（3）：231-240

[21] M. Ester， H.-P.Kriegel， J. Sander， and X. Xu， "A density-based algorithm for discovering clusters in large spatial databases with noise，" in Proc. ACM SIGKDD Conf. Knowl. Discovery Data Mining，1996：226-231

[22] B. J. Frey and D. Dueck， "Clustering by passing messages between data points，"Science，2007.315（5814）：972-976

[23] G. A. Carpenter and S. Grossberg， "A massively parallel  architecture for a self-organizing neural pattern recognition machine，" Comput. Vis.， Graph.， Image Process.，1987. 37（1）：54-115

[24] G. A. Carpenter， S. Grossberg， and D. B. Rosen， "Fuzzy ART：Fast stable learning and categorization of analog patterns by an adaptive resonance system，" Neural Netw.，1991.4（6）：759-771

[25] G. A. Carpenter and S. Grossberg， "ART 2： Self-organization of stable category recognition codes for analog input patterns，"Appl. Opt.，1987.26（23）：4919-4930

[26] G. A. Carpenter， S. Grossberg， and D. B. Rosen， "ART 2-A： An adaptive resonance algorithm for rapid category learning and recognition，"Neural Netw.，1987.4：493-504

[27] G. A. Carpenter and S. Grossberg， "ART 3： Hierarchical  search using chemical transmitters in self-organizing pattern recognition architectures，"Neural Netw.，1990.3（2）：129-152

[28] B. Mirkin， "Choosing the number of clusters，" Wiley Interdiscipl. Rev.， Data Mining Knowl. Discovery，2011.1（3）：252-260

[29] M. M.-T. Chiang and B. Mirkin， "Intelligent choice of the number of clusters in K-means clustering：An experimental study with different cluster spreads，" J. Classification，2010.27（1）：3-40

[30] Grossberg S. How does a brain build a cognitive code？[M]//Studies of mind and brain. Springer， Dordrecht，1982：1-52

[31] Zhu Y， Chen S. Growing neural gas with random projection method for high-dimensional data stream clustering[C]. soft computing，2019：1-19