稀疏矩阵 干货 机器学习-稀疏矩阵的处理

原标题:干货|机器学习-稀疏矩阵处理

什么是稀疏矩阵？

我们知道矩阵是由m行n列组成的二维数据对象，所以有m x n个值。当这个矩阵的大部分值为零，非零元素不规则分布时，这个矩阵称为稀疏矩阵。下图显示了一个8×8稀疏矩阵。

然后我们来看看计算时间的对比。我们运行三种不同的分类算法:伯努利朴素贝叶斯、逻辑回归和支持向量机，然后分别检查每种算法的处理时间。

测试结果总结如下:

可以看出，稀疏矩阵下朴素贝叶斯分类器的运行速度提高了8倍；对于logistic回归，我们可以看到处理时间减少了33%左右，虽然性能不如朴素贝叶斯，但速度提升依然明显；最后，看看支持向量机，与密集矩阵相比，稀疏矩阵只占用一半的处理时间！一般来说，将稠密矩阵转化为稀疏矩阵几乎总能提高处理时间的效率。

稀疏矩阵的稀疏处理

一般来说，为了处理稀疏矩阵，我们会构造更有效的数据结构，压缩稀疏的行和列，或者通过PCA、SVD等方法降维。

1构建更有效的数据结构

因为零值没有太大的意义，我们可以忽略零值，只需要将数据存储或操作在非零值的稀疏矩阵中。有许多数据结构可以用来有效地构造稀疏矩阵。这里有三个常见的例子。

●键字典:使用行和列索引映射到值的字典。

●列表列表:矩阵的每一行都存储为列表，每个子列表都包含列索引和值。

●坐标列表:每个元组存储一个元组列表，包括行索引、列索引和值。

压缩稀疏行或列

通过了解数据，可以合并或删除一些列。比如上面提到的，我们可以将应用按照类型分为金融、娱乐、音乐或电影，然后进行合并，这样可以大大提高计算效率。但是，一些使用频率远低于平均值的列可以适当删除。

3降维

除了传统的PCA、k-SVD、LDA、NNMF等方法，今天我们分享PCA的一个扩展:构造-核集算法。

以维基百科的文本为例，一个369万×796万的稀疏矩阵，复杂度在空之间可想而知。目前还没有能够计算这个矩阵特征值的降维算法。基于此，即使使用最先进的GenSim库在Wiki“文件-词汇”的稀疏矩阵上运行SVD算法，计算机也会在前几千个文件的随机投影过程中快速走下。本文介绍了一种新的构造-核集算法，可以有效地解决上述问题。

低核心集核心集):

基本概念:

对于n维空之间的点集和n维空之间的向量，我们定义向量和点集s之间的最小欧氏距离如下:

对于维矩阵A，它的行向量是，我们把A到S的距离的平方和定义为:

对于核心集:

所谓核心集是指一个矩阵A，它的行向量可以理解为n维空之间的m个点。而核心集就是这些行向量加权的集合c，即。此时我们说核心集C是矩阵A的行向量集的加权子集，但当所有权重都等于1时，这就是集C为A的行向量集，另外，核心集需要满足所有K阶子空的S到A的距离可以近似表示为C到A的核心集的距离..数学表达式是:

简单地说，s到a的距离可以用s到c的距离来近似。

可以理解，当大部分权重等于0时，原来的440万个文档可以用最后几千个文档乘以各自的权重来表示，可以保持足够的信息量，此时的数据量从原来的369万×796万减少到几千×796万。

从这个角度来看，核心集不处理矩阵A中的维度，只压缩行数。因此，通过将构建的核集与现有的主成分分析、奇异值分解或LSA相结合进行降维，可以将原始稀疏矩阵压缩成新的矩阵。

此时，我们可以应用奇异值分解-核集或主成分分析-核集来多步降低稀疏矩阵的维数。

低核心集示例:

在抽样过程中，采用核心集算法、均匀随机抽样和加权随机抽样构造的样本集，对于不同的迭代次数k，由公式计算的相对误差比较图如下图所示-。

可以看出，用核集构造法采样的相对误差一般比其他两种方法更稳定。换句话说，通过构造用于采样的核心集，其样本在表示整体性能方面更具优势，尤其是当样本数量超过一定阈值时。

图为采用不同降维方法对整个维基百科数据进行LSA分析的实验。红线是使用MATLAB的svds工具箱在16GB内存的笔记本电脑上运行的结果，蓝线是使用MATLAB的svds工具箱在集群上运行的结果，绿线是使用内核集-SVD方法在集群上运行的结果。

可以看出，随着维数的增加，每种方法的运行时间都在增加，但svds方法在笔记本上运行MATLAB的LSA分析却因为内存溢出而最先崩溃。在MATLAB的SVD与核集-SVD方法的比较中，核集-SVD方法在运行时间和复杂度方面的优势在空之间。

因此，在大规模稀疏矩阵的降维过程中，核心集结合其他降维方法可以有效提高模型的数据降维性能。