KNN アルゴリズムの正式名は k-Nearest Neighbor で、K 最近傍という意味です。
KNN は分類アルゴリズムです。その基本的な考え方は、異なる特徴値間の距離を測定することで分類することです。
アルゴリズムのプロセスは次のとおりです:
1. サンプル データ セットを準備します (サンプル内の各データは分類されており、分類ラベルが付いています)。
3. テスト データを入力します。
4. A とサンプルセット内の各データ間の距離を計算します。
6. A からの距離が最も小さい k 点を選択します。最初の k 点の頻度
8. 最初の k 点の最も高い頻度を持つカテゴリを A の予測分類として返します。
主な要因
写真の赤い線はマンハッタン距離を表し、緑は直線距離であるユークリッド距離を表し、青と黄色は等価なマンハッタン距離を表します。 マンハッタン距離 - 2 点間の南北方向の距離に東西方向の距離を加えたもの、つまり d(i, j) = |xi-xj|+|yi-yj|。
パスの問題に適しています。 3. チェビシェフ距離 数学では、チェビシェフ距離は、2 点間の距離の座標間の数値差の最大絶対値として定義されます。 チェビシェフ距離は、チェス盤、倉庫保管、物流アプリケーションなどのメソッド グリッド内の 2 点間の距離を計算するために使用されます。 グリッドの場合、チェビシェフ距離が 1 である点は、この点のムーア近傍です。グリッド内の距離を計算する問題に使用されます。
4. ミンコフスキー距離ミンの距離は距離の一種ではなく、一連の距離の定義です。 さまざまな変数パラメータに応じて、最小距離は距離の種類を表すことができます。 式には変数パラメータ p があります:p=1 の場合、それはマンハッタン距離です。
p=2 の場合、それはユークリッド距離です。 p→∞の場合、それはチェビシェフ距離です。
5. 標準化ユークリッド距離 (標準化ユークリッド距離)
情報コーディング (耐障害性を高めるために、コード間の最小ハミング距離をできるだけ大きくする必要があります)。
9. 夾角の余弦 (コサイン)
Jaccard 類似性係数は、サンプルの類似性を測定するために使用できます。
11. ピアソン相関係数
ピアソン相関係数は、ピアソン積率相関係数とも呼ばれ、線形相関係数です。 ピアソン相関係数は、2 つの変数間の線形相関の程度を反映するために使用される統計です。
高次元が距離測定に及ぼす影響:
変数が増えると、ユークリッド距離の識別能力が低下します。
距離に対する変数の値の範囲の影響:
より大きな値の範囲を持つ変数は距離の計算において支配的な役割を果たすことが多いため、最初に変数を標準化する必要があります。
k のサイズが小さすぎると、分類結果がノイズ ポイントの影響を受けやすくなり、誤差が増加します。
k が大きすぎると、最近傍に他のカテゴリのポイントが多すぎる可能性があります (重み付け)。距離が k 値を減らす可能性があります)
k=N (サンプル数) の影響は、現時点では入力インスタンスが何であっても、最も多くの値を持つクラスに属すると単純に予測されるため、まったく望ましくありません。トレーニング インスタンスのモデルが単純すぎるため、トレーニング サンプル内の多くの有用な情報が無視されます。
実際のアプリケーションでは、K 値は通常、最適な値を選択するために交差検証法 (簡単に言えば、一部のサンプルをトレーニング セットとして使用し、一部のサンプルをテスト セットとして使用する) を使用するなど、比較的小さな値をとります。 K値。
経験則: k は通常、トレーニング サンプル数の平方根よりも小さくなります。
1. メリット
シンプルで理解しやすく、実装が簡単で、精度が高く、外れ値に敏感ではありません。
2. 欠点
KNN は、モデルの構築が非常に簡単ですが、すべてのトレーニング サンプルを分類する必要があるため、システムのオーバーヘッドが大きくなります (大量の計算と大きなメモリ オーバーヘッド)。スキャンされ、距離が計算されます。
数値型と公称型(有限個の異なる値を持ち、その値が乱れているもの)。
顧客離れの予測、不正行為の検出など。
ここでは、例として Python を使用して、ユークリッド距離に基づく KNN アルゴリズムの実装を説明します。
ユークリッド距離の式:
ユークリッド距離を例にしたサンプルコード:
#! /usr/bin/env python#-*- coding:utf-8 -*-# E-Mail : Mike_Zhang@live.comimport mathclass KNN: def __init__(self,trainData,trainLabel,k): self.trainData = trainData self.trainLabel = trainLabel self.k = k def predict(self,inputPoint): retLable = "None"arr=[]for vector,lable in zip(self.trainData,self.trainLabel): s = 0for i,n in enumerate(vector) : s += (n-inputPoint[i]) ** 2arr.append([math.sqrt(s),lable]) arr = sorted(arr,key=lambda x:x[0])[:self.k] dtmp = {}for k,v in arr :if not v in dtmp : dtmp[v]=0 dtmp[v] += 1retLable,_ = sorted(dtmp.items(),key=lambda x:x[1],reverse=True)[0] return retLable data = [ [1.0, 1.1], [1.0, 1.0], [0.0, 0.0], [0.0, 0.1], [1.3, 1.1], ] labels = ['A','A','B','B','A'] knn = KNN(data,labels,3)print knn.predict([1.2, 1.1]) print knn.predict([0.2, 0.1])
上記の実装は比較的単純で、scikit-learn などの既製のライブラリを開発時に使用できます。
以上がKNN アルゴリズムの詳細な紹介の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。