稀疏矩陣在機器學習方面是很常見的。儘管它們自然而然地出現在一些數據收集過程中，更多時候，它們是在使用特定的數據轉化技術時得到的。例如我們用一個演算法來提取詞性標籤作為補充標籤，來訓練序列分類器；如果在文檔全集中進行提取，其結果可以被向量化成一個非常巨大的稀疏矩陣，從而作為參數傳遞給分類器；又例如從TalkingData的移動數據中，把移動設備的品牌以及使用的app這兩個變數變為虛擬變數時，我們會得到一個數萬列的稀疏矩陣。

說了這麼多稀疏矩陣，我們不禁會問，是不是也存在稠密矩陣？答案是顯而易見的，那些非零數值佔大多數元素的矩陣即是稠密矩陣（Dense Matrix）。那麼兩者之間除了直觀上的不同，還有其他深層次的區別嗎？或者說，相對於稠密矩陣，稀疏矩陣有哪些優點？

為什麼使用稀疏矩陣？

由於稀疏矩陣含有許多數值為零的元素，我們可以運用特定演算法做以下兩件重要的事：

1. 壓縮矩陣對象的內存檯面空間

2. 加速多數機器學習程序

存儲稀疏矩陣必須為矩陣中的每個32位乃至64位零值分配存儲器，這明顯是浪費內存資源的，因為這些零值不包含任何信息。我們可以利用壓縮技術使我們需要存儲的數據量最小化。這並非唯一好處。幾乎所有的自然機器學習演算法都要求數據矩陣事先存在於內存中，也就是說，當數據矩陣不能完全存入內存中時，機器學習過程就會中斷。將稠密矩陣轉換成稀疏矩陣的好處之一就是在多數情況下，稀疏矩陣可以被壓縮到能適應內存容量。

再者，考慮一個稀疏矩陣和一個稠密矩陣相乘。儘管稀疏矩陣中有很多零值，我們也知道零乘以任何數還是零，然而常規途徑會不可避免地進行此無意義的運算。這就大大拖延了處理時間。顯然，只操作那些返回非零數值的元素是更加有效率的。因此，任何用到基本數學運算（比如乘法）的演算法都能從稀疏矩陣實施中獲益。

我們可以通過下面這個簡單的例子驗證以上結論。假設我們有一個2000×10000的數據集，該矩陣的元素只有1和0兩個數值。為了直觀表現出這個矩陣的稀疏度，我們建立一個象限，用點來表示數值為1的元素，數值為0的元素則留白，如下圖所示。

可以看到，圖像化的數據集大部分都是空白的。作為比較，下圖所示的是一個元素數量相同的稠密矩陣。

現在我們嘗試將稠密矩陣轉換成稀疏矩陣。這裡，我們通過Python SciPy模塊中的壓縮稀疏行（CSR）演算法來完成這一操作。壓縮結果如下圖所示。可以看到，稠密矩陣的大小是160 MB，而稀疏矩陣的大小則是24 MB，這相當於85%的壓縮率！

接著讓我們來看一下計算時間方面的比較。我們運行三種不同的分類演算法：伯努利樸素貝葉斯（Bernoulli Naive Bayes）、邏輯回歸（Logistic Regression）、以及支持向量機（Support Vector Machines），然後分別檢查各個演算法的處理時間。

試驗結果總結如下：

可以看出，樸素貝葉斯分類器在稀疏矩陣下運行速度提升了8倍；對於邏輯回歸，我們看到處理時間減少了大約33%，儘管性能不如樸素貝葉斯，提速還是很明顯的；最後來看支持向量機，相對於稠密矩陣，稀疏矩陣僅僅用了一半的處理時間！總的來說，將稠密矩陣轉換為稀疏矩陣形式幾乎總是可以提升處理時間上的效率。

稀疏矩陣稀疏性處理

通常，為了處理稀疏性矩陣，我們會構造更為有效的數據結構，壓縮稀疏行和列，或者通過PCA、SVD等方法來進行降維。

1構造更為有效的數據結構

因為零值沒有太多的意義，所以我們可以忽略零值，並且僅需要存儲或操作稀疏矩陣中數據或非零值。有多種數據結構可用於有效地構造稀疏矩陣，下面列出了三個常見的例子。

● Dictionary of Keys：使用字典，其中行和列索引映射到值。

● List of Lists：矩陣的每一行都存儲為一個列表，每個子列表包含列索引和值。

● Coordinate List ：每個元組都存儲一個元組列表，其中包含行索引、列索引和值。

2壓縮稀疏行或者列

可以通過對數據的理解來合併或者刪除部分列。例如上文提到app數據，我們可以將app根據其所屬的類型分為金融、娛樂、音樂或者電影等，之後將其進行合併，即可大大提高運算效率。而對於一些使用頻率遠低於平均值的列可以酌情刪掉。

3降維

除了傳統的PCA、k-SVD、LDA、NNMF等方法外，今天分享一個PCA方法的延展：構築-核心集演算法。

將維基百科的文本作為案例，一個369萬（份文件）×796萬（個英文辭彙）的稀疏矩陣，其空間複雜度可想而知。目前還沒有一種降維演算法能夠計算這個矩陣的特徵值。基於這點，即便是用最先進的GenSim庫來對維基的「文件-辭彙」稀疏矩陣運行SVD演算法，計算機也會很快地在最初的幾千份文件的隨機投影過程中宕機。這裡介紹一種新的構築-核心集演算法，從而有效的解決上述問題。

● (k,ε)-核心集((k,ε)-Coreset)：

基礎概念：

對於一個n維空間的點集

和一個n維空間內的向量

，我們定義向量

到點集S中的最小歐式距離為：

對於一個(m×n)維的矩陣A，其行向量是

，我們定義A到S的距離平方和為：

對於核心集：

所謂核心集，指的是對於一個(m×n)的矩陣A，其行向量

可以理解為m個在n維空間的點。而核心集是由這些行向量

加權之後的集合C，即

（這裡的所有權重均大於等於0）。這時我們說，核心集C是矩陣A的行向量集合的一個加權子集。但所有權重均等於1時，這是集合C就是A的行向量的集合。此外，核心集還需滿足，對於所有的k階子空間S，其到A的距離可以近似的表示成其到A的核心集C的距離。用數學表達式表示則是：

簡單地說，就是S到A的距離可以用S到C的距離近似表示。

可以這樣理解，當絕大多數的權重都等於0的時候，原先的440萬份文件，就可以用最後的幾千份文件乘以各自權重代表，並且保持足夠程度的信息量，這時的數據量就從原先的369萬（份文件）×796萬（個英文單詞）降低到幾千（份文件）×796萬（英文單詞）的程度。

從這個角度來講核心集並未對矩陣A中的維度進行處理，而僅僅是對行數進行了壓縮。因此，將構建核心集結合已有的PCA、SVD或者LSA降維，可以將原有的稀疏矩陣壓縮至一個新的(p×q)的矩陣

（這裡，p?m,q?n）。

至此，關於稀疏矩陣的降維處理，我們可以應用SVD-Coreset，或者PCA-Coreset方法進行多步降維。

● 核心集算例：

在抽樣的過程中，利用核心集演算法和利用均勻隨機抽樣，以及加權隨機抽樣所構築的樣本集合，對於不同的迭代次數k，在利用（3）式計算出來的相對誤差對比圖，顯示在下圖（a）-（c）中。

可以看到利用核心集構造的方法抽樣，其相對誤差對比另外兩種方法總體上更為穩定。換言之，通過構造核心集的方法進行抽樣，其樣本在代表全體的表現上更有優勢，尤其是當樣本數量超過一定閾值的時候。

圖（e）顯示的是，應用不同的降維方法在整個（369萬×796萬）維基百科的數據上進行LSA分析的實驗。紅色的線是利用MATLAB的svds工具箱在16GB內存筆記本電腦上運行的結果，藍色的線是利用MATLAB的svds工具箱在集群上運行的結果，綠色的線是利用核心集-SVD方法在集群上運行的結果。

可以看到，隨著維度的增加，每個方法的運行時間都在增加，但是最先崩潰的是用筆記本運行MATLAB的svds方法的LSA分析，原因是內存溢出。在分別利用MATLAB的svds和核心集-SVD的方法比較中，無論是運行時間，還是空間複雜度上，核心集-SVD方法相比較之下具有優勢，並且優勢明顯，且表現穩定。

因此，在大規模稀疏矩陣的降維處理過程中，核心集配合其他的降維方法（包括PCA、SVD等），可以有效的提高模型對數據降維處理的性能。

相關閱讀：

諮詢專欄丨信用卡App運營中的數據分析

諮詢專欄丨四大步驟手把手教你做數據驅動的精準營銷

諮詢專欄丨使用現金貸的都是哪些人？他們有什麼特徵？

推薦閱讀：