基于知识图谱的中文关键短语提取算法

徐远威 李劲华

(青岛大学数据科学与软件工程学院 山东 青岛 266071)

0 引 言

近年来互联网的快速发展,使得新闻文章、互动信息和学术论文等文本数据不断增加,而关键短语有利于帮助我们快速理解文本并获取文本关键信息[1]。关键短语是对文本的内容进行提炼和概括,相比于关键词具有更丰富的语义信息。例如,“中国”“食品”“产业”和“分析师”四个词各自所表达的含义与“中国食品”“产业分析师”作为一个整体所表达的含义有明显的差异。中文关键短语提取是国内文本挖掘[2]中一项基础而又重要的工作,因此需要一种高效提取高质量中文关键短语的技术。

关于关键短语提取的研究主要有监督学习和无监督学习这两种机器学习方法。其中,监督学习将关键短语提取看作是一项二值分类任务[3],把一些特征例如短语长度、位置和频率等作为分类模型的输入。监督学习需要人工标注短语,对于海量数据而言,是一项耗时费力的工作,所以本文着重研究监督学习[4]的方法。

现有的无监督学习方法一般分为基于统计的方法和基于图排序的方法。基于统计的方法一般使用外部文本语料库来辅助提取关键短语,如TF-IDF、TPR算法。TF-IDF是Salton等[5]提出的一种结合逆文档频率和词频来表现词在文本中的关键程度算法,此算法缺点在于粗粒度地通过频率来统计分析,没有考虑到文本语义关系,而且需要大量的外部文本语料来实现。TPR算法[6]是一种主题PageRank算法,使用Wikipedia文章来训练LDA模型,在给定文档主题分布的情况下统计排名得分来提取关键短语,依赖于外部语料库。现有研究者提出多种基于改进TF-IDF的算法,牛萍[7]提出一种TF-IDF与规则相结合的方法,运用一种结合连续单字词和多词表达式识别的方法来进行候选词识别,选取TF-IDF为主要特征来进行关键短语提取。公冶小燕等[8]提出基于改进TF-IDF和共现的主题词抽取算法,对文档的语义相似矩阵进行聚类来提高准确率。

基于图排序的方法中,TextRank算法[9]通过词的相邻关系生成词的共现图,使用图的中心性算法获得每个节点的排名得分,降序排序得分选择前K个作为关键词,缺点在于太依赖于共现关系,没有充分考虑到语义关系。之后多位学者对TextRank进行改进,如ExpandRank[10]、CiteTextRank[11]和WeightedTextRank[12]算法等。近年来,Zuo等[13]利用单词嵌入技术提出一种将Word2Vec与TextRank相结合的算法,通过利用文本之间的语义相似性来提高关键短语提取性能。Yan等[14]充分利用词与句子之间的潜在关系,融合了它们之间的语义关系,并用话题模型提出一种基于图排序的关键短语提取算法,较好地挖掘出文本中的语义关系。

综上所述,基于统计的方法将一个词映射到外部文本语料库中具有相同表面形式的词,由于中文词歧义性较强,相同的词在不同语境中表达的含义可能不同,输入文本中词的真正含义可能因大量扩展语料库被淹没。基于图排序的方法需要构建共现图,依赖于两个词之间的共现关系,若两个词未出现在预设定的窗口范围内,即使语义相关也不会将它们连在构建的共现图边上,从而出现信息遗漏、涵盖信息量少等问题。针对以上缺陷,本文提出一种基于知识图谱的中文关键短语提取算法,主要贡献包括以下三点:

(1) 将词向量化后进行AP聚类加强文本中的主题覆盖率。

(2) 运用知识图谱的语义网络结构挖掘词之间的潜在关系,减少外部语料库的噪声引入。

(3) 结合量化潜在关系的边权值和词频改进PageRank。

1 整体框架

图1为本文算法框架,分为以下五个步骤。

图1 APKGRank算法框架

(1) 预处理输入文本获得分词结果,将分词结果映射到由训练语料库得到的词向量中获得每个词的词向量。

(2) 将基于语义的AP聚类算法应用到文本中得到词集群。

(3) 运用知识图谱将集群中的词连接到知识图谱中的实体,通过语义网络结构挖掘文本中词之间的潜在关系,赋予边权值量化潜在关系构建关系词图。

(4) 对将所有集群提取的关系词图组合成一个完整的文本关系词图执行改进PageRank获得每个词的排名得分。

(5) 对输入文本运用短语生成规则生成候选短语,将短语特征与候选短语得分相结合计算得到最终短语得分,根据降序排序选择前K个候选短语作为关键短语。本文将该算法简称为APKGRank。

2 基于语义的AP聚类

一般来说,一个文本中包含多个主题,一个主题可以用文本中所包含的词来表示,而且同一主题中的词是密切相关的[15]。本文通过基于语义的方法对文本中词进行AP聚类,将文本分成若干个词集群,其中每个集群中的词传递一个主题,从而加强文本的主题覆盖率。

2.1 预处理

对于输入文本,首先进行分词操作得到候选词集,并对候选词完成词性标注,去除其中停用词,过滤处理之后得到整个文本的分词结果。

2.2 词向量表示

Word2vec是2013年Google的Mikolov等[16]发布的一种词向量计算工具,分为Skip-gram和CBOW两个模型。一般来说,虽然Skip-gram模型训练速度不如CBOW模型,但是Skip-gram模型对于不常见词的训练效果更加良好。本文选用Skip-gram模型进行词向量训练。

Skip-gram模型是一个三层浅型神经网络,如图2所示。三层分别为输入层、投影层和输出层,输入层为根据One-hot编码得到的输入词向量,投影层用来放置一个学习权重矩阵,在输出层使用结合哈夫曼树的层次Softmax算法和负采样算法来优化计算输入词与输出词之间的概率分布。其主要思想为根据目标词来预测上下文词,最后根据迭代次数来确定每个词的词向量。

图2 Skip-gram模型

为了传递语义,使用中文维基百科语料库作为辅助文本构建Skip-gram模型。对中文维基百科语料库进行词向量训练后,将预处理的分词映射到训练结果中得到每个词的词向量。缺失值用随机初始化相同维度的词向量表示。

2.3 AP聚类

AP聚类算法是由Frey等[17]提出根据数据对象之间进行“信息传递”的一种聚类算法。与普通的K-Means聚类和谱聚类不同,其优势在于当文本长短的不一致时,不用人为设定簇的个数从而减少人为引入主题个数带来的误差,并且具有明确的质心,其性能和效率相比其他聚类算法都有较大的提高。

AP聚类定义一个相似矩阵来更新迭代归属度矩阵(availability)和吸引度矩阵(responsibility)。前者记为A,A(i,k)表示对象i以对象k作为聚类中心的适合程度,后者记为R,R(i,k)表示对象k相对于其他候选示例适合作为对象i的聚类中心程度。以对象i当作聚类中心的参考度表示为p(i)。我们使用词向量之间的欧氏距离来计算对象i和对象j之间的相似度,记为s(i,j),参考度设为所有相似度值的中位数。当聚类中心稳定或完成预设的迭代次数时,吸引度矩阵和归属度矩阵更新迭代结束。R和A更新公式如式(1)、式(2)所示。

(1)

(2)

考虑到聚类过程中出现振荡的情况,引进阻尼系数λ来控制算法收敛。吸引度矩阵和归属度矩阵设定为本次更新值的(1-λ)倍加上前次迭代更新值的λ倍,通常λ设为0.5。具体公式如式(3)和式(4)所示。

rt+1(i,k)=(1-λ)×rt+1(i,k)+λ×rt(i,k)

(3)

at+1(i,k)=(1-λ)×at+1(i,k)+λ×at(i,k)

(4)

当聚类中心稳定或完成预设的迭代次数时,我们把A(i,i)+R(i,i)>0的点当作聚类的中心,将其余点分派给相距最短的聚类中心,以此完成词向量聚类。

3 知识图谱的应用

本节运用知识图谱进一步来辅助提取关键短语。由于针对中文关键短语,选择使用CN-DBpedia知识图谱[18],表示为KG,通过将每个集群中的词连接到知识图谱中的实体并通过语义关系构建文本关系词图,使用改进PageRank获得词排名得分,最后结合短语生成规则、词得分和短语特征提取关键短语。

3.1 词连接

给定一个知识图谱KG,记为G,将词连接到G,使每个词对应到G中的映射实体。考虑到中文词歧义性较强,一个表层形式的词通常有多个映射实体,例如,“司机”可以指职业、电影或者歌曲。现有的多数研究都集中在语义消歧上[19],大多数的方法需要G中的每个实体都有一个描述该实体的页面p,然后计算p与输入文档d之间的语义关系[20],例如,计算它们之间的余弦相似度,选择相似度最大的页面对应的实体作为映射实体。本文方法为歧义词构建了一个映射字典,每个可能的映射都有一个先验概率。为了计算先验概率,使用百度百科来进行辅助,对于百度百科中歧义词的每个链接,可以得到一对描述词的内容文本和实体,通过计算每个候选实体ce与词t的共现数与t的词频的比例来获得每个候选实体的先验概率。计算公式如式(5)所示,其中T(t,cei)表示词与候选实体的共现次数,T(t)表示词频。

(5)

给定一个词t,如果知识图谱中有描述节点信息且没有出现歧义词情况,则直接连接节点。如果出现歧义词情况,我们利用构建字典并通过结合实体内容文本和输入文档之间的余弦相似度和先验概率来寻找它的正确映射,从而减少外部语料库的噪声引入。

3.2 关系词图构建算法

词连接后得到词的映射实体(称为锚节点),构建一个S-ties关系词图来获得每个集群中词之间的语义关系。首先定义一个知识图谱G=(V,E),其中:V表示实体对应节点的集合;E表示实体之间边的集合;任意一条边对应一个三元组Ek=(vi,vj,lable),其中:vi和vj分别表示始节点和终节点;lable表示始节点与终节点的关系标签;An表示锚节点的集合,即An={v1,v2,…,vk}。

算法1为S-ties词图的构建过程。结合知识图谱G,根据锚节点An对应到G中得到子图,EV是An对应子图中的扩展节点集,我们使用广度优先搜索来遍历锚节点vi和其扩展节点EVi之间不超过h的路径。为了添加具有语义关系的路径并挖掘出锚节点vi与其他节点的扩展节点EVj的潜在关系,使用Word2vec计算两节点之间的余弦相似度作为vi与EVj之间的语义相似度,记为μ(vi,EVj)。考虑到若扩展节点对应的是一个由多个词组成的命名实体,根据其包含词向量计算平均值来进行此节点的词向量表示。我们通过设定一个语义相似度阈值τ来添加具有潜在语义关系的边,其中边的权值表现了两个锚节点之间的语义关系程度。

算法1S-ties词图构建算法

输入:G=(V,E),最长路径h,锚点集An,语义相似度阈值τ。

输出:S-ties词图。

vi,vj∈An,EVk∈EV

forviinAndo

forEVjinEVandi≠jdo

computeμ(vi,EVj);

ifμ(vi,EVj)>=τdo

ifvi指向vj之间不存在边do

add Path;

else do

边的权值weight加1;

return 包含Path的图

为了合并每个词集群构建的关系词图,考虑到将输入文本内容的语义关系添加到关系词图中,对文本的词序列进行遍历,如果两个锚节点vi和vj对应的词ti和tj前后出现在设定的同一窗口λ内,若不存在vi到vj的边,则增添一条权值为1的此方向边。若存在vi到vj的边,则边的权值加1,从而得到了一个完整的带权有向文本关系词图。一个关系词图示例如图3所示。

图3 关系词图示例

3.3 图的中心性算法

构建文本关系词图之后,我们使用图的中心性算法估量图中节点的重要性来获取词的排名得分。现有的词图排序方法采用了度中心性、间接中心性、紧密中心性、特征向量中心性和PageRank等多种图的中心性算法[21]。由于关系词图是一个带权有向图,边反映了词之间的语义关系程度,并且已有的方法表明[22],词频是表现词关键性的一个重要特征,因此需要一种通过结合关系词图的语义关系结构和词频来对词进行排序的图算法。考虑到PageRank使用图结构对节点进行排序,但是PageRank的转移概率是标准化的,它不能反映节点特征的差异。相比基于PageRank改进的个性化PageRank算法为每个节点分配了一个有偏差的转移概率。基于综合考虑,结合边权值和词频改进PageRank迭代公式如式(6)所示。

(6)

式中:PR(vj)是vj的rank得分;p(vj)表示vj的随机转移概率;in(j)为朝向vj的全部节点;p(Wij)表示vi到vj的跳转概率;d是阻尼因子,通常设为0.85。随机转移概率p(vj)和跳转概率p(Wij)计算公式如式(7)和式(8)所示。最后对文本的关系词图执行改进PageRank,得到每个锚节点对应词的排名得分。

(7)

(8)

式中:N是节点数;tf(vj)是vj的词频;weight(vi→vj)表示vi指向vj边的权值。

3.4 关键短语提取

考虑到中文关键短语大多为名词性短语,形容词和副词只是起到修饰作用,本文制定候选短语生成的语句规则:

(1) 由连续一个或者多个名词组成。

(2) 由连续一个动词加一个或者多个名词组成。

(3) 由连续一个名词加一个动词组成。

例如,给定一句“达州市公安交警支队对该路段临时实施管制”,结合词性标注使用规则将生成候选短语“达州市公安交警支队”“路段”和“实施管制”。若出现“达州市公安交警支队”由三个以上词组成的候选短语、表达语义粒度过大的情况,我们结合词之间的凝聚度和自由度来优化生成双词候选短语[23-24],凝聚度表示两个词构成短语的内部紧密性,自由度用来估量词与左右相邻词的自由搭配能力。最后根据规则生成的候选短语得为其包含词得分之和,公式如式(9)所示。

(9)

本文进一步考虑短语首现位置和频率两个短语特征来提高关键短语提取的准确率,在文本中短语首次出现位置越靠前并且出现频率越高表明该短语的重要程度越高,首现位置和频率分别用p(pi)和tf(pi)表示,最终候选短语排名得分计算式表示为:

(10)

计算全部候选短语得分后,根据降序排序选择前K个候选短语作为输入文本的关键短语。

4 实验与结果分析

为了验证本文算法性能,实验采用爬虫在国内新浪、搜狐和腾讯新闻网站上爬取了共1 046篇新闻文本,筛选出内容字数大于500的文本801篇,共计1 233 313字数,平均每篇约1 540字数,每篇文本的关键短语由人工手动标注。中文维基百科语料库选用最近2020年8月发布的语料数据“zhwiki-latest-pages-articles.xml.bz2”,处理之后得到371 263篇文章。通过Neo4j图数据库构建知识图谱CN-DBpedia,其中包含16 341 239个节点,54 173 197个关系。实验在配置为8 GB内存、i5-8300H处理器、Windows 10系统的笔记本进行,开发环境为PyCharm平台、Neo4j数据库。

4.1 评判标准

在实验中,本文采用准确率P、召回率R和F1值来评估关键短语提取的性能,其中:P指算法提取的正确关键短语个数占提取的所有关键短语个数的比例;R指算法提取的正确关键短语个数占人工标注关键短语个数的比例。由于P和R指标有时会出现相互矛盾的情况,使用对P和R的一个综合考虑的评价指标F1值来对算法性能进行评判,下面是三个评判标准的定义:

式中:Ccorrect是算法提取的正确关键短语个数;Ctotal是算法提取的所有关键短语个数;Cmark是人工标注关键短语个数。根据P、R和F1这三个评判指标可以对实验结果得出相对客观的评价。

4.2 实验参数

APKGRank存在两个参数可能影响着算法性能,分别为知识图谱中的语义相似度阈值τ和合并关系词图中的遍历窗口大小λ。因考虑到文本长短不一致导致平均标注关键短语个数不同,在讨论语义相似度阈值τ和遍历窗口大小λ时,将标记关键短语个数固定为所有文本的平均标注个数,提取关键短语个数K为10。

4.2.1 语义相似度阈值

在运用知识图谱CN-DBpedia中,考虑到CN-DBpedia中节点的顶点度较大,在实验中确定锚节点和其扩展节点最长路径的长度为2,设定遍历窗口大小λ为5,提取关键短语个数K为10。图4显示了τ对关键短语提取的影响,可以看出,赋予一个合适的语义相似度阈值可以提高算法性能,当τ=0.4左右时,F1值到达峰值,但是随着τ继续增大,由于较大的语义相似度阈值过滤了过多可能相关的语义关系从而降低了性能。从τ=0.6开始,由于基本过滤掉了全部的语义关系,算法性能不再变化。因此确定语义相似度阈值τ为0.4。

图4 F1值随语义相似度阈值τ的变化情况

4.2.2 窗口大小

为了分析合并关系词图的遍历窗口大小λ对关键短语提取性能的影响,本文设定提取关键短语个数K为10,语义相似度阈值τ为0.4。考虑到如果设置的窗口大小过大,则添加的边权值也会很大,从而影响到由挖掘语义关系得到的边权值,所以在实验中分析窗口大小λ=3,4,5,6,7时的算法性能。实验结果如图5所示,随着窗口逐渐增大,算法性能小幅提高,当λ等于5时,算法性能最佳。这表明适当地增加窗口大小可以把更多相关的词包括在内加强了语义关系,我们确定遍历窗口大小为5。

图5 P、R和F1值随窗口大小λ的变化情况

4.3 对比实验

本实验选用了三种经典的中文关键短语算法TF-IDF、TextRank和LDA来对比本文算法的有效性。图6为知识图谱KG的局部示例,例如考虑文本中未出现在预设定窗口内的“肺炎”和“钟南山”两个词,在共现图中不会引导任何边来连接它们,表明两者之间没有高度相关性,而根据知识图谱的语义网络结构计算“肺炎”与“钟南山”扩展节点之间的语义相似度得到边权值可以表现出两者有密切相关性,并且运用词连接方法得到词的正确映射,避免了扩展语料库中的大量噪声数据引入。从表1提取结果中可以看出,APKGRank算法提取到“新冠肺炎”和“钟南山”这两个关键短语正是需要的关键短语。表1显示了四种算法在提取关键短语个数K=5时的具体结果。

表1 不同方法提取的关键短语

图6 知识图谱KG的局部示例

图7、图8和图9分别显示了四种算法在准确性、召回率和F1值方面的性能情况,其中提取关键短语个数K=5,10,15,20。可以看出,随着提取关键短语个数增加,提取到正确的关键短语个数相比提取关键短语个数的增长较慢导致各算法的准确率逐渐下降,但召回率开始逐渐上升,原因是确定了标记关键短语个数,随着提取关键短语个数增加获取到正确的关键短语个数也逐渐增加。F1值是来综合评判算法性能的指标,可以看出本文方法相比其他三种算法F1值有了明显的提升。当提取关键短语个数为10时,算法性能最佳。这表明了相比于TextRank、TF-IDF和LDA,结合基于语义的AP聚类和知识图谱中的语义网络结构可以更深层次地挖掘出词之间的潜在语义关系,减少了外部语料库的噪声引入,从而提高了关键短语提取的性能。

图7 不同算法在P上的性能

图8 不同算法在R上的性能

图9 不同算法在F1值上的性能

5 结 语

本文提出一种基于知识图谱的中文关键短语提取算法,将基于语义的AP聚类与知识图谱相结合的方法来发现隐藏在输入文本中词之间的语义关系。基于语义的AP聚类方法加强了文本中的主题覆盖率,知识图谱的语义网络结构挖掘出词之间的潜在关系,并减少了外部语料库的噪声引入。最后使用改进PageRank获得每个词的排名得分,将两个短语特征与候选关键短语得分相结合得到最终短语得分。通过与经典的中文关键短语提取算法相比,本文算法在精确率、召回率和F1值上有了显著提升,表明本文算法在提取中文关键短语上性能更加良好。

我们下一步工作设想中,将加入更多的约束规则来优化生成候选关键短语,并结合深度学习模型提高关键短语提取效率。