题 目 k-最近邻算法实现 学生姓名 学生学号 专 业班级 指 导教师 2015-1-2 实验二 k -最近邻算法实现 一、 实验目的 1 . 加强对 k -最近邻算法的理解； 2 . 锻炼分析问题、解决问题并动手实践的能力。 二、 实验要求 使用一种你熟悉的程序设计语言，如 C++或 Java，给定最近邻数 k 和描述每个元组的属性数 n，实现k-最近邻分类算法，至少在两种不同的数据集上比较算法的性能。 三、 实验环境 Win7 旗舰版 + Visu al Stu dio 2010 语言：C++ 四、 算法描述 KNN(k Nearest Neighbors)算法又叫 k 最临近方法。假设每一个类包含多个样本数据，而且每个数据都有一个唯一的类标记表示这些样本是属于哪一个分类， KNN 就是计算每个样本数据到待分类数据的距离。如果一个样本在特征空间中的 k 个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。KNN 方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。因此，采用这种方法可以较好地避免样本的不平衡问题。另外，由于 KNN 方法主要靠 周 围 有限的邻近的样本，而不是靠 判 别类域 的方法来确 定所属类别的，因此对于类域 的交 叉 或重 叠 较多的待 分 样 本 集 来 说 ， KNN 方 法 较 其 他 方 法 更 为 适 合 。 该 方 法 的 不 足 之 处 是 计 算 量 较大 ， 因 为 对 每 一 个 待 分 类 的 文 本 都 要 计 算 它 到 全 体 已 知 样 本 的 距 离 ， 才 能 求 得 它的K 个 最 近 邻 点 。 目 前 常 用 的 解 决 方 法 是 事 先 对 已 知 样 本 点 进 行 剪 辑 ， 事 先 去除 对 分 类 作 用 不 大 的 样 本 。该 算 法 比 较 适 用 于 样 本 容 量 比 较 大 的 类 域 的 自 动 分 类 ，而 那 些 样 本 容 量 较 小 的 类 域 采 用 这 种 算 法 比 较 容 易 产 生 误 分 。 1、 算 法 思 路 K-最 临 近 分 类 方 法 存 放 所 有 的 训 练 样 本 ，在 接 受 待 分 类 的 新 样 本 之 前 不 需 构造 模 型 ， 并 且 直 到 新 的 （ 未 标 记 的 ） 样 本 ...
