一、KNN算法概述
工作原理：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都纯在标签，就每一个样本都有一个标签与之对应。输入没带标签的新数据之后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签，然后给新数据该标签。我们只选择样本数据集中前k个最相似的数据，最后选择k个最相似数据中出现次数最多的分类，作为新数据的分类。
光看文字理解显然不够深刻，来看看图片。
假定新加入了一个绿正方形，现在我们要判定它是属于三角形还是属于圆形。首先根据先看距离正方形最近的图形有哪些，根据它们离正方形的距离进行排序，再根据确定的k值进行划分，选出离目标最近的k个图形，然后判定在k个里面哪个图形占多数，占多数的则把该目标归为哪一类。
这样应该很好理解，也说明了KNN算法的结果很大程度取决于K的选择，其中K通常是不大于20的整数。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
二、距离度量
因为在各种不同的环境下采用knn算法，度量变量距离也有许多种不同的算法。免了对象之间的匹配问题。在KNN算法中一般采用的是欧氏距离或曼哈顿距离：
欧氏距离（二维）：
曼哈顿距离（二维）：
三、实现算法
首先算法一般流程
.收集数据->处理数据（标准化）->分析数据->训练算法->测试算法->使用算法
先创建数据导入块
import numpy as np import operator from matplotlib import pyplot as plt #创建数据集 def createrDataSet(): group = np.array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]]) labels = ['A','A','B','B'] return group,labels
类似这种效果，如何开始写入knn算法
from numpy import * import operator #创建数据集 def createrDataSet(): group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]]) labels = ['A','A','B','B'] return group,labels ture = 1 #inX:输入向量; dataSet:训练样本集; labels:标签向量 k=最近邻居个数; 其中标签元素数目和矩阵dataSet的行数相同。 def classify0(inX,dataSet,labels,k): dataSetSize = dataSet.shape[0] #行数 #计算欧式距离 diffMat = tile(inX,(dataSetSize,1))-dataSet #扩展dataSet行，分别相减，形成（x1-x2）矩阵 sqDiffMat = diffMat**2 sqDistances = sqDiffMat.sum(axis=1) distances = sqDistances**0.5 sortedDistIndicies = distances.argsort()#从小到大排序，获得索引值(下标） #选择距离最小的k个点 classCount={} for i in range(k): voteIlabel = labels[sortedDistIndicies[i]] classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 #排序 sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=ture) return sortedClassCount[0][0]
具体实现过程已经在代码中标识出来了。
我们可以通过简单的测试。
import KNN from numpy import * dataSet,labels = KNN.createrDataSet() inX = array([0,0.3]) k = 3 output = KNN.classify0(inX,dataSet,labels,k) print("测试数据为:",inX,"分类结果为：",output)
PS.按照机器学习实战的那本来敲代码的话可能会遇到'dict' object has no attribute 'iteritems'。
原因：iteritems是为python2环境中dict的函数。在python3报错，将iteritems改为items即可。
四、实战练习
练习当然是我们的海伦约会实例，也是最常见拿来练手的例子了。
海伦女士一直使用在线约会网站寻找适合自己的约会对象。尽管约会网站会推荐不同的人选，但她并不是喜欢每一个人。经过一番总结，她发现自己交往过的人可以进行如下分类：
不喜欢的人
魅力一般的人
极具魅力的人
首先准备数据，海伦收集的样本数据主要包含以下3种特征：
每年获得的飞行常客里程数
玩视频游戏所消耗时间百分比
每周消费的冰淇淋公升数
1.转换数据
将文本记录转换为Numpy解析程序
#处理数据格式 #输入文件名字符串，输出为训练样本矩阵和类标签 def file2matrix(filename): fr = open(filename) arrayOLines = fr.readlines()#得到文件行数 numberOfLines = len(arrayOLines) returnMat = zeros((numberOfLines,3))#得到与之对应行数，3列的0填充矩阵 classLabelVector = [] index = 0 for line in arrayOLines: line = line.strip()#截取所有回车字符 listFromLine = line.split('\t')#按tap格式分割 returnMat[index,:] = listFromLine[0:3]#从头开始填充 classLabelVector.append((listFromLine[-1]))#将标签保留 index += 1 # datingDataMat,datingLabels = file2matrix('datingTestSet2.txt') # print(datingDateMat,datingLabels) from collections import Counter ##将列表的最后一列由字符串转化为数字，便于以后的计算 dictClassLabel = Counter(classLabelVector) classLabel = [] kind = list(dictClassLabel) for item in classLabelVector: if item == kind[0]: item = 1 elif item == kind[1]: item = 2 else: item = 3 classLabel.append(item) return returnMat,classLabel#####将文本中的数据导入到列表
我们可以看到数据
2.分析数据
我们可以使用Matplotlib创建散点图
import matplotlib import matplotlib.pyplot as plt #绘制散点图 fig = plt.figure() ax = fig.add_subplot(111)#分割为1行1列第1块 ax.scatter(datingDataMat[:,1], datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels)) plt.show()
这里对比一下‘玩视频游戏所消耗时间百分比’和‘每周消费的冰淇淋公升数’
很明显
数据还没有处理好看不出什么效果。
3.数据归一化
因为根据knn采用的为欧式距离，在数据属性权重相同的情况下，数字差值最大的属性对计算结果影响最大，所以我们必须使用数据归一化避免相比差值过大严重影响计算结果。
那么接下来我们进行数据归一化，考虑到使用Min-Max标准可能如果max和min不稳定，很容易使得归一化结果不稳定，使得后续使用效果也不稳定。所以我们采用Z-score标准化。数据预处理归一化详细解释
from sklearn.preprocessing import StandardScaler def autoNorm(dataSet): sc = StandardScaler() normDataSet =sc.fit_transform(datingDataMat) mean = sc.mean_ std = sqrt(sc.var_) return normDataSet,mean,std
很明显归一化的数据很易于分析：
4.测试算法
接下来开始评估我们算法的可靠性，通常我们只提供已有数据的90%作为训练样本训练分类器，而使用其余的10%数据去测试分类器。一开始想使用线性回归的
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.1, random_state=0)
发现只能二值计算，有点尴尬，不知道大家有什么好的方法来划分数据集，安装书上的方法属实是最原始的划分方法。
def datingClassTest(): #将返回的特征矩阵和分类向量分别存储到datingDataMat和datingLabels中 datingDataMat, datingLabels = file2matrix('datingTestSet2.txt') #取所有数据的百分之十 hoRatio = 0.10 #数据归一化,返回归一化后的矩阵,数据范围,数据最小值 normMat= autoNorm(datingDataMat) #获得normMat的行数 m = normMat.shape[0] #百分之十的测试数据的个数 numTestVecs = int(m * hoRatio) #分类错误计数 errorCount = 0.0 for i in range(numTestVecs): #前numTestVecs个数据作为测试集,后m-numTestVecs个数据作为训练集 classifierResult = KNN.classify0(normMat[i,:], normMat[numTestVecs:m,:], datingLabels[numTestVecs:m], 4) print("分类结果:%s\t真实类别:%d" % (classifierResult, datingLabels[i])) if classifierResult != datingLabels[i]: errorCount += 1.0 print("错误率:%f%%" % (errorCount / float(numTestVecs) * 100))
这是没简化标签时候截的图，后面优化了一下便于计算
5.使用算法
经过测试我们的knn算法还算不错，现在我们可以编写一个窗口来使用这个分类器了：
def classifyPerson(): #输出结果 resultList = ['讨厌','有些喜欢','非常喜欢'] #三维特征用户输入 precentTats = float(input("玩视频游戏所耗时间百分比:")) ffMiles = float(input("每年获得的飞行常客里程数:")) iceCream = float(input("每周消费的冰激淋公升数:")) #打开的文件名 filename = "datingTestSet2.txt" #打开并处理数据 datingDataMat, datingLabels = file2matrix(filename) #训练集归一化 normMat, mean, std = autoNorm(datingDataMat) #生成NumPy数组,测试集 inArr = array([ffMiles, precentTats, iceCream]) #测试集归一化 norminArr = (inArr - mean) / std #返回分类结果 classifierResult =KNN.classify0(norminArr, normMat, datingLabels, 3) #打印结果 print("你可能%s这个人" % (resultList[classifierResult-1])) classifyPerson()
附上我理想女友的数据
确实有点喜欢哈哈哈
总结
具体算法应该很好理解，要使用起来也不难，很好掌握的一个算法，就是在不同的环境下要考虑该如何改进再使用。下一篇开始学习决策树了。
