足球盘口软件
当前位置: 足球盘口软件 > 前端 >
kNN算法python实现和简单数字识别的方法,机器学习实战

简单说明

py2.7 : 《机器学习实战》 k-近邻算法 11.19 更新完毕

机器学习实战第二章kNN:

kNN算法python实现和简单数字识别的方法,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的。数据大概这个样子:

图片 1

图片 2

方法:

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程序设计有所帮助。

本文实例讲述了kNN算法python实现和简单数字识别的方法。分享给大家供大家参考。...

这个算法主要工作是测量不同特征值之间的距离,有个这个距离,就可以进行分类了。

 

参考 

简称kNN。

原文链接

from numpy import *#导入numpy库

import operator

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 classify0(inX,dataSet,labels,k):#输入待分类向量,da teSet为测试集,labels为目标结果,k为样本值

dataSetSize=dataSet.shape[0]#获取数组的行数

diffMat = tile(inX,(dataSetSize,1)) - dataSet#将inX复制dataSize行,在与dataSet相减,即(x1-x2)

sqDiffMat=diffMat**2#(x1-x2)的平方

sqDistances=sqDiffMat.sum(axis=1)#(x1-x2)^2+(y1-y2)^2

distances=sqDistances**0.5#上述结果开根号

sortedDistIndices=distances.argsort()#将数组的下标按数组从小到大的顺序排序

classCount={}#计算k个值里的类别

for i in range(k):

voteIlabel=labels[sortedDistIndices[i]]#从距离最小的类别开始统计

classCount[voteIlabel]=classCount.get(voteIlabel,0)+1#ge t表示先查看classCount中是否存在votellabel,如果存在,则获取个数,否则,返回0

sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)

return sortedClassCount[0][0]#返回统计中类别值最大的

def file2matrix(filename):#将文件转化成python可以处理的形式

fr = open(filename)#打开文件,此文件与kNN.py文件在同一目录下

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()#去enter

listFromLine = line.split('t')#根据t 将整行分割成元素列表

returnMat[index,:] = listFromLine[0:3]#赋给

classLabelVector.append(int(listFromLine[-1]))#将元素列表的最后一个元素添加到classLabelVector

index += 1#行数+1

return returnMat,classLabelVector

(由于简书显示代码模式很麻烦,决定搬家到CSDN)

已知:训练集,以及每个训练集的标签。

《机器学习实战》第二章k-近邻算法,自己实现时遇到的问题,以及解决方法。做个记录。

接下来:和训练集中的数据对比,计算最相似的k个距离。选择相似数据中最多的那个分类。作为新数据的分类。

 

python实例

1.写一个kNN.py保存了之后,需要重新导入这个kNN模块。报错:no module named kNN.

复制代码 代码如下:

解决方法:1.将.py文件放到 site_packages 目录下
            2.在调用文件中添加sys.path.append("模块文件目录");
import sys 
sys.path.append('c:xxxxb.py') # 这个例子针对 windows 用户来说的 

# -*- coding: cp936 -*-

2.上面的问题解决之后,import kNN。报错:only 2 non-keyword arguments accepted。
问题所在:貌似是粗心少写了两个中括号
   本来是array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]]),结果少写了最外面的两个中括号-_-||

#win系统中应用cp936编码,linux中最好还是utf-8比较好。
from numpy import *#引入科学计算包
import operator #经典python函数库。运算符模块。

3.继续写k-近邻算法函数,保存到kNN.py之后,输入命令:kNN.classify0([0,0],group,labels,3)

#创建数据集
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

报错:module' object has no attribute 'classify0'

#算法核心
#inX:用于分类的输入向量。即将对其进行分类。
#dataSet:训练样本集
#labels:标签向量
def classfy0(inX,dataSet,labels,k):
    #距离计算
    dataSetSize =dataSet.shape[0]#得到数组的行数。即知道有几个训练数据
    diffMat     =tile(inX,(dataSetSize,1))-dataSet#tile:numpy中的函数。tile将原来的一个数组,扩充成了4个一样的数组。diffMat得到了目标与训练数值之间的差值。
    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
    #排序
    sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]

解决方法:重启Python IDLE即可。

意外收获

 

把自己写的模块加入到python默认就有的搜索路径:在python/lib/-packages目录下建立一个 xxx.pth的文件,写入自己写的模块所在的路径即可

把代码也贴在这里吧,如果保存到电脑里,过一段时间就忘了在哪了。还是放在这里保险点.

这个算法主要工作是测量不同特征值之间的距离,有个这个距离,就可以进行分类了。 简称kNN。 已知:训练集,以及每个训练集...

kNN.py:

 

[python] view plain copy

 

  1. from numpy import *  
  2. import operator  
  3.    
  4. def createDataSet():  
  5.     group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])  
  6.     labels = ['A','A','B','B']  
  7.     return group,labels  
  8.   
  9. def classify0(inX,dataSet,labels,k):  
  10.     dataSetSize = dataSet.shape[0]  
  11.     diffMat = tile(inX,(dataSetSize,1)) - dataSet  
  12.     sqDiffMat = diffMat**2  
  13.     sqDistances = sqDiffMat.sum(axis = 1)  
  14.     distances = sqDistances**0.5  
  15.     sortedDistIndicies = distances.argsort()  
  16.     classCount = {}  
  17.     for i in range(k):  
  18.         voteIlabel = labels[sortedDistIndicies[i]]  
  19.         classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1  
  20.     sortedClassCount = sorted(classCount.iteritems(),  
  21.                               key=operator.itemgetter(1),reverse=True)  
  22.     return sortedClassCount[0][0]  

 

然后打开Python Shell:

图片 3

结果还不错。

 

 

机器学习实战k-邻近算法(kNN)简单实施代码解读(转载)

一.概念

k-邻近算法是最简单的机器学习算法之一。

k-邻近算法采用测量不同特征值之间的距离(具体说是欧氏距离)的方法进行分类。

输入待分类的数据后,计算输入特征与样本集数据对应特征的距离,选择样本集中与输入特征距离最小的前k个样本,统计这k个样本数据中出现次数最多的类别作为新数据的分类。

二.kNN的简单实施代码及注释

from numpy import *
import operator

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

def classify0(inX,dataSet,labels,k):

    #求出样本集的行数,也就是labels标签的数目
    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):
        #取第i+1邻近的样本对应的类别标签
        voteIlabel = labels[sortedDistIndicies[i]]
        #以标签为key,标签出现的次数为value将统计到的标签及出现次数写进字典
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1

    #对字典按value从大到小排序
    sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)

    #返回排序后字典中最大value对应的key
    return sortedClassCount[0][0]

三.详细解读

这里创建的是一个名为kNN.py的模块。

首先导入了两个模块,一个是科学计算包numpy,另一个是运算符模块,书中有提到。

接着是一个创建数据集的无参函数creatDataSet(),一共4个样本,每个样本有2个特征和1个分类标签。特征集以4*2的数组形式表示,类别标签集以列表的形式表示。

接下来是一个有4个参数的分类函数classify0(inX,dataSet,labels,k): 
inX表示待分类的输入特征向量, 
dataSet为样本集的特征, 
labels为样本集对应每一个样本的分类标签, 
k为选择最近距离的样本的数目。 
其中dataSet和labels由creatDataSet()函数返回。

★dataSetSize = dataSet.shape[0] 
求出样本集的行数,即样本个数,也是分类标签labels列表里元素的个数。

shape用于返回一个矩阵或数组的大小,返回的是一个元组,即(行数,列数)。如下:

>>> import kNN
>>> dataSet,labels=kNN.creatDataSet()
>>> dataSet.shape
(4, 2)
>>> dataSet
array([[ 1. ,  1.1],
       [ 1. ,  1. ],
       [ 0. ,  0. ],
       [ 0. ,  0.1]])
>>> dataSet.shape
(4, 2)
>>> dataSet.shape[0]
4
>>> dataSet.shape[1]
2
>>> type(dataSet.shape)
<class 'tuple'>

故这里, 
shape[0]即得到shape元组的第一个元素,dataSet的行数; 
shape[1]即得到shape元组的第二个元素,dataSet的列数;

当有n个特征时,欧式距离

d=(A0−B0)2+(A1−B1)2+(A2−B2)2+⋯+(An−Bn)2−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−√

由于这里只有两个特征,故简化为

d=(A0−B0)2+(A1−B1)2−−−−−−−−−−−−−−−−−−−−−√

 

★diffMat = tile(inX,(dataSetSize,1)) - dataSet 
用于构造输入特征值和样本集的差值矩阵,即每一行有两个元素,[(A0−Bi0),(A1−Bi1)],即输入样本的特征和第i个样本对应特征的差。

因为dataSet有多个样本,但inX只有一个,矩阵相减要求维数相同,故使用tile()函数,这里是将inX变为dataSetSize*1维的矩阵,每一行都是inX。

关于numpy库中tile()函数的用法,可参考

★ 
sqDiffMat = diffMat**2 
sqDistances = sqDiffMat.sum(axis=1) 
distances = sqDistances**0.5 
用于计算欧氏距离,先将差值矩阵的每一个元素平方,再按行求和,最后开方。

关于sum()函数,表示普通求和,sum(axis=1)表示每一行向量相加,sum(axis=0)表示每一列向量相加,如下:

>>> dataSet
array([[ 1. ,  1.1],
       [ 1. ,  1. ],
       [ 0. ,  0. ],
       [ 0. ,  0.1]])
>>> dataSet.sum()
4.1999999999999993
>>> dataSet.sum(axis=1)
array([ 2.1,  2. ,  0. ,  0.1])
>>> dataSet.sum(axis=0)
array([ 2. ,  2.2])

★sortedDistIndicies = distances.argsort() 
将输入特征与每个样本的欧式距离从小到大排序,返回的是样本在原欧式距离集中的序号。

接着初始化字典,用for循环处理最邻近的前k个样本,统计各类别出现的次数。

★classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 
以第i+1邻近的样本的类别标签为key,该类别标签出现的次数为value将统计到的类别标签及出现次数写进字典,将该类别出现的次数加1。

关于字典的get()方法,因为voteIlabel是key,get(voteIlabel,0)表示字典按key查找,如果存在这个key,则返回这个key的value;如果当前没有这个key,则返回0。如下:

>>> dic1 = {'color':'red','size':18,3:'good'}
>>> dic1
{'color': 'red', 3: 'good', 'size': 18}
>>> dic1.get('color')
'red'
>>> dic1.get(3)
'good'
>>> dic1.get('size',0)
18
>>> dic1.get(4,0)
0

第一次统计到一个类别标签时,由于字典中无对应的key,就返回0,表示当前没有这个类别,之后加1; 
不是第一次统计到这个类别标签时,则返回这个标签之前出现的次数,并在此基础上加1。

★sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True) 
表示按字典的value进行从大到小排序。 
第一个参数指定要排序的列表或者iterable,如果一个对象是iterable的,表示它可以被遍历;

《机器学习实战》中这一块的第一个参数使用的是classCount.iteritems(),用python3.0以后的版本会出现 
错误:AttributeError: ‘dict’ object has no attribute ‘iteritems’

python3.0不再支持dict.iteritems(),好像不能使用iteritems,改成用items()程序就顺利通过了

具体可参考官方更新文档

docs.python.org/release/3.1.3/whatsnew/3.0.html

图片 4

第二个参数是一个函数,operator.itemgetter(1)表示按字典的第二项即value排序,而不是按key排序; 
第三个参数为True表示从大到小排序。

关于Python中的sorted()函数以及operator.itemgetter()函数,可参考

★return sortedClassCount[0][0] 
最后返回排序后字典中最大的value对应的key,即对新数据分类的类别。

四.运行结果

因为上述代码为一个模块,故首先要F5 run module,然后在command window中导入该模块,再调用creatDataSet()创建样本集,此时可以查看一下样本是否创建成功,之后就可以调用classify0对新的输入进行分类了。

>>> import kNN
>>> dataSet,labels=kNN.creatDataSet()
>>> dataSet
array([[ 1. ,  1.1],
       [ 1. ,  1. ],
       [ 0. ,  0. ],
       [ 0. ,  0.1]])
>>> labels
['A', 'A', 'B', 'B']
>>> kNN.classify0([0,0],dataSet,labels,3)
'B'
返回顶部