基于TAN分類算法的交通事件檢測*

凃 強 李大韋 程 琳

(東南大學(xué)交通學(xué)院 南京 210096)

0 引 言

交通擁堵是全世界大多數(shù)城市都面臨的難題，它可以分為2類：復(fù)發(fā)性擁堵和非復(fù)發(fā)性擁堵。復(fù)發(fā)性擁堵由過度交通需求產(chǎn)生，短時間內(nèi)難以改善；而非復(fù)發(fā)性擁堵通常由道路上的偶發(fā)性事件引起，比如交通事故，故障停車等，如果不及時處理，會造成巨大損失。事件管理系統(tǒng)(IMS)能夠及時對事件進行處理，減少后續(xù)影響，是先進的交通管理系統(tǒng)的重要組成部分。作為事件管理系統(tǒng)的核心技術(shù)，事件檢測算法是一個十分有價值的研究課題。

事件檢測算法根據(jù)不同的方法通常被分成5類：比較算法、統(tǒng)計學(xué)算法、時間序列及濾波算法、交通理論算法和先進算法。加州算法是比較算法的經(jīng)典例子，也是首次廣泛實現(xiàn)的事件檢測算法之一[1]，通常用來作為評估其他算法的基準(zhǔn)。統(tǒng)計算法使用標(biāo)準(zhǔn)的統(tǒng)計技術(shù)識別交通流參數(shù)的突變，包括標(biāo)準(zhǔn)正太偏差算法[2]和貝葉斯算法[3]。時間序列和濾波算法將交通量參數(shù)作為時間序列，用時間序列偏差行為來表明事件，其中包括移動平均[4]和平滑指數(shù)算法[5]。交通理論的經(jīng)典算法是McMaster算法，它是基于交通流密度曲線中的位置決定交通狀態(tài)，然后根據(jù)從一個狀態(tài)到另一個狀態(tài)的轉(zhuǎn)移來檢測事件[6]。先進算法是基于先進的數(shù)學(xué)模型，如神經(jīng)網(wǎng)絡(luò)[7-8]、模糊聚類[9]、支持向量機[10]等方法，這些算法在實驗室環(huán)境均有良好的表現(xiàn)。

為了滿足先進交通管理系統(tǒng)的普遍性需求，貝葉斯網(wǎng)絡(luò)被用來開發(fā)通用算法[11]。測試結(jié)果表明，基于貝葉斯的算法具有穩(wěn)定的性能和很強的可轉(zhuǎn)化性。目前，國內(nèi)將貝葉斯網(wǎng)絡(luò)應(yīng)用于交通事件檢測的研究相對較少，采用的方法主要是基于貝葉斯網(wǎng)絡(luò)或樸素貝葉斯(NB)分類算法[12-14]。但是，基于貝葉斯的算法比較依靠專家經(jīng)驗，比如，它的網(wǎng)絡(luò)結(jié)構(gòu)需要人為設(shè)定。樸素貝葉斯分類算法，作為普通貝葉斯算法的改進，不需要人為設(shè)定網(wǎng)絡(luò)結(jié)構(gòu)，但算法中包含了許多嚴(yán)格的假設(shè)，比如，假設(shè)所有變量之間是嚴(yán)格獨立的。

本文采用了貝葉斯網(wǎng)絡(luò)的一個特殊形式，樹增強樸素貝葉斯分類器，用來作為事件檢測算法，它的網(wǎng)絡(luò)結(jié)構(gòu)和參數(shù)均是由數(shù)據(jù)學(xué)習(xí)確定的，可以有效減少對專家知識的依賴，同時考慮了變量之間的相關(guān)性，相比貝葉斯網(wǎng)絡(luò)和樸素貝葉斯分類算法具有更好的應(yīng)用前景。

1 TAN分類器簡介

1.1 貝葉斯網(wǎng)絡(luò)

貝葉斯網(wǎng)絡(luò)是由隨機變量集合組成的聯(lián)合U={X1,X2,…,Xn}概率分布的編碼，形式上是一對二元數(shù)組B=(G,θ)。G是有向無環(huán)圖，其節(jié)點對應(yīng)隨機變量X1,X2，…,Xn，有向邊代表變量之間的相依性。圖的結(jié)構(gòu)G編碼了獨立性假設(shè)：在給定每個節(jié)點父節(jié)點的條件下，該節(jié)點獨立于它的非自子孫節(jié)點，二元組的第二部分代表這個網(wǎng)絡(luò)每一個變量條件概率分布的集合，集合中元素為，其中xi?Xi, 且Πxi?ΠXi表示Xi在G中的父變量集。B在U上定義了唯一的聯(lián)合概率分布

PB(X1,X2,…,Xn)=

(1)

貝葉斯網(wǎng)絡(luò)用于事件檢測，它必須包含分類變量INC，和屬性變量A1,A2，…，An。A1,A2，…，An代表交通流參數(shù)，INC=1表示事件發(fā)生。在IMS中，實時更新，并用貝葉斯網(wǎng)絡(luò)對P(INC=1|A1,A2，…，An)進行更新。

因為假設(shè)獨立，貝葉斯網(wǎng)絡(luò)用于事件檢測時，分類變量INC必須與屬性變量建立聯(lián)系，每個屬性變量信息均可以用來更新事件的可能性。由于貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí)本身是1個NP問題，不能搜索整個網(wǎng)絡(luò)空間，現(xiàn)有研究中，主要依靠專家經(jīng)驗確定其結(jié)構(gòu)。圖1(a)展示了1個可能的貝葉斯事網(wǎng)絡(luò)結(jié)構(gòu)。

圖1 貝葉斯網(wǎng)絡(luò)、樸素貝葉斯和樹增強樸素貝葉斯分類器典型結(jié)構(gòu)Fig.1 Typical structures of Bayesian network,NB classifier and TAN classifier

1.2 樹增強樸素貝葉斯分類器

為了確定貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)，需要解決如何添加屬性變量的邊。解決這個問題最簡單的方法是假設(shè)每個屬性變量之間都是相互獨立的，此時不需要為每對屬性變量建立邊。這種形式的貝葉斯網(wǎng)絡(luò)經(jīng)常用于NB分類器，其結(jié)構(gòu)見圖1(b)。

樹增強貝葉斯分類器是一類基于NB分類器的網(wǎng)絡(luò)結(jié)構(gòu)，見圖1(c)，分類變量INC沒有父節(jié)點，每個屬性變量含有1個分類變量和至多1個屬性變量作為父節(jié)點。這表明，概率P(INC|A1,A2,…,An)將所有的屬性變量納入考慮，NB分類器中每個變量相互獨立的假設(shè)得到松弛，屬性變量之間的邊可以用訓(xùn)練數(shù)據(jù)獲得。

2 TAN分類算法

2.1 數(shù)據(jù)預(yù)處理

交通系統(tǒng)檢測器收集的交通特征參數(shù)通常包括：交通流量、占有率和速度等。這些交通數(shù)據(jù)均是連續(xù)的，并且其值域和單位都不相同。此外，駕駛員行為的隨機性和檢測器的測量誤差導(dǎo)致原始交通數(shù)據(jù)存在一定的隨機波動。因此，需要對原始交通數(shù)據(jù)進行一定預(yù)處理，才能應(yīng)用于檢測算法中。對原始數(shù)據(jù)的預(yù)處理流程包含3個部分：數(shù)據(jù)平滑、標(biāo)準(zhǔn)化和離散化。

1) 數(shù)據(jù)平滑。數(shù)據(jù)平滑處理是為了消除原始檢測數(shù)據(jù)的隨機波動?，F(xiàn)有研究中，采用的方法主要是移動平均的方法，這種方法雖然簡單易用，但是在處理交通事件突發(fā)的臨界區(qū)間時過于平滑，會增加平均檢測時間。為了克服這一缺點，采用小波去燥的方法對原始數(shù)據(jù)進行平滑處理，本文直接使用Matlab小波工具箱進行數(shù)據(jù)的平滑處理。

2) 標(biāo)準(zhǔn)化。小波去噪過后，需要對去噪交通數(shù)據(jù)進行標(biāo)準(zhǔn)化，將不同單位和值域的交通參數(shù)轉(zhuǎn)化到同一量綱區(qū)間內(nèi)，標(biāo)準(zhǔn)化過程主要是為了提高算法的可轉(zhuǎn)讓性，其采用公式見式(2)

(2)

式中：a′為標(biāo)準(zhǔn)化交通數(shù)據(jù)；a為去噪交通數(shù)據(jù)；Aα和Aβ分別為去噪交通數(shù)據(jù)的最小值和最大值。

3) 離散化。TAN分類器中的屬性變量應(yīng)為離散變量，因此，需要將連續(xù)交通數(shù)據(jù)進行離散化處理?，F(xiàn)有的研究方法，主要是根據(jù)專家經(jīng)驗預(yù)設(shè)分界點，從而將連續(xù)的交通數(shù)據(jù)劃分到不同區(qū)間進而到達離散化的效果。為了克服對專家經(jīng)驗的依賴，采用基于熵的方法對標(biāo)準(zhǔn)化交通測量值進行離散化處理，本方法選擇訓(xùn)練數(shù)據(jù)集最小熵值作為分界點，進行遞歸分區(qū)以達到分層離散化，具體步驟如下[15]。

步驟1。根據(jù)測量值A(chǔ)的屬性取值情況，分成m個區(qū)間，并給定類信息熵的閾值ξ，第i個區(qū)間的區(qū)間類信息熵的計算見式(3)。

(3)

式中：pij是區(qū)間i中類別為j的概率，可見區(qū)間i中包含的類別越小，Entropy(Ai)越小，表示該區(qū)間的離散化效果越好。

步驟2。合并所有相鄰、區(qū)間類信息熵為0且區(qū)間屬性類別相同的區(qū)間，計算所有的相鄰區(qū)間合并后的區(qū)間類信息熵，將區(qū)間類信息熵最小和不超過ξ的相鄰區(qū)間進行閉合，一直重復(fù)，直到找不到可以合并的相鄰區(qū)間；

步驟3。對離散化后的屬性值進行數(shù)字編號。

2.2 檢測算法

通過數(shù)據(jù)預(yù)處理，將交通事件作為0-1分類變量，交通特征參數(shù)作為屬性變量，從而將交通數(shù)據(jù)應(yīng)用到TAN分類算法中。交通事件inc的發(fā)生與否采用0-1變量進行表示，inc=0表示“不發(fā)生”，inc=1表示“發(fā)生”，其向量形式記為INC；類別為i的交通特征參數(shù)屬性變量為ai，其向量形式為Ai，i∈(1,2,…，n)；訓(xùn)練數(shù)據(jù)dk可以表示為{a1,…，an,inc}，一共m組數(shù)據(jù)，相應(yīng)的訓(xùn)練數(shù)據(jù)集為D={d1，d2,…,dm}={A1,A2,…，An,INC}。

2.2.1 學(xué)習(xí)和推理

在1.2中，TAN分類器的網(wǎng)絡(luò)結(jié)構(gòu)并沒有明確給出，它需要通過對訓(xùn)練數(shù)據(jù)的結(jié)構(gòu)學(xué)習(xí)和參數(shù)學(xué)習(xí)獲得，TAN的網(wǎng)絡(luò)結(jié)構(gòu)和參數(shù)學(xué)習(xí)過程如下[16-17]。

步驟1。計算交通特征屬性變量(Ai,Aj)兩兩之間的條件相互信息MI(Ai,Aj|INC)。

MI(Ai,Aj|INC)=

(4)

步驟2。對所有交通特征屬性變量{A1,A2,…,An}，兩兩之間建立以Ai-Aj為弧，權(quán)重為MI(Ai,Aj|INC)的完全無向圖。

步驟3。建立最大權(quán)重生成樹。

步驟4。選擇任一變量作為根節(jié)點，設(shè)置向外連接方向，將無向樹轉(zhuǎn)換為有向樹。

步驟5。增加分類變量INC節(jié)點和它到每個屬性節(jié)點的有向連接，構(gòu)造TAN的網(wǎng)絡(luò)結(jié)構(gòu)。

步驟6。參數(shù)學(xué)習(xí)，采用極大似然估計算法對參數(shù)θ進行估計

(5)

采用聯(lián)合樹算法對后驗概率P(INC=1|A1,A2,…,An)進行推理計算，其基本思想是將貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)圖轉(zhuǎn)換為一個連接樹，通過信息傳遞進行計算，信息依次傳遍連接樹中的所有節(jié)點，并最終使連接樹滿足全局一致性。此處，可以直接使用Matlab中的貝葉斯網(wǎng)絡(luò)工具箱(BNT)進行相應(yīng)的推理計算，因此，不再對其過程進行詳細說明。

2.3.2 事件發(fā)布

在事件管理系統(tǒng)中，實時輸入交通特征屬性變量{A1,A2…,An}，推理計算得到后驗概率，即交通事件發(fā)生的概率P(INC=1|A1,…,An)。如果直接將后驗概率與預(yù)定義的閾值進行比較，會導(dǎo)致誤報率(FAR)較高，因此，采用一個平滑的方法，減少誤報率[18]。

(6)

3 實驗案例

3.1 數(shù)據(jù)描述

數(shù)據(jù)集是新加坡艾耶爾國王高速公路(AYE)數(shù)據(jù)集，該數(shù)據(jù)來自于1個交通仿真系統(tǒng)，在其他交通事件檢測論文中也得到了應(yīng)用[19]。仿真系統(tǒng)在路段上游和下游生成交通量、占有率和速度數(shù)據(jù)，AYE數(shù)據(jù)集模擬了300個事件的交通數(shù)據(jù)集，每個事件包含3部分：10 min事件預(yù)熱;10 min事件持續(xù);30 min事件消散。數(shù)據(jù)集被分成2個部分，訓(xùn)練數(shù)據(jù)集和測試數(shù)據(jù)集。每個數(shù)據(jù)集包括對應(yīng)事件狀態(tài)的3 000個輸入和對應(yīng)無事件狀態(tài)10 500個輸入。以30 s為間隔，每個輸入部分包含交通量、速度、道路占有率和事件狀態(tài)標(biāo)簽。

為了建立TAN分類器事件檢測模型，首先要確定模型中包含的變量。通過數(shù)據(jù)集內(nèi)容和現(xiàn)有研究，選取了8個變量作為TAN分類器節(jié)點，見表1。

表1 TAN分類器中的變量描述Tab.1 Description of Variables Containedin The TAN Classifier

3.2 數(shù)據(jù)預(yù)處理

3.2.1 小波去噪

采用Matlab中的小波工具箱對原始交通數(shù)據(jù)進行去噪處理，分解水平越高，去噪效果越好，但是也會增加計算時間和失真程度。劃分1～5共5個分解水平，將原始交通數(shù)據(jù)(包括訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù))進行小波去噪，通過實驗，本文中最優(yōu)的分解水平是3，見圖2。

圖2 分解水平為3的小波去噪結(jié)果Fig.2 Wavelet denoising results at level 3

3.2.2 標(biāo)準(zhǔn)化

根據(jù)去噪后的訓(xùn)練數(shù)據(jù)集，可以得到式(2)中的Aα和Aβ，其結(jié)果見表2，訓(xùn)練和測試數(shù)據(jù)集都將按照式(2)進行標(biāo)準(zhǔn)化。

表2 由訓(xùn)練數(shù)據(jù)集得到的公式2中Aα和Aβ取值Tab.2 The values of Aαand Aβin equation 2 according to training dataset

3.2.3 離散化

采用2.1中基于熵的離散化處理，可以用訓(xùn)練數(shù)據(jù)得到分界點，見表3。通過比較交通特征參數(shù)與分界點的值，將訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)離散化，所有的交通特征參數(shù)將被劃分為3個狀態(tài)。

表3 TAN分類器中連續(xù)變量分界點

3.3 結(jié)構(gòu)學(xué)習(xí)

使用貝葉斯網(wǎng)絡(luò)，通過學(xué)習(xí)預(yù)處理數(shù)據(jù)，可以得到用于交通事件檢測的TAN分類器結(jié)構(gòu)，見圖3。

圖3 TAN分類器結(jié)構(gòu)Fig.3 The structure of the TAN classifier

下面以節(jié)點Qu為例，得到的參數(shù)概率表見表4。

表4 Qu參數(shù)表Tab.4 The Parameters of Qu

3.4 實驗結(jié)果

圖4 TAN分類器事件檢測算法的1個典型輸出Fig.4 A typical output of TAN classifier basedincident detection algorithm

交通事件檢測存在4種可能結(jié)果：無事件正確檢測、有事件正確檢測、無事件誤報和有事件漏檢。本文采用檢測率(detection rate，DR)，誤報率(false alarm rate，F(xiàn)AR)和平均檢測時間(mean time to detection， MTTD)3個指標(biāo)評估TAN算法性能。為了更好的體現(xiàn)TAN算法的性能，本文還采用貝葉斯網(wǎng)絡(luò)(BN)算法和多層前饋神經(jīng)神經(jīng)網(wǎng)絡(luò)(MLF)算法作為對比算法[19]，其測試結(jié)果見表5。

表5 TAN和MLF算法性能比較Tab.5 Comparison between TAN and MLF with AYE data

根據(jù)表5的結(jié)果，TAN算法比BN算法具有更好的性能，同時TAN算法的平均檢測時間和誤報率會稍高，這是由于TAN算法的網(wǎng)絡(luò)結(jié)構(gòu)和參數(shù)是由數(shù)據(jù)學(xué)習(xí)得到的，而BN算法是基于專家經(jīng)驗得到的。值得注意的是，BN算法性能也依賴專家經(jīng)驗，如果專家經(jīng)驗對網(wǎng)絡(luò)結(jié)構(gòu)和參數(shù)的標(biāo)定較差，輸出結(jié)果性能也會較差，相比之下，TAN算法的性能具有更好的穩(wěn)定性。對比MLF算法，TAN算法的檢測率稍低，但它的誤報率也更低，當(dāng)TAN算法閾值設(shè)置為0.5時，兩種算法的平均檢測時間相當(dāng)。然而，MLF在理論上比TAN算法更復(fù)雜：MLF是一個黑盒模型，其內(nèi)在原理較為復(fù)雜，難以解釋；而TAN分類算法是概率和統(tǒng)計理論，更容易理解。另外在數(shù)據(jù)訓(xùn)練上，MLF網(wǎng)絡(luò)需要更多的數(shù)據(jù)和時間，本研究中MLF的平均訓(xùn)練時間達到344.7 s，而TAN算法的訓(xùn)練時間僅需要2 s。綜上所述，TAN事件檢測算法相比MLF算法具有一定的優(yōu)勢，將會得到更加廣泛的應(yīng)用。

4 結(jié) 論

貝葉斯網(wǎng)絡(luò)檢測算法在性能和轉(zhuǎn)換性方面有著優(yōu)勢，但對專家的經(jīng)驗要求較高，為了減少對于專家經(jīng)驗的依賴，提出了TAN事件檢測算法，通過數(shù)據(jù)學(xué)習(xí)得到TAN網(wǎng)絡(luò)結(jié)構(gòu)和參數(shù)，采用基于熵的方法對檢測數(shù)據(jù)進行離散化處理，并用新加坡艾耶爾國王高速公路的仿真數(shù)據(jù)證實了TAN分類算法的性能。

將TAN算法與BN算法和MLF算法進行性能對比，實驗結(jié)果顯示TAN算法優(yōu)于BN算法，其性能稍遜于MLF算法，但TAN算法在模型訓(xùn)練和標(biāo)定方面有著更快的速度，同時TAN算法相對MLF算法更加容易理解，因此TAN算法具有更廣泛的應(yīng)用前景。此外，TAN分類算法能更合理的滿足現(xiàn)實需求，包括初始訓(xùn)練數(shù)據(jù)需求和處理不同監(jiān)測系統(tǒng)設(shè)計和技術(shù)的靈活性。

由于缺乏合適的數(shù)據(jù)集，本文沒有對TAN算法的轉(zhuǎn)移性進行評估，將來應(yīng)該對TAN算法進行更加全面和詳細的評估。在接下來的研究中，我們將采用先驗分布或者動態(tài)TAN分類器，提高算法處理連續(xù)交通流參數(shù)變量的能力。