萬(wàn)慶生，黃少濱，劉剛，陸路

（哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150001）

基于FCA的領(lǐng)域問(wèn)句相似度計(jì)算方法

萬(wàn)慶生，黃少濱，劉剛*，陸路

（哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150001）

文章提出一種基于形式概念分析的領(lǐng)域問(wèn)句相似度計(jì)算方法，該方法不僅考慮了問(wèn)句的語(yǔ)義與語(yǔ)法結(jié)構(gòu)，更主要的是利用形式概念分析方法提取和建立領(lǐng)域概念集，是一種新的計(jì)算領(lǐng)域問(wèn)句相似度計(jì)算模型。通過(guò)形式概念分析構(gòu)建領(lǐng)域知識(shí)概念集，概念集以概念格形式進(jìn)行組織。將問(wèn)句相似度計(jì)算轉(zhuǎn)換成概念集的相似度計(jì)算。試驗(yàn)結(jié)果表明，使用該方法的相似度計(jì)算準(zhǔn)確率約為84%，并在有噪聲的情況下依然保持高準(zhǔn)確率。

式概念分析；概念格；問(wèn)句；相似度

在基于問(wèn)答對(duì)的問(wèn)答系統(tǒng)中，問(wèn)句相似度計(jì)算直接影響問(wèn)答系統(tǒng)檢索結(jié)果的準(zhǔn)確率。目前，國(guó)內(nèi)外對(duì)問(wèn)句相似度計(jì)算方法已有大量研究，其中大部分問(wèn)句相似度計(jì)算方法采用的是自然語(yǔ)言處理中的句子相似度計(jì)算方法。已有許多句子相似度計(jì)算的方法，如基于編輯距離的方法[1]、基于語(yǔ)義計(jì)算的方法[2]、基于語(yǔ)義依存的方法[3]、基于骨架依存樹(shù)的方法[4]、TF-IDF（Term Frequency-In?verse Document Frequency）方法[5]等。這些方法多數(shù)基于向量空間模型，也有采用句法分析和語(yǔ)義分析。由于問(wèn)句相似是指問(wèn)句答案的相似這一特點(diǎn)，句子相似度計(jì)算方法并不完全適用于問(wèn)句相似度計(jì)算。

在實(shí)際應(yīng)用中，僅通過(guò)問(wèn)句語(yǔ)義和語(yǔ)法相似度衡量問(wèn)句相似度，并不能取得很好效果。

本文提出一種基于形式概念分析的問(wèn)句相似度計(jì)算方法，該方法不僅考慮問(wèn)句的語(yǔ)法與語(yǔ)義結(jié)構(gòu)，更主要的是利用形式概念分析方法提取和建立領(lǐng)域概念集，通過(guò)構(gòu)建領(lǐng)域概念格和提出概念集相似度計(jì)算方法，提高領(lǐng)域問(wèn)句相似度計(jì)算的準(zhǔn)確率。

本文提出基于領(lǐng)域問(wèn)題相似度計(jì)算方法，能很好得解決上述情況下的相似度計(jì)算問(wèn)題。最后利用社保中的五險(xiǎn)（養(yǎng)老保險(xiǎn)、醫(yī)療保險(xiǎn)、工傷保險(xiǎn)、失業(yè)保險(xiǎn)和生育保險(xiǎn)）領(lǐng)域問(wèn)題集進(jìn)行試驗(yàn)，并取得很好效果。

1 相關(guān)知識(shí)

1.1 基于形式概念分析的概念格相關(guān)理論

20世紀(jì)80年代德國(guó)達(dá)姆施塔特科技大學(xué)的Wille教授以形式概念分析（Formal Concept Analy?sis，F(xiàn)CA）重構(gòu)格理論（Lattice T heory）[6]，形式概念分析和基于形式概念分析的概念格相關(guān)理論與技術(shù)，作為數(shù)據(jù)分析研究領(lǐng)域的重要方法和手段，逐漸受到國(guó)際學(xué)術(shù)界的廣泛關(guān)注[7]。概念格也隨之由Wille首先提出。概念格的每個(gè)節(jié)點(diǎn)是一個(gè)形式概念，由外延和內(nèi)涵兩部分組成。外延指概念所覆蓋的實(shí)例。內(nèi)涵指概念的描述，該概念覆蓋實(shí)例的共同特征。概念格的構(gòu)建過(guò)程從本質(zhì)上說(shuō)是概念的聚類(lèi)過(guò)程。概念和概念之間的泛化和例化關(guān)系，可以用一個(gè)Hasse圖來(lái)表示。通過(guò)Hasse圖，可直觀(guān)看出整個(gè)概念格的層次結(jié)構(gòu)。

關(guān)于形式概念分析和概念格詳細(xì)介紹可參考文獻(xiàn)[8-10]。形式概念（Formal Concept）與形式背景（Formal Context）是支撐形式概念分析的兩大理論基礎(chǔ)。在Wille和Ganter的闡述中，有相關(guān)內(nèi)容定義如下：

定義1一個(gè)形式背景K=（U，A，R）由對(duì)象集合U和屬性集合A以及U和A的二元關(guān)系R組成。其中U稱(chēng)為形式對(duì)象，A稱(chēng)為形式屬性。記作（u，a）∈R或uRa，指對(duì)象u具有屬性a。

形式背景K可看成如表1所示的一張二維關(guān)系表。一個(gè)元組代表一個(gè)對(duì)象，列代表屬性集合，如果uRa，則在元組u的a列上進(jìn)行標(biāo)記。表1說(shuō)明對(duì)象1具有屬性b、c和d，對(duì)象3具有屬性a、c、d和e。

表1 形式背景的二維關(guān)系表Table 1 Relation table of formal context

在形式背景K中，在U的冪集M（U）和A的冪集M（A）間可定義兩個(gè)映射f和g如下：

其被稱(chēng)為U的冪集和A的冪集之間的Galois聯(lián)接。如果二元組，滿(mǎn)足條件U1=g(A1)和A1=f(U1)，則被稱(chēng)為形式背景K的一個(gè)形式概念。所以，一個(gè)概念C為一個(gè)二元組（U1，A1），其中U1稱(chēng)為概念C的外延，A1稱(chēng)為概念C的內(nèi)涵。如圖1所示，描述形式概念在具體應(yīng)用中的形式。

定義2形式背景K下的所有形式概念記為C（K），給定形式概念（U1，A1）和（U2，A2），如果U1?U2（等價(jià)于A2?A1）則稱(chēng)形式概念（U1，A1）是（U2，A2）的后繼，相反（U2，A2）是（U1，A1）的前驅(qū)。

概念的前驅(qū)后繼關(guān)系相對(duì)應(yīng)于概念的泛化與細(xì)化關(guān)系。而這種前驅(qū)后繼關(guān)系滿(mǎn)足自反性、反對(duì)稱(chēng)性和傳遞性，因此前驅(qū)后繼關(guān)系是形式背景K上的偏序關(guān)系。通過(guò)這種關(guān)系等到1個(gè)偏序集(C(K),≤)，并且偏序集(C(K),≤)是1個(gè)完全格，稱(chēng)為形式背景K的概念格，記為L(zhǎng)（K）。且L（K）可通過(guò)Hasse圖來(lái)直觀(guān)地描繪L（K）的層次結(jié)構(gòu)。圖2為形式背景如表1所示下的概念格的Hasse圖。

圖1 形式概念結(jié)構(gòu)Fig.1The structure of formal concept

圖2 形式背景K下的概念格Fig.2 The concept lattice of formal context K

1.2 概念格構(gòu)造算法

概念格是以數(shù)學(xué)的序理論和完全格理論為數(shù)學(xué)基礎(chǔ)，描述概念和概念間的層次關(guān)系。構(gòu)造概念格的本質(zhì)就是對(duì)概念進(jìn)行聚類(lèi)。對(duì)于同樣的形式背景，最終形成的概念格結(jié)構(gòu)是唯一的。概念格包括概念和概念間的層次關(guān)系，因此所有構(gòu)造算法必然需要生成所有概念和所有概念之間的層次關(guān)系。

漸進(jìn)式構(gòu)造算法和批處理算法使用完全不同的基本思想。批處理算法主要包括構(gòu)造形式概念集和構(gòu)造概念層次關(guān)系兩個(gè)任務(wù)，大多數(shù)都屬于任務(wù)分割生成模型，只有少部分是屬于任務(wù)交叉生成模型。漸進(jìn)式構(gòu)造算法則是同時(shí)進(jìn)行生成概念和構(gòu)造概念層次關(guān)系兩個(gè)任務(wù)，在生成概念的同時(shí)，更新概念格直接的層次關(guān)系。由于漸進(jìn)式構(gòu)造算法支持動(dòng)態(tài)添加新概念，適合實(shí)際的使用需求并且有優(yōu)越的時(shí)間性能。因此，本文中使用Godin算法構(gòu)造概念格。關(guān)于Godin算法的具體理論證明與細(xì)節(jié)可參考文獻(xiàn)[11-12]。

2 相似度計(jì)算

經(jīng)過(guò)形式概念分析后，可以得到一個(gè)領(lǐng)域概念格L（K），概念格中的每個(gè)節(jié)點(diǎn)為一個(gè)形式概念。L（K）實(shí)際是一個(gè)以完全格為組織形式的領(lǐng)域概念集。領(lǐng)域概念集是進(jìn)行問(wèn)句相似度計(jì)算的基礎(chǔ)。問(wèn)句文本首先經(jīng)過(guò)語(yǔ)義分析、詞性標(biāo)注和分詞，得到由關(guān)鍵詞組成的問(wèn)句向量V=，其中wi為分詞后保留的關(guān)鍵詞。然后經(jīng)過(guò)概念向量提取算法得到問(wèn)句概念向量FV=，其中ci為問(wèn)句向量V所覆蓋的L（K）中的概念。最后將問(wèn)句相似度計(jì)算轉(zhuǎn)換成概念向量的相似度計(jì)算。關(guān)于概念向量提取算法和概念向量相似度計(jì)算將在下面給出詳細(xì)的描述。

2.1 概念向量提取算法

在概念形式分析中，雖然不涉及向量，但是可以把一個(gè)向量看成一個(gè)對(duì)象。一個(gè)向量V=可看成1個(gè)擁有n個(gè)屬性的對(duì)象V={v1,v2…vn}。因此下面所訴的對(duì)象和向量可以互換。

定義3對(duì)于對(duì)象O所具有的屬性集A0，形式概念C1=（U1,A1），如果A1?A0，則稱(chēng)對(duì)象O覆蓋形式概念C1=（U1,A1），記作O∠C1。對(duì)于形式概念C1=（U1,A1）和形式概念C2=（U2,A2），如果A1?A≡，則稱(chēng)形式概念C2=（U2,A2）覆蓋形式概念C1=（U1,A1），記作C2∠C1。

定義4：Cc(O)={Ci|O∠Ci,Ci∈L（K）}，即Cc(O)為對(duì)象O在L（K）上覆蓋的概念的集合。Cc(O)={Ci|?Cj(Cj∠Ci,Ci∈CC(O),CiCC(O)}，即CC(O)為對(duì)象O在L（K）上覆蓋的最大概念集合。

概念向量提取是指給定一個(gè)對(duì)象O和一個(gè)概念格L（K），求集合CC(O)的過(guò)程。本文提出一種求集合CC(O)的概念向量提取算法（Concept Cover）。算法的主要思想是從L（K）的最小下界L∨開(kāi)始進(jìn)行深度優(yōu)先搜索，檢查當(dāng)前格節(jié)點(diǎn)是否被對(duì)象覆蓋，如果被覆蓋則將節(jié)點(diǎn)添加到概念集合中，并返回。由定義2有(U1,A1)≥(U2,A2)A1?A2，所以O(shè)∠?C2O∠C1，即如果對(duì)象O覆蓋概念C，那么概念C的前驅(qū)節(jié)點(diǎn)也被對(duì)象O所覆蓋。因此，當(dāng)搜索到O∠C1后如果繼續(xù)搜索，那么得到的概念集合即為Cc(O)，如果停止當(dāng)前路徑的搜索，那么得到的概念集合即為CC(O)。概念向量提取算法（Concept Cover算法）的偽代碼如下所示。

Call Find Concept:L,O，L∨,Clist{以概念格L，問(wèn)句對(duì)象O，格L的最小下界L∨，存儲(chǔ)提取的概念向量容器Clist為參數(shù)，調(diào)用Find Concept算法}

Concept Cover算法是1個(gè)在概念格L（K）中自底向上深搜過(guò)程，并且每個(gè)節(jié)只訪(fǎng)問(wèn)1次。因此該算法的時(shí)間復(fù)雜度為O（n），n為概念格中節(jié)點(diǎn)個(gè)數(shù)。

2.2 概念向量相似度計(jì)算方法

經(jīng)過(guò)概念向量提取，一個(gè)問(wèn)題對(duì)象O被轉(zhuǎn)換成一個(gè)概念集CC(O)。一個(gè)概念向量V=可以看成一個(gè)概念集O={v1,v2…vn},因此概念向量相似度計(jì)算即為概念集之間的相似度計(jì)算。

概念集之間的相似度計(jì)算依賴(lài)于集合元素間的相似度計(jì)算，即形式概念間相似度的計(jì)算。目前，國(guó)內(nèi)外學(xué)者提出不少在概念格中形式概念的相似度計(jì)算方法。其中文獻(xiàn)[11]中提出一種基于領(lǐng)域本體相似圖（similarity graph）的計(jì)算形式概念相似度方法。其中基于領(lǐng)域本體的相似圖本質(zhì)上是一個(gè)本體之間相似度的二維矩陣。文獻(xiàn)上形式概念中的屬性是本體，本文提出的方法中是詞語(yǔ)，因此基于領(lǐng)域本體相似度圖在本文中就是一個(gè)詞語(yǔ)之間相似度的二維矩陣。這個(gè)矩陣可用前面提到的基于《知網(wǎng)》的語(yǔ)義相似度方法得到。下面給出關(guān)于形式概念相似度計(jì)算的相關(guān)定義，關(guān)于詳細(xì)內(nèi)容可參考文獻(xiàn)[12]。

定義5考慮兩個(gè)在L（K）形式概念（U1，A1）和（U2，A2）,n=|A1|，m=|A2|，假定n≤m，集合η(A1,A2)為任意A1和A2元素間的n對(duì)匹配。定義如下：η(A1,A2)={{…＜an,bn>}|a∈A1,Bi∈A2,?i=1…n, andai≠aj,bi≠bk,?j,,≠i}

進(jìn)而提出形式概念的相似度計(jì)算方法，如下：

其中as（a,b）為計(jì)算a和b的語(yǔ)義相似度結(jié)果，n如定義5中所示。

w是一個(gè)0到1之間的參數(shù)，用以調(diào)節(jié)形式概念中對(duì)象集和屬性集對(duì)相似度計(jì)算影響的權(quán)重。形式概念中的對(duì)象集和屬性集滿(mǎn)足2.1小節(jié)描述的f和g的映射關(guān)系，所以對(duì)象集和屬性集是對(duì)偶關(guān)系，因此，w一般設(shè)置為0.5。Sim（（U1,A1）,（U2,A2））的值域?yàn)閇0,1]，值越大，表明形式背景（U1,A1）和（U2,A2）的相似度越高。

考慮概念集O1＝{a1,a2…an}和概念集O2＝{b1,b2…bn}，ai,bjL(K)，i=1…n，j=1…m那么概念集之間的相似度計(jì)算公式為：

其中n是集合O1的元素個(gè)數(shù)，m是集合O2的元素個(gè)數(shù)。公式（2）求的是集合間元素相似度的加權(quán)平均值。Sim（O1,O2）的值域?yàn)閇0,1],值越大，表明兩個(gè)集合越相似。

3 試驗(yàn)評(píng)估

3.1 試驗(yàn)數(shù)據(jù)和試驗(yàn)方法

本文選擇社保中關(guān)于五險(xiǎn)的問(wèn)題集進(jìn)行試驗(yàn)。社保中五險(xiǎn)包括養(yǎng)老保險(xiǎn)、醫(yī)療保險(xiǎn)、工傷保險(xiǎn)、失業(yè)保險(xiǎn)和生育保險(xiǎn)。問(wèn)題集是從公民在網(wǎng)上提出的關(guān)于五險(xiǎn)的并且頻率較高的問(wèn)題中篩選出的45個(gè)問(wèn)題。試驗(yàn)的問(wèn)題集來(lái)至于公民日常生活所遇到的關(guān)于五險(xiǎn)的真實(shí)問(wèn)題，用此進(jìn)行試驗(yàn)具有實(shí)際意義。其中，關(guān)于每類(lèi)保險(xiǎn)的問(wèn)題數(shù)量是8到10個(gè)不等。對(duì)于每個(gè)問(wèn)題，都通過(guò)人為挑選出與其相似度較高的8到10個(gè)問(wèn)題，也稱(chēng)為相關(guān)問(wèn)題。并通過(guò)不斷添加領(lǐng)域外的問(wèn)題數(shù)量（噪聲），分別使用編輯距離、TF-IDF、基于語(yǔ)義依存方法和本文提出的方法進(jìn)行相似度計(jì)算，并進(jìn)行準(zhǔn)確率和召回率的統(tǒng)計(jì)。通過(guò)試驗(yàn)分析四種方法在不同的噪聲比例中的實(shí)際效果。噪聲比是指社保領(lǐng)域外的問(wèn)題數(shù)（噪聲數(shù)量）除以45（社保領(lǐng)域內(nèi)的45個(gè)問(wèn)題）。在試驗(yàn)中取相似度最高的前k個(gè)問(wèn)題作為檢索結(jié)果，且取k等于相關(guān)問(wèn)題數(shù)，因此準(zhǔn)確率與召回率相等，以下只對(duì)準(zhǔn)確率進(jìn)行統(tǒng)計(jì)。準(zhǔn)確率（Precision）的計(jì)算方法如下定義：

其中Q為問(wèn)題集，P（q）為人為選出與問(wèn)題q相似的問(wèn)題集，H（q）是利用算法求出與問(wèn)題q相似的問(wèn)題集。

3.2 試驗(yàn)結(jié)果及分析

圖3是在噪聲比分別為0、20%、40%、60%、80%和100%情況下4種方法的準(zhǔn)確率比較圖。

圖3 不同噪聲比準(zhǔn)確率對(duì)比Fig.3 Comparision of accuracy at different noise ratios

由圖3可知，本文提出的方法在無(wú)噪聲數(shù)據(jù)情況下，準(zhǔn)確率可達(dá)83.84%，而編輯距離、IF-IDF和基于語(yǔ)義依存方法的準(zhǔn)確率分別為71.76%、73%和76.2%。本文方法的相似度計(jì)算準(zhǔn)確率明顯優(yōu)于前3種方法。隨著噪聲比的增大，四種方法的準(zhǔn)確率都有所下降，并且在噪聲較大時(shí)（80%），準(zhǔn)確率都有明顯下降。但是本文提出的方法始終保持較高準(zhǔn)確率，在噪聲比高達(dá)100%時(shí)，準(zhǔn)確率仍有71.36%。其他3種方法并不基于領(lǐng)域知識(shí)，沒(méi)有區(qū)分領(lǐng)域問(wèn)題的能力，因此準(zhǔn)確率會(huì)隨噪聲比的增大而不斷下降。

本文提出的方法依賴(lài)領(lǐng)域知識(shí)，在噪聲比較小情況下能保持高準(zhǔn)確率。當(dāng)噪聲比較大時(shí)，由于本文試驗(yàn)所用的領(lǐng)域知識(shí)只是五險(xiǎn)領(lǐng)域的部分法律法規(guī)，知識(shí)覆蓋面較小，覆蓋的領(lǐng)域知識(shí)不全，抽取的領(lǐng)域概念的粒度較大，對(duì)噪聲的區(qū)分能力有所下降，導(dǎo)致準(zhǔn)確率降低。但是可通過(guò)健全領(lǐng)域知識(shí)來(lái)改善高噪聲下的準(zhǔn)確率。

3.2.1 與編輯距離方法對(duì)比試驗(yàn)結(jié)果

圖4是噪聲比例分別為0%、20%、40%、60%、80%和100%的情況下，編輯距離和本文方法對(duì)于每個(gè)問(wèn)題的準(zhǔn)確率對(duì)比圖。對(duì)于某個(gè)問(wèn)題，長(zhǎng)條高于曲線(xiàn)說(shuō)明編輯距離方法對(duì)于這個(gè)問(wèn)題的準(zhǔn)確率高于本文方法，反之亦然。

由圖4可知，本文方法的準(zhǔn)確率明顯高于編輯距離方法，并表現(xiàn)更為穩(wěn)定。隨著噪聲比的增大，編輯距離方法對(duì)于各問(wèn)題的準(zhǔn)確率浮動(dòng)較大，準(zhǔn)確率也比較低。編輯距離方法通過(guò)計(jì)算兩個(gè)句子的編輯距離衡量?jī)蓚€(gè)句子的相似度。通過(guò)引入HowNet和《同義詞詞林》對(duì)其進(jìn)行改進(jìn)[1]。這種方法對(duì)句子的結(jié)構(gòu)和詞語(yǔ)出現(xiàn)的次序依賴(lài)性很強(qiáng)，此方法不能有效處理兩句意思相近但結(jié)構(gòu)和用詞不同的句子。這是導(dǎo)致編輯距離方法準(zhǔn)確率低，且對(duì)噪聲很敏感的原因。

圖4 不同噪聲比下編輯距離與本文方法準(zhǔn)確率對(duì)比Fig.4 Comparision of accuracy between edit distance and this method at differenct noise ratios

3.2.2 與TF-IDF方法對(duì)比試驗(yàn)結(jié)果

圖5是噪聲比分別為0%、20%、40%、60%、80%和100%的情況下，TF-IDF和本文方法對(duì)于每個(gè)問(wèn)題的準(zhǔn)確率對(duì)比圖。圖中曲線(xiàn)是本文方法的準(zhǔn)確率曲線(xiàn)，柱狀圖是TF-IDF的準(zhǔn)確率。對(duì)于某個(gè)問(wèn)題，長(zhǎng)條高于曲線(xiàn)說(shuō)明TF-IDF方法對(duì)于這個(gè)問(wèn)題的準(zhǔn)確率高于本文方法，反之亦然。

由圖5可知，本文方法的準(zhǔn)確率明顯高于TFIDF方法，并表現(xiàn)更為穩(wěn)定。在噪聲比為0%時(shí)，TF-IDF方法大多數(shù)問(wèn)題的準(zhǔn)確率明顯低于本文方法的準(zhǔn)確率。隨噪聲比增大，TF-IDF方法的對(duì)于各問(wèn)題的準(zhǔn)確率趨于平穩(wěn)，但普遍較低。這是由于TF-IDF方法缺乏對(duì)噪聲的識(shí)別能力，導(dǎo)致準(zhǔn)確率普遍較低。TF-IDF方法對(duì)于特征詞的加權(quán)是靜態(tài)的，即每個(gè)特征詞的權(quán)重固定不變，但是很多情況下每個(gè)特征詞的權(quán)重不是固定不變的，且可能有很大差異，如引言中所述。在本文提出的方法中，特征詞隨組合不同，所表現(xiàn)的重要性也不同。本文方法具備噪聲的識(shí)別能力，但依賴(lài)于領(lǐng)域知識(shí)，由于領(lǐng)域知識(shí)不夠全面，使得某些問(wèn)題的準(zhǔn)確率波動(dòng)較大，但能保持較高的準(zhǔn)確率。隨著噪聲比增大，TF-IDF方法準(zhǔn)確率高于本文方法準(zhǔn)確率的問(wèn)題越來(lái)越少，表現(xiàn)出在高噪聲比情況下本文方法的明顯優(yōu)勢(shì)。

3.2.3 與語(yǔ)義依存方法對(duì)比試驗(yàn)結(jié)果

圖6是噪聲比例分別為0%、20%、40%、60%、80%和100%的情況下，基于語(yǔ)義依存方法和本文方法對(duì)于每個(gè)問(wèn)題的準(zhǔn)確率對(duì)比圖。圖中曲線(xiàn)是本文方法的準(zhǔn)確率曲線(xiàn)，柱狀圖是基于語(yǔ)義依存方法的準(zhǔn)確率。對(duì)于某個(gè)問(wèn)題，長(zhǎng)條高于曲線(xiàn)說(shuō)明基于語(yǔ)義依存方法對(duì)于這個(gè)問(wèn)題的準(zhǔn)確率高于本文方法的準(zhǔn)確率，反之亦然。

圖5 不同噪聲比下TF-IDF與本文方法準(zhǔn)確率對(duì)比Fig.5 Comparision of accuracy between TF-IDF and this method at different noise ratios

由圖6可知，本文方法的準(zhǔn)確率明顯高于語(yǔ)義依存方法的準(zhǔn)確率，并表現(xiàn)更為穩(wěn)定。語(yǔ)義依存方法的準(zhǔn)確率較高，但隨著噪聲比的增大。波動(dòng)較大。語(yǔ)義依存方法的對(duì)于每個(gè)問(wèn)題的準(zhǔn)確率很不穩(wěn)定，高低起伏較大，最高達(dá)90%，同時(shí)最低只有37.5%。語(yǔ)義依存方法是基于句子的依存結(jié)構(gòu)進(jìn)行相似度計(jì)算的。對(duì)于每個(gè)句子，提取核心詞和直接依存于其的有效詞組成搭配，通過(guò)計(jì)算搭配的相似度來(lái)計(jì)算句子相似度，具體細(xì)節(jié)可參見(jiàn)文獻(xiàn)[3]。

語(yǔ)義依存方法很大程度依賴(lài)兩個(gè)句子的核心詞的語(yǔ)義相似程度。當(dāng)兩個(gè)句子的核心詞語(yǔ)義相差較大時(shí)，相似度相應(yīng)較低。導(dǎo)致準(zhǔn)確率很不穩(wěn)定，隨著噪聲比增大越明顯。

本文方法在計(jì)算領(lǐng)域問(wèn)句相似度上明顯優(yōu)于編輯距離方法、TF-IDF方法和基于語(yǔ)義依存方法，并可通過(guò)健全領(lǐng)域知識(shí)來(lái)進(jìn)一步提高準(zhǔn)確率和降低對(duì)噪聲的敏感度。

圖6 不同噪聲比下語(yǔ)義依存方法與本文方法準(zhǔn)確率對(duì)比Fig.6 Comparision of accuracy between semantic dependency and this method at different noise ratios

4 結(jié)論

本文提出一種基于形式概念分析的領(lǐng)域問(wèn)答系統(tǒng)中的問(wèn)句相似度計(jì)算方法。通過(guò)構(gòu)建領(lǐng)域概念格和提出概念集相似度計(jì)算方法提高領(lǐng)域問(wèn)句相似度計(jì)算的準(zhǔn)確率。給出一種新的領(lǐng)域問(wèn)句相似度計(jì)算的模型，不同于以往基于語(yǔ)義和語(yǔ)法分析以及統(tǒng)計(jì)方法的句子相似度計(jì)算方法。本文方法準(zhǔn)確率有所提高，并可通過(guò)健全領(lǐng)域知識(shí)進(jìn)一步提高準(zhǔn)確率。

[1]車(chē)萬(wàn)翔,劉挺,秦兵,等.基于改進(jìn)編輯距離的中文相似句子檢索[J].高技術(shù)通訊,2004(7):152.

[2]李素建.基于語(yǔ)義計(jì)算的語(yǔ)句相關(guān)度研究[J].計(jì)算機(jī)工程與應(yīng)用,2002(7):219.

[3]李彬,劉挺,秦兵,等.基于語(yǔ)義依存的漢語(yǔ)句子相似度計(jì)算[J].計(jì)算機(jī)應(yīng)用研究,2003,20(12):15-17.

[4]穗志方,俞士汶.基于骨架依存樹(shù)的語(yǔ)句相似度計(jì)算模型[C].北京:中文信息處理國(guó)際會(huì)議,1998.

[5]羅欣,夏德麟,晏蒲柳.基于詞頻差異的特征選取及改進(jìn)的TF-IDF公式[J].計(jì)算機(jī)應(yīng)用,2005,25(9):29.

[6]Wille R.Restructuring lattice theory:An approach based on hier?archies of concept[C].Droceedings of the 7th International Confer?ence on Formal Concept Analysis.Berlin:Springer-Verlag,2009: 314-339.

[7]畢強(qiáng),滕廣青.國(guó)外形式概念分析與概念格理論應(yīng)用研究的前沿進(jìn)展及熱點(diǎn)分析[J].現(xiàn)代圖書(shū)情報(bào)技術(shù),2010(11):12.

[8]Ganter B,Wille R.Formal concept analysis:Mathematical founda?tions[M].Berlin:Springer,1999.

[9]韓道軍.Godin算法的改進(jìn)和FCA在智能搜索引擎中的應(yīng)用[D].鄭州:河南大學(xué),2005.

[10]Godin R,Missaoui R,Alaoui H.Incremental concept formation al?gorithms based on Galois(concept)lattices[J].Computational Intel?ligence,1995,11(2):246-267.

[11]Formica A,Missikoff M.Concept similarity in symontos:an enter?prise ontology management tool[J].Comput J,2002,45:24.

[12]Formica A.Ontology-based concept similarity in formal concept analysis[J].Information Sciences,2005,176(18):2624-2641.

Calculation method of domain question similarity based on FCA

WAN Qingsheng,HUANG Shaobin,LIU Gang,LU Lu(School of Couputer Science and Technology,Harbin Engineering University,Harbin 150001,China)

A domain question similarity calculation method was proposed based on formal concept analysis.This method not only considers the question of semantic and grammatical structure,but also uses the method of formal concept analysis to extract and build domain concept sets.It's a new model for computing the similarity of calculation questions.Concept sets of domain knowledge are built through formal concept analysis,and the concept sets are organized in the form of conceptual lattice.And then the similarity of questions can be transformed into the similarity of concept sets.Finally,the experiment results indicated that the accuracy of similarity calculation by using this method was about 84%,and it could maintain a high accuracy in the case of noise.

formal concept analysis;concept lattice;questions;similarity

TP315

A

1005-9369（2014）02-0103-08

2013-12-09

國(guó)家科技支撐計(jì)劃項(xiàng)目（2012BAH08B02）；中國(guó)博士后科學(xué)基金（2013M541345）；哈爾濱工程大學(xué)中央高?；究蒲袠I(yè)務(wù)專(zhuān)項(xiàng)資金項(xiàng)目（HEUCF100603，HEUCFZ 1212）

萬(wàn)慶生（1975-），男，博士研究生，研究方向?yàn)橹形膯?wèn)答系統(tǒng)。E-mail:79863200@qq.com

*通訊作者：劉剛，副教授，研究方向?yàn)橛?jì)算機(jī)應(yīng)用。E-mail:liugang@hrbeu.edu.cn

時(shí)間2014-1-17 16:36:39[URL]http://www.cnki.net/kcms/detail/23.1391.S.20140117.1636.004.html

萬(wàn)慶生,黃少濱,劉剛,等.基于FCA的領(lǐng)域問(wèn)句相似度計(jì)算方法[J].東北農(nóng)業(yè)大學(xué)學(xué)報(bào),2014,45(2):103-110.

Wan Qingsheng,Huang Shaobin,Liu Gang,et al.Calculation method of domain question similarity based on FCA[J].Journal of Northeast Agricultural University,2014,45(2):103-110.(in Chinese with English abstract)