基于奇異值分解的簡化數據應用

陳卉妍 張仁龍

摘 要：奇異值分解是提取數據特征信息的一種強大工具，其應用可以從信息檢索領域擴展到金融、醫療、統計學等各領域，是簡化數據、相似度計算的一種有效方法。對奇異值分解原理和特性進行闡述，介紹了基于Python與其相關科學計算庫的奇異值分解過程和相似度算法，解釋了將龐大的數據矩陣映射到低維空間的轉換過程，圖像數據通過奇異值分解較原始圖像壓縮了近8倍。分別對SVD在推薦系統和圖像壓縮兩方面的具體應用進行描述，總結出奇異值分解在數據降維中的強大應用和良好前景。

關鍵詞：奇異值分解;推薦引擎;壓縮圖像;相似度計算;數據降維

DOI：10. 11907/rjdk. 191802 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP392文獻標識碼：A 文章編號：1672-7800（2019）008-0162-04

Simplified Data Application Based on Singular Value Decomposition

CHEN Hui-yan， ZHANG Ren-long

（College of Computer and Information Engineering， Beijing University of Agriculture， Beijing 102206， China）

Abstract： Singular value decomposition is a powerful tool to extract data feature information. Its application can be extended from information retrieval to finance， medical， statistics and other fields. It is an effective method to simplify data and similarity calculation. The principle and characteristics of singular value decomposition are expounded in this paper. The process and similarity algorithm of singular value decomposition based on Python and its related scientific computing library are introduced. The mapping of huge data matrix to low-dimensional space is explained. The image data is nearly 8 times compressed by the singular value decomposition than the original image. The specific applications of SVD in recommendation system and image compression are described respectively， and the powerful application and broad prospects of singular value decomposition in data dimension reduction are summarized.

Key Words：Singular value decomposition; recommendation engine; compressed image; similarity calculation; data dimensionality reduction

作者簡介：陳卉妍（1996-），女，北京農學院計算機與信息工程學院碩士研究生，研究方向為數據分析; 張仁龍（1967-），男，北京農學院計算機與信息工程學院教授、碩士生導師，研究方向為程序設計。

0 引言

信息時代，如何從海量數據中檢索出具有價值的信息尤為重要。由于矩陣分解可應用于很多實際問題中，因而在諸多領域得到了廣泛應用，例如推薦系統、信號處理、PCA降維、壓縮數據去噪[1]等。在亞馬遜的推薦算法中，將用戶購買偏好與其他用戶進行對比，據此預測該用戶最可能感興趣[2]的物品并推送給他。中國的淘寶、京東商城、當當書城以及蘇寧易購都屬于協同過濾推薦系統[3]在電子商務中較為成熟的應用典范。

奇異值分解就是矩陣的一種分解方法，利用這種規則的分解方式可用小而多的矩陣集表示原始數據集。而分解數據集的原理就是去除數據中的噪聲和冗余信息，將矩陣拆分成一些小矩陣的點乘，這些小的矩陣就是被保留抽取出來原始數據的相關特征信息。這種分解的核心思想在于其對矩陣的波動并不敏感，因而可以在不改變矩陣相關度量的前提下，得出矩陣的秩，并且逐漸逼近該矩陣的最佳秩，從而使得數據被壓縮[4]、簡化。同樣，該重要性質也可用于協同過濾[5]的推薦引擎中，將當前用戶和其他用戶的數據矩陣進行比較[6]，使用最鄰近方法向用戶實現產品推薦。

1 奇異值分解原理

奇異值分解是一個能適用于任意矩陣的分解方法，對于一個任意m*n的矩陣都有如下分解：

[Datam*n=Um*mΣm*nVTn*n]? ? ? ? ? ? ? ? ? ? （1）

Σ對角線上的元素對應原始數據Data中的奇異值[7]，也即Data*DataT特征值的平方根。通常情況下，前1%～10%的奇異值就可以達到全部奇異值的90%[8]以上，因此可以利用前k個奇異值近似描述整個矩陣。將原始的m行n列數據矩陣分解成為m行k列的矩陣U、k行k列的矩陣Σ和k行n列的矩陣 VT。k是遠遠小于m和n的數，當k與n越相似時，3個矩陣相乘的結果越接近于原始數據Data。

[Datam*n≈Um*kΣk*kVTk*n] （2）

在Python的科學計算庫NumPy中有一個很好的線性代數工具箱linalg，可以方便地實現SVD的具體分解。數據存儲以科學計數法的形式展現，當數值過小時可以忽略不計以0代替。當Σ的對角元素中出現0時，為了節省存儲空間，NumPy會自動將為0的元素刪除，以提高運算效率。矩陣的存儲面積越小，存儲量就會遠遠小于原始數據矩陣Data，并且會在很大程度上提高相似度。分解后具體所需數據如圖1所示。

圖1 深灰色為計算需要數據

2 推薦引擎

2.1 應用原理

在傳統推薦算法中，通常根據產品和用戶數據構成的系數矩陣進行不同項目之間的相似度計算[9]，以完成相似物品推薦。但真實存在的數據往往都是稀疏矩陣，會存在大量空值，使得計算機在運算中做了很多無用功。奇異值分解可以解決這類問題，將原始數據映射到低維空間[10]中，通過減少特征空間從而提高推薦效果，不僅克服了矩陣的稀疏性[11]，還在最大程度上還原了原始數據矩陣。

推薦系統的基本思路是：首先加載原始數據集，定義計算相似度的方法，通過計算奇異值的百分比確定縮小的維度，再對降維數據中為空值的數據進行數值預測，最后以降序排列方式將評分最高的產品返回給用戶完成產品推薦。

2.2 基于SVD的推薦引擎

在推薦系統中，使用最為普遍的一種推薦方法就是協同過濾[12]。首先對數據矩陣進行橫向分析，利用奇異值分解找到與目標用戶具有相似喜好的用戶，再以矩陣的列為標準對比產品與產品之間的相似度，對用戶沒有評分的產品進行推薦，并給出相應的預測分值，以完成產品推薦。

在現有數據中，可以使用不同的距離計算方法計算產品之間的相似度。利用皮爾遜相關系數計算距離時，由于其對用戶的評分量級并不敏感，因此這種算法會認為一個用戶對所有產品都評價極高和一個用戶對所有產品都評價極低是兩個相等的向量。在Numpy中利用0.5+0.5*corrcoef（）進行計算，最后規整其值在0～1之間。使用歐氏距離公式計算產品與產品之間的相似度時，先根據公式得出距離再利用“1/（1+距離）”計算相似度，就可以得到規整的在0和1之間變換的數據，當距離為0時相似度就越大越趨近于1，當距離越遠相似度也就越趨近于0，以此簡化運算過程。

[dx，y=（x1-y1）2+（x2-y2）2+？+（xn-yn）2] （3）

根據余弦相似度[13]計算產品之間的相似性時，如果兩個向量夾角為90°則相似度為0，如果兩個向量方向相同則相似度為1，可以利用Numpy線性代數工具所提供的linalg.norm（）函數計算。

[similarity=cos（θ）A？B∥A∥∥B∥=i=1nAi×Bii=1n（Ai）2×i=1n（Bi）2] （4）

按照前k個奇異值的平方和占總奇異值平方和的百分比確定k的值，將原始的11維矩陣轉換為3維矩陣。利用相似度計算方法，實現根據產品相似度對用戶未進行評分的產品進行分值預測。對編號為1的用戶推薦評分較高的3件商品，降序排列得出的產品序號和相似度結果如圖2所示。

圖2 產品推薦及評分預測

可以使用交叉檢測方法對現有推薦引擎進行評價，將已知的原有數據刪除，對其作出新的預測，查看原有數據與預測數據之間的差異并對推薦系統進行評價。通常利用最小均方根誤差作為評價標準，通過取得均方誤差的平方根進行具體數值評價。

3 圖像壓縮

3.1 應用原理

圖像壓縮的意義是在保證圖像質量的前提下，利用更少的存儲空間保存更接近于原始圖像的圖像。這樣不僅可以壓縮圖像大小，減少存儲位數，還可以加快圖像數據傳輸速度，為人們的工作帶來很大便捷。圖像壓縮[14]的原理是，存儲的數據之間存在著大量的重復和冗余[15]，奇異值分解可以最大程度地保留原始數據并且去除重復數據[16]，以壓縮圖像大小，同時保證圖像質量。

3.2 基于SVD的手寫數字壓縮

現有32*32的手寫數字6圖像一張，利用函數遍歷其所有矩陣元素，在當前值大于閾值時打印1否則打印0，就可將原圖片轉換為0、1分布的共1 024像素大小的手寫數字灰度圖像。利用科學計算庫NumPy中的linalg將矩陣分解為k位數的U、Σ和VT，其中Σ就是將k位數的奇異值Sigma填充到全0矩陣的對角線上，U為32*k的矩陣，VT為k*32[17]的矩陣。最后利用SigRecon實現3個矩陣的點乘重組[18]，最大限度地還原了壓縮前的矩陣圖像。原始圖像與取不同Sigma值時圖像變化如圖3-圖6所示，Sigma長度個數分析如圖7所示。

圖3 原始圖像? ? ? ? ? ? ? ? ? ? ? ?圖4 Sigma=3壓縮后圖像

圖5 Sigma=5壓縮后圖像? ? ? ? ? ?圖6 Sigma=10壓縮后圖像

從數據中可以看出，隨著Sigma值的不斷增加，壓縮后圖像的還原度也越來越高。一般只要保留矩陣80%～90%的能量，就能夠獲得到主要特征并去除無用噪聲。由此可以看出，只要有兩個奇異值就可以實現以上圖像的壓縮重組。重組后的數據由U和VT兩個均為32*2的矩陣組成，總數目是32*2+32*2+2=130個，相比原來的1 024個數字縮小了近8倍。以此類推，假設在n*n個像素的圖像中，奇異值按照從小到大的遞增順序排序，選擇k個奇異值逐漸靠近原始圖像，就可以用 k（2n+1）個像素的數值替換原有n*n個像素的圖像。壓縮比為p=n2/k（2n+1），當k滿足k

圖7 Sigma長度個數分析

4 結語

奇異值分解在圖像壓縮中可以減少圖像的內存空間，經過SVD分解后的圖像比原始圖像壓縮了近8倍，同時也可以加快圖像傳輸速度，有效提高圖像傳輸效率。其在推薦系統中也起到了很大推動作用，可縮小原有矩陣維度，去除冗余提升運算效率。但是，推薦系統還需要考慮是選取基于產品[19]還是基于用戶[20]的相似度計算比較適合，如果用戶數目較多，可以選擇基于產品的相似度計算，有利于減少工作量，這些具體實現方法需根據實際情況進行更改完善。此外，推薦引擎設計還需注意冷啟動問題[21]，可以將開始的推薦問題轉換為搜索問題[22]。例如將不同的產品賦予不同的標簽，通過推薦產品的屬性解決新用戶數據信息為零的問題，也可以將這些屬性作為相似度計算所需數據，轉換為基于內容的推薦。

SVD作為一種強大的降維和壓縮工具，可以得到數據中的重要特征并去除冗余[23]信息，很大程度上保留了原有數據結構。作為機器學習中的一種基本算法，奇異值分解在信號處理、神經網絡、水印處理、模式識別等方面也有廣泛應用，是值得推薦和深度學習的一種算法。

參考文獻：

[1] 王騰飛. 推薦系統的改進[D]. 南京：南京大學，2018.

[2] 王東. 基于用戶與物品信息挖掘的矩陣分解推薦算法研究[D].? 西安：西安電子科技大學，2017.

[3] 劉國樞. 基于局部全局相似度的奇異值分解的協同過濾算法研究[D].? 鄭州：鄭州大學，2016.

[4] 陳亞雄，黃樟燦，馮磊. 基于奇異值分解和Contourlet變換的圖像壓縮算法[J]. 計算機應用研究，2017，34（1）：317-320.

[5] 李衛疆，齊靜，余正濤，等. 融合信任傳播和奇異值分解的社會化推薦算法[J]. 計算機工程，2017，43（8）：236-242.

[6] 余剛，王知衍，邵璐，等. 基于奇異值分解的個性化評論推薦[J]. 電子科技大學學報，2015，44（4）：605-610.

[7] 黃長春，徐抒巖，胡君. 奇異值分解遙感圖像壓縮算法研究[J]. 計算機仿真，2011，28（8）：226-228，353.

[8] 徐翔，王煦法. 基于SVD的協同過濾算法的欺詐攻擊行為分析[J]. 計算機工程與應用，2009（20）：93.

[9] BOBADILLA J， ORTEGA F， HERNANDO A， et al. Recommender systems survey[J]. Knowledge-Based Systems，2013，46（1）：109-132.

[10] 張建軍，陸國生，劉征宇. 基于奇異值分解和項目屬性的推薦算法[J]. 合肥工業大學學報：自然科學版，2018，41（6）：761-765，858.

[11] 魏港明，劉真，李林峰，等. 加入用戶對項目屬性偏好的奇異值分解推薦算法[J]. 西安交通大學學報，2018，52（5）：101-107.

[12] JAMALI M，ESTER M.A matrix factorization technique with trust propagation for recommendation in social networks[C]. Proceedings of the 4th ACM Conference on Recommender Systems，2010： 135-142.

[13] 王娟，林耀進，朱月秀. 聯合奇異值分解與余弦相似性推薦的盲水印算法[J]. 小型微型計算機系統，2015，36（12）：2784-2788.

[14] RUFAI A M，ANBARJAFARI G，DEMIREL H. Lossy medical image compression using Huffman coding and singular value decomposition[C]. Proceedings of Signal Processing and Communications Applications Conference，2013： 1-4.

[15] 王懷光，張培林，張云強，等. 基于奇異值分解和小波變換的圖像壓縮算法[J]. 火炮發射與控制學報，2012（4）：38-42.

[16] KHARATE， G K， PATIL， V H. Color image compression based on wavelet packet best tree[J].? International Journal of Computer Science Issues， 2010，7（4）： 31-35.

[17] 張曉鋒，賈曉強. 基于奇異值分解的數字圖像壓縮技術研究[J]. 電子設計工程，2017，25（19）：179-182，186.

[18] 蔣卓蕓，夏雪. 奇異值分解及其簡單應用[J]. 成都大學學報：自然科學版，2015，34（4）：364-366，370.

[19] 王佳蕾，郭耀，劉志宏. 基于社交網絡信任關系的服務推薦方法[J]. 計算機科學，2018，45（S2）：402-408.

[20] 林子揚. 基于相似度建模及SVD優化的協同過濾推薦引擎研究與設計[D]. 西安：西安電子科技大學，2017.

[21] 魏琳東，黃永峰. 融合用戶屬性信息的冷啟動推薦算法[J]. 電子技術應用，2017，43（10）：137-140，144.

[22] GANTNER Z， DRUMOND L， FREUDENTHALER C， et al. Learning attribute-to-feature mappings for cold-start recommendations[C]. 2010 IEEE 10th International Conference on Data Mining （ICDM）， 2010：176-185.

[23] 吳俊政. 一種基于奇異值分解的圖像壓縮方法[J]. 計算機與數字工程，2009，37（5）：136-138.

（責任編輯：孫 娟）