空間數據挖掘常用方法，以及和普通數據挖掘的不同之處

問題1：空間數據挖掘有哪些常用方法，舉例說明一種方法的原理及應用.

答：空間數據挖掘的常用方法有：統計法，聚類方法，關聯規則發掘方法，Rough集方法，神經網絡方法，云理論，證據理論，模糊集理論，遺傳算法等算法（出自丁信宙，仇環，蘇曉慶. 基于云理論的缺損數據推理和預測 山東理工大學學報 2006年11月）。除此以外還有老師課件上提到的聚類檢測，決策樹方法等。

以下對于一些常見模型做一簡述：

1、空間分析方法 (Spatial Analysis Approach)

利用GIS的各種空間分析模型和空間操作對空間數據庫中的數據進行深加工，從而產生新的信息和知識。目前常用的空間分析方法有綜合屬性數據分析、拓撲分析、緩沖區分析、密度分析、距離分析、疊置分析、網絡分析、地形分析、趨勢面分析、預測分析等，可發現目標在空間上的相連、相鄰和共生等關聯規則，或發現目標之間的最短路徑、最優路徑等輔助決策的知識?？臻g分析方法常作為預處理和特征提取方法與其它數據挖掘方法結合使用。

2、統計分析方法 (Statistical Analysis Approach)

統計方法一直是分析空間數據的常用方法，著重于空間物體和現象的非空間特性的分析。在運用統計方法進行數據挖掘時，一般并不將數據的空間特性作為限制因子加以考慮，空間數據所描述的事物的具體空間位置在這類挖掘中也并不起制約作用。盡管此種挖掘方式與一般的數據挖掘并無本質的差別，但其挖掘后發現的結果都是以地圖形式來描述的，對發現結果的解釋也必然要依托地理空間進行，挖掘的結果揭示和反映的必然是空間規律。但是，統計方法難以處理字符型數據。而且，應用統計方法需要有領域知識和統計知識，一般由具有統計經驗的領域專家來完成。統計方法的最大缺點是要假設空間分布數據具有統計不相關性。這在實際應用中會出現問題，因為很多空間數據是相互關聯的。

3、歸納學習方法 (Induction Learning Approach)

歸納學習方法是從大量的經驗數據中歸納抽取出一般的規則和模式，其大部分算法來源于機器學習領域。歸納學習的算法很多，如Michaski等的AQ11,AQ15，洪家榮等的AE1,AE9，Hunt的CLS, Quinlan的ID3,C5.0等，其中最著名的是Quinlan提出的一種決策樹算法，由ID3算法發展而來，采用嫡來選擇屬性，分類速度快，適合于大數據庫的學習，而C5.0在　ID3的基礎上增加了將決策樹轉換為等價的產生式規則的功能，并解決了連續取值數據的學習問題。Han Jiawei教授等提出了一種面向屬性的歸納方法 (Attribute Oriented Induction, AOI)，專門用于從數據庫中發現知識，通過概念樹的提升對數據進行概括和綜合，歸納出高層次的模式或特征。裴健等對面向屬性的歸納方法進行了擴展，形成了基于空間屬性的歸納方法 (Spatial Attribute Oriented Induction, SAOI)。

4、空間關聯規則挖掘方法 (Spatial Association Rule Mining Approach)

挖掘關聯規則首先由Agrawal等提出，主要是從超級市場銷售事務數據庫中發現顧客購買多種商品時的搭配規律。最著名的關聯規則挖掘算法是Agrawal提出的Apriori算法，其主要思路是統計多種商品在一次購買中共同出現的頻數，然后將出現頻數多的搭配轉換為關聯規則。

5、聚類方法 (Clustering Approach)和分類方法 (Classification Approach)

聚類是按一定的距離或相似性系數將數據分成一系列相互區分的組，根據定義可以把其分為四類：基于層次的聚類方法；分區聚類算法；基于密度的聚類算法；網格的聚類算法。常用的經典聚類方法有K-mean，K-medoids，ISODATA等。

分類就是假定數據庫中的每個對象(在關系數據庫中對象是元組)屬于一個預先給定的類，從而將數據庫中的數據分配到給定的類中，簡單的講就是f:D→L，其中f的域D是屬性數據的空間，L是標號的集合。

分類和聚類都是對目標進行空間劃分，劃分的標準是類內差別最小而類間差別最大。分類和聚類的區別在于分類事先知道類別數和各類的典型特征，而聚類則事先不知道。

6、神經網絡方法 (Neural Network Approach)

神經網絡是由大量神經元通過極其豐富和完善的連接而構成的自適應非線性動態系統，具有分布存儲、聯想記憶、大規模并行處理、自學習、自組織、自適應等功能。神經網絡由輸入層、中間層和輸出層組成。大量神經元集體通過訓練來學習待分析數據中的模式，形成描述復雜非線性系統的非線性函數，適于從環境信息復雜、背景知識模糊、推理規則不明確的非線性空間系統中挖掘分類知識。

7、決策樹方法 (Decision Tree Approach)

決策樹根據不同的特征，以樹型結構表示分類或決策集合，產生規則和發現規律。在空間數據挖掘中，首先利用訓練空間實體集生成測試函數；其次根據不同取值建立樹的分支，在每個分支子集中重復建立下層結點和分支，形成決策樹；然后對決策樹進行剪枝處理，把決策樹轉化為據以對新實體進行分類的規則。

8、粗集理論 (Rough Sets Theory)

粗集理論是波蘭華沙大學Z.Pawlak教授在1982年提出的一種智能數據決策分析工具，被廣泛研究并應用于不精確、不確定、不完全的信息的分類分析和知識獲取。粗集理論為空間數據的屬性分析和知識發現開辟了一條新途徑，可用于空間數據庫屬性表的一致性分析、屬性的重要性、屬性依賴、屬性表簡化、最小決策和分類算法生成等。粗集理論與其它知識發現算法結合可以在空間數據庫中數據不確定的情況下獲取多種知識。

9、模糊集理論 (Fuzzy Sets Theory)

模糊集理論是L.A.Zadeh教授在1965年提出的。它是經典集合理論的擴展，專門處理自然界和人類社會中的模糊現象和問題。利用模糊集合理論，對實際問題進行模糊判斷、模糊決策、模糊模式識別、模糊簇聚分析。系統的復雜性越高，精確能力就越低，模糊性就越強，這是Zadeh總結出的互克性原理。模糊集理論在遙感圖像的模糊分類、GIS模糊查詢、空間數據不確定性表達和處理等方面得到了廣泛應用。

10、空間特征和趨勢探側(Characterization and Trend Detection)方法

這是Ester等人在第4屆KDD國際研討會 (1998)上提出的基于鄰域圖 (neighborhoodgraphs)和鄰域路徑 (neighborhoodpath)概念的挖掘算法。Ester等將一個空間特征定義為空間數據庫中具有空間/非空間性質的目標對象集，并以非空間屬性值出現的相對頻率和不同空間對象出現的相對頻率 (目標對象集相對于整個數據庫)作為感興趣的性質，從空間目標集合經過它的相鄰擴展后的集合中，發現相對頻率的明顯不同，以此提取空間規則：空間趨勢探測挖掘是從一個開始點出發，發現一個或多個非空間性質的變化規律，這種算法的效率在很大程度上取決于其處理相鄰關系的能力。

11、云理論 (Cloudy Theory)

這是李德毅博士提出的用于處理不確定性的一種新理論，包括云模型 (Cloud Model)，虛擬云 (Virtual Cloud)、云運算 (Cloud operation)、云變換 (Cloud Transform)和不確定性推理 (Reasoning under Uncertainty)等主要內容。運用云理論進行空間數據挖掘，可進行概念和知識的表達、定量和定性的轉化、概念的綜合與分解、從數據中生成概念和概念層次結構、不確定性推理和預測等。

12、圖像分析和模式識別 (Image Analysis and Pattern Recognition)方法

空間數據庫 (數據倉庫)中含有大量的圖形圖像數據，一些圖像分析和模式識別方法可直接用于挖掘數據和發現知識，或作為其它挖掘方法的預處理方法。用于圖像分析和模式識別的方法主要有:決策樹方法、神經元網絡方法、數學形態學方法、圖論方法等。

13、證據理論 (Evidence Theory)

由Schafer發展起來的證據理論是經典概率論的擴展。證據理論又稱Dempster-Schafer理論，它是Dempster在20世紀60年代提出，在70年代中期由Schafer進一步發展，形成處理不確定性信息的證據理論，其重要貢獻在于嚴格區分不確定和不知道的界線。證據理論將實體分為確定部分和不確定部分，可以用于基于不確定性的空間數據挖掘。利用證據理論的結合規則、可以根據多個帶有不確定性的屬性進行決策挖掘。證據理論發展了更一般性的概率論，卻不能解決矛盾證據或微弱假設支持等問題。

14、遺傳算法 (Genetic Algorithms)

遺傳算法(簡稱GA)是模擬生物進化過程的算法，最先由美國的John Holland教授于20世紀60年代初提出，其本質是一種求解問題的高效并行全局搜索方法，它能在搜索過程中自動獲取和積累有關搜索空間的知識，并自適應地控制搜索過程以求得最優解。遺傳算法已在優化計算、分類、機器學習等方面發揮了顯著作用。數據挖掘中的許多問題，如分類、聚類、預測等知識的獲取，可以表達或轉換成最優化問題，進而可以用遺傳算法來求解。

15、數據可視化方法 (Data Visualization Approach)

人類的可視化能力，允許人類對大量抽象的數據進行分析。人的創造性不僅取決于人的邏輯思維，而且取決于人的形象思維。人腦的空間認知分析能力目前尚無法全部用計算機代替，因此可視化技術為知識發現提供了有力的幫助。為了了解數據之間的相互關系及發展趨勢，人們可以求助于可視化技術。海量的數據只有通過可視化技術變成圖形或圖像，才能激發人的形象思維—— 從表面上看來是雜亂無章的海量數據中找出其中隱藏的規律。數據可視化技術將大量數據以多種形式表示出來，幫助人們尋找數據中的結構、特征、模式、趨勢、異?，F象或相關關系等。從這個角度講，數據可視化技術不僅僅是一種計算方法，更是看見不可見事物或現象的一種重要手段和方法。

16、地學信息圖譜方法 (Geo-informatics Graphic Methodology)

地學信息圖譜是地球信息的重要表現形式與研究手段，也是地球信息科學的重要組成部分。地學信息圖譜綜合了景觀綜合圖的簡潔性和數學模型的抽象性，是現代空間技術與我國傳統研究成果結合的產物，可反演過去、預測未來。圖是指地圖、圖像、圖解，譜是指不同類別事物特征有規則的序列編排。圖譜是指經過深入分析與高度綜合，反映事物和現象空間結構特征與時空序列變化規律的圖形信息處理與顯示手段。地球信息圖譜是由遙感、地圖數據庫與地理信息系統(或數字地球)的大量地球信息，經過圖形思維與抽象概括，并以計算機多維動態可視化技術顯示地球系統及各要素和現象的宏觀、中觀與微觀的時空變化規律；同時經過中間模型與地學認知的深入分析研究，進行推理、反演與預測，形成對事物和現象更深層次的認識，有可能總結出重要的科學規律。地學信息圖譜不僅應用于數據挖掘，而且服務于科學預測與決策方案。

地學信息圖譜具有以下4個重要功能：①借助圖譜可以反演和模擬時空變化；②可利用圖的形象表達能力，對復雜現象進行簡潔的表達；③多維的空間信息可展示在二維地圖上，從而大大減小了模型模擬的復雜性；④在數學模型的建立過程中，圖譜有助于模型構建者對空間信息及其過程的理解。

地學信息圖譜是形、數、理的有機結合，是試圖從形態來反演空間過程的一種研究復雜系統的方法論。地學信息圖譜中的空間圖形思維、分形分維等方法均可直接用于空間數據挖掘領域。目前，地學信息圖譜的基本理論及其方法體系還不完善，還有待于進一步研究。

17、計算幾何方法 (Computer Geometry Methods)

1975年，Shamos和Hoey利用計算機有效地計算平面點集Voronoi圖，并發表了一篇著名論文，從此計算幾何誕生了。計算幾何中的研究成果已在計算機圖形學、化學、統計分析、模式識別、空間數據庫以及其它許多領域得到了廣泛應用。計算幾何研究的典型問題包括幾何基元、幾何查找和幾何優化等。其中，幾何基元包括凸殼和Voronoi圖、多邊形的三角剖分、劃分問題與相交問題：幾何查找包括點定位、可視化、區域查找等問題；幾何優化包括參數查找和線性規劃。

上述每一種方法都有一定的適用范圍。在實際應用中，為了發現某類知識，常常要綜合運用這些方法?？臻g數據挖掘方法還要與常規的數據庫技術充分結合?？傊?，空間數據挖掘利用的技術越多，得出的結果精確性就越高，因此，多種方法的集成也是空間數據挖掘的一個有前途的發展方向。

以下是對云模型和其在缺損數據的推理預測中的應用做一簡述。

云模型：云是用語言值描述某個定性概念與其數值表示的不確定性轉換的模型。簡單地說，云模型是定性定量間轉換的不確定性模型。該模型用期望Ex，熵En，超熵He三個數值來表示，把模糊性和隨機性完全集成到一起，構成定性和定量間的映射，作為表示的基礎。期望值Ex是概念在論域中的中心值；熵En是定性概念模糊度的度量，反映了在論域中可被這個概念所接受的數值范圍熵越大，概念所接受的數值范圍也越大，概念越模糊。超熵He是熵的不確定性度量，即熵的熵，由熵的隨機性和模糊性共同決定。超熵He反映了云滴的離散程度，超熵越大，離散度越大，隸屬度的隨機性越大。

設U 是一個用精確數值表示的論域（一維的、二維的或多維的），U 上對應著定性概念?，對于論域中的任意一個元素x，都存在一個有穩定傾向的隨機數y=μA(x)，叫作x 對概念? 的確定度，x 在U上的分布稱為云模型，簡稱為云。云由許許多多個云滴組成，一個云滴是定性概念在數量上的一次實現，單個云滴可能無足輕重，在不同的時刻產生的云的細節可能不盡相同，但云的整體形狀反映了定性概念的基本特征。云的“厚度”是不均勻的，腰部最分散，“厚度”最大，而頂部和底部匯聚性好，“厚度”小。云的“厚度”反映了確定度的隨機性的大小，靠近概念中心或遠離概念中心處，確定度的隨機性較小，而離概念中心不近不遠的位置確定度的隨機性大，這與人的主觀感受相一致。

云的數字特征用期望Ex、熵En 和超熵He 來表征，它們反映了定性概念? 整體上的定量特征。

期望Ex：是概念在論域中的中心值，在數域空間最能夠代表定性概念? 的點，即這個概念量化的最典型樣本點，通常是云重心對應的x 值，它應該百分之百地隸屬于這個定性概念。Ex 反映了相應的定性知識的信息中心值。

熵En：熵反映定性概念? 的不確定性。一方面，熵反映了在數域空間可以被語言值? 接受的云滴群的范圍的大小，即模糊度，是定性概念亦此亦彼性的度量；另一方面，熵還反映了代表定性概念的云滴出現的隨機性；此外，熵還揭示了模糊性和隨機

性的關聯性。熵可以用來代表一個定性概念的粒度。通常，熵越大，概念越宏觀，模糊性和隨機性也越大，確定性量化越難。

超熵He：超熵是熵的不確定性的度量，即熵的熵，反映了云滴的離散程度。超熵越大，云滴離散度越大，確定度的隨機性越大，云的“厚度”也越大。

正態云是一種很典型的云模型，被應用于多種現實的模擬，十分具有代表性，因此，一下著重介紹一下與模型的建立方法。

正態云模型既不是一個確定的概率密度函數，也不是一條明晰的隸屬函數曲線，而是由兩次串接的正態發生器[5]生成的許多云滴組成的、一對多的泛正態數學映射圖像，是一朵可伸縮、無確定邊沿、有彈性的云圖，完成定性和定量之間的相互映射。正態云模型的期望曲線是一個正態型曲線。當正態云模型概念對應的論域為一維時，定性定量的不確定性轉換通過正態云發生器算法實現。具體算法如下：

輸入：表示定性概念? 的3 個數字特征值Ex，En，He，云滴數N。

輸出：N 個云滴的定量值，以及每個云滴代表概念? 的確定度。

Step1：生成以En 為期望值，He 為標準差的一個正態隨機數E′n；

Step2：生成以Ex 為期望值，abs（E′n）為標準差的正態隨機數x；

Step3：令x 為定性概念? 的一次具體量化值，稱為云滴；

Step4：計算y=exp(-(x-Ex)2/2(E′n)2)；

Step5：令y 為x 屬于定性概念? 的確定度；

Step6：{x，y}完整地反映了這一次定性定量轉換的全部內容；

Step7：重復Step1~Step6，直到產生N 個云滴。

用該算法生成的云自然地具有不均勻厚度的特性，云的腰部、頂部、底部等并不需要精確地定義，三個數字特征值足以很好地描述整個云的形態。

云模型的應用相當廣泛，下面僅就其在軍事中的一個應用做一描述。在《基于正態云模型的方法求解目標可能位置域》這篇論文當中，作者利用云模型模擬目標可能出現的位置，通過一系列計算，確定一個區域，從而為魚雷發射提供數據支持。

潛艇使用導彈攻擊對方水面艦艇已經成為越來越重要的作戰方式。由于潛艇對隱蔽性的要求，攻擊前很難實時獲得友方兵力的目標指示通報，因此需要根據此前某一時刻通報的目標位置 、速度 、航向 推測出當前的目標可能位置。

模型中已知的前提條件：1．發現目標時刻 ；2． 時刻目標概略中心位置 和誤差分布橢圓的方向 、半軸 和 ；3． 時刻目標速度V、航向H 及其標準偏差 ， 。模型運行的目的是求出時刻T 時的目標概略中心位置( ， )以及誤差分布橢圓的方向 、半軸 和 。

確定目標可能位置域模型的建模思路：按模型中的前提條件，產生M 個 時刻目標隨機位置點；對這M 個點中的任一個點，按照目標速度、航向誤差分別取N1、N2 個隨機速度、航向，在時刻T時產生N1×N2 個隨機位置點。這樣最終產生M×N1×N2 個隨機位置點。最后對M×N1×N2 個隨機位置點進行數據分析得T 時刻的目標位置概率橢圓。該橢圓就是魚雷發射的目標區域。

問題2：論述數據挖掘與空間數據挖掘的異同點。

答：數據挖掘(Data Mining)，就是從大量數據中獲取有效的、新穎的、潛在有用的、最終可理解的模式的非平凡過程。數據挖掘的廣義觀點：數據挖掘就是從存放在數據庫，數據倉庫或其他信息庫中的大量的數據中“挖掘”有趣知識的過程。數據挖掘，又稱為數據庫中知識發現(Knowledge Discovery in Database, KDD)， 也有人把數據挖掘視為數據庫中知識發現過程的一個基本步驟。

知識發現過程以下步驟組成：（1）數據清理，（2）數據集成，（3）數據選擇，（4）數據變換，（5）數據挖掘，（6）模式評估，（7）知識表示。數據挖掘可以與用戶或知識庫交互。

空間數據挖掘是指從空間數據庫中抽取沒有清楚表現出來的隱含的知識和空間關系，并發現其中有用的特征和模式的理論、方法和技術。 空間數據挖掘和知識發現的過程大致可分為以下多個步驟:數據準備、數據選擇、數據預處理、數據縮減或者數據變換、確定數據挖掘目標、確定知識發現算法、數據挖掘、模式解釋、知識評價等，而數據挖掘只是其中的一個關鍵步驟。但是為了簡便，人們常常用空間數據挖掘來代替空間數據挖掘和知識發現?？臻g數據挖掘（Spatial Data Mining， SDM）是數據挖掘的一個分支，是在空間數據庫的基礎上，綜合利用各種技術方法，從大量的空間數據中自動挖掘事先未知的且潛在有用的知識，提取出非顯式存在的空間關系或其它有意義的模式等，揭示出蘊含在數據背后的客觀世界的本質規律、內在聯系和發展趨勢，實現知識的自動獲取，從而提供技術決策與經營決策的依據。數據挖掘所能發現的知識最常見的有以下五種類型：廣義知識、關聯知識、分類知識、聚類知識和預測型知識。而要發現這些知識就需要運用相應空間數據挖掘方法。

綜上所述，二者之間的共同點是：

1. 都是基于已經獲得的數據，無論是存儲在數據庫，數據倉庫，或者是文件當中的數據進行分析；

2. 都是從大量的信息當中，通過數據間的內在聯系提取出操作者感興趣的數據；

3. 提取出的數據都是非顯式存儲的，或者說是隱藏在原有數據當中的；

4. 空間數據挖掘是數據挖掘技術的一個重要分支和發展；

5. 二者均以統計學為數學基礎。

另外二者的不同之處在于：

1. 傳統數據挖掘處理的是數字和類別，而空間數據則是一些更為復雜的數據類型，例如：點、線、多邊形等對象；

2. 傳統數據挖掘通常具有顯式的輸入，而空間數據挖掘的輸入則常常是隱式的；

3. 在傳統數據挖掘中，有一個至關重要的前提假設，即數據樣品是獨立生成的，而這一假設在空間分析中是不成立的，事實上，空間數據之間是高度自關聯的。

4. 數據源十分豐富,數據量非常龐大,數據類型多,存取方法復雜；

5. 應用領域十分廣泛,只要與空間位置相關的數據,都可以對其進行挖掘；

6. 挖掘方法和算法非常多,而且大多數算法比較復雜,難度大；

7.知識的表達方式多樣,對知識的理解和評價依賴于人對客觀世界的認知程度。