机器学习实战——KNN

一、简介

参考：https://blog.csdn.net/c406495762/article/details/75172850

环境：win 10, notebook,python 3.6

原blog较长，主要实现其算法，尽可能的简洁些,并对一些细节给出实例，

如果熟练，细节处的函数尽可能的可以忽略，写出来主要是未来加强印象。

三、四、五、三个实例，前两个同一种方法，分类函数是同一个，只是数据不一样，最后一个使用SKLerrn实现KNN，十分方便。

二、算法简介

1、原理：

输入没有标签的新数据后，将新的数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本最相似数据(最近邻)的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

2、距离度量

欧式距离

3、步骤：

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

k-近邻算法的一般流程：

收集数据：可以使用爬虫进行数据的收集，也可以使用第三方提供的免费或收费的数据。一般来讲，数据放在txt文本文件中，按照一定的格式进行存储，便于解析及处理。
准备数据：使用Python解析、预处理数据。
分析数据：可以使用很多方法对数据进行分析，例如使用Matplotlib将数据可视化。
测试算法：计算错误率。
使用算法：错误率在可接受范围内，就可以运行k-近邻算法进行分类。

优缺点：

优点

简单好用，容易理解，精度高，理论成熟，既可以用来做分类也可以用来做回归；
可用于数值型数据和离散型数据；
训练时间复杂度为O(n)；无数据输入假定；
对异常值不敏感。
缺点：

计算复杂性高；空间复杂性高；
样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；
一般数值很大的时候不用这个，计算量太大。但是单个样本又不能太少，否则容易发生误分。
最大的缺点是无法给出数据的内在含义。
 

三、KNN简单实例

训练集是一个矩阵，测试集也是一个矩阵，要预测测试集中每一个数据的类别

算法步骤：

1、将测试集中的每一个数据扩展成和训练集一样大小的矩阵，用于该数据与训练集的每一个数据进行距离计算

2、扩展矩阵与训练集对应元素相减，

3、相减后的每一个元素进行平方，

4、每一行的元素相加

5、开根号，

6、找出k个最小的的值，这k个中，类别最多的那个即是预测类型

如图：

代码如下：

def classify(inX,dataSet,labels,k):# 返回行数dataSetSize = dataSet.shape[0]# 扩展维度，相减diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet# 平方sqDiffMat = diffMat**2# 求和sqDistances = sqDiffMat.sum(axis=1)# 开根号distances = sqDistances**0.5#返回distances中元素从小到大排序后的索引值sortedDistIndices = distances.argsort()classCount = {}for i in range(k):voteIlabel = labels[sortedDistIndices[i]]classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1# 对字典按值排序，返回的是一个列表，列表元素是元组sortedClassCount = sorted(classCount.items(),key=lambda item:item[1],reverse=True)return sortedClassCount[0][0]

完整代码：

import numpy as npgroup = np.array([[1,101],[5,89],[108,5],[115,8]])
labels = ['爱情片','爱情片','动作片','动作片']def classify(inX,dataSet,labels,k):# 返回行数dataSetSize = dataSet.shape[0]# 扩展维度，相减diffMat = np.tile(inX, (dataSetSize, 1)) - dataSetsqDiffMat = diffMat**2sqDistances = sqDiffMat.sum(axis=1)distances = sqDistances**0.5#返回distances中元素从小到大排序后的索引值sortedDistIndices = distances.argsort()classCount = {}for i in range(k):voteIlabel = labels[sortedDistIndices[i]]classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1# 对字典按值排序，返回的是一个列表，列表元素是元组sortedClassCount = sorted(classCount.items(),key=lambda item:item[1],reverse=True)return sortedClassCount[0][0]test = [101,20]
test_class = classify(test, group, labels, 3)
print(test_class)

预测结果：

动作片

注：源代码使用了operator模块对字典进行排序

python补充：

四个函数，tile(),  np.sum(),  np.argsort(),  sorted(), 

（1）np.tile()

import numpy as npa = [2,3]
b  = np.tile(a,(4,3))
print(b)

[[2 3 2 3 2 3][2 3 2 3 2 3][2 3 2 3 2 3][2 3 2 3 2 3]]

（2）np.argsort():

返回从小到大排序后的索引值

import numpy as npa = np.array([1,2,3,4])
b = np.array([4,3,2,1])
print(a.argsort())
print(b.argsort())

[0 1 2 3]
[3 2 1 0]

（3）np.sum():

0：返回列相加

1：返回行相加

import numpy as npa = np.array([[1,2,3],[4,5,6],[7,8,9],[10,11,12]])
print(a)
print('---------axis=0-----------')
b = a.sum(axis=0)
print(b)
print('---------axis=1-----------')
c = a.sum(axis=1)
print(c)

[[ 1  2  3][ 4  5  6][ 7  8  9][10 11 12]]
---------axis=0-----------
[22 26 30]
---------axis=1-----------
[ 6 15 24 33]

（4）sorted():

第一个参数：可迭代对象

第二个参数，排序规则

第三个参数，是否降序，True为降序，False为升序，

返回值是一个列表，

d = {'mom':23,'linme':34,'ioio':89,'falali':232}
a = sorted(d.items(),key=lambda item:item[1],reverse=True)
print(a)
c = sorted(d.items(),key=lambda item:item[1],reverse=False)
print(c)

[('falali', 232), ('ioio', 89), ('linme', 34), ('mom', 23)]
[('mom', 23), ('linme', 34), ('ioio', 89), ('falali', 232)]

（5）数据处理过程：

import numpy as npgroup = np.array([[1,2],[6,4],[80,81],[78,83]])
print('----------group------------')
print('group: ')
print(group)test = [3,4]
mat = np.tile(test,(4,1))
print('----------mat------------')
print('mat: ')
print(mat)mat_g = mat - group
print('----------mat_g------------')
print('mat_g: ')
print(mat_g)mat_2 = mat_g**2
print('----------mat_2------------')
print('mat_2: ')
print(mat_2)mat_sum = mat_2.sum(axis=1)
print('----------mat_sum------------')
print('mat_sum: ')
print(mat_sum)

----------group------------
group: 
[[ 1  2][ 6  4][80 81][78 83]]
----------mat------------
mat: 
[[3 4][3 4][3 4][3 4]]
----------mat_g------------
mat_g: 
[[  2   2][ -3   0][-77 -77][-75 -79]]
----------mat_2------------
mat_2: 
[[   4    4][   9    0][5929 5929][5625 6241]]
----------mat_sum------------
mat_sum: 
[    8     9 11858 11866]

四、海伦数据

文件总共四列，最后一列是标签，海伦收集的样本数据主要包含以下3种特征：

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

分析数据：数据可视化，数据归一化

数据读取，获取特征矩阵和标签，

在windows上使用open打开utf-8编码的txt文件时开头会有一个多余的字符\ufeff，它叫BOM,是用来声明编码等信息的,但python会把它当作文本解析。对UTF-16, Python将BOM解码为空字串。然而对UTF-8, BOM被解码为一个字符\ufeff。

步骤：

打开文件， 去除BOM， 获取行数， 对于每一行：

去除每行前后空白符， 按tab切分 前三列保存到特征矩阵中， 最后一保存到标签中，

def file2matrix(filename):fr = open(filename,'r',encoding = 'utf-8')arrayOLines = fr.readlines()#针对有BOM的UTF-8文本，应该去掉BOM，否则后面会引发错误。arrayOLines[0]=arrayOLines[0].lstrip('\ufeff')numberOfLines = len(arrayOLines)returnMat = np.zeros((numberOfLines,3))classLabelVector = []index = 0for line in arrayOLines:line = line.strip()listFromLine = line.split('\t')#将数据前三列提取出来,存放到returnMat的NumPy矩阵中,也就是特征矩阵returnMat[index,:] = listFromLine[0:3]if listFromLine[-1] == 'didntLike':classLabelVector.append(1)elif listFromLine[-1] == 'smallDoses':classLabelVector.append(2)elif listFromLine[-1] == 'largeDoses':classLabelVector.append(3)index += 1return returnMat, classLabelVector

归一化步骤：

1、找出每一列最大、小值，返回值是一维列表，每个元素代表该列最大、小值

2、最大值列表减去最小值列表得出差列表

3、将最小值列表扩展为数据集大小，

4、将差值列表扩展为数据集大小，

5、原始数据减去最小值扩展，然后除以差值扩展

def autoNorm(dataSet):minVals = dataSet.min(0)maxVals = dataSet.max(0)ranges = maxVals - minValsnormDataSet = np.zeros(np.shape(dataSet))m = dataSet.shape[0]# 原始值减去最小值normDataSet = dataSet - np.tile(minVals, (m, 1))normDataSet = normDataSet / np.tile(ranges, (m, 1))return normDataSet, ranges, minVals

则全部代码：

import numpy as npdef classify(inX,dataSet,labels,k):# 返回行数dataSetSize = dataSet.shape[0]# 扩展维度，相减diffMat = np.tile(inX, (dataSetSize, 1)) - dataSetsqDiffMat = diffMat**2sqDistances = sqDiffMat.sum(axis=1)distances = sqDistances**0.5#返回distances中元素从小到大排序后的索引值sortedDistIndices = distances.argsort()classCount = {}for i in range(k):voteIlabel = labels[sortedDistIndices[i]]classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1# 对字典按值排序，返回的是一个列表，列表元素是元组sortedClassCount = sorted(classCount.items(),key=lambda item:item[1],reverse=True)return sortedClassCount[0][0]def file2matrix(filename):fr = open(filename,'r',encoding = 'utf-8')arrayOLines = fr.readlines()#针对有BOM的UTF-8文本，应该去掉BOM，否则后面会引发错误。arrayOLines[0]=arrayOLines[0].lstrip('\ufeff')numberOfLines = len(arrayOLines)returnMat = np.zeros((numberOfLines,3))classLabelVector = []index = 0for line in arrayOLines:line = line.strip()listFromLine = line.split('\t')#将数据前三列提取出来,存放到returnMat的NumPy矩阵中,也就是特征矩阵returnMat[index,:] = listFromLine[0:3]if listFromLine[-1] == 'didntLike':classLabelVector.append(1)elif listFromLine[-1] == 'smallDoses':classLabelVector.append(2)elif listFromLine[-1] == 'largeDoses':classLabelVector.append(3)index += 1return returnMat, classLabelVectordef autoNorm(dataSet):minVals = dataSet.min(0)maxVals = dataSet.max(0)ranges = maxVals - minValsnormDataSet = np.zeros(np.shape(dataSet))m = dataSet.shape[0]# 原始值减去最小值normDataSet = dataSet - np.tile(minVals, (m, 1))normDataSet = normDataSet / np.tile(ranges, (m, 1))return normDataSet, ranges, minValsdef main():filename = "datingTestSet.txt"datingDataMat, datingLabels = file2matrix(filename)normMat, ranges, minVals = autoNorm(datingDataMat)# 行数m = normMat.shape[0]# 测试比率hoRatio = 0.10numTestVecs = int(m * hoRatio)#分类错误计数errorCount = 0.0for i in range(numTestVecs):classifierResult = classify(normMat[i,:], normMat[numTestVecs:m,:], datingLabels[numTestVecs:m], 4)print("分类结果:%s\t真实类别:%d" % (classifierResult, datingLabels[i]))if classifierResult != datingLabels[i]:print('分类： ',classifierResult)print('真实： ',datingLabels[i])errorCount += 1.0print("错误率:%f%%" %(errorCount/float(numTestVecs)*100))main()

结果（只输出最后几行）：

分类结果:2	真实类别:3
分类：  2
真实：  3
分类结果:1	真实类别:1
分类结果:2	真实类别:2
分类结果:1	真实类别:1
分类结果:3	真实类别:3
分类结果:3	真实类别:3
分类结果:2	真实类别:2
分类结果:2	真实类别:1
分类：  2
真实：  1
分类结果:1	真实类别:1
错误率:4.000000%

python函数：min(),max(),    列表切分

（1）min(),max()

0：列最值

1：行最值

空：全局最值

import numpy as np
a = np.array([[1,2,3,10,4,5],[2,3,4,3,5,6],[3,4,5,4,6,7]])
print(a)print('-------全局最大小------')
print(a.min())
print(a.max())print('------列最大小-------')
print(a.min(0))
print(a.max(0))print('------行最大小-------')
print(a.min(1))
print(a.max(1))

[[ 1  2  3 10  4  5][ 2  3  4  3  5  6][ 3  4  5  4  6  7]]
-------全局最大小------
1
10
------列最大小-------
[1 2 3 3 4 5]
[ 3  4  5 10  6  7]
------行最大小-------
[1 2 3]
[10  6  7]

（2）列表切分：

import numpy as np
a = np.array([[1,2,3,4,5],[2,3,4,5,6],[3,4,5,6,7]])
print(a)
print('----------------')
print('a[2,:]: ')
print(a[2,:])
print('----------------')
print('a[0:2,:]: ')
print(a[0:2,:])
print('----------------')
print('a[0:2]: ')
print(a[0:2])

[[1 2 3 4 5][2 3 4 5 6][3 4 5 6 7]]
----------------
a[2,:]: 
[3 4 5 6 7]
----------------
a[0:2,:]: 
[[1 2 3 4 5][2 3 4 5 6]]
----------------
a[0:2]: 
[[1 2 3 4 5][2 3 4 5 6]]

五、使用SKLearn中的KNN对手写字体进行处理

步骤：

1、获取训练集特征矩阵，标签

 2、使用训练集特征矩阵、标签初始化KNN实例

3、获取测试集特征矩阵，标签 4、预测测试集，记录正确率

其实即代码：

实例KNN： neigh = kNN(n_neighbors = 3, algorithm = 'auto') neigh.fit(trainingMat, hwLabels)

预测： classifierResult = neigh.predict(vectorUnderTest)

首先将32*32的数据展开成1*1024，然后实例KNN，预测，代码如下：

import numpy as np
from os import listdir
from sklearn.neighbors import KNeighborsClassifier as kNN# 将32*32展开成1*1024
def img2vector(filename):returnVect = np.zeros((1, 1024))fr = open(filename)for i in range(32):lineStr = fr.readline()#每一行的前32个元素依次添加到returnVect中for j in range(32):returnVect[0, 32*i+j] = int(lineStr[j])return returnVectdef handwritingClassTest():hwLabels = []# 训练集列表trainingFileList = listdir('trainingDigits')m = len(trainingFileList)trainingMat = np.zeros((m, 1024))# 获取训练集特征矩阵及其标签for i in range(m):# 训练集文件名fileNameStr = trainingFileList[i]# 数字classNumber = int(fileNameStr.split('_')[0])# 训练集标签列表hwLabels.append(classNumber)# 训练集特征矩阵，即 M*1024trainingMat[i,:] = img2vector('trainingDigits/%s' % (fileNameStr))# 构建分类器neigh = kNN(n_neighbors = 3, algorithm = 'auto')neigh.fit(trainingMat, hwLabels)# 测试集文件名列表testFileList = listdir('testDigits')errorCount = 0.0# 测试集数量mTest = len(testFileList)for i in range(mTest):# 文件名fileNameStr = testFileList[i]# 类别classNumber = int(fileNameStr.split('_')[0])# 特征矩阵vectorUnderTest = img2vector('testDigits/%s' % (fileNameStr))# 预测结果classifierResult = neigh.predict(vectorUnderTest)print("分类返回结果为%d\t真实结果为%d" % (classifierResult, classNumber))if(classifierResult != classNumber):errorCount += 1.0print("总共错了%d个数据\n错误率为%f%%" % (errorCount, errorCount/mTest * 100))handwritingClassTest()

结果（最后几行输出）：

分类返回结果为9	真实结果为9
分类返回结果为9	真实结果为9
分类返回结果为9	真实结果为9
分类返回结果为9	真实结果为9
分类返回结果为9	真实结果为9
分类返回结果为9	真实结果为9
分类返回结果为9	真实结果为9
分类返回结果为9	真实结果为9
分类返回结果为9	真实结果为9
分类返回结果为9	真实结果为9
分类返回结果为9	真实结果为9
总共错了12个数据
错误率为1.268499%

我们发现，使用SKLearn确实比自己手写要方便的多。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！