高 建

?

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

高 建

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

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

搜索代價(jià)；信息過(guò)載；查詢(xún)結(jié)果分類(lèi)

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

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

1 相關(guān)工作

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

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

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

2 分類(lèi)基本概念

2.1 分類(lèi)空間

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

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

分類(lèi)樹(shù)：給定分類(lèi)結(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è)互不重疊的目錄有序列表。使用的屬性被稱(chēng)為第層節(jié)點(diǎn)的分類(lèi)屬性，也是第1層節(jié)點(diǎn)的子分類(lèi)屬性。例如，“Price”是在第2層中所有節(jié)點(diǎn)的分類(lèi)屬性，同時(shí)也是第1層所有節(jié)點(diǎn)的子分類(lèi)屬性。需要指出的是，一個(gè)屬性只能有一次機(jī)會(huì)作為分類(lèi)屬性。

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

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

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

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

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

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

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

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

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

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

2.2 搜索模型

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

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

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

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

3.1 代價(jià)模型

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

例如，計(jì)算在圖1中分類(lèi)樹(shù)上的搜索代價(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)用中，由于不能明確知道用戶(hù)的查詢(xún)意圖，因而無(wú)法確定用戶(hù)會(huì)選擇哪個(gè)分支和哪些元組。為了對(duì)搜索代價(jià)進(jìn)行估計(jì)，需要知道下列2個(gè)與中每個(gè)目錄相關(guān)聯(lián)的概率，從而估計(jì)Cost(,)：

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

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

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

3.2 概率估計(jì)

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

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

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

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

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

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

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

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

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

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

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

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

4 分類(lèi)算法

4.1 分類(lèi)屬性約簡(jiǎn)和屬性劃分

4.1.1 分類(lèi)屬性約簡(jiǎn)

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

4.1.2 文本型屬性劃分

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

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

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

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

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

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

4.2 查詢(xún)結(jié)果分類(lèi)樹(shù)構(gòu)建

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

(1)決定分類(lèi)屬性。

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

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

算法1. 查詢(xún)結(jié)果分類(lèi)樹(shù)構(gòu)建算法 Categorize(R)輸入：查詢(xún)結(jié)果R，參數(shù)M，數(shù)值區(qū)間分割點(diǎn)成績(jī)輸出：基于R的分類(lèi)樹(shù)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è)分類(lèi)屬性A6. if A是一個(gè)文本屬性7. SCL?以occ(vi)的降序列出所有的單值目錄8. for S中的每一個(gè)目錄C9. 構(gòu)建Tree(C, A)，該樹(shù)以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)，該樹(shù)以C為根，以A上劃分的區(qū)間作為C的子目錄14. 計(jì)算15. 選擇作為第l層的分類(lèi)屬性16. for S中的每一個(gè)目錄C17. 把由使用屬性a得到的劃分Tree(C, a)添加到T中18. l = l+119. end

算法1從第0層開(kāi)始創(chuàng)建分類(lèi)樹(shù)，每層的分類(lèi)屬性都是從剩余屬性中選取具有最小搜索代價(jià)的屬性作為分類(lèi)屬性。算法遞歸執(zhí)行，直到每個(gè)目錄包含的元組個(gè)數(shù)不超過(guò)個(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硬盤(pán)，操作系統(tǒng)為Windows 2007，算法采用Java語(yǔ)言實(shí)現(xiàn)。測(cè)試數(shù)據(jù)使用http://estate.yahoo.com的房地產(chǎn)銷(xiāo)售數(shù)據(jù)庫(kù)，選擇Washington州的Seattle城市，元組數(shù)約有20 000條，包含的屬性有Price、SqFt、Location、Bedrooms、Bathrooms、Buildyear、Garage、Livingarea、Neighborhood和Schooldistrict，其中Price、SqFt、Bedrooms、Bathrooms和Buildyear是數(shù)值型屬性，其余為文本型屬性。查詢(xún)歷史包含2 000條用戶(hù)查詢(xún)。

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

5.2 分類(lèi)效果測(cè)試

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

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

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

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

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

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

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

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

6 結(jié)論與展望

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

如何對(duì)分類(lèi)樹(shù)中的目錄進(jìn)行排序是需進(jìn)一步解決的問(wè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ù)庫(kù)查詢(xún)結(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-)，男，遼寧盤(pán)錦人，講師，本科。