一種基于圖模型的Web數(shù)據(jù)庫(kù)采樣方法研究

何康樂(lè)

摘要：在Web數(shù)據(jù)庫(kù)中，有著大量豐富的信息數(shù)據(jù)，這些信息并不能直接看到，只有進(jìn)行特定的查詢才能看到。由于這一特點(diǎn)，對(duì)Web數(shù)據(jù)庫(kù)的實(shí)時(shí)更新及其分布特征的了解成了一個(gè)問(wèn)題，進(jìn)而也會(huì)阻礙到Deep Web數(shù)據(jù)庫(kù)的進(jìn)一步集成。針對(duì)這一困難，本文提出了一種新型的采樣方法，在查詢時(shí)能夠從Web數(shù)據(jù)庫(kù)獲取近似隨機(jī)的增量樣本并記錄，并在此基礎(chǔ)上進(jìn)行下一次查詢，并不會(huì)受到查詢接口的屬性限制，能夠在獲取高質(zhì)量樣本的同時(shí)降低代價(jià)。

關(guān)鍵詞：Web數(shù)據(jù)庫(kù);采樣;圖模型

中圖分類號(hào)：G434 ? 文獻(xiàn)標(biāo)識(shí)碼：A ? 論文編號(hào)：1674-2117（2015）09-0076-02

伴隨著Web的飛速發(fā)展，其作為一個(gè)信息源覆蓋了越來(lái)越多的信息，根據(jù)其所蘊(yùn)含的具體信息深度，我們可以將整個(gè)Web分為兩大部分，包括Deep Web以及Surface Web。[1]所謂的Surface Web指的是能夠采用傳統(tǒng)的普通搜索引擎就能直接索引出的信息內(nèi)容。相對(duì)地，不能直接采用搜索引擎搜索到的信息數(shù)據(jù)內(nèi)容就被放在Deep Web中，其具體內(nèi)容被存儲(chǔ)在能夠進(jìn)行在線訪問(wèn)的Web數(shù)據(jù)庫(kù)之中。由于Deep Web數(shù)據(jù)庫(kù)中存在著海量的信息，可以達(dá)到Surface Web的550倍[2]，想要從中快速獲取想要的信息也成了一個(gè)問(wèn)題。

● Deep Web概述

網(wǎng)絡(luò)中諸多能夠進(jìn)行在線訪問(wèn)的數(shù)據(jù)庫(kù)，統(tǒng)稱為Web數(shù)據(jù)庫(kù)，將全部Web數(shù)據(jù)庫(kù)整合到一起，就統(tǒng)一成了Deep Web，也被稱作是Hidden Web。[3]想要訪問(wèn)Deep Web，就必須從查詢接口進(jìn)行訪問(wèn)，在網(wǎng)頁(yè)上查詢接口是通過(guò)表單表現(xiàn)出來(lái)的，用戶具體需要做的就是輸入一定的條件在表單中，進(jìn)而便可以查詢相關(guān)信息。[4]

● Web數(shù)據(jù)庫(kù)采樣

Web數(shù)據(jù)庫(kù)中信息的質(zhì)量參差不齊，想要對(duì)其進(jìn)行有效研究，傳統(tǒng)做法通常是將全部數(shù)據(jù)庫(kù)進(jìn)行完全的統(tǒng)計(jì)分析。但，由于Web數(shù)據(jù)庫(kù)中的數(shù)據(jù)類型頗為廣泛，本地研究并不需要完整的數(shù)據(jù)庫(kù)，只需要構(gòu)建出一個(gè)具有針對(duì)性的本地?cái)?shù)據(jù)庫(kù)即可。然而，本地?cái)?shù)據(jù)庫(kù)構(gòu)建出來(lái)以后，由于網(wǎng)絡(luò)信息一直在實(shí)時(shí)更新，相應(yīng)地，本地?cái)?shù)據(jù)庫(kù)中的信息也需要實(shí)時(shí)更新，同時(shí)，這會(huì)為本地儲(chǔ)存增加相當(dāng)大的負(fù)擔(dān)，進(jìn)而付出更多的代價(jià)。[5]針對(duì)這一問(wèn)題，我們可以不將所有的信息都從Web數(shù)據(jù)庫(kù)中提取出來(lái)，僅從中抽取想要的數(shù)據(jù)樣本，通過(guò)具有代表性的樣本進(jìn)行數(shù)據(jù)庫(kù)研究。

傳統(tǒng)的采樣方法采集數(shù)據(jù)是通過(guò)數(shù)據(jù)庫(kù)直接獲取信息，進(jìn)行隨機(jī)采樣。隨機(jī)采樣技術(shù)有直方圖法和近似查詢法，但是這類方法都要求數(shù)據(jù)庫(kù)具備無(wú)限制訪問(wèn)接口。所以，在Web數(shù)據(jù)庫(kù)采樣中，這種方法并不適用。參考搜索引擎，也有專家學(xué)者提出可以通過(guò)文檔進(jìn)行隨機(jī)采樣，可以從搜索引擎中隨機(jī)抽取樣本。但是，由于文檔并不能代替查詢表單，所以該方法也不適用于Web數(shù)據(jù)庫(kù)。綜合考慮Deep Web的特點(diǎn)，筆者提出了一種基于圖模型的數(shù)據(jù)采樣方法，該方法摒棄了查詢接口屬性的限制，能夠通過(guò)關(guān)鍵詞進(jìn)行快速查詢。

● 基于圖模型的Web數(shù)據(jù)庫(kù)采樣

1.基本思想

基于圖模型的Web數(shù)據(jù)庫(kù)采樣的基本思想主要可以分成四個(gè)環(huán)節(jié)，首先，從任意的有效查詢中查詢;其次，根據(jù)查詢到的結(jié)果抽取一些進(jìn)行記錄;再次，將記錄好的內(nèi)容放置到本地的樣本數(shù)據(jù)庫(kù)中;最后，根據(jù)樣本庫(kù)的信息，抽取一個(gè)記錄進(jìn)行下一次查詢，達(dá)成循環(huán)（如下頁(yè)圖）。

想要完成Web數(shù)據(jù)庫(kù)采樣，需要解決兩個(gè)問(wèn)題。第一，采集到的樣本存在一定的偏差，必須進(jìn)行修正，保證數(shù)據(jù)分布能夠和Web數(shù)據(jù)庫(kù)相同;第二，獲取樣本相應(yīng)地需要付出一定的代價(jià)，要降低代價(jià)，可以通過(guò)減少查詢次數(shù)來(lái)達(dá)成這一目的。

2.圖模型WG概述

根據(jù)Web數(shù)據(jù)庫(kù)特征建立的一種全新模型，圖模型可以借由圖游歷的形式進(jìn)行采樣。在改樣過(guò)程中，模型中的各個(gè)頂點(diǎn)和邊都被定義了唯一的特征查詢，同時(shí)，查詢后的記錄集合中每個(gè)頂點(diǎn)都有其專門的對(duì)應(yīng)記錄，對(duì)于各個(gè)邊來(lái)說(shuō)，也有著邊上自帶兩點(diǎn)的對(duì)應(yīng)集合記錄。WG能夠提供的具體能力與WDB中的具體查詢接口有關(guān)，因?yàn)橹灰遣樵儯捅仨氂胁樵兘涌?。所以，要想判斷WG中的邊上兩個(gè)頂點(diǎn)是否存在兩個(gè)記錄，就要確定是否存在某個(gè)查詢接口能夠滿足邊上兩點(diǎn)的查詢記錄要求。

3.WG采樣方法

由圖可知，Web數(shù)據(jù)庫(kù)采樣需要解決的主要問(wèn)題是：獲取樣本、選擇查詢以及終止條件。由于我們并不能調(diào)出所有的WDB記錄，那么也很難構(gòu)建出一個(gè)真正意義上的WG，所以，可以根據(jù)當(dāng)前的WG，隨機(jī)抽取一個(gè)點(diǎn)開始游歷，進(jìn)行采樣，基本過(guò)程為：①隨機(jī)抽取一個(gè)Q0，將其遞交給WDB;②將查詢后所得的具體結(jié)果記錄到RL中，并根據(jù)已有的RL建立起對(duì)應(yīng)的WGL;③判斷是否終止，若滿足終止條件，則終止，若不滿足，則繼續(xù)進(jìn)行下一步驟;④對(duì)構(gòu)建出WGL的進(jìn)行分析，然后在RL中找出合適的記錄繼續(xù)進(jìn)行查詢，回到第①步驟進(jìn)行。

（1）WDB-Sampler算法

WDB-Sampler算法主要對(duì)采樣的整體過(guò)程進(jìn)行具體的形式化描述。

（2）記錄選擇

想要進(jìn)行持續(xù)查詢，完成實(shí)時(shí)更新，必須在已經(jīng)基本形成的本地記錄合集中選出合適的某個(gè)記錄進(jìn)行下一步查詢，這就是記錄選擇這一環(huán)節(jié)需要完成的內(nèi)容。采樣WG進(jìn)行具體解釋，就是根據(jù)目前的WGL選出一個(gè)頂點(diǎn)v，根據(jù)v查詢之前沒有查詢到的其他頂點(diǎn)，豐富WGL。

（3）查詢生成

選擇好頂點(diǎn)以后，可以選出具體的某個(gè)記錄，然后完成下一環(huán)節(jié)的查詢。一個(gè)記錄可以獲得多個(gè)查詢，所以，針對(duì)每個(gè)RL中的記錄都要構(gòu)建出對(duì)應(yīng)的統(tǒng)計(jì)信息。

（4）采樣終止

圖模型若是沒有設(shè)計(jì)終止程序，可想而知，數(shù)據(jù)采樣將會(huì)持續(xù)進(jìn)行下去，雖然在理論上這樣做可以得到所有想要的記錄，但是我們事實(shí)上并不需要所有的信息，只是需要其中某些樣本。所以，應(yīng)該設(shè)計(jì)出常量nq>1、0<<1表示若是查詢中連續(xù)nq次的結(jié)果都超出了的重復(fù)記錄，就代表采樣結(jié)束。通常我們將nq值設(shè)計(jì)在5～10之間，設(shè)在5%～15%之間。

（5）偏差修正

因?yàn)椴樵冎形覀兪菍L當(dāng)做樣本進(jìn)行采樣的，那么采樣結(jié)束后往往會(huì)造成較大的偏差。針對(duì)這一問(wèn)題，可以通過(guò)采樣中的查詢記錄數(shù)量和過(guò)程中的Q{}進(jìn)行樣本偏差修正。

● 結(jié)語(yǔ)

筆者提出的基于圖模型的WDB-Sample采樣方法，能夠?qū)eb數(shù)據(jù)庫(kù)轉(zhuǎn)變?yōu)閳D形進(jìn)行增量采樣，該方法能夠脫離屬性限制，保證高質(zhì)量采集樣本的同時(shí)降低代價(jià)，在教育領(lǐng)域中的應(yīng)用應(yīng)該有無(wú)限廣闊的前景。

參考文獻(xiàn)：

[1]劉偉，孟小峰，凌妍妍.一種基于圖模型的Web數(shù)據(jù)庫(kù)采樣方法[J].軟件學(xué)報(bào)，2008（02）.

[2]吳雨.基于圖模型的Web數(shù)據(jù)庫(kù)取樣方法的解析[J].科技創(chuàng)新與應(yīng)用，2013（20）.

[3]王曉玲.一種基于圖模型的Web數(shù)據(jù)庫(kù)采樣方法分析[J].計(jì)算機(jī)光盤軟件與應(yīng)用，2013（13）.

[4]趙琳.Web數(shù)據(jù)庫(kù)特征表示和抽取方法的研究[D].濟(jì)南：山東財(cái)經(jīng)大學(xué)，2012.

[5]董永權(quán).Deep Web數(shù)據(jù)集成關(guān)鍵問(wèn)題研究[D].濟(jì)南：山東大學(xué)，2010.