天天看點
傳回

python 實作協同過濾算法并應用奇異值分解(SVD)優化

★ 協同過濾算法：

     協同過濾算法可以分為基于使用者的協同過濾算法和基于物品的協同過濾算法。

     (1.)  基于物品的協同過濾算法:

     它是計算物品之間的相似度，并根據物品之間的相似度給目标使用者未評分項進行預測。即列與列之間的比較。

     ✿ 目标使用者 u 對未評分項 i 的預測公式為：

python 實作協同過濾算法并應用奇異值分解(SVD)優化

                        ①

     其中：I(u) 表示使用者 u 所有評分過的物品的集合，​

python 實作協同過濾算法并應用奇異值分解(SVD)優化
表示 物品i (i列)和物品j (j列)之間的相似度，
python 實作協同過濾算法并應用奇異值分解(SVD)優化

表示目标使用者 u 對物品 j 的評分。

     (2.) 基于使用者的協同過濾算法:

     它是計算使用者之間的相似度，并根據使用者之間的相似度給目标使用者未評分項進行預測。即行與行之間的比較。

    ✿ 目标使用者 u 對未評分項 i 的預測公式為：

python 實作協同過濾算法并應用奇異值分解(SVD)優化

                       ②

      其中：N(i)表示對商品i打過分的使用者的集合，

python 實作協同過濾算法并應用奇異值分解(SVD)優化
表示使用者u (u行)與使用者v (v行)的相似度，
python 實作協同過濾算法并應用奇異值分解(SVD)優化

表示使用者v對商品i的打分。

     那到底選那一種方法計算相似度來進行預測推薦呢？這取決于使用者或物品的數目，如果使用者的數目很多，我們更傾向與使用基于物品相似度的計算方法。

★ 相似度的三種計算方式：

    (1.) 歐式距離計算相似度：

     X、Y表示資料集矩陣中的任意兩列或兩行：

python 實作協同過濾算法并應用奇異值分解(SVD)優化

                      ③

    相似度取值範圍是：(0,1]。當距離為0時，相似度為1；當距離為非常大時，相似度趨近于0。

    (2.) 皮爾遜相關系數計算相似度：

     Corr(X、Y)是X與Y的相關系數。

python 實作協同過濾算法并應用奇異值分解(SVD)優化

               ④

    相似度範圍是：[0,1]。當X、Y不相關時(Corr(X,Y)=0)，相似度為0.5；當X、Y強正相關時(Corr(X,Y)=1)，相似度為1；當X、Y強負相關時(Corr(X,Y)=-1)，相似度為0。

     (3.) 餘弦相似度：

python 實作協同過濾算法并應用奇異值分解(SVD)優化

                  ⑤

     相似度範圍是：[0,1]。當向量X、Y夾角為90度的時候，相似度為0.5；當夾角為0度時，相似度為1；當夾角為180度時，相似度為0。

★ 基于物品相似度的推薦算法：

    ✿ 代碼流程：

     (1.) 給定使用者user，周遊所有物品，找到該使用者未評分的物品組成一個集合。周遊這個集合no_rated，如物品i未評分。

     (2.) 周遊所有物品，找到該使用者評過分的物品再組成一個集合rated，周遊這個集合，如物品j評過分。

     (3.) 找出既對物品i評過分的，又對物品j評過分的所有使用者，計算這些使用者對物品i的評分并組成列向量，再計算這些使用者對物品j評分并組成向量，計算這兩個向量的相似度(通過上述方法的任何一種)。

     (4.) 周遊集合rated，按(3.)的方法把所有相似度都計算出來。然後把所有相似度的和儲存到simTotal變量中，預測評分根據公式為：rated集合中的所有物品×該物品的相似度的累加和，儲存到變量ratSimTotal中。對預測評分歸一化，ratSimTotal / simTotal

     (5.) 繼續周遊no_rate集合的下一個為評分元素，重複（2)、(3)、(4)，周遊完後，對預測物品按預測評分倒序排列。選前3個物品推薦給使用者。

from numpy import *

def euclidSim(inA, inB):  # 歐式距離計算相似度
    return 1.0/(1.0 + linalg.norm(inA - inB))  # 公式

def pearsSim(inA, inB):   # 皮爾遜相關系數計算相似度
    if len(inA) < 3:
        return 1.0
    return 0.5+0.5*corrcoef(inA,inB,rowvar=0)[0][1]  # 公式

def cosSim(inA,inB):  # 餘弦相似度
    num = float(inA.T * inB)
    denom = linalg.norm(inA)*linalg.norm(inB)
    return 0.5+0.5*(num/denom)  # 公式

def loadDataSet():
    dataset = mat([[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],[1,1,1,0,0],[5,5,5,0,0]])
    return dataset

def standEst(dataMat,user,simMeas,item):  # 計算每個未評分的物品的預測評分，user是給定的要推薦給她物品的使用者，item是未評分的物品
    n = shape(dataMat)[1] # 物品總數
    simTotal = 0.0   # 總的相似度
    ratSimTotal = 0.0  # 該物品的預測評分
    for j in range(n):  # 周遊所有元素
        userRating = dataMat[user,j]
        if userRating == 0:  # 找到該使用者評過分的物品j
            continue
        overLap = nonzero(logical_and(dataMat[:,item].A > 0,dataMat[:,j].A > 0))[0] # 找到既對評過分的物品j和未評分的物品item的使用者的行坐标
        if len(overLap) == 0: # 如果沒有符合這種要求的使用者
            similarity = 0    # 相似度置為0
        else: # 有符合這種要求的使用者
            similarity = simMeas(dataMat[overLap,item],dataMat[overLap,j]) # 根據公式計算相似度
        simTotal += similarity
        ratSimTotal += similarity * userRating
    if simTotal == 0: # 如果未評分的這個物品，大家都沒評過分
        return 0  # 則不推薦
    else:
        return ratSimTotal / simTotal # 對預測評分歸一化

def recommend(dataMat, user, N=3, simMeas=cosSim,estMethod=standEst): # user是給定的使用者，即我們要向他推薦物品的使用者，N是為該使用者推薦的物品的個數
    unratedItems = nonzero(dataMat[user,:].A==0)[1]   # 找出該使用者未評分的物品，即得到列下标
    if len(unratedItems) == 0: # 如果為0,說明該使用者對這些物品都評過分了，不要推薦了
        return 'you rated everything'
    itemScores = []
    for item in unratedItems: # 周遊這些待推薦的物品
        estimateScore = estMethod(dataMat,user,simMeas,item)
        itemScores.append((item,estimateScore))
    return sorted(itemScores,key=lambda jj:jj[1],reverse=True)[:N] # 根據預測評分倒序排列，選前N個待推薦的物品

if __name__ == '__main__':
    dataset = loadDataSet()
    recommend_goods = recommend(dataset,2) # 要推薦的物品
    print('要推薦的物品有：\n',recommend_goods)
    ✿ 運作效果：
python 實作協同過濾算法并應用奇異值分解(SVD)優化
     我們對使用者2，首先推薦物品2，對物品2的預測評分是2.5；再推薦物品1，對物品1的預測評分是2.024。

★ 利用SVD提高推薦效果：

     我們得到的使用者物品資料集實際上會是稀疏的多的矩陣(0特别多)，我們有必要對其進行降維，SVD是一種不錯的方法，我們知道，任何一個矩陣都可以進行奇異值分解：

python 實作協同過濾算法并應用奇異值分解(SVD)優化
     其中：U是m×m的酉矩陣，∑是m×n的對角矩陣，V是n×n的酉矩陣。∑對角線上是M的奇異值(也是M*
python 實作協同過濾算法并應用奇異值分解(SVD)優化
的特征值的開方)，奇異值越大，對應的投影的資訊量就越大，一般來說，我們隻需要選出包含資訊量超過總資訊量的90﹪的幾個奇異值就可以了，即前r個奇異值就滿足這個要求的話，∑就可以隻保留前r列、前r行，即m×n維變成r×r維，而U選取前r列，
python 實作協同過濾算法并應用奇異值分解(SVD)優化
選取前r行，是以M就可以分解為：
python 實作協同過濾算法并應用奇異值分解(SVD)優化

   這樣M就可以用占空間更小的三個矩陣U、∑、V來存貯。SVD可用來對資料集進行壓縮。

   比如壓縮列：

python 實作協同過濾算法并應用奇異值分解(SVD)優化
   壓縮行：
python 實作協同過濾算法并應用奇異值分解(SVD)優化

★ 代碼

  ✿ 代碼疑問：請路過的大佬解答一下！

    (1.) 對降維公式的疑問：

   書中對原資料集采用SVD降維，降維後的資料采用公式：

python 實作協同過濾算法并應用奇異值分解(SVD)優化

    代碼是：

                 xformedItems = dataMat.T * U[:,:dim_num+1] * Sig4.I

    我們看出，降維後資料集變成n×r維。而且根據這個公式求出來的新的資料集Mnew，其實就是V。

   (2.)  疑問2：

     書中，利用上述公式求出的新的資料集Mnew，為何直接用于了相似度的求取。這兩個疑問的關鍵就是：這麼降維後的資料集應該怎麼了解？這正好也是SVD降維的缺點，即轉換後的資料難以了解。

def svdEst(dataMat, user, simMeas, item):  # SVD降維，并計算相似度，求出推薦産品
    n = shape(dataset)[1]
    simTotal = 0.0
    ratSimTotal = 0.0
    U,Sigma,VT = linalg.svd(dataMat) # 奇異值分解
    dim_num = calcDim(Sigma)
    # Sig4 = mat(eye(dim_num+1)*Sigma[:dim_num+1])  # 把前4個奇異值構造成4×4維對角陣
    Sig4 = mat(diag(Sigma[:dim_num+1])) # 跟上一個語句一個意思
    xformedItems = dataMat.T * U[:,:dim_num+1] * Sig4.I  # 不了解
    # print('新資料=',xformedItems)
    for j in range(n):
        userRating =dataMat[user,j]
        if userRating == 0 or j == item:
            continue
        similarity = simMeas(xformedItems[item,:].T,xformedItems[j,:].T) # 不了解
        print(' the {0} and {1} similarity is : {2}'.format(item,j,similarity))
        simTotal += similarity
        ratSimTotal += similarity * userRating
    if simTotal == 0:
        return 0
    else:
        return ratSimTotal/simTotal

def calcDim(sigma):  # 選擇合适的sigma維數
    sigma2 = sigma**2
    for i in range(len(sigma)):
        if sum(sigma2[:i])/sum(sigma2) > 0.9:
            return i
★ 總的SVD推薦算法代碼 
from numpy import *

def euclidSim(inA, inB):  # 歐式距離計算相似度
    return 1.0/(1.0 + linalg.norm(inA - inB))  # 公式

def pearsSim(inA, inB):   # 皮爾遜相關系數計算相似度
    if len(inA) < 3:
        return 1.0
    return 0.5+0.5*corrcoef(inA,inB,rowvar=0)[0][1]  # 公式

def cosSim(inA,inB):  # 餘弦相似度
    num = float(inA.T * inB)
    denom = linalg.norm(inA)*linalg.norm(inB)
    return 0.5+0.5*(num/denom)  # 公式

def loadDataSet():
    # dataset = mat([[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],[1,1,1,0,0],[5,5,5,0,0]])
    # dataset = mat([[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]
    #                ])
    dataset = mat([[0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 5],
                   [0, 0, 0, 3, 0, 4, 0, 0, 0, 0, 3],
                   [0, 0, 0, 0, 4, 0, 0, 1, 0, 4, 0],
                   [3, 3, 4, 0, 0, 0, 0, 2, 2, 0, 0],
                   [5, 4, 5, 0, 0, 0, 0, 5, 5, 0, 0],
                   [0, 0, 0, 0, 5, 0, 1, 0, 0, 5, 0],
                   [4, 3, 4, 0, 0, 0, 0, 5, 5, 0, 1],
                   [0, 0, 0, 4, 0, 4, 0, 0, 0, 0, 4],
                   [0, 0, 0, 2, 0, 2, 5, 0, 0, 1, 2],
                   [0, 0, 0, 0, 5, 0, 0, 0, 0, 4, 0],
                   [1, 0, 0, 0, 0, 0, 0, 1, 2, 0, 0]])

    return dataset

def standEst(dataMat,user,simMeas,item):  # 計算每個未評分的物品的預測評分，user是給定的要推薦給她物品的使用者，item是未評分的物品
    n = shape(dataMat)[1] # 物品總數
    simTotal = 0.0   # 總的相似度
    ratSimTotal = 0.0  # 該物品的預測評分
    for j in range(n):  # 周遊所有元素
        userRating = dataMat[user,j]
        if userRating == 0:  # 找到該使用者評過分的物品j
            continue
        overLap = nonzero(logical_and(dataMat[:,item].A > 0,dataMat[:,j].A > 0))[0] # 找到既對評過分的物品j和未評分的物品item的使用者的行坐标
        if len(overLap) == 0: # 如果沒有符合這種要求的使用者
            similarity = 0    # 相似度置為0
        else: # 有符合這種要求的使用者
            similarity = simMeas(dataMat[overLap,item],dataMat[overLap,j]) # 根據公式計算相似度
        simTotal += similarity
        ratSimTotal += similarity * userRating
    if simTotal == 0: # 如果未評分的這個物品，大家都沒評過分
        return 0  # 則不推薦
    else:
        return ratSimTotal / simTotal # 對預測評分歸一化

def recommend(dataMat, user, N=3, simMeas=cosSim,estMethod=standEst): # user是給定的使用者，即我們要向他推薦物品的使用者，N是為該使用者推薦的物品的個數
    unratedItems = nonzero(dataMat[user,:].A==0)[1]   # 找出該使用者未評分的物品，即得到列下标
    if len(unratedItems) == 0: # 如果為0,說明該使用者對這些物品都評過分了，不要推薦了
        return 'you rated everything'
    itemScores = []
    for item in unratedItems: # 周遊這些待推薦的物品
        estimateScore = estMethod(dataMat,user,simMeas,item)
        itemScores.append((item,estimateScore))
    return sorted(itemScores,key=lambda jj:jj[1],reverse=True)[:N] # 根據預測評分倒序排列，選前N個待推薦的物品

def svdEst(dataMat, user, simMeas, item):
    n = shape(dataset)[1]
    simTotal = 0.0
    ratSimTotal = 0.0
    U,Sigma,VT = linalg.svd(dataMat)
    dim_num = calcDim(Sigma)
    # Sig4 = mat(eye(dim_num+1)*Sigma[:dim_num+1])  # 把前4個奇異值構造成4×4維對角陣
    Sig4 = mat(diag(Sigma[:dim_num+1]))
    xformedItems = dataMat.T * U[:,:dim_num+1] * Sig4.I
    # print('新資料=',xformedItems)
    for j in range(n):
        userRating =dataMat[user,j]
        if userRating == 0 or j == item:
            continue
        similarity = simMeas(xformedItems[item,:].T,xformedItems[j,:].T)
        print(' the {0} and {1} similarity is : {2}'.format(item,j,similarity))
        simTotal += similarity
        ratSimTotal += similarity * userRating
    if simTotal == 0:
        return 0
    else:
        return ratSimTotal/simTotal

def calcDim(sigma):  # 選擇合适的sigma維數
    sigma2 = sigma**2
    for i in range(len(sigma)):
        if sum(sigma2[:i])/sum(sigma2) > 0.9:
            return i

if __name__ == '__main__':
    dataset = loadDataSet()
    # recommend_goods = recommend(dataset,2) # 要推薦的物品
    # print('要推薦的物品有：\n',recommend_goods)
    u,s,vt = linalg.svd(dataset)
    oo = recommend(dataset,1,estMethod=svdEst)
    print(oo)
 ★ 代碼效果：
python 實作協同過濾算法并應用奇異值分解(SVD)優化

★ 不錯的SVD連結：

    1. https://blog.csdn.net/qq_32742009/article/details/82286434

大資料 SVD 協同過濾 cf
上一篇: Codeforces Round #597 (Div. 2) F. Daniel and Spring Cleaning
下一篇: 目标檢測論文、代碼、資料集彙總

繼續閱讀