陳 偉，劉 佳，劉 琳

(1.中國(guó)環(huán)境管理干部學(xué)院，河北 秦皇島 066004；2.秦皇島職業(yè)技術(shù)學(xué)院，河北 秦皇島 066004)

基于“興趣集群”的空間網(wǎng)絡(luò)最優(yōu)位置的選擇與查詢研究

陳 偉1，劉 佳1，劉 琳2

(1.中國(guó)環(huán)境管理干部學(xué)院，河北 秦皇島 066004；2.秦皇島職業(yè)技術(shù)學(xué)院，河北 秦皇島 066004)

針對(duì)空間網(wǎng)絡(luò)的查詢選擇單一性和忽略了群集效應(yīng)的缺陷，本文提出基于興趣集群的最優(yōu)位置查詢方法，給出了該方法的實(shí)施策略，通過(guò)選取合理“興趣集”，研究“興趣集群”的查詢，使得最終查詢結(jié)果滿足集合內(nèi)部的興趣點(diǎn)是高密度、集合與集合之間低耦合，降低數(shù)據(jù)重復(fù)率，從而保證查詢結(jié)果的有效性，提高用戶的滿意度和資源的合理調(diào)配。

空間網(wǎng)絡(luò)；興趣集；最優(yōu)位置

The Research on the Choice of the Optimal Location and Query for Spatial Network Based on the "Interest Cluster"

1.問題提出

目前，路網(wǎng)上的研究大多基于距離量算，如：歐氏距離和路網(wǎng)距離。目標(biāo)對(duì)象多數(shù)集中在“點(diǎn)對(duì)象上”，最常見的應(yīng)用主要有兩種：

(1)最近目標(biāo)點(diǎn)的查找，即要查找距離給定位置最近的加油站、救援廠、急救中心等，已有的研究成果是直接計(jì)算最短路徑，查找到最近的一個(gè)。

(2)最佳位置的查找，如某一連鎖店要選擇最佳位置增開店鋪以擴(kuò)大連鎖范圍，已有的研究成果也是通過(guò)最短路徑量算，并結(jié)合對(duì)周邊同類型店鋪的距離的分析來(lái)選擇最佳位置。

這兩種應(yīng)用查找結(jié)果理論上是正確的，但由于忽視了應(yīng)用中除去距離以外的其它影響因素，使得查找結(jié)果不盡人意，主要問題如下：

(1)選擇的單一性：只靠距離測(cè)算，忽略其它影響因素，使結(jié)果失去了有效性。比如，逛街的時(shí)候，確定了最近的商場(chǎng)，可是其他商場(chǎng)可能都很遠(yuǎn)，而逛街往往是需要商場(chǎng)群體，這樣下一個(gè)又要重新規(guī)劃，只有第一個(gè)距離近了，而其綜合距離卻不一定近。

(2)忽視了群集效應(yīng)：物以類聚，人以群分，任何同類事物的聚集都能產(chǎn)生單個(gè)點(diǎn)所不能創(chuàng)造的價(jià)值，這也給“選址分析”提供了一個(gè)重要的依據(jù)。例如：建新商場(chǎng)，如果是單獨(dú)的一個(gè)地方，周邊不是商業(yè)區(qū)，那么效益可想而知，因?yàn)椴环先藗兿M(fèi)的習(xí)慣。

所以，本文以上述問題為出發(fā)點(diǎn)，提出“興趣集群”的選擇，根據(jù)查詢條件，查找符合條件的“興趣集”，進(jìn)而組成集群，由用戶根據(jù)需要自行選擇一個(gè)“興趣集”做起點(diǎn)，進(jìn)一步訪問“興趣集群”。這種方式不僅能夠解決目前路網(wǎng)查詢的單一性，還具有以下兩方面意義：

(1)將“點(diǎn)查詢”與“面查詢”聯(lián)系到一起，為交通、資源等方面的規(guī)劃、分析及綜合價(jià)值計(jì)算等實(shí)際應(yīng)用提供理論依據(jù)。

(2)對(duì)查詢結(jié)果進(jìn)行了合理性優(yōu)化，使其在一些應(yīng)用(如：大型商場(chǎng)、娛樂、餐飲等行業(yè))中可以得到合理有效的查詢結(jié)果，以提高應(yīng)用價(jià)值。

2.國(guó)內(nèi)外研究現(xiàn)狀

目前，國(guó)內(nèi)外關(guān)于路網(wǎng)信息檢索及其應(yīng)用主要有最近鄰查詢、最優(yōu)位置查詢、軌跡相似性查詢等。

(1)最近鄰查詢：最近鄰(Nearest Neighbors，NN)查詢是計(jì)算數(shù)學(xué)中的一個(gè)傳統(tǒng)問題，根據(jù)實(shí)際需要，通常查找一個(gè)或多個(gè)最近的目標(biāo)點(diǎn)，以下簡(jiǎn)稱(K-NearestNeighbor查詢)KNN，它是典型的相似性查詢方式。KNN查詢方法最經(jīng)典的算法是Dijktra算法，大多數(shù)的研究均是以Dijktra算法為基礎(chǔ)，在其上優(yōu)化和改進(jìn)，但是當(dāng)路網(wǎng)的數(shù)據(jù)量巨大時(shí)會(huì)造成查詢和存儲(chǔ)的代價(jià)很高以致方法不可用。

(2)最優(yōu)位置查詢：最優(yōu)位置亦稱最佳位置(Optimal Locations，OL)查詢，是對(duì)空間信息資源的合理規(guī)劃，在地理信息系統(tǒng)、城市規(guī)劃和資源分配等領(lǐng)域均得到廣泛的應(yīng)用，該應(yīng)用已經(jīng)從歐式空間過(guò)渡到路網(wǎng)中，通過(guò)計(jì)算綜合評(píng)價(jià)值，查找最優(yōu)位置。OL查詢通常會(huì)假設(shè)查詢目標(biāo)存在Lp空間中，未考慮空間位置之間的活動(dòng)常受其實(shí)際路網(wǎng)情況的約束，若仍取兩個(gè)位置點(diǎn)之間的距離是Lp空間距離，會(huì)使查詢結(jié)果降低相應(yīng)的實(shí)用價(jià)值。

(3)軌跡相似性查詢：軌跡相似性查詢是道路網(wǎng)絡(luò)中移動(dòng)對(duì)象數(shù)據(jù)管理的研究熱點(diǎn)，它根據(jù)收集到的移動(dòng)對(duì)象數(shù)據(jù)，分析移動(dòng)對(duì)象的運(yùn)動(dòng)規(guī)律、檢測(cè)異常對(duì)象。例如：它可以預(yù)測(cè)犯罪分子的逃匿軌跡，然后派遣附近警力支援。

軌跡相似性查詢，也是軌跡數(shù)據(jù)應(yīng)用場(chǎng)景中(包括拼車出行服務(wù)、行程分享與推薦服務(wù)等)的關(guān)鍵性技術(shù)。在實(shí)際應(yīng)用中，可以根據(jù)軌跡的相似程度作出相應(yīng)的決策及推薦。例如：拼車、推薦可能喜歡去的地方等。

由上述分析可知，當(dāng)前的路網(wǎng)信息查詢無(wú)論是基于歐式距離還是路徑距離，求得最短路徑或多個(gè)近鄰，均集中在研究“點(diǎn)對(duì)象”中，無(wú)論是靜止的，或者是移動(dòng)的。但隨著路網(wǎng)信息的增加、應(yīng)用的不斷深入，人們獲取的信息中，一部分是需要針對(duì)“面對(duì)象”的，要從“面對(duì)象”中選擇符合條件的“點(diǎn)對(duì)象”，所以查詢結(jié)果除了滿足距離最短以外，還要考慮信息應(yīng)用價(jià)值和意義。

3.基于“興趣集群”的查詢方法研究

3.1 查詢策略

本文主要討論目前路網(wǎng)應(yīng)用中的一種特殊情況，即“集群處理”。當(dāng)某個(gè)查詢要得到的結(jié)果是一個(gè)“面”的時(shí)候，這種“集群處理”的有效性和準(zhǔn)確性，將直接影響是否能給用戶返回的是一系列的由“點(diǎn)到面”的有效結(jié)果。查詢方法完全可以借鑒“點(diǎn)對(duì)象”查詢的處理，只是需要進(jìn)行多個(gè)“點(diǎn)對(duì)象”的分組、融合，形成面、群。其查詢步驟如下：

(1)評(píng)價(jià)選擇的目標(biāo)點(diǎn)

所謂目標(biāo)點(diǎn)就是符合查詢條件的結(jié)果，單個(gè)結(jié)果稱之為“點(diǎn)對(duì)象”，多個(gè)結(jié)果組成的結(jié)果集稱之為“面對(duì)象”。根據(jù)查詢條件查出多個(gè)“點(diǎn)對(duì)象”組成的目標(biāo)集合，分析相似性，根據(jù)相似性指標(biāo)的大小進(jìn)行分組、融合。

(2)確定相似性指標(biāo)

對(duì)于選定的“點(diǎn)對(duì)象”組合，根據(jù)路網(wǎng)數(shù)據(jù)查詢?cè)?，分析其屬性?shù)據(jù)，將屬性數(shù)據(jù)進(jìn)行查詢組合，組成相似性條件，確定滿足條件的點(diǎn)，重新生成新的“面對(duì)象”。

(3)建立排序機(jī)制

即便是多個(gè)離散的點(diǎn)組成的區(qū)域，由于各個(gè)離散點(diǎn)的屬性數(shù)據(jù)不同，所以需要對(duì)其進(jìn)行分析并排序，進(jìn)而能夠規(guī)劃出區(qū)域內(nèi)部以及區(qū)域之間的最優(yōu)路徑。

(4)確定“面對(duì)象”中的“點(diǎn)集”之間的關(guān)系、“面對(duì)象”間的關(guān)聯(lián)關(guān)系

由于“面對(duì)象”是由“點(diǎn)對(duì)象”組成的，所以“面對(duì)象”中的關(guān)系就是“點(diǎn)”與“點(diǎn)”之間的關(guān)系，根據(jù)他們的關(guān)系，進(jìn)而能規(guī)劃出一條行走最優(yōu)路徑?！懊鎸?duì)象”間的關(guān)系亦如此，只不過(guò)是需要綜合計(jì)算面內(nèi)所有點(diǎn)的信息，再規(guī)劃面—面之間的路徑。

(5)建立索引結(jié)構(gòu)

對(duì)于大數(shù)據(jù)的查詢，沒有索引幾乎是完不成的。所以，根據(jù)實(shí)際應(yīng)用領(lǐng)域數(shù)據(jù)的特點(diǎn)，建立索引，以便加快查詢速度，提高查詢效率。

3.2 查詢合理性保證

為了實(shí)現(xiàn)查詢的合理性，查詢條件由傳統(tǒng)單一選項(xiàng)增加到復(fù)合選項(xiàng)，用戶可以根據(jù)選擇增加，或不增加。條件精確度越高，查詢結(jié)果越理想。本文提出“點(diǎn)查詢—面查詢—區(qū)域查詢”，具體可分為兩步執(zhí)行：

(1)確定目標(biāo)點(diǎn)的屬性數(shù)據(jù)集，選擇核心查詢條件，確定查詢符合條件的“點(diǎn)對(duì)象”。

(2)以某一個(gè)“點(diǎn)對(duì)象”為中心，按照一定的規(guī)則向外延伸，再查詢條件范圍內(nèi)，圈住符合條件的所有“點(diǎn)對(duì)象”，組合成新的“面對(duì)象”，即“區(qū)域”。

(3)區(qū)域可以是一個(gè)，也可以是多個(gè)，要根據(jù)具體“點(diǎn)集”的位置來(lái)定，而區(qū)域內(nèi)及區(qū)域間均可以根據(jù)條件形成最優(yōu)路徑。

(4)建立查詢模型。

3.3 結(jié)果集的處理與評(píng)價(jià)

結(jié)果集的大小由查詢條件、查詢目標(biāo)等多種因素決定，無(wú)論其大、小，均需要對(duì)其生成的集合進(jìn)行處理與評(píng)價(jià)，以確保返回給用戶最有效的結(jié)果。

(1)根據(jù)用戶查詢的具體應(yīng)用背景，賦予KNN和OL不同的比重，取值在0～1之間，兩個(gè)比重和等于1。

(2)將查詢點(diǎn)及目標(biāo)點(diǎn)獲取的指標(biāo)數(shù)據(jù)，按照其賦予的權(quán)值進(jìn)行整合，設(shè)定計(jì)算公式，再根據(jù)KNN和OL不同的比重值進(jìn)行組合計(jì)算。

4.結(jié)論

本文提出的基于興趣集群的最優(yōu)位置查詢策略，從用戶的實(shí)際應(yīng)用出發(fā)，對(duì)興趣點(diǎn)進(jìn)行了分析和綜合，由“點(diǎn)對(duì)象”擴(kuò)展到“面對(duì)象”，使原來(lái)單一的查詢結(jié)果更加貼近實(shí)際需求?？紤]了“興趣集群”的最佳位置及路徑查詢使空間網(wǎng)絡(luò)上的查詢變得更加合理化、智能化、個(gè)性化和人性化，提高了用戶的滿意度，使得資源的調(diào)配更加合理。

[1]Deng, K., Zhou, X., Shen, H.T., Sadiq, S., Li, X.: Instance optimal query processing in spatial networks 18(3), 675-693 (2009)

[2]Papadias, D., Zhang, J., Mamoulis, N., Tao, Y.: Query processing in spatial network databases. In: Proc. of Very Large Data Bases,(VLDB), pp. 802-813 (2003)

[3]Gu Y, Guo N, Yu G. Uncertain moving range query techniques in road networks[J]. Ruan Jian Xue Bao/ Journal of Software, 2013,24(6):1243 1262.

[4]李艷紅，黃群，蔣宏，李國(guó)徽.路網(wǎng)中空間關(guān)鍵字連續(xù)范圍查詢算法研究，計(jì)算機(jī)科學(xué)，2014，41(7)

CHEN Wei1，LIU Jia1，LIU Lin2

(1. Environmental Management College of China, Qinhuangdao 066004, China;2. Qinhuangdao Institute of Technology, Qinhuangdao 066004, China)

Aiming at the monotony and the defects of cluster effect of spatial network query, an optimal location query method based on interest cluster is proposed in this paper, and then the implementation strategy is also given. By choosing reasonable interest cluster, the query of interest cluster is studied. Therefore, the final query result can meet the conditions that the point of interest in cluster is high-density, but the clusters are low coupling. Thus, the repetition rate of data is decreased, and validity of query result is guaranteed. So the user satisfaction is increased, and resources are allocated reasonably.

spatial network; interest cluster; optimal position

2015-10-08

河北省教育廳青年基金項(xiàng)目(基于空間網(wǎng)絡(luò)的“興趣集群”的最優(yōu)選擇查詢研究，QN2015133)。

河北省教育廳青年基金項(xiàng)目(基于“路網(wǎng)數(shù)據(jù)庫(kù)”的最佳位置及路徑選擇研究，QN20141059)。

陳偉(1980-)，女，在讀博士，中國(guó)環(huán)境管理干部學(xué)院信息工程系副教授，研究方向：數(shù)據(jù)庫(kù)查詢技術(shù)。

TP333

A

1671-3974(2016)01-0052-03