本文正在参与 人工智能创作者扶持方案

1、最近邻算法

最近邻算法是一种根据实例的学习，或者是局部近似和将一切核算推迟到分类之后的慵懒学习，能够用于基本的分类与回归方法。

如下图所示，最近邻算法的工作原理是存在一个样本数据调集，也称作练习样本集，并且样本会集每个数据都存在标签，即咱们知道样本会集每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本会集数据对应的特征进行比较，然后算法提取样本会集特征最类似数据(最近邻)的分类标签。

KNN最近邻算法

KNN最近邻算法

最近邻分类器基本思想能够浅显地描绘为“假如走的像鸭子，叫的像鸭子，看起来还像鸭子，那么它很可能便是一只鸭子”。最近邻算法要求寄存练习记载，核算记载间举例地衡量，并核算最近邻数k的值。对未知记载分类依靠核算域各个练习记载的间隔，找出k个最近邻，运用最近邻的类标号决定方位记载的类标号(例如，多数表决)。

在分类阶段，k是一个用户界说的常数。一个没有类别标签的向量(查询或测验点)将被归类为最接近该点的k个样本点中最频繁运用的一类。

2、间隔衡量方法

2.1 欧氏间隔(Euclidean distance)

d(x,y)=∑i(xi−yi)2d(x,y)=\sqrt{\sum_{i}^{}(x_i-y_i)^2 }

欧几里得衡量（Euclidean Metric）（也称 欧氏间隔）是一个一般选用的间隔界说，指在维空间中两个点之间的实在间隔，或者向量的天然长度（即该点到原点的间隔） 。 在二维和三维空间中的欧氏间隔便是两点之间的实践间隔。

KNN最近邻算法

2.2 曼哈顿间隔(Manhattan distance)

d(x,y)=∑i∣xi−yi∣d(x,y)=\sum_{i}^{}|x_i-y_i|

想象你在城市道路里，要从一个十字路口开车 到另外一个十字路口，驾驭间隔是两点间的直线间隔吗？显然不是，除非你能穿越大楼。实践驾驭间隔便是这个“曼哈顿间隔” 。而这也是曼哈顿间隔名称的来历， 曼哈顿间隔也称为城市街区间隔(City Block distance)。

KNN最近邻算法

2.3 切比雪夫间隔(Chebyshev distance)

d(x,y)=maxi∣xi−yi∣d(x,y)=max_i|x_i-y_i|

二个点之间的间隔界说是其各坐标数值差绝对值的最大值。

国际象棋棋盘上二个方位间的切比雪夫间隔是 指王要从一个位子移至另一个位子需要走的步数。由于王能够往斜前或斜后方向移动一格， 因而能够较有效率的到达意图的格子。下图是棋盘上一切方位距f6方位的切比雪夫间隔。

KNN最近邻算法

2.4 闵可夫斯基间隔(Minkowski distance)

d(x,y)=(∑i∣xi−yi∣p)1pd(x,y)=(\sum_{i}^{}|x_i-y_i|^p )^{\frac{1}{p} }

取1或2时的闵氏间隔是最为常用的:

  • = 2即为欧氏间隔，
  • = 1时则为曼哈顿间隔
  • 当取无量时的极限情况下，能够得到切比雪 夫间隔

2.5 汉明间隔(Hamming distance)

d(x,y)=1N∑i1xi≠yid(x,y)=\frac{1}{N}\sum_{i}^{}1_{x_i\ne y_i}

汉明间隔是运用在数据传输差错操控编码里边的，汉明间隔是一个概念，它表明两个（ 相同长度）字对应位不同的数量，咱们以表明两个字之间的汉明间隔。对两个字符串进行异或运算，并核算结果为1的个数，那么这个数便是汉明间隔。

KNN最近邻算法

2.6 余弦类似度

两个向量有相同的指向时，余弦类似度的值为1；两 个向量夹角为90时，余弦类似度的值为0；两个向 量指向彻底相反的方向时，余弦类似度的值为-1。

假定和是两个维向量，是 [A_1,A_2,…,A_n] ，是 [B_1,B_2,…,B_n]，则和的夹角的余弦等于：

cos⁡()=A⋅B∥A∥∥B∥=∑i=1nAiBi∑i=1n(Ai)2∑i=1n(Bi)2\cos (\theta )=\frac{A\cdot B}{\left \| A \right \|\left \| B \right \| } =\frac{ {\textstyle \sum_{i=1}^{n}A_i\times B_i} }{\sqrt{ {\textstyle \sum_{i=1}^{n}(A_i)^2} }\times \sqrt{ {\textstyle \sum_{i=1}^{n}(B_i)^2} } }

一般情况下，将欧氏间隔作为间隔衡量，但是这只适用于连续变量。在文本分类这种离散变量情况下，能够用汉明举例作为衡量。如下图所示，对于基因表达微阵列数据，KNN也能够与Pearson和Spearman相关系数结合运用。一般情况下，假如运用一些特别的算法来核算衡量的话，k近邻分类精度可显著提高，如运用大间隔最近街坊或者邻里成分分析法。

KNN最近邻算法

3、kNN算法流程

算法流程如下：

  • 1.核算测验目标到练习会集每个目标的间隔
  • 2.按照间隔的远近排序
  • 3.选取与当前测验目标最近的k的练习目标， 作为该测验目标的街坊
  • 4.核算这k个街坊的类别频次
  • 5.k个街坊里频次最高的类别，即为测验目标 的类别

KNN最近邻算法

KNN最近邻算法

4、KNN算法特色

  • 是一种根据实例的学习

    • 需要一个邻近性衡量来确定实例间的类似性或间隔

  • 不需要树立模型，但分类一个测验样例开销很大

    • 需要核算域一切练习实例之间的间隔

  • 根据局部信息进行预测，对噪声十分灵敏

  • 最近邻分类器能够生成任意形状的决议计划鸿沟

    • 决议计划树和根据规矩的分类器一般是直线决议计划鸿沟

  • 需要恰当的邻近性衡量和数据预处理

    • 避免邻近性衡量被某个属性左右

5、运用KNN实现鸢尾花数据集分类

#  knn实现鸢尾花数据集分类
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
import numpy as np
import pandas as pd
​
​
data_url = "Iris.csv"
df = pd.read_csv(data_url)
X = df.iloc[:, 1:5]
y = df.iloc[:, 5]
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=0)
​
# 利用KNeighborsClassifier函数制造knn分类器
# 选取最近的点的个数n_neighbors=3
###########Begin###########
​
clf = KNeighborsClassifier(n_neighbors=6)
​
###########End#############
clf.fit(X_train, y_train)
y_pred = clf.predict(X_test)
acc = np.sum(y_test == y_pred) / X_test.shape[0]
print("Test Acc:%.3f" % acc)