文档介绍：上海交通大学
硕士学位论文
DBSCAN算法及在城市网格化管理中的应用
姓名:黄毅磊
申请学位级别:硕士
专业:软件工程
指导教师:蔡鸿明;王洪深
20091201
DBSCAN 算法及在城市网格化管理中的应用

DBSCAN 算法及在城市网格化管理中的应用

摘要

城市网格化管理新模式的诞生,改变了以往的城市管理方式,城市管理工作由被动
转为了主动。与之相配套的城市网格化管理信息系统,经过几年来的运行,积累了海量
的业务数据,其中很大部份是空间数据。对这些数据进行空间聚类可以发现城市管理问
题的高发区域。
针对这一需求,本文结合城市网格化管理信息系统的数据特点和空间聚类应用的目
的,设计和实现了一个基于ArcGIS的空间聚类分析工具,其核心算法选择了基于密度的
DBSCAN(Density-Based Spatial Clustering of Applications with Noise)算法。在设计该
核心算法时,本文考虑了与算法实现相关的两个因素:(1)内存开销:算法执行过程
中,需要计算数据集中点和点之间的距离,因此,重点讨论了采用上三角矩阵与n阶方
阵在存储点与点之间的距离时,给算法带来的不同影响,由于采用上三角矩阵在整体上
优于n阶方阵,故采用上三角矩阵保存点和点之间的距离;(2)快速排序:当需要调整
与算法相关的两个参数MinPts(密度阈值)和Eps(邻域半径)对同一数据集进行多次
空间聚类分析时,需要对某点与数据集中其他点之间的距离进行排序,能为以后的判断
节省时间,据此对采用何种排序方法进行了讨论,最终选取了基于三个记录关键字的中
值的快速排序,并在快速排序中递归快要结束时,改用直接选择排序完成最后的排序过
程。本文根据DBSCAN算法的基本思路,设计实现了该算法,对算法的执行过程进行了
详细地描述,给出了算法的核心代码。另外,为了能方便地从城市网格化管理信息系统
中获取分析用数据,以及能够形象化地展现空间聚类结果,DBSCAN空间聚类分析工具
基于ArcGIS Engine实现了前处理(获取数据)和后处理(展现结果)。
最后,本文利用DBSCAN空间聚类分析工具对上海市浦东新区城市网格化管理信息
系统中的空间数据进行了实例分析。按照城市网格化管理的对象总体上分为事件和部件
两大类的情况,本文分别对梅园新村街道2007年四个季度的占道无照经营类问题和金杨
新村街道的废物箱所对应的空间点数据进行了空间聚类分析。前者对参数MinPts和Eps
取用不同的数值进行聚类的试算,在将聚类结果较为合理的情况下所对应的参数值确定
为后续算法使用的参数值后,分别找出了2007年四个季度占道无照经营类问题的高发区
域,并对空间聚类结果进行了环比分析和讨论,发现了城市管理工作中的不足;后者在
充分理解DBSCAN算法两个参数含义的情况下,结合废物箱的相关设置规范,确定了参
I
DBSCAN 算法及在城市网格化管理中的应用
数的取值,从而对废物箱空间设置的情况进行了检验。另外,通过DBSCAN算法的实例
应用,验证了该算法的特点,分析总结了空间聚类结果所体现出的规律。

关键词空间聚类,DBSCAN 算法,城市网格化管理,事件,部件
II
DBSCAN 算法及在城市网格化管理中的应用

DBSCAN ALGORITHM AND ITS APPLICATION
IN URBAN GRIDDING MANAGEMENT

ABSTRACT

Urban Gridding Management is a new pattern of urban management. Known form the
old pattern, it is positive. With the new pattern, a supporting IT system has been developed
which called Urban Gridding Management Information System. After several years operation,
the system has accumulated mass data. Among these data, there are a great many spatial data.
We can find out high-incidence areas of problems in urban management by using spatial
clustering.