在模式识别领域，K-NearestNeighbor(KNN)是一种非参数统计方法.K-NearestNeighbors算法非常简单有效，其模型表示就是整个训练数据集。原则上，通过在整个训练集中搜索与该数据点最相似的K个实例（最近邻）并将这些K个实例的输出变量求和来获得对新数据点的预测。KNN可能需要大量内存或空间来存储所有数据，并且使用距离或接近度度量的方法可能会在非常高的维度（具有许多输入变量）中崩溃，这可能会影响算法在您的问题上的性能性能是负面的做作的。这就是所谓的维数灾难。近似最近邻算法（ApproximateNearestNeighbor,ANN）是一种以牺牲精度换取时间和空间来从大量样本中获取最近邻的方法，以其存储空间小、占用空间小等优点而受到人们的关注。搜索效率高。广泛关注。最近，一家科技公司的数据科学总监MarieStephenLeo写了一篇KNN和ANN的对比，结果表明，在搜索最近邻的相似度为99.3%时，ANN在sklearn上比KNN快380倍。作者表示，几乎每门数据科学课程都会教授KNN算法，但它正在走向“淘汰”！KNN简介在机器学习社区中，找到“K”个与给定项目相似的项目称为相似性搜索或最近邻(NN)搜索。最广为人知的NN搜索算法是KNN算法。在KNN中，给定一个对象集合，例如移动电子商务目录，对于任何新的搜索查询，我们可以从整个目录中找到少量(K)个最近的邻居。例如，在下面的示例中，如果设置K=3，则每个“iPhone”的3个最近邻居都是另一个“iPhone”。同样，每个“Samsung”的3个最近邻居也是“Samsung”。KNN的问题尽管KNN擅长查找相似项，但它使用详细的成对距离计算来查找邻居。如果您的数据包含1000个项目，要找到新产品的K=3个最近邻居，算法需要对数据库中的所有其他产品执行1000个新产品距离计算。这还不算太糟糕，但想象一下真实世界的客户对客户(C2C)市场，其中数据库包含数百万种产品，并且每天可能上传数千种新产品。将每个新产品与所有数百万个产品进行比较既不经济又耗时，这意味着该方法根本无法扩展。解决方案将最近邻算法扩展到大规模数据的方法是完全避免暴力距离计算并使用ANN算法。ApproximateNearestDistanceAlgorithm(ANN)严格来说，ANN是一种在NN搜索过程中允许有少量误差的算法。但在实际的C2C市场中，真实邻居的数量要多于搜索到的K近邻的数量。与bruteforceKNN相比，人工神经网络可以在短时间内达到更高的精度。有几种ANN算法：Spotify的ANNOYGoogle的ScaNNFaissFacebook的HNSWHierarchicalNavigableSmallWorld(HNSW)在HNSW中，作者描述了一种使用多层图的ANN算法。在元素插入阶段，通过指数衰减的概率分布随机选择每个元素的最大层，逐步构建HNSW图。这确保layer=0具有许多支持精细搜索的元素，而layer=2具有e^-2个支持粗搜索的元素。最近邻搜索从顶层开始粗略搜索，然后向下进行到底层。使用贪心图路径算法遍历图并找到所需数量的邻居。HNSW图结构。最近邻搜索从顶部开始（粗略搜索）并在底部结束（精细搜索）。HNSWPython包整个HNSW算法代码已在C++中通过Python绑定实现，用户可以通过键入以下命令将其安装在他们的机器上：pipinstallhnswlib。安装导入包后，需要一些步骤来创建HNSW图，这些步骤已经封装在如下函数中：=False):#ConveniencefunctiontocreateHNSWgraph#features:listoflistscontainingtheembeddings#ef,M:parameterstotunetheHNSWalgorithm<代码>num_elements=len(features)labels_index=np.arange(num_elements)EMBEDDING_SIZE=len(features[0])#Declaringindex#possiblespaceoptionsarel2,cosineorip<代码>p=hnswlib.Index(space='l2',dim=EMBEDDING_SIZE)#Initingindex-themaximumnumberofelementsshouldbeknownp.init_index(max_elements=num_elements,ef_construction=ef,M=M)#Elementinsertion复制代码int_labels=p.add_items(features,labels_index)#Controllingtherecallbysettingef#efshouldalwaysbe>kp.set_ef(ef)#Ifyouwanttosavethegraphtoafileifsave_index_file:<代码>p.save_index(save_index_file)returnp创建HNSW索引后，查询“K”个最近邻只需要下面这行代码：ann_neighbor_indices,ann_distances=p.knn_query(features,k)KNN和ANN基准测试计划首先下载500K+行的大型数据集，然后使用预训练的fasttext句子向量将文本列转换为300d嵌入向量。KNN和HNSWANN模型将在不同长度的输入数据上进行训练[1000.10000,100000,len(data)]来衡量数据大小对速度的影响。最后，将查询两个模型中K=10和K=100处的最近邻居，以衡量“K”对速度的影响。首先导入必要的包和模型。这将需要一些时间，因为需要从Web下载fasttext模型。#Imports#Forinputdata预处理importjsonimportgzipimportpandasaspdimportnumpyasnpimportmatplotlib.pyplotaspltimportfasttext.utilfasttext.util.download_model('en',if_exists='ignore')#Englishpre-trainedmodel<代码>ft=fasttext.load_model('cc.en.300.bin')#ForKNNvsANNbenchmarkingfromdatetimeimportdatetimefromtqdmimporttqdmfromsklearn.neighborsimportNearestNeighborsimporthnswlib数据使用Amazon[AmazonProductsDataset]，其中包含“手机和配件”类别中的527,000件产品。然后运行以下代码将其转换为数据框。请记住，只需要产品标题列，因为它将用于搜索类似产品。#Data:http://deepyeti.ucsd.edu/jianmo/amazon/data=[]withgzip.open('meta_Cell_Phones_and_Accessories.json.gz')asf:forlinf:data.append(json.loads(l.strip()))#预处理：https://colab.research.google.com/驱动器/1Zv6MARGQcrBbLHyjPVVMZVnRWsRnVMpV#scrollTo=LgWrDtZ94w89#Convertlistintopandasdataframedf=pd.DataFrame.from_dict(data)df.fillna('',inplace=True)#Filterunformattedrowsdf=df[~df.title.str.contains('getTime')]#Restricttojust'CellPhonesandAccessories'df=df[df['main_cat']=='手机&配件']#Resetindexdf.reset_index(inplace=True,drop=True)#Onlykeepthetitlecolumnsdf=df[['title']]#Checkthedf打印（df.shape）<代码>df.head()如果一切正常，您将看到如下输出：AmazonProductDatasetEmbeddings要对文本数据执行相似性搜索，您必须首先将其转换为数字向量。一种快速简便的方法是使用预训练网络嵌入层，例如Facebook[FastText]提供的网络嵌入层。由于我们希望所有行都具有相同的长度向量，而不考虑标题中的单词数，因此我们将在df中的标题列上调用get_sentence_vector方法。嵌入完成后，将emb列作为列表输入到NN算法中。理想情况下，此步骤之前应进行一些文本清理预处理。此外，使用微调的嵌入模型是个好主意。#TitleEmbeddingusingFastTextSentenceEmbeddingdf['emb']=df['title'].apply(ft.get_sentence_vector)#ExtractouttheembeddingscolumnalistoflistsforinputtoourNNalgosX=[item.tolist()foritemindf函数['emb'].values]Benchmark有了算法的输入，下一步就是进行benchmarking。具体地，在搜索空间中的产品数量和被搜索的K个最近邻之间进行循环测试。在每次迭代中，除了记录每个算法的耗时外，还会检查pct_overlap，因为一定比例的KNN最近邻也会被挑出来作为ANN最近邻。请注意，整个测试在24/7全天候运行的8核、30GBRAM机器上运行了大约6天，这有点耗时。理想情况下，您可以通过多处理来加快速度，因为每次运行都是独立的。#Numberofproductsforbenchmarkloopn_products=[1000,10000,100000,len(X)]#Numberofneighborsforbenchmarkloopn_neighbors=[10,100]#Dictionarytosavemetricresultsforachiteration<代码>指标={'products':[],'k':[],'knn_time':[],'ann_time':[],'pct_overlap':[]}forproductsintqdm(n_products):#"products"numberofproductsincludedinthesearchspacefeatures=X[:products]forkintqdm(n_neighbors):#"K"最近邻搜索#KNNknn_start=datetime.now()nbrs=NearestNeighbors(n_neighbors=k,metric='euclidean').fit(特征)knn_distances,knn_neighbor_indices=nbrs.kneighbors(X)knn_end=datetime.now()指标['knn_time'].append((knn_end-knn_start).total_seconds())#HNSWANNann_start=datetime.now()p=fit_hnsw_index(features,ef=k*10)ann_neighbor_indices,ann_distances=p.knn_query(features,k)ann_end=datetime.now()metrics['ann_time'].append((ann_end-ann_start).total_seconds())#AveragePercentOverlapinNearestNeighborsacrossall"products"代码指标['pct_overlap'].append(np.mean([len(np.intersect1d(knn_neighbor_indices[i],ann_neighbor_indices[i]))/kforiinrange(len(features))]))metrics['products'].append(products)metrics['k'].append(k)metrics_df代码=pd.DataFrame(指标)metrics_df.to_csv('metrics_df.csv',index=False)metrics_df运行结束时的输出如下。从表中可以看出，HNSWANN完全超越了KNN。结果以表格形式呈现。结果以图表的形式查看基准测试的结果，以真正理解两者之间的区别，其中使用标准的matplotlib代码绘制这些图表。差距是惊人的。根据查询K=10和K=100最近邻所需的时间，HNSWANN完全淘汰了KNN。当搜索空间包含约50万个产品时，ANN搜索100个最近邻的速度是KNN的380倍，搜索到的两个最近邻之间的相似度为99.3%。当搜索空间包含500K个元素，搜索空间中每个元素找到K=100个最近邻时，HNSWANN的速度比Sklearn的KNN快380倍。当搜索空间包含500K个元素时，搜索空间中每个元素找到K=100个最近邻，HNSWANN和KNN搜索到的最近邻相似度为99.3%。基于以上结果，作者认为可以有把握地说：“KNN已死”。本文代码作者已在GitHub上给出：https://github.com/stephenleo/adventures-with-ann/blob/main/knn_is_dead.ipynb
