https://www.pkudodo.com/2018/11/19/1-2/
''' 数据集：Mnist 训练集数量：6万 测试集数量:10000(实际使用:200) ------------------------------ 运行结果:(相邻k数:25) 算法-欧式距离 正确率：97% 运行时长：308s 使用方法-曼哈顿距离 正确率：14% 运行时长：246s ''' import numpy as np import time def loadData(fileName): ''' 加载文件 :param fileName:要加载的文件路径 :return: 数据集和标签集 ''' print('start read file') #存储数据和标记 dataArr = []; labelArr = [] #读取文件 fr = open(fileName) #遍历文件中的每一行 for line in fr.readlines(): #获得当前行，并 #strip：去掉每行字符串首尾指定的字符（默认空格或换行符） #split：将字符串按指定字符切割成每个字段，返回列表形式 curLine = line.strip().split(',') #将每行除标记外的数据放入数据集中（curLine[0]标记信息) #将原始字符串形式的数据转换为整形 dataArr.append([int(num) for num in curLine[1:]]) #将标记信息放入标记集中 #同时将标记转换为整形 labelArr.append(int(curLine[0])) #返回数据集和标记 return dataArr, labelArr def calcDist(x1, x2): ''' 计算两个样本点向量之间的距离 使用欧氏距离，即 样本点各元素相减的平方 再求和 再开方 这里写欧式例子公式不方便，可以百度或谷歌欧式距离（也称欧几里得距离） :param x1:向量1 :param x2:向量2 :return:欧量之间的欧式距离 ''' return np.sqrt(np.sum(np.square(x1 - x2))) #马哈顿距离计算公式 # return np.sum(x1 - x2) def getClosest(trainDataMat, trainLabelMat, x, topK): ''' 预测样本x的标记。 通过找到最近的样本x获取方法topK查看它们的标签。 寻找占某类标签最多的标签 （书中3.1 3.2节） :param trainDataMat:训练集数据集 :param trainLabelMat:训练标签集 :param x:样本需要预测x :param topK:参考最相邻样本的数量(样本数量的选择与正确率有关，详看3.2.3 K值的选择） :return:预测的标记 ''' #建立存储向量x和每个训练集中样本之间的列表 #列表的长度是训练集的长度，distList[i]表示x和训练集中第一 ## i样本的距离 distList = [0] * len(trainLabelMat) #遍历训练集中所有样本点，计算与x的距离 for i in range(len(trainDataMat)): #集中当前样本的向量获取训练 x1 = trainDataMat[i] #计算向量x与训练集样本x的距离 curDist = calcDist(x1, x) #将距离放入相应的列表位置 distList[i] = curDist #对距离列表进行排序 #argsort：函数从小到大排序数组的值，并按相应的索引值输出 #例如： # >>> x = np.array([3, 1, 2]) # >>> np.argsort(x) # array([1, 2, 0]) #返回列表中从小到大的元素索引值，非常适合我们需要找到最小距离的情况 #array通过[:topK]取列表中前topL个放入list中。 #----------------优化点------------------- #因为我们只拿topK小元素索引值，不需要对整个列表进行排序，而是argsort是对整个 #对列表进行排序，存在时间浪费。现成的字典方法只能排序top大或top小，可以自己查阅 #可以稍微修改代码。 #这里没有优化的主要原因是KNN由于高维向量，计算向量与向量之间的距离需要大部分时间 #所以计算时间需要很长时间，所以如果要提高时间，这里的优化意义不大。(当然不是说不能优化， #主要是我太懒了) topKList = np.argsort(np.array(distList))[:topK] #升序排序 #建立长度列表，以选择最多的标记 #3.2.4提到分类决策使用投票表决，topK每个标记每人都有一票，在数组中每个标记代表的位置投资 #自己对应的地方，然后选择最高票进行唱票标记 labelList = [0] * 10 #对topK一个索引进行遍历 for index in topKList: #trainLabelMat[index]：寻找训练标签topK元素索引对应的标记 #int(trainLabelMat[index])：将标记转换为int(其实已经是了int了，但是不int报错) #labelList[int(trainLabelMat[index])]：找到标记在labelList相应的位置 #最后加1，表示投了一票 labelList[int(trainLabelMat[index])] = 1 #max(labelList)：在选票箱中找到票数最多的票数 #labelList.index(max(labelList))：在列表中根据最大值找到相应的索引，相当于预测标记 return labelList.index(max(labelList)) def model_test(trainDataArr, trainLabelArr, testDataArr, testLabelArr, topK): ''' 测试正确率 :param trainDataArr:训练集数据集 :param trainLabelArr: 训练集标记 :param testDataArr: 测试集数据集 :param testLabelArr: 测试集标记 :param topK: 选择多少邻近点参考 :return: 正确率 ''' print('start test') #将所有列表转换为矩阵形式，方便运算 trainDataMat = np.mat(trainDataArr); trainLabelMat = np.mat(trainLabelArr).T testDataMat = np.mat(testDataArr); testLabelMat = np.mat(testLabelArr).T #错误值技术 errorCnt = 0 #遍历测试集，测试每个测试集样本 #由于计算向量和向量之间的时间过长，测试集有6000个样本，这里人为改为 #测试200个样本点，如果要全跑，取消行注，然后下一行for注释即可，同时下面的print #和return还应相应更换注释行 # for i in range(len(testDataMat)): for i in range(200): # print('test %d:%d'%(i, len(trainDataArr))) print('test %d:%d' % (i, 200)) #读取当前测试样本的向量 x = testDataMat[i] #获取预测标记 y = getClosest(trainDataMat, trainLabelMat, x, topK) #如果预测标记与实际标记不一致，错误值计数加1 if y != testLabelMat[i]: errorCnt = 1 #返回正确率 # return 1 - (errorCnt / len(testDataMat)) return 1 - (errorCnt / 200) if __name__ == "__main__": start = time.time() #获得训练集 trainDataArr, trainLabelArr = loadData('../Mnist/mnist_train.csv') #获取测试集 testDataArr, testLabelArr = loadData('../Mnist/mnist_test.csv') #计算测试集的准确性 accur = model_test(trainDataArr, trainLabelArr, testDataArr, testLabelArr, 25) #打印准确率 print('accur is:%d'%(accur * 100), '%') end = time.time() #显示需要时间 print('time span:', end - start)