譚濤　譚樂婷　張剛園

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

關(guān)鍵詞：Deep Web；個(gè)性化爬?。幌嗨贫?；用戶興趣模型

中圖分類號：TP393 文獻(xiàn)標(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ù)攜帶著重要的價(jià)值，能應(yīng)用于許多業(yè)務(wù)領(lǐng)域。這些信息按照蘊(yùn)含的深度可以將整個(gè)網(wǎng)絡(luò)分為兩大部分：Surface Web和Deep Web。那些直接通過超級鏈接由傳統(tǒng)搜索引擎爬取到的頁面集合屬于Surface Web；而廣泛存在于可在線訪問的Web數(shù)據(jù)庫中的大量信息，通常傳統(tǒng)的搜索引擎是索引不到的，這些內(nèi)容則屬于Deep Web的范疇。隨著Web 2.0時(shí)代的到來，目前的整個(gè)網(wǎng)絡(luò)至少有65萬個(gè)數(shù)量級的可訪問Web數(shù)據(jù)庫，其信息容量覆蓋了商業(yè)，教育，醫(yī)學(xué)等眾多領(lǐng)域，遠(yuǎn)遠(yuǎn)超過了Surface Web的信息含量。越來越多的國內(nèi)外學(xué)者投入到對Deep Web的應(yīng)用研究中。

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

2 相關(guān)原理

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

由于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]等。而個(gè)性化推薦應(yīng)用上發(fā)展也日趨成熟，比如擴(kuò)展語義的用戶興趣建模及更新策略[11]，在基于Deep Web數(shù)據(jù)的個(gè)性化推薦應(yīng)用上，也取得了一定的成果。

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

3.1用戶興趣模型的表示

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

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

3.2用戶興趣模式的相似度計(jì)算

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

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

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

4 Deep Web的爬取

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

定義1.給定查詢屬性qi和Web數(shù)據(jù)庫WDB，查詢屬性qi的爬取代價(jià)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站點(diǎn)每個(gè)查詢結(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ù)庫被看做一個(gè)關(guān)系模式的數(shù)據(jù)表。考慮如下：一個(gè)Web數(shù)據(jù)庫表T：該表由定義在結(jié)果屬性集AL={al1，al2，…，alm}上的記錄集D={d1，d2，…，dn}組成；同時(shí)，查詢表單接口中存在一組查詢屬性集Q={q1，q2，…，qm}。用戶通過填寫表單項(xiàng)指定查詢屬性的值，這些查詢在底層數(shù)據(jù)庫中轉(zhuǎn)化為SQL查詢語句。

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

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

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

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

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

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

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

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

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

5 個(gè)性化信息爬取實(shí)驗(yàn)

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

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

6 結(jié)語

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

參考文獻(xiàn)：

[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é)報(bào)，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] 李珊.個(gè)性化服務(wù)中用戶興趣建模與更新研究[J].情報(bào)學(xué)報(bào)，2010，29（1）.