KNN算法的python实现代码

KNN算法的python实现代码

时间:2015-07-08 10:50来源:网络整理 作者:KKWL 点击:
助理编辑 KNN算法的python实现代码 2015/7/7 16:45:21 [中国学网 ] | 责编:崔宁 返回首页 分享到 KNN(k-Nearest Neighbor algorithm )分类算法是最简单的机器学习算法之一,采用向量空间模型来分类

助理编辑 KNN算法的python实现代码

  [  中国学网   ]   |  责编:崔宁

返回首页 分享到

KNN(k-Nearest Neighbor algorithm )分类算法是最简单的机器学习算法之一,采用向量空间模型来分类,概念为相同类别的案例,彼此的相似度高,而可以借由计算与已知类别案例之相似度,来评估未知类别案例可能的分类。

KNN根据某些样本实例与其他实例之间的相似性进行分类。特征相似的实例互相靠近,特征不相似的实例互相远离。因而,可以将两个实例间的距离作为他们的“不相似度”的一种度量标准。KNN模型可以支持两种方法计算实例间距离,他们分别是:Euclidean Distance( 欧氏距离法 ) 和 City-block Distance(城区距离法)。

K最近邻(k-Nearest Neighbor,KNN)分类算法,是一个理论上比较成熟的方法,也是最简单的机器学习算法之一。该方法的思路是:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。KNN算法中,所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法虽然从原理上也依赖于极限定理,但在类别决策时,只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,KNN方法较其他方法更为适合。KNN算法不仅可以用于分类,还可以用于回归。通过找出一个样本的k个最近邻居,将这些邻居的属性的平均值赋给该样本,就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight),如权值与距离成正比。该算法在分类时有个主要的不足是,当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K个邻居中大容量类的样本占多数。 该算法只计算“最近的”邻居样本,某一类的样本数量很大,那么或者这类样本并不接近目标样本,或者这类样本很靠近目标样本。无论怎样,数量并不能影响运行结果。可以采用权值的方法(和该样本距离小的邻居权值大)来改进。该方法的另一个不足之处是计算量较大,因为对每一个待分类的文本都要计算它到全体已知样本的距离,才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑,事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类,而那些样本容量较小的类域采用这种算法比较容易产生误分。

步骤

依公式计算 Item 与 D1、D2 … …、Dj 之相似度。得到Sim(Item, D1)、Sim(Item, D2)… …、Sim(Item, Dj)。

将Sim(Item, D1)、Sim(Item, D2)… …、Sim(Item, Dj)排序,若是超过相似度门槛t则放入邻居案例集合NN。

自邻居案例集合NN中取出前k名,依多数决,得到Item可能类别。

然而k最近邻居法因为计算量相当的大,所以相当的耗时,Ko与Seo提出一算法TCFP(text categorization using feature projection),尝试利用特征投影法(en:feature projection)来降低与

相关信息

  • 网站地图
  • 分享到:

    网友评论

    返回频道今日最新

  • 猜你喜欢
  • 今日最新
  • 本文相关搜索

    精彩推荐 查看更多...

    热门搜索排行榜

    ------分隔线----------------------------