孟祥福 畢崇春 張霄雁 唐曉亮 唐延歡

1(遼寧工程技術(shù)大學(xué)電子與信息工程學(xué)院 遼寧葫蘆島 125105)2 (遼寧工程技術(shù)大學(xué)軟件學(xué)院 遼寧葫蘆島 125105)

?

Web數(shù)據(jù)庫top-k多樣性關(guān)鍵字查詢推薦方法

孟祥福1畢崇春1張霄雁1唐曉亮2唐延歡1

1(遼寧工程技術(shù)大學(xué)電子與信息工程學(xué)院 遼寧葫蘆島 125105)2(遼寧工程技術(shù)大學(xué)軟件學(xué)院 遼寧葫蘆島 125105)

(marxi@126.com)

Web數(shù)據(jù)庫用戶通常使用他們熟知的關(guān)鍵字表達查詢意圖，這可能導(dǎo)致獲取的結(jié)果不能很好滿足其查詢需求，因此為他們提供top-k個與初始查詢語義相關(guān)且多樣化的候選查詢有助于用戶擴展知識范圍，從而更準確完善地表達其查詢意圖.提出一種top-k多樣性關(guān)鍵字查詢推薦方法.1)利用不同關(guān)鍵字在查詢歷史中的同現(xiàn)頻率和關(guān)聯(lián)關(guān)系評估關(guān)鍵字之間的內(nèi)耦合和間耦合關(guān)系；2)根據(jù)關(guān)鍵字之間的耦合關(guān)系構(gòu)建語義矩陣，進而利用語義矩陣和核函數(shù)方法評估不同關(guān)鍵字查詢之間的語義相關(guān)度.為了快速返回top-k個與初始查詢相關(guān)且多樣性的候選查詢，根據(jù)查詢之間的語義相關(guān)度，利用概率密度函數(shù)分析查詢的典型程度，并利用近似算法從查詢歷史中找出典型查詢.對于所有的典型查詢，從中選出少數(shù)代表性查詢，根據(jù)其他典型查詢與代表性查詢之間的語義相關(guān)度，為每個代表性查詢構(gòu)建相應(yīng)的查詢序列；當(dāng)一個新的查詢到來時，評估其與代表性查詢之間的語義相關(guān)度，然后利用閾值算法(threshold algorithm, TA)在預(yù)先創(chuàng)建的查詢序列上快速選出top-k個與給定查詢語義相關(guān)的多樣性候選查詢.實驗結(jié)果和分析表明：提出的關(guān)鍵字之間耦合關(guān)系計算和查詢之間的語義相關(guān)度評估方法具有較高準確性，top-k多樣性選取方法具有較好效果和較高執(zhí)行效率.

Web數(shù)據(jù)庫；多樣性推薦；耦合關(guān)系；典型化分析；top-k選取

關(guān)鍵字查詢無需用戶了解Web數(shù)據(jù)庫的結(jié)構(gòu)和內(nèi)容，而是類似于谷歌和百度等搜索引擎一樣僅使用少數(shù)幾個關(guān)鍵字表達查詢意圖.近年來，關(guān)系數(shù)據(jù)庫上關(guān)鍵字查詢的代表性研究工作主要是基于模式圖(schema graph, SG)[1-3]和候選網(wǎng)(candidate networks, CNs)[4-6]的全文匹配方法.然而，上述方法通常假定用戶能夠使用關(guān)鍵字明確表達自己的查詢意圖，進而主要關(guān)注關(guān)鍵字的形式化匹配及查詢效率，沒有考慮查詢關(guān)鍵字與查詢結(jié)果的語義相關(guān)性.實際上，用戶的查詢意圖通常是模糊或不明確的，并且用戶通常使用自己熟知的關(guān)鍵字表達查詢意圖，因此提出的關(guān)鍵字查詢也并非能夠有效表達出用戶的查詢需求.此外，如果查詢關(guān)鍵字的選擇性過強，還將會導(dǎo)致空或少量查詢結(jié)果問題.這種情況下，為用戶提供一些與初始查詢語義相關(guān)的多樣性候選查詢，有助于擴展用戶的查詢思路，進一步完善其查詢需求的表達.例如當(dāng)科研人員通過DBLP網(wǎng)站進行文獻檢索時，他們所提的查詢關(guān)鍵字通常是某個研究領(lǐng)域的特殊專業(yè)詞匯，有時匹配的結(jié)果會很少，此時他們希望看到與查詢關(guān)鍵字語義相關(guān)的文獻.舉例假設(shè)某位科研人員希望了解信息檢索領(lǐng)域有關(guān)查詢排序的技術(shù)方法，則他很可能輸入的查詢關(guān)鍵字是“information retrieval,ranking,top-k”，這種情況下如果系統(tǒng)能夠為其提供“vector space model”，“l(fā)atent semantic analysis”，“relevance ranking”等與信息檢索和排序函數(shù)相關(guān)的查詢(或查詢關(guān)鍵字)，則對于不了解信息檢索領(lǐng)域的初學(xué)者來說非常重要.由此可見，top-k關(guān)鍵字查詢推薦技術(shù)的關(guān)鍵在于分析關(guān)鍵字之間的語義相關(guān)關(guān)系，進而找到與給定查詢語義相關(guān)的多樣性候選查詢.近年來，從耦合關(guān)系角度分析關(guān)鍵字之間的語義相關(guān)性逐漸興起，文獻[7-9]將耦合關(guān)系分析思想引入到文檔分析、聚類和分類中，有效提高了算法的準確性.作者以前的研究工作[10]提出了基于語義相似度的top-k關(guān)鍵字查詢推薦方法，但在實際應(yīng)用中該方法返回的top-k個候選查詢之間通常非常相似，不能有效拓展用戶知識和查詢視野.針對這一問題，本文在此基礎(chǔ)上進一步研究Web數(shù)據(jù)庫top-k多樣性關(guān)鍵字查詢推薦方法，目的是為普通用戶提供少量語義相關(guān)且彼此具有一定差異的多樣性候選查詢，以便擴展用戶的知識范圍的查詢視野.因此，本文工作對于目前關(guān)鍵字查詢技術(shù)的改善具有重要意義.

1 相關(guān)工作

關(guān)鍵字查詢的研究最早始于信息檢索領(lǐng)域(主要針對無結(jié)構(gòu)化的文本數(shù)據(jù))，后來逐漸擴展到結(jié)構(gòu)化、半結(jié)構(gòu)化以及空間數(shù)據(jù).

近年來，有關(guān)結(jié)構(gòu)化數(shù)據(jù)上的關(guān)鍵字查詢匹配方法大致可分成4類：1)基于模式圖SG的方法，該類方法(如BANKS等)[1-3]把關(guān)系數(shù)據(jù)庫看成一個模式圖，圖中的節(jié)點代表元組，邊代表元組之間的主外鍵約束關(guān)系.對于一個給定的關(guān)鍵字查詢，從圖中找出包含全部或部分查詢關(guān)鍵字的最小子圖作為查詢結(jié)果.2)基于候選網(wǎng)的方法(如DBXplorer，DISCOVER，IR-Style，SPARK等)[4-6]，該類方法首先在每個關(guān)系表中找出包含全部或部分給定查詢關(guān)鍵字的匹配元組，然后每個關(guān)系表中的匹配元組通過主外鍵約束關(guān)系構(gòu)建多個候選網(wǎng)CNs，在此基礎(chǔ)上找出具有最小連接代價的候選網(wǎng)(minimal total joining network of tuples, MTJNT).上述2類方法在理論上都被證明為NP-hard問題，因此需要采用近似方法解決.3)基于元組單元(tuple unit)[11-12]和虛擬文檔(virtual document)[13]的方法.基于元組單元的方法首先利用關(guān)系之間主外鍵約束關(guān)系構(gòu)建視圖，視圖中具有相同主屬性值的記錄集合視為一個元組單元，元組單元是關(guān)鍵字查詢結(jié)果的邏輯單位，關(guān)鍵字查詢結(jié)果就是顯式包含查詢關(guān)鍵字的多個元組單元集合.虛擬文檔與元組單元方法的基本思想類似，都是按主屬性值進行元組聚合，區(qū)別在于后者使用圖模型表示虛擬文檔.4)根據(jù)查詢關(guān)鍵字與元數(shù)據(jù)之間的對應(yīng)關(guān)系將關(guān)鍵字查詢轉(zhuǎn)換成標準的SQL結(jié)構(gòu)化查詢[14-16]，該類方法首先對數(shù)據(jù)進行抽樣，然后分析查詢關(guān)鍵字與元數(shù)據(jù)以及抽樣數(shù)據(jù)之間的對應(yīng)關(guān)系，據(jù)此定義關(guān)鍵字查詢轉(zhuǎn)換規(guī)則，從而將關(guān)鍵字查詢轉(zhuǎn)換成符合用戶查詢意圖的結(jié)構(gòu)化查詢語句.

有關(guān)XML數(shù)據(jù)上的關(guān)鍵字查詢方法，其基本思想是基于最低公共祖先(lowest common ancestor, LCA)及其擴展方法(如(exclusive LCA, ELCA)[17]，(smallest LCA, SLCA)[18]，(MLCA-Meaningful LCA)[19]等)，該類方法先對XML數(shù)據(jù)樹中的節(jié)點進行編碼并構(gòu)建索引，然后查找出XML數(shù)據(jù)樹中顯式包含全部(或部分)查詢關(guān)鍵字的節(jié)點并鑒別出這些節(jié)點的LCA，最后將以LCA為根的子樹作為結(jié)果.關(guān)于空間數(shù)據(jù)的關(guān)鍵字查詢，代表性工作如文獻[20-21]，基本思想是在多維空間中綜合考慮興趣點(point of interests, POI)的位置信息和描述信息與查詢點的距離和與查詢關(guān)鍵字的相關(guān)程度.

現(xiàn)有方法通常在形式上進行查詢關(guān)鍵字的全文匹配，而實際上一個查詢中的關(guān)鍵字之間具有很強的語義相關(guān)性，一個關(guān)鍵字表達的含義會受到其他關(guān)鍵字表達含義的影響，它們合在一起共同表達了用戶的查詢意圖；另一方面，數(shù)據(jù)庫中有些記錄雖然沒有顯式包含查詢關(guān)鍵字，但其在內(nèi)容上可能與查詢十分相關(guān)，上述查詢技術(shù)無法檢索到這些信息.特別是當(dāng)用戶提出的查詢關(guān)鍵字非常具有選擇性或它們之間存在矛盾時，很有可能導(dǎo)致空或少量查詢結(jié)果問題，此時用戶希望系統(tǒng)能為其推薦語義相關(guān)的候選查詢或返回語義相關(guān)的近似查詢結(jié)果.

2 基本概念和解決方案

2.1 基本概念

令D是一個Web數(shù)據(jù)庫，其后臺數(shù)據(jù)庫為關(guān)系數(shù)據(jù)庫，包含關(guān)系表(R1,R2,…,Rn)，每個關(guān)系表包含ni條元組(t1,t2,…,tni)，在此基礎(chǔ)上定義關(guān)鍵字查詢、查詢歷史及相關(guān)概念.

定義1. 關(guān)鍵字查詢.Web數(shù)據(jù)庫D上的關(guān)鍵字查詢Q，是一個包含n個查詢關(guān)鍵字的序列，即Q=[k1,k2,…,kn]，其中每個ki(i∈1,2,…,n)是一個查詢關(guān)鍵字，這些關(guān)鍵字的組合表達了用戶的查詢意圖.

查詢Q中的每個關(guān)鍵字可以是一個單詞或一個短語，取決于如何對關(guān)鍵字查詢進行分解.

定義2. 查詢歷史.Web數(shù)據(jù)庫D上的查詢歷史表示為W={(U1,Q1,K1),(U2,Q2,K2),…,(Un,Qn,Kn)}，其中Ui代表Session ID(一個Session是從用戶連接Web數(shù)據(jù)庫開始到斷開連接為止，這段期間用戶可能會提交多個關(guān)鍵字查詢)，Qi代表查詢ID，Ki代表查詢中包含的查詢關(guān)鍵字.

為了提高查詢歷史的數(shù)據(jù)質(zhì)量，本文采用如下策略修剪查詢歷史：1)去除查詢結(jié)果為空的關(guān)鍵字查詢，因為導(dǎo)致空查詢結(jié)果的查詢沒有意義；2)由于用戶的查詢習(xí)慣通常是由寬泛到具體，用戶通過觀察查詢結(jié)果，逐步改善查詢條件，直到返回有意義的查詢結(jié)果為止，在逐步細化的過程中，最后一個查詢通常是最有實際意義的查詢，因此保留Session中最后一個查詢；3)利用文本分析工具(如AlchemyAPI[22]和Wikipedia[23])對關(guān)鍵字查詢進行分解和規(guī)范化處理.表1給出了基于DBLP數(shù)據(jù)集的修剪后的關(guān)鍵字查詢集合的例子.

Table 1 An Instance of Pruned Keyword Query表1 DBLP數(shù)據(jù)集上修剪后的關(guān)鍵字查詢集合例子

2.2 解決方案

本文提出的Web數(shù)據(jù)庫top-k多樣性關(guān)鍵字查詢推薦方法分成2個處理階段，系統(tǒng)框架如圖1所示.

Fig. 1 Framework of top-k diverse keyword query suggestion system圖1 top-k多樣性關(guān)鍵字查詢推薦系統(tǒng)框架

1) 離線階段.首先在修剪后的查詢歷史中抽取出所有不同的關(guān)鍵字；然后在查詢歷史上利用同現(xiàn)頻率和關(guān)聯(lián)關(guān)系分析方法計算不同關(guān)鍵字之間的耦合關(guān)系；根據(jù)關(guān)鍵字之間的耦合關(guān)系構(gòu)建語義矩陣，再利用核函數(shù)和語義矩陣對查詢歷史中所有不同的關(guān)鍵字查詢進行語義相關(guān)度評估.根據(jù)查詢之間的語義相關(guān)度，利用概率密度估計方法分析查詢的典型程度，然后使用近似算法獲取查詢歷史中具有較高典型程度的查詢，形成典型查詢集合.為了提高top-k候選查詢選取效率，從典型查詢集合中選出少數(shù)代表性查詢，并為每個代表性查詢構(gòu)建一個序列(序列中的元素是查詢歷史中除該關(guān)鍵字查詢之外的所有典型查詢，按其對代表性查詢的語義相關(guān)度降序排列).

2) 在線處理階段.當(dāng)一個關(guān)鍵字查詢到來時，先計算該關(guān)鍵字查詢與代表性查詢之間的語義相似度，然后使用閾值算法(threshold algorithm, TA)在離線階段創(chuàng)建的序列上快速選取前k個與當(dāng)前查詢語義相關(guān)且彼此具有一定差異的查詢提供給用戶，其中當(dāng)前查詢與代表性查詢之間的相似度作為評分函數(shù)的一個權(quán)重，也就是當(dāng)前查詢與某個代表性查詢越接近，那么該代表性查詢對應(yīng)的序列對結(jié)果的影響就越大.

3 關(guān)鍵字之間的耦合關(guān)系評估

本文結(jié)合信息檢索領(lǐng)域文獻[24]提出的文檔-詞條相似度評估思想，利用查詢歷史分析關(guān)鍵字之間的耦合關(guān)系，它包括內(nèi)耦合和間耦合關(guān)系.

3.1 關(guān)鍵字之間的內(nèi)耦合關(guān)系評估

在信息檢索中，如果2個詞條(term)經(jīng)常共現(xiàn)在相同文檔中，則說明這2個詞條在一定程度上語義相關(guān).類似地，在本文環(huán)境下，每個關(guān)鍵字查詢可看成是一個文檔(document)，查詢歷史看成是文檔集合，查詢中的每個關(guān)鍵字看成是一個詞條(term)，那么如果2個關(guān)鍵字經(jīng)常在查詢歷史的相同查詢中共同出現(xiàn)，則說明這2個關(guān)鍵字在一定程度上語義相關(guān).因此，給定一對關(guān)鍵字(ki,kj)，根據(jù)它們在查詢歷史中的共現(xiàn)頻率，其語義相關(guān)性可由Jaccard系數(shù)[25]進行評估：

J(ki,kj)=

(1)

其中，W(ki)和W(kj)分別代表查詢歷史中包含關(guān)鍵字ki和kj的查詢集合，c是給定閾值.基于式(1)，關(guān)鍵字之間的內(nèi)耦合關(guān)系可定義如下：

定義3. 關(guān)鍵字的內(nèi)耦合關(guān)系.如果2個關(guān)鍵字至少在查詢歷史W的某個查詢中共同出現(xiàn)，則它們具有內(nèi)耦合關(guān)系，內(nèi)耦合關(guān)系計算方法如下：

δIaR(ki,kj|W)=J(ki,kj)，

(2)

其中，J(ki,kj)如式(1)所定義.

由于ki和kj還可能與其他關(guān)鍵字共現(xiàn)，因此需要對ki和kj之間的內(nèi)耦合關(guān)系進行歸一化處理.也就是說對于關(guān)鍵字ki，(ki,kj)的內(nèi)耦合關(guān)系在ki與所有其他關(guān)鍵字內(nèi)耦合關(guān)系中所占的比例.所以，關(guān)鍵字(ki,kj)之間的內(nèi)耦合關(guān)系最終按式(3)計算：

(3)

其中，n代表查詢歷史W中所有不同關(guān)鍵字的個數(shù).

算法1. 關(guān)鍵字內(nèi)耦合關(guān)系評估算法.

輸入: 查詢歷史、關(guān)鍵字集合K、關(guān)鍵字個數(shù)n；

輸出: 內(nèi)耦合關(guān)系矩陣IaRMatrix.

①IaRMatrix=?；

② fori=1 ton-1 do

③ fork=i+1 tondo

④IaRMatrix[i][k]=J(K[i],K[k])；

⑤IaRMatrix[k][i]=IaRMatrix[i][k]；

⑥ end for

⑦ form=1 tondo

⑧ if (m≠i) then

⑨Sum=Sum+IaRMatrix[i][m]；

⑩ end if

關(guān)鍵字的內(nèi)耦合關(guān)系反映了在查詢歷史中共現(xiàn)關(guān)鍵字之間的關(guān)聯(lián)關(guān)系.除此之外，2個關(guān)鍵字即便沒有共現(xiàn)，但是它們之間仍然可能存在間接關(guān)聯(lián)關(guān)系.例如，表1中“information retrieval”和“cosine similarity”沒有共現(xiàn)，但它們通過共同關(guān)鍵字“vector space model”間接相關(guān)，本文將關(guān)鍵字之間的這種關(guān)聯(lián)關(guān)系稱為間耦合關(guān)系.

3.2 關(guān)鍵字之間的間耦合關(guān)系評估

給定2個關(guān)鍵字ki和kj，它們在查詢歷史中沒有共現(xiàn)過，但如果與ki和kj同現(xiàn)的關(guān)鍵字集合之間存在交集，則這2個關(guān)鍵字存在間耦合關(guān)系.

給定一個關(guān)鍵字ki，所有與其共現(xiàn)的關(guān)鍵字可看做是ki的語義相關(guān)詞語集合，因此ki和kj的間耦合關(guān)系可以通過二者的語義相關(guān)詞語集合的重合度來評估.例如對于表1中的關(guān)鍵字“vector space model”，其語義相關(guān)詞語集合包括關(guān)鍵字“information retrieval，salton，cosine similarity，SIGIR”；對于關(guān)鍵字“relevance ranking”，其語義相關(guān)詞語集合包括“information retrieval，latent semantic analysis，SIGIR”，由此可見，“vector space model”和“relevance ranking”的語義相關(guān)詞語集合中重疊的關(guān)鍵字為“information retrieval”和“SIGIR”，本文稱其為“共同關(guān)鍵字(common keywords)”.在此基礎(chǔ)上，ki和kj通過共同關(guān)鍵字kc產(chǎn)生的間耦合關(guān)系可定義如下.

定義4. 關(guān)鍵字的間耦合關(guān)系.如果在查詢歷史中至少存在一個關(guān)鍵字，使得δIaR(ki,kc)>0和δIaR(kj,kc)>0成立且ki和kj沒有共現(xiàn)，則ki和kj具有間耦合關(guān)系，它們通過共同關(guān)鍵字kc產(chǎn)生的間耦合關(guān)系計算方法為

δIeR(ki,kj|kc)=min{δIaR(ki,kc),δIaR(kj,kc)}，

(4)

其中，δIaR(ki,kc)和δIaR(kj,kc)分別代表ki和kc，kj和kc的內(nèi)耦合關(guān)系.

需要指出的是，ki和kj之間通常會存在多個共同關(guān)鍵字，并且每個共同關(guān)鍵字在查詢歷史中會有不同重要性.因此，需要評估每個共同關(guān)鍵字的權(quán)重.權(quán)重評估的基本思想是在查詢歷史中出現(xiàn)次數(shù)越多的關(guān)鍵字具有越高權(quán)重，因為出現(xiàn)次數(shù)越多代表用戶查詢該關(guān)鍵字的次數(shù)越多，因此也就說明其越受用戶關(guān)注.令QF(ki)代表關(guān)鍵字ki在查詢歷史中出現(xiàn)的次數(shù)，QFMax代表查詢歷史中最頻繁出現(xiàn)的關(guān)鍵字的出現(xiàn)次數(shù)，關(guān)鍵字的權(quán)重:

(5)

由于ki和kj的共同關(guān)鍵字可能有多個，令S代表ki和kj的共同關(guān)鍵字集合，即S={kc|(δIaR(ki,kc)>0(δIaR(kj,kc)>0)}.關(guān)鍵字ki和kj通過S中所有共同關(guān)鍵字產(chǎn)生的間耦合關(guān)系為

(6)

其中，w(kc)由式(5)計算，δIeR(ki,kj|kc)代表ki和kj通過共同關(guān)鍵字kc產(chǎn)生的間耦合關(guān)系.如果ki和kj的共同關(guān)鍵字多于一個，則式(6)表示的是取ki和kj通過這些共同關(guān)鍵字產(chǎn)生的間耦合關(guān)系的平均值.如果S=?，則δIeR(ki,kj)=0.關(guān)鍵字耦合關(guān)系評估算法如算法2所示.

算法2. 關(guān)鍵字間耦合關(guān)系評估算法.

輸入: 關(guān)鍵字集合K、K中的關(guān)鍵字個數(shù)n、內(nèi)耦合關(guān)系矩陣IaRMatrix、關(guān)鍵字權(quán)重；

輸出: 間耦合關(guān)系矩陣IeRMatrix.

①IeRMatrix=?；

② fori=1 ton-1 do

③ forj=1 tondo

④S←K[i]和K[j]的所有共同關(guān)鍵字；

⑤m=|S|；

⑥ if (S=?) then

⑦IeRMatrix[i][j]=0；

⑧ else

⑨ fork=1 tomdo

⑩minvalue=min{δIaR(K[i],S[k]),δIaR(K[j],S[k])}；

3.3 關(guān)鍵字之間的耦合關(guān)系評估

給定2個關(guān)鍵字ki和kj，它們之間的耦合關(guān)系是內(nèi)耦合關(guān)系和間耦合關(guān)系的結(jié)合，計算方法如下：

(7)

其中，α∈[0,1]是一個參數(shù)，用來調(diào)節(jié)內(nèi)耦合關(guān)系和間耦合關(guān)系在耦合關(guān)系計算中所起的作用.耦合關(guān)系值越大，說明2個關(guān)鍵字之間的語義相關(guān)性越強.需要說明的是，如果α=0，則式(7)將轉(zhuǎn)化成內(nèi)耦合關(guān)系；如果α=1，則式(7)將轉(zhuǎn)化成間耦合關(guān)系.

圖2給出了從表1中抽取出的所有不同關(guān)鍵字的耦合關(guān)系度.這里將式(7)中設(shè)定α=0.5，表示內(nèi)耦合關(guān)系和間耦合關(guān)系在關(guān)鍵字耦合關(guān)系評估中起同等作用.

informationretrievalrelevancerankingsaltonvectorspacemodelcosinesimilaritySIGIRlatentsemanticanalysisdocumentclusteringtf-idfinformationretrieval1.000.090.120.180.090.080.060.000.12relevanceranking0.141.000.140.100.080.180.180.120.14salton0.250.141.000.250.090.100.000.000.25vectorspacemodel0.150.100.101.000.080.080.050.050.10cosinesimilarity0.090.080.090.091.000.200.200.180.09SIGIR0.080.140.100.100.221.000.210.090.10latentsemanticanalysis0.060.110.000.050.190.191.000.170.00documentclustering0.000.120.000.050.250.090.251.000.00tf-idf0.250.140.250.250.090.100.000.001.00

Fig. 2 Example of coupling relationship matrix of keywords
圖2 關(guān)鍵字耦合關(guān)系矩陣實例

從圖2可以看出，同時考慮內(nèi)耦合關(guān)系和間耦合關(guān)系的關(guān)鍵字耦合關(guān)系更為合理.例如對于表1中的2個關(guān)鍵字“relevance ranking”和“cosine similarity”，如果僅考慮內(nèi)耦合關(guān)系，這2個關(guān)鍵字之間的關(guān)系為0；但實際上，這2個關(guān)鍵字在語義上十分相關(guān)，這種相關(guān)性可由間耦合關(guān)系捕獲到.因此，這2個關(guān)鍵字的耦合關(guān)系最終并不是0.本文將關(guān)鍵字之間的耦合關(guān)系存入耦合關(guān)系表中，表結(jié)構(gòu)為{關(guān)鍵字1，關(guān)鍵字2，耦合關(guān)系度}，并在(關(guān)鍵字1，關(guān)鍵字2)上構(gòu)建索引，以便提高檢索效率，進而縮短構(gòu)建語義矩陣(將在4.1節(jié)描述)的時間.

4 語義相關(guān)度計算與典型程度分析

4.1 關(guān)鍵字查詢之間的語義相關(guān)度計算

在信息檢索領(lǐng)域，cosine相似度是基于向量空間模型(vector space model, VSM)的一種常用相似度評估方法.在本文中，查詢歷史可看成是文檔集合，每個查詢看成是一個文檔每個關(guān)鍵字就是文檔中的一個詞條.因此，可以使用cosine相似度進行關(guān)鍵字查詢之間的語義相關(guān)度計算.計算方法可分為3個步驟：

1) 將關(guān)鍵字查詢轉(zhuǎn)換成向量表示

對于給定的一對關(guān)鍵字查詢，其中每個關(guān)鍵字查詢的向量表示都是一個包含n個元素的二元向量VQ，向量VQ中的第i個元素對應(yīng)K中的關(guān)鍵字K[i].如果查詢中存在一個關(guān)鍵字與K[i]對應(yīng)，那么VQ[i]=1；否則VQ[i]=0.

例如給定表1中的一對關(guān)鍵字查詢Q34和Q45，它們共包含5個不同的關(guān)鍵字.假設(shè)關(guān)鍵字的順序為cosine similarity，vector space model，SIGIR，latent semantic analysis，document clustering.基于該順序和上述構(gòu)建向量空間模型的方法，查詢Q34和Q45可以分別用向量[1 1 1 0 0]和[1 0 0 1 1]表示.

2) 構(gòu)建語義矩陣

給定一對查詢，假設(shè)K是這2個查詢中的所有關(guān)鍵字集合，n為K中的關(guān)鍵字個數(shù).根據(jù)關(guān)鍵字之間的耦合關(guān)系，K中所有關(guān)鍵字可以形成一個n×n階的語義矩陣SK，每一個元素SK(i,j)代表關(guān)鍵字ki和kj的耦合關(guān)系，這些值可以從3.3節(jié)描述的關(guān)鍵字耦合關(guān)系表中快速檢索到.

3) 計算關(guān)鍵字查詢之間的語義相關(guān)度

在計算查詢之間語義相關(guān)度過程中，為了保留住關(guān)鍵字之間的耦合關(guān)系，利用步驟2構(gòu)建的語義矩陣將每個查詢對應(yīng)的向量轉(zhuǎn)換成一個新的向量Q′=Q′SK，該向量體現(xiàn)了關(guān)鍵字之間的耦合關(guān)系信息.根據(jù)文獻[26]，2個轉(zhuǎn)換后的向量所對應(yīng)的核函數(shù)可以寫成:

(8)

核方法的基本思想是將低維空間中的非線性可分問題映射到高維空間使其變的線性可分，并利用高維空間中映射函數(shù)的內(nèi)積對低維空間的問題進行分類.其關(guān)鍵在于找到輸入的低維空間到高維空間的映射方法.核函數(shù)的作用是接受2個低維空間的向量輸入，無需尋找從低維空間到高維空間的具體映射，就能夠計算出經(jīng)過某個變換后在高維空間里的向量內(nèi)積值[27].高維空間中的映射函數(shù)的內(nèi)積反映了2個輸入數(shù)據(jù)之間的距離，也就是相似(或相關(guān))性.2個關(guān)鍵字查詢的相似性問題是一個在低維空間中的非線性可分問題，因此本文首先將2個查詢轉(zhuǎn)換成相應(yīng)的向量表示，作為核函數(shù)的輸入，然后利用核函數(shù)來評估兩查詢之間的相似性，核函數(shù)中的語義矩陣SK保留了關(guān)鍵字之間的耦合關(guān)系.最后，根據(jù)cosine相似度評估思想，2個查詢基于核函數(shù)的cosine相似度可定義為

δsim(Qi1,Qi2)=cosker(Qi1,Qi2)=

(9)

查詢歷史中所有不同查詢之間的語義相關(guān)度都可以通過式(9)計算得到.使用基于VSM模型的cosine相似度(簡稱為V-COS)和基于核方法的cosine相似度(簡稱為K-COS)計算得到的不同查詢之間的語義相關(guān)度分別如圖3和圖4所示:

Q12Q25Q34Q45Q53Q64Q121.000.410.000.000.410.41Q250.411.000.330.000.000.67Q340.000.331.000.330.330.33Q450.000.000.331.000.330.00Q530.410.000.330.331.000.00Q640.410.670.330.000.001.00

Fig. 3 Matrix of query similarities obtained by V-COS
圖3 V-COS方法得到的相關(guān)度矩陣

Q12Q25Q34Q45Q53Q64Q121.000.860.740.640.780.87Q250.861.000.740.370.550.98Q340.740.741.000.900.910.74Q450.640.370.901.000.940.37Q530.780.550.910.941.000.55Q640.870.980.740.370.551.00

Fig. 4 Matrix of query similarities obtained by K-COS
圖4 K-COS方法得到的相關(guān)度矩陣

從圖3和圖4可以看出，由K-COS算法得到的查詢之間的語義相關(guān)度的區(qū)分度明顯優(yōu)于V-COS算法.例如在圖3中，查詢Q12與Q25，Q53，Q64的相關(guān)度都是0.41，查詢Q34與Q25，Q45，Q53的相關(guān)度都是0.33；而在圖4中這些值都不相同，并且更貼近實際.

4.2 關(guān)鍵字查詢的典型程度分析

為給用戶提供多樣性候選查詢，需要分析查詢歷史中每條查詢的典型程度，然后保留具有top-k個較高典型程度的查詢作為多樣性候選查詢.

聚類分析與本文所提的典型程度分析具有一定相關(guān)性，聚類分析是將集合中的對象劃分成若干類別，使同一類別中對象之間的相似度盡可能大，不同類別對象之間的相似度盡可能小[28].需要指出的是，典型化分析和聚類分析的目標不同，聚類分析是將對象劃分到不同類別，而典型化分析是要找出代表性對象.一些研究工作把均值點(means)或中心點(medoids)作為一個聚類的代表[29]，然而有時均值點或中心點可能并不是聚類中的代表.如圖5所示，對象B和C分別是集合的均值點和中心點，但分布在A周圍的對象要比B和C的多，因此A要比B和C更具有代表性.

Fig. 5 Difference of medoids,means and typical object圖5 中心點、均值點和典型點對象的區(qū)別

本文提出利用概率密度函數(shù)計算查詢的典型程度，概率密度越大的查詢典型程度越高，也說明其越具有代表性.概率密度是分析集合中某個對象典型程度的核心方法，其基本思想是，給定一個滿足獨立同分布的點集合S和其中一個點o，點o的典型程度與其他點在S中的分布情況有關(guān)，如果點o周圍的點越密集，則o的概率密度越大，那么點o就越具有代表性.根據(jù)查詢之間的語義相關(guān)度，可以將查詢歷史中的所有查詢看成是一個空間中的點集合，其中每個點代表一個查詢，點與點之間的直線距離代表一對查詢之間的語義距離.這樣就可以用概率密度估計方法來評估一個查詢歷史中查詢的典型程.本文采用基于核函數(shù)的概率密度估計方法，核函數(shù)采用常用的高斯核函數(shù)，因為該方法能在數(shù)據(jù)分布未知情況下有效進行概率密度評估[30].

基于上述概率密度分析方法，對于查詢歷史W，其中一條查詢q∈W的典型程度定義為

P(q,W)=f(q|W)，

f(q|W)是W上的概率密度分布函數(shù)：

(10)

給定查詢歷史W(包含n條查詢)和所有查詢之間的語義距離，我們的目標是保留其中m(m?n)條具有較高典型程度的查詢.根據(jù)式(10)，每計算一條查詢的典型程度都需要遍歷W中所有查詢對其的貢獻度，則該算法的時間復(fù)雜度為O(n2).當(dāng)n很大時，算法需要耗費很多時間，因此需要考慮一種的近似解法，本文解決方法的基本思想是：先把查詢歷史W隨機劃分成若干小組，每個小組包含u條查詢，這樣可將W劃分成nu個小組，然后計算每個小組內(nèi)所有查詢的典型程度并從中選取一個具有最高典型程度的查詢，這些查詢構(gòu)成一個新的集合，最后從W中去除其他查詢.對于得到的新集合，重復(fù)執(zhí)行上述過程，直到集合W中只剩下一條查詢?yōu)橹梗瑢⒃摬樵兎湃牒蜻x集中(上述過程記為一次選取過程).為了盡可能確保選取的準確性，將上述選取過程重復(fù)執(zhí)行v次(記為一輪)，這樣候選集中最多存儲v條查詢，然后在最初的查詢歷史W上計算這v條查詢的典型程度，最后輸出一條具有最高典型程度的查詢作為當(dāng)前輪次的選取結(jié)果，并從W中去除該查詢.上述整個過程重復(fù)m輪，這樣就能找到m個近似于準確解的查詢.

算法3. 典型查詢的近似選取算法.

輸入: 查詢歷史W、驗證次數(shù)v、正整數(shù)m、小組大小u；

輸出:m條典型查詢.

① fori=1 tomdo

② fori=1 tovdo

③ repeat

④ 劃分W成為若干小組g，每個小組有u條查詢；

⑤ for each 小組gdo

⑥ 計算g中每個查詢在g的典型程度；

⑦ 從g中選出最典型的查詢，并將g中其他查詢從W中移除；

⑧ end for

⑨ untilW中僅有一條查詢

⑩ 把得到的最典型查詢放入候選集合中；

算法3的復(fù)雜度分析：計算每個小組中所有查詢典型程度的時間復(fù)雜度為O(u2)，每次選取過程要進行l(wèi)=logun次小組劃分.假設(shè)n=ul，在每次選取過程中，第1次劃分可得到nu個小組，第2次劃分可得到(nu)u=nu2個小組，以此類推，這樣每次選取過程總共劃分的小組數(shù)將有個，所以每次選取過程找到最典型查詢的復(fù)雜度是=O(un)，又因為每次淘汰有v次驗證，并且整個淘汰過程循環(huán)m次，因此該算法的時間復(fù)雜度是O(mvun)，其中m，v，u都是比n小很多的正整數(shù).由此可見，該近似選取算法的時間復(fù)雜度要明顯低于準確選取算法.

5 候選查詢的top-k多樣性選取

令Q是一個關(guān)鍵字查詢，T是典型查詢集合.根據(jù)查詢之間的語義相關(guān)度，從T中選取與給定查詢語義相關(guān)的前k個多樣性查詢，該問題定義為

(11)

top-k候選查詢選取方法可分成3個處理步驟：1)選擇代表性查詢；2)為代表性查詢創(chuàng)建序列；3)在線計算當(dāng)前關(guān)鍵字查詢與代表性查詢之間的語義相似度，利用TA算法在查詢序列上選取前k個語義相關(guān)的典型查詢.

5.1 選取代表性查詢

算法4. 代表性查詢選取算法.

輸入: 典型查詢集合T={Q1,Q2,…,Qm};

①Tl≠?；

⑤ for alli=2 toldo

⑨ end for

5.2 創(chuàng)建代表性序列

(12)

其中，τi(Qj)代表查詢Qj在序列τi中的位置.

5.3 候選查詢的top-k選取

在代表性查詢序列上，利用TA算法[31]選取前k個相關(guān)的典型查詢.TA算法通過順序訪問方式發(fā)現(xiàn)每個序列中的某個查詢的排序分數(shù)，然后利用隨機訪問方式從其他序列中發(fā)現(xiàn)該查詢的排序分數(shù)，這些分數(shù)之和作為該查詢在所有序列中的總分數(shù)(總分數(shù)是以該查詢與與其對應(yīng)的代表性查詢之間的相似度作為權(quán)重系數(shù)，進行加權(quán)求和)，定義為

(13)

算法5. 候選查詢的top-k選取算法.

輸入: 代表性序列Tl={τ1,τ2,…,τl}、給定的關(guān)鍵字查詢Q、top-k中的k值；

輸出: top-k個候選查詢.

① 令B={}是能存儲k個關(guān)鍵字查詢的內(nèi)存空間；

② 令L是個一個大小為l的數(shù)組，它用于存儲來自每個序列中的最近一次檢索得到的分數(shù)；

③ repeat

④ for alli∈{1,2,…,l} do

⑤ 從τi中檢索下一個Qj；

⑦ 用Qj在τi中的分數(shù)更新L；

⑧ 通過隨機訪問方式，獲取Qj在其他序列中的分數(shù)；

⑩score(Qj,Q)←所有檢索到的分數(shù)加權(quán) 求和；

6 性能實驗評價

本節(jié)描述實驗環(huán)境，測試各算法性能并與相關(guān)算法進行比較，報告實驗結(jié)果.

6.1 實驗環(huán)境

實驗測試機器配置為Intel PⅣ主頻3.2 GHz處理器、內(nèi)存8 GB.所有算法使用C#和SQL實現(xiàn).實驗數(shù)據(jù)使用2個測試數(shù)據(jù)集：

1) DBLP數(shù)據(jù)集.該數(shù)據(jù)集包含了4個關(guān)系表，分別是Authors，Papers，Write，Proceedings表.它們之間通過主外鍵約束關(guān)系相連接，數(shù)據(jù)庫模式如圖6所示：

Fig. 6 The DBLP schema (PK refers to primary key and FK refers to foreign key)圖6 DBLP數(shù)據(jù)集模式圖(PK代表主鍵、FK代表外鍵)

本文構(gòu)建了基于DBLP數(shù)據(jù)集的Web查詢系統(tǒng)，用戶可通過查詢接口提交查詢.利用該系統(tǒng)征集多個不同研究領(lǐng)域(數(shù)據(jù)庫、數(shù)據(jù)挖掘、信息檢索、機器學(xué)習(xí)、圖形圖像等)的研究人員提交關(guān)鍵字查詢，通過觀察查詢歷史可以發(fā)現(xiàn)，用戶通常在一個Session中提交3～5個查詢，并且查詢條件逐步從寬泛到具體.總共收集5 000條用戶查詢，利用本文第3節(jié)提出的查詢修剪策略，最終保留2 385條查詢作為查詢歷史.查詢關(guān)鍵字涉及Authors.name，Papers.title，Proceedings.name等屬性.由于這些查詢都是由具有專業(yè)背景的研究人員提出的查詢，這些關(guān)鍵字大部分都具有較強的內(nèi)耦合和間耦合關(guān)系，因此基于DBLP的查詢歷史非常適合關(guān)鍵字之間的耦合關(guān)系分析和關(guān)鍵字查詢的語義相關(guān)度評估實驗.

2) IMDB(Internet movie database)：該數(shù)據(jù)集包含了5個關(guān)系表，分別是Actors，Roles，Movies，Movie_diretors，Directors表.它們之間通過主外鍵約束關(guān)系相連接，數(shù)據(jù)庫模式如圖7所示：

Fig. 7 The IMDB schema(PK refers to primary key and FK refers to foreign key)圖7 IMDB模式圖(PK代表主鍵、FK代表外鍵)

由于很難收集到該數(shù)據(jù)集上的真實查詢歷史，本文利用策略模擬查詢歷史：1)根據(jù)數(shù)據(jù)庫模式構(gòu)建視圖，視圖中的每條記錄都是由具有主外鍵約束關(guān)系的元組連接構(gòu)成;2)隨機從視圖中選取10 000條記錄，并從每條記錄的Movies.name，Actors.name，Movies.genre，Roles.role，Directors.name等屬性中抽取關(guān)鍵字;3)從每條記錄已抽取的關(guān)鍵字集合中隨機抽取若干個關(guān)鍵字作為一個關(guān)鍵字查詢.實質(zhì)上，在該方法構(gòu)建的查詢歷史上進行分析，得到的是IMDB數(shù)據(jù)庫中所包含關(guān)鍵字之間的耦合關(guān)系.也就是說，當(dāng)查詢歷史缺失情況下，可以通過從數(shù)據(jù)庫中進行抽樣分析得到關(guān)鍵字之間的耦合關(guān)系，進而實現(xiàn)關(guān)鍵字查詢的相關(guān)推薦.

6.2 關(guān)鍵字耦合關(guān)系的準確性測試

為了測試提出的關(guān)鍵字之間耦合關(guān)系評估方法的準確性，本文在DBLP和IMDB的查詢歷史上分別隨機選取10個關(guān)鍵字.對于每個關(guān)鍵字ki，利用式(7)，將α值從0～1以0.1步長方法進行調(diào)節(jié)，取每個α值對應(yīng)的前5個與當(dāng)前關(guān)鍵字最為相關(guān)的關(guān)鍵字，將這些關(guān)鍵字合起來形成一個關(guān)鍵字集合Ki，即該集合中共有55個關(guān)鍵字(其中有一部分是重復(fù)的關(guān)鍵字).然后，統(tǒng)計集合Ki中出現(xiàn)頻率最高的前5個關(guān)鍵字作為與ki語義上最為相關(guān)的關(guān)鍵字.因為在集合Ki中出現(xiàn)的頻率越高，說明該關(guān)鍵字與給定關(guān)鍵字ki的相關(guān)程度越高.

本文使用查全率(Recall)和準確率(Precision)評價不同α值下關(guān)鍵字之間耦合關(guān)系的準確性.查全率是指檢索到的相關(guān)關(guān)鍵字個數(shù)與相關(guān)關(guān)鍵字總數(shù)之比；準確率是指檢索到的相關(guān)關(guān)鍵字個數(shù)與檢索到的關(guān)鍵字總數(shù)之比.因為相關(guān)關(guān)鍵字個數(shù)和檢索到的關(guān)鍵字個數(shù)都是5，因此查全率和準確率相等.圖8給出了DBLP和IMDB數(shù)據(jù)集上不同α值所對應(yīng)的關(guān)鍵字耦合關(guān)系的準確性(即查全率和準確率)，這里取10個關(guān)鍵字對應(yīng)準確性的平均值.本實驗把式(1)中的閾值c設(shè)為2，因為該值能降低僅共現(xiàn)1次的詞對對內(nèi)耦合關(guān)系評估的影響.

Fig. 8 Accuracy of answers for different values of α on DBLP and IMDB datasets圖8 DBLP和IMDB上不同α值對應(yīng)的準確性

從圖8可以看出，當(dāng)α分別取0.6和0.5時，DBLP和IMDB上的準確性達到了最高值，分別是0.93(DBLP)和0.85(IMDB).由于DBLP上的是真實查詢歷史，關(guān)鍵字之間具有較強的耦合關(guān)系，因此準確性較高；而IMDB的查詢歷史是從原始數(shù)據(jù)中抽樣得到，關(guān)鍵字之間的耦合關(guān)系相對較弱，但是準確性也不低，因此本文方法也適用于原始數(shù)據(jù)中關(guān)鍵字之間的耦合關(guān)系評估.

此外，還可看到對于DBLP數(shù)據(jù)集，α值取從0到0.6時，準確性曲線逐漸上升，說明關(guān)鍵字的間耦合關(guān)系對于準確性的提高具有積極作用；而當(dāng)α值取從0.6～1時，準確性曲線逐漸下降，說明關(guān)鍵字的間耦合關(guān)系對于準確性的提高起到了消極作用.表2給出了當(dāng)α分別取值0，0.6(DBLP)0.5(IMDB)，1時，在DBLP和IMDB上對于給定關(guān)鍵字“association rules”(DBLP)和“Hugh Jackman”(IMDB)的前5個語義相關(guān)關(guān)鍵字.

Table 2 top-5 Relevant Keywords for Different Given Keyword over DBLP and IMDB表2 DBLP和IMDB上與給定關(guān)鍵字相關(guān)的前5個關(guān)鍵字

6.3 關(guān)鍵字查詢語義相關(guān)度的用戶調(diào)查

Fig. 9 Comparison of accuracy for K-COS,V-COS, and Random over DBLP and IMDB圖9 DBLP和IMDB上K-COS，V-COS，Random方法的準確性對比

本文使用用戶調(diào)查方法測試提出的關(guān)鍵字查詢語義相關(guān)度評估方法的準確性.我們首先邀請了10個用戶(博士研究生、碩士研究生和年輕教師)從DBLP和IMDB中各選取10個查詢(每個用戶在每個數(shù)據(jù)集上選取1個查詢).對于每個選取的查詢Qi，利用K-COS，V-COS，Random方法從查詢歷史中獲得前10個相關(guān)查詢，最終合成一個包含30個與給定查詢Qi相關(guān)和不相關(guān)的查詢集合Ki.K-COS和V-COS是本文第4節(jié)提到的方法，Random是隨機選取方法(也就是從查詢歷史中隨機選取10個查詢，該方法作為效果對比的一個基線).在此基礎(chǔ)上，我們把Ki和Qi提供給用戶，由用戶從Ki中標出前10個與Qi相關(guān)的查詢，并且從2方面說明相關(guān)查詢Q′與給定查詢Q的相關(guān)性：

1) 查詢Q′與Q中有部分重疊的查詢關(guān)鍵字，則二者相關(guān)；

2) 查詢Q′與Q包含的關(guān)鍵字之間沒有重疊，但查詢結(jié)果有重疊，則二者也可認為是相關(guān)的.例如，查詢“cosine similarity,vector space model”與查詢“l(fā)atent semantic analysis,document clustering”的查詢結(jié)果之間有部分重疊，說明二者具有語義相關(guān)性，但二者并不包含相同的關(guān)鍵字.

本文用檢索到的相關(guān)查詢個數(shù)與用戶標注的相關(guān)查詢總數(shù)之比來衡量不同關(guān)鍵字查詢語義相關(guān)度評估算法的準確性.圖9給出了在DBLP和IMDB上V-COS，K-COS，Random方法的準確性對比.

從圖9可以看出，K-COS方法的準確性高于V-COS方法.K-COS在DBLP和IMDB上的平均準確性分別為0.88和0.79，而V-COS在DBLP和IMDB上的平均準確性分別為0.66和0.52.這是因為V-COS是在傳統(tǒng)向量空間模型上計算相關(guān)度，僅考慮2個查詢中形式上相同的關(guān)鍵字，沒有考慮關(guān)鍵字之間的耦合關(guān)系；而K-COS同時考慮了查詢之間形式上和語義上的相關(guān)性.因此，得到的語義相關(guān)度更為準確合理.

6.4 多樣性選取的準確性與合理性測試

該實驗?zāi)康氖菧y試本文提出的候選查詢top-k選取方法的準確性與合理性.為了從查詢歷史中獲取前k個與給定關(guān)鍵字查詢最為相關(guān)的典型查詢，最準確的方法是計算給定查詢與典型查詢集合中所有查詢之間的語義相關(guān)度，然后再按語義相關(guān)度大小選取出top-k個候選查詢.由于本文在選取代表性查詢基礎(chǔ)上提出了一種快速top-k選取方法，因此需要驗證僅在代表性查詢排列基礎(chǔ)上選出的top-k個候選查詢與上述方法選取的top-k個候選查詢之間的重疊程度.這里用R(All,k)表示通過計算給定查詢與典型查詢集合中所有查詢之間的相關(guān)度之后選出的top-k個相關(guān)查詢；R(Rep,k)表示利用TA算法在代表性查詢序列上獲取的top-k個相關(guān)查詢.這2個集合之間的重疊程度用Jaccard系數(shù)評估：

J(R(Rep,k),R(All,k))=

(14)

Jaccard系數(shù)的值在[0,1]之間，該值越高，表明重疊程度越高，則top-k選取算法的準確性也就越高.在該實驗中，使用3個參數(shù)描述測試數(shù)據(jù)集：m，l，k，其中，m是指每個代表性查詢序列中的查詢個數(shù)(為了能夠進行準確性評價，本文把數(shù)據(jù)集中的所有查詢看作是典型查詢，因此對于DBLP數(shù)據(jù)集設(shè)置m=2 385，對于IMDB數(shù)據(jù)集設(shè)置m=10 000)，l是代表性查詢序列個數(shù)，k為選取的k個相關(guān)查詢個數(shù).圖10給出了在DBLP和IMDB數(shù)據(jù)集上不同

Fig. 10 Accuracy of top-k selection algorithm for different value of l and k圖10 不同l和k值下top-k選取算法的準確性

l和k值下top-k選取算法的準確性，其中l(wèi)={10,20,40,60,80}，k={10,20,30,40,50,60,70,80,90,100}.

從圖10可以看出，在相同數(shù)據(jù)集的不同l值下，top-k選取算法的準確性相差不大(除IMDB的l=10以外)，這說明僅在少數(shù)代表性查詢序列上選取top-k個候選查詢，其信息丟失程度也很少.同時，還可以看出在DBLP和IMDB上，當(dāng)代表性查詢個數(shù)l≥20時，算法準確性趨于穩(wěn)定，因此這也為代表性查詢個數(shù)l值的選取提供了依據(jù).此外還可看出，在不同k值下，top-k選取算法的準確性隨著k值增大而有所提高，但即便在k值很小的情況下，top-k選取算法準確性也并不低.k值選取方法可以根據(jù)用戶個人需求而定，系統(tǒng)默認值為k=10，也就是默認為用戶提供前10個最為相似的推薦查詢.

下面的實例說明了本文提出的候選查詢top-k多樣性選取方法的合理性.對于給定的查詢，分別利用文獻[10]提出的基于相似度的top-k選取方法(similarity-based top-kselection)和本文提出的top-k多樣性選取方法(top-kdiverse selection)獲取前k個相關(guān)查詢，然后觀察這些查詢之間的語義相關(guān)性和差異性.對于給定查詢，表3給出了2種方法返回的結(jié)果對比.可以看出，基于相似度的top-k選取方法返回的結(jié)果彼此之間非常相似，查詢之間的關(guān)鍵詞重疊度比較高；而本文提出的top-k多樣性選取方法得到的結(jié)果既與給定查詢語義相關(guān)，但彼此之間又有一定差異，從而能夠有效擴展用戶的知識范圍和查詢視野.

Table 3 The Comparison of top-3 Relevant Queries Obtained by Different Methods表3 由不同方法獲得的top-3個相關(guān)查詢對比

6.5 top-k選取算法的響應(yīng)時間測試

該實驗?zāi)康氖菧y試本文提出的top-k選取算法的響應(yīng)時間.在該實驗中，將代表性排列的個數(shù)l值分別固定為10，20，40，60，80，然后測試不同k值下top-k選取算法的響應(yīng)時間，如圖11所示.

從圖11可以看出，top-k選取算法的響應(yīng)時間很快，如果僅返回前10個候選查詢(在實際應(yīng)用中，返回前10個候選查詢基本能滿足用戶需求)，代表性排列數(shù)l為20時(文獻[10]已經(jīng)驗證了當(dāng)代表性排列數(shù)不低于20時，top-k選取方法就能具有較高的準確性)，所需時間不會超過5 s.本文還測試了計算給定查詢與典型查詢集合中所有查詢之間相關(guān)度的時間，該時間在DBLP和IMDB數(shù)據(jù)集上分別為50 s和300 s左右，也就是說不用本文提出的top-k選取方法，獲取前k個查詢需要的時間會很長.因此，本文方法在響應(yīng)時間上具有明顯優(yōu)勢.此外，從圖中還可以看出算法的響應(yīng)時間隨著l和k值的增加而逐漸增長，其原因是當(dāng)l和k值增加后，算法需處理的查詢個數(shù)增多，因此導(dǎo)致響應(yīng)時間增加.

Fig. 11 Execution time of top-k selection algorithm for different value of l and k over DBLP and IMDB datasets圖11 DBLP和IMDB上不同l和k值下top-k查詢選取算法的響應(yīng)時間

7 總 結(jié)

本文提出了一種基于關(guān)鍵字之間耦合關(guān)系的Web數(shù)據(jù)庫top-k多樣性關(guān)鍵字查詢推薦技術(shù).該方法的基本思想是從查詢歷史中選取與給定查詢語義相關(guān)且多樣性的查詢返回給用戶，用戶根據(jù)返回的top-k個多樣性候選查詢，1)可以重新修改初始查詢，使其更加完善；2)可以直接執(zhí)行候選查詢查看相關(guān)結(jié)果.

實驗結(jié)果和分析表明，提出的關(guān)鍵字耦合關(guān)系和關(guān)鍵字查詢語義相關(guān)度評估方法具有較高的準確性，提出的top-k多樣性查詢選取方法能夠有效擴展用戶知識范圍和查詢視野，并且在響應(yīng)時間方面具有絕對優(yōu)勢，特別適用于大規(guī)模數(shù)據(jù)的檢索.本文所提方法既可以作為應(yīng)用層獨立運行，又可以集成在現(xiàn)有關(guān)鍵字查詢系統(tǒng)中提供語義近似查詢服務(wù).如何根據(jù)推薦的top-k個多樣性候選查詢獲得更為細致的查詢結(jié)果是未來研究工作.

[1]Aditya B, Bhalotia G, Chakrabarti S, et al. Banks: Browsing and keyword searching in relational databases[C]Proc of the 28th Int Conf on Very Large Data Bases. San Francisco, CA: Morgan Kaufmann, 2002: 1083-1086

[2]Tata S, Lohman G M. SQAK: Doing more with keywords[C]Proc of the 2008 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2008: 889-902

[3]Ding Bolin, Yu J, Wang Shan, et al. Finding top-kmin-cost connected trees in databases[C]Proc of the 23rd Int Conf on Data Engineering. Los Alamitos, CA: IEEE Computer Society, 2007: 468-477

[4]Agrawal S, Chaudhuri S, Das G. Dbxplorer: A system for keyword-based search over relational databases[C]Proc of the 18th Int Conf on Data Engineering. Los Alamitos, CA: IEEE Computer Society, 2002: 5-16

[5]Hristidis V, Papakonstantinou Y. Discover: Keyword search in relational databases[C]Proc of the 28th Int Conf on Very Large Data Bases. San Francisco, CA: Morgan Kaufmann, 2002: 670-681

[6]Hristidis V, Gravano L, Papakonstantinou Y. Efficient IR-style keyword search over relational databases[C]Proc of the 29th Int Conf on Very Large Data Bases. San Francisco, CA: Morgan Kaufmann, 2003: 850-861

[7]Wang Can, Cao Longbing, Wang Mingchun, et al. Coupled nominal similarity in unsupervised learning[C]Proc of the 20th ACM Int Conf on Information and Knowledge Management. New York: ACM, 2011: 973-978

[8]Wang Can, She Zhong, Cao Longbing. Coupled clustering ensemble: Incorporating coupling relationships both between base clustering and objects[C]Proc of the 29th Int Conf on Data Engineering. Los Alamitos, CA: IEEE Computer Society, 2013: 374-385

[9]Wang Xin, Sukthankar G. Multi-label relational neighbor classification using social context features[C]Proc of the 19th ACM SIGKDD Conf on Knowledge Discovery and Data Mining. New York: ACM, 2013: 464-472

[10]Meng Xiangfu, Cao Longbing, Shao Jingyu. Semantic approximate keyword query based on keyword and query coupling relationship analysis[C]Proc of the 23rd ACM Int Conf on Information and Knowledge Management. New York: ACM, 2014: 529-538

[11]Li Guoliang, Feng Jianhua, Zhou Lizhu. Retune: Retrieving and materializing tuple units for effective keyword search over relational databases[C]Proc of the 27th Int Conf on Conceptual Modeling. Berlin: Springer, 2008: 469-483

[12]Feng Jianhua, Li Guoliang, Wang Jianyong. Finding top-kanswers in keyword search over relational databases using tuple units[J]. IEEE Trans on Knowledge and Data Engineering, 2011, 23(12): 1781-1794

[13]Lopez-Veyna J I, Sosa-Sosa V J, Lopez-Arevalo I. Kesosd: Keyword search over structured data[C]Proc of the 2012 Int Conf on KEYS. New York: ACM, 2012: 23-31

[14]Sarkas N, Bansal N, Das G. Measure-driven keyword query expansion[J]. The VLDB Journal, 2009, 2(1): 121-132

[15]Bergamaschi S, Domnori E, Guerra F. Keyword search over relational databases: A metadata approach[C]Proc of the 2011 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2011: 565-576

[16]Yao Junjie, Cui Bin, Hua Liansheng, et al. Keyword query reformulation on structured data[C]Proc of the 28th Int Conf on Data Engineering. Los Alamitos, CA: IEEE Computer Society, 2012: 953-964

[17]Zhou Rui, Liu Chengfei, Li Jianxin. Fast ELCA computation for keyword queries on XML data[C]Proc of the 13th Int Conf on Extending Database Technology. New York: ACM, 2010: 549-560

[18]Bao Zhifeng, Lu Jiaheng, Ling T W. XReal: An interactive XML keyword searching[C]Proc of the 19th Int Conf on Data Engineering. Los Alamitos, CA: IEEE Computer Society, 2010: 1933-1934

[19]Kong Linbo, Gilleron R, Lemay A. Retrieving meaningful relaxed tightest fragments for XML keyword search[C]Proc of the 12th Int Conf on Extending Database Technology. New York: ACM, 2009: 815-826

[20]Zheng Kai, Su Han, Zheng Bolong, et al. Interactive top-kspatial keyword queries[C]Proc of the 31st Int Conf on Data Engineering. Los Alamitos, CA: IEEE Computer Society, 2015: 423-434

[21]Chen Lisi, Cong Gao, Jensen C S, et al. Spatial keyword query processing: An experimental evaluation[C]Proc of the 39th Int Conf on Very Large Data Bases. San Francisco, CA: Morgan Kaufmann, 2013: 217-228

[22]IBM. AlchemyAPI documentation[EBOL]. 2005 [2015-05-10]. http:www.alchemyapi.com

[23]Huang A, Milne D, Frank E, et al. Clustering documents using a wikipedia-based concept representation[C]Proc of the 13th Pacific-Asia Conf on Knowledge Discovery and Data Mining. New York: ACM, 2009: 628-636

[24]Cheng Xin, Miao Duoqian, Wang Can, et al. Coupled term-term relation analysis for document clustering[C]Proc of the 2013 Int Joint Conf on Neural Networks. Los Alamitos, CA: IEEE Computer Society, 2013: 1-8

[25]Bollegala D, Matsuo Y, Ishizuka M. Measuring semantic similarity between words using Web search engines[C]Proc of the 16th Int Conf on World Wide Web. New York: ACM, 2007: 757-786

[26]AlSumait L, Domeniconi C. Text clustering with local semantic kernels[G]Survey of Text Mining Ⅱ. Berlin: Springer, 2008: 87-105

[27]Wang Xiuhong, Ju Shiguang. Novel kernel function for computing the similarity of text[J]. Journal on Communications, 2012, 33(12): 43-48 (in Chinese)(王秀紅, 鞠時光. 用于文本相似度計算的新核函數(shù)[J]. 通信學(xué)報, 2012, 33(12): 43-48)

[28]Gan Guojun, Ma Chaoqun, Wu Jianhong. Data Clustering: Theory, Algorithms, and Applications[M]. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2007

[29]Bouveyron C, Brunet-Saumard C. Model-based clustering of high-dimensional data: A review[J]. Computational Statistics and Data Analysis, 2014, 71(3): 52-78

[30]Hua M, Pei J, Fu A W C. Top-ktypicality queries and efficient query answering methods on large databases[J]. The VLDB Journal, 2009, 32(18): 809-835

[31]Fagin R, Lotem A, Naor M. Optimal aggregation algorithms for middleware[C]Proc of the 2001 Int Symp on Principles of Database Systems. New York: ACM, 2001: 102-113

Meng Xiangfu, born in 1981. PhD, associate professor, PhD supervisor. His main research interests include user behavior analysis, Web databases top-kquery, non-iidness learning and spatial data management.

Bi Chongchun, born in 1992. Master candidate. His main research interests include spatial data keyword query and spatial data analysis.

Zhang Xiaoyan, born in 1983. PhD candidate, engineer. Her main research interests include top-kranking, spatial data mining.

Tang Xiaoliang, born in 1980. PhD, lecturer. His main research interests include non-iidness learning and remote sensing image processing.

Tang Yanhuan, born in 1992. Master candidate. His main research interests include recommendation system and spatial data mining.

Web Database top-kDiverse Keyword Query Suggestion Approach

Meng Xiangfu1, Bi Chongchun1, Zhang Xiaoyan1, Tang Xiaoliang2, and Tang Yanhuan1

1(SchoolofElectronicandInformationEngineering,LiaoningTechnicalUniversity,Huludao,Liaoning125105)2(SchoolofSoftware,LiaoningTechnicalUniversity,Huludao,Liaoning125105)

Web database users often use the keywords that are familiar to them for expressing their query intentions and this may lead to unsatisfactory results due to the limitation of the users’ knowledge. Providing top-kdiverse and relevant queries can broaden user knowledge scope and thus can help them to formulate more efficient queries. To address this problem, this paper proposes a top-kdiverse keyword query suggestion approach. It first leverages frequency of co-occurrence and correlations between different keywords in query history to measure the intra-and inter-keyword couplings. And then, a semantic matrix, which reserves the coupling relationships between keywords, is generated. Based on the semantic matrix, the semantic similarities between keyword queries can be measured by using a kernel function. To quickly provide the top-kdiverse and semantically related queries, this approach first finds the typical queries from query history by using the probabilistic density estimation method. After this, it finds the representative queries from the set of typical queries and then creates the orders for each representative query according to the similarities of remaining queries in the set of typical queries to the representative query. When a new query coming, the similarities between the given query and representative queries are computed, and then the top-kdiverse and semantically related queries can be selected by using threshold algorithm (TA) over the orders of representative queries. The experimental results demonstrate that both the keyword coupling relationship and query semantic similarity measuring methods can achieve the high accuracy, and the effectiveness of top-kdiverse query selection method is also demonstrated.

Web database; diverse suggestion; coupling relationship; typicality analysis; top-kselection

2016-01-02；

2016-11-04

國家自然科學(xué)基金青年科學(xué)基金項目(61401185)；遼寧省自然科學(xué)基金項目(20170540418)；遼寧省教育廳科學(xué)技術(shù)研究項目(LJYL018) This work was supported by the National Natural Science Foundation of China for Young Scientists (61401185), the Natural Science Foundation of Liaoning Province (20170540418), and the Scientific and Technical Research Fund of Liaoning Provincial Education Department (LJYL018).

TP311.13