基于密度的空間聚類算法在照明運(yùn)維中的應(yīng)用

李今+石曉潤(rùn)

摘要：城市照明數(shù)字化綜合管理系統(tǒng)應(yīng)用過(guò)程中會(huì)產(chǎn)生大量設(shè)施維護(hù)事件記錄，這些數(shù)據(jù)在類型和空間分布上蘊(yùn)含大量信息，對(duì)這些數(shù)據(jù)進(jìn)行分析并加以應(yīng)用很有必要。對(duì)基于密度的空間聚類算法（DBSCAN）進(jìn)行了研究。介紹了DBSCAN算法的基本概念和原理，將該算法應(yīng)用于城市照明管理業(yè)務(wù)數(shù)據(jù)中，對(duì)照明設(shè)施維護(hù)熱點(diǎn)分布進(jìn)行聚類分析，根據(jù)聚類結(jié)果為城市照明運(yùn)維管理區(qū)域劃分和運(yùn)維資源規(guī)劃提供參考依據(jù)。

關(guān)鍵詞：空間聚類；基于密度；DBSCAN；照明設(shè)施維護(hù)

中圖分類號(hào)：TP319

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：16727800（2017）004014804

0引言 信息化系統(tǒng)產(chǎn)生大量基于位置的信息數(shù)據(jù)，這些數(shù)據(jù)具有易收集、分布廣、數(shù)量大的特點(diǎn)，不僅擁有空間屬性，而且具有時(shí)間屬性，非常適合作為數(shù)據(jù)挖掘研究對(duì)象。 為適應(yīng)快速發(fā)展的城市化進(jìn)程，沈陽(yáng)市路燈管理局持續(xù)致力于照明管理水平的創(chuàng)新，在2011年建成沈陽(yáng)城市照明數(shù)字化綜合管理系統(tǒng)（以下簡(jiǎn)稱沈陽(yáng)數(shù)字化系統(tǒng)），系統(tǒng)主要由動(dòng)態(tài)的路燈監(jiān)控管理系統(tǒng)和靜態(tài)的照明設(shè)施地理信息系統(tǒng)組成，通過(guò)工作流柔性建模進(jìn)行動(dòng)、靜態(tài)數(shù)據(jù)融合，實(shí)現(xiàn)了照明設(shè)施應(yīng)急搶修和日常維護(hù)工作標(biāo)準(zhǔn)化管理。 系統(tǒng)自2011年7月運(yùn)行以來(lái)，經(jīng)過(guò)6年時(shí)間積累了海量維護(hù)事件記錄。雖然這些數(shù)據(jù)具有隨機(jī)性，但當(dāng)數(shù)據(jù)量積累到一定程度時(shí)，其在空間上的分布會(huì)存在一定的規(guī)律性，這為城市照明管理業(yè)務(wù)的數(shù)據(jù)挖掘提供了條件[1]。對(duì)照明設(shè)施維護(hù)事件類問(wèn)題進(jìn)行聚類分析，從中找出高發(fā)區(qū)域，然后有針對(duì)性地分析成因，采取合理有效措施，對(duì)搞好運(yùn)維工作有積極的指導(dǎo)作用。本文運(yùn)用基于密度的空間聚類算法對(duì)沈陽(yáng)數(shù)字化系統(tǒng)業(yè)務(wù)數(shù)據(jù)進(jìn)行了研究。1相關(guān)理論 聚類分析根據(jù)數(shù)據(jù)中發(fā)現(xiàn)的描述對(duì)象及其關(guān)系信息，將數(shù)據(jù)對(duì)象分組，使組內(nèi)相似性盡可能大，組間相似性盡可能小。組內(nèi)相似性越大，組間差別越大，聚類就越好[2]。目前常用的聚類算法有基于層次的聚類算法、基于劃分的聚類算法、基于密度的聚類算法等。本文研究的是基于密度的空間聚類方法——DBSCAN算法。1.1DBSCAN簡(jiǎn)介 DBSCAN（DensityBased Spatial Clustering of Application with Noise）算法是一種基于密度的空間數(shù)據(jù)聚類算法，該算法主要基于具有噪聲的空間數(shù)據(jù)，目標(biāo)針對(duì)高密度區(qū)域發(fā)現(xiàn)任意形狀的簇并進(jìn)行劃分，定義簇為密度相連點(diǎn)的最大集合。該算法的中心思想是：對(duì)于某一聚類中的對(duì)象，在給定半徑（Eps）的鄰域內(nèi)，數(shù)據(jù)對(duì)象個(gè)數(shù)必須大于某個(gè)給定值，也就是說(shuō)，鄰域密度必須超過(guò)某一閾值（MinPts） [3]。 DBSCAN算法主要有以下幾個(gè)概念： Eps鄰域：以空間中任意一點(diǎn)P為圓心，以Eps為半徑的范圍內(nèi)包含的點(diǎn)集合。 核心點(diǎn)：這些點(diǎn)在機(jī)遇密度的簇內(nèi)部。點(diǎn)的領(lǐng)域由距離函數(shù)和用戶指定的距離參數(shù)Eps決定。核心點(diǎn)定義是：該點(diǎn)在給定鄰域內(nèi)點(diǎn)的個(gè)數(shù)超過(guò)給定的閾值MinPts，其中MinPts是用戶指定的參數(shù)[4]。 邊界點(diǎn)：邊界點(diǎn)落在多個(gè)核心點(diǎn)鄰域內(nèi)，位于密度劃分簇的邊沿區(qū)域，它不是核心點(diǎn)。 噪聲點(diǎn)：噪聲點(diǎn)是既非核心點(diǎn)也非邊界點(diǎn)的任何點(diǎn)。 密度可達(dá)：在DBSCAN中，P是從q（核心對(duì)象）密度可達(dá)的，如果存在對(duì)象P1，P2，P3…Pn，使得P1=q，Pn=p，Pi是從Eps和MinPts直接密度可達(dá)的，即在Pi的Eps鄰域內(nèi)，P1到Pn密度可達(dá)[4]。 密度相連：如果存在對(duì)象qID，使得對(duì)象P1和P2都是從q關(guān)于MinPts密度可達(dá)，則稱P1、P2是關(guān)于Eps和MinPts密度相連的[2]。1.2參數(shù)選擇 DBSCAN算法有兩個(gè)很敏感的輸入?yún)?shù) Eps 和 MinPts，兩個(gè)參數(shù)的選取對(duì)最終聚類的影響非常大，傳統(tǒng)DBSCAN算法由于Eps值取決于MinPts，所以會(huì)存在以下問(wèn)題：①如果MinPts設(shè)置過(guò)大，則尺寸小于MinPts的簇會(huì)標(biāo)記為噪聲；②如果MinPts設(shè)置過(guò)小，則鄰近的噪聲點(diǎn)可能被錯(cuò)誤地標(biāo)記為簇；③如果Eps設(shè)置過(guò)大，所有的點(diǎn)都會(huì)歸為一個(gè)簇；④如果Eps設(shè)置過(guò)小，那么簇的數(shù)目會(huì)過(guò)多。

本文針對(duì)熱點(diǎn)進(jìn)行位置聚類，在參數(shù)選擇上進(jìn)行如下優(yōu)化：①本文目的是為了發(fā)現(xiàn)熱點(diǎn)常處的位置，根據(jù)經(jīng)驗(yàn)，對(duì)于大部分二維位置數(shù)據(jù)集將MinPts定義為數(shù)值4；②根據(jù)照明行業(yè)管理特征，路燈設(shè)施分布較為均勻，遍布城市各個(gè)區(qū)域，因此將服務(wù)半徑定義為一個(gè)合理的值300m，轉(zhuǎn)換公式如下：

1.3DBSCAN聚類過(guò)程 首先將給定數(shù)據(jù)集Data中所有對(duì)象都標(biāo)記為“unvisited”，DBSCAN隨機(jī)選擇一個(gè)未訪問(wèn)的對(duì)象P，標(biāo)記P為“visited”，并檢查P的Eps半徑鄰域里是否至少包含MinPts個(gè)對(duì)象。如果不是，則P標(biāo)記為噪聲點(diǎn)，否則為P創(chuàng)建一個(gè)新的簇C，并且把P的Eps鄰域中所有對(duì)象都放在候選集合N中[5]。 接下來(lái)把N中不屬于其它簇的對(duì)象依次迭代添加到簇C中。在此過(guò)程中，將N中標(biāo)記為“unvisited”的對(duì)象P′標(biāo)記為“visited”，并檢查它的Eps鄰域，如果P′的Eps鄰域中至少包含MinPts個(gè)對(duì)象，則P′的Eps鄰域中的對(duì)象都被添加到N中。DBSCAN繼續(xù)添加對(duì)象到C，直到C不能擴(kuò)展，即直到N為空。此時(shí)簇C完成生成并輸出。 從剩下的對(duì)象中隨機(jī)選擇一個(gè)未訪問(wèn)的對(duì)象 P ，聚類過(guò)程繼續(xù)，直到所有對(duì)象都被訪問(wèn)。1.4算法流程 DBSCAN算法流程如下：輸入：Eps — 半徑參數(shù) MinPts — 給定點(diǎn)在 Eps 鄰域密度閥值Data — 一個(gè)包含n個(gè)對(duì)象的數(shù)據(jù)集合輸出：基于密度的簇集合方法： 標(biāo)記所有對(duì)象為unvisited； Do 隨機(jī)選擇一個(gè)unvisited對(duì)象P； 標(biāo)記P為visited； If P的Eps鄰域至少有MinPts個(gè)對(duì)象創(chuàng)建一個(gè)新簇 C ，并把 P 添加到 C； 令 N 為 P的Eps鄰域中的對(duì)象集合 For N 中每個(gè)點(diǎn) P If p是unvisited； 標(biāo)記p為visited If P的Eps鄰域至少有MinPts個(gè)對(duì)象，把對(duì)象添加到N； If P不是任何簇的成員，把P添加到C； End For； 輸出C； Else標(biāo)記P為噪聲點(diǎn)； Until沒(méi)有標(biāo)記為unvisited的對(duì)象2應(yīng)用分析2.1數(shù)據(jù)描述 沈陽(yáng)城市照明數(shù)字化綜合管理系統(tǒng)記錄了沈陽(yáng)行政區(qū)劃內(nèi)所有照明設(shè)施維護(hù)事件，數(shù)據(jù)總量已累計(jì)達(dá)36 525條紀(jì)錄，數(shù)據(jù)屬性包括事件來(lái)源、事件分類、受理時(shí)間、經(jīng)緯度位置等信息，具有典型的時(shí)空特性，滿足數(shù)據(jù)挖掘需要，如表1所示。

2.2特征數(shù)據(jù)選擇

2.2.1時(shí)空分布觀察 利用MATLAB的Scatter3繪制2012-2015年沈陽(yáng)路燈管理局照明設(shè)施維護(hù)事件時(shí)空分布三維圖，圖2為俯視圖，圖3為側(cè)視圖。圖中X軸表示東西方向， Y軸表示南北方向， Z軸為年份。從俯視圖和側(cè)視圖進(jìn)行觀察，除了部分邊界受稀疏點(diǎn)影響外，整體空間分布較為平穩(wěn)。

2.2.2特征年份選定 由于相對(duì)完整的數(shù)據(jù)能夠更好地進(jìn)行分布態(tài)勢(shì)觀察，所以取2012-2015年4年整年份的數(shù)據(jù)進(jìn)行觀察。從數(shù)據(jù)總量上看，從2012年的10 007件到2015年5 903件，事件呈現(xiàn)持續(xù)下降趨勢(shì)，反映管理水平和設(shè)施質(zhì)量提升有很大關(guān)系。為了對(duì)本文算法進(jìn)行驗(yàn)證，取特征性最強(qiáng)、實(shí)效性最好的2015年事件紀(jì)錄作為分析數(shù)據(jù)進(jìn)行挖掘。

2.2.3特征事件選定 2015年維護(hù)事件總量達(dá)到5 903件，事件類型包括燈不亮、大面積滅燈、監(jiān)控終端報(bào)警、撞桿、燈具破損、燈門(mén)破損、電纜井丟失等，如圖5所示，其中個(gè)別燈不亮問(wèn)題占到事件總量的70%。在充分考慮空間分布性、數(shù)據(jù)特征性等因素后決定采用個(gè)別燈不亮事件作為基于密度的空間聚類分析數(shù)據(jù)基礎(chǔ)。

2.3基于密度聚類分析 采用DBSCAN聚類算法對(duì)2015年沈陽(yáng)數(shù)字化照明系統(tǒng)記錄的4 127個(gè)維護(hù)事件點(diǎn)進(jìn)行聚類分析。綜合考慮事件影響半徑和最小事件數(shù)量后，最終將Eps半徑參數(shù)設(shè)置為300m，MinPts設(shè)置為4，經(jīng)過(guò)空間聚類共發(fā)現(xiàn)13個(gè)空間簇C1-C13，如圖6所示。從基于密度的空間聚類呈現(xiàn)結(jié)果看，大部分簇在空間分布上具有一致性，且在重點(diǎn)區(qū)域呈現(xiàn)出密集性。只是組簇中所包含的事件空間點(diǎn)數(shù)量和分布范圍有區(qū)別，小部分簇存在一定的差異。將聚類后的數(shù)據(jù)簇與GIS地圖進(jìn)行匹配，得到結(jié)果如圖7所示，從熱點(diǎn)區(qū)域分布情況看，這些空間簇聚合特征明顯，大部分分布在3大聚集區(qū)域：

（1）和平區(qū)、沈河區(qū)的大部分區(qū)域， 集中在渾河以北地區(qū)。這個(gè)區(qū)域是沈陽(yáng)市市中心商圈及居住地，并且有主干道青年大街，是人們經(jīng)?；顒?dòng)的場(chǎng)所，人群分布集中，具有很高的聚集性，因此對(duì)照明設(shè)施故障敏感性非常強(qiáng)，屬于重點(diǎn)保障區(qū)域。 （2）皇姑區(qū)與和平區(qū)、沈河區(qū)、大東區(qū)交界的條帶狀聚集區(qū)域，是重要的居住地，人口較密集，對(duì)路燈依賴性較高。 （3）鐵西區(qū)集中了舊工業(yè)區(qū)、新興商圈和居住區(qū)，人員流動(dòng)性較大，對(duì)功能性照明質(zhì)量要求較高。2.4分析結(jié)果 通過(guò)分析可以看出，事件熱點(diǎn)區(qū)域比較一致，普遍集中在商圈、居住地、工業(yè)區(qū)等場(chǎng)所，這與聚類簇所反映出來(lái)的空間特征較為吻合，符合人們?nèi)粘；顒?dòng)行為和對(duì)功能性照明需求。下面對(duì)基于密度的空間聚類結(jié)果進(jìn)行深層次分析。 （1）根據(jù)聚類分析確定和識(shí)別出照明管理維護(hù)事件聚集區(qū)域，對(duì)維護(hù)事件熱點(diǎn)進(jìn)行相應(yīng)的資源部署調(diào)度。對(duì)于較大范圍管理，可以在統(tǒng)一模型參數(shù)的基礎(chǔ)上按層次聚類分析事件熱點(diǎn)，對(duì)不同區(qū)域進(jìn)行比較分析，確定需要重點(diǎn)保障的區(qū)域[6]。例如以前將青年大街作為路燈管護(hù)區(qū)劃分紅線，紅線左面區(qū)域由西城維護(hù)處管理，紅線右面由東城維護(hù)處管護(hù)。經(jīng)過(guò)本文分析，這樣的管護(hù)區(qū)劃分方式存在“西重東輕”，明顯不合理，在重點(diǎn)區(qū)域存在“扯皮”現(xiàn)象。建議設(shè)立3個(gè)維護(hù)單元根據(jù)區(qū)域重新劃分，或者重新調(diào)整管護(hù)區(qū)，重劃紅線。 （2）在不同空間下分析得到的熱點(diǎn)分布有利于制定針對(duì)性運(yùn)維策略。對(duì)小范圍的事件熱點(diǎn)，比如大東區(qū)和于洪新區(qū)，可增加區(qū)域管理和維護(hù)；而對(duì)于較大范圍的聚類點(diǎn)，則可通過(guò)新裝單燈監(jiān)控、視頻監(jiān)控，制定針對(duì)性的巡檢路線等，及時(shí)發(fā)現(xiàn)問(wèn)題并立即處理；對(duì)于更大范圍內(nèi)形成的區(qū)域熱點(diǎn)，則需要從宏觀角度進(jìn)行統(tǒng)籌規(guī)劃，制定管護(hù)區(qū)劃分、部署調(diào)度、應(yīng)對(duì)策略等，對(duì)不同層面問(wèn)題采用不同的決策方案。3結(jié)語(yǔ) 本文探討了基于密度的聚類分析算法基本原理及實(shí)現(xiàn)過(guò)程，并將該算法應(yīng)用于城市照明管理中。通過(guò)聚類分析發(fā)現(xiàn)存在的問(wèn)題，全面、細(xì)致反映事件的空間分布、變化規(guī)律，為照明管理規(guī)劃提供科學(xué)的依據(jù)和指導(dǎo)。 今后有待改進(jìn)的地方有：①需要對(duì)空間聚類算法進(jìn)行優(yōu)化，降低時(shí)間復(fù)雜度，提高分析工作效率；②在DBSCAN兩個(gè)參數(shù)的設(shè)定上還存在一定的主觀性， 如何更加合理地動(dòng)態(tài)化設(shè)置還需進(jìn)一步研究；③要進(jìn)一步研究事件之間的相關(guān)性，從而分析和發(fā)現(xiàn)熱點(diǎn)之間的關(guān)聯(lián)性。

參考文獻(xiàn)：

[1]〖黃毅磊. DBSCAN算法及在城市網(wǎng)格化管理中的應(yīng)用[D].上海：上海交通大學(xué)，2009.

[2]范明， 范宏建.數(shù)據(jù)挖掘?qū)д揫M] .北京：人民郵電出版社，2011.

[3]李新延，李德仁.DBSCAN空間聚類算法及其在城市規(guī)劃中的應(yīng)用[J].測(cè)繪科學(xué)，2005，30（6）：5153.

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

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

[6]陳鵬，馬偉.層次聚類法在空間犯罪熱點(diǎn)分析中的應(yīng)用[J].中國(guó)人民公安大學(xué)學(xué)報(bào)：自然科學(xué)版，2013（1）：156159.

[7]唐志博，姜小榮，陳偉.基于 DBSCAN 算法的Geolife人員位置分析[J].中國(guó)科技論文，2014（1）：5962.

[8]曾澤林，段明秀.基于密度的聚類算法DBSCAN的研究與實(shí)現(xiàn)[J].科技信息，2012（30）：186189.

[9]吳文浩，吳升.多時(shí)間尺度密度聚類算法事件分析應(yīng)用[J].地球信息科學(xué)學(xué)報(bào)，2015，17（7）：9195.

（責(zé)任編輯：杜能鋼）