KNN最近邻算法分析及实现(Python实现)

Author： Nirvana Of Phoenixl

Proverbs for you：There is no doubt that good things will always come, and when it comes late, it can be a surprise.
（送给你的）

1 KNN算法简介

  最近邻(K-Nearest Neighbor，KNN)算法，是著名的模式识别统计学方法，在机器学习分类算法中占有相当大的地位。它是一个理论上比较成熟的方法。既是最简单的机器学习算法之一，也是基于实例的学习方法中最基本的，又是最好的文本分类算法之一。

  K近邻法（K-Nearest Neighbor, KNN）是一种基本分类与回归方法，其基本做法是：给定测试实例，基于某种距离度量找出训练集中与其最靠近的K个实例点，然后基于这K个最近邻的信息来进行预测。

  通常，在分类任务中可使用“投票法”，即选择这K个实例中出现最多的标记类别作为预测结果；在回归任务中可使用“平均法”，即将这K个实例的实值输出标记的平均值作为预测结果；还可基于距离远近进行加权平均或加权投票，距离越近的实例权重越大。

2 KNN基本原理

  KNN最邻近分类算法的实现原理：为了判断未知样本的类别，以所有已知类别的样本作为参照，计算未知样本与所有已知样本的距离，从中选取与未知样本距离最近的K个已知样本，根据少数服从多数的投票法则（majority-voting），将未知样本与K个最邻近样本中所属类别占比较多的归为一类。

K近邻算法的主要任务是通过判断距离来选取未知样本，它包含的又一下核心公式： 

其中xi表示样本集
通过未知样本和已知样本的距离来判断取舍，主要是根据闵可夫斯基距离（LP）距离，其距离可以表示为：

其中xi，xj表示两个样本，n表示样本数，l表示维度，p表示参数其值取不同则表示不同距离。

根据LP距离可以推到得到不同的衡量距离，具体如下：
当p=1时，LP距离为曼哈顿距离，则可表示为：

当p=2时，LP距离为欧式距离，则可以表示为：

当P= 时，LP距离为切比雪夫距离，它表示两个点之间距离最大的坐标系之间的距离，可以表示为：

3 简单实现KNN分析

  通过基本原理设计一个简单的数据分类，通过随机取点分为两份作为样本点，再随机几个点作为待测点，并且通过KNN判断该点可能属于的类。

                      随机点分类可视化图

代码附录(Python)：

from matplotlib.pyplot import *
import numpy as np
k = 5                                         # 简单例子，取k值为5即可
n=100                                        # 随机点分为两种颜色点的个数
def creatdot(rangex, rangey, dotnum, classtyap):        # 产生随机点分为x,y
x = np.random.normal(rangex, rangey, dotnum)
 y = np.random.normal(rangex, rangey, dotnum)     # 调用正态分布
    scatter(x, y, color=classtyap)                 # 产生点集
    return x, y

def discal(X, Y, markx, marky, classtyap):             # KNN计算距离
    for i in range(len(X)):
        x = X[i]
        y = Y[i]
        dis = ((x - markx)**2 + (y - marky)**2)**0.5
        dismp.append([dis, classtyap])
    return dismp

def creatmark():                              # 产生随机点作为被测数据
    x, y = creatdot(0, 2, 1, "green")
    return x, y

markx, marky = creatmark()

dismp = []
X, Y = creatdot(0, 1, n, "blue")
dismp.append(discal(X, Y, markx, marky, "blue"))
X, Y = creatdot(2, 1, n, "red")
dismp.append(discal(X, Y, markx, marky, "red"))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

呆，站住别跑，留个赞，给个关注嘛都看到这了