K近邻 | python实现 | weixin

01 KNN可以做点什么呢？

在李航的《统计学习方法》中，详细讲解了一中分类算法：K近邻(K Nearest Neighbor)，具体的算法过程和关键点可以参考这篇文章：

算法的理论基础有了，下一步就是自己动手去实现了。

今天我们的文章就是利用python去实现KNN算法，利用这套算法可以做什么呢？

本文利用以下两种方式在python中实现KNN算法：

直接调用python的sklearn包中的knn算法
自定义函数实现KNN算法

02 sklearn包实现

python自带的sklearn包是一个非常强大的机器学习包，其中包含了knn算法，主要包含以下几个函数。

1. 引入sklearn包中的knn类

from sklearn.neighbors import KNeighborsClassifier

2. 取得knn分类器，并使用内置参数调整KNN三要素

knn=KNeighborsClassifier(weights="distance",n_neighbors=10)

这里说明一下此分类器各参数的意义(先了解KNN算法原理，再看参数更容易理解)

3. 使用knn.fit()对训练集进行训练

knn.fit()，训练函数，它是最主要的函数。接收参数只有1个，就是训练数据集，每一行是一个样本，每一列是一个属性。它返回对象本身，即只是修改对象内部属性，因此直接调用就可以了，后面用该对象的预测函数取预测自然及用到了这个训练的结果。

knn.fit(iris_x_train,iris_y_train)

4. 调用knn.predict()预测新输入的类别

knn.predict()，预测函数接收输入的数组类型测试样本，一般是二维数组，每一行是一个样本，每一列是一个属性。返回数组类型的预测结果。

iris_y_predict=knn.predict(iris_x_test)

5. 调用knn.predict_proba()，显示每个测试集样本对应各个分类结果的概率

knn.predict_proba()，基于概率的软判决，也是预测函数，只是并不是给出某一个样本的输出是哪一个值，而是给出该输出是各种可能值的概率各是多少。

knn.predict_proba(iris_x_test)

6. 调用knn.score()计算预测的准确率

knn.score(),计算准确率的函数，接受参数有3个。输出为一个float型数，表示准确率。内部计算是按照predict()函数计算的结果记性计算的。

接收的3个参数：

X: 接收输入的数组类型测试样本，一般是二维数组，每一行是一个样本，每一列是一个属性。
y: X这些预测样本的真实标签，一维数组或者二维数组。
sample_weight=None：是一个和X一样长的数组，表示各样本对准确率影响的权重，一般默认为None.

score=knn.score(iris_x_test,iris_y_test,sample_weight=None)

完成！

利用sklearn实现KNN算法，训练集为130个鸢尾花的训练集，包含了鸢尾花的花瓣花萼长宽以及对应的品种，输入为20个鸢尾花的花瓣花萼长宽，输出为这20个鸢尾花的品种预测，运行结果如下

iris_y_predict=
['Iris-setosa' 'Iris-setosa' 'Iris-setosa' 'Iris-versicolor'
 'Iris-versicolor' 'Iris-setosa' 'Iris-virginica' 'Iris-virginica'
 'Iris-versicolor' 'Iris-virginica' 'Iris-setosa' 'Iris-virginica'
 'Iris-versicolor' 'Iris-virginica' 'Iris-setosa' 'Iris-virginica'
 'Iris-versicolor' 'Iris-virginica' 'Iris-versicolor' 'Iris-setosa']

iris_y_test=
['Iris-setosa' 'Iris-setosa' 'Iris-setosa' 'Iris-versicolor'
 'Iris-versicolor' 'Iris-setosa' 'Iris-virginica' 'Iris-virginica'
 'Iris-versicolor' 'Iris-virginica' 'Iris-setosa' 'Iris-virginica'
 'Iris-versicolor' 'Iris-versicolor' 'Iris-setosa' 'Iris-virginica'
 'Iris-versicolor' 'Iris-virginica' 'Iris-versicolor' 'Iris-setosa']

accuracy is= 95.0 %

预测结果准确率为95%

完整代码我放在了github上，欢迎交流
KNN的sklearn实现

03 自定义函数实现

下面我们升级难度，甩开别人喂到你面前的饭菜，自己动手写一个KNN分类器。

在此之前，你需要非常了解KNN算法原理。

本KNN分类器原理如下：

计算输入x与训练集各点的距离distance（这里numpy数组的元素级计算高效率凸显！）
按distance排序，取distance最近的k个点（k为分类器参数）
对k个点的类别归类计数，x归为多数类（多数表决）
或者对k个点的类别按1/distance权重归类计数，x归为计数大的类（加权表决）

基于上面的算法原理，下面直接给出我写的KNN分类器代码，此分类器特征如下：

可以选择分类决策规则（多数表决/距离加权表决）
可以选择近邻数k
使用欧氏距离度量
一次只能对一个新输入分类，这是此分类器的弊病，后续改进算法提升点（加入for循环即可）
没有设定训练集数据存储方式选择的参数，只能线性扫描（即，没有设置kd树存储），因此难以处理大数据量的训练集

自定义KNN分类器

# newInput: 新输入的待分类数据(x_test)，本分类器一次只能对一个新输入分类
# dataset：输入的训练数据集(x_train),array类型，每一行为一个输入训练集
# labels：输入训练集对应的类别标签(y_train)，格式为['A','B']而不是[['A'],['B']]
# k：近邻数
# weight：决策规则，"uniform" 多数表决法，"distance" 距离加权表决法

def KNNClassify(newInput, dataset, labels, k, weight):
    numSamples=dataset.shape[0]

    """step1: 计算待分类数据与训练集各数据点的距离（欧氏距离：距离差值平方和开根号）"""
    diff=np.tile(newInput,(numSamples,1)) - dataset # 凸显numpy数组的高效性——元素级的运算
    squaredist=diff**2
    distance = (squaredist.sum(axis=1))**0.5 # axis=1,按行累加

    """step2：将距离按升序排序，并取距离最近的k个近邻点"""
    # 对数组distance按升序排序，返回数组排序后的值对应的索引值
    sortedDistance=distance.argsort()

    # 定义一个空字典，存放k个近邻点的分类计数
    classCount={}

    # 对k个近邻点分类计数，多数表决法
    for i in range(k):
        # 第i个近邻点在distance数组中的索引,对应的分类
        votelabel=labels[sortedDistance[i]]
        if weight=="uniform":
            # votelabel作为字典的key，对相同的key值累加（多数表决法）
            classCount[votelabel]=classCount.get(votelabel,0)+1
        elif weight=="distance":
            # 对相同的key值按距离加权累加（加权表决法）
            classCount[votelabel]=classCount.get(votelabel,0)+(1/distance[sortedDistance[i]])
        else:
            print ("分类决策规则错误！")
            print ("\"uniform\"多数表决法\"distance\"距离加权表决法")
            break

    # 对k个近邻点的分类计数按降序排序，返回得票数最多的分类结果
    sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    if weight=="uniform":
        print ("新输入到训练集的最近%d个点的计数为："%k,"\n",classCount)
        print ("新输入的类别是:", sortedClassCount[0][0])

    elif weight=="distance":
        print ("新输入到训练集的最近%d个点的距离加权计数为："%k,"\n",classCount)
        print ("新输入的类别是:", sortedClassCount[0][0])

    return sortedClassCount[0][0]

下面对自定义的KNN分类器进行测试，还是使用鸢尾花数据集.

1. 建立训练集、测试集

iris=pd.read_csv("E:\python\practice\iris.txt")
iris.head()

iris_x=iris.iloc[:,[0,1,2,3]]
iris_y=iris.iloc[:,[4]]

np.random.seed(7)
indices=np.random.permutation(len(iris_x))

iris_x_train=iris_x.iloc[indices[0:130]]
iris_y_train=iris_y.iloc[indices[0:130]]

iris_x_test=iris_x.iloc[indices[130:150]]
iris_y_test=iris_y.iloc[indices[130:150]]

# 将dataframe格式的数据转换为numpy array格式，便于 调用函数计算
iris_x_train=np.array(iris_x_train)
iris_y_train=np.array(iris_y_train)

iris_x_test=np.array(iris_x_test)
iris_y_test=np.array(iris_y_test)

# 将labels的形状设置为(130,)
iris_y_train.shape=(130,)

2. 将训练集、测试集带入自定义KNN分类器进行分类

test_index=12
predict=KNNClassify(iris_x_test[test_index],iris_x_train,iris_y_train,20,"distance")
print (predict)
print ("新输入的实际类别是：", iris_y_test[test_index])
print ("\n")

if predict==iris_y_test[test_index]:
    print ("预测准确!")
else:
    print ("预测错误！")

随意选择一个测试数据，预测结果如下

新输入到训练集的最近20个点的距离加权计数为：
 {'Iris-versicolor': 45.596003202769246}
新输入的类别是: Iris-versicolor
Iris-versicolor
新输入的实际类别是： ['Iris-versicolor']

预测准确!

完整代码我放在了github上，欢迎交流
KNN的自定义函数实现

04 预告

本文结合KNN算法原理，利用python实现了KNN，使用了两种方式：

sklearn包实现
自定义KNN分类器

下期将利用python实现朴素贝叶斯算法，敬请期待~

weixin_33812433