基于用戶行為分析的推薦算法是個性化推薦系統(tǒng)的重要算法，一般將這種類型的算法稱為協(xié)同過濾算法贝攒。協(xié)同過濾就是指用戶可以齊心協(xié)力硅急，通過不斷地和網(wǎng)站互動，使自己的推薦列表能夠不斷過濾掉自己不感興趣的物品爆惧，從而越來越滿足自己的需求。

用戶行為數(shù)據(jù)簡介

用戶行為數(shù)據(jù)在網(wǎng)站上最簡單的存在形式就是日志锨能。網(wǎng)站在運行過程中都產(chǎn)生大量原始日志raw log扯再，并將其存儲在文件系統(tǒng)中芍耘。很多互聯(lián)網(wǎng)業(yè)務(wù)會把多種原始日志按照用戶行為匯總成會話日志session log，其中每個會話表示一次用戶行為和對應(yīng)的服務(wù)熄阻。會話日志通常存儲在分布式數(shù)據(jù)倉庫中斋竞，如支持離線分析的Hadoop Hive和支持在線分析的Google Dremel。

用戶行為在個性化推薦系統(tǒng)中一般分兩種---顯性反饋行為(explicit feedback)和隱性反饋行為(implicit feedback)：

• 顯性反饋行為： 包括用戶明確表示對物品喜好的行為秃殉。不同網(wǎng)站收集顯性反饋行為的主要方式是評分和喜歡/不喜歡坝初。
• 隱性反饋行為： 指那些不能明確反應(yīng)用戶喜好的行為。最具代表性的隱性反饋行為就是頁面瀏覽行為钾军。用戶瀏覽一個物品的頁面并不代表用戶一定喜歡這個頁面展示的物品,比如可能因為這個頁面鏈接顯示在首頁,用戶更容易點擊它而已脖卖。相比顯性反饋,隱性反饋雖然不明確,但數(shù)據(jù)量更大。

顯性反饋數(shù)據(jù)和隱性反饋數(shù)據(jù)的比較.

按照反饋的方向分巧颈，可以分為正反饋和負(fù)反饋畦木。正反饋指用戶的行為傾向于指用戶喜歡該物品，負(fù)反饋指用戶的行為傾向于指用戶不喜歡該物品砸泛。在顯性反饋中十籍，很容易區(qū)分一個用戶行為是正反饋還是負(fù)反饋，而在隱性反饋行為中唇礁，就相對比較難以確定勾栗。

一般來說，不同的數(shù)據(jù)集包含不同的行為盏筐，目前比較有代表性的數(shù)據(jù)集有下面幾個：

• 無上下文信息的隱性反饋數(shù)據(jù)集： 每一條行為記錄僅僅包含用戶ID和物品ID围俘。
• 無上下文信息的顯性反饋數(shù)據(jù)集： 每一條記錄包含用戶ID、物品ID和用戶對物品的評分琢融；
• 有上下文信息的隱性反饋數(shù)據(jù)集： 每一條記錄包含用戶ID界牡、物品ID和用戶對物品產(chǎn)生行為的時間戳；
• 有上下文信息的顯性反饋數(shù)據(jù)集： 每一條記錄包含用戶ID漾抬、物品ID和用戶對物品的評分和評分行為發(fā)生的時間戳宿亡。

用戶行為分析

在利用用戶行為數(shù)據(jù)設(shè)計推薦算法之前，研究人員首先需要對用戶行為數(shù)據(jù)進行分析纳令，了解數(shù)據(jù)中蘊含的一般規(guī)律挽荠，才能對算法的設(shè)計起到指導(dǎo)作用[相當(dāng)與ML中數(shù)據(jù)探索]。

用戶活躍度和物品流行度的分布

[物品的流行度指對物品產(chǎn)生過行為的用戶總數(shù)]

很多互聯(lián)網(wǎng)數(shù)據(jù)的研究發(fā)現(xiàn)平绩，互聯(lián)網(wǎng)上的很多數(shù)據(jù)分布都滿足一種稱為Power Law的分布圈匆，這個分布在互聯(lián)網(wǎng)領(lǐng)域也稱為長尾分布。

很多研究人員發(fā)現(xiàn)捏雌，用戶行為數(shù)據(jù)也蘊含這種長尾分布的規(guī)律跃赚。
物品流行度和用戶活躍度都近似于長尾分布。

用戶活躍度和物品流行度的關(guān)系

僅僅基于用戶行為數(shù)據(jù)設(shè)計的推薦算法一般稱為協(xié)同過濾算法腹忽。協(xié)同過濾算法分為基于鄰域的方法(neighborhood-based)来累、隱語義模型(latent factor model)砚作、基于圖的隨機游走算法(random walk on graph)等窘奏。在這些方法中嘹锁，最著名的、在業(yè)界得到最廣泛應(yīng)用的算法是基于鄰域的方法着裹，而基于鄰域的方法主要包含下面兩種算法：

• 基于用戶的協(xié)同過濾算法： 給用戶推薦和他興趣相似的其他用戶喜歡的物品领猾；
• 基于物品的協(xié)同過濾算法： 給用戶推薦和他之前喜歡的物品相似的物品。

基于鄰域的算法

基于鄰域的算法分為兩類：一類是基于用戶的協(xié)同過濾算法骇扇，另一類是基于物品的協(xié)同過濾算法摔竿。

基于用戶的協(xié)同過濾算法

基于用戶的協(xié)同過濾算法是推薦系統(tǒng)中最古老的算法。

1.基礎(chǔ)算法

基于用戶的協(xié)同過濾算法主要包括兩個步驟：

• 找到和目標(biāo)用戶興趣相似的用戶集合少孝；
• 找到這個集合中的用戶喜歡的继低，且目標(biāo)用戶沒有聽說過的物品推薦給目標(biāo)用戶。

步驟一的關(guān)鍵在于計算兩個用戶的興趣相似度稍走。協(xié)同過濾算法主要利用行為的相似度計算興趣的相似度袁翁。給定用戶u和用戶v，令N(u)表示用戶u曾經(jīng)有過正反饋的物品集合婿脸，令N(v)為用戶v曾經(jīng)有過正反饋的物品集合粱胜。可以通過Jaccard公式簡單計算u和v的興趣相似度：

[圖片上傳失敗...(image-b324e4-1541149645358)]

余弦相似度計算：

余弦相似度

2.基于相似度計算的改進

原來的相似度計算公式狐树，如余弦相似度計算方法太過于粗糙焙压。如果兩個用戶對冷門物品采取過同樣的行為更能說明他們興趣的相似度。John S. Breese在論文中提出如下公式抑钟，根據(jù)用戶行為計算用戶的興趣相似度：

計算公式

其中涯曲，N(i)表示物品i的流行度。公式懲罰了用戶u和v共同興趣列表中熱門物品對他們相似度的影響在塔。

基于用戶的協(xié)同過濾算法的缺點：首先掀抹，隨著網(wǎng)站的用戶數(shù)目越來越大，計算用戶興趣相似度矩陣越來越困難心俗，其運算時間復(fù)雜度和空間復(fù)雜度的增長和用戶的增長近似于平方關(guān)系傲武；其次，基于用戶的協(xié)同過濾很難對推薦結(jié)果做出解釋城榛。

基于物品的系統(tǒng)過濾算法

基于物品的協(xié)同過濾item-based collaborative filtering算法是目前業(yè)界應(yīng)用最多的算法揪利。

1.基礎(chǔ)算法

基于物品的協(xié)同過濾算法(簡稱ItemCF)給用戶與推薦那些和他們之前喜歡的物品相似的物品。ItemCF算法并不利用物品的內(nèi)容屬性計算物品之間的相似度狠持，主要通過分析用戶的行為記錄就是那物品之間的相似度疟位。該算法認(rèn)為，物品A和物品B具有很大的相似性是因為喜歡物品A的用戶大都也喜歡物品B喘垂。

基于物品的協(xié)同過濾算法主要分為兩步：

• 計算物品之間的相似度甜刻；
• 根據(jù)物品的相似度和用戶的歷史行為給用戶生成推薦列表绍撞。

購買了該商品的用戶也經(jīng)常經(jīng)常購買的其他商品，從這句話的定義出發(fā)得院，給出定義物品相似度的計算公式：

物品相似度

其中傻铣，分母|N(i)|是喜歡物品i的用戶數(shù)，分子是同事喜歡物品i和物品j的用戶數(shù)祥绞。
但是非洲，上述公式存在一個問題，如果物品j很熱門蜕径，很多人都喜歡两踏，那么Wij就會很大，接近于1.因此兜喻，該公式會造成任務(wù)物品都會和熱門的物品有很大的相似度梦染，對致力于挖掘長尾信息的推薦系統(tǒng)來說不是一個好的特性。為了避免推薦出熱門的物品朴皆，使用下面的公式：

新計算公式

這個公式懲罰了物品j的權(quán)重帕识，因此減輕了熱門物品會和很多物品相似的可能性。

從上面的定義可以看到车荔，在協(xié)同過濾中兩個物品產(chǎn)生相似度是因為它們共同被很多用戶喜歡渡冻，也就是說每個用戶都可以通過他們的歷史興趣列表給物品”貢獻“相似度。

ItemCF算法計算物品相似度時忧便，先建立一個用戶-物品倒排表族吻，然后對于每個用戶，將他物品列表中的物品量量在共現(xiàn)矩陣C中加1.詳細(xì)代碼：

def ItemSimilarity(train):#train是用戶-物品倒排表
    C = dict()#物品i,j共現(xiàn)矩陣,用字典表示;
    N = dict()#物品i的流行度--喜歡物品i的用戶數(shù)目
    for user, items in train.items():
        for i in items:
            N[i] += 1
            for j in items:
                if i != j:
                    C[i][j] = C[i].get(j, 0) + 1
    W = dict()#物品相似度矩陣 字典
    for i, related_items in C.items():
        for j, cij in related_items.items():
            W[i][j] = cij / math.sqrt(N[i]*N[j])

    return W

在得到物品之間的相似度后珠增，ItemCF通過如下公式計算用戶u對一個物品j的興趣：

用戶u對物品i的興趣計算公式

這里N(u)是用戶喜歡的物品集合超歌，S(j,K)是和物品j最相似的K個物品的集合，wji是物品j和i的相似度蒂教，rui是用戶u對物品i的興趣巍举。(對于隱反饋數(shù)據(jù)集，如果用戶u對物品i有過行為凝垛，即可令rui=1.) 該公式的含義是：和用戶歷史上感興趣的物品[N(u)里]越相似的物品懊悯，越有可能在用戶的推薦列表中獲得比較高的排名。 [在S集合中篩選掉已經(jīng)喜歡的物品]實現(xiàn)代碼：

def Recommendation(train, user_id, W, K):
    rank = dict()
    ru = train[user_id]#用戶喜歡物品字典梦皮，物品：rui(用戶u對物品i的興趣炭分，默認(rèn)為1)
    for i, rui in ru.items():
        # 選擇物品i的相似度矩陣，并由大到小排序剑肯；然后選擇前K個物品
        si = sorted(W[i].items(),key=lambda a:a[1],reverse=True)
        for j, wij in si[:K]:
            if j in ru:#排除已經(jīng)喜歡的物品
                continue
            rank[j] += wij * rui

    return rank

ItemCF算法的一個優(yōu)勢是可以提供推薦解釋捧毛，即利用用戶歷史上喜歡的物品為現(xiàn)在的推薦結(jié)果進行解釋。帶解釋的ItemCF算法：

def Recommendation(train, user_id, W, K):
    rank = dict()
    reason = dict()
    ru = train[user_id]
    for i, rui in ru.items():
        si = sorted(W[i].items(),key=lambda a:a[1], reverse=True)
        for j, wij in si[:K]:
            if j not in ru:
                rank[j] += wij * rui
                reason[j][i] = wij * rui
    return rank, reason

對不同 K 值的測量可以看到：

• 準(zhǔn)確率和召回率和 K 也不成線性關(guān)系;選擇合適的K對獲得最高精度是非常重要的；
• K 和流行度不完全正相關(guān)： 隨著K的增加呀忧，結(jié)果流行度會逐漸提高师痕，但當(dāng)K增加大到一定程度，流行度就不會再有明顯變化而账；
• K 增大會降低系統(tǒng)的覆蓋率胰坟。

2.用戶活躍度對物品相似度的影響

在協(xié)同過濾中兩個物品蒼生相似度是因為它們共同出現(xiàn)在很多用戶的興趣列表中。換句話說福扬，每個用戶的興趣列表都對物品的相似度產(chǎn)生貢獻腕铸。但每個用戶的貢獻不應(yīng)該都相同惜犀。

John S.Breese在論文中提出一個IUF(Inversr User Frequence)用戶活躍度對數(shù)的倒數(shù)的參數(shù)铛碑，他認(rèn)為活躍用戶對物品相似度的貢獻應(yīng)該小于不活躍的用戶,提出應(yīng)該增加IUF參數(shù)來修正物品相似度的計算公式：

物品相似度修正公式

N(i)、N(j)物品i虽界，j的流行度汽烦；u是同時購買物品i和物品j的用戶，N(u)是用戶喜歡的物品數(shù)[用來表示用戶u的活躍度]莉御。上面公式只是對活躍用戶做了一種軟性的懲罰撇吞。
但對于很多過于活躍的用戶，為了避免相似度矩陣過于稠密礁叔，在實際運算中一般直接忽略他的興趣列表牍颈，不將其納入到相似度計算的數(shù)據(jù)集中。ItemCF-IUF實現(xiàn)：

def ItemSimilarity(train):
    C = dict()#分子
    N = dict()#物品i的流行度
    for u, items in train.items():
        for i in items:
            N[i] += 1
            for j in items:
                if i != j:
                    C[i][j] += 1 / math.log(1 + len(items)*1.0)
    W = dict()#相似度矩陣
    for i, related_items in C.items():
        for j, cij in related_items.items():
            W[i][j] = cij / math.sqrt(N[i] * N[j])

    return W

3.物品相似度的歸一化

在研究匯中發(fā)現(xiàn)如果將ItemCF的相似度矩陣按最大值歸一化琅关，可以提高推薦的準(zhǔn)確率煮岁。其研究表明，如果已經(jīng)得到了物品相似度矩陣w涣易，可以用如下公式得到歸一化之后的相似度矩陣w':

歸一化相似度矩陣公式

按照行進行歸一化画机。歸一化的好處不僅僅在于增加推薦的準(zhǔn)確度，還可以提高推薦的覆蓋率和多樣性新症。

UserCF和ItemCF的綜合比較

UserCF的推薦結(jié)果著重于反應(yīng)和用戶興趣相似的小群體的熱點步氏，ItemCF的推薦結(jié)果著重于維系用戶的歷史興趣。換句話說徒爹，UserCF的推薦更社會化荚醒，反映了用戶所在的小型群體中物品的熱門程度，而ItemCF的推薦更加個性化隆嗅，反映了用戶自己的興趣傳承界阁。

從技術(shù)上考慮, UserCF 需要維護一個用戶相似度的矩陣,而 ItemCF 需要維護一個物品相似度矩陣。從存儲的角度說,如果用戶很多,那么維護用戶興趣相似度矩陣需要很大的空間,同理,如果物品很多,那么維護物品相似度矩陣代價較大榛瓮。

UserCF和ItemCF優(yōu)缺點對比.

離線實驗的性能在選擇推薦算法時病不起決定作用。首先應(yīng)該滿足產(chǎn)品的需求披泪，然后需要看實現(xiàn)代價纤子。

隱語義模型

LFM(latent factor model)隱語義模型，該算法最早在文本挖掘領(lǐng)域被提出款票，用于找到文本的隱含語義控硼。相關(guān)的名詞有LSI、pLSI艾少、LDA和Topic Model.

1. 基礎(chǔ)算法

隱語義模型的核心思想是通過隱含特征(latent factor)聯(lián)系用戶興趣和物品卡乾。簡單說就是對物品的興趣分類，對于用戶缚够，首先確定他的興趣分類幔妨，然后從分類中選擇他可能喜歡的物品〕逼浚基于興趣分類的方法大概解決3個問題：

• 如何給物品分類陶冷？
• 如何確定用戶對哪些類的物品感興趣，以及感興趣的程度毯辅？
• 對于一個給定的類埂伦，選擇哪些屬于這個類的物品推薦給用戶，以及如何確定這些物品在一個類中的權(quán)重思恐？

這里的對物品分類的問題沾谜，可以用隱含語義分析技術(shù)較好地解決。它基于用戶行為統(tǒng)計做分類胀莹，和專家標(biāo)記相比：

• 分類來源于對用戶行為的統(tǒng)計基跑，能代表各種用戶的看法；
• 通過指定最終分類的個數(shù)描焰，能控制分類的粒度媳否；數(shù)目越大栅螟，分類粒度越細(xì)；
• 能給一個物品多個分類：隱語義模型計算物品屬于每個類的權(quán)重篱竭，不是硬性地被分到某個類中力图；
• 帶維度屬性，屬于多維度或同維度掺逼；
• 可以確定物品在某個分類中的權(quán)重：通過統(tǒng)計用戶行為決定物品在每個類中的權(quán)重吃媒；

這些都是專家標(biāo)記不能或者很難做到的。

LFM通過如下公式計算用戶u對物品i的興趣：

興趣

公式中puk和qik是模型的參數(shù)吕喘，其中puk度量了用戶u的興趣和第k個隱類的關(guān)系赘那，而qik度量了第k個隱類和物品i之間的關(guān)系。
這兩個參數(shù)的計算方式需要一個訓(xùn)練集氯质，對于每個用戶u募舟，訓(xùn)練集里包含了用戶u喜歡的物品和不感興趣的物品，通過學(xué)習(xí)這個數(shù)據(jù)集病梢，就可以獲得上面的模型參數(shù)胃珍。

推薦系統(tǒng)的用戶行為分為顯性反饋和隱性反饋梁肿。LFM在顯性反饋數(shù)據(jù)(評分?jǐn)?shù)據(jù))上解決評分預(yù)測問題并達到了很好的精度蜓陌。如果是隱性數(shù)據(jù)集，這種數(shù)據(jù)集的特點是只有正樣本(用戶喜歡什么物品)吩蔑，沒有負(fù)樣本(用戶對什么物品不感興趣)钮热。

在隱性反饋數(shù)據(jù)集上應(yīng)用LFM解決TopN推薦的第一個關(guān)鍵問題就是如何給每個用戶生成負(fù)樣本。

對負(fù)樣本采樣時應(yīng)該遵循以下原則：

• 對每個用戶烛芬，要保證正負(fù)樣本的平衡(數(shù)目相似)隧期；
• 對每個用戶采樣負(fù)樣本時，要選取那些很熱門赘娄，而用戶卻沒有行為的物品仆潮。

一般認(rèn)為,很熱門而用戶卻沒有行為更加代表用戶對這個物品不感興趣。因為對于冷門的物品,用戶可能是壓根沒在網(wǎng)站中發(fā)現(xiàn)這個物品,所以談不上是否感興趣遣臼。

需要優(yōu)化的損失函數(shù)如下：

損失函數(shù)

其中性置，后兩項是用來防止過擬合的正則化項，lambda可以通過實驗獲得揍堰。通過梯度下降算法對損失函數(shù)進行優(yōu)化求解鹏浅，得到兩個參數(shù)指。

在LFM中屏歹，重要的參數(shù)有4個：

• 隱特征的個數(shù)F隐砸；
• 學(xué)習(xí)速率alpha；
• 正則化參數(shù)lambda蝙眶；
• 負(fù)樣本/正樣本比例radio季希。

通過實驗發(fā)現(xiàn)，radio對LFM的性能影響最大。

2.LFM和基于鄰域的方法的比較

LFM是一種基于機器學(xué)習(xí)的方法式塌，具有比較好的理論基礎(chǔ)武通。和基于鄰域的方法相比，各有優(yōu)缺點珊搀。

• 理論基礎(chǔ) LFM具有比較好的理論基礎(chǔ)冶忱，是一種學(xué)習(xí)方法，通過優(yōu)化一個設(shè)定的指標(biāo)建立最優(yōu)的模型境析∏羟梗基于鄰域的方法更多的是一種基于統(tǒng)計的方法，并沒有學(xué)習(xí)過程劳淆。
• 離線計算的空間復(fù)雜度 基于鄰域的方法需要維護一張離線的相關(guān)表链沼。

基于圖的模型

用戶行為很容易用二分圖表示，因此很多圖的算法都可以應(yīng)用到推薦系統(tǒng)中沛鸵。

1.用戶行為數(shù)據(jù)的二分圖表示

在研究基于圖的模型之前括勺，首先需要將用戶行為數(shù)據(jù)表示成圖的形式。這里討論用戶行為數(shù)據(jù)是由一系列二元組組成的曲掰，其中每個二元組(u,i)表示用戶u對物品i產(chǎn)生過行為疾捍；這種數(shù)據(jù)集很容易用一個二分圖表示。

二分圖模型

2.基于圖的推薦算法

在二分圖上給用戶進行個性化推薦栏妖。如果將個性化推薦算法放到二分圖模型上乱豆，那么給用戶u推薦物品的任務(wù)就可以轉(zhuǎn)換為度量用戶頂點vu和與vu沒有邊直接相連的物品節(jié)點在圖上的相關(guān)性，相關(guān)性越高的物品在推薦列表中的權(quán)重就越高吊趾。

度量圖中兩個頂點之間相關(guān)性的方法有很多宛裕，但一般來說圖中頂點的相關(guān)性主要取決于下面3個因素：

• 兩個頂點之間的路徑數(shù)；
• 兩個頂點之間路徑的長度论泛；
• 兩個頂點之間的路徑經(jīng)過的頂點揩尸。

相關(guān)性高的一堆頂點一般具有如下特征：

• 兩個頂點之間有很多路徑相連；
• 連接兩個頂點之間的路徑長度都比較短屁奏；
• 連接兩個頂點之間的路徑不會經(jīng)過出度比較大的頂點岩榆。

基于上面3個主要因素，設(shè)計了很多計算圖中頂點之間相關(guān)性的方法了袁。比如隨機游走PersonalRank算法朗恳。

假設(shè)要給用戶u進行個性化推薦，可以從用戶u對應(yīng)的節(jié)點vu開始在用戶物品二分圖上進行隨機游走载绿。游走到任何一個節(jié)點時粥诫，首先按照概率alpha決定是繼續(xù)游走，還是停止這次游走并從vu節(jié)點開始重新游走崭庸。如果決定繼續(xù)游走怀浆，那么就從當(dāng)前節(jié)點指向的節(jié)點中按照均勻分布隨機選擇一個節(jié)點作為游走下次經(jīng)過的節(jié)點谊囚。這樣，經(jīng)過很多次隨機游走后执赡，每個物品節(jié)點被訪問到的概率后收斂到一個數(shù)镰踏。最終的推薦列表中物品的權(quán)重就是物品節(jié)點的訪問概率。

表示公式如：

游走公式

alpha游走概率沙合，1-alpha停留概率奠伪；

代碼實現(xiàn)：

def PersonalRank(G, alpha, root, max_step):
    rank = dict()#推薦結(jié)果
    rank = {x : 0 for x in G.keys()}
    rank[root] = 1

    for k in range(max_step):
        tmp = {x : 0 for x in G.keys()}

        #取節(jié)點i和它的出邊尾節(jié)點集合ri
        for i, ri in G.items():
        #取i->j邊的尾節(jié)點j以及邊E(i,j)的權(quán)重wij, 邊的權(quán)重都為1，
            for j, wij in ri.items():
                if j not in tmp:
                    tmp[j] = 0
                tmp[j] += alpha * rank[i] / (1.0 * len(ri))
                if j == root:
                    tmp[j] += 1 - alpha
        rank = tmp

    return rank

雖然PersonalRank算法可以通過隨機游走進行比較好的理論解釋首懈，但該算法在時間復(fù)雜度上有明顯的缺點绊率。因為在為每個用戶進行推薦時，都需要在整個用戶物品二分圖上進行迭代究履，知道整個圖上的每個頂點的PR值收斂滤否。這一過程時間復(fù)雜度非常高，不僅無法在線提供實時推薦最仑，甚至離線生成推薦結(jié)果也很耗時藐俺。

為了解決PersonalRank每次都需要在全圖迭代并造成時間復(fù)雜度高的問題，給出兩種解決方法泥彤。第一種欲芹，減少迭代次數(shù)，在收斂之前就停止全景。會影響最終的精度耀石，但一般來說影響不會特別大；另一種就是從矩陣論出發(fā)爸黄，重新設(shè)計算法。