简单来说 k-近邻算法采用测量不同特征值之间的距离方法进行分类
k-近邻算法工作原理 存在一个样本数据集合 也称作训练样本集 并且样本集中每个数据都存在标签 即我们知道样本集中每一个数据与所属分类的对应关系。输入没有标签的新数据后 将新数据的每个特征与样本集中数据对应的特征进行比较 然后算法提取样本集中特征最相似数据的分类标签。一般来说只取前k个最相似的数据 通常k是不大于20的整数。
k-近邻算法的优缺点及适用范围优点 精度高、对异常值不敏感、无数据输入假定
缺点 计算复杂度高、空间复杂度高
适用数据范围 数值型和标称型
from numpy import * import operator 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
group矩阵每行包含一个不同的数据 我们可以把它想象为某个日志文件中不同的测量点或者入口。
向量labels包含了每个数据点的标签信息 labels包含的元素个数等于group矩阵行数。
def classify(inX,dataSet,labels,k):
dataSetSize dataSet.shape[0]
diffMat tile(inX,(dataSetSize,1))-dataSet
sqDiffMat diffMat**2
sqDistances sqDistances**0.5
sortedDistIndicies distances.argsort()
classCount {}
for i in range(k):
voteIlabel labels[sortedDistIndicies[i]]
classCount[voteIlabel] classCount.get(voteIlabel,0) 1
sortedClassCount sorted(classCount.iteritems(),key operator.itemgetter(1),reverse True)
return sortedClassCount[0][0]
函数有四个输入参数 用于分类的输入向量inX 输入的训练样本集为dataSet 标签向量为labels 最后的参数k表示用于选择最近邻居的数目 其中标签向量的元素数目和矩阵dataSet的行数相同。
距离计算选择距离最小的k个点排序 将文本记录转换为NumPy的解析程序def file2matrix(filename): fr open(filename) arrayOLines fr.readlines() numberOfLines len(arrayOLines) returnMat zeros((numberOfLines,3)) classLabelVector [] index 0 for line in arrayOLines: line line.strip() listFromLine line.split( t ) returnMat[index,:] listFromLine[0:3] classLabelVector.append(int(listFromLine[-1])) index 1 return returnMat,classLabelVector得到文件行数创建返回的NumPy矩阵解析文件数据到列表
使用函数file2matrix读取文件数据 必须确保文件datingTestSet2.txt存储在我们的工作目录中。此外在执行这个函数之前 我们重新加载了kNN.py模块 以确保更新的内容可以生效 否则Python将继续使用上次加载的模块。
分析数据 使用Matplotlib创建散点图使用Matplotlib制作原始数据的散点图。一般来说 需要采用色彩或者其它的记号来标记不同样本分类 以便于更好地理解数据信息。
在处理不同取值范围的特征值时 我们通常采用的方法是将数值归一化 下面的公式可以将任意范围的特征值转化为0到1区间内的值。
newValue oldValue-min /(max-min)
其中min和max分别是数据集中的最小特征值和最大特征值 下面这个autonorm()函数可以自动将数字特征值转化为0到1的区间。
def autonorm(dataSet): #获得数据的最小值 minVals dataSet.min(0) maxVals dataSet.max(0) #最大值和最小值的范围 ranges maxVals - minVals #shape(dataSet)返回dataSet的矩阵行列数 normDataSet zeros(shape(dataSet)) #返回dataSet的行数 m dataSet.shape[0] #原始值减去最小值 normDataSet dataSet - tile(minVals, (m, 1)) #除以最大和最小值的差,得到归一化数据 normDataSet normDataSet / tile(ranges, (m, 1)) #返回归一化数据结果,数据范围,最小值 return normDataSet, ranges, minVals
在函数aotonorm()中 我们将每列的最小值放在变量minVals中 将最大值放在变量maxVals中 其中dataSet.min(0)中的参数0使得函数可以从列中选取最小值 而不是选取当前行的最小值。
测试算法 验证分类器机器学习算法一个很重要的工作就是评估算法的正确率 通常我们只提供已有数据的90%作为训练样本来训练分类器 而使用其余的10%数据去测试分类器 检测分类器的正确率。需要注意的是 10%的测试数据应该是随机选择的 由于海伦提供的数据并没有按照特定目的来排序 所以我么你可以随意选择10%数据而不影响其随机性。
def datingClassTest(): #打开的文件名 filename datingTestSet.txt #将返回的特征矩阵和分类向量分别存储到datingDataMat和datingLabels中 datingDataMat, datingLabels file2matrix(filename) #取所有数据的百分之十 hoRatio 0.10 #数据归一化,返回归一化后的矩阵,数据范围,数据最小值 normMat, ranges, minVals autonorm(datingDataMat) #获得normMat的行数 m normMat.shape[0] #百分之十的测试数据的个数 numTestVecs int(m * hoRatio) #分类错误计数 errorCount 0.0 for i in range(numTestVecs): #前numTestVecs个数据作为测试集,后m-numTestVecs个数据作为训练集 classifierResult classify0(normMat[i,:], normMat[numTestVecs:m,:], datingLabels[numTestVecs:m], 4) print( 分类结果:%dt真实类别:%d % (classifierResult, datingLabels[i])) if classifierResult ! datingLabels[i]: errorCount 1.0 print( the total error rate is: %f %(errorCount/float(numTestVecs)*100))使用算法 构建完整可用系统
def classifyPerson(): #输出结果 resultList [ 讨厌 , 有些喜欢 , 非常喜欢 ] #三维特征用户输入 precentTats float(input( 玩视频游戏所耗时间百分比: )) ffMiles float(input( 每年获得的飞行常客里程数: )) iceCream float(input( 每周消费的冰激淋公升数: )) filename datingTestSet.txt datingDataMat, datingLabels file2matrix(filename) #训练集归一化 normMat, ranges, minVals autonorm(datingDataMat) inArr np.array([precentTats, ffMiles, iceCream]) #测试集归一化 norminArr (inArr - minVals) / ranges classifierResult classify0(norminArr, normMat, datingLabels, 3) print( 你可能%s这个人 % (resultList[classifierResult-1]))使用k-近邻算法的手写数字识别 收集数据 提供文本文件主备数据 编写函数img2vector() 将图像格式转换为分类器使用的向量格式。分析数据 在python命令提示符中检查数据 确保它符合要求。训练算法 此步骤不适用于k-近邻算法。测试算法 编写函数使用提供的部分数据集作为测试样本 测试样本与被非测试样本的区别在于测试样本是已经完成分类的数据 如果预测分类与实际类别不同 则标记为一个错误。
def img2vector(filename): 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
测试算法
from os import listdir
from numpy import *
import numpy as np
import operator
import datetime
def KNN(test_data,train_data,train_label,k):
#已知分类的数据集 训练集 的行数
dataSetSize train_data.shape[0]
#求所有距离 先tile函数将输入点拓展成与训练集相同维数的矩阵 计算测试样本与每一个训练样本的距离
all_distances np.sqrt(np.sum(np.square(tile(test_data,(dataSetSize,1))-train_data),axis 1))
#print( 所有距离 ,all_distances)
#按all_distances中元素进行升序排序后得到其对应索引的列表
sort_distance_index all_distances.argsort()
#print( 文件索引排序 ,sort_distance_index)
#选择距离最小的k个点
classCount {}
for i in range(k):
#返回最小距离的训练集的索引(预测值)
voteIlabel train_label[sort_distance_index[i]]
#print( 第 ,i 1, 次预测值 ,voteIlabel)
classCount[voteIlabel] classCount.get(voteIlabel,0) 1
#求众数 按classCount字典的第2个元素 即类别出现的次数 从大到小排序
sortedClassCount sorted(classCount.items(), key operator.itemgetter(1), reverse True)
return sortedClassCount[0][0]
#文本向量化 32x32 - 1x1024
def img2vector(filename):
returnVect []
fr open(filename)
for i in range(32):
lineStr fr.readline()
for j in range(32):
returnVect.append(int(lineStr[j]))
return returnVect
#从文件名中解析分类数字
def classnumCut(fileName):
#参考文件名格式为 0_3.txt
fileStr fileName.split( . )[0]
classNumStr int(fileStr.split( _ )[0])
return classNumStr
#构建训练集数据向量 及对应分类标签向量
def trainingDataSet():
train_label []
trainingFileList listdir( trainingDigits )
m len(trainingFileList)
train_data zeros((m,1024))
#获取训练集的标签
for i in range(m):
# fileNameStr:所有训练集文件名
fileNameStr trainingFileList[i]
# 得到训练集索引
train_label.append(classnumCut(fileNameStr))
train_data[i,:] img2vector( trainingDigits/%s % fileNameStr)
return train_label,train_data
#测试函数
def main():
t1 datetime.datetime.now() # 计时开始
Nearest_Neighbor_number int(input( 选取最邻近的K个值 K ))
train_label,train_data trainingDataSet()
testFileList listdir( testDigits )
error_sum 0
test_number len(testFileList)
for i in range(test_number):
#测试集文件名
fileNameStr testFileList[i]
#切片后得到测试集索引
classNumStr classnumCut(fileNameStr)
test_data img2vector( testDigits/%s % fileNameStr)
#调用knn算法进行测试
classifierResult KNN(test_data, train_data, train_label, Nearest_Neighbor_number)
print ( 第 ,i 1, 组 , 预测值: ,classifierResult, 真实值: ,classNumStr)
if (classifierResult ! classNumStr):
error_sum 1.0
print ( n测试集总数为: ,test_number)
print ( 测试出错总数: ,error_sum)
print ( n错误率: ,error_sum/float(test_number)*100, % )
t2 datetime.datetime.now()
print( 耗 时 , t2 - t1)
if __name__ __main__ :
main()
本章小结
k-近邻算法必须保存全部数据集 如果训练数据集很大 必须使用大量的存储空间。必须对数据集中的每个数据计算距离值 实际使用时可能非常耗时。无法给出任何数据的基础结构信息 无法知晓平均实例样本和典型实例样本具有什么特征。
