KNN最近邻算法原理是什么？如何实现？

把近朱者赤，近墨者黑这一思想运用到机器学习中会产生什么?当然是KNN最邻近算法啦!KNN(全称K-Nearest Neighbor)最邻近分类算法是数据挖掘分类算法中最简单的算法之一，白话解释一下就是：由你的邻居来推断出你的类别。那么KNN算法的原理是什么，如何实现?一起与小编来看下面的内容吧。

一、KNN最邻近算法概念

KNN最邻近算法，是著名的模式识别统计学方法之一，在机器学习分类算法中占有很高的地位。KNN最邻近算法在理论上比较成熟，不仅是最简单的机器学习算法之一，而且也是基于实例的学习方法中最基本的，最好的文本分类算法之一。

KNN最邻近算法基本做法是：给定测试实例，基于某种距离度量找出训练集中与其最靠近的k个实例点，然后基于这k个最近邻的信息来进行预测。

KNN最邻近算法不具有显式的学习过程，事实上，它是懒惰学习(lazy learning)的著名代表，此类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理。

二、KNN最邻近算法三要素

KNN最邻近算法三要素为：距离度量、k值的选择及分类决策规则。根据选择的距离度量(如曼哈顿距离或欧氏距离)，可计算测试实例与训练集中的每个实例点的距离，根据k值选择k个最近邻点，最后根据分类决策规则将测试实例分类。

1.距离度量

特征空间中的两个实例点的距离是两个实例点相似程度的反映。K近邻法的特征空间一般是n维实数向量空间Rn。使用的距离是欧氏距离，但也可以是其他距离，如更一般的Lp距离或Minkowski距离。

这里p≥1.

当p=1时，称为曼哈顿距离(Manhattan distance)，即

当p=2时，称为欧氏距离(Euclidean distance)，即

2.k值的选择

k值的选择会对KNN最邻近算法的结果产生重大影响。在应用中，k值一般取一个比较小的数值，通常采用交叉验证法来选取最优的k值。

3.分类决策规则

KNN最邻近算法中的分类决策规则通常是多数表决，即由输入实例的k个邻近的训练实例中的多数类，决定输入实例的类。

三、KNN最邻近算法优缺点

1.优点

①简单，易于理解，易于实现，无需参数估计，无需训练;

②精度高，对异常值不敏感(个别噪音数据对结果的影响不是很大);

③适合对稀有事件进行分类;

④特别适合于多分类问题(multi-modal,对象具有多个类别标签)，KNN要比SVM表现要好.

2.缺点

①对测试样本分类时的计算量大，空间开销大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本;

②可解释性差，无法给出决策树那样的规则;

③最大的缺点是当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。可以采用权值的方法(和该样本距离小的邻居权值大)来改进;

④消极学习方法。

四、KNN算法实现

主要有以下三个步骤：

1.   算距离：给定待分类样本，计算它与已分类样本中的每个样本的距离;

2. 找邻居：圈定与待分类样本距离最近的K个已分类样本，作为待分类样本的近邻;

3. 做分类：根据这K个近邻中的大部分样本所属的类别来决定待分类样本该属于哪个分类;

python示例

import math
import csv
import operator
import random
import numpy as np
from sklearn.datasets import make_blobs
 
#Python version 3.6.5
 
# 生成样本数据集 samples(样本数量) features(特征向量的维度) centers(类别个数)
def createDataSet(samples=100, features=2, centers=2):
    return make_blobs(n_samples=samples, n_features=features, centers=centers, cluster_std=1.0, random_state=8)
 
# 加载鸢尾花卉数据集 filename(数据集文件存放路径)
def loadIrisDataset(filename):
    with open(filename, 'rt') as csvfile:
        lines = csv.reader(csvfile)
        dataset = list(lines)
        for x in range(len(dataset)):
            for y in range(4):
                dataset[x][y] = float(dataset[x][y])
        return dataset
    
# 拆分数据集 dataset(要拆分的数据集) split(训练集所占比例) trainingSet(训练集) testSet(测试集)
def splitDataSet(dataSet, split, trainingSet=[], testSet=[]):
    for x in range(len(dataSet)):
        if random.random() <= split:
            trainingSet.append(dataSet[x])
        else:
            testSet.append(dataSet[x])
# 计算欧氏距离 
def euclideanDistance(instance1, instance2, length):
    distance = 0
    for x in range(length):
        distance += pow((instance1[x] - instance2[x]), 2)
    return math.sqrt(distance)
 
# 选取距离最近的K个实例
def getNeighbors(trainingSet, testInstance, k):
    distances = []
    length = len(testInstance) - 1
    for x in range(len(trainingSet)):
        dist = euclideanDistance(testInstance, trainingSet[x], length)
        distances.append((trainingSet[x], dist))
    distances.sort(key=operator.itemgetter(1))
    
    neighbors = []
    for x in range(k):
        neighbors.append(distances[x][0])
    return neighbors
 
#  获取距离最近的K个实例中占比例较大的分类
def getResponse(neighbors):
    classVotes = {}
    for x in range(len(neighbors)):
        response = neighbors[x][-1]
        if response in classVotes:
            classVotes[response] += 1
        else:
            classVotes[response] = 1
    sortedVotes = sorted(classVotes.items(), key=operator.itemgetter(1), reverse=True)
    return sortedVotes[0][0]
 
# 计算准确率
def getAccuracy(testSet, predictions):
    correct = 0
    for x in range(len(testSet)):
        if testSet[x][-1] == predictions[x]:
            correct += 1
    return (correct / float(len(testSet))) * 100.0
 
 
def main():
    # 使用自定义创建的数据集进行分类
    # x,y = createDataSet(features=2)
    # dataSet= np.c_[x,y]
    
    # 使用鸢尾花卉数据集进行分类
    dataSet = loadIrisDataset(r'C:\DevTolls\eclipse-pureh2b\python\DeepLearning\KNN\iris_dataset.txt')
        
    print(dataSet)
    trainingSet = []
    testSet = []
    splitDataSet(dataSet, 0.75, trainingSet, testSet)
    print('Train set:' + repr(len(trainingSet)))
    print('Test set:' + repr(len(testSet)))
    predictions = []
    k = 7
    for x in range(len(testSet)):
        neighbors = getNeighbors(trainingSet, testSet[x], k)
        result = getResponse(neighbors)
        predictions.append(result)
        print('>predicted=' + repr(result) + ',actual=' + repr(testSet[x][-1]))
    accuracy = getAccuracy(testSet, predictions)
    print('Accuracy: ' + repr(accuracy) + '%')
main()