羅年潔,呂 釗

(華東師范大學計算機科學技術系,上海 200241)

1 概述

領域概念層次結構是對特定領域的概念特征化描述,可反映該領域內的知識和概念關系。它不僅有助于知識推理,促進信息分類、搜索與導航,而且有助于人或機器理解一個高度集中或快速變化的領域[1-2]。一般地,領域概念層次構建主要有2 個部分：領域概念間關系抽取與層次構建?，F有面向領域的概念自動構建方法主要有2 類：基于知識庫的方法和基于原始數據的方法。

基于知識庫的方法是通過已有的結構化或半結構化的知識網獲取領域詞對關系,然后構建概念層次。例如,文獻[3]使用WordNet 構建餐飲系統(tǒng)；文獻[4]首先從維基百科抽取領域詞對關系,然后采用有向無環(huán)圖(Directed Acyclic Graph,DAG)算法構建領域概念圖,最后通過深度遍歷來建立層次結構；文獻[5]使用其構建的知識庫Probase 獲取領域概念關系,再對給定的關鍵詞集使用貝葉斯玫瑰樹(Bayesian Rose Tree,BRT)[6]來構建汽車保險領域的層次結構。

基于原始數據的方法主要依賴于純文本文檔,如文獻[7]基于頻率來統(tǒng)計詞對的共現概率,大于一定閾值則具有上下位關系,然后根據其算法(Fuzzy OntoExt)構建概念圖；文獻[8]基于形式概念分析的研究,首先采用FCA 算法構建概念格,然后使用KMeans 算法對概念進行聚類。

基于知識庫的方法獲取領域概念關系比較方便且準確率高,然而隨著領域發(fā)展,會更新很多詞意,并產生新詞,知識庫拓展性弱,并未能實時反饋這些改變,這樣會導致領域概念間關系的查全率降低[9]?；谠紨祿姆椒〞雎粤说皖l領域詞。FCA 算法比較適用于對象-屬性類型的領域,最后得到的是領域的概念格,而不是一個直接的領域層次結構。

國內開展了中文概念層次結構構建研究,如文獻[10]構建了中文詞典的層次結構,其主要是先定義詞典中詞的語義框架,取得了較好的效果,但該方法擴展性弱,不易移植到其他領域。文獻[11]在獲取領域術語后,采用一種自頂向下的聚類算法獲取領域概念間的層間關系,這種方法的聚類層數需要人工確定,無法自動獲取完整的層次關系。

現有的領域概念層次自動構建方法主要存在以下兩方面的問題：(1)領域概念間的關系查全率低；(2)構建算法復雜度高。為此,本文提出一種混合的領域概念層次結構自動構建算法(DCTA)

2 混合的領域概念層次結構自動構建算法

DCTA 算法的主要步驟如圖1 所示。

圖1 DCTA 算法流程

本文主要采用全自動方法構建中文領域的分類體系,主要包括關系抽取和層次構建2 個部分。

領域詞對關系的抽取過程如下：(1)輸入領域文檔集與領域關鍵詞詞集,使用“領域詞與上下文”的模式,獲取領域詞對共現的句子；(2)使用句法樹和基于規(guī)則的方法,獲取滿足要求的詞對集；(3)對以上2 個方法獲取的詞對集合進行合并。

層次結構自動構建是對存在關系的領域詞構建層次結構,其步驟如下：(1)輸入關系詞對集,通過改進的BRT 算法對節(jié)點進行合并、吸收和連接操作；(2)將所有的子節(jié)點歸并到一個父節(jié)點下,構建領域層次結構。

2.1 領域概念關系抽取

領域概念是在特定領域文檔頻繁出現、反映該領域共性的特征詞語,具有專指性強、領域區(qū)分度高、領域化代表性強的特點。隨著信息的發(fā)展,領域不斷更新,出現了很多新詞,其中包括大量的復合詞,即多個詞組成的多字概念,對于這些新詞,已有的知識庫未能實時更新,而且復合詞根據構成詞存在一定領域層次關系。根據領域詞對關系的特點,本文使用分治策略對句子中的一些特定語法結構進行預處理,選擇使用句法樹和基于規(guī)則的方法。

由于句法分析是對語言進行深入理解的基礎,它從句子結構上分析領域詞對關系,具有語料處理快、標注方法和算法先進、標注標準和其他語料庫的兼容性較好等優(yōu)點。采用句法樹可以很好地提取領域中詞對間關系。

基于規(guī)則的方法被廣泛應用于關系識別和人名識別[12]等領域,可以最大限度地接近自然語言的句法習慣,從而被快速掌握；其表達方式靈活多樣,能最大限度地表達研究人員的思想；同時也能很好地解決復合詞包含的領域關系。

2.1.1 句法樹分析法

本文采用的句法樹是一個詞匯化的概率上下文無關文法(Probalilistic Context Free Grammar,PCFG)[13]語法分析器,句法分析模型句法樹分析的結果一般表示為樹結構,樹的節(jié)點表示句子的語法單元的名稱,而樹的分叉表示2 個或者多個語法單元組成一個新的、跨度更大的語法單元。

例如對“神州行幸?？ㄊ且豢顚槔夏昕蛻粼O計的具有月費低,親情號碼通話優(yōu)惠的資費套餐。”進行句法分析,其中,“神州行幸?？ā薄ⅰ坝H情號碼”、“資費套餐”是3 個領域詞,從句法樹圖可以得到領域概念關系“神州行幸福卡”是“資費套餐”,其句法分析樹結構如圖2 所示。可以看出,句法樹對句子關系能取得很好的結果,但對于名詞復合短語的關系抽取卻不理想,如“神州行”與“幸?？ā敝g存在著整體與部分關系。名詞復合短語是各種語言中普遍存在的一種語法結構,對信息抽取、機器翻譯等應用有很大的影響,由于句法分析對此類結構的處理不夠理想,本文對名詞復合短語進行專門處理,以降低句法分析的難度。針對漢語名詞復合短語的特點,提出一種基于規(guī)則的名詞復合短語分析方法,以減小此類短語對句法分析的影響。

圖2 句法分析實例

2.1.2 基于規(guī)則的分析法

為了實現對復合短語與其他復雜句式中領域概念關系的識別,本文引入基于規(guī)則的分析法,規(guī)則匹配用于發(fā)現一些文檔中沒有明確說明的關系。隨著領域的不斷拓展,出現了很多復合詞,而且這些復合詞往往單獨在一些語句出現,并未能表示它與領域詞的關系,它往往是多個名詞的組合形成。通過統(tǒng)計一些名詞出現在領域概念的開始或結尾的頻率,高頻詞成為領域詞特定的前綴或后綴。根據語義,這些前綴或后綴詞與復合詞具有上下位關系。比如在手機電信領域中,短信業(yè)務、彩鈴業(yè)務等都含有相同的后綴詞業(yè)務,這些后綴詞業(yè)務表達了領域概念“短信業(yè)務”、“彩鈴業(yè)務”的特性與所屬類別。本文根據領域詞的關系特點制定規(guī)則,如表1 所示。

表1 規(guī)則示例

領域概念包含4 種關系：ISA,Part-Of,Attribute-Of 和Instance-Of。ISA 關系表示類別之間有共同的屬性,用來表示概念的逐步細化,類似于面向對象中的繼承概念；Part-Of 關系表示類別之間是整體和部分的關系；Attribute-Of 表示關系表示某對象是一概念的屬性；Instance-Of 關系表示某對象是一概念的實例。表2 為上述4 種關系類型的關系舉例。

表2 領域詞4 種關系類型舉例

2.2 基于改進的BRT 領域概念層次構建

本文基于關系抽取獲取的領域詞對集-構建領域層次。在初始化時每個數據點都是一棵樹,如Ti={xi},xi表示第i個數據節(jié)點的特征向量,每一步選取2 個層次結構Ti,Tj融合成一個新分類結構Tm,如圖3 所示。

圖3 節(jié)點初始化分類體系

本文通過算法比較,確定2 個層次結構的融合方式,有3 種融合方式：連接,吸收,歸并。

(1) 連接(Join)

其中,leaves表示每個層次結構的所有的葉節(jié)點。這個方法是從根節(jié)點合并2 個層次結構,Tm有2 個子節(jié)點,如圖4 所示。

圖4 C 節(jié)點和D 節(jié)點的連接操作

(2) 吸收(Absorb)

如圖5 所示,此方法可以理解Tj變?yōu)門i的子節(jié)點,對于2 棵層次結構,也有可能Ti變?yōu)門j的子節(jié)點,此方法逆向的表示為：

圖5 A 節(jié)點與B 節(jié)點的吸收操作

(3) 歸并(Collapse)

2 棵層次結構的子節(jié)點歸并成一個層次結構下,如圖6 所示。

圖6 歸并操作

算法每一步挑選2 個層次結構進行3 種可能性合并操作,得到每種合并方法的概率,其計算公式如下：

其中,D表示層次結構T的所有數據節(jié)點；f(D)代表邊緣概率；πT是表示所有在T的數據不被分成子層次結構的先驗概率,其定義如下：

其中,γ是介于0 和1 之間的控制模型超級參數；n表示T中子節(jié)點的數目。不同的γ對實驗結果有很大影響。

對于邊緣概率f(D)的表示采用了基于多項式的Dirichlet 共軛分布(DCM)[14],因此,它更能代表一個或多個主題,在分層聚類中,逐步合并簇。

其中,V表示詞量是相對于的頻率；m=表示第i個節(jié)點和j個節(jié)點的關系概率。

對3 種融合方式,采用比率評分Score(D|T)形式決定選擇哪種融合方式,其公式如下：

領域層次結構自動構建算法如下：

輸入領域詞集

輸出領域概念層次結構

在原來的BRT 算法復雜度為O(n2Cv+n2logn),空間復雜度為O(n2),其中,Cv為所有初始化向量xi中所有非零元素的最大數,當領域詞的個數比較多時Cv是一個不容忽視的數。本文將領域詞對間關系也考慮在內,計算了2 個領域詞關系的概率,降低了了邊緣概率的復雜度,此算法將復雜度降低到O(n2logn)。其中,領域詞對關系為：

如果2 個節(jié)點有關系,更能準確計算2 個節(jié)點的融合方式,將R(xi,xj)代入節(jié)點融合運算,不僅降低了算法復雜度,而且有利于保證層次結構構建的正確性。

3 實驗與結果分析

3.1 測試數據集和實驗方案

本文實驗分別對通信、金融和計算機3 個領域實現概念層次自動構建。實驗評估標準參考文獻[15]提出的本體評價標準,其公式如下：

其中,Ref表示參考的層次結構；Comp表示要比較層次結構。通過上式可以計算領域概念層次結構的查準率P、查全率R和綜合指標F值。Ref以手動構建的概念層次結構作為參考標準。

關系抽取部分采用PCFG 的句法結構訓練得到的句法分析器進行句法分析,然后采用規(guī)則匹配的方法,并將兩者結合,統(tǒng)計ISA 和Part-of 兩種關系的種類,實驗表明該2 種關系占總數的80%,表3 展示了30 對領域概念關系抽取結果。該表是對3 個領域的詞對關系舉例說明,部分領域詞對間關系如表2 所示。實驗的機器配置如下：處理器為Intel ?Pentium? CPU G630 @2.7 GHz,內存4 GB,操作系統(tǒng)為Win7 64 位。

表3 領域詞對關系

3.2 結果分析

本文實驗主要包括2 個步驟：領域詞關系抽取和自動構建層次結構,關系抽取對第2 步的層次構建有很大影響,因此,本文對兩部分進行了實驗分析。

3.2.1 領域詞對關系抽取的效果評估

該部分主要是獲取領域關系,表4 顯示的是分別采用句法樹、基于規(guī)則的方法,句法樹與基于規(guī)則結合的方法和人工4 種方法獲取通信領域概念詞對關系的對比結果。

表4 關系抽取效果比較

中文表達比較模棱兩可,再加上句法結構復雜,其中還有一小部分沒有識別出來,對其進行分析,其原因如下：

(1) 若2 個領域概念多次共現在同一句子,共現頻率比較高則可能存在一定的關系,本文缺少對此方面的考慮；

(2) 網絡抓取的部分句子結構比較長,句法比較復雜,中間干擾詞比較多,而結果錯誤的判給其他領域詞。

3.2.2 層次結構自動構建的效果評估

基于上一步獲取領域詞以及關系,在使用改進的BRT 算法時,通過不斷實驗發(fā)現當γ=0.3 時,效果最優(yōu)。對通信領域數據進行5 次實驗,結果如表5所示,其中,n表示領域詞的個數。

表5 通信領域實驗結果 %

筆者發(fā)現領域概念數量越多其查準率越高,因為隨著領域詞豐富,一方面能更多的發(fā)現領域詞關系,對關系識別越有利；另一方面在層次自動構建上,隨著領域概念數量的增多,能更準確地定位到節(jié)點,更有利于提高節(jié)點融合的準確率。

采用BRT 算法和改進的BRT 算法在通信領域的領域概念數n=500 時,做了對比實驗,其結果如表6 所示。可以看出,DCTA 算法構建的層次結構查準率最高達88%,比使用BRT 算法提高了5.4%,查全率提高了5% 。實驗表明本文算法的可行性。

表6 2 種構建算法的結果比較 %

另外,將此算法對金融和計算機領域構建層次結構,其結果如表7 所示?？梢钥闯?本文方法具有很強的移植性,可以適用金融領域和計算機領域。證明該算法充分考慮了領域概念的特點,選擇算法可用性強,適用于構建復雜領域層次結構。

表7 金融領域和計算機領域實驗結果 %

4 結束語

本文提出基于中文面向領域的概念層次自動構建算法(DCTA),該算法主要包括領域詞對關系抽取和自動層次構建,即采用句法樹和基于規(guī)則的混合方法獲取領域詞關系,然后使用改進的BRT算法構建層次結構。本文研究實現了對3 個領域的概念層次自動構建,并在通信領域與傳統(tǒng)的BRT算法進行了對比實驗。實驗結果表明,本文算法具有較高的查準率,而且可移植性強。下一步將改進算法以提高分類體系的準確度,并針對更多的領域進行實驗,推導出適用多個相關領域的分類體系算法。

[1]Sadikov E,Madhavan J,Wang Lu,et al.Clustering Query Refinements by User Intent[C]//Proceedings of the 19th International Conference on World Wide Web.New York,USA：ACM Press,2010：841-850.

[2]Perry P,Wise W,O’ Neill D,et al.Leveraging a Technical Domain Taxonomy to Enhance Collaboration,Knowledge Sharing and Operational Support [C]//Proceedings of SPE Digital Energy Conference and Exhibition.The Woodlands,USA：Society of Petroleum Engineers,2011：19-21.

[3]Agirre E,de Lacalle O.Publicly Available Topic Signatures for All WordNet Nominal Senses [C]//Proceedings of LREC’04.Lisbon,Portugal：European Language Resources Association,2004：1123-1126.

[4]Deshpande O,Lamba D S,Tourn M,et al.Building,Maintaining,and Using Knowledge Bases：A Report from the Trenches [C]//Proceedings of 2013 International Conference on Management of Data.New York,USA：ACM Press,2013：1209-1220.

[5]Liu Xueqing,Song Yangqiu,Liu Shixia,et al.Automatic Taxonomy Construction from Keywords [ C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA：ACM Press,2012：1433-1441.

[6]Blundell C,Teh Y W,Heller K A.Bayesian Rose Trees[C]// Proceedings of UAI’10.Catalina Island,USA：[s.n.],2010：68-76.

[7]Monachesi P,Markus T,Mossel E.Ontology Enrichment with Social Tags for eLearning[C]//Proceedings of the 4th European Conference on Technology Enhanced Learning.Nice,France：[s.n.],2010：385-390.

[8]Lupea M,Tatar D,Marian Z.Learning Taxonomy for Text Segmentation by Formal Concept Analysis[C]//Proceedings of CoRR’ 10.[S.l.]：Springer,2010：84-92.

[9]Tsui E,Wang W M,Cheung C F,et al.A Conceptrelationship Acquisition and Inference Approach for Hierarchical Taxonomy Construction from Tags [ J].Information Processing &Management,2010,46 (1)：44-57.

[10]Bai Xiaopeng,Xue Nianwen.Building a Chinese Lexical Taxonomy[C]//Proceedings of the 2nd CIPS-SIGHAN Joint Conference on Chinese Language Processing.Tianjin,China：[s.n.],2012.

[11]何婷婷,張小鵬.特定領域本體自動構造方法[J].計算機工程,2007,33(22)：235-237.

[12]Wang Zuxing,Zhu Xiaoting,Lu Zhao.A Context-aware Automatic Chinese Transliterated Person Names Recognition Approach[C]//Proceedings of the 8th International Conference on Semantics,Knowledge and Grids.Beijing,China：[s.n.],2012：143-149.

[13]Johnson M.PCFG Models of Linguistic Tree Representations[J].Computational Linguistics,1998,24(4)：613-632.

[14]Madsen R E,Kauchak D,Elkan C.Modeling Word Burstiness Using the Dirichlet Distribution[C]//Proceedings of the 22nd International Conference on Machine Learning.New York,USA：ACM Press,2005：545-552.

[15]Dellschaft K,Staab S.Strategies for the Evaluation of Ontology Learning[C]//Proceedings of 2008 Conference on Ontology Learning and Population：Bridging the Gap Between Text and Knowledge.Amsterdam,Holland：IOS Press,2008：253-272.