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

《dbscan空间聚类演算法及其在城市规划中的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、DBSCAN空間聚類演算法及其在城市規劃中的應用學生：林嘉韋空間分析期中報告2007.04.24測繪科學，第30卷第3期，李新延、李德仁簡報大綱摘要引言DBSCAN演算法DBSCAN演算法的實做DBSCAN演算法在城市規劃中的應用研究結論心得摘要本文介紹了DBSCAN演算法的基本概念和原理，然後將此演算法應用在城市規劃中，對某城市中小學和商業設施等公共設施進行群聚分析，最後針對分析結果進行討論。引言空間資料挖掘（spatialdatamining）是指從空間資料庫中自動或半自動的挖掘事出先未知卻

2、潛在有用資訊的空間分析模式。主要包括空間的關聯、特徵、分類和群聚等規則，而空間群聚是資料挖掘的方法之一，近年來有越來越多相關的研究，逐漸的受到大家的重視。引言從相關文獻中可知目前有許多不同的群聚演算法，主要可以分為以下五類：分割法（partitioningmethod）階層法（hierarchicalmethod）密度基礎演算法（density-basedmethod）網格基礎演算法（grid-basedmethod）模式基礎演算法（model-basedmethod）本文所採用的是一種以密度為

3、基礎的空間群聚方法－DBSCAN演算法的實現與應用。DBSCAN演算法此演算法將具有高密度的區域劃分為群落，並可在帶有雜訊的空間資料庫中發掘任意形狀的群聚。藉由Eps（搜尋半徑）、MinPts（最小點數）兩個參數值來針對每個點做全域的搜尋，即可快速的得到分群的結果。DBSCAN演算法以下介紹DBSCAN演算法的基本概念：Eps-neighbor：空間中任意一點p的Eps-鄰域是指以p為圓心，以Eps為半徑的區域內包含點的集合，記作Neps(p)={q∈D

4、dist(p,q)≤Eps}，其中D是點

5、的集合。corepoint&borderpoint：若一點p的Eps-鄰域至少包含最小數目的MinPts個點，則稱p為核心點，否則稱其為邊界點。DBSCAN演算法directlydensity-reachable：給定一個點集合D，若p是在q的Eps-鄰域內，而q是一個核心點，稱點p從q是直接密度可到達的。density-reachable：密度可到達其定義為，若存在一連串的點p1,…,pn，其中p1=q，pn=p，使得pi+1可由pi直接密度可到達。pqMinPts=5Eps=1cmpqp1D

6、BSCAN演算法density-connected：在Eps和MinPts的條件下，若點集合D中存在一個點o，使得點p和q是從點o密度可到達的，則稱點p和點q是密度可連接的。pqopandqdensity-connectedtoeachotherbyoDBSCAN演算法cluster：點集合D中的非空集合C為一個群聚，當C滿足以下條件時對於∀p,q，若p∈C且q是由p”密度可到達”的話，則q∈C。對於∀p,q，p,q皆屬於C，則點p和點q是密度可連接的。noise：雜訊的定義是指在資料庫內的點所

7、形成的集合，其不能包含於資料庫內任何一個“群”內，意即noise={p∈D

8、∀I:p∉Ci,I=1,2,3,…,k}DBSCAN演算法的步驟初始化設置：建立原始資料庫Origin，在屬性資料庫中增加一新字段ClusterID，以儲存聚類結果，其原始值為0。定義搜尋資料庫Search，用來儲存檢索結果。初始化參數Eps和MinPts。DBSCAN演算法的步驟遍歷Origin，依次將每個點作為種子點進行考察，i=1,j=1,cluster=1：對於點pi，若pi．ClusterID=0，搜尋其Eps

9、-鄰域，若Neps(pi)≧MinPts，則點pi為核心點，pi．ClusterID=cluster，將pi的Eps-鄰域包含的所有點存入Search中。DBSCAN演算法的步驟遍歷Search，將每個點作為種子點進行考察，對於點qi，若qi．ClusterID=0，搜尋其Eps-鄰域，若Neps(qi)≧MinPts，則qi也是一個核心點，同時它是pi的直接密度可到達點，與pi同屬一類，否則為邊界點。j=j+1，若Search為非空集合，執行上一步驟DBSCAN演算法的步驟i=i+1，clus

10、ter=cluster+1，執行步驟2），直到遍歷完資料庫Origin刪除搜尋資料庫Search。群聚結束，Origin屬性資料庫中紀錄了聚類結果，其中ClusterID值為0的即為雜訊。DBSCAN演算法的實做本文選取了四組資料來進行測試DBSCAN演算法的實做DBSCAN演算法在城市規劃中的應用研究本文提出城市規劃的重要內容在於各項基礎設施和配套設施的綜合安排以及合理布局。根據使用性質的不同，本文將各項基礎設施分為：公共服務設施、市政設施、市政設施、交通設施等。根據其服務範圍及等級的不同，又