インテル® DAAL 2018 デベロッパー・ガイド
ライブラリーは、多次元二分検索木に基づく KNN 分類を提供します (KD 木、ここで D は次元を意味し、K は特徴空間の次元の数を意味します)。詳細は、[James2013]、[Patwary2016] を参照してください。
サイズ p の n 特徴ベクトル x1= (x11,…,x1p), …,xn= (xn1,…,xnp) およびクラスラベルのベクトル y = (y1,…,yn)、ここで yi ∈ {0, 1, ..., C - 1} および C はクラスの数、特徴ベクトル xi が属するクラスで、KNN 分類器を作成します。
正の整数パラメーター k およびテスト観測 x0 で、KNN 分類器は次の操作を行います。
KNN アルゴリズムのインテル® DAAL バージョンは、KD 木として知られる空間分割データ構造を使用する PANDA アルゴリズム [Patwary2016] を使用します。木の葉ノード以外のノードは、特徴空間を分割する特徴の識別子および特徴空間を 2 つの部分に分割する分割超平面を定義する適切な特徴値 (切り取り点) を含みます。木の葉ノードには、訓練データセットの要素の関連するサブセット (バケット) があります。バケットの特徴ベクトルは、根ノードからそれぞれの葉までの経路の木ノードで定義された空間の領域に属します。
葉ノード以外のノードでは、KD 木を構築するプロセスは、特徴 (特徴空間の次元) および特徴空間を分割する特徴の値 (切り取り点) の選択を含みます。このプロシージャーは、木の根ノードの特徴空間全体で開始し、木の次のレベルで特徴空間のさらに小さな部分を処理します。
PANDA アルゴリズムは、分割で分散が最大の次元を選択して KD 木を構築します [Patwary2016]。そのため、木の新しい葉ノード以外のノードについて、アルゴリズムは各特徴の空間のそれぞれの領域に属する値の分散を計算し、分散が最大の特徴を選択します。この操作の計算コストは高いため、PANDA は特徴値のサブセットを使用して分散を計算します。
PANDA は、サンプリング・ヒューリスティックを使用して選択した特徴のデータ分布を推定し、推定中央値を切り取り点として選択します。
PANDA は、葉ノードの特徴ベクトルの数が事前に定義されたしきい値以下になるまで、新しい KD 木レベルを生成します。しきい値に達すると、PANDA は木の成長を停止させて、それぞれの葉ノードのバケットと特徴ベクトルを関連付けます。