深入淺出常用推薦系統演算法 Recommendation System
在學習機器學習的過程中，心中一直都圍繞著「我還有推薦演算法沒有碰過，感覺好像缺了一塊」。因此，今日我便花了一些時間把常用的一些推薦演算法整理起來，並附上實際的 Python code 以及每一步的意義。希望能帶給讓入門的讀者更清楚易懂的指南。
這篇文章會提到非個人化的簡單推薦，以及常被使用的協同過濾演算法，以及為了解決資料稀疏性而使用的矩陣分解與 SVD 等技術。那麼話不多說，就讓我們開始吧！
How to choose Algorithms to use?
隨著越來越多的套件與演算法被開發出來，我們其實在使用時都不需要再自己實現演算法。上次在瞭解推薦系統時，就被套件 Surprise(A Python scikit for recommender systems) 震驚了好一陣子。裡面常用的演算法都直接被實現了，甚至一樣使用的 Scikit-learn 的 fit/predict 的 API，讓學習的難易度又再下降一階。
因此，最重要的已經不是演算法如何實現，而是：
哪個演算法，才是當下的狀況中最合適的選項？
在開始學習之前，記得先從這個區域來瞭解不同演算法的優缺點，再來往下一步瞭解演算法能如何實現。這裡補充一下簡稱，IB 代表 item-based；UB 代表 User-based。
IB | Best-seller | Non-Personalized
- 商品數不多。
- 銷售差異懸殊，無須太多的個人化推薦。
UB | Suggestion | Non-Personalized
- 簡化版的 User-based 推薦，不考慮不同評分間的差異。
IB | Feature Similarity | Personalized
- 以 Jaccard Similarity 計算相似度。主要以聯集與交集來判斷哪些商品出現的機率較高，但沒有不同商品間評分的差異。
IB | Text-based Similarity | Personalized
- 以商品 text 為主 item-based 協同過濾，用於無特定 Feature 計算時使用。
IB | item-based Collaborative Filtering | Personalized
- 優點：可以根據使用者來推薦潛在興趣，變化多樣。
- 缺點：商品推薦結果容易變化，缺乏穩定性。
- 缺點：冷啟動問題（Cold Start），且初期推薦效果非常差。
- 缺點：資料稀疏問題，需要以 KNN／MF 矩陣分解來解決。
UB | User-based Collaborative Filtering | Personalized
- 優點：隨著時間推演，演算法推薦會越來越穩定。
- 優點：能夠提前在商品上架前計算演算法矩陣。
- 缺點：無法推薦使用者潛在感興趣的商品，容易重複與老套。
- 缺點：特徵常難以抽取，例如電影。
- 缺點：冷啟動問題（Cold Start），且沒有使用者資料便無法推薦。
- 缺點：資料稀疏問題，需要以 KNN／MF 矩陣分解來解決。
Non-Personalized Recommendation
Best-seller Recommendation
雖然現在一提到推薦演算法，大家就會想到 Netflix 的推薦；但實際上如果商品數不多的情況下，沒有必要一定要用到協同過濾（collaborative filtering）等較複雜的演算法。
很多時候簡單地推薦熱銷商品其實就很夠用了，更何況協同過濾、基於內容的推薦演算法還有冷啟動的問題，亦即使用者在沒有任何使用數據前，沒有辦法使用上述提到的演算法來推薦內容。
這個推薦演算法可以適用於商品數不多的情況下。舉個例子，如果目前僅有 10~20 幾個商品，而且銷售的差異很懸殊，那我就會傾向於不管誰來看，我都推薦賣的最好、評價最高的商品。
How to use it? Step by step:
因為我們參考的資料僅有評分，因此如果評分的數量太少，就要先將該選項刪除避免影響排序。接著我們就利用 Group by 的方式，將已經被評價過的商品 Group 起來，最後根據評分由高到低來排序。
當然，如果除了評分之外購買量也很重要，那就可以再以銷售量進行排序，一樣將銷售量從高到低排序好，並以 pd.concat 以商品名來合併商品。
Non-Personalized Suggestion
另外一種，則能夠以簡單的方式計算出觀看類似商品的人，可能也對哪一些商品有興趣，可以簡單地思考為簡化的 User-based Algorithm。
而這個演算法的使用時機，可以用於產品初期，希望使用者在一開始隨意點了一項內容後，就能直接暴力推薦相似商品時使用。
How to use it? Step by step:
他的概念一樣很簡單，是以「窮盡法」來把所有可能 1 vs 1 配對都列舉出來，並據此排列有多少種組合。什麼意思呢？簡單來說如果小華總共看的 A、B、C 三個商品，則資料就會以下列的方式呈現：
# User|items
小華 A
小華 B
小華 C接著，透過小華所有接觸過的商品類別，分別以從 A、B、C 三個品項裡任取兩個的所有配對方式共六種：
# User|items
小華 A B
小華 A C
小華 B A
小華 B C
小華 C A
小華 C B接著小明也看過了 A、B 兩種商品，資料一樣會被轉換成：
# User|items_1|items_2
小明 A B
小明 B A接著我們相加後去除使用者的欄位，可以得到下面呈現的表格：
# items_1|items_2
A B #小華
A C #小華
B A #小華
B C #小華
C A #小華
C B #小華
A B #小明
B A #小明接著以第一欄的商品（A、B、C），個別 Group 起來檢視對應資料的 Size：
# items_1|items_2|counts
A B 2
C 1
B A 2
C 1
C A 1
B 1可以看到對於上述的資料表格來說，如果使用者看了 A 商品，就推薦給他 B，因為商品 A 對 B 這個組合出現的次數最高；反之如果看 B，就推薦給他 A，非常簡單而直覺。
接著，藉由篩選選出感興趣的 items，就會出現想要優先推薦的 item 了。下面就以「Lord of the Rings」作為搜尋範例：
寫到這裡，其實也覺得不一定每次都要使用非常複雜的演算法，有時候商品數並不多的情況下，簡單的推薦方法就能起到很不錯的效果了。
Content-base Recommendation
Feature Similarity
基於商品特徵的推薦，很適合給從未看過其他商品的人使用，因此在使用者剛進入頁面時，可以藉由一些簡單的選擇題，讓他選出他有興趣的類別。這樣我們就能夠快速推薦東西給他，而不需要等使用者看過以後才能推薦。
How to use it? Step by step
最關鍵的地方，就是使用 Pandas 之中的 Crosstab。讓特定的特徵種類，全部轉換為類似 One-hot Encode 的概念。但我們有了特徵向量的矩陣後，要怎麼拿來推計算相似的程度呢？這就可以使用「雅卡爾相似度」來快速計算。
Jaccard Similarity 雅卡爾相似度
什麼是 Jaccard Similarity？簡單來說：
就是對於所有的聯集中，有多少比例是交集。
我們以學生的選修科目來說明，假設選項總共有國文、英文、數學、自然、社會五個科目，而班上總共有小華和小明兩個學生，分別選修了：
- 小華：國文、英文、社會
- 小明：英文、自然、社會
小華跟小明的交集有「英文、社會」；聯集則有「國文、英文、自然、社會」，，因此他們的 Jaccard Similarity 可以計算為：
2 (英、社) / 4 (國、英、自、社) = 0.5。接著，我們就實際以 Python 來說明怎麼實作這個演算法。在開始計算之前，我們需要轉換類別至下面理想的資料型態：
那我們要如何轉換資料呢？通常我們可以獲得的資料型態如下：
總共有「商品名」與「其所屬的類別」這兩個資料；若沒有則需要調整成上面這個資料格式。接著就可以使用 Pandas 的 crosstab，來把資料轉換成類似 one-hot Encode 的狀態。
如果我們只想要搜尋特定兩個商品間的 Jaccard Similarity，那我們就可以非常簡單地抽取出資料，並以 jaccard_score 的函式快速計算：
然而，如果我們想要計算一整張表格商品的相似度係數，則可以使用 scipy 的 pdist 和 squareform 來快速計算整個係數矩陣。
最後將這個表格儲存下來，之後只要有新增商品就可以計算一次，因為不涉及指數計算，所以就算做到 real-time update 也不會花太多時間。
Text-based Similarity
但實際上在進行推薦時，很多商品並沒有明確的類別可以參照或分類，很多時後僅僅有一些文字來參考。這該怎麼辦呢？這些文字其實也可以拿來作為參考的範例，這時我們就可以應用在 NLP(Nature Language Processing) 領域富有盛名 TF-IDF(Terms Frequency — Inverse Document Frequency) 演算法。
透過文件的說明或文案，可以從上述的演算法當中，來求出每篇文章或每個商品文案中，每個字詞的重要程度。
How to use it? Step by step
如何應用 TF-IDF 的演算法呢？所幸 Scikit-learn 已經幫我們寫好演算法，我們只要引入即可使用。最後一行是根據上面的參數設定後，所區分出來的詞類，可以看到他會變成一組 list。
這裡要特別補充一下 TfidfVectorizer 的各項參數，當初在理解時單看數字覺得很混亂，後來到官方文件研究一下後才比較理解各個參數的意思。上面的範例是指，最少要出現在兩篇以上才不算是停止詞（Stop words）；以及如果超過 70% 的文件都有則也被視為停止詞。
這裡就舉幾個常用的參數：
- Stop_words｜以 List 或 dict 傳入，用於去掉文件裡的停用詞。
- vocabulary｜字典索引，用於對應 {“I”: 0, “love”: 1, “books”: 2} 等索引
- norm｜正規化，默認使用 L2 正規化，意旨使用向量的點積。
- max_df｜可設定 int 或 float，如為 int 代表超過這個文本數就把他列為 Stop_words；如果設定 float(0.0~1.0) 則代表超過這個比例就排除。
- min_df｜和 max 相反，有些詞頻太低導致沒有參考價值，設定方式和上述 max 相同。
當然，如果一旦設定 vocabulary 時，就會自動失效了。
接下來，我們透過 TF-IDF 轉換與計算詞頻之後，我們就可以得到每一個商品對於整合出來的綜合 TF-IDF 稀疏矩陣。也因為得到的 vectorized_data 實際上是壓縮過後的稀疏矩陣（Sparse Matrix），因此必須先將他轉換成 array 的形式才能夠轉換成直接檢視的形式。
當我們計算好所有的詞頻之後，重頭戲就來了。這時就要請出我們簡單確實用的演算法餘弦相似度（Cosine Similarity），這個演算法不僅能用在文字相似推薦，也是之後會介紹的協同過濾（Collaborative Filtering）上。
Cosine Similarity 餘弦相似度
其實餘弦相似度是來自於兩個向量之間的餘弦值，能夠透過歐基理得點積公式求出，公式如下：
可以看到只要簡單地將兩邊同除兩向量的純量乘積後，就和第一個的餘弦相似度公式完全一模一樣。
餘弦值的值會從 -1~1 之間，其特性是：如果兩個向量的方向很接近，那他就會接近 1；完全反方向則為 -1；0 通常代表這兩者之間是獨立的。而在分母除以分量的過程，可以幫他當作是對於各文件間正規化的方法。
同樣地，我們也不需要自己來計算餘弦相似度，Sklearn 一樣幫我們算好，我們只要把套件引入就完事。
接著，我們就可以直接以 cosine_similarity_df 這個 DataFrame 來抽取我們想要看的推薦商品排序。
例如上述我想要找 Rio 這個商品，在排序後我就知道最接近的商品推薦依序是「Alvin and the Chipmunks」跟「The Avengers」這兩項，因此當使用者點擊這些商品時，我們就能夠依序推薦給使用者相關的商品。
Collaborative filtering
終於輪到我們在推薦系統領域裡，最常聽到的協同過濾（Collaborative filtering）。他的概念其實和前面的 item-based Recommendation 非常相似，只是這個演算法的計算資料，是來自於用戶對於特定商品的評分或購買項目。也因此該演算法有一個最為棘手的問題 — — 冷啟動（Cold Start）。
所謂的冷啟動，指的是當使用者剛進入系統時，因為沒有使用或瀏覽過任何商品，因此無法推薦的窘境。因此通常在一開始進行推薦時，較簡單的方式是以 item-based 的方式先給予用戶推薦，接著累積一定的使用資料後，再慢慢放入協同過濾所推薦的內容。
Item-based Recommendation
單純針對這些物品的推薦已經很實用了；但如果我希望能夠將推薦依據使用者實際瀏覽過的商品來決定，那又要怎麼做呢？有兩個簡單的方式能夠生成每一個使用者的專屬 User Feature。
協同過濾相較於使用 item-based 的推薦演算法，需要取得一項額外關鍵的資料 — — 使用者對於特定商品的評分。無論是按讚、五星評分等，都是使用 CF 前的關鍵數據。
如何直觀理解協同過濾（Collaborative filtering）：
對於上面的四部電影，我們可以看到 The Sanlot 和 The Lion King 的評分較為相似；而 Ocean’s Eleven 和 John Wick 則較為相似。
因此以直覺來理解，我們會認為會認為喜歡 The Sandlot 的 User_C 和 D，理論上也會喜歡 The Lion King 這部電影。而且餘弦相似度其實是不計算評分絕對值的高低，因此相似度越接近 1 的電影，理論上人群也越接近同一群。所以只要根據這群人會看的電影，相互推薦即可。
How to use it? Step by step
要生成 User 專屬的 Feature 其實很簡單，只要透過加權平均來計算 User 的 Feature 即可。
首先，我們要透過原先加工過的 item 之 TF-IDF Matrix 來選出使用者有選過的 items。接著我們透過加權把使用者的 Feature 計算出來，接著就能夠拿這組 Feature 來和其他的商品計算 Cosine Similarity。這裡先假設用戶所有的瀏覽次數都僅有一次，以簡化整體的流程：
接下來，我們將讀者已經瀏覽過的商品剔除掉，並以剩下的商品來計算餘弦相似度，接著從高到低排序就可以獲得推薦清單了。
這裡可以特別補充說明，為何在計算餘弦相似度時需要使用 reshape(1, -1) 來轉換資料，是因為 sklearn 預設只能讀取二維 array；但如果直接以 value 來轉換則會獲得一維 array。因次透過 reshape 來轉換成僅有一列，而 -1 則是讓 numpy 自行計算總共要幾列。這種轉換方式會讓矩陣自動變成二維 array，因此可以讓 sklearn 讀取數據。
最後獲得的結果就是以上的表格，是不是很簡單而易懂呢！
User-based Recommendation
這時有趣的地方來了，其實只要將原先的 user_ratings_pivot_filled 整個矩陣轉置一下，就可以得到 item-based Recommendation 所需的矩陣，並用於計算 User 之間的相似度。換句話說，我們只是從計算原先 item 之間的相似度，透過轉置來計算 User 之間對 item 的相似度。
How to use it? Step by step
我們計算推薦商品的演算法，一樣使用的是 Cosine Similarity 餘弦相似度，只是將計算的標的轉換為「對於不同的商品間，用戶與用戶之間的相似度」。因此為了獲得用戶之間的相似度，我們需要先將資料轉換成為方便計算的形式。
以下是我們常見的用戶評分表矩陣：
接著透過轉置，我們就能夠獲得 User-based 所需的矩陣：
接下來，我們以上述的資料來計算各部電影之間的相似度。不過在計算之前，必須將每一個欄位減掉各商品的平均，原因是評分通常為正；但很明顯 1 分跟 5 分分別代表了滿意與不滿意。
而更好的方式，是對於所有的個別電影都減掉各自的平均，就變成大名鼎鼎的皮爾森相關係數（Pearson Correlation Coefficient）。以下就是皮爾森相關係數的公式，是不是其實只比餘弦相似度多了減掉平均的項？
為了讓評分能夠各自區分出喜歡與不喜歡，因此我們個別將每一項減去其平均。且通常用戶僅會給予少部分的電影評分，因此將沒有值的地方先簡單補上 0，避免相似度無法計算。
同時這裡也可以說明一個心態，用戶對於特定的電影評分時，通常會在這部電影很好或很差的情況下填寫。而一部看完不好也不壞的電影，通常就不太會讓用戶特別想要留下評分。
因此這個簡單的以平均來區分好壞，其實是能夠拿來參考與使用的方式。接下來，我們就可以根據之前的計算方式，來計算各項商品間的推薦排序了。
最後，我們就可以獲得對於 user_001 相似的使用者，這時就可以拿 user_210、 user_332 的內容，將 user_001 沒有的電影推薦給他，這就是整個協同過濾運作的原理了。
KNN (K-Nearest Neighbors)
透過協同過濾演算法，計算出 User-based 的餘弦相似度矩陣後，通常就會發生當我們回推這些 User 所用的 items 時，很多地方都會呈現 NaN，因為不是每個使用者都會對各個商品評分或按讚。
因此 KNN 就在這裡發揮作用，藉由簡單的 KNN 插值來補齊這些沒有被填充的商品項目，讓整個資料都能夠以附近的數字來預測。
How to use it? Step by step
KNN 的基礎但核心的概念，就是以周圍指定的 K 個數（例如 3）中，佔比最多的那個類別就歸類為該類別。因此請盡量避免指定偶數項。因為當數字完全相同時，KNN 可能就會選不出來（如果以 Cosine 則可能比較難重複），或是會隨機從中挑一個出來。
這裡的概念其實很簡單，藉由明確有預測結果的欄位，來預測特定 User 對特定欄位的評分值（這裡是 item_001）。而 KNN Regression 則是將周圍的 10 個資料點用於計算平均後輸出。
同樣地，這個插值法一樣也能倒過來使用，亦即用原先用 User 的評價來補齊其他評價；這次則可以用其他商品來當作訓練集，來預測特定商品的分數。
Matrix Factorization
在上一個章節末，我們使用 KNN 來填補使用者沒有填寫的評分；但這僅能使用在商品數不多的情況下。如果商品數非常的多，亦或是使用過該商品的比例非常的低，那使用 KNN 所預測出來的值就會非常的不准。這時，就需要使用矩陣分解（Matrix Factorization）來解決資料稀疏的問題。
What is Matrix Factorization?
矩陣分解就如其名稱所示，將一個原本完整的矩陣，拆解成兩個矩陣相乘。然而可惜的是，抽取出來的特徵矩陣並無法直接透過數字理解，因此在 DataFrame 左邊代表 User 的特徵，才被稱為 潛藏特徵（Latent Factors）。其中，每一列都代表其中一種潛藏特徵。
在分解的過程中，因為我們用了更少的資料來代表原本的矩陣，因此必定會造成資訊損失（Information Loss）；但帶來的優勢便是更小的計算量，以及避免了資料稀疏，造成協同過濾演算法難以計算的困境。
How to find these Matrices?
當我們瞭解矩陣分解的好處後，下一個問題便是「如何計算出這兩個矩陣」；其中，最常被運用的方法便是奇異值分解（Singular value decomposition）。
為什麼會需要中間的 Sigma 對稱矩陣呢？因為對於代數而言，對角矩陣可以針對前面的 U 和後面的 Vt 進行線性變換，而這個特質僅有對稱矩陣做的到；但更細節的數學原理筆者也尚未完全理解，因此僅知道為了獲得線性變換的結果，我們需要一個 Sigma 來作為中介。這個 Sigma 就被稱為奇異值。
如果以直觀的方式來理解 SVD，其實可以把他當作一種降噪跟降維的工具，透過 SVD 的轉換，我們可以獲得這些資料的隱含特徵，並以這些特徵來計算個別的特徵。接著，我們透過將 U、Sigma、Vt 來計算特定的值，以減少整個矩陣的稀疏性，對於商品數破億的電商來說，SVD 就起到很大的作用。
整體來說，SVD 雖然解決了儲存稀疏矩陣的問題；但在計算時的空間複雜度 Big O(n³) 還是太大了，因此 FunkSVD、BiasSVD 因此延伸被創造出來，透過僅有兩個矩陣相乘，來大幅降低計算成本。只是目前筆者也尚未理解這些 SVD 的實際實現方式，因此僅僅點出來仍然有這些演算法而已。
How to use it? Step by step
基本上我們在使用 SVD 到矩陣裡時，會透過直接計算該矩陣來算出資料，已降低資料的儲存量。
Summary
終於把內心一直比較沒有把握的推薦演算法大致理解了一遍，才發現原本以為高深莫測的協同推薦演算法，其實非常地直覺而易懂。我想這也是我繼續學習機器學習的動力，因為很多原先以為很困難、很酷的東西，其實只是自己需要一些時間來學習。
這篇文章一樣是筆者自己在學習 DataCamp 時，一點一滴的實作與釐清觀念所寫成，期待將比較完整與易懂的內容分享給各位讀者。也因為內容較為繁雜，因此如果有部分筆誤還請各位讀者不吝指正！
**【希望用你的掌聲來投票與支持】**
拍 5~10 下：簽個到，表示支持（感謝你的鼓勵啊啊啊）
拍 10~30 下：希望我可以多寫一些文章！有你這位讀者，寫這篇也心滿意足了！
拍 30~50 下：內容對你感覺很有共鳴，希望能多分享給周圍的朋友！You May interest in:
- 如何快速上手資料科學專案流程（上）A Step-by-Step Guide For A Data Science Project
- 快速上手資料科學專案流程全攻略（下）A Step-by-Step Guide For A Data Science Project. II
- Statistical Thinking in Python｜ECDF 進行 EDA 探索式分析的好工具
- Analyzing Police Activity with pandas 案例實作（一）– 如何高效進行數據分析
- Analyzing Police Activity with pandas 案例實作（二）– 數據整理
- 你可能不知道的 SQL 小筆記（查詢篇）
- [數據分析] Lean Analytics — 總說數據分析，你在分析什麼？
- [Statistic] Hypothesis Testing — 以 Python 實踐假設檢定（附程式碼）
- [DataCamp] 快速解析 Python 的各種Import Data 基礎應用技巧
- [DataCamp] Cleaning Data in Python 如何簡單上手資料清洗
Reference Documentation
- Article｜TfidfVectorizer 参数解析
- Article｜推薦演算法總結Recommendation
- Article｜一文让你通俗理解奇异值分解
- Article｜機器學習（37）之矩陣分解在協同過濾推薦中的應用
- Article｜Build a Recommendation Engine With Collaborative Filtering
- Article｜Introduction to Recommender System
- Course｜Building Recommendation Engines in Python
