Scikit Learn-K最近傍法（KNN）
この章は、Sklearnの最近傍法を理解するのに役立ちます。
ネイバーベースの学習方法には、両方のタイプがあります。 supervised そして unsupervised. 教師あり近傍ベースの学習は、分類と回帰予測問題の両方に使用できますが、主に業界の分類予測問題に使用されます。
ネイバーベースの学習方法には特別なトレーニングフェーズがなく、分類中にすべてのデータをトレーニングに使用します。また、基になるデータについては何も想定していません。それが彼らが怠惰でノンパラメトリックな性質を持っている理由です。
最近傍法の背後にある主な原理は次のとおりです。
新しいデータポイントまでの距離にある事前定義された数のトレーニングサンプルクローゼットを見つけるには
これらの数のトレーニングサンプルからラベルを予測します。
ここで、サンプルの数は、K最近傍学習のようにユーザー定義の定数にすることも、半径ベースの近傍学習のように点の局所密度に基づいて変化させることもできます。
sklearn.neighborsモジュール
Scikit-learn have have sklearn.neighbors教師なしおよび監視対象のネイバーベースの学習方法の両方に機能を提供するモジュール。入力として、このモジュールのクラスはNumPy配列またはscipy.sparse 行列。
アルゴリズムの種類
ネイバーベースのメソッドの実装で使用できるさまざまなタイプのアルゴリズムは次のとおりです。
強引な
データセット内のポイントのすべてのペア間の距離の力ずくの計算は、最もナイーブなネイバー検索の実装を提供します。数学的には、D次元のNサンプルの場合、ブルートフォースアプローチは次のようにスケーリングします。0[DN2]
小さなデータサンプルの場合、このアルゴリズムは非常に便利ですが、サンプル数が増えると実行不可能になります。キーワードを書くことでブルートフォースネイバー検索を有効にできますalgorithm=’brute’。
KDツリー
ブルートフォースアプローチの計算の非効率性に対処するために発明されたツリーベースのデータ構造の1つは、KDツリーデータ構造です。基本的に、KDツリーはK次元ツリーと呼ばれる二分木構造です。データポイントが入力されるネストされた正投影領域に分割することにより、データ軸に沿ってパラメータ空間を再帰的に分割します。
利点
以下は、KDツリーアルゴリズムのいくつかの利点です。
Construction is fast −パーティショニングはデータ軸に沿ってのみ実行されるため、KDツリーの構築は非常に高速です。
Less distance computations−このアルゴリズムは、クエリポイントの最近傍を決定するために必要な距離計算が非常に少なくなります。必要なのは[ ()] 距離の計算。
短所
Fast for only low-dimensional neighbor searches−低次元（D <20）の隣接検索では非常に高速ですが、Dが大きくなると、非効率になります。パーティショニングはデータ軸に沿ってのみ実行されるため、
キーワードを書くことにより、KDツリー近傍検索を有効にすることができます algorithm=’kd_tree’。
ボールツリー
KDツリーは高次元では非効率的であることがわかっているため、このKDツリーの非効率性に対処するために、ボールツリーデータ構造が開発されました。数学的には、ノード内の各ポイントが重心によって定義された超球内にあるように、データを重心Cと半径rによって定義されたノードに再帰的に分割します。C と半径 r。以下に示す三角不等式を使用して、隣接検索の候補点の数を減らします。
$$ \ arrowvert X + Y \ arrowvert \ leq \ arrowvert X \ arrowvert + \ arrowvert Y \ arrowvert $$利点
ボールツリーアルゴリズムのいくつかの利点は次のとおりです-
Efficient on highly structured data −ボールツリーはデータを一連のネストされたハイパースフィアに分割するため、高度に構造化されたデータに対して効率的です。
Out-performs KD-tree −ボールツリーは、ボールツリーノードの球面幾何学を持っているため、高次元でKDツリーよりも優れています。
短所
Costly −データを一連のネストされたハイパースフィアに分割すると、その構築に非常にコストがかかります。
キーワードを書くことにより、ボールツリー近傍検索を有効にすることができます algorithm=’ball_tree’。
最近傍アルゴリズムの選択
特定のデータセットに最適なアルゴリズムの選択は、次の要因によって異なります。
サンプル数（N）と次元（D）
これらは、最近傍アルゴリズムを選択する際に考慮すべき最も重要な要素です。それは以下の理由によるものです−
ブルートフォースアルゴリズムのクエリ時間は、O [DN]として増加します。
ボールツリーアルゴリズムのクエリ時間は、O [D log（N）]として増加します。
KDツリーアルゴリズムのクエリ時間は、特徴づけるのが非常に難しい奇妙な方法でDとともに変化します。D <20の場合、コストはO [D log（N）]であり、このアルゴリズムは非常に効率的です。一方、D> 20の場合、コストがほぼO [DN]に増加するため、非効率的です。
データ構造
これらのアルゴリズムのパフォーマンスに影響を与えるもう1つの要因は、データの内在次元またはデータのスパース性です。これは、ボールツリーとKDツリーアルゴリズムのクエリ時間が大きな影響を受ける可能性があるためです。一方、ブルートフォースアルゴリズムのクエリ時間は、データ構造によって変更されません。一般に、ボールツリーおよびKDツリーのアルゴリズムは、固有の次元が小さいスパースデータに埋め込まれると、クエリ時間が短縮されます。
隣人の数（k）
クエリポイントに要求されるネイバーの数（k）は、ボールツリーおよびKDツリーアルゴリズムのクエリ時間に影響します。ネイバーの数（k）が増えると、クエリ時間は遅くなります。一方、ブルートフォースのクエリ時間は、kの値の影響を受けません。
クエリポイントの数
構築フェーズが必要なため、クエリポイントが多数ある場合は、KDツリーとボールツリーの両方のアルゴリズムが効果的です。一方、クエリポイントの数が少ない場合、ブルートフォースアルゴリズムはKDツリーおよびボールツリーアルゴリズムよりもパフォーマンスが向上します。