歡迎登錄中國視覺網!
學術論文頻道
ACADEMIC PAPERS
位置導航:首頁 >> 學術論文 >> 專業論文 >> 基于SVG的空間關聯規則挖掘

基于SVG的空間關聯規則挖掘

發布時間:2019-07-31     來源:中國視覺網       訪問次數:2372


   摘  要: 網絡技術的飛速發展使得SVG成為矢量圖形發布的新標準,SVG文檔中隱藏著大量有趣的空間信息。本文綜合利用空間信息和非空間信息,采用多維多層交叉關聯規則挖掘技術,從SVG文檔中挖掘隱藏的空間關聯規則。
   關鍵詞: SVG文檔;矢量圖形;空間數據挖掘;空間關聯規則挖掘

Abstract: With the population and application of the computer network, SVG has been the new publishing standard for vector graphic. There are large interest spatial information hidden in SVG document. In this paper, We apply cross multilevel association rule discovery technique  to  find spatial association rules from a combination of spatial and non-spatial  information of SVG document.
Keywords: SVG document; Vector graphic; Spatial data mining; Spatial association rule data mining

1   引  言
1.1    SVG文檔
   Internet的迅速發展,圖形圖像信息也需要通過網絡實現共享。目前瀏覽器顯示的大都是柵格形式的圖像,柵格文件具有很多限制性,這些問題矢量圖形可以很好的解決。W3C推出的SVG(Scalable Vector Graphics,可伸縮矢量圖形),是一種基于XML的圖形標準,因它具有純文本、開放、動態、可縮放和平臺無關等特性,成為進行空間矢量數據發布的生力軍。
   SVG基于XML來描述2維矢量圖形,對于基本圖形元素和非幾何特征都可以很好的表達。每一個SVG文檔含有一個根元素需表達的整個內容處于根元素之間,空間對象以圖層組織。圖層Layer可采用表示,屬于同一圖層的幾何元素可以是任何基本幾何元素及其組合,包含于同一組之間。點集、線集、面集、復雜幾何體類等也可采用表示, 元素的ID用于標識不同類型?;鏡耐夾臥兀旱鉖oint、線LineString、面Polygon,可采用、等表達。
   幾何圖形的非幾何特征表達在SVG中一般采用兩種方式:內嵌法和外聯法。內嵌法一般是作為元素(如circle、path等元素)的屬性進行表達[1]。外聯法是指非幾何特征數據存儲在服務器的數據庫中,并且通過ID與SVG文檔中的相關地物進行連接。
   SVG文檔的結構可以認為是樹狀結構,圖1是簡單的SVG文檔,文檔包含了兩個圖層,分別是行政區域圖層和水庫分布圖層。
1.2   空間拓撲關系
   幾何對象間的空間關系通常為三類:空間拓撲

    關系、度量空間關系和順序空間關系??占渫仄斯叵刀雜誑占涫萃誥蚍淺V匾?。通過空間關系進行歸納和分類,得出了5種基本空間拓撲關系[2]:相離關系(Disjoint)、相接關系(Touch)、相交關系(Cross)、包含于關系(Within)、部分覆蓋關系(Overlap)。這些空間拓撲關系之間具有層次性,圖2是空間拓撲關系層次圖。圖中非相離關系是相離關系的補集。相鄰關系是相離關系的子集,如果兩個空間對象相離,并且兩者距離小于給定值,那么它們間的拓撲關系是相鄰。因為在實際應用中,只有兩個相離幾何對象間距離在一定范圍內,才具有實際討論意義。


小支持度閾值和最小置信度閾值的規則成為強規則。
   一直以來關聯規則挖掘都是數據挖掘研究熱點,它與空間領域結合產生了空間關聯規則挖掘。目前空間關聯規則挖掘研究主要是針對柵格圖像[3,4,5],在矢量數據上進行挖掘也有一定的研究 [6]。但基于結構化的SVG文檔進行空間關聯規則挖掘還很少研究,本文探討如何基于SVG文檔進行空間關聯規則挖掘。
2  空間關聯規則挖掘
2.1   據預處理
   SVG是結構化文檔,元素中存在層次性??占潿韻蠹淶耐仄斯叵稻哂脅憒渦?。非空間屬性也可以定義其概念層次結構,因而適合在SVG文檔上進行多維多層關聯規則挖掘。但是SVG文檔并不是為了空間挖掘而建立的,不能直接用于多維多層關聯規則挖掘,需要將其轉換成適合挖掘的形式。數據預處理中的基本思路是從SVG文檔中選取挖掘任務所需幾何對象,根據其空間、非空間信息,構造事務數據庫。
   拓撲關系是挖掘所需主要空間信息,但SVG文檔中通常沒有顯示地記錄幾何對象間的拓撲關系,需要調用相應的空間分析算子進行空間分析,構造空間拓撲關系表[7],如表1所示。構造規則:Itdbmax={(01,02,T)|01,02∈SDoc,01distance=dist02∧dist≦max∧01T02}。SDoc是SVG文檔,max、distance均為數值數據,T為拓撲關系。

   許多挖掘任務,不僅僅在空間信息上挖掘,還需要與非空間信息相結合。根據不同挖掘任務,從SVG文檔中提取空間對象的非空間特征,在空間拓撲關系表中提取對象間的拓撲關系,構造關系表,如表2所示。

   進行多維多層數據挖掘前,數據還需要先轉換成單維單層結構。根據SVG文檔結構、拓撲層次結構、非空間特征概念層次結構對關系表中所有項編碼。每個項所對應編碼第1位用于區分項的類型。取值1表示是空間對象,2表示是拓撲關系,3表示是非空間屬性。編碼其他位取值由其所對應層次結構決定??占潿韻蟮謀嗦肟山柚鶧OM(Document Object Model)操作,采用深度遍歷來實現。算法如下:
輸入:SVG文檔,路徑P為空字符串
輸出:空間對象編碼
步驟:
1.調用GetSVGDocument()函數,得到SVG DOM文檔對象。
2.調用GetElementByid()函數,得到結點L。判斷結點L:
(1)如果 L是葉節點,訪問標志改為True,輸出,返回父節點。
(2)如果結點L是非葉節點:
A.如果L的訪問標志為False,輸出,記錄訪問標志改為Ture,字符1作為尾字符加入路徑P,訪問L的第一個子結點;
B.如果L的訪問標志為True,L有未訪問子結點,路徑P的最后字符值加1,訪問L的下一個子結點;
C.如果L的訪問標志為True,L所有子結點已被訪問,去掉P的最后一個字符,更改后的P的最后一個字符值加1,返回父結點。
3.依次循環,直到SVG文檔所有對象被訪問。
拓撲關系和非空間屬性編碼相對簡單,根據預先定義的層次結構就可以得到相應編碼(如圖3、4所示)。圖3是拓撲關系編碼圖,拓撲關系所對應的編碼是從根結點到本結點路徑上所有編碼的組合,例如相接關系的編碼為”211”,相鄰關系編碼為”22”。圖4是非空間屬性人口、收入概念層次結構編碼圖。表3是表2運用上述編碼規則后形成的編碼表。


2.2   空間關聯規則生成
算法如下所示:
輸入:編碼表Ctab、最大層次數Max_l、各層最小支持度Minsup[Max_l]、最小置信度Mincon[Max_l]。
輸出:強關聯規則。
步驟:
1.掃描編碼表Ctab,計算1層頻繁1項目集到Max_l層頻繁1項目集。
2.循環調用如下過程產生L層頻繁2項目集到L層頻繁k項目集:
(1)由頻繁L層(k-1)項目集產生L層候選k項目集。
(2)循環計算L層候選k項目集中各項目的支持度,得到L層頻繁k項目集。
3.根據最小置信度,得到對應的強關聯規則,檢查冗余,剔除冗余規則。
算法具體分析如下:
   步驟1:頻繁1項集生成中不同層賦予不同的最小支持度,較低層使用遞減的最小支持度,避免丟掉出現在較低抽象層中有意義的關聯規則。
步驟2: L層k項目候選集Ck生成,需要L層(k-1)項目集進行自身連接生成L層K項目候選集,還要使用1層1項目集、2層1項目集…、L-1層1項目集與L層(k-1)項目集連接生成L層K項目候選集。
步驟3:各層規定不同的最小置信度,由各層得到的頻繁項生成強關聯規則。由于項之間的“祖先”關系,如果規則的祖先,它的支持度和置信度都接近于“期望”值,那這個規則是冗余的。應該剔除[8]。
3  應用分析
3.1  區域環境分析
   當前社會經濟、人口迅速發展,生態環境越來越受到關注。圖5是某區域的SVG矢量圖,圖中包括行政區域、長年河、水庫、林地、草地等圖層。通過挖掘空間關聯規則,可幫助分析此區域的環境特征。例如:分析此區域城市與水域、植被等分布的關系,可運用上述空間挖掘思路進行空間挖掘。由于此挖掘任務未涉及非空間屬性,只需選取此區域中幾何對象城市、水域、森林、草地以及其拓撲

關系。城市、水域、植被等圖層處于SVG文檔層次關系第二層,拓撲層次關系總共分為三層。這里列出由第二、三層挖掘后的部分頻繁模式。第二層最小支持度56%,置信度第三層最小支持度40%:
is_a(A, town),is_a(B,river), not_disjoint(A,B),
is_a(C,forest), not_disjoint(A,C),is_a(D,grass),ot_disjoint(A,D),close_to(A,E),cross(A,B),within(A,C),within (A,D)
根據置信度,可以得到強關聯規則。如
is_a(A, town)?is_a(B,river)? cross(A,B)等。
   以上信息表明在此區域城市大都有分布有水源、各種植被。但是還不能提供進一步詳細信息,如城市水源是否充足,植被覆蓋是否茂盛等。因而在之前空間信息基礎上,加入非空間屬性:城市面積、人均水量、人均草地面積、人均森林面積等,并且建立非空間屬性層次圖進一步進行挖掘,得到一組強關聯規則。如規則:is_a(A, town)?is_a(C,grass)? cross(A,C) ?ave_river(Low),表明大多數城市都覆蓋有草地,人均草地占有量低。
3.2 區域環境分析
   目前各個地區都處于發展當中,影響區域發展的因素很多,這些因素與發展的相關性通常都是隱性的,需要通過相關數據進行分析。如圖6是某區域的SVG矢量圖,圖中有城市邊界、公路兩個圖層,以及土地利用等屬性數據。

   在圖6數據基礎上分析城市的公路分布與土地各項利用變化之間的關系,進行空間挖掘。預處理中利用文中所述方法得到地區城市與道路拓撲關系編碼表,此表中包含非空間屬性,分別是公路分布密度、耕地、城鄉工礦居民用地和未利用地的使用變化,其中公路分布密度利用地區城市與道路拓撲關系可求得。圖7可視化的顯示了各區域的公路分布和土地利用變化,各個區域根據公路分布密度的不同賦予了不同顏色,顏色的設置規則如圖8,其中n表示公路密度。對于土地利用的變化采用柱狀圖表示,柱狀圖中長方形顏色不同表示的變化也不同,具體見圖9。



   最后設置最小支持度、置信度進行空間關聯規則的生成,得到一組強關聯規則,這些規則所顯示的信息可作為區域的發展策略的參考依據,幫助區域達到更好的和諧發展。


4  總   結

   本文探討了如何在SVG文檔上挖掘空間關聯規則。為了得到有趣信息,綜合利用空間信息和非空間信息,基于挖掘任務進行多維多層交叉挖掘,并且應用于實際分析,擴展了SVG的研究與應用。
   但是由于基于SVG文檔的挖掘還處于起步階段,所做工作存在很多不足,如關聯規則挖掘中沒有考慮增量挖掘的情況;對于各層最小支持度和置信度依賴于經驗進行手工設置;冗余規則的檢測原則過于簡單,沒有考慮實際應用情況。這些問題都有待于進一步解決。

參 考 文 獻

[1] 徐云和等.基于SVG的空間數據的可視化[J] .計算機應用研究,2005,2:46-48.
[2] 鄔倫等.地理信息系統-原理、方法和應用[M] .北京:科學出版社,2001:65-66.
[3] Thanapat Kangkachit, Kitsana Waiyamai. A business-oriented spatial association rule mining system prototype(Bosarm)[J]. Information and Computer Engineering Postgraduate Workshop , 2002.
[4] Donato Maleba, Francesca A.lisi. An ILP method for spatial association rule mining[J].Working notes of the First Workshop on Multi-Relational Data Mining, 2001:18-29
[5] W.Sabhananda, K.Waiyamai. Data Mining: A Novel Approach for Multi-level association Rules Mining in Large Databases[J]. The Fifth National Computer Science and Engineering Conference, 2001.
[6] 厙向陽,許五弟,薛惠鋒.矢量空間數據庫中關聯規則的挖掘算法研究[J] .計算機應用,2004,24(8):47-49
[7] Ester M., Kriegel H.-P., and Sander J.Spatial Data Mining: A Database Approach[A].in: Proc.5th Int. Symp.on Large Spatial Databases[C], Berlin Germany, 1997:47-66.
[8] Jiawei Han, Micheline Kamber. 數據挖掘-概念與技術[M]. 北京:高等教育出版社, 2005:236-237.



钱流通赚钱 天易棋牌官方网 酷发巴巴游戏 湖北十一选五走势图手机版 辽宁快乐12走势图表 想每天陪妈妈 还能赚钱怎么办 骰宝机有没有赢钱的可能 大嘴棋牌下载地址 真人捕鱼 赚钱收尾货 做代理百世快递赚钱么 捕鱼达人3d凤凰时间 足球赛事分析 海南彩票论坛808长条 广东26选5开奖 幸运飞艇开奖记录彩票控