Python教程

K-近邻算法python

本文主要是介绍K-近邻算法python,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

                                                       k近邻算法概述

K近邻(k-Nearest Neighbor,简称kNN)算法,是一种应用很广泛的监督学习算法。它非常有效且易于掌握,其工作机制也很简单:给定测试样本,基于某种距离度量找出训练集中与其最靠近的k个训练样本,然后基于这k个"邻居"的信息来进行预测。K近邻既可以用于分类又可以用于回归,在分类问题中:我们使用"投票法",即选择这k个样本中出现最多的类别标记作为预测结果;在回归问题中:我们使用"平均法",即将这k个样本的输出的平均值作为预测结果。但是在工业界,knn被广泛应用,因此在本次介绍中,我们将着重介绍k近邻在分类方面的应用。

                                                     什么时候使用k近邻呢?

通常在评估一个算法时,我们通常看三个方面:

易于解释
时间复杂度
预测效果

                                                   k近邻算法是如何工作的呢?

我们来举个例子说明下如何用k近邻来分类爱情片和动作片。有人曾统计过很多电影的打斗镜头和接吻镜头,下图显示了6部电影的打斗镜头和接吻镜头数。假如有一部未看过的电影,如何确定它是爱情片还是动作片呢?

  

首先我们需要知道这个未知镜头存在多少个打斗镜头和接吻镜头,上图的问号位置是该未知电影出现的镜头数图形化展示,具体数字参见下表:

 

现在我们就可以利用knn来利用一种度量方式,计算未知电影与样本中其他电影的距离,如下表所示:

 

现在我们得到了样本中所有电影与未知电影的距离,将距离升序排序,可以找到离未知样本距离最近的k个顶啊应。比如说本题中取k=3,那么最靠近未知电影的三个电影分别是He's Not Really into Dudes、Beautiful Woman 和Califinia Man。K近邻算法然后按照这三部电影的类型决定未知电影的类型,而这电影全是爱情片,因此我们就判定未知电影是爱情片。

到底有哪些度量方法以及k是如何确定的呢

度量方法又叫"metric learning",这个概念在计算机视觉领域比较常见到。这种度量方法一般是距离度量,空间上有欧氏距离,路径上有曼哈顿距离,国际象棋上的一致范数:切比雪夫距离等等。一般来说需要根据不同的应用场景选择不同的度量方法。

说完了,度量方法,那么knn算法中的k到底该如何取值呢?首先我们得尝试去理解k在算法中是如何起作用的。所以我们直接在实际环境中应用k紧邻算法来说明k值得选择。
 

用python语言实现k近邻算法

其python实现如下:

from numpy import *  
import operator  
from os import listdir  
   
def classify0(inX, dataSet, labels, k):  
#inx:用于分类的输入向量
#dataSet:输入的训练样本集
#labels:标签向量
#k:选择最近邻的数目
    dataSetSize = dataSet.shape[0]  
    diffMat = tile(inX, (dataSetSize,1)) - dataSet  #行方向重复dataSetSize次,列方向1次
    sqDiffMat = diffMat**2  
    sqDistances = sqDiffMat.sum(axis=1)  
    distances = sqDistances**0.5  #求距离
    sortedDistIndicies = distances.argsort()   #排序    
    classCount={}            
    for i in range(k):  
        voteIlabel = labels[sortedDistIndicies[i]]  
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1  #字典get方法
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)  #reverse降序、iteritem返回迭代器、itemgetter(1)取value
    return sortedClassCount[0][0]  
我们从网上download一个在线约会网站的例子,一部分数据如下图所示:

 

 

其中每一行是一条会员的信息,依次为每年获得的飞行常客里程数,玩视频游戏所耗时间百分比,每周消费的冰淇淋公升数。

,我们取前两列的数据来画一个二维的散点图,如下图所示:

这里因为数据差值比较大,在应用knn算法前我们先将原始数据做一个归一化处理,将任意取值范围的特征值转化为0到1区间的值。公式如下:

归一化代码如下:

def autoNorm(dataSet):  
    minVals = dataSet.min(0)  
    maxVals = dataSet.max(0)  
    ranges = maxVals - minVals  
    normDataSet = zeros(shape(dataSet))  
    m = dataSet.shape[0]  
    normDataSet = dataSet - tile(minVals, (m,1))  
    normDataSet = normDataSet/tile(ranges, (m,1))   #element wise divide  
    return normDataSet, ranges, minVals  

测试算法

上面我们已经将knn算法实现了,那么我们怎么才能对这个算法做个评估呢?这里我们采用最原始的做法即:错误率,对于分类器来说,错误率就是分类器给出错误结果的次数除以测试数据的总数。那么我们测试数据的代码如下所示:

def datingClassTest():  
    hoRatio = 0.10      #hold out 10%  
    datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')       #load data setfrom file  
    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 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)))  
    print(errorCount)  
这里我们默认取k=3,每测试一条数据就打印输出,最后汇总错误率。log打印输出如下:

 

可以看到,分类错误总计五个,错误率为5%。

我们随机找个人的信息输入进去,测试结果如下:

K值的确定

说了这么多,我们还是没说如何确定k值。我们是这样思考的:选定训练集和对应的测试机,然后选取不同的k值,把其中错误率最低的k作为分类的k值,当有新的训练集更新时,我们再运行模型,不断迭代更新。我们用上面的例子,将k的取值范围定位3-20(一般来说k是不超过20的整数),运行结果如下:

 

最终我们确定可最佳k为7。

这篇关于K-近邻算法python的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!