模糊決策樹

模糊決策樹是決策樹的一種推廣。具有精確描述特徵的決策樹歸納學習已經不能適應一個系統中不精確知識自動獲取的要求，為了在模糊環境下達到不精確知識自動獲取的需要，目前已出現了一些模糊決策樹歸納學習方法，比如模糊ID3算法。

基本介紹

• 中文名：模糊決策樹
• 外文名：fuzzy decision-tree
• 學科：控制科學與工程
• 類別：信息科學
• 基本釋義：決策樹的模糊推廣
• 主要算法：模糊ID3算法

決策樹簡介

決策樹歸納學習與模糊決策樹歸納學習分別是歸納學習與模糊歸納學習的一個重要分支，ID3是決策樹學習算法的代表，模糊ID3和Min-U是模糊決策樹學習算法的代表。

模糊決策樹算法是傳統決策樹算法的一個擴充和完善，使得決策樹學習的套用範圍擴大到了能處理不確定性。模糊決策樹學習的歸納結果與傳統的比較，由於合理地處理了不精確信息，從而有著更強的分類能力及穩健性，使得知識表示的方式更為自然。由於能生成不同水平和不同置信度的推理規則，故而提供了一種構造專家系統的有效途徑，並可為決策者提供豐富的決策信息。

決策樹描述

設E是一組分類例子集合，A為一組描述例子特徵（屬性）的集合，T(E)是一個決策樹歸納的停止準則， 是一個評價函式， 。決策樹的描述過程如下：

如果E滿足停止準則T(E)，

那么返回該樹的葉結點，標記E中的最多數目的例子類別；

否則選擇一個特徵 使得 的值最大；

對特徵 的每一個取值 ，遞歸生成子樹 （其中 由E中特徵 取值為 的例子組成）返回一個非葉結點， 標記分類特徵為 ；

結束。

從決策樹的描述發現，建立決策樹的核心在於評價函式 和停止準則T(E)如何確定。

決策樹推廣

模糊決策樹是決策樹的一種推廣。

設

是給定的m族模糊子集，且滿足

如果一個有向樹滿足：

（1）樹中的每個結點屬於F(U)；

（2）對樹中每一個非葉結點N，它的所有子結點將是F(U)的一個子集族，記為X，則存在i(1≤i≤m)，使得

（3）每一葉結點對應一個或多個分類決策值。

則稱其為一個模糊決策樹，每一組模糊子集對應於一個屬性。

系統

結構

以決策樹作為學習機制構建以規則為中心的專家系統，具有易理解靈活、構造速度快等特點。採用模糊決策樹方法為學習機制，利用模糊決策樹抽取規則構造知識庫，可以實現一個小型的通用專家系統。如圖所示：

各模組構造方法如下：

（1）模糊化模組採用三角型模糊化方法將數據模糊化；

（2）決策樹學習模組以Min-Ambiguity為啟發式構建決策樹；

（3）模糊推理模組採用max-min運算元進行規則推理；

（4）知識庫知識的表示採用規則表示法這種表示法有許多優點如模組性清晰性自然性等；

（5）解釋模組採用圖形化方法將結果表示為樹型；

（6）黑板採用全局靜態對象機制實現；

（7）用戶界面採用圖形化的人機界面使用戶感到直觀方便。

功能

模糊決策系統具有以下功能：

（1）數據預處理轉換為模糊數據；

（2）通過學習產生決策樹；

（3）將決策樹轉化為規則集；

（4）利用規則進行分類決策。

比較分析

下面主要對決策樹與模糊決策樹的異同點進行比較。

（1）屬性值及分類

在決策樹中每一示例的屬性值及分類都分別取互斥的屬性值及分類中的一個，屬性值及分類均是明確的，它們是示例空間上的集合，代表示例的屬性及分類是否屬於該屬性值及要學習的概念。在模糊決策樹中，屬性值或分類反映了與人的思維、認識過程和理解中密切相關的不確定性（模糊性），所以將它們看成示例空間上的模糊集合，代表著示例的屬性及分類隸屬於該屬性值及要學習的概念的程度。特別地情況，屬性值為示例空間上的模糊數。模糊決策樹的歸納學習與決策樹歸納學習相比較，由於合理地處理了不確定信息、噪音數據等問題，從而有較強的分類能力及穩健性，使知識表示的方式更為自然，為決策者提供了豐富的決策信息。

（2）擴展結點

在決策樹歸納學習中，因為屬性值是互斥的，因此在對某一結點進行擴展（分枝）時，按擴展屬性的屬性值可將該結點上的例子集合S劃分成v個不相交的子集合 這些子集合滿足

其中 表示擴展屬性的值 所對應的例子集合(i =1, 2, …v)，v 是擴展屬性的值的個數。在模糊決策樹歸納學習中，因為屬性值為示例空間上的模糊集合，根據模糊集合的特點，當對某一結點按其擴展屬性所對應的屬性值進行擴展（分枝）時， 構成S的一個模糊分割，即每一 為一模糊集合

模糊決策樹在知識的歸納過程中併入了認識上的不確定，使歸納出的知識在容許不精確或衝突的信息方面更穩健。

（3）匹配規則及推理

在決策樹中，每一條從根到葉的路徑對應一條規則，該規則的真實度為1，而且測試例子僅與一條規則相匹配，推理是基於清晰邏輯的;在模糊決策樹中，每一條從根到葉的路徑對應一條模糊規則，該規則的真實度小於等於1，而且測試例子可與多條模糊規則相匹配，並且帶有一定的隸屬度，推理是基於模糊邏輯的。由此可看出，模糊決策樹與決策樹相比較，模糊決策樹更貼近於自然，更符合人類的思維。從決策的角度看，它提供的知識更為合理。

（4）葉結點及規則的真實度

在決策樹中，葉結點僅包含一類的例子，相應的規則的真實度為1。在模糊決策樹中，葉結點包含不止一類的例子，相應規則的真實度小於等於1，從而為構造模糊專家系統提供了更有效的途徑。

（5）訓練示例

對訓練示例，決策樹的測試精度為100%；而模糊決策樹的測試精度非100%。

模糊ID3算法

模糊ID3算法是決策樹歸納學習算法ID3的一種推廣。模糊ID3 算法亦採用分治策略，在決策樹的遞歸構造過程中，在樹的結點上利用屬性的分割模糊熵作為擴展（分枝）屬性的啟發式函式，選擇分割模糊熵最小的屬性作為擴展屬性，它具有分類速度快的優點，適合處理模糊數據，可套用於模糊專家系統等領域。

步驟

ID3算法模糊化後，主算法基本保持不變，但建樹算法在樣本數據提取、訓練數據、生成決策樹葉子結點數據都用模糊數據來表示。模糊ID3建樹算法為：

（1）提取數據源的模糊樣本，根據模糊數值計算各特徵的互信息，得到精確數值；

（2）選擇最大互信息特徵A；

（3）將在A處取相同值例子分為相同樣本子集，樣本子集的類別結果為模糊的；

（4）對含有多個模糊樣本子集遞歸調用建樹算法；

（5）若子集僅含有限模糊類別的樣例，對生成的決策樹對應分枝作 等標記，返回調用處。

計算過程

模糊ID3算法建樹的計算過程為：

（1）計算信息熵H(U)。

（2）計算條件熵H(U|V)。

（3）計算互信息。

選擇較大 遞歸建立決策樹。