【基于数据流挖掘的热点事件检测方法实证探究（论文）17000字】

基于数据流挖掘的热点事件检测方法实证研究摘要近年来随着推特、微博等社交媒体平台的不断发展和流行，大众对于社会事件及国家动态的关注度和参与度不断提升，基于这些社交媒体平台的事件检测算法的研究也因此备受关注。由于平台限制、用户的发帖习惯以及事件的发展特性等多方面因素的影响，导致数据包含的信息少、对存储空间及运行速度的要求较高，很难直接利用现有的模型或算法进行事件检测。针对以上问题，本文将概率图模型与数据流挖掘的方法相结合，提出了一种在线的热点事件检测模型，主要研究内容分为三个部分：（1）基于概率图模型对以数据流形式到来的短文本进行聚类；（2）利用数据流挖掘的方法对聚类得到的微簇进行维护；（3）从模型维护的微簇中不断检测出新事件。实验结果表明，模型在推特等平台产生的短文本流数据上有较好的表现。关键词：概率图模型，数据流挖掘，短文本流，在线事件检测目录摘要 IABSTRACT II目录 III第一章绪论 11.1研究工作的背景与意义 11.2时域积分方程方法的国内外研究历史与现状 11.3本文的主要贡献与创新 21.4本论文的结构安排 3第二章研究相关的概念及技术概述 42.1概率图模型（PGM） 42.1.1贝叶斯网络 42.1.2狄利克雷过程 52.2数据流挖掘的基本知识 62.2.1k-means聚类 62.2.2层次聚类 72.3Glove模型 72.4本章小结 8第三章基于数据流挖掘的热点事件检测方法研究 93.1文本文件预处理 93.2基于概率图模型聚类 103.3基于数据流挖掘的方法维护微簇 143.4事件检测 193.5本章小结 20第四章实验结果及分析 214.1实验相关内容 214.1.1实验数据集及评估指标 214.1.2实验采用的参照模型 214.2实验结果及分析 224.3本章小结 27第五章全文总结与展望 285.1全文工作总结 285.2后续工作展望 28参考文献 30第一章绪论1.1研究工作的背景与意义近年来推特、微博这类社交媒体平台不断发展和流行，它们逐渐成为了反映民众生活中各类事件的一面镜子。一项针对记者的调查2017年全球社会新闻研究2017年全球社会新闻研究/us/resources/research-reports/2017-global-social-journalism-study/?sf=false.但是，由于这些平台对发帖长度的限制以及用户的发帖习惯等各方面因素的影响，导致用户发表的帖子一般都比较简短，语言表述也比较生活化，这导致其包含的内容少，可用信息也比较匮乏。同时，因为社会中总是有各种事件不断的产生，且不同的人对于同一事件的表述也存在较大差异，这会给事件的检测和区分带来困难。并且，热点事件产生后总是在不停发酵，事件和相关帖子的数量也是不断增加的，很难直接利用一些主题模型进行事件检测，对数据的存储是一种极大的挑战，也使得模型的可扩展性成为了需要重点攻克的问题。现有的事件检测算法仍没有一个模型能够在解决上述问题的同时体现出事件的演化。但如果能将概率图模型与数据流挖掘结合起来，利用概率图模型的优势在不需要事先确定微簇具体个数的情况下，就能够对不断输入的文本数据进行聚类，不仅减少了阈值设定不恰当带来的影响，而且能够持续的检测新的热点事件，无需对数据进行分片操作；之后再利用数据流挖掘的方法对概率图模型聚类得到的潜在事件微簇进行管理和维护，就能够实现实时检测社会事件演化和发展的目的。而实时在线的事件检测，对于满足大众需求，分析社会发展状况都具有非常重要的现实意义。1.2时域积分方程方法的国内外研究历史与现状事件检测作为热点事件检测、舆情检测等热门研究的基础，一直以来都受到广大研究者的关注。早先有D.M.Blei等人提出的动态主题模型（DTM）[1]、X.Wei等人提出的动态混合模型（DMM）[2]，他们均是基于LDA主题模型[3]的基础上进行了改进，提出了可用于长文档数据集上的动态事件检测算法。但是随着推特、微博等社交媒体的发展和流行，基于这些社交媒体平台的事件检测开始吸引大家的目光。由于平台限制了单个文本长度，这些模型不再适用于这些平台产生的短文本数据。为此，童薇等人提出了一种高效的微博事件检测算法（EDM）[4]，他们在文章中提出可以通过综合数据语义、时序和社交关系三个方面的特征，整体考虑了微博帖子及发帖人之间的多种相似度，从而实现事件检测；Lei-LeiShi等人则是提出了一种以人为中心的热点事件检测和传播网络社会计算模型（HCSC）[5]，通过筛选核心用户及关键帖子，建立以人为中心的关系网络，不断地模拟事件在用户之间的传递情况，结合LDA模型进行事件的检测。但这些算法都需要对数据进行分批并建立具体的社交关系网络，不仅仅需要处理大量的文本数据，还需要综合考虑各种用户关系，并且无法体现出事件实时的演化情况。MateuszFedoryszak等人在社会数据流上的实时事件检测[6]一文中提出可以将事件看作一组实体及其相关元数据在一段时间上构成的集群链，实体指的是一个文本、图像一类的内容所包含的标签，如命名实体、hashtags等，而元数据则是指的如实体频率等实体相关信息。也就是说每个事件在一个时间片内都是由一组这样的实体和相关的元数据构成的集群进行表示的，如果该事件存续到下一时间片，则该事件在两个时间片中的集群就会被链接，而这样构成的集群链长度就代表了事件的存续时间。当出现无法与前一时刻存在的集群进行链接的集群时，就认为是一个新的事件产生了，但是此方法同样也存在一定的缺陷，即需要根据时间对数据进行分片，分片的大小对事件检测的效果存在影响。而由QuanzhiLi等人提出的依据社交媒体的实时新事件检测方法[7]，通过将文本拆分成如专有名词、hashtag、动词等语义分类，再通过对各分类求相似度并加权求和得到最终的相似度值，根据阈值区分是聚类到已有微簇还是单独形成一个新的簇，此后，簇的维护过程中还采用了大量的经验参数，使得模型的可解释性较差，虽然该模型实现了实时在线的事件检测，但由于是根据相似度进行聚类的，所以模型需要设置较多阈值。1.3本文的主要贡献与创新本文以短文本流数据作为数据集，基于概率图挖掘自动决定微簇的个数，不需要对数据进行分批。由于不是采用相似度进行聚类，所以在此聚类过程中不需要设定阈值。且本文首次将概率图模型与数据流挖掘结合起来用于事件检测。相较于现有的事件检测算法，其能动态实时的反映出事件的演化和发展过程，是事件检测研究领域的一次重大创新。1.4本论文的结构安排本论文总共分为五个章节，具体结构安排如下:第一章为绪论，主要介绍研究工作的背景和意义，以及国内外相关研究工作的历史和现状，描述了本文的主要贡献、创新所在，并给出了论文的主要结构安排；第二章为研究相关的概念和技术概要，本章简要介绍了本文在进行事件检测时所使用的概率图模型及数据流挖掘方法的相关概念的基本知识；第三章为本文所提出的基于数据流挖掘的热点事件检测方法的具体介绍，本章解释了本文所提出的算法模型的结构及工作原理；第四章为实验的结果，本章主要展示了针对本文所提出方法进行的实验得到的结果；第五章提供了对本文整体工作的总结及开展后续研究工作的方向和思路。第二章研究相关的概念及技术概述本章将介绍本文提出的算法模型使用到的概率图模型相关的基本概念，并就采用的数据流挖掘领域的基本方法以及Glove模型进行简单介绍。2.1概率图模型（PGM）概率图模型并不是一种单一的模型，而是一类结合了概率论知识和图论知识，利用图结构来表示概率相关关系的模型的总称。相较于其他学习算法，概率图模型的优势在于可以将一些我们已知的信息利用图结构带入到模型中，但这也就往往意味着在我们使用概率图模型之前需要知道具体的图结构。基本的概率图模型包括三种：贝叶斯网络、马尔可夫模型以及隐马尔可夫模型。而本文提出的算法模型采用的概率图模型即为贝叶斯网络。2.1.1贝叶斯网络贝叶斯网络是一种利用条件概率和先验知识对现实情况进行描述的概率图模型。它的本质是通过先验知识来确定一个随机变量之间的关联约束关系，从而便于得到所需的条件概率。贝叶斯网络是根据贝叶斯公式导出的贝叶斯分数进行记分的，通过对所有可能的情况进行记分，从而筛选得到记分分数最高的那一个作为最优选择。贝叶斯分数的计算方式如2-1所示：scoreBG:d=logPd第一部分logPdG表示的是我们所使用的数据与给定图模型之间的拟合程度，而第二部分logP(G)则是表示图所估计的图模型与先验知识构成的先验图之间的拟合程度。而第一部分所表示的数据与图模型之间的拟合程度又可以表示成如下的式2P(d|G)=P(d|G,θG)P(θ式中P(d|G,θG)是一个似然函数，它所表示的是在给定图模型G及参数θG的情况下，数据d发生的可能性，而P(θG|G)表示的是参数的先验估计，即在给定图模型G本文提出的模型中采用了狄利克雷过程对先验参数进行建模。2.1.2狄利克雷过程狄利克雷过程（DirichletProcess）被广泛的运用在非参数贝叶斯模型中作为先验概率，最常见的使用方式是作为狄利克雷过程混合模型（DPMM）的先验。在对其的多种理解中，中餐馆过程（ChineseRestaurantProcess）以及波利亚缸（Polyaurn）模型是在实践中最常被提及的两种。中餐馆过程（CRP）中餐馆过程（ChineseRestaurantProcess）是非常典型的狄利克雷过程混合模型。其巧妙地将狄利克雷过程理解为餐馆的顾客落座问题，假设存在一个中餐馆，而在这个餐馆中可以存在无限多张桌子，除了当第一个顾客到来时，将会直接在第一张桌子坐下，其后到来的每一个顾客都有两种选择，既可以选择坐在已经有人的桌子上，也可以选择找到一张新的桌子坐下，而选择的标准就是坐在同一张桌子的顾客都喜欢吃桌上的同一盘菜。则此后到来的第n个顾客选择在已经有nk人坐下的第k张桌子坐下的概率计算如式2-3probabilityk=nkα+n−1而该顾客选择在一张没人坐的新桌子坐下的概率计算如式2-4：probabilitynew=αα+n−1由此可见预设参数α的值会影响顾客选择两种方式的概率大小，这个参数数值越大，则顾客坐到一张没有人的新桌子上的概率也就随之变大。在实际的聚类操作中，选择落座的顾客就代表着那些依次到来的新数据，桌子则表示各簇，那些坐到同一张桌子的顾客就意味着那些被聚类到同一个微簇的数据，他们都喜欢同一道菜则说明这些数据之间具有较高的相似性。这样就可以用一个中餐馆顾客落座的问题非常形象的解释基于狄利克雷模型对先验参数建模得到的概率图模型所实现的聚类过程。波利亚缸（Polyaurn）模型不同于中餐馆过程的顾客落座假设，波利亚缸模型描述的是一种球、缸假设。它是假设有一个空缸，以及一个颜色分布H，第一次只能选择从颜色分布里选取一个颜色涂在球上扔进缸中，而在之后的每一次则都可以有两种选择：（1）从缸中随机抽取一个球后放入两个同色球，其概率计算如式2-5：probabilitycolor=ncolorα+n−1其中，ncolor代表缸中涂有颜色color的球的个数，n-1代表缸中球的个数，α（2）从颜色分布H中选取新的颜色涂在一个新的球上放入缸中，其概率计算如式2-6：probabilitynew=αα+n−1从上式可以很明显的看出波利亚缸（Polyaurn）模型与中餐馆过程其实存在着对应关系。在波利亚缸模型中的颜色其实就对应着中餐馆模型中的桌子，选择摸球并放入两个同色球的操作其实就相当于中餐馆模型中新来的顾客选择一个已经有人的桌子坐下的过程，选择选取新的颜色涂到小球加入缸中就类似于中餐馆模型中顾客选择一个新的空桌子坐下的行为。因此，波利亚缸模型同样可以很好的描述聚类问题。2.2数据流挖掘的基本知识聚类作为数据流挖掘的一种重要方法，属于无监督算法的一种，它能够在数据没有标签的情况下自动的将数据划分成我们所需要的几类，因此一直被广泛运用于各个领域内。它可以根据聚类示划分数据的标准不同大致分为五类，分别是基于划分、层次、密度、网格和其他对数据进行划分。而k-means算法及层次聚类作为两种较为常用的方法，时常出现在各项研究中。2.2.1k-means聚类k-means聚类在开始前需要确定最终聚类得到的簇个数k，并随机初始化k各数据点作为簇的质心。在此后，对集合中的每个除了质心的点计算它与所有质心的距离，并将它们划分到距离最近的那个质心归属的集合中去。当所有的数据都被归属到某个集合后，重新计算k个集合的质心，如果重新计算得到的质心与之前的质心间的距离符合我们的需求，也就是说小于实现设定的某个阈值，则算法就结束了，得到的k个集合就是数据的最终划分结果。因为k-means聚类本质上是要最小化平方误差，也就是每个数据点到其所属集合质心的距离之和最小，所以当完成一次划分后新求得的质心与原本质心之间的距离较大时，则说明该种划分方式并没有达到较为理想的效果，就需要利用新求得的k个质心作为基础，迭代的重复上述的步骤，直到最终的结果小于设定的阈值，符合我们的预期为止。k-means作为一种被广泛运用的聚类算法，具有许多显著的优势。比如，它的原理简单，容易实现，参数少，收敛速度也非常的迅速，并且聚类得到的簇种的数据点也较为密集。但同时，它唯一的参数k需要预先给定，无法对许多现实存在的持续增加的数据进行聚类，且初始化的质心对聚类结果有着较大的影响，所以在设定时需要十分谨慎，最终得到的结果也仅仅只是局部最优解。2.2.2层次聚类层次聚类则可以很好的规避k-means需要预先设置簇个数k值以及选择初始化k个质心的问题。如同它的名字一般，层次聚类就是要对数据一层一层的进行聚类，既可以自下而上的凝聚，也可以是自上而下的分割。由于在本文中运用到的理论主要与凝聚法相关，所以分割法就不作过多阐述了。层次聚类凝聚法的思想是在一开始的时候就直接将每一个数据点当作一个独立的类簇结构，计算两个类簇之间的距离，找到距离最小的两个类簇进行合并，形成一个新的类簇，通过重复上述的步骤对所有的类簇不断进行合并，直到达到预期的结果为止，这个预期结果可以是对簇数目的约束也可以是对合并时簇间距离的约束。层次聚类相较于其他聚类方法的最大优势在于它可以一次得到最终的聚类结果，不需要进行多次的迭代，也不需要预设任何的初值。但它有一个与k-means相同的缺点，那就是由于它使用了贪心算法，得到的最终结果也仅仅只是局部最优解，并不一定是全局最优解。2.3Glove模型在涉及自然语言处理的工作中大都会用到wordembedding来获得单词在空间中的向量表示，随着对该领域的工作不断深入，在获得优质的词向量方面的需求不断增加，训练词向量的方法也不再局限于最简单的one-hot方式。而在这里将要介绍的既不是由DeerwesterS等人在1990年首次提出的利用文本的全局统计特征基于奇异值分解的LSA算法[8]，也不是利用局部的上下文特征通过滑动窗口来计算获得词向量的word2vec算法，而是结合了以上两种算法的特点，由JeffreyPennington等人在2014年提出的同时包含了语料库的全局统计特征以及局部的上下文特征的无监督词向量训练方法Glove模型[9]。Glove模型中引入了表示单词与单词之间在文本中共同出现的次数关系的共现矩阵X，在共现矩阵中出现的元素Xij表示的是单词j出现在单词i的上下文中的次数，而Xi则表示单词i上下文中所有单词总共出现的次数。因此，单词j出现在单词i的上下文中的概率就可以表示如式子2Pij=Xij因此，Glove模型就构造出了共现概率矩阵（Co-occurrenceProbabilitiesMatrix）,利用三个单词i、j、k之间的Ratio来表示它们之间的相关性，而Ratio的计算方式如式2-8：Ratio=PikPij也就是说，Glove模型训练得到的单词i、j、k的词向量必须包含共现概率矩阵中的信息，那么这三个向量在通过某种特定的函数进行变换后所表现出来的规律要和Ratio是一致的。从提出Glove模型的文章中可以看出，Glove模型因为结合了LSA和word2vec的优点，克服了LSA计算代价大、对所有单词权重一致的问题，同时解决了word2vec没有充分利用全部语料特征的缺陷，使得其呈现出来的性能远超其他两种方法。在使用Glove模型时，既可以利用自己的语料库进行训练，也可以使用官方提供的预训练词向量。当前，已经有基于多种数据集如维基百科、推特等训练得到的多种维度的预训练词向量可供使用。2.4本章小结本章主要介绍了在研究过程中设计的相关概念，并就使用到的技术进行了简要概述。主要涉及了概率图模型以及狄利克雷过程的两种常见理解，即中餐馆过程（ChineseRestaurantProcess）以及波利亚缸（Polyaurn）模型、数据流挖掘领域用来处理无标签数据划分的两种常用聚类算法，k-means聚类及层次聚类、用于训练词向量的无监督算法模型Glove。第三章基于数据流挖掘的热点事件检测方法研究基于前面所提及的相关概念及技术，本文提出了一种基于数据流挖掘的热点事件检测方法，图3-1描述了该方法检测热点事件的总体流程，其包括文本文件处理模块、基于概率图模型聚类模块、微簇维护模块以及事件检测模块。图3-1基于数据流挖掘的热点事件检测方法检测流程3.1文本文件预处理文本文件预处理模块要在每条文本文件数据到来时先对其进行预处理以便于后续模型对文本信息的利用。此步骤需要在每个文件原有信息的基础上获取其统计信息，并将它们作为文件的特征存储起来，并传入模型的下一个模块。文本文件预处理模块具体的执行流程如图3-2所示。图3-2文本文件预处理流程当一条短文本数据传入模型时，首先将这个文本文件所包含的完整句子拆分成单个单词并按原顺序存储到一个列表中，并为未在模型中出现的单词分配id号，为了便于存储和之后的访问，单词的id号由模型进行统一的统计单词词频及词对的共现分数作为文本文件的特征存储。词对的共现分数cwij体现的是单词之间的关联关系，其计算公式如3-1cwij=freifre其中，frei和frej表示在这个文本文件中单词i和然后将根据每个单词的词性及上下文信息将所有单词划分成10种词性类，分别是名词类、动词类、代词类、形容词类、数词类、副词类、冠词类、介词类、连词类和感叹词类，每个单词在每个分类中仅可出现一次，将分类得到的结果作为该文本文件的特征之一存储起来。也就是说经过预处理模块得到的文本文件除了包含原本的句子信息，如文件序号、句子内容、用于检验模型效果的分类标签外，还增加了各个单词对应的词频信息、词对共现分数信息以及词性类划分结果。在完成文本文件预处理后将其传入模型中保存。3.2基于概率图模型聚类对完成预处理的文本文件采用根据中餐馆过程（ChineseRestaurantProcess）作为先验概率进行建模得到的概率图模型进行聚类。此过程是基于KumarJay等人的OSDM模型[10]改进得到的。在此聚类过程中需要用到的文本信息仅仅是文件序号及经过文本预处理得到的统计信息，而其具体的句子内容在此过程中则不再需要。具体的聚类过程如图3-3所示。图3-3基于概率图模型聚类流程当预处理后的文本文件输入到模型中后，将通过公式3-2求得文件d聚类到各个已有微簇z的概率大小，同时通过公式3-3可求得文件d单独聚类形成一个新的微簇的概率大小：pzd=z=pzd=new=式3-2分为三个部分相乘，式子3-3则分为两个部分，它们与式3-2的前两个部分具有相同的含义。第一部分利用中餐馆过程（CRP）对聚类到各个集群的先验概率进行建模，用于表示聚类集群的完整性，而包含超参数β的第二部分描述了需要聚类的文件与各个微簇间的同质性，即其在文本统计信息间的相似性，并且在这一过程中会对那些具有代表性的单词进行奖励，仅存在于式子3-2中的第三部分则描述了文件d与微簇z中的词对共现信息的权重大小，也就是说同时出现在文件d中及微簇z中的词对越多，文件d越可能被聚类到微簇z中。两式中的各个字符含义如下表3-1所示：表3-1公式3-2及3-3中各字符含义字符名称含义w、d、z单词、文件、微簇n微簇z已经包含的文件个数D整个模型仍在维护的活跃微簇中文件总个数α集中参数，其值越大新到文件聚类形成新微簇的概率大小相对于聚类到某个已有微簇的概率大小也会越大，更易聚类为一个新微簇。β超参数，弱化0值的影响V当前模型中维护的词典大小，即所有活跃微簇中存在的不同单词的个数n分别表示在文件d和微簇z中单词w的出现频次大小n分别表示在文件d和微簇z中的单词总数量lcf表示单词w的全局代表性大小，即单词的特异性程度cw单词i与单词j在微簇中的词对共现权重其中代表单词的特异性程度的lcfw和微簇的词对共现权重cwij的计算方式如式子3-4和3lcfw=log|Z|cwij=在计算时cwij时仅将那些同时出现在文件d和微簇z的单词wi及wj当分别计算得到新到文本文件聚类到各个已有微簇的概率大小以及单独聚类形成一个新的微簇的概率大小后，通过比较选出概率最大的微簇进行聚类。如果聚类形成新微簇的概率最大，则首先从模型中获取新微簇的id号以此初始化一个新的微簇，再将文本文件添加到该微簇中。将文本文件加入到指定微簇的实施过程如算法3-1所示：算法3-1聚类文本文件d到指定微簇z输入：文本文件d、指定微簇z序号输出：完成聚类信息更新后的微簇z更新微簇z的时戳I_cl为最新文件序号更新微簇z的衰退权重I_cd为1.0在文件与微簇的对应字典中加入文件d与微簇z的对应关系将文件d加入到微簇z的文件列表I_cnfor单词w1in更新单词w1if单词w1not在微簇的词频表及词对共现矩阵分配单词w1将微簇z中单词w1的词频加上文件d中的单词w在微簇z的总单词数量上加上文件d中的单词w1for单词w2inif单词w1不是wif单词w2notin微簇z的词对共现矩阵单词将文件d的w1和welse将文件d的w1和w将不存在于微簇z词性分类对应位置的文件d中的单词对应添加到微簇z中更新微簇z的文件增量inc，在其值加上1在算法3-1中，最后更新的微簇的文件增量信息inc存储的是微簇z在上次更新微簇的特征向量及关键词信息后聚类到微簇中的文件个数。由于更新微簇的特征向量及关键词需要花费大量的时间，且当微簇包含的文件数量越来越多时，少量的文件聚类进去并不会造成微簇的特征向量和关键词的改变，所以，有文本聚类到微簇中时仅需要记录下微簇距离上次更新特征向量和关键词的文件增量数，在后续流程中以此为依据判定是否有必要进行更新，即可在较小的影响范围内节约较多的时间。3.3基于数据流挖掘的方法维护微簇在通过概率图模型完成了文本文件的初步聚类后，就会得到若干个微簇。不同的人在描述同一事件时由于表达差异，最终得到的文本也会有较大差异。所以这些微簇既可能分别代表一个独立的事件，也可能由多个微簇构成一个事件。且在聚类的过程中，由于一些噪声词的影响就可能导致单个文本文件聚类到错误的微簇中，如果不将这些错误聚类的内容剔除，将会对后续的聚类过程产生较大的影响。所以，利用微簇的特征向量等信息，结合数据流挖掘的方法对完成初步聚类的微簇进行维护就显得尤为必要。对微簇的具体维护内容可分为三个部分，包括：过时微簇的删除、聚类错误的剔除以及相似微簇的融合。其中，过时微簇的删除是在每次进行文本文件聚类前进行的，其主要的执行过程分为两步：对所有微簇的过时检测和输出检出的过时微簇。具体的执行过程如算法3-2及3-3所示：算法3-2过时微簇的检测输入：模型的信息、微簇的衰退系数LAMDA输出：更新后的模型信息初始化过时微簇的阈值threshold以及待删除微簇词典for微簇in模型的所有微簇：读取微簇最后一次更新的时戳lastupdate及微簇的衰退权重cd根据当前的时戳timestamp计算衰退量power=2计算并存储微簇新的衰退权重cd=cd*powerifcd<threshold：将微簇id作为键，微簇信息作为值存入待删除微簇词典for微簇id及微簇信息in待删除微簇词典：删除微簇算法3-3过时微簇的删除输入：模型信息、过时微簇z的id、过时微簇z信息输出：更新后的模型信息if微簇idin模型已经检测到的事件列表中:从模型事件列表中将微簇信息删去，并将这一情况输出for单词win微簇z的词频字典:从模型的单词-微簇对应关系表中删除单词w与微簇z的对应关系筛选出微簇z中包含单词w的文件，放入列表listOfDocToDeletefor文件inlistOfDocToDelete:从模型的单词-文件对应关系表中删除单词w与文件的对应关系if模型中不再包含单词w：从模型的各项表单中删除单词w的相关信息for文件in微簇z的文件列表:从模型存储的所有文件完整信息中将文件删去从模型各项表单（除存储过时删除信息的表单）中将与文件相关的信息删去将文件加入到模型存储过时删除信息的表单if微簇idin模型中存储的聚类错误剔除微簇-文件对应关系表:for文件in微簇z中因聚类错误剔除删除的文件列表:将文件加入到模型存储过时删除信息的表单从微簇z中因聚类错误剔除删除的文件列表删除微簇id对应键值对从模型中删除微簇z的信息而其余两种对微簇的维护，即聚类错误的剔除以及相似微簇的融合均发生在文本文件聚类完成时，且由于单个文本文件的聚类进入到一个微簇中并不会对微簇在空间的分布产生较大影响，同时为了节约微簇维护所花费的时间，仅当微簇聚类完成时包含文件条数是10的倍数才进行融合检测及对应的融合操作。而当微簇包含的数量小于一定数量时并不能很好的确定该微簇真正描述的主要事件，所以，仅当一个微簇数量大于20时，我们才会在融合相关操作执行完成后进行聚类错误剔除操作。而进行聚类错误剔除的对象会因为是否进行了融合操作而不同，若未进行融合操作，则对象为完成聚类的当前微簇，若进行了融合操作，则对象为融合形成的新的较大微簇。具体的判定逻辑如图3-4所示：图3-4执行聚类错误剔除及相似微簇融合的判定逻辑在进行融合检测时，将结合数据流挖掘的方法，利用微簇在空间中的分布情况，基于微簇的特征向量检测微簇之间的相似度，通过与融合阈值F_THRESHOLD进行比较判定是否需要进行微簇融合。而微簇的特征向量和关键词的更新仅发生在微簇融合检测和事件检测两个步骤中。在计算微簇的特征向量时，首先需要分别计算出微簇的十个词性分类中每个单词对微簇的代表性大小，然后从每个词性分类中选出五个最能代表微簇在这一词性维度特征的单词，当微簇在这一词性维度包含的单词不足五个时，则将这一词性维度的单词全部选入。单词对微簇代表性大小的计算方式如式子3-6所示：Rw→z=nzw其中，nzw为单词w在微簇z中的出现频词大小，它代表的是单词w在微簇中的重要程度，是单词w对微簇z的局部代表性大小，而代表单词的特异性程度的lcfw当筛选出每个词性维度最具有代表性的数个单词后，在每个词性维度的范围内对这些单词的Rw→z进行归一化，将其转化为计算微簇z在该词性维度的特征向量的权重，并利用在Twitter数据集预训练好的Glove模型得到单词的词向量，当该单词在预训练Glove模型的词典中不存在时，则利用python的enchant库取得该单词的相似单词作为代替，根据对应的权重加权求和得到微簇z在此维度的特征向量，最后将这些向量按序拼接形成一个250而微簇的关键词则相当于求取微簇特征向量过程中的副产物，它是在筛选每个词性维度的代表性单词时，不区分维度的将所有单词及其代表性大小以字典形式进行存放。需要注意的是，每个单词只会被存放一次。当微簇的所有受检单词都存入字典后，对单词的代表性大小进行排序，最终筛选出对微簇的代表性排名前10的单词作为微簇的关键词，在这些关键词中就隐含了该微簇所属事件的主题信息。需要注意的是，因为微簇的文件增量inc记录的是微簇在每次更新微簇的特征向量和关键词后聚类的文件个数，所以每次对微簇的特征向量和关键词进行更新操作后，都要将微簇的文件增量inc清0，使其重新进入新的累计周期。在取得被检微簇的最新特征向量后，融合检测要求出模型中所有包含文件数量大于10条的微簇特征向量与当前被测微簇的特征向量之间的余弦相似度，将那些余弦相似度值大于预设阈值F_threshold的微簇存放在一个列表中，最终选择出列表中余弦相似度值最高的那个微簇与被测微簇进行融合。这一方式类似于数据流挖掘中的层次聚类，将基于概率图模型聚类得到的微簇视作一个个数据点，每次总是从达到融合阈值的微簇中选择余弦相似度值最大的两个微簇进行融合。在对两个微簇进行融合时，要根据其优先级选择将哪个微簇作为被融合微簇融合到另一个融合微簇中，一般认为存在于模型的事件列表中的事件微簇比普通微簇具有较高优先级，将作为融合微簇保留下来。而融合过程的操作则类似于文本文件的聚类过程与删除旧微簇过程的结合，具体的步骤如算法3-4所示：：算法3-4相似微簇的融合输入：模型信息、需要融合的微簇z1和输出：融合完成后的微簇clu1根据优先级从微簇z1和z2中选择出融合微簇clu将clu1和clu2中更大的最新时间戳cl及衰退权重cd作为融合后微簇for文件idinclu2将文件id与微簇的对应关系表值从clu2修改为将文件id加入到clu1for单词w1inclu更新单词w1与微簇cluif单词w1notin微簇clu在微簇clu1的词频表及词对共现矩阵分配单词w在微簇clu1的单词w1的词频上加上微簇clu2在微簇clu1的总单词数量上加上微簇clu2中的单词for单词w2in微簇cluif单词w1不是wif单词w2notin微簇clu1将微簇clu2的w1和w2else将微簇clu2的w1和w2将不存在于微簇clu1词性分类对应位置的微簇clu1中的单词对应添加到微簇将模型中微簇clu2因聚类错误剔除而删去的文件信息转存到微簇clu删除模型中存储的微簇clu2if微簇clu2将微簇clu2计算并更新微簇clu1在对微簇执行聚类错误剔除时，剔除关键词需要满足三个条件：①不是无关词，即不是那些所有微簇都可能出现的冠词介词等信息，可根据lcfw大小进行判断；②该词在其他微簇占比更重且具有相对高频，即该词在其他微簇出现的文件数量占簇总文件数比例更高，且数量大于被检微簇的lcf对选定的潜在聚类错误文件进行剔除的具体操作如算法3-5所示：算法3-5潜在错误聚类文件剔除输入：模型信息、需要剔除的文件doc和所在微簇z输出：剔除完成后的微簇z及更新后的模型信息从模型中读出需要剔除的文件具体信息从模型的文件-微簇对应关系字典中删去文件doc的id与微簇z的对应关系从微簇z的文件列表中删去文件doc的idfor单词win文件doc的词频表:从模型的单词-文件对应关系字典中将文件doc的id删去从微簇z的单词w词频中将文件doc包含的单词w词频减去从微簇z的总单词量中将文件doc包含的单词w词频减去if微簇z中单词w的词频等于0:从模型的单词-微簇对应关系字典中将微簇z删去删去微簇z的词对共现矩阵中单词w的对应空间else:for单词w2in文件doc的词频表:if单词w不是单词w2:从微簇z单词w与w2的共现权重减去文件doc中它们的共现权重if微簇z中单词w与w2的共现权重等于0:从微簇z的词对共现信息中删去单词w与w2的共现关系if模型中单词w不再有对应的文件存在:删去模型中与单词w相关的所有列表信息将模型中存储的文件doc的详细信息删去将文件doc的id存储到模型用于存储由聚类错误剔除的文件信息的微簇-文件关系字典中结合数据流挖掘的方法，经过过时微簇的删除，相似微簇融合以及聚类错误剔除三个步骤，一次完整的微簇维护流程就完成了。如果维护完成的微簇还不存在于模型的事件列表中同时满足特定的条件，则会对该微簇进行事件检测，以判断该微簇是否可能时一个独立的新事件。3.4事件检测基于对热点事件的理解，我们认为仅当人们对一个讨论对象的讨论数量大于一定程度且不同于先前的讨论对象时，才可以认为它是一个被人们所关注的热点事件，所以事件检测也仅发生在完成聚类错误剔除的微簇对象上。判断一个微簇是否是一个独立事件的评判标准决定了最终的事件检测效果。本文基于对热点事件的理解，认为当一个微簇能够被进行事件检测时则意味着它满足人们对其讨论数量大于一定程度这一要求，而它与先前讨论对象的差异则可基于数据流挖掘的方法，通过计算该微簇的特征向量与已经检测到的事件之间的余弦相似度进行判定。具体的事件检测操作如算法3-6所示：算法3-6事件检测输入：模型信息、被检微簇z、独立阈值THRESHOLD输出：更新事件集合后的模型信息if模型中的事件字典为空:if微簇z的文件增量inc不为0：更新微簇z的特征向量和关键词将被检测微簇z的id-关键字以键值对形式加入模型事件字典将检测到的事件微簇id及关键词输出else：if微簇z的文件增量inc不为0：更新微簇z的特征向量和关键词设置标志new为Truefor微簇clusin模型的事件字典：if微簇clus的文件数小于微簇clus的文件增量inc的20倍：更新微簇z的特征向量和关键词if微簇clus与微簇z特征向量间的余弦相似度大于THRESHOLD：置标志new为Falseif标志new为True：将被检测微簇z的id-关键字以键值对形式加入模型事件字典将检测到的事件微簇id及关键词输出3.5本章小结本文提出了一种结合概率图模型和数据流挖掘的热点事件检测方法，首先通过概率图模型对预处理后以数据流形式到来的短文本文件进行聚类，每个到来的文本文件只会有两种类型的聚类结果：聚类到已有微簇或单独形成一个微簇，最终的聚类结果由概率图模型计算得到的概率决定。随后，将基于数据流挖掘的方法对聚类的到的若干微簇进行维护，主要分为三个维护步骤：删除过时微簇、相似微簇融合及聚类错误剔除，以控制模型种集群数量，节约存储空间，同时删除前一步产生的错误聚类结果对后续聚类的消极影响。最后，将基于微簇的空间分布从模型维护的微簇中检测出当前人们关注的热点事件，并得到其事件关键字以展示其事件内容。参考文献第四章实验结果及分析4.1实验相关内容4.1.1实验数据集及评估指标实验采用了两个真实数据集及两个综合数据集，其具体信息如下：News：在2014年由JianhuaYin[11]等人为短文本聚类模型而收集而来，并由KumarJay等人[10]对其进行一系列数据清洗操作，如删去停用词、将所有字母转换成小写等后得到的。其内容为属于152个主题的11109个新闻标题。Tweets：此数据集存在于TRECmicroblog/data/microblog.html上，包含了与269个主题相关联的30322/data/microblog.htmlNews-TC和Tweets-TC：由KumarJay等人在[10]一文中对News和Tweets根据主题进行排序后，分别分为16个大块后再对每个块内数据打乱顺序后得到。本次实验对模型聚类效果采用的评估指标有五种，分别为：归一化互信息（NMI）、同质性（Homogeneity）、同质性与完整性的调和平均值（V-Measure）、聚类准确性（Accuracy）、微簇纯度（Purity）。其中归一化互信息评估了整个模型的聚类质量；好的聚类结果应该是每个微簇只包含一类数据，此为同质性，同时每一类数据也仅被聚类到一个单一微簇中，此为完整性，但是同质性和完整性往往难以兼顾，所以同质性和完整性的调和平均（V-Measure）能够反映出二者的综合情况。上述五种评估指标得分均在[0,1]区间，其值越接近于1则说明模型在这一评估方面表现越好。4.1.2实验采用的参照模型本次实验分别采用了五种模型作为参照模型，下面是对它们的简短介绍：DTM：由D.M.Blei等人在2006年提出的[1]动态主题模型，其被用于处理一系列有序文件的聚类问题。Sumblr：由LidanShou等人在2013年提出的[12]一种在线的推文聚类模型，它仅通过单向的一轮处理就能够有效的聚类并维护好集群的信息。DMM：由JianhuaYin等人在2014年提出的[11]用于短文本聚类的狄利克雷多项式混合模型，其不将数据对时间的依赖性考虑在内。MStreamF-O（MF-O）:由JianhuaYin等人在2018年提出的[13]用于一次处理一批包含无限潜在主题的短文本的两种模型之一，其的特点是一次性完成聚类的过程。OSDM：由KumarJay等人[10]在2020年发表于ACL的文章中提出的一种基于概率图模型进行短文本数据流聚类的模型，其在短文本流聚类领域处于较为先进的水平。本文中提及的上述五种模型在News、Tweets及News-TC三种数据集上的五种指标结果参考KumarJay等人在[11]通过反复实验得到的最佳结果。4.2实验结果及分析在实验过程中，我们将参数α设置为0.002，参数β设置为0.0004，而衰退系数LAMDA设置为0.000006。模型中涉及的两个阈值：事件的独立阈值设置为0.707，其为45度的余弦值保留三位小数得到，而在经过实验后从0.750和0.866中选择出了具有更好事件检测结果的0.866作为微簇的融合阈值，其为30度的余弦值保留三位小数得到。由于众多事件检测算法所基于的数据结构不同，大多数的模型所使用的数据都由研究人员自行收集和构造得到，无法直接进行比较，所以接下来将依次展示本文所提出的模型在聚类及最终热点事件检出方面的效果。在表4-1中展示了本文提出的模型HEDBDSM与前面提到的五种参照模型在News、Tweets、News-TC及Tweets-TC四种数据集上得到的聚类效果在NMI、Homogeneity、V-Measure、Purity和Accuracy五种聚类模型的评价指标上的得分：表4-1本文模型HEDBDSM与参照模型在五种评价指标上的得分 Alg.Eva.NewsTweetsNews-TCTweets-TCHEDBDSMOSDMMF-OSumblrDTMDMMNMI0.8120.8150.6850.5750.8080.5860.8530.8360.7460.6980.8000.6360.8660.8580.8030.7230.8100.5820.8740.8470.822//0.269HEDBDSMOSDMMF-OSumblrDTMDMMHomogeneity0.8270.9510.6540.5470.8330.5880.9080.9360.6950.7580.8220.6220.8980.9000.7780.7470.8370.5650.9350.9390.798//0.275HEDBDSMOSDMMF-OSumblrDTMDMMV-Measure0.8110.8050.6840.5750.8080.5860.8510.8310.7440.6960.8000.6360.8670.8570.8030.7230.8100.5820.8720.8420.821//0.269HEDBDSMOSDMMF-OSumblrDTMDMMPurity0.7150.9070.5520.4140.7670.4560.8570.8900.5290.6090.7490.4730.8450.8510.6360.5800.7650.3980.8980.9140.658//0.175HEDBDSMOSDMMF-OSumblrDTMDMMAccuracy0.7150.8800.4200.6060.6470.3340.6620.6650.2460.5390.2460.1500.7720.7690.5840.6530.2940.0730.6640.5650.753//0.131表4-1中加粗的结果为在列所对应的数据集、行所对应的指标上表现最好的一项。从表中可以看出，在算法聚类效果的总体评价指标NMI及同质性和完整性的调和平均V-Measure这两项对模型的聚类能力有较为整体的评估的指标上，本文提出的模型在四个数据集上几乎都有最好的聚类表现。而在其他三个指标上，本文所提出的模型也与表现最优的模型之间的得分差距并不大。尤其是在News-TC及Tweets-TC这两个根据现实事件发展情况做出了调整的数据集上，我们的模型HEDBDSM有较为突出的表现。而在热点事件检出方面，我们认为一个事件从诞生到发展成为一个热点事件，必须满足两个要求：①讨论量达到一定值；②发生关注度的集中增加。因此，我们将以上两个条件具象化为：①该真实分类至少包含20条文本数据；②曾经在某一段时间内该真实分类的文本密集出现，这一点将利用滑动窗口进行筛选，滑动窗口越大，表示认定密集的时间跨度越大，而属于该真实分类的文本数据在此滑动窗口占比越大，则说明该增长需要达到的密集程度越大。通过以上两个具象化的条件，我们利用数据本身的真实分类构造出在根据事件发展情况进行了调整的数据集合News-TC和Tweets-TC上的热点事件集合（以下简称真实热点事件）与我们所检测到的热点事件微簇内容进行比较。得到的结果如下表所示：表4-2在News-TC和Tweets-TC上的热点事件检测效果 事件检测效果滑动窗口占比News-TCTweets-TC检出率精准检出率检出率精准检出率15/10055/60（0.887）51/60（0.850）57/60（0.950）55/60（0.917）20/10040/44（0.909）37/44（0.841）36/39（0.923）34/39（0.872）25/10029/31（0.935）27/31（0.871）25/26（0.962）24/26（0.923）10/3037/40（0.925）34/40（0.850）35/38（0.921）34/38（0.895）15/3011/11（1.000）11/11（1.000）7/7（1.000）7/7（1.000）5/1046/51（0.902）43/51（0.843）52/57（0.912）50/57（0.877）表4-2中的检出率代表真实热点事件在我们检出的热点事件微簇中有与之相对应的微簇的在真实热点事件中的占比，而精准检出率则是在真实热点事件中满足检出率条件的同时，与真实热点事件对应的检出热点事件微簇中的主要成员同样为该真实热点事件的占比。从表中我们可以看到在两个数据集上，除了当滑动窗口最大占比最低的情况，也就是说对热点事件的集中增长这一条件要求最低的情况下，我们的模型HEDBDSM均能达到90%以上的热点事件检出率，而精准检出率也均在84%以上。并且，我们的模型能够反映出热点事件讨论量实时变化情况以及该事件所对应的关键词，图4-1中分别展示了在News-TC和Tweets-TC上整个数据集所囊括的时间跨度上检出的热点事件讨论量的变化情况，并对每种颜色所代表的检出热点事件对应的微簇序号以及关键词作了标注。（a）（b）图4-1在数据集News-TC和Tweets-TC上模型检出的热点事件讨论量实时变化情况及关键词（a）在News-TC数据集上得到的结果；（b）在Tweets-TC数据集得到的结果在图中，如果代表事件讨论量的折现急速上升，说明当前热度不断上升，而当折现趋于平缓时则说明已经关注度变少，讨论量已经几乎不再增加。当折现出现轻微的下降说明模型对该微簇中的可能存在的错误聚类数据进行了清理，而当一个热点事件出现直线下降的情况时，则说明该事件被模型检测到过时，也就是没有关注度了，就要从模型所维护的数据中清理掉。由此可见，HEDBDSM模型能够直观的反映出一个事件讨论量的变化情况，从而反映出一个事件的热度变化。模型在提取热点事件关键词时，以关键词的代表性大小按序输出，排序越靠前的关键词越重要。以News-TC中检测到的第一个事件，也就是序号为4的事件微簇为例，其所包含的是真实标签分类为1号的现实事件，经过人工检视，其描述的是日本侵入中国防空识别区，中国军官予以警示这一事件。从图4-1中现实的关键词提取结果中截取得到图4-2：图4-2模型检测到的序号为4的热点事件微簇对应事件关键词根据图中内容，本文所提出的HEDBDSM模型针对这一事件提取出的十个关键词分别是：“china”、“zone”、“air”、“defense”、“japan”、“bomber”、“disputed”、“airspace”、“island”、“flight”，这十个词清晰的表述了此热点事件的发生对象为中国与日本两国，以及事件的大致内容为中国和日本之间一次有争议的空域飞行。可见，HEDBDSM模型能够较好的提取出能够较好表述热点事件内容的关键词。4.3本章小结本章通过与DTM、Sumblr、MStreamF-O、DMM和OSDM五个模型在News、Tweets、News-TC和Tweets-TC四个短文本数据集上的聚类结果在NMI、Homogeneity、V-Measure、Purity和Accuracy五个聚类算法评价指标方面的评分进行比较，展示了本文所提出的模型HEDBDSM对短文本数据流具有较好的聚类效果，并且通过表格和图例的方式，表现了HEDBDSM能够较为准确的检测出短文本数据流中隐含的热点事件及关键词的能力，取得了预期的效果。

第五章全文总结与展望5.1全文工作总结本文就基于数据流挖掘的方法进行热点事件检测这一课题进行了研究，提出了一种结合概率图模型和数据流挖掘的方法基于推特等社交平台产生的短文本数据流进行热点事件检测的方法HEDBDSM。此方法首次将数据流挖掘的方法与热点事件检测这一研究课题结合起来，是热点事件检测领域的一次巨大创新。HEDBDSM模型在聚类效果上相较于短文本流聚类领域处于领先地位的已有算法也具有十分优异的表现，能够较为准确的从庞大的数据流中检测出热点事件，并抽取出热点事件的关键词。5.2后续工作展望本文提出的HEDBDSM模型虽然达到了预期目标，但由于没有与之完全匹配的数据集用以模型的实验，不能很好的验证模型对热点事件的检验能力，同时在获取微簇的空间特征，计算各个微簇间的空间距离的时候产生了较为大量的计算开销，对模型处理数据的速度产生了一定的影响，针对以上问题，后续工作将主要分为两个部分开展：爬取推特数据上用户发表的短文本数据，按照讨论的事件及事件发布的时间整理生成适用与HEDBDSM模型的热点事件检测数据集。改进微簇特征向量的计算策略，减少对微簇空间特征的重复计算，以提升模型的运行速度，节省计算开销。参考文献BleiDM,LaffertyJD.Dynamictopicmodels[C