協同過濾和矩陣分解

Ⅰ 07_推薦系統演算法詳解

     基於人口統計學的推薦與用戶畫像、基於內容的推薦、基於協同過濾的推薦。

1、基於人口統計學的推薦機制( Demographic-based Recommendation)是一種最易於實現的推薦方法，它只是簡單的根據系統用戶的基本信息發現用戶的相關程度，然後將相似用戶喜愛的其他物品推薦給當前用戶。

2、對於沒有明確含義的用戶信息(比如登錄時間、地域等上下文信息)，可以通過聚類等手段，給用戶打上分類標簽。

3、對於特定標簽的用戶，又可以根據預設的規則(知識)或者模型，推薦出對應的物品。

4、用戶信息標簽化的過程一般又稱為 用戶畫像 ( User Profiling）。

（1）用戶畫像( User Profile)就是企業通過收集與分析消費者社會屬性、生活習慣、消費行為等主要信息的數據之後，完美地抽象出一個用戶的商業全貌作是企業應用大數據技術的基本方式。

（2）用戶畫像為企業提供了足夠的信息基礎，能夠幫助企業快速找到精準用戶群體以及用戶需求等更為廣泛的反饋信息。

（3）作為大數據的根基，它完美地抽象出一個用戶的信息全貌，為進一步精準、快速地分析用戶行為習慣、消費習慣等重要信息，提供了足夠的數據基礎。

1、 Content- based Recommendations(CB)根據推薦物品或內容的元數據，發現物品的相關性，再基於用戶過去的喜好記錄，為用戶推薦相似的物品。

2、通過抽取物品內在或者外在的特徵值,實現相似度計算。比如一個電影,有導演、演員、用戶標簽UGC、用戶評論、時長、風格等等，都可以算是特徵。

3、將用戶(user)個人信息的特徵(基於喜好記錄或是預設興趣標簽)，和物品(item)的特徵相匹配，就能得到用戶對物品感興趣的程度。在一些電影、音樂、圖書的社交網站有很成功的應用,有些網站還請專業的人員對物品進行基因編碼/打標簽(PGC）。

4、 相似度計算：

5、對於物品的特徵提取——打標簽(tag)

        - 專家標簽(PGC）

        - 用戶自定義標簽(UGC)

        - 降維分析數據,提取隱語義標簽(LFM)

     對於文本信息的特徵提取——關鍵詞

        - 分詞、語義處理和情感分析(NLP)

        - 潛在語義分析(LSA）

6、 基於內容推薦系統的高層次結構

7、 特徵工程

（1）特徵( feature)：數據中抽取出來的對結果預測有用的信息。

         特徵的個數就是數據的觀測維度。

         特徵工程是使用專業背景知識和技巧處理數據，使得特徵能在機器學習演算法上發揮更好的作用的過程。

         特徵工程一般包括特徵清洗(采樣、清洗異常樣本)，特徵處理和特徵選擇。

         特徵按照不同的數據類型分類，有不同的特徵處理方法：數值型、類別型、時間型、統計型。

（2）數值型特徵處理

        用連續數值表示當前維度特徵，通常會對數值型特徵進行數學上的處理，主要的做法是歸一化和離散化。

        * 幅度調整歸一化：

            特徵與特徵之間應該是平等的，區別應該體現在 特徵內部 。

            例如房屋價格和住房面積的幅度是不同的，房屋價格可能在3000000~15000000(萬)之間,而住房面積在40-300(平方米)之間，那麼明明是平等的兩個特徵，輸入到相同的模型中後由於本身的幅值不同導致產生的效果不同，這是不合理的

                        

        * 數值型特徵處理——離散化

        離散化的兩種方式：等步長——簡單但不一定有效；等頻——min -> 25% -> 75% -> max

        兩種方法對比：

            等頻的離散化方法很精準，但需要每次都對數據分布進行一遍從新計算，因為昨天用戶在淘寶上買東西的價格分布和今天不一定相同，因此昨天做等頻的切分點可能並不適用，而線上最需要避免的就是不固定，需要現場計算，所以昨天訓練出的模型今天不一定能使用。

            等頻不固定，但很精準，等步長是固定的，非常簡單，因此兩者在工業上都有應用。

（3） 類別型特徵處理

        類別型數據本身沒有大小關系，需要將它們編碼為數字，但它們之間不能有預先設定的大小關系，因此既要做到公平，又要區分開它們，那麼直接開辟多個空間。

        One-Hot編碼/啞變數：One-Hot編碼/啞變數所做的就是將類別型數據平行地展開，也就是說，經過One-Hot編碼啞變數後，這個特徵的空間會膨脹。

（4） 時間型特徵處理

        時間型特徵既可以做連續值,又可以看做離散值。

        連續值：持續時間(網頁瀏覽時長)；間隔時間(上一次購買/點擊離現在的時間間隔)。

        離散值：一天中哪個時間段；一周中的星期幾；一年中哪個月/星期；工作日/周末。

（5） 統計型特徵處理

        加減平均：商品價格高於平均價格多少，用戶在某個品類下消費超過多少。

        分位線：商品屬於售出商品價格的分位線處。

        次序性：商品處於熱門商品第幾位。

        比例類：電商中商品的好/中/差評比例。

8、 推薦系統常見反饋數據 ：

9、 基於UGC的推薦

     用戶用標簽來描述對物品的看法，所以用戶生成標簽(UGC)是聯系用戶和物品的紐帶，也是反應用戶興趣的重要數據源。

    一個用戶標簽行為的數據集一般由一個三元組(用戶,物品,標簽)的集合表示，其中一條記錄(u,i,b)表示用戶u給物品打上了標簽b。

    一個最簡單的演算法：

        - 統計每個用戶最常用的標簽

        - 對於每個標簽,統計被打過這個標簽次數最多的物品

        - 對於一個用戶，首先找到他常用的標簽，然後找到具有這些標簽的最熱門的物品，推薦給他

        - 所以用戶u對物品i的興趣公式為 ，其中 使用戶u打過標簽b的次數， 是物品i被打過標簽b的次數。

    簡單演算法中直接將用戶打出標簽的次數和物品得到的標簽次數相乘，可以簡單地表現出用戶對物品某個特徵的興趣。

    這種方法傾向於給熱門標簽(誰都會給的標簽,如「大片」、「搞笑」等)、熱門物品(打標簽人數最多)比較大的權重，如果一個熱門物品同時對應著熱門標簽,那它就會「霸榜」，推薦的個性化、新穎度就會降低。

    類似的問題,出現在新聞內容的關鍵字提取中。比如以下新聞中,哪個關鍵字應該獲得更高的權重?

10、 TF-IDF：詞頻逆文檔頻率 ( Term Frequency- -Inverse Document Frequency,TF-DF)是一種用於資訊檢索與文本挖掘的常用加權技術。

        TFDF是一種統計方法，用以評估一個字詞對於一個文件集或一個語料庫中的其中份文件的重要程度。字詞的重要性隨著它在文件中出現的次數成正比增加，但同時會隨著它在語料庫中出現的頻率成反比下降。

                    TFIDF=TF IDF

         TF-IDF的主要思想是 ：如果某個詞或短語在一篇文章中出現的頻率TF高，並且在其他文章中很少出現，則認為此詞或者短語具有很好的類別區分能力，適合用來分類。

        TF-DF加權的各種形式常被搜索引擎應用，作為文件與用戶查詢之間相關程度的度量或評級。

         詞頻( Term Frequency,TF) ：指的是某一個給定的詞語在該文件中出現的頻率。這個數字是對詞數的歸一化，以防止偏向更長的文件。(同一個詞語在長文件里可能會比短文件有更高的詞數,而不管該詞語重要與否。） ，其中 表示詞語 i 在文檔 j 中出現的頻率， 表示 i 在 j 中出現的次數， 表示文檔 j 的總詞數。

         逆向文件頻率( Inverse Document Frequency,IDF) ：是一個詞語普遍重要性的度量，某一特定詞語的IDF，可以由總文檔數目除以包含該詞語之文檔的數目，再將得到的商取對數得到 ，其中 表示詞語 i 在文檔集中的逆文檔頻率，N表示文檔集中的文檔總數， 表示文檔集中包含了詞語 i 的文檔數。

（11） TF-IDF對基於UGC推薦的改進 ： ，為了避免熱門標簽和熱門物品獲得更多的權重，我們需要對「熱門進行懲罰。

          借鑒TF-IDF的思想，以一個物品的所有標簽作為「文檔」，標簽作為「詞語」，從而計算標簽的「詞頻」(在物品所有標簽中的頻率)和「逆文檔頻率」(在其它物品標簽中普遍出現的頻率）。

           由於「物品i的所有標簽」 應該對標簽權重沒有影響，而 「所有標簽總數」 N 對於所有標簽是一定的，所以這兩項可以略去。在簡單演算法的基礎上,直接加入對熱門標簽和熱門物品的懲罰項： ，其中， 記錄了標簽 b 被多少個不同的用戶使用過， 記錄了物品 i 被多少個不同的用戶打過標簽。

（一）協同過濾（Collaborative Filtering, CF）

1、基於協同過濾(CF)的推薦：基於內容( Content based,CB)主要利用的是用戶評價過的物品的內容特徵，而CF方法還可以利用其他用戶評分過的物品內容。

    CF可以解決CB的一些局限：

         - 物品內容不完全或者難以獲得時,依然可以通過其他用戶的反饋給出推薦。

        - CF基於用戶之間對物品的評價質量，避免了CB僅依賴內容可能造成的對物品質量判斷的干。

        - CF推薦不受內容限制，只要其他類似用戶給出了對不同物品的興趣，CF就可以給用戶推薦出內容差異很大的物品(但有某種內在聯系)

    分為兩類：基於近鄰和基於模型。

2、基於近鄰的推薦系統：根據的是相同「口碑」准則。是否應該給Cary推薦《泰坦尼克號》?

（二）基於近鄰的協同過濾

1、 基於用戶（User-CF）： 基於用戶的協同過濾推薦的基本原理是，根據所有用戶對物品的偏好，發現與當前用戶口味和偏好相似的「鄰居」用戶群，並推薦近鄰所偏好的物品。

     在一般的應用中是採用計算「K-近鄰」的演算法；基於這K個鄰居的歷史偏好信息，為當前用戶進行推薦。

    User-CF和基於人口統計學的推薦機制：

        - 兩者都是計算用戶的相似度，並基於相似的「鄰居」用戶群計算推薦。

        - 它們所不同的是如何計算用戶的相似度：基於人口統計學的機制只考慮用戶本身的特徵，而基於用戶的協同過濾機制可是在用戶的歷史偏好的數據上計算用戶的相似度，它的基本假設是，喜歡類似物品的用戶可能有相同或者相似的口味和偏好。

2、基於物品（Item-CF）：基於項目的協同過濾推薦的基本原理與基於用戶的類似，只是使用所有用戶對物品的偏好，發現物品和物品之間的相似度，然後根據用戶的歷史偏好信息，將類似的物品推薦給用戶。

    Item-CF和基於內容(CB)的推薦

       - 其實都是基於物品相似度預測推薦，只是相似度計算的方法不一樣，前者是從用戶歷史的偏好推斷，而後者是基於物品本身的屬性特徵信息。

   同樣是協同過濾，在基於用戶和基於項目兩個策略中應該如何選擇呢?

        - 電商、電影、音樂網站,用戶數量遠大於物品數量。

        - 新聞網站，物品(新聞文本)數量可能大於用戶數量。

3、 User-CF和Item-CF的比較

     同樣是協同過濾，在User-CF和ltem-CF兩個策略中應該如何選擇呢？

     Item-CF應用場景

       -  基於物品的協同過濾( Item-CF ) 推薦機制是 Amazon在基於用戶的機制上改良的一種策略因為在大部分的Web站點中，物品的個數是遠遠小於用戶的數量的，而且物品的個數和相似度相對比較穩定，同時基於物品的機制比基於用戶的實時性更好一些，所以 Item-CF 成為了目前推薦策略的主流。

     User-CF應用場景

        - 設想一下在一些新聞推薦系統中，也許物品一一也就是新聞的個數可能大於用戶的個數，而且新聞的更新程度也有很快，所以它的相似度依然不穩定，這時用 User-cf可能效果更好。

    所以，推薦策略的選擇其實和具體的應用場景有很大的關系。

4、 基於協同過濾的推薦優缺點

 （1）基於協同過濾的推薦機制的優點：

        它不需要對物品或者用戶進行嚴格的建模，而且不要求對物品特徵的描述是機器可理解的，所以這種方法也是領域無關的。

       這種方法計算出來的推薦是開放的，可以共用他人的經驗，很好的支持用戶發現潛在的興趣偏好。

（2）存在的問題

        方法的核心是基於歷史數據，所以對新物品和新用戶都有「冷啟動」的問題。

        推薦的效果依賴於用戶歷史好數據的多少和准確性。

        在大部分的實現中，用戶歷史偏好是用稀疏矩陣進行存儲的，而稀疏矩陣上的計算有些明顯的問題，包括可能少部分人的錯誤偏好會對推薦的准確度有很大的影響等等。

        對於一些特殊品味的用戶不能給予很好的推薦。

（三）基於模型的協同過濾

1、基本思想

（1）用戶具有一定的特徵，決定著他的偏好選擇

（2）物品具有一定的特徵，影響著用戶需是否選擇它。

（3）用戶之所以選擇某一個商品，是因為用戶特徵與物品特徵相互匹配。

    基於這種思想，模型的建立相當於從行為數據中提取特徵，給用戶和物品同時打上「標簽」；這和基於人口統計學的用戶標簽、基於內容方法的物品標簽本質是一樣的，都是特徵的提取和匹配。

    有顯性特徵時(比如用戶標簽、物品分類標簽)我們可以直接匹配做出推薦；沒有時，可以根據已有的偏好數據，去發據出隱藏的特徵,這需要用到隱語義模型(LFM)。

2、基於模型的協同過濾推薦，就是基於樣本的用戶偏好信息，訓練一個推薦模型,然後根據實時的用戶喜好的信息進行預測新物品的得分，計算推薦

    基於近鄰的推薦和基於模型的推薦

        - 基於近鄰的推薦是在預測時直接使用已有的用戶偏好數據，通過近鄰數據來預測對新物品的偏好(類似分類)

        - 而基於模型的方法，是要使用這些偏好數據來訓練模型，找到內在規律，再用模型來做預測(類似回歸)

    訓練模型時，可以基於標簽內容來提取物品特徵，也可以讓模型去發據物品的潛在特徵；這樣的模型被稱為 隱語義模型 ( Latent Factor Model,LFM)。

（1）隱語義模型(LFM)：用隱語義模型來進行協同過濾的目標：

            - 揭示隱藏的特徵,這些特徵能夠解釋為什麼給出對應的預測評分

            - 這類特徵可能是無法直接用語言解釋描述的,事實上我們並不需要知道,類似「玄學」

        通過矩陣分解進行降維分析

            - 協同過濾演算法非常依賴歷史數據，而一般的推薦系統中，偏好數據又往往是稀疏的；這就需要對原始數據做降維處理。

            - 分解之後的矩陣，就代表了用戶和物品的隱藏特徵

        隱語義模型的實例：基於概率的隱語義分析(pLSA)、隱式迪利克雷分布模型(LDA)、矩陣因子分解模型(基於奇異值分解的模型,SVD)

（2）LFM降維方法——矩陣因子分解

（3）LFM的進一步理解

    我們可以認為，用戶之所以給電影打出這樣的分數，是有內在原因的，我們可以挖掘出影響用戶打分的隱藏因素，進而根據未評分電影與這些隱藏因素的關聯度，決定此未評分電影的預測評分。

    應該有一些隱藏的因素，影響用戶的打分，比如電影：演員、題材、年代…甚至不定是人直接可以理解的隱藏因子。

    找到隱藏因子，可以對user和Iiem進行關聯(找到是由於什麼使得user喜歡/不喜歡此Item,什麼會決定user喜歡/不喜歡此item)，就可以推測用戶是否會喜歡某一部未看過的電影。

（4）矩陣因子分解

（5）模型的求解——損失函數

（6）模型的求解演算法——ALS

    現在，矩陣因子分解的問題已經轉化成了一個標準的優化問題，需要求解P、Q，使目標損失函數取最小值。

    最小化過程的求解，一般採用隨機梯度下降演算法或者交替最小二乘法來實現交替最小二乘法( Alternating Least Squares,ALS)

    ALS的思想是，由於兩個矩陣P和Q都未知,且通過矩陣乘法耦合在一起，為了使它們解耦，可以先固定Q，把P當作變數，通過損失函數最小化求出P，這就是一個經典的最小二乘問題；再反過來固定求得的P，把Q當作變數，求解出Q：如此交替執行，直到誤差滿足閱值條件，或者到達迭代上限。

（7）梯度下降演算法

Ⅱ Amazon推薦系統是如何做到的

亞馬遜使用了哪些信息進行推薦：

1）當前瀏覽品類

2）與當前商品經常一同購買的商品

3）用戶最近瀏覽記錄

4）用戶瀏覽歷史（長期）中的商品

5）用戶瀏覽歷史（長期）相關的商品

6）購買相同商品的其它用戶購買的物品

7）已購商品的新版本

8）用戶購買歷史（如近期購買商品的互補品）

9）暢銷商品

2、推薦系統模型：U x S → R

1）U是用戶矩陣

2）S是物品矩陣

3）R是用戶對物品的喜愛程度，推薦系統就是基於現有的信息填補R矩陣

3、常用推薦演算法

1）基於內容：易實現，效果好，但是如何獲得一個物品的內容、相似度如何定義等有些情況下會較難把握

2）協同過濾：基於物的協同過濾與基於人的協同過濾

3）矩陣分解（SVD）：用戶-物品評分矩陣A很大且稀疏，將A分解為用戶矩陣（用戶潛在因子）和物品矩陣（物品潛在因子），目標是這兩個矩陣的乘積盡可能接近R。缺點是只利用了評分信息，忽略了用戶屬性和物品屬性

4）因子分解機（FM）：將SVD推廣到多類潛因子的情況，如分解為 用戶、物品、用戶性別、用戶年齡、物品價格 等多個因子，允許因子之間有相關關系（如下圖，方程前半部分是線性回歸，後半部分加入了兩兩因子間關系）

5）深度學習：訓練深度神經網路，輸入用戶id，輸出層做softmax，得到對每個物品id的權重

6）機器學習排序

7）探索與利用：先對用戶聚類（如分為abcde五類），隨機對a中的用戶1和b中的用戶2推薦電影，如果用戶1沒點擊，2點擊了，說明b類用戶可能對該電影更感興趣。

8）集成：對上述多種方法的ensemble

Ⅲ 矩陣分解在協同過濾推薦演算法中的應用

矩陣分解在協同過濾推薦演算法中的應用
推薦系統是當下越來越熱的一個研究問題，無論在學術界還是在工業界都有很多優秀的人才參與其中。近幾年舉辦的推薦系統比賽更是一次又一次地把推薦系統的研究推向了高潮，比如幾年前的Neflix百萬大獎賽，KDD CUP 2011的音樂推薦比賽，去年的網路電影推薦競賽，還有最近的阿里巴巴大數據競賽。這些比賽對推薦系統的發展都起到了很大的推動作用，使我們有機會接觸到真實的工業界數據。我們利用這些數據可以更好地學習掌握推薦系統，這些數據網上很多，大家可以到網上下載。
推薦系統在工業領域中取得了巨大的成功，尤其是在電子商務中。很多電子商務網站利用推薦系統來提高銷售收入，推薦系統為Amazon網站每年帶來30%的銷售收入。推薦系統在不同網站上應用的方式不同，這個不是本文的重點，如果感興趣可以閱讀《推薦系統實踐》（人民郵電出版社，項亮）第一章內容。下面進入主題。
為了方便介紹，假設推薦系統中有用戶集合有6個用戶，即U={u1,u2,u3,u4,u5,u6}，項目（物品）集合有7個項目，即V={v1,v2,v3,v4,v5,v6,v7}，用戶對項目的評分結合為R，用戶對項目的評分范圍是[0, 5]。R具體表示如下：

推薦系統的目標就是預測出符號「？」對應位置的分值。推薦系統基於這樣一個假設：用戶對項目的打分越高，表明用戶越喜歡。因此，預測出用戶對未評分項目的評分後，根據分值大小排序，把分值高的項目推薦給用戶。怎麼預測這些評分呢，方法大體上可以分為基於內容的推薦、協同過濾推薦和混合推薦三類，協同過濾演算法進一步劃分又可分為基於基於內存的推薦（memory-based）和基於模型的推薦（model-based），本文介紹的矩陣分解演算法屬於基於模型的推薦。
矩陣分解演算法的數學理論基礎是矩陣的行列變換。在《線性代數》中，我們知道矩陣A進行行變換相當於A左乘一個矩陣，矩陣A進行列變換等價於矩陣A右乘一個矩陣，因此矩陣A可以表示為A=PEQ=PQ（E是標准陣）。
矩陣分解目標就是把用戶-項目評分矩陣R分解成用戶因子矩陣和項目因子矩陣乘的形式，即R=UV，這里R是n×m， n =6， m =7，U是n×k，V是k×m。直觀地表示如下：

高維的用戶-項目評分矩陣分解成為兩個低維的用戶因子矩陣和項目因子矩陣，因此矩陣分解和PCA不同，不是為了降維。用戶i對項目j的評分r_ij =innerproct(u_i, v_j)，更一般的情況是r_ij =f(U_i, V_j)，這里為了介紹方便就是用u_i和v_j內積的形式。下面介紹評估低維矩陣乘積擬合評分矩陣的方法。
首先假設，用戶對項目的真實評分和預測評分之間的差服從高斯分布，基於這一假設，可推導出目標函數如下：

最後得到矩陣分解的目標函數如下：

從最終得到得目標函數可以直觀地理解，預測的分值就是盡量逼近真實的已知評分值。有了目標函數之後，下面就開始談優化方法了，通常的優化方法分為兩種：交叉最小二乘法（alternative least squares）和隨機梯度下降法（stochastic gradient descent）。
首先介紹交叉最小二乘法，之所以交叉最小二乘法能夠應用到這個目標函數主要是因為L對U和V都是凸函數。首先分別對用戶因子向量和項目因子向量求偏導，令偏導等於0求駐點，具體解法如下：

上面就是用戶因子向量和項目因子向量的更新公式，迭代更新公式即可找到可接受的局部最優解。迭代終止的條件下面會講到。
接下來講解隨機梯度下降法，這個方法應用的最多。大致思想是讓變數沿著目標函數負梯度的方向移動，直到移動到極小值點。直觀的表示如下：

其實負梯度的負方向，當函數是凸函數時是函數值減小的方向走；當函數是凹函數時是往函數值增大的方向移動。而矩陣分解的目標函數L是凸函數，因此，通過梯度下降法我們能夠得到目標函數L的極小值（理想情況是最小值）。
言歸正傳，通過上面的講解，我們可以獲取梯度下降演算法的因子矩陣更新公式，具體如下：

（3）和（4）中的γ指的是步長，也即是學習速率，它是一個超參數，需要調參確定。對於梯度見（1）和（2）。
下面說下迭代終止的條件。迭代終止的條件有很多種，就目前我了解的主要有
1） 設置一個閾值，當L函數值小於閾值時就停止迭代，不常用
2） 設置一個閾值，當前後兩次函數值變化絕對值小於閾值時，停止迭代
3） 設置固定迭代次數
另外還有一個問題，當用戶-項目評分矩陣R非常稀疏時，就會出現過擬合（overfitting）的問題，過擬合問題的解決方法就是正則化（regularization）。正則化其實就是在目標函數中加上用戶因子向量和項目因子向量的二范數，當然也可以加上一范數。至於加上一范數還是二范數要看具體情況，一范數會使很多因子為0，從而減小模型大小，而二范數則不會它只能使因子接近於0，而不能使其為0，關於這個的介紹可參考論文Regression Shrinkage and Selection via the Lasso。引入正則化項後目標函數變為：

（5）中λ_1和λ_2是指正則項的權重，這兩個值可以取一樣，具體取值也需要根據數據集調參得到。優化方法和前面一樣，只是梯度公式需要更新一下。
矩陣分解演算法目前在推薦系統中應用非常廣泛，對於使用RMSE作為評價指標的系統尤為明顯，因為矩陣分解的目標就是使RMSE取值最小。但矩陣分解有其弱點，就是解釋性差，不能很好為推薦結果做出解釋。
後面會繼續介紹矩陣分解演算法的擴展性問題，就是如何加入隱反饋信息，加入時間信息等。

Ⅳ 推薦系統論文閱讀（二十三)-神經圖協同過濾NGCF

論文：

論文題目：《Neural Graph Collaborative Filtering》

論文地址： https://arxiv.org/pdf/1905.08108.pdf

本論文是關於圖結構的協同過濾演算法，在原始的矩陣分解和基於深度學習的方法中，通常是通過映射描述用戶（或物品）的現有特徵（例如ID和屬性）來獲得用戶（或物品）的嵌入。從而利用user和item的embedding進行協同召回。但是作者認為這種方法的固有缺點是：在user與item的interaction數據中潛伏的 協作信號（collaborative signal） 未在嵌入過程中進行編碼。這樣，所得的嵌入可能不足以捕獲協同過濾效果。

讓我們一起來看一下本論文是怎麼利用數據中潛伏的協作信號的吧。

推薦演算法被廣泛的運用在各個領域中，在電商領域，社交媒體，廣告等領域都發揮著至關重要的作用。推薦系統的核心內容就是根據用戶以前的購買和點擊行為來評估用戶對一個物品的喜愛程度，從而針對每個用戶進行個性化推薦。協同過濾演算法認為歷史行為相似的用戶之間的興趣是相同的，所以給用戶推薦的是同類型用戶的愛好，也就是UserCF，而ItemCF給用戶推薦的是跟歷史行為相近的物品。

傳統的協同過濾方法要麼是基於矩陣分解，要麼是基於深度學習的，這兩種方法都忽略了一個非常關鍵的信息---user和item交互的協作信號，該信號隱藏在user和item的交互過程中。原始的協同過濾方法忽略了這種信息，所以在進行user 和 item representation時就不足以較好的進行embedding。

本論文通過將用戶項交互（更具體地說是二分圖結構）集成到embedding過程中，開發了一個新的推薦框架神經圖協同過濾（NGCF），該框架通過在其上傳播embedding來利用user-item圖結構。這種方法在用戶項目圖中進行高階連通性的表達建模，從而以顯式方式將協作信號有效地注入到embedding過程中。

在介紹模型之前先來講解一下什麼是useritem interaction以及什麼是高階的useritem interaction。

我們先看左邊的圖，這個圖就是useritem interaction，u1是我們待推薦的用戶，用雙圓圈表示，他交互過的物品有i1，i2，i3。在看右邊這個樹形結構的圖，這個圖是u1的高階interaction圖，注意只有l > 1的才是u1的高階連接。觀察到，這么一條路徑，u1 ← i2 ← u2，指示u1和u2之間的行為相似性，因為兩個用戶都已與i2進行了交互。而另一條更長的路徑，u1←i2←u2←i4暗示u1可能會點擊i4，因為他的相似用戶u2之前已經購買過i4。另一方面，用戶u1在l = 3這一層會更傾向於i4而不是i5，理由是i4到u1有兩條路徑而i5隻有一條。

當然這種樹結構是不可能通過構建真正的樹節點來表示的，因為樹模型比較復雜，而且結構很大，沒法對每個用戶構建一個樹，這樣工作量太大了。那麼怎麼設計模型結構可以達到跟這個high-order connectivity的效果呢，這個就要運用到神經網路了。通過設計一個embedding propagation layer來表示這種embedding 在每個層之間的傳遞。

還是拿上面那張圖舉例子，堆疊兩層可捕獲u1←i2←u2的行為相似性，堆疊三層可捕獲u1←i2←u2←i4的潛在推薦以及信息流的強度（由層之間的可訓練權重來評估），並確定i4和i5的推薦優先順序。

這個跟傳統的embedding是一樣的，都是對原始的userID和itemID做embedding，跟傳統embedding不同的地方是，在我們的NGCF框架中，我們通過在用戶-項目交互圖上傳播embedding來優化embedding。 由於embedding優化步驟將協作信號顯式注入到embedding中，因此可以為推薦提供更有效的embedding。

這一層是本文的核心內容，下面我們來進行詳細的解讀。

從直觀上來看，用戶交互過的item會給用戶的偏好帶來最直接的依據。類似地，交互過某個item的用戶可以視為該item的特徵，並可以用來衡量兩個item的協同相似性。 我們以此為基礎在連接的用戶和項目之間執行embedding propogation，並通過兩個主要操作來制定流程：消息構建和消息聚合。

Message Construction(消息構建)

對於連接的user-item對(u,i)，我們定義從i到u的消息為：

其中ei是i的embedding，eu是u的embedding，pui是用於控制每次傳播的衰減因子，函數f是消息構建函數，f的定義為：

其中W1和W2用來提取有用的embedding信息，可以看到W2控制的i和u直接的交互性，這使得消息取決於ei和eu之間的親和力，比如，傳遞更多來自相似項的消息。

另一個重要的地方是Nu和Ni，pui = 1/ 。Nu和Ni表示用戶u和item i的第一跳鄰居。 從表示學習的角度來看，pui反映了歷史item對用戶偏好的貢獻程度。 從消息傳遞的角度來看，考慮到正在傳播的消息應隨路徑長度衰減，因此pui可以解釋為折扣因子。

Message Aggregation

聚合方法如下 ：

其中 表示在第一嵌入傳播層之後獲得的用戶u的表示。激活函數採用的是leakyrelu，這個函數適合對pos和neg信號進行編碼。

另一個重要的信息是 ,它的定義如下：

這個信息的主要作用是保留原始的特徵信息。

至此，我們得到了 ，同樣的方法，我們也能獲得 ，這個都是first order connectivoty的信息。

根據前面的計算方式，我們如果將多個Embedding Propagation Layers進行堆疊，我們就可以得到high order connectivity信息了：

計算方式如下：

當我看到這里的時候，我的腦子里產生了一個大大的疑惑，我們在計算第l層的eu和ei時都需要第l-1層的信息，那麼我們怎麼知道ei和eu在第l層是否存在呢？也就是說出現u側的總層數l大於i側總層數的時候，我們如何根據第l-1層的ei來計算第l層的e呢？經過思考，我感覺應該是這樣的，訓練樣本應該是一條path，也就是這個例子是u1 ← i2 ← u2 ← i4這條path，所以可以保證u1跟i4的層數l是一樣的，所以不存在上面那個層數不匹配的問題。

ps:看到後面的實驗結果才知道L是固定的所以每一層都不會缺失。

還有一個就是，不同層之間的W是不一樣的，每一層都有著自己的參數，這個看公式就知道，理由就是我們在提取不同層信息的時候需要不同的W進行信息提取。

另一個疑惑是pui到底是不是每一個l層都一樣？這里看公式好像就是指的是第一跳的Nu和Ni進行就計算的結果。

這部分內容是為了在進行batch訓練的時候進行矩陣運算所推導的數學過程，其實跟之前我們講的那個過程在數學上的計算是完全一樣的，你想像一下，如果不用矩陣進行運算，在訓練過程中要如何進行這么復雜的交互運算。

當進行了l層的embedding propagation後，我們就擁有了l個eu和l個ei，我們將他們進行concate操作：

這樣，我們不僅可以通過嵌入傳播層豐富初始嵌入，還可以通過調整L來控制傳播范圍。

最後，我們進行內積計算，以評估用戶對目標商品的偏好：

採用的是pair-wise方式中的bpr loss：

Ⅳ 協同過濾中als演算法輸出兩個分解矩陣u*v什麼意思

在本文中矩陣來用斜體大自寫字母表示（如：R），標量用小寫字母表示（如：i，j）。給定一個矩陣R，
Rij表示它的一個元素，Ri.表示矩陣R的第i行，R.j表示矩陣R的第j列，RT
表示矩陣R的轉置。R-1
表示矩陣R的逆。在本文中給定的矩陣R表示具有m個用戶、n個對象的評分矩陣，矩陣U、
V分別表示用戶和推薦對象的特徵矩陣

Ⅵ 協同過濾，矩陣分解有感

    這個概念經常在機器學習的文章中看到，但由於接觸不久，所以一直都是一知半解，沒有好好了解過。

    首先從字面上理解，「協同」需要一個「集體「，「過濾」就應該是曬選的意思，那麼協同過濾總的來說就是通過「集體」來「篩選」，以評分推薦系統為例子，這里的「協同」我個人理解就是集合」眾多人的評價」，這里的「評價」，就是「對集體都接觸過的事物進行打分」，這樣大概就能通過一些共同的事物反應出用戶不同的」價值觀「，然後通過這樣的價值觀來」篩選「出價值觀高度相似的人，再相互推薦共同都喜愛的東西。那麼這樣的推薦就很有可能是大家都需要的。

    經過資料洗禮過後，得知cf現在的兩大方向，一種是以記憶為基礎（Memory-base）,另一種是基於模型（Model-based Collaborative Filtering）。

    普及的比較多的前者，它基於關注的目標，又分為基於用戶的協同過濾和基於項目的協同過濾，上面舉的一個簡單的評分推薦系統的例子就可以說是基於用戶的協同過濾，它是通過用戶對共同物品的「主觀價值」來篩選相似用戶，再互補評分高的商品，從而達到推薦商品的目的；那麼基於項目的意思就是通過這個用戶集體對商品集的評價，在物品的角度上去尋找相似度高的物品，達到推薦商品的效果。雖然針對的目標不通，但以我個人理解，大體上都是依賴這個用戶集營造的「價值觀」，只不過區別在於，基於用戶的CF是「關心」各個用戶的「主觀價值」上的「區別」，而基於項目的CF則是要基於這整個用戶集對項目集的「普世價值觀」，來甄別出「物品」上的差異。不知道這么比喻恰不恰當哈，「普世」我這邊理解就是「大多數」，是一種整體趨勢的意思。價值觀比較「抽象」的話，再直接點這里的「價值觀」就相當於物理中的「參考系」。

    但是以上兩種方法在面對，不是每個用戶對大多數商品都做出過評價（數據稀疏）時就無能為力，所以基於這個問題就引導出了基於模型（Model-based ）的CF，我在最近的論文中接觸到的就是一個「矩陣分解」的協同過濾，它能夠基於現有的數據得到一個模型，再用此模型進行推薦。那麼是如何做到的呢？接下來看看矩陣分解。

    假設我先在有一個關於用戶對音樂評分的矩陣如下圖：

    只有上述的數據是很難使用戶相互推薦音樂的，因為可以看出用戶本身聽過的歌就不夠多，那麼如何使數據更加「飽滿」呢？這時正是需要矩陣分解的時候，矩陣分解演算法的數學理論基礎是矩陣的行列變換。行列變換中又有以下規則，我們知道矩陣A進行行變換相當於A左乘一個矩陣，矩陣A進行列變換等價於矩陣A右乘一個矩陣，因此矩陣A可以表示為A=PEQ=PQ（E是標准陣）。

    形象的表示如下圖：

    矩陣分解的目的就是把一個稀疏的用戶評分矩陣分解成用戶因子矩陣和項目因子矩陣相乘的形式R=U(轉置)*I，我們的目的就是最後再讓兩個因子矩陣反乘回去得到飽滿的用戶評分矩陣。那麼這個用戶,項目因子是個什麼東西呢？我們接著上面的音樂評分的形式說，一首歌可能包含多種音樂風格，我們可以量化風格，體現各種風格在一首歌中的比重，那麼這里的「潛在因子」我們就可以當作「音樂風格」，K個因子就可以看作K種風格。譬如下圖：

    可以說，這些因子就是我們的模型中的重要參數，個人理解分解出來的這兩個因子矩陣就可以說是基於模型的CF中的，「模型」的了，其實我覺得可以類比線性模型中的參數，我們的回歸模型最終重要的不就是公式中的各項參數嗎，這兩個因子矩陣其實就是我們這個模型中的重要參數，參數知道了模型也就求出來了。如果不了解線性模型可以參考吳恩達大大的機器學習課程，裡面介紹的很詳細，不像我這邊一知半哈。

    那麼這些個值具體是怎麼得出來的呢？過程和求線性回歸也很像，接下來就是相關的簡單推倒，首先，我們假設，真實的用戶評分和我們預測評分的差遵循高斯分布

R用是評分矩陣   U是用戶因子矩陣，V是項目因子矩陣

接下來就是極大似然估計，使，在現有數據下概率最大化

    類比求線性模型，就能夠了解思想很相似，所以應該同樣是運用了似然估計的思想，要使值最大，式子兩邊同時取對數，可以看到，如果要使概率最大，那麼公式的第一項就要最小，是不是想到了什麼，沒錯接下來就可以看到最小二乘法的式子。

    線性模型我們遇到這個情況一般怎麼做，沒錯，就是梯度下降。首先求偏導數

最後就是梯度下降的矩陣因子更新公式：

    接下來迭代到自己設置的閾值收斂就能得到局部最優解了。

    下面是我根據上述矩陣分解的思想隨機的模擬實踐，可以自行感受一下準度，可能寫搓了點～

注釋：以上諸多圖片材料來自網上多篇博客文章

https://www.hu.com/question/26743347

http://blog.csdn.net/dream_angel_z/article/details/46288167

還有方便實用sklearn的中文API文檔

http://cwiki.apachecn.org/pages/viewpage.action?pageId=10030193

Ⅶ 利用 SVD 實現協同過濾推薦演算法

奇異值分解(Singular Value Decomposition，以下簡稱SVD)
是在機器學習領域廣泛應用的演算法，它不光可以用於 降維演算法中的特徵分解 ，還可以用於 推薦系統 ，以及自然語言處理等領域。

優點： 簡化數據，去除雜訊，提高演算法的結果。
缺點： 數據的轉換可能難以理解。

應用領域： 推薦引擎（協同過濾、相似度計算）、圖像壓縮等。

SVD定義： 如果我們求出了矩陣A的n個特徵值λ1≤λ2≤...≤λn，以及這n個特徵值所對應的特徵向量{w1,w2,...wn}，如果這n個特徵向量線性無關，那麼矩陣A就可以用下式的特徵分解表示：A=WΣW−1，其中W是這n個特徵向量所張成的n×n維矩陣，而Σ為這n個特徵值為主對角線的n×n維矩陣。一般我們會把W的這n個特徵向量標准化，即滿足||wi||2=1, 或者wiTwi=1，此時W的n個特徵向量為標准正交基，滿WTW=I，即WT=W−1, 也就是說W為酉矩陣。要進行特徵分解，矩陣A必須為方陣。那麼如果A不是方陣，則用到SVD。

矩陣A的SVD為：A=UΣVT，其中U是一個m×m的矩陣，Σ是一個m×n的矩陣，除了主對角線上的元素以外全為0，主對角線上的每個元素都稱為奇異值，V是一個n×n的矩陣。U和V都是酉矩陣，即滿足UTU=I,VTV=I。

對於奇異值,它跟我們特徵分解中的特徵值類似，在奇異值矩陣中也是按照從大到小排列，而且奇異值的減少特別的快，在很多情況下，前10%甚至1%的奇異值的和就佔了全部的奇異值之和的99%以上的比例。也就是說，我們也可以用最大的k個的奇異值和對應的左右奇異向量來近似描述矩陣。

因此SVD 也是一種強大的降維工具 ，可以利用 SVD 來逼近矩陣並從中獲得主要的特徵。通過保留矩陣的 80%~90% 的能量，就可以得到重用的特徵並去除雜訊。

推薦系統 是利用電子商務網站向客戶提供商品信息和建議，幫助用戶決定應該購買什麼產品，模擬銷售人員幫助客戶完成購買過程。
主要有以下幾種推薦演算法：
基於內容的推薦（用到自然語言處理）， 協同過濾（主流） ，基於規則推薦（基於最多用戶點擊，最多用戶瀏覽等），混合推薦（類似集成演算法，投票決定），基於人口統計信息的推薦（根據用戶基本信息）

協同過濾推薦分為三種類型。 第一種是基於用戶(user-based)的協同過濾（需要在線找用戶和用戶之間的相似度關系），第二種是基於項目(item-based)的協同過濾（基於項目的協同過濾可以離線找物品和物品之間的相似度關系）， 第三種是基於模型(model based)的協同過濾（用戶和物品，主流）。

一般在推薦系統中，數據往往是使用 用戶-物品 矩陣來表示的。 用戶對其接觸過的物品進行評分，評分表示了用戶對於物品的喜愛程度，分數越高，表示用戶越喜歡這個物品。而這個矩陣往往是稀疏的，空白項是用戶還未接觸到的物品，推薦系統的任務則是選擇其中的部分物品推薦給用戶。

對於這個 用戶-物品 矩陣，用已有的部分稀疏數據來預測那些空白的物品和數據之間的評分關系，找到最高評分的物品推薦給用戶。

具體基於模型的方法有：
用關聯演算法做協同過濾（Apriori演算法、FP Tree演算法）
用聚類演算法做協同過濾（針對基於用戶或者基於模型，Kmeans，DBSCAN）
用分類演算法做協同過濾（設定評分閾值，高於推薦，低於不推薦，邏輯回歸和樸素貝葉斯，解釋性很強）
用回歸演算法做協同過濾（Ridge回歸，回歸樹）
用矩陣分解做協同過濾（由於傳統的奇異值分解SVD要求矩陣不能有缺失數據，必須是稠密的，而用戶物品評分矩陣是一個典型的稀疏矩陣，主要是SVD的一些變種，比如FunkSVD，BiasSVD和SVD++。這些演算法和傳統SVD的最大區別是不再要求將矩陣分解為UΣVT的形式，而變是兩個低秩矩陣PTQ的乘積形式。）
用神經網路做協同過濾（限制玻爾茲曼機RBM）

在 Python 的 numpy 中，linalg已經實現了SVD

Ⅷ 協同過濾(2)： KDD2020- HyperGraph CF 基於超圖

協同過濾推薦系統是當今眾多推薦系統中最流行和最重要的推薦方法之一。

盡管已經被廣泛採用，但是現有的基於 cf 的方法，從矩陣分解到新興的基於圖的方法， 在訓練數據非常有限的情況下表現不佳 （數據稀疏問題）。

本文首先指出了造成這種不足的根本原因，並指出現有基於 CF 的方法固有的兩個缺點，即: 1)用戶和物品建模不靈活; 2)高階相關性建模不足。

在這種情況下，文中提出了一個雙通道超圖協同過濾(DHCF)框架來解決上述問題。

首先，引入 雙通道學習策略 (Dual-Channel)，全面利用分治策略，學慣用戶和物品的表示，使這兩種類型的數據可以優雅地相互連接，同時保持其特定屬性。

其次， 利用超圖結構對用戶和具有顯式混合高階相關性的物品進行建模 。提出了跳躍超圖卷積(JHConv)方法，實現高階關系嵌入的顯式和有效傳播。

推薦系統的核心是一系列的推薦演算法，這些演算法能夠**根據用戶的個人特徵有效地從爆炸式信息篩選出信息。協同過濾是目前最受歡迎和廣泛採用的方法之一。

CF 持有一個基本的假設，當向用戶提供推薦時: 那些行為相似的人(例如，經常訪問同一個網站)很可能在物品(例如，音樂、視頻、網站)上分享相似的偏好。
為了實現這一點，一個典型的基於 CFbased 方法執行一個兩步策略: 它首先利用歷史交互區分相似的用戶和項目; 然後基於上面收集的信息，向特定用戶生成推薦。

現有的 CF 方法可以分為三類。

雖然 CF 方法已經研究了多年，但仍然存在局限性，特別是在訓練的先驗知識非常有限的情況下。為了理解這些缺陷，深入挖掘現有 CF 方法的內在機製得到以下局限性:

基於這些生成的連接組，即超邊，可以分別為用戶和物品構造兩個超圖，即兩個通道的表示。本文提出了一種新的跳躍超圖卷積演算法(JHConv) ，該演算法通過聚合鄰域的嵌入並引入先驗信息，有效地在超圖上進行信息傳播。(與傳統的基於圖的方法對比，用戶超圖和項目超圖，可以更靈活地進行復雜的數據關聯建模，並與不同類型的數據結合。)

超圖定義為 ，V表示圖節點， 表示超邊集合，超圖鄰接矩陣 描述節點與超邊的關系

在高層次上，DHCF 首先通過一個雙通道超圖框架學慣用戶和物品的兩組嵌入，在此框架上，DHCF 通過計算用戶和物品嵌入查找表的內積，進一步計算出用戶-項目偏好矩陣。基於這樣的偏好矩陣，DHCF 估計用戶對某個商品感興趣的可能性。

總體分為三步：

構建用戶和物品嵌入矩陣：

為了在預定義的混合高階關繫上聚合相鄰消息,執行以下高階消息傳遞:

為了提取有區別的信息，我們對用戶和物品定義為

綜上所述，上述兩個過程構成了一個集成的DHCF 層，允許對用戶和物品進行明確的建模和編碼，並通過強大的嵌入功能進一步更新和生成更精確的嵌入超圖結構。這種精細嵌入可以進一步應用於推薦系統中的各種下游任務。

與 傳統 HGNNConv 相比，JHConv 允許模型同時考慮其原始特徵和聚合相關表示，在另一方面，這樣的 resnet結構的跳躍連接使模型能夠避免由於集成了許多其他連接而導致的信息稀釋。

引入高階關聯來實現構建超邊，根據自定義的規則分別對用戶和物品進行高階關聯提取

定義1: 物品的 k 階可達鄰居。在用戶-物品交互圖，更具體地說是二部圖中，如果在 itemi 和 itemj 之間存在一個相鄰頂點序列(即一條路) ，且該路徑中的用戶數小於 k，itemi (itemj)是 itemi (itemi)的 k 階可達鄰居。

定義2： 物品的 k階可達用戶。在物品-用戶二部圖中，如果用戶 j 和物品 k 之間存在直接交互作用，則用戶 j 是 itemi 的 k 階可達鄰居，而物品 k 是 itemi 的 k 階可達鄰居。

對於 itemi，其 k 階可達用戶集稱為 。從數學上講，超圖可以定義在一個集簇上，其中每個集代表一個超邊。因此，這里可以通過物品的 k 階可達用戶集構建超邊。

然後在用戶 k 階可達規則的基礎上構造高階超邊組，該超邊組可表示為:

假設通過K階可達規則，構造a個超邊組，最後的超圖需要將這a個超邊組做融合，見上面的總體框架中的描述。

同理，按照相似的K階可達的規則，對物品進行分析，構成物品的超邊(N個用戶，M個物品)

在實驗中，每個用戶觀察到的交互中的10% 被隨機選擇用於訓練，其餘的數據用於測試。這樣的設置增加了 CF 任務的難度，因為模型只能獲取非常有限的觀察到的交互。此外，由於數據的高度稀疏性，它可以很好地評價模型從有限的隱式數據集中挖掘有用信息的能力。對於所有四個數據集，每個用戶至少有兩個用於訓練的交互。

這篇工作基於超圖結構，提出了一種新的CF框架，與基於圖神經網路的CF相比，超圖結構更符合實際情況；此外，雙通道的思路也值得借鑒，之前也分析的一篇雙通道BPR的論文。近年來，基於圖神經網路的推薦已經成為研究主流，而其中超圖相關的工作少之又少，最近看到的另一篇是SIGIR2020上的一篇Next Item Recommendation with Sequential Hypergraphs，在超圖神經網路上並沒多大的改進，重點仍然在於如何用這種結構去解決存在的問題。

如果覺得有用，歡迎點贊關注贊賞，若對推薦感興趣歡迎評論區/私信交流~~~