基于百科詞條的本體概念聚類方法研究

于 娟，曹 曉

(福州大學(xué)經(jīng)濟(jì)與管理學(xué)院 福州 350116)

基于百科詞條的本體概念聚類方法研究

于 娟，曹 曉

(福州大學(xué)經(jīng)濟(jì)與管理學(xué)院 福州 350116)

該文面向本體關(guān)系集合的自動(dòng)構(gòu)建，提出一種基于百科詞條的本體概念聚類方法，用于發(fā)現(xiàn)領(lǐng)域概念之間的語(yǔ)義關(guān)系。在給定領(lǐng)域本體概念集合的條件下，該方法首先獲取相關(guān)的百科詞條并建立每一概念的向量模型，然后根據(jù)距離判別法進(jìn)行概念聚類，得到概念間的相近關(guān)系。采用該方法對(duì)3個(gè)領(lǐng)域中的領(lǐng)域概念集合進(jìn)行聚類，實(shí)驗(yàn)結(jié)果表明，該文方法比傳統(tǒng)聚類算法有更好的聚類結(jié)果，有助于概念間關(guān)系的自動(dòng)獲取和領(lǐng)域本體自動(dòng)構(gòu)建。

概念聚類; 距離判別法; 百科詞條; 本體概念; 本體學(xué)習(xí)

作為語(yǔ)義Web和知識(shí)管理系統(tǒng)的關(guān)鍵基礎(chǔ)，本體描述某個(gè)領(lǐng)域甚至更廣范圍內(nèi)的概念以及概念之間的關(guān)系，使得這些概念和關(guān)系在共享的范圍內(nèi)具有共同認(rèn)可的、明確的、唯一的定義，以供人之間以及機(jī)器之間進(jìn)行交流[1]。目前，本體在語(yǔ)義檢索、知識(shí)管理和人工智能等相關(guān)領(lǐng)域得到了廣泛的理論和應(yīng)用研究。

本體學(xué)習(xí)是采用機(jī)器學(xué)習(xí)方法(半)自動(dòng)構(gòu)建本體的過(guò)程。根據(jù)學(xué)習(xí)的本體對(duì)象不同，本體學(xué)習(xí)主要包括概念學(xué)習(xí)、關(guān)系學(xué)習(xí)和公理學(xué)習(xí)。其中，關(guān)系學(xué)習(xí)試圖采用計(jì)算機(jī)(半)自動(dòng)地快速地發(fā)現(xiàn)概念間關(guān)系。在這個(gè)信息迅速增長(zhǎng)的時(shí)代，新概念層出不窮，概念間關(guān)系發(fā)生著變化，因此關(guān)系學(xué)習(xí)是當(dāng)前本體研究的重點(diǎn)和熱點(diǎn)之一。

本文研究一種基于百科詞條的本體概念聚類方法，用于支持自動(dòng)發(fā)現(xiàn)概念間的關(guān)系。該方法首先依據(jù)百科詞條建立概念的向量模型，然后根據(jù)距離判別法進(jìn)行概念聚類，進(jìn)而獲取概念間的相關(guān)關(guān)系。

1 研究現(xiàn)狀

聚類是將對(duì)象的集合分成相似的對(duì)象類的過(guò)程[2]。概念聚類是將概念集合分成相似的幾類的過(guò)程。由于同一類的術(shù)語(yǔ)會(huì)在相同的上下文出現(xiàn)，所以可以通過(guò)聚類算法將上下文相似的術(shù)語(yǔ)進(jìn)行聚類，進(jìn)而發(fā)現(xiàn)概念間關(guān)系。概念聚類算法主要分為：劃分聚類、層次聚類、形式概念分析和基于圖結(jié)構(gòu)的聚類。

1) 劃分聚類。首先，構(gòu)建對(duì)象的k個(gè)劃分，然后采用迭代重定位技術(shù)，嘗試通過(guò)對(duì)象在組間移動(dòng)來(lái)改進(jìn)劃分。典型的劃分方法有k均值(k-means)和k中心點(diǎn)，一般都是對(duì)k-means算法的優(yōu)化。文獻(xiàn)[3]在計(jì)算聚類中心時(shí)，先刪掉向量與平均向量相差超過(guò)10%的術(shù)語(yǔ)，再重新計(jì)算每個(gè)類的平均向量?jī)?yōu)化聚類中心。文獻(xiàn)[4]依據(jù)類中元素分布計(jì)算類中聚集程度最大的p個(gè)概念，將距離這p個(gè)概念的平均向量最近的概念作為類的新中心，優(yōu)化聚類中心。

2) 層次聚類。對(duì)給定概念集合進(jìn)行層次的分解，構(gòu)造一棵聚類樹(shù)。層次聚類算法分為凝聚層次聚類和分裂層次聚類。文獻(xiàn)[5]通過(guò)內(nèi)部和外部凝聚層次聚類進(jìn)行概念聚類。文獻(xiàn)[6]對(duì)層次聚類算法適應(yīng)性進(jìn)行改造，通過(guò)計(jì)算層次的耦合-內(nèi)聚比，計(jì)算類數(shù)目的分布密度。文獻(xiàn)[7]計(jì)算最小增加值或最大減少值作為概念層次聚類的合并策略。

3) 形式概念分析。使用二元關(guān)系來(lái)表示領(lǐng)域中的形式背景，從形式背景中抽取概念層，即概念格，通過(guò)概念格結(jié)構(gòu)將對(duì)象分層。文獻(xiàn)[8]構(gòu)造模糊概念格，對(duì)對(duì)象進(jìn)行模糊概念聚類。文獻(xiàn)[9]采用模糊k-means聚類算法約簡(jiǎn)概念格。

4) 基于圖結(jié)構(gòu)的聚類。文獻(xiàn)[10]提出遍歷樹(shù)的螞蟻聚類算法對(duì)術(shù)語(yǔ)進(jìn)行聚類，用標(biāo)準(zhǔn)化的谷歌距離和Wikipedia測(cè)量術(shù)語(yǔ)間距離和相似度。文獻(xiàn)[11]依據(jù)詞性樹(shù)路徑長(zhǎng)度、術(shù)語(yǔ)詞匯相同詞、連續(xù)詞、開(kāi)始結(jié)束詞和術(shù)語(yǔ)概念層次樹(shù)路徑長(zhǎng)度計(jì)算概念相似度，采用SOM自組織神經(jīng)網(wǎng)絡(luò)進(jìn)行概念聚類。

前述研究中，聚類算法大多需要根據(jù)實(shí)驗(yàn)或者經(jīng)驗(yàn)來(lái)設(shè)定閾值，而閾值對(duì)聚類結(jié)果的影響很大。閾值設(shè)置過(guò)大，可能丟失有趣的關(guān)聯(lián)；閾值設(shè)置過(guò)小，可能產(chǎn)生大量的弱相關(guān)的交叉支持模式關(guān)聯(lián)。并且，閾值的設(shè)定存在不確定因素，設(shè)置適當(dāng)?shù)拈撝递^為困難。另一方面，根據(jù)語(yǔ)境構(gòu)建概念模型以計(jì)算概念間相似度時(shí)，少有研究將整個(gè)語(yǔ)料作為共現(xiàn)窗口。因此，本文以百科詞條為語(yǔ)料，研究了一種無(wú)監(jiān)督的概念聚類方法。

2 基于百科詞條的概念聚類

本文提出一種基于百科詞條的本體概念聚類方法。該方法的輸入是：領(lǐng)域本體的概念集合、概念的百科詞條；輸出是：候選本體關(guān)系集合。方法流程圖如圖1所示。

對(duì)圖1中各個(gè)模塊的說(shuō)明：

1) 領(lǐng)域概念集合即領(lǐng)域本體的概念集合，是領(lǐng)域?qū)Ｓ懈拍畹娜?，是?gòu)建領(lǐng)域本體的基礎(chǔ)。領(lǐng)域概念集合可以由領(lǐng)域?qū)＜胰斯そo出，也可借助一些機(jī)器學(xué)習(xí)方法采用人機(jī)結(jié)合的方式獲得，例如，文獻(xiàn)[12]提出或改進(jìn)的一系列領(lǐng)域概念學(xué)習(xí)方法。

圖1 基于百科詞條的概念聚類方法流程圖

2) 百科詞條獲取模塊。對(duì)概念集合中的每一個(gè)概念查找其百科詞條并進(jìn)行預(yù)處理，獲取其中的文本信息。

3) 相關(guān)百科詞條是領(lǐng)域概念的百科詞條，可以是百度百科、維基百科等詞條。

4) 概念向量建模模塊。對(duì)百科詞條進(jìn)行分詞與信息熵過(guò)濾，統(tǒng)計(jì)共現(xiàn)詞語(yǔ)及其詞頻建立領(lǐng)域概念的量化模型。

5) 概念向量模型表示概念的向量模型，其中每一個(gè)分量是一個(gè)共現(xiàn)詞的詞頻。

6) 距離判別概念聚類模塊。采用馬氏距離計(jì)算概念間距離，重心距離計(jì)算概念到類中心的距離，經(jīng)過(guò)多次迭代直至聚類結(jié)果不再改變。

7) 概念類是概念聚類所得的聚類結(jié)果。

2.1 概念向量建模

概念向量建模的輸入是：領(lǐng)域本體的概念集合、概念的百科詞條；輸出是：概念向量模型。該模塊對(duì)于每一個(gè)領(lǐng)域概念，通過(guò)對(duì)概念百科詞條的預(yù)處理，計(jì)算信息熵過(guò)濾詞語(yǔ)，所得概念向量模型中的每個(gè)分量為過(guò)濾后詞語(yǔ)的詞頻。

該模塊首先將概念的百科詞條進(jìn)行語(yǔ)料預(yù)處理；然后計(jì)算每個(gè)概念的共現(xiàn)詞語(yǔ)wk和詞頻fk(1≤k≤ni)。然后使用左右信息熵對(duì)共現(xiàn)詞語(yǔ)進(jìn)行過(guò)濾，并選擇詞頻最高的前n個(gè)詞語(yǔ)。左、右信息熵公式如下所示：P(lw| w)表示在出現(xiàn)詞語(yǔ)w的情況下，w的左鄰接字是l的條件概率；P(wr| w)表示在出現(xiàn)詞語(yǔ)w的情況

式中，l是詞語(yǔ)w的左鄰接字；r是w的右鄰接字；下，w的右鄰接字是r的條件概率；LE(w)為詞語(yǔ)w的左信息熵；RE(w)為詞語(yǔ)w的右信息熵；左、右信息熵越大，則w越獨(dú)立。綜合考慮左右信息熵，得到如下信息熵公式：

對(duì)百科詞條語(yǔ)料中不獨(dú)立的詞語(yǔ)進(jìn)行過(guò)濾，最后每個(gè)概念的概念向量模型表示為：

該算法建立的概念向量模型的時(shí)間復(fù)雜度約為O(n×(m+k ))，其中，n為領(lǐng)域概念的數(shù)量，m為詞語(yǔ)數(shù)量，k為過(guò)濾后的詞語(yǔ)數(shù)量。2.2 距離判別概念聚類

距離判別概念聚類的輸入是：2.1節(jié)所得到的概念向量模型；輸出是：概念類，即存在關(guān)系的概念的集合。本模塊采用馬氏距離計(jì)算概念間的距離，采用重心距離計(jì)算概念到類中心的距離。為敘述方便，先定義距離判別法所用到的數(shù)學(xué)符號(hào)和公式。

設(shè)有k個(gè)類(cluster)c1, c2,… ,ck，它們的均值分別為μ(1),μ(2),…,μ(k)，方差陣分別為∑1,∑2,…,，是來(lái)自類ca的容量為na的概念向量(a=1,2,…,k )。類ca的均值μ(a)和方差陣∑a(a=1,2,…,k )估計(jì)公式如下：

為了描述概念間的相似程度，采用馬氏距離計(jì)算概念之間的距離：

式中，x和y表示概念向量；?1∑ 是類方差矩陣的逆矩陣。

采用重心距離計(jì)算概念與類中心的距離，計(jì)算公式如下：

式中，μ是類C的均值；y是任意一個(gè)概念向量。

距離判別概念聚類方法步驟如下：

1) 人為地將概念分為k個(gè)類 c1, c2,…,ck，計(jì)算每個(gè)類ca的均值(a)μ和方差陣；

2) 采用馬氏距離計(jì)算概念之間的距離，采用重心距離計(jì)算概念與類中心的距離；

3) 將距離類ca近的概念歸為該類，經(jīng)過(guò)多次迭代直至判別結(jié)果不再發(fā)生變化，得到最終的聚類結(jié)果。

該算法形成概念聚類的時(shí)間復(fù)雜度約為O(kmtn2)，其中，n為領(lǐng)域概念的數(shù)量，m為詞語(yǔ)數(shù)量，k為類的數(shù)量，t為迭代次數(shù)。

3 實(shí)驗(yàn)分析

為了驗(yàn)證本文提出的基于百科詞條的本體概念聚類方法的性能，采用該方法及多篇文獻(xiàn)所使用的k-means聚類算法分別對(duì)3個(gè)領(lǐng)域本體的概念集合進(jìn)行聚類。實(shí)驗(yàn)領(lǐng)域包括：電子商務(wù)領(lǐng)域、知識(shí)管理領(lǐng)域和管理信息系統(tǒng)領(lǐng)域。實(shí)驗(yàn)輸入數(shù)據(jù)為由全國(guó)科學(xué)技術(shù)名詞審定委員會(huì)[13]審定公布的領(lǐng)域概念集合，實(shí)驗(yàn)輸出的概念聚類結(jié)果與領(lǐng)域?qū)＜沂止澐值慕Y(jié)果進(jìn)行比較。

按照文獻(xiàn)[14]和[15]設(shè)定本文的實(shí)驗(yàn)性能指標(biāo)，定義某一個(gè)類ci的類匹配度為：

式中，m(ci)表示ci和c′j之間的一致程度，0≤m(ci)≤1；ci是由領(lǐng)域?qū)＜胰斯ご_立的領(lǐng)域概念主題劃分中的一個(gè)主題，i=1,2,…,n，n為主題個(gè)數(shù)；cj′為由聚類方法自動(dòng)得到的一個(gè)類，為ci和cj′中相同概念的個(gè)數(shù)。

定義聚類結(jié)果C′的匹配度為：

式中，C和C′分別表示領(lǐng)域?qū)＜胰斯ご_立的領(lǐng)域概念集合的主題劃分和聚類方法得到的結(jié)果；m(C, C′)反映了兩種結(jié)果C和C′的一致程度，0≤m(C, C′)≤1，l代表完全一致，0代表完全不一致；n為領(lǐng)域?qū)＜胰斯ご_立的領(lǐng)域概念主題劃分的主題個(gè)數(shù)；P(ci)是ci發(fā)生的概率。

圖2～圖4展示了本文方法及k-means對(duì)3個(gè)領(lǐng)域概念集合的聚類結(jié)果與領(lǐng)域?qū)＜胰斯澐纸Y(jié)果的類匹配度。

表1采用4項(xiàng)經(jīng)典的聚類性能指標(biāo)對(duì)本文方法及k-means的聚類結(jié)果進(jìn)行比較，并統(tǒng)計(jì)了3個(gè)領(lǐng)域的本文方法及k-means的聚類結(jié)果與領(lǐng)域?qū)＜胰斯ご_立的領(lǐng)域概念集合的主題劃分的匹配度。

圖4 管理信息系統(tǒng)領(lǐng)域概念聚類情況

表1 3個(gè)領(lǐng)域聚類結(jié)果比較

表1中設(shè)每個(gè)類發(fā)生的概率相同，“本文方法”一列的數(shù)據(jù)為使用本文提出的概念聚類方法所得到的本體關(guān)系，“k-means”一列的數(shù)據(jù)為使用k-means聚類算法得到的本體關(guān)系。在不影響比較結(jié)果的情況下，將表1中的數(shù)據(jù)四舍五入。對(duì)評(píng)價(jià)指標(biāo)的說(shuō)明如下：

1) 候選關(guān)系數(shù)表示自動(dòng)學(xué)習(xí)所得到的候選本體關(guān)系的數(shù)目。

2) 準(zhǔn)確數(shù)表示候選本體關(guān)系中被領(lǐng)域?qū)＜胰斯ご_立的屬于同一主題的數(shù)目。

3) 關(guān)系數(shù)表示領(lǐng)域?qū)＜胰斯ご_立的本體關(guān)系集合中所有本體關(guān)系的數(shù)目。

4) Precision=準(zhǔn)確數(shù)/候選關(guān)系數(shù)。

5) Recall=準(zhǔn)確數(shù)/關(guān)系數(shù)。

6) F-Score是Precision和Recall的調(diào)和平均數(shù)。F-Score計(jì)算公式：

7) RI (rand index)是隨機(jī)一致性指標(biāo)，用來(lái)度量聚類結(jié)果與領(lǐng)域?qū)＜胰斯ご_立的概念所屬主題分布的相似度。RI計(jì)算公式：

式中，TP表示同一類的概念被分到同一個(gè)類，即準(zhǔn)確數(shù)；TN表示不同類的概念被分到不同類；FP表示不同類的概念被分到同一個(gè)類；FN表示同一類的概念被分到不同類。

從表1的比較結(jié)果可以看出，對(duì)3個(gè)領(lǐng)域本體的概念集合進(jìn)行聚類時(shí)，本文方法比k-means總體聚類匹配度高而且準(zhǔn)確率高，說(shuō)明了本文方法的有效性。

4 結(jié) 束 語(yǔ)

本文提出了一種基于百科詞條的本體概念聚類方法，用于支持本體關(guān)系的自動(dòng)獲取。在給定領(lǐng)域概念集合的情況下，該方法首先獲取概念的百科詞條并從中獲取文本信息，然后進(jìn)行分詞和信息熵過(guò)濾，增加建立的概念向量模型，最后采用距離判別法進(jìn)行概念聚類。該方法不必確定閾值，使聚類算法更加自動(dòng)化。實(shí)驗(yàn)結(jié)果表明該概念聚類方法有較好的聚類結(jié)果。

今后的研究方向?qū)⑹?，改進(jìn)概念向量建模過(guò)程中的詞語(yǔ)選取方法以及向量建模算法，在保證準(zhǔn)確率的基礎(chǔ)上提高召回率。

[1] GRUBER T R. A translation approach to portable ontology specifications[J]. Knowledge Acquisition, 1993, 5(2): 199-220.

[2] HAN Jia-wei, KAMBER M, PEI Jian. Data mining: Concepts and techniques[M]. 3rd ed. Beijing: China Machine Press, 2012: 443-444.

[3] 徐德智, JUNAID. Cluster-Merge本體構(gòu)造算法[J]. 計(jì)算技術(shù)與自動(dòng)化, 2010, 59(3): 49-52. XU De-zhi, JUNAID. An ontology learning based on documents clustering[J]. Computing Technology and Automation, 2010, 59(3): 49-52.

[4] 胡云飛. 本體學(xué)習(xí)中關(guān)系獲取的研究[D]. 西安: 西安建筑科技大學(xué), 2012.

HU Yun-fei. Research on relations acquisition of ontology learning[D]. Xi’an: Xi’an University of Architecture and Technology, 2012.

[5] LEUNG K W T, LEE D L. Deriving concept-based user profiles from search engine logs[J]. IEEE Transactions on Knowledge and Data Engineering, 2010, 22(7): 969-982.

[6] 何琳, 侯漢清. 基于統(tǒng)計(jì)自然語(yǔ)言處理技術(shù)的領(lǐng)域本體半自動(dòng)構(gòu)建研究[J]. 情報(bào)學(xué)報(bào), 2009, 28(2): 201-207.

HE Lin, HOU Han-qing. Research on semi-automatic construction of domain ontology based on statistical NLP technique[J]. Journal of the China Society for Scientific and Technical Information, 2009, 28(2): 201-207.

[7] CHEN Shi-xi, WANG Hai-xun, ZHOU Shui-geng. Concept clustering of evolving data[C]//IEEE 25th International Conference on Data Engineering. Shanghai, China: IEEE Computer Society, 2009: 1327-1330.

[8] THO Q T, HUI S C, FONG A C M, et al. Automatic fuzzy ontology generation for semantic web[J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(6): 842-856.

[9] KUMAR C A, SRINIVAS S. Concept lattice reduction using fuzzy k-means clustering[J]. Expert Systems with Applications, 2010, 37(3): 2696-2704.

[10] WONG W, LIU W, BENNAMOUN M. Tree-traversing ant algorithm for term clustering based on featureless similarities[J]. Data Mining and Knowledge Discovery, 2007, 15(3): 349-381.

[11] LEE C S, KAO Y F, KUO Y H, et al. Automated ontology construction for unstructured text documents[J]. Data & Knowledge Engineering, 2007, 60(3): 547-566.

[12] 于娟. 基于文本的領(lǐng)域本體學(xué)習(xí)方法及其應(yīng)用研究[D].大連: 大連理工大學(xué), 2010.

YU Juan. Learning domain ontologies from Chinese text corpora[D]. Dalian: Dalian University of Technology, 2010.

[13] 全國(guó)科學(xué)技術(shù)名詞審定委員會(huì). 全國(guó)科學(xué)技術(shù)名詞審定委員會(huì)簡(jiǎn)介[EB/OL]. [2016-12-24]. http://www.cnctst.cn/.

China National Committee for Terms in Sciences and Technologies. An introduction of China national committee for terms in sciences and technologies [EB/OL]. [2016-12-24]. http://www.cnctst.cn/.

[14] 劉金嶺. 基于《現(xiàn)代漢語(yǔ)語(yǔ)義分類詞典》的文本聚類方法[J]. 情報(bào)雜志, 2010, 29(11): 170-173.

LIU Jin-ling. Text clustering method based on thesaurus of modern Chinese[J]. Journal of Intelligence, 2010, 29(11): 170-173.

[15] 張明衛(wèi), 劉瑩, 張斌, 等. 一種基于概念的數(shù)據(jù)聚類模型[J]. 軟件學(xué)報(bào), 2009, 20(9): 2387-2396.

ZHANG Ming-wei, LIU Ying, ZHANG Bin, et al. Concept-based data clustering model[J]. Journal of Software, 2009, 20(9): 2387-2396.

編 輯 蔣 曉

Ontology Concepts Clustering Based on Encyclopedia Entries

YU Juan and CAO Xiao

(School of Economics and Management, Fuzhou University Fuzhou 350116)

To build the set of ontology relations automatically, this paper presents a preliminary study on a concept clustering method based on encyclopedia entries of obtaining semantic relations among concepts. Given a set of domain ontology concepts, this method clusters concepts in 3 steps: 1) obtaining encyclopedia entries; 2) modeling each of the concepts into a vector; 3) clustering concepts using the distance discrimination method. Clustering experiments on 3 sets of domain ontology concepts demonstrate that the proposed method shows better results compared with classical clustering methods and has good potentials for identifying related concepts automatically in the ontology building tasks.

concept clustering; distance discrimination method; encyclopedia entries; ontology concept; ontology learning

TP181

A

10.3969/j.issn.1001-0548.2017.03.026

2015 ? 10 ? 19；

2016 ? 05 ? 31

國(guó)家自然科學(xué)基金(71201032)；福建省社會(huì)科學(xué)規(guī)劃項(xiàng)目(FJ2016C044)

于娟(1981 ? )，女，博士，副教授，主要從事領(lǐng)域本體、信息管理方面的研究.