0 概述

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

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

1 通配符模式

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

定义1(模式出现和实例)  给定模式P=p₁p₂…p_d, 序列S=s₁s₂…s_n和间隙约束g=[N, M], 如果存在位置序列1≤l₁<l₂<…<l_d≤n, 使得s_lj=p_j(1≤j≤d)且N≤l_j-l_j-1-1≤M(2≤j≤d), 则(l₁, l₂, …, l_d)是序列S中出现的模式P。给定模式P和序列S, 如果(l₁, l₂, …, l_d)是S中出现的模式P, 那么(l₁, l₂, …, l_d)被认为是序列S的P实例。

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

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

定义4(非重复模式)  给定模式P=p₁p₂…p_d, 如果∀1≤i, j≤d, p_i≠p_j, 则将P称为非重复模式。

定义5(子模式与超模式)  对于两种模式P=p₁p₂…p_m和P′=p′₁p′₂…p′_n(n≥m), 如果存在位置序列1≤i₁ < i₂ < … < i_m≤n, 对于所有1≤j≤m, 有p′_ij=p_j, 那么P被认为是P′的子模式, 用P⊆P′表示P′是P的超级模式。只有在没有超级模式P的情况下, 模式P′才是封闭模式, 此时Sup(P)=Sup(P′)。

在挖掘序列模式时, 本文引入SPMW算法^[15-16]。给定序列S=s₁s₂…s_n, 模式P=p₁p₂…p_m, 间隙约束g[N, M], 模式P的水平实例图表示为二元组<V, E>, 其中, V是节点集, E是边集。将节点集划分为m层, 第i(1≤i≤m)层节点对应于p_i的位置。假设A和B是p_i和p_i+1的两个节点, 如果A和B的位置在同一个序列上, 且满足间隙约束, 则有一个从A到B的父子边和一个从B到A的子父边。图 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=p₁p₂…p_d表示d个词满足间隙约束的关系, d取正整数。在构建关联图时, 以词语之间存在的语义关系来确定节点之间的关系, 因为只需要已知项目两两之间的关系, 所以模式长度d取2。间隙约束为g[N, M], 则P=p₁g[N, M]p₂。给定序列S, 最小支持度阈值min_sup, 计算出所有满足间隙约束和一次性条件的序列模式集合, 并且计算出每个模式的支持度Sup(P)。将模式P中的所有不重复的项作为图的节点, 当且仅当模式P的支持度Sup(P)大于等于最小支持度阈值min_sup时节点之间有边, 边的权重为支持度的值, 由于可能存在p₁g[N, M]p₂≠p₂g[N, M]p₁, 因此节点之间的边是有向边。

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

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

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

$\mathrm{PR}\left(N_{i}\right)=\alpha \cdot \sum\limits_{k=1}^{e} \frac{\mathrm{PR}\left(N_{k}\right)}{C\left(N_{k}\right)}+(1-\alpha) \bar{P} $

(1)

其中, N_i表示第i个节点, PR(N_i)表示N_i的PageRank分数, e表示N_i的入边条数, C(N_i)表示N_i的出边条数, α表示一个节点跳转至非邻居节点的衰减系数, P表示所有节点的先验分数。

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

$\operatorname{Nor}_{i, k}=\frac{\operatorname{Sup}\left(N_{k} N_{i}\right)}{\sum\limits_{j=1}^{C\left(N_{k}\right)} \operatorname{Sup}\left(N_{k} N_{j}\right)} $

(2)

式(1)中的P通常被初始化为1/|C|, 其中|C|表示关联图中的节点个数。但是实际情况通常希望更重要的节点分配更高的先验分数, 而不太重要的节点的先验分数变低, 本文利用知识库给出先验排名分数。文献[16-17]提出的监督随机游走被用于预测社交网络中链接的出现, 即监督信息引入到标准的无监督随机游走模型, 并将知识库的语义关系融入监督信息。维基百科或YAGO的知识库提供内容信息以及内容单元之间的链接信息, 在这些链接中含有大量语义信息。维基百科包含超过400万篇文章, 并提供比其他知识库更多的文字覆盖, 因此本文使用工具包Wikipedia-Miner得到维基百科知识库中的链接信息。对于2个节点N_i和N_j, 它们之间的语义相似度计算如式(3)所示:

$\operatorname{sim}\left(N_{i}, N_{j}\right)=\\ 1-\frac{\log _{a}\left(\max \left(\left|E_{i}\right|, \left|E_{j}\right|\right)\right)-\log _{a}\left(\left|E_{i}\right| \cap\left|E_{j}\right|\right)}{\log _{a}(|W|)-\log _{a}\left(\min \left(\left|E_{i}\right|, \left|E_{j}\right|\right)\right)} $

(3)

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

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

$\left\{\begin{array}{l}r_{i}=\frac{1}{z} \sum\limits_{j \in C} \operatorname{sim}\left(N_{i}, N_{j}\right) \\ z=\sum\limits_{i \in C} \sum\limits_{j \in C} \operatorname{sim}\left(N_{i}, N_{j}\right)\end{array}\right. $

(4)

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

$\operatorname{PR}\left(N_{i}\right)=\alpha \times \sum\limits_{k=1}^{e}\left(\operatorname{PR}\left(N_{k}\right) \times \operatorname{Nor}_{i, k}\right)+(1-\alpha) \times r_{i} $

(5)

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

$\sum\limits_{i=1}^{|C|}\left|\mathrm{PR}^{t+1}\left(N_{i}\right)-\mathrm{PR}^{t}\left(N_{i}\right)\right| \leqslant \delta $

(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_β作为关键短语提取的性能指标。设M_ret表示本文关键词提取结果序列, M_rel表示真实词汇表序列, MAP定义如式(7)所示:

$P(i)=\frac{1}{i} \sum\limits_{j=1}^{i} g\left(M_{\text {ret }}(j), M_{\text {rel }}\right)\\ {\rm{AP}} (i)=\frac{\sum\limits_{j=1}^{i} P(j) \times g\left(M_{\text {ret }}(j), M_{\text {rel }}\right)}{\sum\limits_{j=1}^{i} g\left(M_{\text {ret }}(j), M_{\text {rel }}\right)}\\ {\rm{MAP}} ={\frac{1}{M_{\text {ret }}} \sum\limits_{r=1}^{M_{\text {ret }}}} \operatorname{AP}(i) $

(7)

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

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

$R=\frac{\left|M_{\text {ret }} \cap M_{\text {rel }}\right|}{\left|M_{\text {ret }}\right|}\\ F_{\beta}=\frac{\left(1+\beta^{2}\right) \times \text { MAP } \times R}{\beta^{2} \times \text { MAP }+R} $

(8)

3.2 关联图模型参数分析

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

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

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

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

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

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

4 结束语

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