logo标签列表

Python中的大稀疏矩阵kNN

pythonscikit-learnsparse-matrixnearest-neighbor
9

我有两个大的稀疏矩阵：

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>

总共需要加载大约5GB的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])

即使预测1个testX项目也需要一段时间（例如30-60秒），但如果乘以200万，就几乎不可能完成。我的配备有16GB RAM的笔记本电脑开始有点交换内存，但确实可以完成1个testX项。

我的问题是，我该怎么做才能在合理的时间内完成呢？比如在一个大型EC2实例上一夜之间？仅仅增加RAM并防止交换是否足以加快速度（我的猜想是否定的）。也许我可以以某种方式利用稀疏性来加快计算速度？
谢谢。
doc 表明，在拟合稀疏矩阵时，该实现使用“暴力法”，计算所有对的距离。 - xiaohan2012
4个回答
11

传统的kNN数据结构，如在sklearn中使用的KD树，在数据维度增加时变得非常缓慢。对于高维问题，建议切换算法类别并使用近似最近邻（ANN）方法，不幸的是，sklearn似乎缺乏这方面的支持。下面的链接提供了有关算法和理论的文献，说明在这些情况下近似最近邻为什么更快。

  • C ++世界中一个著名的ANN库，在特征描述符空间中用于最近邻的计算机视觉领域广泛使用，称为FLANN。网站上说它包含Python绑定（我从未使用过）。

  • 另一个流行的选择是ANN库，其Python封装程序在此，虽然新的FLANN似乎目前更受欢迎。

  • 还可以查看此答案（但有些链接已失效）。

一个需要注意的问题：您的数据似乎非常高维 - 我不知道这些库在您的情况下的表现如何。它们仍然应该击败sklearn。

在OpenCV中：基于FLANN的匹配和C++源代码。 - samkhan13
谢谢。我的数据是文本数据 - 我现在已经执行了LSA处理，将其降至100维。 sklearn现在每个测试用例大约需要0.5秒，但对于200万条记录来说仍然太慢了。我正在探索FLANN，稍后会回复您它的效果如何。 - mchangun
100维应该非常适合FLANN。视觉中通常使用128维的描述符空间。如果我的答案解决了您的问题，请点赞/接受（最近许多人似乎忘记了这一点）。 - DCS
@DCS 我还没有忘记，一直在试用中。现在它已经很好地工作了，谢谢。 - mchangun
7
“即使是预测一个testX项目也需要一段时间（例如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的性能取决于训练集的大小，这就是为什么传统的k-NN算法并不适用于文本分类的原因。
（文本处理领域的一个常用技巧是使用磁盘索引来构建k-NN分类器，例如Lucene：将整个文档作为查询，检索出前k个文档，从中确定标签。）
根据“算法”文档，我认为批量预测在这种情况下并没有太大帮助：对于稀疏输入的拟合将覆盖此参数的设置，使用蛮力算法。 - Matt
@Matt：这是因为它每批次执行一次性能输入验证，而不是每个样本执行一次，并且避免了Python的函数调用开销——这与稀疏与密集无关。此外，OP说他们已经对数据进行了LSA处理，而LSA（TruncatedSVD）的输出始终是一个密集数组。 - Fred Foo
抱歉，我漏看了那个。我只看了OP问题中的trainX。 - Matt
@larsmans 感谢你的Lucene提示，我以前从未听说过。如果你有在Python中使用它的好例子/文档，我很想看看。 - mchangun
@mchangun：有pylucene，还有我的Lucene+Jython教程。 - Fred Foo
2
据我所知，FLANN和ANN都不能很好地处理稀疏数据。我刚刚发布了一个新的C++库，用于泛型数据类型和泛型相似度度量的K-NN搜索，网址是www.kgraph.org。你只需要插入计算对象i和对象j之间相似度的函数，库将完成其余操作。缺点是你可能无法通过使用Python获得太多好处。由于相似度计算代码将被频繁调用，为用户提供的度量添加Python API并没有太多意义。请注意保留HTML标记。
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接