python中K-近鄰演算法的原理與實作（附源碼）

這篇文章帶給大家的內容是關於python中K-近鄰演算法的原理與實作（附原始碼），有一定的參考價值，有需要的朋友可以參考一下，希望對你有幫助。

k-近鄰演算法透過測量不同特徵值之間的距離方法進行分類。

k-近鄰演算法原理

對於一個存在標籤的訓練樣本集，輸入沒有標籤的新資料後，將新資料的每個特徵與樣本集中將資料對應的特徵進行比較，根據演算法選擇樣本資料集中前k個最相似的數據，選擇k個最相似資料中出現次數最多的分類，作為新資料的分類。

k-近鄰演算法實作

這裡只是單一新資料的預測，對同時多個新資料的預測放在後文中。

假定有訓練樣本集X_train（X_train.shape=(10, 2)），對應的標記y_train（y_train.shape=(10,)，包含0、1)，使用matplotlib.pyplot 作圖表示如下（綠色的點表示標記0，紅色的點表示標記1）：

現有一個新的資料：x（x = np.array([3.18557125, 6.03119673])），作圖表示如下（藍色的點）：

#首先，使用歐拉距離公式計算x 到X_train 中每個樣本的距離：

import math

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

第二，對distances 進行升序操作，使用np.argsort() 方法傳回排序後的索引，而不會對原始資料的順序有任何影響：

import numpy as np

nearest = np.argsort(distances)

第三，取k 個距離最近的樣本對應的標記：

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

最後，對這k 個距離最近的樣本對應的標記進行統計，找出佔比最多標記即為x 的預測分類，此例的預測分類為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-近鄰演算法

一個典型的機器學習演算法流程是將訓練資料集透過機器學習演算法訓練（fit）出模型，透過這個模型來預測輸入樣例的結果。

對於k-近鄰演算法來說，它是一個特殊的沒有模型的演算法，但是我們將其訓練資料集看作是模型。 Scikit Learn 中就是怎麼處理的。

Scikit Learn 中k-近鄰演算法使用

Scikit Learn 中k-鄰近演算法在neighbors 模組中，初始化時傳入參數n_neighbors 為6，即為上方的k：

from sklearn.neighbors import KNeighborsClassifier

kNN_classifier = KNeighborsClassifier(n_neighbors=6)

fit() 方法根據訓練資料集「訓練」分類器，該方法會傳回分類器本身：

kNN_classifier.fit(X_train, y_train)

predict( ) 方法預測輸入的結果，此方法要求傳入的參數類型為矩陣。因此，這裡先對 x 進行 reshape 操作：

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

y_predict 值為0，與前面實作的 kNN 方法結果一致。

實作Scikit Learn 中的KNeighborsClassifier 分類器

定義一個KNNClassifier 類，其構造器方法傳入參數k，表示預測時選取的最相似資料的個數字：

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

fit() 方法訓練分類器，並且傳回分類器本身：

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

predict() 方法處理資料集進行預測，參數X_predict 類型為矩陣。此方法使用列表解析式對 X_predict 進行了遍歷，對每個待測資料呼叫了一次 _predict() 方法。

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]

演算法準確性

模型存在的問題

上面透過訓練樣本集訓練出了模型，但是並不知道這個模型的好壞，還有兩個問題。

1. 如果模型很壞，預測的結果就不是我們想要的。同時實際情況中，很難拿到真實的標記（label），無法檢驗模型。

2. 訓練模型時訓練樣本並沒有包含所有的標記。

對於第一個問題，通常將樣本集中一定比例（如20%）的數據作為測試數據，其餘數據作為訓練數據。

以 Scikit Learn 中提供的鳶尾花資料為例，其包含了150個樣本。

import numpy as np
from sklearn import datasets

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

現在將樣本分為20%範例測試資料和80%比例訓練資料：

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]

將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中文網其他相關文章！