Machine Learning in Action Chapter02 Classifying with k-Nearest Neighbors

Machine Learning in Action Chapter02 Classifying with k-Nearest Neighbors

KNN 概述

KNN 算法是测量不同特征之间的距离来进行分类的算法。

  • 优点:精度高,对异常值不敏感,无数据输入假定
  • 缺点:计算复杂度高,空间复杂度高
  • 使用数据范围:数值型和标称型

KNN 原理

  1. 假设有一个带有标签的样本数据集(训练样本集),其中包含每条数据与所属分类的对应关系。
  2. 输入没有标签的新数据后,将新数据的每个特征与样本集中数据对应的特征进行比较。
    1. 计算新数据与样本数据集中每条数据的距离。
    2. 对求得的所有距离进行排序(从小到大,越小表示越相似)。
    3. 取前 k (k 一般小于等于 20 )个样本数据对应的分类标签。
  3. 求 k 个数据中出现次数最多的分类标签作为新数据的分类。

KNN 一般流程

  1. 收集数据:任何方法
  2. 准备数据:距离计算所需要的数值,最好是结构化的数据格式
  3. 分析数据:任何方法
  4. 训练算法:此步骤不适用于 k-近邻算法
  5. 测试算法:计算错误率
  6. 使用算法:输入样本数据和结构化的输出结果,然后运行 k-近邻算法判断输入数据分类属于哪个分类,最后对计算出的分类执行后续处理

准备:使用 Python 导入数据

1
2
3
4
5
6
7
from numpy import *
import operator

def createDataSet():
group = array([[1.0,1.1], [1.0,1.0], [0,0], [0,0.1]]) # 特征(位置)
labels = ['A','A','B','B'] # 标签
return group, labels

从文本文件中解析数据

KNN 算法伪代码:

1
2
3
4
5
6
对于每一个在数据集中的数据点:
计算目标的数据点(需要分类的数据点)与该数据点的距离
将距离排序:从小到大
选取前K个最短距离
选取这K个中最多的分类类别
返回该类别来作为目标数据点的预测值

实现代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def classify0(inX, dataSet, labels, k):
"""
Desc:
KNN 欧式距离分类实现
Arguments:
inX -- 用于分类的向量
dataSet -- 输入的训练样本
labels -- 输入的标签向量
k -- 最邻近的数目

Return:
sortedClassCount[0][0] -- 预测 inX 的标签
"""
dataSetSize = dataSet.shape[0] # 训练样本的个数

# 距离度量 度量公式为欧氏距离
diffMat = tile(inX, (dataSetSize,1)) – dataSet # tile() 重复 inX 构成矩阵和 dataSet 同维度,直接减去 dataSet 得到差值矩阵
sqDiffMat = diffMat**2 # 求欧式距离
sqDistances = sqDiffMat.sum(axis=1) # 全部求和
distances = sqDistances**0.5

# 将距离排序:从小到大
sortedDistIndicies = distances.argsort()

# 选取前K个最短距离, 选取这K个中最多的分类类别
classCount={}
for i in range(k):
voteIlabel = labels[sortedDistIndicies[i]]
classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True) # 从大到小,排序前 k 个元素出现最多的标签
return sortedClassCount[0][0] # 返回第一个值得标签

实现欧式距离计算的公式:

\[d=\sqrt{(xA_0-xB_0)^2+(xA_1-xB_1)^2}\]

若数据集中存在 4 个特征值,则点 \((1,0,0,1)\)\((7,6,9,4)\) 之间的距离是:

\[\sqrt{(7-1)^2+(6-0)^2+(9-0)^2+(4-1)^2}\]

1
2
3
group, labels = createDataSet()
res = classify0([0,0], group, labels, 3)
# res = 'B'

示例:使用 KNN 算法改进约会网站的配对效果

项目概述

海伦使用在线约会网站寻找约会对象,她发现她曾交往过三种类型的人:

  • 不喜欢的人
  • 魅力一般的人
  • 极具魅力的人

开发流程

  • 收集数据:提供文本文件
  • 准备数据:使用 Python 解析文本文件
  • 分析数据:使用 Matplotlib 画二维散点图
  • 训练算法:此步骤不适用于 k-近邻算法
  • 测试算法:使用海伦提供的部分数据作为测试样本。 测试样本和非测试样本的区别在于:测试样本是已经完成分类的数据,如果预测分类与实际类别不同,则标记为一个错误。
  • 使用算法:产生简单的命令行程序,然后海伦可以输入一些特征数据以判断对方是否为自己喜欢的类型。

准备数据:从文本文件种解析数据

文件 datingTestSet.txt 中,每个样本数据占据一行,共有 1k 行。海伦约会的对象主要包含以下 3 种特征:

  • 每年获得的飞行常客里程数
  • 玩视频游戏所耗时间百分比
  • 每周消费的冰淇淋公升数

数据格式如下:

1
2
3
4
5
40920	8.326976	0.953952	3
14488 7.153469 1.673904 2
26052 1.441871 0.805124 1
75136 13.147394 0.428964 1
38344 1.669788 0.134296 1

将文本记录到转换 NumPy 的解析程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def file2matrix(filename):
"""
Desc:
导入训练数据
Argument:
filename: 数据文件路径
Return:
数据矩阵 returnMat 和对应的类别 classLabelVector
"""
# 打开数据文件
fr = open(filename)
# 获得文件中的数据行的行数
numberOfLines = len(fr.readlines())
# 生成对应的全零矩阵,3 列对应数据特征列
returnMat = zeros((numberOfLines, 3))
classLabelVector = [] # 数据的第 4 列是标签列

index = 0 # 行数
for line in fr.readlines():
# 去除行内空格
line = line.strip()
# 以 '\t' 切割字符串
listFromLine = line.split('\t')
# 每列的属性数据
returnMat[index, :] = listFromLine[0:3]
# 每列的类别数据,就是 label 标签数据
classLabelVector.append(int(listFromLine[-1]))
index += 1
# 返回数据矩阵returnMat和对应的类别classLabelVector
return returnMat, classLabelVector

结果如下:

分析数据:使用 Matplotlib 创建散点图

1
2
3
4
5
6
import matplotlib
import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:, 0], datingDataMat[:, 1], 15.0*array(datingLabels), 15.0*array(datingLabels))
plt.show()

准备数据:归一化数值

不同的特征,因为量纲的不同,直接计算欧氏距离会导致,不同的特征的影响差距过大,在这里,我们假设所有特征的影响权重是相同的,所以进行归一化处理,让权重变得同同一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def autoNorm(dataSet):
"""
Desc:
归一化特征值,消除特征之间量级不同导致的影响
Argument:
dataSet: 数据集
Return:
归一化后的数据集 normDataSet. ranges和minVals即最小值与范围,并没有用到

归一化公式:
Y = (X-Xmin)/(Xmax-Xmin)
其中的 min 和 max 分别是数据集中的最小特征值和最大特征值。该函数可以自动将数字特征值转化为0到1的区间。
"""
# 计算每种属性的最大值、最小值、范围
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
# 极差
ranges = maxVals - minVals
normDataSet = zeros(shape(dataSet))
m = dataSet.shape[0]
# 生成与最小值之差组成的矩阵
normDataSet = dataSet - tile(minVals, (m, 1))
# 将最小值之差除以范围组成矩阵
normDataSet = normDataSet / tile(ranges, (m, 1)) # 矩阵对应位置元素相除
return normDataSet, ranges, minVals

结果如下:

测试算法:作为完整程序验证分类器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def datingClassTest():
"""
Desc:
对约会网站的测试方法
return:
错误数
"""
# 设置测试数据的的一个比例(训练数据集比例=1-hoRatio)
hoRatio = 0.1 # 测试范围,一部分测试一部分作为样本
# 从文件中加载数据
datingDataMat, datingLabels = file2matrix('data/2.KNN/datingTestSet2.txt') # load data setfrom file
# 归一化数据
normMat, ranges, minVals = autoNorm(datingDataMat)
# m 表示数据的行数,即矩阵的第一维
m = normMat.shape[0]
# 设置测试的样本数量, numTestVecs:m表示训练样本的数量
numTestVecs = int(m * hoRatio)
print('numTestVecs=', numTestVecs)
errorCount = 0.0
for i in range(numTestVecs):
# 对数据测试
classifierResult = classify0(normMat[i, :], normMat[numTestVecs:m, :], datingLabels[numTestVecs:m], 3)
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)))
print(errorCount)

执行结果:

示例:手写识别系统

项目概述

构造一个能识别数字 0 到 9 的基于 KNN 分类器的手写数字识别系统。

需要识别的数字是存储在文本文件中的具有相同的色彩和大小:宽高是 32 像素 * 32 像素的黑白图像。

开发流程

  • 收集数据:提供文本文件。

  • 准备数据:编写函数 img2vector(), 将图像格式转换为分类器使用的向量格式

  • 分析数据:在 Python 命令提示符中检查数据,确保它符合要求

  • 训练算法:此步骤不适用于 KNN

  • 测试算法:编写函数使用提供的部分数据集作为测试样本,测试样本与非测试样本的

    区别在于测试样本是已经完成分类的数据,如果预测分类与实际类别不同,则标记为一个错误

  • 使用算法:本例没有完成此步骤,若你感兴趣可以构建完整的应用程序,从图像中提取数字,并完成数字识别,美国的邮件分拣系统就是一个实际运行的类似系统

准备数据:将图像转换为测试向量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def img2vector(filename):
"""
Desc:
将 32X32 的二进制图像矩阵转换为 1x1024 的向量
Args:
filename -- 图片文件 因为我们的输入数据的图片格式是 32 * 32的
Returns:
returnVect -- 图片文件处理完成后的一维矩阵
"""
returnVect = zeros((1,1024))
fr = open(filename)
for i in range(32):
lineStr = fr.readline()
for j in range(32):
returnVect[0,32*i+j] = int(lineStr[j])
return returnVect

结果如下:

测试代码:使用 KNN 算法识别手写数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def handwritingClassTest():
"""
Desc:
手写数字识别分类器,并将分类错误数和分类错误率打印出来
"""
# 1. 导入数据
hwLabels = []
trainingFileList = os.listdir("data/2.KNN/trainingDigits") # load the training set
m = len(trainingFileList) # m 个数据
trainingMat = zeros((m, 1024))
# hwLabels存储0~9对应的index位置, trainingMat存放的每个位置对应的图片向量
for i in range(m):
fileNameStr = trainingFileList[i]
fileStr = fileNameStr.split('.')[0] # take off .txt
classNumStr = int(fileStr.split('_')[0])
hwLabels.append(classNumStr)
# 将 32*32的矩阵->1*1024的矩阵
trainingMat[i] = img2vector('data/2.KNN/trainingDigits/%s' % fileNameStr)

# 2. 导入测试数据
testFileList = os.listdir('data/2.KNN/testDigits') # iterate through the test set
errorCount = 0
mTest = len(testFileList)
for i in range(mTest):
fileNameStr = testFileList[i]
fileStr = fileNameStr.split('.')[0] # take off .txt
classNumStr = int(fileStr.split('_')[0])
vectorUnderTest = img2vector('data/2.KNN/testDigits/%s' % fileNameStr)
classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
print("the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr))
errorCount += classifierResult != classNumStr
print("\nthe total number of errors is: %d" % errorCount)
print("\nthe total error rate is: %f" % (errorCount / mTest))

结果如下:

参考资料:

https://github.com/apachecn/AiLearning/blob/master/docs/ml/2.k-%E8%BF%91%E9%82%BB%E7%AE%97%E6%B3%95.md

https://github.com/apachecn/AiLearning/blob/master/src/py3.x/ml/2.KNN/kNN.py

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×