当前位置:   article > 正文

机器学习算法——K-近邻算法(代码实现手写数字识别)_k近邻算法实现手写数字识别

k近邻算法实现手写数字识别

0、引言,K-近邻算法是一种非常有效的分类算法,它非常有效且易于掌握。

原理:K-近邻算法通过计算不同样本之间的距离来分类物品。
使用前,我们需要有一个训练样本集,并且样本集中每个数据都存在标签,即我们知到样本集中每一数据与其所述分类的对应关系。输入没有标签的新数据,将新数据的每个特征与样本集中数据对应的特征进行比较,然后算法提取样本集中特征最相似(最近邻)的分类标签。一般来说,我们只选择样本数据集中前K个最相似的数据,这就是k-近邻算法中k的由来,通常k是不大于20的整数。最后,选择k个最相似数据中出现频率最高的分类,作为新数据的分类。

K-近邻算法

  • 优点:精度高,对异常值不敏感,无数据输入假定
  • 缺点:计算复杂度高,空间复杂度高
  • 适用的数据范围:数值型和标称型

k-近邻算法的一般流程
1、收集数据,可以使用任何办法
2、准本数据,距离计算所需要的数值,最好是结构比的数据格式
3、分析数据,可使用任何办法
4、测试算法,计算错误率
5、使用算法,首先需要输入样本数据和结构化的输出结果,然后运行k-近邻算法判定输入数据分别属于哪个分类,最后应用对计算出的分类执行后续的处理。
值得注意的是,由于算法本身的特殊性,k-近邻算法无须训练,即可直接参与分类,其计算量主要集中在计算不同样本的特征距离。

为便于测试及学习,博主将所用到的数据集放到了百度网盘上分享
链接:https://pan.baidu.com/s/1XUDa38MRpf4GjV-IpuhSIg
提取码:01gm

1、简单尝试kNN算法(K-NearestNeighbor)

对未知类别属性的数据集中每个点依次执行以下操作:
(1)计算已知类别数据集中的每个点与当前点之间的距离
(2)按照距离递增排序
(3)选取与当前点距离最小的k个点
(4)确定前k个点所在类别的出现频率
(5)返回前k个点出现频率最高的类别作为当前点的预测分类

下面给出一个简单的测试样例,其中每个样本包含两个特征

import numpy as np
import operator


def kNN_classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]

    # 计算欧式距离
    diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances ** 0.5
    sortedDistIndicies = distances.argsort()
    classCount = {}

    # 选择距离最小的k个点
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1

    # 排序
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]


def testDataSet():
    data = np.array(
        [[0.1, 0.1], [0.31, 0.15], [0.66, 0.93], [0.54, 0.89], [1.0, 0.3], [0.86, 0.21], [0.47, -0.55], [0.58, -0.31]])
    labels = ['M', 'M', 'N', 'N', 'P', 'P', 'Q', 'Q']
    return data, labels


data, labels = testDataSet()
predict = kNN_classify0([0.1, 0.5], data, labels, 4)
print("kNN predicts the [0.1,0.5] belongs to ", predict)
"""
运行结果:
kNN predict the [0.1,0.5] belongs to  M
"""
  • 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
'
运行

数据分布基本如下,可以很清楚的看出每一类的分类情况。
在这里插入图片描述

2、约会网站匹配

问题描述:
海伦一直使用某在线约会网站寻找适合自己的约会对象,尽管约会网站会推荐不同的人选,但她并不是喜欢每一个人。经过一番总结,她发现曾交往过三种类型的人:

  • 不喜欢的人
  • 魅力一般的人
  • 极具魅力的人
    另外,我们获取到了海伦的一些信息,完成对约会对象的匹配和分类,我们将按照以下流程完成该项任务。
    (1)收集数据
    (2)准备数据
    (3)分析数据
    (4)测试算法:使用海伦提供的部分数据作为测试样本.
    测试样本和非测试样本的区别在于:测试样本是已经完成分类的数据,如果预测分类与实际类别不同,则标记为一个错误
    (5)使用算法,将特征数据输入算法,判断对方时候符合海伦要求

我们了解到,海伦对于以下几种约会对象的特征比较关注

  • 每年获得的飞行常客里程数
  • 完视频游戏所耗的时间比例
  • 每周消费的冰激凌磅数

下面直接给出完整代码,注释已经较为明确:

import numpy as np
import operator
import time


def kNN_classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]

    # 计算欧式距离
    diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances ** 0.5
    sortedDistIndicies = distances.argsort()
    classCount = {}

    # 选择距离最小的k个点
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1

    # 排序
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]


def file2matrix(filename):
    """
    从文本数据读取海伦关于三个特征的数据集
    :param filename:读取以存储文本存储的海伦个人爱好数据
    :return: 读取得到的数据及标签
    """
    love_dictionary = {'largeDoses': 3, 'smallDoses': 2, 'didntLike': 1}
    fr = open(filename)
    arrayOLines = fr.readlines()
    numberOfLines = len(arrayOLines)  # 获取文件的行数
    # 为数据存储预留空间
    returnMat = np.zeros((numberOfLines, 3))
    classLabelVector = []
    index = 0
    # 读取数据
    for line in arrayOLines:
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index, :] = listFromLine[0:3]
        if (listFromLine[-1].isdigit()):
            classLabelVector.append(int(listFromLine[-1]))
        else:
            classLabelVector.append(love_dictionary.get(listFromLine[-1]))
        index += 1
    return returnMat, classLabelVector


def autoNorm(dataSet):
    """
    归一化输入的数据集,由于算法本身的特性,输入数据的极端值对计算结果影响很大,另外在本例中,由于三个数据的重要性是相同的,
    因此不同的数据不应该因为其取值范围的跨度导致对分类的影响,此种情况下,我们经常采用归一化的手段,将不同取值范围的数据归一化到 [0,1] 区间
    :param dataSet:输入获取到的数据集
    :return: 返回归一化结果
    """
    # 获取归一范围
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    normDataSet = np.zeros(np.shape(dataSet))
    m = dataSet.shape[0]
    normDataSet = dataSet - np.tile(minVals, (m, 1))
    normDataSet = normDataSet / np.tile(ranges, (m, 1))
    return normDataSet, ranges, minVals


def datingClassTest():
    """
    约会网站的改进算法,利用kNN完成海伦的需求,同时验证算法的准确性以及错误预测数
    kNN的训练和测试过程是融为一体的
    :return: none
    """
    valRate = 0.10  # 选择10%的数据作为验证集,测试其准确率
    datingData, datingLabels = file2matrix('datingTestSet2.txt')  # 利用前面的函数加载数据

    """
    打乱数据集,这样可以更客观地评价算法地准确性,利用时间作为随机数的种子,
    np.random.seed(timeseed)用于设置随机数地种子,确保对于datingDataMat,datingLabels的打乱是对应的
    """
    timeseed = int(time.time())
    np.random.seed(timeseed)
    np.random.shuffle(datingData)
    np.random.seed(timeseed)
    np.random.shuffle(datingLabels)

    normMat, ranges, minVals = autoNorm(datingData)  # 归一化数据
    m = normMat.shape[0]
    numTestVecs = int(m * valRate)
    errorNum = 0.0
    for i in range(numTestVecs):
        classifierResult = kNN_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]): errorNum += 1.0
    print("the total accuracy is: %f" % (1 - errorNum / float(numTestVecs)))
    print("error classification's numbers: ", int(errorNum))


datingClassTest()
"""
部分运行结果:
the classifier came back with: 2, the real answer is: 2
the classifier came back with: 2, the real answer is: 2
the classifier came back with: 1, the real answer is: 1
the classifier came back with: 2, the real answer is: 2
the classifier came back with: 3, the real answer is: 3
.......................................................
the classifier came back with: 2, the real answer is: 2
the classifier came back with: 2, the real answer is: 2
the classifier came back with: 1, the real answer is: 1
the total accuracy is: 0.910000
error classification's numbers:  9
"""
  • 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

我们已经利用了上述的分类器做了一个小小的测试,接下来,我们就可以输入一段个人信息,然后利用程序预测海伦对他的喜欢程度预测值了。
代码如下:

def classifyPerson():
    resultList = ['not at all', 'in small doses', 'in large doses']
    percentTats = float(input(
        "percentage of time spent playing video games?"))
    ffMiles = float(input("frequent flier miles earned per year?"))
    iceCream = float(input("liters of ice cream consumed per year?"))
    datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')
    normMat, ranges, minVals = autoNorm(datingDataMat)
    inArr = np.array([ffMiles, percentTats, iceCream, ])
    classifierResult = kNN_classify0((inArr -
                                      minVals) / ranges, normMat, datingLabels, 3)
    print("You will probably like this person: %s" % resultList[classifierResult - 1])

classifyPerson()
"""
运行结果:
percentage of time spent playing video games?>? 0.1
frequent flier miles earned per year?>? 3000
liters of ice cream consumed per year?>? 2.2
You will probably like this person: in small doses
"""
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

3、手写数字识别

0-9手写数字识别是一个非常基础的项目,机器学习可以通过多种方法实现对其的分类,由于其单个数据量较少,我们可以利用支持向量机对其多分类处理,也可以利用简单的全连接神经网络实现分类。下面,我们将利用kNN实现对0-9数据的分类,实现手写数字的识别。
在前述的百度网盘链接中,已经准备了以文本文档格式存储的手写数字,其中每个手写数字的尺寸为32*32的二值图。以文本格式将有助于我们利用kNN实现数字的识别分类。
我们将按照下述流程实现手写数字的识别与分类:
(1)收集数据:利用网盘链接中的文本文件
(2)准备数据:编写函数img2vector(),将图像格式转换为分类器使用的list格式
(3)分析数据:我们可以文本文档打开数据检查是否符合要求
(4)测试算法:编写函数使用提供的部分数据集作为测试样本,测试样本与非测试样本的区别在于测试样本是已经包含标签的数据,即已分类。
(5)使用算法识别数字

前面例子使用的分类器,我们需要将图像格式化处理为一个向量,输入分类器更方便。因此我们将把3232的二值化图像化为11024的向量。

import os


def img2vector(filename):
    """
    格式化输入的数据图像,转换为向量
    :param filename: 文本文件名称
    :return: 1*1024的数字向量
    """
    dataVect = np.zeros((1, 1024)) #预先分配一部分数据
    fr = open(filename)
    for i in range(32):
        lineText = fr.readline()
        for j in range(32):
            dataVect[0, 32 * i + j] = int(lineText[j])  # 利用偏移量使整个手写数字数据分布在数组上
    return dataVect


def handwritingClassficationTest():
    hwLabels = []
    trainingFileList = os.listdir('trainingDigits')  # 加载训练数据
    m = len(trainingFileList)
    trainingMat = np.zeros((m, 1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]  # 切分数据
        classNumStr = int(fileStr.split('_')[0])
        hwLabels.append(classNumStr)
        trainingMat[i, :] = img2vector('trainingDigits/%s' % fileNameStr)
    testFileList = os.listdir('testDigits')  # 遍历测试数据集
    errorCount = 0.0
    mTest = len(testFileList)
    for i in range(mTest):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]  # 切分数据
        classNumStr = int(fileStr.split('_')[0])
        vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)
        classifierResult = kNN_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 accuracy is: %f" % (1 - errorCount / float(mTest)))

handwritingClassficationTest()
"""
部分训练得到的结果:
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the total number of errors is: 10
the total accuracy is: 0.989429
"""
  • 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

在该数据集上,我们得到的正确率为98.9429%,改变k值,修改函数随机选取训练样本,改变训练样本的数目,都会改变kNN的准确率。
值得注意的是,该算法效率不高,且对CPU利用率不高,另一方面,如果可以利用GPU并行加速计算距离,将大大提高运算速度和效率。
k决策树是k-近邻算法优化版,也可以节省大量的计算开销。

4、小结

k近邻算法是分类数据最简单最有效的算法,我们通过约会网站改进和手写数字识别,检验了kNN的可行性及简便性。k近邻算法是基于实例的学习,使用算法时我们必须有接近实际数据的训练样本数据。
k近邻算法必须保存全部数据集,如果训练数据集很大,必须使用大量的存储空间。同时我们需要对数据集中的每个数据相互之间计算距离值,这样的算法也属于计算密集型算法,实际使用需要一定的时间。同时,kNN和其他的算法略有不同,它没有显著式的训练过程,其训练过程体现在预测阶段。
kNN还有一个缺陷,它无法给出任何数据的基础结构信息,因此我们也难以知晓平均实例样本和典型实例样本具有何种特征。这一方面,基于iD3算法的决策树优于kNN,其利用香农熵,准确且量化的反映出了各类数据的混乱程度。

后续博主还会更新k决策树,解决上述的部分缺陷,使之兼具简洁易懂与运算快捷。机器学习算法系列博文还会更新其他的机器学习算法,学习永无止境。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/1008018
推荐阅读
相关标签
  

闽ICP备14008679号