基于改进的SinglePass层次化在线话题聚类算法

潘夏晖虞欣平隋子明

（中国华艺广播公司福建福州350001）

摘要：针对网络数据的海量性和相对无序性，定义了多层次话题语义结构模型，基于多层次话题语义模型，对经典的SinglePass算法做出了改进，包括使用子话题质心来代表子话题内的文档、AverageLink比较策略、进行类似于K均值算法的聚类重调整的方法、子话题和话题的双层次语义结构。在实验过程中对比了在线话题的聚类算法的性能，确定了层次化在线话题聚类方法，形成有机统一的热点话题聚类模型，具有较高的应用价值和研究价值。

关键词：SinglePass；话题；聚类；语义结构

0引言

互联网具有海量信息，而且数以亿计的网民广泛参与，使得相同话题的相关信息以不同时间不同地点在互联网的不同媒体平台上分布，舆情管理部门往往很难全面把握某一话题。传统的靠人工来采集分析舆情信息的方法在面对如此大数据的情况下是不可取的，必须要通过相关的计算机技术，能够自动从互联网上爬取舆情信息，并且将这些无序分散的信息有效地组织起来进行分析，为舆情分析者提供参考依据。

热点话题发现隶属于话题检测，是TDT（TopicDetectionandTracking）话题检测与追踪的重要内容[1]。网络舆情分析中的话题检测一般称为在线话题检测，用到的聚类都是以增量方式进行的。Papka[2]对话题检测中不同的聚类算法进行了对比研究，并提出了一种融合各自优点的单路径聚类算法，即SinglePass聚类算法，该聚类算法很好的解决了聚类中增量的问题，但是该方法对初始输入数据的顺序非常敏感，聚类效果不够稳定；殷风景[3]在原有的SinglePass聚类算法做出了改进，加入了“代”的概念，将文本聚类分代进行，较好的解决了原始SinglePass聚类算法对初始数据敏感的不足，但是该方法在处理大规模数据的时候，也有运行时间过长、精度不高等问题；卡耐基-梅隆大学尝试采用凝聚层次聚类算法进行检测[4]，其核心思想是计算当前聚类集合中每对聚类的相关度，将满足阈值条件的一对聚类融合成新的聚类，通过反复迭代这一过程，系统最终把话题模型构造成具有层次关系的基于一个根节点的非循环有向图。但是该算法的一个重要的缺陷是时间和空间复杂度过高。

目前用于进行在线话题发现的聚类算法主要是SinglePass算法、K均值算法和基于密度的DBSCAN算法等。聚类算法研究很多，但是都是由于准确度不高、响应速度难以达到要求、需要增量式聚类以及用户难介入聚类结果等原因，在实际系统中实现了在线话题发现功能的算法很少，本文选取了话题发现研究中应用最多的SinglePass算法来实现多网络在线话题聚类，该算法参数简单，运算快捷，但也存在精度等方面的问题，所以本文在基于话题的语义结构模型基础上对该算法进行了一系列的改进，用于多层次话题的发现。

1多层次话题语义结构模型

话题是由若干相关子话题集合而成的抽象单元，它通常包含一个核心子话题以及所有与其直接相关的事件或活动，而子话题是最基本的语义单元，通常表示某一对象在某个时间或地点进行的一次活动，这样的子话题通常就对应于一个具体事件，但有些子话题可能缺少明显的地点、时间，甚至对象信息，所以若干个子话题构成的话题才能完整的表达一个事件或者活动的所有信息。层次结构中的各语义单元不仅包含语义内容，而且具有时间（甚至空间）属性，例如同一话题下的不同子话题既有内容上的关联关系，又有时间上的先后顺序。基于这一认识，语义结构模型利用多元组来表示不同的语义单元，在其中同时描述了单元的语义内容、信息来源（包括发布信息的网站、参与发帖/回帖的用户等）、与下层单元的关联关系、时间属性与空间属性等。

根据上一节中的定义以及网络舆情数据的结构性质，提出多层次话题语义结构模型。模型的层次结构如图1所示：

图1多层次话题语义结构模型示意图

Fig1.multi-hierarchicallytopicsemanticstructuralmodel

其中，表示的是最顶层的类别层，每个类别层可以聚类出多个话题，表示这些话题的所属的类别范畴。

表示的是话题集合。每个话题由多个子话题聚类而成，同一个话题内的子话题在语义内容，时间属性和空间属性上都有很大的相关性。

表示的是子话题集合。每个子话题由多篇文档聚类而成，子话题反映的是一个话题内部的信息冗余现象，每个子话题中报道包含的信息基本相似。子话题也有自身的一些属性信息，包括时间、标题、实体集、质心、文档数目等。

表示的最底层的文档集合，每篇文档属于且仅属于一个子话题。文档包含了属于该文本的所有基本信息，包括所属的类别、发布时间、标题内容和网络来源等。

2基于SinglePass的层次化在线话题聚类算法

2.1子话题层次的话题聚类

由于网络数据的增量性质，随着数据的不断到来，子话题将发生变化，然而SinglePass算法对于先到达的数据具有依赖性，这使得话题层的聚类难以进行。因此需要对文档数据进行分割，对每一部分的数据进行聚类，得到固定的子话题并不再改变，然后在对这些子话题进行聚类得到话题。

由于子话题往往对应于一个事件，具有一定的时间属性，因此可以按时间进行分批，由于数据到达是按时间排列的，因此可根据到达文本数量进行分批，也可以按照一定时间段对数据进行分批，但由于网络舆情数据的不确定性和话题的突发性，按时间段对数据进行分批难免会使得分批的数据大小不一，每一批之间的文本数量差距较大，所以本文使用按到达文本数量进行分批。这样对每一批内的文本进行文本聚类，得到的子话题不会再改变并可以用于话题层的聚类。

本文对文本数据的标题和内容都进行向量化应用到聚类算法中。因为舆情数据一般都有标题和内容两个属性，而一篇文本讲述的事件的重点内容或者说关键元素都体现在标题中，所以标题作为文本的一个属性也十分重要。由于标题所表达的内容很少，特别是在进行特征选取后仅剩下动词名词，内容信息更少，实验发现特征化后的标题参与聚类对于精度的提高并不明显，故本文对标题向量在分词后不进行特征化处理。经过实验，本文为标题相似度和正文相似度赋予的权重分别是0.3和0.7，来突出标题对聚簇区分所能起到的作用和内容对于一个聚簇真正的区分性。

对于一批内的文本数据，文本与聚簇间的距离根据计算类别的距离方法的不同，又分为了三类：Single-Link，Complete-Link以及Average-Link聚类方法。Single-Link聚类法就是聚簇间距离等于两聚簇对象之间的最小距离，若用相似度衡量，则是一个聚簇中的任一向量与另一聚簇中任一向量的最大相似度。Complete-link聚类法就是聚簇间的距离等于两个聚簇间向量之间的最大距离。在Complete-link的层次局类中，每一步合并了最小半径的一对类别，或者说是有一对距离最小的最大值。Average-link聚类法是聚簇间的距离等于两聚簇向量之间的平均距离。虽然Single-link聚类法足够简单，但面对实际数据时Average-link聚类法的准确度更佳，而且能有效减少大类的出现[5]，所以本文选择使用Average-link聚类方法。故文本与聚簇之间的距离公式定义如下：

（1）

对于SinglePass算法本身，虽然在线网络数据按照时间具有一定的组织顺序，可一定程度上弱化SinglePass算法对文本进入顺序敏感的缺陷。但文本按照时间的顺序进入并不一定是最佳的进入顺序，SinglePass算法不一定能取得理想的效果。因此本文采用类似与K均值算法的聚类重调整步骤。即在聚类完成后，计算每一个数据点到各聚簇的距离，选择与其最接近的聚簇，若其相似度满足SinglePass聚类时采用的阈值，将该聚类单元调整到此聚簇中，如此反复调整直到满足终止条件，从而减小到达距离对聚类结果的影响。在这过程中存在两个问题，一是终止条件的选择，由于调整会产生连锁反应，在后期很有可能会产生振荡使得调整无法结束，因此本文设置终止条件为当90%的文本不需要调整时，便达到终止条件。二是对单文本聚簇的处理。因为对于只有一个文本的簇，其文档总是会和自身聚簇的距离最近，不可能得到调整，因此在对单文本聚簇的文本进行单独处理，即只计算该文本与其它聚簇的距离，看其最近的距离是否满足SinglePass聚类时采用的阈值，若满足，则将其并入该类，否则仍为单文本簇。经过重调整的步骤，可以大大减小文本进入顺序对算法的影响，提高聚类效果。聚簇重调整流程如图2所示：

图2聚簇重调整算法流程

但是由于分批方法的强制性，可能会使得本身发表在同一时间段内且属于同一子话题的文本被分到不同的批次，也就不可能在同一个子话题中，违背了实际情况。为了解决该问题，本文在每一批子话题形成后，计算其与上一批所有的子话题的质心距离，若两个子话题距离小于严格阈值，将这两个子话题合并作为一个子话题。

2.2话题层次的话题聚类

在话题层，要进行聚类的不是文本而是子话题，其过程是用SinglePass算法将子话题聚成话题。子话题也是用向量空间模型表示，一个子话题也和一篇文本一样有标题向量和内容向量。对于新的一批数据的子话题，要与旧话题内的子话题进行距离比较，就需要计算聚簇与聚簇之间的距离，计算该距离需要聚簇的质心（也就是子话题的质心），质心有很多种定义方法，在文本聚类中一般使用的是平均质心，对于n个文本向量（标题向量或者内容向量），其平均质心的计算公式如下：

（2）

在这里，话题层的聚类和子话题的聚类方法是一样的，两者只是输入的数据不一样，子话题层聚类输入的是文本的标题向量和内容向量，而话题层的输入则是子话题的标题质心向量和内容质心向量，所以，话题层的聚类也会有一个重调整的过程，方法和子话题层的一样。

综上所述，在线话题层次化聚类总流程为：

图3.4层次化在线话题聚类总流程

图3.4中两次聚类重调整步骤流程在图3.3中已经介绍。注意在对话题层进行聚类的过程中，子话题为聚类单元，相当于历史所有的子话题都参与了聚类，重调整时也会全部调整。但是由于在线数据庞大，而且随着时间的推移，数据量会有累积过程，这使得一定时间后算法效率将大大降低，计算时间和和空间都将无法接受。为了解决该问题，本文采取三个措施：

1、话题消亡。

大多数话题都有其产生、发展和消亡的过程，一些话题在经过一定时间后不再会（或很少）有人再提起，可认为该话题消亡，对于这些话题，将其去除不再考虑，具体方法将在下一节介绍。

2、对子话题数目较多的话题只取部分子话题作为话题代表。

对于部分话题（如股市），由于每天都会有报道，那么其数据会随时间呈线性增长，新的子话题要聚到已有话题中必须和每一个已有子话题比较，这将使计算量不断增大。然而一个话题中往往讨论相似问题，只需选出一些代表子话题即可。对于代表子话题的选取，一方面近期子话题代表话题演化到当前的一个趋势，应当保留；另一方面对于早期的子话题，代表了话题的主体，也应有一定体现。因此本文选取每个话题中近几批次的子话题加上之前数据中随机抽取一定数量的子话题一起作为该话题的代表子话题，用于话题层次的聚类和调整中的相似度计算。

3、只对近期子话题进行偏离重调整

原算法在对子话题聚类的重调整过程中将会对所有的子话题进行重调整，由于历史数据庞大且不断增多，计算量也会很大。但是对于一些话题，经过一段时间后已经比较稳定，对于这些稳定话题，初始的子话题不应再作调整，因此本文仅选择近几个批次的子话题进行重调整。

在实际实验的过程中，这三个步骤使得话题的聚类能够在在线的模式下快速高效地进行，显著的减少了整体的运算量。

3实验与结果分析

对于话题聚类性能的比较，本文选取了聚类速度和聚类精度两个主要指标进行衡量。

1、聚类速度的对比

因为热点话题发现聚类算法的运行速度包含了诸多聚类算法之外的因素的影响，比如信息采集的速度、信息分类的速度、分词速度，所以无法准确表达聚类算法在速度方面的性能，而在前文中本文已经选取了向量空间模型来进行话题的聚类，所以分词及向量空间模型的构建都不计入在聚类算法的运行速度之内，本文将对经典的K均值聚类算法、SinglePass聚类算法和本文提出的层次化的话题聚类算法的运行速度进行对比。

本文选取了系统运行实例中所采集的从2012年3月19日起至2012年9月04日之间的台湾新闻舆情数据，共183709篇新闻文档作为实验数据。

首先，从该数据集中通过人工标记抽取了2542篇新闻数据，共94个话题作为研究对象，新闻文本的标题、内容经过分词、分词优化后构建向量空间模型，然后对各算法进行实验比较，下图3.5为运行结果，单位为秒（S）。

图3.5聚类算法运行速度比较

图3.5中K均值算法在开始的时候把聚类数目设定在94个，所有算法在运行的时候每产生10个话题输出计算时间。K均值聚类算法在开始的时候随机产生94个聚簇中心，然后对剩下的文本进行凝聚，K均值算法在产生前面94个话题的时间非常短，剩下的时间都是在重新调整簇中心和迭代。SinglePass算法和层次化在线话题聚类算法在前期算法运行时间相差不大，由于层次化在线话题聚类算法是分批次进行聚类的，所以在前期整体上看运行时间要比SinglePass算法稍微大一些，在聚类快要完成的时候，层次化在线话题聚类算法进行重调整的步骤，这一步和K均值算法的后期工作相接近，但由于前期算法本身就已经进行了聚类，不像K均值一样随机分配聚簇的中心，所以层次化在线话题聚类算法花费的调整时间要比K均值少很多。

总的来说，在文本数较少的情况下，SinglePass算法运行速度最快，而K均值算法最慢，但是，在线情况下，需要用大规模的数据集进行比较，而且在现实情况下，数据比较“脏”，含有很多噪音数据，话题的数目也不确定，因此，本文舍弃了K均值算法，用大规模的现实数据文本对SinglePass算法和层次化在线话题聚类算法进行了实验比较。选取系统运行实例中所采集的从2012年3月19日起至2012年4月19日之间的台湾新闻舆情数据按照时间顺序排序，共21387条作为实验数据进行对比试验。

由于需要处理大规模数据，实验中，数据之间的交换时间（如数据库更新、插入等操作花费的时间）不计算在内，所有文本在实验前也已经做好预处理和向量化，得到的实验结果图如下图3.6所示：

图3.6大规模文本聚类算法运行速度比较

图3.6中可以看出，对于经典的SinglePass算法而言，文档数目越多，算法运行需要消耗的时间就越大，因为聚簇数目越多，SinglePass算法就需要越多的时间进行计算比较。而对于层次化在线话题聚类算法，加入了话题的消亡，子话题代表等措施，大大减少了计算比

较的次数，而且可以发现，在在文档数目过了10000篇以后，层次化在线话题聚类算法的计算时间大致稳定在一个范围，不会再继续增加，这是因为到了一定阶段，话题的产生的数目和消亡的数目相平衡，系统会到达一个稳定状态。因此，层次化在线话题聚类算法在实际应用中也会达到一个稳定状态，该算法是合理可行的，可以运用到实际应用中。

2、聚类精度的对比

本文主要选择F-Score[6]和NMI（normalizedmutualinformation）[7]两种指标作为聚类精度的定量评价指标，其中F-Score是查准率和查全率的结合，查准率与查全率的定义如下：

在聚类结果中全局的F-Score的定义为每个标记话题的F-Score的加权平均值：

式（3.8）

F-Score越高表明聚类效果越好。

归一化互信息NMI定义如下：

式（3.9）

其中，X是聚类结果，Y是标记结果，k是聚类结果中聚簇话题的总数，c是标记话题的总数。当NMI=l时，聚类与实际类别完全匹配；NMI=0则意味着文档完全随机散布。NMI越高表明聚类效果越好。

同样选取数据集中通过人工标记抽取的2542篇新闻数据，共94个话题作为实验对象，层次化在线话题聚类算法中不考虑话题的衰减和子话题代表，分别利用K均值算法、SinglePass算法和层次化在线话题聚类算法进行实验比较，得到结果如下表3.1：

表1聚类算法精度比较

Table1Comparisonofalgorithmsperformance

因为层次化在线话题聚类算法是在经典SinglePass算法上按照批次进行话题的聚类，而且在聚类后期还引入了K均值的思想进行调整，所以该算法聚类出的数目更加接近真实值，而且聚类的精度也要比K均值算法和经典SinglePass算法好很多。

可以看出，本文的提出的层次化在线话题聚类算法在大规模文本数据集上无论在运行时间上还是在计算精度上都要优于SinglePass算法，而对于K均值算法，它本身就不适合在线话题聚类，故不选择。综合起来考虑本文选择层次化在线话题聚类算法为话题发现算法。

4结束语

本文基于多层次话题语义结构模型的热点话题发现的具体处理流程，首先介绍了多层次话题语义结构模型，然后介绍了目前应用在文本聚类中的几种主要的聚类算法，并通过对各聚类算法按照在线话题聚类算法评价标准的比较分析，选用SinglePass算法作为文本聚类的主要方法，并提出了基于SinglePass算法的层次化在线话题聚类。本文提出的基于多层次话题语义结构模型的层次化在线热点话题聚类方法虽然适合在线话题聚类，而且对比传统的SinglePass算法上，精度和实用性都有了很大的提高，但是然而因为这类基于向量空间模型的文本表示方法和基于余弦距离的相似性的固有的缺陷，使得这类算法难以发现凸状类簇之外的类簇，制约了算法的适用性，也在一定程度上削弱了算法的精确程度。如何解决在线话题聚类的这些难题，是文本聚类领域重要的问题。

参考文献：

[1]JAllan，JCarbonell，GDoddington．TopicDetectionandTrackingPilotStudy：FinalReport[A]．In：ProceedingoftheDARPABroadcastNewsTranscriptionandUnderstandingWorkshop[C]，SanFrancisco，1998：194-218.

[2]RonP．On-lineNewEventDetection，ClusteringandTracking[D]．Amherst：DepartmentofComputerScience，UMASS，1999.

[3]殷风景，肖卫东，葛斌，李芳芳．一种面向网络话题发现的增量文本聚类算法[J]．计算机应用研究，2011．1：54-57

[4]YYang，TPierce，JCarbonell．AstudyonRetrospectiveandOn-LineEventdetection[A]．In：Proceedingsofthe21stannualinternationalACMSIGIRconferenceonResearchanddevelopmentininformationretrieval[C]．1998，CMU，USA：ACM，28-36

[5]JPonteandWBCroft．Textsegmentationbytopic[A]．In：ProceedingsoftheEuropeanConferenceonResearchandAdvancedTechnologyforDigitalLibraries[C]．Europe：ECDL，1997，pages113.

[6]Christopher，D．M．，&Hinrich，S．（2001）．Foundationsofstatisticalnaturallanguageprocessing（pp．529–574）．Cambridge，Massachusetts：MITPress.

[7]M．Steinbach，G．Karypis，andV．Kumar．Acomparisonofdocumentclusteringtechniques．KDD-2000WorkshoponTextMining，August2000.

[8]ICTCLAS．ICTCLAS[EB/OL]．http：//www．ictclas．org．2012．1.

[9]GiridharKumaran，JamesAllan，TextClassificationandNamedEntitiesforNewEventDetection．Proceedingsofthe27thannualinternationalACMSIGIRConferenceonResearchanddevelopmentininformationretrieval，Sheffield，UnitedKingdom．July25-29，2004.

[10]RahnamayanS，TizhooshHR，SalamaMM.Opposition-baseddifferentialevolution[J].IEEETransactionsonEvolutionaryComputation，2008，12（1）：64-79.

[11]李伟，黄颖．文本聚类算法的比较[J]．科技情报开发与经济．2006，22（10）：69-72.