机器学习之KNN算法

1 KNN算法

1.1 KNN算法简介

　　KNN（K-Nearest Neighbor）工作原理：存在一个样本数据集合，也称为训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类对应的关系。输入没有标签的数据后，将新数据中的每个特征与样本集中数据对应的特征进行比较，提取出样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k近邻算法中k的出处，通常k是不大于20的整数。最后选择k个最相似数据中出现次数最多的分类作为新数据的分类。

　　说明：KNN没有显示的训练过程，它是“懒惰学习”的代表，它在训练阶段只是把数据保存下来，训练时间开销为0，等收到测试样本后进行处理。

　　举例：以电影分类作为例子，电影题材可分为爱情片，动作片等，那么爱情片有哪些特征？动作片有哪些特征呢？也就是说给定一部电影，怎么进行分类？这里假定将电影分为爱情片和动作片两类，如果一部电影中接吻镜头很多，打斗镜头较少，显然是属于爱情片，反之为动作片。有人曾根据电影中打斗动作和接吻动作数量进行评估，数据如下：

电影名称	打斗镜头	接吻镜头	电影类别
Califoria Man	3	104	爱情片
Beautigul Woman	1	81	爱情片
Kevin Longblade	101	10	动作片
Amped II	98	2	动作片

　　给定一部电影数据（18，90）打斗镜头18个，接吻镜头90个，如何知道它是什么类型的呢？KNN是这样做的，首先计算未知电影与样本集中其他电影的距离（这里使用曼哈顿距离），数据如下：

电影名称	与未知分类电影的距离
Califoria Man	20.5
Beautigul Woman	19.2
Kevin Longblade	115.3
Amped II	118.9

　　现在我们按照距离的递增顺序排序，可以找到k个距离最近的电影，加入k=3,那么来看排序的前3个电影的类别，爱情片，爱情片，动作片，下面来进行投票，这部未知的电影爱情片2票，动作片1票，那么我们就认为这部电影属于爱情片。

　

1.2 KNN算法优缺点

　　优点：精度高，对异常值不敏感、无数据输入假定

　　缺点：计算复杂度高、空间复杂度高

1.3 KNN算法python代码实现

　　实现步骤：

　　　　（1）计算距离

　　　　（2）选择距离最小的k个点

　　　　（3）排序

　　Python 3代码：

import numpy as np
import operator

def classify(intX,dataSet,labels,k):

'''

KNN算法

'''

#numpy中shape[0]返回数组的行数，shape[1]返回列数

dataSetSize = dataSet.shape[0]

#将intX在横向重复dataSetSize次，纵向重复1次

#例如intX=([1,2])--->([[1,2],[1,2],[1,2],[1,2]])便于后面计算

diffMat = np.tile(intX,(dataSetSize,1))-dataSet

#二维特征相减后乘方

sqdifMax = diffMat**2

#计算距离

seqDistances = sqdifMax.sum(axis=1)

distances = seqDistances**0.5

print ("distances:",distances)

#返回distance中元素从小到大排序后的索引

sortDistance = distances.argsort()

print ("sortDistance:",sortDistance)

classCount = {}

for i in range(k):

#取出前k个元素的类别

voteLabel = labels[sortDistance[i]]

print ("第%d个voteLabel=%s",i,voteLabel)

classCount[voteLabel] = classCount.get(voteLabel,0)+1

#dict.get(key,default=None),字典的get()方法,返回指定键的值,如果值不在字典中返回默认值。

#计算类别次数


#key=operator.itemgetter(1)根据字典的值进行排序

#key=operator.itemgetter(0)根据字典的键进行排序

#reverse降序排序字典

sortedClassCount = sorted(classCount.items(),key = operator.itemgetter(1),reverse = True)

#结果sortedClassCount = [('动作片', 2), ('爱情片', 1)]

print ("sortedClassCount:",sortedClassCount)

return sortedClassCount[0][0]

 

2 KNN算法实例

2.1 KNN实现电影分类

　　

import numpy as np
import operator

def createDataset():

#四组二维特征

group = np.array([[5,115],[7,106],[56,11],[66,9]])

#四组对应标签

labels = ('动作片','动作片','爱情片','爱情片')

return group,labels

def classify(intX,dataSet,labels,k):

'''

KNN算法

'''

#numpy中shape[0]返回数组的行数，shape[1]返回列数

dataSetSize = dataSet.shape[0]

#将intX在横向重复dataSetSize次，纵向重复1次

#例如intX=([1,2])--->([[1,2],[1,2],[1,2],[1,2]])便于后面计算

diffMat = np.tile(intX,(dataSetSize,1))-dataSet

#二维特征相减后乘方

sqdifMax = diffMat**2

#计算距离

seqDistances = sqdifMax.sum(axis=1)

distances = seqDistances**0.5

print ("distances:",distances)

#返回distance中元素从小到大排序后的索引

sortDistance = distances.argsort()

print ("sortDistance:",sortDistance)

classCount = {}

for i in range(k):

#取出前k个元素的类别

voteLabel = labels[sortDistance[i]]

print ("第%d个voteLabel=%s",i,voteLabel)

classCount[voteLabel] = classCount.get(voteLabel,0)+1

#dict.get(key,default=None),字典的get()方法,返回指定键的值,如果值不在字典中返回默认值。

#计算类别次数


#key=operator.itemgetter(1)根据字典的值进行排序

#key=operator.itemgetter(0)根据字典的键进行排序

#reverse降序排序字典

sortedClassCount = sorted(classCount.items(),key = operator.itemgetter(1),reverse = True)

#结果sortedClassCount = [('动作片', 2), ('爱情片', 1)]

print ("sortedClassCount:",sortedClassCount)

return sortedClassCount[0][0]



if __name__ == '__main__':

group,labels = createDataset()

test = [20,101]

test_class = classify(test,group,labels,3)

print (test_class)

 

2.2 改进约会网站匹配

　　这个例子简单说就是通过KNN找到你喜欢的人，首先数据样本包含三个特征，（a）每年获得的飞行常客里程数（b）玩游戏消耗的时间（c）每周消耗的冰激淋公升数，样本数据放在txt中，如下，前三列为三个特征值，最后一列为标签

下面

首先读取数据，获取数据集和标签

def file2matrix(filename):

fr = open(filename)

arraylines = fr.readlines()

#获取行数

numberoflines = len(arraylines)

#返回numpy的数据矩阵,目前矩阵数据为0

returnMat = np.zeros([numberoflines,3])

#返回的分类标签

classLabelVector = []

#行的索引

index = 0

for line in arraylines:

#str.strip(rm) 删除str头和尾指定的字符 rm为空时，默认删除空白符(包括'n','r','t',' ')

line = line.strip()

#每行数据是t划分的，将每行数据按照t进行切片划分

listFromLine = line.split('t')

#取出前三列数据存放到returnMat

returnMat[index,:] = listFromLine[0:3]

#根据文本中标记的喜欢程度进行分类

if listFromLine[-1] == "didntLike":

classLabelVector.append(1)

elif listFromLine[-1] == "smallDoses":

classLabelVector.append(2)

else:

classLabelVector.append(3)

index += 1

return returnMat,classLabelVector

数据和标签我们可以打印一下：

下面

下面用Matplotlib作图看一下数据信息：

from matplotlib.font_manager import FontProperties
import numpy as np
import matplotlib.pyplot as plt
from prepareData_1 import file2matrix
import matplotlib.lines as mlines
# from matplotlib.font_manage import FontProperties
'''
函数说明：数据可视化
Parameters:

datingDataMat - 特征矩阵

datingLabels - 分类标签向量
Returns:

无
'''
def showDatas(datingDataMat,datingLabels):

#设置汉子格式

font = FontProperties(fname=r"c:windowsfontssimsun.ttc", size=14)

#函数返回一个figure图像和一个子图ax的array列表。

fig,axs = plt.subplots(nrows=2,ncols=2,sharex=False,sharey=False,figsize=(13,8))


numberofLabels = len(datingLabels)

LabelColors = []

for i in datingLabels:

if i==1:

LabelColors.append('black')

if i ==2:

LabelColors.append('orange')

if i==3:

LabelColors.append("red")

#画散点图，以数据矩阵的第一列（飞行常客历程）、第二列（玩游戏）数据话散点图

#散点大小为15 透明度为0.5

axs[0][0].scatter(x=datingDataMat[:,0],y=datingDataMat[:,1],color=LabelColors,

s=15,alpha=0.5)

axs0_title_text=axs[0][0].set_title(u"每年获得的飞行里程数与玩视频游戏消耗时间占比",

FontProperties=font)

axs0_xlabel_text=axs[0][0].set_xlabel("每年获得的飞行常客里程数",FontProperties=font)

axs0_ylabel_text=axs[0][0].set_ylabel("玩游戏消耗的时间",FontProperties=font)

plt.setp(axs0_title_text,size=9,weight='bold',color='red')

#画散点图，以数据矩阵的第一列（飞行常客历程）、第三列（冰激淋公斤数）数据话散点图

#散点大小为15 透明度为0.5

axs[0][1].scatter(x=datingDataMat[:,0],y=datingDataMat[:,2],color=LabelColors,

s=15,alpha=0.5)

axs0_title_text=axs[0][0].set_title("每年获得的飞行里程数与冰激淋公斤数占比",

FontProperties=font)

axs0_xlabel_text=axs[0][0].set_xlabel("每年获得的飞行常客里程数",FontProperties=font)

axs0_ylabel_text=axs[0][0].set_ylabel("所吃冰激淋公斤数",FontProperties=font)

plt.setp(axs0_title_text,size=9,weight='bold',color='red')

#画散点图，以数据矩阵的第二列（玩游戏）、第三列（冰激淋公斤数）数据话散点图

#散点大小为15 透明度为0.5

axs[1][0].scatter(x=datingDataMat[:,1],y=datingDataMat[:,2],color=LabelColors,

s=15,alpha=0.5)

axs0_title_text=axs[0][0].set_title("玩游戏时间与冰激淋公斤数占比",

FontProperties=font)

axs0_xlabel_text=axs[0][0].set_xlabel("每年获得的飞行常客里程数",FontProperties=font)

axs0_ylabel_text=axs[0][0].set_ylabel("所吃冰激淋公斤数",FontProperties=font)

plt.setp(axs0_title_text,size=9,weight='bold',color='red')


#设置图例

didntLike = mlines.Line2D([],[],color='black',marker='.',markersize=6,label='didntlike')

smallDose = mlines.Line2D([],[],color='orange',marker='.',markersize=6,label='smallDose')

largeDose = mlines.Line2D([],[],color='red',marker='.',markersize=6,label='largeDose')


#添加图例

axs[0][0].legend(handles=[didntLike,smallDose,largeDose])

axs[0][1].legend(handles=[didntLike,smallDose,largeDose])

axs[1][0].legend(handles=[didntLike,smallDose,largeDose])


plt.show()

if __name__ == '__main__':

filename = "datingTestSet.txt"

returnMat,classLabelVector = file2matrix(filename)

showDatas(returnMat,classLabelVector)

这里我把py文件分开写了，还要注意txt数据的路径，高大上的图：

 

 

样本数据中的到底喜欢什么样子的人？自己去分析一下吧。下面要对数据进行归一化，归一化的原因就不多说了，

from prepareData_1 import file2matrix
import numpy as np
'''
函数说明：数据归一化
Parameters:

dataSet - 特征矩阵
Returns:

normDataSet - 归一化后的特征矩阵

ranges - 数据范围

minVals - 数据最小值
'''

def autoNorm(dataSet):

#获得数据的最大最小值

print (dataSet)

print ("**********************")

minVals = dataSet.min(0)

maxVals = dataSet.max(0)

print ("minValues:",minVals)

print ("maxValuse:",maxVals)

#计算最大最小值的差

ranges = maxVals - minVals

print ()

#shape(dataSet)返回dataSet的矩阵行列数

normDataSet=np.zeros(np.shape(dataSet))

#返回dataSet的行数

m = dataSet.shape[0]

#原始值减去最小值

normDataSet=dataSet-np.tile(minVals,(m,1))

#除以最大值和最小值的差，得到的归一化的数据

normDataSet = normDataSet/np.tile(ranges,(m,1))

return normDataSet,ranges,minVals

归一化后的数据如下：

有了以上步骤，下面就可以构建完整的约会分类，去找你喜欢的人了：

from prepareData_1 import file2matrix
from dataNormal_3 import autoNorm
import operator
import numpy as np
'''
函数说明：knn算法，分类器
Parameters:

inX - 用于分类的数据（测试集）

dataset - 用于训练的数据（训练集）

labes - 分类标签

k - knn算法参数，选择距离最小的k个点
Returns:

sortedClassCount[0][0] - 分类结果
'''
def classify0(inX,dataset,labes,k):

dataSetSize = dataset.shape[0]
#返回行数

diffMat = np.tile(inX,(dataSetSize,1))-dataset

sqDiffMat = diffMat**2

sqDistances = sqDiffMat.sum(axis=1)

distances = sqDistances**0.5

sortedDistIndices
=distances.argsort()

classCount = {}

for i in range(k):

voteLabel = labes[sortedDistIndices[i]]

classCount[voteLabel] = classCount.get(voteLabel,0)+1

sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)

return sortedClassCount[0][0]
def datingClassTest():

#filename="test.txt"

filename = "datingTestSet.txt"

datingDataMat,datingLabels = file2matrix(filename)

#取所有数据的10%

hoRatio = 0.1

#数据归一化，返回归一化后的矩阵，数据范围，数据最小值

normMat,ranges,minVals = autoNorm(datingDataMat)

#获得nornMat的行数

m = normMat.shape[0]

#百分之十的测试数据的个数

numTestVecs = int(m*hoRatio)

#分类错误计数

errorCount = 0.0


for i in range(numTestVecs):

#前numTestVecs个数据作为测试集，后m-numTestVecs个数据作为训练集

classifierResult = classify0(normMat[i,:],normMat[numTestVecs:m,:],

datingLabels[numTestVecs:m],10)

print ("分类结果：%d t真实类别：%d"%(classifierResult,datingLabels[i]))

if classifierResult != datingLabels[i]:

errorCount += 1.0

print ("错误率：%f"%(errorCount/float(numTestVecs)*100))

if __name__ == '__main__':

datingClassTest()

都是上面的步骤，这里就不解释了，结果如下所示：

2.3 手写数字识别

　　数据可以样例可以打开文本文件进行查看，其中txt文件名的第一个数字为本txt中的数字，目录trainingDigits中包含了大约2000个例子，每个数字大约有200个样本，testDigits中包含900个测试数据，我们使用trainingDigits中的数据训练分类器，testDigits中的数据作为测试，两组数据没有重合。

数据在这里：https://github.com/Jenny0611/Ml_Learning01

首先我们要将图像数据处理为一个向量，将32*32的二进制图像信息转化为1*1024的向量，再使用前面的分类器，代码如下：

 

import numpy as np
import operator
from os import listdir
from sklearn.neighbors import KNeighborsClassifier as kNN

'''
函数说明：将32*32的二进制图片转换为1*1024向量
Parameters:

filename - 文件名
Returns:

returnVect - 返回的二进制图像的1*1024向量
'''
def img2vector(filename):

#创建1*1024的0向量

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 returnVect

'''
函数说明：手写数字分类测试
Parameters:

filename - 无
Returns:

returnVect - 无
'''
def handwritingClassTest():

#测试集的labels

hwLabels=[]

#返回trainingDigits目录下的文件名

trainingFileList=listdir('trainingDigits')

#返回文件夹下文件的个数

m=len(trainingFileList)

#初始化训练的Mat矩阵的测试集

trainingMat=np.zeros((m,1024))

#从文件名中解析出训练集的类别

for i in range(m):

fileNameStr=trainingFileList[i]

classNumber = int(fileNameStr.split('_')[0])

#将获取的类别添加到hwLabels中

hwLabels.append(classNumber)

#将每一个文件的1*1024数据存储到trainingMat矩阵中

trainingMat[i,:]=img2vector('trainingDigits/%s'%(fileNameStr))

#构建KNN分类器

neigh = kNN(n_neighbors=3,algorithm='auto')

#拟合模型，trainingMat为测试矩阵,hwLabels为对应的标签

neigh.fit(trainingMat,hwLabels)

#返回testDigits目录下的文件列表

testFileList=listdir('testDigits')

errorCount=0.0

mTest=len(testFileList)

#从文件中解析出测试集的类别并进行分类测试

for i in range(mTest):

fileNameStr=testFileList[i]

classNumber=int(fileNameStr.split('_')[0])

#获得测试集的1*1024向量用于训练

vectorUnderTest=img2vector('testDigits/%s'%(fileNameStr))

#获得预测结果

classifierResult=neigh.predict(vectorUnderTest)

print ("分类返回结果%dt真实结果%d"%(classifierResult,classNumber))

if (classNumber != classifierResult):

errorCount += 1.0

print ("总共错了%d个t错误率为%f%%"%(errorCount,errorCount/mTest*100))

if __name__ == '__main__':

handwritingClassTest()

 

2.4 小结

　　KNN是简单有效的分类数据算法，在使用时必须有训练样本数据，还要计算距离，如果数据量非常大会非常消耗空间和时间。它的另一个缺陷是无法给出任何数据的基础结构信息，因此我们无法平均实例样本和典型实例样本具体特征，而决策树将使用概率测量方法处理分类问题，以后章节会介绍。

 

 

 

 

本文参考：http://blog.csdn.net/c406495762/article/details/75172850

　　　　　《机器学习实战》