一、KNN算法概述
KNN（k-Nearest Neighbor）算法，又称K近邻算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。简单来说，k近邻算法采用测量不同特征值之间的距离方法进行分类。
- 优点：精度高、对异常值不敏感、无数据输入假定；
- 缺点：计算复杂度高、空间复杂度高；
- 适用数据范围：数值型和标称型。
工作原理
存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似的数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。——摘自《机器学习实战》
缺点
- 该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的 K 个邻居中大容量类的样本占多数。因此可以采用权值的方法（和该样本距离小的邻居权值大）来改进。
- 该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的 K 个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。
二、算法的Python实现
from numpy import *
import operator
# 创建数据
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
# kNN算法
def classify0(inX, dataSet,labels,k):
'''
参数inX是用于分类的输入向量
参数dataSet是输入的训练样本集
参数labels是标签向量
参数k是用于选择最近邻居的数目
'''
dataSetSize = dataSet.shape[0]
# 使用距离公式计算距离
diffMat = tile(inX, (dataSetSize,1)) - dataSet
sqDiffMat = diffMat**2
sqDistances = sqDiffMat.sum(axis=1)
distances = sqDistances**0.5
#按照距离递增次序排序
sortedDistIndicies = distances.argsort()
classCount={}
# 选择距离最小的k个点
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=True)
# 返回前k个点出现频率最高的类别作为当前点的预测分类
return sortedClassCount[0][0]
group,labels = createDataSet()
classify0([0,0],group,labels,3)
三、使用sklearn中的kNN方法
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn import neighbors,datasets
# 导入sklearn中的neighbors
#加载鸢尾花数据
iris = datasets.load_iris()
data = pd.DataFrame(iris.data,columns=iris.feature_names)
data['target'] = iris.target
tmp = pd.DataFrame({'target':[0,1,2],
'target_name':iris.target_names})
data = pd.merge(data,tmp,on = 'target')
# 创建knn模型并训练
knn = neighbors.KNeighborsClassifier()
knn.fit(iris.data,data['target_name'])
#预测
predict_data = knn.predict([[0.2,0.1,0.3,0.4]])
四、案例：使用KNN算法改进约会网站的配对效果
《机器学习实战》中的案例有点麻烦，所以这里直接调用sklearn模块。
相关数据“dataTestingSet2.txt”来自《机器学习实战》
import pandas as pd
from sklearn import neighbors
#使用pandas导入数据
datingTest = pd.read_table("datingTestSet2.txt",sep='\t',header=None)
datingTest.columns = ['飞行里程','游戏时间百分比','每周消费冰淇淋公升数','target']
#不知道DataFrame怎么直接映射，所以写了个for循环
tmp = []
for i in datingTest['target']:
if i == 1:
tmp.append("dislike")
elif i == 2:
tmp.append("goodfeeling")
else:
tmp.append("like")
datingTest['target_name'] = tmp
datingTrain = datingTest.iloc[:,0:3]
#创建模型并训练
knn = neighbors.KNeighborsClassifier()
knn.fit(datingTrain,datingTest['target_name'])
predictTest = knn.predict([[32688,8.745137,0.857348]])
print(predictTest)
