python机器学习——KNN(K近邻算法)
2024-10-21 23:08:58
背景与原理:
KNN算法其实是逻辑最简单的分类算法——我们认为一个数据的类型是由与其最接近的数据决定的,而“接近”实际上就是我们度量两个数据点之间的距离,如果我们把一组数据看做一个向量$(x_{1},...,x_{n},y)$,其中$y$代表这个数据的类别,那么两组数据$X_{i},X_{j}$间的距离如果使用欧式距离表示为$L_{ij}=\sqrt{\sum_{k=1}^{n}(x_{ik}-x_{jk})^{2}}$
那么对于空间中已经分好类的若干数据,如果我们想预测输入的某组数据属于什么类,那么我们去计算空间中分好类的数据点离它的距离,然后选择距离最近的认为和想预测的数据是最接近的,直接选择距离最近的数据点的类别即可。
当然,只选择最近的是由很大问题的,所以K近邻算法(K-Nearest Neighbours)就是将上述“最近”改成“K个最近的”,然后找出这K个数据点中概率最大的类别作为我们预测的类别。
代码实现:
import numpy as np
import math
from scipy import stats
import matplotlib.pyplot as plt
from sklearn.linear_model import LinearRegression def dis(alpha,beta):
s=0
for i in range(0,len(alpha)-1):
s+=(alpha[i]-beta[i])**2 return math.sqrt(s) def KNN_Test(input,dataset,siz,K):
q=[]
p=[]
for i in range(0,siz):
d=dis(input,dataset[i])
maxp=0
for j in range(0,len(q)):
if q[j]>q[0]:
maxp=j if len(q)<K:
q.append(d)
p.append(i)
elif q[maxp]>d:
q[maxp]=d
p[maxp]=i
cnt=0
for i in range(0,K):
if dataset[p[i]][2]==1:
cnt+=1
if cnt<K/2:
return 0
else:
return 1 x=np.arange(0.,10.,0.02)
y=5-2*x/3+np.random.randn(500)
now=0
dataset=[]
for i in range(0,500):
typ = 0
if 2*x[i]+3*y[i] <= 15:
if abs(np.random.randn(1)[0])<2:
typ = 1
else:
typ = 0
else:
if abs(np.random.randn(1)[0]) < 2:
typ = 0
else:
typ = 1 dataset.append([x[i],y[i],typ]) c_cnt=0
for i in range(0,500):
predict_typ=KNN_Test(dataset[i],dataset,500,10)
if predict_typ==dataset[i][2]:
c_cnt+=1 print(c_cnt/500)
这段代码生成的分类数据和逻辑回归的相同,我们这次使用KNN算法进行分类,准确率相对可观
小结与改进:
KNN算法存在相当的不足之处,在改进中我们可以选择加入权值——虽然我们考虑最近的K个“邻居”,但是我们认为一组数据肯定与离它最近的邻居更接近,因此在计算概率时我们对于距离较近的数据点给出一个较高的权值,距离较远的邻居给出一个较低的权值,这样能更好地体现“近邻”这个观点。
同样,究竟选择几个“邻居”也是值得考虑的,这一点可以通过权衡样本数量来进行调整。
KNN算法的另一个缺点在于训练样本数量很大、维度很多的时候计算开销很大,因此我们可以在预处理阶段使用降维算法对维度进行简化以提高效率
最新文章
- asp.net mvc项目自定义区域
- Jquery ajax请求
- NOIP2009pj道路游戏[环形DP 转移优化 二维信息]
- [知识点]Cantor展开
- Myeclipse 找不到Convert to maven project选项
- 个人电脑配置FTP服务器,四张图搞定。项目需要,并自己写了个客户端实现下载和上传的功能!
- 加密解密(9)Diffie-Hellman密钥交换协议
- 点分治练习:不虚就是要AK
- MLC固态硬盘,与入量是3000次P/E
- Linux下 fcntl 函数用法说明
- JAVA中SSH面试问题
- HDU 3068 最长回文 【最长回文子串】
- 3553: [Shoi2014]三叉神经树(树链剖分)
- Netty(二)——TCP粘包/拆包
- 页面输入的数据格式转换类:BaseAction(经常使用于Struts框架中)
- PE文件简介
- appache 在windows 中无法启动的测试
- 微信小程序 遇到的问题(新)
- Spring 源码分析 spring-core 篇
- java String 类型总结