一種基于深網(wǎng)的個性化信息爬取方法

譚濤　譚樂婷　張剛園

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

關鍵詞：Deep Web；個性化爬取；相似度；用戶興趣模型

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

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

2 相關原理

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

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

3 用戶興趣模型的構建

3.1用戶興趣模型的表示

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

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

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

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

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

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

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

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

4 Deep Web的爬取

Web數(shù)據(jù)庫的爬取實質是在找到一個查詢詞集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的結果記錄數(shù)，k表示目標Web站點每個查詢結果列表頁面展示的最大記錄數(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的結果記錄數(shù)， NWDB表示W(wǎng)eb數(shù)據(jù)庫中總的記錄數(shù)。

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

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

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

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

定義4.多叉樹。數(shù)據(jù)庫表T的層次樹DT（T）是關于查詢詞的多叉樹。構造如下：對一組查詢詞集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é)點的邊構成了抽取該記錄的結構化查詢，在此基礎之上，Deep Web數(shù)據(jù)庫的爬取問題就轉化為樹的遍歷問題，即通過遍歷樹抽取有效葉子節(jié)點中的記錄。由于考慮從根節(jié)點到葉子節(jié)點的邊，采用深度優(yōu)先的遍歷原則。具體的遍歷過程如下：

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

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

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

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

5 個性化信息爬取實驗

為了客觀評估基于Deep Web的用戶個性化爬取方法，我們實現(xiàn)了一個招聘系統(tǒng)的原型，并在真實的Web數(shù)據(jù)庫上進行了驗證。針對15個注冊用戶，每個用戶5個初始選擇興趣，從用戶的首次查詢開始記錄并返回數(shù)據(jù)，對每個興趣，系統(tǒng)設置從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提交時，在返回結果記錄時根據(jù)相似度匹配進行了高相似度的信息推薦；（2）定時推薦：在用戶預約的固定時間段，當服務器處于閑置狀態(tài)時，集中進行計算，將爬取到的新的信息反饋給用戶。采用信息檢索領域的查準率P和查全率R進行衡量。針對15個注冊用戶，每個用戶5個初始選擇興趣，構建了同類興趣和不同類興趣的學習，假定15個用戶的初始興趣都有“計算機”，記錄了此時15個用戶的學習模型，如圖1所示；另一方面，每個的用戶的興趣都會發(fā)生改變，記錄了某個用戶UserI的學習模型的改變，如圖2所示。

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

6 結語

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

參考文獻：

[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].清華大學，2007.

[4] 馬軍，宋玲，韓曉暉，等.基于網(wǎng)頁上下文的數(shù)據(jù)庫分類[J].軟件學報，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] 李珊.個性化服務中用戶興趣建模與更新研究[J].情報學報，2010，29（1）.