Lab6 kNN应用实践 wu-kan

  • 导入数据,归一化数据,距离计算,实现 kNN 分类器
  • 实例学习 kNN 分类器如何改进约会网站,以及识别手写数字

实验目的

利用 python 实现 kNN 分类器

实验环境

硬件

所用机器型号为 VAIO Z Flip 2016

  • Intel(R) Core(TM) i7-6567U CPU @3.30GHZ 3.31GHz
  • 8.00GB RAM

软件

  • Windows 10, 64-bit (Build 17763) 10.0.17763
  • Visual Studio Code 1.39.2
    • Python 2019.10.41019:九月底发布的 VSCode Python 插件支持在编辑器窗口内原生运行 juyter nootbook 了,非常赞!
    • Remote - WSL 0.39.9:配合 WSL,在 Windows 上获得 Linux 接近原生环境的体验。
  • Windows Subsystem for Linux [Ubuntu 18.04.2 LTS]:WSL 是以软件的形式运行在 Windows 下的 Linux 子系统,是近些年微软推出来的新工具,可以在 Windows 系统上原生运行 Linux。
    • Python 3.7.4 64-bit (‘anaconda3’:virtualenv):安装在 WSL 中。

实现 kNN 分类器

导入两个模块:科学计算包 numpy 和运算符模块 operator。在构建完整的 kNN 分类器之前,需要编写一些基本的通用函数。

# 使用createDataSet()函数创建一个简单数据集合和标签,此函数包含在knn1模块中:
>>> import knn1
# 测试函数功能:创建变量group和labels
>>> group,labels=knn1.createDataSet()
#查看变量group和labels的值
>>> group
>>> labels
# 通过函数classify()实现kNN分类器
# 测试分类器功能
>>>knn1.classify([0,0],group,labels,3)

输出结果是 B,可以改变输入[0,0]为其他值,测试运行结果。

使用 kNN 改进约会网站的配对效果

利用收集的在线约会网站的约会数据,将约会网站推荐的匹配对象归入恰当的分类(不喜欢的人,魅力一般的人,极具魅力的人)。

准备数据

收集的数据存放在文本文件 datingTestSet.txt 中,每条数据占一行,总共 1000 行。主要包括 3 个特征:每年获得的飞行里程数,玩游戏视频所耗时间百分比,每周消费的冰激凌公升数。在特征数据输入分类器之前,需要将待处理数据的格式转换为分类器可以接受的格式。

# file2matrix函数解决格式输入问题,函数的输入为文件名字符串,输出为训练样本矩阵和类标签向量,该函数包含在knn2模块中。
>>> import knn2
>>> datingDataMat,datingLabels=knn2.file2matrix('datingTestSet2.txt')
>>> print(datingDataMat)
>>> datingLabels[0:20]
#使用Matplotlib创建散点图
>>> import matplotlib
>>> import matplotlib.pyplot as plt
>>> from numpy import*
>>> plt.scatter(datingDataMat[:,1],datingDataMat[:,2])>>> plt.show()
>>> plt.scatter(datingDataMat[:,1],datingDataMat[:,2], 15.0*array(datingLabels), 15.0*array(datingLabels))
'''
# 数据归一化处理
在处理不同取值范围的特征值时,通常采用的方法是将数值归一化,将取值范围处理为0到1或-1到1之间。如下公式可将任意取值范围的特征值转化为0到1区间内的值:
newValue=(oldValue-min)/(max-min),其中max和min分别是数据集中的相应维度的最大特征值和最小特征值。
'''
#函数autoNorm()将数字特征值转化为0到1的区间。
>>> normMat, ranges, minVals=knn2.autoNorm(datingDataMat)
>>> normMat
>>> ranges
>>> minVals

测试分类器

利用函数 datingClassTest()测试分类器效果:

>>> knn2.datingClassTest()

使用算法:构建完整可用系统

给用户提供程序,通过该程序用户会在约会网站上找到某个人并输出它的信息。程序会给出用户对对方喜欢程度的预测值。

#函数classifyPerson()完成此功能
>>> knn2.classifyPerson()

使用 kNN 识别手写体

实验所用到的实际图像存储在两个子目录中:目录 trainingDigits 中包含了大约 2000 个例子,命名规则如 9_45.txt,表示该文件的分类是 9,是数字 9 的第 45 个实例,每个数字大概有 200 个实例。目录 testDigits 中包含了大约 900 个测试例子。将使用目录 trainingDigits 中的数据训练分类器,使用目录 testDigits 中的数据测试分类器的效果,两组数据没有重叠。

准备数据

使用 kNN 分类器,首先要将图像处理为一个向量。实验中,将把一个32*32的二进制图像矩阵转换成1*1024的向量,为此首先要编写函数 img2vector,将图像转换为向量,该函数创建1*1024的 Numpy 数组,然后打开给定的文件,循环读出文件的前 32 行,并将每行的前 32 个字符值存储在 Numpy 数组中,最后返回数组。

构建训练数据集

函数 trainingDataTest 利用目录 trainingDigits 中的文本数据构建训练集向量,以及对应的分类标签向量(标签向量可理解为对应的文件中数字的正确分类)。由于文件名的规律命名,可编写函数 classnumCut 以实现从文件名中解析分类数字,提供分类标签。注意在程序开头写上from os import listdir以导入 listdir 函数,它可以列出给定目录的文件名。

测试算法

通过测试 testDigits 目录下的样本,计算准确率。

#handwrtingTest() 函数来实现分类器测试。每个数据文件中的数字按顺序展开成一个1024维的向量,而向量之间的距离用欧式距离。
#切换至文件knn3.py所在目录,并在cmd窗口执行
> python knn3.py

实际运行代码时,会发现 kNN 算法分类器的执行效率并不高,因为算法需要为每个测试向量计算约 2000 次欧氏距离,每个距离计算包括 1024 个维度浮点运算,全部样本要执行 900 多次,可见算法实际耗时长。另外,kNN 算法必须保存全部数据集,每次需为测试向量准备 2MB 的存储空间(2 个1024*1024矩阵的空间)。

操作练习

将 knn1 中的语句「from numpy import * 」用语句「import numpy as np」代替,修改其中对应的代码,使其能够正常执行

# -*- coding=utf-8 -*-

# 导入必要的库
import numpy as np
import operator

# 创建简单数据集


def createDataSet():
    group = np.array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
    labels = ['A', 'A', 'B', 'B']
    return group, labels

# k近邻算法


def classify(inX, dataSet, labels, k):
    # inX用于分类的输入向量
    # dataSet输入的训练样本集
    # labels为标签向量
    # k为最近的邻居数目

    # 计算距离
    dataSetSize = dataSet.shape[0]
    diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances ** 0.5
    sortedDistIndicies = distances.argsort()
    classCount = {}

    # 选择距离最小的k个点
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
    # 排序
    sortedClassCount = sorted(
        classCount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

将 knn2 中的语句「from numpy import * 」用语句「import numpy as np」代替,修改其中对应的代码,使其能够正常执行

import numpy as np
import operator
import time

# 将文本记录转换为NumPy的解析程序


def file2matrix(filename):
    fr = open(filename)
    # 得到文件行数
    arrayOfLines = fr.readlines()
    numberOfLines = len(arrayOfLines)
    # 创建返回的Numpy矩阵
    returnMat = np.zeros((numberOfLines, 3))
    classLabelVector = []
    # 解析文件数据到列表
    index = 0
    for line in arrayOfLines:
        line = line.strip()  # 注释1
        listFromLine = line.split('\t')  # 注释2
        returnMat[index, :] = listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    return returnMat, classLabelVector


# 归一化特征值
def autoNorm(dataSet):
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    # 创建一个与dataSet同大小的零矩阵
    normDataSet = np.zeros(np.shape(dataSet))
    # 数据行数
    m = dataSet.shape[0]
    # tile()函数将变量内容复制成输入矩阵同等的大小
    normDataSet = dataSet - np.tile(minVals, (m, 1))
    # 特征值相除
    normDataSet = normDataSet/np.tile(ranges, (m, 1))
    return normDataSet, ranges, minVals

# k近邻算法


def classify0(inX, dataSet, labels, k):
    # inX用于分类的输入向量
    # dataSet输入的训练样本集,
    # labels为标签向量,
    # k用于选择最近的邻居数目

    # 计算距离
    dataSetSize = dataSet.shape[0]
    diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances ** 0.5
    sortedDistIndicies = distances.argsort()
    classCount = {}
    # 选择距离最小的k个点
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
    # 排序
    sortedClassCount = sorted(
        classCount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]


# 分类器针对约会网站的测试代码
def datingClassTest(k=4, h=0.10, classify=classify0):
    # 测试样本的比例
    hoRatio = h
    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 = classify(normMat[i, :], normMat[numTestVecs:m, :],
                                    datingLabels[numTestVecs:m], k)
        print("the classifier came back with: %d, the real answer is :%d" %
              (classifierResult, datingLabels[i]))
        if (classifierResult != datingLabels[i]):
            errorCount += 1.0
    print("the total error rate is: %f" % (errorCount/float(numTestVecs)))
    return errorCount/float(numTestVecs)


def classifyPerson(classify=classify0):
    resultList = ['not at all', 'in small doses', 'in large doses']
    percentTats = float(input("percentage of time spent playing video games?"))
    ffMiles = float(input("frequent flier miles earned per year?"))
    iceCream = float(input("liters of ice cream consumed per year?"))
    datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')
    normMat, ranges, minVals = autoNorm(datingDataMat)
    inArr = np.array([ffMiles, percentTats, iceCream])
    classifierResult = classify(
        (inArr - minVals)/ranges, normMat, datingLabels, 3)
    print("You will probably like this person:",
          resultList[classifierResult - 1])

对于 knn2,测试不同 k 值对错误率的影响

from matplotlib import pyplot as plt
x = []
y = []
for kk in range(1, 30):
    y.append(datingClassTest(k=kk))
    x.append(kk)

plt.plot(x, y)
plt.xlabel('k')
plt.ylabel('error rates')

运行结果

Text(0, 0.5, 'error rates')

1

对于 knn2,使用曼哈顿距离,观察对错误率的影响

from matplotlib import pyplot as plt


def classifyManhattan(inX, dataSet, labels, k):
    # inX用于分类的输入向量
    # dataSet输入的训练样本集,
    # labels为标签向量,
    # k用于选择最近的邻居数目

    # 计算距离--曼哈顿距离

    dataSetSize = dataSet.shape[0]
    diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
    sqDiffMat = abs(diffMat)
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances
    sortedDistIndicies = distances.argsort()
    classCount = {}

    # 选择距离最小的k个点
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
    # 排序
    sortedClassCount = sorted(
        classCount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]


x = []
y = []
for kk in range(1, 30):
    y.append(datingClassTest(k=kk, classify=classifyManhattan))
    x.append(kk)

plt.plot(x, y)
plt.xlabel('k')
plt.ylabel('error rates')

运行结果

Text(0, 0.5, 'error rates')

2

对于 knn2,随机选取训练样本,测试不同样本数目对错误率的影响

from matplotlib import pyplot as plt
r1 = []
e1 = []
for i in range(1, 10):
    r = i/10
    e1.append(datingClassTest(h=1-r))
    r1.append(r)

plt.plot(r1, e1)

plt.xlabel('rate')
plt.ylabel('error rates')

运行结果

Text(0, 0.5, 'error rates')

2

利用 sklearn 实现使用 kNN 改进约会网站的配对效果,并分别比较应用 PCA 前后的效果

import numpy as np
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn import preprocessing
from sklearn.decomposition import PCA

X, y = file2matrix('datingTestSet2.txt')
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)
knn = KNeighborsClassifier()
knn.fit(X_train, y_train)
print(knn.score(X_test, y_test, sample_weight=None))

pca1 = PCA(n_components=1)
pca1.fit(X_train)
X_train_re = pca1.transform(X_train)  # 对于训练数据和测试数据进行降维到一维数据
X_test_re = pca1.transform(X_test)
knn1 = KNeighborsClassifier()
knn1.fit(X_train_re, y_train)  # 再对降维到的一维数据进行KNN算法的训练和测试准确度
print(knn1.score(X_test_re, y_test, sample_weight=None))
print(pca1.explained_variance_ratio_)

运行结果

0.815
0.815
[0.99999997]

利用 sklearn 实现使用 kNN 识别手写体应用,并分别比较应用 PCA 前后的效果

import numpy as np
from sklearn.neighbors import KNeighborsClassifier as KNN
import time
from os import listdir


def img2vector(filename):
    '''
    filename:文件名字
    将这个文件的所有数据按照顺序写成一个一维向量并返回
    '''
    returnVect = []
    fr = open(filename)
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVect.append(int(lineStr[j]))
    return returnVect

# 从文件名中解析分类数字


def classnumCut(fileName):
    '''
    filename:文件名
    返回这个文件数据代表的实际数字
    '''
    fileStr = fileName.split('.')[0]
    classNumStr = int(fileStr.split('_')[0])
    return classNumStr

# 构建训练集数据向量及对应分类标签向量


def trainingDataSet():
    '''
    从trainingDigits文件夹下面读取所有数据文件,返回:
    trainingMat:所有训练数据,每一行代表一个数据文件中的内容
    hwLabels:每一项表示traningMat中对应项的数据到底代表数字几
    '''
    hwLabels = []
    # 获取目录traningDigits内容(即数据集文件名),并储存在一个list中
    trainingFileList = listdir('trainingDigits')
    m = len(trainingFileList)  # 当前目录文件数
    # 初始化m维向量的训练集,每个向量1024维
    trainingMat = np.zeros((m, 1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]
        # 从文件名中解析分类数字,作为分类标签
        hwLabels.append(classnumCut(fileNameStr))
        # 将图片矩阵转换为向量并储存在新的矩阵中
        trainingMat[i, :] = img2vector('trainingDigits/%s' % fileNameStr)
    return hwLabels, trainingMat


def handwritingTest():
    # 构建训练集
    hwLabels, trainingMat = trainingDataSet()

    # 从testDigits里面拿到测试集
    testFileList = listdir('testDigits')

    # 错误数
    errorCount = 0.0

    # 测试集总样本数
    mTest = len(testFileList)

    # 获取程序运行到此处的时间(开始测试)
    t1 = time.time()

    # 构建kNN分类器
    neigh = KNN(n_neighbors=3, algorithm='auto')
    # 拟合模型, trainingMat为训练矩阵,hwLabels为对应的标签
    neigh.fit(trainingMat, hwLabels)

    for i in range(mTest):

        # 得到当前文件名
        fileNameStr = testFileList[i]

        # 从文件名中解析分类数字
        classNumStr = classnumCut(fileNameStr)

        # 将图片矩阵转换为向量
        vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)

        # 调用knn算法进行测试
        classifierResult = neigh.predict([vectorUnderTest])
        print("the classifier came back with: %d, the real answer is: %d" %
              (classifierResult, classNumStr))

        # 预测结果不一致,则错误数+1
        if (classifierResult != classNumStr):
            errorCount += 1.0

    print("\nthe total number of tests is: %d" % mTest)
    print("the total number of errors is: %d" % errorCount)
    print("the total error rate is: %f" % (errorCount/float(mTest)))

    # 获取程序运行到此处的时间(结束测试)
    t2 = time.time()

    # 测试耗时
    print("Cost time: %.2fmin, %.4fs." % ((t2-t1)//60, (t2-t1) % 60))


if __name__ == "__main__":
    handwritingTest()

运行结果

the total number of tests is: 946
the total number of errors is: 12
the total error rate is: 0.012685
Cost time: 0.00min, 6.6449s.

将 knn3 中的语句「from numpy import * 」用语句「import numpy as np」代替,修改其中对应的代码,使其能够正常执行

# -*- coding:utf-8 -*-

import numpy as np
import operator
import time
from os import listdir

# knn实现


def classify(inputPoint, dataSet, labels, k):
    '''
    inputPoint:待判断的点
    dataSet:数据集合
    labels:标签向量,维数和dataSet行数相同,比如labels[1]代表dataSet[1]的类别
    k:邻居数目
    输出:inputPoint的标签
    '''
    dataSetSize = dataSet.shape[0]

    # 先用tile函数将输入点拓展成与训练集相同维数的矩阵,再计算欧氏距离
    diffMat = np.tile(inputPoint, (dataSetSize, 1))-dataSet
    sqDiffMat = diffMat ** 2

    # 计算每一行元素之和
    sqDistances = sqDiffMat.sum(axis=1)

    # 开方得到欧拉距离矩阵
    distances = sqDistances ** 0.5

    # argsort返回的是数组从小到大的元素的索引
    # 按distances中元素进行升序排序后得到的对应下标的列表
    sortedDistIndicies = distances.argsort()

    # 选择距离最小的k个点,统计每个类别的点的个数
    classCount = {}
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel, 0)+1

    # 按classCount字典的第2个元素(即类别出现的次数)从大到小排序
    sortedClassCount = sorted(
        classCount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

# 将图片矩阵转换为向量


def img2vector(filename):
    '''
    filename:文件名字
    将这个文件的所有数据按照顺序写成一个一维向量并返回
    '''
    returnVect = []
    fr = open(filename)
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVect.append(int(lineStr[j]))
    return returnVect

# 从文件名中解析分类数字


def classnumCut(fileName):
    '''
    filename:文件名
    返回这个文件数据代表的实际数字
    '''
    fileStr = fileName.split('.')[0]
    classNumStr = int(fileStr.split('_')[0])
    return classNumStr

# 构建训练集数据向量及对应分类标签向量


def trainingDataSet():
    '''
    从trainingDigits文件夹下面读取所有数据文件,返回:
    trainingMat:所有训练数据,每一行代表一个数据文件中的内容
    hwLabels:每一项表示traningMat中对应项的数据到底代表数字几
    '''
    hwLabels = []
    # 获取目录traningDigits内容(即数据集文件名),并储存在一个list中
    trainingFileList = listdir('trainingDigits')
    m = len(trainingFileList)  # 当前目录文件数
    # 初始化m维向量的训练集,每个向量1024维
    trainingMat = np.zeros((m, 1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]
        # 从文件名中解析分类数字,作为分类标签
        hwLabels.append(classnumCut(fileNameStr))
        # 将图片矩阵转换为向量并储存在新的矩阵中
        trainingMat[i, :] = img2vector('trainingDigits/%s' % fileNameStr)
    return hwLabels, trainingMat


def createDataSet():
    '''
    从trainingDigits文件夹下面读取所有数据文件,返回:
    trainingMat:所有训练数据,每一行代表一个数据文件中的内容
    hwLabels:每一项表示traningMat中对应项的数据到底代表数字几
    '''
    hwLabels = []

    # 获取目录traningDigits内容(即数据集文件名),并储存在一个list中
    trainingFileList = listdir('trainingDigits')
    m = len(trainingFileList)  # 当前目录文件数

    # 初始化m维向量的训练集,每个向量1024维
    trainingMat = np.zeros((m, 1024))

    for i in range(m):

        fileNameStr = trainingFileList[i]

        # 从文件名中解析分类数字,作为分类标签
        hwLabels.append(classnumCut(fileNameStr))

        # 将图片矩阵转换为向量并储存在新的矩阵中
        trainingMat[i, :] = img2vector('trainingDigits/%s' % fileNameStr)
    return trainingMat, hwLabels

# 测试函数


def handwritingTest():

    # 构建训练集
    hwLabels, trainingMat = trainingDataSet()

    # 从testDigits里面拿到测试集
    testFileList = listdir('testDigits')

    # 错误数
    errorCount = 0.0

    # 测试集总样本数
    mTest = len(testFileList)

    # 获取程序运行到此处的时间(开始测试)
    t1 = time.time()

    for i in range(mTest):

        # 得到当前文件名
        fileNameStr = testFileList[i]

        # 从文件名中解析分类数字
        classNumStr = classnumCut(fileNameStr)

        # 将图片矩阵转换为向量
        vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)

        # 调用knn算法进行测试
        classifierResult = classify(vectorUnderTest, trainingMat, hwLabels, 5)
        print("the classifier came back with: %d, the real answer is: %d" %
              (classifierResult, classNumStr))

        # 预测结果不一致,则错误数+1
        if (classifierResult != classNumStr):
            errorCount += 1.0

    print("\nthe total number of tests is: %d" % mTest)
    print("the total number of errors is: %d" % errorCount)
    print("the total error rate is: %f" % (errorCount/float(mTest)))

    # 获取程序运行到此处的时间(结束测试)
    t2 = time.time()

    # 测试耗时
    print("Cost time: %.2fmin, %.4fs." % ((t2-t1)//60, (t2-t1) % 60))


if __name__ == "__main__":
    handwritingTest()

运行结果

the total number of tests is: 946
the total number of errors is: 17
the total error rate is: 0.017970
Cost time: 1.00min, 19.8545s.

实验总结

通过本次实验,我大致熟悉了 kNN 分类器的一些使用场景,原理简单但是非常实用。