李今+石曉潤

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

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

中圖分類號：TP319

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

文章編號：16727800（2017）004014804

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

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

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

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

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

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

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

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

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

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

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

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

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