最適な機能選択のための高速分岐およびバインドアルゴリズム

Branch＆Bound Methodを使用した最適な機能サブセット選択の新しい検索原理が導入されています。基準値を予測するための簡単なメカニズムのおかげで、多くの遅い基準評価を回避することで、かなりの時間を節約できます。それぞれ非再帰的および再帰的基準フォームでの使用に適した提案された予測メカニズムの2つの実装を提案します。どちらのアルゴリズムも、通常、他の既知のブランチおよびバウンドアルゴリズムの数倍高速であることが最適です。検索問題の指数関数的な性質により、アルゴリズムの計算効率が重要であるため、すべてのブランチおよびバインドされたアルゴリズムの検索パフォーマンスに影響を与える他の要因も調査します。合成基準のセットを使用して、ブランチとバインドされたアルゴリズムの速度が、機能間の多様性、異なるサブセットに関する機能の安定性、および機能セットサイズへの基準関数依存に強く依存することを示します。検索が最も劇的に加速されるシナリオ（線形時間で終了）と最悪の条件を特定します。従来の確率的距離基準を使用して、3つの実際のデータセットで実験的に結論を検証します。

A novel search principle for optimal feature subset selection using the Branch & Bound method is introduced. Thanks to a simple mechanism for predicting criterion values, a considerable amount of time can be saved by avoiding many slow criterion evaluations. We propose two implementations of the proposed prediction mechanism that are suitable for use with nonrecursive and recursive criterion forms, respectively. Both algorithms find the optimum usually several times faster than any other known Branch & Bound algorithm. As the algorithm computational efficiency is crucial, due to the exponential nature of the search problem, we also investigate other factors that affect the search performance of all Branch & Bound algorithms. Using a set of synthetic criteria, we show that the speed of the Branch & Bound algorithms strongly depends on the diversity among features, feature stability with respect to different subsets, and criterion function dependence on feature set size. We identify the scenarios where the search is accelerated the most dramatically (finish in linear time), as well as the worst conditions. We verify our conclusions experimentally on three real data sets using traditional probabilistic distance criteria.