隐马尔科夫模型主要解决三个问题^[4]。

(1) 估值问题: 已知观测序列$O=\{{{o}_{1}},{{o}_{2}},\cdot \cdot \cdot ,{{o}_{T}}\}$, 给定隐马尔科夫模型$\lambda =(A,B,\pi )$, 计算给定模型$\text{ }\!\!\lambda\!\!\text{ }$的前提下, 观测序列$O$出现的概率,解决该问题的算法一般为基于动态规划算法的前向-后向算法;

(2) 识别问题: 已知观测序列$O=\{{{o}_{1}},{{o}_{2}},\cdot \cdot \cdot ,{{o}_{T}}\}$, 给定隐马尔科夫模型$\lambda =(A,B,\pi )$, 求给定观测序列条件概率$P(I|O,\lambda )$最大的状态序列I, 本文使用的算法是维特比(Viterbi)算法;

(3) 学习问题: 已知观测序列$O=\{{{o}_{1}},{{o}_{2}},\cdot \cdot \cdot ,{{o}_{T}}\}$, 估计模型的参数$\lambda =(A,B,\pi )$, 使得在该模型下出现该观测序列概率$P(O|\lambda )$最大, 本文使用的学习算法为监督学习且计算速度较快的极大似然估计法。

本文在网页信息抽取的应用中解决的问题为学习问题和识别问题。

本文研究的基于隐马尔科夫模型的网页信息抽取模型, 具有建模速度快、效率较高、准确率较高等优势。然而, 该模型在网页信息抽取中的准确率与效率还有待进一步提高。隐马尔科夫模型在网页信息抽取中存在三个问题。

(1) 映射问题: 在隐马尔科夫模型中, 词汇集为训练数据中所有观测的集合, 在模型建立后, 将待抽取网页文档中的每一个观测映射为词汇集中的一个词汇, 然后调用维特比算法识别出最佳状态序列。本文在网页新闻关键信息抽取中, 将待抽取项DOM树节点路径映射为词汇, 而在实际应用中, 由于网页上信息的多变性与复杂性, 可能会由于词汇集中不存在该观测而出现无法直接映射的情况, 从而无法对信息进行准确识别。

(2) 数据稀疏问题: 在网页新闻信息抽取中, 由于训练数据量或待抽取项在网页中的分布情况等原因, 训练好的隐马尔科夫模型的参数$A,B,\pi$的概率分布中可能会有概率为0的情况发生, 如观测概率分布B中某一个概率${{b}_{j}}(k)$表示状态为j且观测值为k的概率, 该值可能由于未观测到i到o_t的输出而为0, 那么维特比算法使用连乘计算概率时会导致整个路径的概率为0。这显然是不严谨的, 不能因为一个事件还没有观测到就判断该事件的概率为0^[13]。

(3) 减少计算量: 本文的隐马尔科夫模型学习算法使用最大似然估计法已极大地减少了计算量, 但在识别阶段可进一步减少计算量, 提高网页信息提取效率。

在本文中, 每一状态所对应的观测都是唯一确定的DOM树节点路径, 网页中包含不同状态信息的节点在DOM树中的公共路径很少, 而包含同一状态信息的节点在DOM树中的公共路径很多。针对映射观测为词汇的问题, 使用计算DOM树节点路径相似度^[14]的方法, 给定一个观测, 令其在词汇集中路径相似度最大的词汇作为它的映射, 通过该方法, 对于在词汇集中存在的观测, 可找到其对应词汇; 对于词汇集中不存在的观测, 找到与其DOM树节点路径最为接近的词汇作为观测的映射。计算DOM树节点路径相似度的方法如下。

记任一DOM树节点路径为$N=\{{{N}_{a}},{{N}_{b}},{{N}_{c}},\cdot \cdot \cdot \}$, 记深度depth相同的节点$A,B$的相似度如公式(1)所示。

$sim\text{(}{{T}_{A}},{{T}_{B}}\text{)}=\left\{ \begin{align} & \frac{1}{{{2}^{depth}}}\ \ {{T}_{A}}={{T}_{B}} \\ & 0\ \ \ \ \ \ \ \ \ {{T}_{A}}\ne {{T}_{B}} \\ \end{align} \right.$ (1)

据此, 给出计算任意两个节点的DOM树节点路径相似度方法如公式(2)和公式(3)所示。

$sim\text{(}{{N}_{A}},{{N}_{B}}\text{)}=\sum\nolimits_{depth=1}^{dept{{h}_{A}}}{sim\text{(}{{T}_{A}},{{T}_{B}}\text{)}}\ \ dept{{h}_{A}}\le dept{{h}_{B}}$(2)

$sim\text{(}{{N}_{A}},{{N}_{B}}\text{)}=\sum\nolimits_{depth=1}^{dept{{h}_{B}}}{sim\text{(}{{T}_{A}},{{T}_{B}}\text{)}}\ \ dept{{h}_{A}}>dept{{h}_{B}}$(3)

该方法根据等比数列求和的原理计算DOM树节点路径相似度, 例如, 对两个节点深度为5且每层节点都相等的DOM树节点路径, 相似度为$\frac{1}{{{2}^{1}}}+\frac{1}{{{2}^{2}}}+$ $\frac{1}{{{2}^{3}}}+\frac{1}{{{2}^{4}}}+\frac{1}{{{2}^{5}}}=\frac{31}{32}\approx 0.9688$。据此计算方法, 当两个DOM树节点路径完全相同且深度depth为正无穷时, 它们的相似度无限接近于1。因此, 使用该DOM节点相似度计算的方法, 不管词汇集中是否有当前观测, 都可以准确地映射观测为词汇集中词汇, 从而提升网页信息抽取的准确度。

本文使用拉普拉斯平滑^[15](Laplace Smoothing)解决模型参数中零概率的问题, 拉普拉斯平滑的思想是用加1的方法估计没有出现过的观测的次数, 当训练数据较大时, 由每个分量x的计数加1引起的概率分布变化是可以忽略的, 但是它可以有效地避免零概率问题。因此拉普拉斯平滑的方法是分子加1, 分母加观测值总数M, 如公式(4)所示。

${{b}_{j}}(k)=\frac{{{B}_{jk}}+1}{\sum\nolimits_{k=1}^{M}{{{B}_{jk}}+M}}$ (4)

对未观测到值的概率处理如公式(5)所示。

${{b}_{j}}(k)=\frac{1}{\sum\nolimits_{k=1}^{M}{{{B}_{jk}}+M}}$ (5)

拉普拉斯平滑对未观测到值的概率进行相同的处理, 不区分概率分布各部分中未观测值情况出现的多少, 而实际上各部分中未观测值出现的概率数量不等, 因此对拉普拉斯平滑做出改进^[14]如公式(6)所示。

${{b}_{j}}(k)={{b}_{j}}(k)-\delta$ (6)

其中, $\delta$表示未观测到值时的概率, 计算方法如公式(7)所示。

$\delta =\frac{1-\sum\nolimits_{k=1}^{M}{{{B}_{jk}}}}{\sum\nolimits_{k=1}^{M}{{{B}_{jk}}}+M}$ (7)

对初始状态概率分布$\pi $, 状态转移概率分布A进行相同的平滑处理。

针对减少计算量问题, 可以通过在隐马尔科夫模型中结合规则来解决。在一个信息抽取系统中, 除了存在不确定状态和其不确定释放的观测以外, 还有确定状态释放观察值的情况。确定状态在隐马尔科夫模型中作为已知状态, 其观测释放概率设为1。该方法通过匹配模板库, 利用规则的方法, 在使用Viterbi算法确定最佳状态序列之前确定部分状态, 既可以减少Viterbi算法循环次数, 从而减少运行时间, 提高效率, 又可以减少由于数据稀疏等问题带来的对模型参数的负面影响。

对抓取的网页进行初步处理。为减少算法计算量, 提高处理效率, 将网页文档解析为DOM树并将其中的样式、列表、脚本、注释等噪音信息删除, 提取DOM树叶节点的DOM树节点路径写入训练数据集。

本文使用Python的BeautifulSoup库进行网页文档的解析与操作, BeautifulSoup将一个网页文档解析为一棵DOM树且提供了一些简单而强大的方法来浏览、搜索、解析DOM树。利用BeautifulSoup删除噪音信息的具体步骤如表1所示。

经过预处理的DOM树式样如图5所示。

遍历DOM树, 对所有的叶节点, 找出它们从根节点到叶节点的路径, 不同深度的标签以“/”分隔, 若叶节点有class属性, 则将class属性加到叶节点标签之后, 否则加入其父节点的class属性, 得到DOM树节点路径, 得到的DOM树节点路径之 间的顺序依然与原网页文档中文本间的布局顺序一致。

将网页预处理后得到的DOM树节点路径写入未标记训练数据集。去重后作为隐马尔科夫模型的词汇集合, 写入词汇数据集。每一状态的部分词汇如表2所示。

在利用模型进行信息抽取之前, 对未标记训练数据进行人工标记, 标记标题为title,日期为date, 来源为source, 正文为text, 不抽取信息为other, 在DOM树节点路径后用“+标记”的方式进行标记, 写入已标记训练数据集。标记方法如表3所示。

逐条取出已标记训练数据集中的数据, 根据“+”后的标记判断取出的训练数据所属状态, 使用隐马尔科夫模型的学习算法极大似然估计法进行概率分布的计算, 使用改进的拉普拉斯平滑方法解决数据稀疏问题, 得到训练好的模型参数$A,B,\pi$。

使用模板库中的规则进行匹配得到确定状态, 将网页预处理后得到的DOM树节点路径作为观测输入,使用最大路径相似度方法将其映射为词汇集中词汇, 使用Viterbi算法将映射后的词汇序列输入, 得到最佳状态序列, 即每一DOM树节点路径所对应信息的最可能状态所组成的序列。

根据模型识别出的DOM树节点路径所对应信息的状态, 找出对应于标题、日期、来源、正文状态的DOM树节点, 使用BeautifulSoup库中的.get_text()方法取出节点中文本信息, 调用数据库管理模块将文本信息写入表中, 至此完成新闻网页中半结构化信息抽取为结构化信息的转换。

从新浪、搜狐、腾讯、网易等16个新闻网站采集新闻网页链接, 每个新闻网站爬取500个网页作为原始实验数据。为保证数据的多样性, 同时保证实验数据的有效性, 从采集的网页中筛选出2 000篇作为训练数据, 500篇作为测试数据, 训练数据和测试数据均从每个网站中平均选取。

实验环境为Windows10系统, CPU为Intel 4核, 内存为8GB, 开发语言使用Python3.6, 开发工具使用PyCharm 2018, 网页文档爬取解析工具包采用“BeautiflulSoup”, 机器学习库使用“hmmlearn”开发。

使用精确率P、召回率R和F值度量新闻正文抽取的实验结果, 计算方法分别如公式(8)-公式(10)所示。根据F值靠近1的程度判断算法的好坏。

$P=\frac{正确抽取出信息的节点数}{所有抽取的信息节点数}\times 100%$ (8)

$R=\frac{正确抽取出信息的节点数}{所有正确的信息节点数}\times 100%$ (9)

$F=\frac{2\times P\times R}{P+R}\times 100\text{ }\!\!%\!\!\text{ }$ (10)

使用经典隐马尔科夫模型和本文改进的隐马尔科夫模型分别对相同数据进行训练、测试, 对比抽取效果。实验结果如表4和表5所示。

两种方法实验结果对比如表6所示。

对比表4-表6可以看出, 经典隐马尔科夫模型对新闻关键信息抽取的效果较好, 且经过改进的算法进一步提高了抽取准确度。这是因为新闻网页中关键信息之间本身就有一种时序性的关系, 符合隐马尔科夫算法的思想, 且经过改进的隐马尔科夫模型中解决了平滑问题和词汇映射问题, 很大程度上避免了零概率问题对训练和抽取效果的负面影响。

纵向对比, 发现标题的抽取准确度最高, 这是因为标题普遍在标签“<h1>”和“</h1>”中, 且DOM树节点路径与其他待抽取项差异较大, 特征最为明显, 容易被模型学习到抽取规则。同理发现正文的抽取准确率也相对较高, 这是因为正文节点在DOM树中深度一般相同, 且分布较为集中, 正文节点之间的状态转移概率较高, 因此容易被模型学习到并正确抽取出来。

文献[17]也是一种基于隐马尔科夫模型的网页新闻抽取方法, 对新闻标题和正文进行抽取研究, 对网页文档中“<Title>”与“</Title>”标签所直接包含的字符串进行一定的匹配作为标题, 以标题位置作为正文的开始位置, 使用隐马尔科夫模型, 以文本内容特征作为模型的观察值, 查找正文结束位置确定正文。其抽取标题准确率为94.41%, 抽取正文准确率为92.63%。本文方法对标题和正文抽取的准确率分别为98.68%和98.05%, 由于充分考虑了网页信息抽取相较于传统文本信息抽取在布局结构上的特性, 考虑待抽取项的次序关系, 因而网页信息抽取效果更佳。

文献[18]提出的CEPR算法基于标签路径特征融合对网页新闻正文内容进行抽取, 抽取的准确率与本文基本相当, 但对网页新闻中精准的细粒度内容(如标题、日期、来源等信息)抽取不理想。而本文利用隐马尔科夫模型的时序性特征并结合网页文档的特点, 较好地实现了细粒度内容的抽取。