CN103678670B - 一种微博热词与热点话题挖掘系统及方法 - Google Patents

Abstract

本发明涉及社交网络技术领域，特别是一种微博热词与热点话题挖掘系统及方法，所述方法包括如下步骤：对微博中发布的内容数据进行预处理，获得候选热词序列；根据候选热词集合，考虑候选热词在当前时刻和给定历史时间窗口内的出现频率和突发性，计算每个候选热词的生命力，筛选出热词集合；根据筛选出的热词集合，计算热词相关性，构造热词共现网络；根据热词共现网络，使用基于多标签传播的热词聚类算法对热词集合进行划分，获得热点话题集。该系统及方法可以实现微博热词与热点话题的高效挖掘，提高了挖掘精度和处理效率。

Description

一种微博热词与热点话题挖掘系统及方法

技术领域

本发明涉及社交网络技术领域，特别是一种微博热词与热点话题挖掘系统及方法。

背景技术

随着微博的兴起，人们的参与度不断地提高，用户可以通过电脑、手机随时随地地发布自己的所见所闻，并实现即时分享。现在微博已成为互联网的一种时尚，同时也是热点话题产生和讨论的重要场所，热点话题是指在一段时间内，频繁出现在网络上，人们广泛关注并讨论的话题。微博信息的指数增长，使得如何有效地掌控海量信息并提取热点话题，成为亟待解决的问题。

对于热点话题检测，传统的方法是对文本进行聚类，但是这种方法不利于用户直观地识别出热点话题，而且微博具有短文本特性，数据稀疏且分布不平衡，导致这类方法用于发现热点话题的效果并不理想。因此主流的方法是通过热词抽取并聚类实现热点话题发现。

用来权衡词重要性并抽取热词的经典方法有TFIDF和TFPDF等。TFIDF的主要思想是，词出现的频率并不能充分代表文本特征，比如“是”、“神马”这种词，频繁出现，但几乎没有表述文本的能力。而如果一个词在该文本的出现的频率非常高，在其他文本中出现的次数低，这样就能更加充分体现出这个文本的特征，然而，这种方法并不适合于微博中词的权重计算，微博具有短文本特性，一条微博上很少会出现重复的词，而且微博上的热点话题出现之后，会引起用户的广泛转发和讨论，大量微博上包含有同样的关键词，如果用TFIDF的方法来进行关键词抽取，会在一定程度上导致重要词汇遗失。因此，有学者提出了TFPDF的方法，其赋予那些在多数文档中出现的词更高的权重，来抽取热点词汇。这种方法有利于提取热点话题相关的重点词汇，但是也会提取出一些频繁出现但没有表述话题能力的词。热点词汇是指在一段时间内词频剧增的词，而上述两种方法都没有考虑到词随时间的分布情况，不利于热词的抽取。

针对热词聚类，现有的方法有：1）采用初始簇不敏感的Bisecting K-mean聚类算法；2）通过构建词相似度矩阵，利用Affinity Propagation算法在无需指定簇个数情况下进行聚类，其时间复杂度接近；3）基于密度聚类的算法，如DBSCAN；4）层次聚类算法等。

对于海量微博数据的热点发现问题，现有的热词聚类方法的主要问题在于：首先，聚类结果中不同的话题所涉及的词不允许存在交集，这与实际情况并不相符，易导致一些话题没有被发现，或者是话题的辨识度很低。比如，“高校花费问题”和“高校排行榜”这两个话题中，“高校”一词最多只能属于一个话题，而这两个话题无论哪个缺少了“高校”这一关键词，将很难辨识出原本的话题。另外，传统的聚类算法时间复杂度较高，难以适应海量微博数据聚类的要求。

综上，针对社交网络中用户个体的影响力分析已经出现了较完善的技术和方法，但是针对社交网络中社区级别的影响力分析的方法还相对较少，且缺乏对社交网络中各社区的影响力的全面分析评估，面对大规模社交网络的场景，现有方法无论是在分析效果和效率上都难以满足要求。

发明内容

本发明的目的在于克服现有技术的不足，提供一种微博热词与热点话题挖掘系统及方法，该系统及方法有利于提高微博热点发现的准确率和处理效率。

为实现上述目的，本发明的技术方案是：一种微博热词与热点话题挖掘系统，所述系统包括：预处理模块、热词筛选模块、热词共现网络构造模块和热词聚类模块；

预处理模块，用于对社交网络中发布的内容数据进行预处理，获取候选热词，并以此构建候选热词集合；

热词筛选模块，用于根据所述候选热词集合中各个候选热词在当前时刻和给定历史时间窗口内的出现频率和突发性，计算每个候选热词的生命力，筛选出热词，并以此构建热词集合；

热词共现网络构造模块，用于计算热词集合中各个热词的相关性，并以此构造热词共现网络；

热词聚类模块，用于根据所述热词共现网络，使用基于多标签传播的热词聚类算法对热词集合进行划分，获得热点话题集。

本发明还提供一种微博热词与热点话题挖掘方法，所述方法包括如下步骤：

步骤A：对社交网络中发布的内容数据进行预处理，获取候选热词，并以此构建候选热词集合；

步骤B：根据所述候选热词集合中各个候选热词在当前时刻和给定历史时间窗口内的出现频率和突发性，计算每个候选热词的生命力，筛选出热词，并以此构建热词集合；

步骤C：计算所述热词集合中各个热词的相关性，并以此构造热词共现网络；

步骤D：根据所述热词共现网络，使用基于多标签传播的热词聚类算法对热词集合进行划分，获得热点话题集。

进一步地，所述步骤B中，筛选热词并构建热词集合的过程，具体包括以下步骤：

步骤B1：计算在时间段t 内，各个候选热词的营养值；候选热词w 的营养值Nutr _w,t 为在时间段t内，微博集合tw ^t 中每条微博对候选热词w的营养值的贡献之和，计算公式为：

其中，Contr _w,j 为在时间段t内，第j条微博对候选热词w的营养值的贡献，j∈tw ^t ，计算公式为：

其中，表示第j条微博中出现候选热词w的次数，表示第j条微博中的最大词频；

步骤B2：利用候选热词w的突发值来描述候选热词w的词频在当前时间段与历史时间段之间变化的剧烈程度；候选热词w的突发值B _w,t 的计算方法为：取时间段t之前的k个历史时间窗口，历史时间窗口大小与时间段t相同，然后基于二项式分布的离散事件模型，分别统计在时间段t和时间段t之前k个历史时间窗口内包含候选热词w的微博数，采用统计公式，计算候选热词w在时间段t内的突发值，计算公式为：

其中，A表示在时间段t内，包含候选热词w的微博数；B表示在k个历史时间窗口内，包含候选热词w的平均微博数；C表示在时间段t内，不包含候选词w的微博数；D表示在k个历史时间窗口内，不包含词候选热词w的平均微博数；

步骤B3：结合各个候选热词的营养值和突发值，计算每个候选热词的生命力值；归一化的候选热词w的生命力值life _w,t 的计算方法为：

其中，terms表示候选热词集合，w’表示候选热词集合terms中的元素；

步骤B4：根据候选热词的生命力值，对候选热词集合中的候选热词进行排序，筛选出排序靠前的L个候选热词作为热词，并以此构成热词集合。

进一步地，所述步骤C中，热词z和热词k在给定时间段t内的相关性c _z,k 定义为：

其中，r _z,k 表示同时包含热词z和热词k的微博数，n _z 表示包含热词z的微博数，R _k 表示包含热词k的微博数，N表示时间段t内所有的微博数，即N=tw ^t ；

热词共现网络定义为G(V,E,W)，其中为节点集合，表示所述步骤B中得到的热词集合，m表示节点个数；E表示节点之间边的集合，对于任意两个节点，如果这两个节点代表的词存在共现关系，则构建这两个顶点之间的边；W表示边的集合E到实数集合R的映射，若v _i ，v _j 之间有边，则边权值为第i个热词和第j个热词之间的相似度sim(i, j)，定义为：

。

进一步地，所述步骤D中， 热词集合中的每个热词，即每个节点都有一个标签隶属度集合，在每次迭代中更新节点的标签隶属度集合，直到算法收敛，具体包括以下步骤：

步骤D1：根据所述热词共现网络，进行节点的标签初始化；

步骤D2：随机获取未更新标签的节点v，遍历节点v的邻居节点，根据邻居节点的标签集合，更新节点v的标签集合中每个标签的隶属度，对节点v进行标签隶属度归一化；

步骤D3：反复迭代，直到满足迭代终止条件；

步骤D4：根据迭代获得的节点的标签隶属度集合，对节点进行归类，获得热点话题集。

进一步地，所述步骤D1中，标签初始化的方法为：为每个节点分配一个唯一的标签号，并分别以隶属度隶属于这个标签号，这些唯一的标签号集合记为uniqueLabels。

进一步地，所述步骤D2中，标签隶属度的更新规则为：随机获取未更新标签的节点v，获取该节点的邻居节点集合Nb(v)，进而得到邻居节点拥有的标签集合labels，则在第h次迭代，节点v属于标签号的隶属度为：

其中，sim(u, v)表示节点u 和节点v之间的相似度，分母用于标签隶属度的归一化，保证节点v的标签隶属度之和为1。

进一步地，所述步骤D3中，迭代终止条件为：

其中r _h 定义为：

当，迭代结束。

相较于现有技术，本发明的有益效果是：根据候选热词在当前时刻和给定历史时间窗口内的出现频率和突发性，计算每个候选热词的生命力，筛选出热词集合，并根据筛选出的热词集合，计算热词相关性，构造热词共现网络，使用多标签传播的热词聚类算法对热词集合进行划分，获得热点话题集合。所述系统和方法可以实现社交网络热点话题的高效挖掘，在话题检测精度和处理效率上均有提高。

附图说明

图1是本发明系统的模块结构示意图。

图2是本发明方法的流程图。

图3是本发明方法中微博热词聚类的实现流程图。

具体实施方式

下面结合附图及具体实施例对本发明作进一步的说明。

图1是本发明的微博热词与热点话题挖掘系统的模块结构示意图。如图1所示，所述系统包括：预处理模块100、热词筛选模块200、热词共现网络构造模块300和热词聚类模块400。

预处理模块100用于对社交网络中发布的内容数据进行预处理，获取候选热词，并以此构建候选热词集合；热词筛选模块200用于根据所述候选热词集合中各个候选热词在当前时刻和给定历史时间窗口内的出现频率和突发性，计算每个候选热词的生命力，筛选出热词，并以此构建热词集合；热词共现网络构造模块300用于计算热词集合中各个热词的相关性，并以此构造热词共现网络；热词聚类模块400用于根据所述热词共现网络，使用基于多标签传播的热词聚类算法对热词集合进行划分，获得热点话题集。

图2是本发明的微博热词与热点话题挖掘方法的流程图。如图2所示，所述方法包括如下步骤：

步骤A：对社交网络中发布的内容数据进行预处理，获取候选热词，并以此构建候选热词集合。

具体的，可使用中科院的ICTCLA进行分词及词性标注，提取对话题有较强表达能力的名词和动词，之后使用停用词表进一步过滤，得到候选热词集合，记为，r表示候选词数。

步骤B：根据所述候选热词集合中各个候选热词在当前时刻和给定历史时间窗口内的出现频率和突发性，计算每个候选热词的生命力，筛选出热词，并以此构建热词集合。

所述步骤B中，筛选热词并构建热词集合的过程，具体包括以下步骤：

步骤B1：计算在时间段t内，各个候选热词的营养值；候选热词w的营养值Nutr _w,t 为在时间段t内，微博集合tw ^t 中每条微博对候选热词w的营养值的贡献之和，计算公式为：

其中，Contr _w,j 为在时间段t内，第j条微博对候选热词w的营养值的贡献，j∈tw ^t ，计算公式为：

其中，表示第j条微博中出现候选热词w的次数，表示第j条微博中的最大词频；

步骤B2：利用候选热词w的突发值来描述候选热词w的词频在当前时间段与历史时间段之间变化的剧烈程度；候选热词w的突发值B _w,t 的计算方法为：取时间段t之前的k个历史时间窗口，历史时间窗口大小与时间段t相同，然后基于二项式分布的离散事件模型，分别统计在时间段t和时间段t之前k个历史时间窗口内包含候选热词w的微博数，采用统计公式，计算候选热词w在时间段t内的突发值，计算公式为：

其中，A表示在时间段t内，包含候选热词w的微博数；B表示在k个历史时间窗口内，包含候选热词w的平均微博数；C表示在时间段t内，不包含候选词w的微博数；D表示在k个历史时间窗口内，不包含词候选热词w的平均微博数；

步骤B3：结合各个候选热词的营养值和突发值，计算每个候选热词的生命力值；归一化的候选热词w的生命力值life _w,t 的计算方法为：

其中，terms表示候选热词集合，w’表示候选热词集合terms中的元素；

步骤B4：根据候选热词的生命力值，对候选热词集合中的候选热词进行排序，筛选出排序靠前的L个候选热词作为热词，并以此构成热词集合。

具体的，计算得出各热词的生命力值后，可以采用快速排序(Quick Sort)算法，按照生命力值从高到底对候选热词进行排序，按照给定的阈值M，选择生命力值最高的前M个候选热词作为时间段t内的热词。

步骤C：计算所述热词集合中各个热词的相关性，并以此构造热词共现网络。

所述步骤C中，热词z和热词k在给定时间段t内的相关性c _z,k 定义为：

其中，r _z,k 表示同时包含热词z和热词k的微博数，n _z 表示包含热词z的微博数，R _k 表示包含热词k的微博数，N表示时间段t内所有的微博数，即N=tw ^t ；

热词共现网络定义为G(V,E,W)，其中为节点集合，表示所述步骤B中得到的热词集合，m表示节点个数；E表示节点之间边的集合，对于任意两个节点，如果这两个节点代表的词存在共现关系，则构建这两个顶点之间的边；W表示边的集合E到实数集合R的映射，若v _i ，v _j 之间有边，则边权值为第i个热词和第j个热词之间的相似度sim(i, j)，定义为：

。

步骤D：根据所述热词共现网络，使用基于多标签传播的热词聚类算法对热词集合进行划分，获得热点话题集。

基于多标签传播的热词聚类算法的特点在于：由于基于人类语言或文本文档构建的词汇共现网络具有高聚度、短路径特性。因此一个话题可以看成是内部连接紧密与外部链接稀疏的点（词）的集合，符合复杂网络中对社区的定义，再者，话题之间可能存在重叠的关键词，则话题发现问题可以转换为对词共现网络 进行重叠词社区划分的问题；多标签指允许一个节点具有多个社区标签，属于多个热词社区，即允许一个热词属于多个话题。每个标签携带着一个标签隶属度， 在标签传播过程中，对节点的标签和标签隶属度值进行更新，并根据设定的阈值对每个节点的标签集合进行裁剪，最终根据每个节点所拥有的标签将节点划分到多个社区（热点话题）。

所述步骤D中， 热词集合中的每个热词，即每个节点都有一个标签隶属度集合，在每次迭代中更新节点的标签隶属度集合，直到算法收敛。图3是本发明方法中步骤D的实现流程图，具体包括以下步骤：

步骤D1：根据所述热词共现网络，进行节点（热词）的标签初始化；

所述步骤D1中，标签初始化的方法为：为每个节点分配一个唯一的标签号，并分别以隶属度隶属于这个标签号，这些唯一的标签号集合记为uniqueLabels。

步骤D2：随机获取未更新标签的节点v，遍历节点v的邻居节点，根据邻居节点的标签集合，更新节点v的标签集合中每个标签的隶属度，对节点v进行标签隶属度归一化；

所述步骤D2中，标签隶属度的更新规则为：随机获取未更新标签的节点v，获取该节点的邻居节点集合Nb(v)，进而得到邻居节点拥有的标签集合labels，则在第h次迭代，节点v属于标签号的隶属度为：

其中，sim(u, v)表示节点u 和节点v之间的相似度，分母用于标签隶属度的归一化，保证节点v的标签隶属度之和为1。

步骤D3：根据给定的阈值p，对节点v的标签集合进行过滤，之后对保留的标签的隶属度值再次进行归一化；

具体的，步骤D3需要给定一个参数p在迭代过程中对标签隶属度更新后的节点的标签集合进行过滤，只保留部分标签，防止节点的标签集合过于庞大，p的大小表示允许节点拥有的最大标签数量，具体过滤规则为：删除节点的标签隶属集合中的隶属度低于1/p的元素。过滤后得到的标签集合再一次进行归一化，保证节点的各个标签隶属度总和为1。

步骤D4：反复迭代，直到满足迭代终止条件；

所述步骤D4中，迭代终止条件为：判断相邻两次迭代中在产生的标签集合一样的情况下，如果历史记录的各个标签的内部节点数量不再发生变化，则迭代结束，即：

其中r _h 定义为：

当，迭代结束。

步骤D5：根据迭代获得的节点的标签隶属度集合，对节点（热词）进行归类，获得热点话题集。

具体的，迭代结束之后检测各个节点的标签集合，将节点（热词）划分到相应的类别（社区），根据给定的阈值M，每个类别（社区）只需要取生命值排名靠前的M个热词用于表达对应的热点话题。M默认取值10。

本发明所述微博热点话题检测系统及方法，综合考虑词出现的频率和突发性，设计了一种新颖的词生命值计算模型进行热词抽取，之后构建词共现网络，并基于接近线性时间复杂度的多标签传播进行热词聚类，得到热点话题。综上，上述系统和方法能够有效的提取热词与热点话题，并在热点话题检测的精度和时间效率上有较大提高。

以上是本发明的较佳实施例，凡依本发明技术方案所作的改变，所产生的功能作用未超出本发明技术方案的范围时，均属于本发明的保护范围。

Claims (6)

1.一种微博热词与热点话题挖掘方法，其特征在于，所述方法包括如下步骤：

步骤A：对社交网络中发布的内容数据进行预处理，获取候选热词，并以此构建候选热词集合；

步骤B：根据所述候选热词集合中各个候选热词在当前时刻和给定历史时间窗口内的出现频率和突发性，计算每个候选热词的生命力，筛选出热词，并以此构建热词集合；

步骤C：计算所述热词集合中各个热词的相关性，并以此构造热词共现网络；

步骤D：根据所述热词共现网络，使用基于多标签传播的热词聚类算法对热词集合进行划分，获得热点话题集；

所述步骤B中，筛选热词并构建热词集合的过程，具体包括以下步骤：

步骤B1：计算在时间段t内，各个候选热词的营养值；候选热词w的营养值Nutr_w,t为在时间段t内，微博集合tw^t中每条微博对候选热词w的营养值的贡献之和，计算公式为：

${\mathrm{Nutr}}_{w,t}=\underset{j\∈{\mathrm{tw}}^t}{\Σ}{\mathrm{Contr}}_{w,j}$

其中，Contr_w,j为在时间段t内，第j条微博对候选热词w的营养值的贡献，j∈tw^t，计算公式为：

${\mathrm{Contr}}_{w,j}=\frac{{\mathrm{tf}}_{w,j}}{{\mathrm{tf}}_j^{\max }}$

其中，tf_w,j表示第j条微博中出现候选热词w的次数，表示第j条微博中的最大词频；

步骤B2：利用候选热词w的突发值来描述候选热词w的词频在当前时间段与历史时间段之间变化的剧烈程度；候选热词w的突发值B_w,t的计算方法为：取时间段t之前的k个历史时间窗口，历史时间窗口大小与时间段t相同，然后基于二项式分布的离散事件模型，分别统计在时间段t和时间段t之前k个历史时间窗口内包含候选热词w的微博数，采用χ²统计公式，计算候选热词w在时间段t内的突发值，计算公式为：

$B_{w,t}=\frac{(A+B+C+D){(AD-BC)}^2}{(A+B)(C+D)(A+C)(B+D)}$

其中，A表示在时间段t内，包含候选热词w的微博数；B表示在k个历史时间窗口内，包含候选热词w的平均微博数；C表示在时间段t内，不包含候选词w的微博数；D表示在k个历史时间窗口内，不包含词候选热词w的平均微博数；

步骤B3：结合各个候选热词的营养值和突发值，计算每个候选热词的生命力值；归一化的候选热词w的生命力值life_w,t的计算方法为：

${\mathrm{life}}_{w,t}=\frac{B_{w,t}*{\mathrm{Nutr}}_{w,t}}{\underset{w^{\′}\∈terms}{max}(B_{w^{\′},t}*{\mathrm{Nutr}}_{w^{\′},t})}$

其中，terms表示候选热词集合，w’表示候选热词集合terms中的元素；

步骤B4：根据候选热词的生命力值，对候选热词集合中的候选热词进行排序，筛选出排序靠前的L个候选热词作为热词，并以此构成热词集合；

该方法对应的微博热词与热点话题挖掘系统包括：

预处理模块，用于对社交网络中发布的内容数据进行预处理，获取候选热词，并以此构建候选热词集合；

热词筛选模块，用于根据所述候选热词集合中各个候选热词在当前时刻和给定历史时间窗口内的出现频率和突发性，计算每个候选热词的生命力，筛选出热词，并以此构建热词集合；

热词共现网络构造模块，用于计算热词集合中各个热词的相关性，并以此构造热词共现网络；

热词聚类模块，用于根据所述热词共现网络，使用基于多标签传播的热词聚类算法对热词集合进行划分，获得热点话题集。

2.根据权利要求1所述的一种微博热词与热点话题挖掘方法，其特征在于，所述步骤C中，热词z和热词k在给定时间段t内的相关性c_z，k定义为：

$c_{z,k}=log\frac{r_{z,k}/(R_k-r_{z,k})}{(n_z-r_{z,k})/(N-n_z-R_k+r_{z,k})}\×|\frac{r_{z,k}}{R_k}-\frac{n_z-r_{z,k}}{N-R_k}|$

其中，r_z,k表示同时包含热词z和热词k的微博数，n_z表示包含热词z的微博数，R_k表示包含热词k的微博数，N表示时间段t内所有的微博数，即N＝tw^t；

热词共现网络定义为G(V,E,W)，其中V＝{v₁,v₂,...,v_m}为节点集合，表示所述步骤B中得到的热词集合，m表示节点个数；E表示节点之间边的集合，对于任意两个节点v_i,v_j∈{v₁,v₂,...,v_m}，如果这两个节点代表的词存在共现关系，则构建这两个顶点之间的边e_i,j∈E；W表示边的集合E到实数集合R的映射，若v_i，v_j之间有边e_i,j∈E，则边权值为第i个热词和第j个热词之间的相似度sim(i,j)，定义为：

$sim(i,j)=c_{i,j}/\sqrt{\underset{i,j\∈V,i\≠j}{\Σ}{c^2}_{i,j}}.$

3.根据权利要求2所述的一种微博热词与热点话题挖掘方法，其特征在于，所述步骤D中，热词集合中的每个热词，即每个节点都有一个标签隶属度集合，在每次迭代中更新节点的标签隶属度集合，直到算法收敛，具体包括以下步骤：

步骤D1：根据所述热词共现网络，进行节点的标签初始化；

步骤D2：随机获取未更新标签的节点v，遍历节点v的邻居节点，根据邻居节点的标签集合，更新节点v的标签集合中每个标签的隶属度，对节点v进行标签隶属度归一化；

步骤D3：反复迭代，直到满足迭代终止条件；

步骤D4：根据迭代获得的节点的标签隶属度集合，对节点进行归类，获得热点话题集。

4.根据权利要求3所述的一种微博热词与热点话题挖掘方法，其特征在于，所述步骤D1中，标签初始化的方法为：为每个节点分配一个唯一的标签号，并分别以隶属度1.0隶属于这个标签号，这些唯一的标签号集合记为uniqueLabels。

5.根据权利要求4所述的一种微博热词与热点话题挖掘方法，其特征在于，所述步骤D2中，标签隶属度的更新规则为：随机获取未更新标签的节点v，获取该节点的邻居节点集合Nb(v)，进而得到邻居节点拥有的标签集合labels，则在第h次迭代，节点v属于标签号lb_i∈labels的隶属度为：

$b_h({\mathrm{lb}}_i,v)=\frac{\underset{u\∈Nb\left(v\right)}{\Σ}sim(u,v)*b_{h-1}({\mathrm{lb}}_i,u)}{\underset{u\∈Nb\left(v\right)}{\Σ}sim(u,v)}$

其中，sim(u,v)表示节点u和节点v之间的相似度，分母用于标签隶属度的归一化，保证节点v的标签隶属度之和为1。

6.根据权利要求5所述的一种微博热词与热点话题挖掘方法，其特征在于，所述步骤D3中，迭代终止条件为：

其中r_h定义为：

当m_h＝＝m_h-1，迭代结束。