随着云计算、物联网的快速发展，许多新型的应用领域，诸如网络入侵检测、视频监控、气象卫星遥感以及电力供应网等，每时每刻都在产生大量的数据.这些数据并不事先存放在存储介质中，而是像水流一样不断出现，它们具有快速(high speed)、时序(temporally ordered)、海量(massive)等特征，被称作数据流(data stream).

越来越多数据流的产生和应用需求使得对于数据流的挖掘变得炙手可热.挖掘数据流[1-9]的目的是从这些连续不断的流数据中提取隐藏的知识结构.数据流挖掘技术包括数据流分类、数据流聚类、数据流关联规则挖掘等.其中，数据流聚类是数据流学习的一项重点任务，它是将数据对象集合中相似对象划分为一个或多个组(称为“簇”，cluster)的过程，划分后同一簇中元素彼此相似，但与其他簇中元素相异.不同于传统的静态数据聚类，数据流聚类面临许多问题，例如：1)有限内存(bounded memory)，数据流中的数据常是海量，所以不可能在内存及硬盘上存储整个数据流集；2)一次扫描(single-pass)，同样因为数据量巨大，传统的多遍扫描方法不再适用，对其挖掘应该是一个单遍扫描过程，且对流中数据元素的访问只能单次线性(linear scan)，即只能按照流入顺序依次读取一次，无法进行随机访问；3)实时响应(real-time response)，多数应用要求快速响应，因此挖掘应该是一个连续在线的过程；4)概念漂移(concept-drift detection)，数据分布常随着时间的推移而发生变化.

目前，对于数据流聚类算法的研究已在学术界和工业界得到了广泛关注，许多相关算法已被提出[10-26].现有数据流聚类算法均由传统聚类算法扩展而来，根据其所扩展的传统算法不同，我们可以将其分为5类：基于划分的方法(STREAM[10])；基于层次的方法(CluStream[11],HPStream[12],SWClustering[13],E-Stream[14],REPSTREAM[15])；基于密度的方法(DenStream[16],ACSC[17],OPTICS-Stream[18],incPre-Decon[19])；基于网格的方法(D-Stream[20],MR-Stream[21],CellTree[22])；基于模型的方法(SWEM[23],GCPSOM[24],G-Stream[25],RPGStream[26]).表1分别针对6个特性对现有方法进行总结：1)基算法；2)所用计算策略(在线学习或两步学习)；3)类簇个数是否自适应；4)是否可挖掘拓扑结构；5)是否可检测概念漂移；6)是否适合高维数据.

如表1所示，基于划分的数据流聚类方法相对简单并易于实现，但其需要预先定义类簇个数，然而由于数据分布未知，类簇个数通常无法直接得到.此外，该方法无法检测概念漂移.基于层次的数据流聚类方法虽然能够发现有意义的类簇结构，但其一般具有较高的计算代价，而且对流数据到达的顺序敏感.基于密度的数据流聚类方法可以发现任意形状的类簇，但是算法需要预设较多参数.基于网格的数据流聚类方法运行速度较快，也可以发现任意形状的类簇，但是其聚类质量取决于选取的网格粒度.基于模型的数据流聚类方法包含了很多领域知识并强依赖于假设模型，例如SWEM算法基于EM模型、GCPSOM算法基于SOM模型、G-Stream和RPG-Stream算法均基于GNG模型.从表1我们发现，在线(联机)学习算法是处理数据流聚类的一个很好策略，可以解决数据流约束中的一次扫描，实时响应和有限内存问题.STREAM[10]，REPSTREAM[15]，ACSC[17]，incPre-Decon[19]，SWEM[23]，GCPSOM[24]，G-Stream[25]和RPGStream[26]均为在线学习算法，但只有REPSTREAM，ACSC，SWEM，GCPSOM，G-Stream和RPGStream可以处理概念漂移，即此算法能够随着数据的流动更新新来的概念并移除旧的概念.GCPSOM,G-Stream和RPGStream不仅可以解决数据流挖掘中的各类约束，同时可以发现数据的拓扑结构，它们分别基于SOM(self-organizing maps)和GNG(growing neural gas)模型.但GCPSOM和G -Stream面对高维数据无能为力，据现有资料显示只有HPStream[12],incPre -Decon[19]和RPGStream[26]可以处理高维数据.RPGStream虽然可以处理高维数据，但因其基于GNG模型，超参数较多，调节参数对算法性能影响较大.故本文的直接动机是设计一个可在单机执行、适用于高维数据流的高效数据流聚类算法.

目前解决高维问题的基本方法大致有2种：1)特征选择[27-28]，即从样本集中选取重要的特征子集，不改变原有特征空间；2)特征提取[29-30]，主要通过属性间关系，如组合不同属性得到新的属性，改变了原有特征空间.其中特征提取可进一步分为2类，即数据依赖(data-dependent)和数据独立(data-independent).例如主成分分析(principal component analysis, PCA)作为一种数据依赖的方法，虽可以用于数据流聚类，但时间复杂度通常较高.而随机投影(random projection)作为一种数据独立的方法[31-32]，将高维欧氏空间里的点集映射到低维空间，使得相对距离得到一定误差范围内的保持.考虑到数据流本身的特性，如无界性和动态变化，随机投影可以独立于数据，无疑是高维数据流聚类的首选方法.更重要的是，随机投影不仅计算效率高，而且可以通过使用随机矩阵，例如高斯随机矩阵等，有效降低高维数据的维度.低计算复杂度和对度量结构的近似表达使得将随机投影应用到聚类分析更加有效.近来，许多工作聚焦于将随机投影用于聚类问题.文献[33]将随机投影与K-Means算法结合聚类；文献[34]证明了任何含有n个样本d维特征(矩阵A=Rn×d)的集合都可以被投影到t=Ω(k/ε2)维空间，对于任何ε∈(0,1/3)，在O(nd×ε2klog(d))时间下，2+ε范围内最优k-划分被保留.文献[35-36]给出了如何利用JL引理(Johnson-Lindenstrauss)将数据投影到O(nd×log(k)ε2)维，并完成一个(9+ε)的近似保持.然而他们均聚焦于处理高维数据(d很大)，并没有考虑n也很大的场景.此外，基于随机投影，文献[37]探索了基于SLC和ALC链接以及最小扩展树(minimum spanning tree, MST)的快速层次聚类.同时文献[38]将随机投影与密度聚类相结合.文献[39-41]使用随机投影集成和迭代的方法对高维数据聚类.

为解决高维数据流聚类问题(n和d均很大)，本文提出了一种基于随机投影的高维数据流聚类算法RPFART.首先通过随机投影将原始高维数据映射到低维数据空间，再使用ART模型[42]进行数据流聚类.ART具有线性计算复杂度，且仅使用1个超参数，并对参数设置鲁棒.虽然将随机投影用于K-Means算法可以分析理论最差界，但由于ART本身的复杂性我们无法分析RPFART的最差界.所以，本文中我们使用大量实验分析RPFART算法的聚类性能.多个数据集上的实验结果表明:即使原始尺寸压缩到10%，RPFART算法仍可以达到与RPGStream算法相当甚至更好的性能.对于ACT1数据集，其维数从67 500减少到6 750.

1 相关工作

1.1 数据流聚类与ART

设数据流为一个带有时间戳(time stamp)的多维数据点集合，实际应用中n的取值可以无限大，其中每个数据点是一个包含d维的数据记录，其到达时间为ti.数据流本身具有无限、时序、动态性.数据流聚类将数据对象集合中相似对象划分为一个或多个簇，划分后同一簇中元素彼此相似，但与其他簇中元素相异.

自组织神经网络是人工智能领域应用最为广泛的一种学习模型.为解决大部分神经网络模型遭遇的“稳定性-弹性问题”，美国Boston大学的Grossberg和Carpenter于1976年提出了一种无监督竞争型神经网络模型，即自适应谐振理论网络(adaptive resonance theory, ART)[43]，可在稳定原有模式类的前提下学习新的模式.ART模拟了人类大脑如何捕捉、识别、记忆关于事物和事件的信息.随着理论的不断完善，学者们提出了大量基于ART改进的无监督学习模型，如ART1[44],ART2[45],ART2-A[46],ART3[47]和模糊ART(fuzzy ART)[42].模糊ART通过在类别空间实时搜索和匹配现有类簇，增长式地逐步处理每一个输入模式，是本文研究的基本模型.警戒参数(vigilance parameter)用于约束在同一个类簇中模式的最小相似度.当输入模式与现有类簇都不相似时，则生成一个新的类簇来编码这个新模式.模糊ART已用于解决图像和文本挖掘问题，如Web文档管理、基于标记的Web图像组织、图像-文本关联，但还未用于数据流聚类.

模糊ART模型由输入层F1和识别层F2组成，如图1所示.输入层F1包含的输入向量I被提交到网络，与识别层F2中各个类簇的权值向量进行相似度比较并归类.

1) 输入向量(input vector).设I=xi表示输入层F1的输入模式，其中通过补编码(complement coding),xi与它的补向量共同构成了

2) 权值向量(weight vector).设wj表示识别层F2中第j个类cj(j=1,2,…,J)的权值.

3) 参数(parameter).模糊ART随着3个参数动态改变，它们分别是选择参数α>0、学习参数β∈[0,1]、以及警戒参数ρ∈[0,1].

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

步骤1. 类别选择(category choice).对每个输入模式I，模糊ART根据选择函数计算此输入对识别层F2中的每个类簇的选择值，并取具有最大值的类簇作为获胜类簇cj*.第j个类簇cj的选择函数定义为

(1)

这里，模糊与操作∧定义为(p∧q)i≡min(pi,qi)，范式|·|定义为

步骤2. 模板匹配(template matching).输入模式I与获胜类簇cj*使用匹配函数Mj*进行评估，Mj*定义为

(2)

如果获胜类簇cj*的Mj*≥ρ，则发生共振(resonance)，引发步骤3——中心学习.否则，返回步骤2，继续在剩下的类簇中寻找一个获胜类簇.如果所有选出的获胜类簇均不满足Mj*≥ρ，则生成一个新的类簇来编码这个输入模式I.

步骤3. 中心学习(prototype learning).如果获胜类簇cj*的Mj*≥ρ，根据式(3)更新其权值向量wj*.

(3)

1.2 随机投影

随机投影中，原始的d维数据通过随机矩阵Rd×dc被投影到dc(dc≪d)维子空间.样本矩阵Xn×d(n个样本，d维特征)投影到

(4)

随机投影的理论依据是JL引理[31]：高维欧氏空间里的点集映射到低维空间，其相对距离得到一定误差范围内的保持.

定理1[41]. 设样本矩阵X∈n×d包含n个样本d维特征.给定ε,β>0,则:

(5)

这里参数ε控制距离保持的精度，β控制投影成功的概率.dc是一个正整数，且dc≥k0，随机矩阵R是一个d×dc矩阵，R(i,j)=rij,rij是一个独立的随机变量，可以由3种概率分布生成：

rij～N(0,1);

(6)

(7)

(8)

设d→dc将X的第i行映射到E的第i行.

对所有的u,v∈X，在至少1-n-β概率下:

(9)

从式(9)可以看出，理论上JL界(k0)不依赖于原始空间的维度d，为了得到定理1的结果，我们只需要通过一个简单的概率分布生成随机矩阵R，同时进行投影计算.

通过假设输入数据的期望为0，在主成分分析的激励下，文献[41]给出结论：根据概率上的方差分析，压缩后的数据获得了原始数据的全部可变性.首先，压缩后的数据可以从低维数据中获得很多信息，因为这些低维都是线性无关的.其次，原始数据维度的方差之和等于投影后数据维度的方差之和.

定理2[41]. 设矩阵X∈n×d是包含n个d维独立样本的随机向量(X1,X2,…,Xd)，S表示X的样本协方差矩阵.一个随机投影矩阵R∈d×dc将d维随机向量映射到dc维随机向量Y，(Y1,Y2,…,Ydc)=表示的投影后数据Y的协方差矩阵.如果随机投影矩阵R服从定理1所要求的分布，且与随机向量(X1,X2,…,Xd)相互独立，则：

1) 投影数据的维度是相互独立的.

Cov(Yi,Yj)=0,∀i≠j;

2) 随机投影保持了可变性.

当dc→,概率为1，tr(S*)=tr(S).

利用上述性质，已有相关工作验证了将随机投影应用于聚类问题的可行性.Boutsidis等人[33]首次将随机投影与k-Means结合进行聚类;吴等人[34]和Schneider等人[37]针对SLC和ALC聚类以及最小生成树(MST)问题，探索了基于随机投影的快速层次聚类算法.同时Schneider和Vlachos[38]通过使用随机投影来扩展基于密度的聚类，并提出了显著提高学习效率的算法.Ferns和Brodley[39]、Cardoso和Wichert[40]、叶等人[41]提出了使用随机投影对高维数据聚类的集成模型和迭代模型.

2 基于随机投影的数据流聚类算法

2.1 RPFART算法

鉴于随机投影的优良性质，我们提出了一种基于随机投影的数据流聚类算法RPFART.直觉上，通过在低维空间对数据进行聚类，不仅可以大大降低每次模糊ART迭代的计算成本，还可以在原始高维空间中找到与之相关的解决方案.假设有一个数据流序列(实际应用中n的取值可以无限大)，其中每个数据点是一个包含d维的数据记录，其到达时间为ti.RPFART生成了包含一系列节点(nodes)的结构，其中节点代表类簇(cluster),且每个节点均包含相关的权值向量

RPFART算法首先依据dc的大小生成随机投影矩阵R，当一个新的数据点xi到达时，用R将xi投影到对应的dc维(dc≪d)点yi.从而整个数据流被投影到再对使用模糊ART进行聚类.具体见算法1.

算法1. RPFART算法.

输入：

输出：节点集合C={c1,c2,c3,…}及其权值

① 生成满足定理1的随机矩阵Rd×dc(dc≪d);

② for each xi

③ yi=xi×R；

④ 对yi使用模糊ART算法进行聚类；

⑤ end for

2.2 算法复杂度分析

算法1中最耗时的运算是步骤③和步骤④.可以看出随机投影在计算上非常简单，可以快速生成，故步骤③的投影时间复杂度为O(nddc).模糊ART算法包含了类别选择、模板匹配、中心学习3个主要步骤，每个步骤的时间复杂度分别为O(d)，O(md)，O(d)，给定n个输入样本，总体时间复杂度为O(nmd)，其中m是聚类结果中节点个数.故步骤④的时间复杂度为O(nmdc).RPFART算法的总体时间复杂度为O(nddc+nmdc).

3 实验与结果

为了验证本文提出算法的有效性，我们在5个数据集上与现有数据流聚类算法RPGStream进行了比较.实验使用的计算机配置为Intel Core i5-6300U 2.4 GHz处理器和8 GB内存，Windows 10操作系统，所有比较程序均在MATLAB R2015a上设计和运行.

3.1 聚类评价指标

为了对各种聚类算法性能进行评价，我们引入了3项评价指标[26]：1)accuracy(purity);2)NMI(normalized mutual information);3)RI(rand index).

1) Accuracy(Purity)

(10)

其中，K表示类簇个数，表示在类簇i中的样本点数，|Ci|表示类簇i中真实的样本个数.因此，Accuracy度量了聚类的平均纯度，Accuracy越大表明聚类纯度越高.其取值范围在0～1之间.

2) NMI(normalized mutual information)

归一化互信息NMI是一个量化2个分布之间共享统计信息的对称策略.当类簇标签和真实样本类别一对一映射时NMI值到达最大值1.0.给定真实类簇A={A1,A2,…,Ak}和某聚类算法得到的类簇B={B1,B2,…,Bh}，混淆矩阵C中的元素Cij表示即在Ai又在Bj中的样本个数.NMI计算为

NMI(A,B)=

(11)

其中，CA(CB)表示A(B)中样本个数,Ci.(C.j)表示C中i行元素和(C中j列元素和)，N表示样本个数.

3) RI(rand index)

RI比较n×(n-1)/2个数据对，其中n为数据集中样本个数，P1，P2为2种聚类算法，n11为数据对(xi,xj)在P1，P2中划分为同一类的数据对数，n00则为(xi,xj)隶属不同类的数据对数，RI错误率计算为

(12)

由式(12)可得RI∈[0,1]，当P1与P2划分完全一致时RI=1.

3.2 数据集和参数设置

为了对RPFART算法的聚类有效性进行评价，实验中我们使用了人工和真实数据集，表2给出数据集的相关信息：

HyperPlan数据集是人工模拟数据集.HyperPlan是一个含有概念漂移的数据流，包含5个类共10万个样本，每个样本5维.KddCup99，CoverType和ACT均来自UCI.KddCup99数据集最早来源于MIT林肯实验室的一项入侵检测评估项目,记录了9周内TCP网络连接和系统审计数据,仿真各种不同的用户类型、网络流量和攻击手段.这些原始数据包含约50万条连接记录的训练集.每个连接记录包含41个属性，这些连接记录含1种正常的标识类型和22种训练攻击类型共23个类别.CoverType数据集来源于US Geological Survey (USGS)和US Forest Service (USFS)对位于Roosevelt国家森林的四片荒野区域的观测.数据集中包含581 012条记录,这些记录最终被分为7种类型.每条观测记录包含54个地质学和地理学属性.ACT(The Daily and Sports Activities Data Set)数据集包含45个传感器在5 min内以25 Hz的采样频率收集的19项活动的数据.为了获得高维数据集，我们分别将1 min和5 s的活动数据处理为一个样本，结果得到了760×67 500(ACT1)和9 120×5 625(ACT2)数据矩阵.

由算法1所示，RPFART算法需要设置警戒参数ρ和压缩率r.RPGStream算法设置εb=0.01、εn=0.001、β=300(ACT1取30)、λ1=0.2、λ2=0.2、|windows|=600(ACT1取60)、|reservoir|=400(ACT1取50)、agemax=250(代表边年龄的最大值)、weightmin=2(代表神经元节点权值的最小值)，并且每次插入新节点的个数NbNodesInserted=3.

3.3 聚类性能比较

首先评估RPFART的聚类质量，并将其与RPGStream算法在5个数据集上进行比较.每个算法重复实验10次.聚类结果如表3～5所示.参数r表示压缩率，例如对于KddCup99数据集，r=90%表示通过随机投影将特征数减少到54×0.9=48.

从表3～5中我们可以发现：1)RPFART在使用了随机投影后，总体上与RPGStream的结果相当，特别是NMI和Rand指数在所有数据集上均超过了RPGStream.2)RPFART在HyperPlan和ACT2数据集上的聚类纯度略低于RPGStream.3)即使设置一个小的r，例如r=10%，RPFART在ACT1上的聚类纯度、NMI和Rand指数仍然是最好的.4)我们的算法不限于海量数据，即使对高维小样本也可以得到很好的结果，如在ACT1数据集上取得了较好的效果.

为了进一步证明RPFART的性能，我们分别在5个数据集上与离线聚类算法RPK-Means和PCAFART进行了比较.PCAFART算法是将模糊ART与PCA结合对数据流进行聚类.其结果如表6～8所示.

从表6～8中我们可以发现：1)RPFART在精度、NMI、Rand指数都优于KddCup99，CoverType，ACT2，ACT1数据集上的RPK-Means.2)RPFART与PCAFART具有相当的聚类结果，但后者在处理高维ACT1数据集时，出现内存耗尽溢出问题.因此，我们可以得出RPFART更适合于高维数据，同时结合随机投影和模糊ART是可行和有前途的.此外，RPFART的方差比其他方法略小，这表明它相对稳定.除了随机投影，PCA也可以用来降维，但当我们想将PCA与模糊ART结合用于ACT1数据集时，算法因为内存不足而停止.

3.4 运行时间比较

图2显示了r=50%时的5个数据集上RPFART和RPGStream的运行时间.

从图2可以看出：1)RPFART和RPGStream的执行时间都随着数据量的增加而增加.2)随着样本数的增加RPFART比RPGStream更快.研究表明，RPFART算法对大规模、高维数据的处理效率更高.

3.5 随机矩阵的选择

由于RPFART是基于随机投影的，所以直观地说，随机矩阵R的类型选择将在一定程度上对聚类性能产生影响.因此，为分析其影响，我们使用不同类型的随机矩阵进行实验，典型的有高斯分布(式(6))、均匀分布(式(7))和稀疏分布(式(8))随机矩阵.我们还利用Gram Schmidt方法对上述随机矩阵进行正交实验.所有实验均在HyperPlan,Kddcup99,CoverType,ACT2上进行，重复10次，r=50%.结果如表9所示.结果表明，正交后RPFART算法在聚类纯度、NMI和Rand指数上比非正交算法较优.然而，正交化并不免费，计算上十分昂贵.有趣的是，Hecht-Nielsen[48]证明高维空间中存在大量几乎正交(而不是严格正交)的方向，即具有随机方向的一系列向量同样可以是有效正交，从而其可作为一组基的近似.

3.6 处理非平稳数据能力

本节研究RPFART在非平稳数据流聚类中的有效性.许多实际应用程序中，数据通常随着时间演变，即具有非平稳性.例如，第1个类的数据点全部到达后，第2个、第3个类的数据点才依次按类别到达.这种情况下，旧的概念消失，同时新的概念随着新的数据点的到来而出现，从而导致概念漂移.因此我们分别将RPFART在类排序(按类标签)和类未排序的数据流上进行聚类，重复实验10次.图3～5显示了RPFART的聚类纯度、NMI和Rand指数.

从图中可以看出：1)RPFART在类排序数据集上可以找到与类未排序数据集上相当的聚类纯度、NMI和Rand指数.特别是ACT2和ACT1数据集上甚至更优.2)仅KddCup99数据集上RPFART的聚类纯度值略有下降.基于以上结果，我们可以得出结论，不管数据是否按类标签排序到达，RPFART均可以有效地处理概念漂移问题.

3.7 警戒参数ρ的变化

图6显示了r=50%时RPFART在5个数据集上随警戒参数ρ的变化聚类性能的变化.

从图6可以看出：1)5个数据集上聚类纯度均随参数ρ的增大到达一定值后有所下降；2)在HyperPlan,CoverType,ACT2这3个数据集上NMI和Rand指数都随参数ρ的增大稳步增长，但KddCup99和ACT1数据集有下降趋势.

4 结 论

本文基于随机投影提出了高维数据流聚类算法RPFART.首先通过随机投影将原始高维数据映射到低维数据空间，再使用ART模型进行数据流聚类.ART具有线性计算复杂度，仅使用1个超参数，并对参数设置鲁棒.文中使用大量实验分析RPFART算法的聚类性能.多个数据集上的实验结果表明，即使原始尺寸压缩到10%，RPFART算法仍可以达到与RPGStream算法相当甚至更好的性能.对于ACT1数据集，其维数从67 500减少到6 750.

参考文献

[1]Nguyen H L, Woon Y K, Ng W K. A survey on data stream clustering and classification[J]. Knowledge and Information Systems, 2015, 45(3): 535-569

[2]Gaber M M, Zaslavsky A, Krishnaswamy S. Mining data streams: A review[J]. ACM Sigmod Record, 2005, 34(2): 18-26

[3]Gama J, Rodrigues P P. An overview on mining data streams[M] //Foundations of Computational, Intelligence Volume 6. Berlin：Springer, 2009: 29-45

[4]Aggarwal C C. Data streams: An overview and scientific applications[M] //Scientific Data Mining and Knowledge Discovery. Berlin: Springer, 2009: 377-397

[5]Silva J A, Faria E R, Barros R C, et al. Data stream clustering: A survey[J]. ACM Computing Surveys, 2013, 46(1): 1-31

[6]Li Yangyang, Yang Guoli, He Haiyang, et al. A study of large-scale data clustering based on fuzzy clustering[J]. Soft Computing, 2016, 20(8): 3231-3242

[7]Zhang Pu, Shen Qiang. Fuzzy c-means based coincidental link filtering in support of inferring social networks from spatiotemporal data streams[J]. Soft Computing, 2018, 22(21): 7015-7025

[8]Carnein M, Assenmacher D, Trautmann H. An empirical comparison of stream clustering algorithms[C] //Proc of the Computing Frontiers Conf. New York: ACM, 2017: 361-366

[9]Carnein M, Trautmann H. Optimizing data stream representation: An extensive survey on stream clustering algorithms[J]. Business & Information Systems Engineering, 2019, 61(3): 277-297

[10]O’callaghan L, Mishra N, Meyerson A, et al. Streaming-data algorithms for high-quality clustering[C] //Proc of the 18th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2002: 685-694

[11]Aggarwal C C, Han J, Wang J, et al. A framework for clustering evolving data streams[C] //Proc of the 29th Int Conf on Very Large Data Bases. Berlin: VLDB Endowment, 2003: 81-92

[12]Aggarwal C C, Han J, Wang J, et al. A framework for projected clustering of high dimensional data streams[C] //Proc of the 30th Int Conf on Very Large Data Bases. Berlin: VLDB Endowment, 2004: 852-863

[13]Zhou Aoying, Cao Feng, Qian Weining, et al. Tracking clusters in evolving data streams over sliding windows[J]. Knowledge and Information Systems, 2008, 15(2): 181-214

[14]Udommanetanakit K, Rakthanmanon T, Waiyamai K. E-stream: Evolution-based technique for stream clustering[C] //Proc of the Int Conf on Advanced Data Mining and Applications. Berlin: Springer, 2007: 605-615

[15]Lühr S, Lazarescu M. Incremental clustering of dynamic data streams using connectivity based representative points[J]. Data & Knowledge Engineering, 2009, 68(1): 1-27

[16]Cao F, Estert M, Qian W, et al. Density-based clustering over an evolving data stream with noise[C] //Proc of the 2006 SIAM Int Conf on Data Mining. Bethesda: Society for Industrial and Applied Mathematics, 2006: 328-339

[17]Fahy C, Yang S, Gongora M, et al. Ant colony stream clustering: A fast density clustering algorithm for dynamic data streams[J]. IEEE Transactions on Systems, Man, and Cybernetics, 2019, 49(6): 2215-2228

[18]Tasoulis D K, Ross G, Adams N M. Visualising the cluster structure of data streams[C] //Proc of Int Symp on Intelligent Data Analysis .Berlin: Springer, 2007: 81-92

[19]Kriegel H P, Kröger P, Ntoutsi I, et al. Density based subspace clustering over dynamic data[C] //Proc of Int Conf on Scientific and Statistical Database Management. Berlin: Springer, 2011: 387-404

[20]Chen Yixin, Tu Li. Density-based clustering for real-time stream data[C] //Proc of the 13th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2007: 133-142

[21]Wan L, Ng W K, Dang X H, et al. Density-based clustering of data streams at multiple resolutions[J]. ACM Transactions on Knowledge Discovery from Data, 2009, 3(3):1-28

[22]Park N H, Lee W S. Statistical grid-based clustering over data streams[J]. ACM Sigmod Record, 2004, 33(1): 32-37

[23]Dang X H, Lee V, Ng W K, et al. An EM-based algorithm for clustering data streams in sliding windows[C] //Proc of Int Conf on Database Systems for Advanced Applications. Berlin: Springer, 2009: 230-235

[24]Smith T, Alahakoon D. Growing self-organizing map for online continuous clustering[M] //Foundations of Computational Intelligence Volume 4. Berlin: Springer, 2009: 49-83

[25]Ghesmoune M, Lebbah M, Azzag H. A new growing neural gas for clustering data streams[J]. Neural Networks, 2016, 78(1): 36-50

[26]Zhu Yingwen, Chen Songcan. Growing neural gas with random projection method for high-dimensional data stream clustering[J]. Soft Computing, 2020, 24(13): 9789-9807

[27]Agrawal R, Gehrke J, Gunopulos D, et al. Automatic subspace clustering of high dimensional data for data mining applications[C] //Proc of the 1998 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 1998: 94-105

[28]Dy J G, Brodley C E. Feature subset selection and order identification for unsupervised learning[C] //Proc of Int Conf on Machine Learning. New York: ACM, 2000: 247-254

[29]Webb A R. Statistical pattern recognition[M]. New York: John Wiley & Sons, 2003

[30]Keogh E, Chakrabarti K, Pazzani M, et al. Locally adaptive dimensionality reduction for indexing large time series databases[C] //Proc of the 2001 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2001: 151-162

[31]Johnson W B, Lindenstrauss J. Extensions of Lipschitz mappings into a Hilbert space[J]. Contemporary Mathematics, 1984, 26(1): 189-206

[32]Achlioptas D. Database-friendly random projections: Johnson-Lindenstrauss with binary coins[J]. Journal of Computer and System Sciences, 2003, 66(4): 671-687

[33]Boutsidis C, Zouzias A, Drineas P. Random projections for k-means clustering[C] //Advances in Neural Information Processing Systems. New York: Curran Associates, 2010: 298-306

[34]Wu X, Kumar V, Quinlan J R, et al. Top 10 algorithms in data mining[J]. Knowledge and Information Systems, 2008, 14(1): 1-37

[35]Cohen M B, Elder S, Musco C, et al. Dimensionality reduction for k-means clustering and low rank approximation[C] //Proc of the 47th Annual ACM Symp on Theory of Computing. New York: ACM, 2015: 163-172

[36]Musco C N. Dimensionality reduction for k-means clustering[D]. Boston: Massachusetts Institute of Technology, 2015

[37]Schneider J, Vlachos M. On randomly projected hierarchical clustering with guarantees[C] //Proc of the 2014 SIAM Int Conf on Data Mining. Society for Industrial and Applied Mathematics. Philadelphia: SIAM, 2014: 407-415

[38]Schneider J, Vlachos M. Fast parameterless density-based clusteringvia random projections[C] //Proc of the 22nd ACM Int Conf on Information & Knowledge Management. New York: ACM, 2013: 861-866

[39]Fern X Z, Brodley C E. Random projection for high dimensional data clustering: A cluster ensemble approach[C] //Proc of the 20th Int Conf on Machine Learning (ICML-03). New York: ACM, 2003: 186-193

[40]Cardoso , Wichert A. Iterative random projections for high-dimensional data clustering[J]. Pattern Recognition Letters, 2012, 33(13): 1749-1755

[41]Ye Mao, Liu Wenfen, Wei Jianghong, et al. Fuzzy-means and cluster ensemble with random projection for big data clustering[J]. Mathematical Problems in Engineering, 2016, 2016(1): 1-13

[42]Carpenter G A, Grossberg S, Rosen D B. Fuzzy ART: Fast stable learning and categorization of analog patterns by an adaptive resonance system[J]. Neural Networks, 1991, 4(6): 759-771

[43]Grossberg S. How does a brain build a cognitive code[J]. Psychological Review, 1980: 87(1): 1-51

[44]Carpenter G A, Grossberg S. A massively parallel architecture for a self-organizing neural pattern recognition machine[J]. Computer Vision, Graphics, and Image Processing, 1987, 37(1): 54-115

[45]Carpenter G A, Grossberg S. ART 2: Self-organization of stable category recognition codes for analog input patterns[J]. Applied Optics, 1987, 26(23): 4919-4930

[46]Carpenter G A, Grossberg S, Rosen D B. ART 2-A: An adaptive resonance algorithm for rapid category learning and recognition[J]. Neural Networks, 1991, 4(4): 493-504

[47]Carpenter G A, Grossberg S. ART 3: Hierarchical search using chemical transmitters in self-organizing pattern recognition architectures[J]. Neural Networks, 1990, 3(2): 129-152

[48]Robert Hecht-Nielsen. Context vectors: General purpose approximate meaning representations self-organized from raw data[J]. Computational Intelligence: Imitating Life, 1994: 43-56

High Dimensional Data Stream Clustering Algorithm Based on Random Projection

Zhu Yingwen1,2,3 and Chen Songcan1,2

1(College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 211106)2(MIIT Key Laboratory of Pattern Analysis and Machine Intelligence (Nanjing University of Aeronautics and Astronautics), Nanjing 211106)3(College of Computer Science and Engineering, Sanjiang University, Nanjing 210012)

Abstract High dimensional data streams emerge ubiquitously in many real-world applications such as network monitoring. Clustering such data streams differs from traditional data clustering algorithm where the given datasets are generally static and can be read and processed repeatedly, thus facing more challenges due to having to satisfy such constraints as bounded memory, single-pass, real-time response and concept-drift detection. Recently many methods of such type have been proposed. However, when dealing with high dimensional data, they often result in high computational cost and poor performance due to the curse of dimensionality. To address the above problem, in this paper we present a new clustering algorithm for data streams, called RPFART, by combining the random projection method with the adaptive resonance theory (ART) model that has linear computational complexity, uses a single parameter, i.e., the vigilance parameter to identify data clusters, and is robust to modest parameters setting. To gain insights into the performance improvement obtained by our algorithm, we analyze and identify the major influence of random projection on ART. Although our method is embarrassingly simple just by incorporating the random projection into ART, the experimental results on variety of benchmark datasets indicate that our method can still achieve comparable or even better performance than RPGStream algorithm even if the raw dimension is compressed up to 10% of the original one. For ACT1 dataset, its dimension is reduced from 67 500 to 6 750.

Key words high dimensional data; data stream clustering; random projection; adaptive resonance theory; clustering

中图法分类号 TP391

收稿日期：2020-06-16；修回日期：2020-07-03

基金项目：国家自然科学基金重点项目(61732006)

This work was supported by the Key Program of National Natural Science Foundation of China (61732006).

通信作者：陈松灿(s.chen@nuaa.edu.cn)

Zhu Yingwen, born in 1982. PhD candidate with the College of Computer Science & Technology, Nanjing University of Aeronautics and Astronautics (NUAA). Student member of CCF. Received her BSc and MSc degrees in computer science & technology from Nanjing Normal University in 2005 and 2008. Her main research interests include data mining and machine learning.

Chen Songcan, born in 1962. Professor and PhD supervisor. Senior member of CCF. His main research interests include pattern recognition, machine learning and neural computing.