一、算法简介
K最近邻(kNN，k-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一。K近邻的意思是每个样本都可以用它最接近的k个邻居来代表。
kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。因此KNN是通过测量不同特征值之间的距离进行分类。
KNN输入基于实例的学习，属于懒惰学习，即它没有显式的学习过程，也就是说没有训练阶段，数据集事先已有了分类和特征值，待收到新样本后直接进行处理.
二、算法实现步骤
1）计算测试数据与各个训练数据之间的距离；
2）按照距离的递增关系进行排序；
3）选取距离最小的K个点；
4）确定前K个点所在类别的出现频率；
5）返回前K个点中出现频率最高的类别作为测试数据的预测分类
三、注意事项
1、K值的选取
K值的选取非常重要。当K的取值过小时，一旦有噪声成分存在将会对预测产生比较大影响；如果K的值取的过大，就相当于用较大邻域中的训练实例进行预测，学习的近似误差会增大。
常用的取k方法是从k=1开始，使用检验集估计分类器的误差率。重复该过程，每次K增值1，允许增加一个近邻。选取产生最小误差率的K。一般k的取值不超过20，上限是n的开方，随着数据集的增大，K的值也要增大。此外，K一般取奇数来减少平局的产生。
2、距离的选取
常用的是欧式距离。两个样本点之间欧式距离的平方是样本点各个维度差的平方和。
四、算法评价
优点
1.简单，易于理解，易于实现，无需估计参数，无需训练；
2. 适合对稀有事件进行分类；
3.特别适合于多分类问题(multi-modal,对象具有多个类别标签)， kNN比SVM的表现要好。
缺点
1.该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。 该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。
2.该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。
3.可理解性差，无法给出像决策树那样的规则。
五、Python实现knn算法
import numpy as np
import matplotlib.pyplot as plt
import operator
#类的封装
class KNN(object):
def __init__(self, k=3):
self.k = k
def fit(self,x,y):
self.x = x
self.y = y
#计算距离的平方
def _square_distance(self,v1,v2):
return np.sum(np.square(v1-v2))
#投票
def _vote(self,ys):
ys_unique = np.unique(ys)
vote_dict = {}
for y in ys:
if y not in vote_dict.keys():
vote_dict[y] = 1
else:
vote_dict[y] += 1
sorted_vote_dict = sorted(vote_dict.items(), key=operator.itemgetter(1),reverse=True)
return sorted_vote_dict[0][0]
#建立模型
def predict(self,x):
y_pred = []
for i in range(len(x)):
dist_arr = [self._square_distance(x[i],self.x[j])for j in range(len(self.x))]
sorted_index = np.argsort(dist_arr)
top_k_index = sorted_index[:self.k]
y_pred.append(self._vote(ys=self.y[top_k_index]))
return np.array(y_pred)
#模型评分
def score(self,y_true=None, y_pred =None):
if y_true is None or y_pred is None:
y_pred = self.predict(self.x)
y_true = self.y
score = 0
for i in range(len(y_true)):
if y_true[i] == y_pred[i]:
score += 1
score /= len(y_true)
return score
#生成数据
np.random.seed(666)
data_size_1 = 300 #生成两组数据，第一组样本点为300
x1_1 = np.random.normal(loc=5, scale=1, size=data_size_1)#样本点的一个维度
x2_1 = np.random.normal(loc=4, scale=1, size=data_size_1)#样本点的另一个维度
y_1 = [0 for i in range(data_size_1)]
data_size_2 = 400 #
x1_2 = np.random.normal(loc=10, scale=2, size=data_size_2)
x2_2 = np.random.normal(loc=8, scale=2, size=data_size_2)
y_2 = [1 for j in range(data_size_2)]
#数据的拼接
x1 = np.concatenate((x1_1, x1_2), axis=0)
x2 = np.concatenate((x2_1, x2_2), axis=0)
x = np.hstack((x1.reshape(-1, 1), x2.reshape(-1, 1)))
y = np.concatenate((y_1, y_2), axis=0)
#数据洗牌
data_size_all = data_size_2+data_size_1
shuffled_index = np.random.permutation(data_size_all)
x = x[shuffled_index]
y = y[shuffled_index]
#切分训练集和测试集
split_index = int(data_size_all * 0.7)
x_train = x[:split_index]
y_train = y[:split_index]
x_test = x[split_index:]
y_test = y[split_index:]
#数据微化
x_train = (x_train - np.min(x_train, axis=0))/(np.max(x_train, axis=0)-np.min(x_train,axis=0))
x_test = (x_test - np.min(x_test, axis=0))/(np.max(x_test, axis=0)-np.min(x_test,axis=0))
#
clf = KNN(k=3)
clf.fit(x_train,y_train)
score_train = clf.score()
print('Train Accuracy: {:.3}'.format(score_train))
y_test_pred = clf.predict(x_test)
print('Test Accuracy:{:.3}'.format(clf.score(y_test,y_test_pred)))
输出结果为:
Train Accuracy: 0.988
Test Accuracy:0.991
#代码实现主要参考自up主:rocktsunami
