机器学习实战之python实现kNN算法

参考书籍《机器学习实战》

图片.png

举例说明：

以二维数据简单举例：
已知数据集中含有 x1(1,1) x2(0,1)为A类，x3(1,0),x4(10,10) 为B类
判断x5(2,2) 为哪一类。
方法：定k等于3，
分别计算x5与x1、x2、x3、x4的距离，可得出前k个离x5最近的点是x1,x2,x3。其中A类的有两个，B类的有一个，因此判断x5属于A类

python中代码实现

def classify0(x,dataSet,labels,k):#定义kNN算法
    dataSetSize = dataSet.shape[0] #获取数据集的行数，即有多少个数
    diffMat = np.tile(x,(dataSetSize,1))-dataSet #将要判断类型的数据x，转化成和数据集
    #同样结构，并求出和数据集的差(想像坐标系中两个二维点的x、y之差)
    sqDiffMat = diffMat ** 2 #求x与数据集每个点差的平方(x差和y差的平方)
    sqDistances = sqDiffMat.sum(axis=1) #求出x与数据集每个点的差方和（x差的平方+y差的平方）
    distances = sqDistances ** 0.5 #求平方根（勾股定理），即为两点之间的距离
    sorteDistIndicies = distances.argsort() #返回distances中数值从小到大对应的索引值
    
    classCount = {} #统计类型，关键字为类型，值为类型的数量
    for i in range(k): #从前k个最相近的判断类型
        voteIlabel = labels[sorteDistIndicies[i]] #取出类型
        classCount[voteIlabel] = classCount.get(voteIlabel,0)+1
    sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),
                               reverse=True)
    #classCount.items()将字典转为元组，并按照key指定的方式进行排序，reverse为True，则为
    #倒序，operator.itemgetter(1)是指按照元组索引为1的值进行排序
    return sortedClassCount[0][0] #取出排序后第一个元素的类型

以上即为kNN算法的python伪代码

利用以上算法，完成书中的示例：

示例一：约会类型预测

首先来测试下错误率

file = 'datingTestSet2.txt'
def file2matrix(filename):#定义读取文件函数
    f = open(filename) 
    filelist = []
    for i in f.readlines():
        a,b,c,d = i.strip().split('\t')
        filelist.append([a]+[b]+[c]+[d]) #将读取到的信息以列表的形式存入列表
    f.close()
    filearray = np.array(filelist) #转化为np.ndarry格式（向量格式）
    returnMat = filearray[:,:-1] #构建出数据集
    classLabelVector = filearray[:,-1] #数据集对应的类型
    return returnMat,classLabelVector

def autoNorm(dataSet):#定义归一化函数
    ranges = dataSet.astype(float).max(axis=0)-dataSet.astype(float).min(axis=0)
    #这里需要留意，数据的类型必须是数值型的才能参与计算
    minVals = dataSet.astype(float).min(axis=0)
    normDataSet = (dataSet.astype(float)-minVals)/ranges
    return normDataSet,ranges,minVals

def datingClassTest(file): #定义检验函数
    p = 0.1
    datingDataMat,datingLabels = file2matrix(file)#读取数据集
    norMat,ranges,minVals = autoNorm(datingDataMat)#对数据集进行归一化
    numTestVecs = int(len(norMat)*p) #取10%的作为测试集
    errorCount = 0
    for i in range(numTestVecs):
        result = classify0(norMat[i,:],norMat[numTestVecs:,:],
                           datingLabels[numTestVecs:],3) #norMat从0到numTestVecs
        #的为测试数据，后面的为样本集
        print('the result is {},real answer is :{}'.format(result,datingLabels[i]))#输出判断过程
        if result != datingLabels[i]:
            errorCount += 1
    print('the total error tate is {}'.format(errorCount/numTestVecs))#输出最终错误率
print(datingClassTest(file))

错误率很低，可以用来进行预判

def classifyPerson(file):#定义用户使用函数
    resultList = ['not at all','in small doses','in large doses'] #类型列表
    ffMiles = float(input('输入每年获取的飞行常客里程数:'))
    percentTats = float(input('输入玩视频游戏所耗时间百分比:'))
    iceCream = float(input('输入每周消费的冰淇淋公升数:'))
    inArr = np.array([ffMiles,percentTats,iceCream]) #将输入的新数据转化为向量格式
    #注意顺序要和数据集中的顺序一致，即特征要对应上
    datingDataMat,datingLabels = file2matrix(file)
    norMat,ranges,minVals = autoNorm(datingDataMat)
    norinArr = (inArr-minVals)/ranges #将新数据进行归一化
    result = classify0(norinArr,norMat,datingLabels,3)
    print('该对象的类别是：{}'.format(resultList[result-1]))#-1是因为这里使用索引匹配

classifyPerson(file)

示例二：手写识别系统

filepath1 = 'digits/trainingDigits/' #这个为数据集目录
filepath2 = '/digits/testDigits/' #这个为测试数据目录

def img2vector(file): #读取文档，并转化为向量
    returnVect = np.zeros((1,1024))#确保每一行是一个完整的数据，因此将原维度32*32的数据改为维度是1*1024
    num = 0
    f = open(file)
    for i in f.readlines():
        ilen = int(len(i.strip()))
        returnVect[:,num:num+ilen] = list(i.strip())#以切片方式写入数据
        num += ilen
    f.close()
    return returnVect

def readfile(path):#创建数据集及类别
    filelist = os.listdir(path)
    trainingMat = np.zeros((len(filelist),1024))#创建数据集的维度
    hwLabels = []
    num = 0
    for i in filelist:
        Vect = img2vector(path+i)
        classNumstr = int(i.strip().split('_')[0])
        trainingMat[num,:] = Vect #按行循环写入数据
        hwLabels.append(classNumstr)#将类别添加进列表
        num += 1
    return trainingMat,hwLabels
        
def handwritingClassTest(file1,file2):
    trainingMat,hwLabels = readfile(filepath1)#创建数据集
    errorCount = 0
    for i in os.listdir(filepath2):
        vectorTest = img2vector(filepath2+i)#读取测试数据
        classNumstr = int(i.strip().split('_')[0])
        result = classify0(vectorTest,trainingMat,hwLabels,3)
        print('the result is {},real answer is :{}'.format(result,classNumstr))
        if int(result) != classNumstr:
            errorCount += 1
    print('the total error tate is {}'.format(errorCount/len(os.listdir(filepath2))))      
 
handwritingClassTest(filepath1,filepath2)