在Python中使用大稀疏矩阵的kNN

Question

我有两个大的稀疏矩阵:

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,我想找到的最近邻trainX,返回其相应的标签,在发现trainY. trainY是一个长度相同的列表,trainX并且有许多类.(一个类由1-5个单独的标签组成,每个标签是20,000个中的一个,但是类的数量与我现在要做的事情无关.)

我正在使用sklearnKNN算法来做到这一点:

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实例上说一晚？只是拥有更多的内存并防止交换速度足够快(我的猜测是否定的).也许我可以以某种方式利用稀疏性来加速计算？

谢谢.

Answer 1

sklearn当数据的维数增加时,诸如所使用的KD树之类的经典kNN数据结构变得非常慢.对于非常高维的问题,建议切换算法类并使用近似最近邻(ANN)方法sklearn,遗憾的是这些方法似乎缺乏.请参阅下面的链接,了解有关算法和理论的论文,在这些情况下,近似最近邻居的速度要快得多

• C++世界中一个着名的ANN库,在计算机视觉中广泛用于特征描述符空间中的最近邻居FLANN.主页说它包含Python绑定(我从未使用过).

• 另一种流行的选择是ANN用Python包装库在这里,虽然较新的FLANN似乎是目前比较流行的.

• 另见这个答案(但有些链接已经死了).

一个警告:您的数据似乎是非常高的维度 - 我不知道这些库如何为您执行.他们仍然应该击败sklearn.

Answer 2

即使预测 testX 的 1 项也需要一段时间（即大约 30-60 秒，但如果乘以 200 万，这几乎是不可能的）。

这正是所有 scikit-learn 估计器在他们的方法中获取批量样本的原因predict。如果在一次调用中传递多个样本，输入验证和 Python 的慢循环的成本会变小，因此每个样本的时间变得比一个样本的成本乘以样本数量少很多。

>>> from sklearn.datasets import fetch_20newsgroups_vectorized
>>> from sklearn.decomposition import TruncatedSVD
>>> from sklearn.neighbors import KNeighborsClassifier
>>> data = fetch_20newsgroups_vectorized()
>>> X, y = data['data'], data['target']
>>> X = TruncatedSVD(n_components=100).fit_transform(X)
>>> clf = KNeighborsClassifier(n_neighbors=1).fit(X, y)
>>> %timeit clf.predict(X[0])
1000 loops, best of 3: 766 us per loop
>>> %timeit clf.predict(X[0:10])
100 loops, best of 3: 2.44 ms per loop
>>> %timeit clf.predict(X[0:100])
100 loops, best of 3: 14.2 ms per loop
>>> %timeit clf.predict(X[0:1000])
10 loops, best of 3: 117 ms per loop

也许我可以以某种方式利用稀疏性来加速计算？

您可以从训练集中采样，而不是全部使用。k-NN 性能取决于训练集的大小，这就是为什么 vanilla k-NN 算法不是文本分类的很好选择的原因。

（文本处理领域最喜欢的技巧是使用磁盘索引来构建 k-NN 分类器，例如 Lucene：使用整个文档作为查询，检索前k 个文档，从中确定标签。）