徒手搭建不專業的決策樹演算法¶

C4.5 這個演算法是目前最知名的決策樹演算法，先簡單的整理一下決策樹C4.5一些重要的進程

• 1966年 ,hunt's algorithm
• 1979年 ,J.R.Quinlan提出的ID3演算法
• 1993年 ,J.R.Quinlan進一步改進ID3演算法，產生C4.5演算法

其中 hunt's algorithm 據說是不少 決策樹的基礎，今次就來徒手實作看看這個 hunt's algorithm 首先假設每一個節點的資料 $D_t$

設定成為葉節點的條件，彼此要有相同的類別$y_t$

$ \begin{aligned} & \text{IsLeaf(}D_t\text)\{ \\ & \qquad \text{same class }y_t \\ & \} \end{aligned} $

如果沒有 相同的 類別 $y_t$ ，就進行分枝

$ \begin{aligned} & \text{Branch(}D_t\text)\{ \\ & \qquad \text{Split }D_t \text{ by attribute test condition} \\ & \} \end{aligned} $

將這個過程以遞迴方式進行

$ \begin{aligned} & \text{Train(}D_t\text)\{ \\ & \qquad \text{FOR EACH }D_t^{subset}\text{ IN Branch(}D_t\text{)} \\ & \qquad\qquad \text{IF IsLeaf(}D_t\text{)} \text{ THEN} \\ & \qquad\qquad \qquad OUTPUT \; y_t\\ & \qquad\qquad ELSE \\ & \qquad \qquad\qquad \text{Train(}D_t^{subset}\text{)} \\ & \} \end{aligned} $

然後準備一份資料，其中[0] 的部份是 目標 y

最後用C# 實作一番

class HuntAlg
    {
        static void Main(string[] args)
        {
            List<string[]> data = new List<string[]>();
            foreach (string line in File.ReadLines(@"data.csv"))
                data.Add(line.Split(','));
            HuntAlg alg = new HuntAlg();
            alg.Train(data);
        }
        private int LastAttr;
        public HuntAlg(){
            this.LastAttr = 0;
        }
        private bool IsLeaf(List<string[]> data){
            bool res = true;
            string yt = "";
            foreach(var item in data){
                if(yt=="" && res)yt=item[0];
                res = item[0] == yt;
                if(!res)break;
            }
            return res;
        }
        private Dictionary<string,List<string[]>> Branch(List<string[]> data,int attr){
            Dictionary<string,List<string[]>> branch;
            branch = new Dictionary<string,List<string[]>>();
            foreach(string[] row in data){
                string k = row[attr];
                if(!branch.ContainsKey(k))branch[k] = new List<string[]>();
                branch[k].Add(row);
            }
            return branch;
        }
        public void Train(List<string[]> data,int attr=1){
            if(LastAttr ==0)LastAttr = data[0].Length-1;
            var branch = this.Branch(data,attr);
            foreach(var k in branch.Keys)
            {
                var Dt = branch[k];
                Console.WriteLine();
                for(int j =0;j<attr;j++)Console.Write("\t");
                Console.Write("Dt[{0}]={1}:",attr,k);

                if(this.IsLeaf(Dt) || attr>=this.LastAttr)
                {
                    foreach(var item in Dt)Console.Write(item[0]);
                }
                else
                {
                    this.Train(Dt,attr+1);
                }
            }
            return;
        }
    }

輸出

   Dt[1]=3:00
   Dt[1]=1:
           Dt[2]=3:11
           Dt[2]=2:
                   Dt[3]=1:01
                   Dt[3]=3:00
                   Dt[3]=2:1
   Dt[1]=2:1

這大概就接近於隨便亂做的程度，既沒有用到屬性選取，也沒有講到應對overfitting 的作法。問題多多，但隨著逐一改進，就可以漸漸了解決策樹的演進，因此做一個簡易版本仍然十分重要。

參考資料

introduction to data mining pang-ning tan michael steinbach and vipin kumar

决策树的起源——Hunt算法

Incremental decision tree