K近邻算法实例
一、实验目的
1、理解K近邻算法中距离的度量、K值得选取和分类决策规则的确定;
2、掌握用K近邻模型对所给的实例进行正确分类的方法;
3、掌握K近邻相关数据结构并能熟练运用Python编写程序。
二、实验要求
1、读代码,学python。要求能读懂所给代码,能改写代码实现其它类似算法
2、运行结果要截图并对结果做分析;
3、所有内容汇总到本文档,无需提供.py文件;
三、实验内容
- 阅读代码并进行注释
- 用KNN算法改进约会网站的配对效果
海伦女士一直使用在线约会网站寻找适合自己的约会对象。尽管约会网站会推荐不同的任选,但她并不是喜欢每一个人。经过一番总结,她发现自己交往过的人可以进行如下分类:不喜欢的人、魅力一般的人 、极具魅力的人
海伦收集约会数据已经有了一段时间,她把这些数据存放在文本文件datingTestSet.txt中,每个样本数据占据一行,总共有1000行。
海伦收集的样本数据主要包含以下3种特征:每年获得的飞行常客里程数、玩视频游戏所消耗时间百分比、每周消费的冰淇淋公升数
将数据集的部分当作训练集,其余作为测试集,通过KNN算法进行分类预测,将预测结果输出并与真实结果对比,计算分类错误率。
四、实验过程(原理,源码)
KNN算法理解:
KNN 算法采用测量不同特征之间的距离方法进行分类,通俗的讲就是:给定一个样本数据集,并且样本集中每个数据都存在标签,即我们知道样本集中每个数据与所属分类的对应关系。对新输入没有标签的实例,在训练数据集中找到与该实例最邻近的 k 个实例,这 k 个实例的多数属于某个类,就把该输入实例分为这个类。
1.阅读并对代码进行注释
要实现手写数字识别,首先需要将二进制图像转化为向量,通过构造一个函数,将3232的01串连接起来,输出11204的向量。然后通过KNN算法,计算训练集元素之间的距离并进行分类。最后是将手写数字识别的训练集和测试集进行导入,将预测结果输出并与真实结果对比,算出分类的错误率。
通过对代码按照上述思路进行分析并添加注释:
首先是构造一个函数将3232转换为11024的向量
"""
img2vector 函数说明:将32*32的二进制图像矩阵转换成1*1024的向量
Parameters:
filename - 二进制图像文件名
Returns:
returnVect - 1*1024的向量
"""
def img2vector(filename):
returnVect = np.zeros((1, 1024)) #zeros(shape, dtype=float, order='C') 返回一个给定形状和类型的用0填充的数组;
fr = open(filename) #读取二进制图像文件
for i in range(32): #32行
lineStr = fr.readline()
for j in range(32): #32列
returnVect[0, 32*i+j] = int(lineStr[j])
return returnVect #返回1*1024的向量
下面是KNN算法函数,通过输入训练集数据、分类标准、和K值,返回分类结果
"""
classify0函数说明:knn算法,分类器
Parameters:
inX - 用于分类的数据(测试集)
dataSet - 用于训练的数据(训练集)(n*1维列向量)
labels - 分类标准(n*1维列向量)
k - kNN算法参数,选择距离最小的k个点
Returns:
sortedClassCount[0][0] - 分类结果
"""
def classify0(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[0] # numpy函数shape[0]返回dataSet的行数
# 测量欧氏距离
diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet #将inX重复dataSetSize次并排成一列
sqDiffMat = diffMat**2 #二维特征相减后平方(用diffMat的转置乘diffMat)
sqDistances = sqDiffMat.sum(axis=1) #sum()所有元素相加,sum(0)列相加,sum(1)行相加
distances = sqDistances**0.5 #开方,计算出距离
sortedDistIndicies = distances.argsort() # 将距离从小到大进行排序;argsort函数返回的是distances值从小到大的索引值
classCount = {} #定义一个记录类别次数的字典
for i in range(k): # 选取前K个最短距离, 选取这K个中最多的分类类别
voteIlabel = labels[sortedDistIndicies[i]] #取出前k个元素的类别
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1 #字典的get()方法,返回指定键的值,如果值不在字典中返回0;计算类别次数
sortedClassCount = sorted(classCount.items(),
key=operator.itemgetter(1), reverse=True) #reverse降序排序字典
return sortedClassCount[0][0] #返回次数最多的类别,即所要分类的类别
最后是将手写数字识别的训练集导入,并对测试集进行分类,
"""
handwritingClassTest函数说明:进行手写数字识别
"""
def handwritingClassTest():
hwLabels = []
trainingFileList = listdir('trainingDigits') #导入训练集,trainingFileList是训练集各个文件;listdir(path)返回指定路径path下的文件和文件夹列表
m = len(trainingFileList) #训练集的文件个数
trainingMat = np.zeros((m, 1024)) #各个文件变成一行之后的整合矩阵
for i in range(m):
fileNameStr = trainingFileList[i] #fileNameStr单个文件名,训练集的每个文件
fileStr = fileNameStr.split('.')[0] #去除.txt后缀,fileStr取分开后的第一个元素
classNumStr = int(fileStr.split('_')[0]) #classNumStr记录这个数字是什么
hwLabels.append(classNumStr)
trainingMat[i, :] = img2vector('trainingDigits/%s' % fileNameStr) #将训练集的32*32的二进制图像矩阵转换成1*1024的向量
# 导入测试集
testFileList = listdir('testDigits') #iterate through the test set
errorCount = 0.0 #定义错误数量
mTest = len(testFileList) #测试集的数量
for i in range(mTest): #对每个测试集的个体进行识别
fileNameStr = testFileList[i] #测试集的每个文件
fileStr = fileNameStr.split('.')[0] #去除.txt后缀
classNumStr = int(fileStr.split('_')[0]) #训练集中正确的结果
vectorUnderTest = img2vector('testDigits/%s' % fileNameStr) #将测试集的32*32的二进制图像矩阵转换成1*1024的向量
classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3) # 通过knn算法识别对testdigis数据进行猜测的结果
print("分类的结果: %d, 真实结果: %d" % (classifierResult, classNumStr)) #输出训练集的模拟结果和真实结果
if (classifierResult != classNumStr): errorCount += 1.0 #当测试结果和训练结果不同时,错误数量+1
print("\n分类错误数量: %d" % errorCount) #输出模拟识别错误的数量
print("\n分类错误率: %f" % (errorCount/float(mTest))) #输出错误率
上面最后几行代码是将模拟分类的结果和真实结果进行对比,并计算识别错误的数量和错误率。
下面是运行的结果(不太习惯英文输出,改成了中文):
测试集中有946个数据,分类错误的有10个,则错误率为0.10571
2.用KNN算法改进约会网站的配对效果
题目背景:
海伦女士一直使用在线约会网站寻找适合自己的约会对象。尽管约会网站会推荐不同的任选,但她并不是喜欢每一个人。经过一番总结,她发现自己交往过的人可以进行如下分类:
不喜欢的人 didntLike、魅力一般的人 smallDoses 、极具魅力的人 largeDoses
海伦收集约会数据已经有了一段时间,她把这些数据存放在文本文件datingTestSet.txt中,每个样本数据占据一行,总共有1000行。
海伦收集的样本数据主要包含以下3种特征:
每年获得的飞行常客里程数、玩视频游戏所消耗时间百分比、每周消费的冰淇淋公升数
将数据集的部分当作训练集,其余作为测试集,通过KNN算法进行分类预测,将预测结果输出并与真实结果对比,计算分类错误率。
首先第一个函数是KNN算法,与上面代码的KNN算法函数代码相同这里就略去了
"""
函数说明:kNN算法,分类器
Parameters:
inX - 用于分类的数据(测试集)
dataSet - 用于训练的数据(训练集)(n*1维列向量)
labels - 分类标准(n*1维列向量)
k - kNN算法参数,选择距离最小的k个点
Returns:
sortedClassCount[0][0] - 分类结果
"""
然后需要有一个函数将数据集文件进行解读并进行分类
"""
函数说明:打开解析文件,对数据进行分类,1代表不喜欢,2代表魅力一般,3代表极具魅力
Parameters:
filename - 文件名
Returns:
returnMat - 特征矩阵
classLabelVector - 分类label向量
"""
def file2matrix(filename):
fr = open(filename) #打开文件
arrayOlines = fr.readlines() #读取文件所有内容
numberOfLines = len(arrayOlines) #文件行数
returnMat = np.zeros((numberOfLines, 3)) #返回的NumPy矩阵numberOfLines行,3列
classLabelVector = [] #创建分类标签向量
index = 0 #行的索引值
# 读取每一行
for line in arrayOlines:
# 去掉每一行首尾的空白符,例如'\n','\r','\t',' '
line = line.strip()
listFromLine = line.split('\t') #将每一行内容根据'\t'符进行切片,本例中一共有4列
returnMat[index, :] = listFromLine[0:3] #将数据的前3列进行提取保存在returnMat矩阵中,也就是特征矩阵
# 根据文本内容进行分类1:不喜欢;2:一般;3:喜欢
if listFromLine[-1] == 'didntLike':
classLabelVector.append(1)
elif listFromLine[-1] == 'smallDoses':
classLabelVector.append(2)
elif listFromLine[-1] == 'largeDoses':
classLabelVector.append(3)
index += 1
return returnMat, classLabelVector #返回标签列向量以及特征矩阵
由于三个特征值的数量级不同,飞行公里数几万公里,冰激凌数量只有零点几公升。为了让这些数据具备可比性,需要采用标准化方法来消除这些差异。这里采用的是min-max标准化归一方法。对原始数据的线性变换,使结果落到[0,1]区间,转换函数如下:其中max为样本数据的最大值,min为样本数据的最小值,令x = (x−min)/(max−min)
下面为归一化函数
"""
函数说明:对数据进行归一化 min-max标准化
Parameters:
dataSet - 特征矩阵
Returns:
normDataSet - 归一化后的特征矩阵
ranges - 数据范围
minVals - 数据最小值
"""
def autoNorm(dataSet):
minVals = dataSet.min(0) #获取数据的最小值
maxVals = dataSet.max(0) #获取数据的最大值
ranges = maxVals - minVals #最大值和最小值的范围
normDataSet = np.zeros(np.shape(dataSet)) #shape(dataSet)返回dataSet的矩阵行列数
m = dataSet.shape[0] #numpy函数shape[0]返回dataSet的行数
normDataSet = dataSet - np.tile(minVals, (m, 1)) #原始值减去最小值(x-xmin)
normDataSet = normDataSet / np.tile(ranges, (m, 1)) #差值处以最大值和最小值的差值(x-xmin)/(xmax-xmin)
return normDataSet, ranges, minVals #归一化数据结果,数据范围,最小值
最后是导入数据集进行分类测试,这里是采取的使用数据集中的后90%为训练集进行分类训练,剩余数据为测试集进行测试。将模拟分类的结果和真实结果进行对比,并计算识别错误的数量和错误率。
"""
函数说明:分类器测试函数
Returns:
normDataSet - 归一化后的特征矩阵
ranges - 数据范围
minVals - 数据最小值
"""
def datingClassTest():
filename = "datingTestSet.txt" #打开数据集文件
datingDataMat, datingLabels = file2matrix(filename) #将返回的特征矩阵和分类向量分别存储到datingDataMat和datingLabels中
hoRatio = 0.10 #取所有数据的10% hoRatio越小,错误率越低
normMat, ranges, minVals = autoNorm(datingDataMat) #数据归一化,返回归一化数据结果,数据范围,最小值
m = normMat.shape[0] #获取normMat的行数
numTestVecs = int(m * hoRatio) #数据集中10%的个数
errorCount = 0.0 #分类错误的计数
for i in range(numTestVecs):
# 前numTestVecs个数据作为测试集,后m-numTestVecs个数据作为训练集
# k选择label数+1(结果比较好)
classifierResult = classify0(normMat[i, :], normMat[numTestVecs:m, :],
datingLabels[numTestVecs:m], 7)
print("分类结果:%d\t真实类别:%d" % (classifierResult, datingLabels[i])) #输出分类的结果和真实结果
if classifierResult != datingLabels[i]: #分类结果与真实结果不同时,错误计数+1
errorCount += 1.0
print("\n分类错误数量: %d" % errorCount) # 输出模拟识别错误的数量
print("错误率:%f%%" % (errorCount / float(numTestVecs) * 100)) #输出错误率
下图为运行结果
参考
机器学习算法-KNN代码实现https://blog.csdn.net/weixin_47156261/article/details/122244380
数据归一化方法https://blog.csdn.net/xinghuanmeiying/article/details/91873329
机器学习 | KNN算法详解及代码https://zhuanlan.zhihu.com/p/484029409
机器学习实战 – Task01. K邻近http://www.360doc.com/content/20/0817/17/71178898_930801597.shtml
机器学习实战 手写识别系统https://blog.csdn.net/qq_36895331/article/details/109000266
https://blog.csdn.net/xiaoyun5555/article/details/107360933/
附录
手写数字识别代码及注释:
1. import numpy as np
2. import operator
3. from os import listdir
4. """
5. classify0函数说明:knn算法,分类器
6. Parameters:
7. inX - 用于分类的数据(测试集)
8. dataSet - 用于训练的数据(训练集)(n1维列向量)
9. labels - 分类标准(n1维列向量)
10. k - kNN算法参数,选择距离最小的k个点
11. Returns:
12. sortedClassCount[0][0] - 分类结果
13. """
14. def classify0(inX, dataSet, labels, k):
15. dataSetSize = dataSet.shape[0] # numpy函数shape[0]返回dataSet的行数
16. # 测量欧氏距离
17. diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet #将inX重复dataSetSize次并排成一列
18. sqDiffMat = diffMat2 #二维特征相减后平方(用diffMat的转置乘diffMat)
19. sqDistances = sqDiffMat.sum(axis=1) #sum()所有元素相加,sum(0)列相加,sum(1)行相加
20. distances = sqDistances0.5 #开方,计算出距离
21. sortedDistIndicies = distances.argsort() # 将距离从小到大进行排序;argsort函数返回的是distances值从小到大的索引值
22. classCount = {} #定义一个记录类别次数的字典
23. for i in range(k): # 选取前K个最短距离, 选取这K个中最多的分类类别
24. voteIlabel = labels[sortedDistIndicies[i]] #取出前k个元素的类别
25. classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1 #字典的get()方法,返回指定键的值,如果值不在字典中返回0;计算类别次数
26. sortedClassCount = sorted(classCount.items(),
27. key=operator.itemgetter(1), reverse=True) #reverse降序排序字典
28. return sortedClassCount[0][0] #返回次数最多的类别,即所要分类的类别
29. """
30. img2vector 函数说明:将3232的二进制图像矩阵转换成11024的向量
31. Parameters:
32. filename - 二进制图像文件名
33. Returns:
34. returnVect - 11024的向量
35. """
36. def img2vector(filename):
37. returnVect = np.zeros((1, 1024)) #zeros(shape, dtype=float, order='C') 返回一个给定形状和类型的用0填充的数组;
38. fr = open(filename) #读取二进制图像文件
39. for i in range(32): #32行
40. lineStr = fr.readline()
41. for j in range(32): #32列
42. returnVect[0, 32i+j] = int(lineStr[j])
43. return returnVect #返回11024的向量
44.
45. """
46. handwritingClassTest函数说明:进行手写数字识别
47. """
48. def handwritingClassTest():
49. hwLabels = []
50. trainingFileList = listdir('trainingDigits') #导入训练集,trainingFileList是训练集各个文件;listdir(path)返回指定路径path下的文件和文件夹列表
51. m = len(trainingFileList) #训练集的文件个数
52. trainingMat = np.zeros((m, 1024)) #各个文件变成一行之后的整合矩阵
53. for i in range(m):
54. fileNameStr = trainingFileList[i] #fileNameStr单个文件名,训练集的每个文件
55. fileStr = fileNameStr.split('.')[0] #去除.txt后缀,fileStr取分开后的第一个元素
56. classNumStr = int(fileStr.split('')[0]) #classNumStr记录这个数字是什么
57. hwLabels.append(classNumStr)
58. trainingMat[i, :] = img2vector('trainingDigits/%s' % fileNameStr) #将训练集的3232的二进制图像矩阵转换成11024的向量
59. # 导入测试集
60. testFileList = listdir('testDigits') #iterate through the test set
61. errorCount = 0.0 #定义错误数量
62. mTest = len(testFileList) #测试集的数量
63. for i in range(mTest): #对每个测试集的个体进行识别
64. fileNameStr = testFileList[i] #测试集的每个文件
65. fileStr = fileNameStr.split('.')[0] #去除.txt后缀
66. classNumStr = int(fileStr.split('')[0]) #训练集中正确的结果
67. vectorUnderTest = img2vector('testDigits/%s' % fileNameStr) #将测试集的3232的二进制图像矩阵转换成11024的向量
68. classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3) # 通过knn算法识别对testdigis数据进行猜测的结果
69. print("分类的结果: %d, 真实结果: %d" % (classifierResult, classNumStr)) #输出训练集的模拟结果和真实结果
70. if (classifierResult != classNumStr): errorCount += 1.0 #当测试结果和训练结果不同时,错误数量+1
71. print("n分类错误数量: %d" % errorCount) #输出模拟识别错误的数量
72. print("n分类错误率: %f" % (errorCount/float(mTest))) #输出错误率
73.
74. if name == 'main':
75. handwritingClassTest()
约会网站配对效果代码及注释:
1. import matplotlib.lines as mlines
2. import matplotlib.pyplot as plt
3. import time
4. import numpy as np
5. import operator
6.
7. """
8. 函数说明:kNN算法,分类器
9. Parameters:
10. inX - 用于分类的数据(测试集)
11. dataSet - 用于训练的数据(训练集)(n1维列向量)
12. labels - 分类标准(n1维列向量)
13. k - kNN算法参数,选择距离最小的k个点
14. Returns:
15. sortedClassCount[0][0] - 分类结果
16. """
17. def classify0(inX, dataSet, labels, k):
18. dataSetSize = dataSet.shape[0] # numpy函数shape[0]返回dataSet的行数
19. # 测量欧氏距离
20. diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet # 将inX重复dataSetSize次并排成一列
21. sqDiffMat = diffMat 2 # 二维特征相减后平方(用diffMat的转置乘diffMat)
22. sqDistances = sqDiffMat.sum(axis=1) # sum()所有元素相加,sum(0)列相加,sum(1)行相加
23. distances = sqDistances 0.5 # 开方,计算出距离
24. sortedDistIndicies = distances.argsort() # 将距离从小到大进行排序;argsort函数返回的是distances值从小到大的索引值
25. classCount = {} # 定义一个记录类别次数的字典
26. for i in range(k): # 选取前K个最短距离, 选取这K个中最多的分类类别
27. voteIlabel = labels[sortedDistIndicies[i]] # 取出前k个元素的类别
28. classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1 # 字典的get()方法,返回指定键的值,如果值不在字典中返回0;计算类别次数
29. sortedClassCount = sorted(classCount.items(),
30. key=operator.itemgetter(1), reverse=True) # reverse降序排序字典
31. return sortedClassCount[0][0] # 返回次数最多的类别,即所要分类的类别
32.
33.
34. """
35. 函数说明:打开解析文件,对数据进行分类,1代表不喜欢,2代表魅力一般,3代表极具魅力
36. Parameters:
37. filename - 文件名
38. Returns:
39. returnMat - 特征矩阵
40. classLabelVector - 分类label向量
41. """
42. def file2matrix(filename):
43. fr = open(filename) #打开文件
44. arrayOlines = fr.readlines() #读取文件所有内容
45. numberOfLines = len(arrayOlines) #文件行数
46. returnMat = np.zeros((numberOfLines, 3)) #返回的NumPy矩阵numberOfLines行,3列
47. classLabelVector = [] #创建分类标签向量
48. index = 0 #行的索引值
49. # 读取每一行
50. for line in arrayOlines:
51. # 去掉每一行首尾的空白符,例如'n','r','t',' '
52. line = line.strip()
53. listFromLine = line.split('t') #将每一行内容根据't'符进行切片,本例中一共有4列
54. returnMat[index, :] = listFromLine[0:3] #将数据的前3列进行提取保存在returnMat矩阵中,也就是特征矩阵
55. # 根据文本内容进行分类1:不喜欢;2:一般;3:喜欢
56. if listFromLine[-1] == 'didntLike':
57. classLabelVector.append(1)
58. elif listFromLine[-1] == 'smallDoses':
59. classLabelVector.append(2)
60. elif listFromLine[-1] == 'largeDoses':
61. classLabelVector.append(3)
62. index += 1
63. return returnMat, classLabelVector #返回标签列向量以及特征矩阵
64.
65. """
66. 函数说明:对数据进行归一化 min-max标准化
67. Parameters:
68. dataSet - 特征矩阵
69. Returns:
70. normDataSet - 归一化后的特征矩阵
71. ranges - 数据范围
72. minVals - 数据最小值
73. """
74. def autoNorm(dataSet):
75. minVals = dataSet.min(0) #获取数据的最小值
76. maxVals = dataSet.max(0) #获取数据的最大值
77. ranges = maxVals - minVals #最大值和最小值的范围
78. normDataSet = np.zeros(np.shape(dataSet)) #shape(dataSet)返回dataSet的矩阵行列数
79. m = dataSet.shape[0] #numpy函数shape[0]返回dataSet的行数
80. normDataSet = dataSet - np.tile(minVals, (m, 1)) #原始值减去最小值(x-xmin)
81. normDataSet = normDataSet / np.tile(ranges, (m, 1)) #差值处以最大值和最小值的差值(x-xmin)/(xmax-xmin)
82. return normDataSet, ranges, minVals #归一化数据结果,数据范围,最小值
83.
84.
85. """
86. 函数说明:分类器测试函数
87. Returns:
88. normDataSet - 归一化后的特征矩阵
89. ranges - 数据范围
90. minVals - 数据最小值
91. """
92. def datingClassTest():
93. filename = "datingTestSet.txt" #打开数据集文件
94. datingDataMat, datingLabels = file2matrix(filename) #将返回的特征矩阵和分类向量分别存储到datingDataMat和datingLabels中
95. hoRatio = 0.10 #取所有数据的10% hoRatio越小,错误率越低
96. normMat, ranges, minVals = autoNorm(datingDataMat) #数据归一化,返回归一化数据结果,数据范围,最小值
97. m = normMat.shape[0] #获取normMat的行数
98. numTestVecs = int(m hoRatio) #数据集中10%的个数
99. errorCount = 0.0 #分类错误的计数
100. for i in range(numTestVecs):
101. # 前numTestVecs个数据作为测试集,后m-numTestVecs个数据作为训练集
102. # k选择label数+1(结果比较好)
103. classifierResult = classify0(normMat[i, :], normMat[numTestVecs:m, :],
104. datingLabels[numTestVecs:m], 7)
105. print("分类结果:%dt真实类别:%d" % (classifierResult, datingLabels[i])) #输出分类的结果和真实结果
106. if classifierResult != datingLabels[i]: #分类结果与真实结果不同时,错误计数+1
107. errorCount += 1.0
108. print("n分类错误数量: %d" % errorCount) # 输出模拟识别错误的数量
109. print("错误率:%f%%" % (errorCount / float(numTestVecs) 100)) #输出错误率
110.
111. """
112. 函数说明:main函数
113. """
114. def main():
115. # 获取程序运行时间
116. start = time.perfcounter()
117. datingClassTest()
118. # 结束时间
119. end = time.perfcounter()
120.
121. # 打印程序运行时间
122. print('Running time: %f Seconds' % (end - start))
123.
124. if name == 'main':
125. main()