基于通配符模式与随机游走的关键词提取方法

马慧芳,李 苗,童海斌,詹子俊

(1.西北师范大学 计算机科学与工程学院,兰州 730070; 2.桂林电子科技大学 广西可信软件重点实验室,广西 桂林 541004)

0 概述

随着计算机网络技术的发展与上网用户的增加,网页新闻与各类电子文档逐渐融入人们的生活中,文本关键词提取技术可以帮助用户从海量文档中获取有价值的信息,快速理解文档的核心内容。关键词提取在文本挖掘中主要是根据词项对文本内容的相关程度进行排序,因此单篇文档的关键词提取算法应运而生,并且广泛应用于推荐系统[1-2]、网络广告[3-5]及语义导航[6]等技术中。

关键词提取方法主要分为基于特征的关键词提取方法[7-9]、基于图的关键词提取方法[10-11]和基于语义的关键词提取方法[12-13]。基于特征的关键词提取方法使用句子位置、长度、签名词等度量为每个句子分配一个分数,如文献[8]研究频率对关键词提取的影响。基于图的关键词提取方法将文档表示为密集连接的图,其中每个节点表示一个句子,边连接两个句子,边的权重值表示两个句点之间的相似性,然后使用PageRank[14]等图算法对句子进行重要性评分。基于语义的关键词提取方法通过考虑文档内容的潜在语义,生成准确的关键词,如文献[12]利用词汇链表示文本的词汇连贯结构,将提取出包含高出现频次的链词的句子作为文档关键词。本文提出一种基于通配符模式和随机游走算法的关键词提取方法,利用深度优先模式搜索策略发现具有通配符模式的所有实例,通过数据结构层次实例图将模式支持度计算嵌入深度优先模式搜索过程中。

1 通配符模式

序列S是有序的项目列表,用S=s1s2…sn表示,Σ是序列S中所有可能项的集合,通配符是一种能够将Σ中的任意项进行匹配的符号,g[N,M]表示具有最小间隙N和最大间隙M的间隙。模式P=p1g[N,M]p2g[N,M]…g[N,M]pd是项目和间隙的序列,其中,模式长度用|P|表示,为P中的项目数。

定义1(模式出现和实例)给定模式P=p1p2…pd,序列S=s1s2…sn和间隙约束g=[N,M],如果存在位置序列1≤l1

定义2(一次性条件) 假设occ=(l1,l2,…,ld)和occ′=(l′1,l′2,…,l′d)是序列S中模式P的2个实例。如果对于所有1≤p≤d,1≤q≤d,有lp≠l′q,则这两个实例满足一次性条件。

定义3(支持度和支持集) 序列S中模式P的支持度被定义为所有可能的实例集的最大值,其中任何两个实例都满足一次性条件。用Sup(P)表示P的支持度,具有Sup(P)大小的实例集被称为P的支持集。

定义4(非重复模式) 给定模式P=p1p2…pd,如果∀1≤i,j≤d,pi≠pj,则将P称为非重复模式。

定义5(子模式与超模式) 对于两种模式P=p1p2…pm和P′=p′1p′2…p′n(n≥m),如果存在位置序列1≤i1

在挖掘序列模式时,本文引入SPMW算法[15-16]。给定序列S=s1s2…sn,模式P=p1p2…pm,间隙约束g[N,M],模式P的水平实例图表示为二元组,其中,V是节点集,E是边集。将节点集划分为m层,第i(1≤i≤m)层节点对应于pi的位置。假设A和B是pi和pi+1的两个节点,如果A和B的位置在同一个序列上,且满足间隙约束,则有一个从A到B的父子边和一个从B到A的子父边。图1是一个水平实例图,其中,实线表示父子边缘,虚线表示子父边缘,并且使用虚线连接相同的级别节点。

图1 水平实例图

在图1中,已知序列S=bcabccabcacdbdda和间隙约束g[0,5]。模式“b”在序列S中出现4次,分别在节点1、4、8和13处。第二层节点是项目a的4个位置,在满足间隙约束g[0,5]时,连接第一层节点。由前2个层级节点组成的图是模式Q=ba的实例图。类似地,模式R=baa的实例图由3个层级节点组成。实例图第二层中的节点16没有子节点。当计算模式R的支持度时,通过对节点7、10和16的深度优先遍历策略扫描实例图,其中<1,3,7>和<4,10,16>的出现次数为2。

2 关键词提取方法

2.1 关联图生成

模式P=p1p2…pd表示d个词满足间隙约束的关系,d取正整数。在构建关联图时,以词语之间存在的语义关系来确定节点之间的关系,因为只需要已知项目两两之间的关系,所以模式长度d取2。间隙约束为g[N,M],则P=p1g[N,M]p2。给定序列S,最小支持度阈值min_sup,计算出所有满足间隙约束和一次性条件的序列模式集合,并且计算出每个模式的支持度Sup(P)。将模式P中的所有不重复的项作为图的节点,当且仅当模式P的支持度Sup(P)大于等于最小支持度阈值min_sup时节点之间有边,边的权重为支持度的值,由于可能存在p1g[N,M]p2≠p2g[N,M]p1,因此节点之间的边是有向边。

已知序列S=bcabccabcacdbdda,间隙约束g[0,2],最小支持度阈值min_sup=2,所有可能项的集合Σ={a,b,c,d},计算Σ集合中任意两项的模式支持度如表1所示。将模式中所有不重复的项作为图的节点,图的节点集合为{a,b,c,d},当支持度大于等于2时节点之间有边,生成的节点关联图如图2所示。

表1 模式支持度

图2 节点关联图

2.2 引入先验信息的随机游走算法

PageRank是一种计算网页重要程度的算法,该算法认为如果一个网页被很多其他网页链连到,则说明该网页比较重要。模型定义如式(1)所示:

(1)

在式(1)中,节点之间的跳转概率是相同的,而理论上相似节点之间跳转的可能性会更大。节点之间边的权值越大,节点之间跳转的概率越大。在构建关联图时,将节点之间的支持度作为边的权重,因为支持度的取值为正整数,不利于随机游走计算,所以将支持度进行归一化处理,节点Ni跳转到节点Nk的概率如式(2)所示:

(2)

sim(Ni,Nj)=

(3)

其中,Ei是连接到Ni的文档集,|W|是文件总数。

式(3)表示2个节点Ni和Nj之间的语义相似度,在随机游走时需要节点Ni的先验分数,所以分别计算节点Ni与其他节点的相似度。为了更形式化地度量一个节点的先验分数,对节点Ni的先验分数进行归一化,如式(4)所示:

(4)

其中,ri表示节点Ni的先验分数,r=(r1,r2,…,r|N|)即为关联图中所有节点的先验概率分布。式(2)修正了节点之间的跳转概率,式(4)引入了知识库中的先验信息。结合式(2)和式(4)修正PageRank公式,如式(5)所示:

(5)

根据式(5)在关联图上随机游走,迭代计算每个节点的PR值,直至满足式(6)[18-19],使节点分数达到收敛状态,其中δ为随机游走终止阈值,并且使用图中的排名分数PR对关键词进行排序,将排名TopK个词作为关键词。

(6)

3 实验结果与分析

3.1 实验数据与评价指标

为验证本文方法的有效性,本文选取《物种起源》作为中文实验数据。经过预处理操作后有71 923个词项。选取MEHRI与DAROONEH合著的“The role of entropy in word ranking”文献(MD’paper)作为英文实验数据。经过预处理操作后有1 180个词项。选取维基百科知识库作为先验信息,使用工具包Wikipedia-Miner获得词语相似度。根据《物种起源》重要词汇注解表,选取15个重要词项作为评价关键词提取是否有效的基准,提取MD’paper中的9个重要词项作为评价英文关键词提取是否有效的基准。

综合平均精度均值(Mean Average Precision,MAP)、召回率(R)和Fβ作为关键短语提取的性能指标。设Mret表示本文关键词提取结果序列,Mrel表示真实词汇表序列,MAP定义如式(7)所示:

(7)

其中,Mret(j)表示关键词返回序列Mret的第j个词项,g(t,Mrel)表示指示函数,若词项t出现在原词汇表序列Mrel中则返回1,否则返回0,P(i)与AP(i)分别表示Mret中前i个词项的准确率与平均准确率。

Fβ准确率是由MAP和R相结合计算得到,其中β取值为0.5。Fβ定义如式(8)所示:

(8)

3.2 关联图模型参数分析

本节对最大间隙M、最小支持度阈值min_sup和衰减系数α这3个参数进行分析。在分析min_sup时,最大间隙M取3,在中文数据上的准确率如图3所示,在英文数据上的准确率如图4所示。图3结果表明,在min_sup取5时,Fβ具有最高的准确率,所以在中文数据上min_sup的最优取值为5。

图3 最小支持度阈值对准确率的影响(中文)

图4 最小支持度阈值对准确率的影响(英文)

在分析最大间隙M时,min_sup取5,在中文数据上的准确率如图5所示,在英文数据上的准确率如图6所示。图5结果表明MAP和Fβ都在M取4时达到峰值。图6结果表明,当M取3时,MAP具有最高的平均精度均值。造成中英文数据上M的最优取值不同的原因是中文数据《物种起源》是一个较长的文本,而MD’paper英文数据相比于中文数据来说较短。

图5 最大间隙对准确率的影响(中文)

图6 最大间隙对准确率的影响(英文)

在分析衰减系数α时,采用中文数据,当min_sup取5、最大间隙M取4时,得出的MAP如图7所示。当α取0.55时,MAP达到峰值。

图7 衰减系数α对MAP的影响

3.3 关键词提取性能对比及分析

为验证本文关键词提取算法的准确性与优越性,选取TextRank、GraphSum算法与本文算法进行比较分析。实验结果如表2、表3所示,其中阴影部分表示该算法提取出的关键词在关键词参考集中不存在。可见,在中文数据及英文数据上,GraphSum算法得到的关键词与TextRank算法得到的关键词相比更为准确。然而,与本文方法相比,使用GraphSum、TextRank算法得到的结果均有所欠缺。3种方式在中文数据和英文数据进行关键词提取时得到的MAP、R和Fβ如表4所示。本文方法在中文数据和英文数据上进行关键词提取得到的MAP均大于其他两种算法。

表2 3种关键词提取方式的结果对比(中文)

表3 3种关键词提取方式的结果对比(英文)

表4 3种关键词提取方式的性能对比结果

为验证本文方法运行效率,在Celeron 1.40 GHz处理器的Windows 10操作系统下,给出本文方法在不同词量规模下的运行时间,如图8所示。由于本文考虑了语义信息和先验信息,因此本文方法的执行效率会比其他算法更低。但随着词量规模的扩大,本文方法的运行时间接近于线性增长。

图8 3种方式的运行时间比较

4 结束语

本文提出一种基于通配符模式和随机游走算法的关键词提取方法。该方法基于通配符约束和一次性条件来挖掘序列模式,使用深度优先搜索策略计算模式支持度,挖掘出具有间隙约束的所有模式实例,并在模式支持度大于等于最小支持度阈值时构建关联图,同时通过引入先验信息的PageRank算法获取排名前TopK个词语作为关键词。实验结果表明,本文方法相比传统关键词提取算法具有更高的准确率和稳定性。后续可将句子位置、签名词、图结构等信息引入到随机游走算法中,进一步降低关键词提取算法复杂度并提高执行效率。