[TOC]
简单地说,k - 近邻算法 采用测量不同特征值之间的距离方法进行分类。
k - 近邻算法(kNN):它的工作原理是存在一个样本数据集合(训练样本集),并且样本集中每个数据都存在标签,即我们知道样本集中每一数据域所属分类的对应关系。输入每一标签的新数据后,将新数据的每个特征与样本集中数据对应的特征进行比较,然后算法提取样本集中特征最相似数据(最近邻)的分类标签。一般来说,我们只选择样本数据集中前 k 个最相似的数据,这就是 k - 近邻算法中 k 的出处,通常 k 是不大于 20 的整数。最后,选择 k 个最相似数据中出现次数最多的分类,作为新数据的分类。
示例:基于电影中出现的亲吻、打斗出现的次数,使用 k - 近邻算法构造程序,自动划分电影的题材类型。有人统计过很多电影的打斗镜头和接吻镜头,图 2-1 显示了 6 部电影的打斗和接吻镜头数。假如有一部未看过的电影,如何确定的它是爱情片还是动作片呢?可以使用 kNN 来解决这个问题:
首先我们需要知道这个未知电影存在多少个打斗镜头和接吻镜头,图 2-1 问号位置是该未知电影出现的镜头数图形化展示,具体数字参见表 2-1:
计算未知电影与样本集中其他电影的距离,如表 2-2 所示:
现在得到了样本集中所有电影与未知电影的距离,按照距离递增排序,可以找到 k 个距离最近的电影。假定 k=3 ,则三个最近的电影依次是 He...、Bea...、Cal...。k - 近邻算法按照距离最近的三部电影的类型,决定未知电影的类型,而这三部电影都是爱情片,因此判定未知电影是爱情片。
k - 近邻算法的一般流程:
s_1_kNN.py 文件(创建数据集和标签):
- import numpy as np
- import operator
- def createDataSet():
- group = np.array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
- print(group)
- labels = ['A','A','B','B']
- print(labels)
- return group, labels
图 2-2 是带有类标签信息的四个数据点:
现在我们已经知道 Python 如何解析数据,如何加载数据,以及 kNN 算法的工作原理,接下来将使用这些方法完成分类任务。
本节使用程序中的 classify0() 函数运行 kNN 算法,为每组数据分类。该函数的功能是使用 k - 近邻算法将每组数据划分到某个类中,其伪代码如下:
对未知类别属性的数据集中的每个点依次执行以下的操作:
classify0() 如下:
- def classify0(inX, dataSet, labels, k):
- dataSetSize = dataSet.shape[0] # dataSet 的长度
- diffMat = np.tile(inX, (dataSetSize,1)) - dataSet # 分别求出 测试数据的向量减去训练数据的向量
- sqDiffMat = diffMat ** 2 # 求平方
- sqDistances = sqDiffMat.sum(axis=1) # 求和
- distances = sqDistances ** 0.5 # 求出距离
- sortedDistIndicies = np.argsort(distances) # 升序的索引值
- classCount = {} # 记录近邻标签
- for i in range(k):
- voteilabel = labels[sortedDistIndicies[i]] # 近邻标签值
- classCount[voteilabel] = classCount.get(voteilabel,0) + 1 # 记录近邻标签值得数量
- sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True) # 按近邻标签数量排序
- return sortedClassCount[0][0]
classify0() 护士中有 4 个输入参数:用于分类的输入向量是 inX,输入训练样本集是 dataSet,标签向量是 labels,最后的参数 k 表示用于选择最近邻居的数目,其中标签向量的元素数目和矩阵 dataSet 的行数相同。通过使用欧式距离公式,计算两个向量点 xA 和 xB 之间的距离:
计算完所有点之间的距离后,可以对数据按照从小到大的次序排序。然后确定前 k 个距离最小元素所在的主要分类,输入 k 总是正整数;最后,将 classCount 字典分解为元组列表,然后使用工程需第二行导入运算符模块的 itemgetter 方法,按照第二个元素的次序对元组进行排序。此处的排序为逆序,即按照从最大到最小次序排序,最后返回发生频率最高的元素标签。
进行预测:
- group, labels = createDataSet()
- result = classify0([0.4,0.2], group, labels, 3)
- print(result) # B
通过大量的测试数据,我们可以得到分类器的 错误率 :分类器给出错误结果的次数除以测试执行的总数。错误率是常用的评估方法,主要用于评估分类器在某个数据集上的执行效果
将约会网站上的人选进行分类:不喜欢的人、魅力一般的人、极具魅力的人
示例:在约会网站上使用 k - 近邻算法:
样本主要包含以下 3 种特征:
在将特征数据输入到分类器之前,必须将待处理数据的格式改变为分类器可接受的格式。
file2matrix 函数用来处理输入数据的格式。该函数的输入为文本文件名字符串,输出为训练样本矩阵和类标签向量。
- def file2matrix(filename):
- fr = open(filename)
- arrayOLines = fr.readlines() # 读取文件
- numberOfLines = len(arrayOLines) # 行数
- returnMat = np.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
scatter 函数支持个性化标记散点图上的点
- filename = 'datingTestSet2.txt'
- datingDataMat, datingLabels = file2matrix(filename)
- 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()
在处理不同取值范围的特征值时,通常采用的方法是将数值归一化,如将取值范围处理为 0 到 1 或者 -1 到 1 之间。下面的公式可以将任意取值范围的特征值转化为 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 # 差值
- normDataSet = np.zeros(np.shape(dataSet))
- m = dataSet.shape[0]
- normDataSet = dataSet - np.tile(minVals, (m,1)) # 数据 - 最小值
- normDataSet = normDataSet / np.tile(ranges, (m,1)) # 上面的值 / 最小值
- # normDataSet = np.linalg.solve(normDataSet,np.tile(ranges, (m,1)))
- return normDataSet,ranges,minVals
添加 ditingClassTest 函数:
- def datingClassTest():
- hoRatio = 0.10
- filename = 'datingTestSet2.txt'
- datingDataMat, datingLabels = file2matrix(filename)
- 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("classifierResult:" , classifierResult)
- print('datingLabels[i]:',datingLabels[i])
- if(classifierResult != datingLabels[i]):
- errorCount += 1.0
- print('the total error rate is: %f' % (errorCount / float(numTestVecs)))
可以改变函数 datingClassTest 内变量 hoRatio 和变量 k 的值,检测错误率是否随着变量值得变化而增加。依赖于分类算法、数据集和程序设置,分类器的输出结果可能有很大的不同。
添加 classifyPerson 函数,来输入个人信息,判断分类:
- def classifyPerson():
- resultList = ['not at all', 'in small doses', 'in large doses']
- percenTats = float(input('percentage of time spent playing video games?'))
- ffMiles = float(input('freguent flier miles earned per year?'))
- iceCream = float(input('liters of ice cream consumed per year?'))
- filename = 'datingTestSet2.txt'
- datingDataMat, datingLabels = file2matrix(filename)
- normMat, ranges, minVals = autoNorm(datingDataMat)
- inArr = np.array([ffMiles, percenTats, iceCream])
- classifierResult = classify0((inArr - minVals) / ranges,normMat, datingLabels, 3)
- print('you will probably like this person:',resultList[classifierResult - 1])
示例说明:构造使用 k - 近邻分类器的手写识别系统,来识别数字 0 到 9. 需要识别的数字已经使用图形处理软件,处理成具有相同的色彩和大小的黑白图像。
示例:使用 k - 近邻算法的手写识别系统
添加 img2vector 函数,将图像转换为向量:该函数创建 1 X 1024 的 numpy 数组,然后打开给定的文件,循环独处文件的前 32 行,并将每行的头 32 个字符值存储在 numpy 数组中,最后返回数组:
- def img2vector(filename):
- returnVect = np.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
添加 handwritingClassTest 函数,来测试分类器:
- def handwritingClassTest():
- hwLabels = []
- trainingFileList = listdir('trainingDigits')
- m = len(trainingFileList)
- trainingMat = np.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('trainingDigits/%s' % fileNameStr) # 训练集
- # 测试
- testFileList = listdir('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('testDigits/%s' % fileNameStr) # 测试集
- classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3) # 预测标签
- print('classifierResult:',classifierResult)
- print('classNumStr:',classNumStr)
- if(classifierResult != classNumStr):
- errorCount += 1.0
- print('errorCount:',errorCount)
- print('rate:',errorCount/float(mTest))
改变变量 k 的值、修改函数 handwritingClassTest 随机选取训练样本、改变训练样本的数目,都会对 k - 近邻算法的错误率产生影响。
k - 近邻算法是分类数据最简单最有效的算法。k - 近邻算法是基于实例的学习,使用算法时我们必须有接近实际数据上的训练样本数据。k - 近邻算法必须保存全部数据集,如果训练数据集很大,必须使用大量的存储空间。此外,由于必须对数据集中的每个数据计算距离值,实际使用时可能非常耗时。
另一个缺陷是它无法给出任何数据的基础结构信息,因此我们也无法知晓平均实例样本具有什么特征。
来源: http://www.jianshu.com/p/b5422dfbe3f0