KNN原理与实现

Posted on

KNN原理

k 近邻算法的输入为实例的特征向量，对应于特征空间的点；输出为实例的类别，可以取多类。k 近邻算法假设给定一个训练数据集，其中的实例类别已定。分类时，对新的实例，根据其 k 个最近邻的训练实例的类别，通过多数表决等方式进行预测。因此，k近邻算法不具有显式的学习过程。

简单来说就是：我们想要知道研究的对象属于什么分类，我们只需要知道距离这个对象最近的K个对象里面，哪一个分类占比最大，那么该对象就属于这个分类。

近朱者赤，近墨者黑

一般地距离计算公式：

实际使用

  • 收集数据：任何方法
  • 准备数据：距离计算所需要的数值，最好是结构化的数据格式
  • 分析数据：任何方法
  • 训练算法：此步骤不适用于 k-近邻算法
  • 测试算法：计算错误率
  • 使用算法：输入样本数据和结构化的输出结果，然后运行 k-近邻算法判断输入数据分类属于哪个分类，最后对计算出的分类执行后续处理

我们尽量把过程可视化，这样方便我们比较直观地区理解，代码使用 Jupyter Notebook 编辑。

step1 引入数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import numpy as np
import matplotlib 
import matplotlib.pyplot as plt
from sklearn import datasets
import seaborn as sns
import pandas as pd
%matplotlib inline 

# 导入数据，从 seaborn 中导入「鸢尾花」数据
dataset = sns.load_dataset('Iris')
# 因为有多组特征，但是这里是举例子，且为了可视化，我们取前两个特征
# DataFrame 获取特定列方法 df[['a','b']]  | df.loc[:,['a',b]]
dataset2 = dataset[['species','sepal_length','sepal_width']] 
sns.relplot(x='sepal_length',y='sepal_width',hue='species',data=dataset2)

输出如下：

图片还是有点复杂，随意取 setosa 和 versicolor

1
2
3
4
dataset3 = dataset.loc[:,['species','sepal_length','sepal_width']] 
# virginica先不看
dataset3 = dataset3[ dataset3['species'] != 'virginica']
sns.relplot(x='sepal_length',y='sepal_width',hue='species',data=dataset3)

输出如下：

step2 划分测试集和训练集

1
2
3
4
5
6
7
8
9
10
11
12
13
# 拆分数据,重新命令一下列名,查看一下测试集和训练集的分布
from sklearn.model_selection import train_test_split
# dataset3先放着吧
dataset4 = dataset3

# 划分测试集和训练集
species_train , species_test  = train_test_split(dataset4['species'],test_size=0.2)

# 这里取个巧，因为数据量小，还是放到一起，比较好画图
dataset4['type'] = dataset4['species']
dataset4['type'][species_test.index] = 'test'

sns.relplot(x='sepal_length',y='sepal_width',hue='type',data=dataset3)

输出如下：

step3 训练数据

knn没有训练这一步

step4 预测数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# KNN其实灭有训练的过程， 计算即可，但是为了符合标准流程，试一试

from sklearn.neighbors import KNeighborsClassifier

data = dataset4 # 复制一份最终的数据

data_train = data[data['type']!='test']
data_test = data[data['type'] == 'test']

# 使用 sklearn knn算法模型进行训练和预测
knn = KNeighborsClassifier(n_neighbors=5)

#length_train = data[data['type'] == 'test']['sepal_length'].values
#width_train = data[data['type'] == 'test']['sepal_width'].values

knn.fit(data_train[['sepal_length','sepal_width']],data_train['species'])
data_test['type'] = knn.predict(data_test[['sepal_length','sepal_width']])  #这里灭有对齐

# 展示一下分类的结果，如下图所示，基本和 dataset3 一致
data_res = pd.concat([data_train,data_test],axis=0)
sns.relplot(x='sepal_length',y='sepal_width',hue='type',data=data_res)

输出如下：

可以看到，预测十分准确（主要是因为数据太干净太好了）

knn 简单实现

根据开头说的原理，我们可以给出一个很简单的实现，理解处理过程即可，细节灭有深究。
主要有三步：

  1. 计算新数据与样本数据集中每条数据的距离。
  2. 对求得的所有距离进行排序（从小到大，越小表示越相似）。
  3. 取前 k （k 一般小于等于 20 ）个样本数据对应的分类标签。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import numpy as np
from collections import Counter

class myKnn:
    
    def __init__(self,neighbor):
        self.neighbor = neighbor
        self.x = None 
        self.y = None
    def fit(self,x,y):
        # knn 并灭有训练过程, 所以简单地对样本赋值即可
        self.x = x
        self.y = y 
    def _predict(self,x):
        '''
        核心步骤，寻找单个对象所属分类
        '''
        # 计算欧式距离,如果点过多，则计算量会很大
        distance = [sqrt(np.sum(i-x)**2)  for i in self.x]
        # 返回排序后的下标
        sorted_distance = np.argsort(distance) 
        # 找到K个邻居
        neighbor_index = sorted_distance[:self.neighbor]
        neighbor_x = self.y[neighbor_index]
        # 找到K个邻居中最大的标识
        return Counter(neighbor_x).most_common(1)[0][0]
    def predict(self,x_predict):
        '''
        多次调用单个对象的分类，即可实现多个样本的分类
        '''
        y_predict = [self._predict(x) for x in x_predict]
        return np.array(y_predict)
    def score(y_predict,y_test):
        right = 0 
        length = len(y_test)
        for i in range(length):
            if y_predict[i] == y_test[i]:
                right += 1 
        return right  
    def show_neighbor(self):
        print(self.neighbor)

数据的归一化问题

假设我们的数据，一个特征是数字极大但另一个特征特别小，那么我们计算的时候，对象间的距离就会被数字大的特征影响，导致结果不准确。所以我们要使用归一化的方法来处理。
max-min 归一化：

$Z$归一化：

knn 调参

k 是最重要的一个参数，一般建议是 k 小于20，鉴于数据量小，我们可以暴力的遍历一下来看看不同 k 值的表现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 参考 In[243] 代码 , 获取测试集和训练集

x_test = data_test[['sepal_length','sepal_width']]
y_test = data_test['species']

x = data[['sepal_length','sepal_width']]
y = data['species']

length = len(y_test)
y_tmp = np.array(y_test)

# 循环十次，找到最佳的K值
for i in range(1,10):
    right = 0 
    # 初始化对象
    knnme = myKnn(neighbor=i)
    knnme.fit(x.values,y.values)
    y_predict = knnme.predict(x_test.values)
    
    # 计算正确率，以此来打分
    for k in range(length):
        if y_predict[k] == y_tmp[k]:
            right += 1 
        
    print(i,right/length)

输出忽略，结论是 k = 3 或者 k = 5 时正确率最高。

当然了一个算法不会如此简单，也还有其他参数，比如说【距离的权重】等等，后面还得细细看

knn 的优缺点

优点：精度高、对异常值不敏感、无数据输入假定
缺点：计算复杂度高、空间复杂度高
适用数据范围：数值型和标称型