K-近邻算法
- 概念：K近邻算法采用测量不同特征值之间的距离方法进行一个分类
- 优点：精确高、对异常值不敏感、无数据输入假定
- 缺点：计算复杂度高、空间复杂度高
- 适合数据范围：数值型和标称型
- 原理：首先我们需要有一个数据样本集(我们也称作为数据训练集)，在这个训练集中的数据都是带有标签(与所属分类是一一对应的);然后将不带标签的数据与训练集中的数据的特征进行比较，使用算法提取出训练样本集中特征最相似的数据(我们往往选择训练集中的前K个，k<20)的分类标签；最后选择次数出现最好的分类标签作为这个新数据的标签。(如下图，画的不好将就一下呗)
K-近邻算法的一般流程
- 收集数据：可以使用任何方法
- 准备数据：距离计算所需要的数值，最好是结构化的数据格式
- 分析数据:可以使用任何方法
- 训练算法:此步骤不是很适用于K近邻算法
- 测试算法：计算错误率
- 使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理
伪代码
对未知类别属性的数据集中的每个点一次执行以下操作
-
计算已知类别属性数据集中的点与当前点之间的距离
-
按照距离递增次序排序
-
选取与当前点距离最小的K个点
-
确定前K个点所在类别的出现频率
-
返回前k个点出现频率最高的类别作为当前点的预测分类
代码案例
案例一
针对以上的kNN算法,我们在现实中去改进一下约会网站的配对效果
- 收集数据：提供文本文件
- 准备数据：使用Python解析文本文件
- 分析数据：使用Matplotlib画二维扩散图
- 训练算法：该步骤不适用于kNN算法
- 测试算法：使用提供的部分数据作为测试样本（测试样本和非测试样本的区别在于：测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误）
- 使用算法：产生简单的命令行程序，然后我们可以输入一些特征数据以判断对方是否为自己喜欢的类型
案例二
如何在人不太容易看懂的数据上使用分类器呢?
使用kNN算法的手写识别系统
- 收集数据:提供文本文件
- 准备数据：编写函数classify0,将图像格式转换为分类器使用的list格式
- 分析数据：在python命令提示符中检查数据,确保它符合要求
- 训练算法：此步骤不适用于kNN算法
- 测试算法：编写函数使用提供的部分数据作为测试样本，测试样本与非测试样本的区别在于测试样本已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误
- 使用算法：从图像中取数字，并完成数字识别(美国的邮件分拣系统就是一个实际的类似系统)
下面给大家看看我的源码(如有错误请多多指出，大家一起进步)：
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
' a kNN module '
__author__ = 'OJ cheng'
from numpy import * #导入科学计算包
import operator # 导入运算发模块
from os import listdir
#------------------------------------华丽的分界线----------------------------------
#判断未知电影是动作片还是爱情片(根据电影中出现的接吻镜头次数和打斗镜头次数)
def createDataSet():
group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])#NumPy中的方法,参数可以为(列表、元组或者数组)
labels = ['A','A','B','B']
return group,labels
#该函数有四个参数：用于分类的输入向量inX；输入的训练样本集dataSet，标签向量labels，选择最近邻居的数目k
#注意：标签向量的元素数目和矩阵dataSet的行数相同
"""
这个分类器中分别用到了NumPy库中的shape、tile、sum、argsort
-shape：其实可以简单理解成显示NumPyArray的行/列(二维)、维/行/列(多维)
x = array([[0,3],[2,1]])
print(x.shape) #结果为(2, 2) 二行而列
x = zeros((2,3,4))
print(x.shape) #结果为(2,3,4) 二维三行两列
-sum:矩阵求和运算，其中axis指的是轴
对于[[[ 0 1 2 3]
[ 4 5 6 7]
[ 8 9 10 11]]
[[12 13 14 15]
[16 17 18 19]
[20 21 22 23]]
]
axis = 0 的时候，二维消失，第一维和第二维对应元素相加，结果为：
[
[
[12 14 16 18]
[20 22 24 26]
[28 30 32 34]
]
]
axis = 1 的时候，行消失，第一维的三行元素累加，第二维同，结果为(为了表示形象)：
[
[
[12 15 18 21]
]
[
[48 51 54 57]
]
]
axis = 2 的时候，列消失，第一维的三列元素累加，第二维同，结果为(为了表示形象)：
[
[[
6
22
38
]]
[[
54
70
86
]]
]
-tile:这是一个很神奇的函数，可以快速复制，tile(a,x) tile(a,(x,y)),tile(a,(x,y,z))等等
用法如下：
a = [1 3]
tile(a,1) 结果为：[1 3 1 3] #这是一维数组，x=1说明将a复制一次，如果a=2就是复制两次啦
tile(a,(2,3)) 结果为(形象表示)：
[
[
[1 3 1 3 1 3]
[1 3 1 3 1 3] #这是一个二维的1*2的矩阵，说明x=2控制行数，而y=3是控制a复制的次数啦
]
]
tile(3,2,3) 结果为(形象表示)：将三维矩阵当成一个二维矩阵里面放了一个一维矩阵
[
[[1 3 1 3 1 3] [1 3 1 3 1 3]] #这是一个三维的2*4矩阵，说明x=3控制的行数、y=2控制的是列数，而z=3表示a复制的次数
[[1 3 1 3 1 3] [1 3 1 3 1 3]]
[[1 3 1 3 1 3] [1 3 1 3 1 3]]
]
-argsort：这个函数其实就是返回排序后的索引(默认从小到大)，比如：
a = [4,3,5] #索引为：0,1,2
a.argsort() #从小到大排序[3,4,5]对应的索引分别为：[1,0,2] 二维矩阵也是如此的
"""
def classify(inX,dataSet,labels,k):
dataSetSize = dataSet.shape[0]
#利用欧拉公式去计算两点的距离
diffMat = tile(inX,(dataSetSize,1)) - dataSet
sqDiffMat = diffMat ** 2 #平方
sqDistances = sqDiffMat.sum(axis=1) #列相加
distances = sqDistances**0.5 #开根号
#计算完所有点之间的距离后可以对数据进行从小到大的次序排序
sortedDisIndicies = distances.argsort()
#确定前k个距离最小元素所在的主要分类，其中k的值是一个正整数
classCount = {}
for i in range(k) :
voteIlabel = labels[sortedDisIndicies[i]]
classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
#将classCount字典分解为元组列表，然后导入运算符模块的itemgetter方法，按照第二个元素的次序对元组进行排序
#这个时候的元组排序是逆序(从大到小)
#特别注意：python3.x后就不再支持dict的iteritems属性 所以执行sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)会报错
sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
#返回发生频率最高的元素标签
return sortedClassCount[0][0]
# group,labels = createDataSet()
# print(classify([0,0],group,labels,3))
#------------------------------------------------华丽分界线------------------------------
#datingTestSet.txt中样本包括以下三种特征：
#每年获得的飞行常客里程数
#玩视频游戏所占时间百分比
#每周消费的冰淇淋公升数
#第一步：将需要处理的数据格式改变为分类器可以接受的格式
def file2matrix(filename):
fr = open(filename)
#得到文件行数
arrayOLines = fr.readlines()
numberOfLines = len(arrayOLines)
#创建返回的NumPy矩阵
#以零填充的矩阵NumPy,将第三个纬度直接定为3
returnMat = zeros((numberOfLines,3))
classLabelVector = []
index = 0
#解析文件数据到列表
for line in arrayOLines:
#截取掉所有的回车字符
line = line.strip()
#使用\t分割成一个元素列表
listFromLine = line.split('\t')
#选择前三个元素储存到特征矩阵中
returnMat[index,:] = listFromLine[0:3]
#将最后一列元素储存到向量classLabelVector
classLabelVector.append(int(listFromLine[-1]))
index += 1
return returnMat,classLabelVector
datingDataMat,datingLabels = file2matrix('E:\ML_Data\datingTestSet2.txt')
# print(datingDataMat)
#我们使用Matplotlib制作原始数据的散点图
#如果想使用reload在dos直接重新加载，python3.x后都得自己导入，from imp import reload
# import matplotlib
# import matplotlib.pyplot as plt
# fig = plt.figure(1)
# 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()
#第二步：准备数据，归一化数值
#我们认为训练集中的数据，它的三个特征应该是等同重要的，为了避免莫一个特征值明显大于其他两个特征值，我们需要归一化数值
#通常将取值范围处理为0~1或者-1~1：newValue = (oldValue - min)/(max-min)
def autoNorm(dataSet):
#参数0时函数可以从列中选择最小值，不是当前行的最小值
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals
normDataSet = zeros(shape(dataSet))
#dataSet矩阵是1000*3个值，minVals和range的值都是1*3
#使用NumPy中的tile()函数将变量内容复制成输入矩阵同样大小的矩阵
m = dataSet.shape[0]
normDataSet = dataSet - tile(minVals,(m,1))
#需要注意的是：这是特征值相除，对于某些数值处理软件包‘/’可能象征着矩阵除法
#在NumPy中矩阵除法是函数：linalg.sovle(matA,matB)
normDataSet = normDataSet / tile(ranges,(m,1))
return normDataSet,ranges,minVals
normMat,ranges,minVals = autoNorm(datingDataMat)
# print(normMat)
#第三步：我们测试算法，采取传统的方式，10%的数据去测试分类器，检测分类器的准确率
#这是一个测试我们对约会网站改进的准确率
# def datingClassTest():
# hoRatio = 0.10
# datingDataMat,datingLabels = file2matrix('E:\ML_Data\datingTestSet2.txt')
# normMat,ranges,minVals = autoNorm(datingDataMat)
# m = normMat.shape[0]
# numTestVecs = int(m*hoRatio)
# errorCount = 0.0
# for i in range(numTestVecs):
# classifierResult = classify(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],4)
# 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)))
# datingClassTest()#理论上k的值越大,准确率越高(但是往往太大后，准确率就降低)
#将以上算法进行组合，通过这个程序海伦可以在约会网站上找到某个人并输入他的信息，程序会预测他对对方喜欢的程度
#约会网站预测函数
def classifyPerson():
resultList = ['not at all ','in small doses','in large doses']
percentTats = float(input("percetage of time spent playing video games?"))
ffMiles = float(input("frequent flier miles earned per year?"))
iceCream = float(input("liters of ice cream consumed per year?"))
datingDataMat,datingLabels = file2matrix("E:\ML_Data\datingTestSet2.txt")
normMat,ranges,minVals = autoNorm(datingDataMat)
inArr = array([ffMiles,percentTats,iceCream])
classifierResult = classify((inArr-minVals)/ranges,normMat,datingLabels,3)
print("You will probably like this person :",resultList[classifierResult-1])
classifyPerson()
#--------------------------------------华丽分界线------------------------------------------------
#手写识别系统
#第一步：我们首先准备数据并且将图像转化为测试向量
#目录trainingDigits中包含大约2000个例子，每个数据大概有200个样本；
#目录testDigits包含了大约900个测试数据
#我们将32*32的二进制图像矩阵转化为1*1024的向量，以便之前的分类器处理数字图像信息
# def img2vector(filename):
# #创建1*1024的NumPy数组
# returnVect = zeros((1,1024))
# #打开文件
# fr = open(filename)
# #循环读出文件的前32行
# for i in range(32):
# lineStr = fr.readline()
# #将每行的头32个字符值储存在NumPy数组中
# for j in range(32):
# returnVect[0,32*i+j] = int(lineStr[j])
# return returnVect
#在这里写成'\'这种，python在解析的时候一般会再加上一个\(也就是\\),但是遇到\0_13.txt中的\0这种特殊字符的时候不会自动加\
# testVector = img2vector('E:/ML_Data/testDigits/0_13.txt')
# print(testVector[0,0:31])
#第二步：测试算法：使用kNN算法识别手写数字
#在这里我们首先导入os.listdir来列出给定目录的文件名
# def handwritingClasstest():
# hwLabels = []
# trainingFileList = listdir('E:/ML_Data/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('E:/ML_Data/trainingDigits/%s' %fileNameStr)
# testFileList = listdir('E:/ML_Data/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('E:/ML_Data/testDigits/%s' % fileNameStr)
# classifierResult = classify(vectorUnderTest,trainingMat,hwLabels,4)
# 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)))
# handwritingClasstest()
对应数据文件：
百度云链接：https://pan.baidu.com/s/1i4SI12P
相关书籍pdf ：https://github.com/apachecn/MachineLearning/tree/python-2.7/books
大家如果想要深入了解，请翻阅<机器学习实战>这一本书
或者直接访问开源https://github.com/apachecn/MachineLearning
喜欢可以多多收藏哦~转载请标注原文地址呦~
