第八天 实现KNN近邻法

KNN的原理太简单了 我就copy了下别人文章的前两段 原文地址

KNN算法概述

kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

KNN初级算法介绍

最简单最初级的分类器是将全部的训练数据所对应的类别都记录下来，当测试对象的属性和某个训练对象的属性完全匹配时，便可以对其进行分类。但是怎么可能所有测试对象都会找到与之完全匹配的训练对象呢，其次就是存在一个测试对象同时与多个训练对象匹配，导致一个训练对象被分到了多个类的问题，基于这些问题呢，就产生了KNN。

KNN是通过测量不同特征值之间的距离进行分类。它的的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。K通常是不大于20的整数。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

下面通过一个简单的例子说明一下：如下图，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。

实现

这里我使用大名鼎鼎的iris数据进行分类,数据点击链接就可以获得了。对于算法的形式我模仿了下sklearn，当然的比较粗糙简单

前面我们也使用过sklearn，也熟悉了它的一般训练步骤，首先是fit方法，在上一篇文章我们讲过knn是基于实例的学习，没有进行任何参数训练只是保存了实列，那么fit函数就简单了

def fit(self, x, y):
    self.x = x
    self.y = y

其次是predict，这一步要计算测试点和训练集的距离，这里我们使用了numpy，不太熟悉的同学可以稍微了解一下,那么计算单个测试点与测试集各个元素之间的距离可以写成下面形式(这里距离的实现采用了欧式距离),计算距离后进行排序获取前n项的类别，返回计数最高的类别，不懂的同学可以在这个地方一步步调试查看值的变化即可明白

def predict_one(self, test_x):
    distances = np.sum(np.power(self.x - test_x, 2), axis=1) # 计算单个点和测试集各个点的距离
    sorted_distances = distances.argsort()
    top_n = sorted_distances[:self.n_neibor] # 获取距离最近前n项
    temp = np.array([self.y[ix] for ix in top_n]) # 获取前n项中的众数
    return np.bincount(temp).argmax()

另外我试着写了下分类的准确率，就是分类正确的数目/测试数据的长度%

def score(self, test_xs, test_ys):
        leng = len(test_xs)
        same = 0
        predict = self.predict(test_xs)
        for ele in zip(predict, test_ys):
            if ele[0] == ele[1]:
                same += 1
        return "%.2f" % (same/leng)

整体的代码如下:

import numpy as np

class Knn(object):
    def __init__(self, n_neibor=3):
        self.data = []
        self.n_neibor = n_neibor

    def fit(self, x, y):
        self.x = x
        self.y = y

    def predict(self, test_xs):
        rst = []
        for ele in test_xs:
            tmp = self.predict_one(ele)
            rst.append(tmp)
        return rst

    def predict_one(self, test_x):
        distances = np.sum(np.power(self.x - test_x, 2), axis=1)
        sorted_distances = distances.argsort()
        top_n = sorted_distances[:self.n_neibor]
        temp = np.array([self.y[ix] for ix in top_n])
        return np.bincount(temp).argmax()

    def score(self, test_xs, test_ys):
        leng = len(test_xs)
        same = 0
        predict = self.predict(test_xs)
        for ele in zip(predict, test_ys):
            if ele[0] == ele[1]:
                same += 1
        return "%.2f" % (same/leng)


import pandas as pd
from sklearn.preprocessing import LabelEncoder
from sklearn.model_selection import train_test_split
def main():
    data = pd.read_csv('dataset/iris.data', header=-1)
    x = data.values[:, :-1]
    y = data.values[:, -1:]
    y = LabelEncoder().fit_transform(y)
    train_x, test_x, train_y, test_y = train_test_split(x, y)
    knn = Knn(n_neibor=1)
    knn.fit(train_x, train_y)
    print(knn.score(test_x, test_y))
    #y_pre = knn.predict(test_x)
    #print(np.sqrt(np.sum(np.power(test_y-y_pre, 2)))) # 方差


if __name__ == '__main__':
    main()

我numpy不是太熟，predict的时候应该有办法可以直接计算测试集和训练集的距离,我这里采用了比较low的循环写法

sklearn实现

sklearn自带了knn实现,实现如下

from sklearn.neighbors import KNeighborsClassifier
clf = KNeighborsClassifier()
clf.fit(train_x, train_y)
clf.score(test_x,test_y)