机器学习03:k-近邻算法拓展和总结

  • 发布时间:2017年1月9日 13:09
  • 作者:杨仕航

《机器学习实战》书中还讲了一个实例。该实例讲如何数字识别。

k-近邻算法也不太适用运用到该场景(文章后面会总结说明)。不妨可以借鉴一下,拓展我们的思路。尤其是特殊的问题如何处理和计算等等。


收集数据的步骤同样就先跳过。《机器学习实战》为我们准备了一些数据。

此处简单处理0-9的单个数字。已经将手写的数字扫描再用图形处理软件处理成32*32像素的黑白图像。再对应每个像素,若为黑,则输出1,若为白则输出0。


最终的文件可以从我网盘下载:http://pan.baidu.com/s/1qXSmxaO

解压,其中data文件夹有两个文件夹:

1)test:用于测试的数据,有946个文本文件;

2)training:用于构造训练集的数据,有1934个文本文件。

每个文本文件名称下划线前的数字表示当前文件对应识别什么数字。每个文本文件都是32行文本,每一行文本都是32个0和1的字符。


把这个data文件夹放在knn.py同个目录下(当然,最好单独创建一个文件夹放到一起)。

同样在该目录下新建一个文件,命名为recognise.py。添加如下引用:

#coding:utf-8
import numpy as np
import os
from knn import classify0 #k-近邻算法

前面博文写的knn.py文件是包含k-近邻算法的代码,可以再次拿来使用。


数据有了,我们就把数据从文件读取进来,即“准备数据”。这里需要用os遍历文件。《机器学习实战》书中的方法不是很好。

添加下面方法,代码如下:

def _readfile(filename):
    '''从文本文件中读取数据'''
    #初始化1个32*32的二维数组
    vect = np.zeros((32, 32))
    #打开文件
    with open(filename, 'r') as f:
        #读取32行
        for i in range(32):
            line = f.readline()
            #取每一行的前32个字符,并转成int列表写入vect中
            vect[i] = map(int, list(line)[:32])

    #改变二维数组尺寸,变成1*1024二维数组
    #相当于取1024一维向量,计算1024维度的距离
    return vect.reshape(1, -1)

再添加一个获取全部文件数据的方法,代码如下:

def readfiles(folder):
    '''从文件夹中读取全部数据'''
    filenames = os.listdir(folder) #获取文件列表
    m = len(filenames) #获取有多少个文件
    
    #初始化数据集
    dataset = np.zeros((m, 1024))
    labels = []
    
    #遍历文件
    for i in range(m):
        filename = filenames[i] #获取文件名
        #组合路径
        path = os.path.join(folder, filename)
        
        #写入数据集
        labels.append(int(filename.split('_')[0]))
        dataset[i] = _readfile(path)
        
    return dataset, labels

上面代码比较简单,获取每个文本文件的文件名对应的数字,再用上面写的_readfile方法读取数据。


此处,我们无需分析数据。那么就测试算法,找到最合适的k值。添加如下代码:

def test():
    '''测试算法,找到最合适的k值'''
    train_folder = r'data\training'
    test_folder = r'data\test'
    
    #获取训练集和测试集
    train_data, train_labels = get_data_from_files(train_folder)
    test_data, test_labels = get_data_from_files(test_folder)
    
    test_num = len(test_data) #测试集的个数
    k_result = {}
    
    #测试k值
    for k in range(3, 7):
        err_count = 0
        for i in range(test_num):
            result_label = classify0(test_data[i], train_data, train_labels, k)[0]
            label = test_labels[i]
            
            #判断并错误计数
            if label != result_label:
                err_count +=1
        
        #输出结果
        k_result[k] = float(err_count)/test_num)
        print("k:%s,err:%s,ratio:%f" % (k, err_count, k_result[k])
        
    #返回错误率最小的k值
    return min(k_result.iteritems(), key=lambda x:x[1])[0]

为了方便说明问题,引入time模块:

import time

加入测试代码:

if __name__ == "__main__":
    start = time.time()
    print("k=%s is best." % test())
    end = time.time()
    print(end - start)

运行该py文件,得到如下图:

测试得到,k=3错误率最小。

但发现运算的时间很久,差不多每次测试k值要20多秒。这个也是k-近邻算法的缺点。


总结一下:

k-近邻算法是分类算法中最简单最有效的算法。

使用该算法必须要有接近实际数据的训练样本且必须保存全部数据集。若训练集很大的时候,我们不得不准备大量的存储空间。而且每次计算可能比较很耗时。

k-近邻算法的另一个缺陷是它无法给出任何数据的基础结构信息,因此我们也无法知晓平均实例样本和典型实例样本具有什么特征。后面会讲如何使用概率测量方法处理分类问题,该算法可以解决这个问题。

总体来说,该算法很简单有效,用来入门特别适合。

点击查看相关目录

上一篇:我的网站搭建(第40天) 关键字和标签输入插件

下一篇:我的网站搭建(第39天) 博文随机推荐

相关专题: 机器学习实战   

评论列表

智慧如你,不想发表一下意见吗?

新的评论

清空

猜你喜欢

  • 猜测中,请稍等...