【机器学习】这次终于彻底理解了奇异值分解(SVD)原理及应用
奇異值分解(Singular Value Decomposition，以下簡稱SVD)是在機器學習領域廣泛應用的算法，有相當多的應用與奇異值都可以扯上關系，它不光可以用于降維算法中的特征分解，比如做feature reduction的PCA，做數據壓縮（以圖像壓縮為代表）的算法還可以用于推薦系統。以及自然語言處理等領域，如做搜索引擎語義層次檢索的LSI（Latent Semantic Indexing）。本文就對SVD的原理做一個總結。
特征值分解(EVD）
在開始學習奇異值分解（SVD）分解之前，先學習下特征值分解（EVD）。當然，理解SVD之前，還是需要一些基礎知識儲備，如果你對如下基礎知識基本了解，可以跳過本節內容。
方陣
方塊矩陣，也稱方陣、方矩陣或正方矩陣，是行數及列數皆相同的矩陣。由 矩陣組成的集合，連同矩陣加法和矩陣乘法，構成環。除了 ，此環并不是交換環。
單位矩陣
的對角線全是1而其他位置全是0，對所有 矩陣 及 矩陣 都有 及 。例如，若 ：
單位矩陣是方塊矩陣環的單位元。
方塊矩陣環的可逆元稱為可逆矩陣或非奇異方陣。矩陣 是可逆當且僅當存在矩陣 使得
此時 稱為 的逆矩陣，并記作 。
特征向量與特征值
線性代數中對特征值和特征向量的定義：
設 是 階方陣，如果存在 和 維非零向量 ，使 ，則 稱為方陣 的一個特征值， 為方陣 對應于或屬于特征值 的一個特征向量。
從定義可以看出，對特征向量 進行 變換的實質是將特征向量進行縮放，縮放因子為特征值 。
比如說下面的一個矩陣：
它其實對應的線性變換是下面的形式：
上面的矩陣是對稱的，所以這個變換是一個對x，y軸的方向一個拉伸變換（每一個對角線上的元素將會對一個維度進行拉伸變換，當值>1時，是拉長，當值<1時時縮短）。
因此，特征向量的代數上含義是：
將矩陣乘法轉換為數乘操作；
特征向量的幾何含義是：
特征向量通過方陣 變換只進行伸縮，而保持特征向量的方向不變。
特征值分解可以得到特征值與特征向量，特征值表示的是這個特征到底有多重要，而特征向量表示這個特征是什么，可以將每一個特征向量理解為一個線性的子空間，我們可以利用這些線性的子空間干很多的事情。
不過，特征值分解也有很多的局限，比如說變換的矩陣必須是方陣。
矩陣分解
現有特征值和特征向量：
其中 是一個 的實對稱矩陣， 是一個 維向量， 是矩陣 的一個特征值，而 是矩陣 的特征值 所對應的特征向量。
通過求解齊次方程來計算矩陣 的特征值及特征向量：
求出特征值和特征向量就可以將矩陣 特征分解。如果求出了矩陣 的 個特征值 λλλ，以及這 個特征值所對應的特征向量 ，，如果這 個特征向量線性無關，那么矩陣 就可以用下式的特征分解表示：
其中 是這 個特征向量所張成的 維矩陣，而 為這 個特征值為主對角線的 維矩陣。
一般我們會把 的這 個特征向量標準化，即滿足 ，或者說 ，此時 的 個特征向量為標準正交基，滿足 ，即 也就是說 為酉矩陣。
這樣特征分解表達式可以寫成：
矩陣 分解了，相應的，其對應的映射也分解為三個映射。現在假設有 向量，用 Ａ 將其變換到 Ａ 的列空間中，那么首先由 先對 做變換。
這個假設是向量 原來的坐標， 那么經過第一個變換之后， 就可以把向量 變成 。
緊接著，在新的坐標系表示下，由中間那個對角矩陣對新的向量坐標換，其結果就是將向量往各個軸方向拉伸或壓縮：
從上圖可以看到，如果 不是滿秩的話，那么就是說對角陣的對角線上元素存在0，這時候就會導致維度退化， 這樣就可以降維了看沒看到，這樣就會使映射后的向量落入 維空間的子空間中。
最后一個變換就是 對拉伸或壓縮后的向量做變換，由于 和 是互為逆矩陣，所以 變換是 變換的逆變換。
因此，從對稱陣的分解對應的映射分解來分析一個矩陣的變換特點是非常直觀的。假設對稱陣特征值全為1那么顯然它就是單位陣，如果對稱陣的特征值有個別是0其他全是1，那么它就是一個正交投影矩陣，它將 維向量投影到它的列空間中。
注意到要進行特征分解，矩陣 必須為方陣。那么如果 不是方陣，即行和列不相同時，此時需要借助SVD對矩陣進行分解。
奇異值分解(SVD)
本節進入我們的正題奇異值分解（SVD）。
奇異值
特征值及特征值分解都是針對方陣而言，現實世界中，我們看到的大部分矩陣不是方陣，比如每道數據有 個點，一共采集了 道數據，這樣就形成了一個 的矩陣，那么怎樣才能像方陣一樣提取出它的特征，以及特征的重要性。
奇異值分解就是來干這個事情的。奇異值相當于方陣中的特征值，奇異值分解相當于方陣中的特征值分解。
假設 是一個 的矩陣，那么得到的 是一個 的方陣（里面的向量是正交的， 里面的向量稱為左奇異向量）， 是一個 的矩陣（除了對角線的元素都是0，對角線上的元素稱為奇異值）， 是一個 的矩陣，里面的向量也是正交的， 里面的向量稱為右奇異向量）。
那么奇異值和特征值是怎么對應起來的呢？首先，我們將一個矩陣 的轉置 ，將會得到一個方陣，我們用這個方陣求特征值可以得到：
這里得到的 ，就是我們上面的右奇異向量。此外我們還可以得到：
這里的 就是上面說的奇異值， 就是上面說的左奇異向量。奇異值 跟特征值類似，在矩陣 中也是從大到小排列，而且 的減少特別的快，在很多情況下，前10%甚至1%的奇異值的和就占了全部的奇異值之和的99%以上了。也就是說，我們也可以用前 大的奇異值來近似描述矩陣，這里定義一下部分奇異值分解：
右邊的三個矩陣相乘的結果將會是一個接近于 的矩陣，在這兒， 越接近于 ，則相乘的結果越接近于 。而這三個矩陣的面積之和（在存儲觀點來說，矩陣面積越小，存儲量就越小）要遠遠小于原始的矩陣 ，我們如果想要壓縮空間來表示原矩陣 ，我們存下這里的三個矩陣：、、 就好了。
SVD 算法的原理推導
SVD也是對矩陣進行分解，但是和特征分解不同，SVD并不要求要分解的矩陣為方陣，是一種適用于任意矩陣的分解方法。假設我們的矩陣 是一個 的矩陣，那么我們定義矩陣 的SVD為：
其中 是一個 的矩陣， 是一個 的矩陣，除了主對角線上的元素以外全為0，主對角線上的每個元素都稱為奇異值， 是一個 的矩陣。 和 都是酉矩陣，即滿足 ，， 為單位矩陣。
下圖可以很形象的看出上面SVD的定義：
那么我們如何求出SVD分解后的 這三個矩陣呢？
如果我們將 的轉置和 做矩陣乘法，那么會得到 的一個方陣 。既然 是方陣，那么我們就可以進行特征分解，得到的特征值和特征向量滿足下式：
λ
這樣我們就可以得到矩陣 的 個特征值和對應的 個特征向量 了。將 的所有特征向量張成一個 的矩陣 ，就是我們SVD公式里面的V矩陣了。一般我們將 中的每個特征向量叫做 的右奇異向量。
如果我們將 和 的轉置做矩陣乘法，那么會得到 的一個方陣 。既然 是方陣，那么我們就可以進行特征分解，得到的特征值和特征向量滿足下式：
這樣我們就可以得到矩陣 的 個特征值和對應的 個特征向量 了。將 的所有特征向量張成一個 的矩陣 ，就是我們SVD公式里面的 矩陣了。一般我們將 中的每個特征向量叫做 的左奇異向量。
和 我們都求出來了，現在就剩下奇異值矩陣 沒有求出了。由于 除了對角線上是奇異值其他位置都是0，那我們只需要求出每個奇異值 就可以了。
我們注意到:
這樣我們可以求出我們的每個奇異值，進而求出奇異值矩陣 。
上面還有一個問題沒有講，就是我們說 的特征向量組成的就是我們SVD中的 矩陣，而 的特征向量組成的就是我們SVD中的 矩陣，這有什么根據嗎？這個其實很容易證明，我們以 矩陣的證明為例。
上式證明使用了：。可以看出 的特征向量組成的的確就是我們SVD中的V矩陣。類似的方法可以得到 的特征向量組成的就是我們SVD中的 矩陣。
進一步我們還可以看出我們的特征值矩陣等于奇異值矩陣的平方，也就是說特征值和奇異值滿足如下關系：
這樣也就是說，我們可以不用 來計算奇異值，也可以通過求出 的特征值取平方根來求奇異值。
這里我們用一個簡單的例子來說明矩陣是如何進行奇異值分解的。我們的矩陣A定義為：
SVD計算舉例
我們首先求出 和
進而求出 的特征值和特征向量：
接著求 的特征值和特征向量：
利用 求奇異值：
當然，我們也可以用 直接求出奇異值為 和 1.
最終得到 的奇異值分解為：
特征分解和奇異值分解的區別
特征值分解和奇異值分解的目的都是一樣，就是提取出一個矩陣最重要的特征。
所有的矩陣都可以進行奇異值分解，但只有方陣才可以進行特征值分解。當所給的矩陣是對稱的方陣，，二者的結果是相同的。也就是說對稱矩陣的特征值分解是所有奇異值分解的一個特例。但是二者還是存在一些小的差異，奇異值分解需要對奇異值進行從大到小的排序，而且全部是大于等于零。
對于如上的奇異值分解公式，我們可以看到奇異值分解同時包含了旋轉，縮放和投影三種作用，并且 和 都起到了對 進行旋轉的作用，而 起到了對 縮放的作用，特征值分解只有縮放的效果。
在應用上，奇異值分解主要用于數據矩陣，而特征值分解主要用于方型的相關矩陣。
SVD的性質
上面幾節我們對SVD的定義和計算做了詳細的描述，似乎看不出我們費這么大的力氣做SVD有什么好處。那么SVD有什么重要的性質值得我們注意呢？
對于奇異值，它跟我們特征分解中的特征值類似，在奇異值矩陣中也是按照從大到小排列，而且奇異值的減少特別的快，在很多情況下，前10%甚至1%的奇異值的和就占了全部的奇異值之和的99%以上的比例。也就是說，我們也可以用最大的k個的奇異值和對應的左右奇異向量來近似描述矩陣。也就是說：
其中 要比 小很多，也就是一個大的矩陣A可以用三個小的矩陣 來表示。如下圖所示，現在我們的矩陣 只需要灰色的部分的三個小矩陣就可以近似描述了。
由于這個重要的性質，SVD可以用于PCA降維，來做數據壓縮和去噪。也可以用于推薦算法，將用戶和喜好對應的矩陣做特征分解，進而得到隱含的用戶需求來做推薦。同時也可以用于NLP中的算法，比如潛在語義索引（LSI）。
SVD的應用
PCA降維中的應用
下面我們就對SVD用于PCA降維做一個介紹。
在主成分分析（PCA）原理總結中，我們講到要用PCA降維，需要找到樣本協方差矩陣 的最大的 個特征向量，然后用這最大的d個特征向量張成的矩陣來做低維投影降維。可以看出，在這個過程中需要先求出協方差矩陣 ，當樣本數多樣本特征數也多的時候，這個計算量是很大的。
注意到我們的SVD也可以得到協方差矩陣 最大的 個特征向量張成的矩陣，但是SVD有個好處，有一些SVD的實現算法可以不求先求出協方差矩陣 ，也能求出我們的右奇異矩陣 。也就是說，我們的PCA算法可以不用做特征分解，而是做SVD來完成。這個方法在樣本量很大的時候很有效。實際上，scikit-learn的PCA算法的背后真正的實現就是用的SVD，而不是我們我們認為的暴力特征分解。
另一方面，注意到PCA僅僅使用了我們SVD的右奇異矩陣，沒有使用左奇異矩陣，那么左奇異矩陣有什么用呢？
假設我們的樣本是 的矩陣 ，如果我們通過SVD找到了矩陣 最大的 個特征向量張成的 維矩陣 ，則我們如果進行如下處理：
可以得到一個 的矩陣 ，這個矩陣和我們原來的 維樣本矩陣X相比，行數從 減到了 ，可見對行數進行了壓縮。也就是說，左奇異矩陣可以用于行數的壓縮。相對的，右奇異矩陣可以用于列數即特征維度的壓縮，也就是我們的PCA降維。
SVD作為一個很基本的算法，在很多機器學習算法中都有它的身影，特別是在現在的大數據時代，由于SVD可以實現并行化，因此更是大展身手。SVD的原理不難，只要有基本的線性代數知識就可以理解，實現也很簡單因此值得仔細的研究。當然，SVD的缺點是分解出的矩陣解釋性往往不強，有點黑盒子的味道，不過這不影響它的使用。
數據壓縮的應用
奇異值分解可用于有效地表示數據。例如，假設我們希望傳輸以下圖像，該圖像由 個黑色或白色像素的陣列組成。
由于該圖像中只有三種類型的列，如下所示，應該可以用更緊湊的形式表示數據。我們將圖像表示為一個 矩陣，其中每個條目要么是 0，代表黑色像素，要么是 1，代表白色。因此，矩陣中有 375 個條目。
如果我們對 執行奇異值分解，我們會發現只有三個非零奇異值。
σσσ
因此，矩陣可以表示為
σσσ
此時有三個向量 ，每個向量有 15 個條目，三個向量 ，每個向量有 25 個條目，以及三個奇異值 σ。這時我們可以僅使用 123 個數字而不是出現在矩陣中的 375 個數字來表示矩陣。通過這種方式，奇異值分解刪除了矩陣中的冗余，并提供了一種消除冗余后的格式。
為什么只有三個非零奇異值？請記住，非零奇異值的數量等于矩陣的秩。在這種情況下，我們看到矩陣中有三個線性獨立的列，這意味著秩將為 3。
降噪的應用(noise reduction)
前面例子的奇異值都不為零，或者都還算比較大，下面我們來探索一下擁有零或者非常小的奇異值的情況。通常來講，大的奇異值對應的部分會包含更多的信息。比如，我們有一張掃描，帶有噪聲的圖像，如下圖所示
我們可以以同樣的方式進行：使用 矩陣表示數據并執行奇異值分解。我們找到以下奇異值：
σσσσσσ
顯然，前三個奇異值是最重要的，因此我們假設其他奇異值是由于圖像中的噪聲并進行近似
σσσ
這導致以下改進的圖像。
數據分析中的應用
每當我們收集數據時，噪音也會出現：無論儀器有多好，測量中總會有一些誤差。如果我們還記得大奇異值指向矩陣中的重要特征這一主題，那么一旦收集到數據，使用奇異值分解來研究數據似乎很自然。
例如，假設我們收集一些數據，如下所示：
我們可以將數據放入矩陣中：
| -2.23 | 1.61 | -0.02 | 0.88 | -2.39 | 2.02 | 1.62 | -0.35 | -1.67 | 2.46 |
并執行奇異值分解。我們找到奇異值
σσ
由于一個奇異值比另一個大得多，可以安全地假設 σ 的小值是由于數據中的噪聲，并且這個奇異值理想地為零。在這種情況下，矩陣的秩為 1 意味著所有數據都位于 定義的線上。
這個簡短的例子是屬于主成分分析的領域，這是一組使用奇異值來檢測數據中的依賴性和冗余性的技術。
以類似的方式，奇異值分解可用于檢測數據中的分組，這解釋了為什么奇異值分解被用于嘗試改進 Netflix 的電影推薦系統。你觀看過的電影的評分允許程序將你分類為與你的評分相似的其他人。可以通過選擇你小組中其他人評價很高的電影來提出建議。
在圖像壓縮中的應用
一個圖像矩陣，我們總可以將它分解為以下形式，通過選取不同個數的 Σ 中的奇異值，就可以實現圖像的壓縮：
如果只想實現圖像壓縮，我們可以使用python numpy 庫中的 linalg.svd 對圖像矩陣進行分解，進而提取前K個奇異值便能實現SVD圖像壓縮的效果，下面我們看一下代碼:
#_*_?coding:utf-8_*_ import?numpy?as?np import?cv2img?=?cv2.imread('harden.jpg') print('origin?image?shape?is?',?img.shape) #?表示?RGB?中各有一個矩陣，都為300*532 #??origin?image?shape?is??(300,?532,?3)def?svd_compression(img,?k):res_image?=?np.zeros_like(img)for?i?in?range(img.shape[2]):#?進行奇異值分解,?從svd函數中得到的奇異值sigma?是從大到小排列的U,?Sigma,?VT?=?np.linalg.svd(img[:,:,i])res_image[:,?:,?i]?=?U[:,:k].dot(np.diag(Sigma[:k])).dot(VT[:k,:])return?res_image#?保留前?k?個奇異值 res1?=?svd_compression(img,?k=300) res2?=?svd_compression(img,?k=200) res3?=?svd_compression(img,?k=100) res4?=?svd_compression(img,?k=50)row11?=?np.hstack((res1,?res2)) row22?=?np.hstack((res3,?res4)) res?=?np.vstack((row11,?row22))cv2.imshow('img',?res) cv2.waitKey(0) cv2.destroyAllWindows()我們這里分別提取了前300， 200， 100， 50 的奇異值，圖如下：
可以看到，當我們取到前面300個奇異值來重構圖片時，基本與原圖看不出來差別，甚至兩百的都是都還OK。
所以從上面的壓縮結果來看，奇異值可以被看作是一個矩陣的代表值，或者說奇異值能夠代表這個矩陣的信息，當奇異值越大時，它代表的信息越多。因此我們取前面若干個最大的奇異值，就可以基本還原出數據本身。
Numpy實現SVD
在Python中的Numpy模塊中，已經實現了矩陣的奇異值分解。以下為示例的應用代碼：
import?numpy?as?np #generate?a?random?3*4?matrix? A?=??np.random.randint(5,?size=(3,?4)) #parameter?full_matrices:?control?the?size?of?P?and?Q #d?returns?as?numpy.ndarray,?not?matrix? P,d,Q?=?np.linalg.svd(A,?full_matrices=True) print('A:',A) print('P:',P) #D?return?as?diagonal?3*4?matrix D?=?np.zeros(12).reshape(3,4) for?i?in?range(len(d)):D[i][i]?=?d[i] print('D:',D) print('Q:',Q) #check?if?P*D*Q?==?A print('P*D*Q:',np.dot(P,np.dot(D,Q)))A: [[4 1 0 1][2 1 4 4][3 1 1 0]] P: [[-0.47560601 0.6510767 0.59152181][-0.79274458 -0.60868324 0.03256919][-0.38125445 0.45343561 -0.80563093]] D: [[7.07739778 0. 0. 0. ][0. 3.8600754 0. 0. ][0. 0. 1.00511622 0. ]] Q: [[-0.65443214 -0.23308073 -0.50191227 -0.51524366][ 0.71170815 0.12845062 -0.51327944 -0.46207809][ 0.01425989 -0.18061586 -0.67191651 0.71812448][ 0.25492496 -0.94686415 0.18208926 -0.0728357 ]] P*D*Q: [[4.00000000e+00 1.00000000e+00 1.11355742e-15 1.00000000e+00][2.00000000e+00 1.00000000e+00 4.00000000e+00 4.00000000e+00][3.00000000e+00 1.00000000e+00 1.00000000e+00 1.03872001e-15]]參考資料
[1]
https://www.cnblogs.com/pinard/p/6251584.html
[2]https://blog.csdn.net/qq_36653505/article/details/82052593
[3]http://www.ams.org/publicoutreach/feature-column/fcarc-svd
[4]https://blog.csdn.net/shenziheng1/article/details/52916278
往期精彩回顧適合初學者入門人工智能的路線及資料下載(圖文+視頻)機器學習入門系列下載中國大學慕課《機器學習》（黃海廣主講）機器學習及深度學習筆記等資料打印《統計學習方法》的代碼復現專輯 AI基礎下載機器學習交流qq群955171419，加入微信群請掃碼：總結
以上是生活随笔為你收集整理的【机器学习】这次终于彻底理解了奇异值分解(SVD)原理及应用的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： js 对象的深拷贝
- 下一篇： 扫一扫闪退的可能性之一[wex5开发]