写程序学ML:K近邻(KNN)算法原理及实现(二)

2017-09-14 11:27:57来源:CSDN作者:icamera0人点击

分享

[题外话]近期申请了一个微信公众号:平凡程式人生。有兴趣的朋友可以关注,那里将会涉及更多机器学习、OpenCL+OpenCV以及图像处理方面的文章。


2.2   简单实例

为了验证前面实现的K近邻算法正确性,先设计一个简单实例。

该实例中,在code中调用函数createDataSet()创建了样本数据group及分类 labels,具体实现如下:

def createDataSet():	group = array([[1.1, 1.1], [1.0, 1.2], [0.2, 0.4], [0.9, 0.1]]) #创建4x2的数组作为训练样本	labels = ['A', 'A', 'B', 'B'] #4个训练样本所属类的标记		return group, labels

然后调用模块kNN的函数kNN.knnClassify()对应测试样本[0.2, 0]进行分类测试,其分类结果为B,符合预期。具体实现如下:

group, labels = createDataSet() #创建训练样本和对应标记realIndex = kNN.knnClassify([0.2, 0], group, labels, 3) #检测测试样本[0.2, 0]属于哪个类print realIndex

为了清楚地看到训练样本各个类别的分类情况,可以调用matplotlib绘制了样本数据的散列图。具体实现如下:

#Matplotlib 里的常用类的包含关系为 Figure -> Axes -> (Line2D, Text, etc.)#一个Figure对象可以包含多个子图(Axes),在matplotlib中用Axes对象表示一个绘图区域,可以理解为子图。fig = plt.figure() #创建图表figax = fig.add_subplot(1, 1, 1) #在图表fig中创建一个子图ax#绘制散列图,前两个参数表示x轴和y轴所要显示的数据,s表示符号大小,c表示颜色,marker表示符号类型#ax.scatter(group[:, 0], group[:, 1], s = 50, c = 'r', marker = 'o')label = list(ones(2))+list(2*ones(2)) #定义4个元素的数组#使用数组label中的值来改变s和c的值ax.scatter(group[:, 0], group[:, 1], 15.0 * array(label), 15.0 * array(label), marker = 'o')#设置坐标系x轴和y轴的上下限ax.axis([0, 2, 0, 2])ax.set_title('kNN_4_simple_group') #设置子图的的标题plt.xlabel('x_value')plt.ylabel('y_value')plt.savefig("kNN_4_simple_group.pdf")plt.show()

散列图的结果如下图所示。两个蓝色点为A类,黄色点为B类。测试样本[0.2, 0]应该为B类,这与K近邻算法的分类结果一致。



2.3   约会网站

这个实例中会对约会网站的用户信息进行分类,方便用户选择自己喜欢的约会对象。我们有1000个样本,存储在txt文件datingTestSet2.txt中。每个样本有4种信息,分别为:每年获得的飞行常客里程数、玩视频游戏所耗时间百分比、每周消费的冰淇淋公升数和样本分类。

由于样本数据存储在文本文件中,需要先从文件中读出样本数据。这里使用函数file2matrix(filename)来完成这项任务。打开文本文件,获取到样本个数,创建存储所有样本信息的二维数组returnMat,同时创建一个列表classLabelVector用来存储每个样本的分类信息。从文本文件中读取一行数据,将其分割,将前三项写入二维数组returnMat,最后一项写入classLabelVector。具体实现如下:

#从训练样本文件中读取样本信息,并将分类信息与其他数据分别存储在不同的数组中def file2matrix(filename):    fd = open(filename)    numberOfLines = len(fd.readlines()) #获取文件中样本的数目    #创建numberOfLinesx3的二维数组,并初始化为0;存储从文件中读取的样本信息的前三列    returnMat = zeros((numberOfLines, 3))     classLabelVector = [] #定义存储样本类别的列表    fd = open(filename) #重新打开文件,因为前面为了获取样本数目从文件中读取了所有样本,文件指针不在文件最前面    index = 0    for line in fd.readlines(): #从文件中循环读取每一行数据进行处理        line = line.strip() #去掉这一行前面和后面的空格        listFromLine = line.split('/t') #将数据按空格分割,本示例中将所读行数据分为4个独立数据        returnMat[index, :] = listFromLine[0 : 3] #将前3个数据存储到returnMat数组中        classLabelVector.append(int(listFromLine[-1])) #将最后一个数据,即第4个数据,转换成int类型后存储到classLabelVector最后面        index += 1    return returnMat, classLabelVector #returnMat存储样本前3列数据,classLabelVector存储样本对应的分类信息

由于样本中三个特征的单位不同,无法比较,需要将特征信息归一化。每个特征的归一化按照这个公式来完成:newValue = (oldValue - min) / (max - min)

函数autoNorm()的输入参数dataSet为Nx3的二维数组,存储着N个样本的特征值。通过函数min(0)/max(0)求得每一列,即每一种特征中最小值和最大值,然后算出特征范围差。创建与参数dataSet结构完全一样的数组并初始化为0,用来存储归一化结果。对二维数组dataSet中每一个减去该列的最小值,然后除以它们的特征范围差,完成归一化。

#对输入数组进行归一化数值处理,也叫特征缩放,用于将特征缩放到同一个范围内#本例的缩放公式为: newValue = (oldValue - min) / (max - min)def autoNorm(dataSet): #输入数组dataSet为Nx3的二维数组    minVals = dataSet.min(0) #获取数组中每一列的最小值,minVals为1x3的数组;max(0)获取每一行的最小值    maxVals = dataSet.max(0) #获取数组中每一列的最大值,maxVals为1x3的数组;max(1)获取每一行的最大值    ranges = maxVals - minVals #获取特征范围差,ranges也是1x3的数组    normDataSet = zeros(shape(dataSet)) #创建与dataSet的维数、类型完全一样的数组,并初始化为0,用于存储归一化后的结果    m = dataSet.shape[0] #获取输入数组的行数    #tile(minVals, (m, 1))创建mx1的数组,数组元素为1x3的最小值数组,其返回值为mx3的数组    #从原始数组的各个元素中,减去对应列的最小值    normDataSet = dataSet - tile(minVals, (m, 1))    #tile(ranges, (m, 1))创建mx1的数组,数组元素为1x3的特征范围差,其返回值为mx3的数组    #原始数组的各个元素除以对应列的特征范围差,完成归一化    normDataSet = normDataSet / tile(ranges, (m, 1))        return normDataSet, ranges, minVals #返回归一化后Nx3的数组、1x3的特征范围差数组和1x3的每列最小值数组

归一化后的数据就可以进行测试了。函数datingClassTest()完成测试工作。在该函数中,选择所有样本的前一半为测试样例,后一半为训练样例。先调用函数file2matrix()从样本文件datingTestSet2.txt中读出所有样例数据。然后调用函数autoNorm()对样例数据进行归一化。对测试样本从头到尾,调用函数kNN.knnClassify()依次判断其类别,然后跟真实的类别进行比对,记录错误情况,算出错误率。

#根据训练样本datingTestSet2.txt中数据对kNN分类算法进行测试def datingClassTest():    hoRatio = 0.50 #用于分割样本,将文件中获取的样本前面一半作为测试样例,后面一半作为训练样例    #从样本文件datingTestSet2.txt中读取所有样例数据及分类信息    datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')    #将样本数据进行归一化处理    normMat, ranges, minVals = autoNorm(datingDataMat)        m = normMat.shape[0] #获取归一化后二维数组的行数,即所有样本的数目    numTestVecs = int(m * hoRatio) #获取测试样本的数目,为所有样本的一半    errorCount = 0.0 #记录分类错误的次数    for i in range(numTestVecs): #依次循环,从前一半样本中获得每一个样本,跟后面一半样本进行比对,寻找最近邻样本        classifierResult = kNN.knnClassify(normMat[i, :], normMat[numTestVecs : m, :], datingLabels[numTestVecs : m], 3)        #print "the classifier case back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i])        if (classifierResult != datingLabels[i]): #如果分类结果与从文件中读取的值不一致,则判为分类错误            errorCount += 1.0            print "the classifier case back with: %d, the real answer is: %d, index: %d" % (classifierResult, datingLabels[i], i)    print "the total error rate is: %f" % (errorCount / float(numTestVecs)) #打印出错误率    print errorCount #返回错误次数

2.4  手写体识别

这里构建的手写识别系统只能识别数字0到9。需要识别的数字已经使用图形处理软件,处理成具有相同色彩和大小:宽高是32像素x32像素的黑白图像。尽管采用文本格式存储图像不能有效地利用内存空间,但是为了方便理解,我们还是将图像转换为文本格式。

该实例中有两个文件夹存储样本文件,目录trainingDigits中包含了大约2000个例子,每个数字大约有200个样本;目录testDigits中包含了大约900个测试数据。我们使用目录trainningDigits中的数据训练分类器,使用目录testDigits中的数据测试分类器的效果。

首先,需要读取样本文件,将其转换为1x1024的数组。在样本文件中存储了32行32列的数字,来模拟图像数据。函数img2vector(filename)从文本文件中读取其前32行,每一行读取32个字符,将其转换为整型数字,存储在1x1024的数组中。

#将文件中读取的数字字符转换为整型数字,存储在一维数组中def img2vector(filename):    returnVect = zeros((1, 1024)) #创建1x1024的一维数组,并初始化为0    #打开文件从中读取32行数据,并将每一行的32个byte转化为整型数字    fd = open(filename)     for i in range(32):        lineStr = fd.readline() #读取一行数据        for j in range(32):            returnVect[0, 32 * i + j] = int(lineStr[j]) #每个byte转换为整型数字    return returnVect

函数handwritingClassTest()完成手写识别工作。它从训练样本目录trainingDigits读取所有的样本文件,从文件名称中解析出每个样本的类别,即0-9。然后打开文件,读取32x32的字符转换成1x1024的一维数组保存起来。

读取测试样本目录testDigits下的测试样本,同样获取样本的类别以及样本的内容。将测试样本从第一个开始,调用函数kNN.knnClassify()依次与训练样本进行分类测试。统计分类错误的情况,算出错误率。

def handwritingClassTest():    hwLabels = [] #定义存储训练样本类别标记的列表变量    #listdir(): 返回指定的文件夹包含的文件或文件夹的名字的列表。这个列表以字母顺序。 它不包括 '.' 和'..' 即使它在文件夹中。    #目录trainingDigits下面存放着所有的训练样本文件,listdir获取这些文件名将其存储在列表变量trainingFileList中    trainingFileList = listdir('trainingDigits')    m = len(trainingFileList) #获取文件列表中的文件个数    trainingMat = zeros((m, 1024)) #创建mx1024的二维数组且初始化为0,存储训练样本的内容;每个样本1024个byte    for i in range(m): #逐个从样本文件中读取内容转换成整型存储在二维数组trainingMat中        fileNameStr = trainingFileList[i] #获取第i个样本的文件名0_3.txt,表示数字0的第3个样本文件        fileStr = fileNameStr.split('.')[0] #获取样本文件名称0_3        classNumStr = int(fileStr.split('_')[0]) #获取该样本对应的数字类别,即0        hwLabels.append(classNumStr) #将样本的数字类别存储在列表变量hwLabels中        #将文件trainingDigits/0_3.txt读取出来,并将其内容转换为整型数字存储在二维数组trainingMat第i个元素中        trainingMat[i, :] = img2vector('trainingDigits/%s' % fileNameStr)    testFileList = listdir('testDigits') #测试样本存放在testDigits目录下,获取测试样本的文件名列表    errorCount = 0.0    mTest = len(testFileList) #获取测试样本的个数    for i in range(mTest): #对测试样本,逐个进行检测        fileNameStr = testFileList[i] #获取第i个测试样本,如0_1.txt        fileStr = fileNameStr.split('.')[0] #获取文件名0_1        classNumStr = int(fileStr.split('_')[0]) #获取样本的数字类别0        #将文件testDigits/0_1.txt读取出来,并将其内容转换为整型数字存储在1x1024的数组vectorUnderTest中        vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)        #将vectorUnderTest与之前的训练样本逐一进行比较,获取最近邻的3个样本,        #返回这3个样本中类别最多的那个类别,作为该测试样本的类别        classifierResult = kNN.knnClassify(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 "the classifier came back with: %d, the real answer is: %d" /                  % (classifierResult, classNumStr)    print "/nthe total number of errors is: %d" % errorCount #打印出错误数量    print "/nthe total error rate is: %f" % (errorCount / float(mTest)) #打印出错误率

3、小结

K近邻算法是分类数据最简单最有效的算法,这里通过三个例子讲述了如何使用K近邻算法构造分类器。K近邻算法是基于实例的学习,使用算法时我们必须有接近实际数据的训练样本数据。K近邻算法必须保存全部数据集,如果训练数据集很大,必须使用大量的存储空间。此外,由于必须对数据集中的每个数据计算距离值,实际使用时可能非常耗时。

本文中涉及的所有code可以访问如下目录获取:

https://github.com/stevewang0/MLInAction


(完)

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台