机器学习是一门多领域交叉学科,涉及概率论、统计学、逼近论凸分析算法复杂度理论等多门学科。专门研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织已有的知识结构使之不断改善自身的性能。 下面将介绍一种最简单的机器学习,你会发现机器学习其实没有那么神秘。

一、KNN简介

KNN—— 邻近算法,或者说K最近邻(kNN,k-NearestNeighbor) ,最简单的机器学习算法没有之一,KNN 算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别,则该样本也属于这个类别,并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 kNN方法在类别决策时,只与极少量的相邻样本有关。由于kNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,kNN方法较其他方法更为适合。

二、算法思想解析

1.核心思想

物以类聚,人以群分

2.实现过程

如下图

已知有两个含有“标签”的数据集class1和class2,它们在空间上的分布如图所示,现在我们需要知道新加入的绿色数据属于哪个数据集???根据KNN算法的核心思想,我们可以找这个数据“周围”的已知数据,看它们都属于什么数据集从而决定新数据的“标签”,那么就产生了如下问题

  • 如何刻画“周围”的概念
  • 应该找几个“周围”数据
  • 最终如何识别从属关系

2.1如何刻画“周围”的概念

我们可以通过距离的概念来刻画,选取一定数值范围内的距离来规定这些点是我的邻居或者说在我的周围,距离公式有很多,可以选取最常见的欧式距离即
$$
\rho = \sqrt{\sum_{i=1}^n(x_i-y_i)^2}
$$

2.2 应该找几个“周围”数据

这就是KNN中K的取值问题了,意思就是K个与我最近的邻居,这里的K选取如果过大会导致分类模糊,但过小又会受个例影响,波动较大

2.3 最终如何识别从属关系

这就和我们选取的K有关了,如上图,当K=1时的意思就是我与离我最近的那个数据是同一类,那么我就是属于class2,当K=5时,这个时候我应该属于哪个类???最直接的我们可以按“少数服从多数”的思想来聚类,即我属于class1,但有个问题就是如果有两个class2离我特别特别近,这个时候按道理我应该是class2才对,因此我们需要用加权平均而不是算术平均来确定,直观上可以用距离的反比来计算权重。

三、手写数字识别

1 收集数据

来自MNIST有一组著名的手写数字数据集,其中拥有近10000张训练图片和近6000张测试图片,但是下载下来的是两组特殊格式的文件,因此编写了下面的代码来获取所有图片

from array import array
import struct
import os
import png

trainimg = './mnist/train-images.idx3-ubyte'
trainlabel = './mnist/train-labels.idx1-ubyte'
testimg = './mnist/t10k-images.idx3-ubyte'
testlabel = './mnist/t10k-labels.idx1-ubyte'
trainfolder = './mnist/train'
testfolder = './mnist/test'
if not os.path.exists(trainfolder): os.makedirs(trainfolder)
if not os.path.exists(testfolder): os.makedirs(testfolder)

# open(文件路径,读写格式),用于打开一个文件,返回一个文件对象
# rb表示以二进制读模式打开文件
trimg = open(trainimg, 'rb')
teimg = open(testimg, 'rb')
trlab = open(trainlabel, 'rb')
telab = open(testlabel, 'rb')
# struct的用法这里不详述
struct.unpack(">IIII", trimg.read(16))
struct.unpack(">IIII", teimg.read(16))
struct.unpack(">II", trlab.read(8))
struct.unpack(">II", telab.read(8))
# array模块是Python中实现的一种高效的数组存储类型
# 所有数组成员都必须是同一种类型,在创建数组时就已经规定
# B表示无符号字节型,b表示有符号字节型
trimage = array("B", trimg.read())
teimage = array("B", teimg.read())
trlabel = array("b", trlab.read())
telabel = array("b", telab.read())
# close方法用于关闭一个已打开的文件,关闭后文件不能再进行读写操作
trimg.close()
teimg.close()
trlab.close()
telab.close()
# 为训练集和测试集各定义10个子文件夹,用于存放从0到9的所有数字,文件夹名分别为0-9
trainfolders = [os.path.join(trainfolder, str(i)) for i in range(10)]
testfolders = [os.path.join(testfolder, str(i)) for i in range(10)]
for dir in trainfolders:
    if not os.path.exists(dir):
        os.makedirs(dir)
for dir in testfolders:
    if not os.path.exists(dir):
        os.makedirs(dir)
# 开始保存训练图像数据
for (i, label) in enumerate(trlabel):
    filename = os.path.join(trainfolders[label], str(i) + ".png")
    print("writing " + filename)
    with open(filename, "wb") as img:
        image = png.Writer(28, 28, greyscale=True)
        data = [trimage[(i * 28 * 28 + j * 28): (i * 28 * 28 + (j + 1) * 28)] for j in range(28)]
        image.write(img, data)
# 开始保存测试图像数据
for (i, label) in enumerate(telabel):
    filename = os.path.join(testfolders[label], str(i) + ".png")
    print("writing " + filename)
    with open(filename, "wb") as img:
        image = png.Writer(28, 28, greyscale=True)
        data = [teimage[(i * 28 * 28 + j * 28): (i * 28 * 28 + (j + 1) * 28)] for j in range(28)]
        image.write(img, data)

2 实现思路

观察到图片颜色采用的是RGB模式一个像素点是一个三元组数值,因此将图片转换为灰度值并按照像素点以此读取灰度值保存为一个列表,这样我们可以将图片的数字作为字典的Key,并将所有相同Key的图片的灰度值列表append进一个大列表中作为字典的Value储存,根据上述的KNN基本思想,我们取出测试集的图片寻求合适的K并将算法得到的分类与图片本身的数字进行比较来求得算法的准确率,代码如下

'''
    训练组个数:50000张图片
    测试组个数:8000张图片
    算法:KNN
    Date:2020/2/7
    broing................
'''
from PIL import Image
import math
import time

def readImage(Path):    #读取图片灰度值
    ListOne = []
    image = Image.open(Path).convert("1")   #将图片转换为灰度值
    width, height = image.size              #获取图片宽、高
    for i in range(width):
        for j in range(height):
            ListOne.append(image.getpixel((i, j)))  #遍历所有像素点的灰度值并保存为一个列表
    return ListOne

def readData():         #读取所有训练图片灰度值并保存至dictImage
    for i in range(0,10):
        listAll = []
        path_i = str(i)
        for j in range(1,5000):
            path_j = str(j)
            path = './Data/'+path_i+'/'+path_i+' ('+path_j+').png'  #遍历训练组照片
            listAll.append(readImage(path))
        dictImage[path_i] = listAll     #按文件夹名称分类保存训练组数据

def startTest(Path):    #读取测试图片,通过KNN算法进行识别并返回识别的结果
    test = readImage(Path)  # 读取测试图片数据
    reslut = {}         # 存放与训练组比对的结果
    for i in dictImage.keys():  # dictImage.keys()=[0,1,2,3,4,5,6,7,8,9]
        list = []
        for j in dictImage[i]:  # dictImage[i]=[[~],[~],~,[~]]
            sum = 0
            for k in range(len(j)):  # k=[0,0,0,255,~,0,0]
                sum += math.pow((test[k] - j[k]),2)
            list.append(int(math.sqrt(sum)))
        list.sort()
        reslut[i] = list[0]
    #找出最小“距离”
    key = '0'
    min = reslut[key]
    for i in reslut.keys():
        if min > reslut[i]:
            key = i
            min = reslut[i]
    return key  #最小值对应的key即为识别结果

def getPro():   #批量识别测试组照片,并返回准确率
    count = 0   #记录识别正确次数
    Sum = 0     #记录识别次数
    for i in range(0,10):
        path_i = str(i)
        for j in range(1,500):
            Sum += 1
            path_j = str(j)
            path = './mnist/test/'+path_i+'/'+path_i+' ('+path_j+').png'    #遍历测试组图片
            testkey = startTest(path)
            if testkey == path_i:   #判断识别结果是否正确
                count += 1
    return count/Sum   #返回正确率

if __name__ == '__main__':
    start = time.process_time()  # 记录程序开始时间
    dictImage = {}  # 保存训练组数据
    readData()
    # Pro = getPro()
    # print('准确率:',Pro)
    print(startTest('./Data/test.png'))
    end = time.process_time()
    print('Running time:%s S' % (int(end - start)))

3 结果

运行结果如下

非常不错的准确率,就是运行时间有点长,主要是数据太多,而我又是使用最笨的方法读取图片数据,有时间一定优化一下。


只喜欢学习