k-近邻算法

算法原理

将每个新数据与样本集中的每个特征进行比较，计算距离。把距离递增排序选取前k个距离最小的点，并统计前k个点的标签的出现频率，将出现频率最高的标签作为当前数据的预测分类。

此处使用欧氏距离公式：

代码：

import numpy as np import operator import matplotlib import matplotlib.pylab as plt """ 函数说明: 创建数据集的例子 参数： 无 返回值： group：数据集 labels：标签类别 """ def createDataSet(): group = np.array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]]) labels = ['A', 'A', 'B', 'B'] return group, labels """ 函数说明： kNN分类器，k-近邻算法 计算已知类别点和当前点的距离，从前k个距离最小的点中，选取出现频率最高的类别作为当前点的类别 参数： inx： 用于分类的数据，测试集 dataset： 训练样本集 labels： 标签类别 k： 选取最近邻近的数目 返回值： sortClassCount[0][0]: 分类结果 """ def classify0(inx, dataSet, labels, k): # 读取矩阵第一维的长度,即行数 # 注意是shape[0]，不是shape(0) dataSetSize = dataSet.shape[0] # 把inX复制成和dataSet相同行数的矩阵， 并作差 diffMat = np.tile(inx, (dataSetSize, 1)) - dataSet # 将作差的结果平方 sqDiffMat = diffMat**2 # 矩阵每行相加 sqDistances = sqDiffMat.sum(axis=1) # 结果开方 distance = sqDistances**0.5 # 返回排序的下表索引值 sortedDistIndicies = distance.argsort() # 选取前k个距离最小的点并用classCount记录 classCount = {} for i in range(k): # 距离最小的标签 voteIlabel = labels[sortedDistIndicies[i]] # 若标签存在则在标签基础上+1，若不存在返回默认值0，即0+1 classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1 print(classCount) sortClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True) print(sortClassCount) return sortClassCount[0][0] """ 函数说明： 打开文件，读取数据信息 参数： filename： 文件名 返回值 returnMat: 特征矩阵 classLabelVector: 类别向量 """ def file2matrix(filename): fr = open(filename) # 读取文件所有内容，保存在列表中 arrayOLines = fr.readlines() numberOfLine = len(arrayOLines) # 创建numberOfLines行，3列的0矩阵 returnMat = np.zeros((numberOfLine, 3)) classLabelVector = [] index = 0 for line in arrayOLines: line = line.strip() listFromLine = line.split() # 将数据的前3列进行提取保存在returnMat矩阵中，也就是特征矩阵 returnMat[index, :] = listFromLine[0:3] classLabelVector.append(int(listFromLine[-1])) index += 1 return returnMat, classLabelVector """ 函数说明： 归一化数值，将特征值转化为0~1区间内的值 公式：newValue = (oldValue - min) / (max - min) 参数： dataSet： 特征矩阵 返回值： normDataSet： 归一化后的特征矩阵 ranges： 数据范围 minVals： 最小值 """ def autoNorm(dataSet): # 参数 0 可以使函数从列中选取最小值，而不是行 minVals = dataSet.min(0) maxVals = dataSet.max(0) ranges = maxVals - minVals # 创建和 dataset 行列相同的矩阵 normDataSet = np.zeros(np.shape(dataSet)) # 获取 datashape 的行数 m = dataSet.shape[0] # 原始值减去最小值 normDataSet = dataSet - np.tile(minVals, (m, 1)) # 差值除以ranges normDataSet = normDataSet/np.tile(ranges, (m, 1)) return normDataSet, ranges, minVals """ 函数说明： 分类器测试 参数： 无 返回值： 无 """ def datingClassTest(): # hoRatio 表示取10%的数据用来测试 hoRatio = 0.1 # datingDataMat, datingLabels = file2matrix('datingTestSet2.txt') # 数据归一化 normMat, ranges, minvals = autoNorm(datingDataMat) # m为归一化后矩阵的行数 m = normMat.shape[0] # numTestVecs 是测试数据的行数 numTestVecs = int(m*hoRatio) # 错误次数 errorCount = 0.0 for i in range(numTestVecs): # 前 numTestVecs 个数据作为测试集，剩下的作为训练集 # normMat[i, :] 返回 normMat 矩阵第i行的全部 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))) # group, labels = createDataSet() # datingDataMat, datingLabels = file2matrix('datingTestSet2.txt') # # fig = plt.figure() # ax = fig.add_subplot(111) # ax.scatter(datingDataMat[:, 1], datingDataMat[:, 2], 15.0*np.array(datingLabels), 15.0*np.array(datingLabels)) # plt.show() datingClassTest()