Das Prinzip und die Implementierung des K-Nearest-Neighbor-Algorithmus in Python (Quellcode beigefügt)

In diesem Artikel geht es um das Prinzip und die Implementierung des K-Nearest-Neighbor-Algorithmus (Quellcode im Anhang). Ich hoffe, dass er hilfreich ist zu dir.

Der k-Nearest-Neighbor-Algorithmus führt eine Klassifizierung durch, indem er den Abstand zwischen verschiedenen Merkmalswerten misst.

Prinzip des k-Nearest-Neighbor-Algorithmus

Bei einem Trainingsbeispielsatz mit Beschriftungen wird nach der Eingabe neuer Daten ohne Beschriftung jedes Merkmal der neuen Daten in das integriert Stichprobe Die den Daten entsprechenden Merkmale werden verglichen, und die obersten k ähnlichsten Daten im Beispieldatensatz werden gemäß dem Algorithmus ausgewählt, und die Klassifizierung mit den meisten Vorkommen unter den k ähnlichsten Daten wird als Klassifizierung der neuen ausgewählt Daten.

Implementierung des k-Nearest-Neighbor-Algorithmus

Hier erfolgt nur die Vorhersage einzelner neuer Daten, und die Vorhersage mehrerer neuer Daten gleichzeitig wird später platziert .

Angenommen, es gibt einen Trainingsbeispielsatz X_train (X_train.shape=(10, 2)), die entsprechende Markierung y_train (y_train.shape=(10,), einschließlich 0, 1), verwenden Sie matplotlib. Pyplot zum Zeichnen Es wird wie folgt dargestellt (grüne Punkte stellen Markierung 0 dar, rote Punkte stellen Markierung 1 dar):

Es gibt neue Daten: x (x = np.array([3.18557125, 6.03119673])), die Zeichnungsdarstellung ist wie folgt (blaue Punkte):

Zuerst verwenden Euler-Distanz Die Formel berechnet den Abstand von x zu jeder Stichprobe in:

import math

distances = [math.sqrt(np.sum((x_train - x) ** 2)) for x_train in X_train]

Drittens nehmen Sie die Markierungen, die den k nächsten Stichproben entsprechen: np.argsort()

import numpy as np

nearest = np.argsort(distances)

Zählen Sie abschließend die Markierungen, die den k nächsten Stichproben entsprechen Stichproben, um den größten Anteil herauszufinden. Die Markierung ist die vorhergesagte Klassifizierung des Algorithmus

Ein typischer Algorithmusprozess für maschinelles Lernen besteht darin, den Trainingsdatensatz zu verwenden, um das Modell durch den Algorithmus für maschinelles Lernen zu trainieren (anzupassen). und verwenden Sie dieses Modell, um die Ergebnisse der Eingabeproben vorherzusagen.

Für den k-Nearest-Neighbor-Algorithmus handelt es sich um einen speziellen Algorithmus ohne Modell, aber wir betrachten seinen Trainingsdatensatz als Modell. So wird es in Scikit Learn gehandhabt.

Der k-nächste-Nachbarn-Algorithmus in Scikit Learn verwendet Der k-nächste-Nachbarn-Algorithmus in Scikit Learn befindet sich beim Initialisieren im Nachbarmodul 6, das ist die obige k:

topK_y = [y_train[i] for i in nearest[:k]]

-Methode „trainiert“ den Klassifikator basierend auf dem Trainingsdatensatz. Diese Methode gibt den Klassifikator selbst zurück:

from collections import Counter

votes = Counter(topK_y)
votes.most_common(1)[0][0]

-Methode Diese Methode sagt das Ergebnis der Eingabe voraus. Der Typ des übergebenen Parameters muss eine Matrix sein. Daher wird die -Operation zuerst für x ausgeführt:

import numpy as np
import math

from collections import Counter


def kNN(k, X_train, y_train, x):
    distances = [math.sqrt(np.sum((x_train - x) ** 2)) for x_train in X_train]
    nearest = np.argsort(distances)

    topK_y = [y_train[i] for i in nearest[:k]]
    votes = Counter(topK_y)
    return votes.most_common(1)[0][0]

y_predict-Wert ist 0, was mit dem Ergebnis der zuvor implementierten kNN-Methode übereinstimmt.

fit()

Implementieren Sie den KNeighborsClassifier-Klassifikator in Scikit Learn.

predict()reshapeDefinieren Sie eine KNNClassifier-Klasse, die den Parameter k übergibt, der die ähnlichsten Daten darstellt, die während der Vorhersage ausgewählt wurden :

from sklearn.neighbors import KNeighborsClassifier

kNN_classifier = KNeighborsClassifier(n_neighbors=6)

Die Methode trainiert den Klassifikator und gibt den Klassifikator selbst zurück:

kNN_classifier.fit(X_train, y_train)

Die Methode sagt den zu testenden Datensatz voraus und der Typ des Parameters X_predict ist eine Matrix . Diese Methode verwendet das Listenverständnis, um X_predict zu durchlaufen, und ruft die -Methode einmal für alle zu testenden Daten auf.

X_predict = x.reshape(1, -1)
y_predict = kNN_classifier.predict(X_predict)

Algorithmusgenauigkeitfit()

predict()Probleme mit dem Modell_predict()

Das Modell wurde oben durch den Trainingsbeispielsatz trainiert, aber es Ich weiß nicht, wie gut dieses Modell ist, aber es gibt zwei Probleme.

Wenn das Modell schlecht ist, entsprechen die vorhergesagten Ergebnisse nicht unseren Wünschen. Gleichzeitig ist es in tatsächlichen Situationen schwierig, das tatsächliche Etikett zu erhalten und das Modell zu testen.

Beim Training des Modells enthalten die Trainingsbeispiele nicht alle Marker.

1. Für die erste Frage wird normalerweise ein bestimmter Anteil (z. B. 20 %) der Daten im Stichprobensatz als Testdaten und die restlichen Daten als Trainingsdaten verwendet.

Nehmen Sie als Beispiel die in Scikit Learn bereitgestellten Irisdaten, die 150 Proben enthalten.

2. class KNNClassifier:
       def __init__(self, k):
           self.k = k
           self._X_train = None
           self._y_train = None

   Teilen Sie nun die Stichprobe in 20 % Probentestdaten und 80 % Anteil an Trainingsdaten auf:

   def fit(self, X_train, y_train):
       self._X_train = X_train
       self._y_train = y_train
       return self

Verwenden Sie X_train und y_train als Trainingsdaten zum Trainieren des Modells, X_test und y_test als Testdaten für Überprüfung der Modellgenauigkeit.

Nehmen Sie für die zweite Frage die in Scikit Learn bereitgestellten Irisdaten als Beispiel. Der Inhalt der Y-Markierung lautet:

array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
       1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
       1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
       2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
       2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2])

发现0、1、2是以顺序存储的，在将样本划分为训练数据和测试数据过程中，如果训练数据中才对标记只包含0、1，这样的训练数据对于模型的训练将是致命的。以此，应将样本数据先进行随机处理。

np.random.permutation() 方法传入一个整数 n，会返回一个区间在 [0, n) 且随机排序的一维数组。将 X 的长度作为参数传入，返回 X 索引的随机数组：

shuffle_indexes = np.random.permutation(len(X))

将随机化的索引数组分为训练数据的索引与测试数据的索引两部分：

test_ratio = 0.2
test_size = int(len(X) * test_ratio)

test_indexes = shuffle_indexes[:test_size]
train_indexes = shuffle_indexes[test_size:]

再通过两部分的索引将样本数据分为训练数据和测试数据：

X_train = X[train_indexes]
y_train = y[train_indexes]

X_test = X[test_indexes]
y_test = y[test_indexes]

可以将两个问题的解决方案封装到一个方法中，seed 表示随机数种子，作用在 np.random 中：

import numpy as np

def train_test_split(X, y, test_ratio=0.2, seed=None):
    if seed:
        np.random.seed(seed)
    shuffle_indexes = np.random.permutation(len(X))

    test_size = int(len(X) * test_ratio)
    test_indexes = shuffle_indexes[:test_size]
    train_indexes = shuffle_indexes[test_size:]

    X_train = X[train_indexes]
    y_train = y[train_indexes]

    X_test = X[test_indexes]
    y_test = y[test_indexes]

    return X_train, X_test, y_train, y_test

Scikit Learn 中封装了 train_test_split() 方法，放在了 model_selection 模块中：

from sklearn.model_selection import train_test_split

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)

算法正确率

通过 train_test_split() 方法对样本数据进行了预处理后，开始训练模型，并且对测试数据进行验证：

from sklearn.neighbors import KNeighborsClassifier

kNN_classifier = KNeighborsClassifier(n_neighbors=6)
kNN_classifier.fit(X_train, y_train)
y_predict = kNN_classifier.predict(X_test)

y_predict 是对测试数据 X_test 的预测结果，其中与 y_test 相等的个数除以 y_test 的个数就是该模型的正确率，将其和 y_test 进行比较可以算出模型的正确率：

def accuracy_score(y_true, y_predict):
    return sum(y_predict == y_true) / len(y_true)

调用该方法，返回一个小于等于1的浮点数：

accuracy_score(y_test, y_predict)

同样在 Scikit Learn 的 metrics 模块中封装了 accuracy_score() 方法：

from sklearn.metrics import accuracy_score

accuracy_score(y_test, y_predict)

Scikit Learn 中的 KNeighborsClassifier 类的父类 ClassifierMixin 中有一个 score() 方法，里面就调用了 accuracy_score() 方法，将测试数据 X_test 和 y_test 作为参数传入该方法中，可以直接计算出算法正确率。

class ClassifierMixin(object):
    def score(self, X, y, sample_weight=None):
        from .metrics import accuracy_score
        return accuracy_score(y, self.predict(X), sample_weight=sample_weight)

超参数

前文中提到的 k 是一种超参数，超参数是在算法运行前需要决定的参数。 Scikit Learn 中 k-近邻算法包含了许多超参数，在初始化构造函数中都有指定：

def __init__(self, n_neighbors=5,
             weights='uniform', algorithm='auto', leaf_size=30,
             p=2, metric='minkowski', metric_params=None, n_jobs=None,
             **kwargs):
    # code here

这些超参数的含义在源代码和官方文档[scikit-learn.org]中都有说明。

算法优缺点

k-近邻算法是一个比较简单的算法，有其优点但也有缺点。

优点是思想简单，但效果强大， 天然的适合多分类问题。

缺点是效率低下，比如一个训练集有 m 个样本，n 个特征，则预测一个新的数据的算法复杂度为 O(m*n)；同时该算法可能产生维数灾难，当维数很大时，两个点之间的距离可能也很大，如 (0,0,0,...,0) 和 (1,1,1,...,1)（10000维）之间的距离为100。

源码地址

Github | ML-Algorithms-Action

Das obige ist der detaillierte Inhalt vonDas Prinzip und die Implementierung des K-Nearest-Neighbor-Algorithmus in Python (Quellcode beigefügt). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!