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