數據挖掘原理與算法2023/4/211第1頁，共54頁，2023年，2月20日，星期六空間挖掘技術概述大量的空間數據是從遙感、地理信息系統（GIS）、多媒體系統、醫學和衛星圖像等多種應用中收集而來，收集到的數據遠遠超過了人腦分析的能力。日益發展的空間數據基礎設施為空間數據的自動化處理提出了新的課題。空間數據的最常用的數據組織形式是空間數據庫。空間數據庫必須保存空間實體，這些空間實體是用空間數據類型和實體的空間關系來表示出來的。空間數據庫，不同于關系數據庫，它一般具有空間拓撲或距離信息，通常需要以復雜的多維空間索引結構組織。空間挖掘（SpatialMining）或被稱作空間數據挖掘/空間數據庫的知識發現，是數據挖掘技術在空間數據方面的應用。簡言之，空間數據挖掘，就是從空間數據庫中抽取隱含的知識、空間關系或非顯式地存儲在空間數據庫中的其他模式，用于理解空間數據、發現數據間（空間或非空間）的關系。由于空間數據的復雜性及其應用的專業性，在一般的數據挖掘的基本概念的基礎上，需要研究空間數據挖掘特有的理論、方法和應用。2023/4/212第2頁，共54頁，2023年，2月20日，星期六第八章空間挖掘

內容提要引言空間數據概要空間數據挖掘基礎，空間統計學泛化與特化空間規則空間分類算法空間聚類算法空間挖掘的其他問題空間數據挖掘原型系統介紹空間數據挖掘的研究現狀與發展方向其他2023/4/213第3頁，共54頁，2023年，2月20日，星期六空間數據的主要特點空間數據是指與二維、三維或更高維空間的空間坐標及空間范圍相關的數據，例如地圖上的經緯度、湖泊、城市等。訪問空間數據要比訪問非空間數據更復雜。對空間數據的訪問要使用專門的操作和數據結構。空間數據可以用包含著諸如“接近、南、北、包含于”等空間操作符的查詢來訪問。空間數據存放在記錄著實體的空間性數據和非空間性數據的空間數據庫里。由于空間數據關聯著距離信息，所以空間數據庫通常用使用距離或拓撲信息的空間數據結構或者索引來存儲。就數據挖掘而論，這些距離信息提供了所需的相似性度量的基礎。2023/4/214第4頁，共54頁，2023年，2月20日，星期六空間數據的復雜性特征空間數據的復雜性特征主要表現在以下幾個方面：空間屬性之間的非線性關系：空間屬性之間的非線性關系是空間系統復雜性的重要標志，被作為空間數據挖掘的主要任務之一。空間數據的多尺度特征：空間數據的多尺度性是指空間數據在不同觀察層次上所遵循的規律以及體現出的特征不盡相同。多尺度特征是空間數據復雜性的又一表現形式。空間信息的模糊性：模糊性幾乎存在于各種類型的空間信息中，如空間位置的模糊性、空間相關性的模糊性以及模糊的屬性值等等。空間維數的增高：空間數據的屬性增加極為迅速，如在遙感領域，由于傳感器技術的飛速發展，波段的數目也由幾個增加到幾十甚至上百個，如何從幾十甚至幾百維空間中提取信息、發現知識則成為研究中的又一難題。空間數據的缺值：數據的缺值現象源自由于某種不可抗拒的外力而使數據無法獲得或發生丟失。如何對丟失數據進行恢復并估計數據的固有分布參數，成為解決數據復雜性的難點。2023/4/215第5頁，共54頁，2023年，2月20日，星期六空間查詢問題查詢是挖掘的技術，空間查詢及其操作的主要特點有：空間操作相對復雜和不精確：傳統的訪問非空間數據的選擇查詢使用的是標準的比較操作符：>，<，≤，≥，≠。而空間選擇是一種在空間數據上的選擇查詢，要用到空間操作符，包括接近、東、西、南、北、包含、重疊或相交等。下面是幾個空間選擇查詢的例子：例如，“查找北海公園附近的房子”。空間連接（SpatialJoin）問題：在兩個空間關系上的一個空間性連接操作被稱為空間連接（SpatialJoin）。在空間連接中，關系都是空間性的，需要與空間連接對應的條件描述。例如，“相交”關系用于多邊形；“相鄰”關系用于點。相同的地理區域經常有不同的視圖：一個區域不同的視圖（如基礎設施、城市規劃、綠化等）保存在單獨的GIS文件中，融合這些數據，通常需要一個稱為“地圖覆蓋”（MapOverlay）的操作來實現。

一個空間實體可用空間和非空間的屬性來描述。當其空間屬性用一些空間數據結構存儲起來之后，非空間屬性就可以存儲在一個關系數據庫里。對空間數據庫來說，不同的空間實體經常是和不同的位置相關聯的，而且在不同的實體之間進行空間性操作的時候，經常需要在屬性之間進行一些轉換。2023/4/216第6頁，共54頁，2023年，2月20日，星期六空間數據結構由于空間數據的獨特性質，有很多數據結構專門被設計用來存儲或索引空間數據。這些結構有的考慮的是空間實體的輪廓表示，有的是空間數據的索引方法。空間實體表示的最常用方法是“最小包圍矩形”。空間索引技術大多是基于對空間目標的近似技術，例如，空間映射法（1）采用低維空間向高維空間映射的方式：ｋ維空間具有ｎ個頂點的目標可以映射成ｎ*ｋ維空間的點。映射后，可以直接采用點索引技術。（2）直接向一維空間映射：通常數據空間被劃分成大小相同的網格單元，通過給這些網格單元編碼形成一維目標，用傳統的一維的索引結構（如Ｂ+樹等）索引。分割方法（1）采用不允許空間重疊的索引方法：將所在的數據空間按某種方法（如二叉樹劃分、四叉樹劃分、格網劃分等）劃分成彼此不相交的子空間。（2）采用允許空間重疊的索引法：將索引空間劃分為多級的子空間，這些子空間允許重疊，但是一個空間實體完全包含在某一子空間中。2023/4/217第7頁，共54頁，2023年，2月20日，星期六最小包圍矩形通過完整包含一個空間實體的最小包圍矩形（MBR：MinimumBoundingRectangle）來表示該空間實體。例如，下圖顯示一湖泊的MBR：如果用傳統坐標系統來對這個湖定向，水平軸表示東西方向，垂直軸表示南北方向，那么就可以把這個湖放在一個矩形里（中間圖所示）還可以通過一系列更小的矩形來表現這個湖（右圖所示）另一種更簡單的方法是用一對不相鄰的頂點坐標來表示一個MBR，如用{(x1，y1)，(x2，y2)}來表示（中間圖所示）。2023/4/218第8頁，共54頁，2023年，2月20日，星期六空間索引技術空間索引是指依據空間實體的位置和形狀或空間實體之間的某種空間關系，按一定順序排列的一種數據結構，其中包含空間實體的概要信息。空間索引的性能優劣直接影響空間數據庫和地理信息系統的整體性能，也對空間數據挖掘的效率有影響。幾種比較有代表性的空間數據索引結構技術：網格文件四叉樹R-樹k-D樹2023/4/219第9頁，共54頁，2023年，2月20日，星期六網格文件根據正交的網格劃分ｋ維的數據空間。ｋ維數據空間的網格由ｋ個一維數組表示，這些數組稱為刻度，將其保存在主存。刻度的每一邊界構成ｋ-1維的超平面。整個數據空間被所有的邊界劃分成許多ｋ維的矩形子空間，這些矩形子空間稱為網格目錄，用ｋ維的數組表示，將其保存在硬盤上。網格目錄的每一網格單元包含一外存頁的地址，這一外存頁存儲了該網格單元內的數據目標，稱為數據頁。一數據頁允許存儲多個相鄰網格單元的目標。網格文件的查找簡單，查找效率較高，適用于點目標的索引。2023/4/2110第10頁，共54頁，2023年，2月20日，星期六四叉樹四叉樹通過把空間按等級分解成為區域（單元）來表示空間實體。四叉樹實際上每一節點有4個子樹，用于對空間點的表示與索引。如二維空間的四叉樹，每個子節點對應一個矩形，用四種方位西北（ＮＷ），東北（ＮＥ），西南（ＳＷ），東南（ＳＥ）表示空間區域被分為n層，四叉樹中的每級對應一個層次級別，層的數量n是依賴于所需要的精確度的。例如，2023/4/2111第11頁，共54頁，2023年，2月20日，星期六Ｒ-樹Ｒ-樹是Ｂ-樹在多維空間的擴展其葉子節點包含多個形式為（OI，MBR）的實體，OI為空間目標標志，MBR為該目標在ｋ維空間中的最小包圍矩形。非葉子節點包含多個形式為（CP，MBR）的實體。CP為指向子樹根節點的指針，MBR為包圍其子節點中所有MBR的最小包圍矩形。Ｒ-樹必須滿足如下特性：若根節點不是葉子節點，則至少有兩棵子樹；除根之外的所有中間節點至多有Ｍ棵子樹，至少有ｍ棵子樹；每個葉子節點均包含ｍ至Ｍ個數據項；所有的葉子節點都出現在同一層次；所有節點都需要同樣的存儲空間（一個磁盤頁）。2023/4/2112第12頁，共54頁，2023年，2月20日，星期六k-D樹k-D樹被設計用來對多屬性的數據進行索引，而不是必要的空間數據。k-D樹是二叉樹的一個變種，樹中的每一層用來索引一個屬性。樹中的每個結點表示這個空間基于一個分割點被分割成兩個子集。和R-樹一樣，每個最低級別的區間只有一個實體。但是，分割不是用MBR來進行的。它首先按照一個維分割，然后按照另一個維分割，直到每個區間只有一個實體。2023/4/2113第13頁，共54頁，2023年，2月20日，星期六第八章空間挖掘

內容提要引言空間數據概要空間數據挖掘基礎，空間統計學泛化與特化空間規則空間分類算法空間聚類算法空間挖掘的其他問題空間數據挖掘原型系統介紹空間數據挖掘的研究現狀與發展方向其他2023/4/2114第14頁，共54頁，2023年，2月20日，星期六空間數據庫的操作是數據挖掘的基礎假定A和B是二維空間中的兩個空間實體。每個實體由空間中的點的集合組成：<xa,ya>∈A,<xb,yb>∈B。兩個空間實體之間存在若干拓撲關系。這些關系基于兩個實體的位置：分離（Disjoint）：A與B分離，表示B中任何點都不在A中，反之亦然。重疊/相交：A與B重疊或相交表示至少有一個點既在A里也在B里。等價：A與B這兩個實體的所有點都是共有的。包含于：A包含于B，表示A的所有點都在B里。反之不一定。覆蓋/包含：A覆蓋或包含B，當且僅當B包含于A。根據實體在空間中的位置，可以定義方向，通常采用的是傳統的地圖方向：像東、南、西、北等等。空間謂詞有三種形式：表示拓撲關系的謂詞，如相交、覆蓋等；表示空間方向的謂詞，如東、西、左、右等；表示距離的謂詞，如接近、遠離等。2023/4/2115第15頁，共54頁，2023年，2月20日，星期六實體之間的距離的定義常用的兩個空間實體之間的距離有：最小值方法：定義實體A和B的距離為A中的所有點與和B中的所有點之間的歐氏或曼哈頓距離中最小的，即最大值方法：定義實體A和B的距離為A中的所有點與和B中的所有點之間的歐氏或曼哈頓距離中最大的，即平均值方法：定義實體A和B的距離為A中的所有點與和B中的所有點之間的歐氏或曼哈頓距離的平均值，即中心方法：定義實體A和B的距離為A中的中心點與和B中的中心點之間的歐氏或曼哈頓距離的平均值，即2023/4/2116第16頁，共54頁，2023年，2月20日，星期六空間統計學空間統計學（SpatialStatistics）是依靠有序的模型來描述無序事件，根據不確定性和有限的信息來分析、評價和預測空間數據。基于足夠多的樣本，在統計空間實體的幾何特征量的最小值、最大值、均值、方差、眾數或直方圖的基礎上，可以得到空間實體特征的先驗概率，進而根據領域知識發現共性的幾何知識。空間統計學具有較強的理論基礎和大量的成熟算法。空間統計學是基本的數據挖掘技術，特別是多元統計分析（如判別分析、主成分分析、因子分析、相關分析、多元回歸分析等）。統計方法是分析空間數據的最常用的方法。統計方法能夠有效處理數值型數據，其主要方法是基于統計不相關假設的。在空間數據庫中許多空間數據通常是相關的，即空間對象受其鄰近對象的影響，難以滿足這種假設，這樣就會引起問題。它是空間統計學向著實用的挖掘技術發展的一個重要研究課題。統計方法對非線性規劃不能很好建模，難以處理不完全或不確定性數據，而且運算的代價較高。它是空間統計學向著實用的挖掘技術發展的另一個研究課題。2023/4/2117第17頁，共54頁，2023年，2月20日，星期六第八章空間挖掘

內容提要引言空間數據概要空間數據挖掘基礎，空間統計學泛化與特化空間規則空間分類算法空間聚類算法空間挖掘的其他問題空間數據挖掘原型系統介紹空間數據挖掘的研究現狀與發展方向其他2023/4/2118第18頁，共54頁，2023年，2月20日，星期六空間數據的蘊含著豐富的概念眾所周知，概念層次的使用顯示了數據間關系的層次。應用空間數據特性，概念層次承認了層級中不同層次規則和關系的發展。從空間數據中挖掘所蘊含的概念是空間挖掘的重要任務之一。泛化與特化是概念歸納的主要手段，它對空間數據挖掘也是如此。2023/4/2119第19頁，共54頁，2023年，2月20日，星期六逐步求精的分層技術逐步求精（ProgressiveRefinement）的分層是基于空間關系的，因此空間關系可以應用在一個更粗糙或者更精細的層次上。由于空間應用的數據量十分龐大，在尋求更多精確響應之前要先做出一些近似響應。MBR就是一個近似物體形狀的辦法。四叉樹、R-樹和其他大多數空間索引技術都采用了一種逐步求精的方式。逐步求精可以看作是對處理問題無用的數據所做的過濾。2023/4/2120第20頁，共54頁，2023年，2月20日，星期六泛化數據庫中的數據和對象在原始的概念層次包含有詳細的信息，經常需要將大量數據的集合進行概括并以較高的概念層次展示，即對數據進行泛化。基于泛化的數據挖掘方法假定背景知識以概念層次的形式存在。概念層次可由專家提供，或借助數據分析自動生成。空間數據庫中可以定義兩種類型的概念層次：空間概念層：地理區域之間空間關系的概念層次。非空間概念層：非空間屬性所聯系的非空間數據對應的概念層次。空間數據應用的歸納可以被分為兩種子類：空間數據支配泛化：空間數據支配泛化做的是基于空間位置的聚類（所有靠近的實體被分在一組中）。非空間數據支配泛化：根據非空間屬性值的相似性做聚類。2023/4/2121第21頁，共54頁，2023年，2月20日，星期六空間數據支配泛化算法在空間數據支配泛化算法中，首先對空間數據進行歸納：歸納進行至區域的數量達到閾值為止。然后對相關的非空間屬性做相應地更改。例如，要知道我國西北部地區的平均降雨量，可以在空間層次中尋找西北部所有省，再對非空間屬性（降雨量）進行比較，或者歸納（平均降雨量多、中等、少量等）。典型的空間數據支配泛化算法描述:算法8-1空間數據支配泛化算法輸入：空間數據庫D；空間層次H；概念層次C；查詢Q。輸出：所需一般特征的規則r。（1）D’←從數據庫D中按查詢Q獲得的數據集合；（2）根據H的結構，把數據合并到區域中，直到區域的數目達到所需的閾值，或者已經到達H中所要求的層次；（3）FOReach所找的區域DOBEGIN（4）對非空間屬性執行面向屬性的歸納；（5）產生并輸出所找到的泛化規則；（6）END.2023/4/2122第22頁，共54頁，2023年，2月20日，星期六非空間數據支配泛化算法算法首先對非空間屬性作面向屬性的歸納，將其泛化至更高的概念層次。然后，將具有相同的泛化屬性值的相鄰區域合并在一起，可用鄰近方法忽略具有不同非空間描述的小區域。查詢的結果生成包含少量區域的地圖，這些區域共享同一層次的非空間描述。

2023/4/2123第23頁，共54頁，2023年，2月20日，星期六統計信息網格方法STING介紹統計學信息網格方法（STatisticalINformationGrid-basedmethod—STING），使用了一種類似四叉樹的分層技術，把空間區域分成矩形單元。對空間數據庫掃描一次，可以找到每個單元的統計參數（平均數，變化性，分布類型）。網格結構中的每個結點概括了該網格中所含內部屬性的信息。通過獲取這些信息，很多數據挖掘請求（包括聚類）都可以通過檢驗單元統計得到響應。STING方法可以看作是一種層次聚類技術。層級的頂層的組成就是整體空間。最低層是代表每個最小單元的葉子結點。如果使用一個單元在下一層中擁有四個子單元（網格）的話，單元的分割與四叉樹中是一樣的。2023/4/2124第24頁，共54頁，2023年，2月20日，星期六第八章空間挖掘

內容提要引言空間數據概要空間數據挖掘基礎，空間統計學泛化與特化空間規則空間分類算法空間聚類算法空間挖掘的其他問題空間數據挖掘原型系統介紹空間數據挖掘的研究現狀與發展方向其他2023/4/2125第25頁，共54頁，2023年，2月20日，星期六空間規則的主要類型空間規則可以概括對空間實體的結構及其之間關系的描述。在空間數據挖掘中有三種類型的規則：空間特性規則：描述數據，如北京市家庭平均年收入為30000元。空間判別規則：描述不同種類數據間的差異，依靠它們能夠區分不同種類的特點。如北京市家庭平均年收入為30000元，而上海的家庭平均年收入為35000元。空間關聯規則：是兩個數據集合之間的關聯。如在北京市、住在國貿附近的家庭的平均收入為50000元。所有這些規則都可以被看作是對空間類型的描述，而描述是一種為數據庫或者其中一些子集找到一個表示的方法。特性規則是一種最簡化的形式。2023/4/2126第26頁，共54頁，2023年，2月20日，星期六空間關聯規則空間關聯規則是空間數據實體之間的關聯，有：非空間的先決條件和空間性的結果：如在北京、所有的重點學校都是位于老住宅區附近。空間性先決條件和非空間的結果：如在北京、房子在國貿附近，就比較貴。空間性先決條件和空間性結果：如在北京、所有市區的房子都在三環以內。空間關聯規則挖掘是傳統關聯規則挖掘的延伸，常用最小支持度和最小可信度來作為基本的統計參數，由于空間數據的特點，往往是在多層概念上進行歸納。挖掘空間關聯規則的有效方法是自上而下、逐步加深的搜索技術。首先在高的概念層次進行搜索，在較粗的精度級別查找頻繁發生的模式和在這些模式中較強的隱含關系；然后，對頻繁發生的模式加深搜索至較低的概念層次，這種處理持續到找不到頻繁發生的模式為止。2023/4/2127第27頁，共54頁，2023年，2月20日，星期六空間關聯規則基本步驟典型的五步算法：步驟1：通過給定的查詢抽取出相關的數據。步驟2：應用一個粗的空間運算方法，計算整個相關數據的集合。步驟3：過濾出那些支持度小于最小支持度閾值的1階謂詞。步驟4：應用一個細化的空間計算方法，從所導出的粗的謂詞集合中計算謂詞。步驟5：向低層深入，在多個概念層次上找到關聯規則的完整集合。算法8-4

空間關聯規則算法輸入：空間數據庫D；概念層次C；層次的最小支持度和可信度s和α；尋找感興趣實體的查詢q；感興趣的拓撲關系p。輸出：空間關聯規則R。（1）D’=q(D)；（2）在D’中應用粗糙謂詞，建造CP；//CP是由滿足D’中實體對的粗糙謂詞組成的（3）通過尋找滿足s的粗糙謂詞來找到頻繁粗糙謂詞FCP；（4）從FCP中找到頻繁精確謂詞FFP；（5)尋找所有的頻繁精確謂詞得到R，然后歸納準則.2023/4/2128第28頁，共54頁，2023年，2月20日，星期六第八章空間挖掘

內容提要引言空間數據概要空間數據挖掘基礎，空間統計學泛化與特化空間規則空間分類算法空間聚類算法空間挖掘的其他問題空間數據挖掘原型系統介紹空間數據挖掘的研究現狀與發展方向其他2023/4/2129第29頁，共54頁，2023年，2月20日，星期六空間分類方法空間分類方法用來對空間實體的集合進行分類。給空間實體分類，可以通過非空間屬性或空間屬性或二者結合，并可利用概念層次來進行取樣。對于樣本數據的訓練可以通過改造傳統的分類算法來完成，例如，對ID3算法擴展。2023/4/2130第30頁，共54頁，2023年，2月20日，星期六空間決策樹建造一個決策樹，有五個主要步驟：根據已知的分類，從數據D中找到例子S。確定最佳謂詞p用來分類。一般首先在較粗的層次中尋找相關謂詞，然后再在較為細化的層次。找到最佳的緩沖區大小和形狀。對于取樣中的每個實體，它周圍的區域被稱為緩沖區。目標是選擇一個能產生對測試集中的類型進行最不同的緩沖區。使用p和C，對每個緩沖區歸納謂詞。使用泛化的謂詞和ID3建造二叉樹T。算法8-5

空間決策樹算法輸入：空間數據庫D；概念層次C；預定的類別。輸出：二叉決策樹T。（1）根據預定的類別，從數據D中找到例子S；（2）確定最佳謂詞p用來分類；（3）找到最佳的緩沖區大小和形狀；（4）使用p和C，對每個緩沖區歸納謂詞；（5）使用泛化的謂詞和ID3建造二叉樹T.2023/4/2131第31頁，共54頁，2023年，2月20日，星期六第八章空間挖掘

內容提要引言空間數據概要空間數據挖掘基礎，空間統計學泛化與特化空間規則空間分類算法空間聚類算法空間挖掘的其他問題空間數據挖掘原型系統介紹空間數據挖掘的研究現狀與發展方向其他2023/4/2132第32頁，共54頁，2023年，2月20日，星期六空間聚類空間聚類算法必須在大型多維數據庫上有效工作，而且應該能夠探測到不同形狀的聚類。因此，難度和挑戰性要比傳統數據要大。空間聚類找到的聚類不應該依賴于檢驗空間中的點的順序，而且聚類也不應該受不相干的點影響。傳統的聚類算法可以通過改造來實現空間數據聚類。2023/4/2133第33頁，共54頁，2023年，2月20日，星期六基于隨機搜索的聚類方法CLARANS擴展CLARANS算法可以表示為查找一個圖，圖中的每個節點都是潛在的解決方案。在替換一個中心點后獲得的聚類稱為當前聚類的鄰居。隨意測試的鄰居的數目由參數maxneighbor限制。如果找到一個更好的鄰居，將中心點移至鄰居節點，重新開始上述過程，否則在當前的聚類中生成一個局部最優。找到一個局部最優后，再任意選擇一個新的節點重新尋找新的局部最優。局部最優的數目被參數numlocal限制。CLARANS并不搜索遍所有的求解空間，也不限制在任何具體的采樣中。CLARANS每次迭代的計算復雜度與對象的數量基本呈線性關系。基于CLARANS的空間數據聚類算法有兩種：空間支配算法SD（CLARANS）和非空間支配算法NSD（CLARANS）。2023/4/2134第34頁，共54頁，2023年，2月20日，星期六DBCLASD算法一種大型空間數據庫基于距離分布的聚類算法，叫做DBCLASD（DistributionBasedClusteringofLargeSpatialDatabases），它是DBSCAN的擴展。假定聚類中的項目是均勻分布的，算法嘗試確定滿足最近鄰居距離的分布。只要最近的鄰居距離滿足均一分布的假設，那么這個元素就被加入聚類。算法8-7DBCLASD算法輸入：要被聚類的空間實體D；輸出：聚類集合K。（1）K←0；//初始化，沒有聚類（2）c←Ф；//初始化候選集合為空（3）FOReachpointpinDDOBEGIN（4）IFpisnotinaclusterTHENBEGIN（5）

創建一個新的聚類C，并把p加入C；（6）

把p臨近的點加入C；（7）END （8）FOReachpointqinCDOBEGIN（9）

把C中沒有處理過的點q的鄰居點加入C；（10）K←K∪{C}（11）END.2023/4/2135第35頁，共54頁，2023年，2月20日，星期六BANG算法BANG方法使用了一種類似k-D樹的網格結構。這個結構為適應屬性的分布而做了一定調整，使密集的區域具有大量的更小的網格，而不夠密集的區域只有少量的更大的網格。接著按照網格（塊）的密度排序，也就是按照區域分割的網格里的項目數量。根據期望的聚類數量，那些密度最大的網格被選為聚類的中心。對于每個選定的網格，只要它們的密度小于或者等于當前這個聚類的中心，就把這個臨近的網格加入。2023/4/2136第36頁，共54頁，2023年，2月20日，星期六小波聚類用小波聚類歸納空間聚類的方法是把數據看作像STING那樣的信號，小波聚類使用的是網格。歸納聚類的時間復雜度是O(n)，并且不受外界影響。與一些方法不同，小波聚類可以找到任意形狀的聚類，而且不需要知道期望的聚類個數。n維空間的空間實體集合可看作是一個信號。聚類的邊界與高頻相應。聚類本身是低頻率高振幅的。可以使用信號處理技術尋找空間中低頻的部分。可以使用小波變換來尋找聚類。小波變換是用來找出信號中的頻譜的。一個空間實體的小波變換分解維空間圖像的層次。它們可以用來把一個圖像縮放為不同的大小。2023/4/2137第37頁，共54頁，2023年，2月20日，星期六使用近似值來確定聚類的特性一旦找到了空間聚類，可以使用近似值來確定這些聚類的特性：通過確定聚類附近的特征實現的。例如，一個聚類“靠近學校”。通常更多地用復雜的近似多邊形表示，而非指用簡單的MBR。聚合鄰近定義為衡量一個聚類（或者元素群）與一個特征（或者空間中某個實體）接近的程度。聚合鄰近距離可以由聚類中所有點的距離總和來度量。CRH算法是典型的確定聚合鄰近關系方法。它使用三種幾何形狀來界定一個聚類：內接矩形R：包含了一系列點的MBR。矩形邊緣與坐標軸平行。外接圓C：包圍一系列點的圓周；以內接矩形的對角線為直徑。凸多邊形H：包含點的集合的最小邊界。CRH首先使用一個外接圓來接近給定的類；其次使用內接矩形來表示特征，并根據特征與聚類的接近程度來進行排序；最后使用凸多邊形來評估前面所有最接近的特征。2023/4/2138第38頁，共54頁，2023年，2月20日，星期六第八章空間挖掘

內容提要引言空間數據概要空間數據挖掘基礎，空間統計學泛化與特化空間規則空間分類算法空間聚類算法空間挖掘的其他問題空間數據挖掘原型系統介紹空間數據挖掘的研究現狀與發展方向其他2023/4/2139第39頁，共54頁，2023年，2月20日，星期六空間挖掘的其他問題1．空間在線分析挖掘空間在線分析挖掘（SOLAM：SpatialOnlineAnalyticalMining）建立在多維視圖基礎之上，是基于網絡的驗證型空間數據挖掘和分析工具。空間在線分析挖掘通過數據分析與報表模塊的查詢和分析工具（OLAP、決策分析、數據挖掘）完成對信息和知識的提取，以滿足決策的需要。它建立在客戶/服務器的結構之上，由用戶驅動，支持多維數據分析，在用戶的指導下驗證設定的假設。美國BusinessObjects公司的BusinessObjects（BO）就是采用DataＷarehouse+OLAP+DataMining方案推出的第一個集多數據源查詢、任意報表生成和OLAP及數據挖掘技術為一體的決策支持工具軟件包。2023/4/2140第40頁，共54頁，2023年，2月20日，星期六空間挖掘的其他問題2．挖掘圖像數據庫的方法圖像數據庫是一類特殊的空間數據庫，其數據幾乎全部是圖像或圖片。圖像數據庫用于遙感、醫學圖像等應用，通常以柵格形式表示，柵格代表一個或多個光譜范圍的圖像密度。圖像數據庫的挖掘可以看成是空間數據挖掘的一部分，其主要問題在于如何區分圖像。以下列出對這方面問題的一些研究。Magellan研究恒星分類POSS-II（SecondPalomarObservatorySkySurvey）基于內容的時空查詢CONQUEST

2023/4/2141第41頁，共54頁，2023年，2月20日，星期六空間挖掘的其他問題3．基于Rough集方法Rough集理論被廣泛研究并應用于不精確、不確定、不完全的信息的分類分析和知識獲取中。Rough集理論為空間數據的屬性分析和知識發現開辟了一條新途徑，可用于空間數據庫屬性表的一致性分析、屬性的重要性、屬性依賴、屬性表簡化、最小決策和分類算法生成等。Rough集方法與其他知識發現方法相結合，可以在數據庫中數據不確定情況下獲取多種知識。4．基于云理論挖掘方法云理論是由李德毅等提出的一種用于處理不確定性的新理論，由云模型、不確定性推理和云變換三大支柱構成。云理論將模糊性和隨機性結合起來，解決了作為模糊集理論基石的隸屬函數概念的固有缺陷，為KDD中定量與定性相結合的處理方法奠定了基礎，可以用于處理GIS中融隨機性和模糊性為一體的屬性不確定性。2023/4/2142第42頁，共54頁，2023年，2月20日，星期六空間挖掘的其他問題5．探測性的數據分析（EDA）探測性的數據分析，簡稱EDA，采用動態統計圖形和動態鏈接窗口技術將數據及其統計特征顯示出來，可發現數據中非直觀的數據特征及異常數據。EDA技術在知識發現中用于選取感興趣的數據子集，即數據聚焦，并可初步發現隱含在數據中的某些特征和規律。6．可視化現代的數據可視化（DataVisualization）技術是指運用計算機圖形學和圖像處理技術，將數據轉換為圖形或圖像在屏幕上顯示出來，并進行交互處理的理論、方法和技術。它涉及到計算機圖形學、圖像處理、計算機輔助設計、計算機視覺及人機交互技術等多個領域。數據可視化概念首先來自科學計算可視化。2023/4/2143第43頁，共54頁，2023年，2月20日，星期六第八章空間挖掘

內容提要引言空間數據概要空間數據挖掘基礎，空間統計學泛化與特化空間規則空間分類算法空間聚類算法空間挖掘的其他問題空間數據挖掘原型系統介紹空間數據挖掘的研究現狀與發展方向其他2023/4/2144第44頁，共54頁，2023年，2月20日，星期六空間數據挖掘原型系統介紹加拿大SimonFraser大學開發的空間數據挖掘系統原型GeoMiner很有代表性。該系統包含有三大模塊：空間數據立方體構建模塊，空間聯機分析處理（OLAP）模塊和空間數據挖掘模塊，采用的空間數據挖掘語言是GMQL。目前已能挖掘三種類型的規則：特征規則、判別規則和關聯規則。GeoMiner的體系結構如圖8-12所示，包含四個部分：圖形用戶界面，用于進行交互式地挖掘并顯示挖掘結果；發現模塊集合，含有上述三個已實現的知識發現模塊以及四個計劃實現的模塊（分別用實線框和虛線框表示）；空間數據庫服務器，包括MapInfo、ESRI/OracleSDE、Informix-Illustra以及其他空間數據庫引擎；存儲非空間數據、空間數據和概念層次的數據庫和知識庫。2023/4/2145第45頁，共54頁，2023年，2月20日，星期六空間數據挖掘原型系統介紹

空間數據圖形用戶界面GeoMiner：知識發現模塊空間數據庫服務器和數據立方體非空間數據概念層次空間特征規則發現模塊空間關聯規則發現模塊空間預測模塊空間模式分析模塊空間比較規則發現模塊空間分類規則發現模塊空間聚類分析模塊未來的空間發現模塊2023/4/2146第46頁，共54頁，2023年，2月20日，星期六空間數據挖掘原型系統介紹到目前為止，尚沒有對空間數據挖掘查詢語言SDMQL（SpatialDataMiningQueryLanguage）的定義。Han等人為了挖掘地理空間數據庫設計了一種地理數據挖掘查詢語言GMQL（Geo-MiningQueryLanguage），它是對空間SQL的擴展，并成功地應用于空間數據挖掘系統原型GeoMiner中。GMQL可作為制定SDMQL的基礎，以進一步界定SDMQL語言的基本原語。SDMQL的設計指導原則主要有：在空間數據挖掘請求中應說明用于挖掘的相關數據集。在空間數據挖掘請求中應說明想要挖掘的知識的種類。挖掘過程中應該可能運用相關的背景知識。挖掘結果應該能用較概括的或多層次概念的術語來表述。應能夠說明各種各樣的閾值，使得可以靈活地過濾掉那些不是很令人感興趣的知識。應采用類似SQL的語法以適應在高級語言的水平上進行數據挖掘并與關系查詢語言SQL保持自然的融合。2023/4/2147第47頁，共54頁，2023年，2月20日，星期六第八章空間挖掘

內容提要引言空間數據概要空間數據挖掘基礎，空間統計學泛化與