數(shù)據(jù)挖掘三大經(jīng)典算法在交通領(lǐng)域的應(yīng)用綜述

引 言

近幾年，隨著我國(guó)經(jīng)濟(jì)的快速發(fā)展，交通基礎(chǔ)設(shè)施建設(shè)規(guī)模不斷擴(kuò)大，為了有效監(jiān)控和管理各類交通基礎(chǔ)設(shè)施，提高道路運(yùn)營(yíng)和服務(wù)水平，特綜合了先進(jìn)的信息技術(shù)、數(shù)據(jù)通信技術(shù)、電子傳感技術(shù)、控制技術(shù)及計(jì)算機(jī)技術(shù)，設(shè)計(jì)了能夠?qū)Υ蠓秶煌ㄔO(shè)施進(jìn)行實(shí)時(shí)、準(zhǔn)確、高效管理的綜合交通管理系統(tǒng)——智能運(yùn)輸系統(tǒng)（Intelligent Transportation System， ITS），該系統(tǒng)逐漸受到了世界各國(guó)交通研究者的高度重視 [1]。

智能運(yùn)輸系統(tǒng)的一個(gè)顯著特點(diǎn)是以交通信息的收集、處理、發(fā)布、交換、分析、利用為主線，為交通參與者提供多樣服務(wù)。在上述各環(huán)節(jié)中，交通信息的收集是基礎(chǔ)工作，與交通服務(wù)水平的質(zhì)量緊密相關(guān)，因此各國(guó)研究者對(duì)交通信息收集技術(shù)展開了大量研究 [2]。一般而言，交通信息的收集方式主要分為兩種，即利用人工方式進(jìn)行交通數(shù)據(jù)調(diào)查，如交通問卷調(diào)查 ；基于交通檢測(cè)設(shè)備由計(jì)算機(jī)自動(dòng)完成數(shù)據(jù)收集， 常見的技術(shù)包括利用微波車檢器、超聲波車檢器、感應(yīng)線圈、視頻車檢器等交通檢測(cè)設(shè)備收集交通流量、速度和占有率等數(shù)據(jù)指標(biāo)。隨著這些交通檢測(cè)技術(shù)的日益升級(jí)以及國(guó)家對(duì)智能交通的大力倡導(dǎo)，我國(guó)各地區(qū)的交通管理部門已經(jīng)積累了大量歷史交通數(shù)據(jù)，如何對(duì)這些數(shù)據(jù)進(jìn)行有效分析和利用，以進(jìn)一步改善整個(gè)道路系統(tǒng)的服務(wù)水平，成為當(dāng)前交通研究領(lǐng)域一項(xiàng)有價(jià)值的課題。在此背景下，能夠從海量數(shù)據(jù)中挖掘出有用規(guī)律和模式的數(shù)據(jù)挖掘技術(shù)便成為研究者手中的利器。

本文首先對(duì)數(shù)據(jù)挖掘技術(shù)中的三大經(jīng)典算法進(jìn)行原理描述，在此基礎(chǔ)上，對(duì)這些算法近些年在交通領(lǐng)域中的熱門應(yīng)用進(jìn)行綜述和總結(jié)性分析。

1 數(shù)據(jù)挖掘三大經(jīng)典算法概述

1.1 C4.5算法

C4.5 算法是數(shù)據(jù)挖掘?qū)W科中用于機(jī)器自動(dòng)分類的一種決策樹學(xué)習(xí)算法，其基本思想是基于信息熵理論和樹狀分類規(guī)則構(gòu)建樣本屬性與樣本類別之間的映射關(guān)系[3-4]。C4.5 算法的前身是由著名機(jī)器學(xué)習(xí)專家 Quinlan 在 1986 年提出的 ID3 算法[5]，采用遞歸分治的方式進(jìn)行決策樹的迭代構(gòu)建。在構(gòu)建過程中依據(jù)最優(yōu)劃分屬性的屬性值將當(dāng)前層的樣本集劃分為若干子集。ID3 算法基于信息熵理論選擇當(dāng)前樣本集中具有最大信息增益的屬性作為最優(yōu)劃分屬性。然而，這種做法容易導(dǎo)致最優(yōu)劃分屬性的選擇偏向于取值較多的屬性，為此， Quinlan 又在 1993 年提出了 ID3 的改進(jìn)算法——C4.5 算法。與前者不同，C4.5 算法采用信息增益率確定最優(yōu)劃分屬性， 以顯著改進(jìn)算法的泛化性能。此外，C4.5 算法還能夠?qū)B續(xù)型屬性及屬性值空缺的情況進(jìn)行處理，并且在樹剪枝方面也采用了較為成熟的策略。圖 1 所示為利用 C4.5 決策樹算法進(jìn)行分類決策的過程示例。圖中描述的樣本具有 3 個(gè)屬性，包括天氣（Outlook）、空氣濕度（Humidity）、是否有風(fēng)（Windy），以及1個(gè)決策類別（是否去打高爾夫）。

注 ：最左邊的一條分類決策規(guī)則是 ：如果晴天且空氣濕度不大于 75，則可以去打高爾夫

                                                                                                       圖1 基于 C4.5 決策樹算法進(jìn)行分類決策

1.2 K-Means算法

K-Means算法 [6] 是一種無監(jiān)督學(xué)習(xí)算法，是數(shù)據(jù)挖掘?qū)W科中常用的聚類技術(shù)之一。它通過對(duì)樣本內(nèi)部分布特征進(jìn)行歸納和描述（采用“類內(nèi)相似性最大，類間相似性最小”的歸類原則），將樣本集自動(dòng)劃分成指定的 k個(gè)類別。該算法最顯著的特點(diǎn)是無需人工提前標(biāo)定樣本類別。基本思想 ：從樣本集中隨機(jī)選擇 k 個(gè)樣本，每個(gè)樣本代表一個(gè)類中心。對(duì)剩余每個(gè)樣本，根據(jù)其與各類中心之間的距離，將它指派到距離最相近的類中，然后計(jì)算各類新的類中心。不斷重復(fù)上述過程， 直至聚類函數(shù)收斂。聚類函數(shù)見式（1）：

式中 ：E是數(shù)據(jù)集中所有樣本的平方誤差和 ；p是給定的樣本向量 ；mi是類 Ci的中心（均值）向量。K-Means算法簡(jiǎn)單，計(jì)算復(fù)雜度低，可擴(kuò)展性強(qiáng)，得到了眾多研究者的青睞。然而， 它本質(zhì)上是一種貪心算法，可能會(huì)收斂到“局部最優(yōu)”，而且對(duì)初始中心點(diǎn)的選擇較為敏感。此外，初始參數(shù) k需要人工設(shè)定。圖 2所示為利用 K-Means算法進(jìn)行聚類的示意圖。

1.3 SVM算法

SVM（Support Vector Machine，SVM）算法 [7] 屬于有監(jiān)督學(xué)習(xí)算法范疇，是一種機(jī)器自動(dòng)分類算法。該算法通過尋求結(jié)構(gòu)化風(fēng)險(xiǎn)最小提高學(xué)習(xí)機(jī)的泛化能力，實(shí)現(xiàn)經(jīng)驗(yàn)風(fēng)險(xiǎn)和置信范圍最小化，實(shí)現(xiàn)在統(tǒng)計(jì)樣本量較少的情況下依然能獲得良好分類性能的目的。SVM 算法對(duì)復(fù)雜的非線性決策邊界的建模準(zhǔn)確度極高，且不容易出現(xiàn)“過擬合”現(xiàn)象。缺點(diǎn)是訓(xùn)練時(shí)間較長(zhǎng)，因此適合小樣本分類問題。圖 3 描述了利用SVM 算法對(duì)樣本進(jìn)行分類的過程。

2 數(shù)據(jù)挖掘三大經(jīng)典算法在交通領(lǐng)域的應(yīng)用

2.1 C4.5算法在交通中的應(yīng)用

ZHANG 等人 [8-9] 采用 C4.5 算法對(duì)交通沖突數(shù)據(jù)進(jìn)行了建模分析，并利用所構(gòu)建的決策樹對(duì)造成交通沖突的各種影響因素、種類和碰撞程度以及受影響人群進(jìn)行了細(xì)分，進(jìn)而歸納分析出導(dǎo)致各種交通沖突的主要影響因素及其對(duì)應(yīng)的沖突程度和受影響人群的特性。Park 等人 [10] 提出了一種基于 C4.5算法的路線航策略，并將其應(yīng)用于個(gè)人車載導(dǎo)航系統(tǒng)，取得了良好的效果。Griffin 和 Huang[11] 基于收集的 GPS 數(shù)據(jù)對(duì)交通出行目的進(jìn)行了分類和決策，所構(gòu)建的模型基于 C4.5 決策樹算法。他們的實(shí)驗(yàn)結(jié)果顯示，C4.5 決策樹算法的分類效果很好，且最終得到的分類規(guī)則具有較強(qiáng)的可解釋性，容易理解。徐磊和方源敏 [12] 對(duì) C4.5 算法進(jìn)行了改進(jìn)，并基于改進(jìn)的模型對(duì)交通擁堵和各種影響因素之間的內(nèi)在關(guān)系進(jìn)行了挖掘分析，獲取的規(guī)則對(duì)于城市交通管理和疏導(dǎo)具有很強(qiáng)的指導(dǎo)意義。徐春榮 [13] 研究了 C4.5 算法在交通擁堵分類中的可行性和有效性，考慮到 C4.5 算法的時(shí)間復(fù)雜度較高，在算法學(xué)習(xí)過程中引入了基于實(shí)例的規(guī)則進(jìn)行提速。改進(jìn)后的模型不僅能以很高的精度分類交通擁堵程度，而且大大降低了分類所花費(fèi)的時(shí)間開銷。趙明 [14] 通過分析天氣、時(shí)間段、特殊路況、道路設(shè)施質(zhì)量及節(jié)假日等影響因素，構(gòu)建了基于 C4.5 算法的預(yù)測(cè)模型，對(duì)未來的交通擁堵程度進(jìn)行預(yù)測(cè)。他們的實(shí)驗(yàn)結(jié)果表明，基于 C4.5 算法的預(yù)測(cè)模型在交通擁堵預(yù)警應(yīng)用中具有顯著的優(yōu)勢(shì)和可靠性。

通過上述分析可以看出，C4.5 算法在交通領(lǐng)域主要應(yīng)用于交通的分類決策。由于 C4.5 算法基于信息熵理論，具有堅(jiān)實(shí)的理論基礎(chǔ)，因此具有出色的分類性能，并且最終導(dǎo)出的分類規(guī)則具有較強(qiáng)的可解釋性，使其在交通影響因素分析研究領(lǐng)域具有顯著優(yōu)勢(shì)。

2.2 K-Means算法在交通中的應(yīng)用

Bocarejo 和Díaz 對(duì)哥倫比亞首都波哥大的交通事故數(shù)據(jù)進(jìn)行了研究，并利用 K-Means 算法進(jìn)行了聚類分析。研究結(jié)果表明，基于 K-Means 的聚類分析方法能夠有效找出隱藏在事故數(shù)據(jù)中的規(guī)律和模式。他們找出的一個(gè)有趣模式是，在波哥大市區(qū)發(fā)生的致命交通事故主要分為兩種類型，一類是公交車與行人相互沖突 ；另一類是公交車與摩托車相互沖突。因此，他們建議從道路運(yùn)營(yíng)和安全管理角度對(duì)這兩類事故進(jìn)行重點(diǎn)監(jiān)控，并制定相應(yīng)的預(yù)警政策。Raiwani 和 Baluni 對(duì)印度烏塔拉坎德邦的交通事故數(shù)據(jù)進(jìn)行了 K-Means 聚類，分析的數(shù)據(jù)指標(biāo)包括交通事故發(fā)生的具體地點(diǎn)、所屬區(qū)域、發(fā)生時(shí)間以及交通事故中受傷或死亡人員的姓名、年齡、性別、家庭地址。聚類結(jié)果顯示出一些有趣的關(guān)聯(lián)模式，例如，在該城市的哪幾個(gè)地區(qū)更易發(fā)生交通事故，事故中人員受傷程度與性別之間是否存在內(nèi)在關(guān)聯(lián)等。Deb Nath 等人利用改進(jìn)的K-Means 算法對(duì)道路行程時(shí)間指標(biāo)進(jìn)行了預(yù)測(cè)。他們的研究表明，相較于連續(xù)滑動(dòng)平均方法（SMA）、鏈?zhǔn)狡骄椒ǎ–A）及樸素貝葉斯分類方法（NBC），改進(jìn)的 K-Means 算法具有更加顯著的預(yù)測(cè)效果。Pankaj 和 Patil 在交通標(biāo)志識(shí)別（Traffic Sign Recognition，TSR）系統(tǒng)中采用 K-Means 算法進(jìn)行交通標(biāo)志圖像分割，顯著改善了交通標(biāo)志的識(shí)別效果。閏明月基于K-means 算法對(duì)城市交通客流量數(shù)據(jù)進(jìn)行了分析，得到了一些有用的結(jié)論，為城市交通規(guī)律分析、城市規(guī)劃與交通政策的制定提供了依據(jù)。高勃等人采用 K-means 算法對(duì)北京地鐵路網(wǎng)重要度進(jìn)行了聚類分析。研究發(fā)現(xiàn)，在不同時(shí)間段，北京地鐵車站和區(qū)間在路網(wǎng)中的重要度是動(dòng)態(tài)變化的，路網(wǎng)中車站（區(qū)間）的重要度異質(zhì)性也隨時(shí)間而改變。他們構(gòu)建的聚類模型能夠較好地從歷史數(shù)據(jù)中挖掘出北京地鐵路網(wǎng)的規(guī)律模式。沈吟東等學(xué)者基于大量 GPS 運(yùn)營(yíng)數(shù)據(jù)，創(chuàng)新性地將K-means聚類算法應(yīng)用于公交運(yùn)營(yíng)時(shí)段劃分，并結(jié)合十堰市和?？谑泄坏臄?shù)據(jù)案例，驗(yàn)證了所提出模型的可行性和有效性。

綜上所述，當(dāng)需要對(duì)數(shù)據(jù)樣本進(jìn)行歸類但又沒有可用的人工標(biāo)定訓(xùn)練數(shù)據(jù)時(shí)，以 K-means 為代表的聚類分析算法便成為最佳選擇。K-means 算法通過數(shù)據(jù)的內(nèi)部分布特征迭代進(jìn)行相似度計(jì)算，可以自動(dòng)對(duì)數(shù)據(jù)集進(jìn)行歸類。在交通研究領(lǐng)域， 交通檢測(cè)數(shù)據(jù)由于數(shù)量巨大、標(biāo)定成本過高等原因?qū)е略诖蟛糠謶?yīng)用中都沒有事先標(biāo)定類別的訓(xùn)練樣本，因此，K-means 聚類算法就有了用武之地。

2.3 SVM算法在交通中的應(yīng)用

Borkar 和Malik 通過布設(shè)在路側(cè)的傳聲器收集車輛的音頻數(shù)據(jù)，并基于這些數(shù)據(jù)估計(jì)交通密度狀態(tài)。他們利用各種核函數(shù) SVM 分類器對(duì)收集到的數(shù)據(jù)進(jìn)行學(xué)習(xí)和分類。最終， 數(shù)據(jù)樣本被分成 3 類（Low，Medium，Heavy），分別對(duì)應(yīng)交通密度低（自由流）、交通密度中等（暢通）、交通密度很大（擁堵） 三種狀態(tài)。實(shí)驗(yàn)結(jié)果表明，基于二次核函數(shù)的 SVM 分類器可以獲得 96.67% 的分類精度，而基于多項(xiàng)式核函數(shù)的 SVM 分類器分類準(zhǔn)確率高達(dá) 98.33%。Alioua 等人基于 SVM 人臉檢測(cè)技術(shù)提取車輛駕駛者的臉部特征，并根據(jù)眼睛和鼻子的特征信息判斷駕駛者是否處于疲勞駕駛狀態(tài)。采用這種方法得到的識(shí)別率達(dá) 94%。一些研究者設(shè)計(jì)了基于 SVM 算法的分類器對(duì)由車輛攝像頭捕捉的交通標(biāo)志符號(hào)圖像進(jìn)行識(shí)別和歸類， 研究顯示，利用 SVM 算法在復(fù)雜決策邊界情形下的高精度分類性能，可以有效對(duì)在非理性條件下（復(fù)雜道路條件、雨霧天氣、有遮擋物等）的交通標(biāo)志進(jìn)行準(zhǔn)確辨認(rèn)和識(shí)別。此外， 還有一些學(xué)者利用 SVM算法對(duì)交通流短時(shí)預(yù)測(cè)課題展開了研究，并取得了不錯(cuò)的效果。

SVM 算法是一種有堅(jiān)實(shí)理論基礎(chǔ)的小樣本學(xué)習(xí)方法，從本質(zhì)上看，它避開了從歸納到演繹的傳統(tǒng)過程，實(shí)現(xiàn)了從訓(xùn)練樣本到分類樣本的“轉(zhuǎn)導(dǎo)推理”，大大簡(jiǎn)化了機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域的分類和回歸問題。因此，SVM 算法在交通事件自動(dòng)檢測(cè)、交通狀態(tài)判別及短時(shí)交通流預(yù)測(cè)等方面均有成功的應(yīng)用。需要說明的是，SVM 是借助二次規(guī)劃來求解支持向量， 而求解二次規(guī)劃涉及高階矩陣的計(jì)算，此時(shí)矩陣的存儲(chǔ)和計(jì)算將耗費(fèi)大量的計(jì)算機(jī)資源，因此 SVM 算法對(duì)大規(guī)模訓(xùn)練樣本難以實(shí)施。

3 結(jié) 語

本文簡(jiǎn)要概述了 C4.5，K-Means 和 SVM 三大經(jīng)典數(shù)據(jù)挖掘算法的基本原理，并對(duì)這三種算法在交通領(lǐng)域的有效應(yīng)用進(jìn)行了綜述，以期對(duì)研究者充分發(fā)掘它們?cè)诮鉀Q交通問題中的潛力提供有益借鑒。在未來的研究工作中，筆者將進(jìn)一步研究和探討這些算法的原理及其在交通領(lǐng)域的應(yīng)用。