编程大作业实验报告-sa

1、编程实验：学号：SA15010025邮箱：huxc一、K 近邻算法实现实验运行环境：C+代码，算法思路分析：vs2013,windows7，64 位K 近邻算法原理是给定一个训练集，对于新的输入实例，在训练集中找到与该实例最近的k 个实例，这 k 个实例中的多数属于某个类，就把该输入实例分为这个类。因为要找到最近的 k 个实例，所以计算输入实例与训练集中实例之间的距离是关键！ 为了提高k 近邻的搜索效率，常常考虑使用特殊的结构训练数据，以减少计算距离的次数，本算法采用 kd 树法。数据结构，kd 树是二叉树。为了构造平衡二叉树，采用中位值法。本次实验采用的是欧氏距离来计算距离；A.创建 kd

2、树的算法流程（kd 树的创建采用的是递归算法）：（1）申请树节点kd_tree_node *root，判断递归是否结束，结束条件是输入数据的个数为 1，若递归结束则返回root;否则继续执行(2);（2）起始维度为split_dim=1，升序排列第split_dim 维的数据，分成两部分left 和right； （3）对树，递归调用 create_kd_tree（），维度改为split_dim%K+1;（4）对于右，递归调用 create_kd_tree(), 维度改为split_dim%K+1;（5）设置相应的成员变量,返回节点指针；kd 树是一种对 k中的实例点进行以便对其进行快速检索的树

3、形B. k-近邻搜索算法流程：公共操作P:在每个结点时，若数组（或者其他数据结构）容量k，则将该结点加入数组，若数组容量以达到k，则比较当前节点是否比数组末尾元素与x的距离更近，若更近则以当前节点代替堆顶结点，并调整数组，更新最大距离。（1）从根节点出发，递归地向下kd树，若目标x当前维的坐标小于切分点的坐标，则移动到结点，否则移动到右子结点，知道结点为叶节点为止。执行公共操作P。（2）递归的向上回退，在每个节点进行以下操作：（a）执行公共操作P。（b）检查该子结点的兄弟结点区域是否有比堆顶元素更近的点或堆容量未满。具体的，检查另一子结点对应的区域是否与以目标点为求心，以目标点与堆顶元素距离为

4、半径的球体相交。如果相交或容量未满，以另一子结点为根节点执行(1)。（3）当回退到根节点时，搜索结束，堆中实例即为所求实例。3. 结果分析iris 数据集由 3 种不同类型的鸢尾花的 50 个样本数据。其中的一个种类与另外两个种类是线性可分离的，后两个种类是非线性可分离的。由于k 近邻的算法原理，对线性可分和非线性可分的情况都是可以处理的。因此，k 从小变大的时候，准确率会有逐渐变小的趋势，运行结果也反应了这一趋势。经测试显示：kleft=p;同理对中和右有：root-middle=create_DC_tree(middle_index,dim),root-right=create_DC_tree(right_index,dim);如果，相应的 left_index 大小为 0，那么指针就设置为 NULL，返回root搜索决策树的算法流程：search_DC_tree()就是正常的树搜索，根据节点的split_val 分割点的值，判断测试实例转到哪个，直到到达叶节点。3.结果分析根据程序调试过程，画出如下的决