DBSCAN空间聚类演算法及其在城市规划中的应用.ppt

DBSCAN空間聚類演算法及其在城市規劃中的應用,學生：林嘉韋,空間分析期中報告,2007.04.24,測繪科學，第30卷第3期，李新延、李德仁,簡報大綱,摘要 引言 DBSCAN演算法 DBSCAN演算法的實做 DBSCAN演算法在城市規劃中的應用研究 結論 心得,摘要,本文介紹了DBSCAN演算法的基本概念和原理，然後將此演算法應用在城市規劃中，對某城市中小學和商業設施等公共設施進行群聚分析，最後針對分析結果進行討論。,引言,空間資料挖掘（spatial data mining）是指從空間資料庫中自動或半自動的挖掘事出先未知卻潛在有用資訊的空間分析模式。 主要包括空間的關聯、特徵、分類和群聚等規則，而空間群聚是資料挖掘的方法之一，近年來有越來越多相關的研究，逐漸的受到大家的重視。,引言,從相關文獻中可知目前有許多不同的群聚演算法，主要可以分為以下五類： 分割法（partitioning method） 階層法（hierarchical method） 密度基礎演算法（density-based method） 網格基礎演算法（grid-based method） 模式基礎演算法（model-based method） 本文所採用的是一種以密度為基礎的空間群聚方法DBSCAN演算法的實現與應用。,DBSCAN演算法,此演算法將具有高密度的區域劃分為群落，並可在帶有雜訊的空間資料庫中發掘任意形狀的群聚。 藉由Eps（搜尋半徑）、MinPts（最小點數）兩個參數值來針對每個點做全域的搜尋，即可快速的得到分群的結果。,DBSCAN演算法,以下介紹DBSCAN演算法的基本概念： Eps-neighbor：空間中任意一點p的Eps-鄰域是指以p為圓心，以Eps為半徑的區域內包含點的集合，記作Neps(p)=qD | dist(p,q) Eps ，其中D是點的集合。 core point & border point：若一點p的Eps-鄰域至少包含最小數目的MinPts個點，則稱p為核心點，否則稱其為邊界點。,DBSCAN演算法,directly density-reachable：給定一個點集合D，若p是在q的Eps-鄰域內，而q是一個核心點，稱點p從q是直接密度可到達的。 density-reachable：密度可到達其定義為，若存在一連串的點p1 ,pn，其中p1 = q，pn = p，使得pi+1 可由pi直接密度可到達。,MinPts = 5 Eps = 1 cm,DBSCAN演算法,density-connected：在Eps和MinPts的條件下，若點集合D中存在一個點o，使得點p和q是從點o密度可到達的，則稱點p和點q是密度可連接的。,p and q density-connected to each other by o,DBSCAN演算法,cluster：點集合D中的非空集合C為一個群聚，當C滿足以下條件時 對於 p , q，若pC且q是由p”密度可到達”的話，則qC。 對於 p , q，p ,q皆屬於 C，則點p和點q是密度可連接的。 noise：雜訊的定義是指在資料庫內的點所形成的集合，其不能包含於資料庫內任何一個 “群” 內，意即noise=pD |I: pCi, I= 1,2,3,k ,DBSCAN演算法的步驟,初始化設置： 建立原始資料庫Origin，在屬性資料庫中增加一新字段ClusterID，以儲存聚類結果，其原始值為0。 定義搜尋資料庫Search，用來儲存檢索結果。 初始化參數Eps和MinPts。,DBSCAN演算法的步驟,遍歷Origin，依次將每個點作為種子點進行考察，i=1,j=1, cluster=1： 對於點pi，若piClusterID=0，搜尋其Eps-鄰域，若Neps(pi) MinPts，則點pi為核心點， piClusterID=cluster，將pi的Eps-鄰域包含的所有點存入Search中。,DBSCAN演算法的步驟,遍歷Search，將每個點作為種子點進行考察，對於點qi，若qiClusterID=0，搜尋其Eps-鄰域，若Neps(qi) MinPts，則qi也是一個核心點，同時它是pi的直接密度可到達點，與pi同屬一類，否則為邊界點。 j=j+1，若Search為非空集合，執行上一步驟,DBSCAN演算法的步驟,i=i+1，cluster=cluster+1，執行步驟 2），直到遍歷完資料庫Origin 刪除搜尋資料庫Search。 群聚結束，Origin屬性資料庫中紀錄了聚類結果，其中ClusterID值為0的即為雜訊。,DBSCAN演算法的實做,本文選取了四組資料來進行測試,DBSCAN演算法的實做,DBSCAN演算法在城市規劃中的應用研究,本文提出城市規劃的重要內容在於各項基礎設施和配套設施的綜合安排以及合理布局。 根據使用性質的不同，本文將各項基礎設施分為：公共服務設施、市政設施、市政設施、交通設施等。 根據其服務範圍及等級的不同，又可分為市級、居住區級以及小區級。,案例研究,本文以某城市中的小學、中學以及商業設施為例，來探討其聚集的程度和分布的模式。,參數設定： Eps = 500m MinPts = 2,案例研究,由圖中可看出小學的分佈較為平均，但在老城區的學校分佈密度較大，其服務半徑不到200m，按照都市計畫規定小學位於居住小區域，其服務半徑以500m較為合理，因此需要適當的調整。 但老城區的人口稠密，因此服務半徑以300m至400m為最適當，而在非城市核心區其服務半徑可適當的提高。,案例研究,本文以某城市中的小學、中學以及商業設施為例，來探討其聚集的程度和分布的模式。,參數設定： Eps = 1000m MinPts = 2,案例研究,結果顯示，在老城區55.8%的學校服務半徑在500m以內，88.6%的學校服務半徑在800m以內。而在非城市核心區，服務半徑在1000m以內的只有40%，60%的學校服務半徑在1500m以內。 因此可以界定老城區的中學服務半徑以800m為上限，而在非城市核心區則以1500m2000m為宜。,案例研究,本文以某城市中的小學、中學以及商業設施為例，來探討其聚集的程度和分布的模式。,參數設定： Eps = 400m MinPts = 3,案例研究,該城市商業設施主要聚集在城市核心區，尤其是老城區及其周邊地區，有將近97%的商業設施位於此範圍內。 在實驗中得知，當Eps取400m，MinPts取3時，可以得到最佳的群聚效果。在圖17中，第18類的總數佔了8.3%，構成主要的商業中心，另外第8、4、3、12、9所佔比例為3%6%之間，成為次級的商業中心。,結論,本文探討DBSCAN演算法的原理和其實驗的過程，將其應用在城市規劃領域上，可以對城市中公共設施和市政公用設施的聚集特徵和分佈模式進行研究。 除此之外，透過對群聚結果的分析，可以對規劃設計的某些規範或指標進行修正，對城市規劃提供一個較為科學的依據和指導。,心得,DBSCA