机器学习实战笔记(一)KNN算法

文章目录
  1. 1. 机器学习基础
  2. 2. K-近邻算法
    1. 2.1. 1. 特点
    2. 2.2. 2. 工作原理
    3. 2.3. 3. 一般流程
  3. 3. 实例
    1. 3.1. 1.使用python导入数据
    2. 3.2. 2.KNN算法
    3. 3.3. 3.优化约会网站的配对效果
    4. 3.4. 4.手写识别系统
  4. 4. 小结
  5. 5. 参考的文章:

用python学习机器学习的笔记,所有的代码和实例来源于《机器学习实战》一书。

机器学习基础

机器学习可以分为监督学习和无监督学习,监督学习又可以分为分类和回归,之所以称之为监督学习,是因为这类算法必须知道预测什么,即目标变量的分类信息。与之相对的无监督学习分为聚类和密度估计,此时数据没有类别信息,也不会给定目标值。

K-近邻算法

k近邻算法就是分类算法的一种。简单地说,k-近邻算法采用测量不同特征值之间的距离方法进行分类。

1. 特点

优点:精度高、对异常值不敏感、无数据输入假定。
缺点:计算复杂度高、空间复杂度高。
适用数据类型:数值型和标称型。

2. 工作原理

  • 有一个样本数据集(训练数据集),并且知道其中数据和分类之间的对应关系。(每个数据都存在标签)。
  • 输入没有标签的新数据之后,将新数据的每个特征和样本集中的数据对应的特征进行比较;然后提取样本数据集中最相似数据的分类标签(距离最近);一般只选择样本集中前k个最相似的数据(k不等于20)。
  • 把k个数据标签中出现次数最多的那个分类,作为新数据的分类。

    3. 一般流程

    收集数据:任何方法。

    准备数据:距离计算所需要的数值,最好是结构化的数据格式。

    分析数据:一般可采用可视化的方法进行分析。

    训练算法:K-近邻算法中不适用。

    测试算法:计算错误率。

    使用算法:输入样本数据和结构化的输出结果,然后运行k-近邻算法判定输入数据分别属于哪个分类,最后对计算出的分类执行后续处理。

实例

1.使用python导入数据

1
2
3
4
5
6
7
8
#创建数据集和标签
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

2.KNN算法

使用k-近邻算法将每组数据划分到每个类中:

  1. 计算当前点和测试数据集中的点之间的距离。
  2. 按照距离递增次序排序。
  3. 选取和当前距离最小的k个点。
  4. 计算前k个点的类别出现的频率。
  5. 返回前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
'''
Parameters:
inX - 用于分类的数据(测试集)
dataSet - 用于训练的数据(训练集)
labes - 训练数据集的label
k - 选择距离最小的k个点
return:
sortedClassCount[0][0] - 输入数据的预测分类
'''
# k-近邻算法
def classify0(inX, dataSet, labels, k):
# 计算距离
dataSetSize = dataSet.shape[0]
# 用tile将输入向量复制成和数据集一样大的矩阵
diffMat = tile(inX, (dataSetSize, 1)) - dataSet
sqDiffMat = diffMat ** 2
# 将矩阵的每一行相加,axis = 1表示行相加
sqDistances = sqDiffMat.sum(axis=1)
distances = sqDistances ** 0.5
# 按距离从小到大排序,并返回对应的索引位置
sortedDistIndicies = distances.argsort()

#创建一个字典,存储标签和出现次数
classCount = {}
# 选择距离最小的k个点
for i in range(k):
# 查找样本的标签类型
voteIlabel = labels[sortedDistIndicies[i]]
# 在字典中给找到的样本标签类型+1
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
# 排序并返回出现次数最多的标签类型
sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]

3.优化约会网站的配对效果

准备数据:从文本文件中解析数据,数据存放在文本文件datingTestSet2.txt中,在将文本中的数据输入到分类器之前,必须将待处理数据的格式转化为分类器可以接受的格式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#将文本记录转化为NumPy矩阵
def file2matrix(filename):
fr = open(filename,'r')
#获取文件数据行的行数
numberOfLines = len(fr.readlines())
#生成一个0矩阵
returnMat = zeros((numberOfLines,3))
#要返回的标签
classLabelVector = []
fr = open(filename, 'r')
index = 0
#解析文件数据到列表
for line in fr.readlines():
# 去除字符串首尾的空格
line = line.strip()
#用制表符\t分割字符串
listFormLine = line.split('\t')
#每列的属性数据
returnMat[index] = listFormLine[0:3]
#每列的label标签数据,-1最后一列
classLabelVector.append(int(listFormLine[-1]))
index += 1
return returnMat,classLabelVector

使用Matplotlib画图,分析数据的特征。

1
2
3
4
5
6
7
8
9
10
#使用Matplotlib画二维散点图
def draw():
import matplotlib
import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111)
datingDataMat, datingLabels = file2matrix("datingTestSet2.txt")
ax.scatter(datingDataMat[:,1], datingDataMat[:,2])
#ax.scatter(datingDataMat[:,1], datingDataMat[:,2], 15.0*array(datingLabels), 15,0*array(datingLabels))
plt.show()

如果给的数据的权重不一致,就需要进行归一化操作,归一化特征值,消除特征之间量级不同导致的影响。
这里采用的是线性函数转换:y=(x-MinValue)/(MaxValue-MinValue)。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#归一化特征值
def autoNorm(dataSet):
#每列的最小值
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))
# norm_dataset = (dataset - minvalue) / ranges
return normDataSet, ranges, minVals

测试算法:首先使用了file2matrix和autoNorm()函数从文件中读取数据并将其转换为归一化特征值。接着计算测试向量的数量,此步决定了normMat向量中哪些数据用于测试,哪些数据用于分类器的训练样本;然后将这两部分数据输入到原始kNN分类器函数classify0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#测试算法
def datingClassTest():
#测试范围,一部分测试一部分作为样本
hoRatio = 0.1
#加载数据
datingDataMat, datingLabels = file2matrix("datingTestSet2.txt")
#归一化数据
normMat, ranges, minVals = autoNorm(datingDataMat)
#数据的行数
m = normMat.shape[0]
#设置样本的测试数据
numTestVecs = int(m * hoRatio)
print('numTestVecs', numTestVecs)
#分类错误数
errorCount = 0
#numTestVecs: m表示训练样本的数量
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]))
errorCount += classifierResult != datingLabels[i]
print("the total error rate is :%f" %(errorCount / numTestVecs))
print(errorCount)

4.手写识别系统

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

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

目录 trainingDigits 中包含了大约 2000 个例子,每个例子内容如下图所示,每个数字大约有 200 个样本;目录 testDigits 中包含了大约 900 个测试数据。

1
2
3
4
5
6
7
8
9
#将图像数据转换为向量
def img2vector(filename):
returnVect = zeros((1, 1024))
fr = open(filename, 'r')
for i in range(32):
lineStr = fr.readline()
for j in range(32):
returnVect[0, 32 * i + j] = int(lineStr[j])
return returnVect
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
def handwritingClassTest():
#导入数据
hwLabels = []
trainingFileList = os.listdir('.../2.KNN/trainingDigits')
m = len(trainingFileList)
trainingMat = zeros((m, 1024))
for i in range(m):
#从文件名解析分类数字
fileNameStr = trainingFileList[i]
fileStr = fileNameStr.split('.')[0]
classNumStr = int(fileStr.split('_')[0])
hwLabels.append(classNumStr)
trainingMat[i] = img2vector('.../2.KNN/trainingDigits/%s' % fileNameStr)

#导入测试数据
testFileList = os.listdir('.../2.KNN/testDigits')
errorCount = 0
mTest = len(testFileList)
for i in range(mTest):
fileNameStr = testFileList[i]
fileStr = fileNameStr.split('.')[0]
classNumStr = int(fileStr.split('_')[0])
vectorUnderTest = img2vector('.../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))

小结

k-近邻算法是分类数据最简单最有效的算法,k-近邻算法必须保存全部数据集,如果训练数据集的很大,必须使用大量的存储空间。此外,由于必须对数据集中的每个数据计算距离值,实际使用时可能非常耗时。k-近邻算法的另一个缺陷是它无法给出任何数据的基础结构信息,因此我们也无法知晓平均实例样本和典型实例样本具有什么特征。

参考的文章:

https://blog.csdn.net/c406495762/article/details/75172850
https://github.com/apachecn/MachineLearning/blob/master/docs/2.k-%E8%BF%91%E9%82%BB%E7%AE%97%E6%B3%95.md
http://www.pythoner.com/238.html