如何克服 KNN 算法的计算成本？

机器算法验证 机器学习 k-最近邻
2022-03-30 14:14:00

当数据集很大时，如何克服 KNN 算法的计算成本。

请记住，我正在使用自己的函数在 R 中构建 knn 算法

是否有任何操纵与此有关？

我已经尝试了 6000 个实例的数据集，这需要很长时间。

笔记

wdbc_n是我的标准化数据集。

Lbl是数据集的类标签。

0.1是我在 lpnorm 函数中定义的 l 范数，我没有放在这里。

fx1NN<-function(TrainS, TestS,TrainLabel,p){ 
  n<-dim(TrainS)[1]
  Dist=matrix(0,nrow=n,ncol=1)
    for (i in 1:n){
      Dist[i]=lpnorm(as.matrix(TrainS[i,]-TestS),p) 
    }
  Dist2=which.min(Dist)
  predL=TrainLabel[Dist2] 
  return(predL)
}


LOOCV1NN<-function(Data,Lbl,p){ 
  N<-dim(Data)[1] 
  predLOOCV=matrix(0,nrow=N,ncol=1)
  for (i in 1:N){
    LOOOCV_train=Data[-i,] 
  LOOOCV_test=Data[i,] 
  TLabel=Lbl[-i] 
predLOOCV[i]=fx1NN(LOOOCV_train,LOOOCV_test,TLabel,p) 
  }

  confM=confusionMatrix(factor(predLOOCV),factor(Lbl)) 
  R=as.matrix(confM)
  Recall=R[1,1]/sum(R[,1])
  Precision=R[1,1]/sum(R[1,])
  F1score=2/((1/Recall)+(1/Precision))
  CorClass=sum(predLOOCV==Lbl) 
LL<-list(confM,CorClass,F1score) 
  return(LL)
}
LOOCV1NN(wdbc_n,Lbl,0.1)
1个回答

有大量关于加速最近邻搜索的文献，以及许多软件库（您可以考虑使用其中之一，而不是从头开始重新实现）。我将在下面描述一些通用类的解决方案。这些方法中的大多数旨在通过利用数据中的某种结构来减少计算量。

并行化

一种方法是并行计算（例如，使用集群、GPU 或单台机器上的多个内核）。这种策略不是减少计算量，而是将问题分解为多个部分，在不同的处理单元上同时解决。例如，加西亚等人。（2008 年）通过使用 GPU 并行化蛮力搜索报告了大幅加速。

精确的空间划分方法

此类方法旨在减少查找最近邻居所需的距离计算次数。数据点用于构建分层划分数据空间的树结构。树可以有效地识别一些无法识别的数据点是新查询点的最近邻居，因此不需要计算到这些点的距离。许多算法存在使用不同类型的树。常见的变体包括 KD 树、度量/球树和覆盖树。例如，参见 Kibriya 和 Frank (2007)。基于树的方法可以用来计算精确的解决方案（即最近的邻居匹配那些通过蛮力搜索找到的）。这种方法对于低维数据是有效的，但在高维设置中性能会下降。还有基于树的近似最近邻搜索方法（见下文）。

近似最近邻搜索

如果愿意满足于近似最近邻而不是精确最近邻，则可以实现更大的加速（特别是对于高维数据）。这在实践中通常就足够了，尤其是对于大型数据集。已经为近似最近邻搜索提出了许多不同的策略。参见 Muja 和 Lowe (2014) 的评论。

基于局部敏感散列 (LSH) 的方法特别流行（例如，参见 Andoni 和 Indyk 2006）。这里的想法是使用专门的哈希函数将数据点有效地映射到离散的桶中，这样相似的点就会出现在同一个桶中。可以在映射到与查询点相同的桶的训练点子集中搜索邻居。散列函数应根据用于定义最近邻居的距离度量进行定制。

还有基于空间划分树和最近邻图的近似最近邻搜索算法。例如，参见 Muja 和 Lowe (2014) 以及 Liu 等人。（2005 年）。

降维

降维将高维数据点映射到低维空间。在低维空间中搜索邻居更快，因为距离计算在更少的维度上进行。当然，必须考虑映射本身的计算成本（这在很大程度上取决于所使用的方法）。请注意，低维空间中的最近邻搜索等效于使用不同的距离度量。

在某些情况下（取决于数据的方法和结构），可以降低维数，以使低维空间中的最近邻与高维空间中的最近邻大致匹配。对于监督学习（例如 KNN 回归和分类），匹配高维空间中的邻居通常无关紧要。相反，目标是学习具有良好泛化性能的函数。降维有时可以通过作为正则化的一种形式来提高泛化性能，或者通过提供距离对问题更有意义的空间。

有大量关于降维的文献，包括线性、非线性、有监督和无监督方法。PCA 通常是人们尝试的第一件事，因为它是一种标准方法，在许多情况下效果很好，并且可以有效地扩展到大型数据集。但是，它（或其他方法）是否能正常工作取决于问题。

有关最近邻搜索的示例应用，请参阅 Degalla 和 Bostrom (2006)，比较 PCA 和随机投影以进行最近邻分类。

特征选择

特征选择方法保留输入特征的子集并丢弃其余部分。通常，训练集中的标签/目标值用于选择与解决分类或回归问题相关的特征。与降维类似，特征选择通过减少维数来加速最近邻搜索。它通常不旨在保持距离。

最近的原型

这里的想法是将训练集压缩成较少数量的代表点（称为原型）。这通过减少要搜索的点数来加速邻居搜索。它还可以对监督学习问题产生去噪效果。加西亚等人。（2012）审查各种方法。

组合方法

上面描述的许多技术可以结合起来产生进一步的加速。例如，Pan and Manochoa (2011) 和 Gieseke 等人。(2014) 使用 GPU 分别并行化局部敏感哈希和基于树的方法。

参考

  • 安多尼和印地克 (2006)。高维近似最近邻的近似最优散列算法。

  • 迪加拉和博斯特罗姆 (2006)。通过主成分分析减少高维数据与最近邻分类的随机投影。

  • 加西亚等人。（2008 年）。使用 GPU 进行快速 k 最近邻搜索。

  • 加西亚等人。（2012）。最近邻分类的原型选择：分类学和实证研究。

  • 吉塞克等人。（2014）。缓冲 kd 树：在 GPU 上处理大量最近邻查询。

  • 基布里亚和弗兰克 (2007)。精确最近邻算法的经验比较。

  • 刘等人。（2005 年）。实用近似最近邻算法的研究。

  • Muja 和 Lowe (2014)。用于高维数据的可扩展最近邻算法。

  • 潘和马诺查 (2011)。用于 k 近邻计算的基于 GPU 的快速局部敏感散列。

其它你可能感兴趣的问题
上一篇数学家的时间序列分析教科书 下一篇随机过程毕竟不是那么随机（确定性）