張 晶

（聊城大學(xué) 東昌學(xué)院 電子科學(xué)系，聊城 252000）

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

張 晶

（聊城大學(xué) 東昌學(xué)院 電子科學(xué)系，聊城 252000）

1 決策樹知識獲取方法

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

由于決策樹知識獲取即為決策樹學(xué)習(xí)，而決策樹學(xué)習(xí)的核心就是決策樹的學(xué)習(xí)算法，因此研究決策樹的知識獲取方法實際上也就是研究決策樹的學(xué)習(xí)算法。所以在此就可以直接利用這一算法生成決策樹，以實現(xiàn)通過決策樹進行知識的自動獲?。礄C器學(xué)習(xí)）。

1.1 生成樹的構(gòu)造算法

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

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

其算法描述如下：

1）樹從表示訓(xùn)練樣本的單個節(jié)點作為起始點。

2）如果樣本屬于同一類，則該節(jié)點將成為葉節(jié)點，并用該類做標(biāo)記。

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

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

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

遞歸劃分步驟當(dāng)且僅當(dāng)下列條件之一成立時結(jié)束：

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

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

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

假設(shè)用F 代表當(dāng)前樣本集，當(dāng)前候選屬性集用F.attributelist表示，則 C4.5算法C4.5formtree（F，F(xiàn).attributelist）的偽代碼如下：

1）創(chuàng)建根節(jié)點M；

2）IF F都屬于同一類C，則返回M為葉節(jié)點，標(biāo)記為類C；

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

為葉節(jié)點，標(biāo)記M為F中出現(xiàn)最多的類；

4）FOR EACH F.attributelist中的屬性

計算信息增益率information gain ratio；

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

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

7）FOR EACH 由節(jié)點M一個新的葉子節(jié)點

{IF 該葉子節(jié)點對應(yīng)的樣本子集 F 為空

則分裂此葉子節(jié)點生成新葉節(jié)點，將其標(biāo)記為 F 中出現(xiàn)最多的類

ELSE

在該葉子節(jié)點上執(zhí)行 C4.5formtree（F，F(xiàn).attributelist），繼續(xù)對它分裂；}

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

1.2 轉(zhuǎn)化規(guī)則算法

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

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

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

設(shè)規(guī)則的形式為W

if C then CLASS E

精簡之后的規(guī)則形式為R－

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

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

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

將決策樹轉(zhuǎn)化為規(guī)則后，因為他們是易于理解的，所以它們可以構(gòu)成專家系統(tǒng)的基礎(chǔ)。對規(guī)則的剪枝將比對樹的剪枝算法提供更高的準(zhǔn)確率，原因是規(guī)則的剪枝等價于在樹的剪枝中只剪一個葉節(jié)點，而這在樹的剪枝中是無法做到的。

2 決策樹構(gòu)造應(yīng)用舉例

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

表1 選取的樣本數(shù)據(jù)

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

圖1 產(chǎn)生的故障決策樹

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

if配置正確，網(wǎng)卡不能捕獲到包，then 出現(xiàn)硬件故障；

if配置正確，網(wǎng)卡能夠捕獲到包，then 出現(xiàn)安全問題；

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

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

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

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

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

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

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

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

1）決策樹與Petri網(wǎng)一樣，知識獲取過程簡單、計算復(fù)雜度低，但決策樹能實現(xiàn)知識的自動獲取，而Petri網(wǎng)的構(gòu)建是由人工完成的。

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

3）神經(jīng)網(wǎng)絡(luò)與決策樹一樣，不僅可以實現(xiàn)知識的自動獲取，并且也能實現(xiàn)知識的表示；但與決策樹相比較，神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)收斂速度稍慢、網(wǎng)絡(luò)參數(shù)的確定困難，而且它的適應(yīng)性差，系統(tǒng)的任何變化都需要重新訓(xùn)練。

4 結(jié)束語

決策樹知識獲取方法具有知識獲取過程簡單、計算復(fù)雜度低、適應(yīng)性強的特點，并且能夠?qū)崿F(xiàn)知識獲取與知識表示的融合，是一個性能優(yōu)良的自動知識獲取方法（即機器學(xué)習(xí)方法）。

[1]朱福喜, 朱三元, 伍春香. 人工智能基礎(chǔ)教程[M]. 清華大學(xué)出版社, 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

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

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

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

TP391

A

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

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

2010-12-22