基于密度的空間聚類算法在照明運維中的應用

李今+石曉潤

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

關鍵詞：空間聚類；基于密度；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：//www.cnblogs.com/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.

（責任編輯：杜能鋼）