pythonK近邻算法的kd树实现资源-CSDN下载

5星 · 超过95%的资源 91 浏览量 2021-01-20 04:33:40 上传评论收藏 84KB PDF 举报

资源推荐

资源详情

资源评论

python K近邻算法的近邻算法的kd树实现树实现

k近邻算法的介绍近邻算法的介绍

k近邻算法是一种基本的分类和回归方法，这里只实现分类的k近邻算法。

k近邻算法的输入为实例的特征向量，对应特征空间的点；输出为实例的类别，可以取多类。

k近邻算法不具有显式的学习过程，实际上k近邻算法是利用训练数据集对特征向量空间进行划分。将划分的空间模型作为其分

类模型。

k近邻算法的三要素近邻算法的三要素

k值的选择：即分类决策时选择k个最近邻实例；

距离度量：即预测实例点和训练实例点间的距离，一般使用L2距离即欧氏距离；

分类决策规则。

下面对三要素进行一下说明：

1.欧氏距离即欧几里得距离，高中数学中用来计算点和点间的距离公式；

2.k值选择：k值选择会对k近邻法结果产生重大影响，如果选择较小的k值，相当于在较小的邻域中训练实例进行预测，这样有

点是“近似误差”会减小，即只与输入实例较近（相似）的训练实例才会起作用，缺点是“估计误差”会增大，即对近邻的实例点

很敏感。而k值过大则相反。实际中取较小的k值通过交叉验证的方法取最优k值。

3.k近邻法的分类决策规则往往采用多数表决的方式，这等价于“经验风险最小化”。

k近邻算法的实现：近邻算法的实现：kd树树

实现k近邻法是要考虑的主要问题是如何退训练数据进行快速的k近邻搜索，当训练实例数很大是显然通过一般的线性搜索方式

效率低下，因此为了提高搜索效率，需要构造特殊的数据结构对训练实例进行存储。kd树就是一种不错的数据结构，可以大

大提高搜索效率。

本质商kd树是对k维空间的一个划分，构造kd树相当与使用垂直于坐标轴的超平面将k维空间进行切分，构造一系列的超矩

形，kd树的每一个结点对应一个这样的超矩形。

kd树本质上是一棵二叉树，当通过一定规则构造是他是平衡的。

下面是过早kd树的算法：

开始：构造根结点，根节点对应包含所有训练实例的k为空间。选择第1维为坐标轴，以所有训练实例的第一维数据的中位数

为切分点，将根结点对应的超矩形切分为两个子区域。由根结点生成深度为1的左右子结点，左结点对应第一维坐标小于切分

点的子区域，右子结点对应第一位坐标大于切分点的子区域。

重复：对深度为j的结点选择第l维为切分坐标轴，l=j(modk)+1,以该区域中所有训练实例的第l维的中位数为切分点，重复第一

步。

直到两个子区域没有实例存在时停止。形成kd树。

以下是以下是kd树的树的python实现实现

准备工作

#读取数据准备

def file2matrix(filename):

fr = open(filename)

returnMat = [] #样本数据矩阵

for line in fr.readlines():

line = line.strip().split(' ')

returnMat.append([float(line[0]),float(line[1]),float(line[2]),float(line[3])])

return returnMat

#将数据归一化，避免数据各维度间的差异过大

def autoNorm(data):

#将data数据和类别拆分

data,label = np.split(data,[3],axis=1)

minVals = data.min(0) #data各列的最大值

maxVals = data.max(0) #data各列的最小值

ranges = maxVals - minVals

normDataSet = np.zeros(np.shape(data))

m = data.shape[0] #tile函数将变量内容复制成输入矩阵同样大小的矩阵

normDataSet = data - np.tile(minVals,(m,1))

normDataSet = normDataSet/np.tile(ranges,(m,1))

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余3页未读，立即下载

内容反馈

df595420469

2023-06-16

这篇文章细节考虑得非常周到，非常适合拿来作为自己的学习资料。
虚伪的小白

2023-06-16

我学过很多K近邻算法的实现方法，但这个kd树的实现方法是最简单易懂的。
恽磊

2023-06-16

这个文件让我觉得python实现K近邻算法的过程很简单易懂。
阿玫小酱当当囧

2023-06-16

这个文件讲解了K近邻算法的实现方法，内容非常详细。
西西里的小裁缝

2023-06-16

如果你正在学习K近邻算法，这个文件一定能对你的学习产生帮助！

前往

页

weixin_38638309

粉丝: 3

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip