文章目录
  1. 1. KNN算法简介
    1. 1.1. 优点
    2. 1.2. 缺点
    3. 1.3. 经验
    4. 1.4. 应用
  2. 2. KNN算法实现
  3. 3. 参考

近朱者赤,近墨者黑,看一个人经常跟什么人来往,就可以大致推算出这个人的水平。在机器学习领域,有一个采用类似思想实现的算法,那便是KNN(K-Nearest Neighbor),即K近邻算法,其中K是关键参数。该算法比较简单,本文简单介绍如何从零开始实现这个算法,以便加深对算法的理解。

KNN算法简介

KNN算法的主要实现步骤如下:

  • 算距离:对于给定的一条测试数据,计算它与训练集中每个样本的距离(一般采用欧式距离)
  • 找邻居:找到距离这条测试数据最近的K个训练样本
  • 做决策:根据这K个训练样本的标签,投票决定测试数据的预测值。对于分类问题,一般取出现次数多的标签,即少数服从多数;对于回归问题,一般取这K个标签的平均值

优点

  • 简单,易实现
  • 只有一个超参数K,参数调优方便快捷
  • 特别适合多分类问题

缺点

  • 惰性算法,在预测时,需要遍历所有的训练样本,内存开销大,性能差
  • 可解释性差,无法给出明确的预测规则

经验

  • K选择:一般来说K值越大,决策边界越平滑,模型越稳定,但是不代表K越大越好。一般采用交叉验证来确定K值。K的取值范围是[1, 训练样本数的平方根],并且最好是奇数
  • 距离选择:对于文本来说,夹角余弦比欧式距离更合适,其他场景还是用欧式距离
  • 特征工程:涉及到距离计算的算法,在特征工程阶段,最好进行标准化或者归一化

应用

  • 客户流失预测
  • 欺诈侦测
  • 推荐

KNN算法实现

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
import numpy as np
from collections import Counter

from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
from sklearn.neighbors import KNeighborsClassifier

class KNNClassifier(object):
def __init__(self, k=3):
"""
构造方法,只有一个参数k,最小值为1,默认为3。最好是奇数。
k: 邻居数,int型
"""
assert k >= 1, "k must be integer and larger than 0"

self.k = k
self.X = None
self.y = None

def fit(self, X, y):
"""
训练,KNN无训练过程,因此只做赋值。同时要求以下两点:
1、X和y的维度要一致
2、k要小于X的训练样本个数,否则没有意义

X: 训练样本,array型
y: 训练标签,array型
"""
assert X.shape[0] == y.shape[0], "the shape of X and y must be match"
assert self.k <= X.shape[0], "k must be smaller than shape of X"

self.X = X
self.y = y

def _calc_euclidean_distance(self, array1, array2):
"""
计算两个样本array1和array2之间的欧式距离
array1: 第一个样本,array型
array2: 第二个样本,array型
"""
return np.linalg.norm(array1 - array2)

def _vote(self, topk_y):
"""
根据选出的k个标签,进行投票,少数服从多数
topk_y: 选出的k个标签值,array型
"""
return Counter(topk_y).most_common()[0][0]

def predict(self, x):
"""
预测,遍历测试样本,对于每个样本,分别与所有训练样本计算距离,然后选出距离最近的k个标签,进行决策
x: 测试样本,维度要与训练样本X保持一致,array型
"""
assert self.X is not None and self.y is not None , "must training before predict"
assert x.shape[1] == self.X.shape[1]

y_pred = []
for i in range(len(x)):
distances = [self._calc_euclidean_distance(x[i], self.X[j]) for j in range(len(self.X))]
nearest_index = np.argsort(distances)
topk_index = nearest_index[:self.k]
y_pred.append(self._vote(self.y[topk_index]))
return np.array(y_pred)


############## 以上是算法实现过程,下面对算法进行测试,以及与sklearn自带的KNN进行对比 ###############


# 导入iris数据
iris = datasets.load_iris()
X = iris.data
y = iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=888)

# 使用我的算法进行预测,并给出准确率
knn_me = KNNClassifier(3)
knn_me.fit(X_train, y_train)
y_predict_me = knn_me.predict(X_test)
print("The accuracy of my knn is {}.".format(accuracy_score(y_test, y_predict_me)))

# 使用sklearn的算法进行预测,并给出准确率
knn_std = KNeighborsClassifier(n_neighbors=3)
knn_std.fit(X_train, y_train)
y_predict_std = knn_std.predict(X_test)
print("The accuracy of sklearn knn is {}.".format(accuracy_score(y_test, y_predict_std)))

执行上面代码,输出如下,可以看出,精度是一致的。当然,我的算法没有考虑各种异常,以及大数量下的性能优化,切不可应用在生产环境下。

1
2
The accuracy of my knn is 0.9473684210526315.
The accuracy of sklearn knn is 0.9473684210526315.

参考

文章目录
  1. 1. KNN算法简介
    1. 1.1. 优点
    2. 1.2. 缺点
    3. 1.3. 经验
    4. 1.4. 应用
  2. 2. KNN算法实现
  3. 3. 参考