一种基于图聚类的用户生成文本流中的突发话题检测方法

摘要

本发明涉及一种基于图聚类的用户生成文本流中的突发话题检测方法，属于互联网数据挖掘技术领域。该方法提供了相对传统的话题检测问题的一种基于图的新视角，将在文本流中检测突发话题转化为一个典型的图聚类问题，这样可以根据已有的图论方法来得到解决。该方法主要步骤包括：获取文本流；检测突发词；构建突发词图；聚类突发词。该方法针对用户生成文本流中的突发话题检测，其性能优于已有的基于文档聚类、概率话题模型和基于突发特征聚类的方法。

主权项

1.一种基于图聚类的用户生成文本流中的突发话题检测方法，其特征在于，该方法包括以下步骤：1)获取用户生成文档：首先从Web 2.0站点采集大量网页格式的文档；然后从该网页格式的文档中提取出文档正文作为处理后的文档，同时提取该文档的发表时间，并保存；2)构造文本流：设定时间单位，并将检测时间窗的大小设定为一个时间单位；根据时间窗对所述处理后的文档进行划分，将同一时间窗内的所有处理后的文档组成一个文档集，将所有文档集按照时间顺序组成文本流；将前t₁个时间窗的文档集作为话题检测的参考文档集；3)检测突发词：对t时刻，t≥t₁+1的文档集进行话题检测，遍历字典中所有的词并判定是否是突发词；若某个词在t时刻出现率大于该词在参考文档集中的平均出现率的一定倍数T_b时，则判为突发词，T_b的取值范围为2.5-10；4)构建初始突发词图：将t时刻检测到的突发词连接成无向加权的初始突发词图G_t，该图的顶点是突发词，该图的边的权重用Jaccard相似度度量；5)约简突发词图：按照所述初始突发词图G_t中边的权重，从小到大的顺序移除边；用表示移除i条边后的中间图，则该中间图形成对原图G_t的顶点集合的一个聚类L⁽ⁱ⁾(G_t)，聚类中的一类对应于中间图一个最大联通子图的顶点集合；计算聚类L⁽ⁱ⁾(G_t)的模块性Q⁽ⁱ⁾，找到最大的模块性Q⁽ⁱ⁾并输相应的中间图作为约简后的突发词图；6)突发话题检测：对约简后的突发词图的每一个最大连通子图s提取内聚子图，将大于N个顶点的内聚子图中所有顶点集合对应词的组合为检测出的突发话题，N取值为大于3的正整数。