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

安敬民,李冠宇

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

0 概述

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

同領(lǐng)域概念聚類的傳統(tǒng)方法主要有基于劃分、基于層次、基于形式概念分析以及基于語義距離的方法。基于劃分的方法需要人為設(shè)定劃分的個(gè)數(shù)和窮舉所有可能的劃分情況,并給定遞歸算法將概念從一個(gè)劃分移到另一劃分來提高劃分結(jié)果的準(zhǔn)確性,典型算法為K-means[1-2]。基于層次的方法是將復(fù)雜概念網(wǎng)中每一個(gè)概念節(jié)點(diǎn)視為一個(gè)獨(dú)立的聚類,利用領(lǐng)域一致度計(jì)算公式,迭代合并同領(lǐng)域概念,最終將復(fù)雜概念網(wǎng)分為多個(gè)領(lǐng)域的概念網(wǎng),其中基于分布密度計(jì)算[3]的方法為主要代表。基于形式概念分析的方法主要采用概念格將對象分層,模糊概念格[4]和模糊K-means[5]是其中的代表方法。基于語義距離的方法主要通過計(jì)算領(lǐng)域概念在概念樹中的距離進(jìn)行聚類,目前有基于遍歷樹的螞蟻聚類算法[6]和百科詞條的本體概念聚類方法[7]等。文獻(xiàn)[1-2]采用優(yōu)化后的K-means方法選取并優(yōu)化聚類中心,結(jié)合設(shè)定的聚類閾值實(shí)現(xiàn)同領(lǐng)域概念的聚類。文獻(xiàn)[3]利用層次的耦合內(nèi)聚比得到類數(shù)目的分布密度,通過密度聚類實(shí)現(xiàn)最終的概念聚類。文獻(xiàn)[4-5]利用形式概念分析對概念的模糊處理能力,擴(kuò)大了概念聚類范圍,增強(qiáng)了聚類效果。文獻(xiàn)[6]通過計(jì)算領(lǐng)域概念間的谷歌距離以及Wikipedia的距離和相似度實(shí)現(xiàn)聚類。文獻(xiàn)[7]利用馬氏距離得到概念向量間的語義距離,并通過多次迭代完成百科詞條中的概念聚類。

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

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

1 問題描述與定義

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

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

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

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

2 基于WordNet的概念相似度綜合計(jì)算

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

2.1 概念間相似度計(jì)算方法

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

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

(1)

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

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

(2)

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

(3)

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

(4)

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

(5)

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

2.2 概念間相似度綜合計(jì)算

為提高概念間相似度計(jì)算的精確度,本文從多角度考慮對概念相似度有影響的因素,并將其以權(quán)重加和的形式作為綜合計(jì)算結(jié)果。為使綜合計(jì)算結(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],并利用降維過程中得到的特征值計(jì)算主成分貢獻(xiàn)率(q1,q2,q3,q4,q5),最終得到概念間相似度綜合計(jì)算公式為:

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é)中兩個(gè)概念間的同領(lǐng)域綜合相似度KSIM,按照對應(yīng)概念ci和cj兩個(gè)維度來構(gòu)建概念相似度矩陣:

RSIM(ci,cj)=

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

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

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

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

將簡化得到的概念相似度矩陣R′SIM轉(zhuǎn)化為概念間的關(guān)系無向圖G(V,E),其中,V表示圖中的概念節(jié)點(diǎn)(頂點(diǎn)),E表示概念節(jié)點(diǎn)間的邊。若在相似度矩陣R′SIM中KSIM(ci,cj)=1,則概念ci、cj對應(yīng)的頂點(diǎn)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ā),將圖中的各個(gè)節(jié)點(diǎn)視為一個(gè)整體,而沒有主客之分,即在本文的聚類過程中,區(qū)別以往傳統(tǒng)的以聚類質(zhì)心為主的聚類方法,而是將已聚類的節(jié)點(diǎn)作為整體,通過圖熵最小化理論計(jì)算出下一步的最優(yōu)聚類結(jié)果。利用圖熵的聚類方法可以在每次聚類結(jié)果輸出后保留原文本文檔中已被聚類到某領(lǐng)域的概念,從而解決概念重疊問題。

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

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

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

(7)

Pout(vi)=1-Pin(vi)

(8)

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

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

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

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

(9)

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

(10)

若每次聚類后得到的e(G)最小,則此時(shí)同領(lǐng)域相似概念聚類為最優(yōu)。圖3中虛線框內(nèi)為經(jīng)過若干步聚類后得到的最優(yōu)聚類集合,以加入c4概念節(jié)點(diǎn)為例,判斷當(dāng)前e(G)的變化情況。結(jié)合上文公式可知:加入c4前,計(jì)算得到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,此時(shí)e(G)=1.81。由此可見:加入c4可使圖熵減小,聚類結(jié)果優(yōu)化;反之,若使圖熵e(G)增大,則拒絕加入c4。

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

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

從給定的圖G中任意選取一個(gè)概念節(jié)點(diǎn)ci作為起始點(diǎn),結(jié)合最大信息熵原理和圖熵最小化計(jì)算公式,最終形成一個(gè)滿足同領(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中任意選取一個(gè)節(jié)點(diǎn)ci?V′作為聚類起始點(diǎn) do

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

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

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

7.G′.Delete(cj)

8.Else Continue}

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

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

11.G′.Add(ck)

12.Else Continue}

13.Return List(G′)}

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

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

5 實(shí)驗(yàn)與結(jié)果分析

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

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

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

(11)

(12)

(13)

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

通過實(shí)驗(yàn)獲得的聚類結(jié)果以及Precision和Recall指標(biāo)計(jì)算公式,得到表1和表2所示的對比結(jié)果。

表1 4種方法的查準(zhǔn)率對比

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

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

圖4 4種方法的F值對比

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

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

6 結(jié)束語

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