基于穩定性語義聚類的相關模型估計

孫芯宇 吳江 蒲強

摘要：針對由不穩定聚類估計的相關模型影響檢索性能的問題，提出了基于穩定性語義聚類的相關模型（SSRM）。首先利用初始查詢前N個結果文檔構成反饋數據集；然后探測數據集中穩定的語義類別數量；接著從穩定性語義聚類中選擇與用戶查詢最相似的語義類別估計SSRM；最后通過實驗對模型的檢索性能進行了驗證。對TREC數據集5個子集的實驗結果顯示，SSRM相比相關模型（RM）、語義相關模型（SRM），平均準確率（MAP）性能最少提高了32.11%和0.41%；相比基于聚類的文檔模型（CBDM）、基于LDA的文檔模型（LBDM）和Resampling等基于聚類的檢索方法，MAP性能最少提高了23.64%，19.59%和8.03%。實驗結果表明，SSRM有利于改善檢索性能。

關鍵詞：信息檢索；語義聚類；穩定性驗證；獨立分量分析；相關模型估計

中圖分類號：TP391.3 文獻標志碼：A

Abstract：To solve the problem of relevance model based on unstable clustering estination and its effect on retrieval performance， a new Stable Semantic Relevance Model （SSRM） was proposed. The feedback data set was first formed by using the top N documents from user initial query， after the stable number of semantic clusters had been detected， SSRM was estimated by those stable semantic clusters selected according to higher userquery similarity. Finally， the SSRM retrieval performance was verified by experiments. Compared with Relevance Model （RM）， Semantic Relevance Model （SRM） and the clusteringbased retrieval methods including ClusterBased Document Model （CBDM）， LDABased Document Model （LBDM） and Resampling， SSRM has improvement of MAP by at least 32.11%， 0.41%， 23.64%，19.59%， 8.03% respectively. The experimental results show that retrieval performance can benefit from SSRM.

Key words：information retrieval； semantic clustering； stability validation； Independent Component Analysis （ICA）； relevance model estimation

0 引言

信息檢索研究中常用偽相關反饋方法估計相關模型，改善用戶查詢，更準確獲取用戶信息需求。相關模型的估計需要用到偽相關反饋技術，通常假設用戶初始查詢的前N個結果文檔是查詢相關的，但大多數情況下這個假設并不成立。全部N個文檔參與反饋必將帶入不相關噪聲，使得相關模型估計偏離用戶查詢[1-2]。

聚類技術可將N個查詢結果文檔形成的數據集劃分成若干類別，只選擇與用戶查詢最相似的聚類中的文檔估計語言模型，可以減少模型估計中不相關文檔帶來的噪聲。已有研究[3-4]表明，語義聚類技術相比傳統聚類技術在聚類效果上有顯著改善。語義聚類指在未知數據類別的潛在語義空間上的聚類操作，語義空間以多個數據主題為基張成。語義聚類通常借助本體[4]或利用統計[5-6]的方法進行。本體WordNet可以判斷文檔間的關聯，決定文檔是否劃分到相同的語義聚類。雖然借助本體的語義聚類效果有所改善，但是規則式的語義聚類方法不能靈活適應各種數據。潛在語義索引（Latent Semantic Indexing，LSI）[5]、獨立分量分析（Independent Component Analysis，ICA）[6]采用統計方法分離語義主題，為典型的語義聚類技術。LSI技術將最大方差投影方向定義為語義類別，但最大方差投影方向并不總是表示數據的真實語義類別[6]。ICA技術具有在任意方向上分離出數據中獨立分量的能力，分量間不要求一定滿足正交關系。相比LSI定義的最大方差投影方向，ICA的任意方向上分離的獨立分量更能表示數據中真實存在的語義類別，因此本文采用ICA進行語義聚類。ICA算法分離出的每一個獨立分量代表數據中的一個語義類別，以每個獨立分量為基可張成ICA語義空間。

由于數據中未知的語義類別數量和ICA算法的隨機性，多次運行ICA算法分離的獨立分量是不同的[7]，因此得到的數據語義聚類也不一樣，也就是語義聚類是不穩定的。數據本來具有隱含的固定數量的語義主題，在不穩定的語義聚類上估計相關模型必定存在主題偏差。文獻[8-9]利用語義聚類估計了相關模型，并提升了檢索性能，但沒有考慮語義聚類的穩定性。

如果能夠預先探測數據中隱含語義類別的個數，那么ICA算法根據此類別數量才能分離出接近真實可靠的語義聚類穩定性語義聚類。探測數據集中的聚類個數通常使用多個k值重復運行包含隨機性的聚類算法，并利用聚類穩定性指標計算不同k值下的聚類穩定性，選擇聚類穩定性最高的k值作為最合適的聚類個數[10]。

針對基于穩定聚類的語言模型估計對檢索性能的影響等研究工作較少，本文提出一種基于穩定性語義聚類估計的相關模型（Stable Semantic Relevance Model， SSRM），通過探測前N個查詢結果文檔構成的數據集中存在的穩定語義類別數量來驗證語義聚類的穩定性。本文認為在穩定性驗證后的語義聚類中，選擇與用戶查詢最相似的語義類別估計的相關模型，能夠獲取比現有方法更好的檢索性能。

由于ICA算法的隨機性，在微小差別條件下多次運行ICA算法可以解決單次運行分離獨立分量的不可靠問題。假設數據集中存在從1到n的語義類別數量，通過如下方法保證穩定性語義聚類：探測1到n的類別數量，在同一數據集上使用Bootstrapping方法微小改變運行條件，多次運行ICA算法，并聚類得到的一組獨立分量。將聚類質量得分最高對應的探測類別數量作為數據集中穩定的語義聚類數量。

本文研究工作將解決如下問題：如何驗證語義聚類穩定性；如何選擇參與相關模型估計的穩定性語義聚類；如何估計基于穩定性語義聚類的相關模型；如何利用穩定性語義聚類估計的相關模型進行檢索實驗，并將檢索結果在縱向和橫向上同已有典型算法詳細比較，以證明基于穩定性語義聚類估計的相關模型能夠帶來檢索性能上的提升。

1 相關模型和潛在語義聚類的關系

信息檢索中，通過相關文檔的反饋可以改善用戶查詢，研究表明檢索性能改善效果明顯[11]。用戶查詢已知，相關文檔未知的情況下使得相關模型估計變得困難。文獻[11]提出一種在相關文檔未知情況下，利用用戶查詢和初始查詢結果前面若干文檔估計相關模型的理論方法。方法假設用戶查詢和文檔之間存在一個隱含的相關模型，因此可觀察的用戶查詢和文檔是由隱含的相關模型隨機采樣詞條生成的。這樣，用戶查詢和文檔通過相關模型聯系起來。

利用查詢和初始查詢結果的前面若干文檔作為相關反饋文檔，可以近似估計相關模型。有兩種經典的相關模型估計方法[11]：一種假設由反饋文檔估計的文檔模型獨立生成查詢詞條和文檔詞條，查詢詞條和文檔詞條間無關聯關系；另一種假設查詢詞條由文檔模型獨立生成，但各查詢詞條保持和文檔詞條關聯，關聯度高的詞條在相關模型估計中擁有較高的權重。

相關模型的估計通常采用基于聚類的方法[1-2，8-9，12]，好處在于可以先對初始查詢結果文檔聚類，然后只選擇用戶查詢最相似的某個類別中的文檔參與估計相關模型。基于聚類的方法估計相關模型的基本思想是：借助聚類選擇，過濾掉與用戶查詢相似度不高的文檔帶來的噪聲。

ICA算法已被證明是一種有效的語義聚類方法[8-9]，和文獻[8-9]不同的是，本文重點考慮了ICA算法的隨機性造成在同一數據集上多次運行ICA算法分離的獨立分量結果不唯一性，也就是語義聚類數量的不唯一問題，因此有必要驗證ICA算法在不同數據類別數量上分離獨立分量的穩定性。本文認為在穩定的語義聚類中選擇和用戶查詢最相似的語義類別估計的相關模型能夠改善檢索性能。驗證的基本思想是，假設數據集中存在L個語義類別，利用重采樣方法[7，13]，在同一數據集上分別按1至L個類別，多次運行ICA算法，并將每次得到的一組獨立分量進行聚類。如果在某個數量m上的語義類別穩定，那么獨立分量應接近聚類中心而遠離其他聚類，這時可將分離的獨立分量數量m作為數據集中的語義類別數量。

2 ICA語義聚類及穩定性驗證

2.1 ICA語義聚類

如果將語義空間看成一組相互獨立的隱含主題為基構成的空間，那么混合了隱含主題的一組文檔在語義空間上張成用戶可觀察的文檔集合[14]。已知混合主題的文檔集合，利用ICA技術可分離其中的隱含主題，即將文檔集表示為獨立分量的線性組合[6]。本文將獨立分量表示的相互獨立的隱含主題定義為文檔集中的語義類別。ICA模型如式（1）：

2.2 語義聚類的穩定性驗證

多次利用隨機性和無監督的ICA算法分離的語義類別是不同的。如果能事先驗證數據中存在的穩定類別數量，那么通過ICA算法得到的語義類別才可靠并接近數據類別的真實情況。在盡可能接近真實可靠的語義聚類上估計的相關模型應該能夠提升檢索性能，本文實驗部分將驗證這一猜測。

語義聚類的穩定性驗證的基本過程是：假設數據集中存在不同的獨立分量數量，即語義類別數量。遍歷每個類別數量，多次運行ICA算法，將得到的獨立分量進行聚類；然后考察聚類質量，將聚類質量最高情況下對應的獨立分量個數作為數據集中穩定的語義聚類數量。

3 基于穩定性語義聚類的相關模型估計

已知用戶查詢的情況下，利用前N個初始查詢結果文檔作為偽相關反饋可以估計相關模型。例如，已知用戶查詢Q和前N個結果文檔構成的文檔集D，相關模型R的估計為p（D|Q，R）=∏Ni=1p（di|Q，R）。p（di|Q，R）為假設已知相關模型R和用戶查詢Q的條件下，生成文檔di的條件概率。

由于前N個查詢結果文檔并非都與用戶查詢相關，將N個結果文檔全部參與反饋估計相關模型必定帶入不相關的噪聲，導致估計的相關模型偏離用戶查詢主題。這里提出利用基于穩定性語義聚類估計相關模型（SSRM）的方法，期望估計的相關模型比已有方法更好地改善檢索性能。SSRM估計過程包括兩個階段：1）選擇參與相關模型估計的穩定性語義聚類；2）基于穩定性語義聚類估計相關模型。

3.1 篩選穩定性語義聚類

語義聚類穩定性驗證后得到的一組獨立分量將作為數據集中穩定的語義聚類，對應多個語義類別。穩定性語義聚類選擇的目的是，選取穩定性語義聚類中適合度高于閾值的一組語義類別參與相關模型的估計。語義聚類的適合度采用KL散度計算，基本思想是將語義聚類和用戶查詢的相似度距離作為語義聚類的適合度，離用戶查詢相似度距離最小的語義聚類適合度最高。語義聚類的適合度按照語義聚類模型和查詢模型間的相似度計算，并篩選出適合度高于閾值的語義聚類。計算如式（7）：

如果語義聚類模型和用戶查詢模型生成詞條w的概率越接近，那么這兩種模型的詞條分布越相似。適合度高于閾值的語義聚類下的文檔將用來估計相關模型，期待緩解使用全部前N個查詢結果文檔估計相關模型帶入的不相關噪聲，造成相關模型估計出現主題偏移的問題。

3.2 估計相關模型

假設用戶查詢詞條q1，q2，…，qk間相互獨立，與文檔詞條w保持某種程度的關聯。通過式（7）選擇的穩定性語義聚類將在相關模型估計過程中發揮橋梁作用，它將用戶查詢和語義聚類中文檔詞條關聯起來。使用穩定性語義聚類后，在已知用戶查詢Q的情況下，相關模型p（w | Q， R）的估計轉化為計算文檔詞條w和用戶查詢q在穩定性語義聚類中的同現概率，如式（8）：

4 實驗結果與分析

4.1 實驗設計

實驗目的是為了驗證基于穩定性語義聚類估計的相關模型（SSRM）更接近用戶的查詢需求，比已有的相關模型和基于聚類的檢索方法在檢索性能上有所改善。

實驗將在TREC數據集上測試SSRM的檢索性能。實驗中，TREC標題用來模擬用戶查詢，并刪除了無相關結果文檔的查詢。數據集使用Porter進行詞干處理，同時刪除了停止詞。實驗使用Indri5.0建立數據集索引。查詢編號51～150的美聯社（Associated Press Newswire，AP）數據集作為訓練集，查詢編號151～200的AP數據集、華爾街日報（Wall Street Journal，WSJ）、圣何塞水星報（San Jose Mercury News，SJMN）、查詢編號301～400的金融時報（Financial Times，FT）和洛杉磯時報（Los Angeles Times，LA）等數據集作為測試集。

估計SSRM實驗步驟包括：1）使用基本的查詢似然模型得到初始查詢結果文檔；2）使用DTU工具箱[14]255中的ICA算法對前50個用戶查詢結果文檔進行語義聚類；3）穩定性語義聚類驗證。首先假設前50個文檔形成的數據集中存在20個語義類別，然后使用Bootstapping方法運行FastICA算法[6]154930次，探測數據集中存在的穩定語義類別；4）通過式（7）選擇適合度高于閾值的穩定性語義聚類。適合度閾值設定為0.3，即選擇KL散度值由高到低排列的前面30%的穩定性聚類參與相關模型的估計；5）利用選擇的穩定性語義聚類進行相關模型估計。估計中，選擇穩定性語義聚類生成詞條的概率值大于閾值0.3的詞條作為語義聚類的關鍵詞。

為了驗證SSRM的檢索性能高于其他相關模型和基于聚類的方法，實驗在查詢平均準確率均值（Mean Average Precision， MAP）上縱向和橫向比較了SSRM和其他模型的檢索性能?？v向比較的模型包括：1）基線相關模型（Relevance Model， RM）：Indri實現Lavarenko的相關模型[11]122-123作為檢索性能比較基線；2）在無穩定性驗證的ICA語義聚類上估計的語義相關模型（Semantic Relevance Model， SRM）。橫向比較的方法包括：基于聚類的方法（ClusterBased Document Model， CBDM）[1]、基于LDA的文檔模型（LDABased Document Model， LBDM）[15]和重采樣（Resampling）方法[2]。

4.2 三種相關模型性能縱向比較

表1給出了SSRM在測試集上的MAP性能相比RM、SRM的MAP性能的提升情況?！?chg”表示SSRM相對RM和SRM在MAP性能上提高的百分比。表中值的上標α、β、γ分別表示RM、SRM和SSRM三種模型在置信度為95%的情況下，MAP值在Wilcoxon檢驗下顯著性提高?！癠pper”列中的值為MAP性能上界。性能上界值計算方法：首先手動選取前50個查詢結果文檔中真正查詢相關的文檔，然后將這些真實相關的文檔作為反饋估計語義相關模型（SRM）并檢索得到MAP值。之所以利用SRM計算檢索性能上界，主要考慮SRM沒有消耗額外的時間驗證語義聚類的穩定性。

表1縱向比較的結果顯示，SSRM在所有測試集上得到的MAP值均高于RM和SRM，MAP性能最少提高了32.11%和0.41%。例如在AP測試集，使用SSRM得到的MAP值為0.3431，相對RM的MAP值0.25，在性能上提升了37.24%；相對SRM的MAP值0.3345，在性能上提升了2.57%。

表1中SSRMMAP值的提高驗證了經過穩定性驗證的語義聚類更好過濾了用戶查詢無關的噪聲，因而估計的相關模型更接近用戶查詢的實際需求，從而提高了MAP性能。同時也觀察到，并非所有MAP值都是顯著性提高的。例如對于AP測試集，SSRMMAP值提高只對RM是顯著性提高，而對SRM的提高是非顯著的；但是對于SJMN和FT測試集，SSRM相對RM和SRM在MAP值上的提升都是顯著性的。這說明SJMN和FT測試集中主題噪聲影響了相關模型的估計，但SSRM能夠有效過濾這兩種測試集中的噪聲，因而帶來的MAP提升是顯著性的。

測試集FT和LA每個主題對應的真實相關文檔在TREC五個數據集中最少[8]，但SSRM在這兩個測試集上相對其他三個測試集的MAP性能提升最大。這進一步驗證了SSRM能夠較好過濾數據集中用戶查詢不相關噪聲，使穩定性語義聚類中的文檔查詢相關，并遠離查詢不相關主題。在AP和WSJ兩個測試集上，SSRM對MAP性能的提升有限，其原因可能是兩個數據集中的文檔包含多個語義主題，使用ICA算法很難將多語義主題文檔劃分到合適的語義類別中。這說明利用ICA算法進行穩定性語義聚類，對于多個語義主題的文檔效果有限。由表1還可以觀察到，SSRM的MAP值離性能上界還存在不小差距，說明基于穩定性語義聚類估計出的相關模型在MAP性能上還有改進空間。

4.3 四種聚類方法性能橫向比較

橫向比較的三種基于聚類的方法為：基于聚類方法（CBDM）、基于LDA的方法（LBDM）和重采樣（Resampling）方法。比較的原因是：這三種方法是信息檢索中比較典型的方法，同時三種方法沒有作穩定性聚類驗證工作，可以對比驗證SSRM的性能。表2中三種基于聚類的方法的MAP值均來源于文獻[1-2，15]的數據。

表2顯示，SSRM在測試集上相比三種基于聚類方法的MAP性能改善明顯。相比三種基于聚類的檢索方法，MAP性能至少提高了23.64%，19.59%和8.03%。由于SSRM采用ICA算法進行語義聚類，并對語義聚類進行了穩定性驗證，這說明ICA算法相比其他三種聚類方法在語義聚類上的效果更好，特別是經過語義聚類穩定性驗證后估計的相關模型，在語義上更接近用戶查詢，是提升MAP性能的主要原因。

圖1顯示了SSRM、RM、SRM三種相關模型和檢索上界UP在AP訓練集和5個測試集上檢索的準確率召回率曲線的比較情況。可以看出，無論在訓練階段還是在測試階段，SSRM總是獲得比RM明顯好的檢索性能。通常情況下，SSRM也能得到相對SRM好的檢索性能。檢索性能的改善證明了語義聚類經過穩定性驗證后，更好地將查詢相關的文檔聚在一起，因此SSRM方法較SRM方法使用更多的真實相關文檔參與相關模型估計，而RM方法直接使用前N個查詢結果文檔估計相關模型，帶入了較多的不相關噪聲。

圖1顯示，在WSJ和FT測試集上，在高召回率一端，SSRM比RM的檢索性能稍差；同時，SSRM在AP和WSJ測試集上相比SRM提升的檢索性能有限，甚至在低召回率一端，SSRM的檢索性能比SRM還差。顯示表明，SSRM在召回率的中前段對檢索性能的提升最明顯。

圖1中SSRM的檢索性能同性能上界有很大差距。由于性能上界由真實的相關文檔估計的相關模型得到，這個差距說明通過數據聚類的方法不能完全獲取相關模型估計需要的真實相關的反饋文檔，同時也說明SSRM方法有較大的提升空間。一個解決思路是如何更好地選擇主題相關文檔，將聚類粒度放到段落或句子層次而不是整個文檔上。

5 結語

本文研究了ICA語義聚類穩定性驗證對相關模型估計的影響及其對檢索性能的改善效果。研究發現，語義聚類經過穩定性驗證后，能夠更好地將查詢相關的文檔聚在一起。

利用語義聚類的適合度篩選出和用戶查詢最相似的語義聚類，并以篩選出的語義聚類為文檔和查詢間的橋梁，估計出的穩定性語義聚類模型（SSRM）能夠改善檢索性能。由于不相關噪聲會使相關模型估計中出現偏離用戶查詢主題的問題，SSRM有效利用了穩定性語義聚類的噪聲過濾功能，因而SSRM更接近用戶的查詢需求。另外，SSRM相比基于聚類方法的檢索性能提升，也說明ICA算法是一種適合的語義聚類算法。

研究發現對于多主題文檔，文檔級別上的語義聚類很難將其劃分到合適的類別中。將來的工作考慮段落或者句子粒度上的聚類，并做聚類的穩定性驗證工作。另外，如何根據不同數據集學習適合數據集的訓練參數，也是一個值得研究的問題。

參考文獻：

[1]LIU X， CROFT W B. Clusterbased retrieval using language models[C]// Proceedings of the 27th International Conference on Research and Development in Information Retrieval. New York： ACM， 2004：186-193.

[2]LEE K S， CROFT W B， ALLAN J. A clusterbased resampling method for pseudorelevance feedback[C]// Proceedings of the 31st International Conference on Research and Development in Information Retrieval. New York： ACM， 2008：235-242.

[3]NASIR J A， VARLAMIS I， KARIM A， et al. Semantic smoothing for text clustering[J]. KnowledgeBased Systems， 2013， 54（4）： 216-229.

[4]ALSULAMI B S， ABULKHAIR M F， ESSA F A. Semantic clustering approach based multiAgent system for information retrieval on Web[J]. International Journal of Computer Science & Network Security， 2012， 12（1）：41-44.

[5]HOFMANN T. Probabilistic latent semantic indexing[C]// Proceedings of the 22nd International Conference on Research and Development in Information Retrieval. New York： ACM， 1999：56-73.

[6]HYVARINEN A. Survey on independent component analysis[J]. Neural Computing Surveys， 1999， 2（7）：1527-1558.

[7]HIMBERG J， HYVARINEN A， ESPOSITO F. Validating the independent components of neuroimaging timeseries via clustering and visualization[J]. Neuroimage， 2004， 22（3）： 1214-1222.

[8]PU Q， HE D. Pseudo relevance feedback using semantic clustering in relevance language model[C]// Proceedings of the 18th ACM International Conference on Information and Knowledge Management. New York： ACM， 2009：1931-1934.

[9]蒲強，何大慶，楊國緯.一種基于統計語義聚類的查詢語言模型估計[J].計算機研究與發展，2011，48（2）：224-231.（PU Q， HE D Q， YANG G W. An estimation of query language model based on statistical semantic clustering [J]. Journal of Computer Research and Development， 2011， 48（2）： 224-231.）

[10]劉家辰， 苗啟廣， 宋建鋒. 使用聚類穩定性分析方法增強單類學習算法[J]. 西安電子科技大學學報（自然科學版）， 2015， 2（2）：58-64. （LIU J C， MIAO Q G， SONG J F. Enhanced oneclass learning based on clustering stability analysis[J]. Journal of Xidian University （Natural Science）， 2015， 42（2）： 58-64.）

[11]LAVRENKO V， CROFT W B. Relevancebased language models[C]// Proceedings of the 24th International Conference on Research and Development in Information Retrieval. New York： ACM， 2001：120-127.

[12]劉銘，劉秉權，劉遠超.面向信息檢索的快速聚類算法[J].計算機研究與發展，2013，50（7）： 1452-1463.（LIU M， LIU B Q， LIU Y C. A fast clustering algorithm for information retrieval [J]. Journal of Computer Research and Development， 2013， 50（7）：1452-1463.）

[13]張永，浮盼盼，張玉婷.基于分層聚類及重采樣的大規模數據分類[J].計算機應用， 2013， 33（10）： 2801-2803.（ZHANG Y， FU P P， ZHANG Y T. Largescale data classification based on hierarchical clustering and resampling[J]. Journal of Computer Applications， 2013， 33（10）： 2801-2803.）

[14]KOLENDA T， HANSEN L K， SIGURDSSON S. Independent components in text[J]. Perspectives in Neural Computing， 2000， 32： 235-256.

[15]WEI X， CROFT W B. LDAbased document models for Ad Hoc retrieval[C]// Proceedings of the 29th International Conference on Research and Development in Information Retrieval. New York： ACM， 2006：178-185.