kNN と ANN
ベクトル検索アルゴリズムの 2 つの主要なカテゴリは、K ニアレスト ネイバー (kNN) と近似ニアレスト ネイバー (ANN: 人工ニューラル ネットワークと混同しないでください) です。 kNN は正確ですが、計算負荷が高いため、大規模なデータセットには適していません。 一方、ANN は、精度と効率のバランスがよく、大規模なアプリケーションに適しています。
kNN のしくみ
- ベクター化: データセット内の各データ ポイントは、多次元空間のベクトルとして表されます。
- 距離の計算: 新しいデータ ポイント (クエリ ポイント) を分類するために、このアルゴリズムは、distance 関数を使用して、クエリ ポイントとデータセット内の他のすべてのポイント間の距離を計算します。
- ネイバーの検索: アルゴリズムは、計算された距離に基づいて、クエリ ポイントに最も近い k 個のデータ ポイント (ネイバー) を識別します。 k (ネイバーの数) の値は非常に重要です。 k の値が小さい場合、ノイズの影響を受けやすい可能性があり、k の値が大きい場合、詳細が欠落する可能性があります。
- 予測の実行:
- 分類: 分類タスクの場合、kNN は、k 個のネイバー ノードの中で最頻であるクエリ ポイントにクラス ラベルを割り当てます。 つまり、「多数決」によって決定します。
- 回帰: 回帰タスクの場合、kNN は、クエリ ポイントの値を k 個のネイバーの平均値 (または重み付けされた平均) として予測します。
ANN のしくみ
- ベクター化: データセット内の各データ ポイントは、多次元空間のベクトルとして表されます。
- インデックス作成とデータ構造: ANN アルゴリズムでは、高度なデータ構造 (KD ツリー、ローカリティに依存するハッシュ、グラフ ベースのメソッドなど) を使用してデータ ポイントのインデックスを作成し、検索を高速化します。
- 距離の計算: ANN アルゴリズムでは、すべてのポイントへの正確な距離を計算する代わりに、ヒューリスティックを使用して、最も近いネイバーを含む可能性が高い空間の領域をすばやく特定します。
- ネイバー ノードの検索: このアルゴリズムは、クエリ ポイントに近い可能性が高いデータ ポイントのセットを識別します。 これらのネイバーは、正確に最も近いポイントであるとは限りませんが、実用目的では十分に近いポイントと言えます。
- 予測の実行:
- 分類: 分類タスクの場合、ANN は、kNN と同様に、識別されたネイバー ノードの中で最頻のクエリ ポイントにクラス ラベルを割り当てます。
- 回帰: 回帰タスクの場合、ANN は、クエリ ポイントの値を、識別されたネイバーの平均値 (または加重平均) として予測します。