【機器學習實戰】第14章 利用SVD簡化數據

（公式沒顯示是因為需要載入：<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=default"></script> ）

SVD 概述

奇異值分解（SVD, Singular Value Decomposition）: 提取信息的一種方法，可以把 SVD 看成是從雜訊數據中抽取相關特徵。從生物信息學到金融學，SVD 是提取信息的強大工具。

SVD 場景

信息檢索-隱形語義檢索（Lstent Semantic Indexing, LSI）或 隱形語義分析（Latent Semantic Analysis, LSA）

隱性語義索引：矩陣 = 文檔 + 詞語

• 是最早的 SVD 應用之一，我們稱利用 SVD 的方法為隱性語義索引（LSI）或隱性語義分析（LSA）。

推薦系統

1. 利用 SVD 從數據中構建一個主題空間。
2. 再在該空間下計算其相似度。(從高維-低維空間的轉化，在低維空間來計算相似度，SVD 提升了推薦系統的效率。)

• 上圖右邊標註的為一組共同特徵，表示美式 BBQ 空間；另一組在上圖右邊未標註的為日式食品 空間。

圖像壓縮

例如：32*32=1024 => 32*2+2*1+32*2=130(2*1表示去掉了除對角線的0), 幾乎獲得了10倍的壓縮比。

SVD 原理

SVD 工作原理

矩陣分解

• 矩陣分解是將數據矩陣分解為多個獨立部分的過程。
• 矩陣分解可以將原始矩陣表示成新的易於處理的形式，這種新形式是兩個或多個矩陣的乘積。（類似代數中的因數分解）
• 舉例：如何將12分解成兩個數的乘積？（1，12）、（2，6）、（3，4）都是合理的答案。

SVD 是矩陣分解的一種類型，也是矩陣分解最常見的技術

• SVD 將原始的數據集矩陣 Data 分解成三個矩陣 U、∑、V
• 舉例：如果原始矩陣 (Data_{m*n}) 是m行n列，
• (U_{m*n}) 表示m行n列
• (∑_{m*k}) 表示m行k列
• (V_{k*n}) 表示k行n列。

(Data_{m*n} = U_{m*k} * ∑_{k*k} * V_{k*n})

具體的案例：（大家可以試著推導一下：https://wenku.baidu.com/view/b7641217866fb84ae45c8d17.html ）

• 上述分解中會構建出一個矩陣∑，該矩陣只有對角元素，其他元素均為0(近似於0)。另一個慣例就是，∑的對角元素是從大到小排列的。這些對角元素稱為奇異值。
• 奇異值與特徵值(PCA 數據中重要特徵)是有關係的。這裡的奇異值就是矩陣 (Data * Data^T) 特徵值的平方根。
• 普遍的事實：在某個奇異值的數目(r 個=>奇異值的平方和累加到總值的90%以上)之後，其他的奇異值都置為0(近似於0)。這意味著數據集中僅有 r 個重要特徵，而其餘特徵則都是雜訊或冗餘特徵。

SVD 演算法特點

優點：簡化數據，去除雜訊，優化演算法的結果缺點：數據的轉換可能難以理解使用的數據類型：數值型數據

推薦系統

推薦系統 概述

推薦系統是利用電子商務網站向客戶提供商品信息和建議，幫助用戶決定應該購買什麼產品，模擬銷售人員幫助客戶完成購買過程。

推薦系統 場景

1. Amazon 會根據顧客的購買歷史向他們推薦物品
2. Netflix 會向其用戶推薦電影
3. 新聞網站會對用戶推薦新聞頻道

推薦系統 要點

基於協同過濾(collaborative filtering) 的推薦引擎

• 利用Python 實現 SVD(Numpy 有一個稱為 linalg 的線性代數工具箱)
• 協同過濾：是通過將用戶和其他用戶的數據進行對比來實現推薦的。
• 當知道了兩個用戶或兩個物品之間的相似度，我們就可以利用已有的數據來預測未知用戶的喜好。

基於物品的相似度和基於用戶的相似度：物品比較少則選擇物品相似度，用戶比較少則選擇用戶相似度。【矩陣還是小一點好計算】

• 基於物品的相似度：計算物品之間的距離。【耗時會隨物品數量的增加而增加】
• 由於物品A和物品C ?相似度(相關度)很高，所以給買A的人推薦C。

• 基於用戶的相似度：計算用戶之間的距離。【耗時會隨用戶數量的增加而增加】
• 由於用戶A和用戶C ?相似度(相關度)很高，所以A和C是興趣相投的人，?對於C買的物品就會推薦給A。

相似度計算

• inA, inB 對應的是 列向量

1. 歐氏距離：指在m維空間中兩個點之間的真實距離，或者向量的自然長度（即改點到原點的距離）。二維或三維中的歐氏距離就是兩點之間的實際距離。

• 相似度= 1/(1+歐式距離)
• 相似度= 1.0/(1.0 + la.norm(inA - inB))
• 物品對越相似，它們的相似度值就越大。

1. 皮爾遜相關係數：度量的是兩個向量之間的相似度。

• 相似度= 0.5 + 0.5*corrcoef() 【皮爾遜相關係數的取值範圍從 -1 到 +1，通過函數0.5 + 0.5*corrcoef()這個函數計算，把值歸一化到0到1之間】
• 相似度= 0.5 + 0.5 * corrcoef(inA, inB, rowvar = 0)[0][1]
• 相對歐氏距離的優勢：它對用戶評級的量級並不敏感。

1. 餘弦相似度：計算的是兩個向量夾角的餘弦值。

• 餘弦值 = (A·B)/(||A||·||B||) 【餘弦值的取值範圍也在-1到+1之間】
• 相似度= 0.5 + 0.5*餘弦值
• 相似度= 0.5 + 0.5*( float(inA.T*inB) / la.norm(inA)*la.norm(inB))
• 如果夾角為90度，則相似度為0；如果兩個向量的方向相同，則相似度為1.0。

推薦系統的評價

• 採用交叉測試的方法。【拆分數據為訓練集和測試集】
• 推薦引擎評價的指標： 最小均方根誤差(Root mean squared error, RMSE)，也稱標準誤差(Standard error)，就是計算均方誤差的平均值然後取其平方根。
• 如果RMSE=1, 表示相差1個星級；如果RMSE=2.5, 表示相差2.5個星級。

推薦系統 原理

• 推薦系統的工作過程：給定一個用戶，系統會為此用戶返回N個最好的推薦菜。
• 實現流程大致如下：

1. 尋找用戶沒有評級的菜肴，即在用戶-物品矩陣中的0值。
2. 在用戶沒有評級的所有物品中，對每個物品預計一個可能的評級分數。這就是說：我們認為用戶可能會對物品的打分（這就是相似度計算的初衷）。
3. 對這些物品的評分從高到低進行排序，返回前N個物品。

項目案例: 餐館菜肴推薦系統

項目概述

假如一個人在家決定外出吃飯，但是他並不知道該到哪兒去吃飯，該點什麼菜。推薦系統可以幫他做到這兩點。

開發流程

收集 並 準備數據

def loadExData3(): # 利用SVD提高推薦效果，菜肴矩陣 """ 行：代表人 列：代表菜肴名詞 值：代表人對菜肴的評分，0表示未評分 """ return[[2, 0, 0, 4, 4, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5], [0, 0, 0, 0, 0, 0, 0, 1, 0, 4, 0], [3, 3, 4, 0, 3, 0, 0, 2, 2, 0, 0], [5, 5, 5, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 5, 0, 0, 5, 0], [4, 0, 4, 0, 0, 0, 0, 0, 0, 0, 5], [0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 4], [0, 0, 0, 0, 0, 0, 5, 0, 0, 5, 0], [0, 0, 0, 3, 0, 0, 0, 0, 4, 5, 0], [1, 1, 2, 1, 1, 2, 1, 0, 4, 5, 0]]

分析數據: 這裡不做過多的討論(當然此處可以對比不同距離之間的差別)

訓練演算法: 通過調用 recommend() 函數進行推薦

recommend() 會調用 基於物品相似度 或者是 基於SVD，得到推薦的物品評分。

• 1.基於物品相似度

# 基於物品相似度的推薦引擎def standEst(dataMat, user, simMeas, item): """standEst(計算某用戶未評分物品中，以對該物品和其他物品評分的用戶的物品相似度，然後進行綜合評分) Args: dataMat 訓練數據集 user 用戶編號 simMeas 相似度計算方法 item 未評分的物品編號 Returns: ratSimTotal/simTotal 評分（0～5之間的值） """ # 得到數據集中的物品數目 n = shape(dataMat)[1] # 初始化兩個評分值 simTotal = 0.0 ratSimTotal = 0.0 # 遍歷行中的每個物品（對用戶評過分的物品進行遍歷，並將它與其他物品進行比較） for j in range(n): userRating = dataMat[user, j] # 如果某個物品的評分值為0，則跳過這個物品 if userRating == 0: continue # 尋找兩個用戶都評級的物品 # 變數 overLap 給出的是兩個物品當中已經被評分的那個元素的索引ID # logical_and 計算x1和x2元素的真值。 overLap = nonzero(logical_and(dataMat[:, item].A > 0, dataMat[:, j].A > 0))[0] # 如果相似度為0，則兩著沒有任何重合元素，終止本次循環 if len(overLap) == 0: similarity = 0 # 如果存在重合的物品，則基於這些重合物重新計算相似度。 else: similarity = simMeas(dataMat[overLap, item], dataMat[overLap, j]) # print the %d and %d similarity is : %f(iten,j,similarity) # 相似度會不斷累加，每次計算時還考慮相似度和當前用戶評分的乘積 # similarity 用戶相似度， userRating 用戶評分 simTotal += similarity ratSimTotal += similarity * userRating if simTotal == 0: return 0 # 通過除以所有的評分總和，對上述相似度評分的乘積進行歸一化，使得最後評分在0~5之間，這些評分用來對預測值進行排序 else: return ratSimTotal/simTotal

• 2.基於SVD(參考地址：http://www.codeweblog.com/svd-%E7%AC%94%E8%AE%B0/)

# 基於SVD的評分估計# 在recommend() 中，這個函數用於替換對standEst()的調用，該函數對給定用戶給定物品構建了一個評分估計值def svdEst(dataMat, user, simMeas, item): """svdEst(計算某用戶未評分物品中，以對該物品和其他物品評分的用戶的物品相似度，然後進行綜合評分) Args: dataMat 訓練數據集 user 用戶編號 simMeas 相似度計算方法 item 未評分的物品編號 Returns: ratSimTotal/simTotal 評分（0～5之間的值） """ # 物品數目 n = shape(dataMat)[1] # 對數據集進行SVD分解 simTotal = 0.0 ratSimTotal = 0.0 # 奇異值分解 # 在SVD分解之後，我們只利用包含了90%能量值的奇異值，這些奇異值會以NumPy數組的形式得以保存 U, Sigma, VT = la.svd(dataMat) # # 分析 Sigma 的長度取值 # analyse_data(Sigma, 20) # 如果要進行矩陣運算，就必須要用這些奇異值構建出一個對角矩陣 Sig4 = mat(eye(4) * Sigma[: 4]) # 利用U矩陣將物品轉換到低維空間中，構建轉換後的物品(物品+4個主要的特徵) xformedItems = dataMat.T * U[:, :4] * Sig4.I # 對於給定的用戶，for循環在用戶對應行的元素上進行遍歷， # 這和standEst()函數中的for循環的目的一樣，只不過這裡的相似度計算時在低維空間下進行的。 for j in range(n): userRating = dataMat[user, j] if userRating == 0 or j == item: continue # 相似度的計算方法也會作為一個參數傳遞給該函數 similarity = simMeas(xformedItems[item, :].T, xformedItems[j, :].T) # for 循環中加入了一條print語句，以便了解相似度計算的進展情況。如果覺得累贅，可以去掉 print the %d and %d similarity is: %f % (item, j, similarity) # 對相似度不斷累加求和 simTotal += similarity # 對相似度及對應評分值的乘積求和 ratSimTotal += similarity * userRating if simTotal == 0: return 0 else: # 計算估計評分 return ratSimTotal/simTotal

排序獲取最後的推薦結果

# recommend()函數，就是推薦引擎，它默認調用standEst()函數，產生了最高的N個推薦結果。# 如果不指定N的大小，則默認值為3。該函數另外的參數還包括相似度計算方法和估計方法def recommend(dataMat, user, N=3, simMeas=cosSim, estMethod=standEst): # 尋找未評級的物品 # 對給定的用戶建立一個未評分的物品列表 unratedItems = nonzero(dataMat[user, :].A == 0)[1] # 如果不存在未評分物品，那麼就退出函數 if len(unratedItems) == 0: return you rated everything # 物品的編號和評分值 itemScores = [] # 在未評分物品上進行循環 for item in unratedItems: estimatedScore = estMethod(dataMat, user, simMeas, item) # 尋找前N個未評級物品，調用standEst()來產生該物品的預測得分，該物品的編號和估計值會放在一個元素列表itemScores中 itemScores.append((item, estimatedScore)) # 按照估計得分，對該列表進行排序並返回。列表逆排序，第一個值就是最大值 return sorted(itemScores, key=lambda jj: jj[1], reverse=True)[: N]

測試 和 項目調用，可直接參考我們的代碼

完整代碼地址: https://github.com/apachecn/MachineLearning/blob/master/src/python/14.SVD/svdRecommend.py

要點補充

基於內容(content-based)的推薦

1. 通過各種標籤來標記菜肴
2. 將這些屬性作為相似度計算所需要的數據
3. 這就是：基於內容的推薦。

構建推薦引擎面臨的挑戰

問題

• 1）在大規模的數據集上，SVD分解會降低程序的速度
• 2）存在其他很多規模擴展性的挑戰性問題，比如矩陣的表示方法和計算相似度得分消耗資源。
• 3）如何在缺乏數據時給出好的推薦-稱為冷啟動【簡單說：用戶不會喜歡一個無效的物品，而用戶不喜歡的物品又無效】

建議

• 1）在大型系統中，SVD分解(可以在程序調入時運行一次)每天運行一次或者其頻率更低，並且還要離線運行。
• 2）在實際中，另一個普遍的做法就是離線計算並保存相似度得分。(物品相似度可能被用戶重複的調用)
• 3）冷啟動問題，解決方案就是將推薦看成是搜索問題，通過各種標籤／屬性特徵進行基於內容的推薦。

項目案例: 基於 SVD 的圖像壓縮

收集 並 準備數據

將文本數據轉化為矩陣

# 載入並轉換數據def imgLoadData(filename): myl = [] # 打開文本文件，並從文件以數組方式讀入字元 for line in open(filename).readlines(): newRow = [] for i in range(32): newRow.append(int(line[i])) myl.append(newRow) # 矩陣調入後，就可以在屏幕上輸出該矩陣 myMat = mat(myl) return myMat

分析數據: 分析 Sigma 的長度個數

通常保留矩陣 80% ～ 90% 的能量，就可以得到重要的特徵並去除雜訊。

def analyse_data(Sigma, loopNum=20): """analyse_data(分析 Sigma 的長度取值) Args: Sigma Sigma的值 loopNum 循環次數 """ # 總方差的集合（總能量值） Sig2 = Sigma**2 SigmaSum = sum(Sig2) for i in range(loopNum): SigmaI = sum(Sig2[:i+1]) 根據自己的業務情況，就行處理，設置對應的 Singma 次數 通常保留矩陣 80% ～ 90% 的能量，就可以得到重要的特徵並取出雜訊。 print 主成分：%s, 方差佔比：%s%% % (format(i+1, 2.0f), format(SigmaI/SigmaSum*100, 4.2f))

使用演算法: 對比使用 SVD 前後的數據差異對比，對於存儲大家可以試著寫寫

例如：32*32=1024 => 32*2+2*1+32*2=130(2*1表示去掉了除對角線的0), 幾乎獲得了10倍的壓縮比。

# 列印矩陣def printMat(inMat, thresh=0.8): # 由於矩陣保護了浮點數，因此定義淺色和深色，遍歷所有矩陣元素，當元素大於閥值時列印1，否則列印0 for i in range(32): for k in range(32): if float(inMat[i, k]) > thresh: print 1, else: print 0, print # 實現圖像壓縮，允許基於任意給定的奇異值數目來重構圖像def imgCompress(numSV=3, thresh=0.8): """imgCompress( ) Args: numSV Sigma長度 thresh 判斷的閾值 """ # 構建一個列表 myMat = imgLoadData(input/14.SVD/0_5.txt) print "****original matrix****" # 對原始圖像進行SVD分解並重構圖像e printMat(myMat, thresh) # 通過Sigma 重新構成SigRecom來實現 # Sigma是一個對角矩陣，因此需要建立一個全0矩陣，然後將前面的那些奇異值填充到對角線上。 U, Sigma, VT = la.svd(myMat) # SigRecon = mat(zeros((numSV, numSV))) # for k in range(numSV): # SigRecon[k, k] = Sigma[k] # 分析插入的 Sigma 長度 analyse_data(Sigma, 20) SigRecon = mat(eye(numSV) * Sigma[: numSV]) reconMat = U[:, :numSV] * SigRecon * VT[:numSV, :] print "****reconstructed matrix using %d singular values *****" % numSV printMat(reconMat, thresh)

完整代碼地址: https://github.com/apachecn/MachineLearning/blob/master/src/python/14.SVD/svdRecommend.py

• 作者：片刻 1988
• GitHub地址: https://github.com/apachecn/MachineLearning
• 版權聲明：歡迎轉載學習 => 請標註信息來源於 ApacheCN

推薦閱讀：