一种基于自适应关联熵的关键字提取算法

罗有志，陈征明，陈 明，梅文涛

(1.国网湖南供电服务中心(计量中心)，湖南 长沙 410004； 2.国网湖南省电力有限公司常德供电分公司，湖南 常德 415000)

0 引 言

随着信息时代的来临，人们获取的信息量呈现几何形式地增长，出现了许多不同类型的数据信息，其中文本[1]类型的数据和图形[2]类型的数据等最具有代表性。文本挖掘[3-6]技术能够从海量的文本类型数据中找到人们所需要的信息，如何快速有效地对文本信息进行挖掘已成为当前人工智能[7-8]领域的一个重要研究方向。关键字词汇的提出较大程度地减少了文本信息挖掘的工作量，极大地提高人们的工作效率。作为文本挖掘技术中的重要基础性工作，如何对关键字进行标识直接关系到文本信息挖掘的效果，因此确保关键字提取[9-10]的准确度对文本信息处理具有重要意义。

对于关键字的提取，传统的TF(Term Frequency)方法[11]是以词汇频率的大小来进行的，具备简单易行的特点，其中频率高的词汇成为关键字的比例较大，而频率较低的词汇成为关键字的可能性较小。这种基于统计的方法忽略了词汇在单文本中所包含的意义，使得关键字的提取不全面，造成文本语义的缺失。TFIDF算法[12-14]在原有词频(TF)的基础上增加了IDF系数(IDF=log (N/n))，充分考虑整体文档集数N和词汇在某些文档中出现的次数n，但是在处理低频且IDF值较高以及处理高频且IDF值较低的词汇时具有较为明显的错误缺陷。TextRank算法能够很好地处理单文本和多文本的关键字提取问题，具有快速反馈、弱语言相关等特点，但TextRank算法[15-16]主要是利用局部词汇之间的关系来进行确定，受词频影响仍然较大，缺乏对文档整体全面的考量，同时由于权重的固定不能够对词汇链接关系进行有效的判断。为了优化TextRank算法特性，李鹏等[17]提出了Tag-Text Rank方法,利用网页标签提高网页关键词提取效果。谢玮等[18]在TextRank基础上,同时考虑词的逆文档频率,用于论文审稿自动推荐中的关键词提取。本文提出利用关联规则挖掘[19-20]找出文本中所包含的频繁项目集，计算出词汇所包含的关联信息熵，并结合TextRank算法对候选关键字权重系数进行调整，自适应调整窗口大小，迭代计算得到最终的节点权重，选取排名靠前的词汇项作为关键字，得到较为理想的关键字提取效果。

1 相关概念

文本数据挖掘的关键字提取是进行相关研究的基础性工作，提取效果的好坏直接关系到文本内容信息的读取。由于TextRank算法具有简单有效和语言弱相关等特点，目前已成为广泛使用的关键字提取方法，但是受到词频影响较大，因而相较于其他关键字提取算法不具备太大的优势。本文引入信息熵和词汇之间的关联关系，解决词汇词频的单一特性，更好地考虑词汇的全局和上下文语义特性，获得更好的提取效果。

1.1 TextRank算法模型

该算法首先利用分词对文本进行分割，以“句”为单元排除无用习性的词汇，保留其中的动词、名词等作为候选关键字选项集Qi={si1,si2,…,sin}，其中i代表句子编号。通过设定滑动窗口的参数K值，将句子中距离小于K的词汇归纳到同一窗口进行标记，即{s0,s1,…,sk}{s1,s2,…,sk+1},…,{sn-k,sn-k+1,…,sn}，出现在同一窗口的词汇之间建立链接关系，形成相应关键字链接矩阵。在TextRank模型中主要包括无向图和有向图2种类型，具体如图1、图2所示。

图1 无向图

图2 有向图

其中，无向图的矩阵表达式为：

(1)

迭代计算公式如下：

(2)

有向图的矩阵表达式为：

(3)

迭代计算公式如下：

(4)

其中，In(si)代表与词汇si相链接的集合，out(sj)代表指向sj的词汇集合，d为阻尼系数。通过对文档进行遍历迭代收敛到一定的区间范围，从而得到所有词汇的T(si)值序列，进而选取其值排名靠前的词汇作为文本的关键字。

具体算法步骤如下：

1)利用语句分隔符对文本进行句子切割，并通过分词器得到文本词汇，标记词汇属性，剔除停用词等无关语义的词汇，保留其中的动词、名词、形容词等重要词汇，采用句子为单位对文本进行切割划分。

2)根据文本中划分的句子中的词汇信息，筛选出重复词组，建立初始化单词链接矩阵。

3)遍历文本中的所有句子，以参数值为K的滑动窗口对句子中同一窗口中包含的词汇进行标记，找出链接矩阵所对应位置的词组，并对有向图/无向图进行迭代计算，直至收敛到可接受的区间值。

4)针对文本遍历图中所有节点的权重进行排序，选择其中权重靠前的n个词组节点作为此文本的关键字候选。

TextRank算法能够实现简单有效的关键字提取，但是其存在的局部性容易忽略词汇整体的上下文联系，对于词汇本身在全文中的特点也缺乏考虑。同时由于受词汇切割的影响，导致文本在顺序窗口迭代时存在某些缺陷，致使算法全局性较弱。

1.2 关联熵的相关定义

在海量文本内容中，信息熵能够对文本进行量化评估，表达了词汇所携带的信息量情况，得到整体文本所包含的信息期望值。通常情况下，针对某一词汇来讲，其信息熵[21-23]值越大，则其在整个文本中的分布也就越平均，也就表明这种词汇出现的概率也就越大，包含单调性、非负性、累加性3种特性。其计算公式如下：

(5)

其中，Pi表示类i的概率，n表示分类的数目。

对于文本关联规则来说，主要是通过词汇与词汇之间的关联信息，找出文本集中所包含词汇项之间的关系。为了得到词汇之间的关联信息，关联规则选取的好坏直接关系到词汇关联信息的准确性，蕴含表达式如下：

R:X⟹Y

(6)

其中，X∩Y≠0，表示由于词汇集X的出现，导致词汇集Y出现。若将词汇A与词汇B之间的关联称为交易，则词汇项集为若干个词汇项的集合，其中词汇项可能是词汇A或B，也可能是词汇A与B之间的关联交易。对于词汇项集来说，count(X)代表词汇项集X所包含关联交易数量。通常采用置信度(confidence)和支持度(support)这2个参数对规则进行评价。其中支持度表示同时有词汇项集X与词汇项集Y的概率情况，具体公式如下：

(7)

其中，D表示全体词汇项集。

置信度表示在词汇项集X出现的情况下，词汇项集Y出现的概率情况，具体公式如下：

(8)

关联规则算法包含频繁项集的建立和关联规则的产生2个步骤，目前较为流行的算法包括Apriori算法和FP-growth算法等。

为了更好地对关联规则进行直观描述，本文引入关联熵的概念，对词汇在文本中所包含的关联规则进行度量计算。通过对文本中词汇之间的关系进行关联规则挖掘，建立频繁词汇集Q={(s1,…,sk),(si,…,sl),…,(sj,…,sl)}作为文本的词汇项集，并根据频繁词汇项集计算得到词汇si的权重，记为W(si)：

W(si)=H(si)×count(si)

(9)

其中，count(si)为词汇si在文本中出现的次数。词汇集S={s1,s2,…,sn}中包含n个词汇，其中词汇si出现的概率记为Psi，则词汇si的信息熵Hsi的计算如公式(5)所示。为了更好地体现新热门词汇在文本中的意义，特赋予新出现的词汇信息熵值为1，代表其所反映的文本热点问题。

2 基于自适应关联熵的关键字提取算法

对于TR算法而言，图节点中的权重系数计算主要通过遍历链接矩阵，而其中涉及节点词汇的阻力系数d值和滑动窗口的参数K值基本上是固定不变的。除此之外，TR假设只有同一个句子中并且位置距离保持在滑动窗口K值内，才会将2个不同词汇进行同一标识，这样遍历链接矩阵时会忽略词汇在文本中的上下文信息，容易引起词汇在文本中的重要性偏差，降低文本关键字的提取效果。

根据Chomsky对文本语句的阐述，文本语句单元中词汇的顺序不构成语句语义的必要联系，存在顺序相异词汇的语句可能会产生相似的语义。同时，段落和文档都包含一定的语义方向，所包含的词汇频率信息也在一定程度上影响到词汇权重的计算。为了得到更有效的关键字集合，本文以句子为单元将文本S划分为S={s1,s2,…},{…},{sn-k,…,sn}，其中{s1,s2,…}称为一个单独的句子，包含词汇s1,s2,…,si。将出现在同一个句子中的词汇标识为信息关联，即：

S:s1⟹si

(10)

式(10)表示词汇s1,s2,…,si之间互存关联信息。

以单个词汇作为初始频繁集，根据词汇之间的关联信息逐步得到高层频繁项集。为了更好地与关键字提取信息进行吻合，设定频繁项集的层级数与关键字提取数n保持一致。低层级的频繁项集往往包含于高层级的频繁项集，如“关键字”与“关键字提取”，而“关键字提取”包含“关键字”信息，这样就会造成某些关联信息的冗余，所以应该保留高精度的文档主体。假设频繁项集s1和s2对应的层级数为i和j，满足s1⟺s2，且i>j，则可认为频繁项集s1包含频繁项集s2的关联规则，则在文本中去除频繁项集s2，最终生成不含重复关联信息的频繁项集Q，即：

Q={(s1,…，sk),(si,…，sl),…,(sj,…，sf)}

(11)

根据关联熵的概念，计算得到关联词汇s1的信息熵为Hs1(X)，具体计算公式如下：

(12)

其中，Ps1i为词汇s1在频繁项集Q中i项集合中出现的概率，进而得到词汇s1的权重W(s1)值(信息熵越大表明词汇s1分布在文本中的重要性越大，信息熵越小表明词汇s1的重要性越小)。

为了使算法更符合实际情况，利用整个句子作为滑动窗口的构造基础，将TR算法中的滑动窗口参数K设置为随着句子长度L而变化，使得滑动窗口能够自适应调整，窗口参数K′=(L′/L)K，即整个词汇集中的词汇都存在边图矩阵连接。通过对文本词汇之间存在的关联关系进行挖掘，得到有效的频繁项集信息，最大程度地对词汇在文本中的含义进行评估，并通过链接矩阵迭代计算得到词汇的权重T(s)值，选取T(s)值排名靠前的词汇作为关键字的选项，具体的算法步骤如下：

1)利用语句分隔符对文本进行句子切割，并通过分词器得到文本词汇，标记词汇属性，剔除停用词等无关语义的词汇，保留其中的动词、名词、形容词等重要词汇。

2)对文本词汇进行关联规则挖掘，将包含在同一句子中的词汇A和B定义为存在关联关系{A,B}，并对整个文本进行关联规则联合迭代，生成最大频繁词汇项集Q={(s1,…，sk),(si,…，sl),…,(sj,…，sl)}，同时根据不同大小的频繁项集生成相应的滑动窗口参数K，使当前参数K′值为前向K值的句子长度L的正相关比例，即K′=(L′/L)K，让滑动窗口最大程度地反映同一语句词汇的标识问题。

(13)

式(13)可得到词汇的权重T(s)值。

4)遍历整个频繁项集Q={(s1,…，sk),(si,…，sl),…,(sj,…，sl)}的链接矩阵，迭代计算词汇T(s)值，待收敛到可信阈值区间，对所有词汇的T(s)值进行排序，选取T(s)排名靠前的N个词汇作为文本段的关键字。

本文采用关联熵概念来计算文本关键字信息，弱化了词汇频率的重要性，针对词汇上下文信息作出更准确的关键字提取效果。根据得出的词汇关联熵信息，可得出词汇与其他词汇之间存在的链接程度信息，即词汇与其他关联词汇之间的阻尼程度如何。若词汇在文本中出现的频率较低，但该词汇在文本结构中出现在较为重要的位置(如与高频词汇关联程度较高等)，则表明该低频词汇在文本中的重要性应该有所提高，即词汇关联熵信息权重有所增强，因而这类低频而重要的词汇得到更好的处理。

3 实验数据分析

本文通过提取搜狗文本集和复旦大学文本集中的历史、法律、教育、艺术、计算机等类别文本作为实验样本，每种类别下样本数量保持在1000份左右。在处理实验文本之前，首先利用中文分词器(hanlp分词器)对实验文本进行预处理，剔除停用词和无用符号并标注词汇的词性。选取实验运行环境：操作系统为Win 7，内核Intel Core i7 CPU M 540，内存4 GB。

对于这些文档而言，关键字个数基本保持在5个左右，因此设定提取的关键字数量为5和6，具体的实验效果如表1、表2所示。

表1 提取5个关键字的覆盖率 单位：%

表2 提取6个关键字的覆盖率 单位：%

实验数据表明，在大量文本数据信息的情况下，相较于TFIDF算法[12]、TR算法[16]及Tag-TR算法[17]，本文提出的改进关联熵的关键字提取算法能够达到更好的效果。针对文本内容的解释，其上下文含义不仅仅体现在词汇出现的频率上，词汇在上下文出现的位置以及词汇与词汇之间的关联也有很大的意义，因而对于关键字的选取应计算词汇在文本中的关联信息。为了更进一步观察算法在关键字提取过程中特点(如关键词“文档”和关键词“支付”)，将其所代表的PR曲线展示出来，如图3、图4所示。

图3 PR图——关键字“文档”

图4 PR图——关键字“支付”

从图3和图4可以看出，本文曲线与坐标轴的面积是最大的，表明相较于TFIDF算法、TR算法及Tag-TR算法，本文提取关键字的效果有一定的优势，通过对词汇之间存在的关联关系进行挖掘，并将其用关联熵进行量化分析，结合TR迭代计算选取排名靠前的k个词汇作为关键字候选，能够得到较好的关键字提取效果。

4 结束语

在数据信息大爆发的时代，网页内容和各种工单基本都以文本的形式进行传输，如何对文本进行高效处理就显得尤为关键。文本关键字能够简化文本的阅读效率，大大提高信息接受程度，因而关键字提取效果的好坏直接关系到信息量的获取程度。在传统基于词频的关键字提取的经验积累上，利用文本词汇上下文信息对词汇重要性进行全局化的评估，能够最大程度地反映词汇所占文本的关键程度，得到较好的关键字提取效果。但在处理分散词汇以及不常用词汇时还存在一定不足，如某个词汇确定为关键字，而其在某文本中出现的次数不多，就容易将这部分词汇归纳为非关键字，导致结果出现偏差。下一步将在全局训练样本中对词汇关联熵进行研究，对算法做进一步提升和改进。