分類木のカテゴリカル予測子の分割

複数レベルの予測子の分割における問題

分類木を成長させるときに、多数のレベルがあるカテゴリカル予測子の最適なバイナリ分割を見つけることは、連続予測子の分割を見つける場合より計算が困難です。連続予測子の場合、隣接する 2 つの一意な予測子の値の中間で木を分割できます。一方、L 個のレベルがあるカテゴリカル予測子の厳密で最適なバイナリ分割を見つけるには、分類木に対して 2^L-1-1 通りの分割を検討しなければなりません。この式を得るには、

1. L 個の異なる値を左右のノードに割り当てる方法の数をカウントします。2^L 通りの方法があります。

2. 左右を交換できるので、2^L を 2 で除算します。

3. 空のノードが含まれるケースを除外します。

回帰問題とバイナリ分類問題では、計算をショートカットする厳密な探索アルゴリズムが使用されます[1]。分類木では、平均応答 (回帰の場合) またはいずれかのクラス確率 (分類の場合) によりカテゴリの順序を決定できます。したがって、最適な分割は順序付きリストの L – 1 とおりの分割の 1 つになります。したがって、クラスの個数が K ≥ 3 であるデータの分類木を成長させる場合のみ、計算が困難になります。

カテゴリカル予測子の分割アルゴリズム

計算を減らすため、適切な分割を見つけるヒューリスティックなアルゴリズムがいくつか用意されています。fitctree を使用して分類木を成長させるときや、アンサンブル分類 (fitcensemble) またはマルチクラス ECOC モデル (fitcecoc) の templateTree を使用して分類学習器を作成するときに、名前と値のペアの引数 'AlgorithmForCategorical' を使用して、カテゴリカル予測子を分割するアルゴリズムを選択できます。

アルゴリズムを指定しなかった場合、カテゴリカル予測子の既知のクラス数およびレベル数を使用して、最適なアルゴリズムが各分割について選択されます。予測子のレベルが MaxNumCategories 個以下である場合、厳密探索アルゴリズムを使用してカテゴリカル予測子が分割されます。それ以外の場合、クラスとレベルの個数に基づくヒューリスティックな探索アルゴリズムが選択されます。MaxNumCategories の既定のレベルは 10 です。プラットフォームによっては、レベル数が 32 または 64 を超えるカテゴリカル予測子に対する厳密探索を実行できません。

使用できるヒューリスティック アルゴリズムは、純度による左への引き寄せ、主成分ベースの分割、クラス別の 1 対他です。

純度による左への引き寄せ

純度による左への引き寄せアルゴリズムでは、はじめに L 個のカテゴリカル レベルをすべて右の枝に配置します。その後、このアルゴリズムは以下の処理を行います。

1. 各クラスの最大のクラス確率をもつ K カテゴリを検査します。

2. 分割基準の最大値をもつカテゴリを左枝に移動します。

3. 右側の子に 1 つのカテゴリしか残らなくなるまで左へのカテゴリの移動を続け、各移動の分割基準を記録します。

このシーケンスが完了すると、分割基準が最大になる分割が選択されます。

このアルゴリズムを選択するには、fitctree または templateTree で 'AlgorithmForCategorical','PullLeft' を指定します。

主成分ベースの分割

主成分ベースの分割アルゴリズム [2] では、分離超平面を探索することにより、L 個の予測子のレベルについて最適に近いバイナリ分割を見つけます。超平面は、センタリングされたクラス確率行列の重み付き共分散行列の 1 番目の主成分に対して垂直になります。

このアルゴリズムは、見つかった主成分とそのカテゴリのクラス確率のベクトル間の内積として計算されるスコアを各 L カテゴリに割り当てます。その後、分割基準が最大になる L - 1 個の分割のうちの 1 つが選択されます。

このアルゴリズムを選択するには、fitctree または templateTree で 'AlgorithmForCategorical','PCA' を指定します。

クラス別の 1 対他

クラス別の 1 対他アルゴリズムでは、はじめに L 個のカテゴリカル レベルをすべて右の枝に配置します。K 個のクラスそれぞれについて、そのクラスの確率に基づいてカテゴリの順序が設定されます。

1 番目のクラスについて、各カテゴリを順番に左の枝に移動し、各移動で分割基準を記録します。その後、このプロセスを残りのクラスについて繰り返します。このシーケンスが完了すると、分割基準が最大になる分割が選択されます。

このアルゴリズムを選択するには、fitctree または templateTree で 'AlgorithmForCategorical','OVAbyClass' を指定します。

複数レベルのカテゴリカル予測子をもつデータの調査

この例では、多数のレベル (カテゴリ) をもつカテゴリカル予測子が含まれているデータ セットを調べる方法と、分類用のバイナリ決定木に学習をさせる方法を示します。

標本データの読み込み

census1994 ファイルを読み込みます。このデータ セットは、個人の年収が $50,000 を超えるかどうかを予測するための、米国勢調査局の人口統計データから構成されいます。変数名が格納されている文字ベクトルの cell 配列を指定します。

load census1994
VarNames = adultdata.Properties.VariableNames;

table adultdata 内の変数には、名前に _ という文字が含まれているものがあります。_ を空白に置き換えます。

VarNames = strrep(VarNames,'_',' ');

予測子データ tbl と応答ベクトル Y を指定します。

tbl = adultdata(:,1:end-1);
Y = categorical(adultdata.salary);

カテゴリカル予測子の調査

一部のカテゴリカル変数には、多数のレベル (カテゴリ) が含まれています。各カテゴリカル予測子のレベルの個数をカウントします。

varfunとisnumericを使用して、table tbl 内の数値ではないカテゴリカル予測子のインデックスを求めます。関数 varfun は、table tbl の各変数に関数 isnumeric を適用します。

cat = ~varfun(@isnumeric,tbl,'OutputFormat','uniform');

numelとcategoriesを使用してカテゴリカル予測子内のカテゴリの個数をカウントする無名関数を定義します。

countNumCats = @(var)numel(categories(categorical(var)));

無名関数 countNumCats は予測子を categorical 配列に変換し、予測子の空でない一意なカテゴリをカウントします。

varfun と countNumCats を使用して、tbl 内のカテゴリカル予測子のカテゴリの個数をカウントします。

numCat = varfun(@(var)countNumCats(var),tbl(:,cat),'OutputFormat','uniform'); 

各カテゴリカル予測子のカテゴリの個数をプロットします。

figure
barh(numCat);
h = gca;
h.YTickLabel = VarNames(cat);
ylabel('Predictor')
xlabel('Number of categories')

モデルの学習

バイナリ分類の場合、多数のカテゴリをもつカテゴリカル予測子の最適な分割を見つけるために、計算のショートカットが使用されます。クラス数が 2 を超える分類の場合、fitctree または templateTree の名前と値のペアの引数 AlgorithmForCategorical' を使用して、適切な分割を見つけるための厳密なアルゴリズムまたはヒューリスティックなアルゴリズムを選択できます。既定では、カテゴリカル予測子の既知のクラス数およびレベル数を使用して、各分割について最適なアルゴリズムのサブセットが選択されます。

tbl と Y を使用して、分類木に学習をさせます。応答ベクトル Y には 2 つのクラスが含まれているので、カテゴリカル予測子の分割には厳密なアルゴリズムが使用されます。

Mdl = fitctree(tbl,Y)

Mdl = 
  ClassificationTree
           PredictorNames: {'age'  'workClass'  'fnlwgt'  'education'  'education_num'  'marital_status'  'occupation'  'relationship'  'race'  'sex'  'capital_gain'  'capital_loss'  'hours_per_week'  'native_country'}
             ResponseName: 'Y'
    CategoricalPredictors: [2 4 6 7 8 9 10 14]
               ClassNames: [<=50K    >50K]
           ScoreTransform: 'none'
          NumObservations: 32561

参照

[1] Breiman, L., J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Boca Raton, FL: Chapman & Hall, 1984.

[2] Coppersmith, D., S. J. Hong, and J. R. M. Hosking. “Partitioning Nominal Attributes in Decision Trees.” Data Mining and Knowledge Discovery, Vol. 3, 1999, pp. 197–217.

参考

fitctree | fitcensemble | templateTree | fitrtree

関連するトピック

• 決定木
• 決定木の成長
• アンサンブル アルゴリズム