基于LOF改進的K-means算法在交通事故黑點識別中的應用

張欣妍，董四輝，張紫慧，郭相儀

(大連交通大學 交通運輸工程學院，遼寧 大連 116028)

0 引 言

根據相關統計數據顯示，世界各地每年有超百萬人死于交通事故。由于城市內路網密集、交通流量大，所以城市交通事故占事故總量的大多數。為了保障道路安全又減少人力、物力投入，首要任務即是交通事故黑點的識別。相關部門可以根據識別出的道路黑點更有針對性的采取措施進行治理。提高事故黑點識別的準確率及效率一直是各國專家學者研究的重點。美國公開交通事故數據，以便展開交通安全研究。Moosavi等[1，2]構建了全美的交通事故數據集，并對交通事故特征進行分析，使用其中洛杉磯市部分數據進行研究。現有的黑點識別方法主要有事故率法[3]、基于統計的累計頻率曲線法[4]、聚類的算法、基于密度的DBSCAN[5]算法，基于分類的K-means算法等。K-means算法簡單易于實現，但由于對隨機選擇的初始聚類中的依賴及離群點的存在，聚類效果并不理想。舒玥等[6]使用距離法移除離群點，改進初始聚類中心的選擇方式，提高K-means聚類對事故黑點的識別效率，但對于黑點距離較近的識別效果不佳。經典的K-means聚類優化算法[7]的有K-means++、二分K-means、K-medoids，但均只針對某一缺點的優化。LOF是由Breunig等[8]人提出的一種以密度為基礎的異常點檢測算法。楊紅等[9]提出基于LOF的K-means算法，通過LOF識別離群點并改進準則函數，該方法雖然降低了離群點對聚類的影響，但隨機選擇初始聚類中心仍然會降低聚類的效率。本文提出一種利用LOF篩選離群點并通過離群因子優化初始聚類中心的選擇，以此提高K-means算法的聚類效果，使其更適用于交通事故黑點的識別。

1 算法介紹

1.1 K-means算法

傳統K-means聚類算法在交通事故黑點識別中應用較多，K-means是迭代聚類算法，它以距離作為度量指標，基于類目數K，對給定數據集進行分類。在交通事故黑點的識別過程中，即是由交通事故數據組成數據集合，給定聚類組數K，即事故黑點數，再將該集合劃分為K組。具體步驟如下：

(1)首先選定K值；

(2)將K個數據點隨機自動選擇為初始化的聚類數據中心；

(3)對數據集中每一個點與K個聚類中心之間的距離進行計算，并將其劃分到距離最近的聚類中心所屬的集合；

(4)重新計算K個集合的聚類中心；

(5)此時若新中心和原中心之間的距離低于所給定的閾值(也就是表示重新計算的中心的位置與原位置變化較小，趨于穩定)，則算法結束；

(6)重復(3—5)，直到中心不再變化。

但是K-means算法的初始聚類中心是隨機確定的，不同的初始聚類中心可能導致完全不同的聚類結果，聚類過程中受異常點干擾比較大。

1.2 離群點檢測(LOF)算法

LOF算法中主要是通過比較每個點和其鄰域點的密度來判斷該點是否為離群點，點的密度越低，越可能被認定是離群點。LOF算法不是通過除所求點外全數據集內其他點來計算密度，是通過對點的第n鄰域來計算，所以稱所得點為“局部”離群因子。具體算法如下

(1)d(A,B)：點A和點B之間的距離(選用歐式距離)。

(2)dn(A)：點A的第n距離，定義如下：

dn(A)=d(A,B)

(1)

記點B為距離點A第n遠的點(不包括點A在內)。

簡言之，點A的第n距離即距點A第n遠的點與點A間的距離(不包括點A在內)。

(3)Nn(A):點A的第n距離鄰域，定義如下：

距點A第n距離及第n距離以內的所有點的集合，|Nn(A)|≥n。

(4)dn(A,B)，點B到點A的第n可達距離，定義如下

dn(A,B)=max{dn(A),d(A,B)}

(2)

即點A的第n距離和點A、B間距離的最大值。

(5)ρn(A):點A的局部可達密度，定義為

(3)

表示點A的第n鄰域內的所有點到點A的平均可達距離的倒數。

(6)LOFn(A)：局部離群因子，定義如下

(4)

表示點A的鄰域點集合Nn(A)的局部可達密度與點A的局部可達密度之比的平均數。LOF值越大，說明該點異常性越強；相反的，LOF值越小，說明該點越正常(可能為負值)。

1.3 基于LOF改進的K-means算法

在基于LOF剔除離群點，以避免離群點使聚類中心偏移的基礎上，再通過局部離群因子選取初始聚類中心，降低隨機選擇的初始聚類中心對聚類中心的影響。具體實現步驟如下。

(1)首先利用LOF算法對全數據集Q篩選，調整LOF閾值和n值，構建離群點集合Q0；

(2)剔除原數據集合中的(1)中篩選出的離群點，構建密集點集合Q1；

(3)選取Q1中LOF值最小的點X1作為首個初始聚類中心；

(4)給定距離閾值d，搜索在X1閾值d半徑范圍內的數據點，在Q1中刪除這些數據點及X1，構建數據集合Q2；

(5)在Q2中依照步驟(3)選出X2作為初始聚類中心中第二個點，進行步驟(4)，依此往復，直至選出K個初始聚類中心；

(6)調用K-means，使用(5)中選出的初始聚類中心對密集點集合Q1進行劃分，并迭代選出最優的聚類中心。

2 實 例

Moosavi等建立的全美交通事故數據集，包括交通事故發生時間、天氣、事故點的經緯度等事故信息。選用洛杉磯市2018年7月1日至2018年12月31日的交通事故數據，計5543起。并利用事故點經緯度(見表1)在ArcGIS中撒點分布，如圖1所示，以獲取交通事故的分布情況，以此為基礎擬定聚類中心數量。

表1 交通事故點經緯度

圖1 交通事故發生點在ArcGIS中分布圖

現在對交通事故黑點沒有統一定義，根據所使用數據以及道路情況，認為200 m半徑范圍發生超過30起事故可能為事故黑點。

2.1 K-means算法的黑點識別

設定K值即黑點數目為25，使用K-means算法對事故點經緯度進行聚類，得到聚類中心即事故黑點。并通過經緯度將事故黑點在ArcGIS中顯示，如圖2所示。

圖2 K-means算法的識別結果

2.2 LOF與K-means結合的算法的黑點識別

設置n=30，調整閾值，對離群點搜索并剔除，選擇K=25，進行事故黑點識別，識別出的事故黑點在ArcGIS中分布如圖3所示。

圖3 LOF與K-means結合的算法的識別結果

2.3 基于LOF改進的K-means算法的黑點識別

在2.2的基礎上，設定距離閾值為200，K=25，使用改進后的K-means算法進行黑點識別，識別出的事故黑點在ArcGIS中分布如圖4所示。

圖4 基于LOF改進的K-means算法的識別結果

2.4 3種算法的事故黑點識別效果對比

聚類效果通常使用誤差平方和作為評價，以SSE表示，計算公式如下

(5)

其中K為事故數據分類數；ni為第i類事故集合中點的個數；Ci為第i類事故集合；xij為Ci中的點；ci為Ci的聚類中心。

SSE值越大則誤差越大，即聚類效果差；反之聚類效果好。

對3種算法計算得出的事故黑點，分別在劃定閾值半徑范圍內搜索事故點，統計事故數量，與定義相比較，對識別準確性進行驗證。K-means算法識別出的事故黑點隨機性較大，需多次運行，實驗50次，僅有9次識別準確，其余均存在識別出的黑點偏離道路，半徑范圍內事故數量并不滿足定義的情況。LOF與K-means結合的算法，雖然對K-means識別效果有所提高，但聚類結果仍不穩定，實驗50次，有28次識別準確。而基于LOF改進的K-means算法對事故黑點的識別穩定，實驗50次，僅有4次識別不精確。

3種算法的SSE值及平均識別精度如表1所示，基于LOF改進的K-means聚類算法在事故黑點識別上遠優于傳統K-means算法及LOF與K-means結合的算法。

表1 事故黑點識別效果對比

3 結 語

提出基于LOF剔除離群點，并將LOF運用到K-means算法初始聚類中心的選擇上。設定距離閾值，保證各初始聚類中心不在較近的范圍內；選取LOF值較低的點，確保了初始聚類中心位于密度較大處。實例證明，改進后的算法在黑點識別中，識別精度相較于K-means算法LOF與K-means結合的算法分別提高24%、12%。在50次實驗中，改進后的算法的識別準確次數分別是另兩種算法的5.1倍和1.6倍，穩定性較好。