畢崇春，孟祥福，張霄雁，唐延歡，唐曉亮，梁海波

(1.遼寧工程技術(shù)大學(xué) 電子與信息工程院，遼寧 葫蘆島 125105； 2.遼寧工程技術(shù)大學(xué) 軟件學(xué)院，遼寧 葫蘆島 125105)(*通信作者電子郵箱marxi@126.com)

0 引言

隨著移動(dòng)網(wǎng)絡(luò)的普遍應(yīng)用，對(duì)于興趣點(diǎn)(Point Of Interests, POI)，如飯店、賓館、旅游景點(diǎn)等的空間Web對(duì)象(簡稱空間對(duì)象)的查詢已成為當(dāng)前空間數(shù)據(jù)庫和信息檢索領(lǐng)域的研究熱點(diǎn)?？臻g對(duì)象一般包含兩類信息：空間信息(Spatial Information,如經(jīng)緯度)和描述信息(Descriptive Information,如對(duì)象名稱、特征等信息)。空間查詢條件的基本形式為：{位置，〈關(guān)鍵字1,關(guān)鍵字2,…,關(guān)鍵字m〉}，其中“位置”代表空間信息查詢條件(通常用一對(duì)經(jīng)緯度或一個(gè)地理范圍表示)；關(guān)鍵字代表文本查詢條件[1]。研究發(fā)現(xiàn)，目前大約有五分之一的Web查詢都與空間位置相關(guān)[2]，并且這種類型查詢的比例還在不斷增長。然而，由于空間數(shù)據(jù)庫通常蘊(yùn)含海量數(shù)據(jù)且空間查詢又通常是試探性的，因此一個(gè)普通查詢往往會(huì)返回大量結(jié)果，這種情況被稱為“信息過載”問題。例如，當(dāng)用戶向Yahoo房地產(chǎn)網(wǎng)站提交了一個(gè)尋找“位于西雅圖市中心(位置查詢)、價(jià)格較低(關(guān)鍵字查詢)”的房屋查詢條件后，系統(tǒng)會(huì)返回?cái)?shù)以千計(jì)的房產(chǎn)信息。為了找到真正感興趣的信息，用戶需要逐條檢查每個(gè)結(jié)果對(duì)象的相關(guān)性，這將浪費(fèi)大量時(shí)間和精力。

為了解決信息過載問題，一些研究工作提出根據(jù)空間對(duì)象與查詢條件的位置相近度和文本相關(guān)度對(duì)查詢結(jié)果進(jìn)行top-k排序[3-7]。然而，這種方法返回的空間對(duì)象的排序次序固定，不能為用戶提供多樣選擇，而不同用戶的需求可能是不同的。文獻(xiàn)[10]指出，分類與排序是解決多查詢結(jié)果問題的兩個(gè)互補(bǔ)手段。本文提出一種空間對(duì)象查詢結(jié)果分類方法，該方法能夠在查詢結(jié)果集上動(dòng)態(tài)產(chǎn)生一棵分層的分類樹，樹的每個(gè)葉節(jié)點(diǎn)包含一類在位置和語義上都相近的空間對(duì)象，用戶通過檢查分類樹中間節(jié)點(diǎn)的標(biāo)簽，可以逐步定位到其感興趣的信息。下面用一個(gè)簡單例子來說明本文分類方法的基本思想。

例1 對(duì)于Yahoo房地產(chǎn)搜索網(wǎng)站，圖1給出了利用本文方法在查詢條件“位于西雅圖市中心且價(jià)格≤250 000”的查詢結(jié)果上生成的一棵分類樹。該樹的每個(gè)節(jié)點(diǎn)上都帶有一個(gè)描述房產(chǎn)特征信息的標(biāo)簽，用戶可根據(jù)樹各節(jié)點(diǎn)標(biāo)簽進(jìn)行導(dǎo)航，進(jìn)而找到他們所感興趣的房子。

圖1 Yahoo房產(chǎn)網(wǎng)站上的空間查詢結(jié)果分類樹實(shí)例

本文的分類方法由兩個(gè)步驟構(gòu)成：第一步是在離線階段分析空間對(duì)象之間的耦合關(guān)系(本文的耦合關(guān)系是指空間對(duì)象之間在位置信息和描述信息上存在的顯式/隱式關(guān)聯(lián)關(guān)系)，并據(jù)此對(duì)空間對(duì)象進(jìn)行聚類?，F(xiàn)實(shí)中，如果用戶對(duì)某個(gè)空間對(duì)象感興趣，那么他通常也會(huì)對(duì)與該對(duì)象位置和語義相近的一類對(duì)象感興趣，因此每個(gè)空間對(duì)象聚類都對(duì)應(yīng)一種類型的用戶需求。第二步，對(duì)于一個(gè)用戶查詢，根據(jù)在離線階段產(chǎn)生的空間對(duì)象聚類，在查詢結(jié)果集上利用改進(jìn)的C4.5決策樹算法自動(dòng)生成一棵分類樹，用戶通過檢查分類樹標(biāo)簽最終導(dǎo)航到其感興趣的結(jié)果對(duì)象。

1 相關(guān)工作

近年來，隨著Web上的空間對(duì)象日益增多和移動(dòng)網(wǎng)絡(luò)的普遍應(yīng)用，空間關(guān)鍵字的top-k查詢和排序方法受到了廣泛關(guān)注。根據(jù)文獻(xiàn)[8-9]，這些空間查詢方法可分為三類。1)布爾kNN(kNearest Neighbor)查詢[5]：該類方法用于檢索那些距離查詢位置最近且文本描述包含所有查詢關(guān)鍵字的前k個(gè)空間對(duì)象。2)top-k范圍查詢[6]：用于檢索那些與查詢關(guān)鍵字具有最高文本相關(guān)度且位于查詢區(qū)域內(nèi)的前k個(gè)空間對(duì)象。3)top-kkNN查詢[7]：該類方法根據(jù)空間對(duì)象的位置相近性和文本相關(guān)性進(jìn)行top-k檢索和排序，排序分?jǐn)?shù)根據(jù)對(duì)象到查詢位置的距離和空間對(duì)象的文本描述與查詢關(guān)鍵字的文本相關(guān)度的權(quán)重進(jìn)行評(píng)估。

就我們所知，目前還沒有對(duì)空間數(shù)據(jù)查詢結(jié)果分類方法的研究工作。在關(guān)系數(shù)據(jù)庫查詢領(lǐng)域，文獻(xiàn)[10]和[11]分別提出了基于貪心算法(Greedy Algorithm)和基于決策樹分類算法的查詢結(jié)果分類方法。Chakrabarti等[10]提出了一種利用貪心算法構(gòu)建查詢結(jié)果分類樹的方法，該方法利用系統(tǒng)中的歷史查詢數(shù)據(jù)推斷大多數(shù)用戶的偏好，據(jù)此作為當(dāng)前用戶對(duì)每個(gè)分類屬性感興趣的概率。文獻(xiàn)[11]利用了C4.5決策樹算法，提出了一種兩步解決方法：第一步對(duì)用戶的歷史查詢數(shù)據(jù)聚類；第二步構(gòu)建一棵搜索樹來實(shí)現(xiàn)用戶的個(gè)性化查詢。然而，使用該方法構(gòu)建分類樹存在以下兩個(gè)缺點(diǎn)：1)元組聚類僅依賴于用戶歷史查詢數(shù)據(jù)，若歷史查詢數(shù)據(jù)不充分或不準(zhǔn)確，就會(huì)導(dǎo)致算法失效；2)數(shù)值屬性值域的劃分采用二元?jiǎng)澐?，然而這種劃分在實(shí)際應(yīng)用中通常會(huì)導(dǎo)致不合適(過大或過小)的數(shù)值區(qū)間分割。本文方法借鑒了上述在關(guān)系數(shù)據(jù)庫查詢領(lǐng)域?qū)Σ樵兘Y(jié)果進(jìn)行分類的思想來對(duì)空間查詢結(jié)果進(jìn)行分類。需要指出的是，空間數(shù)據(jù)所包含的信息比關(guān)系數(shù)據(jù)更為復(fù)雜(包含位置和描述信息)，對(duì)象聚類和結(jié)果分類需要同時(shí)考察空間對(duì)象在位置和描述信息方面的相關(guān)性。

在文本分類[12-14]和Web查詢結(jié)果分類[15-16]方面，研究者也進(jìn)行了大量研究，但是分類對(duì)象與本文的分類對(duì)象不同：本文是對(duì)空間對(duì)象進(jìn)行分類，空間對(duì)象同時(shí)包含了空間位置信息和文本描述信息，而文本分類方法僅能對(duì)文本信息進(jìn)行分類。本文提出的分類樹構(gòu)建方法目的在于搜索代價(jià)最小化，而現(xiàn)存的文本分類方法僅考慮如何準(zhǔn)確劃分?jǐn)?shù)據(jù)。

2 相關(guān)定義和解決方案

本章首先給出分類樹及其搜索代價(jià)定義，然后描述解決方案。

2.1 查詢結(jié)果分類樹

空間對(duì)象包含位置信息和描述信息，本文將描述信息轉(zhuǎn)換成〈屬性，值〉的形式，這樣每個(gè)空間對(duì)象的描述信息將構(gòu)成一個(gè)關(guān)系元組。例如，在例1的Yahoo房產(chǎn)信息中，一個(gè)房屋的描述信息將由〈Price,14 999〉，〈View,water〉，〈Bedrooms,5〉，〈SqFt,2 000〉等數(shù)據(jù)單元構(gòu)成。

用D表示一個(gè)包含n個(gè)空間對(duì)象的數(shù)據(jù)集，A表示D中空間對(duì)象描述信息的屬性集{A1,A2,…,Am}。在此基礎(chǔ)上定義查詢結(jié)果分類樹和預(yù)計(jì)搜索代價(jià)。

定義1 分類樹。一個(gè)分類樹T(V,E,L)是由一個(gè)節(jié)點(diǎn)集合V、一個(gè)邊集合E和一個(gè)標(biāo)簽集合L三部分構(gòu)成。每個(gè)節(jié)點(diǎn)v∈V都有一個(gè)描述該節(jié)點(diǎn)特征的標(biāo)簽lab(v)∈L，它需要滿足如下條件：1)該標(biāo)簽是指定在某個(gè)屬性上的等值或范圍查詢條件(如Price<100 000或Price between 100 000 and 150 000)；2)節(jié)點(diǎn)v中包含的一組空間對(duì)象N(v)必須滿足它所有前驅(qū)(包括它自身)上的標(biāo)簽；3)一個(gè)中間節(jié)點(diǎn)的所有孩子節(jié)點(diǎn)上的標(biāo)簽都指定在同一屬性上(該屬性被稱為分類屬性)，這些標(biāo)簽構(gòu)成了對(duì)節(jié)點(diǎn)v中所有N(v)個(gè)對(duì)象的不相交劃分。

2.2 預(yù)計(jì)搜索代價(jià)

給定一個(gè)空間查詢結(jié)果分類樹T，用v表示一個(gè)葉節(jié)點(diǎn)，該節(jié)點(diǎn)包含了T中一組空間對(duì)象N(v)，Cj是集合C中的一個(gè)聚類(該聚類中包含了一組位置相近和語義相關(guān)的空間對(duì)象集合)，Cj∩v≠?表示葉節(jié)點(diǎn)v中包含了聚類Cj中的空間對(duì)象，Anc(v)表示節(jié)點(diǎn)v的前驅(qū)集合(包括v本身在內(nèi))，但不包含根節(jié)點(diǎn)；Sib(v)表示節(jié)點(diǎn)v的兄弟集合(包含v本身在內(nèi))。令K1和K2分別表示訪問葉節(jié)點(diǎn)中一個(gè)空間對(duì)象以及訪問一個(gè)中間節(jié)點(diǎn)標(biāo)簽的代價(jià)，Pj表示用戶對(duì)于聚類Cj感興趣的概率。

定義2 預(yù)計(jì)搜索代價(jià)。用戶使用分類樹找到所有相關(guān)對(duì)象的預(yù)計(jì)搜索代價(jià)為：

(1)

例如，假設(shè)某用戶對(duì)圖1所示的分類樹最上面的葉節(jié)點(diǎn)(“SqFt：1 500～1 999”)感興趣的概率是100%，再假設(shè)K1=K2=1，則用戶訪問葉節(jié)點(diǎn)“SqFt：1 500～1 999”的搜索代價(jià)為：3(檢查根下3個(gè)子節(jié)點(diǎn)標(biāo)簽的代價(jià))+3(檢查中間節(jié)點(diǎn)“View: Street”下3個(gè)孩子標(biāo)簽的代價(jià))+2(檢查中間節(jié)點(diǎn)“Location: 0～4.9 km”下2個(gè)孩子標(biāo)簽的代價(jià))+8(檢查葉節(jié)點(diǎn)“SqFt: 1 500～1 999”下8個(gè)空間對(duì)象的代價(jià))=16。

2.3 解決方案

分類樹構(gòu)建的解決方案如下：

1)空間對(duì)象耦合相關(guān)度評(píng)估與聚類。

首先利用歐氏距離計(jì)算兩個(gè)空間對(duì)象在空間位置上的距離；然后利用語義相關(guān)度評(píng)估方法計(jì)算空間對(duì)象在描述信息上的語義相關(guān)度；最后，用式(2)將位置關(guān)系和語義關(guān)系相融合得到兩個(gè)空間對(duì)象oi和oj之間的耦合相關(guān)度：

Sim(oi,oj)=α·E_sim(oi,oj)+(1-α)·S_sim(oi,oj)

(2)

其中：α∈[0,1]是一個(gè)調(diào)節(jié)參數(shù)，E_sim()和S_sim()分別代表oi和oj之間的位置相近度和語義相關(guān)度。

根據(jù)空間對(duì)象之間的耦合關(guān)系，利用基于概率密度估計(jì)的聚類方法把空間對(duì)象劃分為q個(gè)類別{C1,C2,…,Cq}，使得每個(gè)類別中包含的空間對(duì)象在位置和語義上都比其他類中的對(duì)象更為接近。

2)分類樹構(gòu)建。

對(duì)于一個(gè)空間數(shù)據(jù)庫D、一個(gè)聚類集合C和一個(gè)空間查詢Q，本文目的是構(gòu)建一棵分類樹T(V,E,L)，使得：①該樹中的葉節(jié)點(diǎn)包含了D中滿足查詢Q的所有空間對(duì)象；②不存在另外一棵樹T′既滿足條件1)又使得搜索代價(jià)Cost(T′,C)

算法1 查詢結(jié)果分類樹生成過程。

輸入：空間數(shù)據(jù)庫D，聚類集合C和空間查詢條件Q。

輸出：分類樹T。

1)離線階段。計(jì)算空間數(shù)據(jù)庫D中所有空間對(duì)象之間的耦合相關(guān)度，在此基礎(chǔ)上對(duì)D中的空間對(duì)象進(jìn)行聚類，得到一個(gè)不相交的空間對(duì)象聚類集合C={C1,C2,…,Cq}，其中每個(gè)聚類Cj{1≤j≤q}都關(guān)聯(lián)一個(gè)用戶對(duì)其感興趣的概率Pj。

2)在線階段。在查詢Q返回的結(jié)果集T上，使用C1,C2,…,Cq作為類標(biāo)簽，利用改進(jìn)的C4.5算法構(gòu)建一棵具有最小預(yù)計(jì)搜索代價(jià)Cost(T,C)的分類樹。

算法1的復(fù)雜度分析 在離線階段(步驟1))需要計(jì)算出D中任意一對(duì)空間對(duì)象之間的耦合相關(guān)度，如果D中有n個(gè)空間對(duì)象，則離線階段的計(jì)算復(fù)雜度為O(n2)。為了降低離線計(jì)算的工作量，可以以固定時(shí)間間隔計(jì)算耦合相關(guān)度或當(dāng)數(shù)據(jù)更新程度較大時(shí)再計(jì)算耦合相關(guān)度。對(duì)于在線階段(步驟2))的計(jì)算復(fù)雜度，本文將在第3章的算法3中進(jìn)行分析。

3 空間對(duì)象的耦合相關(guān)度評(píng)估與聚類方法

本章首先描述空間對(duì)象之間的耦合相關(guān)度評(píng)估方法，然后提出如何根據(jù)空間對(duì)象的耦合相關(guān)度對(duì)其進(jìn)行聚類。

3.1 耦合相關(guān)度評(píng)估

空間對(duì)象之間的耦合相關(guān)度是由空間對(duì)象在位置上的相近度和描述信息上的語義相關(guān)度構(gòu)成。

1)空間對(duì)象的位置相近度。

歐氏距離是現(xiàn)有研究工作中最常用的評(píng)估空間對(duì)象之間距離的方法[3,6,9]，本文也采用歐氏距離評(píng)估空間對(duì)象之間的位置距離，空間對(duì)象oi和oj的距離定義如下：

(3)

其中，n表示空間對(duì)象的空間維度。基于式(3)，空間對(duì)象oi和oj之間在距離上的相近度定義如下：

E_Sim(oi,oj)=1-Dist(oi,oj)/Maxdist

(4)

式(4)是對(duì)位置相近度的歸一化處理，其中Maxdist代表空間數(shù)據(jù)庫中所有空間對(duì)象之間的最大距離。

2)空間對(duì)象的語義相關(guān)度。

現(xiàn)有方法通常采用VSM(Vector Space Model)及其改進(jìn)方法評(píng)估兩個(gè)文本之間的相關(guān)度，但現(xiàn)實(shí)中空間對(duì)象的描述之間通常存在復(fù)雜的語義關(guān)系。本文提出一種語義相關(guān)度評(píng)估方法。該方法是對(duì)文獻(xiàn)[18]中提出方法的一種改進(jìn)，其基本思想是：對(duì)于同一屬性下的兩個(gè)值，如果它們?cè)谕粚傩灾涤蛑谐霈F(xiàn)的次數(shù)(或者發(fā)生頻率)類似，則表示這兩個(gè)值具有相關(guān)性，這反映了一個(gè)屬性中不同屬性值之間的內(nèi)耦合關(guān)系(intra-coupling relationship)。如前文所述，空間對(duì)象的描述信息將首先被轉(zhuǎn)換成〈屬性，值〉形式的關(guān)系元組，因此可使用屬性值的出現(xiàn)頻率來計(jì)算同一屬性下不同值之間的內(nèi)耦合相關(guān)度。具體來講，對(duì)于包含n個(gè)空間對(duì)象的空間數(shù)據(jù)集D，首先將所有空間對(duì)象的描述信息轉(zhuǎn)換成一個(gè)具有m個(gè)屬性{A1,A2,…,Am}和n條元組{t1,t2,…,tn}的關(guān)系表。在此基礎(chǔ)上，屬性Aj中的一對(duì)屬性值x和y的內(nèi)耦合度相關(guān)度(Intra-similarity)計(jì)算方法如下：

(5)

其中，NAj(x)和NAj(y)分別表示屬性Aj中包含屬性值x和y的元組個(gè)數(shù)。從式(5)可以看出，如果兩個(gè)屬性值在同一值域中的出現(xiàn)頻率越高，則它們之間的內(nèi)耦合相關(guān)度越大。

同一屬性上的兩個(gè)屬性值之間除了具有內(nèi)耦合關(guān)系外，它們的相關(guān)度還受到其他屬性的影響，這里稱之為間耦合相關(guān)度。屬性值之間的間耦合相關(guān)度評(píng)估的基本思想是：對(duì)于屬性Aj中的兩個(gè)屬性值x和y，假設(shè)U是x和y在其他屬性Ak上共同出現(xiàn)的屬性值的交集。如果U非空，則稱x和y在屬性Ak上相關(guān)。

基于上述思想，屬性值x和y在屬性Ak上的間耦合相關(guān)度定義為：

(6)

其中：U是x和y在屬性Ak上的交集，u是U的一個(gè)元素(即，u與x和y在相同元組中共同出現(xiàn)過)，PAk |Aj(u|x)(以及PAk |Aj(u|y))是u關(guān)于x(和y)的信息條件概率(Information Conditional Probability， ICP)，計(jì)算方法如下：

PAk |Aj(u|x)=|TAk(u)∩TAj(x)|/|TAj(x)|

(7)

其中：TAj(x)表示D中包含Aj=x的元組集合，TAk(u)表示D中包含Ak=u的元組集合。也就是說，u對(duì)于x的ICP指的是當(dāng)x在關(guān)系表中出現(xiàn)時(shí)，u與x共同出現(xiàn)的概率。可以看出，對(duì)于同一個(gè)屬性的兩個(gè)值，如果它們?cè)谄渌麑傩陨系腎CP越高，那么這兩個(gè)值的間耦合相關(guān)度就越高。

式(8)給出了屬性值〈x,y〉在所有其他屬性上的間耦合相關(guān)度計(jì)算方法：

(8)

接下來，把屬性值x和y之間的內(nèi)耦合和間耦合相關(guān)度進(jìn)行結(jié)合就可得到它們之間的語義相關(guān)度，即：

S_SimAj(x,y)=β*IaSAj(x,y)+(1-β)*IeSAj(x,y)

(9)

其中，β(β∈[0，1])是一個(gè)調(diào)節(jié)參數(shù)，用來調(diào)整內(nèi)耦合和間耦合相關(guān)度在最終的語義相關(guān)度中的作用。

最后，空間對(duì)象oi和oj在描述信息上的語義相關(guān)度可定義為它們?cè)谒袑傩陨系膬?nèi)耦合和間耦合相關(guān)度的結(jié)合：

(10)

其中，wk代表Ak的屬性權(quán)重，m是屬性個(gè)數(shù)。

3)空間對(duì)象的耦合相關(guān)度。

給定空間對(duì)象oi和oj在位置上的相近度和在描述信息上的語義相關(guān)度，它們之間的耦合相關(guān)度可以用式(2)來計(jì)算。接下來，本文將論述如何利用空間對(duì)象之間的耦合相關(guān)度對(duì)它們進(jìn)行聚類。

3.2 空間對(duì)象聚類

本文提出的空間對(duì)象聚類的基本思想是：首先利用概率密度估計(jì)方法評(píng)估空間對(duì)象的典型程度，然后提取前k個(gè)最具有代表性的空間對(duì)象，最后把其他對(duì)象按其對(duì)代表性對(duì)象的耦合相關(guān)度分配到不同聚類中。

1)概率密度估計(jì)方法。

高斯核函數(shù)是概率密度估算中的常用方法，當(dāng)僅知道空間對(duì)象的耦合關(guān)系距離矩陣時(shí)，可以使用該方法找出空間對(duì)象集合中的代表性對(duì)象[19]。對(duì)于一個(gè)空間對(duì)象集合D=(o1,o2,…,on)，對(duì)象o的概率密度f(o)可以表示為：

(11)

根據(jù)空間對(duì)象的典型程度，可以選出前k個(gè)典型程度最高的對(duì)象作為代表，其他對(duì)象按其對(duì)代表對(duì)象的耦合相關(guān)度進(jìn)行聚類，這樣可將空間對(duì)象劃分成k個(gè)類別。

2)空間對(duì)象的聚類算法。

給定一個(gè)空間數(shù)據(jù)庫D，選取前k個(gè)代表性對(duì)象的準(zhǔn)確方法是利用式(11)逐個(gè)計(jì)算每個(gè)空間對(duì)象的典型程度。然而，在數(shù)據(jù)規(guī)模很大的情況下，逐個(gè)計(jì)算空間對(duì)象的典型程度具有很高復(fù)雜度，因此需要考慮一種近似算法。本文提出一種基于淘汰思想的聚類方法，該方法的優(yōu)點(diǎn)是簡便且具有較高準(zhǔn)確性，其聚類過程為：

a)將空間數(shù)據(jù)庫D隨機(jī)劃分成若干個(gè)小組，每個(gè)小組都包含u個(gè)對(duì)象，即將D劃分成了「n/u?個(gè)小組，接著在每個(gè)小組內(nèi)計(jì)算所有對(duì)象的典型程度，選取每個(gè)小組中典型程度最高的對(duì)象構(gòu)成一個(gè)新的集合，然后從D中去除其他對(duì)象。

b)對(duì)于新得到的集合，重復(fù)上述過程，直到D中只剩下一個(gè)對(duì)象，將該對(duì)象放入top-k候選對(duì)象集合中(上述過程記為一次選取過程)。

c)為了保證選取對(duì)象的準(zhǔn)確性，需要將上述選取過程重復(fù)執(zhí)行v次(記為一輪)，這樣top-k候選對(duì)象集合中最多會(huì)包含v個(gè)對(duì)象，接著在最初的空間數(shù)據(jù)庫D上計(jì)算這v個(gè)對(duì)象的典型程度，最后將具有最高典型程度的對(duì)象作為當(dāng)前輪次的選取結(jié)果，并從D中將該對(duì)象去除。

上述a)～c)過程重復(fù)k輪，這樣就能得到k個(gè)近似于準(zhǔn)確解的對(duì)象。

d)將D中剩余對(duì)象依次與這k個(gè)代表性對(duì)象分別比較耦合關(guān)系距離，各自劃分到與代表性空間對(duì)象最相近的類別中。

算法2 top-k代表性對(duì)象近似選取和聚類算法。

輸入：空間數(shù)據(jù)庫D，驗(yàn)證次數(shù)v，正整數(shù)k，小組大小u。

輸出：top-k個(gè)代表性對(duì)象及其對(duì)應(yīng)的聚類。

fori=1 tokdo

fori=1 tovdo

repeat

劃分D成為若干小組g，每個(gè)小組有u個(gè)對(duì)象

for each小組gdo

計(jì)算g中每個(gè)對(duì)象在g中的典型程度

從g中選出典型程度最高的對(duì)象，將g中其他對(duì)象從D中移除

end for

untilD中僅有一個(gè)對(duì)象

把得到的典型程度最高的對(duì)象放入候選集合中

end for

在D上計(jì)算候選集合中每個(gè)對(duì)象的典型程度，輸出一個(gè)典型程度最高的對(duì)象作為第i次選出的代表性空間對(duì)象

end for

將其他對(duì)象按其與代表性對(duì)象的距離進(jìn)行聚類

3.3 用戶對(duì)聚類感興趣的概率估計(jì)

本文借助查詢歷史評(píng)估用戶對(duì)空間對(duì)象聚類感興趣的概率，其直覺是如果某個(gè)聚類中的空間對(duì)象被用戶查詢的次數(shù)越多，說明用戶對(duì)該聚類感興趣的概率就越大。

給定一個(gè)空間對(duì)象聚類Cj，先統(tǒng)計(jì)查詢歷史H中能夠返回Cj中任意一個(gè)對(duì)象的查詢，這些查詢構(gòu)成一個(gè)集合Sj，即Sj={QCj|?Qi∈H，使得oi(oi∈Cj)能夠由Qi返回}。這樣，對(duì)于每一個(gè)聚類Cj，可通過計(jì)算Sj中包含的查詢個(gè)數(shù)與查詢總數(shù)之比得到用戶對(duì)該聚類感興趣的概率，即Pj=Sj中包含的查詢個(gè)數(shù)/H中的查詢總數(shù)。

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

本章首先提出空間對(duì)象查詢結(jié)果分類樹的構(gòu)建算法；然后描述對(duì)于文本信息中的分類型屬性和數(shù)值型屬性的劃分標(biāo)準(zhǔn)；最后給出分類樹構(gòu)建算法描述。

4.1 屬性劃分

本文提出了基于C4.5決策樹算法的查詢結(jié)果分類樹構(gòu)建方法。由于C4.5算法需要對(duì)屬性進(jìn)行劃分，空間對(duì)象的描述信息主要包含文本屬性和數(shù)值屬性，因此下面分別描述文本和數(shù)值屬性的劃分標(biāo)準(zhǔn)。

1)文本屬性的劃分。

對(duì)于每一個(gè)不同的文本值，在查詢結(jié)果分類樹上產(chǎn)生一個(gè)新的子樹，并且在該子樹上計(jì)算信息增益。

2)數(shù)值屬性的劃分。

本文借助用戶的查詢歷史劃分?jǐn)?shù)值屬性值域。對(duì)于數(shù)值屬性Ai，用vmin和vmax分別表示Dom(Ai)的最小值和最大值。首先考慮簡單劃分的情況，假設(shè)僅將Dom(Ai)劃分成兩個(gè)互不相交的數(shù)值區(qū)間，即[vmin,v]和(v,vmax]。如果在查詢歷史中，大多數(shù)查詢范圍是以點(diǎn)v開始或結(jié)束，則點(diǎn)v是一個(gè)最佳分割點(diǎn)。因?yàn)橥ㄟ^查詢歷史可知，大多數(shù)用戶是對(duì)以點(diǎn)v劃分的兩個(gè)數(shù)值區(qū)間其中之一感興趣。

對(duì)于查詢歷史中指定在屬性Ai上的范圍查詢，令Nv-start和Nv-end分別代表這些查詢中以點(diǎn)v開始或結(jié)束的查詢個(gè)數(shù)，然后用Nv-start和Nv-end之和代表點(diǎn)v的“分割能力”。很明顯，如果查詢歷史中以點(diǎn)v開始或結(jié)束的范圍查詢數(shù)量越多，說明認(rèn)為點(diǎn)v是一個(gè)好的分割點(diǎn)的用戶越多，那么點(diǎn)v的分割能力就越強(qiáng)。假設(shè)要將Dom(Ai)劃分為k個(gè)數(shù)值區(qū)間，采用上述方法，那么需要選取具有最高分割能力的(k-1)個(gè)點(diǎn)。需要指出的是，數(shù)值屬性的候選分割點(diǎn)是通過在該屬性值域區(qū)間內(nèi)以固定數(shù)值間隔獲得的。

4.2 分類樹構(gòu)建算法

基于上述思想，算法3給出了基于改進(jìn)決策樹算法的查詢結(jié)果分類樹構(gòu)建過程。

算法3 查詢結(jié)果分類樹構(gòu)建算法。

函數(shù)：BuildTree(A,R,C,λ)

輸入：空間對(duì)象描述信息的屬性集A，結(jié)果對(duì)象集合R，C是R中每個(gè)對(duì)象在聚類中對(duì)應(yīng)的標(biāo)簽，終止閾值λ。

輸出：查詢結(jié)果分類樹T。

創(chuàng)建一個(gè)根節(jié)點(diǎn)r

ifR中所有對(duì)象有同樣的類標(biāo)簽，終止算法

for每個(gè)屬性Aj∈A

ifAj是一個(gè)文本屬性then

forAj的每個(gè)屬性值vdo

在當(dāng)前根節(jié)點(diǎn)下創(chuàng)建一個(gè)分支，將滿足條件“Aj=v”的那些對(duì)象加入到該分支中

計(jì)算gaing(Aj,Tj)，Tj是由劃分屬性Aj而產(chǎn)生的子樹

else

forAj的每個(gè)范圍[lowi,upi] do

在當(dāng)前根節(jié)點(diǎn)下創(chuàng)建一個(gè)分支，將滿足條件“l(fā)owi≤Ai

計(jì)算gaing(Aj,Tj)，Tj是由劃分屬性Aj的值域產(chǎn)生的子樹

end if

end for

選擇具有最大g(Aj,Tj)的屬性Aj，從A中移除Aj

ifg(Aj,Tj)>λthen

用子樹Tj代替r，對(duì)于Tj(用Rk表示leafk中的對(duì)象集合)中每個(gè)葉節(jié)點(diǎn)leafk，遞歸執(zhí)行BuildTree(A，Rk，C，λ)

end if

利用算法3，可在查詢結(jié)果集上動(dòng)態(tài)地生成一個(gè)查詢結(jié)果分類樹，用戶可通過檢查標(biāo)簽的方式自左至右或自上而下訪問該樹，并最終定位到其感興趣的葉子節(jié)點(diǎn)。

算法3的復(fù)雜度分析 假設(shè)結(jié)果集中有n個(gè)空間對(duì)象，m是分類屬性個(gè)數(shù)，k為類別數(shù)；在計(jì)算某個(gè)屬性的信息增益時(shí)，可以采用一些優(yōu)化算法。本文先按該屬性的屬性值對(duì)結(jié)果中的所有對(duì)象進(jìn)行排序，然后對(duì)該屬性上的所有不同屬性值進(jìn)行一次性的信息增益計(jì)算，這樣該屬性上的信息增益計(jì)算時(shí)間復(fù)雜度為O(k)。對(duì)于一個(gè)樹節(jié)點(diǎn)，由于每次計(jì)算信息增益的復(fù)雜度為O(k)，并且最多有m個(gè)候選分類屬性以及n種可能的劃分(最壞情況就是該屬性下有n個(gè)不同的屬性值)，因此對(duì)一個(gè)節(jié)點(diǎn)的所有可能劃分進(jìn)行信息增益計(jì)算的復(fù)雜度為O(mnk)。根據(jù)文獻(xiàn)[11]對(duì)決策樹的分析，生成的查詢結(jié)果分類樹的深度為logn，則算法3總的時(shí)間復(fù)雜度為O(mnklogn)。

5 實(shí)驗(yàn)

5.1 實(shí)驗(yàn)設(shè)置

所有實(shí)驗(yàn)在Windows 2007操作系統(tǒng)，Intel P4 3.2 GHz CPU和8 GB內(nèi)存的PC機(jī)上運(yùn)行，使用下列真實(shí)數(shù)據(jù)來評(píng)估算法效果和性能。

數(shù)據(jù)集 測試數(shù)據(jù)是從Yahoo房地產(chǎn)網(wǎng)站提取的包含100 000個(gè)房屋信息的房地產(chǎn)數(shù)據(jù)集。每個(gè)房屋都包含位置信息和描述信息，位置信息用經(jīng)度和緯度表示，描述信息由{Price,City,SqFt,Bedrooms,Livingarea,Schooldistrict,View,Neighborhood,Pool,Garage,Boatdock,Buildyear}屬性來描述，其中Price，SqFt，Bedrooms和Buildyear是數(shù)值屬性，剩余是文本屬性。

查詢歷史 邀請(qǐng)50名本科生作為測試者，他們作為不同類型的用戶向房地產(chǎn)數(shù)據(jù)集提交空間查詢，利用這種方式收集了500條查詢作為查詢歷史，用于數(shù)值屬性值域的劃分和用戶對(duì)空間對(duì)象聚類感興趣概率的估計(jì)。

所有算法采用Java編寫，使用R-tree[21]建立空間對(duì)象索引，空間對(duì)象數(shù)據(jù)表增加一列用于存放每條房屋記錄的類標(biāo)簽，查詢結(jié)果分類樹構(gòu)建算法(算法3)的終止閾值λ設(shè)為0.005。

對(duì)比方法 不同聚類方法得到的聚類結(jié)果不同，進(jìn)而影響到查詢結(jié)果分類樹的搜索代價(jià)，本文選取了兩種聚類方法：最遠(yuǎn)距離優(yōu)先的聚類方法和基于淘汰的聚類方法(本文方法)，然后對(duì)基于不同聚類方法構(gòu)建的查詢結(jié)果分類樹的實(shí)際搜索代價(jià)進(jìn)行對(duì)比。

最遠(yuǎn)距離優(yōu)先聚類方法的基本思想是：首先從空間對(duì)象集合中隨機(jī)抽出1個(gè)對(duì)象，然后從剩余對(duì)象中選取與該對(duì)象耦合關(guān)系距離最大的對(duì)象，并將其從集合中移除，下一步再從剩余對(duì)象中選出與上一個(gè)選出對(duì)象耦合關(guān)系距離最大的對(duì)象，重復(fù)上述步驟，直到k個(gè)對(duì)象被選出為止。最后，把剩余對(duì)象按其與這k個(gè)對(duì)象的耦合關(guān)系距離分別劃歸到相應(yīng)類別中。

5.2 屬性值相關(guān)度評(píng)估方法的合理性測試

該實(shí)驗(yàn)?zāi)繕?biāo)是評(píng)估空間對(duì)象文本值語義相關(guān)度評(píng)估方法的合理性。表1分別給出了在不同大小的數(shù)據(jù)集下與給定文本值最相關(guān)的前三個(gè)文本值。注意，在該實(shí)驗(yàn)中式(9)的參數(shù)β設(shè)為0.5，也就是說在評(píng)估文本值的語義相關(guān)度時(shí)內(nèi)耦合度和間耦合度起到同等重要的作用。

表1 不同大小數(shù)據(jù)集下對(duì)于給定屬性值的top-3個(gè)相關(guān)文本值

從表1中可以看出，與給定值最為相關(guān)的前三個(gè)文本值之間的語義相關(guān)度是合理的。還可以看出，從10 000，20 000個(gè)房屋數(shù)據(jù)集中獲取的相關(guān)度值低于從50 000個(gè)房屋數(shù)據(jù)集中獲取的相關(guān)度值，但相關(guān)度值的變化程度不大，并且相關(guān)度值大小的相對(duì)順序沒有發(fā)生改變。由此可見，本文提出的文本值之間的語義相關(guān)度評(píng)估方法是合理穩(wěn)定的。

5.3 搜索代價(jià)實(shí)驗(yàn)

該實(shí)驗(yàn)?zāi)康氖菧y試本文提出的查詢結(jié)果分類方法的實(shí)際搜索代價(jià)，同時(shí)也對(duì)基于不同聚類方法構(gòu)建的查詢結(jié)果分類樹的實(shí)際搜索代價(jià)進(jìn)行對(duì)比。實(shí)際搜索代價(jià)定義如下：

(12)

與定義2中的預(yù)計(jì)搜索代價(jià)不同，實(shí)際搜索代價(jià)是用戶通過使用查詢結(jié)果分類樹找到感興趣對(duì)象而真正訪問過的中間節(jié)點(diǎn)數(shù)和葉節(jié)點(diǎn)中的對(duì)象數(shù)。假設(shè)訪問中間節(jié)點(diǎn)標(biāo)簽和訪問葉節(jié)點(diǎn)中對(duì)象的代價(jià)是相等的，即K1=K2=1，實(shí)際搜索代價(jià)越低，表明查詢結(jié)果分類方法的效果就越好。

為了評(píng)估實(shí)際搜索代價(jià)，首先邀請(qǐng)10名測試者，每一名測試者提出1個(gè)測試查詢條件(比如，包含區(qū)域位置和價(jià)格區(qū)間)，然后在對(duì)應(yīng)的結(jié)果集中標(biāo)出他們認(rèn)為最滿足其需求和偏好的5個(gè)對(duì)象。最后，利用查詢結(jié)果分類樹構(gòu)建算法(算法3)根據(jù)不同聚類標(biāo)準(zhǔn)在查詢結(jié)果集上生成分類樹，用戶通過使用分類樹找出他們標(biāo)注的對(duì)象。在這一過程中，記錄用戶通過使用分類樹上找出所有標(biāo)注對(duì)象的實(shí)際搜索代價(jià)。表2分別給出了不同空間查詢條件下基于不同聚類方法生成的查詢結(jié)果分類樹的實(shí)際搜索代價(jià)。

表2 不同查詢條件的查詢結(jié)果分類樹實(shí)際搜索代價(jià)對(duì)比

從表2可以看出，對(duì)于測試者提出的10條測試查詢(指定了位置范圍和/或價(jià)格區(qū)間)，每個(gè)查詢返回的查詢結(jié)果總數(shù)都在500個(gè)以上，如果逐個(gè)檢查結(jié)果的相關(guān)性是非常耗時(shí)的。通過構(gòu)建查詢結(jié)果分類樹，用戶可以根據(jù)分類樹上的分支標(biāo)簽檢查各分支的相關(guān)性，進(jìn)而快速定位到感興趣的信息。從表2可以看出，與基于最遠(yuǎn)距離優(yōu)先的聚類方法相比，在基于淘汰思想的聚類算法上生成的查詢結(jié)果分類樹具有明顯較低的搜索代價(jià)。由此可見，本文的空間聚類方法具有較高準(zhǔn)確性。圖2(a)和圖2(b)分別給出了10條測試查詢?cè)诓煌垲悩?biāo)準(zhǔn)下的實(shí)際搜索代價(jià)和平均搜索代價(jià)對(duì)比。平均搜索代價(jià)是指找到每個(gè)相關(guān)對(duì)象的平均實(shí)際搜索代價(jià)。

圖2 10條測試查詢下基于不同聚類方法生成的

5.4 分類樹的生成時(shí)間測試

對(duì)于一個(gè)給定的空間查詢，通常會(huì)返回多個(gè)查詢結(jié)果，而查詢結(jié)果分類樹又是在在線階段動(dòng)態(tài)生成的，因此需要能夠快速生成。該實(shí)驗(yàn)?zāi)康氖菧y試在不同規(guī)模的查詢結(jié)果下分類樹的生成時(shí)間。圖3給出了房地產(chǎn)數(shù)據(jù)集上不同查詢結(jié)果個(gè)數(shù)下的分類樹生成時(shí)間。

圖3 不同查詢結(jié)果數(shù)下的分類樹生成時(shí)間

從圖3可以看出，在查詢結(jié)果數(shù)為100 000條的情況下，分類樹的構(gòu)建時(shí)間也不超過1.1 s，因此能夠適用于大規(guī)模數(shù)據(jù)情況下的查詢分類。

6 結(jié)語

本文提出了一種用于處理空間數(shù)據(jù)庫查詢信息過載問題的分類方法，該方法在離線階段評(píng)估空間對(duì)象之間的耦合關(guān)系，使用基于概率密度估計(jì)方法對(duì)空間對(duì)象進(jìn)行聚類。在在線階段，對(duì)于一個(gè)空間查詢條件，采用改進(jìn)決策樹算法在查詢結(jié)果上構(gòu)建一棵分類樹，用戶通過檢查分類樹中間節(jié)點(diǎn)標(biāo)簽的方式逐步定位到其感興趣的葉節(jié)點(diǎn)信息。

本文方法與現(xiàn)有方法有兩方面不同：一是空間聚類方法同時(shí)考慮了空間對(duì)象之間的位置相近性和語義相關(guān)度；二是查詢結(jié)果分類樹構(gòu)建算法同時(shí)考慮了訪問中間節(jié)點(diǎn)的代價(jià)和訪問葉節(jié)點(diǎn)中對(duì)象的代價(jià)。如何將將查詢結(jié)果排序方法融入到分類方法之中是進(jìn)一步的研究工作。

References)

[1] 劉喜平,萬常選,劉德喜,等.空間關(guān)鍵詞搜索研究綜述[J].軟件學(xué)報(bào),2016,27(2):329-347.(LIU X P, WAN C X, LIU D X, et al. Survey on spatial keyword search [J]. Journal of Software, 2016, 27(2): 329-347.)

[2] 張金增,孟小峰.移動(dòng)Web搜索研究[J].軟件學(xué)報(bào),2012,23(1):46-64.(ZHANG J Z, MENG X F. Research on mobile Web search [J]. Journal of Software, 2012, 23(1): 46-64.)

[3] ZHENG K, SU H, ZHENG B L. Interactive top-kspatial keyword queries [C]// Proceedings of the 2015 IEEE 31st International Conference on Data Engineering. Piscataway, NJ: IEEE, 2015: 423-434.

[4] CARY A, WOLFSON O, RISHE N. Efficient and scalable method for processing top-kspatial boolean queries [C]// Proceedings of the 2010 International Conference on Scientific and Statistical Database Management. Berlin: Springer, 2010: 87-95.

[5] LU Y, LU J H, SHAHABI C. Efficient algorithms and cost models for reverse spatial-keywordk-nearest neighbor search [J]. ACM Transactions on Database Systems, 2014, 39(2): 573-598.

[6] LU J H, LU Y, CONG G. Reverse spatial and textualknearest neighbor search [C]// Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2011: 349-360.

[7] HU H Q, LI G L. Top-kspatio-textual similarity join [J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(2): 551-565.

[8] 周傲英,楊彬,金澈清,等.基于位置的服務(wù):架構(gòu)與進(jìn)展[J].計(jì)算機(jī)學(xué)報(bào),2011,34(7):1155-1171.(ZHOU A Y, YANG B, JIN C Q, et al. Location-based services: architecture and progress [J]. Chinese Journal of Computers, 2011, 34(7): 1155-1171.)

[9] CHEN L, CONG G, JENSEN C S, et al. Spatial keyword query processing: an experimental evaluation [J]. Proceedings of the VLDB Endowment, 2013, 6(3): 217-228.

[10] CHAKRABARTI K, CHAUDHURI S, HWANG S. Automatic categorization of query results [C]// Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2004: 755-766

[11] CHEN Z Y, LI T. Addressing diverse user preferences in SQL-query-result navigation [C]// Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2007: 641-652.

[12] 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.

[13] ROUSSEAU F, KIAGIAS E, VAZIRGIANNIS M. Text categorization as a graph classification problem [C]// Proceedings of the 2015 Annual Meeting of the Association for Computational Linguistics. Beijing: [s.n.], 2015: 1702-1712.

[14] ZHENG W B, TANG H, QIAN Y T. Collaborative work with linear classifier and extreme learning machine for fast text categorization [J]. Journal of World Wide Web, 2013, 18(2): 1-18.

[15] ZENG H J, HE Q C, CHEN Z. Learning to cluster Web search results [C]// SIGIR ’04: Proceedings of the 27th Annual International ACM SIGIR Conference On Research and Development in Information Retrieval. New York: ACM, 2004: 210-217.

[16] GRBOVIC M, DJURIC N, RADOSAVLJEVIC V. QueryCatego-rizr: a large-scale semi-supervised system for categorization of Web search queries [C]// WWW 2015: Proceedings of the 24th International Conference on World Wide Web Companion. New York: ACM, 2015: 199-202.

[17] TWEEDIE L, SPENCE R, WILLIAMS D, et al. The attribute explorer [C]// CHI ’94: Proceedings of the 1994 Conference Companion on Human Factors in Computing Systems. New York: ACM, 1994: 435-436.

[18] WANG C, CAO L B, WANG M C. Coupled nominal similarity in unsupervised learning [C]// CIKM ’11: Proceedings of the 20th ACM International Conference on Information and Knowledge Management. New York: ACM, 2011: 973-978.

[19] 王秀紅,鞠時(shí)光.用于文本相似度計(jì)算的新核函數(shù)[J].通信學(xué)報(bào),2012,33(12):43-48.(WANG X H, JU S G. Novel kernel function for computing the similarity of text [J]. Journal of Communications, 2012, 33(12): 43-48.)

[20] BORIAH S, CHANDOLA V, KUMAR V. Similarity measures for categorical data: a comparative evaluation [C]// Proceedings of the 2008 SIAM International Conference on Data Mining. Atlanta, Georgia: [s.n.], 2008: 243-254.

[21] GUTTMAN A. R-trees: a dynamic index structure for spatial searching [C]// Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data. New York: ACM, 1984: 47-57.

This work is partially supported by the National Natural Science Foundation of China (61401185), the General Project of Liaoning Province Education Department (LJYL018), the Natural Science Foundation of Liaoning Province (201705 40418).

BIChongchun, born in 1992, M. S. candidate. His research interests include spatial data analysis and query.

MENGXiangfu, born in 1981, Ph. D., associate professor. His research interests include Web database query, spatial data analysis.

ZHANGXiaoyan, born in 1983, Ph. D. candidate, engineer. Her research interests include spatial data query, city calculation.

TANGYanhuan, born in 1992, M. S. candidate. His research interests include spatial data mining, recommender system.

TANGXiaoliang, born in 1980, Ph. D., lecturer. His research interest include machine learning.

LIANGHaibo, born in 1995. His research interest include data mining, database query.