knn算法代码

50年前的kNN算法，只用14行代码在文本分类上超越风头正盛的Transformer，包括BERT——

这个来自ACL Finding的成果，一发布就火爆学术圈，让人重新思考还有多少旧方法可以用于今天的机器学习任务。

有人盛赞它的创意性超过95%的同会论文，但是却没有获奖实在令人想不通。

短短14行代码，完全打开了大家的思路。

然而，才不到几天的时间，就有人发现：

这一切好像都是个误会。

BERT没有被打败，代码有bug，结果有问题！

这是，反转了？？

重测后性能从SOTA变最差

先再来简单回顾一下这篇论文的主要背景和思想：

它讲的是如今由于精度高被经常用于文本分类的深度神经网络模型（DNN），因为其计算密集型的特性，需要数百万个参数和大量标记数据才能保证效果，这就导致它用起来或者做优化，以及转移到分布外数据等情况时都很费钱。

在此，来自滑铁卢大学和AFAIK机构的研究人员，就“突发奇想”提出了一种不需要参数的替代方案：

将简单的压缩算法比如gzip和k近邻分类算法进行结合来做这件事（用到了归一化压缩距离NCD）。

结果，这种简单的方案在没有任何训练参数的情况下，效果居然很不错——

在7个分布内数据集上有6个结果与各类DNN相媲美，在分布外数据集上的结果则接连5把胜出，把BERT都给打败了。

而且它在少样本情况下也好使，相反此时的DNN却因为标记数据太少根本无法进行有效训练。

来自于美国的机器学习研究员Ken Schutte（博士毕业于MIT电气工程与计算机科学），在看到这篇论文后非常感兴趣，并冒出了一些新点子。

于是他并决定复现一下。

结果，就出现了蹊跷：

也就是说，它的效果可能并没有那么强。

具体而言，Ken指出，在论文的表5中，结果显示该方法在OOD数据集上打败了所有其他基于神经网络的方法：

而他对前四个数据集都重新进行了一遍测试（使用kNN(k=2) 精度），结果有很大出入，根本无法打败那些基准模型，甚至从性能最佳变为性能最差。（最后一个数据集因为太大Ken还没尝试）

下面是详细解释。

在论文中，作者在使用kNN分类器时，都是取值k=2。

（kNN是一种有监督算法，通过“有标签”的样本最终确定未知样本的类别，该算法主要参数就是k值的选择，k值越大，分类效果越稳定，但计算量也越大）

Ken认为，这个选择有点没必要，不会给分类器增加太多信息，取1就行。

而当取2时，在训练集中搜索出的两个近邻点类别标签不一致的情况下，比如一个是正类，一个是负类，那么就产生了平局情况，我们需要进一步确定唯一正确的那个点。

在这个确定的过程中，论文中的源码（位于experiments.py文件中的calc_acc方法中）出现了问题：

简单来说就是，这段代码的做法其实是只要2个近邻点标签中有一个与中心点真实类别一致（简而言之，有一个对就算对），就判断为正确，这也就相当于Top-2精度。

但标准的KNN算法，会使用其他打破平局的策略，比如距离近的类别优先，或随机选取来确定，也就是采用标准的kNN(k=2) 精度来评估结果，“更严格”。

这就导致在k=2时原方法计算的准确率其实是高于标准算法的，也就是最终效果并没有现在我们看上去的那么牛。

这不，Ken重新写了两种打破平局的策略（一个是随机选择，一个是递减k），重新计算了各数据集下模型的准确率，结果均出现了不同程度的下滑：

当然，我们可以发现，如果还是按照top-2算，Ken复现的结果基本和原论文没有差别，侧面证明Ken的发现是有效的。

网友：虽然但是，不影响方法本身的创新性

这个消息出来之后，网友是怎么看的呢？

有意思的是，大家都觉得Ken的分析很有道理，但这不影响该方法本身的创新性。

GoogleAI的研究员Lucas Beye也表达了类似的意思。

值得一提的是，在Ken之后，斯坦福博士Yann Dubois又发现该论文的问题还不止如此——

其训练测试集也重叠了。

比如DengueFilipino的训练集和测试集完全一样，而KirundiNews的重复率也高达90%。

当然，一如既往，由于该方法实在是太特别了，尽管网友评论中也充斥着“wtf”这样的声音，但大部分人还是坚决捍卫它的重要贡献，认为问题不大，可能只是审查不到位等等。

这不，“你可以扼杀一篇论文，但你无法扼杀一个想法”的评论都出来了。

大家怎么看？这两个bug影响你对这篇论文的看法吗？

Ken原博：

— 完 —

量子位 QbitAI · 头条号签约

禄俩尤3397怎样在spark里跑java版的knn算法 -
傅晏馨13737627416 ______ 将KNN算法调用Spark的api进行重写.然后就可以在sparkshell里运行了

禄俩尤3397文本分类的方法
傅晏馨13737627416 ______ 文本分类问题与其它分类问题没有本质上的区别,其方法可以归结为根据待分类数据的某些特征来进行匹配,当然完全的匹配是不太可能的,因此必须(根据某种评价标准)选择最优的匹配结果,从而完成分类. 后来人们意识到,究竟依据什么...

禄俩尤3397python 问题 实现KNN算法 -
傅晏馨13737627416 ______ iteritems直接改成items就可以了,不需要其他操作

禄俩尤3397knn算法怎么用于regression -
傅晏馨13737627416 ______ K最近邻(k-Nearest Neighbor,KNN)分类算法,是一个理论上比较成熟的方法,也是最简单的机器学习算法之一.该方法的思路是:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别.

禄俩尤3397请教K - NN法则算法的原理,全天在线,如有提示,立即给分 -
傅晏馨13737627416 ______ KNN(K 最近邻居)算法 该算法的基本思路是:在给定新文本后,考虑在训练文本集中与该新文本距离最近(最相似)的 K 篇文本,根据这 K 篇文本所属的类别判定新文本所属的类别,具体的算法步骤如下:STEP ONE:根据特征项集合重新描...

禄俩尤3397为什么在做KNN分类器时不用测试集也能得出分类结果 -
傅晏馨13737627416 ______ knn算法(k-Nearest Neighbor algorithm).是一种经典的分类算法.注意,不是聚类算法.所以这种分类算法必然包括了训练过程.然而和一般性的分类算法不同,knn算法是一种 懒惰算法 .它并非像其他的分类算法先通过训练建立分类模型.,而是一种被动的分类过程.它是边测试边训练建立分类模型.算法的一般描述过程如下:1.首先计算每个测试样本点到其他每个点的距离.这个距离可以是欧氏距离,余弦距离等.

禄俩尤3397k近邻算法实际上是一种分类算法,其通过找出样本最近的k个... - 上学吧
傅晏馨13737627416 ______ 用 function 定义函数时,参数表中的参数称为形参,必须是变量,不能用常数.你希望输入的数据(例如3)称为实参,是要在调用时输入的,例如在命令窗口中输入 k_means(data,3,3) 其中data是要处理的数据.

禄俩尤3397用matlab求ln2的值,运用以下三种算法,求和,程序过程. -
傅晏馨13737627416 ______ >> N = 100; >> k = 1:N; % 算法1 >> SN1 = sum((-1).^(k-1)./k) SN1 = 0.6882 % 算法2 >> SN1_1=SN1-(-1).^(N-1)./N; >> SN1_2=SN1_1-(-1).^(N-2)./(N-1); >> SN2 = SN1 - (SN1-SN1_1)^2/(SN1-2*SN1_1+SN1_2) SN2 = 0.6931 % 算法3 >> SN3 = sum(1./(k.*2.^k)) SN3 = 0.6931