属性選択尺度とは？決定木の分割基準をわかりやすく解説

属性選択尺度の基本概念

属性選択尺度（attribute selection measure）とは、クラスラベルが付与された訓練タプルからなるデータパーティションDを、単一のクラスへと「最も良く」分離する分割テストを選び出すためのヒューリスティック（発見的手法）です。

分割基準の結果に従ってDをより小さなパーティションへ分割できる場合、理想的にはすべてのパーティションが純粋（pure）な状態になります。つまり、あるパーティションに属するタプルがすべて同一クラスに属することを意味します。

概念的には、「最良」の分割基準とは、このような純粋なパーティションに最も近い結果をもたらすものを指します。属性選択尺度は、特定のノードにおけるタプルをどのように分割するかを決定する役割を担うため、「分割規則（splitting rule）」とも呼ばれます。

属性選択尺度は、与えられた訓練タプルに対して各属性のランキングを提供します。そして、その尺度において最も優れた評価を得た属性が、当該タプルの分割属性として選択されます。

分割属性が多値属性である場合や、木構造が二分木に限定されるケースでは、分割基準の一部として分割ポイント（split point）または分割サブセット（splitting subset）も併せて決定する必要があります。

パーティションDに対して生成されたツリーノードには分割基準のラベルが付けられ、基準の各結果ごとに枝が作られ、タプルはそれに応じて振り分けられます。代表的な属性選択尺度には、情報利得、利得比、ジニ指数の3つがあります。

情報利得（Information Gain）

情報利得は、クラスに関する最大限の情報をもたらす最適な特徴量・属性を決定するために用いられます。エントロピーという概念に基づく手法であり、ルートノードからリーフノードへと向かう過程で、エントロピーの水準を低減させることを目指します。

ノードNがパーティションDのタプルを保持しているとします。このとき、情報利得が最大となる属性がノードNの分割属性として選ばれます。この属性を採用することで、結果として生じる分割内のタプルを分類するために必要な情報量が最小化され、それらの分割におけるランダム性、すなわち「不純度（impurity）」が最小になります。

利得比（Gain Ratio）

情報利得による尺度には、結果の数が多いテストに対して偏りを持つという弱点があります。そのため、取りうる値の数が多い属性を選好してしまう傾向があります。例えば、製品IDのような一意識別子として機能する属性を考えてみましょう。

製品IDで分割を行うと、膨大な数のパーティションが生じ、それぞれのパーティションには1つのタプルしか含まれません。各パーティションが完全に純粋であるため、この分割に基づいてデータセットDを分類するのに必要な情報量は Info_{product_ID}(D) = 0 となってしまいます。このような問題への対策として、利得比が用いられることがあります。

ジニ指数（Gini Index）

ジニ指数は、CART（Classification And Regression Tree）アルゴリズムで採用されている尺度です。ジニ指数は、データパーティションまたは訓練タプルの集合Dの不純度を、次の式で計算します。

$$\mathrm{Gini(D)=1-\displaystyle\sum\limits_{i=1}^m p_i^2}$$

ここで、p_iはD内のタプルがクラスC_iに属する確率を表し、|C_i,D|/|D|によって計算されます。ジニ指数が小さいほど、そのパーティションの純度が高いことを示します。