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个独立的标签组成，每个标签是20000个标签中的一个，但是类的数量与我现在要做的事情无关。）

我正在使用sklearn的KNN算法执行此操作：

from sklearn import neighbors

clf = neighbors.KNeighborsClassifier(n_neighbors=1)
clf.fit(trainX, trainY)
clf.predict(testX[0])

甚至预测一个项目也需要一段时间（比如30-60秒，但是如果你乘以200万，那就几乎不可能了）。我的16GB内存的笔记本电脑开始交换一点内存，但在testX中确实完成了一个项目。

我的问题是，我该怎么做才能在合理的时间内完成？比如说一个晚上在一个大型的EC2上？会有更多的内存和阻止交换速度足够快（我猜是没有）。也许我可以利用稀疏来加速计算？

谢谢你。

Answer 1

Even predicting for 1 item of testX takes a while (i.e. something like 30-60 secs, but if you multiply by 2 million, it becomes pretty much impossible).

这正是所有scikit学习估计器在其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

Maybe I can somehow make use of the sparsity to speed up the calculation?

你可以从训练集中抽取样本，而不是全部使用。k-NN的性能取决于训练集的大小，这就是为什么香草k-NN算法不是一个很好的文本分类选择。

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

Answer 2

据我所知，弗兰恩和安都不能很好地处理稀疏数据。我刚刚发布了一个新的C++库，用于KNN搜索，用于通用数据类型和通用相似性度量在www. kgCop.Org。你所要做的就是插入计算对象i和对象j之间相似性的函数，库将完成其余的魔术。缺点是，使用python可能无法获得太多好处。由于相似度计算代码将被频繁调用，因此为用户提供的度量添加python API没有多大意义。

Answer 3

经典的kNN数据结构，如用于sklearn的KD树，随着数据维数的增加而变得非常慢。对于非常高维的问题，最好切换算法类并使用近似近邻（ANN）方法，不幸的是，这种方法似乎缺乏。有关算法和理论的论文，请参见下面的链接，在这些情况下，为什么近似近邻速度更快。

<> L.>P>一个著名的在C++世界中的ANN库，它广泛应用于计算机描述中的特征描述符空间中的最近邻，是^{}。主页上说它包含Python绑定（那时我从未使用过）。

• 另一个流行的替代方案是带有Python包装器的^{}库，尽管较新的FLANN目前似乎更流行。

• 另请参见this answer（但有些链接已失效）。

一个警告：你的数据似乎是高维的，我不知道这些库是如何为你工作的。他们仍然应该打败sklearn。