KNN算法简介

前言

KNN算法，也就是“K-近邻算法”，这个算法相对简单，并不需要任何数学运算的推导，所以作为机器学习的入门算法，是再好不过的了。

KNN算法的思想及其原理。

kNN(k-NearestNeighbor)，也就是k最近邻算法。顾名思义，所谓K最近邻，就是k个最近的邻居的意思。也就是在数据集中，认为每个样本可以用离他最距离近的k个邻居来代表。

knn.png

这不也就是近朱者赤近墨者黑，从百度百科上的这张图我们可以看到，如果我们想知道点Xu是什么颜色，我们就取5个离它最近的点，然后看这5个点中哪一种颜色的点最多，我们就认为Xu点的颜色属于这其中最多的那个颜色。图中最近的5个点中红色占的比例最多，所以我们判断Xu属于红色区域。

KNN算法思想

理解了KNN原理之后，在算法的角度上去实现，我们需要下面的流程：
1、计算测试对象到训练集中每个对象的距离（这里我们一般使用欧式距离来计算）

欧式距离公式.jpg

2、对这些距离数据进行排序，选取与当前测试对象最近的k个训练对象，作为该测试对象的邻居
3、统计这k个邻居中的类别频数，其中频数最高的类别，即为测试对象的类别。

KNN算法python代码实现

这里我们使用的是Anaconda的Jupyter Notebook
使用一组肿瘤的大小和时间的数据对应标签是良性和恶性的例子。

import numpy as np
import matplotlib.pyplot as plt
from matplotlib import font_manager
#选取电脑中的字体格式作为之后可视化输出时的文字的中文格式
my_font=font_manager.FontProperties(fname=r"C:\Windows\Fonts\STKAITI.TTF")
# raw_data_x是特征，第一列是肿瘤大小，第二列是肿瘤时间；raw_data_y是标签，0为良性，1为恶性
raw_data_X = [[3.393533211, 2.331273381],
              [3.110073483, 1.781539638],
              [1.343853454, 3.368312451],
              [3.582294121, 4.679917921],
              [2.280362211, 2.866990212],
              [7.423436752, 4.685324231],
              [5.745231231, 3.532131321],
              [9.172112222, 2.511113104],
              [7.927841231, 3.421455345],
              [7.939831414, 0.791631213]
             ]
raw_data_y = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
x=[8.90933607318, 3.365731514]#待测试的肿瘤数据
# 设置训练组
X_train = np.array(raw_data_X)
y_train = np.array(raw_data_y)
print(X_train[y_train==1,0])
# 将数据可视化
#其中X_train[y_train==0,0]代表的意思是肿瘤类别标志为0的第一列的数据，即训练集中良性肿瘤的大小的数据。
plt.scatter(X_train[y_train==0,0],X_train[y_train==0,1], color='g', label = '良性')
plt.scatter(X_train[y_train==1,0],X_train[y_train==1,1], color='r', label = '恶性')
plt.scatter(x[0],x[1],color='black',label = '待测试')
plt.xlabel('Tumor Size')
plt.ylabel('Time')
plt.legend(['良性','恶性','待测试'],loc='best',prop=my_font)
plt.axis([0,10,0,5])
plt.show()

from math import sqrt
distances=[]
#用来记录x到样本数据集中的每个点的距离
for x_train in X_train:
    d = sqrt(np.sum((x_train-x)**2))
    distances.append(d)
distances
#使用argsort()排序的方法，返回的时对应的数组中的索引，这样我们就可以知道对应索引在y_train 中的标签类型了
nearest = np.argsort(distances)
print('nearest==',end='')
print(nearest)
#找出对应k=6个最近的点，得出他们得类型标签
k = 6
topK_y = [y_train[i] for i in nearest[:k]]
print('topK_y==',end='')
print(topK_y)
#Counter()函数可以输出对应标签得频数
from collections import Counter
votes = Counter(topK_y)
print('votes==' ,end='')
print(votes)
#  取出频数最多的一组，并获取其标签值
predict_y = votes.most_common(1)[0][0]
print('预测结果==',end='')
print(predict_y)

输出结果：

image.png

nearest==[7 8 5 9 6 3 0 1 4 2]
topK_y==[1, 1, 1, 1, 1, 0]
votes==Counter({1: 5, 0: 1})
预测结果==1

封装我们手写的KNN算法

我们可以将KNN算法分装到类中，以后使用的时候直接调用即可。
我是在jupyter notebook 打开的文件夹里创建一个myKnn的文件夹，然后新建一个KNN.py文件，在里面键入下面的内容：

import numpy as np
from math import sqrt
from collections import Counter
class kNNClassifier:
    def __init__(self, k):
        """初始化分类器"""
        assert k >= 1, "k must be valid"
        self.k = k
        self._X_train = None
        self._y_train = None

    def fit(self, X_train, y_train):
        """根据训练数据集X_train和y_train训练kNN分类器"""
        assert X_train.shape[0] == y_train.shape[0],             "the size of X_train must be equal to the size of y_train"
        assert self.k <= X_train.shape[0],             "the size of X_train must be at least k"
        self._X_train = X_train
        self._y_train = y_train
        return self    
    def predict(self,X_predict):
        """给定待预测数据集X_predict，返回表示X_predict结果的向量"""
        assert self._X_train is not None and self._y_train is not None,             "must fit before predict!"
        assert X_predict.shape[1] == self._X_train.shape[1],            "the feature number of X_predict must be equal to X_train"
        y_predict = [self._predict(x) for x in X_predict]
        
        return np.array(y_predict)    
    def _predict(self, x):
        
        distances = [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]]
        #print(topK_y)
        votes = Counter(topK_y)        
        return votes.most_common(1)[0][0]    
    def __repr__(self):
        return "kNN(k=%d)" % self.k

实现调用


import numpy as np
import matplotlib.pyplot as plt
from matplotlib import font_manager
my_font=font_manager.FontProperties(fname=r"C:\Windows\Fonts\STKAITI.TTF")
# raw_data_x是特征，raw_data_y是标签，0为良性，1为恶性
raw_data_X = [[3.393533211, 2.331273381],
              [3.110073483, 1.781539638],
              [1.343853454, 3.368312451],
              [3.582294121, 4.679917921],
              [2.280362211, 2.866990212],
              [7.423436752, 4.685324231],
              [5.745231231, 3.532131321],
              [9.172112222, 2.511113104],
              [7.927841231, 3.421455345],
              [7.939831414, 0.791631213]
             ]
raw_data_y = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
# 设置训练组
X_train = np.array(raw_data_X)
y_train = np.array(raw_data_y)

x=[8.90933607318, 3.365731514]
# 将数据可视化
plt.scatter(X_train[y_train==0,0],X_train[y_train==0,1], color='g', label = '良性')
plt.scatter(X_train[y_train==1,0],X_train[y_train==1,1], color='r', label = '恶性')
plt.scatter(x[0],x[1],color='black')
plt.xlabel('Tumor Size')
plt.ylabel('Time')
plt.legend(['良性','恶性'],loc='best',prop=my_font)
plt.axis([0,10,0,5])
plt.show()
x_pre=np.array(x)
%run myKnn/kNN.py
#from myKnn.kNN import kNNClassifier
knn_clf = kNNClassifier(k=6)
knn_clf.fit(X_train, y_train)
X_predict = x_pre.reshape(1,-1)
y_predict = knn_clf.predict(X_predict)
y_predict

输出的结果：