一种面向文本的领域分类关系自动学习方法

摘要

本发明公开了一种面向文本的领域分类关系自动学习方法，采用MEDLINE作为语料库，进行术语抽取与概念抽取，将抽取到的概念进行基于句法相似度和语义相似度的五个维度相似度的计算，然后各个维度的相似度进行加权，得出最终相似度矩阵，以此为依据进行层次聚类得出初始的树状图，再对树状图进行相应的剪枝和聚簇标记，最终得出体现概念之间的分类关系树状图；本发明不需要大量的手工标记，节省了人力与时间开销；将抽取到的术语与权威知识库UMLS超级叙词表进行映射，得出准确的领域概念；采用层次聚类的分布式方法，结合领域背景知识，提供五个维度相似度的计算；提出基于极值距离估计的无监督的层次聚类动态剪枝方法，能够更好地得出领域相关的分类关系。

说明书

技术领域

本发明属于本体学习领域，尤其涉及一种面向文本的领域分类关系自动学习方法。

背景技术

虽然生物医学研究领域已经广泛承认了领域本体的实用性，但是对于领域本体的有效使用仍然存在很多阻碍。领域本体一个非常重要的要求就是，他们对于领域概念和概念之间的关系必须取得高覆盖率。然而，这些本体的构建通常是一个手工的，耗时的过程，并且容易产生各种各样的错误。有限的资源导致了概念和关系的丢失，同时加大了知识变化引起的更新本体的难度。此外，构建本体需要领域专家的参与，即使同领域的专家对知识模型的认知也未必相同，所以难以保证构建本体的一致性。因此，许多研究人员致力于采用自然语言处理、计算机语言学和人工智能等领域的方法，实现语义知识的自动和半自动提取，即本体学习技术。

本体学习包括术语抽取、概念抽取、分类关系抽取、非分类关系抽取及公理抽取等。分类关系作为本体构建的重要组成部分，是国内外研究的重点，主要体现的是领域概念间的上下位关系。目前，分类关系的学习主要有两种方法：基于规则的方法和分布式方法。基于规则的方法使用预定义的规则或者启发式模式来提取术语和关系，这些方法通常是基于Hearst提出的词汇-句法模式。分布式方法则将分类关系学习作为一种聚类或者分类任务，并且着重强调分布式相似性，它的优势在于可以发现文本中没有明确出现的关系。

基于规则的方法依赖于能够提供高准确度的静态语言模式(规则)，不但需要广泛的领域专业知识，而且需要大量的手工标记，很难推广到其他领域。分布式方法需要极少量的先验知识，提供了更好的可扩展性，但是关键点在于有效的相似度计算准则。

发明内容

本发明的目的在于针对现有技术的不足，提供一种面向文本的领域分类关系自动学习方法，采用MEDLINE作为语料库，进行术语抽取与概念抽取，将抽取到的概念进行基于句法相似度和语义相似度的五个维度相似度的计算，然后各个维度的相似度进行加权，得出最终的相似度矩阵，以此为依据进行层次聚类得出初始的树状图，再对树状图进行相应的剪枝和聚簇标记，最终得出体现概念之间的分类关系树状图。

本发明的目的是通过以下技术特征来实现的：一种面向文本的领域分类关系自动学习方法，包括以下步骤：

(1)将从MEDLINE上抽取到的xml格式的论文中的摘要部分存储为txt格式，作为语料库；

(2)对步骤(1)得到的语料库采用自然语言处理工具MMTx进行初步术语抽取；

(3)将步骤(2)抽取到的术语与UMLS超级叙词表映射，不同的术语可能会映射到相同的概念；将所有的术语进行概念映射，最终形成领域概念集合；

(4)综合句法相似度和语义相似度进行概念间相似度的计算，将相似度分为5个维度，最终的概念C_i和C_j之间的相似度Sim(C_i，C_j)是各维度相似度归一化加权的结果，对于n个概念最终得到一个n×n的相似度矩阵；Sim(C_i，C_j)的计算公式如下：

其中，w_l是第l个维度相似度的权值，前三个维度的相似度是基于句法计算的，后两个维度的相似度是基于语义计算的，具体计算方法如下：

(4.1)sim₁(C_i，C_j)的计算：计算概念C_i和C_j的概念名称C_name的杰卡德相似系数；每个C_name由一系列字符串T构成，那么，概念C_i和C_j的相似度表示为

T_i∩T_j＝{t_i∈T_i，t_j∈T_j|LD(|t_i|，|t_j|)＜α}

其中，LD(|t_i|，|t_j|)为t_i和t_j之间的莱文斯坦距离，T_i∩T_j的评估标准是构成它们的字符串之间的莱文斯坦距离小于预定义值α；

(4.2)sim₂(C_i，C_j)的计算：计算概念C_i的概念名称C_name和C_j所代表的术语集β之间的杰卡德相似系数；

(4.3)sim₃(C_i，C_j)的计算：计算概念C_i所代表的术语集β和C_j的概念名称C_name之间的杰卡德相似系数；

(4.4)sim₄(C_i，C_j)的计算：计算两个概念C_i和C_j在临床医学权威知识库SNOMED>i，首先，查询其在SNOMED>i在SNOMED>i为中心的由其所有父节点形成的图，采用图的宽度优先搜索算法对两个概念各自的父节点图进行处理，得出二者的公共父节点，其中两个概念的最近距离即为最终距离；对最短距离进行归一化处理即可得到本维度的相似度；

(4.5)sim₅(C_i，C_j)的计算：计算两个概念在DBpedia知识库中的相似度；概念C_i和C_j的相似度是各自从DBpedia中抽取到的类别数组的杰卡德相似系数；

(5)对相似度矩阵进行层次聚类得出初始的树状图：基于以上5个维度相似度的计算，采用自底向上的凝聚型聚类算法AHC对分类关系进行学习，簇间距离选用最大距离作为标准；

(6)对树状图进行相应的剪枝和聚簇标记，得出概念之间的分类关系；具体为：首先创建聚簇标记向量λ＝{λ₁，λ₂，…，λ_m}，m为所有聚簇标记的总数，然后，对层次聚类产生的树状图进行剪枝操作，若在剪枝的过程中有新的聚簇产生，对新的聚簇进行标记并更新树状图，重复此操作，直到不再有新的聚簇产生，即得到最终的概念之间的分类关系。

进一步地，所述步骤(4.5)中，DBpedia可以从维基百科中获取大量的结构化信息，根据相关接口查找出概念在维基百科中的统一资源标识符URI以及该概念所属类型，每个URI都归属于一系列的类别，这些类别反映了概念在维基百科这个巨大的开放信息网的所有相关信息，概念C_i和C_j的相似度是各自从DBpedia中抽取到的类别数组的杰卡德相似系数；

进一步地，所述步骤(5)中，分类关系体现的就是概念之间的上下位关系，可图形化为多叉树结构，这种结构与层次聚类的任务目标是非常契合的，因此选用层次聚类方法；簇间距离选用最大距离(Complete Linkage)作为标准，保证聚类过程中考虑到每个概念的影响，公式如下：

其中，d_max(C_i,C_j)为概念C_i和C_j之间的最大距离，dist(x,z)为x和z之间的距离。

进一步地，所述步骤(6)中，采用无监督动态剪枝方法，在无监督的情况下动态地估计出适应每一个单独的树状图的切割高度；为了找到每次迭代过程中树状图的剪枝高度，构造一个二元函数y＝f(x)，其中，x∈[0,1]反映的是修剪树的高度，y值反映的是每个x产生的聚类簇的个数；x的最优值既不应该产生最大数量的聚类簇，也不应该产生最小数量的聚类簇；x的值越大，产生的聚类簇的数量越小，当x低于一个特定值时，聚类簇的数量不再变化，这个拐点记为x_F1；此外，为了避免聚簇数量极低的情况，寻找另一端的限定值x_m，最终，由x_F1和x_m共同求出剪枝高度x_f。

进一步地，采用极值距离估计EDE的方法计算拐点x_F1的近似值，拐点x_F1的定义为

F(x)＝f(x)-g(x)

其中，x的定义域为[a,b]，g(x)是点(a,f(a))到点(b,f(b))的弦，δ₁和δ₂是足够小的正数；那么，x_F1表示f(x)到g(x)距离最远时所对应的x值，即：

其中，f’(x)表示f(x)的导数。

进一步地，限定值x_m是x<1的情况下产生最小数量聚类簇所对应的剪枝高度，将x_m设为0.99。

进一步地，根据x_F1和x_m计算最终的修剪高度x_f：由f(x_F1)和f(x_m)得出理想的聚簇数量N＝(f(x_F1)-f(x_m))/2，然后在f(x)中寻找最接近N的值，该值所对应的x即为最佳剪枝高度x_f。

进一步地，概念与分类关系抽取完成后，形成由概念与关系构成的本体知识，选用protégé作为该轻量级本体的一个可视化展示平台。

本发明的有益效果是：

1)与基于规则的方法相比，不需要大量的手工标记，节省了人力与时间开销；

2)将抽取到的术语与权威知识库UMLS超级叙词表进行映射，得出准确的领域概念；

3)采用层次聚类的分布式方法，结合领域背景知识，提供了基于句法相似度和语义相似度的五个维度相似度的计算，优于传统的欧氏距离、夹角余弦距离等；

4)提出了一种基于极值距离估计的无监督的层次聚类动态剪枝方法，能够更好地得出领域相关的分类关系。

附图说明

图1为面向文本的领域分类关系自动学习方法流程框架图；

图2为计算在SNOMED CT中两个概念Ci和Cj到公共父节点的最短距离；

图3为对层次聚类产生的树状图进行剪枝和聚簇标记的流程图；

图4为计算每次迭代过程中树状图的最佳剪枝高度示意图。

具体实施方式

下面结合附图和具体实施例对本发明作进一步详细说明。

首先给出相关定义及描述：

领域概念：是从特定领域内的自然语言语句中抽取出来的，用一个三元组来表示为C_i＝(C_id,C_name,β)，其中C_id表示概念的唯一标识符，C_name是用于表示概念名的字符串，β表示由从自然语言语句中提取出来的字符串术语的集合，每个术语又被定义为β_i＝(β_name,s_i)，其中，β_name表示抽取到的术语字符串，s_i表示术语所在语句。

例1：“Exclude patients with a current diagnosis of hepatic or renaldisease.Exclude patients with severe liver disorder or kidney disease.”

该语句识别出的概念为：

(C₁,“liver>1,β₂})，

其中β₁＝(“hepatic>1)，β₂＝(“liver>2)；

(C₂,“kidney>3,β₄})，

其中β₃＝(“renal>1)，β₄＝(“kidney>2)

以下通过实施例对本发明方法的实现过程进行详细描述，如图1所示，本发明面向文本的领域分类关系自动学习方法包括以下步骤：

(1)将从MEDLINE上抽取到的xml格式的论文中的摘要部分存储为txt格式，作为语料库；本实施例中，选取MEDLINE的有关阿尔茨海默病的最新论文作为数据源；

(2)对步骤(1)得到的语料库采用自然语言处理工具MMTx(MetaMap Transfer)进行初步术语抽取；

(3)将步骤(2)抽取到的术语与UMLS超级叙词表(Unified Medical LanguageSystem Metathesaurus)映射，那么，不同的术语可能会映射到相同的概念，如例1所示，MMTx抽取到的术语“hepatic disease”和“liver disorder”在UMLS中映射到相同的概念“liver disease”；将所有的术语进行概念映射，最终形成领域概念集合；

(4)综合句法相似度和语义相似度进行概念间相似度的计算，将相似度分为5个维度，最终的概念C_i和C_j之间的相似度Sim(C_i，C_j)是各维度相似度归一化加权的结果，对于n个概念来讲，最终得到的是一个n×n的相似度矩阵；Sim(C_i，C_j)的计算公式如下：

其中，w_l是第l个维度相似度的权值，前三个维度的相似度是基于句法计算的，后两个维度的相似度是基于语义计算的，具体计算方法如下：

(4.1)sim₁(C_i，C_j)的计算：计算概念C_i和C_j的概念名称C_name的杰卡德相似系数(Jaccard>name由一系列字符串T构成，那么，概念C_i和C_j的相似度表示为

T_i∩T_j＝{t_i∈T_i，t_j∈T_j|LD(|t_i|，|t_j|)＜α}

其中，LD(|t_i|，|t_j|)为t_i和t_j之间的莱文斯坦距离，T_i∩T_j的评估标准是构成它们的字符串之间的莱文斯坦距离(Levenshtein>

(4.2)sim₂(C_i，C_j)的计算：计算概念C_i的概念名称C_name和C_j所代表的术语集β之间的杰卡德相似系数(Jaccard>

(4.3)sim₃(C_i，C_j)的计算：计算概念C_i所代表的术语集β和C_j的概念名称C_name之间的杰卡德相似系数(Jaccard>

(4.4)sim₄(C_i，C_j)的计算：计算两个概念C_i和C_j在临床医学权威知识库SNOMED>i，首先，查询其在SNOMED>i在SNOMEDCT本体库中的所有父节点，得到以概念C_i为中心的由其所有父节点形成的图，对于两个概念C_i和C_j来讲，他们存在至少一个公共父节点，采用图的宽度优先搜索(BFS)算法对两个概念各自的父节点图进行处理，得出二者的公共父节点，其中两个概念的最近距离即为最终距离。如图2所示，该图由概念C_i和C_j及其父节点构成，P₁ⁱ到P₆ⁱ是概念C_i的父节点，P₁^j到P₇^j是概念C_j的父节点，P₆ⁱ/P₇^j和P₅ⁱ/P₆^j是两个概念的公共父节点，图中“△”标识的路径即为二者到公共父节点的最短距离d_min，对最短距离进行归一化处理即可得到本维度的相似度：

sim₄(C_i，C_j)＝1-d_min/d_max

其中，d_max为所有概念两两之间最短距离的最大值；

(4.5)sim₅(C_i，C_j)的计算：计算两个概念在DBpedia知识库中的相似度；DBpedia可以从维基百科中获取大量的结构化信息，根据相关接口查找出概念在维基百科中的统一资源标识符(Uniform>i和C_j的相似度是各自从DBpedia中抽取到的类别数组的杰卡德相似系数(Jaccard>

(5)对相似度矩阵进行层次聚类得出初始的树状图；

分类关系体现的就是概念之间的上下位关系，可图形化为多叉树结构，这种结构与层次聚类的任务目标是非常契合的，所以，基于以上5个维度相似度的计算，采用自底向上的凝聚型聚类算法(Agglomerative Hierarchical Clustering，AHC)对分类关系进行学习。簇间距离选用最大距离(Complete Linkage)作为标准，保证聚类过程中考虑到每个概念的影响。

其中，d_max(C_i,C_j)为概念C_i和C_j之间的最大距离，dist(x,z)为x和z之间的距离；

(6)对树状图进行相应的剪枝和聚簇标记，得出概念之间的分类关系；

由于概念数据集非常庞大，AHC产生的树状图拥有非常繁杂的分支结构，本发明的目的是找到由详细概念构成的不相交的概念集合分支，从而发现不同概念之间的上下位关系。因此，需要选取合适的方法来识别单个分支，这个识别分支的过程通常被称为剪枝(Tree Cutting，Branch Cutting，or Dendrogram Pruning)。

本发明采用一种无监督的动态剪枝方法，顾名思义，就是在无监督的情况下动态地估计出适应每一个单独的树状图的切割高度，而不是直接设置一个绝对不变的全局阈值。剪枝和聚簇标记的流程图如图3所示，首先创建聚簇标记向量λ＝{λ₁，λ₂，…，λ_m}，m为所有聚簇标记的总数，然后，对层次聚类产生的树状图进行剪枝操作，若有新的聚簇产生，对该聚簇进行标记并更新树状图，重复此操作，直到不再有新的聚簇产生，即得到最终的概念之间的分类关系。

那么，为了找到每次迭代过程中树状图的剪枝高度，本发明构造了一个二元函数y＝f(x)，其中，x∈[0,1]反映的是修剪树的高度，y值反映的是每个x产生的聚类簇的个数；x的最优值既不应该产生最大数量的聚类簇，也不应该产生最小数量的聚类簇；如图4所示，x的值越大，产生的聚类簇的数量越小，当x低于一个特定值时，聚类簇的数量不再变化，这个拐点是我们首先要提取出的一个关键点，记为x_F1。此外，我们需要避免聚簇数量极低的情况，这就需要寻找另一端的限定值x_m，最终，由x_F1和x_m共同求出剪枝高度x_f。

本发明采用极值距离估计(Extremum Distance Estimator，EDE)的方法计算拐点x_F1的近似值，这个方法是希腊雅典大学的Christopoulos,Demetris>

F(x)＝f(x)-g(x)

其中，x的定义域为[a,b]，g(x)是点(a,f(a))到点(b,f(b))的弦,δ₁和δ₂是足够小的正数。那么，x_F1则表示f(x)到g(x)距离最远时所对应的x值。那么，Christopoulos,Demetris>

其中，f’(x)表示f(x)的导数。图4给出拐点x_F1的直观解释。

另外一个限定值x_m是x<1的情况下产生最小数量聚类簇所对应的剪枝高度，为了避免只有一个聚类簇的情况出现，将x_m设为0.99，如图4中点(x_m,f(x_m))所示。最后，根据x_F1和x_m计算最终的修剪高度x_f。由f(x_F1)和f(x_m)得出理想的聚簇数量N＝(f(x_F1)-f(x_m))/2，然后在f(x)中寻找最接近N的值，该值所对应的x即为最佳剪枝高度x_f。

概念与分类关系抽取完成后，形成由概念与关系构成的本体知识，可选用protégé作为该轻量级本体的一个可视化展示平台。

上述实施例用来解释说明本发明，而不是对本发明进行限制，在本发明的精神和权利要求的保护范围内，对本发明作出的任何修改和改变，都落入本发明的保护范围。