基于圖熵極值理論的領(lǐng)域概念聚類方法

安敬民,李冠宇

(1.大連東軟信息學院 計算機與軟件學院,遼寧 大連 116023; 2.大連海事大學 信息科學技術(shù)學院,遼寧 大連 116026)

0 概述

在構(gòu)建領(lǐng)域本體的過程中,需要設(shè)計本體自學習機制以便在后期可以自動補充和擴展本體。而在本體自學習過程中,同領(lǐng)域概念的聚類是關(guān)鍵步驟,其決定所構(gòu)建領(lǐng)域本體在實際應(yīng)用過程中所提供領(lǐng)域概念的準確性。

同領(lǐng)域概念聚類的傳統(tǒng)方法主要有基于劃分、基于層次、基于形式概念分析以及基于語義距離的方法?；趧澐值姆椒ㄐ枰藶樵O(shè)定劃分的個數(shù)和窮舉所有可能的劃分情況,并給定遞歸算法將概念從一個劃分移到另一劃分來提高劃分結(jié)果的準確性,典型算法為K-means[1-2]。基于層次的方法是將復雜概念網(wǎng)中每一個概念節(jié)點視為一個獨立的聚類,利用領(lǐng)域一致度計算公式,迭代合并同領(lǐng)域概念,最終將復雜概念網(wǎng)分為多個領(lǐng)域的概念網(wǎng),其中基于分布密度計算[3]的方法為主要代表?；谛问礁拍罘治龅姆椒ㄖ饕捎酶拍罡駥ο蠓謱?模糊概念格[4]和模糊K-means[5]是其中的代表方法?；谡Z義距離的方法主要通過計算領(lǐng)域概念在概念樹中的距離進行聚類,目前有基于遍歷樹的螞蟻聚類算法[6]和百科詞條的本體概念聚類方法[7]等。文獻[1-2]采用優(yōu)化后的K-means方法選取并優(yōu)化聚類中心,結(jié)合設(shè)定的聚類閾值實現(xiàn)同領(lǐng)域概念的聚類。文獻[3]利用層次的耦合內(nèi)聚比得到類數(shù)目的分布密度,通過密度聚類實現(xiàn)最終的概念聚類。文獻[4-5]利用形式概念分析對概念的模糊處理能力,擴大了概念聚類范圍,增強了聚類效果。文獻[6]通過計算領(lǐng)域概念間的谷歌距離以及Wikipedia的距離和相似度實現(xiàn)聚類。文獻[7]利用馬氏距離得到概念向量間的語義距離,并通過多次迭代完成百科詞條中的概念聚類。

上述方法是目前對于領(lǐng)域概念聚類處理的主要方法,但在聚類過程中均未考慮概念重疊問題,即一個概念(節(jié)點)可能同時屬于多個領(lǐng)域,如“古董”一詞,可以理解為“陳舊的事物”,同時也可以理解為“具有守舊思想的人”,因此,其同時屬于兩個領(lǐng)域的概念,而因為基于K-means劃分和基于距離的方法所產(chǎn)生的概念集合總是不相交的,所以無法解決概念重疊問題?；谟嬎忝芏鹊姆椒ê托问礁拍罘治隹梢越鉀Q該類問題,但前者需要先選擇初始種子概念作為聚類核心點,結(jié)合各概念周圍的密度和設(shè)定的閾值,遞歸納入新的概念并迭代循環(huán)執(zhí)行(根據(jù)閾值會不同程度地在不同聚類結(jié)果中出現(xiàn)相同概念詞匯),而在此過程中有較多的主觀因素涉及其中(如選取初始概念),也是影響聚類效果的主要原因;后者雖然可以通過隸屬模糊和上下位近似的方法保留更多的概念信息,解決概念重疊問題,但同樣需提供若干個選定的聚類中心,仍然受到人為因素的影響。

本文提出以圖熵最大化實現(xiàn)初始節(jié)點隨機選擇代替質(zhì)心法,以圖熵最小化保證聚類結(jié)果的準確性?；谥形腤ordNet[8]多角度計算概念間的語義相似度同時構(gòu)建相似度矩陣,并將其轉(zhuǎn)化為以概念為節(jié)點的無向圖,利用圖熵最小化計算公式[9]結(jié)合最大信息熵理論[10],使圖中概念節(jié)點能夠在無需選取聚類質(zhì)心的情況下實現(xiàn)最優(yōu)同領(lǐng)域概念聚類,同時解決領(lǐng)域概念重疊問題。

1 問題描述與定義

現(xiàn)代漢語中有許多詞語具有一詞多義的特點,即一個詞語同時具有多個領(lǐng)域概念。所以,在對該類詞語進行同領(lǐng)域概念聚類時,其結(jié)果應(yīng)同時出現(xiàn)在不同領(lǐng)域,如圖1所示(以概念領(lǐng)域Di和Dj以及其中的概念c1c8和ck為例),多個領(lǐng)域在概念上具有交集,而目前的概念聚類方法并不能很好地適用于該問題的處理(關(guān)于概念重疊問題的具體解釋,此處不再贅述)。

圖1 領(lǐng)域概念聚類重疊示意圖

從非結(jié)構(gòu)化數(shù)據(jù)(如文本文檔等)角度出發(fā),對某個文本文檔中的概念進行同領(lǐng)域聚類時,若ck被歸類在Di中,則ck不會出現(xiàn)在Dj中,造成Dj中的概念缺失而使查全率和查準率降低,本文針對此問題進行研究。

定義1ck表示某個概念的詞語,若ck使得ck∈Di且ck∈Dj,i≠j,則對ck進行概念歸類時會產(chǎn)生概念重疊現(xiàn)象。

2 基于WordNet的概念相似度綜合計算

在對同領(lǐng)域概念進行聚類之前,要將概念間的相似度量化,根據(jù)概念與概念間的相似度判斷聚類的方式,同時相似度的精度也直接影響聚類結(jié)果的準確性。本文通過結(jié)合中文WordNet多角度計算概念間的相似度,提高相似度計算的準確性。

2.1 概念間相似度計算方法

目前基于WordNet計算概念間相似度的方法有從概念在WordNet中的語義距離[11]、深度及密度[12]角度出發(fā),或者考慮概念的語義重合度和概念包含的語義信息內(nèi)容[13]等方面相似度。本文結(jié)合文獻[14]的設(shè)計思想,對各角度語義相似度計算方式進行綜合考量,以提高概念相似度的精度。

基于WordNet中語義距離D(c1,c2)的概念間相似度表示為CS(c1,c2),計算公式如式(1)所示:

(1)

其中,a是c1、c2對中文WordNet中概念集合的平均語義距離。

以Hmax(c1)和Hmax(c2)分別表示c1、c2所在語義樹的最大深度,H(c1)和H(c2)分別表示c1、c2在樹中的深度,則基于WordNet中語義樹及概念深度的概念間相似度計算公式如式(2)所示:

(2)

用n(c)表示語義樹中以c為根節(jié)點的直接子節(jié)點數(shù),nmax(O)表示與c所在同一語義樹O中的所有節(jié)點的直接子節(jié)點最大值,結(jié)合文獻[12,14]計算概念相似度的方法,給出基于WordNet中語義樹及概念密度的概念間相似度計算公式如式(3)所示:

(3)

若將從c出發(fā)到語義樹根節(jié)點所經(jīng)過的節(jié)點個數(shù)記為S(c),則c1、c2基于WordNet語義樹的語義重合度計算公式如式(4)所示:

(4)

將式(4)結(jié)合文獻[15-16]中的概念信息內(nèi)容相似度計算方法,得到式(5):

(5)

其中,I(c)的計算公式見文獻[13-14]。

2.2 概念間相似度綜合計算

為提高概念間相似度計算的精確度,本文從多角度考慮對概念相似度有影響的因素,并將其以權(quán)重加和的形式作為綜合計算結(jié)果。為使綜合計算結(jié)果更具客觀合理性,引入主成分分析法[17]代替人為設(shè)定影響因子的方式。

構(gòu)建矩陣α=(xi1,xi2,xi3,xi4,xi5)T,i=1,2,3,4,5。其中xi由形如β=(CS,HS,PS,SS,IS)的向量組構(gòu)成。利用主成分分析法將α降為一維矩陣γ=[x′1,x′2,x′3,x′4,x′5],并利用降維過程中得到的特征值計算主成分貢獻率(q1,q2,q3,q4,q5),最終得到概念間相似度綜合計算公式為:

KSIM(c1,c2)=q1x′1+q2x′2+q3x′3+q4x′4+q5x′5

(6)

3 同領(lǐng)域相似概念結(jié)構(gòu)圖

3.1 概念相似度矩陣

根據(jù)本文2.2節(jié)中兩個概念間的同領(lǐng)域綜合相似度KSIM,按照對應(yīng)概念ci和cj兩個維度來構(gòu)建概念相似度矩陣:

RSIM(ci,cj)=

其中,1≤i≤n,1≤j≤n。

在矩陣RSIM中,對角線部分是同一概念的相似度值,有KSIM(ci,ci)=1,但由于在實際的領(lǐng)域概念聚類過程中強調(diào)不同概念的聚類,因此該值并無應(yīng)用意義。為簡化聚類操作,令KSIM(ci,ci)=0。

3.2 同領(lǐng)域相似概念的圖構(gòu)建

設(shè)定閾值λ,當矩陣RSIM中KSIM(ci,cj)大于λ時,將該值重新設(shè)定為1;反之,若小于λ,則設(shè)定為0。經(jīng)過化簡后的矩陣R′SIM為一個只含有元素0、1的矩陣。

將簡化得到的概念相似度矩陣R′SIM轉(zhuǎn)化為概念間的關(guān)系無向圖G(V,E),其中,V表示圖中的概念節(jié)點(頂點),E表示概念節(jié)點間的邊。若在相似度矩陣R′SIM中KSIM(ci,cj)=1,則概念ci、cj對應(yīng)的頂點Vi、Vj間存在無向邊Eij;反之,若KSIM(ci,cj)=0,則說明概念間不存在無向邊。最終形成同領(lǐng)域相似概念的圖結(jié)構(gòu),如圖2所示(以c1c7和cn為例)。

圖2 領(lǐng)域Di中的相似概念結(jié)構(gòu)圖

4 基于圖熵的領(lǐng)域概念聚類優(yōu)化

從信息論的最大信息熵理論角度出發(fā),將圖中的各個節(jié)點視為一個整體,而沒有主客之分,即在本文的聚類過程中,區(qū)別以往傳統(tǒng)的以聚類質(zhì)心為主的聚類方法,而是將已聚類的節(jié)點作為整體,通過圖熵最小化理論計算出下一步的最優(yōu)聚類結(jié)果。利用圖熵的聚類方法可以在每次聚類結(jié)果輸出后保留原文本文檔中已被聚類到某領(lǐng)域的概念,從而解決概念重疊問題。

設(shè)已構(gòu)建的同領(lǐng)域相似概念結(jié)構(gòu)圖G(V,E)的子圖G′(V′,E′),對G′的內(nèi)連接節(jié)點和外連接節(jié)點定義如下:

定義2在G′(V′,E′)和G(V,E)中,vi∈V′,vj∈V,且∈E′,則vi、vj互為G′中的內(nèi)連接節(jié)點;vi∈V′,vj∈V,且?E′∈E,則vj為vi在G′中的外連接節(jié)點。

在圖G′(V′,E′)和G(V,E)中,點vi的內(nèi)連接率表示為Pin(vi),外連接率表示為Pout(vi),計算公式分別為:

(7)

Pout(vi)=1-Pin(vi)

(8)

其中,n表示vi的內(nèi)連接節(jié)點數(shù),N(vi)表示vi的內(nèi)外連接節(jié)點數(shù)之和。

4.1 相似概念結(jié)構(gòu)圖的圖熵處理方法

若設(shè)同領(lǐng)域相似概念結(jié)構(gòu)圖中某概念節(jié)點ci的熵值[18-19]為e(ci),結(jié)合信息熵[20]公式和ci的內(nèi)外連接節(jié)點,有:

e(ci)=-Pin(ci)lbPin(ci)-Pout(ci)lbPout(ci)

(9)

文獻[9]指出,圖熵可定義為所有節(jié)點的熵值之和,即:

(10)

若每次聚類后得到的e(G)最小,則此時同領(lǐng)域相似概念聚類為最優(yōu)。圖3中虛線框內(nèi)為經(jīng)過若干步聚類后得到的最優(yōu)聚類集合,以加入c4概念節(jié)點為例,判斷當前e(G)的變化情況。結(jié)合上文公式可知:加入c4前,計算得到e(c1)=0.92,e(c2)=e(c3)=1,e(c4)=0.81,e(c5)=e(c6)=e(c7)=e(cn)=0,則e(G)=3.73;加入c4后,e(c1)=e(c2)=e(c3)=0,e(c4)=0.81,e(c5)=1,e(c6)=e(c7)=e(cn)=0,此時e(G)=1.81。由此可見:加入c4可使圖熵減小,聚類結(jié)果優(yōu)化;反之,若使圖熵e(G)增大,則拒絕加入c4。

圖3 聚類過程中圖熵e(G)變化示意圖

4.2 基于圖熵的領(lǐng)域概念聚類優(yōu)化算法

從給定的圖G中任意選取一個概念節(jié)點ci作為起始點,結(jié)合最大信息熵原理和圖熵最小化計算公式,最終形成一個滿足同領(lǐng)域Di最優(yōu)概念聚類的子圖G′ (概念集合),具體算法如下:

輸入含有各領(lǐng)域概念的文本文檔

輸出領(lǐng)域Di的概念聚類集合表

1.根據(jù)領(lǐng)域Di給定的概念,抽取文本文檔中的同領(lǐng)域相似概念,構(gòu)建領(lǐng)域的相似概念結(jié)構(gòu)圖G(V,E)

2.令V′=?

3.For 在G中任意選取一個節(jié)點ci?V′作為聚類起始點 do

4.{遍歷ci的所有鄰居節(jié)點,并與ci形成一個聚類子圖G′

5.For G′中的V′≠? do

6.{If 刪除G′中的cj后e(G′)變小

7.G′.Delete(cj)

8.Else Continue}

9.For G′外存在V′的鄰居節(jié)點 do

10.{If 加入G′外的ck后e(G′)變小

11.G′.Add(ck)

12.Else Continue}

13.Return List(G′)}

在給定具有各領(lǐng)域概念的文本中,利用文獻[2]提出的領(lǐng)域概念相關(guān)度和一致度計算公式抽取領(lǐng)域概念,并結(jié)合概念相似度綜合計算公式,構(gòu)建同領(lǐng)域相似概念的相似度矩陣,并將其轉(zhuǎn)化為對應(yīng)的圖關(guān)系,通過圖熵理論優(yōu)化聚類結(jié)果。由于在此過程中聚類的對象是由文本文檔構(gòu)建的同領(lǐng)域相似概念結(jié)構(gòu)圖,因此聚類后原文檔中的概念并未刪除,使再次聚類某領(lǐng)域概念時仍可以抽取已被聚類過的概念,從而解決領(lǐng)域概念重疊問題。

該算法首先任選圖G中的某個節(jié)點ci并遍歷其鄰居節(jié)點構(gòu)建子圖G′,此過程時間復雜度為O(n);然后計算影響G′中圖熵值增大的節(jié)點,并做刪除操作,此過程時間復雜度為O(n×m);最后增加G′外使圖熵減小的鄰居點,此過程時間復雜度為O(n×p)。所以,算法總的時間復雜度為O(n×m+n×p),即O(n2)。

5 實驗與結(jié)果分析

本文設(shè)計基于圖熵極值化理論的領(lǐng)域概念聚類方法,旨在對傳統(tǒng)概念聚類方法在聚類查準率(Precision)上的優(yōu)化以及對概念重疊問題的處理,從而提高查全率(Recall)。所以,本文從領(lǐng)域概念的查準率和查全率以及綜合評估指標F值3個方面將其與傳統(tǒng)領(lǐng)域概念聚類方法進行對比。

本文實驗環(huán)境是在Windows10下搭建的實驗平臺,主要包括Microsoft.NET framework和SQL Server 2012 database,使用C#語言實現(xiàn)。選擇由全國科學技術(shù)名詞審定委員會審定公布的領(lǐng)域概念集合(http://www.cnctst.cn/)作為實驗數(shù)據(jù)集,從中選取12個不同的領(lǐng)域概念各500個,將其混合后再以逐次增加數(shù)據(jù)的方式分為4組實驗數(shù)據(jù)集,分別為800個、1 200個、1 800個和2 200個領(lǐng)域概念。

由于本文貢獻點在于處理中文領(lǐng)域概念聚類和聚類過程中的概念重疊問題,因此與文獻[1,3,7]方法在領(lǐng)域概念查準率、查全率以及綜合評估指標F-Measure值3個方面進行對比,并使用文獻[2]中的計算公式,如式(11)～式(13)所示:

(11)

(12)

(13)

其中,N為聚類后屬于領(lǐng)域Di的概念個數(shù),M為聚類后領(lǐng)域Di中的概念個數(shù),A表示所有文檔的概念中屬于Di的概念個數(shù)。

通過實驗獲得的聚類結(jié)果以及Precision和Recall指標計算公式,得到表1和表2所示的對比結(jié)果。

表1 4種方法的查準率對比

表2 4種方法的查全率對比

為減小實驗比較誤差,將表1和表2中的查準率與查全率數(shù)據(jù)結(jié)合式(13)計算出4種方法在混合領(lǐng)域概念聚類上的F值,比較結(jié)果如圖4所示。

圖4 4種方法的F值對比

從圖4可以看出,4種方法在第一次實驗時,相互間的F值差距不明顯,最低的文獻[1]方法為0.703,而最高的則是本文方法達到0.784。隨著實驗的進行,本文方法相比其他方法優(yōu)勢逐漸明顯,在數(shù)據(jù)量為2 200的第4次實驗中,本文方法優(yōu)勢最為明顯,與基于傳統(tǒng)K-Means劃分方法的文獻[1]方法相比F值提高近30%,同時基于密度計算的文獻[3]方法和基于距離計算的文獻[7]方法相較于本文方法F值下降幅度也較為明顯。

經(jīng)分析每組實驗數(shù)據(jù)可知,隨著概念數(shù)據(jù)量增加,概念重疊情況也隨之增多,文獻[1]方法對于該問題無法處理,文獻[3,7]方法對其稍有作用,但文中并未提及和考慮該問題,沒有提出有針對性的解決方案。本文方法在概念聚類過程中能夠在保證原有聚類效率的前提下解決重疊問題,提高了概念聚類性能。

6 結(jié)束語

本文針對領(lǐng)域概念聚類過程中的概念重疊現(xiàn)象,提出基于圖熵極值理論的領(lǐng)域概念聚類方法。利用圖熵原理和在生成概念聚類的過程中不刪除原文本領(lǐng)域概念的方法,優(yōu)化聚類結(jié)果,提升查全率、查準率及F值。實驗結(jié)果驗證了該方法的有效性。但本文方法中閾值的選取仍為人工設(shè)定,受到主觀因素影響,因此,下一步將研究不同閾值的選取對聚類性能的影響,并設(shè)計閾值自動生成機制。