大数据十大经典算法kNN讲解.ppt

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