基于語義聚類的查詢分解算法在空間數(shù)據(jù)集成系統(tǒng)中的應(yīng)用

饒祎　盧桂強　霍?！⊥踟S

摘要：通過對空間數(shù)據(jù)集成系統(tǒng)中數(shù)據(jù)查詢基本流程的分析，指出了系統(tǒng)中數(shù)據(jù)源的異構(gòu)性給查詢帶來的問題，并闡述了傳統(tǒng)基于語法層面的查詢分解方法的不足。提出了一種基于語義聚類的查詢分解算法，在語義層面上將用戶的查詢請求分解為子查詢并提交給相應(yīng)的數(shù)據(jù)源，從而提高了系統(tǒng)對數(shù)據(jù)查詢請求的響應(yīng)率和結(jié)果的精確性。

關(guān)鍵詞：空間數(shù)據(jù)集成；查詢分解；語義距離；聚類算法；K-means

中圖分類號：TP311.11 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）21-4963-04

對于大型的空間信息系統(tǒng)而言，其建設(shè)往往不是一蹴而就的，一般都需要很長的時間、地域跨度，這就導(dǎo)致了不同時間、地點建設(shè)的部分產(chǎn)生了一定程度的異構(gòu)性，形成了眾多的“信息孤島”。而空間數(shù)據(jù)集成的主要目的就是屏蔽底層數(shù)據(jù)源的異構(gòu)性，使用戶能夠透明地訪問這些數(shù)據(jù)源[1，2]，即在存儲、表示、管理、通信等方式均不相同的異種數(shù)據(jù)源上，通過資源服務(wù)的方式為用戶提供邏輯上統(tǒng)一的數(shù)據(jù)視圖和信息訪問接口。簡而言之，空間數(shù)據(jù)集成系統(tǒng)就是架設(shè)在用戶與眾多數(shù)據(jù)源之間紐帶，而評判一個空間數(shù)據(jù)集成系統(tǒng)是否優(yōu)秀的一個重要方面，就是看這個它能否為用戶提供精確、快速的數(shù)據(jù)查詢服務(wù)，這往往是用戶最關(guān)心的事情。

空間數(shù)據(jù)集成系統(tǒng)中通常集成了多種分布的異構(gòu)數(shù)據(jù)源，它們之間沒有統(tǒng)一的模式結(jié)構(gòu)，對于相同概念的表述往往不盡相同，這給數(shù)據(jù)查詢帶來了很大的困難。用戶提交的數(shù)據(jù)查詢請求，通常包含多個概念且沒有統(tǒng)一的規(guī)范，如果不經(jīng)預(yù)處理，直接下發(fā)給數(shù)據(jù)源進(jìn)行檢索，會極大地增加通信開銷，并且還會令各數(shù)據(jù)源進(jìn)行大量不相關(guān)的查詢操作，嚴(yán)重影響系統(tǒng)的性能。因此，為空間數(shù)據(jù)集成系統(tǒng)設(shè)計一種準(zhǔn)確高效的查詢分解算法是必要的，其目的是使得分解后生成的子查詢能夠更加貼合不同數(shù)據(jù)源的要求，降低開銷，提高系統(tǒng)對用戶查詢響應(yīng)效率及精確性。

1 關(guān)鍵技術(shù)概述

1.1查詢分解

空間數(shù)據(jù)集成系統(tǒng)的查詢分解流程如圖1所示，用戶通過統(tǒng)一的服務(wù)接口描述自己所需的數(shù)據(jù)并提交查詢，系統(tǒng)解析查詢，將查詢分解為多個子查詢提交給相應(yīng)的數(shù)據(jù)源，之后將這些數(shù)據(jù)源返回的結(jié)果以統(tǒng)一視圖反饋給用戶。

如何對頂層用戶的查詢請求進(jìn)行有效的分解，并使得分解后的子查詢比原來的查詢請求更容易得到滿意的匹配服務(wù)，這是能否為用戶提供精確空間數(shù)據(jù)服務(wù)的關(guān)鍵。傳統(tǒng)的信息查詢技術(shù)主要是基于語法層次的，它能夠在為用戶提供一定程度的數(shù)據(jù)資源發(fā)現(xiàn)功能，但無法對用戶查詢進(jìn)行語義層次的理解，導(dǎo)致了查詢系統(tǒng)經(jīng)?！罢`解”用戶的初衷，用戶提交的查詢請求通常會得到大量與需要無關(guān)的搜索結(jié)果。而對于每一個獨立的空間數(shù)據(jù)源實體來說，它所涉及到的空間數(shù)據(jù)概念往往較為集中，如果查詢請求分解后的子查詢中包含的概念范圍是發(fā)散的，則分解后仍然無法得到滿意的匹配結(jié)果。

為解決以上問題，該文采用基于語義聚類的查詢分解方法對用戶的查詢請求進(jìn)行預(yù)處理，在語義層面上將其分解為概念范圍相對集中的子查詢，以提高子查詢的匹配成功率。

1.2語義距離

為了將人們在Web上使用的文本信息轉(zhuǎn)化為計算機系統(tǒng)能夠理解的描述，萬維網(wǎng)之父英國人TimBerners Lee提出了語義Web這一概念[3]，目的是通過將Web內(nèi)容的語法結(jié)構(gòu)和語義以知識表示形式呈現(xiàn)出來，以實現(xiàn)與其它信息源共享知識，使得人與人、人與機器以及機器與機器之間能夠準(zhǔn)確地互相理解。

基于語義Web思想，可以通過構(gòu)建空間數(shù)據(jù)集成系統(tǒng)統(tǒng)一的知識體系，對系統(tǒng)中不同的數(shù)據(jù)源上的信息進(jìn)行語義標(biāo)記，將模糊、有異義的關(guān)鍵詞抽象、提煉為精確、無異義的概念。判斷用戶需求與數(shù)據(jù)源的相關(guān)程度，其實就是看查詢請求表述的概念與數(shù)據(jù)源表述的概念之間語義距離的大小。

語義距離是指在不同概念間存在的繼承關(guān)系或二元關(guān)系鏈中最短的關(guān)系鏈長度的一種度量，通過對概念之間相似程度的計算，可以量化概念之間的語義距離。

概念間的語義相似度計算公式[4]為：

1.3聚類分析

聚類分析是知識發(fā)現(xiàn)（Knowledge Discovery in Database， KDD）中的一項重要研究內(nèi)容，旨在將數(shù)據(jù)集合劃分為若干類的過程，使得類內(nèi)差異小，類間差異大[5]。在這個過程中沒有任何關(guān)于數(shù)據(jù)集分類的先驗知識，沒有任何指導(dǎo)，僅僅依靠事務(wù)之間的相似性作為類屬劃分的準(zhǔn)則。聚類準(zhǔn)則是度量分類對象之間的接近與相似程度從而判斷樣本是否歸為一類的分類數(shù)據(jù)指標(biāo)，通常的聚類準(zhǔn)則可分為三個：基于距離的、基于密度的以及基于聯(lián)接的。聚類的方法主要可以分為基于劃分的方法、基于分層的方法、基于密度的方法和基于網(wǎng)格的方法[6]。

第一種是劃分法（partitioning methods）。給定一個有N個元組或者記錄的數(shù)據(jù)集，分裂法將構(gòu)造K個分組，每個分組將代表一個聚類，K

第二種為層次法（hierarchical methods）。對給定的數(shù)據(jù)集進(jìn)行層次似的分解，直到某種條件滿足為止。具體有可分為“自底向上”和“自頂向下”兩種方案。例如在“自底向下”方案中，初始時每一個數(shù)據(jù)記錄都組成一個單獨的組，在接下來的迭代中，它把那些相互鄰近的組合并成一個組，直到所有的記錄組成一個分組或者某個條件滿足為止。代表算法有：BIRCH算法、CURE算法、CHAMELEON算法等。

第三種是基于密度的方法（density-based methods）。它不是基于各種各樣的距離的，而是基于密度的，只要一個區(qū)域中的點的密度大于某個閥值，就把它加到與之相近的聚類中去。代表算法有：DBSCAN算法、OPTICS算法、DENCLUE算法等。

第四種為基于網(wǎng)格的方法（grid-based methods）。先將數(shù)據(jù)對象空間劃分成為有限個單元（cell）的網(wǎng)格結(jié)構(gòu)，所有的處理都是以單個的單元為對象的。代表算法有：STING算法、CLIQUE算法、WAVE-CLUSTER算法。

2 基于語義距離的K-means聚類查詢分解算法

通過對主要的聚類算法進(jìn)行比較，由于K-means聚類法具有運算量小、能用于處理龐大樣本數(shù)據(jù)的明顯優(yōu)勢，該文采用K-means聚類法作為數(shù)據(jù)查詢請求分解的基礎(chǔ)。

2.1算法基本思想

K-means算法[7-8]的核心思想是：給定簇的個數(shù)K，將n個對象分到K個簇中去，使得類內(nèi)對象之間的相似性最大，而類之間的相似性最小。其使用隨機方式選擇K個元素作為初始的聚類中心，按照算法的迭代執(zhí)行，整個算法的結(jié)束條件是簇的中心（或凝聚點）不再改變。K-means的計算復(fù)雜性是O（nKt），其中，n為元素數(shù)量，K為簇的數(shù)量，t為迭代次數(shù)。

2.1.1聚類準(zhǔn)則函數(shù)

2.1.2聚類中心的選擇方法

算法的每次迭代需要確定新的聚類中心，由于查詢請求的聚類結(jié)果是概念的集合，選擇聚類中心也就是選擇最能夠代表這個類中的語義含義的子概念。本算法中采用了基于最小距離和的中心選擇方法，即如果某一子概念到類內(nèi)其它概念的距離和最小，就將其設(shè)定為新的聚類中心：

2.1.3算法工作原理

算法首先隨機從請求概念集中選取K個點作為初始聚類中心，然后計算各子概念到聚類中心的距離，將其歸到離它最近的那個聚類中心所在的類。計算新形成的類的聚類中心，如果相鄰兩次迭代的聚類中心沒有任何變化，說明分解調(diào)整結(jié)束，聚類準(zhǔn)則函數(shù)GC已經(jīng)收斂。

2.2 算法描述

3 性能分析與結(jié)論

在實驗環(huán)境中，我們對基于語義聚類的查詢分解算法進(jìn)行了仿真測試，對含有不同空間屬性概念個數(shù)的查詢訪問進(jìn)行了模擬，以此來分析算法在數(shù)據(jù)查詢請求復(fù)雜度不同的情況下的表現(xiàn)。圖2顯示了算法在各種請求復(fù)雜度情況下的響應(yīng)率，可見使用傳統(tǒng)查詢算法的情況下系統(tǒng)響應(yīng)率隨著數(shù)據(jù)查詢請求復(fù)雜度的提高急劇下降，而采用了語義聚類查詢分解算法的曲線則較為平緩。

實驗結(jié)果證明基于語義聚類的查詢分解算法可以有效地提高系統(tǒng)對用戶數(shù)據(jù)查詢請求的響應(yīng)率，從而提高了空間數(shù)據(jù)集成系統(tǒng)的總體性能。

參考文獻(xiàn)：

[1] Maurizio L. Data Integration： a Theoretical Perspective[J].The ACM SIGACT-SIGMOD -SIGART Symposium on Principles of Database Systems， 2002.

[2] 李曉軍，丘健妮，彭龍軍，等.多源空間數(shù)據(jù)集成技術(shù)狀況與應(yīng)用前景研究[J].計算機與現(xiàn)代化，2006（5）.

[3] Bermers-Lee T，Hendler J，Lassila O. The semantic web[J].Scientific American，2001，284（5）：34-43.

[4] 王家琴，李仁發(fā)，李仲生.一種基于本體的概念語義相似度方法的研究[EB/OL].http：//www.paper.edu.cn.

[5] Han J W，Kambr M.Data mining concepts and techniques[M]. Beijing： Higher Education Press，2001：145-176.

[6] 張敏.基于劃分的模糊聚類算法[J].軟件學(xué)報，2004（6）.

[7] Olivia P. 數(shù)據(jù)挖掘?qū)嵺`[M].北京：機械工業(yè)出版社，2003.

[8] 周愛武，于亞飛. K-means聚類算法的研究[J].計算機技術(shù)與發(fā)展，2011，21（2）.