属性サブセット選択の基礎知識：最適な属性の組み合わせを見つける4つのヒューリスティック手法

属性サブセット選択とは

属性サブセット選択は、無関係または冗長な属性（次元）を除去することで、データセットのサイズを削減する手法です。その目的は、すべての属性を使用した場合と同じクラスの確率分布にできるだけ近い結果が得られるような、最小限の属性セットを発見することにあります。

n個の属性がある場合、考えられる部分集合は2ⁿ通り存在します。最適な属性サブセットを網羅的に探索することは、特に属性数nやデータクラス数が増加するにつれて非常に高いコストがかかります。そのため、探索空間を絞り込むヒューリスティック手法が一般的に採用されています。

貪欲法によるアプローチ

これらの手法は多くの場合「貪欲法」と呼ばれ、属性空間を探索しながら、その時点で最良と思われる選択を繰り返し行います。局所的な最適解を選び続けることで、最終的に大域的な最適解へ到達することを目指すアプローチです。このような貪欲法は実践において効率的であり、ほぼ最適な解に近い結果をもたらすことができます。

「最良」および「最悪」の属性は、通常、統計的有意性検定を用いて決定されます。この検定では、各属性が互いに独立していると仮定します。また、分類用の決定木構築で使用される情報利得など、さまざまな属性評価尺度を利用することも可能です。

代表的な4つのヒューリスティック手法

1. 段階的前向き選択（Stepwise Forward Selection）

空の属性集合から開始する手法です。まず元の属性の中から最良のものを1つ選んで追加し、以降の各反復ステップで、残りの属性の中から最も良い属性を順次減少セットに挿入していきます。

2. 段階的後向き除去（Stepwise Backward Elimination）

完全な属性集合から開始する手法です。各ステップごとに、集合内に残っている中で最悪の属性を1つずつ除去していきます。

3. 前向き選択と後向き除去の組み合わせ

段階的前向き選択と後向き除去の両方の技術を組み合わせた手法です。各ステップで最良の属性を選択すると同時に、残りの属性から最悪の属性を除去することで、より効率的な探索を実現します。

4. 決定木帰納法（Decision Tree Induction）

ID3、C4.5、CARTなどの決定木アルゴリズムは、本来分類のために設計されたものです。決定木帰納法では、フローチャートに似た構造を構築します。内部ノード（非葉ノード）は属性に対するテストを表し、各ブランチはテストの結果に対応し、外部ノード（葉ノード）はクラス予測を表します。各ノードで、アルゴリズムはデータを単一のクラスに分割するための「最良」の属性を選択します。

決定木帰納法を属性サブセット選択に活用する場合、与えられたデータから決定木を構築します。このとき、木に出現しなかった属性は無関係とみなされ、木に出現した属性の集合が削減後の属性サブセットとして採用されます。