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

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

0 引 言

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

1 算法介紹

1.1 K-means算法

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

(1)首先選定K值；

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

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

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

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

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

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

1.2 離群點檢測(LOF)算法

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

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

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

dn(A)=d(A,B)

(1)

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

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

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

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

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

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

(2)

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

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

(3)

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

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

(4)

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

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

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

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

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

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

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

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

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

2 實 例

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

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

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

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

2.1 K-means算法的黑點識別

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

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

2.2 LOF與K-means結(jié)合的算法的黑點識別

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

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

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

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

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

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

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

(5)

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

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

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

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

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

3 結(jié) 語

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