探讨资料采矿技术应用於时空资料分析之研究.pdf

探探探探討資討資料料料料採礦採礦技技技技術應術應用於用於用於用於時時空空空空資資料分析之研究料分析之研究料分析之研究料分析之研究 壹、前言 Baher EI-Geresy and Christopher Jones的文章中提到時空的定義包含 空間維度spatial axis， 時間維度temporal axis， 物件維度features axis三個維度 。 可以用各種查詢語言Queries來定義並描述出以維度所組成的定義範圍search space， 各領域專家進一步設計模組models來解決更加複雜的查詢問題。 因此本 篇文章特別針對時空spatial-temporal所有相關文獻談到查詢問題和模組model 設計來找出時空分析問題的範圍。 時空資料庫spatial temporal data base可以從時空現象來談可以分為三種基本 類型位置分析the where view、物件分析the what view、時間分析the when view。1.The where view 位置分析主要探討物件確切的空間位置Location based model。2.The what view物件特性分析主要探討物件的特徵或特性Object feature based model 。3.The snapshot view瞬間分析主要討論某一時間點物件 的特性Time based model。4.The when view時間的分析主要討論事件和事件 之間的關聯性Relationship between events。 從時空的行為來談可以分為三種基本類型 1.物件功能分析The Functional view就空間位置關係而言，經過若干時間之後各物件位置已經改變。2.物件 趨勢The trend view 各物件的特性跟著時間進行出現了變化。 3.物件的行為探 討The Behavior view針對所有時空背景下的物件所改變的現象或行為進行分 析探討 我們最後目的要推論和展示出時間及空間下的關係，這些時空的行為也 可以稱為模式pattern，這些模式可以在時間不同而進行改變，但是如何顯現展 示時間及空間的模式仍舊尚待繼續研究獲得解決。 貳、問題探討 [Cristophe Claramunt 2000 ]時空的關係表示Temporal and spatial relationship 必須先從時間的關係表示談起，時間的區間和時間操作運算包含{相等equals、 先前before、相遇meets、涵蓋overlaps、期間during、開始starts、結束 finishes}。2.空間的操作運算關係表示包含{相等equal、接觸touch、完全包 含in、部分包含contain、覆蓋cover、被覆蓋covered、完全重疊overlap、 完全分開disjoint} 進一步綜合時間和空間兩者的關係可以得到時空的關係表 示Representation of temporal spaces 時空關係表示包含有兩物件相等EQUAL、 兩物件接觸TOUCH、A 物件被包含於 B 物件IN、A 物件包含 B 物件CON、 兩物件只有部分覆蓋CVR、被覆蓋CVRD、兩物件重疊OVLP、兩物件完全 2006 電子商務與數位生活研討會 - 2 - 分開DISJ等等。根據實際情況推論統計後得到空間的位向關係 8 種，時間的關 係 7 種，時空的關係卻高達有 84 種，在此限於篇幅無法完全列出。時空資料探 勘所分析得到的規則涵蓋了上述所有可能發生的時空關係。 二維空間的實際應用分析，時空關係分析可以從時間維度的遞移性開始，例 如人口變化、商業移動改變的現象探討等。在同時具有時間和空間以及其他屬性 維度的應用領域之下， 研究問題必須能同時包含時間維度和空間維度所有的語意 查詢才能稱為具有一般性。 至於探討造成如此結果背後的原因則必須從時空的轉 換改變來探討，分為以下兩種情形來進行討論。1. 第一種是開始和結束狀態的 推論由物件在開始或結束的狀態下，探討造成最後呈現的結果所造成的原因。 2. 第二種是轉換改變的探討 從空間維度位置關係改變以及時間維度關係改變 來推論時空維度的時空關係改變， 在關係改變之間必定存在轉換改變機制而造成 最後的結果。 參、方法探討 時空資料探勘分析的基本範例做法Rules type尋找時空關係規則的方法可 以分類為改良資料探勘基本概念、資料型態符合時空資料要求，至於維度提高和 複雜度提高都是必須面對的挑戰。 第一類關聯法則分析由Agrawal 在1993 年提出，主要目的是從龐大銷售交 易記錄資料庫中，尋找銷售項目間令人感到有興趣的關聯或相互關係（Agrawal, 1993）。最典型的應用是市場購物籃分析（Han and Kamber, 2001），它利用關 聯法則能從項目相對發生的次數與數量，找出原本未知的關係法則，做為進一步 預測的依據與作決策時的參考，如此將有助於提昇決策的品質。例如牛奶、麵 包（support 20 , confidence80），其中支持度support 20，表示在全部 的交易記錄中， 顧客同時買牛奶和麵包的比例為20； 而信賴度confidence 80， 表示在顧客買了牛奶的前提下，再買麵包的比例為80。關聯法則就是在項目間 探尋滿足最小支持度和最小信賴度的規則。關聯法則的描述如下令I { I, I2, .Im}是所有商品項目 （items） 的集合，D是資料庫中所有交易記錄 （transaction） T的集合，T為I的子集合。一個集合X⊆I稱為項目集（itemset），此項目集 所包含的物品項目之個數稱為此項目集的長度， 若其長度為k， 則稱此項目集為k- 項目集（k-itemset）。關聯法則的型式可以表示為X⇒Y，X,Y⊆ I且X∩Y O。關 聯法則含有支持度（support）與信賴度（confidence）兩個參數。支持度是指在X 和Y兩項目集同時在交易記錄D出現的次數與交易記錄D的交易總筆數的比。 支持度代表事件的發生機率，介於0 100之間；信賴度為X和Y兩項目集在 交易記錄D同時出現的次數與X項目集在交易記錄D出現的次數比。信賴度代 2006 電子商務與數位生活研討會 - 3 - 表已發生某事件的情況下，另一事件發生的機率，亦介於0 100之間。關聯 法則是否有意義，端視其支持度是否超過支持度門檻值（minimum support）及 信賴度是否大於最小的信賴度門檻值（minimum confidence）而定。支持度門檻 值及信賴度門檻值之設定是很重要的，當支持度門檻值設太低時，會將重要性較 低之項目也包含進來，而設太高又怕因此而失去某些重要規則。Han and Kamber （2001）認為門檻值的設定需依據使用者的需求而定。至於關聯法則的產生，主 要是經由以下兩個步驟1.辨識高頻項目集合Agrawal et al., （1993）指出辨 識常出現的項目集合為從資料庫中找出大於或等於支持度門檻值的高頻項目集 合（Frequent itemsets）。2.產生關聯法則使用前一步驟所發現高頻率出現項 目集合，並依據使用者所訂之信賴度，以產生關聯法則。當此方法針對時空資料 進行分析時，關聯法則必須考量空間位向關係和時間發生前後關係，綜合考量兩 者關係後，推論時空關係結果。購物籃分析法則基本上已經具備時間關係的成分， 必須另外考量改善的部分是如何加入空間位向關係將是未來本研究的重要方向。 第二類聚類群聚clustering是把有形或抽象的物件歸類到類似物件的類別的 過程；將類似物件集合成同群，不同群物件的集合不相似，群聚與分類最大不同 是，群聚不預先知道類別標籤，而把資料歸類成新類別。例如可透過數學方法來 尋找空間物件的相似性，而分析最終目的是將資料進行分類的工作。基於模式而 言，分群目前依方法分類有下列五種，探討如下1分割方法Partitioning此 種為亦稱非層次化方法， 目標通常是將資料分割到類似小組裡，創造分群的集合 。 K-means 企圖把一套資料分成子集，因此在給定的子集之內指向在對其他子集的 成員顯著地不同時對彼此有一定程度的相似之處。這樣的子集通常叫作一分群， 它優點是很快速。K-means 的步驟由使用者設定要找多少個群組，設要找 K 個 群組在資料庫中以亂數找出 K 個點來當作初始的質心，驗證這 K 個點是否為最 後之 質心， 如果 是則完 成， 如果否則繼 續尋找，直 到都符合為 止。 CLARANSClustering LargeApplications Based upon Randomized Search起源於兩 演 算 法 ， PAMPartitioning Around Medoids 及 CLARAClust-ering Large Application，CLARANS 的缺點是被群聚的過程都在暫存記憶體中，因此計算 二分群間總距離總是代價高。 2階層方法Hierarchical將資料組織到大群組裡，大群組裡含有更小的群 組並且依此類推，此種群聚過程稱之。以歐式距離Euclidean distance計算相似 度，方法分成凝聚法agglomerative為 bottom up 及分散法divise為 top down。 BIRCHBalanced Iterative Reducing and Clustering [Zhang 96] 提 出 Clustering FeatureCF 及 CF 樹概念，CF 代表子分群，動態建一平衡壓縮的 CF 樹然後對 葉節點群聚，焦點在以代表物體減少考慮的物體的數目，集中於有關分群和一分 群擁有貢獻物體可減短查詢。CF 樹與 CLARANS 合用有不錯的效能。 3傳統群聚法最喜歡球狀和類似的分群尺寸， 或對於outliers易破碎。CURE 2006 電子商務與數位生活研討會 - 4 - [Guha 98]能處理非球形的形狀和變化尺寸，對於outliers較健全，它不處理 categorical屬性，忽視兩不同分群物件間的聚集aggregate互連的資訊。而 ROCK[Guha 99] 處理categorical屬性，基於互連度而合併兩分群， 當強調互連時 ， 忽視兩不同分群的相似資訊。Chameleon[Karypis99]使用動態模式，主要改善 CURE及ROCK的上述缺點。 4密度基礎方法density-basedDBSCAN[Ester96]它將含有雜訊之空間資 料，選出高密度區域為任何形狀之分群。DBSCAN 交給使用者從已發現可接受 之分群中去決定參數，這些參數常以經驗或觀察為依據，因此很難去決定，為 了解決此問題，Optics[Ankerst99]計算一個密度基礎的分群順序，它擴充 DBSCAN，根據此順序自動去處理參數。Optics 結構與 DBSCAN 相等，時間複 雜度一樣。DENCLUE[Hinneburg98]將資料存到 cell 中成樹狀存取結構較 DBSCAN 快速。格子基礎方法Grid-based STING[Wang97]探索存在格子 cell 的 統計資訊，其缺點是分群形狀其邊不是水平就是垂直，此點儘管有快速時間，但 會有損及其品質及正確率。WaveCluster[Sheikholeslami98] 採密度及格子基礎方 式群聚，透過小波轉換法群聚物件，它較 BIRCH、DBSCAN 及 CLARNS 佳，可 處理到 20 維度。CLIQUE[Agrawal98]透過整合高密度及格子基礎方式群聚，擅 長於大型高維度資料庫，它可自動發現最高維度的子空間有高密度分群，維度增 加亦有好的延展性，但因方法簡單化的代價即會降低正確率。 5模式基礎方法Model-basedCOBWEB [Fisher87] 輸出一樹，以機率概 念描述樹節點，根據 category utility 每一層分群再被分割，此舉可最大化推論能 力。COBWEB 以分類樹的形式進行群聚；但它處理離散的屬性資料。 CLASSIT[Gennari89]以連續資料作遞增式群聚擴充 COBWEB，但同 COBWEB 一樣無法處理大型資料庫。 聚類分析可以採用上述提供的方法將時間維度，空間維度和屬性資料維度同 時進行處理，但是必須注意到時間維度和空間維度資料必須先進行前處理，前處 理指的是將時間維度的規格適當化，時間的規格代表意義在於長期、中期或短期 的分析都會直接影響到最後的結果。另外空間維度資料也必需進行單位規格統 一，特別是座標資料必須進行一致化，空間資料型態點線面資料考量跟設計方法 論有很大關係，也是未來本研究的重要項目，接下來將繼續討論時空資料分析過 程將遭遇的問題。 肆、問題討論 在 關 聯 法 則 Spatial-temporal associations 和 聚 類 分 析 Spatial-temporal clustering，針對時空資料進行分析過程中發現存在一些問題。 1Meta-Rules 的問題時空資料探勘因為資料維度增加，資料量也大幅增加， 結果容易出現產生太多的規則，如何篩選以及改良的解決步驟，將是研究主要目 2006 電子商務與數位生活研討會 - 5 - 標，解決的方法是從眾多的時空資料探勘的規則進行歸納分析，採用屬性導向的 歸納演算法，過濾重新組合所有規則，換句話說，將產生的規則視為原始資料， 再進行一次歸納分析得到更準確的規則。 時空關聯分析過程中如果產生過多的規則，可以直接調整門檻值，例如最小 信心度和最小支援度，重新校正過後的結果將會產生更少數而且更高階的規則， 對下一步驟規則的評估有很大的幫助，至於在時空聚類分析的過程中，同樣也會 遭遇到類似的問題，也可以藉由調整內部的分類的判斷值來產生更合理的群聚 數。 2如果依照地理資訊系統GIS解決時空分析問題的想法提升維度數目 Dimensioning-up從空間座標維度新增時間軸的方式來解決問題，可能會得到比 較不理想的結果，因為某一部分資料存在時間維度和空間維度可能具有些前後相 接的關係context，如果使用加入時間維度的分析方式並無法找出時空關聯的現 象關係，為什麼在解決時空問題的時候時間和空間因素之間不應該分離因為從 地球科學的角度來看，地球本身是空間維度，但是地球經由公轉以及自轉形成時 間維度，所以其實時間和空間具有不可分割的特性。 3時間軸的資料前處理Temporal Re-scale做法時間資料的特性跟一般屬 性資料有很大的不同，時間單位小至毫秒，長至數年甚至世紀，比例的大小影響 不容忽視，所以進行資料分析之前必須先瞭解資料的時間性質，設定合理時間軸 規格才能得到較合理的結果。 時空資料探勘技術的應用可以包含1.普遍的幾何知識普遍的幾何知識是 指某類目標的數量、大小、形態特徵等的普遍的幾何特徵。計算和統計出時空間 目標幾何特徵量的最小值、最大值、均值、方差、眾數等,還可統計出特徵量的 直方圖。2.時空間分佈規律空間分佈規律是指目標在地理空間的分佈規律,分成 在垂直向、水平向以及垂直向和水平向的聯合分佈規律。垂直向分佈即地物沿高 程帶的分佈,如植被沿高程帶分佈規律、植被沿坡度坡向分佈規律等;水平向分佈 指地物在平面區域的分佈規律,如不同區域農作物的差異、公用設施的城鄉差異 等。3.空間關聯規律它是指空間目標間相鄰項鏈、共生、包含等空間關聯規則 。 例如,村落與道路相連,道路與河流的交叉處是橋樑等。4. 空間聚類規則或空間 分類規則 是指特徵相近的空間目標聚類成上一級類的規則, 可用於 GIS 的空間 概括和綜合。例如,將距離很近的散佈的居民點聚類成居民區。5. 時空間特徵 規則 它是指某類或幾類空間目標的幾何和屬性的普遍特徵, 即共性的描述。普 遍的幾何知識屬於空間特徵的一類,作用十分重要。由於它在遙感影像解譯中,所 以分離出來的單獨作為一類知識。6. 時空間區分規則 它指兩類或多類目標間 幾何的或屬性的不同特徵, 即可以區分不同目標的特徵。7. 時空間演變規則 2006 電子商務與數位生活研討會 - 6 - 若 GIS 資料庫指時空資料庫或 GIS 資料庫中存有同一地區多個時間資料的快照 Snapshot ,則可以發現空間演變規則。時空間演變規則指空間目標依時間的變化 規則,即哪些地區易變,哪些地區不易變,哪些目標易變及怎麼變,哪些目標固定不 變。 伍、結論 90年代初期，GIS 時空分析能力著重在利用既有開發的時空分析模組直接整 合在 GIS 軟體中。對於 GIS 時空分析模式整體概念的建構，與如何落實與地理 學觀念的結合並沒有太多討論。 這些模式和 GIS 軟體間， 因為普遍缺乏對人類思 考、 學習、 交換時空資訊與知識的認知概念， 如何以數位系統的方式表達與執行 ， 彼此在資料、 功能、 與使用上， 經常顯得格格不入而難以有效整合Anselin, 2000。 1995 年 NCGIA 在美國倡議將 GIS 提昇到科學的地位NCGIA, 1995，強調以數 位化的方法，完整呈現人對地理概念的深層認知，發展新的概念化方法 Conceptualization、技術，不但能快速取得並整合大量時空資訊，並能有效的進 行環境問題的分析與預測， 得到領域專家信任的結論， 讓 GIS 在地理學研究的角 色，從理想世界的時空分析，逐漸走向對真實世界的理解。對於複雜地理問題的 研究，不論採用哪一種方法和數學模型，都很難描述這個真實的世界。唯有充分 運用大量地理資料庫的支援、 快速電腦運算儲存的能力、 綜合多種 GIS 時空分析 研究方法、引進資料探勘相關模式，進而統合相關領域的研究成果，建立 GIS 面對複雜問題的整合時空分析模式，才能面對真實世界的環境問題。研究時空資 料分析目前有幾個領域發表研究成果討論包括1人工智慧方法2時間資料庫 方法 3時間地理資訊系統整合 4資料探勘方法。資料探勘對於資料時空性質 的運作，必須以可適用於時空計算之演算法的發展為基礎，這類結合運算及資料 庫的研究提出一個結合時空知識的判斷機制。在過去一直是資料探勘相關研討會 的重點之一，有相當研究討論資料探索data mining 及時空間分析之議題，由於 現今資料取得容易，但卻缺乏足夠智慧之機制轉換為資訊，所以時空的資料探索 spatial temporal data exploration將會是未來研究的重點，應用層面也可能擴及任 何資訊系統應用領域。 陸、參考文獻 A. Hinneburg and D.A.Keim,An efficient approach to Clustering inLarge multimedia Databases with Noise.KDD98 , 1998, pp.58-65. Bartlett, D., Space, time, chaos and coastal GIS.InProceedings 16thInternational Cartography Conference, 1993, pp.539-555 2006 電子商務與數位生活研討會 - 7 - Barry de ville, Microsoft Data Mining - Integrated Business Intelligence for e- Commerce and Knowledge Management, Digital Press, Butterworth-Heinemann. 2001, pp. 24-55 Bather EI-Geresy and Christopher Jones, Models and Queries in a spatio-temporal GIS, In GIS and Geocomputation, Edited by Peter Atkinson and David martin , 2000, pp.27-39, Christophe Claramunt and Bin Jiang, A representation of relationships in temporal spaces, In GIS and Geocomputation, Edited by Peter Atkinson and David martin , 2000, pp.41-53 D. Fisher. Knowledge acquisition via incremental conceptual clustering. Machine Learning, 2 1987,pp.139-172. Fenzhen Sua, Chenghu Zhoua, Vincent Lyne b, Yunyan Dua, Wenzhong Shi, “A data-mining approach to determine the spatio-temporal relationship between environmental factors and fish distribution”,Ecological Modelling,174, 2004, pp421-431 Feng Qi and A-xing Zhu, “Knowledge discovery from soil maps using inductive learning”,Int. J. Geographical Ination Science, vol. 17, no. 8, 2003, pp.771 795 Guha, Sudipto; Rastogi, Rajeev; Shim, Kyuseok; “ROCKARobust Clustering Algorithm For Categorical Attribute,“ Proceedings - International Confer ence on Data Engineering Proceedings of the 1999 15th International Conference on Data Engineering, ICDE-99 Mar 23-Mar 26 1999 H. Samet, The Design and Analysis of Spatial Data Structures, Addison-Wesley. 1990 Jiawei Han and Micheline Kamber,Data Mining Concepts and Techniques, Fraser University,morankaufmannpublishers,2001, pp.45-61 JohnF.Roddick and Brian G. Lees, Paradigms for spatial and spatio-temporal data mining,InGeographic Data Mining and Knowledge Discovery Edited By Harvey J.Miller, Jiawei Han,2001,,London and NewYork,pp.33-50 J. Han, K. Koperski, and N. Stefanovic, , “GeoMiner a system prototype for spatial data mining,”ACM-SIGMOND, 1997 , pp. 553-556. J Gennari,P.Langley, and D. Fisher,. Moddels of incremental concept ation.I Artificial Intelligence, vol.40, 1989,pp.11-61. 2006 電子商務與數位生活研討會 - 8 - Jussi Rasinmaki, “Modelling spatio-temporal environmental data”,Environmental Modelling Han, Eui-Hong; Kumar, Vipin “Chameleon Hierar chical Clustering Using Dynamic ModelingI,“ Computer v 32n8 1999,IEEE M. Kanevski, ,“Environmental data mining and modeling based on machine learning algorithms and geostatistics”,Environmental Modelling Software, 19, 2004, pp.845–855 MacQueen, J.B., “Some s for Classification and Analy sis of Multivariate Observations,“Proceedings of the Fifth Berkeley Symposium on Mathematical StatisticsandProbability,1, 1967,pp.281-297. Martin Ester, Hans-Peter Kriegel and Jorg Sander, Algorithms and applications for spatial data mining,InGeographic Data Mining and Knowledge Discovery Edited By HarveyJ.Miller,Jiawei Han,London andNewYork,2001,pp.161-187 M. Ankerst, M. Breunig,H.-P.Kriegel, andJ.Sander.OpticsOrder ing points to identify the clustering structure, SIGMOD’99. Martin Ester, Hans-Peter Kriegel, JrgSander, Xiaowei XuADensity-Based Algorithm for Discovering ClustersinLarge Spatial Databases with Noise. KDD 1996 226-231 Openshaw, S.,. Artificial Intelligence in Geography. Wiley, London., 1997 Openshaw, S., See, L.,. Applying soft computing approaches to river level forecasting. Hydrological Sciences Journal44 5, 1999, pp.763–778. P. W. Eklund, S. D. Kirkby and A. Salim“Data mining and soil salinity analysis” Int. J. Geographical Ination Science, vol. 12, no. 3, 1998,pp 247 268 Quinlan J.R., Induction of decision tree.Machine Learning, 181-106, 1986 Quinlan J.R., C4.5 Programs for Machine Learning, San Mateo, CA Morgan Kaufmann., 1993 Quinlan J.R., See5 An Inal Tutorial. Accessed at , 2001 S. Kawano, “A context-dependent knowledge model for uation of regional environment”,Environmental Modelling Software, 20, 2005, pp.343-352 S. Agarwal, R. Agarwal, P.M. Deshpande, G. Gupta, J.F. Naughton, R. Ramakrishnan, 2006 電子商務與數位生活研討會 - 9 - and S. Sarawagi, “On the computation of multidimensional aggregates,”VLDB, 1996, pp. 506-521. See, L., Abrahart, R.J.,. Multi-model data fusion for hydrological forecasting. Computers Geosciences27 8, 2001, pp. 987–994. Tian Zhang, Raghu Ramakrishnan, Miron Livny,“ BIRCH An Efficient Data Clustering forVeryLarge Databases,“SIGMOD Conf.1996 pp.103-114 . V.G.Lyubartsev,V.L.Vladymyrov, Multidisciplinary marine environmental database forAral Sea,Journal of Marine Systems,47, 2004, pp.3-9 Vladimirov, V.L., Miroshnichenko, V.V.,. Multipurpose database management systems for the marine environmental research. In Harmancioglu, N.B., Alpaslan, M.N., Ozgul, S.D., Singh, V.P. Eds., Integrated Approach to Environmental Data Management Systems. Proceedings of the NATO ARW. Kluwer Academic Publishing, Dordrecht, 1997, pp. 355– 364. W.Wang,Yang, R.Muntz, STINGAStatistical Ination grid Approach to Spatial Data Mining, VLDB’97 Wright, D.J.and Goodchild,M.F.,Data from the deep implications for the GIS community.International Journal of Geographical Ination Science,Vol11, 1997, pp. 523-528.