一、算法思想和原理

基本思想可以参考这篇文章https://blog.csdn.net/hajk2017/article/details/82862788，来自博主hajk2017
https://blog.csdn.net/qq_41709378/article/details/105386111，来自博主三个半_Z，这篇文章能够迅速理解算法的原理和代码实例计算，里面也牵扯到如何采用交叉验证选择k值
有关KD树的构造可以参考知乎专栏https://zhuanlan.zhihu.com/p/23966698,出处为JoinQuant量化课堂。

二、KNN算法的实现

1.简单实例

  1. import matplotlib.pyplot as plt
  2. import numpy as np
  3. import operator #注意这个库
  5. # 已知分类的数据
  6. x1 = np.array([3,2,1])
  7. y1 = np.array([104,100,81])
  8. x2 = np.array([101,99,98])
  9. y2 = np.array([10,5,2])
  10. scatter1 = plt.scatter(x1,y1,c='r') #（x1,y1）是一类
  11. scatter2 = plt.scatter(x2,y2,c='b') #（x2,y2）是一类
  13. # 未知数据
  14. x = np.array([18])
  15. y = np.array([90])
  16. scatter3 = plt.scatter(x,y,c='k')
  19. #画图例
  20. plt.legend(handles=[scatter1,scatter2,scatter3],labels=['labelA','labelB','X'],loc='best')
  22. plt.show()
  24. # 已知分类的数据
  25. x_data = np.array([[3,104],
  26.                    [2,100],
  27.                    [1,81],
  28.                    [101,10],
  29.                    [99,5],
  30.                    [81,2]]) #红色和蓝色的点一起归于x_data
  31. y_data = np.array(['A','A','A','B','B','B']) #定义标签
  32. x_test = np.array([18,90]) #测试实例
  34. # 计算样本数量
  35. x_data_size = x_data.shape[0] #计算行数
  36. x_data_size
  38. #复制x_test
  39. np.tile(x_test, (x_data_size,1))#后面的参数是复制行和列的次数，第一个是行的次数，第二个是列的次数，这个相当于在行的方向复制6次，目的是要计算这个点和所有点的距离
  40. # 计算x_test与每一个样本的差值
  41. diffMat = np.tile(x_test, (x_data_size,1)) - x_data
  42. diffMat
  43. # 计算差值的平方
  44. sqDiffMat = diffMat**2
  45. sqDiffMat
  46. # 求和
  47. sqDistances = sqDiffMat.sum(axis=1)
  48. sqDistances
  49. # 开方
  50. distances = sqDistances**0.5
  51. distances #得到欧式距离
  52. # 从小到大排序
  53. sortedDistances = distances.argsort() #对索引进行排序
  54. sortedDistances
  56. classCount = {} #建立一个字典
  57. # 设置k
  58. k = 5
  59. for i in range(k): #这里要统计最近k个点的标签多少，便于依照少数服从多数原则进行分类
  60.     # 获取标签
  61.     votelabel = y_data[sortedDistances[i]] 
  62.     # 统计标签数量
  63.     classCount[votelabel] = classCount.get(votelabel,0) + 1 #get函数获取键值，如果获取不到键值，就返回0 [key！这里有点难以理解]
  65. classCount
  67. # 根据operator.itemgetter(1)-第1个值对classCount排序，然后再取倒序
  68. sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1), reverse=True) #数量最多的在最前面
  69. sortedClassCount #得到一个list
  71. # 获取数量最多的标签
  72. knnclass = sortedClassCount[0][0]
  73. knnclass #得到分类类别

2.鸢尾花的应用

  1. # 导入算法包以及数据集
  2. import numpy as np
  3. from sklearn import datasets
  4. from sklearn.model_selection import train_test_split
  5. from sklearn.metrics import classification_report,confusion_matrix
  6. import operator
  7. import random
  9. def knn(x_test, x_data, y_data, k):
  10.     # 计算样本数量
  11.     x_data_size = x_data.shape[0]
  12.     # 复制x_test
  13.     np.tile(x_test, (x_data_size,1))
  14.     # 计算x_test与每一个样本的差值
  15.     diffMat = np.tile(x_test, (x_data_size,1)) - x_data
  16.     # 计算差值的平方
  17.     sqDiffMat = diffMat**2
  18.     # 求和
  19.     sqDistances = sqDiffMat.sum(axis=1)
  20.     # 开方
  21.     distances = sqDistances**0.5 #求解欧氏距离
  22.     # 从小到大排序
  23.     sortedDistances = distances.argsort()
  24.     classCount = {}
  25.     for i in range(k):
  26.         # 获取标签
  27.         votelabel = y_data[sortedDistances[i]]
  28.         # 统计标签数量
  29.         classCount[votelabel] = classCount.get(votelabel,0) + 1
  30.     # 根据operator.itemgetter(1)-第1个值对classCount排序，然后再取倒序
  31.     sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1), reverse=True)
  32.     # 获取数量最多的标签
  33.     return sortedClassCount[0][0]
  35. data_size = iris.data.shape[0] #计算多少个数据（行数）
  37. index = [i for i in range(data_size)] 
  38. random.shuffle(index)  #打乱上面的list
  40. # 载入数据
  41. iris = datasets.load_iris() #sklearn库自带的数据集
  42. # x_train,x_test,y_train,y_test = train_test_split(iris.data, iris.target, test_size=0.2) #分割数据0.2为测试数据，0.8为训练数据，系统自带的切分数据集代码形式
  44. #打乱数据
  45. data_size = iris.data.shape[0] #计算多少个数据（行数）
  46. index = [i for i in range(data_size)] 
  47. random.shuffle(index)  #打乱上面的list
  48. iris.data = iris.data[index]
  49. iris.target = iris.target[index]
  51. #切分数据集(自己实操的方式)
  52. test_size = 40
  53. x_train = iris.data[test_size:] #取剩余部分
  54. x_test =  iris.data[:test_size] #取前40个
  55. y_train = iris.target[test_size:]
  56. y_test = iris.target[:test_size]
  58. predictions = []
  59. for i in range(x_test.shape[0]):
  60.     predictions.append(knn(x_test[i], x_train, y_train, 5))
  62. print(classification_report(y_test, predictions))
  64. print(confusion_matrix(y_test,predictions))

3.sklearn库的使用

  1. # 导入算法包以及数据集
  2. from sklearn import neighbors
  3. from sklearn import datasets
  4. from sklearn.model_selection import train_test_split
  5. from sklearn.metrics import classification_report
  6. import random
  8. # 载入数据
  9. iris = datasets.load_iris()
  10. print(iris)
  12. # 打乱数据切分数据集
  13. # x_train,x_test,y_train,y_test = train_test_split(iris.data, iris.target, test_size=0.2) #分割数据0.2为测试数据，0.8为训练数据
  15. #打乱数据
  16. data_size = iris.data.shape[0]
  17. index = [i for i in range(data_size)] 
  18. random.shuffle(index)  
  19. iris.data = iris.data[index]
  20. iris.target = iris.target[index]
  22. #切分数据集
  23. test_size = 40
  24. x_train = iris.data[test_size:]
  25. x_test =  iris.data[:test_size]
  26. y_train = iris.target[test_size:]
  27. y_test = iris.target[:test_size]
  29. # 构建模型
  30. model = neighbors.KNeighborsClassifier(n_neighbors=3) #直接利用sklearn库进行分类
  31. model.fit(x_train, y_train)
  32. prediction = model.predict(x_test)
  34. print(classification_report(y_test, prediction))