基于事件元素無向圖的查詢擴展方法

葉 雷，高盛祥，余正濤，秦廣順，洪旭東

(昆明理工大學 信息工程與自動化學院，云南 昆明 650500)

基于事件元素無向圖的查詢擴展方法

葉 雷，高盛祥，余正濤，秦廣順，洪旭東

(昆明理工大學 信息工程與自動化學院，云南 昆明 650500)

借助新聞事件元素之間的關(guān)聯(lián)特性，提出了基于事件元素無向圖的查詢擴展方法，利用新聞事件元素之間的關(guān)聯(lián)關(guān)系進行查詢擴展提升新聞事件檢索效果。首先分析候選事件文檔與查詢項的關(guān)系，確定待擴展的元素；然后利用事件元素之間的關(guān)聯(lián)關(guān)系構(gòu)建無向圖，通過事件向量空間計算邊的權(quán)重；最后，利用無向圖節(jié)點權(quán)重模型計算事件元素權(quán)重，依據(jù)權(quán)重進行事件元素擴展。在新聞事件查詢擴展方面進行了對比試驗，結(jié)果表明該文提出的查詢擴展方法取得了較好的效果。

新聞事件；查詢擴展；事件元素；事件元素無向圖

1 引言

在信息檢索領(lǐng)域，查詢擴展技術(shù)是指在用戶輸入的原查詢項的基礎(chǔ)上，加入一些與查詢相關(guān)的詞語，組合成新的查詢，用來解決查詢信息不全的問題，有助于提高檢索的性能。目前，在信息檢索領(lǐng)域，常見的查詢擴展有基于語義知識詞典、基于全局文檔集分析和基于局部文檔集分析三種方法。基于語義知識詞典的方法[1]通常利用WordNet、HowNet或同義詞詞林等語義知識詞典中提供的同義關(guān)系和上下位關(guān)系選取新詞；基于全局分析的技術(shù)[2-3]以詞關(guān)聯(lián)假設(shè)為基礎(chǔ)，分析文檔集中的全部語詞，計算所有詞語對的關(guān)聯(lián)強度，利用詞語之間的關(guān)聯(lián)實現(xiàn)查詢擴展；基于局部分析的技術(shù)[4-8]首先進行初始檢索，把與查詢最相關(guān)的N篇文檔當做擴展詞的來源，在這些文檔中尋找與查詢項相關(guān)的詞語實現(xiàn)查詢擴展，經(jīng)典的局部分析方法叫做局部反饋(Local Feedback)，也稱偽相關(guān)反饋(Pseudo Feedback)。

近幾年，新聞事件的查詢擴展方法成為專家學者研究的熱點，如仲兆滿等人研究了基于局部分析面向事件的查詢擴展方法[9](LA-EO)，該方法針對事件的特點將查詢項分成事件項和限制項，重點研究了擴展事件的選取以及查詢項與文本相似度的計算，并與其他查詢擴展方法進行了實驗對比，針對事件類信息檢索，LA-EO具有更優(yōu)的檢索性能；如文獻[10]提出的基于事件本體的查詢擴展(EO-QE),該方法在查詢擴展中引入了事件本體，重點探討了事件的四元組概念以及在不同事件元素下的擴展策略。

上述面向事件的查詢擴展方法，通過引入事件屬性和本體的思想，在事件類信息檢索中有了一定的提高。在新聞事件檢索中，檢索的對象是事件，事件由事件元素組成，包括事件的主體、事件發(fā)生的時間與地點等，而且同一事件或相似事件的事件元素之間具有關(guān)聯(lián)關(guān)系。因此，針對新聞事件的檢索，查詢擴展的層面應該是事件元素而不是一般的詞語。如果查詢項包含了目標事件的更多元素，那么檢索效果就會更好。例如，在檢索關(guān)于“5·12汶川地震”事件的過程中，原查詢項是“汶川縣、地震”，經(jīng)過擴展后查詢項變成了“汶川縣、地震、2008年5月12日、救援、死亡……”，查詢項中包含了更多目標事件的元素詞語，那么檢索的精度會得到提高。因此，本文提出了基于事件元素的查詢擴展方法，結(jié)合無向圖的思想，進行新聞事件信息的查詢擴展。

2 事件表示

事件可以定義為在一個特定時間和環(huán)境發(fā)生的、由若干對象參與的、表現(xiàn)出若干動作特征的一件事情。事件的表示模型有很多種，本文對于事件的定義來自于ACE[11]。根據(jù)該定義，事件是一個由事件觸發(fā)詞(Trigger)和描述事件屬性的元素組成的集合。圖1表述了一個事件的構(gòu)成。其中“出生”是該事件的觸發(fā)詞，“習近平”是對象要素，“1953年”是對應的時間，“陜西富平”則是地點。

圖1 “出生”事件的表示模型

3 基于事件元素無向圖的查詢擴展

基于事件元素無向圖的查詢擴展方法流程如圖2所示，首先采用偽相關(guān)反饋技術(shù)從待檢索文檔集中獲取m篇與查詢最相關(guān)文檔，用作待擴展的事件元素詞的來源。然后分析文檔與查詢的關(guān)系，把文檔標記成相關(guān)文檔或者相似文檔，相關(guān)文檔提取事件的所有元素，相似文檔只提取事件的觸發(fā)詞元素。抽取文檔中的事件元素，構(gòu)造以事件元素為節(jié)點的無向圖，利用事件元素無向圖節(jié)點權(quán)重模型計算圖中節(jié)點的權(quán)重，結(jié)合文檔與查詢的分析，進行事件元素擴展。

圖2 基于事件元素無向圖的查詢擴展方法流程圖

3.1 用偽相關(guān)反饋技術(shù)獲取文檔

偽相關(guān)反饋技術(shù)首先通過普通檢索算法從初始文檔中尋找到一個初始結(jié)果，然后假定其中排名最前面的m篇文檔是相關(guān)的，最后在這個假設(shè)條件下進行相關(guān)反饋。本文采用基于BM25算法作為偽相關(guān)反饋技術(shù)的檢索算法從待檢索文檔集中獲取文檔，作為擴展詞的來源。BM25檢索算法是一種經(jīng)典的概率統(tǒng)計檢索算法[12]，用以計算文檔D和查詢Q的相似性。給定一個查詢Q，包含關(guān)鍵詞q1,…,qt，查詢和文檔的BM25分值計算方法如式(1)所示。

(1)

其中，N代表候選文檔的總數(shù)；n(qi)為含有查詢關(guān)鍵詞qi的文檔數(shù)量；f(qi,A)是查詢詞qi在A中出現(xiàn)的頻率；f(qi,Q)表示查詢詞qi在Q中出現(xiàn)的頻率；|A|表示文檔長度，avgal是所有候選文檔的平均長度；k1，k3和b是調(diào)節(jié)因子。

3.2 文檔和查詢的關(guān)系分析

事件元素包括事件觸發(fā)詞和其他元素詞(時間、地點、人物等)，多個事件可能會出現(xiàn)相同的事件觸發(fā)詞，但是事件的其他元素詞不會相同，例如，事件1“2008年5月12日，汶川縣發(fā)生8.0級地震”和事件2“2015年4月25日，尼泊爾發(fā)生8.1級地震”的觸發(fā)詞都是“地震”，其他屬性詞卻不一樣。因此，我們認為觸發(fā)詞為事件的共性元素，其他元素詞為事件的特性元素。

如果文檔中僅出現(xiàn)查詢的事件觸發(fā)詞，沒有出現(xiàn)其他元素詞，那么把文檔標記為查詢相似文檔；如果文檔中既出現(xiàn)查詢的事件觸發(fā)詞，又包含了其他元素詞，那么把文檔標記為查詢相關(guān)文檔。對于查詢相似文檔，把文檔中抽取到的事件共性元素(觸發(fā)詞)作詞為待擴展詞語；對于查詢相關(guān)文檔，把從文檔中抽取到的所有事件元素詞作為待擴展詞語。

3.3 事件元素的抽取

在構(gòu)造無向圖之前，需要抽取事件元素作為待擴展詞，關(guān)于事件元素的抽取方法可參看文獻[13]，本文采用的抽取方法如下:對新聞事件語料進行命名實體識別，通過觸發(fā)詞詞典匹配語料中的觸發(fā)詞，在每一個觸發(fā)詞的上下文中搜索相鄰的命名實體，匹配到的命名實體包括人名、機構(gòu)名、地點和時間等，作為事件發(fā)生的對象、地點和時間要素。觸發(fā)詞及其相關(guān)的事件元素即結(jié)構(gòu)化地表示了一個事件。

3.4 事件元素無向圖的構(gòu)建

為了有效地表示事件元素之間的關(guān)聯(lián)關(guān)系，采用無向圖的方法。無向圖的構(gòu)建，具體可以分為兩個部分，第一個部分是節(jié)點以及邊的生成，第二個部分是邊權(quán)重的計算。下面詳細說明事件元素的無向圖構(gòu)建過程。

3.4.1 無向圖節(jié)點和邊的生成

將抽取到的每一個事件元素對應無向圖中的一個節(jié)點，在這個過程中需要注意兩點，一是多個事件可能會出現(xiàn)相同的事件元素，這些共現(xiàn)的事件元素在圖中只用一個節(jié)點表示；二是對時間表達式做統(tǒng)一處理，例如，“2015年3月9日”和“2015年3月9日17時59分”，將這個時間統(tǒng)一標記為“2015年3月9日17時59分”。每個事件內(nèi)部的元素節(jié)點兩兩相連，形成無向圖的邊。

例如，事件1“2008年5月12日14時28分，汶川縣發(fā)生8.0級地震”，事件2“2008年5月12日，大量師生死于坍塌校舍之下”和事件3“2015年4月25日，尼泊爾發(fā)生8.1級地震”構(gòu)成的無向圖如圖3所示。

圖3 事件元素無向圖

3.4.2 無向圖邊權(quán)重的計算

事件元素無向圖邊的權(quán)重反映的是事件元素之間的關(guān)聯(lián)程度。借鑒向量空間模型的思想，以新聞事件為特征，構(gòu)建向量空間，來表征事件元素，將事件元素間的關(guān)聯(lián)程度計算問題轉(zhuǎn)換為事件特征空間上向量之間的相似度計算問題。

(1) 事件向量空間的構(gòu)造

假設(shè)從偽相關(guān)反饋的N篇文檔中抽取到M個事件，形成子事件集合K={W1,W2,…,Wm}，根據(jù)集合K里面的每一個子事件作為向量空間中的一維，構(gòu)建一個M維的向量空間。

(2) 事件元素到向量空間的映射

利用對相應維度賦布爾值的方法，實現(xiàn)事件元素到向量空間的映射。以事件元素e1映射到M維的向量空間K={W1,W2,…,Wm}為例，具體步驟如下:

1) 對事件元素e1，判斷其在第一維度W1上面的取值。如果e1在事件W1里面出現(xiàn)，則該維度值為1，反之為0。

2) 循環(huán)第一步，計算e1在每一維度上的取值。

3) 計算出e1在每一個維度上的取值之后，就得到了e1在向量空間中的特征向量。

利用上面的方法，實現(xiàn)事件元素到M維向量空間上的映射。

(3) 事件元素特征向量相似度計算

使用向量之間的余弦夾角對事件元素進行相似度計算，如式(2)所示。

(2)

其中，θ表示Si，Sj在向量空間中的向量夾角，Wik為Si在第k維上面的取值，Wjk是Sj在第k維上面的取值，m表示事件向量空間的維數(shù)。

事件元素兩兩之間計算相似度，得到事件元素的相似度矩陣，如式(3)所示。

(3)

將事件元素之間的相似度作為無向圖中兩個節(jié)點的邊的權(quán)重。

3.5 事件元素無向圖節(jié)點權(quán)重計算模型

如果兩個事件元素節(jié)點之間相連，就說明這兩個元素節(jié)點存在聯(lián)系。當計算某節(jié)點的權(quán)重時，如果相連接的節(jié)點越多，那么其權(quán)重也應該越大。同時也要考慮原查詢事件元素的影響，如果某個節(jié)點與原查詢事件元素相連接，那么該事件元素節(jié)點應該更加重要，更有可能作為原查詢事件的擴展元素。

基于上述思想，新聞事件元素的無向圖節(jié)點重要度模型可以表示為式(4)。

(4)

其中，SW(i)表示節(jié)點i的權(quán)重(重要度)，d表示平衡系數(shù)，一般設(shè)置為0.85，Mi,j是相似度矩陣M中的值，表示無向圖中第i個事件元素和第j個事件元素之間的相似度，Q是原查詢事件元素集合，λ是大于1的可調(diào)參數(shù)。

3.6 事件元素的擴展和權(quán)重設(shè)置

計算出事件元素無向圖節(jié)點的權(quán)重，即得到事件元素的評分值。按照權(quán)重從高到低的順序擴展前N個元素，同時考慮到3.2節(jié)關(guān)于文檔和查詢的關(guān)系分析，對于查詢相似文檔，只擴展觸發(fā)詞元素，相關(guān)文檔擴展所有元素。

一般來說，不同的擴展詞對應的重要性也不同，擴展得到的查詢詞權(quán)重的設(shè)置是否合理對檢索性能有很大的影響?？紤]到擴展詞的評分越高，它在查詢中所占的權(quán)重應該越高，我們的權(quán)重設(shè)置使用如式(5)所示。[6]

(5)

其中，W(q|Qexp)表示查詢詞q在擴展后查詢Qexp中的權(quán)重，W(q|Q)表示查詢詞q在初始查詢Q中的權(quán)重，通常使用q在Q中的頻度表示，Score(q)代表擴展詞q的得分值，即式(4)所得結(jié)果，MaxScore表示所有擴展詞評分的最大值。α和β為兩個大于0的可調(diào)參數(shù)，通常情況下都設(shè)置成1。

4 實驗及分析

4.1 檢索性能評價指標

信息檢索技術(shù)常用指標有平均準確率(Mean Average Precision，MAP)，n位置的準確率(precision at position n，P@n)等，下面將分別進行介紹。

4.1.1 Mean average precision

MAP(Mean Average Precision)把所有查詢項的AP放在一起求宏平均，作為衡量系統(tǒng)對多個查詢的平均檢索質(zhì)量[14]，反映系統(tǒng)在全部相關(guān)文檔上性能的單值指標。檢索到的相關(guān)文檔位置越靠前，那么MAP值便會越高。假如沒有檢索出相關(guān)文檔，則MAP值是0。

給定一個查詢,其平均AP的計算公式如式(6)所示。

(6)

其中，N為文檔的個數(shù)，rel(n)是關(guān)于第n個文檔相關(guān)性的一個二元函數(shù)。

針對多個查詢，我們通過對所有查詢的AP值求平均得到MAP，如式(7)所示。

(7)

4.1.2 Precision at position n

P@n是指對一個排序結(jié)果，返回前n個結(jié)果的準確率。有時用戶使用搜索引擎搜索想要的結(jié)果可能只對返回的前n個頁面感興趣，P@n就是從這樣的角度對檢索性能進行衡量的評價標準，如式(8)所示。

(8)

例如，對于查詢返回的前五個文檔是{irrelevant(不相關(guān))，relevant(相關(guān))，relevant，relevant，irrelevant}，那么P@1到P@5的值分別是{0，1/2，2/3，3/4，3/5}。對于查詢集合，通過對所有查詢的P@n值求平均得到P@n值。

4.2 實驗數(shù)據(jù)說明

目前已有的信息檢索語料多用于通用搜索評測，設(shè)置的查詢項并不面向新聞事件。所以，我們通過互聯(lián)網(wǎng)爬蟲技術(shù)從中國新聞網(wǎng)、新華網(wǎng)、新浪新聞等新聞網(wǎng)站收集了3 000個面向新聞事件的頁面，并對這些頁面做一些處理，每個頁面保留其標題及正文，把這些文本作為實驗語料。爬取的新聞主題包括汶川地震、MH370失聯(lián)、昆明火車站恐怖襲擊等一系列社會熱點話題。查詢項的設(shè)置采用與用戶使用搜索引擎相一致的方式，即輸入若干個詞語當做查詢。針對爬取的新聞文本，我們?nèi)斯ぴO(shè)計了八個面向事件的查詢項，新聞文本的分布及相應查詢項的設(shè)置如表1所示。

表1 實驗數(shù)據(jù)分布及查詢項設(shè)置

4.3 實驗設(shè)計與結(jié)果分析

為了驗證所提方法的有效性，設(shè)計了兩個試驗。實驗1比較了事件元素擴展詞的個數(shù)對檢索性能的影響，在得到擴展詞之后，逐漸增加擴展詞詞數(shù)，比較檢索結(jié)果；實驗2比較不同擴展方法的檢索性能，采用經(jīng)典的查詢擴展算法Rocchio方法[4]作為對照。

4.3.1 事件元素擴展詞個數(shù)的影響

事件元素擴展詞數(shù)量的選擇會影響檢索結(jié)果精度，擴展詞語的數(shù)量太少的話，達不到查詢擴展的目的，而擴展詞數(shù)量過多的話，又會引起查詢噪音問題。對查詢事件元素擴展的個數(shù)從0～18之間做了對比實驗，針對八個事件查詢主題，所提方法在不同擴展詞個數(shù)下得到的平均MAP和P@5如圖4所示。

圖4 不同擴展詞個數(shù)的實驗結(jié)果

從圖4可以看出，擴展詞數(shù)量在0到10之間時，隨著查詢事件元素擴展詞數(shù)量的增加，檢索性能MAP和P@5都有一定幅度的提高。當擴展詞個數(shù)達到10的時候，檢索性能達到最優(yōu)，平均MAP為0.394 3，P@5為0.723 2。而擴展詞個數(shù)達到10之后，增加擴展詞個數(shù)并沒有繼續(xù)提高檢索性能，反而性能有一定的下降。從此可見，查詢擴展詞數(shù)目應該選擇10的時候檢索性能最好，太多的話會引入噪音。

4.3.2 不同查詢擴展方法的性能比較

為驗證所提查詢擴展方法的有效性，在相同擴展詞個數(shù)(10個)的條件下，我們與其它擴展方法進行了對比實驗。其中，不進行查詢擴展的方法記為M1，Rocchio方法記為M2，本文所提方法記為M3。實驗采用的評價指標為MAP和P@5，實驗結(jié)果如圖5所示。

圖5 不同擴展方法的實驗結(jié)果

由圖5可見，在相同的條件下，所提出的擴展方法的檢索性能相較其他方法都有一定的提高。這主要是因為考慮到面向事件的查詢擴展，應該擴展的是事件元素詞，而不是一般的詞語。同時，考慮到了事件元素之間存在的關(guān)聯(lián)以及原查詢項的事件元素對節(jié)點權(quán)重的影響，通過構(gòu)建事件元素無向圖節(jié)點權(quán)重模型進行查詢擴展，取得了很好的效果。

5 總結(jié)

本文提出了一種基于事件元素無向圖的查詢擴展方法。利用新聞事件元素構(gòu)成無向圖，計算出事件元素之間的相似性，通過節(jié)點權(quán)重模型計算事件元素的重要程度并得到擴展詞。實驗證明所提方法在面向事件的查詢擴展中取得了較好的效果，能夠提高事件檢索的性能。進一步將深入考慮新聞事件的主題對事件元素的影響，以及不同類型主題的事件元素的共性，研究新聞事件的查詢擴展方法。

[1] Richardson R,Smeaton A.Using WordNet in a Knowledge-Based Approach to Information Retrieval[C]//Proceedings of the Working paper CA-0395,School of Computer Applications,Trinity College Dublin.1995.

[2] Wei J,Bressan S,Ooi B C.Mining term association rules for automatic global query expansion:methodology and preliminary results[C]//Proceedings of the First International Conference on.IEEE,2000,1:366-373.

[3] Zhang CQ,Qin ZX,Yan XW.Association-Based segmentation for Chinese-crossed query expansion[J].IEEE Intelligent Informatics Bulletin,2005,5(1):18-25.

[4] C Buckley,G Salton,J Allan,et al.Automatic query expansion using SMART[C]//Proceedings of the Overview of Text Retrieval Conference.1994:69-80.

[5] Song M,Song I Y,Hu X,et al.Integration of Association Rules and Ontology For Semantic Query Expansion[J].Data & Knowledge Engineering,2007,63(1):63-75.

[6] 丁國棟,白碩,王斌.一種基于局部共現(xiàn)的查詢擴展方法[J].中文信息學報,2006,20(3):84-91.

[7] Guihong Cao,Jian-Yun Nie,Jianfeng Gao,and Stephen Robertson.Selecting good expansion terms for pseudo-relevance feedback[C]//Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval,Singapore,2008,243-250.

[8] 黃名選,嚴小衛(wèi),張師超.基于矩陣加權(quán)關(guān)聯(lián)規(guī)則挖掘的偽相關(guān)反饋查詢擴展[J].軟件學報,2009,20(7):1854-1865.

[9] 仲兆滿,朱平,李存華,管燕,劉宗田.一種基于局部分析面向事件的查詢擴展方法[J].情報學報,2012,31(2):151-159.

[10] Zhong ZM,Li CH,Guan Y,et al.A method of query expansion based on event ontology[J].Journal of Convergence Information Technology,2012,7(9):364-371.

[11] ACE (Automatic Content Extraction) Chinese Annotation Guidelines for Events[C]//Proceedings of the National Institute of Standards and Technology.2005.

[12] S E Robertson,S Walker,S Jones,et al.Okapi in TREC3[C]//Proceedings of Text Retrieval Conference,Gaithersburg,USA.U.S.National Institute of Standards and Technology,NIST Special Publication 500-225:1994.109-126.

[13] 趙妍妍,秦兵,車萬翔,等.中文事件抽取技術(shù)研究[J].中文信息學報,2008,22(1):3-8.

[14] Baeza-Yates R,Ribeiro-Neto B.Modern information retrieval[M].New York:ACM press,1999.

A Query Expansion Method Based on Undirected Graph of Event Elements

YE Lei,GAO Shengxiang,YU Zhengtao,QIN Guangshun,HONG Xudong

(School of Information Engineering and Automation,Kunming University of Science and Technology,Kunming,Yunnan 650500,China)

This paper proposes a query expansion method based on undirected graph of event elements,which utilizes the relevance between news event elements to conduct query expansion to improve news event retrieval.Firstly,we select out the elements to be extended by analyzing the relationship between candidate events and queries.Then,we construct an undirected graph to represent the extracted event elements and the relationship between them,and compute the edge weights through event vector space.Finally,we compute the weight of event elements by the undirected graph model of node weight,and extend event elements according to the weights computed.Experimented on news event query expansion data,it is proved that the proposed query expansion method has a good effect on news event retrieval.

news event; query expansion; event elements; undirected graph

葉雷(1992—),碩士研究生,主要研究領(lǐng)域為信息檢索、自然語言處理。E-mail:yelei0128@gmail.com高盛祥(1977—),博士研究生,主要研究領(lǐng)域為信息檢索、機器翻譯。E-mail:gaoshengxiang.yn@foxmail.com余正濤(1970—),通信作者,博士,教授,博士生導師,主要研究領(lǐng)域為自然語言處理、信息檢索、機器翻譯。E-mail:ztyu@hotmail.com

1003-0077(2011)00-0017-06

2016-09-10 定稿日期:2016-10-15

國家自然科學基金(61472168、61175068)；云南省自然科學基金(2013FA130);云南省科技創(chuàng)新人才基金(2014HE001)

TP391

A