基于密度及文本特征的新闻标题抽取算法

彭圳生,巩青歌,高志强,段妍羽,曾子贤

(1. 武警工程大学 信息工程学院，陕西 西安 710086；2. 军队大数据与云计算重点实验室，陕西 西安 710086)

0 引言

[1][2]。

相对于有着成熟研究的Web正文信息抽取技术[3-5]，新闻标题抽取技术的研究相对较少，其主要难点在于： 对于大量的复杂非规范网页来说，无法根据某种统一的网页结构或规则进行统一抽取，且新闻标题的特征不像正文一样明显[6]，在抽取的过程中，很容易被埋没在正文中或者被遗漏，无法很好地与正文分开抽取。然而，只有从网页中准确抽取出新闻标题，才能为后期信息检索和文本挖掘提供准确依据。

1 相关工作

虽然新闻标题抽取是Web信息抽取中的一个重要课题，但这方面的研究目前还比较少[7]，尤其对于复杂不规范的网页结构，尚未提出一种通用的新闻标题抽取方法。目前对新闻标题的抽取技术主要集中在： ①基于网页规则[5,8-12]方法；②基于机器学习[1,7,13-17]方法;③基于相似度[18-21]方法。

针对基于网页规则的新闻标题抽取技术研究，Zhang[9]等通过XPath规则自动抽取Web论坛内容，并通过统计和预测的方法自动生成抽取规则。Wang[10]等提出一种基于DOM树的提取方法，将DOM树转化为STU-DOM树，通过信息提取算法自动准确地从HTML文档中提取有用的相关内容。

针对基于机器学习方法的新闻标题抽取技术研究，朱青[13]等将HTML格式及DOM树结构等信息引入机器学习抽取过程中，实现对新闻标题的抽取。罗永莲[7]等提出一种基于新闻特点与网页标记信息的方法，将网页标记和文本相似度作为机器学习的特征来提取新闻标题。

针对基于相似度的新闻标题抽取技术研究，李国华[18]等利用网页标题和正文信息之间的关系，通过计算句子之间的相似度和对应权值确定新闻标题。Mohammadzadeh[21]等人将每个文本片段的内容与HTML文件中的标题进行比较，并实现了四种类型的相似性比较方法。

随着网页结构日趋复杂，网页元素日趋多样，网页噪声内容逐步增多，按照网页结构和HTML标签编写规则并维护模板的统一抽取网页信息的方法愈来愈不可行。一方面，随着HTML和CSS的分离，样式特征很难具有区分性质，重新标注网页训练集，而后再重新训练机器学习，模型代价巨大，基于样式特征的机器学习方法已经不再适用；另一方面，由于网页编写规则不统一，不同网站编写的随意性很大，基于网页DOM结构和XPath的信息抽取方法很难保证抽取效果。因此基于网页规则及基于机器学习的抽取方法的实用性和适用性极大降低。

本文将基于密度的正文抽取方法引入新闻标题的抽取方法中，过滤网页中非文本信息(例如，链接、图片、视频等非文本网页噪声)的干扰，提出一种基于密度和文本特征的语料判定模型，通过判定模型将网页划分为语料区和标题候选区，利用Text Rank算法[22]从语料中计算key-value权重集合，结合改进的相似度计算方法从标题候选区域抽取出新闻标题。最后通过多源数据适应性实验和传统算法的对比实验，验证了算法的适用性和有效性。

2 抽取算法实现

基于密度及文本特征的新闻标题抽取算法(title extraction with density and text-features, TEDT)实现主要由三部分构成： 语料判定模型(corpus decision model, CDM)进行区域划分；通过TextRank算法构建key-value权重集合，获得词(key)和词对应的权重(value)；利用改进的相似度计算方法，从标题候选队列中抽取新闻标题。

2.1 语料判定模型

对语料区和标题候选区进行划分前，需要过滤Script、Style、Comment标签，去除网页特殊标记(包括空格)并只保留换行符“ ”，最后再过滤掉不包含中文文本信息的行，处理后的HTML网页源代码中由含有中文的文本行和换行符“ ”构成。新闻的正文区域和标题区域有如下特征。

(1) 正文一般在标题下方，两者中间一般含有发布时间、新闻来源、编辑或者外部链接等信息。

(2) 新闻标题的文本特征表现为标题是对正文的概括，所以标题中关键词多。此外，由于新闻标题的简洁性，新闻标题含有的特殊符号少且一般没有分句符。

(3) 正文具有连续性，即从正文开始到正文结束之间的内容一定为正文。正文部分(即使包含图片、视频和链接)文本行之间的间隔一般不超过10个换行符[5]；文本行之间如果没有间隔，则必定属于正文。

(4) 正文的文本行一般较长且含有分句符。

(5) 正文的头部和尾部的文本特征表现为阿拉伯数字比较多，例如发布日期、发布时间和浏览次数等其它特殊标记。由于已经不属于正文部分，所以分句符较少，且一些特殊的词出现的频率较高，如，“来源”、“编辑”、“收藏”、“分享”、“评论”、“阅读”等。

根据以上关于网页中新闻内容密度分布特性和新闻文本特征的分析，总结出以下特征变量：

(1) 纯文本数(Pure Text Number, PTN): 一个文本行中包含中文字符的个数。

(2) 句数(Sentence Number, SN): 一个文本行中句子的个数，按照“，。；！？”的标点符号划分。

(3) 数字数(Numerals Number, NN): 一个文本行中所包含的阿拉伯数字的个数。

(4) 特殊字符数(Special Characters Number, SCN): 一个文本行中“: - |《》”符号和其他不同于分隔句子的符号个数。

(5) 特殊中文字符(Special Chinese Characters, SCC): 在正文开始前与正文结束后出现频率较高的词语，如“来源、编辑、收藏、分享、评论、阅读”等。

(6) 中心间隔(Center Distance,CD)： 当前文本行与上一个加入语料区文本行之间的换行符个数。

(7) 字符数(Characters Number, CN): 每个文本行中字符的个数，不管是汉字、英文还是符号都算作一个字符。

区域划分的关键在于判别语料区和标题候选区，为保证所选取的语料都属于正文，并在进入标题候选区之前语料选取判停，我们引入了风险因子，如式(1) 所示。

(1)

其中，α表示准备加入到语料区的文本行的权值，PTN表示该文本行的纯文本数，∑leni*SCCi表示该文本行中所出现的第i个特殊中文字符数与该字符长度乘积的和，NN表示当前文本行中出现阿拉伯数字的个数，SCN表示当前文本行中出现的特殊字符的个数，SN表示当前文本行中分句符的个数。以上所有变量均有可能为0，因此ln中的分子、分母同时加上调节常量1。

风险因子ln部分的分母NN+SCN+∑leni*SCCi+1体现为： 加入语料库中的文本行中，如果当前文本行中出现的阿拉伯数字、特殊字符数和特殊中文字符所占比重越大，则越有可能不属于正文，ln部分的分子PTN-∑leni*SCCi+1体现为，加入语料库中的文本行中，如果纯文本数越多，特殊中文字符所占比重越小，则该行越有可能属于正文。此外，当前文本行中分句符的个数SN体现为，如果加入语料区中的该行中含有的分句符越多，其越有可能属于正文。

根据风险因子的计算公式，当α大于0时，将对应文本行加入语料区，当α小于0时可以认为选取的语料不属于正文。结合正文连续性的特征，进一步得到语料判定模型(Corpus Decision Model, CDM)，如式(2)所示。

(2)

其中，CDMi是对加入语料库的第i个文本行的判断值，CDi表示当前加入语料区的文本行的中心间隔，即第i行与前一个加入语料区的文本行之间换行符“ ”的个数，CNi表示第i个文本行中字符的个数；当CDi为0且CNi不为0时，CDMi的判定值为1，表明在文本行与文本行之间没有间隔且加入语料区的文本行不为空行的情况下，该文本行一定属于语料区；当CDi≥10或CNi为0时，CDMi的判定值为0，表明当前文本行与其加于语料区中的上一文本行间隔距离大于10或者加入语料区的当前文本行为空行的情况下，该行一定不属于语料区；当0

算法1CDM区域划分算法伪代码

程序输入: HC(Html Code)

程序输出: corpus, titleCandidateQueue

初始化变量

1： Corpus = []

2： titleCandidateQueue = []

3： HC←removeScript/Style/Label(HC)

初始语料选择

4：Forall textLine in HC

5： PTN←chineseNumber(textLine)

6：EndFor

反向判定

8：FortextLine in HCstart

9： PTN←ChineseNumber (textLine)

10： SN←sentenceNumber (textLine)

11： NN←numeralsNumber (textLine)

12： SCN←specialCharactersNumber(textLine)

13： SCC←specialChineseCharacters (textLine)

14： CN←lenght(textLine)

15： CD←distance (textLine)

16：IfCD=0 and CN≠0

17： Corpus.append(textLine)

18：EndIf

19：IfCD≥10 or CN=0

20：Break(set textLine index as end)

21：EndIf

22：Ifα<0(αrefer to PTN,SN,NN,SCN,SCC)

23：Break(set textLine index as end)

24：Elsedo step 17

25：EndIf

26:EndFor

27： titleCandidateQueue.append(HC0～end)

正向判定

28：FortextLine in HCstart

29： do step 9～25

30：EndFor

为了展示网页文本行区划分的效果，以凤凰资讯2017年12月26日新闻《技术创新领导未来： 小间距LED 2018年行业10大猜想》为例，经过算法1处理后，其网页文本行被划分成三个部分，其中第一个部分为新闻标题候选区(0～287行)，第二个部分为语料区(288～391行)，第三个部分(392～1 000行)直接舍弃，具体效果如图1所示。

图1 网页文本行区域划分效果图

2.2 构建单词权重集合

TextRank[22]是PageRank算法[23]的改进版，其算法核心如式(3)所示。

(3)

式(3)中，TextRank利用权重项ωji，表示两个节点之间的边连接的重要程度,其中d为阻尼系数，一般取值为0.85。对于一个给定的点Vi，ln(Vi)为指向Vi的点集合，Out(Vj)为Vj指向其他点的集合。利用TextRank构建单词权重集合的具体算法如算法2所示。

算法2TextRank构建key-value权重集合算法伪代码

2.3 计算标题候选队列权重

在算法2输出单词权重集合的基础上，根据改进的相似度公式计算标题候选队列的相似度。在数据挖掘领域，通常采用Jaccard相似系数计算两个含有布尔值度量对象之间的距离(相似度)，如式(5)所示。

(5)

(6)

(7)

在对β进行归一化处理时，式(7)中的βi为标题候选队列中选取的当前文本行的β值，βj(1≤j≤n)是标题候选队列每个文本行的β值，n为标题候选队列的长度值。

从新闻标题候选队列中抽取新闻标题的算法伪代码如算法3所示。

算法3改进Jaccard标题抽取算法伪代码

在算法3中，首先利用改良的风险因子β过滤标题候选区中不具备新闻标题文本特性的候选项，而后通过改进Jaccard标题抽取算法抽取新闻标题。通过计算β

图2 网页文本行标题候选区密度分布

3 实验与结果分析

为了验证本文基于密度及文本特征新闻标题抽取算法(算法源代码https://github.com/pzs741/TEDT)的有效性，设计两组实验:

(1) 针对主流新闻网站和复杂不规范新闻网站，测试算法的适用性。

(2) 与传统的基于相似度和基于规则的新闻标题抽取算法进行对比，验证算法的有效性。

3.1 测试样本集

测试样本主要来源于各大主流门户网站和院校内部信息网，通过网络爬虫爬取了3 100个新闻网站并手工摘取并标注了新闻标题，其中主流门户网2 050个，院校内部信息网1 050个，分为主流网站新闻标题和复杂不规则网站新闻标题两个互不重叠数据集。

3.2 评价标准

抽取单一网页新闻标题的准确率P，召回率R和F1值定义如式(8)所示。

(8)

其中，a是自动抽取的网页新闻标题的字符序列，b是手工标注网页新闻标题的字符序列，LCS(a,b)为a、b的最大公共子序列，.len是序列对应的长度。

为综合评价TEDT算法对大量复杂不规范网页的性能，采用平均准确率、平均召回率和平均F1的值作为评价指标，如式(9)所示。

(9)

其中，Pi,Ri,F1i分别是单个网页的准确率、召回率和F1值，N为网页集合的数量。抽取新闻标题的最终结果有四种情况，其主要受到TEDT算法中CDM区域划分的影响。第一种抽取结果为准确的新闻标题，出现这种情况表示算法划区是准确的；第二种抽取结果是含有杂质的新闻标题(一般为