譚濤　譚樂婷　張剛園

摘要：Deep Web蘊含海量的可供訪問的信息，是數(shù)據(jù)庫領(lǐng)域的研究熱點。目前已有的多數(shù)研究主要集中在Deep Web數(shù)據(jù)集成的技術(shù)層面.數(shù)據(jù)集成雖然滿足了對Deep Web信息查詢的需要，但這樣的查詢不能學(xué)習(xí)用戶的興趣，造成時間和資源的浪費。針對這樣的需求，本文將個性化推薦引入到Deep Web的數(shù)據(jù)查詢中，提出了一種結(jié)構(gòu)化數(shù)據(jù)細粒度管理的用戶模型， 和基于樹結(jié)構(gòu)的Deep Web爬取方案，用樹的遍歷方法解決了個性化服務(wù)中分布在各個Web數(shù)據(jù)庫中信息爬取的問題。最后通過實驗驗證了個性化推薦的執(zhí)行效率及Deep Web爬取的覆蓋率。

關(guān)鍵詞：Deep Web；個性化爬??；相似度；用戶興趣模型

中圖分類號：TP393 文獻標(biāo)識碼：A 文章編號：1009-3044（2016）02-0008-03

Abstract： Deep Web is becoming a hot research topic in the area of database. Most of the existing researches mainly focus on Deep Web data integration technology. Deep Web data integration can partly satisfy people's needs of Deep Web information search， but it cannot learn users interest， and people search the same content online repeatedly would cause much unnecessary waste. According to this kind of demand， this paper introduced personalization recommendation to the Deep Web data query， proposed a user interest model based on fine-grained management of structured data and a crawl technology based on the tree structure is presented， with the traversal method of tree to solve the information crawl problems in the personalization service distributed in various web databases. Finally， developed a prototype recommendation system and verified the efficiency and effectiveness of the personalization recommendation and the coverage and cost of Deep Web crawl through the experiment.

Key words： Deep Web； Personalization Crawl； Similarity； User Interest Model

1 概述

互聯(lián)網(wǎng)的飛速發(fā)展使Web成為了海量的信息中心，Web上的網(wǎng)站和網(wǎng)頁數(shù)量快速增長，其信息量巨大，提供的數(shù)據(jù)攜帶著重要的價值，能應(yīng)用于許多業(yè)務(wù)領(lǐng)域。這些信息按照蘊含的深度可以將整個網(wǎng)絡(luò)分為兩大部分：Surface Web和Deep Web。那些直接通過超級鏈接由傳統(tǒng)搜索引擎爬取到的頁面集合屬于Surface Web；而廣泛存在于可在線訪問的Web數(shù)據(jù)庫中的大量信息，通常傳統(tǒng)的搜索引擎是索引不到的，這些內(nèi)容則屬于Deep Web的范疇。隨著Web 2.0時代的到來，目前的整個網(wǎng)絡(luò)至少有65萬個數(shù)量級的可訪問Web數(shù)據(jù)庫，其信息容量覆蓋了商業(yè)，教育，醫(yī)學(xué)等眾多領(lǐng)域，遠遠超過了Surface Web的信息含量。越來越多的國內(nèi)外學(xué)者投入到對Deep Web的應(yīng)用研究中。

本文提出了一種結(jié)構(gòu)化數(shù)據(jù)細粒度管理的用戶模型；同時，針對在Web數(shù)據(jù)庫中信息的個性化爬取的問題，采用了樹結(jié)構(gòu)模型的爬取技術(shù)；并通過原型試驗進行了驗證。

2 相關(guān)原理

網(wǎng)站，超鏈接，數(shù)據(jù)庫及其查詢接口是構(gòu)成Deep Web的基本要素。網(wǎng)站后臺由服務(wù)器支持，包含多個網(wǎng)站數(shù)據(jù)庫，用以存放在線訪問的信息；同時網(wǎng)站數(shù)據(jù)庫又通過HTML表單查詢，表單即為查詢接口。個性化服務(wù)是依據(jù)用戶的瀏覽習(xí)慣和歷史記錄為其后面的訪問提供個性化推薦，采用用戶模型來描述用戶興趣，進行相似度匹配，將相似度高的信息推薦給用戶。用戶興趣不是一成不變的，因此構(gòu)造用戶模型是一個不斷學(xué)習(xí)更新的過程，需要跟蹤用戶習(xí)慣從而及時更新推薦信息。

由于Deep Web數(shù)據(jù)的動態(tài)變化，要從中準(zhǔn)確地獲取用戶所需信息，在數(shù)據(jù)集成方面的研究得到了研究者們的廣泛關(guān)注。至今，在該研究領(lǐng)域已經(jīng)取得了若干成果，比如Deep Web的頁面獲取[5，6]、查詢接口的集成[3，4]、結(jié)果數(shù)據(jù)的抽取與標(biāo)注[7，8]等。而個性化推薦應(yīng)用上發(fā)展也日趨成熟，比如擴展語義的用戶興趣建模及更新策略[11]，在基于Deep Web數(shù)據(jù)的個性化推薦應(yīng)用上，也取得了一定的成果。

3 用戶興趣模型的構(gòu)建

3.1用戶興趣模型的表示

用戶的興趣特點是多樣的，并且是不斷變化的，采用感興趣和不感興趣兩類去刻畫，顯得過于簡單，且不能有效地描述用戶多個方面的興趣特征，尤其對于那些頻繁更新的短期興趣變化，就得不到及時地跟蹤更新?？紤]到上述因素，本文構(gòu)建了結(jié)構(gòu)化數(shù)據(jù)細粒度管理方式。該用戶興趣模型依據(jù)領(lǐng)域本體由下到上的歸納合并，形成過程簡單，描述準(zhǔn)確；同時細化了用戶興趣，通過分門別類地描述降低了不同類別間主題的干擾程度，有利于短期興趣的更新和推薦模型精度的提高。

本文中，用戶興趣模型被形式化描述為一個五元組M：M={S，K，L，W，T}。其中，K=（Ku，Kc）；S為用戶興趣模型建立的狀態(tài)，K為對應(yīng)主題的特征項，由兩部分組成：Ku為更新前興趣模型中的特征；Kc為經(jīng)過動態(tài)更新后的特征。對于初始的用戶模型狀態(tài)S0， 由于沒有反饋信息，不需對其進行更新，故Kc 為一個空集；K的語義由L代表，用招聘信息進行描述。如職位，行業(yè)，工作經(jīng)驗等；W表示特征項K的權(quán)重；T表示更新時間，主要用來幫助分析用戶興趣變化。例如：M={Si，Ki，Li，Wi，Ti}，Si為該用戶興趣模型在動態(tài)調(diào)整更新中產(chǎn)生的主題狀態(tài)；對應(yīng)的特征項集合Ki， Ki =（Kiu，Kic）；L={Li1，Li2，….，Lim}為對應(yīng)Ki的語義；Wi代表特征Ki的權(quán)重，是一個[0，1]之間的值；Ti為對應(yīng)Si的更新時間。

3.2用戶興趣模式的相似度計算

用戶的初始興趣模型建立起來后，接下來需要解決的就是相似度匹配，及根據(jù)匹配結(jié)果進行個性化推薦?；舅枷胧牵簩⒏呦嚓P(guān)度的信息作為種子，在其模式庫中利用相似度擴展近鄰，在用戶興趣庫中尋找類似的興趣信息，從而提高召回率。我們還嘗試了利用統(tǒng)計和機器學(xué)習(xí)的方法，改進經(jīng)典的相似度度量，以獲得更好的效果。

定義1：用戶提交的查詢Q：一個Deep Web查詢由一組關(guān)鍵字組成，Q={qi|qi∈Q，1<=i<=k}其中，Q為用戶查詢的關(guān)鍵字集合。

定義2：Web數(shù)據(jù)庫的查詢接口WDBI（Web Database Interface）：由屬性名、所屬數(shù)據(jù)類型以及相應(yīng)的候選值構(gòu)成，定義如下：WDBI={|Ai∈A，ADTi∈ ADT，AVAi∈AVA，1

定義3：給定查詢詞集合Q1：含m個數(shù)據(jù)，Q1中各數(shù)據(jù)的權(quán)重分別為：wq1，wq2，….wqm，用戶興趣模型中的狀態(tài)集合S2：含n個數(shù)據(jù)， S2中個數(shù)據(jù)的權(quán)重分別為ws1，ws2，…，wsn，將Q1中的數(shù)據(jù)qi和S2中的數(shù)據(jù)sj進行相似性匹配，相似性度量方法定義為：Sim（Q1，S2）=（（max[i=1mj=1nWqi*Wsj]）*aij）*vAi其中aij的引入目的是保證wqi 與wsj 只參與一次配對的相似性匹配。當(dāng)wqi 與wsj 配對時，aij=1；否則aij=0。

其中vAi表示W(wǎng)eb數(shù)據(jù)庫查詢接口上不同數(shù)據(jù)類型引起的不同的屬性相似性度量值。采用一個由文本關(guān)鍵字組成的向量表示文本類型，令Wi是用戶興趣模型Si基于屬性Ai的特征向量，Wj是數(shù)據(jù)查詢基于屬性Ai的特征向量，通過向量之間夾角的余弦值表示，公式為：

4 Deep Web的爬取

Web數(shù)據(jù)庫的爬取實質(zhì)是在找到一個查詢詞集Q={q1，q2，…，qm}使得查詢詞的覆蓋率在爬取代價<=常數(shù)的約束情況下取到最大值。針對查詢詞的覆蓋率及爬取代價定義如下：

定義1.給定查詢屬性qi和Web數(shù)據(jù)庫WDB，查詢屬性qi的爬取代價Exp（qi，WDB）定義為：Exp（qi，WDB）= ND（qi，WDB）/k （1）

其中ND（qi，WDB）表示W(wǎng)eb數(shù)據(jù)庫中匹配qi的結(jié)果記錄數(shù)，k表示目標(biāo)Web站點每個查詢結(jié)果列表頁面展示的最大記錄數(shù)。

定義2.給定查詢屬性qi和Web數(shù)據(jù)庫WDB，查詢屬性qi的覆蓋率Cov（qi，WDB）定義為：Cov（qi，WDB）= ND（qi，WDB）/NWDB （2）

其中ND（qi，WDB）表示W(wǎng)eb數(shù)據(jù)庫中匹配qi的結(jié)果記錄數(shù)， NWDB表示W(wǎng)eb數(shù)據(jù)庫中總的記錄數(shù)。

當(dāng)查詢表單接口中存在一組查詢屬性集Q={q1，q2，…，qm}，該屬性集的覆蓋率Cov（q1q2 …qm，WDB）=（ND（q1，WDB）∪…∪ND（qm，WDB））/ NWDB （3）

其中ND（q1，WDB）∪…∪ND（qm，WDB）表示查詢屬性q1，q2，…qm 的Web數(shù)據(jù)庫所有查詢記錄的并集的總數(shù)。

為了在有限次的查詢次數(shù)限制下，找到查詢詞序列使其覆蓋率最大化，本文提出了基于樹結(jié)構(gòu)的Deep Web數(shù)據(jù)爬取方法。Web數(shù)據(jù)庫被看做一個關(guān)系模式的數(shù)據(jù)表。考慮如下：一個Web數(shù)據(jù)庫表T：該表由定義在結(jié)果屬性集AL={al1，al2，…，alm}上的記錄集D={d1，d2，…，dn}組成；同時，查詢表單接口中存在一組查詢屬性集Q={q1，q2，…，qm}。用戶通過填寫表單項指定查詢屬性的值，這些查詢在底層數(shù)據(jù)庫中轉(zhuǎn)化為SQL查詢語句。

定義3.Web數(shù)據(jù)庫的劃分。將一個Web數(shù)據(jù)庫表T劃分為若干非空子集{T1，T2，…，Tm}，T中的每個元組分屬于某個子集Ti， 根據(jù)等價關(guān)系的理論，當(dāng)Ti∩Tj=且T1∪T2∪…∪Tm =T時，稱Ti是T的劃分塊?；谏鲜龆x，一個Web數(shù)據(jù)庫被劃分為若干不相交的塊，那么查詢結(jié)果的元組就分屬于其中一個特定的塊。

如果結(jié)果記錄集D的數(shù)量非常大，通常會依據(jù)某種排序規(guī)則進行查詢的排序，只返回滿足查詢條件的前面k條記錄（其中k為一個常數(shù)，如1000或1500）。這樣就存在3種結(jié)果返回情況：

（1）當(dāng)k<|T|時，向上溢出，結(jié)果記錄不能全部返回；（2）當(dāng)|T|=0時，向下溢出，結(jié)果記錄返回為空；（3）當(dāng)0<|T|

定義4.多叉樹。數(shù)據(jù)庫表T的層次樹DT（T）是關(guān)于查詢詞的多叉樹。構(gòu)造如下：對一組查詢詞集Q={q1，q2，…，qm}，一個查詢的屬性Ai表示樹中的節(jié)點，該屬性的一個屬性值通過從該節(jié)點出發(fā)的邊表示。如果屬性Ai的屬性值的集合為V={v1，v2，…，vn}，Vi稱為屬性Ai的域，那么屬性節(jié)點Ai就有n條邊。樹中的第m+1層為葉子節(jié)點。

根據(jù)定義4，數(shù)據(jù)庫中每條記錄都屬于不同的葉子節(jié)點，而從根節(jié)點到葉子節(jié)點的邊構(gòu)成了抽取該記錄的結(jié)構(gòu)化查詢，在此基礎(chǔ)之上，Deep Web數(shù)據(jù)庫的爬取問題就轉(zhuǎn)化為樹的遍歷問題，即通過遍歷樹抽取有效葉子節(jié)點中的記錄。由于考慮從根節(jié)點到葉子節(jié)點的邊，采用深度優(yōu)先的遍歷原則。具體的遍歷過程如下：

（1）從根節(jié)點中的查詢詞序列的任意一個查詢q0開始，提交給Web數(shù)據(jù)庫WDB；

（2）如果返回的結(jié)果集|T|>k（閾值）時，上溢，則繼續(xù)從下一層選擇一個查詢，加入到查詢路徑中組成新的查詢；循環(huán)該過程，直到找到一個葉子節(jié)點；

（3）如果找到一個葉子節(jié)點，繼續(xù)利用其父節(jié)點的其他屬性值構(gòu)建遍歷的該葉子的兄弟節(jié)點；否則，執(zhí)行（2）；

（4）判斷葉子節(jié)點的有效性，如果有效，則提取記錄并保存，否則，丟棄該葉子節(jié)點。

5 個性化信息爬取實驗

為了客觀評估基于Deep Web的用戶個性化爬取方法，我們實現(xiàn)了一個招聘系統(tǒng)的原型，并在真實的Web數(shù)據(jù)庫上進行了驗證。針對15個注冊用戶，每個用戶5個初始選擇興趣，從用戶的首次查詢開始記錄并返回數(shù)據(jù)，對每個興趣，系統(tǒng)設(shè)置從Deep Web數(shù)據(jù)源獲得的最大返回信息條目為30。 在本實驗部分，我們使用三個Deep Web數(shù)據(jù)源： 智聯(lián)招聘、中華英才網(wǎng)、前程無憂網(wǎng)。進行Deep Web數(shù)據(jù)的爬取。對用戶的查詢qi，三個數(shù)據(jù)源獲得的招聘信息條目數(shù)為762，905，689條。利用前文所述的推薦原理，對上述的15個注冊用戶進行了推薦，分兩個方面進行：（1）實時推薦：在用戶查詢qi提交時，在返回結(jié)果記錄時根據(jù)相似度匹配進行了高相似度的信息推薦；（2）定時推薦：在用戶預(yù)約的固定時間段，當(dāng)服務(wù)器處于閑置狀態(tài)時，集中進行計算，將爬取到的新的信息反饋給用戶。采用信息檢索領(lǐng)域的查準(zhǔn)率P和查全率R進行衡量。針對15個注冊用戶，每個用戶5個初始選擇興趣，構(gòu)建了同類興趣和不同類興趣的學(xué)習(xí)，假定15個用戶的初始興趣都有“計算機”，記錄了此時15個用戶的學(xué)習(xí)模型，如圖1所示；另一方面，每個的用戶的興趣都會發(fā)生改變，記錄了某個用戶UserI的學(xué)習(xí)模型的改變，如圖2所示。

在圖1中，對同類興趣的學(xué)習(xí)，隨著用戶興趣模型不斷地累加學(xué)習(xí)，推薦的準(zhǔn)確性和查全率不斷提高。由此看出，隨著學(xué)習(xí)的進行，本文的推薦算法能實時更新用戶興趣模型。在圖2中，對于不斷變化的同一用戶興趣，由于推薦算法是選擇用戶新近的興趣主題進行匹配的，因此被模型捕捉到的興趣主題呈現(xiàn)出分散的趨勢。

6 結(jié)語

隨著Deep Web的迅速發(fā)展，大量的Deep Web信息如浩瀚的海洋，往往導(dǎo)致“信息過載”和“信息迷向”，個性化服務(wù)能很好地解決這樣的問題。針對現(xiàn)有招聘信息服務(wù)在面向不同用戶的個性化推薦方面的不足，提出了將基于Deep Web個性化推薦應(yīng)用到招聘服務(wù)中的解決方案，使用戶在盡可能少的參與下，得到了較好的個性化的服務(wù)。但是，該工作還需要進一步的探討：第一，對于在Deep Web爬取中設(shè)置的上溢閾值還需要在理論上做進一步分析；第二，個性化推薦算法的用戶滿意度和質(zhì)量，還需要進一步給出更合理的評估方法。

參考文獻：

[1] Chang KCC， He B， Li CK， et al.Structured databases on the Web： Observations and implications，” SIGMOD Record， 2004（33）.

[2] BrightPlanet.com， The deep Web： Surfacing hidden value， 2000， http：//brightplanet.com.

[3] 王靜帆.基于文本相似度二階段招聘信息檢索[D].清華大學(xué)，2007.

[4] 馬軍，宋玲，韓曉暉，等.基于網(wǎng)頁上下文的數(shù)據(jù)庫分類[J].軟件學(xué)報，2008，19（2）.

[5] He B， Tao T， Chang K C C.Clustering structured Web sources： A schema-based， model-differentiation approach. Springer-Verlag. Heraklion， 2004 [the 9th Intl Conf. on Extending Database Technology].

[6] Peng Q， Meng WY， He H， et al.WISE-Cluster： Clustering e-commerce search engines automatically，ACM Press. Washington， 2004 [the 6th ACM Intl Workshop Conf. on Web Information and Data Management].

[7] Wu WS， Yu C， Doan AH， et al.An interactive clustering-based approach to integrating source query interfaces on the deep Web，ACM Press. Paris， 2004 [the 24th ACM SIGMOD Intl Conf. on Management of Data].

[8] He H， Meng WY， Yu C.WISE-Integrator： An automatic integrator of Web search interfaces for e-commerce，”Morgan Kaufmann Publishers. San Fransisco， 2003 [the 29th Intl Conf. on Very Large Data Bases].

[9] Zhai YH， Liu B.Web data extraction based on partial tree alignment，” ACM Press. Chiba， 2005 [Proc. of the 14th Intl World Wide Web Conf.].

[10] Zhao H K， Meng W Y， Wu Z H， et al. Fully automatic wrapper generation for search engines，ACM Press. Chiba， 2005 [the 14th Intl World Wide Web Conf.] .

[11] 李珊.個性化服務(wù)中用戶興趣建模與更新研究[J].情報學(xué)報，2010，29（1）.