kNN

《机器学习实战》 k-近邻算法学习笔记

1. 概述

k-近邻算法采用测量不同特征值之间的距离方法进行分类。

2. 原理

将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据的分类标签。

即 选择 k 个最相似数据中出现次数最多的分类。

3. 伪代码

  1. 计算已知类别数据集中的点与当前点之间的距离
  2. 按照距离递增次序排序
  3. 选取与当前点距离最小的 k 个点
  4. 确定前 k 个点所在类别的出现概率
  5. 返回前 k 个点出现频率最高的类别作为当前点的预测分类

4. 代码分解

4.1 创建数据集和标签

1
2
group = np.array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
labels = ['A','A','B','B']

4.2 计算距离

这里使用欧式距离公式计算。

1
2
3
4
dataSetSize = dataSet.shape[0]
diffMat = np.tile(inX, (dataSetSize,1)) 
sqDiffMat = np.square(diffMat - dataSet)
distances = np.sqrt(sqDiffMat.sum(axis=1))

4.3 排序

1
sortedDistIndicies = distances.argsort()

4.4 选取k个点及所在类别出现概率

1
2
3
for i in range(k):
	voteIlabel = labels[sortedDistIndicies[i]]
	classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1

4.5 返回分类结果

1
2
3
sortedClassCount = sorted(classCount.items(),
			key = operator.itemgetter(1),reverse=True)
return sortedClassCount[0][0]

5. 预测

1
result = classify0([0,0], group, labels, 3)

结果: [0,0] 属于'B'类。

6. 其他

6.1 argsort

argsort函数返回的是数组值从小到大的索引值。

1
2
3
In [2]: x = np.array([3,1,2])
In [3]: np.argsort(x)
Out[3]: array([1, 2, 0])
6.2 tile
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
In [7]: a = [1,2]
In [8]: np.tile(a,2)
Out[8]: array([1, 2, 1, 2])
In [9]: np.tile(a,(2,3))
Out[9]:
array([[1, 2, 1, 2, 1, 2],
       [1, 2, 1, 2, 1, 2]])
In [10]: np.tile(a,(2,2,3))
Out[10]:
array([[[1, 2, 1, 2, 1, 2],
        [1, 2, 1, 2, 1, 2]],
       [[1, 2, 1, 2, 1, 2],
        [1, 2, 1, 2, 1, 2]]])
6.3 计算欧式距离
1
2
3
distances = np.sqrt(np.sum(np.square(inX - dataSet)))
distances = np.linalg.norm(inX - dataSet)
6.4 get

Python 字典(Dictionary) get() 函数返回指定键的值，如果值不在字典中返回默认值。

1
dict.get(key, default=None)

参数：

  • key – 字典中要查找的键
  • default – 如果指定键的值不存在时，返回该默认值值。
6.5 iteritems
1
2
sortedClassCount = sorted(classCount.iteritems(),
				key = operator.itemgetter(1),reverse=True)

这种情况下会报错：

AttributeError: 'dict' object has no attribute 'iteritems'

Python3.5中：iteritems变为items。

6.6 数值归一化

在处理不同取值范围的特征值时，我们通常采用的方法是将数值归一化。

newvalue = (oldvalue - min)/(max - min)

7. 完整代码

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
34
35
36
37
# -*- coding: utf-8 -*-
# !/usr/bin/env python
import numpy as np
import operator
def CreatDataSet():
	group = np.array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
	labels = ['A','A','B','B']
	return group,labels
def classify0(inX, dataSet, labels, k):
	# 计算欧式距离
	dataSetSize = dataSet.shape[0]
	diffMat = np.tile(inX, (dataSetSize,1)) 
	sqDiffMat = np.square(diffMat - dataSet)
	distances = np.sqrt(sqDiffMat.sum(axis=1))
	# 排序
	sortedDistIndicies = distances.argsort()
	# print(distances)
	# print(sortedDistIndicies)
	# 选择距离最小的k个点 和每个类别出现的次数
	classCount = {}
	for i in range(k):
		voteIlabel = labels[sortedDistIndicies[i]]
		classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
	print(classCount)	
	# 对每个类别出现的次数进行排序
	sortedClassCount = sorted(classCount.items(),
				key = operator.itemgetter(1),reverse=True)
	return sortedClassCount[0][0]
if __name__ == '__main__':
	group,labels = CreatDataSet()
	result = classify0([0,0], group, labels, 3)
	print(result)

8.使用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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
# -*- coding: utf-8 -*-
# !/usr/bin/env python
import numpy as np
import pandas as pd
from os import listdir
import operator
# 32*32 转 1*1024向量 
def img2vector(filename):
	returnVet = np.zeros((1, 1024))
	fr = open(filename)
	for i in range(32):
		lineStr = fr.readline()
		for j in range(32):
			returnVet[0,i*32+j] = int(lineStr[j])
	return returnVet	
# 使用 listdir 读取数据
def getDataSet(filePath):
	FileList = listdir(filePath)
	DataLen = len(FileList)
	DataMat = np.zeros((DataLen, 1024))
	Labels = []
	for i in range(DataLen): 
		filename = FileList[i]
		fileStr = filename.split('.')[0]
		fileLabel = fileStr.split('_')[0]
		Labels.append(fileLabel)
		DataMat[i] = img2vector('%s/%s' % (filePath,filename))
	return DataMat,Labels
# 计算欧式距离
def getEucDistance(trainSet, dataSet):
	dataSetSize = dataSet.shape[0]
	inX = np.tile(trainSet, (dataSetSize, 1))
	dist = np.sqrt((np.square(inX - dataSet)).sum(axis=1))
	return dist
# 分类器
def classify(inX, dataSet, labels, k):
	dist = getEucDistance(inX, dataSet)
	SortDit = dist.argsort()
	classCount = {}
	for i in range(k):
		voterIlabel = labels[SortDit[i]]
		classCount[voterIlabel] = classCount.get(voterIlabel, 0) + 1
	sortedclassCount = sorted(classCount.items(), 
		key=operator.itemgetter(1),reverse=True)
	return sortedclassCount[0][0]
# 测试分类器
def handWriteClassTest():
	trainingMat,trainingLabels = getDataSet('digits/trainingDigits')
	testMat,testLables = getDataSet('digits/testDigits')
	errorCount = 0
	for i in range(testMat.shape[0]):  
		classifieRet = classify(testMat[i], trainingMat, trainingLabels, 10)
		if(classifieRet != testLables[i]):
			errorCount += 1
			print('ret: %s, label:%s' % (classifieRet,testLables[i]))
	print('errCnt:%d,errRat:%.6s' % (errorCount, errorCount/testMat.shape[0]))
if __name__ == '__main__':
	handWriteClassTest()
listdir

os.listdir() 方法用于返回指定的文件夹包含的文件或文件夹的名字的列表

使用方法：

1
2
3
4
5
6
7
from os import listdir
FileList = listdir(filePath)
	#输出所有文件和文件夹
for file in FileList:
	print(file)

参数：

  • filePath – 需要列出的目录路径

总结

测试发现错误率为74%

原因如下：

1
2
3
4
5
6
7
def img2vector(filename):
	returnVet = np.zeros((1, 1024))
	for i in range(32):
		lineStr = open(filename).readline()
		for j in range(32):
			returnVet[0,i*32+j] = int(lineStr[j])
	return returnVet

导致对于每条数据，lineStr读到的都是第一行的数据。

改正：

1
2
3
4
5
6
7
8
def img2vector(filename):
	returnVet = np.zeros((1, 1024))
	fr = open(filename)
	for i in range(32):
		lineStr = fr.readline()
		for j in range(32):
			returnVet[0,i*32+j] = int(lineStr[j])
	return returnVet