基于查詢意圖的數據空間預取方法

祝官文, 周連科, 王念濱, 劉丹

(哈爾濱工程大學 計算機科學與技術學院，黑龍江 哈爾濱 150001)

?

基于查詢意圖的數據空間預取方法

祝官文, 周連科, 王念濱, 劉丹

(哈爾濱工程大學 計算機科學與技術學院，黑龍江 哈爾濱 150001)

摘要：為在查詢前預取用戶可能訪問的數據，提出了一種利用查詢日志的數據空間預取方法。該方法從查詢日志中提取意圖特征，并采用聚類技術對其進行聚類，識別用戶查詢意圖，并基于該意圖預取查詢結果。實驗結果表明：該方法在預取準確率和查詢效率方面均顯著優于已有方法。

關鍵詞：數據空間；預取；查詢意圖；聚類；查詢日志；查詢結果；預取準確率；查詢效率

在大數據時代，數據呈現海量、多樣等特點，面對這些新的數據管理特點，傳統的數據管理系統已無法滿足當今用戶的需求，為此，Michael Franklin等[1]提出了一種嶄新的數據管理思想——數據空間。而正是因為數據空間的特點[2]，導致了用戶對數據空間的查詢訪問產生較大延遲，從而影響了數據空間的服務質量。因此研究如何降低數據空間的訪問延遲，提高數據空間管理系統性能具有重大價值。目前解決網絡延遲、提高查詢效率的有效方法之一是預取技術[3-4]。

目前已有的預取方法總體上可以分為兩類：一種是對用戶歷史訪問序列進行分類總結，判斷用戶當前訪問類型，預測該用戶最可能訪問的數據序列，如基于數據挖掘的預取方法(mining-prefetching，MI)、基于Markov模型的預取方法(Markov-prefetching，MA)等[5-6]；另一種是通過分析用戶最近訪問的數據內容，根據內容之間的關聯，發現最可能被訪問的其它數據，如基于流行度的預取方法[7](popularity-prefetching，PO)、基于神經網絡的預取方法(NN-prefetching，NN)等[8]。

通過對現有的預取方法進行分析發現，它們主要存在以下問題：

1)大多數預取方法都是基于Web非結構化數據的預取，僅針對單一類型數據，而沒有綜合考慮結構化、非結構化等多種異構數據的統一預取機制；

2)除了基于語義的預取方法，其他預取方法都不能對用戶歷史上沒有訪問過的數據進行預取。

3)沒有考慮用戶查詢意圖，預取的效果較差。

為此，本文將用戶查詢意圖應用到數據空間預取中，提出了一種基于查詢意圖的數據空間預取方法(query intent-prefetching，QI)，以有效解決上述問題。其主要思想是：首先提取用戶搜索日志的意圖特征，采用SOM聚類算法將查詢詞相同的用戶搜索日志按照查詢意圖劃分為不同的意圖類，然后識別用戶當前查詢最傾向的意圖類，根據該意圖類對用戶可能訪問的數據進行預測。

1意圖特征提取

查詢意圖是指在用戶提交某一查詢后，實際期望瀏覽的數據。通常情況下，用戶很難通過僅提交一次查詢獲得符合其真實意圖的查詢結果。在數據空間的用戶查詢日志中，每條記錄記載了用戶對某一實體對象的查詢訪問信息，用戶連續訪問的實體對象可能屬于同一個查詢意圖，也可能不屬于同一個查詢意圖。為了便于提取相同查詢詞的不同查詢意圖，本文使用簡單易行的查詢意圖切分方法，把用戶輸入一個查詢詞后做出的連續訪問記錄切分為同一個查詢意圖，若重新輸入新的查詢詞，則將后續訪問記錄切分為另一個查詢意圖。屬于同一個查詢意圖的所有日志記錄記為一個搜索日志。這樣每個搜索日志中包含一條或者多條日志記錄，每條日志記錄中記載了用戶對某一實體的訪問信息。

數據空間擴展倒排列表中記錄了出現在每個實體中的關鍵詞，對于每個搜索日志，可根據擴展倒排列表和詞性分析，從實體中提取出名詞或者專有名詞作為該搜索日志的意圖特征，并采用TF-IDF方法計算出這些特征在該搜索日志中的權重，具體定義如下：

(1)

式中：wij表示第i個特征在第j搜索日志中的權重，tfij表示第i個特征在第j個搜索日志中出現的頻率，max(tfj)表示第j個搜索日志中所有特征出現頻率的最大值，dfi表示包含第i個特征的搜索日志數目，n表示所有搜索日志的數目。

然而TF-IDF機制本身僅僅是一種基于頻率信息的特征權重表示方法，并不能充分體現意圖特征之間、搜索日志之間以及意圖特征和搜索日志之間的語義關聯，也因此不能依據語義信息對用戶查詢意圖進行建模。因此本文引入了LSA(latent semantic analysis)方法對其分析建模[9]，通過低秩近似的方法對搜索日志意圖特征向量進行降維操作，將意圖特征向量映射到低維語義空間，以表達其語義特性。

圖1　SVD分解Fig.1　SVD decompositon

圖1展示了“意圖特征-搜索日志”矩陣進行奇異值分解，其中，矩陣X為“意圖特征-搜索日志”矩陣，m表示所提取的全部特征數，n表示所有的搜索日志數。通過SVD分解，得到由矩陣X的左、右奇異向量分別構成的矩陣F0和D0，以及由所有奇異值自大到小排列構成的對角陣S0，其中r為矩陣X的秩。LSA方法取矩陣F0的前k列，矩陣D0的前k行，矩陣S0的前k個奇異值所得矩陣相乘的積作為原始矩陣的近似X′，并得到Fk、Dk和Sk，從而將意圖特征和搜索日志映射到一個相同的k維語義空間。每個意圖特征由Fk的行向量表示，每個搜索日志的查詢意圖由Dk的列向量表示，又稱此列向量為搜索日志的意圖特征向量，這樣二者之間的關聯關系就可以使用常見的相似性度量方法進行衡量，為用戶日志聚類提供了語義層面的依據。

2基于SOM的用戶搜索日志聚類

意圖特征向量可以邏輯表示搜索日志的查詢意圖，查詢意圖相同的搜索日志具有相似的意圖特征，為了提取出每個查詢詞的不同查詢意圖，需要對查詢詞相同的搜索日志按照意圖相似度的不同進行聚類。

圖2　SOM網絡拓撲結構Fig.2　SOM network topology

SOM[10]是一種自組織特征映射聚類算法，基于神經網絡的基本思想，模擬人腦自組織映射的工作原理，構建包括輸入層和輸出層的SOM網絡。其拓撲結構如圖2所示，輸入層由n個數據節點構成，輸出層則由m個聚類結果節點構成，輸入節點和輸出節點之間相互連接，在訓練過程中逐步迭代賦予各個連接以權重wij(i=1,2...n;j=1,2...,m)，使得對于相似性較高的輸入數據節點被自動映射到相同的輸出聚類節點，形成聚類。本文將每個用戶搜索日志的意圖特征向量作為SOM網絡的輸入，通過SOM網絡自學習過程，將查詢詞相同的用戶搜索日志，按照其查詢意圖的相似度進行聚類。具體聚類過程如下:

1)隨機初始化網絡連接權重[(w11,...,wnm)]；

2)給出一個新的輸入向量[搜索日志的意圖特征向量]；

3)計算輸入向量與競爭層的每一個神經元的距離，當前輸入向量i與第j個神經元的距離D(j) 計算方式為

(2)

4)選擇競爭層中與當前輸入向量距離最近的神經元作為獲勝神經元；

5)賦予獲勝神經元以及與其相鄰的神經元以新的連接權重；

(3)

6)轉步驟2)，重復進行以后各步直至所有搜索日志完成聚類。

3意圖提取

通過對具有相同查詢詞的用戶搜索日志進行聚類，搜索日志根據其意圖特征向量被劃分到不同的類中，每個類代表了查詢詞的不同查詢意圖。意圖提取的主要思想是通過分析每個類實體對象的共同性以及不同類之間實體對象的差異性，提取出該類具有代表性的詞，組成意圖映射Ti，來描述該類的查詢意圖，如圖3所示。

圖3　意圖映射Fig.3　Intent mapping

根據上述思想，可把意圖提取過程分為類內緊湊型提取、類間差異性提取及綜合提取三個部分，類內緊湊型提取過程僅根據詞在一個類內部的出現情況對其重要性進行評價，類間差異性提取過程根據詞在不同類間出現的差異性對其重要性進行評價，最后經過綜合提取過程，把類內緊湊型提取結果和類間差異性提取結果結合起來，對詞進行綜合評價。抽取每個類代表性詞的依據是這個詞在該類的很多搜索日志中頻繁出現，而在其它類中很少出現。意圖提取算法描述如下：

輸入：所有意圖聚類的集合C，閾值λ；

輸出：意圖映射集T；

步驟：

1)Initialize: Foreach(TiinT)Ti=Φ；

2)Foreach(CiinC)

3) Foreach(tjinCi)

4) 類內緊湊型提取：

5)類間差異性提取：

6)綜合提取：

if(Score(Ci,tj)>λ)addtjtoTi

7) returnT；

其中，λ為詞重要性評價閾值，freq(Ci,tj)表示詞tj在類Ci中出現的頻率，max(freq(Ci,t))表示Ci類中所有詞出現的最大頻率，ief(Ci,tj)表示詞tj在類Ci的實體中出現的概率，詞tj相對于類Ci的重要性與freq(Ci,tj)、ief(Ci,tj)成正比，而與該詞在所有類中出現的頻率成反比。

4用戶查詢意圖的識別

準確識別用戶的查詢意圖并快速返回用戶實際需要的數據，對數據空間查詢服務質量有重要影響。用戶查詢意圖識別大致分為兩個過程：

1)根據用戶歷史查詢日志，獲取能夠描述用戶查詢意圖傾向的數據特征的過程，即意圖傾向特征提取過程；

2)根據提取出來的意圖傾向特征，與用戶當前查詢對應的不同查詢意圖進行匹配的過程，即意圖匹配過程。

4.1 意圖傾向特征提取過程

同一用戶不同情況下提出相同的查詢，查詢意圖卻不一定相同，用戶的興趣愛好、實時需求、數據流行度等多種因素都會影響到用戶的意圖傾向。而意圖傾向特征的提取就是要從用戶或者同類用戶的歷史日志中，找出與當前查詢相同的所有搜索日志，從搜索日志中提取出能夠描述用戶意圖傾向的特征，并計算每個特征權重，組成意圖傾向特征向量，意圖傾向特征向量能夠反映出用戶訪問數據的特點。下面將分別描述在用戶曾提出過相同查詢與用戶未提出過相同查詢兩種情況下意圖傾向特征的提取算法。

1)當用戶曾提出過相同查詢時，從該用戶歷史查詢日志中提取意圖傾向特征的算法描述如下：

輸入：搜索日志集LOG，閾值w；

輸出：意圖傾向特征向量L；

步驟：

①Initialize:L=Φ；

血清CA19-9、CEA水平已被證實與胰腺癌的病情變化及對治療的反應相關[4,12]，是目前胰腺癌診斷及預后判斷中應用最為廣泛的2種血清腫瘤標志物。近年研究發現血清CA125水平與胰腺癌的肝轉移及手術獲益相關[13-14]。血清CA242與CA724也是臨床中常用的與消化道腫瘤相關的腫瘤標志物，但敏感度和特異度并不高。本研究結果顯示血清CA19-9和CEA水平升高是晚期胰腺癌患者預后不良的危險因素，而血清CA242、CA125、CA724與患者預后的關系不明顯，再次證實血清CA19-9和CEA水平是預測胰腺癌患者的預后重要指標。

②Foreach(tjinLOG)

⑦if(Weight(tj)>w) add to L；

⑧returnL；

其中，LOG表示用戶歷史查詢日志中，與當前查詢相同的所有搜索日志集合，freq(tj)表示詞tj在LOG中出現的頻率，max(freq(t))表示在LOG中所有詞出現的最大頻率，ief(tj)表示詞tj在LOG的實體中出現的概率，ILF(tj)表示詞tj在LOG的不同搜索日志中出現的概率，詞tj的權重與freq(tj)、ief(tj)、ILF(tj)均成正比，詞tj的權重越高，說明它在LOG的實體、搜索日志中較為普遍存在，能夠描述用戶查詢所有數據的共同特點，可作為該用戶的意圖傾向特征。

2)當用戶未提出過相同查詢時，從同類用戶歷史查詢日志中提取意圖傾向特征的算法描述如下：

輸出：意圖傾向特征向量L；

步驟：

①Initialize:L=Φ；

②Foreach(tjinLOG)

⑧if(Weight(tj)>w′)addtoL；

⑨returnL；

其中，U表示用戶所在的類中曾提出過當前查詢的所有用戶，freq(tj)、ief(tj)、ILF(tj)的含義同從用戶歷史日志中提取意圖傾向特征的算法，與其不同的是，增加了IUF(tj)來表示詞tj在不同用戶的搜索日志中出現的概率，詞tj的權重越高，說明它更能反映同類用戶查詢數據的共同特點，可作為該類用戶的意圖傾向特征。

4.2意圖匹配過程

通過搜索日志聚類與意圖提取，已經得到了每個查詢對應的幾種不同意圖，并采用意圖映射來描述每個查詢意圖，對于用戶當前提出的查詢，意圖匹配的任務就是要根據用戶的意圖傾向特征及每個查詢意圖對應的意圖映射，判斷用戶當前查詢最可能屬于哪種意圖。意圖匹配算法描述如下：

輸入：意圖傾向特征向量L，意圖映射集T；

步驟：

1) Foreach(Ti∈T)

2)Foreach(tinTi)

5)k=argimax{sim(L,Ti)}；

其中，Sim(L,Ti)為用戶當前查詢相對于每種意圖的傾向性度量，若描述某個查詢意圖的重要特征詞在用戶的歷史查詢日志中出現的概率越高，則用戶傾向于該查詢意圖的可能性就越大，最后，通過argimax{sim(L,Ti)}}返回傾向性最大的意圖類別，作為用戶當前查詢的意圖。

5數據預取

在識別出用戶當前查詢的意圖之后，該意圖所屬類中所有搜索日志都具有相同的查詢意圖，它們訪問的實體對象有許多共同的特點，對于其中比較流行訪問的實體對象，很可能是當前用戶查詢訪問對象。因此可根據該意圖所屬類中的用戶歷史查詢日志，提出一種數據預取策略。

6實驗分析

6.1實驗環境與數據集

硬件環境：Intel(R)Core(TM)i5，CPU3.20GHz，內存4G，硬盤1TB。

數據集：目前針對數據空間領域并不存在公用的數據集，因此本實驗從課題組為某單位開發的數據空間信息管理系統β版本中，提取2014年1月至2014年11月500個用戶的2860910條查詢日志作為實驗數據集，其中，4/5作為訓練集，其余作為測試集。用戶查詢日志的每條記錄包括有訪問時間、訪問用戶的ID、查詢搜索詞，訪問實體ID、訪問次序，數據路徑等信息。

6.2評價方法

為了對本文提出的預取方法進行性能評價，本文引入如下性能指標：

1)查詢響應時間

執行N個包含不同格式數據的查詢，在不同時刻執行三次Q1、Q2、Q3，計算3個查詢的平均執行時間作為查詢響應時間:

(4)

其中，Responsetime表示查詢響應時間，T1、T2、T3分別表示執行三次查詢時間。

2)命中率

(5)

其中，HR表示命中率，|R|表示總共發出的訪問請求數，R+表示所發出的訪問請求中，數據已經得到正確預取的請求數。

3)預取準確率

(6)

其中，PR表示預取準確率，P+表示預取出來的數據被訪問的數目，P-表示預取出來的數據沒有被訪問的數目。

4)網絡流量增加率

(7)

其中，ITR為網絡流量增加率，TP表示預取所有數據產生的網絡流量，TSP表示正確預取的數據產生的網絡流量，TP-TSP表示沒有正確預取的數據增加的網絡流量，TT是未使用預取時，讀取所有數據產生的網絡流量。

一般而言，預取準確率越高，命中率越低，網絡流量增加率也較小；而查詢響應時間則受命中率、網絡性能等多種因素影響。

6.3實驗結果與分析

6.3.1詞權重閾值對意圖識別效果的影響

由于詞的權重能夠反映同類用戶查詢數據的共同特點，不同的權重閾值選擇影響用戶的意圖傾向特征選擇的效果，為此，針對不同的閾值下，意圖識別效果進行對比。圖4展示了針對用戶曾提出相同查詢情況，不同閾值w下意圖識別的準確率對比，從圖中可知，閾值取0.14時，意圖識別準確率最高。

圖4　不同閾值w下意圖識別準確率對比Fig.4　Accuracy comparision of intent identification under different threshold w

圖5展示了針對用戶未曾提出相同查詢情況，不同閾值w′下意圖識別的準確率對比，從圖中可知，閾值取0.025時，意圖識別準確率最高。

圖5　不同閾值w′下意圖識別準確率對比Fig.5　Accuracy comparision of intent identification under different threshold w′

6.3.2預取方法有效性驗證

本文從兩個角度分別驗證了預取方法的有效性：預取方法對查詢響應時間的影響和預取的性能。

圖6展示了本文方法(QI)對查詢響應時間的影響。與沒有采取預取的方法相比，明顯加快了查詢速度；另外，在不同流行度取值的情況下，其查詢響應時間也不同，并且在閾值取0.65時其響應時間最小，則預取方法此時效果最佳。

圖6　預取對查詢響應時間的影響Fig.6　Response time comparision of theidentification under different popularity threshold μ′

圖7展示了本文方法(QI)性能情況。隨著流行度閾值取值越大，其預取準確率越高，而命中率與網絡流量增加率則越低當μ′取值小于等于0.25時，由于預取數據量過大，預取數據花費了大量的時間，同時占據了大量的帶寬，雖然命中率比較高，但是預取的準確率卻很低，所以并沒有提高查詢效率；當μ′取值大于等于1.85時，由于預取的數據量很小，命中率較低，所以此時的查詢響應效率與沒有預取時差不多。

圖7　預取效果評估Fig.7　Performance evaluation of our proposed method under different popularity threshold μ′

6.3.3不同方法對比

區別于已有的方法，本文方法(QI)采用基于查詢意圖的方法，從而更加個性化的預取，為此本節與已有方法進行對比，實驗結果如圖8和圖9所示，其中實驗時，流行度閾值選取0.65。

圖8　不同預取方法效果對比Fig.8　Effectiveness comparision of different prefetching proposals

圖9　不同預取方法性能對比Fig.9　Efficiency comparision of different prefetching proposals

從圖8和圖9中可知，本文提出的方法明顯優于已有的方法，而且準確率高達90%以上、時間僅為16.5s。這主要是由于預取結果中大部分與用戶意圖相吻合。

7結論

1)為了進一步提高數據空間查詢效率，本文結合數據空間的特點及現有預取方法的優缺點，在數據空間用戶提出查詢時，分析用戶查詢意圖，對用戶可能訪問的數據進行預測。

2)預取是在緩存技術的基礎上實現的，是緩存技術的擴展，但本文沒有對緩存的替換策略、一致性更新策略等緩存管理機制進行深入研究，未來可對具體緩存管理機制、用戶類型與流行度大小間關系、動態預取等方面做深入研究。

參考文獻：

[1]FRANKLIN M, HALEVY A, MAIER D. From databases to dataspaces: a new abstraction for information management[J]. ACM SIGMOD record, 2005, 34(4): 27-33.

[2]TURAB MIRZA H, CHEN Ling, CHEN Gencai. Practicability of dataspace systems[J]. International journal of digital content technology and its applications, 2010, 4(3): 233-243.

[3]NANDINI N, YOGISH H K, RAJU G T. Pre-fetching techniques for effective web latency reduction - A survey[C]//Proceedings of IEEE AFRICON Conference. Pointe-Aux-Piments, 2013: 1-6.

[4]GAWADE S, GUPTA H. Review of algorithms for web pre-fetching and caching[J]. International journal of advanced research in computer and communication engineering, 2012, 1(2): 62-65.

[5]RAJU G T, SUDHAMANI M V. A novel approach for prefetching of web pages through clustering of web users to reduce the web latency[C]//Proceedings of International Conference On Advances In Computing. [S.l.], 2012: 983-989.

[6]邢永康, 馬少平. 多Markov鏈用戶瀏覽預測模型[J]. 計算機學報, 2003, 26(11): 1510-1517.

XING Yongkang, MA Shaoping. Modeling user navigation sequences based on multi-Markov chains[J]. Chinese journal of computers, 2003, 26(11): 1510-1517.

[7]SHI Lei, GU Zhimin, PEI Yunxia, et al. A PPM prediction model based on web objects′ popularity[C]//Proceedings of the 2nd International Conference on Fuzzy Systems and Knowledge Discovery. Changsha, China: 2005: 110-119.

[8]XU Chengzhong, IBRAHIM T I. A keyword-based semantic prefetching approach in Internet news services[J]. IEEE transactions on knowledge and data engineering, 2004, 16(5): 601-611.

[9]KOU Gang, PENG Yi. An application of latent semantic analysis for text categorization[J]. International journal of computers, communications and control, 2015, 10(3): 357-369.

[10]ASTUDILLO C A, JOHN OOMMEN B. Topology-oriented self-organizing maps: a survey[J]. Pattern analysis and applications, 2014, 17(2): 223-248.

A dataspace prefetching method based on query intent

ZHU Guanwen，ZHOU Lianke，WANG Nianbin，LIU Dan

(College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China)

Abstract：In order to prefetch the data that may be accessed by user before a query was posed, a novel prefetching method towards databaspace by exploiting query logs was proposed. Firstly, some intention features were extracted from the query logs, and the clustering technique was performed on the intention features. Secondly, the user query intention was identified. Finally, the query answers were prefetched according to the identified intention. The experimental results show that the proposed method can not only have a higher accuracy, but also improve the query efficiency, and it outperforms the existing methods.

Keywords：dataspace; prefetching; query intent; clustering; query logs; query answer; prefetch accuracy; query efficiency

中圖分類號：TP311

文獻標志碼：A

文章編號：1006-7043(2016)02-0236-06

doi:10.11990/jheu.201411073

作者簡介：祝官文(1986-), 男, 博士研究生;通信作者：周連科，E-mail：zhoulianke@hrbeu.edu.cn.

基金項目：國家自然科學基金資助項目(61272185); 黑龍江省自然科學基金資助項目(F201238, F020510);.中央高校基本科研業務專項資金資助項目(HEUCFZ1219, HEUCF100608, HEUCF100613).

收稿日期：2014-11-24.網絡出版日期：2015-12-15.

網絡出版地址：http://www.cnki.net/kcms/detail/23.1390.u.20151215.1141.030.html

周連科(1977-), 男, 講師;

王念濱(1967-), 男, 教授, 博士生導師.