在Sklearn中使用稀疏矩阵会使算法变慢还是变快？

Question

我有大量但稀疏的训练数据。我想在ExtraTreeClassifier中使用它。考虑到计算时间，我不确定是否需要使用稀疏csr_matrix或原始数据。哪个版本的数据使用该分类器运行得更快，我们是否可以将其答案推广到所有具有稀疏功能的模型？

Answer 1

如果你的数据是稀疏的，额外的树分类器使用csc_matrix会更快。如果有疑问，我建议您同时使用两个版本进行基准测试。

如果您的数据足够稀疏，则所有算法都应从使用适当的稀疏格式中受益。例如，基于点积的算法在数据稀疏的情况下会快得多。

Answer 2

取决于您的数据

内存消耗。

如果你的数据是密集的，那么密集的表示需要d*sizeof(double)字节的数据(即通常是d * 8字节)。稀疏表示通常需要sparsity*d*(sizeof(int)+sizeof(double))。根据您的编程语言和代码质量，由于内存管理开销，它也可能更多。典型的Java实现增加了8字节的开销，并将舍入为8字节大小；因此稀疏向量可以很容易地使用16 + sparsity * d * 24字节。然后。

如果稀疏度为1，这意味着稀疏表示需要多50%的内存。我猜practise的内存折衷应该是50%左右的稀疏性；如果你的实现没有仔细优化，可能甚至是30% -所以每3个值中就有1个应该是零。

内存消耗通常是一个关键问题。你使用的内存越多，你的CPU就会有更多的页面错误和缓存缺失，这可能会对性能产生很大的影响(这就是为什么BLAS会以针对你的CPU缓存优化的块大小执行大的矩阵乘法)。

优化和SIMD。

密集向量代码(例如BLAS)通常比稀疏操作优化得更好。具体地说，SIMD (单指令，多数据) CPU指令通常只与密集数据一起工作。

随机访问。

许多算法可能需要随机访问向量。如果您的数据表示为double[]数组，则随机访问是O(1)。如果您的数据是稀疏向量，则随机访问通常是O(sparsity*d)的，即您必须扫描向量以检查是否存在值。因此，对于某些操作，转置矩阵可能是有益的，并且使用稀疏列而不是稀疏行。

另一方面，一些算法可能会从中受益。但许多实现都内置了这样的优化，并将自动处理这些优化。有时你也有不同的选择。例如，APRIORI在行上工作，因此可以很好地处理行稀疏数据。另一方面，Eclat是一个解决相同问题的算法，但它首先将所有数据转换为行稀疏形式，然后甚至计算列差异以进一步优化。

代码复杂性。

处理稀疏数据的代码通常要复杂得多。特别是，它不能轻易地利用SSE和类似的快速CPU指令。这就是为什么稀疏矩阵乘法比密集运算慢得多的原因之一-在不知道数据的某些特征的情况下优化这些运算是令人惊讶的困难。:-(