ok,今天花了一天时间看了小人书(机器学习实战),并且撸到了KNN算法,并完成了一个KNN算法的应用
真的!!!小人书是本特别不错的适合入门ML的书!!!!!
没有繁杂的数学推导过程,先给出概念和实战应用,等对ML有个大致了解后再去啃那些理论书,大量的代码真的很对胃口啊啊啊啊
关与机器学习的这里不废话太多,直接进入正题
KNN算法
那么什么是KNN呢?
K近邻算法(KNN), 首先KNN属于机器学习中监督学习中的一个算法,这里先不说什么是监督学习,很直接的理解,KNN就是一个算法,大家按普通算法的路子学就行了
KNN的用途:
KNN是一个分类算法,当然主要用于各种各样的分类了啊,比如给你一大堆的狗,让你给他们一个个分类(泰迪啊,金毛啊,西伯利亚雪橇犬啊......),这时候就可以用到KNN了
KNN的工作原理:
首先给出官方介绍: 存在一个样本数据集合 ,也称作训练样本集, 并且样本集中每个数据都存在标签,即我们知道样本集中每一数据与所属分类的对应关系。 输人没有标签的新数据后, 将新数据的每个特征与样本集中数据对应的特征进行比较,然后算法提取样本集中特征最相似数据(最 近 邻 )的分类标签。一般来说,我们只选择样本数据集中前 K个最相似的数据,这就是 K- 近邻算法中 K 的出处 , 通常 K 是不大于 20 的整数.最后 ,选择 & 个最相似数据中出现次数最多的分类,作为新数据的分类
太繁杂了吧,这里给出通俗的理解:
首先拿出刚刚分类的狗,首先我们要先知道各种各样的狗(样本集)是长什么样子(标签)的,现在从外面跑来一只小野狗,我们 想知道这个小野狗是属于什么狗,然后我们就开始拿这个狗给分好类的狗进行对比,首先先比比身材,比比眼睛,耳朵....(样本特征),最后我们找出了一个跟这个小野狗(k个特征)最像(最近邻)的狗,那么就可以判断出这个小野狗属于什么狗
上面的狗也很麻烦?
再来一个不是很严谨的但是更容易理解的:
给出一个三维坐标,我们给出一堆水果,x轴代表大小,y轴代表颜色,z轴代表形状(0为圆,1为椭圆....)
然后我们分别把苹果,梨,葡萄按特征放在这个三维坐标里,当然这三种水果应该是分成三部分,现在拿出一个不知道是什么的水果,按照它的特征找出它在三维坐标里的位置,然后一个个计算这个未知水果距离每个已知水果的距离,当它与K个最近距离中哪个水果多,那么就判断这个水果是什么水果,
比如: 在离这个水果最近的10个水果中有5个苹果,3个梨,2个葡萄,那么就说这个水果是个苹果
废话太多,重新进入正题:
用到KNN的一般流程
(1) 收集数据:可以使用任何方法。
(2) 准备数据:距离计算所需要的数值,最好是结构化的数据格式。
(3) 分析数据:可以使用任何方法。
(4) 训练算法:此步驟不适用于 K近邻算法。
(5) 测试算法:计算错误率。
(6) 使 用 算法 :首先需要输入样本数据和结构化的输出结果,然后运行女-近邻算法判定输入数据分别属于哪个分类,最后应用对计算出的分类执行后续的处理
因此看出,KNN主要在用在整个程序的最后的结果处理
那么,KNN的算法的算法流程是什么?
对未知类别属性的数据集中的每个点依次执行以下操作:
(1) 计算已知类别数据集中的点与当前点之间的距离;
(2) 按照距离递增次序排序;
(3) 选取与当前点距离最小的K个点;
(4) 确定前K个点所在类别的出现频率;
(5) 返回前K个点出现频率最高的类别作为当前点的预测分类。
代码实现就是:
def classify(inx, dataset, labels, k):# inx: 用于分类的输入向量 dataset: 训练样本集 labels: 标签向量 k : k值
datasetsize = dataset.shape[0] #: shape用于读取矩阵长度,[参数]为维数
diffmat = tile(inx, (datasetsize , 1)) - dataset # 此处使用inx构造一个和样本集一样的矩阵,从而使未知量可以和每一个已知样本进行对比,并且注意,一下进行的运算结果,其运算是单独对每一行进行运算
sqdiffmat = diffmat**2
sqdistances = sqdiffmat.sum(axis= 1)
distances = sqdistances**0.5 # 以上为求距离,即输入向量与样本的距离
sorteddistindicies = distances.argsort() # 将距离从小到大排序
classcount = {}
for i in range(k):
voteiabel = labels[sorteddistindicies[i]]
classcount[voteiabel] = classcount.get(voteiabel, 0) + 1 #统计离各标签最近K个的个数
sortedclasscount = sorted(classcount.items(), key = operator.itemgetter(1), reverse = True) # iteritems()返回一个迭代器
# sorted()用于进行排序,items()将字典以列表的形式返回,key为用于比较的维度,reverse为排序方式,默认false从小到大
return sortedclasscount[0][0]
解读一下: 注:一下在非具体实例分析时皆以找狗为例
首先:要进行对未知狗的分类,需要拉过来一个未知狗(输入向量),到你的狗圈(样本集),以及定义出什么样的是什么狗(每个狗有每个狗的狗样),以及跟几个狗(K)对比
然后使用欧式距离公式,求出未知狗和狗圈里每个狗的距离,找出最像的K个狗,看哪种狗的数量最高就是属于哪个狗了
欧式距离公式:
1.下面是一个实例:找女朋友
大致了解一下就是在一个交友网站上,根据对方几个特征而预测到底适不适合做女朋友
数据的话之后会上传到给github上
给出找女朋友的策略
(1) 收集数据:提供文本文件。
(2)_ 准备数据 : 使用python解析文本文件。
( 3 ) 分 析 数 据 :使用matplotlib画二维扩散图。
(4) 训练算法:此步驟不适用于K近邻算法。
(5) 测试算法:使用部分数据作为测试样本。 测试样本和非测试样本的区别在于:测试样本是已经完成分类的数据,如果预测分类与实际类别不同,则标记为一个错误。
(6) 使用 算 法 :产生简单的命令行程序,然后输入一些特征数据以判断对方是否为自己喜欢的类型。
首先我们分析一下数据
def file2matrix(filename):
fr = open(filename)
arrayolines = fr.readlines() #读取到文件行数
numberoflines = len(arrayolines) #得到文件行数
returnmat = zeros((numberoflines, 3)) # 创建返回的numpy矩阵,以0填充
classlabelvector = []
index = 0
for line in arrayolines:
line = line.strip() # 去除回车字符
listfromline = line.split('\t') # 进行切片 ,切片中是\t,生成一个元素列表
returnmat[index, : ]= listfromline[0:3] # 选取3个元素存储到特征矩阵中
classlabelvector.append(int(listfromline[-1])) # 将最后一列存贮到向量中
index += 1
return returnmat, classlabelvector
代码解读: 首先传过来一个文件,打开文件得到文件数量,然后创建一个等大小的0矩阵,由于文件中每个样本数据包含三个特征和一个标签,因此将特征值和标签分开
归一化数值
这里的归一化解释一下,还记得我们计算KNN的时候是按每个样本的特征值差平方和求根的吗?这里的每个特征应该是等价的(以后会有对每个特征的侧重),就拿等价来说的时候,虽然在计划上是等价的,但是由于每个特征值取值范围不同,那么很有可能就不能等价(例如:a特征的值基本都是10000左右,而b特征值都是10左右,如果直接计算的话连个特征就是不平等的,导致出现错误),因此这里要对数据做归一化处理,使数据特征值转化为0到1区间内(如果这里再有特征侧重可添加权重,但应先做归一化处理)
处理方法:
归一化方法
也就是将原数值减去最小值然后除以最大值和最小值的差
上代码:
def autonorm(dataset):
minvals = dataset.min(0) # min(0)和max(0)可从数据集中选出最小值和最大值
maxvals = dataset.max(0)
ranges = maxvals - minvals
normdataset = zeros(shape(dataset)) #读取一个和数据集一样的0矩阵
m = dataset.shape[0]
normdataset = dataset - tile(minvals, (m, 1)) # 元数据集每行将去一个最小值
normdataset = normdataset/tile(ranges, (m, 1))
return normdataset, ranges, minvals
很容易理解,就是按照上面的数学公式对数据进行处理,因为是做矩阵运算,所以要引用同等零型矩阵
测试算法:
经过KNN处理后的数据结果,我们想知道他的处理结果怎么样,这里就要进行测试,也就是评估算法正确率,
通常我们只提供已有数据的 90 %作为训练样本来训练分类器 ,而使用其余的 10% 数据去测试分类器(测试数据占总数据比例不同也会影响到算法的测试结果),且数据划分是随机的
这里我们测试的方法就是对数据进行一系列操作后(读取,归一,分类)然后与标签进行对比算出正确率
上代码:
def datingclasstest():
horatio = 0.10
datingdatamat, datinglabels = file2matrix('datingTestSet2.txt') # 获取数据
normmat, ranges, minvals = autonorm(datingdatamat) # 将数据的样本集进行归一化
m = normmat.shape[0] # 数据集0维维数
numtestvecs = int(m*horatio) # 采取10%做为测试集
errorcount = 0.0
for i in range(numtestvecs):
classifierresult = classify(normmat[i, : ], normmat[numtestvecs:m, :], # knn分类器
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 right rate is : %f" % (1-errorcount/float(numtestvecs)))
最后我们到了最后一步---使用算法:
def classifyperson():
resultlist = ['not at all', 'in small doses', 'in large deses']
percenttats = float(input("percentage of time spent playing vider games?\n\t"))
ffmiles = float(input("frequent flier miles earned per year?\n\t"))
icecream = float(input("liters of ice cream consumed per year?\n\t"))
datingdatamat, datinglabels = file2matrix('datingTestSet2.txt')
normmat, ranges, minvals = autonorm(datingdatamat)
inarr = np.array([ffmiles, percenttats, icecream])
classifierresult = classify((inarr- minvals)/ranges, normmat, datinglabels, 3)
print("you will probably like this person: ", resultlist[classifierresult -1])
这里用到了input()函数进行数值输入从而当做未知数据进行运算,最后得出结果
程序运行截图
3-NN时
5-NN时:
正确率还是不错的
到这里一个应用KNN算法的找女朋友应用就结束了,由于本人为ML初学者,因此很多内容是参考机器学习实战这本书,因此这篇文章也算是学习的一个笔记
学习ML已经快有两个月了,这是第一次真正的去接触ML算法,之前一开始都有在为ML打基础(微积分,线性代数,概率统计,ps,这些只是入门基础,而且真正的学会这些才只是入门基础,毕竟只是学了一遍这些书后的我对很多算法的数学推导还是力不从心的啊),不过,加油就是了!!!
