基于LOF改進(jìn)的K-means算法在交通事故黑點(diǎn)識(shí)別中的應(yīng)用

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

(大連交通大學(xué) 交通運(yùn)輸工程學(xué)院，遼寧 大連 116028)

0 引 言

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

1 算法介紹

1.1 K-means算法

傳統(tǒng)K-means聚類算法在交通事故黑點(diǎn)識(shí)別中應(yīng)用較多，K-means是迭代聚類算法，它以距離作為度量指標(biāo)，基于類目數(shù)K，對給定數(shù)據(jù)集進(jìn)行分類。在交通事故黑點(diǎn)的識(shí)別過程中，即是由交通事故數(shù)據(jù)組成數(shù)據(jù)集合，給定聚類組數(shù)K，即事故黑點(diǎn)數(shù)，再將該集合劃分為K組。具體步驟如下：

(1)首先選定K值；

(2)將K個(gè)數(shù)據(jù)點(diǎn)隨機(jī)自動(dòng)選擇為初始化的聚類數(shù)據(jù)中心；

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

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

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

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

但是K-means算法的初始聚類中心是隨機(jī)確定的，不同的初始聚類中心可能導(dǎo)致完全不同的聚類結(jié)果，聚類過程中受異常點(diǎn)干擾比較大。

1.2 離群點(diǎn)檢測(LOF)算法

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

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

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

dn(A)=d(A,B)

(1)

記點(diǎn)B為距離點(diǎn)A第n遠(yuǎn)的點(diǎn)(不包括點(diǎn)A在內(nèi))。

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

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

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

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

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

(2)

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

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

(3)

表示點(diǎn)A的第n鄰域內(nèi)的所有點(diǎn)到點(diǎn)A的平均可達(dá)距離的倒數(shù)。

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

(4)

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

1.3 基于LOF改進(jìn)的K-means算法

在基于LOF剔除離群點(diǎn)，以避免離群點(diǎn)使聚類中心偏移的基礎(chǔ)上，再通過局部離群因子選取初始聚類中心，降低隨機(jī)選擇的初始聚類中心對聚類中心的影響。具體實(shí)現(xiàn)步驟如下。

(1)首先利用LOF算法對全數(shù)據(jù)集Q篩選，調(diào)整LOF閾值和n值，構(gòu)建離群點(diǎn)集合Q0；

(2)剔除原數(shù)據(jù)集合中的(1)中篩選出的離群點(diǎn)，構(gòu)建密集點(diǎn)集合Q1；

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

(4)給定距離閾值d，搜索在X1閾值d半徑范圍內(nèi)的數(shù)據(jù)點(diǎn)，在Q1中刪除這些數(shù)據(jù)點(diǎn)及X1，構(gòu)建數(shù)據(jù)集合Q2；

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

(6)調(diào)用K-means，使用(5)中選出的初始聚類中心對密集點(diǎn)集合Q1進(jìn)行劃分，并迭代選出最優(yōu)的聚類中心。

2 實(shí) 例

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

表1 交通事故點(diǎn)經(jīng)緯度

圖1 交通事故發(fā)生點(diǎn)在ArcGIS中分布圖

現(xiàn)在對交通事故黑點(diǎn)沒有統(tǒng)一定義，根據(jù)所使用數(shù)據(jù)以及道路情況，認(rèn)為200 m半徑范圍發(fā)生超過30起事故可能為事故黑點(diǎn)。

2.1 K-means算法的黑點(diǎn)識(shí)別

設(shè)定K值即黑點(diǎn)數(shù)目為25，使用K-means算法對事故點(diǎn)經(jīng)緯度進(jìn)行聚類，得到聚類中心即事故黑點(diǎn)。并通過經(jīng)緯度將事故黑點(diǎn)在ArcGIS中顯示，如圖2所示。

圖2 K-means算法的識(shí)別結(jié)果

2.2 LOF與K-means結(jié)合的算法的黑點(diǎn)識(shí)別

設(shè)置n=30，調(diào)整閾值，對離群點(diǎn)搜索并剔除，選擇K=25，進(jìn)行事故黑點(diǎn)識(shí)別，識(shí)別出的事故黑點(diǎn)在ArcGIS中分布如圖3所示。

圖3 LOF與K-means結(jié)合的算法的識(shí)別結(jié)果

2.3 基于LOF改進(jìn)的K-means算法的黑點(diǎn)識(shí)別

在2.2的基礎(chǔ)上，設(shè)定距離閾值為200，K=25，使用改進(jìn)后的K-means算法進(jìn)行黑點(diǎn)識(shí)別，識(shí)別出的事故黑點(diǎn)在ArcGIS中分布如圖4所示。

圖4 基于LOF改進(jìn)的K-means算法的識(shí)別結(jié)果

2.4 3種算法的事故黑點(diǎn)識(shí)別效果對比

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

(5)

其中K為事故數(shù)據(jù)分類數(shù)；ni為第i類事故集合中點(diǎn)的個(gè)數(shù)；Ci為第i類事故集合；xij為Ci中的點(diǎn)；ci為Ci的聚類中心。

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

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

3種算法的SSE值及平均識(shí)別精度如表1所示，基于LOF改進(jìn)的K-means聚類算法在事故黑點(diǎn)識(shí)別上遠(yuǎn)優(yōu)于傳統(tǒng)K-means算法及LOF與K-means結(jié)合的算法。

表1 事故黑點(diǎn)識(shí)別效果對比

3 結(jié) 語

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