爆发主题探测关键问题算法研究

　爆发 主题 探测 关键 问题 的 算法研究* *

　 谢靖 中国科学院国家科学图书馆

　[ [ 摘要] ] 本文阐述爆发主题探测研究中面临主题结构判定和爆发特征发现两个关键问题，分别对解决两个问题中使用的常用算法进行研究。分析对比各种算法的优缺点，以及算法适用的环境。从信息保真度、爆发特征计算准确性、算法效率等三个方面的指标对各种算法对比评述。

　[ [ 分类号] ] TP393 [ [ 关键字] ] 爆发探测

　主题聚类

　爆发特征

　算法对比分析 Research on Key

　Problems of Burst Detection and Relate d Algorithms

　Xie Jing National Science Library, Chinese Academy of Sciences

　[Abstract] This paper describes the two key issues: topic structure determination and burst feature detection in burst topic detection research. Do research work on the algorithms to solve the two problems. Compare the advantages and disadvantages of these algorithms, as well as algorithms applicable environmental. Give the algorithms analysis from information fidelity, calculation accuracy, and the algorithm efficiency three indicators. [Keyword] Burst Detection, Topic Clustering, Burst Feature, Algorithms Analysis 1 1 引言

　 当前正处于一个信息爆炸的时代，面对每天层出不穷该的海量信息，人们希望从这些信息中发现热点的、重要的、关键的信息，以及自己最关注的资源。因此，对大量的信息进行识别、分析和筛选，发现有价值，热点的信息显得尤为重要。爆发主题探测是一项重要研究领域，其主要目标是发现在一定时间段内以较

　 ? 本文系国家社会科学基金项目“网络科技信息中爆发主题的监测与分析方法研究”（项目编号：09BTQ035）的研究成果之一。

　高的频率出现，或者在某个时间范围出现突增特征或有异常变化的主题信息。这类主题即被标识为具有爆发特征的热点主题[1] 。具有爆发特征的信息，往往更加被人们关注，因此被认为拥有更高的情报价值。

　爆发主题探测从网络信息中获取文本流，将信息在一定范围内进行主题分布的聚类，然后将数据集合在时间或空间维度映射分析，从而根据分布特征，发现具有爆发特征的主题。针对主题结构和爆发特征的算法，由于研究领域和应用场景各不相同，算法的特性各有千秋。本文将爆发探测研究分解为：爆发主题的判定和爆发特征分析两个方面的关键问题。对两个研究方面使用的相关算法做重点研究，分析其核心算法，以及其衍生算法。对比在解决同类问题中的算法特征和优缺点，以及算法适用的场景。

　2 2 爆发探测 的 关键 问题

　1 2.1 主题结构的判定

　从新闻、网络信息、邮件等一系列文本流是一系列文本词汇的集合，这些词汇中包含大量的非结构化的、无组织的数据，并不能够直接被人们所利用。显著意义的主题信息和事件信息才是人们关注的重点，如何将人们关注的信息流聚焦成集中的主题、揭示文本流的主题结构是爆发探测的首要工作。主题结构判定首先需要从文本流中抽取出的关键词或者术语等；其次需要对这些关键词和术语在同一时间的爆发特征上进行主题聚类，甚至是相似主题的汇聚和归并；最后记录聚类主题在文本中出现的频率、密度等分布特征[2] 。通过特定算法计算出主题爆发能量特征，是爆发特征的发现的必要工作。

　2.2 2 爆发特征 发现

　文本信息汇聚由主题来组织和表达之后，判断其是否具有爆发特征，需要根据它们的到达时间进行分析研究。例如，特定时间点突然关于某个事件的新闻报道增多则说明该事件主题具有爆发性特征。某一时间段内，关于某个研究领域的来往邮件频繁，说明关于这个研究领域的主题讨论具有爆发性特征。

　爆发特征与特定主题的文本流到达时间、到达率、统计频率、以及主题能量

　等因素都有直接关系。这些因素的不规律性对准确的发现爆发特征具有一定的难度，爆发特征经常具有间歇性、粗糙性、隐匿性等特征[3] ，因而，从一系列文本流中提取爆发信息的爆发特征是爆发探测研究中的重点和难点。

　3 3 爆发探测 相关 算法 研究

　3.1 1 主题结构判定 算法模型

　基于文本流中词汇的爆发特征探测，由于词汇表达意义的不明确和随机性，简单的词汇探测对爆发探测的实用价值不大，因此文本流的爆发主题结构判定，是爆发探测的一个关键性问题。在文本的主题结构判断中，常用的方法是分为：主题聚类算法和概率统计模型算法，本文以几种常用的算法为例对算法进行研究对比。

　(1) 文本 主题聚类算法 模型

　① K-MEANS 算法[4] ：

　K-MEANS预先定义k个聚类数量；然后将待聚类的n个数据对象按照定义的 k个聚类进行迭代划分，迭代后最终获得的聚类满足两个条件：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。K-MEANS 算法的工作过程说明如下：

　? 从 n 个数据对象任意选择 k 个对象作为初始聚类起始中心点； ? 剩余的 n-k 个对象数据，则根据它们与这些聚类中心的相似度，通过中心度距离计算，分别分配给与其最相似的聚类中心所代表的聚类； ? 再计算每个所获新聚类中所有对象的均值； ? 重复迭代这一计算过程，直到测度函数收敛为止。

　K-MEANS 算法的特点是采用测度函数计算均方差，使得聚类内部各对象距离最小，各类之间的对象距离尽可能最大，已达到聚类的最佳效果。K-MEANS 算法的缺点是生成的聚类结果对于脏数据很敏感，脏数据的存在会引起较大的聚类误差[5] 。

　②K-MEDOIDS 算法[6]

　由于 K-MEANS 算法对脏数据敏感的缺点，K-MEDOIDS 算法选取一个 mediod的对象来代替 K-MEANS 算法的中心对象的作用， medoid 就标识了这个类。K-means 中心点取当前聚类中所有数据点的平均值，而在 K-medoids 算法中，取当前聚类中的点的距离之和最小的作为中心点。K-MEDOIDS 算法过程如下：

　? 从 n 个数据中任意选取 K 个对象数据作为 medoids；

　? 将余下的对象数据根据与 medoid 最相近的原则划分到各个 medoids代表的类；

　? 对于每个类中，顺序选取一个数据，计算用该数据对象代替 medoids后的消耗 E，用消耗最少的代替 medoids 值，如此循环迭代直到 K个 medoids 固定下来。

　这种算法对于脏数据和异常数据不敏感，但是在迭代计算 K 个 medoids 值，算法的时间复杂度，计算量显然很大，因此一般只适合小数据量聚类计算，不适用大数据的计算[7] 。

　③Clarans 算法[8]

　Clarans 算法是 K-MEDOIDS 算法基础上的改进算法，目的是改进 K-MEDOIDS算法在大数据量处理方面的性能。Clara 算法使用数据的抽样来代替整个数据集合，在这些抽样的数据上再利用 K-MEDOIDS 算法得到最佳的 medoids 值。Clarans算法将 K-MEDOIDS 算法的迭代计算分散在每个采样上，从而使得 K-MEDOIDS 算法能够处理大量的数据，其算法思想是将大的数据集拆分成小的数据集，类似于分布计算的思想，因此算法应用在分布式计算平台上效果更佳。

　(2) 文本 主题分布 算法 模型

　基于模型的方法给每一个聚类假定一个模型，然后去寻找一个能满足这个模型的数据集，目标数据集是由一系列的概率分布所决定的。以下比较了 LSA 和 LDA 两种经典主题分布算法。

　①LSA（Latent Semantic Analysis）[9]

　潜在语义分析算法采用 Bag of Word 模型假设，在已知一个文档数据集及相应的词典 ，将数据集表示为一个的共生矩阵， ，其中， 表示词典中的第 j 个单词在第 i 个文档中出现的次数。LSA 的基本思想就是，将文档从稀疏的高维词典

　空间映射到一个低维的向量空间，称之为隐含语义空间(Latent Semantic Space)。

　LSA 的优点在于：低维空间表示可以刻画同义词对应着相同或相似的主题、降维可去除部分噪声，充分利用冗余数据，无监督并且完全自动化，该算法与语言无关；而 LSA 的不足在于：没有刻画 term 出现次数的概率模型，无法解决多义词的问题。

　②LDA（Latent Dirichlet Allocation）[10]

　LDA 算法也采用 Bag of Words 的研究方式，将每一篇文档视为一个词频向量，从而将文本信息转化为了易于建模的数字信息。LDA 的思想是利用文本建模的生成模型，该模型可以随机生成可观测的数据，是一种非监督机器学习技术，可以用来识别大规模文档集或语料库中潜藏的主题信息。在 LDA 的视角中每一篇文档代表了一些主题所构成的一个概率分布，而每一个主题又代表了很多单词所构成的一个概率分布。

　狄利克雷分布是概率组合出现概率的统计，通过隐藏主题的发现过程，从而得到每一篇文档在不同主题下可能的概率分布。一篇文章可以包括多个不同的主题，但是每个主题得出可能的概率值不同。在一篇文章中某个主题的概率值，可以作为该主题该文本中主题突发的能量统计值，因此是基于文本流的主题爆发探测重要依据。

　3.2 2 爆发特征的 发现 算法 模型

　发现主题在时间维度上的变化特征的是爆发探测的关键环节。其主要思想是对其文本流的到达时间在时间维度上的分析计算，发现其突增，高涨，波动，衰减等一系列的变化和分布特征，从而确定主题的爆发时间和爆发特点。爆发特征的发现算法起初不局限于用在文本流的发现上，而是在物理学对伽马射线的爆发探测，或者经济学对股价的分析探测上，随着网络的发展，文本流的激增过程中，爆发特征探测也逐渐被引入到对文本流的探测任务中。爆发特征的发现算法主要有以下几个方面：

　（1）基于阈值的爆发探测：爆发探测研究，在早期 Swan and Allan (1999, 2000) 和 Swan and Jensen (2000)等人就提出了基于阈值探测的方法，但是这

　种方法具有局限性，它可以探测到显著的消息突发，但是对于短小连续的，类似于白噪声的突发则难以探测到。Towards Burst Detection for Non-Stationary Stream Data 文章使用大纲结构的转移聚集树与时间序列预测的相关技术相结合[11] ，提出了一种新的动态确定适当的阈值点的方法，通过实验发现这种方法对与线性的趋势爆发探测处理比较适用。

　（2）以“到达率”为依托的爆发探测：Kleinberg 在 Bursty and Hierarchical Structure in Streams 文章中提出了一种无限状态自动机的模型[12] ，根据突发消息的到达率而改变它的状态，不管到达率如何变化可以在数据流中探测到长期的范围内的突发变化。该算法设计了一个加权自动机模型，充分考虑到低爆发率中包含高爆发率，遵照爆发率依赖于当前的状态的思路，由简单的二维状态模型，引申为多维度无限状态模型，根据到达率的变化自动机改变当前自身的状态，从而自动适应爆发频率。从而实现爆发特征的捕获和探测。

　（3）基于窗口模型的爆发探测：在对多个领域的研究中使用的经典窗口算法模型主要包括：里程碑窗口模型、滑动窗口模型和阻尼窗口模型[13] 。这些模型的窗口大小是固定的，不能根据爆发到达率的变化而改变窗口的大小。纽约大学的 Yunyue Zhu 和 Dennis Shasha 在其论文 Efficient Elastic Burst Detection in Data Streams 中对经典的固定大小窗口模型的局限性做了改进，提出了弹性窗口爆发探测模型[14] 。弹性窗口算法实现类似小波分析的爆发监测，该算法提出了一种 Haar 的小波树层级数据结构。基于时间序列的数据流，可以分解成离散的数据块，通过多个层级小波树变化，在从低层级到高层级变换中，爆发数据会最终落入到一个窗口中，从而捕获到爆发特征。文章提出一种变换小波树（SWT）的算法，从而实现爆发特征更精确的定位。弹性窗口变换小波算法的优势在于：其利用离散数据流的特征，保存完整的信息，在小波变换中无信息损失；能够监测高维度的突发；算法执行效率高出传统统计型算法，几十个数量级，达到 O（n）的时间复杂度，方便大数据量的分析和爆发特征的检索。

　（4）聚集金字塔爆发探测算法[15] ：Better Burst Detection 一文对变换小波树或者简单的变换二元树会将很多事件窗口可能被错误的标注为爆发点的问题做出了改进，提出了聚集金字塔爆发探测算法。整个算法框架基于称为聚集金字塔（aggregation pyramid）的密集数据结构构建，框架中的所有数据结构都

　包含了聚集金字塔单元的子集，在此数据机构基础上，采用一种启发式的检索算法从众多的结构中发现最有效的几个，并给予对应的输入。通过对合成的数据和实际环境中的数据的实验发现，依据数据的分布，与变动二元树相比有很大的改进效果。

　（5）动力学加速度探测模型[16] ：主题动力学模型是建立在物理学的质量和速度—动力学概念基础上的，它的思想是将文本流的到达率看作是物理上能量的积累，引入物理学的动量、加速度、势能等概念，和物理学的思想，并将爆发看作一个物理学的动态现象，是一段时间内动量的增加。该模型构建了一个主题的加速度动态模型，基于该模型分析判断主题的爆发特征。

　4 4 算法 对比与 应用 分析

　从 Kleinberg 基于词频统计的爆发特征探测算法，到 LDA 等基于主题分布的提取，发现主题的探测。从基于阈值的突发监测方法，通过改进和演化发展到无限状态自动机、弹性窗口、金字塔模型、动力学模型等。并不能简单的说明算法的优点和缺点，在不同的应用场景下对信息失真度、爆发点定位的准确度、算法效率等要求各不相同，只有结合爆发探测的研究内容和实际应用环境，才能对算法做出实用性的选择。

　1 4.1 数据流 的 信息 保真度

　 主题结构判断中，不同聚类的算法对原始信息的表示都有一定的损失，本文称为信息的保真度。在以上算法中对信息的真实度还原表现不同的效果。文本主题聚类方法，例如 k-means 算法，可以根据预先设定对文本流聚类出 k 个主题分类。K 个主题分类中虽然有排序，但是没有完整的包含每个主题对爆发探测贡献能量的多少，如图 1 所示，k-means 算法只保留了最大可能的主题 2 能量贡献，而过滤掉其他主题的能量贡献能力，因此在后续计算爆发特征的时候，会造成计算量化的偏差。而 LDA 等主题分布模型，是概率组合出现概率的统计，在一个文本流中某个主题可能的概率值，如图 2 所示，在每个主题分布上的分布概率，可以作为该主题该文本中主题突发的能量统计值[17] ，因此在主题爆发量化的统计计

　算中，复杂的主题分布模型更具有信息的保真度。

　图 1 k-means 主题能量贡献

　图 2 LDA 主题能量贡献

　在爆发特征探测计算过程中，弹性窗口爆发探测模型和聚集金字塔爆发探测模型，都使用了小波变换树来提高爆发特征探测的准确性。由于在小波变换算法中，可以做到无信息损失，因此该类算法模型相对阈值分析和固定窗口模型的算法，有较高的信息爆发特征的保真性，这也是弹性窗口变换小波算法主要优点之一[14] 。

　4.2 爆发特征 计 算 的 准确性

　 在可见的爆发特征中可能分布着微小的潜在爆发特征，例如阈值探测方法中提到的“白噪声爆发特征”；Kleinberg 无限状态自动机模型中提到的“低爆发率中包含高爆发率”；Yunyue Zhu 和 Dennis Shasha 弹性窗口模型的研究称为“高维度爆发特征”。说明这种隐含爆发特征的准确定位是难度较大的，对这种高维度的爆发特征的探测是对几种算法模型的考验。基于窗口阈值的爆发探测方法，在处理复杂的高纬度爆发有很多局限性，如图 3 所示。

　 图 3 窗口阈值探测低维度爆发特征[13]

　图 4 变幻小波树高维度爆发特征模型[14]

　 无限状态自动机算法中，考虑高维度爆发而对现有算法做出改进。而弹性窗口小波变换算法在从低层级到高层级可以捕捉到落到高层级窗口的爆发特征，如图 4 所示。因此小波变换算法自身有利于捕捉到高维度的爆发特征[14] 。此外，爆发特征的窗口边界因素可能被误判为突发特征，也是硬性爆发特征准确性的重要因素。聚集金字塔爆发探测算法的重要改进即克服了变换小波树或者简单的变换

　二元树会将很多事件窗口可能被错误的标注为爆发点的问题。

　3 4.3 算法 的 执行效率 与应用场景

　长文本的文本流的主题爆发探测，由于单个文本信息丰富，容易从其中提取出反应的主题信息，因此更实用 LDA 等复杂 bag of word 的文本主题分布算法，列举出主题分布律，文本流中的主题分布概率将作为爆发探测中的主题能量，实现主题爆发探测。这种算法模型在计算效果和执行效率上并不一定适合高速的短文本流应用，如常用的 SNS 社交网络的评论信息，论坛，微博等[18] 。

　对于高速的短文本流的爆发主题探测中，较为复杂的 LDA 等主题分布模型表现并不良好。在 Online Burst Detection Over High Speed Short Text Streams一文中对高速文本流提出了一种简单的时间概率判断模型[19] ，并通过一系列的试验数据，证明了简单时间概率判断模型相对于 von-Mises Fisher (vMF)的混合模型和潜在狄利克雷分布(Latent Dirichlet Allocation，LDA) 的主题分布模型在处理高速短文本流的效率上的优势。

　5 5 结语

　 爆发主题探测涉及到文本流的主题结构的判定和爆发特征的发现两个方面的关键问题。针对两个关键问题研究分析其中主要算法的思想和优缺点，在信息保真度、爆发特征准确性、执行效率三个方面对几种典型算法进行比较分析。由于不同的算法在效率，文本和参数依赖性等方面各有不同特性，在不用的应用场景下，也衍生出相应适用于特定环境的算法模型。因此在算法的选择上需根据文本流特征、信息保真度要求、以及文本流到达频率所要求的算法效率等多方面综合考虑，选取适用的算法模型。

　参考文献 ：

　[1] Chen W, Chundi P. Extracting hot spots of topics from time-stamped documents[J]. Data & Knowledge Engineering, 2011, 70(7): 642-660,

　[2] Wayne Xin Zhao, Jing Jiang, Jing He, Dongdong Shan, Hongfei Yan, Xiaoming Li. Context modeling for ranking and tagging bursty features in text streams[C]. International Conference on Information and Knowledge Management, 2010: 1769-1772

　[3] Wei Chen, Parvathi Chundi. Extracting Hot Spots of Basic and Complex Topics From Time Stamped Documents[C]. IEEE Symposium on Computational Intelligence and Data Mining, 2009: 125-132

　[4] Yiu-ming Cheung, k*Means: A new generalized k-means clustering algorithm[J]. Pattern Recognition Letters, 2003, 24(15):2883-2893 [5]MacQueen, J. B. Some Methods for classification and Analysis of Multivariate Observations[J]. University of California Press. 2009, 4(4): 281–297. [6]H.S. Park , C.H. Jun. A simple and fast algorithm for K-medoids clustering[J], Expert Systems with Applications, 2009, 36(2):3336-3341. [7]T. Velmurugan and T. Santhanam. Computational Complexity between K-Means and K-Medoids Clustering Algorithms for Normal and Uniform Distributions of Data Points, Journal of Computer Science[J] 2010(3), 363-368. [8]Raymond T. Ng, Jiawei Han. CLARANS: A Method for Clustering Objects for Spatial Data Mining[J]. IEEE Transactions on Knowledge and Data Engineering, 2002.14(5):1003-1016

　[9] Peter Wiemer-Hastings, Latent Semantic Analysis[J]. Information Science and Technology,

　2004, 38(1): 188–230 [10] David M. Blei, Andrew Y. Ng, Michael I. Jordan. Latent Dirichlet Allocation[J]. Journal of Machine Learning Research, 2003(3): 993-1022 [11] Daniel Klan, Marcel Karnstedt, Christian Pölitz, Kai-uwe Sattler. Towards Burst Detection for Non-Stationary Stream Data[C]. Lernen, Wissensentdeckung und Adaptivitat, 2008: 57-60 [12] Jon M. Kleinberg. Bursty and Hierarchical Structure in Streams[C]. Data Mining and Knowledge Discovery, 2003:91-101 [13] Srivatsan Laxman, P. S. Sastry, K. P. Unnikrishnan. A Fast Algorithm for Finding Frequent Episodes in Event Streams[C]. Knowledge discovery and data mining, 2007:410-419 [14] Yunyue Zhu, Dennis Shasha. Efficient Elastic Burst Detection in Data Streams[C]. Knowledge discovery and data mining, 2003: 336-345 [15] Xin Zhang Dennis Shasha. Better Burst Detection[C]. Data Engineering, ICDE, 2006 [16] Satoshi Morinaga, Kenji Yamanishi. Tracking dynamics of topic trends using a finite mixture model[C]. Knowledge discovery and data mining, 2004:811-816 [17] Dan He, D. Stott Parker. Topic Dynamics: an alternative model of "Bursts" in Streams of Topics[C]. Knowledge discovery and data mining, 2010:443-452 [18] Michael Mathioudakis, Nick Koudas. Twitter Monitor : Trend Detection over the Twitter Stream[C]. International Conference on Management of Data , 2010:1155-1158 [19] Zhijian Yuan, Yan Jia, Shuqiang Yang. Online Burst Detection Over High Speed Short Text Streams[C]. International Conference on Computational Science, 2007:717-725

相关热词搜索：探测 算法 爆发