1、KNN要点

超参数的选择（hyperparameters）

  • k值的选择：
    • K的取值尽量要取奇数，以保证在计算结果最后会产生一个较多的类别，如果取偶数可能会产生相等的情况，不利于预测。
    • 常用的方法是从k=1开始，使用检验集估计分类器的误差率。重复该过程，每次K增值1，允许增加一个近邻。选取产生最小误差率的K。
    • 一般k的取值不超过20，上限是n的开方，随着数据集的增大，K的值也要增大。
  • 距离的选择
    • 关于距离的度量方法，常用的有：欧几里得距离、余弦值（cos）, 相关度 （correlation）, 曼哈顿距离 （Manhattan distance）或其他。

方法：

  1. 遍历所有超参数
  2. 将所有数据作为训练集
  3. 将部分数据作为训练集，部分作为测试集
  4. 将部分数据作为训练集，部分作为测试集，部分作为验证集
  5. 技巧：交叉验证（cross-validation）image.png

K-Nearest Neighbor on images never used!

  • KNN应用到图像识别的缺点：慢，距离的度量不准确，维度增加导致数据点指数增加导致计算量的指数增加

2.python实现

numpy实现方法1：

import csv
import random
import math
import operator

# 加载数据集

def loadDataset(filename, split, trainingSet = [], testSet = []):
with open(filename, ‘r’) as csvfile: # with 的作用就是自动调用close（）方法 ！！！
lines = csv.reader(csvfile)
dataset = list(lines)
for x in range(len(dataset)-1):
for y in range(4):
dataset[x][y] = float(dataset[x][y])
if random.random() < split: # 将数据集随机划分
trainingSet.append(dataset[x])
else:
testSet.append(dataset[x])

计算点之间的距离，多维度的
def euclideanDistance(instance1, instance2, length):
distance = 0
for x in range(length):
distance += pow((instance1[x] - instance2[2]), 2)
return math.sqrt(distance)

获取k个邻居
def getNeighbors(trainingSet, testInstance, k):
distances = []
length = len(testInstance) -1
for x in range(len(trainingSet)):
dist = euclideanDistance(testInstance, trainingSet[x], length)
distances.append((trainingSet[x], dist)) # 获取到测试点到其他点的距离
distances.sort(key = operator.itemgetter(1)) #对所有距离进行排序
neighbors = []
for x in range(k): #获取到距离最近的K个点
neighbors.append(distances[x][0])
return neighbors

得到这K个邻居分类最多的那一类
def getResponse(neighbors):
classVotes = {}
for x in range(len(neighbors)):
response = neighbors[x][-1]
if response in classVotes:
classVotes[response] += 1
else:
classVotes[response] = 1
sortedVotes = sorted(classVotes.items(), key = operator.itemgetter(1), reverse=True)
return sortedVotes[0][0]

计算预测准确率
def getAccuracy(testSet, predictions):
correct = 0
for x in range(len(testSet)):
if testSet[x][-1] == predictions[x]:
correct += 1
return (correct/float(len(testSet))) * 100.0

def main():

  1. # prepare data<br />    trainingSet = []<br />    testSet = []<br />    split = 0.67<br />    loadDataset(_r_'irisdata.csv', split, trainingSet, testSet)<br />    print('Trainset:' + repr(len(trainingSet)))<br />    print('Testset:' + repr(len(testSet)))<br />    # generate predictions<br />    predictions = []<br />    k = 3<br />    for x in range(len(testSet)):<br />        neighbors = getNeighbors(trainingSet, testSet[x], k)<br />        result = getResponse(neighbors)<br />        predictions.append(result)<br />        print('predicted=' + repr(result) + ', actual =' + repr(testSet[x][-1]))<br />    print('predictiongs: ' + repr(predictions))<br />    accuracy = getAccuracy(testSet, predictions)<br />    print('Accuracy: ' + repr(accuracy) + '%')<br />    <br />if __name__ == '__main__':<br />    main()

使用sklearn库进行knn分析

from sklearn import neighbors

from sklearn import datasets
import numpy as np
iris = datasets.loadiris()
iris_x = iris.data
iris_y = iris.target
# print(iris_x)
# print(iris_y)
# 可以看到，标签是按0-2顺序排列的，这样的数据集不利于我们使用，所以，我们要对数据集进行随机打乱，然后划分训练集和测试集。
indices = np.random.permutation(len(iris_x))
iris_x_train = iris_x[indices[:-10]]
iris_y_train = iris_y[indices[:-10]]
iris_x_test = iris_x[indices[:-10]]
iris_y_test = iris_y[indices[:-10]]
print(iris_y_train)
# 导入KNeighborsClassifier，构造kNN分类器，传入了参数n_neighbors，就是我们的k值
from sklearn.neighbors import KNeighborsClassifier
knn = KNeighborsClassifier(_n_neighbors=3)
# 对knn进行训练
knn.fit(iris_x_train, iris_y_train)
# 预测
iris_y_predict = knn.predict(iris_x_test)
print(iris_y_predict)
error_index = np.nonzero(iris_y_test - iris_y_predict)[0]
print(error_index)
len(error_index)/len(iris_y_test)