14 最小記述長

この章では、属性評価を計算する監視あり手法である最小記述長について説明します。

MDLとは

最小記述長（MDL）は、情報理論モデルの選択原理の1つです。MDLでは、最も単純でコンパクトな表現が、データの説明として最適かつ最も可能性が高いとみなされます。MDL原理は、Oracle Data Miningの属性評価モデルの作成に使用されます。

MDLでは、各属性をターゲット・クラスの単純な予測モデルとして考えます。単一予測子のこれらのモデルは、MDLメトリック（ビット単位での圧縮）に関して互いに比較され、ランク付けされます。MDLでは、オーバーフィットを回避するため、モデルの複雑性にペナルティが課されます。これは、比較を公平に行うために（モデルとしての）予測子の複雑性を考慮した、合理的なアプローチです。

MDLでは、モデル選択の問題は、通信の問題として扱われます。送信者、受信者および送信するデータがあります。分類モデルでは、送信するデータがモデルで、これはトレーニング・データにおけるターゲット・クラス値のシーケンスです。

属性評価では、2つの部分で構成されるコードを使用してデータを送信します。前半部分（プリアンブル）ではモデルを送信します。モデルのパラメータは、予測の各値に関連するターゲットの確率です。ターゲットの値がj個、予測子の値がk個、各値に対してn_i（i= 1、...、k）個の行がある場合、C_i個（n_i-1個からj-1個を一度に選び出す組合せの数）の条件付き確率が考えられます。プリアンブルのビット・サイズは、Sum(log₂(C_i))と示すことができます。ここで、Sumはkに対する合計です。こうして計算した値が、それぞれの単一予測モデルに関連付けられるペナルティを表します。コードの後半部分では、モデルを使用してターゲット値を送信します。

シーケンスの最もコンパクトな符号化とは、記号（ターゲット・クラス値）の確率に最も適合する符号化であることがよく知られています。したがって、シーケンスに最も高い確率を割り当てるモデルには、最小のターゲット・クラス値の送信コストが含まれます。これは、ビットではSum(log₂(p_i))となります。ここで、p_iは、モデルに関連する行_iの予測確率です。

予測子のランクは、関連付けられた記述長のリストにおける位置で表されます（最短が先頭）。

MDL用のデータ準備

MDLに対する自動データ準備では、監視ありビニングが実行されます。監視ありビニングでは、ディシジョン・ツリーを使用して最適なビンの境界が作成されます。質的属性と量的属性のいずれもビニングされます。

MDLでは、欠損値をそのまま（ランダムに欠損している値として）処理します。スパースな量的データは0（ゼロ）に、スパースな質的データはゼロ・ベクトルに置換されます。ネストした列の欠損値はスパースとして解釈されます。単純なデータ型の列の欠損値は、ランダムに欠損した値として解釈されます。

独自のデータ準備を行う場合、MDLでは通常ビニングを行うことによってメリットが得られます。ただし、データ内に外れ値が存在する場合に外部等幅ビニングを使用すると、属性評価モデルの識別能力が著しく低下することがあります。この手法では、ほとんどのデータが少数のビン（極端な場合は単一のビン）に集中する可能性があります。この場合、より優れた解決策として、分位ビニングを使用します。