この記事は、https://www.oneapi.io/spec/ で 2023年9月14日に公開された『oneAPI 1.3 Provisional Specification Rev. 1』 (HTML、PDF) をベースにしています。原文は2000 ページ近くあり、翻訳の時間とリソースも限られるため、全文翻訳ではなく、記事形式で区切った仕様とその解説を提供することにしました。
この回では、『oneAPI 1.3 Provisional Specification Rev. 1』の「oneDAL」の「Nearest Neighbors (kNN)」の節を取り上げています。
k 近傍法 (kNN)
k 近傍法分類 (kNN)
kNN 分類アルゴリズムは、トレーニング・セットから k 近傍観測値の多数決を計算することで、新しい特徴ベクトルのクラスを推測します。
| 操作 | 計算メソッド | プログラミング・インターフェイス | |||
|---|---|---|---|---|---|
| トレーニング | ブルートフォース | k-d ツリー | train(…) |
train_input |
train_result |
| 推論 | ブルートフォース | k-d ツリー | infer(…) |
infer_input |
infer_result |
数学的定式化
トレーニング
X = {x1, …, xn} を p 次元の特徴ベクトルのトレーニング・セット、Y = {y1, …, yn} をクラスラベルのセットであると仮定します。ここで、yi ∈ {0, …, c−1}、1 ≤ i ≤ n です。X、Y および最近傍 k が与えられると、問題はトレーニング内の特徴ベクトルと推論ステージでの推論セット間の距離計算を可能にするモデルを構築します。
トレーニング法: ブルートフォース
トレーニング操作は、初期トレーニング・セット X からすべての特徴ベクトルを格納するモデルを生成します。
トレーニング法: k-d ツリー
トレーニング操作は、トレーニング・セット X を分割する k-d ツリーを構築します (詳細は、「k-d ツリー」 (英語) を参照)。
推論
を p 次元の特徴ベクトルの推論セットとします。トレーニング・ステージで生成されたモデル X′、および最近傍数 k が与えられた場合、問題は、次の手順を実行してこれぞれの 
(1 ≤ j ≤ m) のラベル 
を予測します。
ユークリッド距離
に最も近い、トレーニング・セット内の k特徴ベクトルのセット
を特定します。l番目のクラスの条件付き確立を、ラベルyjがlに等しい
内のベクトルの比率として推測します。
特徴ベクトル
の確立が最も高いクラスを予測します。
推論法: ブルートフォース
ブルートフォース推論法は、実装で定義される順序ですべてのペア 
(1 ≤ i ≤ n、1 ≤ j ≤ m ) を反復することで、最も近い特徴ベクトルのセット 
を決定します。最終的な予測は式 (1) と (2) に従って計算されます。
推論法: k-d ツリー
k-d ツリー推論法は、k-d ツリーを走査して、 (1 ≤ j ≤ m) に最も近いリーフノードに関連する特徴ベクトルを見つます。現在分かっている k 番目の最近傍の集合 
は、ツリーの走査中に漸進的に更新されます。探索アルゴリズムは、 と特徴空間のそれぞれの部分との間の距離が、 と から最も遠い特徴ベクトルとの間の距離以上のノードの探索を制限します。ツリーの走査が終了すると、
になります。最終的な予測値は式 (1) と (2) に従って計算されます。
使用例
使用例については、こちら (英語) を参照してください。
プログラミング・インターフェイス
この節のすべてのタイプと関数は、oneapi::dal::knn 名前空間で宣言され、oneapi/dal/algo/knn.hpp ヘッダーファイルをインクルードして使用できます。
プログラミング・インターフェイスについては、こちら (英語) を参照してください。
法務上の注意書き
The content of this oneAPI Specification is licensed under the Creative Commons Attribution 4.0 International License (英語). Unless stated otherwise, the sample code examples in this document are released to you under the MIT license (英語).
This specification is a continuation of Intel’s decades-long history of working with standards groups and industry/academia initiatives such as The Khronos Group*, to create and define specifications in an open and fair process to achieve interoperability and interchangeability. oneAPI is intended to be an open specification and we encourage you to help us make it better. Your feedback is optional, but to enable Intel to incorporate any feedback you may provide to this specification, and to further upstream your feedback to other standards bodies, including The Khronos Group SYCL* specification, please submit your feedback under the terms and conditions below. Any contribution of your feedback to the oneAPI Specification does not prohibit you from also contributing your feedback directly to other standard bodies, including The Khronos Group under their respective submission policies.
By opening an issue, providing feedback, or otherwise contributing to the specification, you agree that Intel will be free to use, disclose, reproduce, modify, license, or otherwise distribute your feedback at its sole discretion without any obligations or restrictions of any kind, including without limitation, intellectual property rights or licensing obligations.
This document contains information on products, services and/or processes in development. All information provided here is subject to change without notice.
© Intel Corporation. Intel、インテル、Intel ロゴ、その他のインテルの名称やロゴは、Intel Corporation またはその子会社の商標です。
* その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。
