基于Web挖掘的领域本体自动学习

ISSN100020054清华大学学报(自然科学版)2005年第45卷第S1期

CN1122223󰃗N.45,No.S1JTsinghuaUniv(Sci&Tech),2005,Vol1󰃗39

172921733

基于Web挖掘的领域本体自动学习

方卫东,　袁　华,　刘卫红

(华南理工大学计算机科学与工程学院,广州510640)

摘　要:为获取领域本体并量化概念关系的可信度,提出了一种基于Web挖掘的学习模型。通过可扩展的模式集和分布语义模型获取本体主干,使用关联规则发现概念间的一般关系,对候选本体进行修剪和合并。模式可信度、概念语义距离与关联特征决定了概念间关系的可信度。通过“文本分析本体获取文本扩充”的迭代过程,优化模型参数和阈值。该模型解决了现有本体学习方法对词典或核心本体的依赖性、以及不能对关系进行可信度量化的问题。实验证明了所提出模型的有效性。

关键词:机器学习;Web挖掘;自然语言处理;本体;分布

语义;主题签名;上下文签名

中图分类号:TP181

文章编号:100020054(2005)S121729205

文献标识码:A

的瓶颈。如何以自动或者半自动的方式获取和演化领域本体是目前在人工智能、文本挖掘、信息搜索等多个领域的重要研究课题。另外,由于本体是未来语

义网(semanticweb)的基础,本体学习对其发展和应用具有重要意义。

目前有代表性的基于文本的本体学习方法[15]

存在两个问题:一是依赖于某些通用词典(如WordNet等)或核心本体(coreontology),侧重于

扩展已有词典中概念之间的关系或者扩充核心本体;二是对于所获取的概念之间的关系缺乏可信度量化。上述特点使得这些方法不适于从特定文本中学习领域本体。原因是:1)通用词典中涉及的概念数量往往非常巨大,概念间的关系非常复杂,以扩展该类词典的方法获取领域本体效率很低;2)在某些语言中适合本体学习的词典可能不存在;3)概念关系可信度没有量化导致在半自动本体获取中人工修改概念关系缺乏数值根据,以及在自动本体获取中本体修剪和合并的不准确性。

针对上述问题,本文提出了一种基于Web挖掘的领域本体自动获取方法,旨在通过挖掘分布于Web上的特定领域文本,发现本体概念和概念之间

Automaticdomainontologylearning

basedonwebmining

FANGWeidong,YUANHua,LIUWeihong

(SchoolofComputerScienceandEngineering,

SouthChinaUniversityofTechnology,Guangzhou510640,China)Abstract:Thispaperproposesaweb2basedlearningmodeltoacquiredomainontologiesandtoquantifytheconfidenceofconceptrelations.Anontologybackbonewascapturedwithanextensiblepatternsetandadistributionalsemanticmodeltofindthegeneralrelationsbetweenconceptsusingassociationrules,aswellastopruneandmergecandidateontologies.Theconfidenceofconceptrelationswasdeterminedbytheconfidenceofpatterns,semanticdistancesandassociationfeaturesofconcepts.Modelparametersandthresholdswereoptimizedwitharecursiveprocedureof“textanalysis2ontologylearning2textenrichment”.Anexperimentprovedeffectivenessofthismodel.Thismodelsolvestheproblemoflexiconorcoreontologydependenciesintraditionalontologylearningmethods.

Keywords:machine

learning;

webmining;

natural

language

的关系,并对所发现的关系进行可信度量化,从而为自动或半自动的本体修剪与合并提供量化依据。

1　方法概述

本体知识可以从文本、字典、知识库、半结构化数据以及关系模式等多种资源中通过学习获取[1]。基于文本的本体学习目的是使用自然语言分析技术

processing;ontology;distributionalsemanticmodel;topicsignatures;contextsignatures

收稿日期:2005205220

基金项目:国家自然科学基金资助项目(90412015);

生物信息学网格(CG20032GA002)

本体正在越来越多的计算机应用中发挥作用,而对领域本体的建立和维护成为制约这些应用发展

作者简介:方卫东(19702),男(汉),山东,博士研究生。

E2mail:fangwd@scut.edu.cn

1730

清华大学学报(自然科学版)2005,45(S1)

抽取特定领域文本中所包含的概念、个体,并发现它们之间的关系。由于文本是Web上最丰富的资源,基于文本的本体学习也因此成为最具挑战性和最有意义的学习方式。

基于文本的本体学习方法大体可以分为两类,即基于自然语言规则的方法[2,3]和基于统计分析的方法[4,5]。前者具有较好的精度,但对于概念间潜在关系的分析依赖复杂的语言处理模型;而后者适合于大规模文本处理,但缺乏必要的语义逻辑基础。

本文所提出的本体学习模型有机的结合了上述两种方法。在本模型中,领域文本首先通过扩展的模式匹配规则进行粗分析以抽取本体主干。然后再根据概念相互共现的规律发现概念间的一般关系。学习过程从一组由人工选定领域文本开始,然后根据已得到的本体按照文[6]所提出的方法对Web进行语义搜索以丰富领域文本。模型中所使用的阈值和参数在学习过程中不断进行迭代优化,以提高准确性和效率(见图1)。

2　本体主干的获取

2.1　本体与本体主干

尽管本体的概念由来已久,但至今尚没有一个为所有人接受的定义。然而在计算机领域中,本体所包含的一些基本要素却被大多数人认可。这些要素包括:概念、概念之间的特化󰃗泛化关系(is-a关系)以及概念之间的其他关系等。在目前比较流行的以描述逻辑为基础定义的本体中还定义了概念之间的约束关系,如概念之间的互斥、互补、最小󰃗大关系约束等。考虑到实现的难度和实际对本体知识的需要,本文采用如下的本体形式定义[7]:

定义1　一个领域D上的本体O是一个四元组:

O=〈C,is-a,R,Ρ〉.

其中:其中C是一个概念集合;is-a是C上的一个偏序关系(即:is-a是一个二元关系,is-a由于本体概念间关系的复杂性,直接确定定义1中的所有元素是非常困难的。本文采取的方法是:

首先确定本体主干,然后再发现本体概念间的其他关系。本体主干包含了特定领域中的所有概念及其之间的is-a关系。以下是本体主干的形式定义:

定义2　一个本体O的主干8是它的一个子集:

8=〈C,is-a,h〉.

其中:C、I、is-a的定义同定义1;h是函数,定义为:C×C→is-a。

图1　模型总体框架

本体主干的获取方法可以通过两种方法实现:基于语言规则的方法和基于统计的方法。本文所采用的方法是:首先采用模式分析的方法找出文本中存在的显式的is-a关系,然后由分布语义模型发现概念之间潜在的is-a关系。2.2　识别显式的is-a关系

为量化所得到的关系的可信度,模式库中的每条匹配规则被赋予一个可信度值。模式可信度、概念间的语义距离和关联特征等决定了关系的可信度。本体修剪和合并根据冲突消解规则和概念间关系的可信度值进行。

本文所提出的方法充分利用了句法模式在表达特定关系上的准确性,同时又避免了使用复杂的自然语言理解模型处理概念间的一般关系。另外,渐增式运行和对参数的迭代优化也使得本模型具有较好的容错性和可扩充性。实验表明,本文所提出的方法可以比较有效地从Web文本中学习领域本体知识,并合理量化本体概念间关系的可信度。

相关研究表明[8],概念之间的is-a关系可以通过简单的模式匹配在文本集中发现,而领域概念则可以通过命名实体识别(namedentityrecognition,NER)获取。例如在以下句子片断中:“某些体育运动,如篮球、排球、足球等,……,”通过NER技术可以识别出以下概念:体育运动、篮球、排球和足球。而在该句子中包含如下模式:

方卫东,等:　基于Web挖掘的领域本体自动学习1731

〈某些〉].N0〈如〉N1[N2,…,〈及󰃜或〉Ni〈等〉该模式表达了以下语义:

forall　Ni,i≥1,is-a(Ni,N0).

实际领域文本中,概念可以通过NER技术发现,而获取概念间is-a关系的关键是建立表达该关系的模式集。显然用人工的方法很难列举出所有表达is-a关系的模式,要使得该方法具有可扩展性,必须有自动的方法对模式集进行扩充。本文采用了文[8]所建议的模式扩展方法,如算法1(H(x)表示

x的泛化概念)。

—宾语签名:以c为宾语的动词集;

—修饰词签名:一个形容词和名词的集合,集合中的元素在名词性短语中修饰c。

以下以主题签名为例说明上述签名的计算方法。概念c的主题签名Stopic,c是一个与c共同出现在文本集中的概念列表以及每个概念ci与c共同出现的权重wi,即

Stopic,c=〈(c1,w1),(c2,w2),…,(cn,wn)〉.(2)　　权重wi表示了概念c与ci的相关程度。wi计算方式可以有很多种,如互信息法,ς2检验法以及其他的标准统计检验方法。在本文实验中采用了ς2检验法[5],计算公式如下(式中freqi,j表示术语i在文档j中的出现次数)。

freqi,j-mi,j,freqi,j>mi,j;

mi,j(3)wi,j=

0,其他.

m

i,j

算法1　模式扩充算法

1)若本体主干中不存在未提取的概念对则退出;

2)从本体主干中抽取概念对〈t1,t2〉,其中t2=H(t1);

3)从文本集中提取包含t1和t2的句子;4)对句子进行分析,提取共同模式;

5)若所提取模式已经存在于模式库中,转步骤6;否则将模式加入模式库;

6)转步骤1。

=

∑freq∑freq

∑freq

i,j

iji,j

ij

i,j

.(4)

为便于本体合并和对学习结果进行定量分析,在实际实验中,每一种模式Pi被赋予一个可信度

Ri。对于任意两个概念c1,c2,如果存在n个模式

　　当计算出领域文本中所包含的某概念的签名后,将之与已经确定is-a关系的概念进行比较。通过实验设定一个阈值,当两个概念间语义距离小于该阈值时则认为它们属于同一概念的特化。两个概念c1,c2之间的语义距离采用如下公式进行计算:

D(c1,c2)=

(Pi,Ri)支持is-a(c1,c2),则c1和c2之间的关系的

可信度定义为这些模式中可信度的最大值,即:

(1)R[is-a(c1,c2)]=max(R1,R2,…,Rn).

Ri的初值由人工指定,并在学习过程中进行迭代

∑S

i

i

(c1,c2)×w.i(5)

修正。

2.3　发现潜在的is-a关系

　　其中:Si(c1,c2)是c1,c2之间的不同签名距离,

即主题签名(i=topic)、主语签名(i=subject)、谓语签名(i=object)和修饰词(i=modifier)签名。wi是不同签名所占的权重,下式进行计算:

Si(c1,c2)=

Si,c1󰃖Si,c2.󰃜Si,c1󰃜×󰃜Si,c2󰃜

∑w

j

i

=1.0。Si(c1,c2)以

基于模式的方法只能识别文本中存在的显式的is-a关系,不能用于发现文本中潜在的关系。而对

(6)

潜在is-a关系的分析不仅可以直接丰富本体主干,而且还可以通过算法1更新模式库中的模式,从而间接地对本体主干进行扩展。

为发现概念间潜在的is-a关系,本文使用了分布语义模型。基本假定是:两个在语义上相近的概念,与它们共同出现的词的规律(主题签名)和它们所处的上下文(上下文签名)也必定相似。概念c的主题签名和上下文签名的含义如下。

󰃛主题签名:与c在同一上下文(比如同一句子)中出现的词的集合。

󰃛上下文签名,包括:

—主语签名:以c为主语的动词集;

′概念c1,c2间潜在is-a关系的可信度定义为

′′)]=R[is-a(c1,c2)]D(c2,c2).(7)[is-a(c1,c2R′

′)的计算分别如式其中,R[is-a(c1,c2)]和D(c2,c2(1)和式(5)所示。

3　概念间的一般关系

如定义1所述,在领域本体中除了存在is-a关

系外,还存在着其他的关系。本文把概念间存在的一般关系分为以下两类,分别采取不同方法进行处理。

1)通用关系:这类关系在大多数领域概念间都是存在的,包括:一般属性关系、整体部分关系、成员集体关系等。

1732

清华大学学报(自然科学版)2005,45(S1)

2)领域关系:指专门存在于某领域中的关系。

例如在新闻报道中的原因事件关系、人物事件关系;在市场分析中的生产商产品关系,生产者消费者关系,商场顾客关系等。

对于第一类关系的做法同处理is-a关系类似,即基于可扩展的模式分析法。对于第二类关系所采用的学习方法如3.1所述。3.1　领域关系的发现

3.2　关系的修剪

实验表明,由算法2获取的概念关系中存在大量冗余。例如在对手机市场相关网页文本进行分析时,在商品质量和手机质量之间都存在较强关联。而事实上,因为手机是一种商品,所以手机质量之间的关联是商品质量的自然体现,不应该被视作新的关联。对此,本文采取以下策略对该类冗余进行修剪。

首先设定一个阈值K。对于任意一对关联L:

)且b=H(b′)(如:a′→b′,若a=H(a′a→b和L′

)且图2a所示),则若support(L)>Ksupport(L′

),则删除L′,否confidence(L)>Kconfidence(L′

)或b≠H(b′)(如则删除L;否则,若a≠H(a′

图2b所示),则令x=support(L)confidence(L),

)confidence(L′)。若x>y则删除y=support(L′,否则删除L。L′

概念间领域关系学习的算法启发自文[9]所提出的发现项目间关联规则方法。在该文中,给定一个

交易集T={ti󰃜i=1,2,…,n},其中:每一个交易是一个项目集ti={ai,j󰃜j=1,2,…,n,ai,j∈C},C是项目名称的集合。关联规则Xk→Yk(Xk,Yk󰃜{ti󰃜Xk∪YkΑti}󰃜support(Xk→Yk)=,(8)

n

confidence(Xk→Yk)=

󰃜{ti󰃜Xk∪YkΑti}󰃜.󰃜{ti󰃜XkΑti}󰃜

(9)

　　本文将上述算法的思想推广到发现概念间的领域关系上。即:如果概念c1的出现总是伴随c2的出现,则推测c2可能与c1存在某种关系。给定两个阈值ksupport和kconfidence,概念间领域关系的发现算法如下所示:

算法2　发现概念间的领域关系

1)从本体库中任意选取两个概念c1,c2,使得c1≠H(c2),且c2≠H(c1),若不存在这样的概念,转步骤6;

2)按式(8)计算support(c1→c2),若support(c1→c2)3)按公式(9)计算confidence(c1→c2),若confidence(c1→c2)4)将(c1→c2)加入规则库,转步骤1;

5)对关系进行修剪;6)结束。

图2　本体关系修剪

4　实验分析

为验证本文所提出的本体学习算法,在实验中使用Google从网络上搜集了一组与“手机市场”相关的850个网页作为初始领域文本。使用文[10]中提出的命名实体识别方法获取候选本体概念,并使用了文[6]中所提出的方法利用抽取到的本体从Web上自动搜索相关网页。

图3是实验中所获得的部分本体,表1列出了部分与“手机”和“市场”相关的概念关系在学习时所得到的可信度。实验结果说明,所提出的模型可以有效获取领域概念间存在的is-a关系和一般关系。另外,实验表明:

1)充分利用网页中的结构化和半结构化信息可以大大提高概念提取的精度;

2)使用下文签名可以在一定程度上提高准确率,但对召回率提高不明显;

3)自动获取的网页质量对领域本体获取的准确性和系统的稳定性影响很大。

概念间领域关系的可信度R[g(c1,c2)]用如下公式计算:

R[g(c1,c2)]=

support(c1→c2)confidence(c1→c2).

(10)

其中,support(c1→c2)和confidence(c1→c2)按式(8)和式(9)计算。

方卫东,等:　基于Web挖掘的领域本体自动学习1733

图3　实验所得的与“手机市场”相关的部分概念及其关系

表1　部分概念关联及其可信度

概念价格

品牌市场短信投诉

手机

可信度

0.920.680.850.700.69

[3]NavigliR,VelardiP,GangemiA.Ontologylearningandits

applicationtoautomatedterminologytranslation[J].IEEE31.

[4]MaedcheA,StaabS.Discoveringconceptualrelationsfrom

text[A].Proc14thEuroConfonArtificialIntelligence[C].Amsterdam:IOSPress,2000.

[5]AgirreE,AnsaO,HovyE,etal.

ontologiesusingtheWWW[A].

Enrichingverylarge

IntelligentSystems,2003,18(1):22

市场概念销售

竞争趋势分析潜力

可信度

0.930.900.500.820.44

Proc1stWorkshopon

OntologyLearningOL’2000[C].Berlin,Germany:CEURWorkshop,2000.

[6]FANGWeidong,ZHANGLing,WANGYanxuan,etal.

Towardasemanticsearchenginebasedonontologies[A].Proc4thIntlConfMachineLearningandCybernetics

(ICMLC2005)[C].NewYork:IEEEPress,2005.StummeG,MadcheA.FCA2Merge:Bottom2upmergingofontologies[A].Proc7thIntConfArtificialIntelligence[C].[8]

SanFrancisco:MorganKaufmann,2001.225230.

HearstMA.AutomateddiscoveryofWordNetrelations[A].

FellbaumC,ed.WordNet:AnElectronicLexical

[C].

Cambridge,

MA:

MIT

Press,

1998.

Database

5　结　论

本文提出的模型解决了现有本体学习方法需依赖于通用词典或核心本体和不能对所获得的关系进行可信度量化的问题。下一步的工作将围绕如何提高系统的稳定性和运行效率,使之能应用于实际生产中的大规模分析。

参考文献　(References)

[1]MaedcheA,StaabS.Ontologylearningforthesemanticweb

[J].IEEEIntelligentSystems,2001,16(2):72

79.

[2]MorinE.Automaticacquisitionofsemanticrelationsbetween

termsfromtechnicalcorpora[A].Proc5thIntCongressonTerminologyandKnowledgeEng(TKE’99)[C].Vienna:TermNet,1999.

[7]

[9]

131151.

SrikantR,AgrawalR.Mininggeneralizedassociationrules[A].

ProcVeryLargeDataBase[C].

SanFrancisco:

Chinese

MorganKaufmannPublishers,1995.407419.[10]SUNJian,GAOJianfeng,ZHANGLei,etal.

namedentityidentificationusingclass2basedlanguagemodel[A].Proc19thIntConfComputationalLinguistics[C].SanFrancisco:MorganKaufmann,2002.967973.