推薦系統(tǒng)（三）：基于矩陣分解的推薦算法

一、矩陣分解原理

1.1、奇異值分解

奇異值分解（Singular Value Decomposition，SVD）是一種常見的矩陣分解方式，對于一個m \times n 的矩陣A，可定義其SVD為：
A=U \Sigma V^{*}
其中U為m \times m矩陣，V是n \times n矩陣，\Sigma為m \times n矩陣，其除了對角線元素外全為0，即
\boldsymbol{\Sigma}=\left(\begin{array}{cccccc}{\lambda_{1}} & {0} & {0} & {\cdots} & {\cdots} & {0}\\ {0} & {\lambda_{2}} & {0} & {\cdots} & {\cdots} & {0}\\ {0} & {0} & {\cdots} & {\cdots} & {\cdots} & {0}\\ {\cdots} & {\cdots} & {\cdots} & {\lambda_{n-1}} & {\cdots}& {0} \\ {\cdots} & {\cdots} & {\cdots} & {\cdots} & {\lambda_{n}} & {0} \\ {0}& {0}& {0}& {0}& {0}& {\mathbf{0}}\end{array}\right)
由于奇異值矩陣包含了原矩陣的信息，其其中主要信息由較大的幾個奇異值所表征，因此奇異值分解可用來作為矩陣降維，即：
A_{m \times n}=U_{m \times m} \Sigma_{m \times n} V_{n \times n}^{\mathrm{*}} \approx U_{m \times k} \Sigma_{k \times k} V_{k \times n}^{\mathrm{*}}
在推薦系統(tǒng)中，m代表樣本的用戶數(shù)，維度通常會很高，當k \ll m時會大大減輕線上存儲和計算的壓力?；诰仃嚪纸獾耐扑]算法的步驟可以分為：
（1）加載用戶對物品的評分矩陣；
（2）矩陣分解，求奇異值，根據(jù)奇異值的能量占比確定降維至k的數(shù)值；
（3）使用矩陣分解對物品評分矩陣進行降維；
（4）使用降維后的物品評分矩陣計算物品相似度，對用戶未評分過的物品進行預測；
（5）產(chǎn)生前n個評分值高的物品，返回編號并預測評分值。

1.2、PQ分解

SVD計算之前需要先把評分矩陣A補全，將稀疏矩陣變?yōu)槌砻芫仃嚕@樣就會帶來一些問題：1. 稠密矩陣需要耗費巨大的存儲空間；2. SVD計算復雜度很高，在大規(guī)模稠密矩陣上計算不現(xiàn)實。隱語義模型也是基于矩陣分解的，但是是將原始矩陣分解成兩個矩陣相乘的形式：
A=P Q^{*}
其中P為用戶因子矩陣，Q為物品因子矩陣。
通常上式不會精確相等，需要最小化二者之間的差異，可通過如下?lián)p失函數(shù)來表達：
\min \left(c_{i j}\left\|r_{i j}-\sum_{i=1}^{K} p_{i k} q_{k j}\right\|_{2}^{2}+\beta\left\|p_{i}\right\|^{2}+\gamma\left\|q_{j}\right\|^{2}\right)
其中r_{ij}表示用戶i對物品j的評分交互，1表示有交互，0表示無交互，c_{ij}表示用戶偏愛某個商品的置信參數(shù)，交互次數(shù)多權(quán)重就會增加，如果用d_{ij}表示交互次數(shù)的話，則可表示為c_{ij}=1+\alpha d_{ij}。
通過上述方法將協(xié)同過濾問題轉(zhuǎn)化為了一個優(yōu)化問題，求解上述損失函數(shù)通常采用交替最小二乘法(alternating least squares) ，計算過程如下：
（1）隨機初始化Q，對上式中p_i求偏導，令導數(shù)為0，得到當前最優(yōu)解p_i
\nabla_{p_i} \text {loss}=\frac{\partial \operatorname{loss}}{\partial p_{i}}=-2c_{ij}\left(r_{i j}-\sum_{i=1}^{K} p_{i k} q_{k j}\right) q_{k j}+2\beta p_{i}
（2）固定p，對上式q_j求偏導，令導數(shù)為0，得到當前最優(yōu)解q_j
\nabla_{q_j} \text {loss}=\frac{\partial \operatorname{loss}}{\partial q_{j}}=-2c_{ij}\left(r_{i j}-\sum_{i=1}^{K} p_{i k} q_{k j}\right) p_{ik}+2\gamma q_{j}
（3）固定q，對上式中p_i求偏導，令導數(shù)為0，得到當前最優(yōu)解p_i
（4）重復以上（2）到（3），直至達到迭代次數(shù)或收斂
\begin{array}{l}{p_{i k}=p_{i k}-\nabla_{p_i} l o s s} \\ {q_{k j}=q_{k j}-\nabla_{q_j} l o s s}\end{array}

二、算法實現(xiàn)

1、SVD的實現(xiàn)與說明

為簡明說明SVD的作用過程，采用10\times 11維的用戶評分矩陣，行代表用戶，列代表物品，數(shù)值代表評分，未評分值為0。

import numpy as np
def load_data():
    return [[0,0,1,0,0,2,0,0,0,0,5],
            [0,0,0,5,0,3,0,0,0,0,3],
            [0,0,0,0,4,1,0,1,0,4,0],
            [3,3,4,0,0,0,0,2,2,0,0],
            [5,4,2,0,0,0,0,5,5,0,0],
            [0,0,0,0,5,0,1,0,0,0,0],
            [4,1,4,0,0,0,0,4,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],
            [1,0,0,4,0,0,0,1,2,0,0]
            ]
data = load_data()
mat = np.mat(data)
原始數(shù)據(jù)
U,Sigma,VT = np.linalg.svd(mat)

rate = sum(Sigma[0:4]**2)/sum(Sigma**2)
rawdata = U[:,:10]*np.mat(np.diag(Sigma[:10]))*VT[:10,:]
recondata = U[:,:4]*np.mat(np.diag(Sigma[:4]))*VT[:4,:]

進行SVD分解，可以得到U， \Sigma ，V^{*}三個矩陣，\Sigma值如下：

Sigma

可見前4個值能量占比為 ，說明了SVD的降維作用，下表分別為全10個奇異值的重構(gòu)表和前4個奇異值的重構(gòu)表，可以看出后者能夠較好地代表前者。
全10個奇異值的重構(gòu)表

前4個奇異值的重構(gòu)表

即將物品的評分矩陣映射到低維空間，亦即矩陣的轉(zhuǎn)置，如下：
降維后的物品評分矩陣

2、SVD推薦算法的實現(xiàn)

數(shù)據(jù)加載與相似度計算函數(shù)
定義幾種相似度計算方法，包括Cosine相似度、歐幾里得距離、皮爾遜相關(guān)系數(shù)，本文采用Cosine相似度。

import data
import numpy as np

def cos_sim(X,Y):
    num = float(X.T*Y)
    denum = np.linalg.norm(X)*np.linalg.norm(Y)
    return 0.5+0.5*(num/denum)
def eclud_sim(X,Y):
    return 1.0/(1.0+np.linalg.norm(X-Y))
def pears_sim(X,Y):
    if len(X)<3:
        return 1.0
    return 0.5+0.5*np.corrcoef(X,Y,rowvar=0)[0][1]

SVD評分估計
基于矩陣奇異值分解轉(zhuǎn)換的商品評價估計，實現(xiàn)過程的詳述見注釋

def svd_estimate(data,user,sim_measure,item):
    n = data.shape[1]   # 列維度，物品數(shù)量
    sim_total,rate_sim_total = 0.0,0.0  # 相似度初始化
    
    U,Sigma,VT = np.linalg.svd(data)   #SVD分解
    low_dim = data.T * U[:,:4] * np.mat(np.diag(Sigma[:4])).I  # 將數(shù)據(jù)降到低維空間
    for j in range(n):  #對于給定用戶，循環(huán)所有物品，計算與item的相似度
        user_rating = data[user,j]  #用戶user對物品j的評分
        if user_rating == 0 or j == item:  # 未評價 或 item本身
            continue
        similarity = sim_measure(low_dim[item,:].T,low_dim[j,:].T)  #相似度計算
        print ('%d and %d similarity is:%f'%(item,j,similarity))
        
        sim_total += similarity  #相似度求和
        rate_sim_total += similarity*user_rating  #對相似度及評分值的乘積求和
    if sim_total == 0:
        return 0 
    else:
        return rate_sim_total/sim_total

基于SVD進行推薦
尋找未評級的物品，對給定用戶建立一個未評分物品列表，并計算評價值，進而推薦

def recommend(data,user,N=3,sim_measure=cos_sim,est_method=svd_estimate):
    unrated_item = np.nonzero(data[user,:].A == 0)[1]  #未評價的物品
    if len(unrated_item) == 0:
        return ('you rated everything')
    print(unrated_item)
    item_score = []    
    for item in unrated_item:  #在未評價的物品中
        estimate_score = est_method(data,user,sim_measure,item)  #計算評價值
        item_score.append((item,estimate_score))  #記錄商品及對應評價值
    return sorted(item_score,key=lambda x: x[1],reverse=True)[:N]  #推薦前N個未評價物品

結(jié)果分析

data = np.mat(data.load_data())
result = recommend(data,2,N=3,sim_measure=cos_sim,est_method=svd_estimate)
print(result)

對于第2號用戶，[0,0,0,0,4,1,0,1,0,4,0]，其未評價的列表為[ 0~1~2~3~6~8~10]，則可計算得到未評價物品與所有已評價物品的相似度為：

0 and 4 similarity is:0.481378
0 and 5 similarity is:0.457935
0 and 7 similarity is:0.986661
0 and 9 similarity is:0.481274
1 and 4 similarity is:0.488477
1 and 5 similarity is:0.453733
1 and 7 similarity is:0.973832
1 and 9 similarity is:0.489637
2 and 4 similarity is:0.461096
2 and 5 similarity is:0.587373
2 and 7 similarity is:0.825805
2 and 9 similarity is:0.479893
3 and 4 similarity is:0.476120
3 and 5 similarity is:0.693686
3 and 7 similarity is:0.545381
3 and 9 similarity is:0.487154
6 and 4 similarity is:0.874726
6 and 5 similarity is:0.869111
6 and 7 similarity is:0.526060
6 and 9 similarity is:0.906349
8 and 4 similarity is:0.481115
8 and 5 similarity is:0.445549
8 and 7 similarity is:0.980209
8 and 9 similarity is:0.477279
10 and 4 similarity is:0.447311
10 and 5 similarity is:0.933246
10 and 7 similarity is:0.453173
10 and 9 similarity is:0.496646

對所有未評分物品的評分為：

[(0, 2.1996914641365213), (1, 2.219755646468587), (2, 2.1991365553488067), (3, 2.3121588279962424), (6, 2.6822454316204456), (8, 2.205955763398433), (10, 2.2151987747133908)]

推薦其中的前三個：

[(6, 2.6822454316204456), (3, 2.3121588279962424), (1, 2.219755646468587)]

3、PQ分解推薦算法的實現(xiàn)

按照上述算法實現(xiàn)PQ分解的過程如下：

def matrix_factorization(matrix,k,lr):
    matrix = np.mat(matrix)
    m,n = matrix.shape
    P = np.mat(np.random.random((m,k)))
    Q = np.mat(np.random.random((k,n)))
    loss = 1.0
    epoch = 0
    while loss>=0.0005 and epoch<=epochs:
        loss = 0.0
        for i in range(m):
            for j in range(n):
                r = matrix[i,j]
                r_ = 0
                l2_p,l2_q = 0,0
                for t in range(k):
                    r_ += P[i,t]*Q[t,j]
                    l2_p += P[i,t]**2
                    l2_q += Q[t,j]**2
                e = r-r_
                loss += e**2+beta*l2_p+gamma*l2_q
                for t in range(k):
                    P[i,t] += lr*(2*e*Q[t,j]-2*beta*P[i,t])
                    Q[t,j] += lr*(2*e*P[i,t]-2*gamma*Q[t,j])
        epoch += 1
    return P,Q

設(shè)置參數(shù)并對比分解后復原的結(jié)果原數(shù)據(jù)的差異

beta = 0.001
gamma = 0.001
epochs = 20000
data = np.mat(data.load_data())
P,Q = matrix_factorization(data,10,0.002)
result = P*Q
print(P*Q)

可見當k=10時，與原數(shù)據(jù)已十分接近，k=4時也比較接近，說明了矩陣分解能夠表征原數(shù)據(jù)。


k=10時的結(jié)果

k=4時的結(jié)果

另外可以看出P,Q矩陣分別從橫軸和縱軸提取了原矩陣的信息，進而可利用Q矩陣替代上文的V矩陣的作用而進行推薦，在此不予贅述。


P值

Q值

參考資料

[1]. https://blog.csdn.net/xiaoxiaowenqiang/article/details/78076984
[2]. 推薦系統(tǒng)與深度學習. 黃昕等. 清華大學出版社. 2019.
[3]. 推薦系統(tǒng)算法實踐. 黃美靈. 電子工業(yè)出版社. 2019.
[4]. 推薦系統(tǒng)算法. 項亮. 人民郵電出版社. 2012.
[5]. 美團機器學習實踐. 美團算法團隊. 人民郵電出版社. 2018.
[6]. https://blog.csdn.net/recall_tomorrow/article/details/80218051

花萼樓前雨露新，長安城里太平人?！?張說《十五日夜御前口號踏歌詞二首》

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容