決定木の符号長計算方式の検討

概要

論文の詳細を見る
MDL(Minimum Description Length)基準は、「与えられらたデータをパラメータ自体の符号長を含めて最も短く符号化できる確率モデルを最良のモデルとする」ものである。このMDL基準を決定木の学習に用いる場合、決定木の符号化方法を指定する必要があるが、決定木の符号化方法自体は自明では無い。このためMDL基準を利用する場合、一般的に属性値のグルーピング等に制限を加え、符号化方法を限定している。このため、必ずしも最小の符号長を持つモデルを発見できるわけではない。ここでは、従来の符号化方法を拡張し、グルーピングに制限を加えない場合の符号化方法を提案する。本稿では、まず文献[1]で述べられたMDL基準式を説明する。次に属性Aの値の種類がr個の時の属性値と枝との任意の組み合わせを考える。その組み合わせ数M(r)を用い、文献[1]のMDL基準式の「分岐枝の情報」を置き換え、任意のグルーピングに対するMDL基準式を提案する。
一般社団法人情報処理学会の論文
1995-09-20