数値特徴量とのバイナリ分類用の正確なスプリッター

このユニットでは、次の設定で $\mathrm{feature}_i \geq t$ という条件を作成する、最もシンプルで一般的な分割アルゴリズムについて説明します。

• バイナリ分類タスク
• サンプルに欠損値がない
• 例で事前に計算されたインデックスなし

数値特徴を持ち、バイナリラベル「オレンジ」と「青」を持つ $n$ の例があるとします。正式には、データセット $D$ を次のように記述します。

$$D = \{(x_i,y_i)\}_{i\in[1,n]}$$

ここで

• $x_i$ は、$\mathbb{R}$（実数の集合）の数値特徴の値です。
• $y_i$ は {orange, blue} のバイナリ分類ラベル値です。

目標は、サンプル $D$ を $x_i \geq t$ 条件に従ってグループ $T (rue)$ と $F(alse)$ に分割することでしきい値 $t$(しきい値) を見つけ、ラベルの分離を向上させることです。たとえば、$&$ などは、$$ や $&があります。

シャノン エントロピーは、無秩序の尺度です。バイナリラベルの場合:

• 例に示すラベルのバランスが取れている場合、シャノン エントロピーは最大になります（青 50%、オレンジ 50%）。
• 例のラベルが純粋な場合（100% が青または 100% がオレンジ）は、シャノン エントロピーが最小値（値ゼロ）になります。

図 8. 3 つの異なるエントロピー レベルです。

 

正式には、$T$ と $F$ のラベル分布のエントロピーの加重和を減らす条件を見つける必要があります。対応するスコアは、情報ゲインです。これは、$D$' のエントロピーと {$T$,$F$} エントロピーの差です。この差を「情報ゲイン」と呼びます。

次の図では、エントロピーが高いままで情報が少なくなる、不良なスプリットを示しています。

図 9. 分割が不適切な場合でも、ラベルのエントロピーは減少しません。

 

対照的に、次の図ではエントロピーが低くなる（そして情報が増える）場合のスプリットが良くなります。

図 10. 分割を適切に行うと、ラベルのエントロピーが減少します。

 

形式設定:

\[\begin{eqnarray} T & = & \{ (x_i,y_i) | (x_i,y_i) \in D \ \textrm{with} \ x_i \ge t \} \\[12pt] F & = & \{ (x_i,y_i) | (x_i,y_i) \in D \ \textrm{with} \ x_i \lt t \} \\[12pt] R(X) & = & \frac{\lvert \{ x | x \in X \ \textrm{and} \ x = \mathrm{pos} \} \rvert}{\lvert X \rvert} \\[12pt] H(X) & = & - p \log p - (1 - p) \log (1-p) \ \textrm{with} \ p = R(X)\\[12pt] IG(D,T,F) & = & H(D) - \frac {\lvert T\rvert} {\lvert D \rvert } H(T) - \frac {\lvert F \rvert} {\lvert D \rvert } H(F) \end{eqnarray}\]

ここで

• $IG(D,T,F)$ は、$D$ を $T$ と $F$ に分割して得られる情報です。
• $H(X)$ は、サンプル $X$ のエントロピーです。
• $|X|$ は、セット $X$ 内の要素の数です。
• $t$ はしきい値です。
• $pos$ は正の値です（上記の例では「&blue」など）。別のラベルをポジティブ ラベルとして選択しても、エントロピーの値や情報のゲインは変化しません。
• $R(X)$ は、$X$ の例における正のラベル値の比率です。
• $D$ は（このユニットで前述した）データセットです。

次の例では、単一の数値特徴 $x$ を持つ 2 項分類データセットを想定しています。次の図は、さまざまなしきい値 $t$ 値（x 軸）を示しています。

1. 特徴 $x$ のヒストグラム。
2. $D$、$T$、$F$ のセットにおける「青色の」例の比率をしきい値に基づいて決定。
3. $D$、$T$、$F$ のエントロピー。
4. 情報の獲得。つまり、$D$ と {$T$,$F$} の間のエントロピーのデルタを、サンプル数で重み付けします。

図 11. 4 つのしきい値のプロット。

 

これらのプロットは、以下のものを示しています。

• 「頻度」は、18 ～ 60 の濃度で観測が比較的広く分散していることを示しています。値の分散が広くなると、多くの分割の可能性があるため、モデルのトレーニングに適しています。

• データセット内のラベルの「青」の比率は 25% 程度です。青色のラベルの比率は、しきい値が 20 ～ 50 であることを示します。

  • $T$ セットには、過剰な「青」のラベルの例が含まれています（しきい値 35 で最大 35%）。
  • $F$ セットには、「青」のラベルの例の補修収支が含まれています（しきい値 35 では 8% のみ）。

  「青いラベルの比率」と「エントロピー」のプロットは、しきい値のこの範囲でラベルを比較的うまく分離できることを示します。

• この所見は、「情報ゲイン」プロットで確定します。最大 0.074 の情報ゲイン値に対して t~=28 で最大の情報ゲインが得られます。したがって、スプリッターから返される条件は $x \geq 28$ となります。

• 情報ゲインは常に正または null になります。しきい値が最大値 / 最小値に収束すると、0 に収束します。その場合、$F$ または $T$ は空になり、もう一方にはデータセット全体が含まれ、$D$ のものと等しいエントロピーが表示されます。$H(T)$ = $H(F)$ = $H(D)$ の場合、情報ゲインもゼロになります。しきい値 60 で、$F と$ F および $と$ $および$ F のそれぞれの値に対するラベルが

実数の集合（$\mathbb{R}$）における $t$ の候補値は無限です。ただし、サンプルの数には限りがあるため、$T$ と $F$ に分割される $D$ のセグメントは限られています。したがって、テストされるのは、有限数の $t$ の値のみです。

従来のアプローチでは、値 x_i を昇順に並べ替え、x_s(i) は次のようになります。

$$ x_{s(i)} \leq x_{s(i+1)} $$

次に、$x_i$ の連続する並べ替えられた値の中間の値ごとに $t$ をテストします。たとえば、特定の特徴の浮動小数点値が 1,000 個あるとします。並べ替えた後、最初の 2 つの値は 8.5 と 8.7 とします。この場合、最初にテストするしきい値は 8.6 になります。

正式には、t に対して次の候補値が考慮されます。

$$ X = \left\{ \frac {x_{s(i)} + x_{s(i + 1)}} {2} \lvert x_{s(i)} \ne x_{s(i+1)} \right\} $$

このアルゴリズムの時間複雑性は $\mathcal{O} ( n \log n) $ であり、特徴値が並べ替えられたことでノード内のサンプル数が $n$ になっています。ディシジョン ツリーに適用した場合、各ノードと各特徴にスプリッター アルゴリズムが適用されます。各ノードはその親サンプルの最大 1/2 を受け取ることに注意してください。したがって、マスター定理によれば、このスプリッターでディシジョン ツリーをトレーニングする場合の複雑さは次のようになります。

$$ \mathcal{O} ( m n \log^2 n ) $$

ここで

• $m$ は特徴の数です。
• $n$ はトレーニングの例の数です。

このアルゴリズムでは、特徴の値が重要です。順序が重要です。このため、このアルゴリズムは特徴値のスケールや分布とは独立して機能します。したがって、ディシジョン ツリーのトレーニングで数値特徴を正規化またはスケーリングする必要はありません。