基于拓?fù)潢P(guān)系的gml空間面對(duì)象聚類算法分析

《基于拓?fù)潢P(guān)系的gml空間面對(duì)象聚類算法分析》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第1章緒論面對(duì)象進(jìn)行分析成了一個(gè)需要研究與解決的問題。目前空間聚類算法主要存在以下兩個(gè)問題：一方面，空間聚類主要針對(duì)關(guān)系數(shù)據(jù)，隨著Intemet的廣泛應(yīng)用，GML數(shù)據(jù)越來越多，面I句GML的空間聚類的研究卻很少；另一方面，沒有考慮空間拓?fù)潢P(guān)系的相似性，而空間對(duì)象間的拓?fù)潢P(guān)系是指兩個(gè)空間目標(biāo)在拓?fù)渥儞Q(如放縮、旋轉(zhuǎn))下保持不變的空間關(guān)系，是空間對(duì)象的固有屬性，因此目前對(duì)GML數(shù)據(jù)進(jìn)行空間聚類研究，并考慮空間拓?fù)潢P(guān)系的相似性具有重要意義。本文將在國(guó)家自然科學(xué)基金項(xiàng)目(40871176)的資助下研究下列問題：(1)如何針

2、對(duì)GML存儲(chǔ)的空間數(shù)據(jù)，以面對(duì)象為核心進(jìn)行拓?fù)潢P(guān)系的計(jì)算；(2)如何高效地對(duì)基于拓?fù)潢P(guān)系的GML空間面對(duì)象進(jìn)行聚類，發(fā)現(xiàn)空間面對(duì)象中的分布規(guī)律。1．2研究現(xiàn)狀空間關(guān)系【6】是指地理實(shí)體之間存在的一些具有空間特性的關(guān)系，如拓?fù)潢P(guān)系m、距離關(guān)系【8】、方向關(guān)系【91等，是空間數(shù)據(jù)組織、查詢、分析、推理的基礎(chǔ)?？臻g關(guān)系理論及其研究直接影響著GIS系統(tǒng)的設(shè)計(jì)、開發(fā)和應(yīng)用，受到了國(guó)際GIS及相關(guān)學(xué)術(shù)界的高度重視。而空間分析fl01，在某種程度上正是處理這種空間實(shí)體之間的相互關(guān)系一一空間關(guān)系，美國(guó)UCGIS曾在1998年把空間

3、分析列為GIS界十大重點(diǎn)問題之一，這主要源于它對(duì)現(xiàn)實(shí)的巨大指導(dǎo)作用?？臻g拓?fù)浞治觥緇l】是空間分析的主要內(nèi)容，也是GIS和空間數(shù)據(jù)庫的關(guān)鍵技術(shù)，現(xiàn)實(shí)中的應(yīng)用非常廣泛?？臻g拓?fù)潢P(guān)系的形式化描述是建立在點(diǎn)集拓?fù)淅碚摶A(chǔ)【l2】之上的。這里我們主要針對(duì)面對(duì)象，討論二維空間中的拓?fù)潢P(guān)系，包括點(diǎn)一面、線一面、面一面等。而每一種形式的空間關(guān)系有多種，這里我們只討論包含、相交、相鄰關(guān)系。目前，對(duì)于包含關(guān)系的判斷【13’141，國(guó)內(nèi)外學(xué)者已提出了很多算法，如射線法【15’16】及其改進(jìn)算法【17,18】、夾角和法【191、拓?fù)溆成?/p>

4、法[20,21】、基于鏈碼和特征形的方法【221等。射線法的基本思想是從欲判斷的點(diǎn)向面作一條射線，求出其與面邊界的交點(diǎn)個(gè)數(shù)，從而得出點(diǎn)在面內(nèi)(外)。夾角和法的基本思想是連接判斷點(diǎn)與面的各頂點(diǎn)，計(jì)算其夾角和，其中順時(shí)針方向?yàn)檎?，逆時(shí)針方向?yàn)樨?fù)。若夾角和為2萬，則點(diǎn)在多邊形內(nèi)：若夾角和為0，則點(diǎn)在多邊形外。夾角和法適用于凹、凸多邊形，有孔的多邊形除外。拓?fù)溆成浞▌t只適用于凸多邊形，它將點(diǎn)在凸多邊形內(nèi)外的判斷轉(zhuǎn)化為映射點(diǎn)在射影直線上的位置關(guān)系問題。對(duì)于相交關(guān)系的判斷可以用混合積的方法【23l，也可以使用參數(shù)化向量的方法【

5、24】。對(duì)于相鄰關(guān)系的判斷可以用距離來度量，但是當(dāng)對(duì)面對(duì)象使用距離來度量時(shí)，首先需通過空間近似方法(如2第1章緒論點(diǎn)近似、最小外接矩形近似)，但它們的近似質(zhì)量不高，計(jì)算出的距離總有一定誤差。而判斷點(diǎn)、線、面的包含、相交、相鄰關(guān)系是空間拓?fù)浞治鲋械闹匾M成部分。例如，在GIS空問查詢中，要求列出給定面內(nèi)的所有空間對(duì)象，這時(shí)就必須計(jì)算空問對(duì)象間的包含關(guān)系。因此，研究這一問題的快速算法具有實(shí)際的應(yīng)用價(jià)值?？臻g聚類分析是空間模式識(shí)別和空間數(shù)據(jù)挖掘的重要手段之一。國(guó)內(nèi)外研究者已經(jīng)提出了多種空間聚類算法，例如，DBSCAN算法

6、【25】是一個(gè)基于密度的空間聚類算法，用來發(fā)現(xiàn)帶有噪聲的空問數(shù)據(jù)庫中任意形狀的聚類。該算法的效率較高，但算法執(zhí)行前需輸入閾值參數(shù)，且它僅能對(duì)點(diǎn)進(jìn)行聚類。GDBSCAN算法【26】對(duì)DBSCAN算法進(jìn)行了推廣，它不僅能對(duì)點(diǎn)進(jìn)行聚類，也能對(duì)線或面進(jìn)行聚類?？梢钥闯?，這些空間聚類算法主要針對(duì)歐幾何空間中的數(shù)據(jù)對(duì)象。然而空間對(duì)象不僅具有非空間的屬性特征，而且具有與空間位置、拓?fù)浣Y(jié)構(gòu)相關(guān)的空間特征。文獻(xiàn)127]提出了一種基于密度的空間聚類的一般觀點(diǎn)一一拓?fù)渚垲?，它針?duì)基于密度的空間聚類及其變種引入了拓?fù)涞母拍?，給出了聚類拓?fù)?/p>

7、結(jié)構(gòu)的定義，把簇定義為多種類型的拓?fù)湫完P(guān)聯(lián)集合，但它僅能對(duì)點(diǎn)進(jìn)行聚類，并未涉及線、面等空間對(duì)象。然而，一方面，目前空間聚類分析只針對(duì)關(guān)系數(shù)據(jù)，但在GIS中，通常使用GML來表達(dá)地理信息，而GML是半結(jié)構(gòu)化數(shù)據(jù)，因此，研究GML的空間聚類算法具有理論意義和應(yīng)用價(jià)值。另一方面，目前空間聚類分析方法存在著兩個(gè)偏向，一是從事GIS理論方法和技術(shù)工具研究的工作者大多根據(jù)空間對(duì)象的地理坐標(biāo)進(jìn)行聚類，即只考慮對(duì)象的空間鄰近性，而不考慮對(duì)象的屬性特征的相似性；另一種是從事GIS應(yīng)用和地學(xué)研究的工作者，則直接套用傳統(tǒng)聚類分析方法，根

8、據(jù)屬性特征集進(jìn)行分析，而忽視了對(duì)象的空間鄰近性?？臻g對(duì)象本質(zhì)上具有地理位置和屬性特征雙重含義，二者結(jié)合才能完整地描述空間特征和空間差異。將空間拓?fù)潢P(guān)系和屬性特征納入統(tǒng)一的空間距離測(cè)度和空間聚類分析系統(tǒng)，將會(huì)改善空間分析和空間數(shù)據(jù)挖掘的信息質(zhì)量?？臻g數(shù)據(jù)與傳統(tǒng)數(shù)據(jù)相比，具有自己獨(dú)特的特點(diǎn)。表現(xiàn)在兩個(gè)方面：一是空間數(shù)據(jù)都與某一對(duì)象相關(guān)，空間數(shù)據(jù)中除包含以文字、字