一种面向网络文本大数据的话题检测或跟踪方法

摘要

本发明公开了一种面向网络文本大数据的话题检测或跟踪方法，其基本思路如下：通过检测不同文档中共同出现的关键词，构造关键词的图模型及对应的邻接矩阵，并将其与谱聚类相结合，提出了一种新的话题检测模型，计算得到每篇文档关于话题的概率分布，当新文档到达时计算其与历史话题所表示属性集的相似度，实现话题的自动检测或跟踪，并通过MapReduce编程模型来实现分布式的方法。本发明的特点在于，用关键词的共现关系对话题进行显示挖掘，而非隐式，面向大数据采用分布式计算，将互联网中的数据信息进行聚类，可拓展性更强，可处理的数据量更大，极大地提高了吞吐率。

说明书

技术领域

本发明属于大数据分析和机器学习交叉的技术领域，更具体地，涉及一 种面向文本大数据的话题检测或跟踪方法。

背景技术

随着互联网信息的大幅膨胀，信息量呈指数增长，浩瀚的网络数据远远 超出了人类的掌控能力，用户难以从众多信息中快捷地提取自己所需要的 信息。话题检测或跟踪(Topic Detection and Tracking，TDT)是一项针 对新闻媒体信息流进行新话题的自动检测和已知话题的后续跟踪的信息处 理技术。由于话题检测和跟踪与信息检索和数据挖掘等自然语言处理技术 存在着很多的共性，而且它直接面向具备突发性特征的新闻语料，因此逐渐 成为大数据分析的研究热点。这项技术以自然语言处理为依托，涉及机器学 习、人工智能等多种学科的相关技术。它的发展与应用息息相关，在信息安 全、私人订制、金融证券分析等领域都有一定的需求。例如，TDT可以发展 成为一种对用户进行有针对性的信息传送的崭新信息服务模式。

目前的研究仍然以传统基于统计策略的文本分类、信息过滤和聚类等 技术为主，忽视了新闻语料本身具备的特点，比如话题的突发性与跳跃性、 相关报道的延续与继承性、新闻内容的层次性以及时序性等。针对这一问题， 当前的研究趋势是将多种方法进行融合，并嵌入新闻语料特性实现话题的 识别与追踪，，比如结合命名实体的话题模型描述、以时间为参数的权重与 阈值估计等等。虽然这些方法能够在一定程度上提高TDT系统性能，但只 是对传统统计策略的一种补充与修正，并没有形成独立于话题检测或跟踪 领域特有的研究框架与模型。

发明内容

本发明的目的在于提供一种面向文本大数据的话题检测或跟踪方法， 其可有效解决对新话题进行检测和对已出现话题的识别和跟踪问题，通过 引入一种谱聚类和检测共同出现的关键字相结合的方法，提出了一种新的 话题检测模型，并通过MapReduce编程模型来实现分布式的方法，使吞吐 率得以显著提高。

本发明提供了一种面向文本大数据的话题检测或跟踪方法，包括如下 步骤：

(1)对中文分词后的文档集构造图模型，每个关键词都视为图的一个 结点，用关键词的共现关系构造结点间的边，得到图及其邻接矩阵；

(2)构造拉普拉斯矩阵，采用分布式的方法进行特征分解并计算其前 k个特征向量；

(3)对拉普拉斯矩阵的前k个特征向量构成的矩阵使用K-means算法 进行聚类，聚类的结果中每一行所属的类别就是原来图中的节点亦即最初 的n个数据点分别所属的类别；

(4)构造话题的属性向量，根据话题的属性向量及上述聚类结果计算 每篇文档关于话题的概率分布；

(5)利用步骤(1)-(4)的方法进行话题检测与追踪的相关应用。

在本发明的一个实施例中，所述步骤(1)具体包括如下子步骤：

(1.1)对文档集进行中文分词后，每个名词短语或命名实体作为一个 关键词，将每个关键词视为图的一个结点；

(1.2)构造结点间的边，将共同在同一文档出现的关键词连接起来， 边的权重用于表示在文档中所有关键词序列共同出现次数的规范化值，所 述规范化是令所有的权重和为1，即边的权重表示该关键词序列共同出现次 数/所有关键词序列共同出现次数；所述关键词序列是指共同在一篇文档中 出现的两个关键词；

(1.3)将上述图模型用邻接矩阵的形式表示为N阶方阵，记为W∈R^n×n， 其中n为关键词的总数。

在本发明的一个实施例中，所述步骤(2)具体包括如下子步骤：

(2.1)把邻接矩阵W的每一列元素加起来得到n个数，将它们放在对 角线上，令其余元素都为零，组成一个n×n的矩阵，记为D∈R^n×n；并令 L＝D-W，L即为拉普拉斯矩阵；

(2.2)采用MapReduce模型进行分布式特征分解，将矩阵L横向分割 为p个数据片段，每一台计算机存储矩阵的n/p行，设定p台计算机存储的 n/p×n矩阵分别为L₁，L₂，…，L_p，其中p为集群中的计算机的个数；

(2.3)在各个计算机上分别对其存储的L_i进行奇异值分解，其中i＝1， 2，…，p，对矩阵L_i进行奇异值分解后计算其前k个特征向量，即前k个 特征值对应的特征向量其中k值是预先设定的话题簇的数 量；

(2.4)计算出矩阵L_i的前k个特征向量后，构造矩阵V_i∈R^n/p×k， V_i的每一列元素是特征分解后的特征向量再将p台计算机上的矩 阵V_i按i＝1，2，…，p的次序整合成矩阵V∈R^n×k，则V的每一列元素是 特征向量再将矩阵V进行规范化得到矩阵U∈R^n×k。

在本发明的一个实施例中，所述步骤(3)具体包括如下子步骤：

(3.1)将矩阵U的每一行视为k维空间中的一个向量μ_j，j＝1，2，…， n，在k维空间中向量μ_j可以看作是一个数据点；

(3.2)使用K-means算法对矩阵U听向量进行聚类，K-means算法是 一个迭代的过程。

在本发明的一个实施例中，所述步骤(3.2)具体包括如下子步骤：

(3.2.1)选定k个中心点的初值，初值为随机选定或者根据经验 值；

(3.2.2)将每个数据点μ_j归类到它最近的那个中心点所代表的簇中；

(3.2.3)用公式计算出每个簇的新的中心点；

(3.2.4)计算平方误差函数最大迭代步数为 M，若迭代次数没有达到M，且计算出的J值与上次计算的J值之差不小于 阈值ζ，转向(3.2.2)；

(3.2.5)若迭代次数达到最大步数M或者相邻两次J值相差小于阈值 ζ，迭代结束；聚类的结果中每一行所属的类别就是原来图中的节点亦即最 初的n个数据点分别所属的类别。

在本发明的一个实施例中，所述步骤(4)具体包括如下子步骤：

(4.1)聚类的结果将图分为了相互之间无联系的簇，而簇内部的各结 点紧密相连，把每一个簇视为一个话题T，簇内结点表示的每一个关键词视 为话题属性，它表征话题的内容；将这些属性排列在一起组成了话题t∈T 的一个属性向量f_t；

(4.2)文档d属于话题t的概率函数由d和属性向量f_t的余弦相似度决 定，公式为

$p\left(t\right|d)=\frac{\cos \mathrm{ine}(d,f_t)}{{\Sigma }_{t^{\prime }\in T}\cos \mathrm{ine}(d,f_{t^{\prime }})}$

每篇文档代表了一些话题所构成的一个概率分布，将每篇文档属于所 有话题的概率进行排序，文档内容最贴近于序列位排第一的话题；

(4.3)对于所有的话题t_i和t_j，定义重叠部分为t_i和t_j中共同出现的关 键词，重叠比率为重叠部分占t_i和t_j所有关键词总数的比率，若t_i和t_j的重 叠比率比阈值ω要大，则将t_i和t_j合并成一个新的话题t，且定义重新计算概率函数，进入步骤(4.2)；阈值ω根据经验值设置。

在本发明的一个实施例中，所述步骤(5)具体为：

话题检测：网络爬虫从互联网上爬取出一篇新的文档后，利用上述步骤 将文档表示成一系列属性的集合，计算它与所有的历史文档的属性集的相 似度，选择具有最大相似度的话题簇，归类其中；若低于相似度门槛η₁， 则定义为新话题。

在本发明的一个实施例中，所述步骤(5)具体为：

话题追踪：在历史训练文档中，事先指定一个话题，在新文档到达时计 算其与指定话题的相似度，判断当前文档是否属于该话题，若相似度大于阈 值η₂，则判断当前文档属于指定话题，实现了对已知话题的追踪；若相似 度小于η₂，则不属于该话题。

在本发明的一个实施例中，所述步骤(1)还包括：

(1.4)采用K最近邻分类算法稀疏化矩阵，或者预先设定一个阈值ε， 将矩阵W中小于阈值ε的元素都设置为0，从而稀疏化矩阵；并且当位置 (i，j)或(j，i)上任一元素不为0，则将对应的两个元素都改为S_ij，其中 S_ij(i∈[0，n-1]，j∈[0，n-1])为矩阵W中的元素。

与现有技术相比，本发明具有以下的优点和技术效果：

(1)、用谱聚类和识别文档中共同出现的关键字相组合的方式，提出了 一种新的话题检测方法，结合图模型，用关键词的共现关系对话题进行显示 挖掘；

(2)、通过MapReduce编程模型实现了分布式谱聚类的应用，分布式 存储拉普拉斯矩阵，并对存储节点各自存储的矩阵进行奇异值分解，直接面 向文本大数据，极大地提高了吞吐率；

(3)、用本发明中的方法将文档表示成一系列属性的集合，通过计算它 与历史文档集的相似度，构建文档关于话题的概率分布，有效地自动检测新 话题或实现了对已知话题进行追踪；

(4)、可拓展性强，随着时间的推移文档规模越来越大，数据量也越来 越大，数据的分布式存储节点也可以根据具体情况而自行增加；

(5)、本发明满足了话题检测或跟踪和面向文本大数据的要求，具有极 高的应用价值。

附图说明

图1是本发明面向文本大数据的话题检测或跟踪方法的总体流程图；

图2是本发明面向文本大数据的话题检测或跟踪方法的具体流程图；

图3是本发明实施例中一种分布式存储原理示意图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及 实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施 例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的本发明 各个实施方式中所涉及到的技术。特征只要彼此之间未构成冲突就可以相 互组合。

以下首先对本发明的技术术语进行解释和说明：

拉普拉斯矩阵：度矩阵和邻接矩阵的差，度矩阵是一个对角矩阵，它包 含了每个顶点的度；拉普拉斯矩阵是一个半正定矩阵，特征值中0出现的 次数就是图连通区域的个数，最小的特征值永远是0。

K最近邻(K-Nearest-Neighbor，KNN)分类算法：如果一个样本在特 征空间中的K个最相似(即特征空间中最邻近)的样本中的大多数属于某一 个类别，则该样本也属于这个类别。

MapReduce编程模型：MapReduce是Google提出的一个软件架构，用 于大规模数据集的并行计算。指定一个Map函数，用来把一组键值对映射 成一组新的键值对，指定并发的Reduce函数，用来保证所有映射的键值对 中的每一个共享相同的键组。

奇异值分解(Singular Value Decomposition，SVD)：适用于任意的矩阵， 最大的作用是数据的降维，能够用小得多的数据集来表示原始数据集，这实 际上是去除了噪声和冗余信息。

本发明的主要步骤为处理数据词典、分布式谱聚类、构建文档-话题概 率模型和话题检测或跟踪，即对中文分词后的文档，构建数据词典，并构建 关键词的邻接矩阵，使用K-means算法进行聚类，每一个类就对应于一个 话题，再分别计算文档属于每个话题的概率；再对新出现话题进行检测，对 已出现话题实施追踪。

如图1所示，本发明面向文本大数据的话题检测或跟踪方法包括以下 步骤：

(1)对中文分词后的文档集构造图模型，每个关键词(keyword)都视 为图的一个结点，用关键词的共现关系构造结点间的边，得到图及其邻接矩 阵；

具体地，如图2所示，本步骤包括如下子步骤：

(1.1)对大规模文档集(document collection)进行中文分词后，每个 名词短语或命名实体都作为一个关键词(keyword)，将每个关键词视为图 (graph)的一个结点(node)，设关键词的总数为n，这里没有考虑词与词 之间的顺序；

(1.2)构造结点间的边，将共同在同一文档出现的关键词连接起来， 边的权重用于表示在所有文档中关键词序列共同出现次数的规范化值，规 范化是令所有的权重和为1，即某关键词序列共同出现次数/所有关键词序 列共同出现次数；这里将共同在一篇文档中出现的两个关键词称作关键词 序列；

(1.3)将上述步骤生成的图模型用邻接矩阵的形式表示为N阶邻接矩 阵，记为W∈R^n×n，矩阵W中的元素记为S_ij(i∈[0，n-1]，j∈[0，n-1])；

(1.4)关键词的总数n是一个相当大的值，因此存储矩阵W会占用很 大的存储空间。为了避免存储稠密矩阵，通常会采用K最近邻(K-Nearest- Neighbor，KNN)分类算法稀疏化矩阵，或者预先设定一个阈值ε，将矩阵 W中小于阈值ε的元素都设置为0，从而达到稀疏矩阵的目的，对于阈值ε 的选择可以根据存储设备和精度要求进行修改。这种方法可能会导致最后 的矩阵不对称，为了使稀疏矩阵存储的是对称形式，只要位置(i，j)或(j， i)上任一元素不为0，则将对应的两个元素都改为S_ij；这一步骤可以省略。

(2)构造拉普拉斯矩阵，采用分布式的方法进行特征分解并计算其前 k个特征向量；

具体地，如图2所示，本步骤包括如下子步骤：

(2.1)把邻接矩阵W的每一列元素加起来得到n个数，将它们放在对 角线上，令其余元素都为零，组成一个n×n的矩阵，记为D∈R^n×n；并令 L＝D-W，L即为拉普拉斯矩阵；

(2.2)当面向文本大数据时，拉普拉斯矩阵L会十分庞大，我们将采 用分布式的方法实现特征分解，具体使用MapReduce模型，假设集群共p 个计算机，将矩阵L横向分割为p个数据片段，每一台计算机存储矩阵的 n/p行，设定p台计算机存储的n/p×n矩阵分别为L₁，L₂，…，L_p，如图3 所示。但计算机间的通信代价比较大，通常通过广播的方式进行消息传递。

(2.3)在各个计算机上分别对其存储的L_i(i＝1，2，…，p)进行奇异 值分解(Singular Value Decomposition，SVD)，因为特征分解只适用于方阵， 而SVD适用于任意的矩阵。对矩阵L_i(i＝1，2，…，p)进行奇异值分解后 计算其前k个特征向量，即前k个特征值对应的特征向量这里的k值是预先设定的话题簇的数量，“前k个”指将特征值按从小到大 的顺序排列后的第1，2，…，k个；

(2.4)计算出矩阵L_i(i＝1，2，…，p)的前k个特征向量后， 构造矩阵V_i∈R^n/p×k，V_i的每一列元素是特征分解后的特征向量再将p台计算机上的矩阵V_i按i＝1，2，…，p的次序整合成矩阵V∈R^n×k， 则V的每一列元素是特征向量再将矩阵V进行规范化得到矩阵U∈ R^n×k；这里将n阶矩阵进行了非线性降维，简化了后续的计算复杂度。

(3)对拉普拉斯矩阵的前k个特征向量构成的矩阵使用K-means算法 进行聚类，聚类的结果中每一行所属的类别就是原来图中的节点亦即最初 的n个数据点分别所属的类别；

具体地，如图2所示，本步骤包括如下子步骤：

(3.1)将矩阵U的每一行视为k维空间中的一个向量μ_j，j＝1，2，…， n，在k维空间中向量μ_j可以看作是一个数据点；

(3.2)使用K-means算法进行聚类，K-means算法是一个迭代的过程。

进一步地，所述步骤(3.2)具体包括：

(3.2.1)选定k个中心点的初值，可以随机选定，也可以根据经 验值人为设定；

(3.2.2)根据距离公式将每个数据点μ_j归类到它最近的那个中心点所 代表的簇中；

(3.2.3)用公式计算出每个簇的新的中心点；

(3.2.4)计算平方误差函数最大迭代步数为 M，若迭代次数没有达到M，且计算出的J值与上次计算的J值之差不小于 阈值ζ(ζ一般设置为0.001)，转向(3.2.2)；

(3.2.5)迭代次数达到最大步数M或者相邻两次J值相差小于阈值ζ， 迭代结束；聚类的结果中每一行所属的类别就是原来图中的节点亦即最初 的n个数据点分别所属的类别。

(4)构造话题的属性向量，根据话题的属性向量及上述聚类结果计算 每篇文档关于话题的概率分布；

具体地，如图2所示，本步骤包括如下子步骤：

(4.1)直观上，聚类的结果将图(graph)分为了相互之间无联系的簇， 而簇内部的各结点紧密相连，把每一个簇视为一个话题(topic)T，簇内结 点表示的每一个关键词视为话题属性，它表征话题的内容；将这些属性排列 在一起组成了话题t∈T的一个属性向量f_t；

(4.2)文档d属于话题t的概率函数由d和属性向量f_t的余弦相似度决 定，公式为

$p\left(t\right|d)=\frac{\cos \mathrm{ine}(d,f_t)}{{\Sigma }_{t^{\prime }\in T}\cos \mathrm{ine}(d,f_{t^{\prime }})}$

于是每篇文档代表了一些话题所构成的一个概率分布，而不是绝对地 只代表一个主题。将每篇文档属于所有话题的概率进行排序，显然文档内容 最贴近于序列位排第一的话题。

(4.3)对于所有的话题t_i和t_j，定义重叠部分为t_i和t_j中共同出现的关 键词，重叠比率为重叠部分占t_i和t_j所有关键词总数的比率。若t_i和t_j的重 叠比率比阈值ω要大，则将t_i和t_j合并成一个新的话题t，且定义重新计算概率函数，进入步骤(4.2)；阈值ω根据经验值设置。

(5)利用步骤(1)-(4)的方法进行话题检测与追踪的相关应用。

具体地，相关应用可以包括：

话题检测：网络爬虫从互联网上爬取出一篇新的文档后，利用上述步骤 将文档表示成一系列属性的集合，计算它与所有的历史文档的属性集的相 似度，选择具有最大相似度的话题簇，归类其中；若低于相似度门槛η₁， 则定义为新话题；或者

话题追踪：在历史训练文档中，事先指定一个话题，在新文档到达时计 算其与指定话题的相似度，判断当前文档是否属于该话题，若相似度大于阈 值η₂，则判断当前文档属于指定话题，实现了对已知话题的追踪；若相似 度小于η₂，则不属于该话题。

本发明是一个显式数据挖掘并对大规模文本集进行聚类的过程，创新 点具体体现在：

(1)聚类方法对强连通子集的挖掘，采用图模型的方式将文本集形象 化，使得聚类效果显示更加具体；

(2)面向大数据采用分布式计算，由于数据量较为庞大，单个计算机 无法容纳并处理，所以采用计算机集群进行分布式存储计算，有效提高了吞 吐率；

(3)用关键词的共现关系对话题进行显示挖掘，而非隐式。在显式的 数据挖掘中，尝试预测一个特定的数据点，比如以给定的一个房子的售价来 预测邻近地区内其他房子的售价；而在隐式的数据挖掘中，一般会尝试创建 数据组或找到现有数据内的模式。

通过本发明所述的方法，可将互联网中的数据信息尤其是新闻媒体信 息流进行聚类，自动在线检测并提取出用户感兴趣的话题，并能将特定时间 段内最活跃的话题智能推送给用户，后续还能根据用户的需求对话题的动 态演化过程进行准确跟踪。系统采用分布式存储的方法，可拓展性更强，可 处理的数据量更大，极大地提高了吞吐率。

本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已， 并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同 替换和改进等，均应包含在本发明的保护范围之内。