基于密度的空间聚类算法在照明运维中的应用

对照明设施维护热点分布进行聚类分析，根据聚类结果为城市照明运维管理区域划分和运维资源规划提供参考依据。

关键词：空间聚类；基于密度；DBSCAN；照明设施维护

中图分类号：TP319

文献标识码：A

文章编号：16727800（2017）004014804

0引言 信息化系统产生大量基于位置的信息数据，这些数据具有易收集、分布广、数量大的特点，不仅拥有空间属性，而且具有时间属性，非常适合作为数据挖掘研究对象。 为适应快速发展的城市化进程，沈阳市路灯管理局持续致力于照明管理水平的创新，在2011年建成沈阳城市照明数字化综合管理系统（以下简称沈阳数字化系统），系统主要由动态的路灯监控管理系统和静态的照明设施地理信息系统组成，通过工作流柔性建模进行动、静态数据融合，实现了照明设施应急抢修和日常维护工作标准化管理。 系统自2011年7月运行以来，经过6年时间积累了海量维护事件记录。虽然这些数据具有随机性，但当数据量积累到一定程度时，其在空间上的分布会存在一定的规律性，这为城市照明管理业务的数据挖掘提供了条件[1]。对照明设施维护事件类问题进行聚类分析，从中找出高发区域，然后有针对性地分析成因，采取合理有效措施，对搞好运维工作有积极的指导作用。本文运用基于密度的空间聚类算法对沈阳数字化系统业务数据进行了研究。1相关理论 聚类分析根据数据中发现的描述对象及其关系信息，将数据对象分组，使组内相似性尽可能大，组间相似性尽可能小。组内相似性越大，组间差别越大，聚类就越好[2]。目前常用的聚类算法有基于层次的聚类算法、基于划分的聚类算法、基于密度的聚类算法等。本文研究的是基于密度的空间聚类方法——DBSCAN算法。1.1DBSCAN简介 DBSCAN（DensityBased Spatial Clustering of Application with Noise）算法是一种基于密度的空间数据聚类算法，该算法主要基于具有噪声的空间数据，目标针对高密度区域发现任意形状的簇并进行划分，定义簇为密度相连点的最大集合。该算法的中心思想是：对于某一聚类中的对象，在给定半径（Eps）的邻域内，数据对象个数必须大于某个给定值，也就是说，邻域密度必须超过某一阈值（MinPts） [3]。 DBSCAN算法主要有以下几个概念： Eps邻域：以空间中任意一点P为圆心，以Eps为半径的范围内包含的点集合。 核心点：这些点在机遇密度的簇内部。点的领域由距离函数和用户指定的距离参数Eps决定。核心点定义是：该点在给定邻域内点的个数超过给定的阈值MinPts，其中MinPts是用户指定的参数[4]。 边界点：边界点落在多个核心点邻域内，位于密度划分簇的边沿区域，它不是核心点。 噪声点：噪声点是既非核心点也非边界点的任何点。 密度可达：在DBSCAN中，P是从q（核心对象）密度可达的，如果存在对象P1，P2，P3…Pn，使得P1=q，Pn=p，Pi是从Eps和MinPts直接密度可达的，即在Pi的Eps邻域内，P1到Pn密度可达[4]。 密度相连：如果存在对象qID，使得对象P1和P2都是从q关于MinPts密度可达，则称P1、P2是关于Eps和MinPts密度相连的[2]。1.2参数选择 DBSCAN算法有两个很敏感的输入参数 Eps 和 MinPts，两个参数的选取对最终聚类的影响非常大，传统DBSCAN算法由于Eps值取决于MinPts，所以会存在以下问题：①如果MinPts设置过大，则尺寸小于MinPts的簇会标记为噪声；②如果MinPts设置过小，则邻近的噪声点可能被错误地标记为簇；③如果Eps設置过大，所有的点都会归为一个簇；④如果Eps设置过小，那么簇的数目会过多。

本文针对热点进行位置聚类，在参数选择上进行如下优化：①本文目的是为了发现热点常处的位置，根据经验，对于大部分二维位置数据集将MinPts定义为数值4；②根据照明行业管理特征，路灯设施分布较为均匀，遍布城市各个区域，因此将服务半径定义为一个合理的值300m，转换公式如下：

1.3DBSCAN聚类过程 首先将给定数据集Data中所有对象都标记为“unvisited”，DBSCAN随机选择一个未访问的对象P，标记P为“visited”，并检查P的Eps半径邻域里是否至少包含MinPts个对象。如果不是，则P标记为噪声点，否则为P创建一个新的簇C，并且把P的Eps邻域中所有对象都放在候选集合N中[5]。 接下来把N中不属于其它簇的对象依次迭代添加到簇C中。在此过程中，将N中标记为“unvisited”的对象P′标记为“visited”，并检查它的Eps邻域，如果P′的Eps邻域中至少包含MinPts个对象，则P′的Eps邻域中的对象都被添加到N中。DBSCAN继续添加对象到C，直到C不能扩展，即直到N为空。此时簇C完成生成并输出。 从剩下的对象中随机选择一个未访问的对象 P ，聚类过程继续，直到所有对象都被访问。1.4算法流程 DBSCAN算法流程如下：输入：Eps — 半径参数 MinPts — 给定点在 Eps 邻域密度阀值Data — 一个包含n个对象的数据集合输出：基于密度的簇集合方法： 标记所有对象为unvisited； Do 随机选择一个unvisited对象P； 标记P为visited； If P的Eps邻域至少有MinPts个对象创建一个新簇 C ，并把 P 添加到 C； 令 N 为 P的Eps邻域中的对象集合 For N 中每个点 P If p是unvisited； 标记p为visited If P的Eps邻域至少有MinPts个对象，把对象添加到N； If P不是任何簇的成员，把P添加到C； End For； 输出C； Else标记P为噪声点； Until没有标记为unvisited的对象2应用分析2.1数据描述 沈阳城市照明数字化综合管理系统记录了沈阳行政区划内所有照明设施维护事件，数据总量已累计达36 525条纪录，数据属性包括事件来源、事件分类、受理时间、经纬度位置等信息，具有典型的时空特性，满足数据挖掘需要，如表1所示。

2.2特征数据选择

2.2.1时空分布观察 利用MATLAB的Scatter3绘制2012-2015年沈阳路灯管理局照明设施维护事件时空分布三维图，图2为俯视图，图3为侧视图。图中X轴表示东西方向， Y轴表示南北方向， Z轴为年份。从俯视图和侧视图进行观察，除了部分边界受稀疏点影响外，整体空间分布较为平稳。

2.2.2特征年份选定 由于相对完整的数据能够更好地进行分布态势观察，所以取2012-2015年4年整年份的数据进行观察。从数据总量上看，从2012年的10 007件到2015年5 903件，事件呈现持续下降趋势，反映管理水平和设施质量提升有很大关系。为了对本文算法进行验证，取特征性最强、实效性最好的2015年事件纪录作为分析数据进行挖掘。

2.2.3特征事件选定 2015年维护事件总量达到5 903件，事件类型包括灯不亮、大面积灭灯、监控终端报警、撞杆、灯具破损、灯门破损、电缆井丢失等，如图5所示，其中个别灯不亮问题占到事件总量的70%。在充分考虑空间分布性、数据特征性等因素后决定采用个别灯不亮事件作为基于密度的空间聚类分析数据基础。

2.3基于密度聚类分析 采用DBSCAN聚类算法对2015年沈阳数字化照明系统记录的4 127个维护事件点进行聚类分析。综合考虑事件影响半径和最小事件数量后，最终将Eps半径参数设置为300m，MinPts设置为4，经过空间聚类共发现13个空间簇C1-C13，如图6所示。从基于密度的空间聚类呈现结果看，大部分簇在空间分布上具有一致性，且在重点区域呈现出密集性。只是组簇中所包含的事件空间点数量和分布范围有区别，小部分簇存在一定的差异。将聚类后的数据簇与GIS地图进行匹配，得到结果如图7所示，从热点区域分布情况看，这些空间簇聚合特征明显，大部分分布在3大聚集区域：

（1）和平区、沈河区的大部分区域， 集中在浑河以北地区。这个区域是沈阳市市中心商圈及居住地，并且有主干道青年大街，是人们经常活动的场所，人群分布集中，具有很高的聚集性，因此对照明设施故障敏感性非常强，属于重点保障区域。 （2）皇姑区与和平区、沈河区、大东区交界的条带状聚集区域，是重要的居住地，人口较密集，对路灯依赖性较高。 （3）铁西区集中了旧工业区、新兴商圈和居住区，人员流动性较大，对功能性照明质量要求较高。2.4分析结果 通过分析可以看出，事件热点区域比较一致，普遍集中在商圈、居住地、工业区等场所，这与聚类簇所反映出来的空间特征较为吻合，符合人们日常活动行为和对功能性照明需求。下面对基于密度的空间聚类结果进行深层次分析。 （1）根据聚类分析确定和识别出照明管理维护事件聚集区域，对维护事件热点进行相应的资源部署调度。对于较大范围管理，可以在统一模型参数的基础上按层次聚类分析事件热点，对不同区域进行比较分析，确定需要重点保障的区域[6]。例如以前将青年大街作为路灯管护区划分红线，红线左面区域由西城维护处管理，红线右面由东城维护处管护。经过本文分析，这样的管护区划分方式存在“西重东轻”，明显不合理，在重点区域存在“扯皮”现象。建议设立3个维护单元根据区域重新划分，或者重新调整管护区，重划红线。 （2）在不同空间下分析得到的热点分布有利于制定针对性运维策略。对小范围的事件热点，比如大东区和于洪新区，可增加区域管理和维护；而对于较大范围的聚类点，则可通过新装单灯监控、视频监控，制定针对性的巡检路线等，及时发现问题并立即处理；对于更大范围内形成的区域热点，则需要从宏观角度进行统筹规划，制定管护区划分、部署调度、应对策略等，对不同层面问题采用不同的决策方案。3结语 本文探讨了基于密度的聚类分析算法基本原理及实现过程，并将该算法应用于城市照明管理中。通过聚类分析发现存在的问题，全面、细致反映事件的空间分布、变化规律，为照明管理规划提供科学的依据和指导。 今后有待改进的地方有：①需要对空间聚类算法进行优化，降低时间复杂度，提高分析工作效率；②在DBSCAN两个参数的设定上还存在一定的主观性， 如何更加合理地动态化设置还需进一步研究；③要进一步研究事件之间的相关性，从而分析和发现热点之间的关联性。

参考文献：

[1]〖黄毅磊. DBSCAN算法及在城市网格化管理中的应用[D].上海：上海交通大学，2009.

[2]范明， 范宏建.数据挖掘导论[M] .北京：人民邮电出版社，2011.

[3]李新延，李德仁.DBSCAN空间聚类算法及其在城市规划中的应用[J].测绘科学，2005，30（6）：5153.

[4]聚类算法之密度聚类算法DBSCAN[EB/OL].http：//blog.csdn.net/u011955252/article/details/50814737？locationNum=3.

[5]DBSCAN算法[EB/OL].http：///aijianiula/p/4339960.html.

[6]陈鹏，马伟.层次聚类法在空间犯罪热点分析中的应用[J].中国人民公安大学学报：自然科学版，2013（1）：156159.

[7]唐志博，姜小荣，陈伟.基于 DBSCAN 算法的Geolife人员位置分析[J].中国科技论文，2014（1）：5962.

[8]曾泽林，段明秀.基于密度的聚类算法DBSCAN的研究与实现[J].科技信息，2012（30）：186189.

[9]吴文浩，吴升.多时间尺度密度聚類算法事件分析应用[J].地球信息科学学报，2015，17（7）：9195.

（责任编辑：杜能钢）