KNNアルゴリズムとKDツリー

KNNアルゴリズムとKDツリー
KNNアルゴリズムの構想は非常に簡単で,新しいサンプルに対して,それに最も近いk個のサンプルを探し出し,さらにこのk個のサンプルのカテゴリに基づいて,多数投票により新しいサンプルのカテゴリを予測する.k近隣アルゴリズムには学習や訓練過程がない.しかし、k近隣アルゴリズムには、超パラメータk値の選択、距離のメトリック方式、決定規則、およびk近隣を迅速に検索するアルゴリズム(kdツリーなど)など、注目すべき点が多い.
1.KNNアルゴリズムの三要素
KNNアルゴリズムの流れは非常に簡単で,1つのKNNアルゴリズムを決定し,3つの基本要素を明確にすればよい.すなわち、k値の選択、距離のメトリック方式、決定規則である.
1.1 k値の選択
KNNアルゴリズムにおいてk値は,新しいサンプルに対して訓練セットから最も近いk個のサンプルを選択し,このk個のサンプルで新しいサンプルのカテゴリを決定することを表す.k値はスーパーパラメータとして,適切な値を遅く明確に与え,kが大きすぎるか小さすぎるとアルゴリズム誤差が増大する.一般に、k値のサイズは、検証セットを残すことによって決定することができる.すなわち、検証セットの精度が最も高いk値を選択する.
1.2距離測定方式
サンプル間の距離を計算する場合、異なる距離計算方式があり、一般的にはヨーロッパ式の距離が一般的であり、より一般的なLp L p距離を採用することもできる.
Lp L p距離:Lp(xi,xj)=(Σnk∣xki−xkj∣p)1 pL p(x i,xj)=(Σkn|xik−xjk|p)1 p
ヨーロッパ式距離はLp L p距離の特殊な情況で、つまりp=2 p=2の時:
ヨーロッパ式距離:L 2(xi,xj)＝Σnk∣xki−xkj∣2−−−−−−−−−−−−−−−−−−−−−√L 2(x i,x j)＝Σkn｜xik−xj｜2
またマンハッタン距離(街区距離とも呼ばれる)もLp L p距離の特殊な場合,すなわちp=1 p=1の場合である.
マンハッタン距離:L 1(xi,xj)=Σnk∣xki−xkj∣L 1(x i,x j)=Σkn|xik−xj|
p=∞p=∞であれば、
Lp(xi,xj)=(∑nk∣∣xki−xkj∣∣∞)1∞=maxk∣∣xki−xkj∣∣ L p ( x i , x j ) = ( ∑ k n | x i k − x j k | ∞ ) 1 ∞ = max k | x i k − x j k |
異なる距離メトリック方式を選択すると、最終結果も異なり、一般的にはヨーロッパ式の距離を選択します.
1.3決定規則
決定ルールとは,訓練集中が新しいサンプルに最も近いk個のサンプル決定をどのように利用するかを指す.デフォルトでは、通常、多数の投票ルール(すなわち、k個のサンプルが属するカテゴリが最も多いクラスを選択する)が使用されるため、決定ルールの重要性は無視されやすい.もしあなたが望むなら、他の意思決定ルールを選ぶこともできます.
1.4 KNNアルゴリズムの解
先に説明したように,KNNアルゴリズムをコードで以下のように解釈した.
問題の説明
トレーニングデータセット(n個のサンプル):D={(x 1,y 1),(x 2,y 2),…,(xn,yn)}D={(x 1,y 1),(x 2,y 2),.,(x n,y n)}新しいサンプル:x x x
新しいサンプルxのカテゴリを明確にする必要がある

train_data #     
train_label #         ，           ， trian_data[i]    train_label[i]
distances = []
for i in range(0, len(train_data)):
    distances.append(distance(x,train_data[i])) #    x          
nn = np.argsort(distances) # distances    ，          
y = decision_rule(nn[0:k-1]) # k              x   

上記のアルゴリズムによれば,訓練サンプルの数が少ない場合に実行可能であり,線形走査による一度の計算消費の計算量はそれほど大きくない.しかし、訓練サンプルのデータ量が大きい場合は?各新しいサンプルは,すべての訓練サンプルと距離を計算する必要があり,距離を計算した後もソートする必要があり,時間的複雑度も空間的複雑度も高く,サンプル数が大きい場合,このような複雑度は受け入れられない.では、もっと効率的な方法はありませんか?ここでは、最小スタック(ソート時間とソートに必要な空間を減らす)、トレーニングデータのソートなど、個人的な見解があります.
さいしょうスタック
前のアルゴリズムフローでは,試料xとすべての訓練試料との距離を保存し,その後並べ替え,前k個の訓練試料を取って決定した.しかし、実際にはk kサイズの最小スタックを維持することができます.毎回の距離の計算では,この最小スタックを更新するだけでよい.すべての距離を保存する必要がなく、メモリ容量を節約できます.また、計算量を削減できます.
トレーニングデータのソート
最も初歩的な考え方は,まず訓練データを並べ替え,順序付けされた訓練データに対しては,検索のたびに二分ルックアップ法を用いることで,近隣のサンプルを見つけることができ,k近隣のものは近隣の近くにある.しかし、実はよく考えてみると、これは操作できないので、何に基づいて並べ替えますか?訓練データから新しいサンプルまでの距離に基づいてソートするのか.Are you kidding me? これが最も原始的なアルゴリズムではないでしょうか.naiveです.
では、実際の状況では、どうすればいいのでしょうか.よく見かけるのはKDツリーです.
2.KDツリー
前にいくつかの私自身の考えが検索戦略を改善する構想を提出して、実はKNNアルゴリズムはもっと詳しくて使いやすい検索アルゴリズムがあって、つまりkdツリー、kdツリーはk-dimensional treeを表します.kdツリーのkとknnのkは全く意味が異なり、kdツリーのkは英語名のkのようにk次元を表すことに注意してください.
kdツリーの考えはまず訓練データで検索ツリーを構築することであり、私の前にデータを並べ替える考えも実はこれをやりたいと思っていたが、私自身はこんなに深くは思わなかった.ツリーを構築してから、ツリーを検索すると、検索時間を大幅に節約できます.kdツリーでKNN問題を解決する主な2点は,1)kdツリーの構築;2)kdツリー検索の利用方法.
2.1 kdツリーの構築
kdツリーの構築は比較的簡単で,1~k次元(サンプルxi x iの次元はk)から順にデータセットを左右の2つのノードに分割し,すべての訓練サンプルが分割されるまで再帰的に分割する.
kdツリーを構築するプロセス

x(1)x(1)x(1)を初期の分割座標軸として選択し、すべての訓練サンプルの座標軸x(1)x(1)の下の中位点(奇数サンプルであれば中間位置の数、偶数サンプルであれば中間2つの数の平均値)を計算し、この中位点を通過することで、すべての訓練サンプルをルートノードとして2つの部分に分割することができ、この2つの部分は、左右のサブノードの分割データサンプル

とする.

深さj jのノードについて、j(mod)k+1 j(m o d)k+1(ルートノードの深さ0)を分割の座標軸として選択し、同様に中位点でデータを2つの部分に分割する.

は、サンプルが区分されないまで往復する.

kdツリーは、各サンプルが1つのノードを占めることを保証します.2つの点x 1(3,5)、x 2(3,10)x 1(3,5)、x 2(3,10)が同じ分割点で区切られても?
2.2 kdツリーで検索
kdツリーの構築は比較的簡単であり,kdツリー上でどのように検索し,k近隣のサンプルと近隣のサンプルを見つけるかが鍵である.
kdツリー探索k近隣

新しいサンプルxについて、まず、サンプルに対応するリーフノードが見つかった(kdツリー上で検索されたプロセスでも、完全に一致する点が見つかった場合、リーフノードに再帰される).サンプルxの現在の次元の座標がノードの座標より小さい場合、左サブノードに移動します.そうでない場合、右サブノードに移動します.

葉結点を近隣とする.

は、リーフノードからロールバックを開始し、ロールバック路上のノードについて、ノードとサンプルxとの距離を判断する(k個の近隣点がまだ揃っていない場合は加入する;整列しているが、k近隣の点より近い場合は、k近隣結果を更新する).また,各ロールバックノードについて,そのノードの別のサブノード検索に入るか否かを判断する必要があるが,どのように判断するか.k近傍のk個の点のうち、必ず試料点xから最も遠い点が存在する場合、それらの間の距離を判断基準とし、リターンノードの分割座標軸から試料xまでの距離がこの最も遠い距離より大きい場合、これ以上探索する必要はない.

はルートノードまでロールバックします.