k-近邻算法笔记（1）

作者: omuraisu | 来源:发表于2017-09-07 23:34 被阅读0次

机器学习实战—— kNN.py学习笔记
机器学习实战之K-近邻算法（二）
最“懒惰”的kNN分类算法
K近邻
学习笔记——机器学习（七）
【机器学习实战】第2章 k-近邻算法（KNN）
K-近邻算法学习及实现
机器学习笔记-k近邻算法
python之k-近邻算法（sklearn版）
k-近邻算法

学习到的第一个机器学习算法是“k-近邻算法 (kNN) ”, 它的工作原理是:
存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输人没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据(最近邻)的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处,通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

准备工作：建立训练用样本集group和其标签集labels

import numpy as np
import operator
import sys
reload(sys)
sys.setdefaultencoding('utf8')
def createDataSet():
    group=np.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):
    dataSetSize=dataSet.shape[0]#查看训练集有多少行，即有多少个实例。
    diffMat=np.tile(inX,(dataSetSize,1))-dataSet
    #将测试数据也重复扩大成训练集一样的形式
    #tile函数详细：http://blog.csdn.net/april_newnew/article/details/44176059
    sqDiffMat=diffMat**2#平方运算
    sqDistances=sqDiffMat.sum(axis=1)
    distances=sqDistances**0.5#开根运算
    sortedDistIndicies=distances.argsort()#argsort返回升序排序后的索引值。
    #关于argsort详细:http://blog.csdn.net/maoersong/article/details/21875705
    classCount={}
    for i in range(k):
        voteIlabel=labels[sortedDistIndicies[i]]#将标签向量按排序索引存储于voteIlabel中
        classCount[voteIlabel]=classCount.get(voteIlabel,0)+1#对前k个点所在类别进行出现次数统计。
        #关于get函数:http://www.runoob.com/python/att-dictionary-get.html
    sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)
    #iteritems()迭代输出字典的键值对，与item()类似，用法iter = dict.iteritems() iter.next()
    #itemgetter(1)表明按值排序，reverse=True表明降序排序。

函数的四个参数分别为：
inX：需要分类的测试数据。
dataSet：训练样本集
labels：训练样本集的标签集
k：需要取的最相近距离的个数。

两点间距离公式如下：

在约会网站数据上使用kNN算法

读取文件

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() #移除每行首尾指定字符。参数为空则移除空白符（如/d，/r，/n等)
        listFromLine=line.split('\t')
        returnMat[index,:]=listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))
        index +=1
    return returnMat,classLabelVector
datingDataMat,datingLabels=file2matrix('文件路径')

准备数据：归一化数值
归一化公式：newValue = {oldValue-min)/(max-min)

def autoNorm(dataSet):#归一化特征值函数
    minVals=dataSet.min(0) #axis=0，求每列中的最小值
    maxVals=dataSet.max(0)# 求每列中的最大值。详细参考：http://blog.csdn.net/qq_18433441/article/details/54743271
    ranges=maxVals-minVals
    normDataSet=np.zeros(np.shape(dataSet))
    m=dataSet.shape[0]#取dataSet的行数 详细参考：http://blog.csdn.net/u010758410/article/details/71554224
    normDataSet=dataSet-np.tile(minVals,(m,1))
    normDataSet=normDataSet/np.tile(ranges,(m,1))
    return normDataSet,ranges,minVals
normMat,ranges,minVals=autoNorm(datingDataMat)

3.测试算法：作为完整程序验证分类器

def datingClassTest():#训练测试
    hoRatio=0.1 #测试数据集占总数据的比例。
    datingDataMat,datingLabels=file2matrix('文件路径') #读取文件数据
    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],5)
        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))

使用算法构建完整可用系统：��

def classifyPersion():
    resultList=['not at all','in small doses','in large doses']
    persenTats=float(raw_input("percentage of time spent playing video games?"))
    ffMiles=float(raw_input("freguent flier miles earned per year?"))
    iceCream=float(raw_input("liters of ice cream consumed per year?"))
    datingDataMat,datingLabels=file2matrix('文件路径')
    normMat,ranges,minVals=autoNorm(datingDataMat)
    inArr=np.array([ffMiles,persenTats,iceCream])
    classifierResult=classify0((inArr-minVals)/ranges,normMat,datingLabels,3)
    print "You will probably like this person:",resultList[classifierResult-1]

classifyPersion()

代码里自己总结的一些小疑问。

shape[0]
函数中，shape[0]用于查看训练样本集有多少行，即有多少实例。
tile函数
用np.tile函数将测试数据重复，扩大为和训练数据集一样的大小。用这个扩大后的测试数据集和训练样本集相减，即为diffMat。
关于tile函数的具体使用参考：http://blog.csdn.net/april_newnew/article/details/44176059
**2运算
2为平方运算，0.5为开根运算
.sum(axis=1)
axis=1表示按行相加。axis=0表示按列相加。
argsort()
distances.argsort()返回升序排序后的索引值。
关于argsort（）详细用法参考：http://blog.csdn.net/maoersong/article/details/21875705
get函数
classCount.get(voteIlabel,0)返回计数字典里voteIlabel这个类别的出现次数。即键voteIlabel对应的值。还没被统计过，也就是不存在的话，返回默认值0
关于get函数的详细用法参考：http://www.runoob.com/python/att-dictionary-get.html
sorted函数
sorted函数为用于列表或者iterator的排序函数，其直接返回一个排序后的新数据，而不是对原数据进行操作。
四个参数：
classCount.iteritems() ：teritems()迭代输出字典的键值对，与item()类似
key=operator.itemgetter(1)：itemgetter(1)表明按值排序，0表明按键排序。
reverse=True：表明降序排序
itemgetter详细：http://blog.163.com/wjyydhs810@126/blog/static/162071754201411864324976/
排序详解：https://www.douban.com/note/271284737/