KNN(k-nearest neighbor的缩写)最近邻算法

KNN可以看成：有一些已知标签的数据，当有新数据进入时，计算该数据与已知数据最近的k个点的距离，从而推测出这个数据时什么类型

常用算法

• 欧拉算法

  计算两个点每个维度差平方，最后求平方根

  image

  多维度情况下

  image

  可以表示为，X右下标表示维度

  image

  进而

  image

• 曼哈顿算法

  image

• 明可夫斯基算法

  image

  通过 曼哈顿和欧拉算法推倒而来，上面为曼哈顿，下面为欧拉

  image

  进而

  image

  最终推导出最底部的明可夫斯基

  image

代码实现

#这里使用欧拉算法来实现
import numpy as np
from math import sqrt
from collections import Counter#用来统计数组中元素出现次数的类库

#k为要计算的点的个数，X_train为训练数据，y_train为训练标签，x为要预测的数据
def kNN_classify(k, X_train, y_train, x):

    assert 1 <= k <= X_train.shape[0], "k must be valid"
    assert X_train.shape[0] == y_train.shape[0], \
        "the size of X_train must equal to the size of y_train"
    assert X_train.shape[1] == x.shape[0], \
        "the feature number of x must be equal to X_train"

    #关键代码，将计算出的差值存放到distances
    distances = [sqrt(np.sum((x_train - x)**2)) for x_train in X_train]
    #对distances进行索引排序
    nearest = np.argsort(distances)
    #获取差距最小的k个元素的标签
    topK_y = [y_train[i] for i in nearest[:k]]
    #计算结果各元素出现的次数
    votes = Counter(topK_y)
    #取出出现元素次数最多的标签
    return votes.most_common(1)[0][0]

使用scikit-learn 中的 kNN

#导包
from sklearn.neighbors import KNeighborsClassifier

#创建scikit-learn的knn分类器，k值为6
kNN_classifier = KNeighborsClassifier(n_neighbors=6)
#训练
kNN_classifier.fit(X_train, y_train)
#转换维度，变为n*2的矩阵，2为维度，n为要预测数据的个数
X_predict = x.reshape(-1, 2)

#预测，返回值为预测结果数组
y_predict = kNN_classifier.predict(X_predict)
#获取预测值
y_predict[0]

案例鸢尾花识别

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets 
#获取鸢尾花数据
iris = datasets.load_iris()
#iris.keys()#查看数据格式

#获取X的数据
X = iris.data
#获取标签
y = iris.target

#以下是分割数据代码

#打乱数据，得到打乱后的索引
shuffled_indexes = np.random.permutation(len(X))
#划分数据，百分之20的是测试数据
test_ratio = 0.2
#获取测试数据大小
test_size = int(len(X) * test_ratio)
#获取测试数据索引
test_indexes = shuffled_indexes[:test_size]
#获取训练数据索引
train_indexes = shuffled_indexes[test_size:]
#获取所有的训练数据
X_train = X[train_indexes]
#获取所有的训练标签
y_train = y[train_indexes]
#获取所有的测试数据
X_test = X[test_indexes]
#获取所有的测试数据
y_test = y[test_indexes]

#分割数据结束

#以下使用sklearn的分割方法
#导报
from sklearn.model_selection import train_test_split

#test_size分割大小，random_state随机值不置则每次随机
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=666)

#使用数据
#导包
from sklearn.neighbors import KNeighborsClassifier

#创建scikit-learn的knn分类器，k值为6
kNN_classifier = KNeighborsClassifier(n_neighbors=6)
#训练
kNN_classifier.fit(X_train, y_train)
#转换维度，变为n*4的矩阵，4为维度，n为要预测数据的个数
X_predict = x.reshape(-1, 2)

#预测，返回值为预测结果数组
y_predict = kNN_classifier.predict(X_test)
#简单对预测进行评分 
sum(y_predict == y_test) / len(y_test)

案例2手写数字识别

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets

#导入手写数字库
digits = datasets.load_digits()
X = digits.data
y = digits.target


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, random_state=666)

from sklearn.neighbors import KNeighborsClassifier

#创建k为3的模型
knn_clf = KNeighborsClassifier(n_neighbors=3)
#拟合
knn_clf.fit(X_train, y_train)
#预测
y_predict = knn_clf.predict(X_test)
#导入评分包
from sklearn.metrics import accuracy_score
#使用评分包的评分
accuracy_score(y_test, y_predict)
#使用knn自带评分
knn_clf.score(X_test, y_test)