基于啟發(fā)式搜索代價(jià)的多查詢結(jié)果分類方法

高 建

?

基于啟發(fā)式搜索代價(jià)的多查詢結(jié)果分類方法

高 建

（盤錦職業(yè)技術(shù)學(xué)院 機(jī)電工程系，遼寧盤錦124010）

提出了一種基于搜索代價(jià)的對(duì)Web數(shù)據(jù)庫多查詢結(jié)果進(jìn)行分類的方法，該方法首先通過分析用戶的查詢習(xí)慣，構(gòu)建一個(gè)通用的查詢結(jié)果分類樹探測(cè)模型，然后根據(jù)探測(cè)模型建立分類樹的搜索代價(jià)模型。對(duì)于搜索代價(jià)，提出了基于查詢歷史的搜索代價(jià)估計(jì)方法。最后，以降低搜索代價(jià)為目標(biāo)在查詢結(jié)果集上生成一個(gè)分類樹，用戶通過檢查該分類樹上各分支節(jié)點(diǎn)的標(biāo)簽來逐步定位到其感興趣的信息。實(shí)驗(yàn)及分析表明，本文所提方法能夠有效避免信息過載，并且具有較好分類效果和較低搜索代價(jià)。

搜索代價(jià)；信息過載；查詢結(jié)果分類

隨著WWW的發(fā)展，以數(shù)據(jù)庫為中心的Web應(yīng)用越來越廣泛。對(duì)于用戶提交的查詢，傳統(tǒng)的查詢處理技術(shù)只是簡單地返回滿足查詢要求的查詢結(jié)果。然而，對(duì)于蘊(yùn)含海量數(shù)據(jù)的Web數(shù)據(jù)庫來說，一個(gè)查詢往往會(huì)產(chǎn)生大量的查詢結(jié)果，也就是“信息過載”現(xiàn)象，信息過載發(fā)生在用戶不確定他搜尋什么[1]。這種情況下，用戶開始通常會(huì)提出一個(gè)普通的、選擇性較弱的查詢，以便將所有可能需求的結(jié)果包含進(jìn)來。對(duì)查詢結(jié)果進(jìn)行分類和排序是處理信息過載的2種互補(bǔ)的技術(shù)。通過分類或排序，用戶通常會(huì)重新形成一個(gè)更具選擇性的查詢。所以，分類和排序并非直接有用，其作用在于協(xié)助用戶形成更為明確的查詢條件?，F(xiàn)有研究工作提出的查詢分類是預(yù)先生成一個(gè)目錄結(jié)構(gòu)，目錄中的分支標(biāo)簽也是預(yù)先指定好的，在查詢的時(shí)候，查詢結(jié)果被集成到預(yù)定義的目錄結(jié)構(gòu)中。由于這樣的分類是獨(dú)立于查詢的，因此查詢結(jié)果在目錄中的分布會(huì)不均勻，一些目錄下可能具有大量的結(jié)果元組，而另外一些目錄下可能就具有少量的結(jié)果元組。

為了解決信息過載問題，本文提出一種對(duì)查詢結(jié)果進(jìn)行分類的方法。該方法根據(jù)元組內(nèi)容對(duì)元組聚類，然后在查詢結(jié)果集上生成一個(gè)帶標(biāo)簽的分類樹。該分類樹是在查詢進(jìn)行過程中生成的，所以不會(huì)出現(xiàn)預(yù)分類問題。該方法通過鑒定分類空間開始，然后開發(fā)一個(gè)探測(cè)模型，這樣用戶可以跟著導(dǎo)航層次結(jié)構(gòu)進(jìn)行逐步細(xì)化查詢。

1 相關(guān)工作

解決Web數(shù)據(jù)庫信息過載的2種方法是對(duì)查詢結(jié)果進(jìn)行排序和分類。目前已經(jīng)有大量工作對(duì)查詢結(jié)果排序方法進(jìn)行了研究，大致分成3類：第一類是利用用戶相關(guān)反饋，用戶通過在屬性或元組上明確指定其偏好，然后系統(tǒng)根據(jù)用戶反饋對(duì)查詢結(jié)果排序[2-3]；第二類是利用用戶偏好描述文件對(duì)查詢結(jié)果進(jìn)行個(gè)性化排序，用戶偏好文件由用戶根據(jù)其偏好創(chuàng)建和更新[4-5]；第三類是通過分析查詢歷史，推測(cè)隱式用戶偏好，據(jù)此對(duì)查詢結(jié)果進(jìn)行排序[6-7]。查詢歷史記錄了使用系統(tǒng)的所有用戶提交的查詢條件集合，在很大程度上能反映出用戶的查詢習(xí)慣和大多數(shù)用戶的興趣偏好，因此本文也利用查詢歷史來估計(jì)用戶使用查詢結(jié)果分類樹進(jìn)行搜索的代價(jià)。

近年來，已有一些工作研究信息檢索結(jié)果[8]和文本文檔[9-10]分類方法。但是，Web數(shù)據(jù)庫查詢的分類與信息檢索和文本文檔的分類不同，主要差別是數(shù)據(jù)庫同時(shí)包含文本和數(shù)值，而信息檢索的對(duì)象就是文本文檔；另一方面，對(duì)查詢結(jié)果分類既要考慮分類準(zhǔn)確性還要考慮用戶使用分類樹的搜索代價(jià)，而文本分類只需考慮分類的準(zhǔn)確性。

對(duì)于數(shù)據(jù)庫查詢結(jié)果的分類，只有文獻(xiàn)[11]研究了關(guān)系數(shù)據(jù)庫SQL查詢結(jié)果的分類方法，該方法基于C4.5決策樹算法，根據(jù)屬性的信息增益確定分類樹的分類屬性，對(duì)數(shù)值型屬性的區(qū)間劃分采用二元?jiǎng)澐址椒?。該方法雖然具有較低的搜索代價(jià)，但是存在以下不足：(1)查詢結(jié)果元組只能在葉節(jié)點(diǎn)下查看，非葉子節(jié)點(diǎn)不能展開顯示所包含的元組；(2)分類屬性確定的依據(jù)是屬性的信息增益，而信息增益反映的是屬性劃分?jǐn)?shù)據(jù)的能力而并非降低搜索代價(jià)的能力；(3)數(shù)值區(qū)間劃分的范圍過大或過小，不能滿足用戶的現(xiàn)實(shí)需求。本文所提方法能夠有效克服上述問題，因此具有較為重要的理論意義和應(yīng)用價(jià)值。

2 分類基本概念

2.1 分類空間

令是一個(gè)元組集合(是一個(gè)基本表、一個(gè)視圖、或者一個(gè)查詢的結(jié)果集)。假設(shè)不包含任何聚合或派生的屬性。的一個(gè)層次分類是一個(gè)基于屬性和值對(duì)于在中元組的遞歸劃分。圖1給出了在yahoo房地產(chǎn)網(wǎng)站上搜索位置在西雅圖市的房產(chǎn)查詢結(jié)果分類樹例子。

結(jié)合上例，描述查詢結(jié)果分類的基本思想和相關(guān)概念。

分類樹：給定分類結(jié)構(gòu)的根(第0層)，它包含所有在中的元組，使用一個(gè)屬性將中的元組劃分成為一個(gè)相互非重合的目錄(第1層節(jié)點(diǎn))。例如，圖1中的根節(jié)點(diǎn)，根據(jù)屬性“Neighborhood”將元組劃分成3個(gè)分支，即, 和，被劃分成3個(gè)不連接的目錄分支。

歸納步驟：給定一個(gè)在第-1層的節(jié)點(diǎn)，根據(jù)一個(gè)給定的屬性遞歸劃分包含在中的元組集合()，使其成為一個(gè)互不重疊的目錄有序列表。使用的屬性被稱為第層節(jié)點(diǎn)的分類屬性，也是第1層節(jié)點(diǎn)的子分類屬性。例如，“Price”是在第2層中所有節(jié)點(diǎn)的分類屬性，同時(shí)也是第1層所有節(jié)點(diǎn)的子分類屬性。需要指出的是，一個(gè)屬性只能有一次機(jī)會(huì)作為分類屬性。

與每一個(gè)節(jié)點(diǎn)關(guān)聯(lián)的是一個(gè)分類標(biāo)簽以及一個(gè)元組集，定義如下。

分類標(biāo)簽：標(biāo)簽()是對(duì)一個(gè)節(jié)點(diǎn)的描述。例如，圖1中根的第一個(gè)孩子有標(biāo)簽“Neighborhood?{Redmond,Bellevue}”，同時(shí)上述目錄分支的第一個(gè)孩子有標(biāo)簽“Price: 200k-225k”。

元組集：包含在中的元組集()，稱為的元組集合，該集合滿足上的標(biāo)簽。換句話說，()是在中滿足從根到路徑上所有節(jié)點(diǎn)標(biāo)簽的元組子集。例如，在圖1中對(duì)于帶有標(biāo)簽“Neighborhood: Redmond, Bellevue”的目錄，()是一個(gè)在中位于Redmond或Bellevue的房產(chǎn)集合。

由此可見，一個(gè)目錄的標(biāo)簽，向用戶明確描述了哪個(gè)元組在父節(jié)點(diǎn)的集合中。用戶通過觀察標(biāo)簽就能夠決定是否去選擇進(jìn)一步展開的子目錄。()有如下結(jié)構(gòu)。

如果分類屬性是一個(gè)文本型屬性：()的形式為“?”，其中ì()，()表示屬性在的值域。如果.?，則元組滿足標(biāo)簽()。

如果分類屬性是一個(gè)數(shù)值型屬性：()的形式為“1￡<2”，其中1,2?()。如果1￡<2，則元組滿足標(biāo)簽()。

根據(jù)上述層次分類結(jié)構(gòu)，對(duì)于分類結(jié)構(gòu)的每一個(gè)層次，需要進(jìn)行如下操作。

(1)對(duì)于層次，確定其分類屬性。

(2)對(duì)于第-1層的每一個(gè)分類，決定如何去劃分()中的元組，使其在屬性的值域上成為互不重疊的子集。

目標(biāo)是選取在每一個(gè)層次上的屬性-劃分結(jié)合，使得查詢結(jié)果分類樹有最小的信息過載。

2.2 搜索模型

給定一個(gè)查詢結(jié)果分類樹，用戶通常會(huì)以自頂向下或自左向右的方式檢查該樹的非葉子節(jié)點(diǎn)(或稱中間節(jié)點(diǎn))上的標(biāo)簽，然后逐步定位到其所需信息。假設(shè)用戶現(xiàn)在位于節(jié)點(diǎn)(可以是根節(jié)點(diǎn)、中間節(jié)點(diǎn)或葉子節(jié)點(diǎn))，在該節(jié)點(diǎn)上操作如下。

(1)如果是一個(gè)非葉子節(jié)點(diǎn)，用戶可以有2種方式探測(cè)目錄：一是“顯示元組”方式，即顯示()中的所有元組；二是“顯示子目錄”方式，即顯示下的所有子目錄，如果下有個(gè)子目錄，用戶將檢查這個(gè)子目錄標(biāo)簽，然后選定其中某個(gè)子目錄C進(jìn)行探測(cè)，遞歸執(zhí)行上述過程。

(2)如果是一個(gè)葉子節(jié)點(diǎn)，則只能進(jìn)行“顯示元組”操作，即顯示()中的所有元組。

3 代價(jià)評(píng)估

3.1 代價(jià)模型

給定一個(gè)查詢結(jié)果分類樹，用戶使用樹以某種路徑進(jìn)行探測(cè)進(jìn)而找到相關(guān)元組的代價(jià)用Cost(,)表示，該代價(jià)包含2個(gè)部分：一部分是用戶檢查中間節(jié)點(diǎn)標(biāo)簽的代價(jià)，另一部分是用戶檢查節(jié)點(diǎn)下元組的代價(jià)。一般情況下，用戶查找相關(guān)元組的時(shí)間與用戶需要檢查的條目(包括中間節(jié)點(diǎn)的標(biāo)簽和節(jié)點(diǎn)下的元組)的總數(shù)呈正比，即用戶需要檢查的標(biāo)簽或元組數(shù)越多，在查找相關(guān)元組上花費(fèi)的時(shí)間就越多，搜索代價(jià)就越高。

例如，計(jì)算在圖1中分類樹上的搜索代價(jià)Cost(,)。假設(shè)對(duì)于檢查根節(jié)點(diǎn)的代價(jià)是0，分支“Price: 225k-250k”下包含20條元組，則搜索代價(jià)就是3（用于檢查3個(gè)第一層目錄的標(biāo)簽）+3（用于檢查“Neighborhood: Redmond, Bellevue”子目錄的3個(gè)標(biāo)簽）+20（用于檢查在分支“Price:225k-250k”下的20條元組）=26。

在實(shí)際應(yīng)用中，由于不能明確知道用戶的查詢意圖，因而無法確定用戶會(huì)選擇哪個(gè)分支和哪些元組。為了對(duì)搜索代價(jià)進(jìn)行估計(jì)，需要知道下列2個(gè)與中每個(gè)目錄相關(guān)聯(lián)的概率，從而估計(jì)Cost(,)：

探測(cè)的概率：假設(shè)用戶探測(cè)目錄的概率為()。用戶探測(cè)目錄，是指用戶在目錄上進(jìn)行了“顯示元組”或“顯示子目錄”操作；相應(yīng)地，用戶忽略的概率是1-()。

“顯示元組”的概率：假設(shè)用戶探測(cè)目錄，令用戶使用“顯示元組”方式探測(cè)目錄的概率為P()，那么用戶使用“顯示子目錄”方式探測(cè)的概率就是1-P()。如果是一個(gè)葉節(jié)點(diǎn)，則P()=1，因?yàn)樵撉闆r下“顯示元組”是唯一的選項(xiàng)。

假設(shè)在上述概率已知的情況下，下面介紹如何計(jì)算Cost(,)?？紤]分類樹中的一個(gè)非葉子節(jié)點(diǎn)，令1,2, …,C是中的個(gè)子目錄。如果用戶對(duì)于節(jié)點(diǎn)選擇了“顯示元組”，則表明他檢查在中的所有元組，因此代價(jià)就是|()|；如果用戶對(duì)于節(jié)點(diǎn)選擇了“顯示子目錄”操作，則總體代價(jià)就是檢查下所有子目錄標(biāo)簽的代價(jià)加上可能選擇去探測(cè)下若干子目錄的代價(jià)。對(duì)于第二種情況，代價(jià)模型中的第一個(gè)因數(shù)是*，其中是檢查一個(gè)目錄標(biāo)簽的代價(jià)，代表下的子目錄總數(shù)；第二個(gè)因數(shù)是探測(cè)目錄C的代價(jià)。因此，用戶探測(cè)節(jié)點(diǎn)的搜索代價(jià)公式為：

Cost()=P()*|()|+

(1-P())**+(C)*(C)) (1)

如果是一個(gè)葉節(jié)點(diǎn)，()=|()|。注意，上述定義對(duì)于葉子節(jié)點(diǎn)，P()=1也成立。并且，當(dāng)是根節(jié)點(diǎn)時(shí)，該代價(jià)就是分類樹的搜索代價(jià)。

3.2 概率估計(jì)

本節(jié)討論如何利用查詢歷史估計(jì)概率P()和()，從而估計(jì)分類樹的搜索代價(jià)Cost()。

選擇“顯示元組”操作的概率：假設(shè)用戶探測(cè)非葉子節(jié)點(diǎn)，有2個(gè)互斥的選擇：“顯示元組”和“顯示子目錄”。首先考慮用戶探測(cè)選擇“顯示子目錄”的概率，如果的子分類屬性A能夠使得用戶僅僅對(duì)下少數(shù)子目錄感興趣，該情況下使用“顯示子目錄”可以使用戶忽略大部分其他子目錄，所以在很大程度上減少了用戶需要檢查的元組數(shù)量。另一方面，如果用戶對(duì)下大部分或所有子目錄感興趣，即用戶對(duì)A()中的大部分或所有的值感興趣，則將選擇“顯示元組”操作。

本文采用查詢歷史作為評(píng)估P()和()值的依據(jù)，具體方法如下：在查詢歷史中，如果用戶已在屬性上指定了查詢條件，表明用戶對(duì)A中的一些值感興趣；如果用戶在A上沒有指定查詢條件，表明他對(duì)上的所有值都感興趣。如果(A)表示查詢歷史中在屬性A上包含查詢條件的查詢個(gè)數(shù)，表示查詢歷史中查詢記錄的總數(shù)；(A)/表示用戶對(duì)屬性A中的一些值感興趣的比例。因此，一個(gè)用戶對(duì)于A中的一些值感興趣，即選擇“顯示子目錄”操作的概率是(A)/，相應(yīng)地對(duì)執(zhí)行“顯示元組”的概率P()就是1-(A)/。

探測(cè)目錄的概率：探測(cè)目錄的概率用()表示。探測(cè)目錄是指用戶根據(jù)上的標(biāo)簽來決定使用“顯示元組”或“顯示子目錄”來探測(cè)目錄的概率，或者說，()是在用戶檢查的標(biāo)簽條件下進(jìn)一步選擇探測(cè)的概率。

由于用戶探測(cè)意味著用戶已經(jīng)檢查了的標(biāo)簽，因此，()=(用戶探測(cè))/(用戶檢查的標(biāo)簽)。當(dāng)且僅當(dāng)用戶探測(cè)的上級(jí)目錄并且對(duì)執(zhí)行showcat操作時(shí)，用戶才可能去檢查的標(biāo)簽，因此，

注意，上式中分母，即條件概率：

(對(duì)執(zhí)行‘顯示子目錄’操作|用戶探測(cè))

實(shí)際上就是對(duì)執(zhí)行‘顯示子目錄’操作的概率，即(A())/。

再考慮式(2)中的分子，概率：(用戶探測(cè))，是用戶對(duì)上標(biāo)簽感興趣的概率，這個(gè)概率值可用查詢歷史中在的分類屬性A上與()相重疊的查詢條件個(gè)數(shù)來估計(jì)，即用N()/來計(jì)算，其中表示查詢歷史中查詢的總數(shù)。

最后，()可以用下式來衡量：

()=N()/(A) (3)

其中，N()代表查詢歷史中在的分類屬性A上與標(biāo)簽()相重疊的查詢條件個(gè)數(shù)，(A)表示查詢歷史中在屬性A上包含查詢條件的查詢個(gè)數(shù)。

4 分類算法

4.1 分類屬性約簡和屬性劃分

4.1.1 分類屬性約簡

在查詢歷史中，屬性的出現(xiàn)次數(shù)()越低，用戶對(duì)根節(jié)點(diǎn)執(zhí)行“顯示元組”操作的概率P()就越高。因?yàn)橐粋€(gè)樹的“顯示元組”的代價(jià)通常要比“顯示子目錄”的代價(jià)高，一個(gè)高的“顯示元組”概率意味著樹的搜索代價(jià)將有一個(gè)較大的(P()*|()|)值。所以，在預(yù)處理階段需要消除低出現(xiàn)頻率的屬性。在本文中，如果一個(gè)屬性以小于的比例出現(xiàn)在查詢歷史中，即，()/<，消除。閾值由系統(tǒng)或?qū)＜抑付ā?/p>

4.1.2 文本型屬性劃分

分類樹的構(gòu)建需要對(duì)分類屬性進(jìn)行劃分，即對(duì)分類屬性下的值進(jìn)行劃分。

對(duì)于一個(gè)文本型分類屬性，本文采用單值劃分方法。例如，對(duì)于目錄，如果它的子分類屬性在()上包含個(gè)不同值{1,…,v}，則將目錄劃分成個(gè)子分支目錄，每個(gè)目錄的標(biāo)簽對(duì)應(yīng)這個(gè)不同的文本值。

為了降低搜索代價(jià)，首先統(tǒng)計(jì)每個(gè)文本值v在查詢歷史中出現(xiàn)的次數(shù)，記為(v)，該值存放在知識(shí)庫表中，其結(jié)構(gòu)為{ID，文本值，出現(xiàn)次數(shù)}。

4.1.3 數(shù)值型屬性劃分

劃分?jǐn)?shù)值屬性的基本思想是利用最佳分割點(diǎn)對(duì)數(shù)值屬性的值域進(jìn)行數(shù)值區(qū)間的劃分。最佳分割點(diǎn)是查詢歷史中用戶經(jīng)常以某個(gè)數(shù)值開始或結(jié)束的查詢數(shù)值點(diǎn)。假設(shè)要將屬性的值域劃分為個(gè)區(qū)間，則需要-1個(gè)分割點(diǎn)，這些分割點(diǎn)是查詢歷史中指定在屬性上的大多數(shù)范圍查詢的起始點(diǎn)或結(jié)束點(diǎn)。

給定一個(gè)分割點(diǎn)，令b和e分別代表查詢歷史中以點(diǎn)開始或結(jié)束的查詢條件的個(gè)數(shù)，把b和e相加作為點(diǎn)作為分割點(diǎn)的最終成績，該成績?cè)酱螅瑒t點(diǎn)越適合作為分割點(diǎn)。

4.2 查詢結(jié)果分類樹構(gòu)建

本文以遞歸方式構(gòu)建查詢結(jié)果分類樹，對(duì)于分類樹的每一層，都需要處理以下兩個(gè)問題。

(1)決定分類屬性。

(2)對(duì)于在-1層的每一個(gè)目錄，劃分在()中屬性的值域，使得信息過載最小化。

在本文中，當(dāng)且僅當(dāng)節(jié)點(diǎn)包含超過個(gè)元組，將對(duì)進(jìn)一步劃分，其中是一個(gè)給定的參數(shù)。查詢結(jié)果分類樹構(gòu)建算法如下所示。

算法1. 查詢結(jié)果分類樹構(gòu)建算法 Categorize(R)輸入：查詢結(jié)果R，參數(shù)M，數(shù)值區(qū)間分割點(diǎn)成績輸出：基于R的分類樹T1. 創(chuàng)建一個(gè)根節(jié)點(diǎn) (層次=0) 并且添加到T2. l =1； //把當(dāng)前的層設(shè)置為13.while在第l-1 層存在至少一個(gè)目錄，它的|tset(C)|>M時(shí)4. S?{C | C是在l-1層的目錄且|tset(C)|>M}5. for每一個(gè)分類屬性A6. if A是一個(gè)文本屬性7. SCL?以occ(vi)的降序列出所有的單值目錄8. for S中的每一個(gè)目錄C9. 構(gòu)建Tree(C, A)，該樹以C為根，以A上的每個(gè)文本值作為C的子目錄10. else //A是一個(gè)數(shù)值型屬性11. SPL?按分割點(diǎn)對(duì)數(shù)值區(qū)間進(jìn)行分割12. for S中的每一個(gè)目錄C13. 構(gòu)建Tree(C, A)，該樹以C為根，以A上劃分的區(qū)間作為C的子目錄14. 計(jì)算15. 選擇作為第l層的分類屬性16. for S中的每一個(gè)目錄C17. 把由使用屬性a得到的劃分Tree(C, a)添加到T中18. l = l+119. end

算法1從第0層開始創(chuàng)建分類樹，每層的分類屬性都是從剩余屬性中選取具有最小搜索代價(jià)的屬性作為分類屬性。算法遞歸執(zhí)行，直到每個(gè)目錄包含的元組個(gè)數(shù)不超過個(gè)為止。

5 實(shí)驗(yàn)及性能分析

5.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)使用的機(jī)器配置為64位3.30 G處理器，8 G內(nèi)存和500 G硬盤，操作系統(tǒng)為Windows 2007，算法采用Java語言實(shí)現(xiàn)。測(cè)試數(shù)據(jù)使用http://estate.yahoo.com的房地產(chǎn)銷售數(shù)據(jù)庫，選擇Washington州的Seattle城市，元組數(shù)約有20 000條，包含的屬性有Price、SqFt、Location、Bedrooms、Bathrooms、Buildyear、Garage、Livingarea、Neighborhood和Schooldistrict，其中Price、SqFt、Bedrooms、Bathrooms和Buildyear是數(shù)值型屬性，其余為文本型屬性。查詢歷史包含2 000條用戶查詢。

對(duì)比算法：將本文方法(簡稱Cost-based)與文獻(xiàn)[11]方法(簡稱C4.5-based)進(jìn)行對(duì)比，分別測(cè)試二者在實(shí)際搜索代價(jià)和平均搜索代價(jià)方面的效果。

5.2 分類效果測(cè)試

本文邀請(qǐng)10個(gè)用戶，每個(gè)用戶提出一個(gè)測(cè)試查詢，對(duì)于每個(gè)測(cè)試查詢，用戶從查詢結(jié)果中選出與其興趣和偏好最為相關(guān)的部分元組。在此基礎(chǔ)上測(cè)試分類樹的分類效果。

(1)實(shí)際搜索代價(jià)

實(shí)際搜索代價(jià)不同于預(yù)計(jì)搜索代價(jià)，它是用戶使用分類樹找到所有相關(guān)元組而實(shí)際訪問的條目(包括檢查節(jié)點(diǎn)標(biāo)簽和元組)的代價(jià)總和。很明顯用戶通過檢查越少的節(jié)點(diǎn)數(shù)和元組數(shù)就能找到所有相關(guān)元組，那么表明實(shí)際搜索代價(jià)越低，因此分類方法越好。表1給出了每個(gè)測(cè)試查詢?cè)?種分類方法下的實(shí)際搜索代價(jià)。

表1 不同分類方法的實(shí)際搜索代價(jià)對(duì)比

(2)平均搜索代價(jià)

僅對(duì)比實(shí)際搜索代價(jià)實(shí)際上并不公平，因?yàn)閷?duì)于相同的測(cè)試查詢使用不同的分類算法，用戶通常會(huì)找到不同個(gè)數(shù)的相關(guān)元組，因此需要用實(shí)際搜索代價(jià)除以找到的相關(guān)元組數(shù)，也就是平均搜索代價(jià)來反映用戶找到一個(gè)相關(guān)元組所需花費(fèi)的代價(jià)。表2給出了對(duì)于每個(gè)測(cè)試查詢利用上述2種分類方法的平均搜索代價(jià)對(duì)比。

表2 不同分類方法的平均搜索代價(jià)對(duì)比

通過上述比較可知，本文提出的分類效果優(yōu)于文獻(xiàn)[11]提出的方法，這是因?yàn)椋?1)對(duì)于劃分?jǐn)?shù)值屬性，本文采用了多元?jiǎng)澐?，即選取多個(gè)最佳分割點(diǎn)，使得分割后的每個(gè)區(qū)間都是用戶在以往查詢中經(jīng)常指定的，因此降低了搜索代價(jià)，而文獻(xiàn)[11]方法僅使用二元?jiǎng)澐?，不可避免地?dǎo)致劃分的區(qū)間過大或者過小，從而造成搜索代價(jià)的增加；(2)本文方法每層選取的分類屬性是用戶在查詢歷史中頻繁指定的屬性，因此會(huì)降低執(zhí)行“顯示元組”操作的概率，從而降低了搜索代價(jià)，而文獻(xiàn)[11]方法是通過考察屬性的信息增益來確定分類屬性，然而信息增益的目的是用來劃分?jǐn)?shù)據(jù)而并非降低搜索代價(jià)；(3)本文方法在非葉子節(jié)點(diǎn)上能夠進(jìn)行“顯示子目錄”和“顯示元組”操作，而文獻(xiàn)[11]的方法只能在葉節(jié)點(diǎn)上顯示元組。綜上，本文方法在分類效果和搜索代價(jià)方面都優(yōu)于現(xiàn)有方法。

6 結(jié)論與展望

提出了一種以降低搜索代價(jià)為目的的Web數(shù)據(jù)庫查詢結(jié)果分類方法，該方法在查詢處理階段根據(jù)查詢結(jié)果動(dòng)態(tài)生成一個(gè)分類樹，用戶通過檢查節(jié)點(diǎn)標(biāo)簽來決定探測(cè)哪個(gè)分支。本文方法分成2個(gè)階段，在離線階段，根據(jù)查詢歷史計(jì)算用戶探測(cè)某個(gè)分支的概率，包括“顯示子目錄”和“顯示元組”的概率；在線處理階段，在查詢結(jié)果集上根據(jù)搜索代價(jià)選取分類屬性，以遞歸方式生成查詢結(jié)果分類樹。實(shí)驗(yàn)結(jié)果表明，本文方法構(gòu)建的查詢結(jié)果分類樹具有較低的搜索代價(jià)和較好的分類效果。

如何對(duì)分類樹中的目錄進(jìn)行排序是需進(jìn)一步解決的問題。

[1] Meng X F, Ma Z M, Yan L. Answering approximate queries over autonomous web databases[C]. Proceedings of the 18th International World Wide Web Conference, 2009, 1021-1030.

[2] Agarwal G, Mallick N, Turuvekere S. Ranking database queries with user feedback: a neural network approach[C]. Proceedings of the International Conference on Database Systems for Advanced Applications, 2008, 424-431.

[3] Wichterich M, Beecks C, Seidl T. Ranking multimedia databases via relevance feedback with history and foresight support[C]. Proceedings of the IEEE 24th International Conference on Data Engineering Workshop, 2008, 16-25.

[4] Santhanam G R,Basu S, Honavar V. Representing and reasoning with qualitative preferences for compositional systems[J]. Journal of Artificial Intelligence Research, 2011, 42(1): 211-274.

[5] Koutrika G, Ioannidis Y E. Personalized queries under a generalized preference model[C]. Proceedings of the International Conference on Data Engineering, 2005, 841-852.

[6] Coffman J, Weaver A C. Learning to rank results in relational keyword search[C]. Proceedings of the ACM Conference on Information and Knowledge Management, 2011, 1689-1698.

[7] 孟祥福, 馬宗民, 李昕, 等. 基于上下文偏好的Web數(shù)據(jù)庫查詢結(jié)果Top-k排序方法[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 37(9): 1986-1998.

[8] Liu T Y, Wan H, Ma W Y. An editor labeling model for training set expansion in web categorization[C]. Proceedings of the 2005 IEEE International Conference on Web Intelligence, 2005: 165-171.

[9] Bekkerman R, El-Yaniv R, Tishby N, Winter Y. Distributional word clusters vs words for text categorization[J]. Journal of Machine Learning Research, 2003, 3(3): 1183-1208.

[10] Al-Mubaid H, Umair S. A. A new text categorization technique using distributional clustering and learning logic[J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(9): 1156-1165.

[11] Chen Z Y, Li T. Addressing diverse user preferences in SQL-Query-Result navigation[C]. Proceedings of the ACM SIGMOD International Conference on Management of Data, 2007: 641-652.

責(zé)任編校：孫 林

Categorization Approach to Query Results Based on Heuristic Searching Cost

GAO Jian

（Department of Mechanical and Electrical Engineering, Panjin Vocational & Technical college, Panjin 124010, China）

This paper proposes a categorization approach to query results based on searching cost. Firstly, a general exploration model which meets users’ query habits is presented. And then, a searching cost model is built corresponding to the exploration model. To estimate the searching cost, this paper proposes a searching cost measuring method by taking advantage of query history. Lastly, a labeled and leveled categorization tree is generated according to the searching cost. By using the categorization tree, users can easily find their favorite results by checking the label assigned on the tree nodes. The experiments demonstrate that the method can efficiently avoid the information overload, and has the higher categorization accuracy and lower searching cost as well.

searching cost; information overload; query result categorization

10.15916/j.issn1674-3261.2017.02.004

TP311

A

1674-3261(2017)02-0085-06

2016-06-22

高建(1981-)，男，遼寧盤錦人，講師，本科。