参考：

KNN简介

k-近邻算法采用测量不同特征值之间的距离方法进行分类。

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

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

使用sklearn程序包实现

sklearn.neighbors提供了基于近邻的无监督和有监督的学习方法的功能。无监督最近邻是许多其他学习方法的基础，特别是流形学习(manifold learning)和光谱聚类(spectral clustering)。有监督的 neighbors-based (基于邻居的) 学习有两种方式：离散标签数据的分类和连续标签数据的回归。
class sklearn.neighbors.KNeighborsClassifier(n_neighbors=5, *, weights='uniform', algorithm='auto', leaf_size=30, p=2, metric='minkowski', metric_params=None, n_jobs=None, **kwargs）
最近邻方法背后的原理是找到在距离上离新样本最近的一些样本，并且从这些样本中预测标签。最近邻的样本数可以是用户定义的常数(k-最近邻)，也可以根据不同的点的局部密度(基于半径的近邻学习)确定。一般来说，距离可以用任意来度量：标准的欧氏距离是最常见的选择。基于邻居的方法被称为非泛化机器学习方法，因为它们只是“记住”它的所有训练数据(可能转换成一个快速的索引结构，比如Ball树或KD树)。
尽管它很简单，但最近邻已经成功地解决了大量的分类和回归问题，包括手写数字和卫星图像等场景。作为一种非参数方法，在决策边界非常不规则的情况下通常是成功的。
sklearn.neighbors 中的类输入不管是numpy中的array数组，还是scipy.sparse矩阵都可以处理。对于密集矩阵，可以支持大量的距离度量。于稀疏矩阵，支持任意的Minkowski度量进行搜索。

参阅文档：1.6Nearest Neighbors

鸢尾花knn分类例程

鸢尾花的Knn分类示例程序一：

python


# 导入load_iris
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler

iris = load_iris()
x_train, x_test, y_train, y_test = train_test_split(iris.data, iris.target, random_state=22)

# 标准化
std = StandardScaler()
# 训练集标准化
x_train = std.fit_transform(x_train)
# 测试集的标准化操作
x_test = std.fit_transform(x_test)

# K值：算法传入参数不定的值    理论上：k = 根号(样本数)
# K值：后面会使用参数调优方法，去轮流试出最好的参数[1,3,5,10,20,100,200]
knn = KNeighborsClassifier(n_neighbors=1)

# 调用fit()
knn.fit(x_train, y_train)

# 预测测试数据集，得出准确率
y_predict = knn.predict(x_test)
print("实际测试集标签：", y_test)
print("预测测试集类别：", y_predict)
print("准确率为：", knn.score(x_test, y_test))

基于近邻的分类是一种基于实例的学习或非泛化学习：它不是试图构造一个通用的内部模型，而是简单地存储训练数据的实例。分类是由每个点的最近邻的简单多数投票中计算得到的：一个查询点被标记的数据标签是由它最近邻点中最具代表性的数据标签来决定的。

scikit-learn实现了两个不同的最近邻分类器： KNeighborsClassifier 分类器根据每个查询点的k个最近邻实现学习，其中k是用户指定的整数值。 RadiusNeighborsClassifier分类器根据每个训练点的固定半径内的邻居数实现学习，其中是用户指定的浮点值。

KNeighborsClassifier 中的K近邻分类是最常用的分类方法。k值的最佳选择是高度依赖于数据的：一般来说，较大的会抑制噪声的影响，但使分类边界不那么清晰。

在数据不均匀采样的情况下， RadiusNeighborsClassifier中基于半径的近邻分类是更好的选择。用户指定一个固定的半径，以便在稀疏的邻居中使用更少的最近邻居来进行分类。对于高维参数空间，这种方法由于所谓的 “维度灾难” 而变得不那么有效。

基本的最近邻分类使用一样的权重：也就是说，分配给查询点的值是根据最近邻居的简单多数投票计算的。在某些情况下，最好是对邻居进行加权，这样更靠近的邻居对拟合来说贡献更大。这可以通过weights关键字来实现。默认值是weights=“uniform”，为每个邻居分配同样的权重。weights = 'distance'分配的权重与到查询点的距离成反比。或者，可以提供用户定义的距离函数来计算权重.

模型调参：超参数搜索

在机器学习模型中，需要人工选择的参数称为超参数。比如随机森林中决策树的个数，人工神经网络模型中的隐藏层层数和每层的节点个数，正则项中常数大小等等，它们都需要事先指定。超参数选择不恰当，就会出现欠拟合或者过拟合的问题。我们在选择超参数有两个途径：1.凭经验；2.选择不同大小的参数，带入到模型中，挑选表现最好的参数。通过途径2选择超参数时，可以使用GridSearchCV方法，自动对输入的参数进行排列组合，并一一测试，从中选出最优的一组参数。
GridSearchCV，自动调参，只要把参数输进去，就能给出最优化的结果和参数。适合于小数据集，一旦数据的量级上去了，很难得出结果。数据量比较大的时候可以使用一个快速调优的方法——坐标下降。它其实是一种贪心算法：拿当前对模型影响最大的参数调优，直到最优化；再拿下一个影响最大的参数调优，如此下去，直到所有的参数调整完毕。这个方法的缺点就是可能会调到局部最优而不是全局最优，但是省时间省力。
通常算法不够好，需要调试参数时必不可少。比如SVM的惩罚因子C，核函数kernel，gamma参数等，对于不同的数据使用不同的参数，结果效果可能差1-5个点，sklearn为我们提供专门调试参数的函数grid_search。 class sklearn.model_selection.GridSearchCV(estimator, param_grid, *, scoring=None, n_jobs=None, refit=True, cv=None, verbose=0, pre_dispatch='2*n_jobs', error_score=nan, return_train_score=False)
参数：

estimator：scikit-learn估计器接口
param_grid：dict or list of dictionaries以参数名称（str）作为键，将参数设置列表尝试作为值的字典，或此类字典的列表，在这种情况下，将探索列表中每个字典所跨越的网格。这样可以搜索任何顺序的参数设置。
cv:确定交叉验证切分策略。None,默认使用5折交叉验证；integer,用于指定在(Stratified)KFold中的折叠次数
n_jobs: 并行数，int：个数,-1：跟CPU核数一致, 1:默认值
verbose：日志冗长度，int：冗长度，0：不输出训练过程，1：偶尔输出，>1：对每个子模型都输出。

python


from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
from sklearn.model_selection import GridSearchCV
iris = load_iris()
x_train, x_test, y_train, y_test = train_test_split(iris.data, iris.target, random_state=22)

# 标准化
std = StandardScaler()
x_train = std.fit_transform(x_train)
x_test = std.fit_transform(x_test)

# 使用网格搜索和交叉验证找到合适的参数
knn = KNeighborsClassifier()
param = {"n_neighbors": [3, 5, 10]}

gc = GridSearchCV(knn, param_grid=param, cv=2)

gc.fit(x_train, y_train)

# 训练验证集的结果
print("在交叉验证当中验证的最好结果：", gc.best_score_)    ##best_score_：成员提供优化过程期间观察到的最好的评分
print("每次交叉验证的结果为：", gc.cv_results_)     #每次交叉验证后的验证集准确率结果和训练集准确率结果
print("最优参数是：",gc.best_params_)   #best_params_：描述了已取得最佳结果的参数的组合

new_model = gc.bestestimator    #获取搜索到的最优模型

原理及其手动实现

导入数据

python


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手动实现

classify0()函数有4个输入参数：用于分类的输入向量是inX，输入的训练样本集为dataSet，标签向量为labels，最后的参数k表示用于选择最近邻居的数目，其中标签向量的元素数目和矩阵dataSet的行数相同。

python


def classify0(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={}          
    for i in range(k):  #选择距离最小的K个点
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]
# 确定前k个距离最小元素所在的主要分类，最后返回发生频率最高的元素标签

python


def file2matrix(filename):
    love_dictionary={'largeDoses':3, 'smallDoses':2, 'didntLike':1}
    fr = open(filename)
    arrayOLines = fr.readlines()
    numberOfLines = len(arrayOLines)            #get the number of lines in the file
    returnMat = zeros((numberOfLines,3))        #prepare matrix to return
    classLabelVector = []                       #prepare labels return   
    index = 0
    for line in arrayOLines:
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index,:] = listFromLine[0:3]
        if(listFromLine[-1].isdigit()):
            classLabelVector.append(int(listFromLine[-1]))
        else:
            classLabelVector.append(love_dictionary.get(listFromLine[-1]))
        index += 1
    return returnMat,classLabelVector

# 归一化
def autoNorm(dataSet):
    minVals = dataSet.min(0)    #将每列的最小值放在变量minVals中，参数0使得函数可以从列中选取最小值，而不是当前行的最小值
    maxVals = dataSet.max(0)    #将每列的最大值放在变量maxVals中
    ranges = maxVals - minVals  #计算可能的取值范围
    normDataSet = zeros(shape(dataSet))
    m = dataSet.shape[0]
    normDataSet = dataSet - tile(minVals, (m,1))    #用当前值减去最小值，然后除以取值范围，
    # tile()函数将变量内容复制成输入矩阵同样大小的矩阵
    normDataSet = normDataSet/tile(ranges, (m,1))   #element wise divide
    return normDataSet, ranges, minVals

测试：

python


def datingClassTest():
    hoRatio = 0.50      #hold out 10%
    datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')       #load data setfrom file
    normMat, ranges, minVals = autoNorm(datingDataMat)
    m = normMat.shape[0]
    numTestVecs = int(m*hoRatio)
    errorCount = 0.0
    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]))
        if (classifierResult != datingLabels[i]): errorCount += 1.0
    print("the total error rate is: %f" % (errorCount / float(numTestVecs)))
    print errorCount

def classifyPerson():
    resultList = ['not at all', 'in small doses', 'in large doses']
    percentTats = float(raw_input(\
                                  "percentage of time spent playing video games?"))
    ffMiles = float(raw_input("frequent flier miles earned per year?"))
    iceCream = float(raw_input("liters of ice cream consumed per year?"))   #raw_input函数允许用户输入文本行命令并返回用户所输入的命令
    datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')
    normMat, ranges, minVals = autoNorm(datingDataMat)
    inArr = array([ffMiles, percentTats, iceCream, ])
    classifierResult = classify0((inArr - \
                                  minVals)/ranges, normMat, datingLabels, 3)
    print "You will probably like this person: %s" % resultList[classifierResult - 1]

手写数字识别实例

首先编写一段函数img2vector，将图像转换为向量。将 32 x 32 的二进制图像矩阵转换为 1 x 1024 的向量

python


from numpy import *
import operator
from os import listdir

def img2vector(filename):
    returnVect = zeros((1,1024))
    fr = open(filename)
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVect[0,32*i+j] = int(lineStr[j])
    return returnVect

def handwritingClassTest():
    hwLabels = []
    trainingFileList = listdir('trainingDigits')           #load the training set
    m = len(trainingFileList)
    trainingMat = zeros((m,1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]     #take off .txt
        classNumStr = int(fileStr.split('_')[0])
        hwLabels.append(classNumStr)
        trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr)
    testFileList = listdir('testDigits')        #iterate through the test set
    errorCount = 0.0
    mTest = len(testFileList)
    for i in range(mTest):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]     #take off .txt
        classNumStr = int(fileStr.split('_')[0])
        vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)
        classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
        print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr)
        if (classifierResult != classNumStr): errorCount += 1.0
    print "\nthe total number of errors is: %d" % errorCount
    print "\nthe total error rate is: %f" % (errorCount/float(mTest))

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