基于ID3算法的飛行時間分析

張 祥，陳 軍，余士龍，吳晨陽，許向運

(1.94995部隊，如皋 226500；2.95631部隊，瀘州 646000)

0 引言

隨著計算機技術的高速發展，信息數據量呈現出幾何倍數增長。如何從海量數據中有效地提取有用信息，一直是數據挖掘技術的目的所在[1]。20世紀80年代末發展起來的數據挖掘技術，就是從大量不完全的、有噪聲的實際數據中，提取潛在有用的信息和知識的一種技術手段。在飛行氣象保障領域，為了能夠更好地滿足飛行任務的需求，需要綜合衡量各類快速變化的氣象要素的影響。由于飛行員在飛行水平、飛機性能等各個方面存在著一定的差異，因此，不同氣象要素對飛行時間的長短有著明顯影響。文章將決策樹算法引入氣象要素分析過程中，決策樹算法主要用來對研究數據進行預測與分類，是目前應用最為廣泛的一種數據挖掘算法[2，3]。通過ID3決策樹算法對氣象信息進行充分挖掘，找到對飛行時間長短影響較大的分類規則，用于分析飛行的進展情況，從而提出針對性建議，使飛行保障質量得到提高。

1 ID3算法的構造

ID3決策樹是一種經常使用的分類方法，其利用一種類似流程圖的樹結構進行預測分類建模，將核心問題的搜索空間分為若干個不同的子類[4]。樹的節點是樣本的屬性，屬性的取值為樹的分支。決策樹的產生是對大量樣本的屬性進行分析歸納的結果[5]。應用此種方法自頂向下地建造一棵樹對分類過程進行建模，便可以將數據進行有效地集中并得到分類結果。ID3決策樹算法首先計算訓練樣本集合中所有屬性的信息增益，將信息增益最大的屬性作為測試屬性。創建與判斷屬性值一一對應的各個子葉節點，代表訓練樣本子集；以此類推，調用遞歸繼續劃分各樣本子集，直到無法進一步劃分，算法結束。正是因為ID3算法在每個非葉節點選擇信息增益最大的屬性作為測試屬性，從而保證了當前情況下的最有利拆分，使得樹的平均深度較小，有效地提高了分類效率。

假設訓練集S中包含了s個數據樣本，類別屬性中有m個不同的值Ci(i=1，2，…，m)，第Ci類的樣本數記為si，則需要分析樣本的總信息熵為：

(1)

式中，Pi是任意樣本屬于Ci的概率，通常通過si/s得到。

設測試屬性A可以取k個不同的值{a1，a2，…，ak}，按照屬性A可以將訓練集S劃分成k個子集{S1，S2，…，Sk}，則第j(j=1，2，…，k)個子集Sj包含了訓練集S中屬性A取aj值的樣本，將它們作為從集合S的節點生長出來的新的葉節點。將子集Sj中類別為Cj的樣本數記為sij，得到按照測試屬性A進行樣本劃分的信息熵值為：

(2)

由公式(1)和(2)得到用測試屬性A劃分訓練集S后的信息增益(Gain)為：

Gain(A)=I(s1，s2，…，sm)-E(A)

(3)

E(A)值越小，則Gain(A)值越大，表示選擇測試屬性A進行分類能夠更好地提供信息，應當優先選擇該屬性進行分類，以減小分類的不確定程度。遞歸調用上述過程對訓練集S的k個分支進行劃分，通過信息增益進行選擇，便能夠將其他屬性作為節點的子節點和分支生成決策樹。

2 仿真實驗

2.1 飛行時間影響要素分析

為保證飛行質量，了解各個氣象要素對飛行時間的影響程度至關重要。根據預報員與飛行人員的研究，可以將能見度、云量和風速3個屬性作為基本屬性，構建模型分析晴天條件下能見度、云量和風速對飛行時間長短的影響。模型中的能見度、云量和風速的相互關系產生了多目標協同問題。對于能見度屬性，結合人工觀測與能見度儀數據，將大于等于飛機起飛標準的能見度值定為高能見度屬性值，小于起飛標準為低能見度屬性值；對于云量屬性，將大于等于6成定為多云，小于6成為少云；對于風速屬性，將大于等于13 m/s定為大風，小于13 m/s定為小風。飛行時間為數值型，需要對屬性進行離散化，將其劃分為“長”和“短”兩類。取其平均值作為分界點，大于平均值的屬于“長”類別，小于平均值的則屬于“短”類別。

經過離散化處理，得到50組數據集合如表1所示。

表1 氣象要素與飛行時間數據

2.2 信息增益計算與決策樹生成

根據公式(1)，計算總信息熵，總記錄數為50，飛行時間“長”的數據有27，“短”的有23。

根據公式(1)和(2)，計算每個測試屬性的信息熵。風速屬性值有“大”和“小”兩種。其中“大風”條件下，飛行時間為“長”的記錄為12，飛行時間為“短”的記錄為17，可表示為(12，17)；“小風”條件下，飛行時間為“長”的記錄為15，飛行時間為“短”的記錄為6，可表示為(15，6)。則風速屬性的信息熵計算過程為：

云量屬性值有“多”和“少”兩種：其中“多云”條件下，飛行時間為“長”的記錄為3，飛行時間為“短”的記錄為12，可表示為(3，12)；“少云”條件下，飛行時間為“長”的記錄為24，飛行時間為“短”的記錄為11，可表示為(24，11)。則云量屬性的信息熵計算過程為：

能見度屬性值有“高”和“低”兩種：其中“高能見度”條件下，飛行時間為“長”的記錄為19，飛行時間為“短”的記錄為5，可表示為(19，5)；“低能見度”條件下，飛行時間為“長”的記錄為8，飛行時間為“短”的記錄為18，可表示為(8，18)。則能見度屬性的信息熵計算過程為：

根據公式(3)，計算3個氣象要素屬性的信息增益分別為：

Gain(風速)=I(27，23)-E(風速)=0.0654

Gain(云量)=I(27，23)-E(云量)=0.1502

Gain(能見度)=I(27，23)-E(能見度)=0.1780

由此可見，能見度屬性的信息增益值最大，應選取它的兩個屬性值“高”和“低”作為根節點的兩個分支。

按照上述步驟對兩個分支進行劃分，計算信息增益值，循環進行直到沒有新的節點分支，則計算結束。得到的決策樹模型如圖1所示。

圖1 飛行時間決策樹模型

由決策樹模型能夠得到各類不同的決策規則。

3 結束語

ID3算法是決策樹算法中最典型的算法，文章通過編寫MATLAB程序，仿真實現了對現有數據的挖掘，分析了氣象要素對飛行時間的影響，有助于實現飛行保障的針對化管理。由于ID3算法偏向于選取高度分支屬性，而該選法并不一定全是最優屬性，因此仍有改進提升的空間。