如何优化算法用来计算K-近邻算法？
如何优化算法用来计算K-近邻算法？
提问于 2018-10-04 05:20:39
KNN是一种很容易实现的简单算法：
# for each test datapoint in X_test:
# calculate its distance from every points in X_train
# find the top k most closest points
# take majority vote of the k neighbors and use that as prediction for this test data point然而我认为时间复杂度还不够好。在实际应用中，该算法是如何优化的？(比如它使用的是什么技巧或数据结构？)
回答 2
Stack Overflow用户
发布于 2018-10-04 06:22:45
K-近邻算法与其他学习方法不同，因为没有从训练样本中归纳出任何模型。数据保持原样；它们只是存储在内存中。
将遗传算法与k-NN相结合，提高了性能。另一种成功的技术实例选择也被提出，以同时面对k-NN的有效存储和噪声。你可以尝试这样做:当一个新的实例应该被分类时；而不是涉及所有的学习实例来检索k邻居，这将增加计算时间，首先选择较小的实例子集。
您还可以尝试：
通过减少邻域大小的训练documents
- Improving k-NN的数量和通过高级存储结构
减少k-NN的相似性来提高k-NN速度
Stack Overflow用户
发布于 2018-10-20 21:44:29
您所描述的是使用O( kNN (X_test)*size(X_train)*d)的暴力大小计算，其中d是特征向量中的维数。
更有效的解决方案是使用空间索引在X_train数据上建立索引。这通常将单个查找减少到O( log(size(X_train)) * d)，甚至O( log(size(X_train)) + d)。
常见的空间索引有：
- kD-Trees (它们经常被使用，但是使用诸如RStarTree
- Quadtrees之类的'd')
- R-Trees，时伸缩性很差(对于大'd'，通常效率不高，但是例如，PH-Tree与d=1000配合工作很好，并且具有出色的删除/插入时间(免责声明，这是我自己的work))
- BallTrees (我对them)
- CoverTrees不是很了解(对于高'd'，但是构建时间较长的
，我真的不是很了解
还有“近似”NN搜索/查询这一类。它们以正确性和速度为代价，它们可能会跳过几个最接近的邻居。您可以在python here中找到性能比较和大量实现。
如果您正在寻找上面一些空间索引的Java实现，那么可以看看my implementations。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/52635854
复制相关文章
相似问题
腾讯云开发者
