空間信息系統(tǒng)原理10-1課件

1、空間數(shù)據(jù)挖掘Outline: 數(shù)據(jù)挖掘空間數(shù)據(jù)挖掘outline數(shù)據(jù)挖掘數(shù)據(jù)挖掘簡介背景、地位、應用數(shù)據(jù)挖掘原語和數(shù)據(jù)挖掘查詢語言數(shù)據(jù)挖掘的體系結構數(shù)據(jù)挖掘的功能、分類、主要問題數(shù)據(jù)挖掘方法空間數(shù)據(jù)挖掘什么是數(shù)據(jù)挖掘？數(shù)據(jù)挖掘（數(shù)據(jù)庫中的知識發(fā)現(xiàn)）：從大量的、不完全的、有噪聲的、模糊的、隨機的數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程。相近似的術語：從數(shù)據(jù)庫中發(fā)現(xiàn)知識（KDD）、數(shù)據(jù)分析、數(shù)據(jù)融合(Data Fusion）等。原始數(shù)據(jù)是可以結構化的，如關系數(shù)據(jù)庫中的數(shù)據(jù)；也可以是半結構化的，如文本、圖形、圖象數(shù)據(jù)，甚至是分布在網(wǎng)絡上的異構型數(shù)據(jù)。例：IC卡數(shù)據(jù)

2、地理信息系統(tǒng)人流動態(tài)圖用途：公交，水電，房地產(chǎn)，商業(yè)，環(huán)境長遠：經(jīng)濟評價，分析與預測outline數(shù)據(jù)挖掘數(shù)據(jù)挖掘簡介背景、功能、應用數(shù)據(jù)挖掘原語和數(shù)據(jù)挖掘查詢語言數(shù)據(jù)挖掘的體系結構數(shù)據(jù)挖掘的功能、分類、主要問題數(shù)據(jù)挖掘方法空間數(shù)據(jù)挖掘Data MiningDatabase TechnologyStatisticsOtherDisciplinesInformationScienceMachineLearningVisualization數(shù)據(jù)挖掘：多學科的匯合數(shù)據(jù)挖掘：KDD過程的核心Data CleaningData IntegrationDatabasesData WarehouseKnow

3、ledgeTask-relevant DataSelectionData MiningPattern Evaluation應用領域數(shù)據(jù)庫分析和決策支持市場分析管理客戶關系管理，交叉銷售，市場分割風險分析管理預測，客戶保持，質(zhì)量控制，競爭分析欺騙檢測管理其他應用文本挖掘（新聞組，email，文檔）和Web分析智能查詢應答outline數(shù)據(jù)挖掘數(shù)據(jù)挖掘簡介背景、地位、應用數(shù)據(jù)挖掘原語和數(shù)據(jù)挖掘查詢語言數(shù)據(jù)挖掘的體系結構數(shù)據(jù)挖掘的功能、分類、主要問題數(shù)據(jù)挖掘方法空間數(shù)據(jù)挖掘在數(shù)據(jù)庫中自動發(fā)現(xiàn)所有的模式？不切實際的，可能有太多卻讓人不感興趣的的模式數(shù)據(jù)挖掘可以是一個交互過程用戶指定要挖掘什么必須提供給

4、用戶一套與數(shù)據(jù)挖掘系統(tǒng)交互的原語把這些原語合并起來，就是數(shù)據(jù)挖掘查詢語言更靈活的用戶交互圖形用戶界面設計的基礎數(shù)據(jù)挖掘工業(yè)和實踐的標準化數(shù)據(jù)挖掘原語和語言use database AllElectronics_db use hierarchy location_hierarchy for B.addressmine characteristics as customerPurchasing analyze count% in relevance to C.age, I.type, I.place_made from customer C, item I, purchases P, items_

5、sold S, works_at W, branchwhere I.item_ID = S.item_ID and S.trans_ID = P.trans_ID and P.cust_ID = C.cust_ID and P.method_paid = AmEx and P.empl_ID = W.empl_ID and W.branch_ID = B.branch_ID and B.address = Canada and I.price = 100with noise threshold = 0.05 display as tableExample: 一個DMQL查詢outline數(shù)據(jù)挖

6、掘數(shù)據(jù)挖掘簡介背景、地位、應用數(shù)據(jù)挖掘原語和數(shù)據(jù)挖掘查詢語言數(shù)據(jù)挖掘的體系結構數(shù)據(jù)挖掘的功能、分類、主要問題數(shù)據(jù)挖掘方法空間數(shù)據(jù)挖掘outline數(shù)據(jù)挖掘數(shù)據(jù)挖掘簡介背景、地位、應用數(shù)據(jù)挖掘原語和數(shù)據(jù)挖掘查詢語言數(shù)據(jù)挖掘的體系結構數(shù)據(jù)挖掘的功能、分類、主要問題數(shù)據(jù)挖掘方法空間數(shù)據(jù)挖掘數(shù)據(jù)挖掘功能（1）概念描述：特征和比較歸納、概括、對比數(shù)據(jù)的特征，例如，干燥地區(qū)和濕潤地區(qū)關聯(lián)contains(x, “computer”) contains(x, “software”) support = 1%, confidence = 75%age(X, “20.29”) income(X, “20.29K

7、”) buys(X, “PC”) 2%, 60%多維關聯(lián) vs. 一維關聯(lián)分類和預測 為將來的預測發(fā)現(xiàn)描述和區(qū)別類或概念的模型（函數(shù)）例如，基于氣候為國家分類，基于一加侖汽油所行駛的里程為汽車分類表示方法：決策樹，分類規(guī)則，神經(jīng)網(wǎng)絡預測：預測未知或丟失的數(shù)值聚類分析類標簽未知：聚合數(shù)據(jù)以形成新的類，例如，聚類房屋以發(fā)現(xiàn)分布模式聚類原則：使類內(nèi)部的相似性最大化，類間的相似性最小化數(shù)據(jù)挖掘功能（2）離群點（outlier）分析離群點：不符合數(shù)據(jù)的一般行為的數(shù)據(jù)對象可以理解為噪音或異常在欺騙檢測、稀少事件份系中很有用趨勢和演化分析趨勢和背離：衰退分析連續(xù)模式挖掘，周期分析基于相似性的分析其它定向模式

8、或統(tǒng)計分析數(shù)據(jù)挖掘功能（3）根據(jù)要挖掘的數(shù)據(jù)庫關系，失誤，面向?qū)ο?，面向關系，空間，時間序列，文本，多媒體，異構，遺產(chǎn)， WWW，等等根據(jù)要挖掘的知識特征，區(qū)別，關聯(lián)，分類，聚類，趨勢，背離，outlier分析，等等根據(jù)利用的技術面向數(shù)據(jù)庫，數(shù)據(jù)倉庫（OLAP），機器學習，統(tǒng)計學，可視化，神經(jīng)網(wǎng)絡，等等根據(jù)適合的應用零售，電信，銀行，欺騙分析，DNA挖掘，股市分析，Web挖掘， Weblog分析，等等數(shù)據(jù)挖掘的分類挖掘方法和用戶交互在數(shù)據(jù)庫中挖掘不同的知識提取的多個層次上的知識的交互式挖掘背景知識的結合數(shù)據(jù)挖掘查詢語言和ad-hoc數(shù)據(jù)挖掘數(shù)據(jù)挖掘結果的表達和可視化處理噪音和不完全數(shù)據(jù)模式評價

9、：the interestingness problem性能和擴展性數(shù)據(jù)挖掘算法的效率和擴展性并行的、分布的、增量的挖掘方法數(shù)據(jù)挖掘中的主要問題（1）outline數(shù)據(jù)挖掘數(shù)據(jù)挖掘簡介數(shù)據(jù)挖掘方法數(shù)據(jù)泛化特征和比較關聯(lián)規(guī)則挖掘分類聚類分析空間數(shù)據(jù)挖掘描述數(shù)據(jù)挖掘：用簡明的、概括的、信息豐富的、有辨別力的格式描述概念或任務相關數(shù)據(jù)集預測數(shù)據(jù)挖掘：基于數(shù)據(jù)和分析，為數(shù)據(jù)庫構造模型，預測未知數(shù)據(jù)的趨勢和性質(zhì)描述數(shù)據(jù)挖掘 vs. 預測數(shù)據(jù)挖掘數(shù)據(jù)泛化在數(shù)據(jù)庫中，從底概念層到高概念層，抽取任務相關集的過程方法數(shù)據(jù)立方體方法（OLAP方法）面向?qū)傩缘臍w約方法泛化的結果可用泛化關系或數(shù)據(jù)立方體的形式表達，用

10、以執(zhí)行進一步的OLAP操作，也可以映射為概括表、圖表或曲線來進行可視化表示，還能從中抽取特征和判別規(guī)則12345Conceptual levels在數(shù)據(jù)立方體中執(zhí)行計算并存儲結果Strength數(shù)據(jù)泛化的有效運用各種計算方法例如， count( ), sum( ), average( ), max( )泛化（一般化）和特殊化可以在數(shù)據(jù)立方體上通過roll-up和drill-down完成Limitations只能處理簡單的非數(shù)字型數(shù)據(jù)維和簡單的數(shù)值型的集合運算缺少智能分析，不能判斷：該使用哪一維，泛化應達到哪一層數(shù)據(jù)立方體方法不限制于分類數(shù)據(jù)或特殊的運算How it is done?用關系數(shù)據(jù)庫

11、查詢收集任務相關數(shù)據(jù)（初始關系）提升泛化層次，通過屬性移除或?qū)傩砸话慊瘓?zhí)行數(shù)據(jù)泛化通過合并同樣的、一般的元組，應用聚合并累積各自的數(shù)目面向?qū)傩缘臍w約數(shù)據(jù)focusing: 任務相關數(shù)據(jù)，包括維數(shù)，結果為初始關系屬性移除：移除屬性A如果有一個關于A的值的集合，而沒有關于A的一般化操作A的高層概念用其它的屬性表達屬性一般化：存在一組關于A的一般化操作時屬性閾值控制：一般為2-8，指定或缺省泛化關系閾值控制：控制最后關系/規(guī)則的大小面向?qū)傩詺w約的基本原理泛化關系泛化關系中，一些/所有屬性被泛化，計數(shù)，或其他集合值的累積交叉表把結果制成交叉表的形式可視化技術：餅圖、柱狀圖、曲線圖彪、立方體，等等定量特

12、征規(guī)則把泛化結果以定量的形式制成特征規(guī)則，如泛化結果的表示泛化結果的表示泛化關系泛化結果的表示交叉表outline數(shù)據(jù)挖掘數(shù)據(jù)挖掘簡介數(shù)據(jù)挖掘方法數(shù)據(jù)泛化特征和比較關聯(lián)規(guī)則挖掘分類聚類分析空間數(shù)據(jù)挖掘特征：提供一個指定數(shù)據(jù)集合的簡明、簡潔概括ExampleDMQL: 描述Big-University數(shù)據(jù)庫中畢業(yè)生的一般特征use Big_University_DBmine characteristics as “Science_Students”in relevance to name, gender, major, birth_place, birth_date, residence, ph

13、one#, gpafrom studentwhere status in “graduate”對應的SQL語句：Select name, gender, major, birth_place, birth_date, residence, phone#, gpafrom studentwhere status in “Msc”, “MBA”, “PhD” 特征Prime Generalized RelationInitial Relationexample比較：提供兩個或多個數(shù)據(jù)集合的比較描述方法：把相關數(shù)據(jù)集劃分成目標類和對比類把這兩類都泛化到概念層次的同一層Compare tuples w

14、ith the same high level descriptionsPresent for every tuple its description and two measures:support - distribution within single classcomparison - distribution between classesHighlight the tuples with strong discriminant features 相關分析：發(fā)現(xiàn)最能區(qū)別不同類的屬性（特征）比較outline數(shù)據(jù)挖掘數(shù)據(jù)挖掘簡介數(shù)據(jù)挖掘方法數(shù)據(jù)泛化特征和比較關聯(lián)規(guī)則挖掘分類聚類分析空間

15、數(shù)據(jù)挖掘關聯(lián)規(guī)則挖掘：在事務數(shù)據(jù)庫、關系數(shù)據(jù)庫和其他信息倉庫中，從項目或?qū)ο蟮募现邪l(fā)現(xiàn)頻繁模式、關聯(lián)、相關性或因果關系結構應用：Basket數(shù)據(jù)分析，cross-marketing，目錄設計， loss-leader 分析，聚類，分類，等等找出表達一項目集的存在和另一個項目集相關的所有規(guī)則規(guī)則格式: “antecedent consequent support, confidence”.buys(x, “diapers”) buys(x, “beers”) 0.5%, 60%major(x, “CS”) takes(x, “DB”) grade(x, “A”) 1%, 75%可能在規(guī)則上作一

16、些限制 （例如，僅找出包括Home Laundry Appliances的規(guī)則 ）關聯(lián)規(guī)則挖掘置信度（confidence）和支持度（support） ：規(guī)則 X Y的置信度是D中包含X的事務，又包含Y的百分比， c = （包含X和Y的事務的數(shù)目）/（包含X的事務總數(shù)）X Y的支持度是D中既包含X又包含Y的事務的百分比 s = （包含X和Y的事務的數(shù)目）/（D中事務的總數(shù)） 挖掘關聯(lián)規(guī)則：發(fā)現(xiàn)所有的具有最小的、用戶指定的置信度和支持度的規(guī)則發(fā)現(xiàn)頻繁項目集：聚有最小支持度的項目集合使用頻繁項目集生成想要的規(guī)則關聯(lián)規(guī)則的挖掘算法挖掘關聯(lián)規(guī)則exampleFor rule A C:support =

17、 support(A, C) = 50%confidence = support(A, C)/support(A) = 66.6%Min. support 50%Min. confidence 50%布爾型 vs. 數(shù)量型關聯(lián)(基于要處理的值的類型)buys(x, “SQLServer”) buys(x, “DMBook”) buys(x, “DBMiner”) 0.2%, 60%age(x, “30.39”) income(x, “42.48K”) buys(x, “PC”) 1%, 75%單維 vs. 多維關聯(lián) (see ex. Above)單層 vs. 多層分析什么牌子的啤酒與什么牌子的

18、尿布關聯(lián)？各種擴展相關性，因果關系分析關聯(lián)不一定意味著相關性和因果關系最大模式和最緊密項目集強化約束例如，小的銷售 (sum 1,000)?關聯(lián)規(guī)則outline數(shù)據(jù)挖掘數(shù)據(jù)挖掘簡介數(shù)據(jù)挖掘方法數(shù)據(jù)泛化特征和比較關聯(lián)規(guī)則挖掘分類聚類分析空間數(shù)據(jù)挖掘分類：預測絕對的（categorical）類標簽基于訓練集和分類屬性的值（類標簽）分類數(shù)據(jù)（構造一個模型），用以分類新的數(shù)據(jù)典型應用：信用認可、target marketing、醫(yī)學診斷、治療效果分析分類過程：模型構造：描述一個預先確定的類的集合模型表示為分類規(guī)則、決策樹或數(shù)學公式模型的使用：分類將來的或未知的對象模型的精確性評估測試集獨立于訓練集分

19、類Classifier(Model)TrainingDataClassificationAlgorithmsIF rank = professorOR years 6THEN tenured = yes 分類過程（1）模型構造ClassifierTestingDataUnseen Data(Jeff, Professor, 4)Tenured?分類過程（2）將模型用于預測決策樹用于將數(shù)據(jù)分成兩個集合（如“拒絕”和“接受”）內(nèi)部節(jié)點表示關于一個屬性的測試分支表示一個測試結果葉結點表示類標簽或類的分布（類預測）決策樹的泛化樹的構造開始，所有的訓練例子都在根節(jié)點基于選定的屬性，遞歸的劃分這些例子樹的

20、修剪確定并移除反映噪音或outlier的分支決策樹的使用：分類未知樣品根據(jù)決策樹測試樣品的屬性值利用決策樹歸約的分類訓練數(shù)據(jù)集age?student?credit rating?noyesfairexcellent40nonoyesyesyes30.40輸出：一個“buys_computer”的決策樹用IF-THEN 的形式表示每一條從根結點到葉結點的路徑對應一個規(guī)則葉結點為類預測信息ExampleIF age = “=30” AND student = “no” THEN buys_computer = “no”IF age = “40” AND credit_rating = “excel

21、lent” THEN buys_computer = “yes”IF age = “ g_close_to(x, water) (80%)is_a(x, big_city) g_close_to(x, sea) - g_close_to (x, us_boundary) (92%)example類SQL的空間數(shù)據(jù)挖掘查詢接口 Discover spatial association rules inside USAfrom airport A, highway H, port Pin relevance to USA cities Cwhere g_close_to(C.geo, X.geo)

22、 and X in A, H, P with minimum support as 2.0%and minimum confidence as 85%outline數(shù)據(jù)挖掘空間數(shù)據(jù)挖掘空間數(shù)據(jù)挖掘簡介空間數(shù)據(jù)挖掘方法空間特征化空間關聯(lián)規(guī)則空間分類空間聚類空間數(shù)據(jù)挖掘的實現(xiàn)空間數(shù)據(jù)挖掘的未來方向空間分類目標考慮數(shù)據(jù)庫中對象的空間屬性和空間關系，以及它們的非空間屬性，以發(fā)現(xiàn)分類規(guī)則目前空間數(shù)據(jù)分類的研究尚處在起步階段 Ng和Yu提出了一種方法以抽取專題地圖上聚類的強的、公共的、判別性的特征，僅適用于分析專題地圖的屬性值 決策樹空間分類算法 ，不適合處理帶有不完整信息的問題 空間數(shù)據(jù)分類標準中包含數(shù)

23、據(jù)間的空間關系，如果輸入數(shù)據(jù)出現(xiàn)了不一致、噪聲等情況，決策樹算法可能會造成錯分，嚴重影響決策樹算法的預測準確度。不能很好地體現(xiàn)地理空間關系對于分類的影響?？臻g決策樹outline數(shù)據(jù)挖掘空間數(shù)據(jù)挖掘空間數(shù)據(jù)挖掘簡介空間數(shù)據(jù)挖掘方法空間特征化空間關聯(lián)規(guī)則空間分類空間聚類空間數(shù)據(jù)挖掘的實現(xiàn)空間數(shù)據(jù)挖掘的未來方向空間聚類空間數(shù)據(jù)聚類在一個大的多維數(shù)據(jù)集合中采用距離度量以標識出聚類，由此來發(fā)現(xiàn)數(shù)據(jù)集合的整個分布模式。 空間聚類的應用通過聚類，在地理信息系統(tǒng)中，給地震目錄分組或創(chuàng)建主題地圖，檢測地震斷層，等等空間聚類算法基于隨機搜索的聚類方法CLARANS 并不搜索遍所有的求解空間，也不限制在任何具體的

24、采樣中。每次迭代的計算復雜度與對象的數(shù)量基本呈線性關系。CLARANS也可檢測出離群點，例如不屬于任何聚類的點?？臻g支配算法SD和非空間支配算法NSDCLARANS聚焦法：引入R樹，可用于處理大型數(shù)據(jù) 平衡迭代消減聚類法BIRCH 聚類特征（clustering feature）和聚類特征樹（CF-tree） 較為靈活的增量式聚類方法，具有良好的算法伸縮性、對數(shù)據(jù)輸入順序不敏感性以及較好的聚類效果 大型空間數(shù)據(jù)庫基于距離分布的聚類算法DBCLASD 采用遺傳算法進行空間聚類 outline數(shù)據(jù)挖掘空間數(shù)據(jù)挖掘空間數(shù)據(jù)挖掘簡介空間數(shù)據(jù)挖掘方法空間數(shù)據(jù)挖掘的實現(xiàn)空間數(shù)據(jù)挖掘的未來方向加拿大Simo

25、n大學開發(fā)該系統(tǒng)在空間數(shù)據(jù)庫建模中使用SAND體系結構，包含有三大模塊：空間數(shù)據(jù)立方體構建模塊、空間聯(lián)機分析處理（OLAP）模塊和空間數(shù)據(jù)采掘模塊采用的空間數(shù)據(jù)采掘語言是GMQL主要功能模型：Geo-Characterizer and Geo_Comparator (Spatial OLAP)Geo-ClassifierGeo-AssociatorGeo-Cluster-AnalyzerGeo-PredictorGeo-Pattern-AnalyzerGeoMiner：一個空間數(shù)據(jù)挖掘原型系統(tǒng)GeoMiner的體系結構GeoMiner的體系結構包含4個部分：圖形用戶界面，用于進行交互式地挖掘并

26、顯示挖掘結果；發(fā)現(xiàn)模塊集合，已實現(xiàn)的知識發(fā)現(xiàn)模塊和計劃實現(xiàn)的模塊分別以實線框和虛線框表示；空間數(shù)據(jù)庫服務器，包括MapInfo，ESRI/Oracle SDE，Informix-Illustra以及其它空間數(shù)據(jù)庫引擎；存儲非空間數(shù)據(jù)、空間數(shù)據(jù)和概念層次的數(shù)據(jù)庫和知識庫. Graphic User InterfaceSpatial DB HierarchyNon-Spatial DBGeo-ComparatorGeo-CharacterizerGeo-ClassifierGeo-Cluster AnalyzerGeo-Associator Future Modules Future Module

27、s Spatial Database and Cube Server地理數(shù)據(jù)挖掘查詢語言GMQL GMQL（Geo-Mining Query Language） Han等人為了挖掘地理空間數(shù)據(jù)庫而設計，成功應用于空間數(shù)據(jù)挖掘系統(tǒng)原型GeoMiner中是對空間SQL的擴展，可作為制定SDMQL的基礎，以進一步界定SDMQL語言的基本原語mine characteristic rules type of rule (characteristic, discriminant, association, clustering, classification)for “Description of st

28、ates along I 80 highway”from us_hiway, states_census SQL like from, where clauseswhere states_census.obj intersects us_hiway.obj high level concepts and and highway = I 80” spatial joins may be usedwith respect to states_census.obj, state_name, pop90, capita_income list of relevant attributesset attribute threshold 51 fo