k-近邻算法采用测量不同特征值之间的距离方法进行分类。
<b>[html]</b> view plain copy
优点：精度高、对异常值不敏感、无数据输入假定
缺点：计算复杂度高、空间复杂度高
适用数据范围：数值型和标称型
存在一个一个数据集合，也称训练数据集，并且每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，选择前k（通常k是不大于20的整数）个最相似（最邻近）的数据。在这些数据中取出现次数最多的分类。
<b>[python]</b> view plain copy
'''''
kNN算法核心分类函数
这里距离使用的是欧式距离sqrt((a1-b1)**2 + (a2-b2)**2 + ... + (an-bn)**2)
参数：
inX：用于分类的输入向量
dataSet：训练集样本
labels：标签向量
k：选择最近邻居的数目
'''
def classify0(inX,dataSet,labels,k):
dataSetSize = np.size(dataSet,axis=0) #数据集样本数目
diffMat = np.tile(inX,(dataSetSize,1)) - dataSet #tile函数构建dataSet同样规格的矩阵，输入向量的各个特征减去训练集中对应特征
sqDiffMat = diffMat**2 #计算输入向量与训练集中各个样本的距离
sqDistances = np.sum(sqDiffMat,axis=1) #把每一列的矩阵相加
sortedIndicies = np.argsort(sqDistances) #按照距离升序，新矩阵显示的是在之前矩阵的距离
classCount = {} #存储k个最近邻居的标签及数目
for i in range(k): #找到k个最近邻居并存储
voteILabel = labels[sortedIndicies[i]]
classCount[voteILabel] = classCount.get(voteILabel,0) + 1
sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True) #对value降序排序，返回一个数组
return sortedClassCount[0][0] #预测的分类
import numpy as np
import operator
import matplotlib
import matplotlib.pyplot as plt
将文本记录转换为numpy矩阵
filename：文件路径
def file2matrix(filename):
fr = open(filename) #打开文件
arrayOLines = fr.readlines() #读取文件
numberOfLines = len(arrayOLines) #获取文件行数
returnMat = np.zeros((numberOfLines,3)) #构造行数=文本行数，列数=特征数的numpy零矩阵
classLabelVector = [] #存储文本中每个样本对应分类标签
index = 0 #索引，用于调到下一行进行赋值
for line in arrayOLines:
line = line.strip() #截取所有回车字符
listFromLine = line.split('\t') #使用tab字符'\t'将上一步得到的整行数据分割成一个元素列表
returnMat[index,:] = listFromLine[0:3] #选取前三个字符将他们存储到特征矩阵中
classLabelVector.append(int(listFromLine[-1])) #将文本中的最后一列(列表标签)单独存储到一个列表中
index += 1
return returnMat,classLabelVector #返回一个特征矩阵和标签列表
归一化特征值
dataSet：训练集样本(特征矩阵)
newValue = (oldValue - min)/(maxValue - minValue)
def autoNorm(dataSet):
minVals = np.min(dataSet,axis=0) #每一列的最小值
maxVals = np.max(dataSet,axis=0) #每一列的最大值
ranges = maxVals - minVals #每一列的取值范围
normDataSet = np.zeros(np.shape(dataSet)) #构造一个新的dataSet大小的numpy零矩阵
m = np.size(dataSet,axis=0) #取dataSet行数
normDataSet = dataSet - np.tile(minVals,(m,1)) #按照公式进行归一化
normDataSet = normDataSet/np.tile(ranges,(m,1))
return normDataSet,ranges,minVals #归一化后的特征矩阵，取值范围，训练集每一列的最小值'''
分类器针对约会网站的测试函数
取训练集的前10%样本作为测试集
def datingClassTest():
hoRatio = 0.10
datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')
normMat,ranges,minVals = autoNorm(datingDataMat)
m = np.size(normMat,axis=0)
numTestVecs = int(hoRatio*m)
errorCount = 0.0
for i in range(numTestVecs):
classifierResult = classify0(normMat[i,:], normMat[numTestVecs:m,:], datingLabels[numTestVecs:m], 3)
print("The classifier came back with:%d,the real answer is:%d" % (classifierResult,datingLabels[i]))
if classifierResult != datingLabels[i]:
errorCount += 1.0
print("the total error rate is:%f" % (errorCount/float(numTestVecs)))
约会网站预测函数
def classifyPerson():
resultList = ["not at all","in small does","in large does"]
percentTats = float(input("percentage of time spent playing video games?"))
ffMiles = float(input("frequent flier miles earned per year?"))
iceCream = float(input("liters of ice cream consumes per year?"))
datingDataMat,datingLabels = file2matrix("datingTestSet2.txt")
inArr = np.array([ffMiles,percentTats,iceCream])
classifierResult = classify0(((inArr-minVals)/ranges),datingDataMat,datingLabels,3)
print("You will probably like this person:",resultList[classifierResult - 1])
The classifier came back with:3,the real answer is:3
The classifier came back with:2,the real answer is:2
The classifier came back with:1,the real answer is:1
The classifier came back with:3,the real answer is:1
the total error rate is:0.050000
percentage of time spent playing video games?10
frequent flier miles earned per year?10000
liters of ice cream consumes per year?0.5
You will probably like this person: in small does
import os
将32*32的黑白图像转换成1*1024的向量
def img2vector(filename):
returnVect = np.zeros((1,1024)) #构造1*1024的numpy零矩阵
fr = open(filename) #打开文件
for i in range(32): #循环读取每一个像素点(字符)，转换为1*1024的向量
lineStr = fr.readline()
for j in range(32):
returnVect[0,32*i+j] = int(lineStr[j])
return returnVect
手写数字识别系统的测试函数
每一个样本为单个文件，统一存在训练集文件夹下
def handwritingClassTest():
hwLabels = [] #存储手写数字分类标签的列表
trainingFileList = os.listdir('trainingDigits') #进入训练集目录
m = len(trainingFileList) #统计训练样本数目
trainingMat = np.zeros((m,1024)) #构造m*1024numpy零矩阵，为了将所有训练样本转换成二维矩阵进行计算
for i in range(m): #将所有训练样本转换成m*1024的numpy矩阵
fileNameStr = trainingFileList[i] #样本名称
fileStr = fileNameStr.split('.')[0] #获取样本对应类别标签
classNumStr = int(fileStr.split('_')[0])
hwLabels.append(classNumStr)
trainingMat[i, :] = img2vector('trainingDigits/' + fileNameStr) #将32*32的黑白图像转换成1*1024的向量
testFileList = os.listdir('testDigits') #进入训练集文件夹，得到所有测试样本列表
errorCount = 0.0 #预测错误个数
mTest = len(testFileList) #测试样本个数
for i in range(mTest): #每个测试集样本进行预测
fileNameStr = testFileList[i] #测试样本名称
fileStr = fileNameStr.split('.')[0] #获取测试样本真正的类别标签
vectorUnderTest = img2vector('testDigits/%s' % fileNameStr) #将32*32的黑白图像转换成1*1024的向量
prediction = classify0(vectorUnderTest,trainingMat,hwLabels,3) #预测手写数字
print("the classifier came back with: %d,the real answer is:%d" % (prediction,classNumStr))
if classNumStr != prediction:
errorCount += 1
print("\nthe total number of errors is:%d" % errorCount) #预测错误次数
print("\nthe total error rate is:%f" % (errorCount/float(mTest))) #预测错误率
the classifier came back with: 9,the real answer is:9
the total number of errors is:10
the total error rate is:0.010571
实际使用这个算法时，时间复杂度和空间复杂度相当高， 因此执行效率并不高。此外还需要为向量准备2MB的存储空间。为了解决存储空间和计算时间的开销，可以引入k决策树，可以节省大量的计算开销。
knn是分类数据最简单有效的算法。knn是基于实例的学习，使用算法时必须有接近实际数据的训练样本数据。knn必须保存全部数据集，如果训练数据集很大，则须使用大量存储空间。此外，由于必须对数据集中的每个数据计算距离值，实际使用时可能非常耗时。
knn另一个缺陷是无法给出任何数据的基础结构信息，因此也无法知晓平均实例样本和典型实例样本具有什么特征。knn