數據挖掘三大經典算法在交通領域的應用綜述

楊小平

（無錫職業技術學院，江蘇 無錫 214000）

0 引 言

近幾年，隨著我國經濟的快速發展，交通基礎設施建設規模不斷擴大，為了有效監控和管理各類交通基礎設施，提高道路運營和服務水平，特綜合了先進的信息技術、數據通信技術、電子傳感技術、控制技術及計算機技術，設計了能夠對大范圍交通設施進行實時、準確、高效管理的綜合交通管理系統——智能運輸系統（Intelligent Transportation System，ITS），該系統逐漸受到了世界各國交通研究者的高度重視[1]。

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

本文首先對數據挖掘技術中的三大經典算法進行原理描述，在此基礎上，對這些算法近些年在交通領域中的熱門應用進行綜述和總結性分析。

1 數據挖掘三大經典算法概述

1.1 C4.5算法

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

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

1.2 K-Means算法

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

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

圖2 K-Means算法聚類過程示意圖

1.3 SVM算法

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

2 數據挖掘三大經典算法在交通領域的應用

2.1 C4.5算法在交通中的應用

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

圖3 SVM算法分類過程示意圖

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

2.2 K-Means算法在交通中的應用

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

綜上所述，當需要對數據樣本進行歸類但又沒有可用的人工標定訓練數據時，以K-means為代表的聚類分析算法便成為最佳選擇。K-means算法通過數據的內部分布特征迭代進行相似度計算，可以自動對數據集進行歸類。在交通研究領域，交通檢測數據由于數量巨大、標定成本過高等原因導致在大部分應用中都沒有事先標定類別的訓練樣本，因此，K-means聚類算法就有了用武之地。

2.3 SVM算法在交通中的應用

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

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

3 結 語

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