一種挖掘查詢語句子話題並聚類的信息搜索方法
2023-10-07 11:06:29 2
專利名稱：一種挖掘查詢語句子話題並聚類的信息搜索方法
技術領域：
本發明屬於計算機信息檢索技術領域，涉及一種挖掘用戶查詢語句的子話題，並對子話題進行聚類的信息搜索方法。
背景技術：
挖掘查詢語句的子話題、將子話題聚類並根據話題包含關係構建樹形的層次結構，可以為用戶提供更精準的查詢擴展、查詢建議，並按文檔所屬話題，在檢索結果中分類展示。目前挖掘查詢子話題的相關研究非常有限，一種方法是從搜尋引擎返回的結果文檔中，抽取關鍵短語並使用數據挖掘的算法，從而找出候選的子話題(參考文獻E. Uluhan and B. Badur. Developmetn of a Framework for Sub-topic Discovery from the Web.2008.In Proceedings ofPICMET2008)。在計算查詢之間的相似度時，則有很多方法。一種方法是使用馬爾科夫隨機場模型計算查詢詞與隱式概念之間的依賴度(參考文獻D. Metzler md W. B. Croft. Latent Concept Expansion Using Markov Random Fields.In Proceedings of SIGIR2007 禾口 H.Lang，D. Metzler, B. Wang, J-T. Li. Improved Latent Concept Expansion Using Hierarchical Markov Random Fields. In Proceedings of SIGIR2010)。另一禾中方法米用上下文模型，計算查詢的上下文之間的相似度，用來表示兩個查詢之間的相似度(參考文獻X. Wang and C. Zhai. Mining term association patterns from search logs for effective query reformulation. In Proceedings ofCIKM2008.)。還有一禾中較為簡單直接的方式，即計算查詢之間的餘弦相似度。聚類算法也有很多，比如常見的K-means、層次聚類等等。有些方法在聚類的同時，還挖掘出該類的中心項，如星形聚類(參考文獻X. Wang and C. Zhai. Mining term association patterns from search logs for effective query reformulation. In Proceedings of CIKM2008.)。在現有的方法中，還未發現有使用查詢日誌作為挖掘查詢子話題的來源，而且在計算查詢語句之間的相似度時，沒有充分考慮到詞彙不匹配問題，以及詞彙過匹配問題。另外現有的聚類方法是基於詞彙相似度的聚類方法，沒有深入挖掘話題之間的包含關係，難以在話題之間建立樹形的層次結構。因此這些聚類方法，在聚類查詢子話題時，存在一定的缺陷，無法充分滿足用戶需求。
發明內容
本發明的目的在於解決現有技術中的問題，提出一種挖掘用戶所查詢的語句的子話題，並對這些子話題進行聚類的信息搜索方法。該方法能夠自動挖掘某個查詢語句所可能包含的所有子話題，根據話題之間的包含關係進行聚類，進而實現為用戶提供更合理的查詢建議、查詢結果的多樣性展示等目的。本發明的挖掘查詢語句子話題並聚類的信息搜索方法，其步驟包括
1)對原始查詢語句和查詢日誌中的歷史查詢語句分別分詞，得到查詢詞序列；2)將對所述歷史查詢語句分詞後得到的查詢詞序列作為候選子話題，計算所述候選子話題與所述原始查詢語句的相似度；3)利用語義詞典找出原始查詢語句的同義表達方式並作為擴展查詢語句，計算所述候選子話題與所述擴展查詢語句的相似度，並用該相似度修正步驟幻所得的相似度；4)根據相似度的預設閥值對所述候選子話題進行篩選，得到最終子話題；5)對所述最終子話題進行聚類，並根據聚類後的子話題間的包含關係構建樹形層次結構；6)搜尋引擎按照所述樹形層次結構對檢索結果進行分類，用戶通過選擇所述樹形層次結構的不同葉子節點來獲得不同分類粒度的檢索結果。進一步地，利用每個所述歷史查詢語句在查詢日誌中出現的次數修正步驟3)最終得出的相似度；還可通過計算每個所述歷史查詢語句與所述原始查詢語句的點擊相似度，並用該點擊相似度進進一步修正步驟幻最終得出的相似度；所述點擊相似度採用如下公式計算
\υρΓΛυ0\CL(P^Q) = K \ f )其中，集合％和Uq分別為用戶在查詢歷史查詢語句Pi和原始查詢語句Q時點擊的
\υρΓΛυ0\
所有url ；/(1^^)為單調上升函數。進一步地，步驟1)所述的查詢日誌包括用戶提交的查詢語句、查詢時間和點擊的結果文檔。進一步地，通過餘弦相似度方法計算所述候選子話題與所述原始查詢語句的相似度或所述候選子話題與所述擴展查詢語句的相似度。進一步地，所述語義詞典包括HowNet和同義詞詞林。進一步地，所述篩選是將與原始查詢語句的相似度小於所述預設閥值的候選子話題刪去。進一步地，所述聚類的方法包括K-means方法和後綴樹聚類方法。進一步地，在所述聚類後的每個類中選取一個歷史查詢作為該類的中心項，根據該中心項的話題包含關係構建所述樹形層次結構。本發明利用查詢日誌挖掘用戶查詢語句的子話題，這些子話題可以用於擴展用戶查詢，或者為用戶提供更多的查詢建議；對查詢子話題進行聚類，並按照話題的包含關係構建樹形的層次結構，可以根據需要從不同的粒度來為用戶提供查詢擴展、查詢建議等，還能根據子話題的結構，對搜尋引擎返回的結果文檔劃分層次結構，方便用戶按照話題類別來瀏覽檢索結果。
圖1為本發明實施例的挖掘查詢子話題並聚類的信息搜索方法的流程圖。圖2為本發明實施例的對查詢子話題構建樹形結構的示意圖。
具體實施例方式下面通過實施例並結合附圖，對本發明作詳細的說明。圖1為本實施例的挖掘查詢子話題並聚類的信息搜索方法的流程圖，對各個步驟具體說明如下1)對原始查詢語句和歷史查詢語句分詞a)設原始查詢語句為Q，對其分詞，得到一串查詢詞序列Qlq2...qn，其中 Qi(i e [Ο,η])為單個查詢詞；b)設查詢日誌中的所有歷史查詢語句為P = {P1;P2，…PJ，對每個歷史查詢語句 Pi分詞，得到一個查詢詞序列PilPi2... Pim，其中Pu(j e
)為單個查詢詞；將這些查詢詞序列(仍用Pi表示)作為候選子話題。所述查詢日誌是用戶在使用搜尋引擎時，由搜索服務提供商記錄的用戶的一系列行為，包括用戶提交的查詢語句、查詢時間、點擊的結果文
檔等信息。2)子話題挖掘對候選子話題進行挖掘，得到最終子話題。a)計算候選子話題Pi與原始查詢語句Q的相似度Sin^Pi，Q)，可以使用餘弦相似度的方法進行計算，也可以使用其它方法。使用餘弦相似度方法進行計算的公式如下，其中 W是Pi或Q中的查詢詞力―)和Cq(W)分別是W在Pi或Q中出現的次數
Σ cPj{w)c0{w)
SimjPnQ)=廣6 ,(ι)
\ wePf^ WEgb)為解決原查詢語句Q與歷史查詢Pi的詞彙不匹配問題，利用語義詞典對原始查詢Q進行擴展，找出與原始查詢語句Q同義的多種表達方式1^, ，…，Qn}，進而計算候選子話題Pi與每個擴展查詢語句A的相似度Sim(Pi, Qj)。詞彙不匹配屬自然語言處理領域的經典問題，是指兩個詞彙或語句在字面上存在較大差異，但是表達同一個語義。中文可用的語義詞典非常多，如HowNet、同義詞詞林等資源。將原始查詢Q分詞後得到詞序列qiq2. . . qn，對每一個詞I，從語義詞典中抽取它的所有同義詞，組成同義詞集合 Si = {s|s e synonyms ( )}。然後分別使用每一個同義詞Sij代替原始查詢語句Q中的查詢詞I，組成一個新的查詢，即擴展後的查詢語句，得到擴展查詢集合IA，( ，…，Qn}。使用公式(1)計算每一個擴展後查詢％與歷史查詢Pi的相似度Sin^Pi，Qj) 0然後我們通過加權求和用Sim (P」 Qj)來更新候選子話題Pi與原始查詢語句Q的相似度Sim (Pi, Q)，即SMiP1,Q) = W0SimiP1 ,Q) + ^ WjSimiPl,Qj)(2)
J其中，公式右邊的Sim(PyQ)由公式⑴計算得來，Wj為相應的權重。c)為進一步解決原查詢語句Q與歷史查詢語句Pi的詞彙過匹配問題，利用查詢日誌中的點擊信息來判別歷史查詢與原查詢是否屬於同一查詢意圖。詞彙過匹配問題是指 兩個詞彙或語句字面的相似度非常高，即使用了很多共同的詞語，但是表達的語義相差很大。首先考慮了歷史查詢Pi在查詢日誌中的出現次數對該子話題的影響。當Pi在查
5詢日誌中出現的次數越多，對其相似度賦予更高的係數，當Pi出現的次數較少時，相似度則得到較小的係數。進而對公式(2)有如下更新Sim (P" Q) = f (C(Pi)) □ Sin^P」 Q) (3)其中，等式右邊的SinKPi, Q)由公式⑵計算而來。其次，採用點擊相似度來增強候選子話題Pi與原始查詢語句Q的相似度Sin^Pi， Q)。從查詢日誌中，分別統計出用戶在查詢Pi和Q上點擊的所有url，記為集合％和UQ，根據兩個集合的重合度，來計算PjPQ的點擊相似度CL(Pi;Q)，如公式(4)所示CL(P^Q) = A Ρ· β\)
ιuPi ι十丨 ι⑷
\UR rd/0 I其中，/(+〃+)為單調上升函數；f可根據需要進行調整。在不同的數據集
I U Pi I + I Uq I
上，可能使用不同的f函數才能得到最佳效果，根據在模型訓練階段的實驗結果，確定用何 \UP r,U0 I \upr,u0\ \UP r,U0 I IogIf^nfT0I
種 f 函數，如/(ι 廣111 二) = , ' 『 ι 『 『) = ,、等；還可以對
I ^ I +1 ^e I I ^ I +1 ^e I I ^ I +1 ^e I log(| UPi\ + \UQ\)
lLJ ^u , 1θ§( Σ WrUi)
每個url賦予一定權重，然後進行計算，W( TT\ Jt ) = , /'eVt7g7，其中，Ui為相應
I^ I + I^e I log( Σ w'ui)
U1 &U UUq
集合中的url，分子中的 為集合。％中的元素，分母中的1^為集合〃。〃e中的元素，Wi 為每個Ui所對應的權重。然後利用CUPi, Q)再次更新Sin^Pi，Q)的得分，如公式(5)所示SinKPi, Q) = CL (Pi, Q) □ SinKPi, Q) (5)其中，公式右邊的Sim(PyQ)由公式(3)計算得來。至此，得到最終的候選子話題 Pi與原始查詢語句Q的相似度Sim (P" Q)；d)通過相似度的預設閥值對所述候選子話題進行篩選，如果Sim (P」 Q)大於某個閾值δ，則保留該歷史查詢，作為查詢Q的最終子話題。3)子話題聚類首先採用常用的聚類方法，如K-means方法、後綴樹聚類方法等，根據最終子話題所屬的領域進行聚類。然後在每個類中選取一個歷史查詢作為該類的中心項，根據中心項的話題包含關係，構建樹形的層次結構。父節點的話題範圍更為廣泛，子節點的話題範圍則較為具體，即父節點中的話題較子節點的話題更為泛化。下面是通過一個查詢實例對上述流程作更具體、直觀的說明。1)任務初始化(對查詢語句分詞)a)原始查詢Q = 「蘋果MP3」，對其分詞後得到序列Q = 「蘋果MP3」 ；b)查詢日誌中有歷史查詢P1 = 「蘋果MP3保修」，P2 = 「蘋果MP3價格」，P3 = 「蘋果MP3售後服務」，P4 =「iPod報價」，P5 = 「蘋果施肥」，經過分詞後，分別得到序列「蘋果 MP3保修」，「蘋果MP3價格」，「蘋果MP3售後服務」，「 iPod報價」，「蘋果施肥」，每個查詢在日誌中出現的次數分別為c (Pi)。2)子話題挖掘
a)使用公式(1)計算候選子話題Pi與原始查詢語句Q的相似度Sin^Pi，Q)；b)查詢語義字典，得到「蘋果」的同義詞有{ 「iP0d」，「apple」}，「MP3」的同義詞有 { 「數位音樂播放器」 }，代入原始查詢得到Q1 =「iPod MP3」，Q2 = "apple MP3」，Q3 「蘋果數位音樂播放器」。根據公式(1)，計算每個擴展查詢A原始查詢語句Q的相似度Sim (Pi, Qi)。再根據公式⑵，更新相似度Sim(PiiQ)；c)結合每個歷史查詢在日誌中出現的次數C(Pi),根據公式(3)，修正每個歷史查詢Pi與原始查詢語句Q的相似度Sim(PpQ)；根據公式(4)計算每個歷史查詢Pi與原始查詢語句Q的點擊相似度CL (Pi, Q)，再根據公式( 更新查詢Pi與原始查詢語句Q的相似度 Sim(Pi, Q)；d)根據事先約定的閾值δ，當查詢Pi與原始查詢語句Q的相似度Sim(PyQ)小於該閾值時，剔除該查詢，本例中可以剔除P5,因為其與原始查詢語句Q的點擊相似度為0，因 ift Sim(P5, Q)較小。3)子話題聚類a)經過步驟1、2，得到子話題P1, P2，P3，P4,聚類得到三類(P1, P3I, {P2}和{P4}。b)其中{P1; P3I屬話題「服務」，{PJ和{PJ屬於話題「價格」，這兩個話題均是原始查詢Q的子話題，根據話題的包含關係，構建出樹形的層次圖，如圖2所示。圖2是一個三層的樹形結構，根節點為「蘋果MP3」，是用戶提交的初始查詢，葉子節點為該查詢語句的子話題聚類，每個聚類中包含多個具有相同信息需求的子話題。圖中第二層節點為子話題聚類的父節點，即該層節點的話題範疇包含葉子節點的話題範疇，並且範疇更為寬泛。搜尋引擎在返回所有的檢索結果之後，按照葉子節點聚類的結果，對這些檢索結果進行分類。用戶可以根據自己的需求，選擇不同的分類粒度來顯示檢索結果。當用戶選擇顯示「聚類1」的結果時，將分類標籤為「聚類1」的檢索結果呈現給用戶；當用戶選擇顯示「蘋果MP3價格」的結果時，將分類標籤為「聚類2」和「聚類3」的檢索結果呈現給用戶。上述實施例僅是為了說明本發明的原理，而非用於限制本發明的範圍。本領域的技術人員可在不違背本發明的技術原理及精神下，對實施例作修改與變化。本發明的保護範圍應如權利要求所述。
權利要求
1.一種挖掘查詢語句子話題並聚類的信息搜索方法，其步驟包括1)對原始查詢語句和查詢日誌中的歷史查詢語句分別分詞，得到查詢詞序列；2)將對所述歷史查詢語句分詞後得到的查詢詞序列作為候選子話題，計算所述候選子話題與所述原始查詢語句的相似度；3)利用語義詞典找出原始查詢語句的同義表達方式並作為擴展查詢語句，計算所述候選子話題與所述擴展查詢語句的相似度，並用該相似度修正步驟幻所得的相似度；4)根據相似度的預設閥值對所述候選子話題進行篩選，得到最終子話題；5)對所述最終子話題進行聚類，並根據聚類後的子話題間的包含關係構建樹形層次結構；6)搜尋引擎按照所述樹形層次結構對檢索結果進行分類，用戶通過選擇所述樹形層次結構的不同葉子節點來獲得不同分類粒度的檢索結果。
2.如權利要求1所述的方法，其特徵在於，利用每個所述歷史查詢語句在所述查詢日誌中出現的次數修正所述步驟3)最終得出的相似度。
3.如權利要求2所述的方法，其特徵在於，計算每個所述歷史查詢語句與所述原始查詢語句的點擊相似度，並用該點擊相似度進一步修正步驟幻最終得出的相似度；所述點擊相似度採用如下公式計算
4.如權利要求1所述的方法，其特徵在於，所述查詢日誌包括用戶提交的查詢語句、查詢時間和點擊的結果文檔。
5.如權利要求1所述的方法，其特徵在於，通過餘弦相似度方法計算所述候選子話題與所述原始查詢語句的相似度或所述候選子話題與所述擴展查詢語句的相似度。
6.如權利要求1所述的方法，其特徵在於，所述語義詞典包括HowNet和同義詞詞林。
7.如權利要求1所述的方法，其特徵在於，所述篩選是將與原始查詢語句的相似度小於所述預設閥值的候選子話題刪去。
8.如權利要求1所述的方法，其特徵在於，所述聚類的方法包括K-means方法和後綴樹聚類方法。
9.如權利要求1所述的方法，其特徵在於，在所述聚類後的每個類中選取一個歷史查詢作為該類的中心項，根據該中心項的話題包含關係構建所述樹形層次結構。
全文摘要
本發明提供一種挖掘查詢語句的子話題，並對子話題進行聚類的信息搜索方法。該方法將原始查詢語句和歷史查詢語句分別分詞，得到查詢詞序列，計算原查詢語句與歷史查詢語句的相似度。進一步可將原查詢通過語義詞典進行擴展，計算擴展查詢語句與歷史查詢語句的相似度，並修正歷史查詢語句與原始查詢語句的相似度；還可通過歷史查詢語句的點擊信息進一步修正歷史查詢語句與原始查詢語句的相似度。然後通過相似度的預設閥值選出最終子話題，並對其進行聚類以及構建樹形的層次結構。用戶通過選擇樹形層次結構的不同葉子節點來獲得不同分類粒度的檢索結果，方便用戶按照話題類別來瀏覽檢索結果。
文檔編號G06F17/30GK102419778SQ20121000477
公開日2012年4月18日 申請日期2012年1月9日 優先權日2012年1月9日
發明者孫樂, 江雪 申請人:中國科學院軟體研究所