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

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

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

0 引言

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

1 ID3算法的構(gòu)造

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

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

(1)

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

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

(2)

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

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

(3)

E(A)值越小，則Gain(A)值越大，表示選擇測試屬性A進行分類能夠更好地提供信息，應(yīng)當(dāng)優(yōu)先選擇該屬性進行分類，以減小分類的不確定程度。遞歸調(diào)用上述過程對訓(xùn)練集S的k個分支進行劃分，通過信息增益進行選擇，便能夠?qū)⑵渌麑傩宰鳛楣?jié)點的子節(jié)點和分支生成決策樹。

2 仿真實驗

2.1 飛行時間影響要素分析

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

經(jīng)過離散化處理，得到50組數(shù)據(jù)集合如表1所示。

表1 氣象要素與飛行時間數(shù)據(jù)

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

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

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

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

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

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

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

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

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

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

按照上述步驟對兩個分支進行劃分，計算信息增益值，循環(huán)進行直到?jīng)]有新的節(jié)點分支，則計算結(jié)束。得到的決策樹模型如圖1所示。

圖1 飛行時間決策樹模型

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

3 結(jié)束語

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