引 言

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

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

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

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

1.1 C4.5算法

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

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

                                                                                                       圖1 基于 C4.5 決策樹算法進行分類決策

1.2 K-Means算法

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

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

1.3 SVM算法

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

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

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

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

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

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

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

綜上所述，當(dāng)需要對數(shù)據(jù)樣本進行歸類但又沒有可用的人工標(biāo)定訓(xùn)練數(shù)據(jù)時，以 K-means 為代表的聚類分析算法便成為最佳選擇。K-means 算法通過數(shù)據(jù)的內(nèi)部分布特征迭代進行相似度計算，可以自動對數(shù)據(jù)集進行歸類。在交通研究領(lǐng)域， 交通檢測數(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ù)估計交通密度狀態(tài)。他們利用各種核函數(shù) SVM 分類器對收集到的數(shù)據(jù)進行學(xué)習(xí)和分類。最終， 數(shù)據(jù)樣本被分成 3 類（Low，Medium，Heavy），分別對應(yīng)交通密度低（自由流）、交通密度中等（暢通）、交通密度很大（擁堵） 三種狀態(tài)。實驗結(jié)果表明，基于二次核函數(shù)的 SVM 分類器可以獲得 96.67% 的分類精度，而基于多項式核函數(shù)的 SVM 分類器分類準(zhǔn)確率高達 98.33%。Alioua 等人基于 SVM 人臉檢測技術(shù)提取車輛駕駛者的臉部特征，并根據(jù)眼睛和鼻子的特征信息判斷駕駛者是否處于疲勞駕駛狀態(tài)。采用這種方法得到的識別率達 94%。一些研究者設(shè)計了基于 SVM 算法的分類器對由車輛攝像頭捕捉的交通標(biāo)志符號圖像進行識別和歸類， 研究顯示，利用 SVM 算法在復(fù)雜決策邊界情形下的高精度分類性能，可以有效對在非理性條件下（復(fù)雜道路條件、雨霧天氣、有遮擋物等）的交通標(biāo)志進行準(zhǔn)確辨認(rèn)和識別。此外， 還有一些學(xué)者利用 SVM算法對交通流短時預(yù)測課題展開了研究，并取得了不錯的效果。

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

3 結(jié) 語

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