K近邻算法(K-NN)

30
五月
2021

K近邻算法

  1. 算法简介
  2. 算法的三要素
    –K值的选择
    –距离度量
    –决策规则
  3. 鸢尾花分类案例

算法简介

K近邻算法是一种分类回归算法,于1968年由Cover,Hart提出 该算法简单直观,很容易理解,通俗点来讲就是有点随大流,“ 人以类聚物以群分”的味道,该数据周围是什么类,他也就是什么类。
李航大大的统计学习方法中这样定义:给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最相邻的
K个实例,这K个实例中多数属于哪个类,则该新输入的实例也属于该类。

算法的三要素

由上述的定义可知:
最相邻:如何来度量相邻?
K个实例:K值究竟是多少?
多数属于哪个类:怎样去判别属于哪个类?

引出了K近邻算法的三个核心要素:

1:K值的选择

k值一般为奇数,这个很容易理解,比如二分类中,偶数很可能造成K个近邻刚好有k/2的数值分布在一个类中,两个类中各有k/2个元素。造成无法判定新的元素属于哪个类。
K值既不能太大也不能太小:
	K值过小:很容易产生一种过拟合的现象,模型整体变复杂,容易受到异常点的影响
	K值过大:很容易产生欠拟合的现象,模型整体变得简单,单纯的依靠整体数据的分布判定。

2:距离的度量

1:欧式距离:即我们日常所使用的的距离度量方式

a1=(x1,y1), a2=(x2,y2)
d12 = ( x 1 − x 2 ) 2 + ( y 1 − y 2 ) 2 \sqrt{(x_1-x_2)^2+(y_1-y_2)^2} (x1x2)2+(y1y2)2

扩展到n维:

d12 = ( ∑ k = 1 n ( x 1 k − x 2 k ) 2 \sqrt{(\displaystyle\sum_{k=1}^{n} (x_{1k}-x_{2k})^2} (k=1n(x1kx2k)2

2:曼哈顿距离:更加贴近现实的“城市街区距离
d12 = ∣ x 1 − x 2 ∣ + ∣ y 1 − y 2 ∣ |x_1-x_2|+|y_1-y_2| x1x2+y1y2

扩展到n维

d12 = ∑ k = 1 n ∣ x 1 k − x 2 k ∣ ) \displaystyle\sum_{k=1}^n|x_{1k}-x_{2k}|) k=1nx1kx2k)
3:切比雪夫距离("国王距离“---->>>国王”唱跳rap都行,横着走竖着走斜着走都可以“)

在这里插入图片描述
d12 = max ( ∣ x 1 − x 2 ∣ , ∣ y 1 − y 2 ∣ ) (|x_1-x_2|,|y_1-y_2|) (x1x2,y1y2)

扩展到n维

d12 = max ( ∣ x 1 k − x 2 k ∣ ) (|x_{1k}-x_{2k}|) (x1kx2k)

4:闵式距离(带有参数,相当于1-3号距离的整合版)
d12 = ∑ k = 1 n ∣ x 1 k − x 2 k ∣ p p \sqrt[p]{\displaystyle\sum_{k=1}^n|x_{1k}-x_{2k}|^p} pk=1nx1kx2kp

p=1时:曼哈顿距离
p=2时:欧氏距离
p-->∞时:切比雪夫距离

小结:

以上四种距离度量方式在我们日常生活中较为常见,易于理解、直观。
缺点:
	将各个特征的量纲也就是单位不加区分统一度量,在ML数据处理中脱离实际
	为考虑每个特征的分布情况(期望,方差...)

5:标准欧氏距离

考虑其各个特征分布的均值(M)与标准差(S)

标准化度量: X ∗ = ( X − M ) / S X^* = (X-M)/S X=(XM)/S
d12 = ∑ k = 1 n ( x 1 k − x 2 k ) / S ) 2 \sqrt{\displaystyle\sum_{k=1}^n{(x_{1k}-x_{2k})/S})^{2}} k=1n(x1kx2k)/S)2

扩展:
6:汉明距离

信息论、通原中汉明码编码,两个码字码重差
码重:二进制码重1的个数

7:杰卡德距离

杰卡德相似系数(Jaccard similarity coefficient):两个集合A和B的交集元素在A,B的并集中所占的比例,称为两个集合的杰卡德相似系数,用符号J(A,B)表示:(图片引用)

在这里插入图片描述
8:余弦距离
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

主要用来进行向量方向的差异度量,根据cos(θ)可知,该距离范围为[-1,1],根据其向量之间的开角大小来确定相应的余弦距离

9:马氏距离

三哥数学、统计学家提出的,挺厉害的:
见链接(http://www.111)

鸢尾花案例

使用sklearn工具包,利用里面datasets现成小数据集
共4类特征,三种目标值
from sklearn.datasets import load_iris
#分割数据集,采用交叉验证
from sklearn.model_selection import train_test_split,GridSearchCV
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
import matplotlib.pyplot as plt
import pandas as pd
import seaborn as sea
#下面两句是我jupyter无法显示中文,没有中文SimHei字体包,有的话可以不写
from pylab import mpl
mpl.rcParams["font.sans-serif"]=["SimHei"]
#获取数据
iris_data = load_iris()
iris_data.feature_names

#数据预处理
data = pd.DataFrame(iris_data.data,columns=['sepal length ',
 'sepal width ',
 'petal length ',
 'petal width '])
data["target"]=iris_data.target
#数据分割
train_set,test_set,train_target,test_target = train_test_split(data.iloc[:,:4],data["target"],test_size=0.2,random_state=22)

#特征处理
transfer = StandardScaler()
train_set = transfer.fit_transform(train_set)
test_set = transfer.transform(test_set)
#(模型训练)
estimator = KNeighborsClassifier()
param_dict = {"n_neighbors":[i for i in range(1,10) if i%2==1]}
#十折交叉验证
estimator = GridSearchCV(estimator=estimator,param_grid=param_dict,cv=10)
#训练
estimator.fit(train_set,train_target)
#预测
pre = estimator.predict(test_set)

#模型评估
print("模型预测的输出为:\n %s"%pre)
score = estimator.score(test_set,test_target)
print("模型的精度为:%3.1f%%"%(score*100))

模型预测的输出为:
[0 2 1 2 1 1 1 1 1 0 2 1 2 2 0 2 1 1 1 1 0 2 0 1 2 0 2 2 2 2]
模型的精度为:93.3%

sea.lmplot(x="sepal length ",y="petal length ",data=data,hue="target",fit_reg=False)
plt.title("鸢尾花萼片-花瓣长度分布图")

在这里插入图片描述

TAG

网友评论

共有访客发表了评论
请登录后再发布评论,和谐社会,请文明发言,谢谢合作! 立即登录 注册会员