1.KNN原理：
存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一个数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中最相似数据（最近邻）的分类标签。一般来说，只选择样本数据集中前 $k$ 个最相似的数据，这就是KNN算法 $k$ 的出处, 通常 $k$ 是不大于20的整数。最后，选择 $k$ 个最相似数据中出现次数最多的分类，作为新数据的分类。
2.实验准备：
- Python
- scikit-learn（一个基于python的机器学习库）
3.实验代码：
代码有两个版本，一个是自己编写的简单的KNN算法实现，一个是基于scikit-learn库中KNN算法实现的，数据均采用scikit-learn中的手写体数据集。
版本1（自己编写）：
# -*- coding: utf-8 -*-
"""
This script is an exercise on KNN.
Created on Tue Nov 03 21:21:39 2015
@author: 90Zeng
"""
import numpy as np
from sklearn import datasets
import operator
#-----------------function classify--------------------------------------
def classify0(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[ 0 ]
# 计算输入的向量inX与所有样本的距离
diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
sqDiffMat = diffMat ** 2
sqDistances = sqDiffMat.sum(axis = 1)
distances = sqDistances ** 0.5
# 对距离大小进行排序
sortedDistIndices = distances.argsort()
classCount = {}
# 选择距离最小的 K 个点
for i in range(k):
voteLabel = labels[ sortedDistIndices[i] ]
classCount[ voteLabel ] = classCount.get(voteLabel, 0) + 1
# 按照类别的数量多少进行排序
sortedClassCount = sorted(classCount.iteritems(),
key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0] # 返回类别数最多的类别名称
#-------------------end of function classify--------------------------------
def handwritingClassTest():
# 导入数据
digits = datasets.load_digits()
totalNum = len(digits.data)
# 选出90%样本作为训练样本，其余10%测试
trainNum = int(0.8 * totalNum)
trainX = digits.data[0 : trainNum]
trainY = digits.target[0 : trainNum]
testX = digits.data[trainNum:]
testY = digits.target[trainNum:]
errorCount = 0
testExampleNum = len( testX )
for i in range( testExampleNum ):
# 测试样本在测试集中真实的类别
trueLabel = testY[i]
classifierResult = classify0( testX[ i, : ], trainX, trainY, 5 )
print "
The classifier came back with: %d, the real answer is: %d"
% ( classifierResult, trueLabel )
if trueLabel != classifierResult:
errorCount += 1
else:
pass
print "
The total number of errors is: %d" % errorCount
print "
the total error rate is: %f" % (
errorCount / float( testExampleNum)
)
if __name__ == '__main__':
print "start..."
handwritingClassTest()
运行结果：
版本2（使用库函数）：
# -*- coding: utf-8 -*-
"""
This script is an exercise on KNN.
Created on Tue Nov 06 21:26:39 2015
@author: ZengJiulin
"""
print(__doc__)
import numpy as np
from sklearn import neighbors, datasets
digits = datasets.load_digits()
totalNum = len(digits.data)
# 选出90%样本作为训练样本，其余10%测试
trainNum = int(0.8 * totalNum)
trainX = digits.data[0 : trainNum]
trainY = digits.target[0 : trainNum]
testX = digits.data[trainNum:]
testY = digits.target[trainNum:]
n_neighbors = 10
clf = neighbors.KNeighborsClassifier(n_neighbors, weights='uniform')
clf.fit(trainX, trainY)
Z = clf.predict(testX)
print "
the total error rate is: %f" % ( 1 - np.sum(Z==testY) / float(len(testX)) )
运行结果：
4.总结
KNN的优点：精度高、对异常值不敏感，无数据输入假定
缺点：计算复杂度高（要计算待分类样本与所有已知类别样本的距离），空间复杂度高（存储所有样本点和目标样本的距离）