機器學習實戰之SVD

1. 奇異值分解 SVD(singular value decomposition)
1.1 SVD評價
   優點: 簡化數據, 去除噪聲和冗余信息, 提高算法的結果
   缺點: 數據的轉換可能難以理解
1.2 SVD應用
(1) 隱性語義索引(latent semantic indexing, LSI)/隱性語義分析(latent semantic analysis, LSA)
      在LSI中, 一個矩陣由文檔和詞語組成的.在該矩陣上應用SVD可以構建多個奇異值, 這些奇異值代表文檔中的概念或主題, 可以用于更高效的文檔搜索.
(2) 推薦系統
      先利用SVD從數據中構建一個主題空間, 然后在該主題空間下計算相似度.
1.3 SVD分解
     SVD是一種矩陣分解技術,其將原始的數據集矩陣A(m*n)分解為三個矩陣，分解得到的三個矩陣的維度分別為m*m,m*n,n*n.其中除了對角元素不為0,其它元素均為0,其對角元素稱為奇異值,且按從大到小的順序排列, 這些奇異值對應原始數據集矩陣A的奇異值,即A*A(T)的特征值的平方根.

在某個奇異值(r個)之后, 其它的奇異值由于值太小,被忽略置為0, 這就意味著數據集中僅有r個重要特征,而其余特征都是噪聲或冗余特征.如下圖所示:

問題: 如何選擇數值r?
解答: 確定要保留的奇異值數目有很多啟發式的策略,其中一個典型的做法就是保留矩陣中90%的能量信息.為了計算能量信息,將所有的奇異值求其平方和,從大到小疊加奇異值,直到奇異值之和達到總值的90%為止;另一種方法是,當矩陣有上萬個奇異值時, 直接保留前2000或3000個.,但是后一種方法不能保證前3000個奇異值能夠包含錢90%的能量信息,但是操作簡單.
****SVD分解很耗時,通過離線方式計算SVD分解和相似度計算,是一種減少冗余計算和推薦所需時間的辦法.
2. 基于協同過濾的推薦引擎
2.1 定義
       協同過濾是通過將用戶和其他用戶的數據進行對比來實現推薦的.
       例如: 試圖對某個用戶喜歡的電影進行預測,搜索引擎會發現有一部電影該用戶還沒看過,然后它會計算該電影和用戶看過的電影之間的相似度, 如果相似度很高, 推薦算法就會認為用戶喜歡這部電影.

缺點: 在協同過濾情況下, 由于新物品到來時由于缺乏所有用戶對其的喜好信息,因此無法判斷每個用戶對其的喜好.而無法判斷某個用戶對其的喜好,也就無法利用該商品.

2.2 相似度計算

協同過濾利用用戶對食物的意見來計算相似度,下圖給出了一些用戶對菜的評級信息所組成的矩陣:

定義相似度在0-1之間變化,且物品對越相似,其相似度值越大,可以使用公式  相似度 = 1/(1 + 距離)   來計算相似度.
計算距離的方法如下:
(1) 歐氏距離
(2)皮爾遜相關系數(pearson correlation)
    度量兩個向量間的相似度,該方法優于歐氏在于其對用戶評級的量級不敏感,例如某個人對所有物品的評分都是5分,另一個人對所有物品評分都是1分,皮爾遜相關系數認為這兩個評分向量是相等的. 不過皮爾遜相關系數的取值范圍是(-1,1),通過0.5 + 0.5 * corrcoef()將其歸一化到0-1之間.
(3) 余弦相似度( cosine similarity)
    計算的是兩個向量夾角的余弦值.其取值范圍是(-1,1),因此也要將其歸一化到(0,1)區間.
以下是這三種相似度計算方法的代碼實現:
<span style="font-size:18px;">def eulidSim(in1,in2):
    return 1.0/(1.0+la.norm(in1-in2))

def pearsonSim(in1,in2):
    if len(in1) < 3: #檢查是否存在3個或更多的點,小于的話,這兩個向量完全相關
        return 1.0
        return 0.5 + 0.5 * corrcoef(in1,in2,rowvar = 0)[0][1]

</span><span style="font-size:18px;"> def cosSim(in1,in2):
    num = float(in1.T * in2)
    denom = la.norm(in1) * la.norm(in2)
    return 0.5 + 0.5 * (num/denom)
</span>
2.3 餐館菜推薦引擎
(1) 用處: 推薦餐館食物. 給定一個用戶, 系統會為此用戶推薦N個最好的推薦菜.為了實現這一目的,要做到:
尋找用戶沒有評級的菜, 即在用戶-物品矩陣中的0值;
在用戶沒有評級的所有物品中,對每個物品預計一個可能的評級分數.
對這些物品的評分從高到低進行排序,返回前n個物品
下面是實現代碼:
<span style="font-size:18px;">#計算在給定相似度計算方法的條件下,用戶user對物品item的估計評分值
def standEst(dataMat,user,simMea,item):
    n = shape(dataMat)[1]
    simTotal = 0.0
    ratSimTotal = 0.0
    for j in range(n):
        userRate = dataMat[user,j]
        if userRate == 0 :
            continue
        #得到對菜item和j都評過分的用戶id,用來計算物品item和j之間的相似度
        overlap = nonzero(logical_and(dataMat[:,item].A>0,dataMat[:,j].A>0))[0]
        if len(overlap) == 0:
            similarity = 0
        else:
            #計算物品item和j之間的相似度(必須選取用戶對這兩個物品都評分的用戶分數構成物品分數向量)
            similarity = simMea(dataMat[overlap,item],dataMat[overlap,j])
        simTotal += similarity
        ratSimTotal += similarity * userRate
    if simTotal ==0:
        return 0
    else:
        return ratSimTotal/simTotal  #歸一化處理

#輸入依次是數據矩陣,用戶編號,返回的菜的個數,距離計算方法,獲得物品評分的函數
def recommend(dataMat,user,n=3,simMea=cosSim,estMethod=standEst):
    #返回user用戶未評分的菜的下標    
    unratedItem = nonzero(dataMat[user,:].A == 0)[1]
    if(len(unratedItem) == 0):
        return 'you rated every one'
    
    itemScore = []
    #對每個沒評分的菜都估計該用戶可能賦予的分數
    for item in unratedItem:
        score = estMethod(dataMat,user,simMea,item)
        itemScore.append((item,score))
    
    #返回評分最高的前n個菜下標以及分數
    return sorted(itemScore, key = lambda jj:jj[1],reverse = True)[:n]</span>
2.4 利用SVD提高推薦效果
    實際的數據集得到的矩陣相當稀疏,因此可以先利用SVD將原始矩陣映射到低維空間中,; 然后再在低維空間中, 計算物品間的相似度,大大減少計算量.
其代碼實現如下:
<span style="font-size:18px;">#通過SVD對原始數據矩陣降維,便于計算物品間的相似度
def scdEst(dataMat,user,simMea,item):
    n = shape(dataMat)[1]
    simTotal = 0.0
    ratSimTotal = 0.0

    u,sigma,vt = la.svd(dataMat) #sigma是行向量
    sig4 = mat(eye(4) * sigma[:4]) #只利用最大的4個奇異值,將其轉換為4*4矩陣,非對角元素為0
    xformedItems = dataMat.T * u[:,:4] * sig4.I #得到n*4

    for j in range(n):
        userRate = dataMat[user,j]
        if userRate == 0  or j == item:
            continue
        #得到對菜item和j都評過分的用戶id,用來計算物品item和j之間的相似度
        #overlap = nonzero(logical_and(dataMat[:,item].A>0,dataMat[:,j].A>0))[0]
        #if len(overlap) == 0:
        #    similarity = 0
        #else:
            #計算物品item和j之間的相似度
        #    similarity = simMea(dataMat[overlap,item],dataMat[overlap,j])
        similarity = simMea(xformedItems[item,:].T,xformedItems[j,:].T)
        simTotal += similarity
        ratSimTotal += similarity * userRate
    if simTotal ==0:
        return 0
    else:
        return ratSimTotal/simTotal  #歸一化處理</span>
3. 基于SVD的圖像壓縮
<span style="font-size:18px;">#打印矩陣
def printMat(in1,thresh=0.8):
    for i in range(32):
        for k in range(32):
            if(float(in1[i,k]) > thresh):
                print 1,
            else:
                print 0,
        print ''

#利用SVD實現圖像壓縮,允許基于任意給定的奇異值來重構圖像,默認去前3個奇異值
def imgCompress(numSV=3,thresh=0.8):
    #32*32 matrix    
    my1 = []
    for line in open('0_5.txt').readlines():
        newrow = []
        for i in range(32):
            newrow.append(int(line[i]))
        my1.append(newrow)
    myMat = mat(my1)
    print '***original matrix***'
    printMat(myMat)

    u,sigma,vt = la.svd(myMat)
    #將sigma矩陣化,即sigrecon的對角元素是sigma的元素
    sigrecon = mat(zeros((numSV,numSV)))
    for k in range(numSV):
        sigrecon[k,k] = sigma[k]

    #重構矩陣
    reconMat = u[:,:numSV] * sigrecon * vt[:numSV,:]

    print '***reconstruct matrix***'
    printMat(reconMat)</span>

以數字為例:數字0存儲為32*32的矩陣,需要存儲1024個數據; 通過實驗發現只需要2個奇異值就能夠很精確地對圖像進行重構,u,vt的大小都是32*2的矩陣,再加上2個奇異值,則需要32*2*2+2=130個0-1值來存儲0;通過對比發現,實現了幾乎10倍的壓縮比.