机器学习实战——KNN（K近邻算法）

首先，这篇博客是根据《机器学习实战》这本书写的，代码只是略有不同。书上的代码是python2.7版本的，我的python3.6有的用不了，各种问题。所以把我已经运行没问题的代码贴上来，再加上自己的一点注释。即是帮自己再次理解，也是帮助有可能因为问题运行不了的小伙伴。

KNN原理：根据已经有标签已经有类别的数据，凭借新输入样本与其最近的K个样本的类别来预测新输入的样本的类别。

先来书上的第一个例子，也是最简单的例子。

给定数据含有四个样本，一共有两个类。每个样本含有两个特征。

第一步：导入数据

from numpy import *
import operator     #导入需要用到的包

def creatdataset():
    group=array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])   #四个样本的特征
    labels=['A','A','B','B']    #四个样本的标签
    return group,labels

第二步：KNN算法

def classify0(inx,dataset,labels,k):     #inX是你要输入的要分类的“坐标”，dataSet是上面createDataSet的array，
                                            #就是已经有的，分类过的坐标，label是相应分类的标签，k是KNN，k近邻里面的k  
    datasetsize=dataset.shape[0]    #dataSetSize是dataSet的行数，用上面的举例就是4行
    diffmat=tile(inx,(datasetsize,1))-dataset      #前面用tile，把一行inX变成4行一模一样的（tile有重复的功能，
                                                #dataSetSize是重复4遍，后面的1保证重复完了是4行，而不是一行里有四个一样的），
                                                #然后再减去dataSet，是为了求两点的距离，先要坐标相减，这个就是坐标相减  
    sqdiffmat=diffmat**2
    sqdistances=sqdiffmat.sum(axis=1)   #axis=1是行相加，这样得到了(x1-x2)^2+(y1-y2)^2  
    distance=sqdistances**0.5     #这样求出来就是欧式距离
    
    sorteddistanceindicies=distance.argsort()    #argsort是排序，将元素按照由小到大的顺序返回下标，比如([3,1,2]),它返回的就是([1,2,0])  
    classcount={}
    for i in range(k):
        votelabel=labels[sorteddistanceindicies[i]]
        classcount[votelabel]=classcount.get(votelabel,0)+1        #求每个类别的个数，有‘A’就让'A'的计数加1
        
    sortclass=sorted(classcount.items(),key=operator.itemgetter(1),reverse=True)   #从大到小排序
    return sortclass[0][0]   #第一个就是最大的，返回最大的类别就是预测的类别

第三步：输入预测样本

group,labels=creatdataset()
classre=classify0([0,0],group,labels,3)      #要预测的样本是【0,0】这个点
print(classre)

结果是B，没什么问题。

再来第二个例子，这个例子是用三个特征的数据样本来预测约会对象。

第一步：从文件中导入数据

from numpy import *
import operator    

def filematrix(filename):
    fr=open(filename)      #打开文件
    arrayoflines=fr.readlines()    #读取文件
    numberoflines=len(arrayoflines)     #得到文件的行数
    returnmat=zeros((numberoflines,3))      #returnmat是一个numberoflines行3列的0矩阵，用来存放feature
    classlabelvector=[]        #设置一个空list来存label
    index=0
    for line in arrayoflines:     #一行一行读数据
        line=line.strip()     #截取所有回车字符
        listfromline=line.split('\t')    #将上一步得到的整行数据分割成一个列表
        returnmat[index,:]=listfromline[0:3]             #1-3列是特征列，依次将特征存放到returnmat中
        classlabelvector.append(listfromline[-1])     #最后一列也就是第4列是label列，存放到classlabelvector中
        index+=1
    return returnmat,classlabelvector    #返回特征矩阵和标签列表

第二步：归一化数据

数据已经导入了，为什么不可以想上一个例子一样直接预测呢？这里有个问题，大家打开数据就可以发现第一列和第三列都是比较小的数值，而第二列的数值则很大。如果直接用这样的数据进行预测就会出现，第二个特征所占的比重远超其他两个特征。而这种情况不是我想要的，在我眼里，这三个特征同等重要。这个怎么理解呢，就好像高考总分300，语文数学英语都是100分就显得这三门课同等重要，但是如果英语有298分，数学和语文各有一分，那么，平衡就消失了。通过综合能力考查学生的手段就不复存在了。就是这个意思。那么怎么办呢，这里呢采取归一化处理。也就是将这三门课同时压缩成0-1之间的数，这样，问题就解决了。

归一化公式：newvalue=(oldvalue-min)/(max-min)

下面代码：

#将特征值归一化
def autonorm(dataset):
    minvalue=dataset.min(0)    #每列的最小值
    maxvalue=dataset.max(0)    #每列的最大值
    ranges=maxvalue-minvalue     
    normdataset=zeros(shape(dataset))    #数据集大小的0矩阵
    m=dataset.shape[0]     #数据集行数
    normdataset=dataset-tile(minvalue,(m,1))     #数据集-m行的3列最小值
    normdataset=normdataset/tile(ranges,(m,1))   #数据集-m行的3列最大值
    return normdataset,ranges,minvalue      #返回归一化之后的数据

第三步：输入预测样本

将数据集的90%作为已有的标签样本，10%的样本作为测试样本，就可以做测试了。

#测试
def datingtest():
    horatio=0.10        
    datingdatamat,datinglabel=filematrix('datingTestSet2.txt')  #打开文件，并把特征和标签都存到相应的矩阵和列表中
    normmat,ranges,minvalue=autonorm(datingdatamat)     #得到归一化后的数据
    m=normmat.shape[0]                     #得到数据的行数
    numtestvecs=int(m*horatio)           #得到10%的测试数据
    errorcount=0                         #初始错误个数设为0
    for i in range(numtestvecs):
        classifierresult=classify0(normmat[i],normmat[numtestvecs:m,:],datinglabel[numtestvecs:m],3)    #利用分类函数得到预测类别
        print('the classifier came back with:',classifierresult,'the real answer is:',datinglabel[i])    
        if(classifierresult!=datinglabel[i]): 
            errorcount+=1                                 #如果预测类别和真实类别不等的话，错误个数+1
    print('the error rate:',(errorcount/float(numtestvecs)))         #输出错误率

datingtest()

.

.

.

可以看到错误率为5%，还算可以接受吧。

PS.datingTestSet2.txt这个文件在CSDN上就有。