Python에서 K-최근접 이웃 알고리즘의 원리와 구현(소스코드 첨부)

이 글은 파이썬에서 K-최근접 이웃 알고리즘의 원리와 구현을 소개합니다(소스 코드 첨부). 도움이 필요한 친구들이 참고할 수 있기를 바랍니다.

k-최근접 이웃 알고리즘은 서로 다른 특징 값 사이의 거리를 측정하여 분류를 수행합니다.

k-Nearest Neighbor Algorithm 원리

레이블이 있는 학습 샘플 세트의 경우 레이블 없이 새 데이터를 입력한 후 새 데이터의 각 특성을 샘플 세트의 데이터에 해당하는 특성과 비교하여 샘플을 선택합니다. 알고리즘에 따른 데이터 상위 k개의 가장 유사한 데이터를 집중시키고, 가장 유사한 k개의 데이터 중 가장 많이 발생하는 카테고리를 새로운 데이터의 카테고리로 선택합니다.

k-Nearest Neighbor Algorithm Implement

여기서는 하나의 새로운 데이터에 대한 예측만 있고 동시에 여러 개의 새로운 데이터에 대한 예측은 나중에 배치됩니다.

훈련 샘플 세트가 있다고 가정합니다. 점은 표시 0을 나타내고 빨간색 점은 표시 1을 나타냅니다. , 오일러 거리 공식을 사용하여 x에서 X_train의 각 샘플까지의 거리를 계산합니다.

import math

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

두 번째, 거리에 대해 오름차순 연산을 수행하고, np.argsort( ) 메서드를 사용하여 정렬된 인덱스를 반환합니다. 원본 데이터의 순서에 미치는 영향:

import numpy as np

nearest = np.argsort(distances)

셋째, k개의 가장 가까운 샘플에 해당하는 마크를 선택합니다.

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

마지막으로 k에 대해 가장 가까운 샘플에 해당하는 마크가 계산되고 가장 큰 비율로 예측 분류가 이루어집니다. 이 예에서 예측된 분류는 0입니다.

from collections import Counter

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

위 코드를 메소드로 캡슐화합니다:

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]

Scikit Learn

의 k-최근접 이웃 알고리즘은 일반적인 기계 학습 알고리즘 프로세스를 사용하는 것입니다. 머신러닝 알고리즘을 통해 모델을 학습(맞춤)하기 위한 학습 데이터 세트를 만들고, 이 모델을 사용하여 입력 샘플의 결과를 예측합니다.

np.argsort() 方法返回排序后的索引，而不会对原数据的顺序有任何影响：

from sklearn.neighbors import KNeighborsClassifier

kNN_classifier = KNeighborsClassifier(n_neighbors=6)

第三，取 k 个距离最近的样本对应的标记：

kNN_classifier.fit(X_train, y_train)

最后，对这 k 个距离最近的样本对应的标记进行统计，找出占比最多标记即为 x 的预测分类，此例的预测分类为0：

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

将上面的代码封装到一个方法中：

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

Scikit Learn 中的 k-近邻算法

一个典型的机器学习算法流程是将训练数据集通过机器学习算法训练（fit）出模型，通过这个模型来预测输入样例的结果。

对于 k-近邻算法来说，它是一个特殊的没有模型的算法，但是我们将其训练数据集看作是模型。Scikit Learn 中就是怎么处理的。

Scikit Learn 中 k-近邻算法使用

Scikit Learn 中 k-邻近算法在 neighbors 模块中，初始化时传入参数 n_neighbors 为 6，即为上面的 k：

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

fit() 方法根据训练数据集“训练”分类器，该方法会返回分类器本身：

def predict(self, X_predict):
    y_predict = [self._predict(x) for x in X_predict]
    return np.array(y_predict)

def _predict(self, x):
    distances = [math.sqrt(np.sum((x_train - x) ** 2))
                 for x_train in self._X_train]
    nearest = np.argsort(distances)

    topK_y = [self._y_train[i] for i in nearest[:self.k]]
    votes = Counter(topK_y)

    return votes.most_common(1)[0][0]

predict() 方法预测输入的结果，该方法要求传入的参数类型为矩阵。因此，这里先对 x 进行 reshape 操作：

import numpy as np
from sklearn import datasets

iris = datasets.load_iris()
X = iris.data
y = iris.target

y_predict 值为0，与前面实现的 kNN 方法结果一致。

实现 Scikit Learn 中的 KNeighborsClassifier 分类器

定义一个 KNNClassifier 类，其构造器方法传入参数 k，表示预测时选取的最相似数据的个数：

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

X_train = X[test_size:]
y_train = y[test_size:]

X_test = X[:test_size]
y_test = y[:test_size]

fit() 方法训练分类器，并且返回分类器本身：

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])

predict() 方法对待测数据集进行预测，参数 X_predict 类型为矩阵。该方法使用列表解析式对 X_predict 进行了遍历，对每个待测数据调用了一次 _predict()

k-최근접 이웃 알고리즘은 모델이 없는 특수 알고리즘이지만 훈련 데이터 세트를 모델로 간주합니다. 이것이 Scikit Learn에서 처리되는 방식입니다.

Scikit Learn의 k-최근접 이웃 알고리즘은

Scikit Learn의 k-최근접 이웃 알고리즘은 이웃 모듈에 있습니다. 초기화 중에 전달된 매개변수 n_neighbors는 6입니다. 이는 위의 k입니다.

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

fit() 메서드는 훈련 데이터 세트를 기반으로 분류기를 "훈련"합니다. 이 메서드는 분류기 자체를 반환합니다.

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

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

1. predict() 이 메서드는 다음의 결과를 예측합니다. 이 메소드에는 전달된 매개변수 유형이 필요합니다. 는 행렬입니다. 따라서 reshape 작업은 x에서 먼저 수행됩니다.

   X_train = X[train_indexes]
   y_train = y[train_indexes]
   
   X_test = X[test_indexes]
   y_test = y[test_indexes]

   y_predict 값은 0이며 이는 이전에 구현한 kNN 방법의 결과와 일치합니다.

2. Scikit Learn에서 KNeighborsClassifier 분류기를 구현하세요

KNNClassifier 클래스를 정의하면 생성자 메서드가 예측 중에 선택된 가장 유사한 데이터의 수를 나타내는 매개변수 k를 전달합니다.

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

fit() 메소드는 분류기를 훈련하고 분류기 자체를 반환합니다. <p></p> <pre class="brush:php;toolbar:false">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)</pre> <code>predict() 이 메소드는 테스트할 데이터 세트를 예측하며 매개변수 X_predict 유형은 행렬입니다. 이 메서드는 목록 이해를 사용하여 X_predict를 순회하고 테스트할 각 데이터에 대해 _predict() 메서드를 한 번씩 호출합니다.

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)

알고리즘 정확도

🎜모델 문제🎜🎜🎜모델은 훈련 샘플 세트를 통해 훈련되었지만 이 모델의 품질은 아직 알 수 없습니다. 🎜🎜🎜🎜모델이 나쁘면 예측 결과가 우리가 원하는 결과가 아닐 것입니다. 동시에 실제 상황에서는 실제 라벨을 얻고 모델을 테스트하는 것이 어렵습니다. 🎜🎜🎜🎜모델을 훈련할 때 훈련 샘플에 모든 마커가 포함되어 있지 않습니다. 🎜🎜🎜🎜첫 번째 질문의 경우 일반적으로 샘플 세트의 데이터 중 특정 비율(예: 20%)이 테스트 데이터로 사용되고 나머지 데이터는 훈련 데이터로 사용됩니다. 🎜🎜Scikit Learn에서 제공되는 붓꽃 데이터를 예로 들어보겠습니다. 여기에는 150개의 샘플이 포함되어 있습니다. 🎜

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

🎜이제 샘플을 20% 샘플 테스트 데이터와 80% 교육 데이터로 나눕니다. 🎜

accuracy_score(y_test, y_predict)

🎜 X_train 및 y_train을 교육 데이터로 사용하여 모델을 교육하고 X_test 및 y_test를 테스트 데이터로 사용하여 모델 정확도를 확인합니다. 🎜🎜두 번째 질문의 경우 Scikit Learn에서 제공하는 붓꽃 데이터를 예로 들어 보겠습니다. y 표시의 내용은 다음과 같습니다. 🎜

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

위 내용은 Python에서 K-최근접 이웃 알고리즘의 원리와 구현(소스코드 첨부)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!