我有两个大的稀疏矩阵：
In [3]: trainX
Out[3]:
<6034195x755258 sparse matrix of type '<type 'numpy.float64'>'
with 286674296 stored elements in Compressed Sparse Row format>
In [4]: testX
Out[4]:
<2013337x755258 sparse matrix of type '<type 'numpy.float64'>'
with 95423596 stored elements in Compressed Sparse Row format>
总共需要大约 5 GB RAM 来加载。请注意，这些矩阵高度稀疏（占用 0.0062%）。
对于中的每一行testX,我想找到the最近邻在trainX并返回其相应的标签，在trainY. trainY是一个长度相同的列表trainX并且有很多很多课程。 （一个类由 1-5 个单独的标签组成，每个标签是 20,000 个标签之一，但类的数量与我现在想做的事情无关。）
我在用sklearn的 KNN 算法可以做到这一点：
from sklearn import neighbors
clf = neighbors.KNeighborsClassifier(n_neighbors=1)
clf.fit(trainX, trainY)
clf.predict(testX[0])
甚至预测 1 项testX需要一段时间（即大约 30-60 秒，但如果乘以 200 万，则几乎不可能）。我的 16GB RAM 笔记本电脑开始进行一些交换，但确实能够完成 1 个项目testX.
我的问题是，我该如何做才能在合理的时间内完成？比如说在大型 EC2 实例上住一晚？只要有更多的内存并防止交换速度就足够了（我的猜测是不会）。也许我可以以某种方式利用稀疏性来加速计算？
谢谢。
经典的 kNN 数据结构，例如中使用的 KD 树sklearn当数据维度增加时变得非常慢。对于非常高维的问题，建议切换算法类别并使用近似最近邻 (ANN) 方法，该方法sklearn不幸的是，似乎缺乏。请参阅下面的链接，了解有关算法和理论的论文，为什么近似最近邻在这些情况下要快得多。
C++ 世界中著名的 ANN 库，广泛用于计算机视觉中的特征描述符空间中的最近邻，是FLANN http://www.cs.ubc.ca/research/flann/。主页说它包含 Python 绑定（当时我从未使用过）。
另一种流行的选择是ANN http://www.cs.umd.edu/~mount/ANN/带有 Python 包装器的库here http://scikits.appspot.com/ann，虽然目前较新的FLANN似乎更受欢迎。
也可以看看这个答案 https://stackoverflow.com/questions/5565935/k-nearest-neighbour-in-python（但有些链接已失效）。
一个警告：你的数据似乎是very高维 - 我不知道这些库如何为您执行。他们还是应该打败sklearn.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
