step by step
1、kNN原理介绍
2、手写体数据集测试
3、算法优缺点总结
一、kNN原理介绍
- 1.1 算法概述
给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例（也就是上面所说的K个邻居）， 这K个实例的多数属于某个类，就把该输入实例分类到这个类中。
- 1.2 示例
说明： 测试样本（绿色圆形）应归入要么是第一类的蓝色方形或是第二类的红色三角形。如果k=3（实线圆圈）它被分配给第二类，因为有2个三角形和只有1个正方形在内侧圆圈之内。如果k=5（虚线圆圈）它被分配到第一类（3个正方形与2个三角形在外侧圆圈之内）。
- 1.3 算法Code Sample
import operator
def classify0(inX, dataSet, labels, k):
"""
参数:
- inX: 用于分类的输入向量
- dataSet: 输入的训练样本集
- labels: 样本数据的类标签向量
- k: 用于选择最近邻居的数目
"""
# 获取样本数据数量
dataSetSize = dataSet.shape[0]
# 矩阵运算，计算测试数据与每个样本数据对应数据项的差值
diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
# sqDistances 上一步骤结果平方和
sqDiffMat = diffMat**2
sqDistances = sqDiffMat.sum(axis=1)
# 取平方根，得到距离向量
distances = sqDistances**0.5
# 按照距离从低到高排序
sortedDistIndicies = distances.argsort()
classCount = {}
# 依次取出最近的样本数据
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]- 1.4 算法快速测试
import numpy as np
# 创建数据集
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
group, labels = createDataSet()
print('group:', group)
print('labels:', labels) # 输出数值
# 测试算法效果
classify0([0, 0], group, labels, 3)快速测试效果
group: [[1. 1.1]
[1. 1. ]
[0. 0. ]
[0. 0.1]]
labels: ['A', 'A', 'B', 'B']
'B'二、手写体数据集测试
- 2.1 下载数据集
# 在 Jupyter Notebook 单元格中执行，下载并解压数据。
!wget "http://labfile.oss.aliyuncs.com/courses/777/digits.zip"
# 解压缩
!unzip digits.zip- 2.2 查看解压后文本内容0_1.txt
!cat digits/testDigits/0_1.txt
00000000000000011000000000000000
00000000000111111110000000000000
00000000001111111111100000000000
00000000001111111111110000000000
00000000011111111111111000000000
00000000011111100011111000000000
00000000111110000001111000000000
00000000111110000001111100000000
00000000111110000000111110000000
00000001111110000000111110000000
00000001111110000000011111000000
00000001111110000000001111000000
00000001111110000000001111100000
00000001111100000000001111000000
00000001111000000000001111000000
00000001111000000000001111000000
00000001111000000000000111000000
00000000111100000000000111000000
00000000111100000000000111000000
00000000111100000000000111000000
00000001111000000000011110000000
00000001111000000000011110000000
00000000111000000000011110000000
00000000111110000011111110000000
00000000111110001111111100000000
00000000111111111111111000000000
00000000011111111111111000000000
00000000111111111111100000000000
00000000011111111111000000000000
00000000001111111000000000000000
00000000001111100000000000000000
00000000000100000000000000000000- 2.3 图像转换为向量
# 为了使用前面两个例子的分类器，我们必须将图像格式化处理为一个向量。我们将把一个 32x32 的二进制图像矩阵转换为 1x1024 的向量
def img2vector(filename):
# 创建向量
returnVect = np.zeros((1, 1024))
# 打开数据文件，读取每行内容
fr = open(filename)
for i in range(32):
# 读取每一行
lineStr = fr.readline()
# 将每行前 32 字符转成 int 存入向量
for j in range(32):
returnVect[0, 32*i+j] = int(lineStr[j])
return returnVect测试效果
- 2.4 手写体测试
from os import listdir
def handwritingClassTest():
# 样本数据的类标签列表
hwLabels = []
# 样本数据文件列表
trainingFileList = listdir('digits/trainingDigits')
trainingFileList = trainingFileList[1:]
m = len(trainingFileList)
# print(m)
# 初始化样本数据矩阵（M*1024）
trainingMat = np.zeros((m, 1024))
# 依次读取所有样本数据到数据矩阵
for i in range(m):
# 提取文件名中的数字
fileNameStr = trainingFileList[i]
# print(fileNameStr)
fileStr = fileNameStr.split('.')[0]
# print(fileStr)
# print((fileStr.split('_')[0]))
classNumStr = int((fileStr.split('_')[0]))
hwLabels.append(classNumStr)
# 将样本数据存入矩阵
trainingMat[i, :] = img2vector(
'digits/trainingDigits/%s' % fileNameStr)
# 循环读取测试数据
testFileList = listdir('digits/testDigits')
testFileList = testFileList[1:]
# 初始化错误率
errorCount = 0.0
mTest = len(testFileList)
# 循环测试每个测试数据文件
for i in range(mTest):
# 提取文件名中的数字
fileNameStr = testFileList[i]
print(fileNameStr)
fileStr = fileNameStr.split('.')[0]
classNumStr = int(float((fileStr.split('_')[0])))
# 提取数据向量
vectorUnderTest = img2vector('digits/testDigits/%s' % fileNameStr)
# 对数据文件进行分类
classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
# 打印 K 近邻算法分类结果和真实的分类
print("测试样本 %d, 分类器预测: %d, 真实类别: %d" %
(i+1, classifierResult, classNumStr))
# 判断K 近邻算法结果是否准确
if (classifierResult != classNumStr):
errorCount += 1.0
# 打印错误率
print("\n错误分类计数: %d" % errorCount)
print("\n错误分类比例: %f" % (errorCount/float(mTest)))
测试效果
三、算法优缺点总结
3.1 优点
- 1、算法原理简单，容易理解，精度高，理论成熟，既可以用来做分类也可以用来做回归；
- 2、可以适配多种类型数据；
- 3、特别适合于多分类问题(multi-modal,对象具有多个类别标签)， KNN比SVM的表现要好；
- 4、和朴素贝叶斯之类的算法比，对数据没有假设，准确度高，对异常点不敏感。
3.2 缺点
- 1、计算量太大，尤其是特征数非常多的时候（每一个待分类文本都要计算它到全体已知样本的距离，才能得到它的第K个最*邻点）；
- 2、样本不平衡的时候，对稀有类别的预测准确率低（当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数）；
- 3、对训练数据依赖度特别大，对训练数据的容错性太差（如果训练数据集中，有一两个数据是错误的，刚刚好又在需要分类的数值的旁边，这样就会直接导致预测的数据的不准确）
- 4、可解释性较差（无法给出数据的内在含义）。
