乐趣区

关于人工智能:稀疏矩阵的概念介绍

jiezi

在机器学习中，如果咱们的样本数量很大，在大多数状况下，首选解决方案是缩小样本量、更改算法，或者通过增加更多内存来降级机器。这些计划不仅粗犷，而且可能并不总是可行的。因为大多数机器学习算法都冀望数据集（例如罕用的 DataFrame）是保留在内存中的对象（因为内存读取要比磁盘读取快不止一个量级），所以降级硬件这种解决方案基本上会被否定。所以科学家们找到的一种既可能保存信息，又节俭内存的计划：咱们称之为“稠密矩阵”。

背景

Pandas 的 DataFrame 曾经算作机器学习中解决数据的标配了，那么稠密矩阵的真正需要是什么？答案是空间复杂度和工夫复杂度。当波及数百万行和 / 或数百列时，pandas DataFrames 变得最蹩脚，这时因为 pandas DataFrams 存储数据的形式。例如上面的图, 这是 CSV 文件的磁盘和内存大小比拟。咱们在这里应用的数据集是 Santander Customer Satisfaction 数据集。途中比拟了 CSV 文件在读取为 DataFrame 之前和读取为 DataFrame 之后的磁盘 / 内存应用状况。

import os
import pandas as pd

#Read csv file
data = pd.read_csv("train.csv")
memory_usage = data.to_numpy().nbytes/1e6

#Read the original file size using os module
disk_usage = os.path.getsize('/content/train.csv')/1e6

#Lets plot results
plt.figure(figsize=(10,8))
plt.bar(x=["CSV","DataFrame"],height=[disk_size,memory_usage])
plt.title("Size comparison - CSV vs DataFrame")
plt.ylabel("Usage (MB)")
plt.show()

能够显著地看到数据大小的差别，可能是因为外面蕴含了很多 0 或者空值导致的，本文前面咱们会有具体的剖析和介绍

什么是稠密矩阵？

有两种常见的矩阵类型，密集和稠密。次要区别在于稠密指标有很多零值。密集的指标没有。这是一个具备 4 列和 4 行的稠密矩阵的示例。

在下面的矩阵中，16 个中有 12 个是零。这就引出了一个简略的问题：

咱们能够在惯例的机器学习工作中只存储非零值来压缩矩阵的大小吗？

简略的答案是：是的，能够！

咱们能够轻松地将高维稠密矩阵转换为压缩稠密行矩阵（简称 CSR 矩阵）。对于这种压缩咱们的要求是压缩后的矩阵能够利用矩阵运算并以无效的形式拜访指标，所以 CSR 并不是惟一办法，还有有更多的选项来存储稠密矩阵。例如：Dictionary of keys (DOK)、List of Lists (LIL)、Coordinate list (COO)、Compressed row storage (CRS) 等。

然而稠密矩阵的一个次要毛病是拜访单个元素变得更加简单。上面能够为抉择不同的办法提供一些参考：

  • 如果关怀的是高效批改 – 应用 DOK、LIL 或 COO。这些通常用于构建矩阵。
  • 如果关怀的是无效的拜访和矩阵操作 – 应用 CSR 或 CSC

下面说到了很多名词为简略起见咱们深入研究一个 CSR 的示例。思考上面的矩阵。

将上述矩阵转换为 CSR 矩阵的状况。在这里应用的是 scipy 包的 sparsemodule。

import numpy as np
from scipy import sparse#create the metrix with numpy
m = np.array([[1,0,0,0],
             [0,1,2,0],
             [0,0,0,0],
             [2,1,1,1]])
#convert numpy array into scipy csr_matrix
csr_m = sparse.csr_matrix(m)

尽管咱们的原始矩阵将数据存储在二维数组中，但转换后的 CSR 矩阵将它们存储在 3 个一维数组中。

值数组 Value array：顾名思义，它将所有非零元素存储在原始矩阵中。数组的长度等于原始矩阵中非零条目标数量。在这个示例中，有 7 个非零元素。因而值数组的长度为 7。

列索引数组 Column index array：此数组存储值数组中元素的列索引。（这里应用从零开始的索引）

行索引数组 Row index array：该数组存储所有以后行和之前行中非零值的累积计数。row_index_array [j] 编码第 j 行上方非零的总数。最初一个元素示意原始数组中非零元素的数量。长度为 m + 1；其中 m 定义为原始矩阵中的行数。

这样下面的矩阵被存储为以下模式：

下面两个数组很好了解，然而第三个行索引数组 Row index array 看起来就没有那么直观了：

Row index array 的数值个数是 #row + 1, 示意该行后面值在 values 的总数，或者说第一个值在 values 中的地位

咱们顺次解释下：

  • 第一个值 0：后面的 values 总数是 0，也就是 values 的 index 起始是 0。
  • 第二个值 1：示意第 3 行起始，前一行的只有一个非 0 值，所以后面的 values 总数是 1，也就是 values 的 index 起始是 1。
  • 第三个值 3：示意第 3 行起始，前二行的非 0 值为 3（1，1，2），所以后面的 values 总数是 3，也就是 values 的 index 起始是 3。
  • 第四个值 3：示意第 4 行起始，因为第 3 行没有非 0 值，所以非 0 值的总数还是 3
  • 第五个值 4：没有第 5 行，所以能够认为这个值是整个矩阵中所有非 0 值的总数

绘制样本数据

同样咱们也能够对稠密的矩阵进行可视化 

import matplotlib.pyplot as plt
plt.style.use('fivethirtyeight')

#read dataset
data = pd.read_csv("train.csv")

#plot samples
plt.figure(figsize=(8,8))
plt.spy(data.head(500).T)
plt.axis('off')
plt.grid(False)
plt.show()

这张图他能通知咱们什么？首先，这里是 plt.spy () 函数的介绍：绘制二维数组的稠密模式。这可视化了数组的非零值。

在上图中，所有黑点代表非零值。所以能够了解为将这些数据转换为稠密矩阵是值得得，因为可能节俭很多得存储。

那么如何判断数据的稠密水平呢？应用 NumPy 能够计算稠密度。

sparsity = 1- np.count_nonzero(data)/ data.size
print(sparsity)

在咱们应用的数据集运行代码后，会失去 0.906 作为稠密度。这意味着，超过 90% 的数据点都用零填充。回到嘴下面的图，这就是下面咱们看到为什么 pandas 占用内存多的起因。

咱们为什么要关怀稠密矩阵？

好吧，应用稠密矩阵有很多很好的理由。他们次要是，

  • 与根本办法相比，可节俭大量内存。
  • 与传统办法相比，它通常会缩小模型训练工夫。

sklearn API 中的简直所有算法当初都反对 csr_matrix 作为输出，这是一个十分好的音讯

例如上面：这是来自 sklearn.ensemble.RandomForestClassifier 的示例

X {array-like, sparse matrix} 形态 (n_samples, n_features)

训练输出样本。在函数外部它的 dtype 将被转换为 dtype = np.float32。如果提供了稠密矩阵，则将其转换为稠密的 csc_matrix。

让咱们持续应用数据集进行试验。

内存压缩比拟 

def get_mem_usage(train,test,labels=['Train','Test'],plot=True):
    
    """Helper function for plotting in-disk memory usage for pandas df"""
    
    #get the original memory usage 
    train_original_size = train.to_numpy().nbytes/1e6
    test_original_size = test.to_numpy().nbytes/1e6
    
    #convert into csr_metrix
    train_csr = sparse.csr_matrix(train)
    test_csr = sparse.csr_matrix(test)
    
    #get memory usage
    train_csr_size = (train_csr.data.nbytes+train_csr.indptr.nbytes+train_csr.indices.nbytes)/1e6
    test_csr_size = (test_csr.data.nbytes+test_csr.indptr.nbytes+test_csr.indices.nbytes)/1e6
    
    original_sizes = [train_original_size, test_original_size]
    sparse_sizes = [train_csr_size, test_csr_size]
    
    if plot:
        width = 0.35
        x = np.arange(len(labels))

        fig, ax = plt.subplots(figsize=(10,8))

        rects1 = ax.bar(x - width/2, original_sizes, width, label='Original')
        rects2 = ax.bar(x + width/2, sparse_sizes, width, label='Sparse')

        ax.set_ylabel('Memory Usage(MB)')
        ax.set_title('Memory Usage Comparison'.title())
        ax.set_xticks(x)
        ax.set_xticklabels(labels)
        ax.legend()

        plt.grid(False)
        plt.show()

    else:
        return sparse_sizes+original_sizes
        
from sklearn.model_selection import train_test_split

#train test split
xtrain,xtest,ytrain,ytest = (train_test_split(X,y,test_size=0.3,random_state=1997))

#plot compressed memory vs original memory
get_mem_usage(xtrain,xtest)

咱们的数据集大抵压缩为 0.9 倍，下面计算出的数据集的稠密度也是 0.96，根本相似

通过这个简略的技巧，咱们缩小了数据集的内存使用量。让咱们持续进行模型训练工夫比拟。

模型训练工夫比照

在这里将应用 sklearn API 测试风行的机器学习算法。

LogisticRegression

GradientBoostingClassifier

LinearSVC

上图中能够看到，LogisticRegression 和 GradientBoostingClassifier 能够显著地提高效率然而，LinearSVC 效率不显著，这可能是因为 LinearSVC 须要投影到更高的维度无关（这个不确定，然而它的算法和 LR 和 GBC 不太一样），然而总之，应用稠密矩阵不仅能够升高内存占用还能够进步训练的效率。

https://www.overfit.cn/post/b47f933731bc43c28733c93dd991af72

作者：Ransaka Ravihara

退出移动版