基于k-mediods及其改進算法的非法營運車輛識別

帥　丹　藍章禮　李益才

(重慶交通大學信息科學與工程學院　重慶 400074)

?

基于k-mediods及其改進算法的非法營運車輛識別

帥丹藍章禮李益才

(重慶交通大學信息科學與工程學院重慶 400074)

摘要為從大量社會車輛中識別出疑似非法營運的車輛，提高交通管理部門行政執法的目的性和針對性，維護道路運輸市場秩序，消除交通安全隱患。結合RFID車輛信息數據提出了基于k-mediods的非法營運車輛識別算法，并針對k-mediods算法缺點進行了基于距離貢獻率和算法偶然性的2種改進。非法營運車輛識別的實現，首先需要提取出車輛RFID數據，并對其進行預處理，進而得到車輛運行行為數據，再利用PCA處理得到車輛運行特征數據，最后通過k-mediods算法聚類分析識別出非法營運車輛。實驗結果表明，算法流程清晰，能夠有效地識別出非法營運車輛。同時通過對算法進行改進，提高了算法穩定性和對非法營運車輛的正確識別數量，降低了錯誤識別數量。

關鍵詞k-mediods距離貢獻率偶然性RFID

0引言

相對滯后的公共交通滿足不了群眾日益增長的出行需求，這就為實載率高、方便靈活、具有成本優勢的非法營運車輛的存在提供了肥沃的土壤，但由于非法營運車輛的巨大危害性，打擊和規范非法營運車輛是交通行政執法的重中之重[1,2]。因此如何有效地從大量的社會車輛中識別出疑似非法營運車輛，對提高交通管理部門行政執法的目的性和針對性，維護道路運輸市場秩序，消除交通安全隱患具有重要意義。

RFID(無線射頻識別)技術作為一種新興的車輛監控技術，因其識別速度高，精確性能好，成本低廉，正在被廣泛地應用于物流、交通、醫療、商品防偽等諸多領域[3-6]。RFID裝置能夠采集到的數據包括時間、地點以及RFID卡中所含信息如車輛牌照號、車輛類型等，能夠很好地滿足對各類車輛的監控和數據采集功能。

數據挖掘中聚類分析在城市交通、道路安全、事故分析、交通違規違法行為分析等方面得到較為深入的研究和廣泛的應用[7-10]。文獻[11]提出了一種混合蛙跳算法與模糊C均值相結合的聚類算法，用于城市交通流數據的聚類分析；文獻[12]提出灰色定權聚類對區域內高等級公路進行聚類；文獻[13] 采用快速DBSCAN算法對鐵路異物侵限檢測；文獻[14]采用主成分分析方法實現了疲勞駕駛行為特征提取，對疲勞駕駛進行了分析；文獻[15]針對車輛行駛過程中的GPS設備采集提供的車輛行駛位置和速度等數據，根據超速情況劃分和確定重點監控車輛和實現對該車技術狀況和駕駛人情況信息的查詢。但是利用聚類分析算法分析RFID數據，識別車輛運行規律和識別非法營運車輛的研究還比較少見。

本文結合車輛RFID數據，運用數據挖掘中的經典聚類分析算法k-mediods對非法營運車輛進行識別，首先將從RFID獲取的車輛運行信息存入數據庫，并通過提取特征數據等對數據進行預處理得到車輛運行的行為數據，再利用PCA(主成分分析)處理得到車輛運行特征數據，最后通過k-mediods聚類分析算法對特征數據進行分析識別非法營運車輛。同時，針對k-mediods的各成分對相似性貢獻率相同和偶然性比較大的問題，結合RFID車輛數據特點，對算法缺點分別做了改進，提高了非法營運車輛的正確識別數量、降低了錯誤識別數量。

1基于k-mediods算法的非法營運車輛識別

1.1非法營運車輛識別系統流程

非法營運車輛識別系統流程如圖1所示。

圖1　非法營運車輛識別系統流程

先將車輛運行信息存儲于車輛信息數據庫；再對存放車輛信息的數據庫進行預處理，包括：分析并提取車輛運行的行為數據，建立數據倉庫并定時更新；然后對數據倉庫中的車輛運行行為數據進行PCA處理；接著利用k-mediods算法進行聚類分析，最后得到車輛分類識別結果中非法營運車輛信息并將其存入數據庫。若運行的車輛信息在非法營運車輛信息數據庫中，則此車被判定為非法營運車輛；反之被判定為合法車輛。

其中，分析的車輛信息為RFID采集的數據，包括車牌號碼、車輛通過地點、車輛通過時間；提取的行為特征數據包括車牌號碼、通過時間間隔、平均通過時長、時間間隔方差、通過頻次、高峰時期通過占比等相關信息；PCA處理之后得到6維車輛運行特征數據和每一維數據貢獻率；k-mediods聚類算法分析輸出基于RFID的車輛數據分類結果；數據倉庫更新比較耗時，因此頻率可設定為一周一次，時間定為凌晨車少的時間點。

1.2算法流程

RFID數據的k-mediods算法流程如圖2所示。

圖2　RFID數據的k-mediods算法流程圖

算法輸入：包含n個對象的車輛運行信息，結果簇的個數k。

算法輸出：k個簇的集合，使得所有對象與其最近中心點的相異度總和最小方法。

其步驟描述為：

1) 從數據庫中獲取聚類分析車輛的數據信息O(n)，需要聚類的個數k；

2) 隨機選擇k個對象作為初始中心點；

3) 將剩余對象分配到臨近中心的簇，并計算此時的目標函數oldE；

4) 隨機產生一個代替原中心的對象Orand；

5) 依次利用Orand代替原始的k個對象；

5.1) 初始化即將替代的簇中心下標i=0；

5.2) 判斷是否遍歷完所有簇中心，若遍歷完則轉向步驟6),否則轉向下一步5.3)；

5.3) 將剩余對象分配到臨近中心的簇，計算目標函數newE；

5.4) 計算此時代價函數S=newE-oldE；

5.5) 判斷S是否小于0，若小于0則轉向步驟5.7)，否則轉向下一步5.6)；

5.6) 下標i=i+1，轉向5.2);

5.7) 記錄此時下標j=i，并用Orand代替Oj，轉向步驟5.3);

6) 結束。

算法其他說明：

a) 輸入的n個對象的車輛信息，包含車牌號、已知的車輛類型以及經過PCA處理之后的車輛運行特征數據，同時對這些特征數據進行了歸一化處理，歸一化處理公式如下：

(1)

其中，norci(p)表示第i個對象在第p維特征數據經過歸一化處理的結果；c表示車輛信息的對象；ci(p)表示第i個對象在第p維特征數據值；min(c(p))表示所有車輛信息中的第p維特征數據值的最小值；max(c(p))表示所有車輛信息中的第p維特征數據值的最大值。

b) 輸入的結果簇k為經驗值，其確定方法在本文不做討論。

c) 目標函數E的公式如下：

(2)

其中j表示聚類分析后簇的序號，范圍為：1到k；i為對象序號，范圍為：1到n；cj表示第j個簇的中心；xi表示第i個對象；dist表示求cj與xi歐式距離。其中dist(cj,xi)的公式如下：

(3)

其中cj(p)表示cj的第p個運行特征數據，m表示對象共有多少特征數據。

式(1)的意義為：分別將屬于第j個簇中心的對象xi與所在簇中心cj之間的距離的平方依次相加，表示聚類分析后簇內部數據的差異性，在一定范圍內，目標函數E越小，聚類分析效果越好。

d) 代價函數公式如下：

S=newE-oldE

(4)

其中newE表示利用隨機對象替換原簇中心之后的目標函數值，oldE表示原對象的目標函數值。若S<0，則可以替換原簇中心；反之，則不能替換原簇中心。

2k-mediods算法在車輛RFID數據應用的改進

k-mediods算法是一種使目標函數下降最快的方法，屬于啟發式搜索算法，能從n個對象中找出以k個中心點為代表的一個局部優化劃分聚類。與k-means算法比較，k-mediods算法解決了k-means算法本身的缺陷：對初始值依賴過大的問題和對噪聲點、離群點敏感型問題[16,17]。但是仍存在以下缺點：

a) k-mediods算法利用歐式距離表征其相似性，數據的每個屬性對距離的貢獻都一樣，這樣不能體現出屬性的重要程度，因此無法達到良好的聚類效果。

b) 在算法中僅僅是隨機指定一個非代表對象Orandom來依次替換代表對象Oj，雖然在時間復雜度比較小，運行時間也比較小，但是偶然性太大，不能達到良好的聚類效果。

因此針對以上2個缺點，結合車輛RFID數據特點對算法進行了2種改進。

2.1改進一：基于距離貢獻率的改進

由k-mediods算法的缺點a)，其使用歐式距離度量相似性的過程中，每個屬性對距離貢獻率一樣。因此提出以下改進，在非法營運車輛識別系統中經過PCA分析和處理之后，由于對象每一維對數據的影響不同，故根據其重要程度為每一維乘以其權值wp，其中：

(5)

RFID數據經過PCA處理之后，每一維特征數據的重要程度不一樣，第一維的數據占了很大的比重，其對數據分析而言是最重要的，第二維次之，剩余維依次減小。這樣改進可以增加最主要的成分對計算相似度的貢獻率，適合處理基于車輛RFID數據。因此，將式(3)中的歐式距離改進為式(6)：

(6)

與式(3)相比，考慮了每一維車輛運行特征數據的重要程度對距離的影響，將權值wp乘上相應運行特征數據值與簇中心的歐式距離。

2.2改進二：基于偶然性的改進

由于k-mediods算法的缺點b)，其算法偶然性太大，因此提出以下改進，在算法中僅僅是隨機指定一個非代表性對象Orandom來依次替換代表對象Oj，修改為依次用所有的非代表性對象Oi(i=1,2,…,n)來替代Oj，再依次計算代價函數。

這樣改進可以排除隨機指定非代表性對象的偶然性，得到在每一輪換的過程中使得目標函數值最小的替換對象，即最優替換對象。在非法營運車輛識別系統中后臺處理使得系統對時間的敏感度不高，因此，此改進適合處理基于車輛RFID數據。

3結果分析

在Win7環境下，使用VC++平臺實現本文提出的基于k-mediods算法及其改進的非法營運車輛識別系統。通過車輛RFID的數據實驗數據中排除了出租車的干擾后共1762輛車，包含：公交車57輛、長途車40輛、社會車1635輛、非法營運車30輛。在對基于車輛RFID數據進行分類和處理時，關心的結果是非法營運車輛正確識別數量、誤識別數量，因此實驗結果重點分析和對比非法營運車輛正確識別數量和誤識別數量。實驗結果曲線均是經過15次車輛運行數據得出的平均值，簇數目k取值從1到30。

3.1k-mediods算法結果分析

主要分析用最原始的k-mediods來分析經過標準化，但沒有經過處理的車輛RFID數據運行特征數據，實驗結果如圖3所示。

圖3　非法營運車輛識別、誤識別數量曲線圖

根據非法車輛識別數量、非法車輛曲線圖可以分析得出最佳k值為14，此時的正確識別數量平均值為29.93輛，錯誤識別數量為2.13輛。再進一步分析效果相對較好的一段曲線k從10到18之間所有實驗結果。如表1所示。

表1　提取監控視頻關鍵幀實驗結果表

表1中i為實驗次數，k為相應的簇個數，N為正確識別數目。從15次實驗的非法車輛正確識別數量來看，其偶然性太大，比如在k=11的時候，有2次識別的非法營運車數量為0輛，1次識別的非法營運車數量為26輛，12次識別的非法營運車數量為30輛。因此需要對算法進行改進以更好地適應本系統中車輛RFID數據。

3.2基于距離貢獻率改進前后結果對比與分析

主要分析借助于改進一算法對標準化的數據乘以相應權值之后的改進k-mediods改進算法時間復雜度雖然比原來算法有所提高，但本算法在分析非法營運車輛的應用中是后臺運行，不需要考慮算法的運行時間，其識別率的實驗結果如圖4所示。

圖4　算法改進一之后的非法車輛識別、誤識別數量曲線

根據非法車輛識別數量和非法車輛曲線圖，經分析可以得出最佳k值為10，此時的正確識別出來平均值為30輛，錯誤識別數量為0.4輛。雖然還是有誤識別的車輛，但是與對車輛RFID運行特征數據利用k-mediods算法進行改進以前的識別結果相比：非法車輛正確識別數量明顯增加，此時可以完全識別，同時誤識別數量明顯減少，驗證了算法改進一的合理性。

3.3基于偶然性改進前后結果對比與分析

主要分析在算法改進一的基礎上再對算法進行改進二，對標準化的數據乘以相應權值之后，利用所有非對象點替換隨機點的k-mediods算法時間復雜度雖然比原來算法高，但本算法在分析非法營運車輛的應用中是后臺運行，不需要考慮算法的運行時間，其識別率的實驗結果如圖5所示。

圖5　算法改進二之后的非法車輛識別、誤識別數量曲線

根據非法車輛識別數量和非法車輛曲線圖，經分析可以得出最佳k值為18、19，此時的正確識別數量平均值均為30輛，錯誤識別數量均為0輛。與對車輛RFID運行特征數據利用改進一之后的k-mediods算法的識別結果相比：全部正確識別非法營運車輛，并且誤識別數量有明顯減少。其中k從3到19的正確識別數量均為30輛，而最大的誤識別率也只有2輛，因此算法穩定性明顯提高，降低了偶然性帶來的影響，驗證了算法改進二的合理性。

3.4算法改進實驗結果前后對比

算法經過改進前后，其在最佳k值的情況下，非法營運車輛正確、錯誤識別平均數量對比如表2所示。

表2　算法改進前后實驗結果對比表

由表2可得：原始k-mediods算法能夠識別出非法營運車輛。經過基于距離貢獻率的算法改進之后，非法營運車輛正確識別數量達到30，即可以完全識別出非法營運車輛；錯誤識別數量也有明顯下降。再經過基于偶然性的算法改進之后，在最佳k值得情況下，也可以完全識別出非法營運車輛，同時錯誤識別非法營運車輛的數量降低為0。由此也可以得原始算法的合理性和算法改進的合理性。

4結語

本文結合車輛RFID數據，利用k-mediods聚類分析算法對非法營運車輛進行識別，同時，針對k-mediods算法的缺點進行了基于距離貢獻率和偶然性的改進。實驗結果表明，能夠有效地識別出非法營運車輛，經過改進之后，提高了算法穩定性和非法營運車輛的正確識別數量、降低了錯誤識別數量。但算法中的聚類數量k值憑經驗得出，在以后研究中，將進一步完善算法，使得算法能夠結合自動訓練合適的k值范圍。

參考文獻

[1] 郭譞.涉非法營運車輛案件的情況分析[J].法制與經濟,2014(3):100-102.

[2] 祁巍巍.非法營運車輛的監管及其對策研究[D].華東理工大學,2012.

[3] 付華偉,何小敏,許亮,等.基于RFID和遺傳算法的實時炸藥倉儲優化操作[J].計算機工程與科學,2014,36(2):286-291.

[4] 鄭方偉,周明天,張宇威.RFID自助收銀研究和設計[J].微電子學與計算機,2011,28(3):186-189.

[5] 王德玉,張霖言,劉紫熠.RFID技術在電力企業中的應用及前景[J].天津電力技術,2014(2):78-80.

[6] Malakar B,Roy B K.Survey of RFID applications in railway industry[C]//Automation,Control,Energy and Systems (ACES),2014 First International Conference on.IEEE,2014:1-6.

[7] 張昀,周涑,任海軍,等.數據挖掘在電力負荷壞數據智能辨識與修正中的應用[J].重慶大學學報ISTIC EI,2013,36(2):73-78.

[8] 張成叔.數據挖掘中關聯規則挖掘方法的研究及應用[J].軟件,2013,34(9):138.

[9] Fan X D.Clustering Analysis Based on Data Mining Applications[J].Applied Mechanics and Materials,2013:1026-1029.

[10] Stutz C,Runkler T A.Classification and prediction of road traffic using application-specific fuzzy clustering[J].Fuzzy Systems,IEEE Transactions on,2002,10(3):297-308.

[11] 楊祖元,徐姣,羅兵,等.基于SFLA-FCM聚類的城市交通狀態判別研究[J].計算機應用研究,2010(5):1743-1745.

[12] 許洪國,劉兆惠,王超.道路安全等級定權聚類評價模型及因素辨析[J].交通運輸工程學報,2007,7(2):94-98.

[13] 郭保青,朱力強,史紅梅.基于快速DBSCAN聚類的鐵路異物侵限檢測算法[J].儀器儀表學報,2012,33(2):241-247.

[14] 毛吉吉,初秀民,嚴新平,等.汽車駕駛員駕駛疲勞監測技術研究進展[J].中國安全科學學報,2005,15(3):108-112.

[15] 丁博.基于數據挖掘的車輛運行狀態監控技術應用研究[D].北京交通大學,2011.

[16] 孫勝,王元珍.基于核的自適應k-Medoid聚類[J].計算機工程與設計,2009(3):674-675.

[17] Park H S,Jun C H.A simple and fast algorithm for K-medoids clustering[J].Expert Systems with Applications,2009,36(2):3336-3341.

[18] 姚麗娟,羅可,孟穎.一種新的k-medoids聚類算法[J].計算機工程與應用,2013,49(19):153-157.

RECOGNISING ILLEGAL OPERATION VEHICLES BASED ON K-MEDIODS AND ITS IMPROVED ALGORITHM

Shuai DanLan ZhangliLi Yicai

(SchoolofInformationScienceandEngineering,ChongqingJiaotongUniversity,Chongqing400074,China)

AbstractIn order to recognise the vehicles to be suspected operating illegally from a large number of social vehicles, improve the purposive intention and pertinence of the traffic administration in administrative enforcement, maintain the market order of road transportation and eliminate the hidden traffic safety hazard, we proposed the k-mediods-based illegal operation vehicles recognition algorithm in combination with RFID vehicle information data. In light of the shortcomings of k-mediods algorithm, we made two improvements on it, the distance contribution rate-based and the algorithm contingency-based respectively. To implement the illegal operation vehicles recognition, firstly it needs to extract vehicles’ RFID data, and carries out pretreatment on them, and then obtains the behaviour data of vehicles operation; secondly, it acquires the characteristics data of vehicles operation by means of PCA processing; finally, it recognises the illegal operation vehicles by k-mediods-based clustering analysis. Experimental results show that the algorithm has a clear flow, it can recognise the illegal operation vehicles effectively, meanwhile it can improve the stability of the algorithm by improving it, and in turn raises the numbers of correct recognition of the illegal operation vehicles, and decreases the numbers of wrong recognition as well.

Keywordsk-mediodsDistance contribution rateContingencyRFID

收稿日期：2014-12-11。重慶市教委科學技術研究項目(KJ1304 21)。帥丹，碩士生，主研領域：交通信息化。藍章禮，教授。李益才，副教授。

中圖分類號TP391

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.05.038