《大数据十大经典算法kNNPPT.》由会员分享，可在线阅读，更多相关《大数据十大经典算法kNNPPT.（15页珍藏版）》请在金锄头文库上搜索。
1、KNN:K最近邻分类算法 K-Nearest Neighbor Classification KNN算法怎么来的？ KNN算法是怎么来的 电影名称打斗次数接吻次数电影类型 California Man 3104Romance Hes Not Really into Dudes 2100Romance Beautiful Woman 181Romance Kevin Longblade 10110Action Robo Slayer 3000 995Action Amped II 982Action 未知1890Unknown 猜猜看：最后一行未知电影属于什么类型的电影。 KNN算法是怎么来的
2、点X坐标Y坐标点类型 A点 3104Romance B点 2100Romance C点 181Romance D点 10110Action E点 995Action F点 982Action G点1890Unknown 猜猜看：最后一行未知点属于什么类型的点。 KNN算法是怎么来的 想一想：下面图片中只有三种豆，有三个豆是 未知的种类，如何判定他们的种类？ 1968年，Cover和Hart提出了最初的近邻法。 最近邻算法 提供一种思路，即：未知的豆离 哪种豆最近就认为未知豆和该豆是同一 种类。由此，我们引出最近邻算法的定 义：为了判定未知样本的类别，以全部 训练样本作为代表点，计算未知样本与
3、所有训练样本的距离，并以最近邻者的 类别作为决策未知样本类别的唯一依据 。但是，最近邻算法明显是存在缺陷的 ，我们来看一个例子。 KNN算法是怎么来的 问题：有一个未知形状X(图中绿色的圆 点)，如何判断X是什么形状? K-最近邻算法 显然，通过上面的例子我们可以明显发现 最近邻算法的缺陷对噪声数据过于敏感，为 了解决这个问题，我们可以可以把位置样本周边 的多个最近样本计算在内，扩大参与决策的样本 量，以避免个别数据直接决定决策结果。由此， 我们引进K-最近邻算法。 KNN算法是用来干什么的 K-最近邻算法是最近邻算法的一个延伸。基本思路 是：选择未知样本一定范围内确定个数的K个样本，该K个
4、样本大多数属于某一类型，则未知样本判定为该类型。 下面借助图形解释一下。 KNN算法的实现步骤 算法步骤： step.1-初始化距离为最大值 step.2-计算未知样本和每个训练样本的距离dist step.3-得到目前K个最临近样本中的最大距离maxdist step.4-如果dist小于maxdist，则将该训练样本作为K-最近 邻样本 step.5-重复步骤2、3、4，直到未知样本和所有训练样本的 距离都算完 step.6-统计K个最近邻样本中每个类别出现的次数 step.7-选择出现频率最大的类别作为未知样本的类别 KNN算法的缺陷 观察下面的例子，我们看到，对于位置样本 X，通过KN
5、N算法，我们显然可以得到X应属于红点 ，但对于位置样本Y，通过KNN算法我们似乎得到了 Y应属于蓝点的结论，而这个结论直观来看并没有说 服力。 KNN算法的具体实现 由上面的例子可见：该算法在分类时有个重要的 不足是，当样本不平衡时，即：一个类的样本容量很大 ，而其他类样本数量很小时，很有可能导致当输入一个 未知样本时，该样本的K个邻居中大数量类的样本占多数 。 但是这类样本并不接近目标样本，而数量小的这类样 本很靠近目标样本。这个时候，我们有理由认为该位置 样本属于数量小的样本所属的一类，但是，KNN却不关 心这个问题，它只关心哪类样本的数量最多，而不去把 距离远近考虑在内，因此，我们可以采
6、用权值的方法来 改进。和该样本距离小的邻居权值大，和该样本距离大 的邻居权值则相对较小，由此，将距离远近的因素也考 虑在内，避免因一个样本过大导致误判的情况。 KNN算法的缺陷 从算法实现的过程大家可以发现，该算法存两个严重 的问题，第一个是需要存储全部的训练样本，第二个是需要 进行繁重的距离计算量。对此，提出以下应对策略。 KNN算法的改进：分组快速搜索近邻法 其基本思想是：将样本集按近邻关系分解成组，给 出每组质心的位置，以质心作为代表点，和未知样本计算距 离，选出距离最近的一个或若干个组，再在组的范围内应用 一般的knn算法。由于并不是将未知样本与所有样本计算距 离，故该改进算法可以减少
7、计算量，但并不能减少存储量。 KNN算法的改进：压缩近邻算法 利用现在的样本集，采取一定的算法产生一个新的样本 集，该样本集拥有比原样本集少的多的样本数量，但仍然保持 有对未知样本进行分类的能力。 基本思路：定义两个存储器，一个用来存放生成的样本 集，称为output样本集；另一个用来存放原来的样本集，称为 original样本集。 1.初始化：output样本集为空集，原样本集存入 original样本集，从original样本集中任意选择一个样本移动到 output样本集中； 2.在original样本集中选择第i个样本，并使用output 样本集中的样本对其进行最近邻算法分类，若分类错误，则将 该样本移动到output样本集中，若分类正确，不做任何处理； 3.重复2步骤，直至遍历完original样本集中的所有样 本，output样本集即为压缩后的样本集。 通过这种方式也能减少算法的计算量，但仍然无法减少 存储量。
