SVD知識梳理

• 一、引入
• 二、SVD的定義、性質
• • 定義
  • 例題
  • 奇異值分解一定存在
  • 緊奇異值分解和截斷奇異值分解
  • • 幾何解釋
• 三、SVD算法
• • 計算過程
• 四、SVD與矩陣近似
• 五、python實現
• 六、應用

一、引入

主成分分析PCA、潛在語義分析都會用到SVD
不要求A矩陣是方陣，SVD是線性代數中相似對角化的延伸
任意mn的矩陣都可以用三個矩陣相乘的形式表示
分別是m階正交矩陣、由降序排列的非負的對角線元素構成的mn矩形對角矩陣、n階正交矩陣
矩陣奇異值分解一定存在但不唯一
SVD可以看作矩陣壓縮數據的一種方法，這種近似是在平方損失意義下的最優近似

二、SVD的定義、性質

定義

A=UΣV^T
滿足以下條件
UU^T=E;
VV^T=E;
Σ=diag(σ₁,σ₂,…σ_p),其中σ₁>=σ₂>=…>=σ_p>=0；p=min{m,n}

例題

奇異值分解一定存在

設定m>=n,分三步完成證明
1、確定v和Σ
①Σ
A^TA的特征值都是非負的||Ax||²=x^TA^TAx=λx^Tx=λ||x||²
所以λ=|Ax||²/||x||²>=0
假設正交矩陣V的列的排列使對應的特征值降序排列：λ₁>=λ₂>=λ₃>=…>=λ_n
計算矩陣A的奇異值σ_j=√λj, j=12,…n
說明：A^TA的特征值與A的特征值是平方關系
A^TA=(UΣV^T)^T(UΣV^T)=V(Σ^TΣ)V^T;
AA^T=(UΣV^T)(UΣV^T)^T=U(ΣΣ^T)U^T;
V的列向量是A^TA的特征向量，U的列向量是AA^T的特征向量，Σ的奇異值是A^TA和AA^T的特征值的平方根，A^TA和AA^T的特征值相同

R(A)=r,R(A^TA)=r,由于A^TA是對稱矩陣，它的秩等于正的特征值的個數
所以剩下的n-r個特征值為0。所以σ同理

Σ= ②v
V₁=[v₁,v₂,…v_r];V₂=[v_r+1,…v_n]
其中V₁對應的是A^TA的正特征值對用的特征向量， 其中V₂對應的是A^TA的0特征值對用的特征向量V=[V₁,V₂]
V₂
A^TAx=0(V₂的列向量構成了A^TA的零空間N(A^TA)=N(A),所以V₂的列向量構成A的零空間的一組標準正交基)
Ax=0（正交矩陣的轉置乘以正交矩陣等于單位矩陣）
③U
u_j=1/σ_jAv_j,j=1,2…r
U₁=[u₁,u₂,…u_r]
則AV₁=U₁Σ₁
U₂與V~2同理

緊奇異值分解和截斷奇異值分解

緊奇異值分解（無損壓縮，與原始矩陣秩相同）
截斷奇異值分解（有損壓縮，小于原始矩陣的秩）：滿足了秩的要求以后其余元素都變成零

幾何解釋

被分成的三個矩陣可以解釋為，一個坐標軸的旋轉或反射變換、一個坐標軸的縮放變換、另一個坐標軸的旋轉或反射變換。

三、SVD算法

計算過程

①計算A^TA的特征值和特征向量，特征值開方從大到小排序即為Σ
注意：因為A不是方陣，所以在構造的時候，要將格式修改為m*n的形式，缺的位置補零。
②求n階正交矩陣V:特征向量單位化
③求m階正交矩陣U:
u_j=1/σ_jAv_j (j=1,2,3…,r) U₁=[u₁,u₂,u₃,…u_r]
求A^T的零空間的一組標準正交基{u_r+1,u_r+2,…u_m}
（A^Tx=0,求出特征向量以后記得標準化）
U=[U₁,U₂]
④得到奇異值分解

四、SVD與矩陣近似

弗羅貝尼烏斯范數：是向量L₂范數的直接推廣，對應機器學習中的平方損失函數

矩陣的外積展開式

若A的秩為n，A_k的秩為k, 且A_k是秩為k的矩陣中在弗羅貝尼烏斯范數意義下A的最優近似矩陣。那么A_k就是A的截斷奇異值分解。
通常奇異值σ_i遞減的很快，所以k取很小值時，A_K也可以對A有很好的近似。

五、python實現

import numpy as np a = np.random.randint(-10,10,(4, 3)).astype(float) print(a) print("-----------------") u, sigma, vT = np.linalg.svd(a) print(u) print("-----------------") print(sigma) print("-----------------") print(vT) print("-----------------")# 將sigma 轉成矩陣 SigmaMat = np.zeros((4,3)) SigmaMat[:3, :3] = np.diag(sigma) print(SigmaMat) print("------驗證-------") a_ = np.dot(u, np.dot(SigmaMat, vT)) print(a_)

六、應用

推薦算法

import numpy as npimport randomclass SVD:def __init__(self,mat,K=20):self.mat=np.array(mat)self.K=Kself.bi={}self.bu={}self.qi={}self.pu={}self.avg=np.mean(self.mat[:,2])for i in range(self.mat.shape[0]):uid=self.mat[i,0]iid=self.mat[i,1]self.bi.setdefault(iid,0)self.bu.setdefault(uid,0)self.qi.setdefault(iid,np.random.random((self.K,1))/10*np.sqrt(self.K))self.pu.setdefault(uid,np.random.random((self.K,1))/10*np.sqrt(self.K)) def predict(self,uid,iid): #預測評分的函數#setdefault的作用是當該用戶或者物品未出現過時，新建它的bi,bu,qi,pu，并設置初始值為0self.bi.setdefault(iid,0)self.bu.setdefault(uid,0)self.qi.setdefault(iid,np.zeros((self.K,1)))self.pu.setdefault(uid,np.zeros((self.K,1)))rating=self.avg+self.bi[iid]+self.bu[uid]+np.sum(self.qi[iid]*self.pu[uid]) #預測評分公式#由于評分范圍在1到5，所以當分數大于5或小于1時，返回5,1.if rating>5:rating=5if rating<1:rating=1return ratingdef train(self,steps=30,gamma=0.04,Lambda=0.15): #訓練函數，step為迭代次數。print('train data size',self.mat.shape)for step in range(steps):print('step',step+1,'is running')KK=np.random.permutation(self.mat.shape[0]) #隨機梯度下降算法，kk為對矩陣進行隨機洗牌rmse=0.0for i in range(self.mat.shape[0]):j=KK[i]uid=self.mat[j,0]iid=self.mat[j,1]rating=self.mat[j,2]eui=rating-self.predict(uid, iid)rmse+=eui**2self.bu[uid]+=gamma*(eui-Lambda*self.bu[uid]) self.bi[iid]+=gamma*(eui-Lambda*self.bi[iid])tmp=self.qi[iid]self.qi[iid]+=gamma*(eui*self.pu[uid]-Lambda*self.qi[iid])self.pu[uid]+=gamma*(eui*tmp-Lambda*self.pu[uid])gamma=0.93*gammaprint('rmse is',np.sqrt(rmse/self.mat.shape[0]))def test(self,test_data): #gamma以0.93的學習率遞減test_data=np.array(test_data)print('test data size',test_data.shape)rmse=0.0for i in range(test_data.shape[0]):uid=test_data[i,0]iid=test_data[i,1]rating=test_data[i,2]eui=rating-self.predict(uid, iid)rmse+=eui**2print('rmse of test data is',np.sqrt(rmse/test_data.shape[0]))def getData(): #獲取訓練集和測試集的函數import ref=open('C:/Users/xuwei/Desktop/data.txt','r')lines=f.readlines()f.close()data=[] for line in lines:list=re.split('\t|\n',line)if int(list[2]) !=0: #提出評分0的數據，這部分是用戶評論了但是沒有評分的data.append([int(i) for i in list[:3]])random.shuffle(data)train_data=data[:int(len(data)*7/10)]test_data=data[int(len(data)*7/10):]print('load data finished')print('total data ',len(data)) return train_data,test_datatrain_data,test_data=getData() a=SVD(train_data,30) a.train() a.test(test_data)

代碼鏈接：https://blog.csdn.net/akiyamamio11/article/details/79042688

總結

以上是生活随笔為你收集整理的奇异值分解SVD（证明全部省略）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。