[發明專利]一種基于改進型決策樹算法的路況信息預測方法

有效

• 申請號: 201810144289.2
• 申請日: 2018-02-12
• 公開（公告）號: CN108364467B
• 公開（公告）日: 2020-08-07
• 發明（設計）人: 何涇沙;侯立夫;廖志鋼;黃輝祥
• 申請（專利權）人: 北京工業大學
• 主分類號: G08G1/01
• 分類號: G08G1/01;G08G1/065;G06K9/62
• 代理公司: 北京匯信合知識產權代理有限公司 11335
• 代理人: 夏靜潔

本發明公開了一種基于改進型決策樹算法的路況信息預測方法，包括：基于道路連通力的影響因子確定分析道路連通力的屬性；采集道路數據，數據預處理，計算信息熵，計算各屬性的屬性熵，基于關聯函數計算各屬性的關聯函數值，基于各屬性的關聯函數值計算各屬性的權重值；基于信息熵、各屬性的屬性熵和各屬性的權重值計算各屬性的信息增益，根據各屬性信息增益的大小進行排序構建決策樹，并根據決策樹預測道路路況。本發明通過計算屬性的關聯函數值，同信息熵展開運算得出的屬性權重值來構建決策樹，可以克服傳統ID3算法傾向于將選取具有更多可能取值的元素作為高權重屬性的問題，利用構建的決策樹去預測下一時段的道路擁堵改善程度。

技術領域

本發明涉及決策樹算法與道路交通流模型技術領域，尤其涉及一種基于改進型決策樹算法的路況信息預測方法。

背景技術

隨著全球城市化的推進，城市中的機動車保有量逐年增加。截止2016年6月底，北京的機動車保有量已達544萬量，位居全國之首。對北京、東京、紐約這種特大型城市，這一數據會隨著年代的推移而繼續上升。數量巨大的機動車不僅會造成交通擁堵，伴隨而來的還有空氣污染、能源浪費等問題，阻礙了城市發展，降低了人們的生活水平。在全球200個大型城市中(人口大于80萬)，北京的交通擁擠程度排名第15。擁堵的交通狀況不僅給人們的出行帶來了額外的時間消耗，更提升了燃油消耗，使得運輸、物流等行業的運營成本大幅提升。2011年，在澳大利亞國內最大的六個城市中，交通堵塞引發的物流運輸延誤致使物流公司虧損137億美元。在中國，運輸燃料費用則占物流公司總運營成本的46％。綜上而言，減緩道路擁堵、改善道路交通條件不僅可以降低人們的出行成本，還有益于降低道路擁堵帶來的經濟損失并減少尾氣排放。造成交通擁堵的原因是多樣化的，在現有交通條件下，最大化利用道路資源可以有效地減緩堵塞，展開對道路信息的研究則有助于直觀高效地評估道路可承載車流量與尋路算法的有效性。

1、決策樹算法與改進

決策樹是一種常用的分類與回歸方法，該方法從一組無序、無規律的事例中推理出決策樹表示形式的分類規則。決策樹分類算法采用自頂向下的遞歸方式，在決策樹內部節點間進行屬性值比較，根據不同屬性值判斷從該節點向下的分支，判斷至葉子節點時即可得出分類結果。決策樹中的節點表示一個屬性，測試結果則輸出在葉節點的分支中，不同條件對應的結果在下一層的節點中進一步驗證。因此，從決策樹的根到葉節點的每條路徑便對應了一種選擇辦法，越靠近根部的節點屬性權重值越高，整棵決策樹對應了一組表達式規則。

決策樹分類算法由決策樹的生成和修剪兩個步驟組成。生成算法通過輸入一組帶有類別標記的樣本參數來構造一棵二叉或多叉的決策樹。對于二叉樹，內部節點，一般表示為一個邏輯判斷；樹的邊可看作邏輯判斷的分支結果。對于多叉樹，內部節點是樣本集的屬性，邊是該屬性的所有取值，屬性值的數量決定了決策樹邊的數量，樹的葉子節點是類別標記。決策樹構造過程采用的方法是自上而下的遞歸方法，具體算法如下：

算法Generate_decision_tree

輸入：訓練樣本samples，由離散值屬性表示；候選屬性的集合attribute_list。

輸出：由給定樣本產生的一棵決策樹。

(1)、創建節點N；

(2)、如果samples都在同一個類C則返回N作為葉子節點，以類C為標記，程序結束；

(3)、如果attribute_list為空，則返回N作為葉節點，標記為samples中最普通的類，程序結束；

(4)、選擇attribute_list中具有最高信息增益的屬性h_attribute；

(5)、標記節點N為h_attribute；

(6)、對于h_attribute中的每一個已知值Si，由節點N生長出一個條件為h_attribute＝Si的分枝；