• 机器学习笔记 十四：k-近邻算法（kNN）的实现

    目录

    1. 什么是机器学习

    简单地说，机器学习就是把无序的数据转换成有用的信息。主要任务就是分类

    机器学习的应用：
    在这里插入图片描述
    机器学习算法：

    在这里插入图片描述

    机器学习会涉及很多统计学的知识，我认为机器学习可以等同于统计学，比如对于一件事情都评价，我们每个人的标准都是不一样的，所以最后得到的评价模型也是不一样的，这个时候就需要结合统计学的知识，通过大量的例子，从中找到共性，来构建我们的模型。

    2. k-近邻算法（kNN）

    k-近邻算法采用测量不同特征值之间的距离方法进行分类：
    在这里插入图片描述备注： 一般来说，只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。

    2.1 kNN的原理

    通过图片进行解释，第一张图片是通过两个特征构建的一个坐标系（接吻镜头和打斗镜头），在此我们需要预测问号电影属于哪一个类别的电影，所以由第二张图可以绘制出他的坐标位置，并建立它与其他已知坐标点之间的距离，可以得到第三张图。我们假设 k=3 ，通过前3部电影的类型，我们可以预测出未知电影的类型为爱情片。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    2.2 k-近邻算法的一般流程

    (1) 收集数据： 可以使用任何方法。
    (2) 准备数据： 距离计算所需要的数值，最好是结构化的数据格式。
    (3) 分析数据： 可以使用任何方法。
    (4) 训练算法： 此步骤不适用于k-近邻算法。
    (5) 测试算法： 计算错误率。
    (6) 使用算法： 首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。

    2.3 kNN伪代码

    (1) 计算已知类别数据集中的点与当前点 （未知点） 之间的距离；
    (2) 按照距离递增顺序排列；
    (3) 选取与当前点 （未知点） 距离最小的k个点；
    (4) 确定前k个点所在类别的出现频率；
    (5) 返回前k个点出现频率最高的类别作为当前点的预测分类。

    3. 函数介绍

    3.1 get()函数：利用字典统计列表中元素出现次数

    ls=['a','b','c','d','a']

cou={} #创建一个空字典
for i in ls:
    cou[i]=cou.get(i,0)+1     #之后称其为get的赋值语句，目的是新建字典键值对
    
    '''
    赋值语句代码等价于
    cou[i]=0
    cou[i]=cou[i]+1
    '''
print(cou)

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    输出结果：

    {'a': 2, 'b': 1, 'c': 1, 'd': 1}

    • 1

    cou[i]=cou.get(i,0)+1 ： 从逻辑上执行了两次，而这两次里get语句每次执行时的功能是不一样的：

    • 第一次： cou[i]=cou.get(i,0)+1（i=‘aa’）
      此时get语句的功能为赋初值，即把键’a’的初值置为0然后加1

    • 第二次： cou[i]=cou.get(i,0)+1（i=‘aa’）
      因get语句已经作为赋值语句出现过一次了，因此此时再执行这条语句时，赋值功能已经无效了，也就是get语句里第二个参数对’a’这个键已经无效了，所以这条语句此时可等价为：cou[i]=cou.get(i)+1

    3.2 strip()函数

    strip() 用于移除字符串头尾指定的字符（默认为空格或换行符）或字符序列。

    str = "0000000this is string example....wow!!!0000000"

print (str.strip( '0' ))

    • 1
    • 2
    • 3

    输出结果：

    this is string example....wow!!!

    • 1

    3.3 python中使用matplotlib时，其中的add_subplot(111)含义

    绘制网格图，而三个参数的含义如下：
    1.第一个参数和第二个参数表示网格的个数
    2.第三个参数表示第几个子图

    例如：

    • 111： 表示整个网格只有一个（1*1），那么子图也只有一个，所以当前两个参数都是1的时候，第三个参数只能是1
    • 221-222-223-224：第一个参数和第二个参数表示整个网格有 4 个 （2*2） ，也就是4个子图，可以按坐标系进行理解，一共4个区域。那么最后一个参数表示第几个子图，显然一共有4个子图，就看你怎么排版。

    3.4 tile()：把数组沿各个方向复制

    比如 a = np.array([0,1,2])， np.tile(a,(2,1)) 就是把a先沿x轴复制1倍，即没有复制，仍然是 [0,1,2]。 再把结果沿y方向复制2倍，即最终得到
    array([[0,1,2], [0,1,2]])
    在这里插入图片描述

    3.5 min(0),max(0)

    min(0)返回该矩阵中每一列的最小值
    min(1)返回该矩阵中每一行的最小值
    max(0)返回该矩阵中每一列的最大值
    max(1)返回该矩阵中每一行的最大值

    4. kNN实现

    数据集：

    在这里插入图片描述

    '''
Created on July 27, 2022
kNN: k Nearest Neighbors

Input:      inX: 输入向量 (1xN)
            dataSet: 训练样本集 (NxM)
            labels: 标签向量 (1xM vector)
            k: 最近邻居数目 (should be an odd number)

Output:     the most popular class label

@author: amyniez
'''

from numpy import *
import operator
from os import listdir


def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    
    ## 欧式距离计算
    diffMat = tile(inX, (dataSetSize, 1)) - dataSet
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances ** 0.5
    sortedDistIndicies = distances.argsort()   # 获取排列的位置索引

    ## 选择距离最近都k个点
    # 统计列表中每个元素出现次数
    classCount = {}   # 创建空字典
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1     # 新建字典键值对，赋予初始值为0
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)   # 创建一个迭代器,获取容器中第1维的数据
    return sortedClassCount[0][0]


def createDataSet():
    group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
    labels = ['A', 'A', 'B', 'B']
    return group, labels


# 文本文件格式转换为矩阵
def file2matrix(filename):
    fr = open(filename)
    numberOfLines = len(fr.readlines())         #get the number of lines in the file
    returnMat = zeros((numberOfLines,3))        #prepare matrix to return
    classLabelVector = []                       #prepare labels return
    fr = open(filename)
    index = 0
    for line in fr.readlines():
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index,:] = listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    return returnMat,classLabelVector


# 归一化处理
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))     # tile复制数据集为1000*3，m代表行扩大m倍，1代表列
    normDataSet = normDataSet / tile(ranges, (m, 1))  # element wise divide
    return normDataSet, ranges, minVals


def datingClassTest():
    hoRatio = 0.50  # hold out 10%
    datingDataMat, datingLabels = file2matrix('TestSet1.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)


def img2vector(filename):
    returnVect = zeros((1, 1024))
    fr = open(filename)
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVect[0, 32 * i + j] = int(lineStr[j])
    return returnVect


def handwritingClassTest():
    hwLabels = []
    trainingFileList = listdir('trainingDigits')  # load the training set
    m = len(trainingFileList)
    trainingMat = zeros((m, 1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]  # take off .txt
        classNumStr = int(fileStr.split('_')[0])
        hwLabels.append(classNumStr)
        trainingMat[i, :] = img2vector('trainingDigits/%s' % fileNameStr)
    testFileList = listdir('testDigits')  # iterate through the test set
    errorCount = 0.0
    mTest = len(testFileList)
    for i in range(mTest):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]  # take off .txt
        classNumStr = int(fileStr.split('_')[0])
        vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)
        classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
        print("the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr))
        if (classifierResult != classNumStr): errorCount += 1.0
    print("\nthe total number of errors is: %d" % errorCount)
    print("\nthe total error rate is: %f" % (errorCount / float(mTest)))


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    import kNN
import matplotlib
import matplotlib.pyplot as plt


group, lables = kNN.createDataSet()

Matr, Labels = kNN.file2matrix('TestSet1.txt')

fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(Matr[:,1], Matr[:,2])
plt.show()

normSet, ranges, minVals = kNN.autoNorm(Matr)
kNN.datingClassTest()

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    图像显示：
    在这里插入图片描述
    分类精读：
    在这里插入图片描述

  • 相关阅读:
    操作系统学习笔记---计算机系统概述
    如何测试微信公众号？
    小米汽车SU7全色系H5自适应展示源码
    Ajax 使用流程详解
    连续六个季度实现盈利改善，达达集团内外双重确定性凸显
    Handler-源码分析
    NFNet：NF-ResNet的延伸，不用BN的4096超大batch size训练 | 21年论文
    条件编译总报错，该如何解决？
    node.js的安装和使用（保姆教程）
    【Docker】将自定义的镜像上传至dockerhub或阿里云私有仓库，并在其他节点进行拉取
  • 原文地址：https://blog.csdn.net/amyniez/article/details/126011190