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

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

?

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

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

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

(marxi@126.com)

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

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

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

1 相關(guān)工作

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

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

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

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

2 基本概念和解決方案

2.1 基本概念

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

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

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

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

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

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

2.2 解決方案

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

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

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

2) 在線(xiàn)處理階段.當(dāng)一個(gè)關(guān)鍵字查詢(xún)到來(lái)時(shí)，先計(jì)算該關(guān)鍵字查詢(xún)與代表性查詢(xún)之間的語(yǔ)義相似度，然后使用閾值算法(threshold algorithm, TA)在離線(xiàn)階段創(chuàng)建的序列上快速選取前k個(gè)與當(dāng)前查詢(xún)語(yǔ)義相關(guān)且彼此具有一定差異的查詢(xún)提供給用戶(hù)，其中當(dāng)前查詢(xún)與代表性查詢(xún)之間的相似度作為評(píng)分函數(shù)的一個(gè)權(quán)重，也就是當(dāng)前查詢(xún)與某個(gè)代表性查詢(xún)?cè)浇咏敲丛摯硇圆樵?xún)對(duì)應(yīng)的序列對(duì)結(jié)果的影響就越大.

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

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

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

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

J(ki,kj)=

(1)

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

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

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

(2)

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

由于ki和kj還可能與其他關(guān)鍵字共現(xiàn)，因此需要對(duì)ki和kj之間的內(nèi)耦合關(guān)系進(jìn)行歸一化處理.也就是說(shuō)對(duì)于關(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)計(jì)算：

(3)

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

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

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

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

①I(mǎi)aRMatrix=?；

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

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

給定2個(gè)關(guān)鍵字ki和kj，它們?cè)诓樵?xún)歷史中沒(méi)有共現(xiàn)過(guò)，但如果與ki和kj同現(xiàn)的關(guān)鍵字集合之間存在交集，則這2個(gè)關(guān)鍵字存在間耦合關(guān)系.

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

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

δ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之間通常會(huì)存在多個(gè)共同關(guān)鍵字，并且每個(gè)共同關(guān)鍵字在查詢(xún)歷史中會(huì)有不同重要性.因此，需要評(píng)估每個(gè)共同關(guān)鍵字的權(quán)重.權(quán)重評(píng)估的基本思想是在查詢(xún)歷史中出現(xiàn)次數(shù)越多的關(guān)鍵字具有越高權(quán)重，因?yàn)槌霈F(xiàn)次數(shù)越多代表用戶(hù)查詢(xún)?cè)撽P(guān)鍵字的次數(shù)越多，因此也就說(shuō)明其越受用戶(hù)關(guān)注.令QF(ki)代表關(guān)鍵字ki在查詢(xún)歷史中出現(xiàn)的次數(shù)，QFMax代表查詢(xún)歷史中最頻繁出現(xiàn)的關(guān)鍵字的出現(xiàn)次數(shù)，關(guān)鍵字的權(quán)重:

(5)

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

(6)

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

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

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

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

①I(mǎi)eRMatrix=?；

② 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)系評(píng)估

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

(7)

其中，α∈[0,1]是一個(gè)參數(shù)，用來(lái)調(diào)節(jié)內(nèi)耦合關(guān)系和間耦合關(guān)系在耦合關(guān)系計(jì)算中所起的作用.耦合關(guān)系值越大，說(shuō)明2個(gè)關(guān)鍵字之間的語(yǔ)義相關(guān)性越強(qiáng).需要說(shuō)明的是，如果α=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)系評(píng)估中起同等作用.

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)系矩陣實(shí)例

從圖2可以看出，同時(shí)考慮內(nèi)耦合關(guān)系和間耦合關(guān)系的關(guān)鍵字耦合關(guān)系更為合理.例如對(duì)于表1中的2個(gè)關(guān)鍵字“relevance ranking”和“cosine similarity”，如果僅考慮內(nèi)耦合關(guān)系，這2個(gè)關(guān)鍵字之間的關(guān)系為0；但實(shí)際上，這2個(gè)關(guān)鍵字在語(yǔ)義上十分相關(guān)，這種相關(guān)性可由間耦合關(guān)系捕獲到.因此，這2個(gè)關(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)建索引，以便提高檢索效率，進(jìn)而縮短構(gòu)建語(yǔ)義矩陣(將在4.1節(jié)描述)的時(shí)間.

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

4.1 關(guān)鍵字查詢(xún)之間的語(yǔ)義相關(guān)度計(jì)算

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

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

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

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

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

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

3) 計(jì)算關(guān)鍵字查詢(xún)之間的語(yǔ)義相關(guān)度

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

(8)

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

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

(9)

查詢(xún)歷史中所有不同查詢(xún)之間的語(yǔ)義相關(guān)度都可以通過(guò)式(9)計(jì)算得到.使用基于VSM模型的cosine相似度(簡(jiǎn)稱(chēng)為V-COS)和基于核方法的cosine相似度(簡(jiǎn)稱(chēng)為K-COS)計(jì)算得到的不同查詢(xún)之間的語(yǔ)義相關(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算法得到的查詢(xún)之間的語(yǔ)義相關(guān)度的區(qū)分度明顯優(yōu)于V-COS算法.例如在圖3中，查詢(xún)Q12與Q25，Q53，Q64的相關(guān)度都是0.41，查詢(xún)Q34與Q25，Q45，Q53的相關(guān)度都是0.33；而在圖4中這些值都不相同，并且更貼近實(shí)際.

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

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

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

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

本文提出利用概率密度函數(shù)計(jì)算查詢(xún)的典型程度，概率密度越大的查詢(xún)典型程度越高，也說(shuō)明其越具有代表性.概率密度是分析集合中某個(gè)對(duì)象典型程度的核心方法，其基本思想是，給定一個(gè)滿(mǎn)足獨(dú)立同分布的點(diǎn)集合S和其中一個(gè)點(diǎn)o，點(diǎn)o的典型程度與其他點(diǎn)在S中的分布情況有關(guān)，如果點(diǎn)o周?chē)狞c(diǎn)越密集，則o的概率密度越大，那么點(diǎn)o就越具有代表性.根據(jù)查詢(xún)之間的語(yǔ)義相關(guān)度，可以將查詢(xún)歷史中的所有查詢(xún)看成是一個(gè)空間中的點(diǎn)集合，其中每個(gè)點(diǎn)代表一個(gè)查詢(xún)，點(diǎn)與點(diǎn)之間的直線(xiàn)距離代表一對(duì)查詢(xún)之間的語(yǔ)義距離.這樣就可以用概率密度估計(jì)方法來(lái)評(píng)估一個(gè)查詢(xún)歷史中查詢(xún)的典型程.本文采用基于核函數(shù)的概率密度估計(jì)方法，核函數(shù)采用常用的高斯核函數(shù)，因?yàn)樵摲椒茉跀?shù)據(jù)分布未知情況下有效進(jìn)行概率密度評(píng)估[30].

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

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

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

(10)

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

算法3. 典型查詢(xún)的近似選取算法.

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

輸出:m條典型查詢(xún).

① fori=1 tomdo

② fori=1 tovdo

③ repeat

④ 劃分W成為若干小組g，每個(gè)小組有u條查詢(xún)；

⑤ for each 小組gdo

⑥ 計(jì)算g中每個(gè)查詢(xún)?cè)趃的典型程度；

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

⑧ end for

⑨ untilW中僅有一條查詢(xún)

⑩ 把得到的最典型查詢(xún)放入候選集合中；

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

5 候選查詢(xún)的top-k多樣性選取

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

(11)

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

5.1 選取代表性查詢(xún)

算法4. 代表性查詢(xún)選取算法.

輸入: 典型查詢(xún)集合T={Q1,Q2,…,Qm};

①Tl≠?；

⑤ for alli=2 toldo

⑨ end for

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

(12)

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

5.3 候選查詢(xún)的top-k選取

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

(13)

算法5. 候選查詢(xún)的top-k選取算法.

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

輸出: top-k個(gè)候選查詢(xún).

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

② 令L是個(gè)一個(gè)大小為l的數(shù)組，它用于存儲(chǔ)來(lái)自每個(gè)序列中的最近一次檢索得到的分?jǐn)?shù)；

③ repeat

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

⑤ 從τi中檢索下一個(gè)Qj；

⑦ 用Qj在τi中的分?jǐn)?shù)更新L；

⑧ 通過(guò)隨機(jī)訪問(wèn)方式，獲取Qj在其他序列中的分?jǐn)?shù)；

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

6 性能實(shí)驗(yàn)評(píng)價(jià)

本節(jié)描述實(shí)驗(yàn)環(huán)境，測(cè)試各算法性能并與相關(guān)算法進(jìn)行比較，報(bào)告實(shí)驗(yàn)結(jié)果.

6.1 實(shí)驗(yàn)環(huán)境

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

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

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

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

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

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

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

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

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

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

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

6.3 關(guān)鍵字查詢(xún)語(yǔ)義相關(guān)度的用戶(hù)調(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方法的準(zhǔn)確性對(duì)比

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

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

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

本文用檢索到的相關(guān)查詢(xún)個(gè)數(shù)與用戶(hù)標(biāo)注的相關(guān)查詢(xún)總數(shù)之比來(lái)衡量不同關(guān)鍵字查詢(xún)語(yǔ)義相關(guān)度評(píng)估算法的準(zhǔn)確性.圖9給出了在DBLP和IMDB上V-COS，K-COS，Random方法的準(zhǔn)確性對(duì)比.

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

6.4 多樣性選取的準(zhǔn)確性與合理性測(cè)試

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

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

(14)

Jaccard系數(shù)的值在[0,1]之間，該值越高，表明重疊程度越高，則top-k選取算法的準(zhǔn)確性也就越高.在該實(shí)驗(yàn)中，使用3個(gè)參數(shù)描述測(cè)試數(shù)據(jù)集：m，l，k，其中，m是指每個(gè)代表性查詢(xún)序列中的查詢(xún)個(gè)數(shù)(為了能夠進(jìn)行準(zhǔn)確性評(píng)價(jià)，本文把數(shù)據(jù)集中的所有查詢(xún)看作是典型查詢(xún)，因此對(duì)于DBLP數(shù)據(jù)集設(shè)置m=2 385，對(duì)于IMDB數(shù)據(jù)集設(shè)置m=10 000)，l是代表性查詢(xún)序列個(gè)數(shù)，k為選取的k個(gè)相關(guān)查詢(xún)個(gè)數(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選取算法的準(zhǔn)確性

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

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

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

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

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

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

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查詢(xún)選取算法的響應(yīng)時(shí)間

7 總 結(jié)

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

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

[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ì)算的新核函數(shù)[J]. 通信學(xué)報(bào), 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

國(guó)家自然科學(xué)基金青年科學(xué)基金項(xiàng)目(61401185)；遼寧省自然科學(xué)基金項(xiàng)目(20170540418)；遼寧省教育廳科學(xué)技術(shù)研究項(xiàng)目(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