CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
- 导入数据，归一化数据，距离计算，实现 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')
对于 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')
对于 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')
利用 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 分类器的一些使用场景，原理简单但是非常实用。