基于奇異值分解的簡(jiǎn)化數(shù)據(jù)應(yīng)用

陳卉妍 張仁龍

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

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

DOI：10. 11907/rjdk. 191802 開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

中圖分類號(hào)：TP392文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

作者簡(jiǎn)介：陳卉妍（1996-），女，北京農(nóng)學(xué)院計(jì)算機(jī)與信息工程學(xué)院碩士研究生，研究方向?yàn)閿?shù)據(jù)分析; 張仁龍（1967-），男，北京農(nóng)學(xué)院計(jì)算機(jī)與信息工程學(xué)院教授、碩士生導(dǎo)師，研究方向?yàn)槌绦蛟O(shè)計(jì)。

0 引言

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

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

1 奇異值分解原理

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

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

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

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

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

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

2 推薦引擎

2.1 應(yīng)用原理

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

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

2.2 基于SVD的推薦引擎

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

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

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

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

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

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

圖2 產(chǎn)品推薦及評(píng)分預(yù)測(cè)

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

3 圖像壓縮

3.1 應(yīng)用原理

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

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

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

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

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

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

圖7 Sigma長(zhǎng)度個(gè)數(shù)分析

4 結(jié)語(yǔ)

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

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

[8] 徐翔，王煦法. 基于SVD的協(xié)同過濾算法的欺詐攻擊行為分析[J]. 計(jì)算機(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] 張建軍，陸國(guó)生，劉征宇. 基于奇異值分解和項(xiàng)目屬性的推薦算法[J]. 合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2018，41（6）：761-765，858.

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

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

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

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

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

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