一种从维基中抽取领域术语间上下位关系的方法

摘要

一种从维基中抽取领域术语间上下位关系的方法，按照如下步骤：（1）以领域名称对应的维基页面为起始页面，进行深度为3的广度优先遍历，并利用URL正则表达式过滤到未指向领域术语的超链接，遍历得到的页面与超链接分别存为页面文本集与二元组集合；（2）从二元组集合中获得双向链接特征、边介数特征、聚集系数特征；从文本集中获得的锚文本位置特征、锚文本上下文特征，并构建五维特征向量；（3）采用Random Forest分类器将二元组集合中的超链接按照上下位关系与非上下位关系进行二值分类。本发明能综合运用文本特征与超链接拓扑特征，实现从维基中自动抽取上下位关系。

说明书

技术领域

本发明涉及一种信息抽取方法，特别涉及一种从维基中抽取领域术语间上下位关系的方法。 

背景技术

上下位关系（Hyponymy relation）是领域术语之间最基本的语义关系，主要描述领域术语间的从属关系，例如“数据挖掘”领域的两个术语K-means algorithm、Cluster analysis之间就存在上下位关系。上下位关系是构建分类体系的基础，在海量数字资源，特别是与领域相关的数字资源（如专业文献、教科书等）的组织管理、分类、检索中具有基础性作用。然而，上下位关系通常隐含在领域相关的文本中，人工标注上下位关系不仅费时费力，而且要求标注者具备针对领域较深厚的专业知识。为此，需要一种自动化的方法来实现领域术语之间上下位关系的抽取。 

专利号为ZL201110312280.6，名称为：一种面向文本的领域术语与术语关系抽取方法，在该专利中，发明人提出一种面向文本的领域术语与术语关系抽取方法。该专利主要依据文本特征，通过条件随机场（Conditional Random Fields，CRF）模型进行多层次标记序列标注，得到待识别文本中术语间的关系，其中包括上下位关系，该发明中将其简写为Hypo。仅依据句子结构特征、术语词频、词性、词性一系列文本特征，使得抽取的准确率不高；其次在术语抽取中涉及分词、词性标注操作，这些文本预处理的结果无法保证完全正确，这也限制了后续的上下位关系抽取的性能。 

发明内容

为了克服上述现有技术的缺陷，本发明的目的在于提供一种从维基中抽取领域术语间上下位关系的方法，该方法从维基中特定领域的页面与超链接中提取文本特征与拓扑特征，利用Random Forest分类器从超链接中自动抽取出上下位关系；以实证分析发现的维基页面文本特征与超链接拓扑特征为指导，采用有监督的分类学习算法，实现领域术语上下位关系自动抽取；与目前单纯基于文本特征的方法相比，有效地提高了抽取的准确率与召回率。 

为达到以上目的，本发明采取如下技术方案予以实现。 

一种从维基中抽取领域术语间上下位关系的方法，包括如下步骤： 

步骤一：领域术语的页面文本与超链接关系获取 

（1）以领域名称对应的维基页面为起始页面，进行深度为3的广度优先遍历； 

（2）将遍历到的页面存为一个文本集：对于每个页面文本，用该文本对应的URL去掉http://en.wikipedia.org/wiki/后剩余的字符串作为文件名，该文件名也作为领域术语； 

（3）将遍历到的超链接关系存为一个二元组集合E：二元组形式为(term_i，term_j),term_i与term_j为超链接所连接的页面文本对应的文件名； 

（4）利用一组URL正则表达式过滤到未指向领域术语的超链接，即不遍历能匹配下列正则表达式的URL： 

a)^List_of_w+$ 

b)^w+(ist|ists)$ 

c)^[1-9]+_w+$ 

d)^w+(organisation|government|company)w+$ 

e)^w+(man|men)$ 

步骤二：特征选择与构建 

选择能够从超链接关系中识别出上下位关系的特征，并构建E中每个超链接(term_i，term_j)的特征向量；这里上下位关系是指子类与类（kind-of），实例与类（is-a）关系； 

所述的识别出上下位关系的特征包括五个特征：从二元组集合中获得的双向链接特征、边介数(edge-betweenness)特征、聚集系数（Clustering coefficient）特征；从文本集中获得的锚文本（anchor text）位置特征、锚文本上下文（Context）特征；对五个特征进行量化，并构建五维特征向量； 

步骤三：上下位关系抽取 

利用所构建的五维特征向量，结合每个特征向量对应超链接的类标签（上下位关系与非上下位关系），形成一个训练数据集，采用Random Forest分类器将二元组集合中的超链接按照上下位关系与非上下位关系进行二值分类，从而实现上下位关系的抽取。 

步骤二所述的五个特征及特征向量的构建具体如下： 

利用从二元组形式的超链接集合E，建立以领域术语为节点，超链接为边的有向图G_W(N，E)，其中N为领域术语集，其中的每个领域术语对应一个维基页面文件名； 

特征一：双向链接特征（two_way） 

对于(term_i,term_j)∈E,若(term_j，term_i)∈E，则two_way_ij＝1；否则two_way_ij＝0； 

特征二：边介数特征（edge_betw） 

对于(term_i，term_j)∈E,edge_betw_ij＝b(i，j)；这里，b(i，j)表示(term_i,term_j)这条边在G_W中的边介数；b(i，j)的计算公式如下： 

$b(i,j)=\underset{\underset{u\ne w}{u,w\in N}}{\Sigma }\frac{{\sigma }_{u,w}(i,j)}{{\sigma }_{u,w}}---\left(1\right)$

式（1）中，σ_u，w是节点u，w在G_W中最短路径的条数；σ_u，w(i，j)是节点u，w在G_W中通过边(term_i，term_j)的最短路径的条数； 

特征三：聚集系数特征（clustering） 

对于(term_i,term_j)∈E,设定${\mathrm{clustering}}_{\mathrm{ij}}=\frac{c\left(j\right)}{c\left(i\right)+1}---\left(2\right)$

式（2）中，c(i)、c(j)分别是节点term_i、term_j在G_W中的聚集系数。节点u聚集系数计算公式为：$c\left(u\right)=\frac{\mathrm{numberoftrianglesconnectedtonodeu}}{\mathrm{numberoftriplescenteredonnodeu}},$表示包含节点u的三角形的个数除以以u为中心节点的连通三元组的个数； 

通过分析页面文本，获得两个特征： 

特征四：锚文本位置特征（anchor_loc） 

若two_way_ij＝0，则anchor_loc_ij＝0； 

若two_way_ij＝1，则 

$\mathrm{anchor}\_{\mathrm{loc}}_{\mathrm{ij}}=\frac{\mathrm{loc}({\mathrm{term}}_i,{\mathrm{term}}_j)}{\mathrm{loc}({\mathrm{term}}_j,{\mathrm{term}}_i)+1}---\left(3\right)$

式（3）中，loc(x，y)表示超链接(x，y)在页面x中的位置，即从网页起始处的字符到超链接(x，y)锚文本起始处之间的字符数量； 

特征五：锚文本上下文特征（anchor_cont） 

从超链接(term_i，term_j)所在的页面文本中提取(term_i，term_j)的锚文本及其前后各32个单词，组成一个文本片段； 

1)若该文本片段能够匹配下表中的某个正则表达式，假设为第k个，则anchor_cont_ij＝w_k； 

2)若该文本片段能够匹配下表中的多个正则表达式，设为第k₁，k₂，...，k_m（m＞1）个正则表达式，则$\mathrm{anchor}\_{\mathrm{cont}}_{\mathrm{ij}}=\max (w_{k_1},w_{k_2},...,w_{k_m});$； 

3)若该文本片段不能匹配下表中的正则表达式，则anchor_cont_ij＝0； 

基于上述五个特征，对于每个(term，term_j)∈E，构建五维特征向量： 

(two_way_ij，edge_betw_ij，clustering_ij，anchor_loc_ij，anchor_con_ij)。 

本发明的优点是： 

1、本发明以维基百科为数据源，利用实证研究发现的一组特性，将锚文本的文本特征与超链接的拓扑特征相结合，采用有监督的分类学习算法，实现领域术语上下位关系自动抽取；与目前单纯基于文本特征的方法相比，有效地提高了抽取的准确率。 

2、本发明以维基百科为数据源，以爬取到的特定领域页面的标题为术语，由于这些术语由维基百科上不同领域的专家设定，质量与完整性较高，能够保障上下位关系抽取的召回率。 

附图说明

附图是从维基中抽取领域术语间上下位关系的过程。 

具体实施方式

以下结合附图对本发明的具体技术方案作进一步的详细描述。 

本发明中，领域术语是指在表达一个学科领域内特定概念或关系的词或短语。例如， 在Data mining领域中，典型的领域术语包括Cluster analysis、k-means algorithm、Classification以及Support vector machines等。上下位关系是领域术语的语义关系，表示术语间kind-of（子类与类）与is-a（实例与类）两类从属关系，例如，k-means algorithm与Cluster analysis之间以及Support vector machines与Classification之间就存在上下位关系。 

所发明的从维基中抽取领域术语间上下位关系的方法包括如附图所示的3个步骤，其具体流程为： 

步骤一：领域术语的页面文本与超链接关系获取 

1）以领域名称对应的维基页面为起始页面，进行深度为3的广度优先遍历，例如，要获取Data mining领域中的候选领域术语与超链接关系，则从位置http://en.wikipedia.org/wiki/Data_mining开始遍历。进行深度为3的遍历的依据是：我们人工标注的Data mining、Data structure、Euclidean geometry三个领域的领域术语，95%以上都包含在遍历到的页面文本对应的领域术语中；部分遍历到的页面文本并不能对应领域术语，但对后续的上下位关系抽取性能影响不大。 

2）将遍历到的页面存为一个文本集：对于每个页面文本，用该文本对应的URL去掉http://en.wikipedia.org/wiki/后剩余的字符串作为文件名，如http://en.wikipedia.org/wiki/Data_mining对应文本的文件名为Data_mining；该文件名也作为领域术语。 

3）将遍历到的超链接关系存为一个二元组集合E：二元组形式为（term_i,term_j),term_i与term_j为超链接所连接的页面文本对应的文件名，例如，(Data_mining，Cluster_analysis)表示http://en.wikipedia.org/wiki/Data_mining上指向http://en.wikipedia.org/wiki/Cluster_analysis的超链接。 

4）遍历中存在部分未指向领域术语的超链接，如关于外部联接、组织机构、人物等，为此，利用一组URL正则表达式过滤到这些超链接，即不遍历能匹配下列正则表达式的URL： 

a)^List_of_w+$ 

b)^w+(ist|ists)$ 

c)^[1-9]+_w+$ 

d)^w+(organisation|government|company)w+$ 

e)^w+(man|men)$ 

步骤二：特征选择与构建： 

对三个领域（Data mining、Data structure、Euclidean geometry）的数据集中的超链接进行人工标注，并对标注数据集进行分析，发现了与上下位关系抽取相关的五个特征，包括：从二元组集合中获得的双向链接特征、边介数(edge-betweenness)特征、聚集系数（Clustering coefficient）特征；从文本集中获得的锚文本（anchor text）位置特征、锚文本上下文（Context）特征。 

利用从二元组形式的超链接集合E，建立以领域术语为节点，超链接为边的有向图G_W(N，E)，其中N为领域术语集，其中的每个领域术语对应一个维基页面文件名。 

特征一：双向链接特征（two_way） 

对于三个数据集的实证分析表明，对于单向超链接，仅有14%～16%的超链接是上下位关系；而对于双向超链接，即两个页面互相有链接指向对方，则约有31%～42%的超链接是上下位关系；这表明如果是双向超链接，则更可能是上下位关系。 

为此，对于(term_i，term_j)∈E，若(term_j，term_i)∈E，则two_way_ij＝1；否则two_way_ij＝0。 

特征二：边介数特征（edge_betw） 

对于三个数据集的实证分析表明，边（超链接）的介数与该边是上下位关系的可能性具有正相关性，即介数越大，越可能是上下位关系。 

为此，对于(term_i，term_j)∈E,edge_betw_ij＝b(i，j)；这里，b(i，j)表示(term_i，term_j)这条边在G_W中的边介数；b(i，j)的计算公式如下： 

$b(i,j)=\underset{\underset{u\ne w}{u,w\in N}}{\Sigma }\frac{{\sigma }_{u,w}(i,j)}{{\sigma }_{u,w}}---\left(1\right)$

式（1）中，σ_u，w是节点u，w在G_W中最短路径的条数；σ_u，w(i，j)是节点u，w在G_W中通过边(term_i，term_j)的最短路径的条数。 

对于b(i，j)的计算，利用Ulrik Brandes在文献《On Variants of Shortest-Path Betweenness Centrality and their Generic Computation》中提出的算法。 

特征三：聚集系数特征（clustering） 

对于三个数据集的实证分析表明，存在上下位的领域术语在E中聚集系数较大，且上位词的聚集系数通常比下位词的聚集系数大。如Cluster analysis对应节点在E中的聚集系数比k-means algorithm的大。 

为此，对于(term_i，term_j)∈E,设定${\mathrm{clustering}}_{\mathrm{ij}}=\frac{c\left(j\right)}{c\left(i\right)+1}---\left(2\right)$

式（2）中，c(i)、c(j)分别是节点term_i、term_j在G_W中的聚集系数。节点u聚集系数的计算公式为：$c\left(u\right)=\frac{\mathrm{numberoftrianglesconnectedtonodeu}}{\mathrm{numberoftriplescenteredonnodeu}},$表示包含节点u的三角形的个数除以以u为中心节点的连通三元组的个数。 

通过分析页面文本，获得两个特征： 

特征四：锚文本位置特征（anchor_loc） 

对于三个数据集的实证分析表明，对于双向超链接，两个锚文本在页面中出现的位置具有较大的差异，具体来说，上位词的锚文本往往出现距离页面起始处字符间隔较远的位置，下位词的锚文本往往出现距离页面起始处字符间隔较近的位置。以Cluster_analysis与k-means_algorithm两个页面之间的双向超链接为例，超链接(k-means_algorithm，Cluster_analysis)出现在所在页面的首句，而超链接(Cluster_analysis，k-means_algorithm)出现在较后的位置。 

为此，锚文本位置特征计算如下： 

若two_way_ij＝0，则anchor_loc_ij＝0； 

若two_way_ij＝1，则 

$\mathrm{anchor}\_{\mathrm{loc}}_{\mathrm{ij}}=\frac{\mathrm{loc}({\mathrm{term}}_i,{\mathrm{term}}_j)}{\mathrm{loc}({\mathrm{term}}_j,{\mathrm{term}}_i)+1}---\left(3\right)$

式（3）中，loc(x，y)表示超链接(x，y)对应锚文本在页面x中的位置，即从网页起始处的字符到超链接(x，y)锚文本起始处之间的字符数量。 

特征五：锚文本上下文特征（anchor_cont） 

从超链接(term_i，term_j)所在的页面文本中提取(term_i，eerm_j)的锚文本及其前后各32个单词，组成一个文本片段； 

1)若该文本片段能够匹配下表中的某个正则表达式，假设为第k个，则anchor_cont_ij＝w_k； 

2)若该文本片段能够匹配下表中的多个正则表达式，设为第k₁，k₂，...，k_m（m＞1）个正则表达式，则$\mathrm{anchor}\_{\mathrm{cont}}_{\mathrm{ij}}=\max (w_{k_1},w_{k_2},...,w_{k_m});$； 

3)若该文本片段不能匹配下表中的正则表达式，则anchor_cont_ij＝0。 

上表中的权重w_k是通过对三个领域的数据集统计分析得到的，是指当文本片段匹配到正则表达式后，对应超链接是上下位关系的比例。 

基于上述五个特征，对于每个(term_i，term_j)∈E，构建五维特征向量： 

(two_way_ij，edge_betw_ij，clustering_ij，anchor_loc_ij，anchor_con_ij)。 

步骤三：上下位关系抽取： 

利用所构建的五维特征向量，结合每个特征向量对应超链接的类标签（上下位关系与非上下位关系），形成一个训练数据集。采用Random Forest分类器训练出一个分类模型，能够从二元组集合中的超链接按照上下位关系与非上下位关系进行二值分类，从而实现上下位关系的抽取。