机器学习SVD【二】
本篇的數(shù)據(jù)和代碼參見：https://github.com/stonycat/ML-in-Action?
一、開篇：簡述SVD應(yīng)用?
利用SVD實(shí)現(xiàn),我們能夠用小得多的數(shù)據(jù)集來表示原始數(shù)據(jù)集。這樣做,實(shí)際上是去除了噪聲和冗余信息。簡而言之，SVD是一種從大量數(shù)據(jù)中提取主要關(guān)鍵數(shù)據(jù)的方法。
下面介紹幾種應(yīng)用場景：?
1、隱性語義索引?
最早的SVD應(yīng)用之一就是信息檢索。我們稱利用SVD的方法為隱性語義索引(LatentSemantic Indexing,LSI)或隱性語義分析(Latent Semantic Analysis,LSA)。在LSI中,一個(gè)矩陣是由文檔和詞語組成的。應(yīng)用SVD時(shí)，構(gòu)建的SVD奇異值代表了文章的主題或者主要概念。?
當(dāng)我們查找一個(gè)詞時(shí),其同義詞所在的文檔可能并不會(huì)匹配上。如果我們從上千篇相似的文檔中抽取出概念,那么同義詞就會(huì)映射為同一概念。
2、推薦系統(tǒng)?
簡單版本的推薦系統(tǒng)能夠計(jì)算項(xiàng)或者人之間的相似度。更先進(jìn)的方法則先利用SVD從數(shù)據(jù)中構(gòu)建一個(gè)主題空間,然后再在該空間下計(jì)算其相似度。
SVD是矩陣分解的一種類型,而矩陣分解是將數(shù)據(jù)矩陣分解為多個(gè)獨(dú)立部分的過程。
二、矩陣分解?
很多情況下,數(shù)據(jù)中的一小段攜帶了數(shù)據(jù)集中的大部分信息,其他信息則要么是噪聲,要么就是毫不相關(guān)的信息。?
在線性代數(shù)中還有很多矩陣分解技術(shù)。矩陣分解可以將原始矩陣表示成新的易于處理的形式,這種新形式是兩個(gè)或多個(gè)矩陣的乘積。?
不同的矩陣分解技術(shù)具有不同的性質(zhì),其中有些更適合于某個(gè)應(yīng)用,有些則更適合于其他應(yīng)用。最常見的一種矩陣分解技術(shù)就是SVD。公式如下：
上述分解中會(huì)構(gòu)建出一個(gè)矩陣 Σ ,該矩陣只有對角元素,其他元素均為0。另一個(gè)慣例就是,Σ 的對角元素是從大到小排列的。這些對角元素稱為 奇異值(Singular Value) ,它們對應(yīng)了原始數(shù)據(jù)集矩陣 Data 的奇異值。奇異值和特征值是有關(guān)系的。這里的奇異值就是矩陣 Data?DataTData?DataT ?特征值的平方根。
科學(xué)和工程中,一直存在這樣一個(gè)普遍事實(shí):在某個(gè)奇異值的數(shù)目( r 個(gè))之后,其他的奇異值都置為0。這就意味著數(shù)據(jù)集中僅有 r個(gè)重要特征,而其余特征則都是噪聲或冗余特征。
三、利用 Python 實(shí)現(xiàn) SVD?
NumPy有一個(gè)稱為linalg的線性代數(shù)工具箱。接下來,我們了解一下如何利用該工具箱實(shí)現(xiàn)如下矩陣的SVD處理:?
Sigma為了方便僅返回對角元素。?
建立一個(gè)新文件 svdRec.py 并加入如下代碼:
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
測試：
>>> import svdRec >>> Data=svdRec.loadExData() >>> U,Sigma,VT=linalg.svd(Data) >>> Sigma array([ 9.64365076e+00, 5.29150262e+00, 8.36478329e-16,6.91811207e-17, 3.76946717e-34])- 1
- 2
- 3
- 4
- 5
- 6
前 3 個(gè)數(shù)值比其他的值大了很多(如果你的最后兩個(gè)值的結(jié)果與這里的結(jié)果稍有不同,也不必?fù)?dān)心。它們太小了,所以在不同機(jī)器上產(chǎn)生的結(jié)果就可能會(huì)稍有不同,但是數(shù)量級(jí)應(yīng)該和這里的結(jié)果差不多)。于是,我們就可以將最后兩個(gè)值去掉了。數(shù)據(jù)表示為：?
我們是如何知道僅需保留前 3 個(gè)奇異值的呢?確定要保留的奇異值的數(shù)目有很多啟發(fā)式的策略,其中一個(gè)典型的做法就是保留矩陣中?90%?的能量信息。我們將所有的奇異值求其平方和，將平方和累加到總值的 90% 為止。
另一個(gè)啟發(fā)式策略就是,當(dāng)矩陣上有上萬的奇異值時(shí),那么就保留前面的 2000 或 3000 個(gè)。盡管后一種方法不太優(yōu)雅,但是在實(shí)際中更容易實(shí)施。
現(xiàn)在我們已經(jīng)通過三個(gè)矩陣對原始矩陣進(jìn)行了近似。我們可以用一個(gè)小很多的矩陣來表示一個(gè)大矩陣。有很多應(yīng)用可以通過 SVD 來提升性能。下面我們將討論一個(gè)比較流行的 SVD 應(yīng)用的例子 —— 推薦引擎。
四、基于協(xié)同過濾的推薦引擎?
協(xié)同過濾( collaborative filtering )是通過將用戶和其他用戶的數(shù)據(jù)進(jìn)行對比來實(shí)現(xiàn)推薦的，唯一所需要的數(shù)學(xué)方法就是相似度的計(jì)算。
1、相似度計(jì)算?
利用用戶對它們的意見來計(jì)算相似度：這就是協(xié)同過濾中所使用的方法。它并不關(guān)心物品的描述屬性,而是嚴(yán)格地按照許多用戶的觀點(diǎn)來計(jì)算相似度。
我們希望,相似度值在 0 到 1 之間變化,并且物品對越相似,它們的相似度值也就越大。我們可以用“相似度 =1/(1+ 距離 ) ”這樣的算式來計(jì)算相似度。當(dāng)距離為 0 時(shí),相似度為 1.0 。如果距離真的非常大時(shí),相似度也就趨近于 0 。?
1-距離采用歐式距離來計(jì)算（計(jì)算平方和）。
2-第二種計(jì)算距離的方法是皮爾遜相關(guān)系數(shù)( Pearson correlation )。?
該方法相對于歐氏距離的一個(gè)優(yōu)勢在于,它對用戶評級(jí)的量級(jí)并不敏感。比如某個(gè)狂躁者對所有物品的評分都是 5 分,而另一個(gè)憂郁者對所有物品的評分都是 1 分,皮爾遜相關(guān)系數(shù)會(huì)認(rèn)為這兩個(gè)向量是相等的。在 NumPy 中,皮爾遜相關(guān)系數(shù)的計(jì)算是由函數(shù) corrcoef() 進(jìn)行的,后面我們很快就會(huì)用到它了。皮爾遜相關(guān)系數(shù)的取值范圍從? 1 到 +1 ,我們通過?0.5 + 0.5*corrcoef()?這個(gè)函數(shù)計(jì)算,并且把其取值范圍歸一化到 0 到 1 之間。
3-余弦相似度 ( cosine similarity )?
其計(jì)算的是兩個(gè)向量夾角的余弦值。如果夾角為 90 度,則相似度為 0 ;如果兩個(gè)向量的方向相同,則相似度為 1.0 。
其中 ‖A‖‖B‖‖A‖‖B‖ 為A、B的2范數(shù)。你可以定義向量的任一范數(shù),但是如果不指定范數(shù)階數(shù),則都假設(shè)為 2 范數(shù)。 from numpy import * from numpy import linalg as la #相似度1：歐式距離 def ecludSim(inA,inB):return 1.0/(1.0 + la.norm(inA - inB)) #相似度2：威爾遜距離 def pearsSim(inA,inB):if len(inA) < 3 : return 1.0return 0.5+0.5*corrcoef(inA, inB, rowvar = 0)[0][1] #相似度3：余弦 def cosSim(inA,inB):num = float(inA.T*inB)denom = la.norm(inA)*la.norm(inB)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
2、基于物品的相似度還是基于用戶的相似度？?
?
上圖：行與行之間比較的是基于用戶的相似度,列與列之間比較的則是基于物品的相似度。到底使用哪一種相似度呢??
這取決于用戶或物品的數(shù)目。
基于物品相似度計(jì)算的時(shí)間會(huì)隨物品數(shù)量的增加而增加,基于用戶的相似度計(jì)算的時(shí)間則會(huì)隨用戶數(shù)量的增加而增加。?
如果用戶的數(shù)目很多,那么我們可能傾向于使用基于物品相似度的計(jì)算方法。對于大部分產(chǎn)品導(dǎo)向的推薦引擎而言,用戶的數(shù)量往往大于物品的數(shù)量,即購買商品的用戶數(shù)會(huì)多于出售的商品種類。
3、推薦引擎的評價(jià)?
如何對推薦引擎進(jìn)行評價(jià)呢?此時(shí),我們既沒有預(yù)測的目標(biāo)值,也沒有用戶來調(diào)查他們對預(yù)測的滿意程度。這里我們就可以采用前面多次使用的交叉測試的方法。具體的做法就是,我們將某些已知的評分值去掉,然后對它們進(jìn)行預(yù)測,最后計(jì)算預(yù)測值和真實(shí)值之間的差異。?
通常用于推薦引擎評價(jià)的指標(biāo)是稱為最小均方根誤差( Root Mean Squared Error , RMSE )的指標(biāo),它首先計(jì)算均方誤差的平均值然后取其平方根。
五、示例:餐館菜肴推薦引擎?
構(gòu)建一個(gè)基本的推薦引擎,它能夠?qū)ふ矣脩魶]有嘗過的菜肴。然后,通過 SVD 來減少特征空間并提高推薦的效果。這之后,將程序打包并通過用戶可讀的人機(jī)界面提供給人們使用。
(1) 尋找用戶沒有評級(jí)的菜肴,即在用戶-物品矩陣中的 0 值;?
(2) 在用戶沒有評級(jí)的所有物品中,對每個(gè)物品預(yù)計(jì)一個(gè)可能的評級(jí)分?jǐn)?shù)。這就是說,我們?
認(rèn)為用戶可能會(huì)對物品的打分(這就是相似度計(jì)算的初衷);?
(3) 對這些物品的評分從高到低進(jìn)行排序,返回前N個(gè)物品。
下述代碼：遍歷數(shù)據(jù)行中的每個(gè)物品。如果某個(gè)物品評分值為 0 ,就意味著用戶沒有對該物品評分,跳過了這個(gè)物品。該循環(huán)大體上是對用戶評過分的每個(gè)物品進(jìn)行遍歷,并將它和其他物品進(jìn)行比較。
但是如果存在重合的物品,則基于這些重合物品計(jì)算相似度。隨后,相似度會(huì)不斷累加,每次計(jì)算時(shí)還考慮相似度和當(dāng)前用戶評分的乘積。最后,通過除以所有的評分總和,對上述相似度評分的乘積進(jìn)行歸一化。這就可以使得最后的評分值在 0 到 5 之間,而這些評分值則用于對預(yù)測值進(jìn)行排序。
#遍歷 計(jì)算相似度 def standEst(dataMat, user, simMeas, item):#數(shù)據(jù)矩陣、用戶編號(hào)、相似度計(jì)算方法和物品編號(hào)n = shape(dataMat)[1]simTotal = 0.0;ratSimTotal = 0.0for j in range(n):userRating = dataMat[user, j]if userRating == 0: continue#尋找兩個(gè)用戶都做了評價(jià)的產(chǎn)品overLap = nonzero(logical_and(dataMat[:, item].A > 0, dataMat[:, j].A > 0))[0]if len(overLap) == 0:similarity = 0else:#存在兩個(gè)用戶都評價(jià)的產(chǎn)品 計(jì)算相似度similarity = simMeas(dataMat[overLap, item], dataMat[overLap, j])print ('the %d and %d similarity is: %f' % (item, j, similarity))simTotal += similarity #計(jì)算每個(gè)用戶對所有評價(jià)產(chǎn)品累計(jì)相似度ratSimTotal += similarity * userRating #根據(jù)評分計(jì)算比率if simTotal == 0:return 0else:return ratSimTotal / simTotal#推薦實(shí)現(xiàn)：recommend() 產(chǎn)生了最高的 N 個(gè)推薦結(jié)果 def recommend(dataMat, user, N=3, simMeas=cosSim, estMethod=standEst):unratedItems = nonzero(dataMat[user, :].A == 0)[1] #尋找用戶未評價(jià)的產(chǎn)品if len(unratedItems) == 0: return ('you rated everything')itemScores = []for item in unratedItems:estimatedScore = estMethod(dataMat, user, simMeas, item)#基于相似度的評分itemScores.append((item, estimatedScore))return sorted(itemScores, key=lambda jj: jj[1], reverse=True)[:N]- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
recommend()函數(shù)在所有的未評分物品上進(jìn)行循環(huán)。對每個(gè)未評分物品,則通過調(diào)用standEst() 來產(chǎn)生該物品的預(yù)測得分。該物品的編號(hào)和估計(jì)得分值會(huì)放在一個(gè)元素列表itemScores 中。最后按照估計(jì)得分,對該列表進(jìn)行排序并返回。
測試：
>>> reload(svdRec) <module 'svdRec' from '/home/zq/Git_zq/ML-in-Action-Code-and-Note/ch14/svdRec.py'> >>> myMat=mat(svdRec.loadExData()) >>> myMat[0,1]=myMat[0,0]=myMat[1,0]=myMat[2,0]=4 >>> myMat[3,3]=2 >>> myMat matrix([[4, 4, 0, 2, 2],[4, 0, 0, 3, 3],[4, 0, 0, 1, 1],[1, 1, 1, 2, 0],[2, 2, 2, 0, 0],[5, 5, 5, 0, 0],[1, 1, 1, 0, 0]]) >>> svdRec.recommend(myMat,2) the 1 and 0 similarity is: 1.000000 the 1 and 3 similarity is: 0.928746 the 1 and 4 similarity is: 1.000000 the 2 and 0 similarity is: 1.000000 the 2 and 3 similarity is: 1.000000 the 2 and 4 similarity is: 0.000000 [(2, 2.5), (1, 2.0243290220056256)]- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
這表明了用戶 2 (由于我們從 0 開始計(jì)數(shù),因此這對應(yīng)了矩陣的第 3 行)對物品 2 的預(yù)測評分值為 2.5 ,對物品 1 的預(yù)測評分值為 2.05 。
下面利用 SVD 提高推薦的效果
>>> from numpy import linalg as la >>> U,Sigma,VT=la.svd(mat(svdRec.loadExData2())) >>> Sigma array([ 15.77075346, 11.40670395, 11.03044558, 4.84639758,3.09292055, 2.58097379, 1.00413543, 0.72817072,0.43800353, 0.22082113, 0.07367823]) >>> Sig2=Sigma**2 #計(jì)算平方和 >>> sum(Sig2) 541.99999999999955 >>> sum(Sig2)*0.9 #取前90% 487.79999999999961 >>> sum(Sig2[:3]) #>90% SVD取前三個(gè)特征值 500.50028912757932- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
下述程序中包含有一個(gè)函數(shù) svdEst() 。在 recommend() 中,這個(gè)函數(shù)用于替換對 standEst() 的調(diào)用,該函數(shù)對給定用戶給定物品構(gòu)建了一個(gè)評分估計(jì)值。
#利用SVD def svdEst(dataMat, user, simMeas, item):n = shape(dataMat)[1]simTotal = 0.0;ratSimTotal = 0.0U, Sigma, VT = la.svd(dataMat) #不同于stanEst函數(shù)，加入了SVD分解Sig4 = mat(eye(4) * Sigma[:4]) # 建立對角矩陣xformedItems = dataMat.T * U[:, :4] * Sig4.I #降維：變換到低維空間#下面依然是計(jì)算相似度，給出歸一化評分for j in range(n):userRating = dataMat[user, j]if userRating == 0 or j == item: continuesimilarity = simMeas(xformedItems[item, :].T, xformedItems[j, :].T)print ('the %d and %d similarity is: %f' % (item, j, similarity))simTotal += similarityratSimTotal += similarity * userRatingif simTotal == 0:return 0else:return ratSimTotal / simTotal- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
構(gòu)建推薦引擎面臨的挑戰(zhàn)
SVD 分解可以在程序調(diào)入時(shí)運(yùn)行一次。在大型系統(tǒng)中, SVD 每天運(yùn)行一次或者其頻率更低,并且還要離線運(yùn)行。?
1-推薦引擎中還存在其他很多規(guī)模擴(kuò)展性的挑戰(zhàn)性問題,比如矩陣的表示方法。在上面給出的例子中有很多 0 ,實(shí)際系統(tǒng)中 0 的數(shù)目更多。也許,我們可以通過只存儲(chǔ)非零元素來節(jié)省內(nèi)存和計(jì)算開銷?
2-一個(gè)潛在的計(jì)算資源浪費(fèi)則來自于相似度得分。在我們的程序中,每次需要一個(gè)推薦得分時(shí),都要計(jì)算多個(gè)物品的相似度得分,這些得分記錄的是物品之間的相似度。因此在需要時(shí),這些記錄可以被另一個(gè)用戶重復(fù)使用。在實(shí)際中,另一個(gè)普遍的做法就是離線計(jì)算并保存相似度得分。
3-推薦引擎面臨的另一個(gè)問題就是如何在缺乏數(shù)據(jù)時(shí)給出好的推薦。這稱為冷啟動(dòng) ( cold-start )問題,冷啟動(dòng)問題的解決方案,就是將推薦看成是搜索問題。?
為了將推薦看成是搜索問題,我們可能要使用所需要推薦物品的屬性。在餐館菜肴的例子中,我們可以通過各種標(biāo)簽來標(biāo)記菜肴,比如素食、美式 BBQ 、價(jià)格很貴等。同時(shí),我們也可以將這些屬性作為相似度計(jì)算所需要的數(shù)據(jù),這被稱為基于內(nèi)容( content-based )的推薦。可能,基于內(nèi)容的推薦并不如我們前面介紹的基于協(xié)同過濾的推薦效果好,但我們擁有它,這就是個(gè)良好的開始。
六、示例:基于 SVD 的圖像壓縮?
在代碼庫中,我們包含了一張手寫的數(shù)字圖像,該圖像在第 2 章使用過。原始的圖像大小是 32×32=1024 像素,我們能否使用更少的像素來表示這張圖呢?如果能對圖像進(jìn)行壓縮,那么就可以節(jié)省空間或帶寬開銷了。我們可以使用 SVD 來對數(shù)據(jù)降維,從而實(shí)現(xiàn)圖像的壓縮。
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
imgCompress()函數(shù)基于任意給定的奇異值數(shù)目來重構(gòu)圖像。該函數(shù)構(gòu)建了一個(gè)列表,然后打開文本文件,讀入字符。?
接下來就開始對原始圖像進(jìn)行SVD分解并重構(gòu)圖像。在程序中,通過將 Sigma 重新構(gòu)成 SigRecon 來實(shí)現(xiàn)這一點(diǎn)。 Sigma 是一個(gè)對角矩陣,因此需要建立一個(gè)全0矩陣,然后將前面的那些奇異值填充到對角線上。最后,通過截?cái)嗟?U 和 V T 矩陣,用 SigRecon 得到重構(gòu)后的矩陣,該矩陣通過 printMat() 函數(shù)輸出。
小結(jié)?
VD 是一種強(qiáng)大的降維工具,我們可以利用 SVD 來逼近矩陣并從中提取重要特征。通過保留矩陣 80% ~ 90% 的能量,就可以得到重要的特征并去掉噪聲。
在大規(guī)模數(shù)據(jù)集上, SVD 的計(jì)算和推薦可能是一個(gè)很困難的工程問題。通過離線方式來進(jìn)行SVD 分解和相似度計(jì)算,是一種減少冗余計(jì)算和推薦所需時(shí)間的辦法。?
在下一章中,我們將介紹在大數(shù)據(jù)集上進(jìn)行機(jī)器學(xué)習(xí)的一些工具。
總結(jié)
以上是生活随笔為你收集整理的机器学习SVD【二】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 升腾联手VMware 发布首款本土化桌面
- 下一篇： spark与storm的对比