k-近邻算法（kNN）采用测量不同特征值之间的距离方法进行分类。
优点：精度高、对异常值不敏感、无数据输入假定
缺点：计算复杂度高、空间复杂度高
使用数据范围：数值型和标称型
工作原理：存在一个样本数据集合，也称为训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中的k的出处，通常k是不大于20的整数。然后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。
kNN.py
# coding:utf-8
# !/usr/bin/env python '''
Created on Sep 16, 2010
kNN: k Nearest Neighbors Input: inX: vector to compare to existing dataset (1xN)
dataSet: size m data set of known vectors (NxM)
labels: data set labels (1xM vector)
k: number of neighbors to use for comparison (should be an odd number) Output: the most popular class label @author: pbharrin
''' from numpy import *
import operator
from os import listdir def classify0(inX, dataSet, labels, k): #inX是用于分类的输入向量，dataSet是输入的训练样本集，labels是标签向量，k是选择最近邻居的数目
dataSetSize = dataSet.shape[0] #shape函数求数组array的大小，例如dataSet一个4行2列的数组
#距离计算
diffMat = tile(inX, (dataSetSize,1)) - dataSet #tile函数的功能是重复某个数组，例如把[0,0]重复4行1列，并和dataSet相减
sqDiffMat = diffMat**2 #对数组中和横纵坐标平方
#print(sqDiffMat)
sqDistances = sqDiffMat.sum(axis=1) #把数组中的每一行向量相加，即求a^2+b^2
#print(sqDistances)
distances = sqDistances**0.5 #开根号，√a^2+b^2
#print(distances)
#a = array([1.4, 1.5,1.6,1.2])
sortedDistIndicies = distances.argsort() #按升序排序，从小到大的下标依次是2,3,1,0
#print(sortedDistIndicies)
classCount={} #字典 #选择距离最小的k个点
for i in range(k):
voteIlabel = labels[sortedDistIndicies[i]] #按下标取得标记
#print(voteIlabel)
classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 #在字典中计数
#print(classCount[voteIlabel])
#排序
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
#print(sortedClassCount)
return sortedClassCount[0][0] #返回计数最多的标记 def createDataSet():
group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
labels = ['A','A','B','B']
return group, labels def file2matrix(filename): #处理格式问题，输入为文件名字符串，输出为训练样本矩阵和类标签向量
fr = open(filename)
numberOfLines = len(fr.readlines()) #取得文件的行数，1000行
returnMat = zeros((numberOfLines,3)) #生成一个1000行3列的矩阵
classLabelVector = [] #创建一个列表
fr = open(filename)
index = 0 #表示特征矩阵的行数
for line in fr.readlines():
line = line.strip()
listFromLine = line.split('\t') #将字符串切片并转换为列表
returnMat[index,:] = listFromLine[0:3] #选取前三个元素，存储在特征矩阵中
#print listFromLine
#print returnMat[index,:]
classLabelVector.append(int(listFromLine[-1])) #将列表的最后一列存储到向量classLabelVector中
index += 1
return returnMat,classLabelVector #返回特征矩阵和类标签向量 def autoNorm(dataSet): #归一化特征值
minVals = dataSet.min(0) #最小值
maxVals = dataSet.max(0) #最大值
ranges = maxVals - minVals #范围
normDataSet = zeros(shape(dataSet))
m = dataSet.shape[0]
normDataSet = dataSet - tile(minVals, (m,1)) #原来的值和最小值的差
normDataSet = normDataSet/tile(ranges, (m,1)) #特征值差除以范围
return normDataSet, ranges, minVals def datingClassTest():
hoRatio = 0.10 #测试数据的比例
datingDataMat,datingLabels = file2matrix('datingTestSet2.txt') #load data setfrom file
normMat, ranges, minVals = autoNorm(datingDataMat)
m = normMat.shape[0]
numTestVecs = int(m*hoRatio)
errorCount = 0.0
for i in range(numTestVecs):
#inX是用于分类的输入向量，dataSet是输入的训练样本集，labels是标签向量，k是选择最近邻居的数目
classifierResult = classify0(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],3)
print "分类器的结果: %d, 真正的结果: %d" % (classifierResult, datingLabels[i])
if (classifierResult != datingLabels[i]): errorCount += 1.0
print "整体的错误率: %f" % (errorCount/float(numTestVecs))
print errorCount def classifyPerson():
resultList = ['不喜欢','一点点','很喜欢']
percentTats = float(raw_input('请输入玩游戏的时间百分比：'))
ffMiles = float(raw_input('请输入飞行里程总数：'))
iceCream = float(raw_input('请输入冰淇淋的升数：'))
datingDateMat,datingLabels = file2matrix("datingTestSet2.txt") #导入数据
normMat,ranges,minVals = autoNorm(datingDateMat) #归一化
inArr = array([ffMiles,percentTats,iceCream])
classifierResult = classify0((inArr-minVals)/ranges,normMat,datingLabels,3) #分类的结果
print "喜欢的程度：",resultList[classifierResult-1] def img2vector(filename): #把32×32的二进制图像矩阵转换为1×1024的向量
returnVect = zeros((1,1024))
fr = open(filename)
for i in range(32):
lineStr = fr.readline()
for j in range(32):
returnVect[0,32*i+j] = int(lineStr[j])
return returnVect def handwritingClassTest():
#准备训练数据
hwLabels = []
trainingFileList = listdir('digits/trainingDigits') #导入训练数据集合
m = len(trainingFileList)
trainingMat = zeros((m,1024))
#和m个训练样本进行对比
for i in range(m):
fileNameStr = trainingFileList[i]
fileStr = fileNameStr.split('.')[0] #取得去掉后缀名的文件名
classNumStr = int(fileStr.split('_')[0]) #取得文件名中代表的数字
hwLabels.append(classNumStr) #由文件名生成标签向量
trainingMat[i,:] = img2vector('digits/trainingDigits/%s' % fileNameStr) #输入的训练样本集
#准备测试数据
testFileList = listdir('digits/testDigits') #iterate through the test set
errorCount = 0.0
mTest = len(testFileList)
#预测测试样本
for i in range(mTest):
fileNameStr = testFileList[i]
fileStr = fileNameStr.split('.')[0] #取得去掉后缀名的文件名
classNumStr = int(fileStr.split('_')[0]) #取得文件名中代表的数字
vectorUnderTest = img2vector('digits/testDigits/%s' % fileNameStr) #用于分类的输入向量
#inX是用于分类的输入向量，dataSet是输入的训练样本集，labels是标签向量，k是选择最近邻居的数目
classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
print "分类器的结果: %d, 真实的结果: %d" % (classifierResult, classNumStr)
if (classifierResult != classNumStr): errorCount += 1.0
print "\n预测的错误数是: %d" % errorCount
print "\n预测的错误率是: %f" % (errorCount/float(mTest)) if __name__ == '__main__':
# #group,labels = createDataSet()
# #classify0([0,0],group,labels,3)
# datingDateMat,datingLabels = file2matrix("datingTestSet2.txt")
# #print datingDateMat
# #print datingLabels
# import matplotlib
# import matplotlib.pyplot as plt
# fig = plt.figure()
# ax = fig.add_subplot(111) #控制位置
# ax.scatter(datingDateMat[:,1],datingDateMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels)) #点的横纵坐标，大小和颜色
# #plt.show()
#
# normMat,ranges,minVals = autoNorm(datingDateMat)
# print normMat
# print ranges
# print minVals # datingClassTest()
# classifyPerson()
# testVector = img2vector("digits/testDigits/0_0.txt")
# print testVector[0,0:31]
handwritingClassTest()
1.使用Python导入数据
NumPy函数库中存在两种不同的数据类型（矩阵matrix和数组array），都可以用于处理行列表示的数字元素
>>> import kNN
>>> group,labels = kNN.createDataSet()
>>> group
array([[ 1. , 1.1],
[ 1. , 1. ],
[ 0. , 0. ],
[ 0. , 0.1]])
>>> labels
['A', 'A', 'B', 'B']
>>> group
array([[ 1. , 1.1],
[ 1. , 1. ],
[ 0. , 0. ],
[ 0. , 0.1]])
>>> group.shape #shape函数求数组array的大小
(4, 2)
>>> group.shape[0]
4
>>> group.shape[1]
2
2.从文本文件中解析数据
>>> kNN.classify0([0,0],group,labels,3) #[0,0]是用于分类的输入向量，group是输入的训练样本集，labels是标签向量，3是选择最近邻居的数目
'B'
3.如何测试分类器
例子：使用k-近邻算法改进约会网站的配对效果
1.准备数据：从文本文件中解析数据
2.分析数据：使用Matplotlib创建散点图
datingDateMat,datingLabels = file2matrix("datingTestSet2.txt")
#print datingDateMat
#print datingLabels
import matplotlib
import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111) #控制位置
ax.scatter(datingDateMat[:,1],datingDateMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels)) #点的横纵坐标，大小和颜色
plt.show()
3.准备数据：归一化数值
在计算欧式距离的时候，数值差最大的属性对计算结果的影响最大。在处理这种不同取值范围的特征值的时候，我们通常的方法是将数值归一化，如将取值范围处理为0到1或者-1到1之间。
def autoNorm(dataSet): #归一化特征值
minVals = dataSet.min(0) #最小值
maxVals = dataSet.max(0) #最大值
ranges = maxVals - minVals #范围
normDataSet = zeros(shape(dataSet))
m = dataSet.shape[0]
normDataSet = dataSet - tile(minVals, (m,1)) #原来的值和最小值的差
normDataSet = normDataSet/tile(ranges, (m,1)) #特征值差除以范围
return normDataSet, ranges, minVals
normMat,ranges,minVals = autoNorm(datingDateMat)
print normMat
print ranges
print minVals
4.测试算法：作为完整程序验证分类器
def datingClassTest():
hoRatio = 0.10 #测试数据的比例
datingDataMat,datingLabels = file2matrix('datingTestSet2.txt') #load data setfrom file
normMat, ranges, minVals = autoNorm(datingDataMat)
m = normMat.shape[0]
numTestVecs = int(m*hoRatio)
errorCount = 0.0
for i in range(numTestVecs):
#inX是用于分类的输入向量，dataSet是输入的训练样本集，labels是标签向量，k是选择最近邻居的数目
classifierResult = classify0(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],3)
print "分类器的结果: %d, 真正的结果: %d" % (classifierResult, datingLabels[i])
if (classifierResult != datingLabels[i]): errorCount += 1.0
print "整体的错误率: %f" % (errorCount/float(numTestVecs))
print errorCount
5.使用算法：构建完整可用系统
def classifyPerson():
resultList = ['不喜欢','一点点','很喜欢']
percentTats = float(raw_input('请输入玩游戏的时间百分比：'))
ffMiles = float(raw_input('请输入飞行里程总数：'))
iceCream = float(raw_input('请输入冰淇淋的升数：'))
datingDateMat,datingLabels = file2matrix("datingTestSet2.txt") #导入数据
normMat,ranges,minVals = autoNorm(datingDateMat) #归一化
inArr = array([ffMiles,percentTats,iceCream])
classifierResult = classify0((inArr-minVals)/ranges,normMat,datingLabels,3) #分类的结果
print "喜欢的程度：",resultList[classifierResult-1]
例子：手写识别系统
1.准备数据，将图像转换为测试向量
def img2vector(filename): #把32×32的二进制图像矩阵转换为1×1024的向量
returnVect = zeros((1,1024))
fr = open(filename)
for i in range(32):
lineStr = fr.readline()
for j in range(32):
returnVect[0,32*i+j] = int(lineStr[j])
return returnVect
testVector = img2vector("digits/testDigits/0_0.txt")
print testVector[0,0:31]
2.测试算法：使用k-近邻算法识别手写数字
def handwritingClassTest():
#准备训练数据
hwLabels = []
trainingFileList = listdir('digits/trainingDigits') #导入训练数据集合
m = len(trainingFileList)
trainingMat = zeros((m,1024))
#和m个训练样本进行对比
for i in range(m):
fileNameStr = trainingFileList[i]
fileStr = fileNameStr.split('.')[0] #取得去掉后缀名的文件名
classNumStr = int(fileStr.split('_')[0]) #取得文件名中代表的数字
hwLabels.append(classNumStr) #由文件名生成标签向量
trainingMat[i,:] = img2vector('digits/trainingDigits/%s' % fileNameStr) #输入的训练样本集
#准备测试数据
testFileList = listdir('digits/testDigits') #iterate through the test set
errorCount = 0.0
mTest = len(testFileList)
#预测测试样本
for i in range(mTest):
fileNameStr = testFileList[i]
fileStr = fileNameStr.split('.')[0] #取得去掉后缀名的文件名
classNumStr = int(fileStr.split('_')[0]) #取得文件名中代表的数字
vectorUnderTest = img2vector('digits/testDigits/%s' % fileNameStr) #用于分类的输入向量
#inX是用于分类的输入向量，dataSet是输入的训练样本集，labels是标签向量，k是选择最近邻居的数目
classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
print "分类器的结果: %d, 真实的结果: %d" % (classifierResult, classNumStr)
if (classifierResult != classNumStr): errorCount += 1.0
print "\n预测的错误数是: %d" % errorCount
print "\n预测的错误率是: %f" % (errorCount/float(mTest))
