基于情节记忆的高效短文本流聚类算法.pdf

第 49卷 第 10期2023年 10月Computer Engineering 计算机工程基于情节记忆的高效短文本流聚类算法刘子健1，王勇2，刘媛妮3，周由胜1，3（1.重庆邮电大学 计算机科学与技术学院，重庆 400065；2.大唐微电子技术有限公司，北京 100094；3.重庆邮电大学 网络空间安全与信息法学院，重庆 400065）摘要：现有基于相似度的短文本流聚类算法多数需要手动设置相似度阈值，且难以处理文本稀疏性问题。针对短文本流的特点和传统流聚类算法的局限性，提出基于情节记忆的短文本流聚类算法。将情节记忆思想融入流聚类算法，通过稀疏经验重放增强聚类的特征表示，并使用反向索引提高聚类效率。在线阶段通过新的相似度计算公式以及动态计算相似度阈值，将当前文本分配到现有集群或新集群，并且不断更新聚类特征。离线阶段通过聚类增强、语义再分配以及删除过时聚类，提高整体算法性能。基于公开和合成数据集的实验结果表明，相较于基准流聚类算法，所提算法在各项评价指标上均取得了较好的实验结果，并且对于文本数量较大的数据集，运行时间能减少 13个数量级。关键词：文本流聚类；短文本流；情节记忆；主题演化；文本特征开放科学（资源服务）标志码（OSID）：中文引用格式：刘子健，王勇，刘媛妮，等.基于情节记忆的高效短文本流聚类算法 J.计算机工程，2023，49（10）：145-153.英文引用格式：LIU Z J，WANG Y，LIU Y N，et al.Efficient clustering algorithm of short text streams based on episodic memory J.Computer Engineering，2023，49（10）：145-153.Efficient Clustering Algorithm of Short Text Streams Based on Episodic MemoryLIU Zijian1，WANG Yong2，LIU Yuanni3，ZHOU Yousheng1，3（1.College of Computer and Science and Technology，Chongqing University of Posts and Telecommunications，Chongqing 400065，China；2.Datang Microelectronics Technology Co.，Ltd.，Beijing 100094，China；3.College of Cyberspace Security and Information Law，Chongqing University of Posts and Telecommunications，Chongqing 400065，China）【Abstract】Most existing similarity-based short text stream clustering algorithms must manually set the similarity threshold，and it is difficult to solve the problem of text sparsity.Aiming at the characteristics of short text streams and the limitations of traditional stream clustering algorithms，a novel clustering algorithm of short text streams based on episodic memory is proposed.First，the idea of episodic memory is integrated into the stream clustering algorithm，and then，the feature representation of clustering is enhanced by sparse experience replay，and the clustering efficiency is improved by using reverse index.In the online stage，the current text is allocated to the existing cluster or new cluster via the new similarity calculation formula and the dynamic calculation of similarity threshold，and the clustering features are updated constantly.In the offline phase，the overall algorithm performance is improved through a clustering enhancement algorithm，semantic redistribution algorithm，and deleting outdated clustering algorithms.An experimental analysis based on public data sets and composite data sets shows that the proposed algorithm achieves better experimental results on various evaluation indicators compared with the benchmark stream clustering algorithms；for data sets with a large number of texts，the running time can be reduced by 1-3 orders of magnitude.【Key words】text stream clustering；short text stream；episodic memory；topic evolution；text featureDOI：10.19678/j.issn.1000-3428.0065972基金项目：国家自然科学基金（62272076）；重庆市自然科学基金面上项目（cstc2020jcyj-msxmX0343，cstc2020jcyj-msxmX1021）；重庆市教委科学技术研究项目（KJZD-K20200602）。作者简介：刘子健（1999），男，硕士研究生，主研方向为数据挖掘；王 勇，高级工程师、硕士；刘媛妮，副教授、博士；周由胜，教授、博士。收稿日期：2022-10-11 修回日期：2022-12-06 Email：人工智能与模式识别文章编号：1000-3428（2023）10-0145-09 文献标志码：A 中图分类号：TP3112023年 10月 15日Computer Engineering 计算机工程0概述 随着互联网技术的快速发展，社交媒体平台上每 天 都 涌 现 出 海 量 的 短 文 本 数 据，例 如 微 博、Twitter、新闻网站等。随着时间推移这些源源不断产生的短文本数据形成了短文本流。近年来，短文本流聚类受到较多的关注，广泛应用于热点话题检测1、事件检测与追踪2、新闻推荐3等任务。但由于短文本流具有无限长、特征稀疏、多歧义、主题演化等特性，对其进行聚类仍是一个很大的挑战。与 K-means4、高斯混合模型5、谱聚类6等传统聚类算法不同，流聚类算法根据所采用的技术可分为基于相似度的流聚类算法和基于模型的流聚类算法。基于相似度的短文本流聚类算法大多使用向量空间模型来表示文档，通过相似度度量计算文档和聚类之间的相似度，再根据相似度阈值将文档分配给现有聚类或新的聚类。CluStream7是经典的短文本流聚类算法，包括在线微聚类阶段和离线宏聚类阶段，使用金字塔时间框架存储不同时刻的历史微集群，使用改进的 K-means 算法在微集群上进行聚类，获得用户指定数量为 K 的宏集群。之后提出的很多流聚类算法都借鉴了这个框架。DenStream8将微聚类与用于流聚类的密度估计过程相结合，能够在线对离群值和真实数据进行区分，形成任何形状的数据聚类。SHOU 等9建立一个持久摘要模型Sumblr，在 Twitter文本流中将 Tweet压缩成 Tweet特征向量（TCVs）并进行在线维护，模型根据 TCVs 的统计信息将未来的 Tweet 分配到聚类。MStream10计算文档属于现有集群和新集群的概率，并根据这些概率将文档分配给现有集群或新集群，无须设置相似度阈值，能更自然地检测新集群并处理概念漂移问题。RAKIB 等11提出一种利用文本中高频的biterm 项对每批文本中的小部分文本进行聚类的方法，然后利用获得的聚类分配填充 MStream 算法的聚类模型，使用基于统计度量的相似度阈值进行文本分配，在缓解概念漂移问题的同时提升了聚类效率。基于相似度的流聚类算法大多运行速度较快、实时性较好，局限性在于需要手动设置阈值以确定在线文档的主题分配以及难以处理文本稀疏问题。近几年，越来越多的研究人员对基于模型的短文本流聚类算法进行研究。MStream10是一种基于狄利克雷多项式混合模型的短文本流聚类算法，该算法使用了两个狄利克雷先验和，其中，是指文本选择新集群的先验概率，对应于文本选择与共享比其他集群更相似内容集群的先验概率，该算法的变 体 为 MStreamF（删 除 旧 群 体）。DP-BMM12是一 种 基 于 比 特 数 的 短 文 本 流 聚 类 混 合 算 法，与MStreamF类似，该算法的变体为 DP-BMM-FP（删除以前批次中获得的聚类）。OSDM13是一种基于语义增强狄利克雷模型的短文本流聚类算法，它扩展了 MStream 算法，整合了文本和集群之间的常用词，从中获得单词的语义信息，并使用该语义信息计算文本和集群之间的相似性。DCT-L14是一种基于狄利克雷多项式混合模型的短文本流动态聚类算法，它在一个特定的时间戳内为每个短文本分配一个主题（即集群），并使用产生的主题分布作为推断后续文档主题的优先级。OSGM15在计算文本分配概率中引入词共现语义信息，在线地在词汇变化的子空间中动态维护不断变化的活动主题，并且无须通过外部资源来处理术语歧义问题。LAST16是一个终身学习增强短文本流聚类算法，在基于模型的流聚类算法上增加了情节记忆模块，使得聚类算法同时保持基于批处理和基于单遍处理的优点。基于模型的短文本流聚类算法假设文档是由一个混合模型生成的，这个混合模型通过选择一定概率的主题，再从这个主题中选择一定概率的单词生成文档，通常使用吉布斯采样17或 EM 算法18来估计混合模型的参数，局限性在于需要预先指定主题数量，不能处理短文本流中不断发展的未知数量的主题。本文提出一种带情节记忆的短文本流聚类算法。该算法由两个阶段组成：在线聚类和离线聚类。在线聚类阶段将情节记忆思想19融入聚类算法，通过稀疏经验重放增强聚类的特征表示，使得未来文本以更大的概率选择最近的聚类，并采用反向索引计算文本和选定聚类的相似度并分配文档到现有聚类或新的聚类，通过动态阈值处理概念漂移问题。离线聚类阶段采用目前最优的聚类增强算法进行优化，并通过语义再分配算法处理歧义问题，同时根据聚类 id对过时聚类进行删减。1基础知识 1.1情景记忆模块与稀疏经验重放情景记忆模块19用于在内存中存储一些之前处理过的文本。由于内存有限，选择在一定更新间隔内将新文本写入内存。算法在内存中维护一个情节记忆模块，如图 1所示，当连续到达的文档数量达到存储间隔时，就把当前文本添加到情节记忆模块。由于文本流中的文本是按顺序到达的，最开始存入的文本具有更高的过时性，因此当情节记忆模块的大小超过了设置的最大值时，则从后往前删除文本，以保持记忆模块中存储最近的一些文本数据。146第 49卷 第 10期刘子健，王勇，刘媛妮，等：基于情节记忆的高效短文本流聚类算法在聚类过程中，每经过一定的更新间隔从情节记忆模块中选择文本进行经验重放。经验重放将有助于利用过去的文本信息更新这些主题的特征向量，增大这些主题在聚类过程中被选中的概率。但将记忆模块中的文本全部用来经验重放，一方面增加了时间和空间的开销，另一方面太多不相关的文本也会影响聚类结果，因此随机抽取记忆模块中的部分文本进行稀疏经验重放。当到达重放间隔时，在情节记忆模块中随机抽取数量为 E 的文本，并对其进行一次扫描聚类。对这些过去已经处理的文本都只选择一个已经存在的聚类而不是产生一个新聚类。在确定聚类后需要更新聚类对应的词汇特征和语义表示。重放文本用 t表示，更新聚类词汇特征过程如式（1）式（3）所示，更新聚类语义表示过程如式（4）和式（5）所示。nzf=nzf+Ntf f t（1）nz=nz+Nt（2）mz=mz+1（3）Sz=Sz+St（4）Szm=Szmz（5）其中：nzf是聚类z中的特征f对应的频率；Ntf是重放文本 t 中的特征f对应的频率；nz是聚类z的特征数量；Nt是文本 t的特征数量；mz是聚类z的文本数量；Sz是聚类z的聚类向量；St是文本 t的语义向量；Szm是聚类z的聚类中心向量。1.2反向索引在线聚类阶段先在内存中生成聚类 id-特征正向索引，再通过正向索引创建反向索引，如图 2 所示。算法通过反向索引能够找到包括同一特征的聚类 id。反向索引由向量I=lfid表示，其中，lfid是聚类特征中包括特征f的聚类 id 集合。通过计算当前文本和选定具有共同特征聚类的相似度进行聚类。使用反向索引减少文本相似度计算次数，提高算法运行效率。2基于情节记忆的短文本流聚类算法 所提算法主要包括在线聚类和离线聚类两个阶段。整个算法流程如图 3 所示，其中，T 表示当前模型的运行时间，UI表示离线聚类算法运行的更新间隔，通过取余在 UI内执行离线聚类算法。在线聚类阶段包括特征提取、相似度计算、构建聚类模型以及情节记忆模块；离线聚类阶段包括增强聚类、语义再分配和删除过时聚类。从词汇特征和语义两个层面进行文本特征提取。使用 biterm20对文本进行词汇层面特征提取。与 biterm 类似的还有 unigram 和 bigram。unigram 将单个单词作为一个特征，而 bigram 是将连续的两个单词作为一个特征。biterm 对文本预处理后的文本进行分词，然后计算单词列表的笛卡尔积，能够更加全面地提取文本中的词汇特征，提取出的特征数量比其他方法更多。对于单词数量为 k的句子，特征数量为(k(k-1)/2。特征提取过程如式（6）所示：f(k)=wiwjij 1k i j（6）通过词平均法构建文档向量表示文本语义信息，其中词向量可以通过 GloVe 模型21获得。每个聚 类 的 词 汇 特 征 通 过 一 个 向 量F表 示，F=nzfnzmziidz，其中，nzf是聚类z中的特征f对应的频率，nz是聚类z的特征数量，mz是聚类z的文本数图 2聚类 id-特征正/反向索引Fig.2Cluster id-feature forward/reverse index图 1情节记忆模块结构Fig.1Structure of episodic memory module1472023年 10月 15日Computer Engineering 计算机工程量，iidz是聚类z的唯一id。每个聚类的语义表示由聚类向量Sz和聚类中心向量Szm组成。Sz为聚类 z中文本的文档向量求和。Szm由聚类向量除以聚类大小（通过聚类中的文本数量mz表示）计算得到。2.1在线聚类阶段在线聚类阶段基于单遍处理的方法。先对当前文本进行预处理和特征提取，如果已处理的文本数量达到了经验重放间隔 R，则随机选取数量为 E的文本进行稀疏经验重放更新聚类特征，再对当前文本进行聚类。聚类过程根据反向索引选择现有包含该文本特征的聚类，计算文本和选取聚类的相似度，基于统计度量的动态相似度阈值将文本分配到新的聚类或者是现有聚类中。如果处理文本数量达到了存储间隔 T，则将当前文本加入情节记忆模块，并且根据设置的内存大小判断是否删除旧文本。2.1.1文本与聚类相似度计算采取基于共同特征的相似度计算公式计算文本和聚类之间的相似度，计算公式如式（7）所示：Sim(tz)=f t z()Ntf+nzf DfNt+nz（7）其中：Ntf为文本t的特征f对应的频率；Nt为文本t的特征总数。首先对文本t和聚类z之间共同的特征f对应的频 率 求 和，然 后 再 乘 上 一 个 类 似 于 逆 文 档 频 率（Inverse Document Frequency，IDF）的权重Df，计算公式如式（8）所示：Df=loga|z|f z（8）其中：|z|为存在的聚类总数；|f z|为包含特征f的聚类数量；Df的大小能够反映特征f的重要性。如果特征f在聚类中越多出现，那么该特征的重要性越低。2.1.2聚类模型构建当文本 t 被分配到聚类z时更新聚类z的F向量，构建过程如式（1）式（5）所示。如果当前文本没有被分配到一个新的聚类，那么iidz保持不变，否则iidz自增 1，因此最近创建的聚类拥有最高的聚类 id。同时，更新反向索引I，对于文本中的每个特征添加聚类 id到相应的F特征向量中。语义向量更新和文本分配过程如式（9）所示：Sz=Sz+StSzm=Szmziidz=iidz相同聚类中有连续文本max(iidz)+1z Z（9）算法 1 在线聚类算法输入 文本流S=Stt=1、重放间隔 R、重放文本数量 E、写入模块更新间隔 T输出 每个文本的聚类标签ZSt1.for t=1 to do/从短文本流开始2.if t%R=0 then/执行稀疏经验重放3.从 M 中随机选取文本集 E4.通过式（1）和式（2）执行稀疏经验重放5.通过式（1）式（5）更新聚类模型 M6.end if7.通过式（6）提取文本特征8.通过反向索引 I得到与St有相同特征的聚类集 L9.通过式（7）计算St和 L中聚类的相似度Siml10.计算Siml中的最大相似度maxl、相似度均值l和方差l11.if maxl l+l then12.j=cluster index for maxl/获取maxl对应的聚类标签13.ZSt=jth/分配文本聚类标签图 3算法整体流程Fig.3Overall procedure of the algorithm148第 49卷 第 10期刘子健，王勇，刘媛妮，等：基于情节记忆的高效短文本流聚类算法14.else15.分配该文本到一个新聚类16.end if17.通过式（1）式（5）更新聚类模型 M18.if t%T=0 then19.把当前文本St写入情节记忆模块 M20.end if21.return ZSt2.2离线聚类阶段在每个更新间隔内进行离线聚类。离线聚类阶段 主 要 包 括 聚 类 增 强、语 义 再 分 配、过 时 聚 类 删除 3步。2.2.1聚类增强在每个更新间隔内选择一组在线聚类模块获得的聚类，对这些聚类的分布进行增强。聚类的大小对应聚类中文本的数量，选择聚类大小大于+的聚类，和分别为在线聚类结果中所有聚类大小的平均值和方差。文本数量较大的聚类具有更多的异常值，这可能导致未来文本的不正确分配。通过增强较大聚类中的文本分布，将未来文本分配到合适的聚类。采用目前较优的聚类增强算法22，该算法通过迭代分类进行聚类增强，每次迭代生成分别包含非异常值和异常值的训练集和测试集，使用训练集训练分类算法，再使用训练好的模型对测试集进行分类，重复迭代直到每个聚类中文本分布趋于稳定或者达到预设的最大迭代次数。另外，该聚类增强算法的质量在很大程度上取决于初始聚类质量（对应所提算法在线聚类阶段的结果），具体算法过程参考文献 22。2.2.2语义再分配单文本聚类（只包含一个文本的聚类）中的文本与其他聚类没用共享的词汇特征，但这些聚类可能在语义上与其他现有聚类类似，选择这些文本重新分配至其他现有的聚类。通过余弦相似度计算文本和聚类中心的语义相似度，再分别计算相似度的均值 和方差，如果最大的相似度值大于+，则将该文本分配到对应的聚类，否则仍然在原来通过在线聚类阶段得到的聚类中。在进行语义分配后，需要同时更新聚类的词汇特征表示以及语义表示。算法 2 语义再分配算法输入 聚类大小为 1的聚类文本集合 T、词向量字典 D、聚类的语义特征集合字典Sz，Sz，m、文本语义特征向量和SSUM（初始化为 0向量）输出 聚类模型 M1.for t in T do2.对文本 t进行预处理得到单词列表Wt3.for w in Wt do4.SSUM=SSUM+D(w)5.St=SSUMlen()W/得到文本的语义向量6.end for7.通过余弦相似度计算St和已存在聚类的聚类中心向量Sz，m的相似度Simt8.计算Simt中的最大相似度maxt、相似度均值t和方差t9.if maxt t+t then10.获取maxt对应的聚类标签 j11.ZSt=j/修改当前文本聚类标签为 j12.通过式（1）式（5）更新聚类模型并删除原始聚类中的文本 t13.else14.文本 t保留在原始聚类中15.end for2.2.3过时聚类删除根据聚类编号iidz以及聚类大小来删除过时聚类，根据在线聚类算法最近创建的聚类拥有更高的iidz，分别计算聚类编号和聚类大小的均值z、m和方差z、m，删除聚类编号idz小于z-z并且聚类大小小于m-m的聚类对应的F向量和反向索引I中该聚类的信息。算法 3 过时聚类删除算法输入 聚类 id集合iid，z，z Z、聚类大小集合mz，z Z输出 聚类模型 M1.计算iid，z和mz的均值 z、m和方差 z、m2.for z in F do3.if iid，zzz and mzmm then4.Delete Fidz and reverse index lf，idz/删除过时聚类的特/征向量以及反向索引中该聚类信息3实验与结果分析 3.1实验环境与数据集实验环境为 Windows 10 64位操作系统，处理器为 AMD Ryzen 7 4800H CPU，内存为 16.00 GB。使用 PyCharm 2021 实 现 所 提 算 法，调 用 Python 的Sklearn包进行指标统计。在实验中使用 3个公开的短文本数据集。News-T23 和Tweets-T10 数据集分别包含 11 109个新闻标题和 30 322 篇推文，它们分别有152 和 269 个类别。NT11数据集是 News-T 数据集和 Tweets-T 数据集的结合，包括 41 429 篇文本和416个类别，文档的平均长度为 7.97。文本预处理包括将所有字母转化成小写字母、删除停用词以及词干提取。表 1显示了这些短文本数据集预处理之后的统计数据，从平均单词数可以看出这 3 个数据集适用于短文本流聚类。在实验时对数据集进行混乱处理，以检验不同算法在处理顺序随机且不同主题的文本到达时的算法质量。表 1实验数据集基本统计信息 Table 1Basic statistical information of experimental data sets单位：个数据集News-TTweets-TNT文本数11 10930 32241 429聚类数152269416词汇量8 11012 30120 411平均单词数6.237.976.911492023年 10月 15日Computer Engineering 计算机工程3.2评价指标使用 4 种广泛使用的度量指标来评估聚类性能：归一化互信息（Normalized Mutual Information，NMI），准确率（A），同质性（h）和 V-Measure（V）24。NMI 用于评价整体聚类质量，代表聚类分配和文档实际分配组的随机变量共享的统计信息数量。NMI定义如下：NNMI=cknckloga()Nnckncnkcncloga()ncNknkloga()nkN（10）其中：nc是类别 c中文档的数量；nk是聚类 k中文档的数量；nck是既在类别 c 又在聚类 k 中的文档数量；N是数据集中文档的数量。NMI越接近 1，意味着聚类质量越高。准确率用于将聚类结果与数据的实际类别进行比较，测量了所有聚类中正确分配的文档所占的比率。准确率定义如下：A=1NiN(cimap(ki)（11）(xy)=1x=y0 x！=y（12）其中：ki和ci分别表示xi对应的聚类结果和真实标签；表示指示函数；map函数表示最佳类别标记的重现分配，以保证统计结果的正确。一般通过匈牙利算法25实现最佳重分配，从而在多项式时间内求解标签分配问题。准确率越高，意味着聚类效果越好。同质性表示算法从真值组的同一类中获得的聚类成员所占的比例，定义如下：h=1-H(C|K)H(C)（13）H(C|K)=-c=1|Ck=1|Kncknloga(ncknk)（14）H(C)=-c=1|C|ncnloga(ncn)（15）其中：H(C|K)是给定集群划分条件下类别划分的条件熵；H(C)是类别划分的熵；n表示实例总数；nc表示类别c下的实例数；nk表示集群k下的实例数；nck表示类别c中被划分到集群k的实例数。V-Measure基于两个类别之间的条件熵，也就是求已知某一个类别划分后，另外一个类别划分的不确定性程度。不确定性越小，意味着两个类别划分越接近，相应h值或c值越大。完整性衡量了属于同一个真实类别的样本都被分配到同一个簇中的比例的加权平均值。V-Measure 是同质性和完整性的调和平均值，定义如下：V=2 h ch+c（16）c=1-H(K|C)H(K)（17）3.3结果分析将所提算法与以下基准算法进行比较：1）MStream，基于狄利克雷多项式混合模型的短文本流聚类算法有基于批处理和基于单遍处理的两种变体。基于批处理的方法对每一批短文本进行聚类，存储一段时间内产生的所有聚类。通过对同一批文本多次进行吉布斯采样，提高初始聚类结果。基于单遍处理的方法只对文本进行一次聚类。2）MStreamF，是 MStream 的一个带有遗忘规则的变体，只保留有限时间范围内的最新文本，删除以前批次的过时聚类。本文采用基于批处理模式的 MStream 和 MStreamF 算法进行实验，并采用原 始 论 文 中 MStream 和 MStreamF 算 法 的 参 数（=0.03、=0.03）。3）OSDM，基于单遍处理的短文本流聚类算法，将词形语义信息集成到 MStream 算法，以消除短文本流聚类中的术语歧义问题。本文采用原始论文中的参数进行实验（=2 10-3、=4 10-5、=6 10-6)。4）DP-BMM，采用与 MStream 算法类似的方法，利用每个文档构造的词来增强短文本中的单词共现模式。与 MStream 算法的区别在于，DP-BMM 采用基于 biterm 的聚类方法。本文采用原论文中的 DP-BMM 算法参数进行实验（=0.03、=0.03）。5）EStream，采用在线和离线两个阶段进行短文本流聚类，并且通过反向索引计算文本和选定聚类相似度。EStream 算法的参数只有一个 UI，实验中UI设置为 500。将所提算法和以上基准算法进行比较。为了减少误差，对每个数据集取 10次实验结果的平均值作为最终结果。表 2 给出了所提算法与其他算法在3个数据集上的实验结果，其中部分实验结果来源于文献 11，不同数据集的最优结果用加粗字体标示。从实验结果来看，所提算法相比于其他算法具有一定的性能优势，在 3 个数据集上多项评价指标都高于 EStream，证明了改进后的流聚类算法结合情节记忆 模 块 的 有 效 性。值 得 注 意 的 是，所 提 算 法 在News-T 数据集上的归一化互信息指标没达到最优，可能的原因是该数据集的数据量偏小，导致在进行经验重放时能够增强的聚类表示较少。相比之下，DP-BMM 和 MStreamF进行了超参数调优，更好地实现了将文本分配到不同聚类。但是在 NT数据集上，所提算法的归一化互信息、同质性、准确率指标明显高于其他算法，可能的原因是其他算法并没有在 NT数据集上进行超参数调优，而所提算法使用经验重放缓解文本流稀疏性问题，并且通过参数影响实验得到最佳的重放间隔和重放数量。150第 49卷 第 10期刘子健，王勇，刘媛妮，等：基于情节记忆的高效短文本流聚类算法另外，对比所提算法和其他算法的平均运行时间，实验结果如表 3 所示。由表 3 可知，所提算法比MStream、MStreamF、DP-BMM、OSDM 算法的运行时间更短，证明了所提算法通过反向索引优化聚类运行效率的有效性。DP-BMM 算法的运行时间最长，可能的原因是该算法在每个聚类中存储了该聚类所有文本的 biterm 项，使用吉布斯采样选取聚类，而对同一文本多次执行吉布斯采样是一项很耗时的操作。假设文本数量为 M，聚类数量为 K，每个文本的单词个数为 L，执行吉布斯采样的次数为 I，那么DP-BMM 算法的时间复杂度为O(IKML)。由于所提算法包括情节记忆模块和稀疏经验重放，整体聚类次数得到了增加，因此运行时间比 EStream 算法略长。在线聚类阶段计算的是当前文本和选定聚类的相似度，假设每次运行需要挑选聚类个数为 c，稀疏经验重放的数量为 E，因为在线聚类对当前文本只须执行一次，只有产生重放才会再次执行聚类，所以所提算法的时间复杂度为O(M+E)cLL)。本文忽略了离线聚类阶段的运行时间，因为离线聚类阶段只会对一小部分文本进行再次聚类。3.4消融实验本节主要分析内存大小 M、重放间隔 R 和重放文本数量 E 对算法性能的影响。参照 EStream 算法设置在线阶段和离线阶段的更新间隔为 500。采用控制变量法进行实验。3.4.1内存大小对算法性能的影响内存大小是指情节记忆模块中存储的文本数量。图 4 显示了在 News-T、Tweets-T、NT 数据集上不同的内存大小对 NMI 的影响。由图 4 可以看出，随着内存大小的不断增大，NMI数值总体而言也不断增大。因为情节记忆模块中存放着较多的最近文本，更有助于利用过去的文本信息更新主题的特征向量，但内存大小并不是越大越好，可通过验证集来设置一个适合的数值。3.4.2重放间隔对算法性能的影响重放间隔是指稀疏经验重放的文本数量间隔。图 5 显示了在 News-T、Tweets-T、NT 数据集上不同的重放间隔对 NMI 的影响。由图 5 可以看出，随着重放间隔的增加，NMI大体呈现下降趋势，可能的原因是一些聚类的特征会随着时间慢慢减少。过小的重放间隔会使得聚类时间变长，而过大的重放间隔会使得算法的性能降低。表 2各算法在 3个数据集上的实验结果 Table 2Experimental results of each algorithm on three data sets算法MStreamMStreamFOSDMDP-BMMEStream所提算法News-T归一化互信息0.8590.8690.8580.8780.8610.871同质性0.9020.8710.9070.8920.8760.938准确率0.7160.6170.5080.7580.8750.904V-Measure0.8540.8640.8590.8790.8630.876Tweets-T归一化互信息0.8670.8740.8420.8620.8590.885同质性0.8730.8970.9390.8630.8980.908准确率0.6080.5970.5070.7380.8330.831V-Measure0.8590.8710.8460.8650.8520.875归一化互信息0.7980.7430.7910.7620.8840.902NT同质性0.6210.6610.4190.6590.9150.948准确率0.6580.6170.5080.7380.8820.896V-Measure0.7930.7450.7900.7680.8890.882表 3不同算法的平均运行时间 Table 3Average running time of different algorithms单位：s算法MStreamMStreamFOSDMDP-BMMEStream所提算法News-T238169325 016811Tweets-T58631020512 3072426NT81068570318 2205165图 4内存大小对归一化互信息指标的影响Fig.4Influence of the memory size on the normalized mutual information index图 5重放间隔对归一化互信息指标的影响Fig.5Influence of the replay interval on the normalized mutual information index1512023年 10月 15日Computer Engineering 计算机工程3.4.3重放文本数量对算法性能的影响重放文本是指在每个重放间隔内进行经验重放的文本。图 6显示了在 News-T、Tweets-T、NT数据集上不同的重放文本数量对 NMI的影响。由图 6可以看出，随着重放文本数量增加，NMI呈现上升趋势。可能的原因是重放文本数量越多，就会有更多的采样文本被用来更新聚类特征向量。如图 7所示，过少的重放文本会减少聚类的特征数量降低算法的性能，但过多的重放文本会导致算法运行时间变长。4结束语 本文将情节记忆思想融入短文本流聚类算法，提出一种带情节记忆的高效短文本流聚类算法。采用在线-离线阶段对短文本流进行聚类：在线阶段融入情节记忆思想缓解短文本流的稀疏性问题，通过反向索引减少聚类运行时间；离线阶段通过聚类增强、语义再分配以及删除过时聚类来提高聚类性能。通过在 3 个公开数据集上与 6 个基准算法进行实验对比，结果表明所提算法的多项评价指标都取得了较好的结果，并且在运行时间上比多数算法减少13个数量级。通过消融实验可知，不同的记忆内存大小、重放间隔以及重放文本数量对算法性能均有一定的影响。后续可将深度学习模型和词共现矩阵引入短文本流聚类算法，对文本进行深度顺序编码，以提高聚类精度，并将其应用于针对短文本流的新闻推荐等场景进一步拓宽使用范围。参考文献 1 AGGARWAL C C.A survey of stream clustering algorithms M.S.l.：Chapman and Hall，2018.2 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.3 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.4 谢娟英，王艳娥.最小方差优化初始聚类中心的K-means算法 J.计算机工程，2014，40（8）：205-211，223.XIE J Y，WANG Y E.K-means algorithm based on minimum deviation initialized clustering centersJ.Computer Engineering，2014，40（8）：205-211，223.（in Chinese）5 刘攀登，刘清明.稀疏数据中基于高斯混合模型的位置推荐框架 J.计算机工