DBSCAN算法優化及其在GSM-R鐵塔監測系統中的應用

胡淼淼 劉宏志 張 鐸

1(北京工商大學計算機與信息工程學院 北京 100048)2(北京工商大學食品安全大數據技術北京市重點實驗室 北京 100048)3(北京博時遠信技術有限公司 北京 100070)

0 引 言

在數據挖掘中，聚類算法可以根據數據的屬性(對象之間的距離)將數據劃分為不同的類。目前，主要的聚類算法可以劃分為以下幾類：基于劃分的方法、基于密度的方法、基于網格的方法以及基于層次的方法[1-4]。其中，基于密度的聚類算法主要的目標是尋找被低密度區域分離的高密度區域，與其他聚類算法不同的是基于密度的聚類算法可以在具有噪聲數據的空間數據庫中發現任意形狀的聚類。本文對基于密度的聚類算法DBSCAN的原理進行了分析并對算法進行了優化，使得算法能自適應確定參數滿足GSM-R鐵塔監測系統中傾角傳感器的校正需要。

1 GSM-R鐵塔監測及DBSCAN算法

1.1 GSM-R鐵塔監測

GSM-R系統是我國針對鐵路運輸的實際需要而專門設計的綜合專用數字通信系統[5-6]。近年來，隨著鐵路無線通信技術的飛速發展，越來越多的GSM-R通信鐵塔被部署應用。GSM-R通信鐵塔監測系統結合了物聯網技術，使用傾角傳感器、氣象傳感器、電磁傳感器和沉降傳感器等多種傳感器監測鐵塔狀態，保證了GSM-R鐵塔的正常使用[7]。其中，傾角傳感器是直接監測鐵塔的傾斜狀態的傳感器，在環境惡劣的情況下，傾角傳感器能及時發現鐵塔傾斜，方便維護人員及時加固鐵塔，避免傾倒影響鐵塔的正常使用。但是，傾角傳感器在人工安裝過程中會出現一定的角度偏移，因此在使用前需對傾角傳感器進行校正。

目前，GSM-R鐵塔監測系統多采用在穩定條件下傾角傳感器采集數據的平均值作為鐵塔中心角度偏移值進行傳感器校正。由于實際應用中的傾角傳感器在穩定條件下仍會受鐵塔塑性形變的影響，采集到部分噪聲數據，并且噪聲數據會影響鐵塔中心角度偏移值的計算結果，進而影響告警數據的產生，造成嚴重的后果。因此，本文提出使用DBSCAN算法代替平均值計算法進行傾角傳感器的校正，通過對算法進一步優化使其可以自適應確定所需參數適用于GSM-R鐵塔監測系統的傾角傳感器校正需要。優化后的DBSCAN算法可以通過密度聚類避免噪聲數據的影響，對聚類結果計算聚類中心可獲得鐵塔中心角度偏移值對傾角傳感器進行校正。

1.2 DBSCAN算法基本原理

基于密度的聚類算法DBSCAN算法是由MARTIN等[8-10]提出的一種基于密度的聚類算法，用來尋找被低密度區域分離的高密度區域。該算法將具有指定要求密度的相應區域劃分為簇，并在具有噪聲數據的數據庫樣本中發現任意形狀的簇，其對簇的定義即為密度相連點的最大集合。

DBSCAN算法使用之初需要用戶輸入參數Eps值和MinPts值。其中，Eps為鄰域半徑參數，MinPts為鄰域密度閾值。DBSCAN算法基本定義如下。

定義1以輸入數據集內任意一個數據對象為圓心，Eps為半徑的球形區域內所有數據對象的集合即為Eps鄰域。

定義2在Eps鄰域內的數據對象個數大于或等于MinPts的數據對象為核心點。在Eps鄰域內的對象數小于MinPts，但是在核心點Eps鄰域內的數據對象為邊界點。

定義3數據對象Pi在核心點Pj的Eps鄰域內，則Pi到Pj直接密度可達。

定義4若存在一個對象鏈P1,P2,…,Pn，且有Pi+1到Pi直接密度可達，則P1到Pn密度可達。

定義5基于密度可達性的最大的密度相連對象的集合稱為簇。數據集中不屬于任何簇的數據對象即為噪聲點。

DBSCAN通過檢查數據集中每個對象的Eps鄰域來尋找聚類。如果一個點P的Eps鄰域包含多于MinPts個數據對象，則創建一個P作為核心對象的新簇。然后，DBSCAN反復地尋找從這些核心對象直接密度可達的對象，這個過程涉及密度可達簇的合并。當沒有新的點可以被添加到任何簇時，聚類過程結束。

1.3 算法應用分析

在傳統GSM-R鐵塔監測系統中，傾角傳感器的校正是由傳感器在穩定狀態下采集的數據取平均值來確定的。根據中國鐵路總公司印發的《鐵路通信鐵塔監測系統技術條件》可知，穩定狀態即風速為零級(風速小于等于0.2 m/s)時的狀態，此時風速不能對鐵塔傾斜造成明顯影響。研究表明鐵塔在風載荷影響下的隨機振動不會立刻停止[11]，當傳感器采集校正所需零級風數據時，由于隨機振動的影響傳感器仍會采集到部分噪聲數據。因此，使用平均值計算鐵塔中心偏移值對傾角傳感器進行校正并不準確。

穩定狀態下傾角傳感器采集數據較為集中，從中心向外側數據密度逐漸降低，噪聲數據周圍數據密度最低。DBSCAN算法是一種基于密度的空間聚類算法，該算法可以忽略噪聲數據的影響對鐵塔中心區域數據進行聚類，聚類中心即為鐵塔中心偏移值。此外，受風向影響鐵塔中心偏移方向不確定，運動軌跡沒有規律，因此采集數據的高密度區域形狀并不固定。與傳統的基于劃分方法的聚類算法和基于層次方法的聚類的凸形聚類簇算法不同，DBSCAN算法的聚類簇可以是任意形狀的。因此DBSCAN算法適用于GSM-R鐵塔監測系統的傾角傳感器校正。

但是，DBSCAN算法在使用過程中聚類對象的密度由事先指定的兩個參數Eps(鄰域半徑)和MinPts(鄰域密度閾值)來確定。用戶需要在沒有先驗知識的情況下設定這兩個參數，DBSCAN算法對參數十分敏感，這兩個參數的選擇將直接影響算法最終的聚類結果質量。而GSM-R鐵塔監測系統通常能監測2 000個左右的鐵塔，這些鐵塔地理位置不同，環境不同甚至鐵塔種類也不同，因此在GSM-R鐵塔監測數據集中不同鐵塔的數據密度不同，使用全局參數難以準確計算出不同鐵塔的中心角度偏移值。本文對DBSCAN算法進行了優化，使其可以針對不同鐵塔數據集自適應確定Eps和MinPts參數，從而可以準確計算各個鐵塔的中心角度偏移值，對傾角傳感器進行校正。

2 DBSCAN算法優化

針對DBSCAN算法的參數敏感問題，已有不少學者提出了解決辦法。OPTICS算法通過對數據集中的數據對象進行排序得到一個有序的對象列表(cluster-ordering)，根據對象列表的信息對數據對象進行分類進而提取聚類[12]。文獻[13]根據數據對象在不同維度的密度分布動態設置Eps參數。文獻[14]提出了動態近鄰概念，即參數隨數據對象的密度動態變化。文獻[15]基于密度最大區域中心點對DBSCAN算法進行了改進。文獻[16]通過分析數據的統計特性自適應確定參數。本文在DBSCAN算法及其各類改進算法的研究基礎上，根據GSM-R鐵塔監測系統的使用需要對DBSCAN算法進行了優化。通過Canopy粗聚類確定算法所需參數Eps值，然后根據統計學方法確定參數MinPts，使得算法可以根據不同數據集自適應確定參數，解決了DBSCAN算法的參數敏感問題，提高了聚類效果。

2.1 鄰域半徑確定方法

根據DBSCAN算法的原理可知，算法根據數據對象之間的距離確定數據對象之間的親疏關系，Eps參數的選擇將直接影響最后的聚類效果。在參數MinPts一定的情況下，參數Eps選擇越小，則聚類結果中簇的密度越高，但會導致本該完整的簇被拆分為多個簇，大量的數據對象被錯誤的標記為噪聲數據。參數Eps選擇越大，則聚類結果中簇的密度會降低，同時會導致噪聲數據被歸入簇中，無法成功分離噪聲數據。

在數據對象分布不均勻的情況下，對任意一個數據對象，將距離該數據對象最近的多個數據對象的距離平均值作為該對象處的密度衡量標準。符合聚類需要的距離平均值將是需要獲取的Eps參數值。設輸入數據集D={P1,P2,…,Pn}。Pi為D中任意一個數據對象，計算數據對象Pi到D的子集S={P1,P2,…,Pi-1,Pi+1,…,Pn}中所有數據對象之間的距離。將距離按遞增排序后存入集合R={r1,r2,…,rk-1,rk,rk+1,…,rn-1}。其中，rk被稱為K-距離即數據對象Pi到除自身外所有數據對象之間距離第k近的距離。數據對象Pi到其他數據對象之間距離的平均值為：

(1)

Canopy算法是一種快速簡單但是并不準確的聚類算法，多用于數據集的粗劃分[17-18]。本文使用該算法進行數據集的粗聚類，根據粗聚類結果獲取合適的Eps值。Canopy算法使用之初要定義兩個距離值T1和T2，為了確定這兩個距離值，首先要在輸入數據集D中任選一個數據對象記為P，并將其移出數據集D。計算數據對象P的K-距離集合并求平均值。根據計算結果做如下設定：

(2)

然后按照K-距離集合將數據集D中所有距離小于T1的數據對象加入以P為中心的canopy類，將距離小于T2的所有數據對象移除數據集D。執行完一次后重新選擇一個數據對象，T1和T2不變，重復上述步驟，直至數據集D為空。

上述步驟執行完成后會獲得多個canopy類，這些類中會出現部分數據重疊的現象。因此Canopy算法的劃分是不準確的，但是分布雜亂的數據對象經過大致劃分可以確定數據密度分布情況。對多個canopy類按數據對象數目進行排序，數目最多的canopy類的數據密度相比較其他類更接近數據集的最大密度。在該類中任選一個數據對象，計算其K-距離平均值，該值即為所求Eps參數值。

2.2 鄰域密度閾值確定方法

在參數Eps已經確定的情況下，參數MinPts選擇越大，聚類結果中簇的密度越高，但是會減少核心點的數量，將完整的自然簇分割。參數MinPts選擇較小會使大量數據對象被錯誤的標記為核心點，導致噪聲數據無法正確標識。本文通過統計數據集D中所有數據對象在其Eps鄰域內的數據對象的個數，并通過求數學期望得到MinPts參數值表示為:

(3)

式中：Qi表示數據對象Pi其Eps鄰域內的數據對象的個數。

綜上，本文在對DBSCAN算法及其各類改進算法的研究基礎上，結合對鐵塔數據集統計分析，使用Canopy算法粗聚類確定算法所需參數Eps值，根據統計學方法確定參數MinPts值，使得算法可根據不同數據集自適應確定參數，解決了DBSCAN算法的參數敏感問題。將計算所得參數Eps和MinPts值代入DBSCAN算法進行聚類計算，所得聚類結果按照密度大小進行排序，選擇密度最高的聚類簇計算簇中心即為穩定狀態下鐵塔中心偏移值。其余聚類簇為鐵塔在火車共振等外力影響下的偏移中心，等同于噪聲數據。

3 實驗設備

本文中采用的實驗設備如圖1所示，左側儀器是串口輸出型雙軸傾角傳感器，內置高精度16 bit A/D 差分轉換器，通過5 階濾波算法，最終輸出雙方向的傾角值，分別是水平方向X軸的傾角值和Y軸的傾角值。圖1右側儀器為推動裝置用于檢測傳感器是否準確。

圖1 實驗設備圖

傾角傳感器輸出的水平方向X軸的傾角值和Y軸的傾角值是角度偏移值，并不能直接為DBSCAN算法所用，需要將傾角轉換為偏離X軸方向的實際距離值和偏移Y軸方向的實際距離值，方便DBSCAN算法按照密度聚類，具體計算模型如圖2所示。

圖2 角度轉換距離計算模型

在計算過程中設塔高為h，指塔頂到鐵塔底座中心的距離。在圖2中，鐵塔底座中心為點O，塔頂為A，OA之間距離為塔高h。α為X軸方向傾斜角度即∠AOB，β為Y軸方向傾斜角度即∠AOC，θ為垂直方向實際傾斜角度即∠AOD，則有:

(4)

X軸方向偏移距離為:

x=h·cosθ·tanα

(5)

Y軸方向偏移距離為:

y=h·cosθ·tanβ

(6)

經過上述計算將得出塔頂的具體偏移位置即為塔頂的實際距離坐標(x,y)，垂直狀態下坐標為(0,0)。將傾角傳感器采集角度值全部轉換為距離值后使用優化后的DBSCAN算法對傾角傳感器在穩定狀態下采集的數據進行聚類計算，求得具體的鐵塔中心距離偏移值，最后將鐵塔中心的距離偏移值轉換成角度偏移值對傾角傳感器進行校準。

4 實驗結果分析

本文所使用所有數據均是使用圖1所示傾角傳感器在四個采集點采集到的實際數據。四個采集點分別為4097號鐵塔(濟南西)、4099號鐵塔(曲阜東)、4100號鐵塔(滕州東)和4101號鐵塔(棗莊)。數據采集信息如表1所示，傳感器每250 ms采集一次數據。數據集包含時間、風速、風向、X軸傾角和Y軸傾角等信息。

表1 總數據集基本信息

本文首先使用優化后的DBSCAN算法分別對以上四個數據集中全部零級風數據計算鐵塔中心角度偏移值，計算結果如表2所示。通過比較計算結果發現4 099號數據集的DBSCAN算法計算所得鐵塔中心角度偏移值與平均值計算結果差距較大，其他數據集計算結果差距相對較小，其中4101號數據集計算結果差距最小。通過對數據集分析發現4099號數據集在2016年6月21日風速變化較大，下午5時最大風級達8級(最大風速17.3 m/s)，根據規定已達到大風預警條件，數據集中零級風總數最少且受大風影響噪聲數據較多。而4101號數據集全天風速相對穩定，且最大風級不超過3級(最大風速5.4 m/s)，數據集中零級風數據較多且噪聲數據最少。上述結論表明，噪聲數據會對中心角度偏移值的計算產生較大影響，需要進一步驗證DBSCAN算法分離噪聲數據的能力。

表2 總數據集計算結果

為了確定改進DBSCAN算法能有效分離噪聲數據求得準確鐵塔中心角度偏移值，本文人工從數據集中分離出最大風級不超過2級(最大風速3.3 m/s)的5個小時的連續數據，人工排除了受大風影響偏移較大的噪聲數據，節選數據集信息如表3所示。分別使用改進DBSCAN算法和平均值計算法對節選數據進行計算，計算結果如表4所示。通過比較計算結果發現改進DBSCAN算法計算所得鐵塔中心角度偏移值與表2計算結果差距較小，最大偏差為0.029°。而平均值計算所得結果與表2相比仍有比較大的差距，最大偏差已超過0.567°，根據《鐵路通信鐵塔監測系統技術條件》規定鐵塔中心偏移超過0.567°將會產生提示告警，因此可以證明平均值計算法易受噪聲數據影響，不能準確計算出鐵塔中心角度偏移值容易產生誤差告警。此外，表4平均值計算結果更接近于改進DBSCAN算法計算所得結果。綜上所述，改進DBSCAN算法受噪聲數據影響較小，能夠根據不同數據集自適應確定合適的參數Eps值和MinPts值，分離出絕大部分噪聲數據，求得相對準確的鐵塔中心角度偏移值對傾角傳感器進行校正。

表3 節選數據集基本信息

表4 節選數據集計算結果

5 結 語

GSM-R鐵塔監測系統保證了鐵路通信鐵塔的正常使用，其中傾角傳感器的監測結果直接反映了鐵塔的傾斜狀態。為了避免傾角傳感器受到人工安裝誤差的影響，本文提出使用DBSCAN算法代替平均值計算法進行傾角傳感器的校正。通過研究DBSCAN算法的基本原理，結合其他學者的研究工作解決了該算法的參數敏感問題，使其適用于GSM-R鐵塔監測系統的使用需要。實際數據測試結果表明，優化后的DBSCAN算法能根據不同數據集自適應確定所需參數，不受噪聲數據的影響，同時并未增加算法的處理時間，計算結果與全站儀所測實際數據對比準確率可達98.57%，適用于傾角傳感器校正需要。

參考文獻

[1] Dharni C, Bnasal M. An improvement of DBSCAN Algorithm to analyze cluster for large datasets[C]// Innovation and Technology in Education. IEEE, 2013:42-46.

[2] Rodriguez A, Laio A. Machine learning. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191):1492.

[3] 孫吉貴, 劉杰, 趙連宇. 聚類算法研究[J]. 軟件學報, 2008, 19(1):48-61.

[4] Smiti A, Eloudi Z. Soft DBSCAN: Improving DBSCAN clustering method using fuzzy set theory[C]// The, International Conference on Human System Interaction. IEEE, 2013:380-385.

[5] 車顏澤. 高速鐵路GSM-R無線通信系統簡介[J]. 華東科技:學術版, 2016(7):307-307.

[6] Tokody D, Maros D, Schuster G, et al. Communication-based intelligent railway- Implementation of GSM-R system in Hungary[C]// IEEE, International Symposium on Applied Machine Intelligence and Informatics. IEEE, 2016:99-104.

[7] 江文丹, 李春, 吳宏松. GSM-R綜合監測系統在高鐵中的應用研究[J]. 鐵道通信信號, 2015, 51(S1):70-72.

[8] Ester M, Kriegel H P, Sander J, et al. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise[C]// International Conference on Knowledge Discovery and Data Mining. AAAI Press, 1996:226-231.

[9] Borah B, Bhattacharyya D K. An improved sampling-based DBSCAN for large spatial databases[C]// International Conference on Intelligent Sensing and Information Processing. IEEE, 2004:92-96.

[10] 馮少榮, 肖文俊. 基于密度的DBSCAN聚類算法的研究及應用[J]. 計算機工程與應用, 2007, 43(20):216-221.

[11] 潘峰, 李顯鑫, 侯中偉,等. 1000kV特高壓山區單回路輸電塔風振特性研究[J]. 電力建設, 2013, 34(8):64-68.

[12] Ankerst M, Breunig M M, Kriegel H P, et al. OPTICS: ordering points to identify the clustering structure[J]. Acm Sigmod Record, 1999, 28(2):49-60.

[13] Jahirabadkar S, Kulkarni P. Algorithm to determine ε -distance parameter in density based clustering[J]. Expert Systems with Applications, 2014, 41(6):2939-2946.

[14] 李陽, 馬驪, 樊鎖海. 基于動態近鄰的DBSCAN算法[J]. 計算機工程與應用, 2016, 52(20):80-85.

[15] 范敏, 李澤明, 石欣. 一種基于區域中心點的聚類算法[J]. 計算機工程與科學, 2014, 36(9):1817-1822.

[16] 夏魯寧, 荊繼武. SA-DBSCAN:一種自適應基于密度聚類算法[J]. 中國科學院大學學報, 2009, 26(4):530-538.

[17] 趙慶. 基于Hadoop平臺下的Canopy-Kmeans高效算法[J]. 電子科技, 2014, 27(2):29-31.

[18] 余長俊, 張燃. 云環境下基于Canopy聚類的FCM算法研究[J]. 計算機科學, 2014, 41(S2):316-319.