kNN算法python实现和简单数字识别的方法

本文实例讲述了knn算法python实现和简单数字识别的方法。分享给大家供大家参考。具体如下：

knn算法算法优缺点：

优点：精度高、对异常值不敏感、无输入数据假定
缺点：时间复杂度和空间复杂度都很高
适用数据范围:数值型和标称型

算法的思路：

knn算法（全称k最近邻算法），算法的思想很简单，简单的说就是物以类聚，也就是说我们从一堆已知的训练集中找出k个与目标最靠近的，然后看他们中最多的分类是哪个，就以这个为依据分类。

函数解析：

库函数：

tile()
如tile(a,n)就是将a重复n次

a = np.array([0, 1, 2])
np.tile(a, 2)
array([0, 1, 2, 0, 1, 2])
np.tile(a, (2, 2))
array([[0, 1, 2, 0, 1, 2],[0, 1, 2, 0, 1, 2]])
np.tile(a, (2, 1, 2))
array([[[0, 1, 2, 0, 1, 2]],[[0, 1, 2, 0, 1, 2]]])
b = np.array([[1, 2], [3, 4]])
np.tile(b, 2)
array([[1, 2, 1, 2],[3, 4, 3, 4]])
np.tile(b, (2, 1))
array([[1, 2],[3, 4],[1, 2],[3, 4]])`

自己实现的函数

createdataset()生成测试数组
knnclassify(inputx, dataset, labels, k)分类函数

inputx 输入的参数
dataset 训练集
labels 训练集的标号
k 最近邻的数目

#coding=utf-8
from numpy import *
import operator

def createdataset():
    group = array([[1.0, 0.9], [1.0, 1.0], [0.1, 0.2], [0.0, 0.1]])
    labels = ['a','a','b','b']
    return group,labels
#inputx表示输入向量（也就是我们要判断它属于哪一类的）
#dataset表示训练样本
#label表示训练样本的标签
#k是最近邻的参数，选最近k个
def knnclassify(inputx, dataset, labels, k):
    datasetsize = dataset.shape[0]#计算有几个训练数据
    #开始计算欧几里得距离
    diffmat = tile(inputx, (datasetsize,1)) - dataset
   
    sqdiffmat = diffmat ** 2
    sqdistances = sqdiffmat.sum(axis=1)#矩阵每一行向量相加
    distances = sqdistances ** 0.5
    #欧几里得距离计算完毕
    sorteddistance = distances.argsort()
    classcount = {}
    for i in xrange(k):
        votelabel = labels[sorteddistance[i]]
        classcount[votelabel] = classcount.get(votelabel,0) + 1
    res = max(classcount)
    return res

def main():
    group,labels = createdataset()
    t = knnclassify([0,0],group,labels,3)
    print t
   
if __name__=='__main__':
    main()

knn应用实例

手写识别系统的实现

数据集：

两个数据集：training和test。分类的标号在文件名中。像素32*32的。数据大概这个样子：

方法：

knn的使用，不过这个距离算起来比较复杂（1024个特征），主要是要处理如何读取数据这个问题的，比较方面直接调用就可以了。

速度：

速度还是比较慢的，这里数据集是：training 2000+，test 900+（i5的cpu）

k=3的时候要32s+

#coding=utf-8
from numpy import *
import operator
import os
import time

def createdataset():
    group = array([[1.0, 0.9], [1.0, 1.0], [0.1, 0.2], [0.0, 0.1]])
    labels = ['a','a','b','b']
    return group,labels
#inputx表示输入向量（也就是我们要判断它属于哪一类的）
#dataset表示训练样本
#label表示训练样本的标签
#k是最近邻的参数，选最近k个
def knnclassify(inputx, dataset, labels, k):
    datasetsize = dataset.shape[0]#计算有几个训练数据
    #开始计算欧几里得距离
    diffmat = tile(inputx, (datasetsize,1)) - dataset
    #diffmat = inputx.repeat(datasetsize, aixs=1) - dataset
    sqdiffmat = diffmat ** 2
    sqdistances = sqdiffmat.sum(axis=1)#矩阵每一行向量相加
    distances = sqdistances ** 0.5
    #欧几里得距离计算完毕
    sorteddistance = distances.argsort()
    classcount = {}
    for i in xrange(k):
        votelabel = labels[sorteddistance[i]]
        classcount[votelabel] = classcount.get(votelabel,0) + 1
    res = max(classcount)
    return res

def img2vec(filename):
    returnvec = zeros((1,1024))
    fr = open(filename)
    for i in range(32):
        linestr = fr.readline()
        for j in range(32):
            returnvec[0,32*i+j] = int(linestr[j])
    return returnvec
   
def handwritingclasstest(trainingfloder,testfloder,k):
    hwlabels = []
    trainingfilelist = os.listdir(trainingfloder)
    m = len(trainingfilelist)
    trainingmat = zeros((m,1024))
    for i in range(m):
        filename = trainingfilelist[i]
        filestr = filename.split('.')[0]
        classnumstr = int(filestr.split('_')[0])
        hwlabels.append(classnumstr)
        trainingmat[i,:] = img2vec(trainingfloder+'/'+filename)
    testfilelist = os.listdir(testfloder)
    errorcount = 0.0
    mtest = len(testfilelist)
    for i in range(mtest):
        filename = testfilelist[i]
        filestr = filename.split('.')[0]
        classnumstr = int(filestr.split('_')[0])
        vectorundertest = img2vec(testfloder+'/'+filename)
        classifierresult = knnclassify(vectorundertest, trainingmat, hwlabels, k)
        #print classifierresult,' ',classnumstr
        if classifierresult != classnumstr:
            errorcount +=1
    print 'tatal error ',errorcount
    print 'error rate',errorcount/mtest
       
def main():
    t1 = time.clock()
    handwritingclasstest('trainingdigits','testdigits',3)
    t2 = time.clock()
    print 'execute ',t2-t1
if __name__=='__main__':
    main()

希望本文所述对大家的python程序设计有所帮助。