資料探勘 - 決策樹歸納

決策樹是一種包含根節點、分支和葉子節點的結構。每個內部節點表示對某個屬性的測試，每個分支表示測試的結果，每個葉子節點包含一個類別標籤。樹中最頂層的節點是根節點。

以下決策樹用於表示“購買電腦”的概念，該概念表示公司中的客戶是否可能購買電腦。每個內部節點表示對某個屬性的測試。每個葉子節點表示一個類別。

決策樹的優點如下：

• 它不需要任何領域知識。
• 它易於理解。
• 決策樹的學習和分類步驟簡單快速。

決策樹歸納演算法

1980 年，機器研究員 J. Ross Quinlan 開發了一種稱為 ID3（迭代二分器）的決策樹演算法。後來，他提出了 C4.5，它是 ID3 的繼任者。ID3 和 C4.5 採用貪婪演算法。在此演算法中，沒有回溯；樹以自上而下的遞迴分治方式構建。

Generating a decision tree form training tuples of data partition D
Algorithm : Generate_decision_tree

Input:
Data partition, D, which is a set of training tuples 
and their associated class labels.
attribute_list, the set of candidate attributes.
Attribute selection method, a procedure to determine the
splitting criterion that best partitions that the data 
tuples into individual classes. This criterion includes a 
splitting_attribute and either a splitting point or splitting subset.

Output:
 A Decision Tree

Method
create a node N;

if tuples in D are all of the same class, C then
   return N as leaf node labeled with class C;
   
if attribute_list is empty then
   return N as leaf node with labeled 
   with majority class in D;|| majority voting
   
apply attribute_selection_method(D, attribute_list) 
to find the best splitting_criterion;
label node N with splitting_criterion;

if splitting_attribute is discrete-valued and
   multiway splits allowed then  // no restricted to binary trees

attribute_list = splitting attribute; // remove splitting attribute
for each outcome j of splitting criterion

   // partition the tuples and grow subtrees for each partition
   let Dj be the set of data tuples in D satisfying outcome j; // a partition
   
   if Dj is empty then
      attach a leaf labeled with the majority 
      class in D to node N;
   else 
      attach the node returned by Generate 
      decision tree(Dj, attribute list) to node N;
   end for
return N;

樹剪枝

進行樹剪枝是為了去除訓練資料中由於噪聲或異常值導致的異常現象。剪枝後的樹更小且更簡單。

樹剪枝方法

有兩種方法可以修剪樹：

• 預剪枝 - 透過提前停止樹的構建來修剪樹。

• 後剪枝 - 這種方法從完全生長的樹中刪除子樹。

成本複雜度

成本複雜度由以下兩個引數衡量：

• 樹中的葉子節點數量，以及
• 樹的錯誤率。