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