K-近邻算法(k-Nearest Neighbor)
简单的说,K-近邻算法采用测量不同特征值之间的距离方法进行分类。{使用欧几里得度量(euclidean metric)}
优点:精度高、对异常值不敏感、无数据输入假定。
缺点:计算复杂度高、空间复杂度高。
适用数据范围:数值型和标程称型。
K-近邻算法的一般流程
(1)收集数据:可以使用任何方法。
(2)准备数据:距离计算所需要的数值,最好是结构化的数据格式。
(3)分析数据:可以使用任何方法。
(4)训练算法:此步骤不适用于K-近邻算法。
(5)测试算法:计算错误率。
(6)使用算法:首先需要输入样本数据和结构化的输出结果,然后运行K-近邻算法判断输入数据分别属于哪个分类,最后应用对计算出的分类执行后续的处理。
K-近邻算法是分类数据最简单最有效的算法。K-近邻算法是基于实例的学习,使用算法时我们必须有接近实际数据的训练样本数据。K-近邻算法必须保存全部数据集,如果训练数据集的很大,必须使用大量的存储空间。此外,由于必须对数据集中的没个数据计算距离值。实际使用时可能非常耗时。
K-近邻算法的另一个缺陷是无法给出任何数据的基础结构信息,因此我们也无法知晓平均实例样本和典型实例样本具有什么特征。
官方给的是python 2的代码,很多东西在python 3中已经无法使用,并且python 2 也快停止维护了。
增加了很多注释,能够更方便的理解 。
# -*- coding: utf-8 -*- # K阶邻算法 from numpy import * import operator import matplotlib import matplotlib.pyplot as plt from os import listdir 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 # 用kNN计算电影级别 def classify0(inX, dataSet, labels, k): # 测试 训练 结果 k阶 # shape 的功能是查看矩阵或者数组的维数。 # shape()或者a.shape返回的是矩阵的行列数([a,b],其中a是行数,b是列数) # shape[0] 只返回行数 shape[1] 只返回列数 dataSetSize = dataSet.shape[0] # tile 重复A的各个维度 # tile(A,B) 在行方向上重复A次,在列方向上重复B次 diffMat = tile(inX, (dataSetSize, 1)) - dataSet # diffMat的二次方 (a**b == a的b次方) sqDiffMat = diffMat ** 2 # sum numpy 下的方法 默认axis为None,表示将所有元素的值相加 axis=1表示按行相加 , axis=0表示按列相加 sqDistances = sqDiffMat.sum(axis=1) # 开根号 distances = sqDistances ** 0.5 # argsort返回数值从小到大的索引(值数组索引0,1,2,3) sortedDistIndecies = distances.argsort() # 新建字典 classCount = {} for i in range(k): voteIlabel = labels[sortedDistIndecies[i]] # 在字典中查找voteIlabel,如果找不到返回0,默认为 None # 不断累加计数的过程 classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1 # python3中:classCount.iteritems()修改为classCount.items() # sorted(iterable, cmp=None, key=None, reverse=False) --> new sorted list。 # reverse默认升序 # key关键字排序itemgetter(1)按照第1位元素的大小(字典序)排序 sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True) # 返回的sortedClassCount 是对出现次数的排序 返回排序的第一个元素的第一个子元素 # eg:[('A', 2), ('B', 1)] 返回 ('A', 2) 中的 第0个 'A' return sortedClassCount[0][0] # 从文件里读取数据 def file2Matrix(filename): fr = open(filename) # readlines() 方法用于读取所有行(直到结束符 EOF)并返回列表 arrryOlines = fr.readlines() # 获取数据行数 numberOfLines = len(arrryOlines) # zeros 创建0矩阵 returnMat = zeros((numberOfLines, 3)) classLabelVector = [] index = 0 for line in arrryOlines: line = line.strip() listFromLine = line.split('\t') # t[index, :] == t[index: , index: ] 对于二维数组的遍历 # t[: ,index] == t[: index, : index] 对于二维数组的遍历 returnMat[index, :] = listFromLine[0:3] # -1索引表示最后一列元素,位label信息存储在classLabelVector classLabelVector.append(int(listFromLine[-1])) index += 1 return returnMat, classLabelVector # 画特征图 def paintFigure(datingDataMat, datingLabels): fig = plt.figure() ax = fig.add_subplot(111) # 没样本分类的特征图 # ax.scatter(datingDataMat[:, 1], datingDataMat[:, 2]) # 有样本分类的特征图 ax.scatter(datingDataMat[:, 1], datingDataMat[:, 2], 15.0 * array(datingLabels), 15.0 * array(datingLabels)) plt.show() # 归一化数值方法 def autoNorm(dataSet): # min(0)中的参数0 使得函数可以从从列中选取最小值,而不是选取当前行的最小值 minVals = dataSet.min(0) # max(0)中的参数0 使得函数可以从从列中选取最大值,而不是选取当前行的最大值 maxVals = dataSet.max(0) ranges = maxVals - minVals # 创建数据长度大小的数组(shape 返回维数[a,b]) normDataSet = zeros(shape(dataSet)) # shape[0] 只返回行数 shape[1] 只返回列数 m = dataSet.shape[0] # 这里是对矩阵进行计算,而不是对单一数据进行计算,用tile()对minVals展开到m,(m,1) 沿着各个维度延伸的次数 normDataSet = dataSet - tile(minVals, (m, 1)) normDataSet = normDataSet / tile(ranges, (m, 1)) return normDataSet, ranges, minVals # 对文件数据进行k阶邻算法 def datingClassTest(): # 测试数据百分比 hoRatio = 0.10 datingDataMat, datingLabels = file2Matrix( 'G:\MLiA_SourceCode\machinelearninginaction\Ch02\datingTestSet2.txt') normMat, ranges, minVals = autoNorm(datingDataMat) m = normMat.shape[0] # 用于测试的数据数量 numTestVecs = int(m * hoRatio) # 错误数据数 errorcount = 0.0 for i in range(numTestVecs): classifierResult = classify0(normMat[i, :], normMat[numTestVecs:m, :], datingLabels[numTestVecs:m], 3) print("the classifer came back with:%d,the real answer is:%d" % (classifierResult, datingLabels[i])) if (classifierResult != datingLabels[i]): errorcount += 1 print("the total errror rate is:%f" % (errorcount / float(numTestVecs))) def classifyPerson(): resultList = ['not at all', 'in small doses', 'in large doses'] percentTats = float(input("percentage of time spent playing miles earned per year?")) ffMiles = float(input("frequent flier miles earned per year?")) iceCream = float(input("liters of ice cream consumed per year?")) datingDataMat, datingLabels = file2Matrix( "G:\MLiA_SourceCode\machinelearninginaction\Ch02\datingTestSet2.txt") normMat, ranges, minVals = autoNorm(datingDataMat) inArr = array([ffMiles, percentTats, iceCream]) classifierResult = classify0((inArr - minVals) / ranges, normMat, datingLabels, 3) print("You will probably like this person:", resultList[classifierResult - 1]) # 将二进制图片存到数组中 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 # 手写数字系统的测试代码 def handwritingClassTest(): hwLabels = [] # trainingFileList = listdir('G:/MLiA_SourceCode/machinelearninginaction/Ch02/digits/trainingDigits') m = len(trainingFileList) trainingMat = zeros((m, 1024)) for i in range(m): fileNameStr = trainingFileList[i] fileStr = fileNameStr.split('.')[0] classNumStr = int(fileStr.split('_')[0]) hwLabels.append(classNumStr) trainingMat[i, :] = img2vector( 'G:/MLiA_SourceCode/machinelearninginaction/Ch02/digits/trainingDigits/%s' % fileNameStr) testFileList = listdir('G:/MLiA_SourceCode/machinelearninginaction/Ch02/digits/testDigits') 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( 'G:/MLiA_SourceCode/machinelearninginaction/Ch02/digits/testDigits/%s' % fileNameStr) classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3) print("the classifier came back with: %d,the real answer is: %d" % (classifierResult, classNumStr)) if (classifierResult != classNumStr): errorCount += 1.0 print("\nthe total number of errors is: %d" % errorCount) print("\nthe total error rate is: %f" % (errorCount / float(mTest))) if __name__ == '__main__': # 测试电影分级方法 # groups, labels = createDataSet() # print(classify0([0.5, 1.5], groups, labels, 3)) # 测试画特征图方法 # datingDataMat, datingLabels = file2Matrix( # 'G:\MLiA_SourceCode\machinelearninginaction\Ch02\datingTestSet2.txt') # paintFigure(datingDataMat, datingLabels) # 测试autoNorm 归一化数值方法 # print(datingDataMat[0:5]) # print("\n\n") # datingDataMat, ranges, minVals = autoNorm(datingDataMat) # print(ranges) # print("\n\n") # print(minVals) # print("\n\n") # print(datingDataMat[0:5]) # 测试约会网站评级 # datingClassTest() # 输入数据测试约会网站 # classifyPerson() # 测试手写系统 handwritingClassTest() # 矩阵输出测试 # a = arange(9) # b = a.reshape(3, 3) # print(b) # print("\n\n") # print(b[0:1, 0:2])
0 条评论