トップ   編集 凍結解除 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索   ヘルプ   最終更新のRSS

C4.5

Last-modified: 2016-10-20 (木) 19:18:17
Top / C4.5

C4.5による決定木学習

  • C4.5 を使って決定木学習 をしてみる。
  • 参考
    • C4.5について(菊池先生)
    • (教科書)J.R.キンラン(著),古川康一(監訳),AIによるデータ解析,トッパン,1995.
    • C4.5 example(琉球大當間先生)

インストール

データを作る

  • Wikipediaのサンプル を使う。*1
    • カテゴリーおよびパラメータ指定ファイル(golf.names)
      do, don't.                         | 従属変数、ゴルフをするかしないか
      
      weather     : fine, cloudy, rain.  | 独立変数、天気(3カテゴリ)
      temperature : continuous.          | 独立変数、気温(連続数)
      humidity    : continuous.          | 独立変数、湿度(連続数)
      wind        : y, n.                | 独立変数、風が強いか強くないか
      
      • 最後の行は改行すること(以下同様)
    • 学習データ(golf.data)
      fine,29,85,n,don't
      fine,27,90,y,don't
      cloudy,28,78,n,do
      rain,21,96,n,do
      rain,20,80,n,do
      rain,18,70,y,don't
      cloudy,18,65,y,do
      fine,22,95,n,don't
      fine,21,70,n,do
      rain,24,80,n,do
      fine,24,70,y,do
      cloudy,22,90,y,do
      cloudy,27,75,n,do
      rain,22,80,y,don't
      
      • データには欠損があってもいいようで、その場合は「?」と記述する。*2
  • テストデータ(golf.test)
    rain,22,70,y,do
    fine,24,70,y,don't
    • これは適当に作った。モデルの精度の評価に使うものなので、従属変数のデータも必要。

実行

  • 決定木を作る
    $ c4.5 -f golf
    • 以下が出力される。
      C4.5 [release 8] decision tree generator        Wed Jul 27 12:31:06 2011
      ----------------------------------------
      
          Options:
              File stem <golf>
      
      Read 14 cases (4 attributes) from golf.data
      
      Decision Tree:
      
      weather = cloudy: do (4.0)
      weather = fine:
      |   humidity <= 75 : do (2.0)
      |   humidity > 75 : don't (3.0)
      weather = rain:
      |   wind = y: don't (2.0)
      |   wind = n: do (3.0)
      
      Tree saved
      
      Evaluation on training data (14 items):
      
               Before Pruning           After Pruning
              ----------------   ---------------------------
              Size      Errors   Size      Errors   Estimate
      
                 8    0( 0.0%)      8    0( 0.0%)    (38.5%)   <<
  • この結果は以下のように解釈できる。*3
     if      天気が曇り
         * ゴルフをする *
     else if 天気が晴れ
       if      湿度が75以下
         * ゴルフをする *
       else if 湿度が75より上
         * ゴルフをしない *
       end
     else if 天気が雨
       if      風が強い
         * ゴルフをしない *
       else if 風が弱い
         * ゴルフをする *
       end
     end
  • Wikipediaの決定木とほぼ(細かい数値を除いて)一致している。
  • 「weather = cloudy: do (4.0)」などのカッコの中身は、各葉に到達したトレーニング事例の数である*4。なお、「(/)」という表記になっていた場合、右側の値はその葉で分類を間違えたトレーニング事例の数である。
  • Decision Tree が複雑だった場合(?)は、Simplified Decision Tree も生成される。これは発見的方法を使って、学習データ(?)を分類する際に分類の精度を落とさないで構造をより理解しやすいように単純化した決定木である*5*6
  • 「Evaluation on training data」以下は、学習データに対する決定木の精度を示す。「14 items」はデータ数、「Before Pruning」は学習後の決定木、「After Pruning」は単純化した決定木、「Size」は決定木の枝の数、「Errors」は分類エラー、「Estimate」はその木が新しい事例に対して何%の割合で間違えるか*7を示す*8
  • 決定木を作る&テストデータに対する評価
    $ c4.5 -f golf -u
    • 上記の学習結果に加えて、以下が出力される。
      Evaluation on test data (2 items):
      
               Before Pruning           After Pruning
              ----------------   ---------------------------
              Size      Errors   Size      Errors   Estimate
      
                 8    2(100.0%)      8    2(100.0%)    (38.5%)   <<
      
      
                (a)  (b)      <-classified as
               ---- ----
                       1      (a): class do
                  1           (b): class don't
      • 「Evaluation on test data」以下はテストデータを決定木にかけた結果。2個のデータがどちらもエラーになり、エラー率100%。*9
      • 「(a) (b)」以下は正誤行列。一行目は「クラスdoのデータ1つがクラスdon'tに分類された(エラー)」という意味。ニ行目は「クラスdon'tのデータ1つがクラスdoに分類された(エラー)」という意味。
  • 学習されたルールを見る
    $ c4.5rules -f golf
    • 以下が出力される。
      C4.5 [release 8] rule generator Wed Jul 27 13:46:18 2011
      -------------------------------
      
          Options:
              File stem <golf>
      
      Read 14 cases (4 attributes) from golf
      
      ------------------
      Processing tree 0
      
      Final rules from tree 0:
      
      Rule 2:
              weather = cloudy
              ->  class do  [70.7%]
      
      Rule 4:
              weather = rain
              wind = n
              ->  class do  [63.0%]
      
      Rule 1:
              weather = fine
              humidity > 75
              ->  class don't  [63.0%]
      
      Rule 3:
              weather = rain
              wind = y
              ->  class don't  [50.0%]
      
      Default class: do
      
      Evaluation on training data (14 items):
      
      Rule  Size  Error  Used  Wrong            Advantage
      ----  ----  -----  ----  -----            ---------
         2     1  29.3%     4      0 (0.0%)        0 (0|0)    do
         4     2  37.0%     3      0 (0.0%)        0 (0|0)    do
         1     2  37.0%     3      0 (0.0%)        3 (3|0)    don't
         3     2  50.0%     2      0 (0.0%)        2 (2|0)    don't
      
      Tested 14, errors 0 (0.0%)   <<
      
                (a)  (b)      <-classified as
               ---- ----
                  9           (a): class do
                       5      (b): class don't
      • これは前述の決定木を、人間が理解しやすいルールの形で表現したもの。
      • 例えば「Rule 4」は、「天気が雨で風が強くなければゴルフをする」という意味。「[63.0%]」は、これまで調べられていない事例に対してこのルールの条件部が満足されると、分類において63%の正しさがあることを予測している*10
      • ルール番号は、特に意味はなく、元の木の葉の順序から決められている*11
      • 「Evaluation on training data」以下は各ルールの成績である。例えば「2 1 29.3% 4 0 (0.0%) a (b|c) do」は、ルール2は条件部に1つのテストがあり予測されたエラーは29.3%であり、学習データを分類するために4回使われた。これらの事例は間違いがなかった。もしもこのルールが除かれたならば、このルールによって正しく分類されたb個の事例は誤って分類され、このルールによって間違って分類されていたc個の事例は正しく分類され、全体の効果はaである。そのルールの条件部を満足する全ての事例はクラスdoに属していた。*12
  • テストデータも加えて学習されたルールを見る
    $ c4.5rules -f golf -u
    • 上に加えて以下が出力される。
      Evaluation on test data (2 items):
      
      Rule  Size  Error  Used  Wrong            Advantage
      ----  ----  -----  ----  -----            ---------
         3     2  50.0%     1      1 (100.0%)     -1 (0|1)    don't
      
      Tested 2, errors 2 (100.0%)   <<
      
                (a)  (b)      <-classified as
               ---- ----
                       1      (a): class do
                  1           (b): class don't
  • 決定木による分類
    $ consult -f golf

交差検定

  • C4.5付属の xval.sh で交差検定用のデータセットを生成できる。

*1 MATLAB Note/統計/決定木 も参照して下さい。
*2 J.R.キンラン(著),古川康一(監訳),AIによるデータ解析,トッパン,1995.p.4
*3 J.R.キンラン(著),古川康一(監訳),AIによるデータ解析,トッパン,1995.p.7
*4 J.R.キンラン(著),古川康一(監訳),AIによるデータ解析,トッパン,1995.p.7より引用
*5 J.R.キンラン(著),古川康一(監訳),AIによるデータ解析,トッパン,1995.p.7より一部引用
*6 教科書には「テストデータを分類する際に分類の精度を落とさないで~」とあるが、学習データから単純化決定木を作っているような記述もある。
*7 オーバフィッティングの確率を出している?
*8 J.R.キンラン(著),古川康一(監訳),AIによるデータ解析,トッパン,1995.p.8より一部引用
*9 このテストデータは適当に作ったので、ある意味当然か。
*10 J.R.キンラン(著),古川康一(監訳),AIによるデータ解析,トッパン,1995.p.9より一部引用
*11 J.R.キンラン(著),古川康一(監訳),AIによるデータ解析,トッパン,1995.p.9より引用
*12 J.R.キンラン(著),古川康一(監訳),AIによるデータ解析,トッパン,1995.p.11より改変して引用