完全加權關聯規則挖掘及其在查詢擴展中的應用

摘要：為了將完全加權關聯規則挖掘技術應用于查詢擴展，提出面向查詢擴展的基于多種剪枝策略的完全加權詞間關聯規則挖掘算法，該算法能夠極大地提高挖掘效率；提出了一種新的查詢擴展模型和擴展詞權重計算方法，使擴展詞權值更加合理，在此基礎上提出一種新的基于局部反饋的查詢擴展算法，該算法利用完全加權關聯規則挖掘算法自動從局部反饋的前列初檢文檔中挖掘與原查詢相關的完全加權關聯規則，構建規則庫，從中提取與原查詢相關的擴展詞，實現查詢擴展。實驗結果表明，查詢擴展算法的檢索性能確實得到了很好的改善和提高，與現有查詢擴展算法比較，在相同的查全率水平級下其平均查準率有了明顯的提高。

關鍵詞：信息檢索； 局部反饋； 查詢擴展； 關聯規則； 項完全加權

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

文章編號：1001－3695(2008)06－1724－04

0引言

由于Internet網絡的開放性和信息發布的容易性，Web信息急劇膨脹，其資源以指數速度增長，導致人們查詢信息時出現信息過載和詞不匹配等難以克服的問題。如何解決信息過載和詞不匹配問題，以致能夠高效、準確地從信息的汪洋大海中尋找到更多所需的信息，一直是信息檢索領域中一個十分重要而富有挑戰的研究課題。查詢擴展（query expansion）是解決信息過載和詞不匹配問題的關鍵技術之一，它指的是利用計算機多種技術，以用戶原查詢為基礎，把與原查詢相關的詞或詞組（如同義詞、近義詞等）添加到原查詢，得到比原查詢更長的新查詢，以便更完整地描述原查詢所隱含的語義或者主題，幫助信息檢索系統提供更多有利于判斷文檔相關性的信息。查詢擴展能夠彌補用戶查詢信息不足的缺陷，改善和提高信息檢索系統的查全率和查準率。傳統的查詢擴展[1]主要有全局分析的、局部分析的以及基于用戶查詢日志的和基于關聯規則挖掘的查詢擴展。



基于關聯規則挖掘的查詢擴展[2~8]是從數據挖掘的角度對查詢擴展進行研究，它利用數據挖掘技術發現與原查詢相關的擴展詞實現查詢擴展，近年來得到較多專家、學者的關注和研究。在現有的基于關聯規則挖掘的查詢擴展研究中，大多是從全局分析的角度進行，而從局部分析的角度進行的研究不多。然而，基于全局的方法要推廣到實際的信息檢索系統難度很大，因為全局分析下的文檔集很大，其文本數據庫中數據項一般都有數千，甚至到數萬，由于頻繁項集的數量是隨著數據庫中數據項數目的增加呈指數增長的，即使采取各種剪枝策略，項集的數量還是非常多，致使挖掘詞間關聯規則的效率和時間無法讓用戶接受，而用戶查詢信息時都追求速度快，信息全而準。另一方面，現有的研究中，很少重視研究關聯規則的挖掘技術及其質量對查詢擴展檢索性能的影響，更沒有考慮在挖掘詞間關聯規則時其特征詞在不同的事務文檔記錄中往往有著不同的重要性而引入完全加權的項權重。針對這些問題，本文首先提出面向查詢擴展的基于多種剪枝策略的完全加權詞間關聯規則挖掘算法，該算法能夠極大地提高挖掘效率；然后，將完全加權關聯規則挖掘技術應用于查詢擴展，提出了一種新的查詢擴展模型和擴展詞權重計算方法，使擴展詞權值更加合理，在此基礎上進一步提出一種新的基于局部反饋的查詢擴展算法，該算法利用完全加權關聯規則挖掘算法自動從局部反饋的前列初檢文檔中挖掘與原查詢相關的完全加權關聯規則，構建規則庫，從中提取與原查詢相關的擴展詞，實現查詢擴展。實驗結果表明，該算法能改善和提高信息檢索系統查全率和查準率，與現有對比算法比較，在相同的查全率水平級下其平均查準率有明顯的提高。

1基于多種剪枝策略的完全加權關聯規則挖掘算法

1．1基本概念

基于向量空間模型的文本數據庫中，每個特征詞項不僅在數據庫中有著不同的重要性，而且在不同的文檔記錄中有著不同的權重，在挖掘詞間關聯規則時應該反映這些不同的權值。在進行詞間關聯規則挖掘時，如果充分考慮了各個特征詞項在不同文檔記錄中有著不同權重，則這種挖掘就稱為項完全加權關聯規則挖掘，簡稱為完全加權關聯規則挖掘。完全加權關聯規則支持度和置信度，以及完全加權頻繁項集和強關聯規則的概念詳見文獻[9]，這里不再詳述。

式(6)左邊部分正好是包含完全加權q-項集T1的k－項集最大可能支持度，由此可知，包含T1的完全加權k－項集一定是非頻繁項集（證畢）。

定理2對于完全加權k－項集的任何子集，只要至少存在一個子集的權值之和小于其k－權值閾值，則該k－項集一定是非頻繁項集。

證明根據題設，對于完全加權k－項集的任何子集，至少存在一個子集的權值之和小于其k－權值閾值，不妨令該子集為Tsub，則由定理1可知道，包含Tsub的k－項集一定是非頻繁項集（證畢）。

1．2多種剪枝策略

在面向查詢擴展的完全加權關聯規則挖掘算法中，采用了多種剪枝策略，最大限度地減少候選項集數量，極大地提高了挖掘效率，具體的剪枝策略是：a)將頻度為0的候選項集剪掉，因為頻度為0的候選項集不可能成為頻繁項集；b)根據定理1對每個候選項集Ck檢查其權值之和與其相應的k－權值閾值比較，如果其權值之和不低于其相應的k－權值閾值，就保留，否則，就將其保存到k中（k是指不可能成為頻繁(k+1)－項集的k－項集集合），并從候選項集集合中刪除該候選項集；c)對各個候選項集Ck，檢查其各個(k-1)_子集，只要存在它的某個子集出現在k-1（k-1是指不可能成為頻繁k－項集的(k-1)－項集集合）中，根據定理2，可以從候選項集集合中刪除該候選項集；d)當挖掘到候選2_項集時，只保留含有原查詢項的候選2_項集，而將不含原查詢項的候選2_項集剪掉，這樣在整個挖掘過程中會極大地減少候選項集的產生，大大提高挖掘效率。這種剪枝策略的理論依據是：查詢擴展的核心問題是如何設計和利用擴展詞的來源，在基于關聯規則挖掘的查詢擴展中，那些含有原查詢項的候選項集、頻繁項集和關聯規則才對查詢擴展有實際意義，而那些不含原查詢詞的關聯規則對查詢擴展沒有貢獻率和實際意義的，因此，只挖掘含有原查詢項的關聯規則可以達到查詢擴展的目的。選擇在候選2_項集進行剪枝，就可以保證在后續挖掘中產生的候選項集都是含有原查詢項的候選項集。雖然這種剪枝策略也會剪掉一部分頻繁項集和關聯規則，但剪掉的頻繁項集和關聯規則絕大部分是不含原查詢項的關聯規則，即使存在少量的含有查詢項的關聯規則，也不會影響查詢擴展的效果。因為，查詢項和擴展項往往都重復出現在各個頻繁項集和關聯規則中，即使減少了部分關聯規則，但是按照所給定的查詢擴展模型，所需的擴展詞都能從現有的關聯規則中提取，實現查詢擴展。為了驗證這種剪枝策略既能極大地提高挖掘效率又不影響其查詢擴展效果，筆者編寫了源程序進行了對比實驗。實驗結果表明，挖掘時采用d)種剪枝策略，其挖掘時間平均可減少89%，減少幅度最大時可以減少99%，，其候選項集比原來的平均減少了96%，頻繁項集的數量比原來的平均減少了94%，關聯規則數量也比原來的平均減少93%，而兩種挖掘方式中所獲得的擴展詞及其權重完全相同。

1．3面向查詢擴展的基于多種剪枝策略的完全加權關聯規則挖掘算法

1．3．1算法基本思想

首先根據包含k－項集的（k+1）－權值閾值，找出在后續遍歷中有可能生成頻繁（k+1）－項集的k－項集，組成候選k－項集Ck，經過本文所述的多種剪枝策略后，產生只含原查詢項的候選項集Ck，由Ck產生頻繁k－項集Lk，同時，通過連接Ck生成候選（k+1）－項集Ck+1，重復運用k－權值閾值逐層迭代發現頻繁項集，直到候選項集集合為空才結束挖掘。最后，根據完全加權置信度從頻繁項集中找出強關聯規則。

1．3．2算法描述

算法： All_weightedassociation rules mining between terms (簡稱AWARMBT算法)

輸入：文本數據庫D ，最小完全加權支持度和置信度閾值（minawsupport和minawconf）。

輸出：完全加權強關聯規則。

Begin

1)掃描數據庫D，找出可能的最大項目集的項目個數(Itemsets_Maxsize)，事務記錄總數(TransactionCount)和項目總數(ItemCount)；

2)for ( j=1; j

3)累加各個1－項集的支持數(SC (C1)，)及權值(SumWeight(C1))、求其最大權值(MaxWeight (C1))以及包含1－項集的2－權值閾值(KIWT (C1，2))，產生C1，1 ，L1；

4)for(k=2;k++) {

5)L=L∪Lk-1;//L為頻繁項集的集合

6)由Ck連接生成Ck+1；

7)if(k=2)

8)進行第d)種剪枝，將不含原查詢項的2_項集剪掉；

9)若k和Ck+1都不空 ，則進行第c)種剪枝；

10)for對于每一個事務記錄

11)累加候選項集Ck在數據庫D中出現頻度；

12)if若候選項集頻度為0

13)進行第a)種剪枝，將頻度為0的候選項集剪掉；

14)for對于每一個事務記錄

15)遍歷文本數據庫D，統計Ck中所有候選項集的權值之和(SumWeight(Ck))和包含Ck的(k+1)－權值閾值(KIWT(Ck，k+1))。

16)進行第b)種剪枝；

17)生成頻繁項目集，并入庫；

18)輸出頻繁項集；

19)若候選項集為空，則退出循環；

20)如果k大于Itemsets_Maxsize，則退出循環

21)}

22)生成強關聯規則；

End

2完全加權關聯規則挖掘在查詢擴展中的應用

完全加權關聯規則挖掘算法考慮了本文數據庫中特征項隨著文檔記錄的不同而各異的情況，挖掘出來的詞間關聯規則比較合理和實際，在信息檢索查詢擴展中具有很高的應用價值。本文將完全加權關聯規則挖掘技術應用到查詢擴展中，提出了一種新的基于局部反饋的查詢擴展算法。下面詳細介紹該算法的基本思想及其具體的實現過程。

2．1算法基本思想

首先對用戶查詢在文檔集中進行初檢，對初檢相似度值排降序，提取前列n篇文檔；然后，對前列初檢文檔進行完全加權詞間關聯規則挖掘，提取含有原查詢項的完全加權關聯規則構建規則庫，根據所給的查詢擴展模型和擴展詞權重計算方法，從規則庫中提取擴展詞添加到原查詢中構建新查詢，實現查詢擴展，最后對新查詢進行第二次檢索。

2．2初檢文檔預處理

基于局部反饋的查詢擴展是假設初檢排序文檔的前列n篇都與原查詢相關（實際上會存在一些不相關的文檔）。其中n的選擇是至關重要的，若n過大，即初檢文檔過多，不相關文檔就多，初檢文檔由于噪聲多而與原查詢總體上的相關性就下降。若n過小，初檢文檔過少，就會遺漏一些相關的反饋信息。為了選擇好n的具體值，本文進行了相關的實驗。實驗結果表明當查詢與文檔的相似度為0.2時其查全率和查準率之間達到最大的折中，檢索性能較好。因此，在本論文的后續實驗中，初檢文檔與查詢的相似度值取0.2，此時獲得的初檢文檔數量就是n值。初檢文檔的預處理指的是對前n篇初檢文檔進行結構化處理，抽取代表其特征的特征詞。即，對前列初檢文檔進行語詞切分、去掉停用詞等預處理，抽取特征詞，計算其權值，建立特征詞庫和以每篇文檔為記錄的向量空間模型文本數據庫。具體的預處理過程：

a)分詞處理。提取初檢文檔中其與查詢的相似值不低于0.2的文檔，對每一篇進行分詞處理，去掉停用詞，提取該篇文檔的特征詞，計算其詞頻及整篇文檔的詞頻最大值，求出整個文檔集的特征詞及其dfj（即包含該特征詞的文檔數量），求每一篇文檔的特征詞權值，存入文本數據庫中。

b)求出整個文檔集的特征詞權值之和，按權值總和值排降序。

c)過濾特征詞。事實上，權值總和較大的特征詞最能反映整個前列n篇初檢文檔的語義內容，而權值總和較小的特征詞對整個前列n篇初檢文檔的語義內容貢獻較少。為了提高挖掘效率，減少挖掘時的特征詞個數，同時也為了減少噪聲，提高關聯規則的質量，需要去掉權值總和較小的特征詞。為此，規定一個特征詞權值總和閾值Wm，取前列特征詞權值總和不低于Wm的特征詞進行詞間關聯規則挖掘。為保證都能挖掘出與每一個查詢項相關的擴展詞，必須使所取的前列特征詞中都包含有全部查詢項，因此，Wm的值應等于特征詞庫里所有查詢項（詞）權值總和中的最低者，此時，若所獲得的特征詞個數低于50，則直接取前列50個特征詞。總之，所取的前列特征詞中必須包含所有的原查詢項并且其數量最少是50個。

2．3查詢擴展模型

本文給出的查詢擴展模型為：Queryi→Expansion_Termj （awsup，awconf），該式是一個完全加權關聯規則，規則前件是查詢項集合，后件是擴展項集合，awsup是完全加權支持度，awconf是完全加權置信度，Queryi代表第i個一個或一個以上的多查詢項組成的集合，Expansion_Termj代表第j個一個或者一個以上的多擴展項組成的集合。

2．4擴展詞權重的計算方法

在查詢擴展中，原查詢項永遠是最重要的，是最能反映用戶查詢意圖的，應該具有最高的權重，擴展詞指的是與原查詢相關的語詞，是原查詢的語義補充和完善，其重要性不會高于原查詢語詞；在基于完全加權關聯規則挖掘的查詢擴展中，由于關聯規則的置信度表明了擴展詞與查詢詞的關聯程度，所以擴展詞的權重可以用其所在的關聯規則置信度（awconf）來充當； 同一個擴展詞往往重復出現在不同的關聯規則前件或后件，有著不同的置信度；擴展詞與整個查詢的相關程度是不同的，存在全相關和部分相關的關聯，若擴展詞只與部分查詢項相關，稱為部分相關，若與原查詢中所有查詢項都相關，稱為全相關，在進行查詢擴展時，擴展詞應體現與整個查詢的相關程度，與整個查詢相關程度越高，其權重應該越大。根據這些原則，本文給出進行查詢擴展時原查詢和擴展詞的權重計算方法如下：原查詢的各個查詢項權重設為2；當擴展詞重復出現在不同的關聯規則中，并且存在不同的置信度（awconf）時，在其支持度不低于所給的最小支持度閾值的情況下，選擇其置信度值最高的關聯規則，并將其置信度作為該擴展詞的置信度，這樣就可以給出擴展詞權重Wexpti的計算公式，即

Wexpti=num1/num2×awconf(7)

其中：num1為與擴展詞項關聯的前件或者后件的原查詢項個數；num2原查詢中所有查詢項總個數；awconf為擴展詞置信度。

2．5基于局部反饋的查詢擴展算法描述

算法：New query expansion algorithm oflocal feedback (簡稱NEQ_of_LF算法)

輸入：原查詢Q，minawsup和minawconf（最小完全加權支持度和置信度閾值）。

輸出：與原查詢Q相關的擴展詞集合及其對應的權重，查詢擴展后的檢索結果。

算法描述：

a） 根據基于向量空間模型的檢索算法（即tf－idf算法）對原查詢Q在文檔集中進行初檢。選取其相似度值不低于0.2的前列排序文檔組成局部前列文檔集。

b） 對a）中的前列文檔集利用本文的AWARMBT挖掘算法進行完全加權關聯規則挖掘，挖掘到（查詢項數+1）_頻繁項集，找出含有原查詢項的頻繁項集生成關聯規則，構建規則庫。

c） 從規則庫中提取擴展詞，計算其權重，存入擴展詞庫中。

d） 將原查詢項的權重置為2，和擴展詞一起構成新查詢實現查詢擴展，再次檢索并輸出結果。

3實驗設計及其結果分析

3．1實驗測試文檔集、查詢集及其語料預處理

從網上下載了720篇計算機方面的論文作為實驗用的原始測試文檔集。設計了10個實際的查詢 （Q1，Q2，…，Q10）作為查詢集供實驗用，在原始測試文檔集中通過人工檢索比較，獲得這10個查詢的相關文檔篇數。對原始測試文檔集經過分詞、去掉停用詞等文檔預處理，提取每一篇文檔的特征詞，計算其權值，構建基于向量空間模型的文本數據庫和整個文檔集的總特征詞庫。對查詢集中的10個查詢也作類似的預處理，得到查詢向量形式。

為了評估查詢擴展算法的檢索性能，將查全率（recall）和查準率（precision）作為評估標準，采用t－檢驗作為對比實驗結果的顯著性驗證。t－檢驗用于信息檢索性能分析在文獻[10]中有詳細的描述。這里僅給出定義，即自由度為（n-1）的t分布為

t=/S(Di)n(8)

其中：=1/nni=1Di；S(Di)=1/（n-1）ni=1(Di-)2；Di為兩種對比實驗數據的差值。

3．2實驗結果及其分析

筆者編寫了實驗源程序，將本文的NEQ_of_LF算法與經典的查詢擴展算法——基于局部上下文分析的查詢擴展[11]（即LCA－Based QE）以及沒有進行查詢擴展的基于向量空間模型的檢索算法（即基線）進行檢索性能比較。三種算法分別對所設計的10個查詢在相同的測試文檔集中進行檢索，統計這10個查詢在相同的查全率水平級下其平均查準率，繪制出查全率/平均查準率曲線圖，其性能比較如圖1所示。本文算法與其他三種算法之間的顯著性驗證(t－檢驗值)比較如表1所示。

表1顯著性驗證比較

項目本文算法VS. tf－idf本文算法VS. LCA－Based QE

t值5. 66. 9

差異是否顯著差異極顯著差異極顯著

備注：(t0.05)9=2.262，(t0.01)9=3.25，(t0.001)9=4.781。

實驗結果表明，相對于傳統的tf－idf算法（即基線），本文算法和LCA－Based QE算法在相同查全率水平級下其平均查準率都有明顯的提高，分別提高了21%和11%。其中本文算法提高幅度最大； 在相同查全率水平級下本文NEQ_of_LF算法的平均查準率比LCA－Based QE算法的提高了9%。表1表明了本文算法與其他兩種對照算法的實驗結果之間在統計上存在顯著性差異，在自由度為9的情況下，其顯著性水平明顯高于臨界值α為0.01時的t檢驗值。

從圖1可以看出，本文提出的NEQ_of_LF算法獲得了很好的結果，能夠改善和提高檢索性能。與現有算法比較，其檢索性能確實獲得了明顯的提高。主要原因分析如下：基于局部上下文分析的查詢擴展算法只考慮從初檢文檔中選出與原查詢詞共現的擴展詞，沒有考慮擴展詞在不同事務文檔中具有不同權重的問題，而本文的查詢擴展算法采用完全加權詞間關聯規則挖掘算法（即AWARMBT算法）在前列n篇初檢文檔中挖掘與原查詢相關的擴展詞，充分考慮了各個特征項及其項集在不同的事務文檔記錄中具有不同的重要性，引入完全加權的項權值，因而挖掘出的詞間關聯規則比較合理，獲得的擴展詞會更加準確地體現與原查詢的語義關系，所以其查詢擴展檢索性能得到很好地改善和提高，比基于局部上下文分析的查詢擴展算法獲得很好的檢索性能；另外，對原查詢進行擴展優化后，一些存在歧義性的查詢詞通過查詢擴展達到消歧作用，能夠檢索到原查詢中所不能檢索到的文檔，這樣就使得本文的查詢擴展算法的檢索性能比傳統的基于向量空間模型檢索算法的有了明顯提高，實驗結果證實了上述結論。

4結束語

本文針對現有查詢擴展存在的缺陷，將完全加權關聯規則挖掘技術與查詢擴展結合起來研究，首先提出面向查詢擴展的基于多種剪枝策略的完全加權詞間關聯規則挖掘算法，該算法能夠極大地提高挖掘效率，然后提出一種新的基于局部反饋的查詢擴展算法，該算法利用完全加權關聯規則挖掘算法自動從局部反饋的前列初檢文檔中挖掘與原查詢相關的完全加權關聯規則，構建規則庫，從中提取與原查詢相關的擴展詞，實現查詢擴展。實驗結果表明了本文查詢擴展算法的檢索性能確實得到了很好的改善，與現有查詢擴展算法比較，在相同的查全率水平級下其平均查準率有了明顯的提高。

參考文獻：

［1］黃名選，嚴小衛，張師超.查詢擴展技術進展與展望[J].計算機應用與軟件，2007，24(11): 1－4.

[2]FONSECA B M，GOLGHER P B，MOURA E S，et al.Discovering search engine related query using association rules[J].Journal of Web Engineering，2004，2(4): 215－227.

[3]ZHANG Cheng－qi，QIN Zhen－xing，YAN Xiao－wei.Association－based segmentation for Chinese－crossed query expansion[J].IEEE Intelligent Informatics Bulletin，2005，5(1):18－25.

[4]QIN Zhen－xing，LIU Li，ZHANG Shi－chao.Mining term association rules for heuristic query construction[C]//Proc of the 8th Pacific－Asia Conference， PAKDD 2004. Sydney:[s.n.]，2004:145－154.

[5]GRY M，HADDAD H. Knowledge discovery for automatic query expansion on the World－Wide Web[C]//Proc of Advances in Conceptual Modeling: ER’99 Workshops， Lecture Notes in Computer Science 1727. Paris:Springer，1999:34－347.

[6]SONG Min， SONG I Y，HU Xiao－hua，et al.Semantic query expansion combining association rules with ontologies and information retrieval techniques[C]//Proc of DaWaK. 2005:326－335.

[7]WEI J，QIN Zhen－xing，BRESSAN S，et al.Mining term association rules for automatic global query expansion:a case study with topic 202 from TREC4[C]//Proc of Americas Conference on Information Systems.2000.

[8]WEI J，BRESSAN S，OOI B C.Mining term association rules for automatic global query expansion:methodology and preliminary results[C]//Proc ofthe 1st International Conference on Web Information Systems Engineering. Hong Kong:[s.n.]， 2000:366－373.

[9]譚義紅，林亞平.向量空間模型中完全加權關聯規則的挖掘[J].計算機工程與應用，2003（13）：208－211.

[10]HULL D.Using statistical testing in the evaluation of retrieval experiments[C]//Proc of ACM SIGIR.1993:329－338.

[11]XU Jin－xi，CROFT B.Query expansion using local and global document analysis[C]//Proc of CAN－SIGIR Conference Retrieval.Zurich，Switzerland:[s.n.]，1996:4－11.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文