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

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

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

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

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

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

按照反饋的方向分，可以分為正反饋和負(fù)反饋。正反饋指用戶的行為傾向于指用戶喜歡該物品，負(fù)反饋指用戶的行為傾向于指用戶不喜歡該物品。在顯性反饋中，很容易區(qū)分一個(gè)用戶行為是正反饋還是負(fù)反饋，而在隱性反饋行為中，就相對(duì)比較難以確定。

一般來(lái)說(shuō)，不同的數(shù)據(jù)集包含不同的行為，目前比較有代表性的數(shù)據(jù)集有下面幾個(gè)：

• 無(wú)上下文信息的隱性反饋數(shù)據(jù)集： 每一條行為記錄僅僅包含用戶ID和物品ID。
• 無(wú)上下文信息的顯性反饋數(shù)據(jù)集： 每一條記錄包含用戶ID、物品ID和用戶對(duì)物品的評(píng)分；
• 有上下文信息的隱性反饋數(shù)據(jù)集： 每一條記錄包含用戶ID、物品ID和用戶對(duì)物品產(chǎn)生行為的時(shí)間戳；
• 有上下文信息的顯性反饋數(shù)據(jù)集： 每一條記錄包含用戶ID、物品ID和用戶對(duì)物品的評(píng)分和評(píng)分行為發(fā)生的時(shí)間戳。

用戶行為分析

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

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

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

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

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

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

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

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

基于鄰域的算法

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

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

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

1.基礎(chǔ)算法

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

• 找到和目標(biāo)用戶興趣相似的用戶集合；
• 找到這個(gè)集合中的用戶喜歡的，且目標(biāo)用戶沒(méi)有聽(tīng)說(shuō)過(guò)的物品推薦給目標(biāo)用戶。

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

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

余弦相似度計(jì)算：

余弦相似度

2.基于相似度計(jì)算的改進(jìn)

原來(lái)的相似度計(jì)算公式，如余弦相似度計(jì)算方法太過(guò)于粗糙。如果兩個(gè)用戶對(duì)冷門物品采取過(guò)同樣的行為更能說(shuō)明他們興趣的相似度。John S. Breese在論文中提出如下公式，根據(jù)用戶行為計(jì)算用戶的興趣相似度：

計(jì)算公式

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

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

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

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

1.基礎(chǔ)算法

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

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

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

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

物品相似度

其中，分母|N(i)|是喜歡物品i的用戶數(shù)，分子是同事喜歡物品i和物品j的用戶數(shù)。
但是，上述公式存在一個(gè)問(wèn)題，如果物品j很熱門，很多人都喜歡，那么Wij就會(huì)很大，接近于1.因此，該公式會(huì)造成任務(wù)物品都會(huì)和熱門的物品有很大的相似度，對(duì)致力于挖掘長(zhǎng)尾信息的推薦系統(tǒng)來(lái)說(shuō)不是一個(gè)好的特性。為了避免推薦出熱門的物品，使用下面的公式：

新計(jì)算公式

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

從上面的定義可以看到，在協(xié)同過(guò)濾中兩個(gè)物品產(chǎn)生相似度是因?yàn)樗鼈児餐缓芏嘤脩粝矚g，也就是說(shuō)每個(gè)用戶都可以通過(guò)他們的歷史興趣列表給物品”貢獻(xiàn)“相似度。

ItemCF算法計(jì)算物品相似度時(shí)，先建立一個(gè)用戶-物品倒排表，然后對(duì)于每個(gè)用戶，將他物品列表中的物品量量在共現(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通過(guò)如下公式計(jì)算用戶u對(duì)一個(gè)物品j的興趣：

用戶u對(duì)物品i的興趣計(jì)算公式

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

def Recommendation(train, user_id, W, K):
    rank = dict()
    ru = train[user_id]#用戶喜歡物品字典，物品：rui(用戶u對(duì)物品i的興趣，默認(rèn)為1)
    for i, rui in ru.items():
        # 選擇物品i的相似度矩陣，并由大到小排序；然后選擇前K個(gè)物品
        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算法的一個(gè)優(yōu)勢(shì)是可以提供推薦解釋，即利用用戶歷史上喜歡的物品為現(xiàn)在的推薦結(jié)果進(jìn)行解釋。帶解釋的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

對(duì)不同 K 值的測(cè)量可以看到：

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

2.用戶活躍度對(duì)物品相似度的影響

在協(xié)同過(guò)濾中兩個(gè)物品蒼生相似度是因?yàn)樗鼈児餐霈F(xiàn)在很多用戶的興趣列表中。換句話說(shuō)，每個(gè)用戶的興趣列表都對(duì)物品的相似度產(chǎn)生貢獻(xiàn)。但每個(gè)用戶的貢獻(xiàn)不應(yīng)該都相同。

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

物品相似度修正公式

N(i)、N(j)物品i，j的流行度；u是同時(shí)購(gòu)買物品i和物品j的用戶，N(u)是用戶喜歡的物品數(shù)[用來(lái)表示用戶u的活躍度]。上面公式只是對(duì)活躍用戶做了一種軟性的懲罰。
但對(duì)于很多過(guò)于活躍的用戶，為了避免相似度矩陣過(guò)于稠密，在實(shí)際運(yùn)算中一般直接忽略他的興趣列表，不將其納入到相似度計(jì)算的數(shù)據(jù)集中。ItemCF-IUF實(shí)現(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':

歸一化相似度矩陣公式

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

UserCF和ItemCF的綜合比較

UserCF的推薦結(jié)果著重于反應(yīng)和用戶興趣相似的小群體的熱點(diǎn)，ItemCF的推薦結(jié)果著重于維系用戶的歷史興趣。換句話說(shuō)，UserCF的推薦更社會(huì)化，反映了用戶所在的小型群體中物品的熱門程度，而ItemCF的推薦更加個(gè)性化，反映了用戶自己的興趣傳承。

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

UserCF和ItemCF優(yōu)缺點(diǎn)對(duì)比.

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

隱語(yǔ)義模型

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

1. 基礎(chǔ)算法

隱語(yǔ)義模型的核心思想是通過(guò)隱含特征(latent factor)聯(lián)系用戶興趣和物品。簡(jiǎn)單說(shuō)就是對(duì)物品的興趣分類，對(duì)于用戶，首先確定他的興趣分類，然后從分類中選擇他可能喜歡的物品?；谂d趣分類的方法大概解決3個(gè)問(wèn)題：

• 如何給物品分類？
• 如何確定用戶對(duì)哪些類的物品感興趣，以及感興趣的程度？
• 對(duì)于一個(gè)給定的類，選擇哪些屬于這個(gè)類的物品推薦給用戶，以及如何確定這些物品在一個(gè)類中的權(quán)重？

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

• 分類來(lái)源于對(duì)用戶行為的統(tǒng)計(jì)，能代表各種用戶的看法；
• 通過(guò)指定最終分類的個(gè)數(shù)，能控制分類的粒度；數(shù)目越大，分類粒度越細(xì)；
• 能給一個(gè)物品多個(gè)分類：隱語(yǔ)義模型計(jì)算物品屬于每個(gè)類的權(quán)重，不是硬性地被分到某個(gè)類中；
• 帶維度屬性，屬于多維度或同維度；
• 可以確定物品在某個(gè)分類中的權(quán)重：通過(guò)統(tǒng)計(jì)用戶行為決定物品在每個(gè)類中的權(quán)重；

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

LFM通過(guò)如下公式計(jì)算用戶u對(duì)物品i的興趣：

興趣

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

推薦系統(tǒng)的用戶行為分為顯性反饋和隱性反饋。LFM在顯性反饋數(shù)據(jù)(評(píng)分?jǐn)?shù)據(jù))上解決評(píng)分預(yù)測(cè)問(wèn)題并達(dá)到了很好的精度。如果是隱性數(shù)據(jù)集，這種數(shù)據(jù)集的特點(diǎn)是只有正樣本(用戶喜歡什么物品)，沒(méi)有負(fù)樣本(用戶對(duì)什么物品不感興趣)。

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

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

• 對(duì)每個(gè)用戶，要保證正負(fù)樣本的平衡(數(shù)目相似)；
• 對(duì)每個(gè)用戶采樣負(fù)樣本時(shí)，要選取那些很熱門，而用戶卻沒(méi)有行為的物品。

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

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

損失函數(shù)

其中，后兩項(xiàng)是用來(lái)防止過(guò)擬合的正則化項(xiàng)，lambda可以通過(guò)實(shí)驗(yàn)獲得。通過(guò)梯度下降算法對(duì)損失函數(shù)進(jìn)行優(yōu)化求解，得到兩個(gè)參數(shù)指。

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

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

通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，radio對(duì)LFM的性能影響最大。

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

LFM是一種基于機(jī)器學(xué)習(xí)的方法，具有比較好的理論基礎(chǔ)。和基于鄰域的方法相比，各有優(yōu)缺點(diǎn)。

• 理論基礎(chǔ) LFM具有比較好的理論基礎(chǔ)，是一種學(xué)習(xí)方法，通過(guò)優(yōu)化一個(gè)設(shè)定的指標(biāo)建立最優(yōu)的模型?；卩徲虻姆椒ǜ嗟氖且环N基于統(tǒng)計(jì)的方法，并沒(méi)有學(xué)習(xí)過(guò)程。
• 離線計(jì)算的空間復(fù)雜度 基于鄰域的方法需要維護(hù)一張離線的相關(guān)表。

基于圖的模型

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

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

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

二分圖模型

2.基于圖的推薦算法

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

度量圖中兩個(gè)頂點(diǎn)之間相關(guān)性的方法有很多，但一般來(lái)說(shuō)圖中頂點(diǎn)的相關(guān)性主要取決于下面3個(gè)因素：

• 兩個(gè)頂點(diǎn)之間的路徑數(shù)；
• 兩個(gè)頂點(diǎn)之間路徑的長(zhǎng)度；
• 兩個(gè)頂點(diǎn)之間的路徑經(jīng)過(guò)的頂點(diǎn)。

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

• 兩個(gè)頂點(diǎn)之間有很多路徑相連；
• 連接兩個(gè)頂點(diǎn)之間的路徑長(zhǎng)度都比較短；
• 連接兩個(gè)頂點(diǎn)之間的路徑不會(huì)經(jīng)過(guò)出度比較大的頂點(diǎn)。

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

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

表示公式如：

游走公式

alpha游走概率，1-alpha停留概率；

代碼實(shí)現(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é)點(diǎn)i和它的出邊尾節(jié)點(diǎn)集合ri
        for i, ri in G.items():
        #取i->j邊的尾節(jié)點(diǎn)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算法可以通過(guò)隨機(jī)游走進(jìn)行比較好的理論解釋，但該算法在時(shí)間復(fù)雜度上有明顯的缺點(diǎn)。因?yàn)樵跒槊總€(gè)用戶進(jìn)行推薦時(shí)，都需要在整個(gè)用戶物品二分圖上進(jìn)行迭代，知道整個(gè)圖上的每個(gè)頂點(diǎn)的PR值收斂。這一過(guò)程時(shí)間復(fù)雜度非常高，不僅無(wú)法在線提供實(shí)時(shí)推薦，甚至離線生成推薦結(jié)果也很耗時(shí)。

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