基于決策樹的知識獲取方法研究

張 晶

（聊城大學 東昌學院 電子科學系，聊城 252000）

基于決策樹的知識獲取方法研究

張 晶

（聊城大學 東昌學院 電子科學系，聊城 252000）

1 決策樹知識獲取方法

知識獲取是指從大量數據中去除無用信息、提取有用信息的過程。決策樹學習的目的就是從大量實例中歸納出以決策樹形式表示的知識，因此決策樹的學習過程就是一種知識獲取過程。所以可以把決策樹的學習與知識獲取問題聯系起來，從而把知識獲取問題轉換為決策樹的學習問題，從而實現知識的自動獲取。

由于決策樹知識獲取即為決策樹學習，而決策樹學習的核心就是決策樹的學習算法，因此研究決策樹的知識獲取方法實際上也就是研究決策樹的學習算法。所以在此就可以直接利用這一算法生成決策樹，以實現通過決策樹進行知識的自動獲取（即機器學習）。

1.1 生成樹的構造算法

決策樹構造可以分為兩步進行。第一步，決策樹的生成：通過訓練樣本集生成決策樹的過程。在一般情況下，訓練樣本數據集是根據實際需要由歷史的、綜合性的、用于數據分析處理的數據集。第二步，決策樹的剪枝：決策樹的剪枝就是對上一階段生成的決策樹進行檢驗、修正的過程。主要是用新的樣本數據集（稱為測試數據集）中的數據校驗決策樹生成過程中產生的初步規則，將那些影響預測準確性的分枝剪除掉。

在決策樹生成的過程中，訓練樣本數據集作為輸入的內容，決策樹作為最終的輸出結果。決策樹的每一個決策節點對應著要進行分類的下一個決策屬性（測試屬性），分支則對應著按該屬性進一步劃分的取值特征，葉子代表類或者類的分布。首先，根據用戶的實際需要選擇類別標識屬性及其決策樹的決策屬性集，決策屬性集是指在候選屬性中選擇屬性集，然后構造決策樹。決策樹歸納的基本算法被稱為貪心算法，是以自頂向下遞歸各個擊破的方式來構造決策樹。

其算法描述如下：

1）樹從表示訓練樣本的單個節點作為起始點。

2）如果樣本屬于同一類，則該節點將成為葉節點，并用該類做標記。

3）否則，算法將選擇最有分類能力的屬性作為決策樹的當前節點。

4）根據當前決策節點屬性取值的不同，將訓練樣本數據集劃分為若干子集。每個取值形成一個分枝。根據上一步得到一個子集，重復進行上面步驟，最后遞歸形成每個劃分樣本上的決策樹。

5）如果某個屬性出現在一個節點上，就不能在該節點的任何后代中考慮它。

遞歸劃分步驟當且僅當下列條件之一成立時結束：

1）給定節點的所有樣本屬于同一類。

2）剩余的屬性可以用來進一步劃分樣本。在這種情況下，通過多數表決的形式，將給定的節點轉換成葉節點，并以樣本中元組個數最多的類別作為類別標記； 同時，還可以存放該節點樣本的類別分布。

3）如果某一個分枝test_attribut＝ai沒有樣本，則以該樣本的多數類來創建一個樹葉。

假設用F 代表當前樣本集，當前候選屬性集用F.attributelist表示，則 C4.5算法C4.5formtree（F，F.attributelist）的偽代碼如下：

1）創建根節點M；

2）IF F都屬于同一類C，則返回M為葉節點，標記為類C；

3）IF F.attributelist為空 OR F中所剩的樣本數少于某給定值則返回M

為葉節點，標記M為F中出現最多的類；

4）FOR EACH F.attributelist中的屬性

計算信息增益率information gain ratio；

5）M的測試屬性test.attribute = F.attributelist具有最高信息增益率的屬性；

6）IF 測試屬性為連續型則找到該屬性的分割閾值；

7）FOR EACH 由節點M一個新的葉子節點

{IF 該葉子節點對應的樣本子集 F 為空

則分裂此葉子節點生成新葉節點，將其標記為 F 中出現最多的類

ELSE

在該葉子節點上執行 C4.5formtree（F，F.attributelist），繼續對它分裂；}

決策樹是由訓練集構造的，所以它能正確處理訓練集中的大部分記錄。事實說明，這樣將會導致決策樹非常復雜，使得決策樹不平衡，個別分支很長，這就需要對決策樹進行剪枝。決策樹的剪枝就是指用單個的葉節點來替換整個子樹。

1.2 轉化規則算法

決策樹生成以后，需要從決策樹中提取分類規則，一般需要兩個步驟，先獲得簡單規則，然后再精簡規則屬性。

1）獲得簡單規則：對于已經生成的決策樹，可以非常容易地從中提取分類規則，并以if-then的形式表示。對從根節點到樹葉的每條路徑創建一個規則，沿著給定路徑上的每個屬性值對形成規則前件（if部分）的一個合取項，葉節點包含類預測，形成規則后件（then部分）。If-then規則易于理解，特別是當給定的樹很大時。

2）精簡規則屬性：從決策樹上直接獲得的簡單規則，有可能包含了許多無關屬性，在不影響規則預測效果的情況下，應該盡量刪除那些不必要的條件。

設規則的形式為W

if C then CLASS E

精簡之后的規則形式為R－

if C－then CLASS E其中C－是從C中刪除條件Q之后的形式。這樣，規則W－覆蓋的實例可分為以下4個部分：滿足條件C，屬于類E的；滿足條件C，屬于其他類的；滿足條件C－，但不滿足條件Q，屬于類E的；滿足條件C－，但不滿足條件Q，屬于其他類的，以上四類實例分別用Y1，F1，Y2，F2來表示。

規則W覆蓋了Y1＋F1個實例，其中誤判實例數目為F1。規則R－覆蓋了Y1＋F1＋Y2＋F2。所以規則R的誤判概率為UCF（F1，Y1＋F1），規則 R－的誤判概率為 UCF（F1＋ F2，Y1＋ F1＋ Y2＋ F2） 。如果 UCF（F1，Y1＋ F1）≥ UCF（F1＋ F2，Y1＋F1＋Y2＋F2） ，則可以從條件C中刪除條件Q。

獲得最優規則的前件集是一個重要問題。Quinlan 提出了一種貪婪搜索方法，即每次從條件集合中刪除一個對預測效果影響最小的條件，如果刪除該條件后，誤判概率減少了，則上述過程繼續。如果刪除后，誤判概率增加了，則不能夠刪除該條件，而整個精簡過程也同時結束。

將決策樹轉化為規則后，因為他們是易于理解的，所以它們可以構成專家系統的基礎。對規則的剪枝將比對樹的剪枝算法提供更高的準確率，原因是規則的剪枝等價于在樹的剪枝中只剪一個葉節點，而這在樹的剪枝中是無法做到的。

2 決策樹構造應用舉例

為了驗證構造決策樹方法在系統知識獲取上的有效性，選取網絡設備信息中的7種屬性組成故 障 識 別 參 數 集 B。B＝ {B1，B2，B3，B4，B5，B6，B7}，其中B1代表網卡狀態、B2代表配置是否正確、B3代表CPU利用率、B4代表DISK利用率、B5代表網卡收包錯誤率、B6代表是否重啟動、B7代表網卡是否捕獲到包，共60個樣本實例來建立故障決策樹，其中選取20個作為測試數據。選取的樣本數據如表1所示。

表1 選取的樣本數據

產生的故障決策樹如圖1所示，最終屬性“配置是否正確”為決策樹的根，將“配置是否正確”的值分為2段，左子樹和右子樹。而后在2個分枝的基礎上以相同的屬性選擇算法遞歸構造各自的子節點以及最終的葉節點，這里得到的決策樹結構比較簡單。當數據樣本變得很大，故障類別也很豐富的時候，會形成一個較為復雜的決策樹,得出的規則更適合用于故障的識別。

圖1 產生的故障決策樹

從樹根遍歷整個決策樹,得到的7條分類規則如下所示：

if配置正確，網卡不能捕獲到包，then 出現硬件故障；

if配置正確，網卡能夠捕獲到包，then 出現安全問題；

if配置不正確，網卡不能捕獲到包，CPU利用率≤50，then 正常；

if配置不正確，網卡不能捕獲到包，CPU利用率＞50，沒有重啟，then 版本更新；

if配置不正確，網卡不能捕獲到包，CPU利用率＞50，已經重啟，then 硬件故障；

if配置不正確，網卡能夠捕獲到包，網卡收包錯誤率≤20，then 配置錯誤；

if配置不正確，網卡能夠捕獲到包，網卡收包錯誤率＞20，then 正常；

這些規則表現了故障的特征。最后把這些規則存入知識庫，利用它對故障分類提供決策依據，并給出故障原因。

3 決策樹知識獲取性能分析

就目前的知識獲取方法而言，主要包括神經網絡、遺傳算法、Petri網等，它們與決策樹比較如下：

1）決策樹與Petri網一樣，知識獲取過程簡單、計算復雜度低，但決策樹能實現知識的自動獲取，而Petri網的構建是由人工完成的。

2）遺傳算法雖然也能實現知識的自動獲取，但它的計算復雜度遠遠高于決策樹，并且它只是一種知識獲取方法，不能實現知識表示，而決策樹是把知識的獲取與表示融于一身的。

3）神經網絡與決策樹一樣，不僅可以實現知識的自動獲取，并且也能實現知識的表示；但與決策樹相比較，神經網絡學習收斂速度稍慢、網絡參數的確定困難，而且它的適應性差，系統的任何變化都需要重新訓練。

4 結束語

決策樹知識獲取方法具有知識獲取過程簡單、計算復雜度低、適應性強的特點，并且能夠實現知識獲取與知識表示的融合，是一個性能優良的自動知識獲取方法（即機器學習方法）。

[1]朱福喜, 朱三元, 伍春香. 人工智能基礎教程[M]. 清華大學出版社, 2006: 78-83.

[2]田盛豐, 等. 人工智能與知識工程[M]. 中國鐵道出版社,1999: 121-127.

[3]Shyi-Ming Chen, Jyh-Sheng Ke, Jin-Fu Chang. Knowledge representation using fuzzy Petrinets. Knowledge and Data Engineering IEEE Transactions, 1990, 2: 311-319.

[4]Crosbie, Mark, and Gene Spafford. Applying Genetic Programnning to IntrusionDetection. The AAAI Fall Symposium on Genetic Programming, 2003: 1-8.

Based on the decision tree of knowledge acquisition method

ZHANG Jing

本文以決策樹理論為基礎，提出了基于決策樹知識獲取的方法。該方法充分利用決策樹把知識表示與獲取融于一身的優點，使知識表示與知識獲取同時進行，克服了傳統人工智能系統中知識表示與知識獲取分離的缺點。

決策樹；知識獲取；貪心算法

張晶（1975－），女，山東聊城人，講師，碩士，研究方向為計算機軟件與理論。

TP391

A

1009-0134(2011)4(下)-0154-03

10.3969/j.issn.1009-0134.2011.4(下).46

2010-12-22