インテル® DAAL 2018 デベロッパー・ガイド

詳細

ライブラリーは、多次元二分検索木に基づく KNN 分類を提供します (KD 木、ここで D は次元を意味し、K は特徴空間の次元の数を意味します)。詳細は、[James2013]、[Patwary2016] を参照してください。

サイズ pn 特徴ベクトル x1= (x11,…,x1p), …,xn= (xn1,…,xnp) およびクラスラベルのベクトル y = (y1,…,yn)、ここで yi {0, 1, ..., C - 1} および C はクラスの数、特徴ベクトル xi が属するクラスで、KNN 分類器を作成します。

正の整数パラメーター k およびテスト観測 x0 で、KNN 分類器は次の操作を行います。

  1. ユークリッド距離に従って x0 に最も近い訓練データの k 特徴ベクトルのセット N0 を識別します。
  2. ラベル yj に等しい N0 のベクトルの割合として、クラス j の条件付き確率を推定します。
  3. テスト観測 x0 に最も大きな確率のクラスを割り当てます。

KNN アルゴリズムのインテル® DAAL バージョンは、KD 木として知られる空間分割データ構造を使用する PANDA アルゴリズム [Patwary2016] を使用します。木の葉ノード以外のノードは、特徴空間を分割する特徴の識別子および特徴空間を 2 つの部分に分割する分割超平面を定義する適切な特徴値 (切り取り点) を含みます。木の葉ノードには、訓練データセットの要素の関連するサブセット (バケット) があります。バケットの特徴ベクトルは、根ノードからそれぞれの葉までの経路の木ノードで定義された空間の領域に属します。

訓練段階

葉ノード以外のノードでは、KD 木を構築するプロセスは、特徴 (特徴空間の次元) および特徴空間を分割する特徴の値 (切り取り点) の選択を含みます。このプロシージャーは、木の根ノードの特徴空間全体で開始し、木の次のレベルで特徴空間のさらに小さな部分を処理します。

PANDA アルゴリズムは、分割で分散が最大の次元を選択して KD 木を構築します [Patwary2016]。そのため、木の新しい葉ノード以外のノードについて、アルゴリズムは各特徴の空間のそれぞれの領域に属する値の分散を計算し、分散が最大の特徴を選択します。この操作の計算コストは高いため、PANDA は特徴値のサブセットを使用して分散を計算します。

PANDA は、サンプリング・ヒューリスティックを使用して選択した特徴のデータ分布を推定し、推定中央値を切り取り点として選択します。

PANDA は、葉ノードの特徴ベクトルの数が事前に定義されたしきい値以下になるまで、新しい KD 木レベルを生成します。しきい値に達すると、PANDA は木の成長を停止させて、それぞれの葉ノードのバケットと特徴ベクトルを関連付けます。

予測段階

KNN 分類器とクエリーベクトル x0, ..., xr で、これらのベクトルのラベルを計算します。指定された各クエリーベクトル xi について解くため、アルゴリズムは KD 木を走査して xi に最も近い葉ノードに関連付けられている特徴ベクトルを見つけます。検索中に、アルゴリズムは、クエリーベクトルと特徴空間のそれぞれの部分の間の距離が k 番目の近傍からの距離以上であるノードの調査を制限します。この距離は、木の走査中に段階的に更新されます。