一种时序海量网络新闻的热点事件快速检测方法

摘要

一种时序海量网络新闻的热点事件快速检测方法，包括：将网络新闻文本序列按时间间隔分为区块序列；对第一个区块的新闻文本按狄利克雷过程进行聚类，形成聚类簇集合；把前一区块聚类后的结果进行衰减、过滤，作为后续区块的先验分布，然后对后续区块按按狄利克雷过程进行聚类；对每个聚类簇按照报道量进行事件的热度排序；将排序值最高的T个聚类簇作为热点事件，选取每个聚类簇中tf-idf值最高的M个特征作为热点的关键词，对热点进行展示。本发明可以大大提高网络新闻聚类的效率；同时内存的占用不随数据量的增加而线性增加，适用于大规模文本数据分析。

说明书

技术领域

本发明提供了一种在线新闻的热点事件发现方法，具体涉及到从网上时序报道的海量新 闻文本中快速发现热点事件，并按热度对事件排序，属于自然语言处理和数据挖掘领域。

背景技术

随着网络技术的蓬勃发展与随之而来的信息爆炸，人们一方面可以随时获取到最新、最 全的新闻大事，另一方面，读者获得关键信息的时间成本也随之增加。如何从海量的在线网 络新闻中自动获得有用信息成为一项迫切的任务。网络在线新闻的热点事件检测可以满足人 们从时序海量的网络新闻中获取重要信息、提高阅读效率，同时也能帮助政府相关部门进行 网络舆情监控和突发事件监测。

目前，很多方法在进行网络新闻热点检测和新闻推荐时，使用了主题模型(Topic Model) 和仿射传播(Affinity Propagation)算法。但这两类方法存在的问题是需要事先给定新闻中热点 数目k，而且只能处理静态数据。实际情况是，每天发生的新闻大事数量并不确定，同时， 新闻报道是动态、实时的。

除上述问题外，事件本身还会经历发生、发展和衰减的过程，在热点事件发现中，也应 该考虑这些自然的规律。

发明内容

本发明中所指的网络新闻热点事件指的是：在一组时序的网络新闻文本流中存在的、在 某一特定的时间段内被连续而广泛报道、并受到高度关注的事件。在不作特别说明的情况下， 本发明所述的时间单位都假定按“天”为单位，时间跨度也以“1天”为间隔。但本发明的 方法适用于任意时间单位。

本发明的目的是提供一种新的方法，通过快速处理海量的网络新闻文本数据，检测其中 的热点事件，并按热度对事件排序。面对时序海量的新闻文本，既要求算法时间效率高，又 不能随着新闻数据的增加而线性增加空间复杂性，同时，还能对热点事件的发生、发展、衰 减过程建模。

本发明的原理是：使用一个带时间因子的狄利克雷过程用于网络新闻聚类，它一方面能 很好地表示新闻热点的动态演化过程，另一方面将一般的狄利克雷过程变成了增量模型，内 存的占用不会随数据量增加而线性增加，适用于大规模网络文本数据的处理。此外，为了进 一步提高时间效率，本发明提出了一种基于贪心搜索的快速推断算法取代吉布斯采样，大大 加快了算法速度。之后，对挖掘出的热点事件（即新闻文本聚类簇）进行排序，提取出最热 门的事件。

下面先对几个术语进行解释：

-聚类簇：通过聚类方法形成的每个类称为一个聚类簇。本发明中，每个聚类簇代表 一个可能的事件。

-聚类簇大小：聚类簇中的元素个数；对于文本聚类而言，聚类簇的大小是指其中的 文本个数。

-狄利克雷过程(Dirichlet Process)：也称为中餐馆过程(Chinese Restaurant Procss)，在 [WIKI]上有详细解释（http://en.wikipedia.org/wiki/Dirichlet_process）。

-tf-idf值：信息检索中的常用概念，是度量一个词（或短语）表征文本内容的一种方 法。假定某个词（或短语）term在一个文本Text中出现的频次为tf，该词（或 短语）在文本集合中的df个文本中出现，若文本集合中的文本总数为Num， 该term在文本Text中的tf-idf值按如下公式计算（对数log取10为底数）：

$\mathrm{tf}-\mathrm{idf}=\mathrm{tf}*\log \frac{\mathrm{Num}}{\mathrm{df}}$

本发明对应的操作示意图如图1所示，在图中的[f₁f₂，...]表示特征集合，特征是由词表示 的，实际上是文本集中词的集合。每个聚类簇代表一个事件，聚类簇集合构成热点事件库。

本发明提供的技术方案如下：

一种时序海量网络新闻的热点事件快速检测方法（流程参见图2），包括：

A.使用带时间因子的狄利克雷过程对网络新闻文本在线聚类，包括如下三步：

A1.将网络新闻文本序列按时间间隔分为区块序列，每个区块包含时间间隔内的多 个新闻文本（如，以“1天”为间隔，每个区块包含1天的新闻文本）。

A2.对第一个区块（如，第一天）的新闻文本按狄利克雷过程进行聚类，形成聚类 簇集合。

A3.对于后续的每一区块，利用前一区块聚类后的结果也按按狄利克雷过程进行聚 类，但在聚类之前，需要对前一区块的聚类结果先做作衰减处理，再做过滤处理。衰减 处理的基本思想是在前一区块处理完之后，对形成的每个聚类簇以a为衰减因子实施衰 减，假定某个聚类簇的大小为r（即，包含r个文本），则，通过修改衰减后，其大小变 为r’=a*r，其中a∈(0,1)。聚类簇内部的特征分布保持不变。过滤处理的基本思想是： 删除大小小于一定阈值t(如设置t=30，也可以设为其它值)的聚类簇，同时，删除持续报 道时间超过一定时间长度（如150天，也可设置为其它值）的聚类簇。

B.对热点事件进行排序和展示，具体分为如下二步：

B1.对每个聚类簇，计算此聚类簇在报道期间内平均时间段的报道量，然后按照报 道量进行事件的热度排序；

B2.将排序值最高的T个聚类簇作为T个热点事件（T为用户自定义值），选取每个 聚类簇中tf-idf值最高的M（M可以自行设定，如M=20）个特征（即代表词）作为热点 的关键词，对热点进行展示。

利用本发明提供的技术方案，可以大大提高网络新闻聚类的效率；同时内存的占用不随 数据量的增加而线性增加，适用于大规模文本数据分析；此外，改进过的狄利克雷过程混合 模型，通过加入时间因子，能模拟新闻热点产生、发展、衰减过程，符合实际情况；对新闻 热点的过滤一方面提高了系统效率，另一方面去除了噪音，提高了系统的准确性。

附图说明

图1本发明所述方法操作示意图。

图2本发明所述方法流程图。

具体实施方式

下面通过实例对本发明做进一步的说明。

假定有连续三天的网络新闻报道，其中第一天有100篇关于地震、60篇关于高考、30篇 关于国防、10篇关于外交、5篇关于经济；第二天有70篇关于医疗保健、50篇关于地震、 20篇关于国防、30篇主题不明确；第三天有80篇关于医疗保健、50篇关于旅游、10篇主题 不明确。我们并不知道总新闻热点事件数是多少，也不知道每篇文章具体属于哪类事件。

首先，引入几个符号说明：

(1)m为区块的大小，即，文本数，按时间序列表示为：x_1:m＝(x₁,x₂,...,x_m)，其中，x_i表 示第i个文本，i＝1…m。

(2)区块中的m个文本对应的聚类簇，以序列表示为：

assign_1:m＝(assign₁,assign₂,...,assign_m),其中assign_j∈C，C表示聚类簇集，即C={c₁,c₂,…, c_k}，聚类簇的个数为K=|C|；

(3)N_j表示属于聚类簇c_j的文本个数；

(4)L表示文本集合中总共包含的不同词数（每个词都有序号）；

(5)表示属于聚类簇c_j的文本集合中序号为l的词总共出现的次数；

(6)是对应于的超参数，超参数给定为一个初始的常量值（如，将每个都设置为1）， 且α也是超参数(其值也可以设为1)。

(7)Γ(a)在数学上称为伽马函数。其一般形式为：当变量a为正整数

时，其值为阶乘，即：Γ(a+1)＝aΓ(a)＝a!。（详细说明见高等教育出版社《数学手册》 第1版p587-589）

A部分的实现如下：

A1.将网络新闻文本序列按时间间隔分为区块序列，每个区块内包含多个新闻文本（下 面以“天”为时间单位，以“1天”为区块的时间间隔，因此每个区块包含1天的新闻文本， 时间单位也可以设置为其它值，如“3天”、“1周”、“1月”等）。

A2.对第一个区块（即，第一天）的每个文本，按时间顺序通过如下算法进行聚类：

输入：有序的m个文本，表示为x_1：m

输出：每个文本对应的聚类簇，即：序列assign_1∶m

第1步：初始化聚类簇集合为空，即，C={}，聚类簇个数为0，K=0

第2步：设定一个初始值p_max＝0；

第3步：对于区块中每一个文本（假设当前为第i个文本x_i），重复执行第3.1步~第3.3 步

第3.1步：新增一个聚类簇c_new，即：C'＝C∪{c_new}；

第3.2步：对于每一个聚类簇c_j∈C'，重复执行第3.2.1步~第3.2.1步：

第3.2.1步：当文本属于c_j时，计算当前区块整体的概率p如下：

①计算当前文本x_i之前各文本x_r(1≤r≤i)属于相应聚类簇的概率值：

$p\left(x_r\right)=(\frac{N_{{\mathrm{assign}}_r}}{{\Sigma }_{k=1}^K{N}_k+\alpha }\times \frac{\underset{l=1}{\overset{L}{\Pi }}\Gamma (n_{{\mathrm{assign}}_r}^l+{\beta }_{{\mathrm{assign}}_r}^l)}{\Gamma (\underset{l=1}{\overset{L}{\Sigma }}{n}_{{\mathrm{assign}}_r}^l+{\beta }_0)})$

②假定文本x_i之后的各文本x_r(i＜r≤m)属于单独的新聚类簇，其概率值为：

$p\left(x_r\right)=\frac{\alpha }{{\Sigma }_{k=1}^{K+1}{N}_k+\alpha }\times \frac{\underset{l=1}{\overset{L}{\Pi }}\Gamma (n_r^l+{\beta }_r^l)}{\Gamma (\underset{l=1}{\overset{L}{\Sigma }}{n}_r^l+{\beta }_0)}$

③上面所计算各个文本x_i所属聚类簇的概率值之集表示为：

$p={\Pi }_{r=1}^{m}p\left(x_r\right)$

第3.2.2步：若概率p大于最大概率值p_max，即：p>p_max时:

第3.2.2.1步：第i个文本x_i的聚类簇指定为c_j：assign_i=c_j；

第3.2.2.2步：更新最大概率值，使p_max=p；

第3.3步：若第i个文本x_i所属的聚类簇不属于集合C，即：assign_i=c_K+1:

第3.3.1步：将新的聚类簇c_K+1加入到聚类簇集合C:C=C∪{c_K+1};

第3.3.2步：聚类簇数增1，即：K=K+1；

第4步：返回每个文本对应的聚类簇，即assign_1:m

通过上述过程聚类出了5个聚类簇，分别代表地震、高考、国防、外交和经济，包含 文本数分别为100篇，60篇，30篇，10篇和5篇。

A3.在进入第二天的聚类时，先将第一天的聚类结果进行衰减。假设衰减因子a为 0.5，衰减过后，每个聚类簇的大小分别变为50，30，15，5和2.5。接着进行过滤。假设 过滤阈值t=30，则过滤之后只有前两个聚类簇，即地震（聚类簇c₁）和高考（聚类簇c₂） 继续存在，作为第二天（即，第二个区块）聚类的热点先验分布。对第二区块进行上述 类似聚类，与上述唯一不同的是第1步的初始化改为：

第1’步：初始化聚类簇集合C=｛c₁，c₂｝，聚类簇个数为2，K=2；

B部分：关于事件的热度排序与展示的实现分别如下：

B1.事件的热度排序：

第1步：计算每个聚类簇c_j中的文本个数，计为N_j；

第2步：计算每个聚类簇c_j中文本的时间跨度D_j(按单位时间计，如“天”，最晚报 道时间与最早时间间隔，如连续报道的天数)

第3步：计算聚类簇c_j在时间单位内的平均报道量：Score_j＝N_j/D_j；

第4步：按Score_j值由大到小对聚类簇集排序，取前T（如T=10）个作为最热的T 个事件。

B2.对热点事件进行排序和展示：

第1步：将每个聚类簇看成一个“大文本”，于是，所有的聚类簇形成了若干个“大 文本”集合；

第2步：以“大文本”集为背景，计算最热T个事件（聚类簇）中每个特征f(文本 中的一个词表示一个特征)的tf-idf值；

第3步：取tf-idf值最高的M（如M=20）个特征作为热点的关键词进行热点展示。