K 最近隣人とはデータを分類する ML アルゴリズム

アルゴリズムは機械学習の世界を動かします。

彼らはしばしばその予測能力を称賛され、膨大な量のデータを消費して即座に結果を出す働き者として語られます。

その中には、怠け者と呼ばれることが多いアルゴリズムがあります。 しかし、データ ポイントの分類に関しては、かなりのパフォーマンスを発揮します。 これは k 最近傍アルゴリズムと呼ばれ、最も重要なアルゴリズムの 1 つとしてよく引用されます。   機械学習  アルゴリズム。

k 最近傍アルゴリズムとは何ですか?

k-nearest neighbors (KNN) アルゴリズムは、データ ポイントに最も近いデータ ポイントが属するグループに基づいて、データ ポイントがいずれかのグループのメンバーになる可能性を推定するためのデータ分類方法です。

k 最近傍アルゴリズムは、   教師あり機械学習  分類と回帰の問題を解決するために使用されるアルゴリズム。 ただし、主に分類問題に使用されます。

KNN は、遅延学習のノンパラメトリックアルゴリズムです。

これは、トレーニング データを提供してもトレーニングを実行しないため、遅延学習アルゴリズムまたは遅延学習器と呼ばれます。 代わりに、トレーニング時間中にデータを保存するだけで、計算は実行しません。 データセットに対してクエリが実行されるまで、モデルは構築されません。 これにより、KNN は  データマイニング。

基礎となるデータ分布について何の仮定もしないため、ノンパラメトリックな方法と見なされます。 簡単に言えば、KNN は、データ ポイントの周囲のデータ ポイントを調べることによって、そのデータ ポイントが属するグループを判断しようとします。

A と B の 2 つのグループがあるとします。

データ ポイントがグループ A にあるかグループ B にあるかを判断するために、アルゴリズムはその近くのデータ ポイントの状態を調べます。 データ ポイントの大部分がグループ A にある場合、問題のデータ ポイントがグループ A にある可能性が非常に高く、その逆も同様です。

つまり、KNN では、最も近い注釈付きデータ ポイント (最近傍とも呼ばれます) を調べることによって、データ ポイントを分類します。

K-NN 分類と K-means クラスタリングを混同しないでください。 KNN は、最も近いデータ ポイントに基づいて新しいデータ ポイントを分類する教師付き分類アルゴリズムです。 一方、K-means クラスタリングは  監督されない  データを K 個のクラスタにグループ化するクラスタリング アルゴリズム。

KNN はどのように機能しますか?

前述のように、KNN アルゴリズムは主に分類器として使用されます。 見えない入力データ ポイントを分類するために KNN がどのように機能するかを見てみましょう。

人工ニューラル ネットワークを使用した分類とは異なり、k 最近傍分類は理解しやすく、実装も簡単です。 データ ポイントが明確に定義されているか、非線形である場合に最適です。

基本的に、KNN は投票メカニズムを実行して、目に見えない観測のクラスを決定します。 これは、多数決を持つクラスが問題のデータ ポイントのクラスになることを意味します。

K の値が 1 の場合、最も近い近傍のみを使用してデータ ポイントのクラスを決定します。 K の値が 10 に等しい場合、10 個の最近傍を使用します。

これを概観するために、分類されていないデータ ポイント X を考えます。散布図には、既知のカテゴリ A と B を持つ複数のデータ ポイントがあります。

データポイント X がグループ A の近くに配置されているとします。

ご存知のように、最も近い注釈付きのポイントを見て、データ ポイントを分類します。 K の値が 1 に等しい場合、データ ポイントのグループを決定するために 1 つの最近傍のみを使用します。

この場合、データ ポイント X は、その最近傍が同じグループにあるため、グループ A に属します。 グループ A に 10 個を超えるデータ ポイントがあり、K の値が 10 に等しい場合、データ ポイント X はグループ A に属し、その最近傍点はすべて同じグループに属します。

別の未分類のデータ ポイント Y がグループ A とグループ B の間に配置されているとします。K が 10 に等しい場合、最も多くの票を獲得したグループを選択します。つまり、Y を最も多くの近傍を持つグループに分類することを意味します。 たとえば、Y がグループ B に 7 つの隣人を持ち、グループ A に 3 つの隣人を持っている場合、Y はグループ B に属します。

分類子が投票数が最も多いカテゴリを割り当てるという事実は、存在するカテゴリの数に関係なく当てはまります。

データ ポイントが近傍かどうかを判断するために距離メトリックがどのように計算されるのか疑問に思われるかもしれません。

データ ポイントとその最近傍の間の距離測定値を計算するには、ユークリッド距離、マンハッタン距離、ハミング距離、およびミンコフスキー距離の 4 つの方法があります。 3 つのうち、ユークリッド距離は、最も一般的に使用される距離関数またはメトリックです。

KNN 分類の精度を検証するには、   混同行列  使用されている。 尤度比検定などの他の統計手法も検証に使用されます。

KNN 回帰の場合、手順の大部分は同じです。 投票数が最も多いクラスを割り当てる代わりに、近隣の値の平均が計算され、未知のデータ ポイントに割り当てられます。

KNN アルゴリズムを使用する理由

分類は、データ サイエンスと機械学習における重要な問題です。 KNN は、パターン分類および回帰モデルに使用される、最も古いものの正確なアルゴリズムの 1 つです。

k 最近傍アルゴリズムを使用できる領域の一部を次に示します。

• 信用格付け: KNN アルゴリズムは、個人の信用格付けを、同様の特徴を持つ個人と比較することによって決定するのに役立ちます。
• ローンの承認:信用格付けと同様に、k 最近傍アルゴリズムは、特性を類似した個人と比較することによって、ローンを債務不履行にする可能性が高い個人を特定するのに役立ちます。
• データの前処理:データセットには多くの欠損値が含まれる場合があります。 KNN アルゴリズムは、欠損値を推定する欠損データ代入と呼ばれるプロセスに使用されます。
• パターン認識:パターンを識別する KNN アルゴリズムの機能により、幅広いアプリケーションが作成されます。 たとえば、クレジット カードの使用パターンを検出し、異常なパターンを特定するのに役立ちます。 パターン検出は、顧客の購入行動のパターンを識別するのにも役立ちます。
• 株価予測: KNN アルゴリズムには未知のエンティティの値を予測する才能があるため、過去のデータに基づいて株式の将来の価値を予測するのに役立ちます。
• レコメンデーション システム: KNN は類似した特性を持つユーザーを見つけるのに役立つため、レコメンデーション システムで使用できます。 たとえば、オンライン ビデオ ストリーミング プラットフォームで使用して、同様のユーザーが視聴するものを分析することで、ユーザーが視聴する可能性が高いコンテンツを提案できます。
• コンピューター ビジョン: KNN アルゴリズムが画像分類に使用されます。 同様のデータポイントをグループ化できるため、たとえば、猫をグループ化し、犬を別のクラスにグループ化できるため、いくつかの場合に役立ちます。   コンピュータビジョン  アプリケーション。

K の最適値の選び方

最適な K 値 (つまり、KNN の近傍数) を決定する特定の方法はありません。 これは、どの値を使用するかを決定する前に、いくつかの値を試してみる必要がある場合があることを意味します。

これを行う 1 つの方法は、トレーニング サンプルの一部が「不明」であると見なす (またはそのふりをする) ことです。 次に、k-nearest neighbors アルゴリズムを使用してテスト セット内の未知のデータを分類し、トレーニング データに既に含まれている情報と比較して、新しい分類がどの程度優れているかを分析できます。

2 クラスの問題を扱うときは、K に奇数の値を選択することをお勧めします。そうしないと、各クラスの近傍数が同じになるシナリオが発生する可能性があります。 また、K の値は、存在するクラスの数の倍数であってはなりません。

K の最適値を選択するもう 1 つの方法は、sqrt(N) を計算することです。ここで、N はトレーニング データ セットのサンプル数を表します。

ただし、K=1 や K=2 などのより低い値の K は、ノイズが多く、外れ値の影響を受ける可能性があります。 このような場合、オーバーフィッティングの可能性も高くなります。

一方、K の値が大きいほど、ほとんどの場合、より滑らかな決定境界が生じますが、大きすぎてはいけません。 そうしないと、データ ポイントの数が少ないグループは、常に他のグループに負けてしまいます。 さらに、K を大きくすると計算コストが高くなります。

KNN の長所と短所

KNN アルゴリズムを使用する最も重要な利点の 1 つは、モデルを構築したり、いくつかのパラメーターを調整したりする必要がないことです。 これは遅延学習アルゴリズムであり、熱心な学習者ではないため、モデルをトレーニングする必要はありません。 代わりに、すべてのデータ ポイントが予測時に使用されます。

もちろん、それには計算コストと時間がかかります。 しかし、必要な計算リソースがあれば、KNN を使用して回帰と分類の問題を解決できます。 とはいえ、正確な予測を生成できるより高速なアルゴリズムがいくつかあります。

もちろん、KNN は完璧な機械学習アルゴリズムではありません。 KNN 予測子はすべてをゼロから計算するため、大規模なデータ セットには適していない可能性があります。

KNN と次元の呪い

膨大な量のデータが手元にある場合、そこから迅速かつ直接的な情報を抽出することは非常に困難です。 そのために、本質的にデータを「ポイントに直接到達させる」次元削減アルゴリズムを使用できます。

「次元の呪い」という言葉は、SF映画からそのまま出てきたような印象を与えるかもしれません. しかし、それが意味することは、データに特徴が多すぎるということです。

データに含まれる特徴が多すぎると、モデルが過剰適合するリスクが高くなり、モデルが不正確になります。 また、ディメンションが多すぎると、データセット内のすべてのデータ サンプルが互いに等距離に見えるため、データのグループ化が難しくなります。

k-nearest neighbors アルゴリズムは、次元の呪いにより、オーバーフィッティングの影響を非常に受けやすくなっています。 ただし、この問題は  ブルートフォースの実装  KNNアルゴリズムの。 ただし、大規模なデータセットには実用的ではありません。

機能が多すぎると、KNN はうまく機能しません。 したがって、主成分分析 (PCA)や特徴選択などの次元削減手法は、データ準備段階で実行する必要があります。

KNN: 心をつかんだ怠惰なアルゴリズム

アルゴリズムの中で最も怠惰であるにもかかわらず、KNN は印象的な評判を築いており、いくつかの分類および回帰問題の頼りになるアルゴリズムです。 もちろん、その遅延性により、大規模なデータ セットが関係する場合には最適な選択ではない可能性があります。 しかし、これは最も古く、最も単純で正確なアルゴリズムの 1 つです。

限られた量のデータを使用してアルゴリズムをトレーニングおよび検証することは、非常に困難な作業になる可能性があります。 しかし、効率的に行う方法があります。 これはクロス検証と呼ばれ、トレーニング データの一部をテスト データ セットとして予約することを伴います。