KNN アルゴリズムの詳細な紹介

KNN アルゴリズムの正式名は k-Nearest Neighbor で、K 最近傍という意味です。

アルゴリズムの説明

KNN は分類アルゴリズムです。その基本的な考え方は、異なる特徴値間の距離を測定することで分類することです。

アルゴリズムのプロセスは次のとおりです:

1. サンプル データ セットを準備します (サンプル内の各データは分類されており、分類ラベルが付いています)。
3. テスト データを入力します。
4. A とサンプルセット内の各データ間の距離を計算します。
6. A からの距離が最も小さい k 点を選択します。最初の k 点の頻度
8. 最初の k 点の最も高い頻度を持つカテゴリを A の予測分類として返します。

主な要因

トレーニングセット（またはサンプルデータ）

トレーニングセットが小さすぎると誤判定が発生します。トレーニングセットが大きすぎると、テストデータを分類するシステムのオーバーヘッドが非常に大きくなります。

距離 (または同様の測定アルゴリズム)

適切な距離測定とは何ですか?距離が近いほど、2 つの点が同じカテゴリに属する​​可能性が高くなります。

距離の測定には次のものが含まれます:

1. ユークリッド距離

ユークリッド距離 (ユークリッド距離とも呼ばれる) は、一般的に使用される距離の定義であり、m 次元空間内の 2 点間の距離を指します。またはベクトルの自然長 (つまり、点から原点までの距離)。 2 次元および 3 次元空間におけるユークリッド距離は、2 点間の実際の距離です。

スペースの問題に適しています。

2. マンハッタン距離

タクシー幾何学またはマンハッタン距離は、19 世紀にハーマン ミンコフスキーによって作成された用語で、標準上の 2 点の絶対軸距離の合計を示す幾何学用語です。座標系。 マンハッタン距離は、軸上のユークリッド空間の固定直交座標系上のユークリッド距離によって形成される線分の射影の距離の合計である。

写真の赤い線はマンハッタン距離を表し、緑は直線距離であるユークリッド距離を表し、青と黄色は等価なマンハッタン距離を表します。 マンハッタン距離 - 2 点間の南北方向の距離に東西方向の距離を加えたもの、つまり d(i, j) = |xi-xj|+|yi-yj|。

パスの問題に適しています。

3. チェビシェフ距離

数学では、チェビシェフ距離は、2 点間の距離の座標間の数値差の最大絶対値として定義されます。

チェビシェフ距離は、チェス盤、倉庫保管、物流アプリケーションなどのメソッド グリッド内の 2 点間の距離を計算するために使用されます。

グリッドの場合、チェビシェフ距離が 1 である点は、この点のムーア近傍です。

グリッド内の距離を計算する問題に使用されます。

4. ミンコフスキー距離

ミンの距離は距離の一種ではなく、一連の距離の定義です。

さまざまな変数パラメータに応じて、最小距離は距離の種類を表すことができます。

式には変数パラメータ p があります:

p=1 の場合、それはマンハッタン距離です。

p=2 の場合、それはユークリッド距離です。

p→∞の場合、それはチェビシェフ距離です。

5. 標準化ユークリッド距離 (標準化ユークリッド距離)

標準化ユークリッド距離は、単純なユークリッド距離の欠点に対処するために作成された改良スキームであり、重み付けされたユークリッド距離とみなすことができます。

標準ユークリッド距離の考え方: データの各次元成分の分布は異なるため、まず各成分を平均と分散が等しくなるように「標準化」する必要があります。

6. マハラノビス距離

はデータの共分散距離を表します。

これは、2 つの未知のサンプルセットの類似性を計算する効果的な方法です。

次元的に独立しているため、変数間の相関による干渉を排除できます。

7. バタチャリヤ距離 統計学では、バタチャリヤ距離は 2 つの離散確率分布を測定するために使用されます。これは、クラス間の分離性を測定するために分類でよく使用されます。

8. ハミング距離

2 つの等しい長さの文字列 s1 と s2 の間のハミング距離は、一方を他方に変更するために必要な最小置換数として定義されます。

たとえば、文字列「1111」と「1001」の間のハミング距離は2です。

アプリケーション:

情報コーディング (耐障害性を高めるために、コード間の最小ハミング距離をできるだけ大きくする必要があります)。

9. 夾角の余弦 (コサイン)

幾何学では夾角の余弦を使用して 2 つのベクトルの方向の差を測定することができ、データマイニングでは差を測定するために使用できます。サンプルベクトル間。

10. Jaccard 類似性係数 (Jaccard 類似性係数)

Jaccard 距離は、2 つのセット間の区別を測定するために、2 つのセット内のすべての要素に対する比率を使用します。

Jaccard 類似性係数は、サンプルの類似性を測定するために使用できます。

11. ピアソン相関係数

ピアソン相関係数は、ピアソン積率相関係数とも呼ばれ、線形相関係数です。 ピアソン相関係数は、2 つの変数間の線形相関の程度を反映するために使用される統計です。

高次元が距離測定に及ぼす影響:
変数が増えると、ユークリッド距離の識別能力が低下します。

距離に対する変数の値の範囲の影響:
より大きな値の範囲を持つ変数は距離の計算において支配的な役割を果たすことが多いため、最初に変数を標準化する必要があります。

k

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 サイトの他の関連記事を参照してください。