陳卉妍 張仁龍

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

關(guān)鍵詞：奇異值分解;推薦引擎;壓縮圖像;相似度計算;數(shù)據(jù)降維

DOI：10. 11907/rjdk. 191802 開放科學(xué)（資源服務(wù)）標識碼（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-），女，北京農(nóng)學(xué)院計算機與信息工程學(xué)院碩士研究生，研究方向為數(shù)據(jù)分析; 張仁龍（1967-），男，北京農(nóng)學(xué)院計算機與信息工程學(xué)院教授、碩士生導(dǎo)師，研究方向為程序設(shè)計。

0 引言

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

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

1 奇異值分解原理

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

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

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

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

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

圖1 深灰色為計算需要數(shù)據(jù)

2 推薦引擎

2.1 應(yīng)用原理

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

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

2.2 基于SVD的推薦引擎

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

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

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

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

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

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

圖2 產(chǎn)品推薦及評分預(yù)測

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

3 圖像壓縮

3.1 應(yīng)用原理

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

3.2 基于SVD的手寫數(shù)字壓縮

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

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

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

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

圖7 Sigma長度個數(shù)分析

4 結(jié)語

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

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

參考文獻：

[1] 王騰飛. 推薦系統(tǒng)的改進[D]. 南京：南京大學(xué)，2018.

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

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

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

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

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

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

[8] 徐翔，王煦法. 基于SVD的協(xié)同過濾算法的欺詐攻擊行為分析[J]. 計算機工程與應(yīng)用，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]. 合肥工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2018，41（6）：761-765，858.

[11] 魏港明，劉真，李林峰，等. 加入用戶對項目屬性偏好的奇異值分解推薦算法[J]. 西安交通大學(xué)學(xué)報，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] 王娟，林耀進，朱月秀. 聯(lián)合奇異值分解與余弦相似性推薦的盲水印算法[J]. 小型微型計算機系統(tǒng)，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]. 火炮發(fā)射與控制學(xué)報，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] 張曉鋒，賈曉強. 基于奇異值分解的數(shù)字圖像壓縮技術(shù)研究[J]. 電子設(shè)計工程，2017，25（19）：179-182，186.

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

[19] 王佳蕾，郭耀，劉志宏. 基于社交網(wǎng)絡(luò)信任關(guān)系的服務(wù)推薦方法[J]. 計算機科學(xué)，2018，45（S2）：402-408.

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

[21] 魏琳東，黃永峰. 融合用戶屬性信息的冷啟動推薦算法[J]. 電子技術(shù)應(yīng)用，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]. 計算機與數(shù)字工程，2009，37（5）：136-138.

（責(zé)任編輯：孫 娟）