データマイニングの基礎第2章データマイニングの基礎的な手法その2

まず決定木の枝刈りについて

悲観的枝刈り
- 葉ノードのデータを母集団からの標本としてエラー率を計算、母集団のエラー率を推測してそれを元に枝刈りする
  - この説明ではさっぱりわからない
コスト複雑度枝刈り
- 各ノードを根とする部分木のコスト評価関数(エラーコストと葉ノード数に比例するコスト)が閾値を越えるノードを枝刈り
  - まあようするにこれ以上分類してもあまり精度が上がらないというのを計算して分割を止めるのですね
MDL(最小記述長)原理を利用した枝刈り

そもそも「決定木とはなにか」「なにをするためのものか」といったことの説明がさっぱりないので自分なりの理解を書いておくと、与えられたデータセットをクラス分けするために、データの属性毎の分割を各ノードとするツリー状の構造で管理するデータ構造またはその分割結果で、作成した決定木に新しいデータを適用することでクラス分類できるようになることを目指しているのでしょう。つまり「教師あり学習」の「クラス分類」のための手法。単に細かく分類すればいいわけではなく効率的な分割が求められるので最適な分割順や枝刈りに工夫が求められる。
個人的にはそもそもどのような属性でデータを分割しようかというデータ準備、前処理の部分のほうが重要だと思いますね。第1章でもそんなことは書いてありましたけど。

続いて 2.2 ルール学習を読みます。

分離統括法
- 全データからあるルールで説明(被覆、カバー)できるデータを取り除くことを繰り返す
  - つまり if ... else if ... else if .... を繰り返すということですね
ルールの探索手法
- 山登り法
- ビーム探索法
- 発見的手法
- 確率的探索手法
- トップダウン探索 - 一般的なルールから特殊なルールへと探索
- ボトムアップ探索 - 特殊なルールから一般的なルールへと探索

しくみはシンプルですが、探索手法はなかなか面白そうですね。詳細はあまり書かれていません。また非常に計算量が多くかかるようです。