預測喜歡：在一個簡單的推薦引擎的算法裡面

推薦引擎（有時稱為推薦系統）是一種工具，可讓算法開發人員在給定項目列表中預測用戶可能喜歡或不喜歡什麼。 推薦引擎是搜索字段的一個非常有趣的替代品，因為推薦引擎可以幫助用戶發現他們可能不會遇到的產品或內容。 這使得推薦引擎成為 Facebook、YouTube、亞馬遜等網站和服務的重要組成部分。

推薦引擎以兩種方式之一理想地工作。 它可以依賴於用戶喜歡的項目的屬性，對其進行分析以確定用戶可能還喜歡什麼； 或者，它可以依賴其他用戶的好惡，然後推薦引擎使用它來計算用戶之間的相似度指數，並相應地向他們推薦項目。 也可以結合這兩種方法來構建一個更強大的推薦引擎。 但是，與所有其他與信息相關的問題一樣，選擇適合所解決問題的算法至關重要。

在本教程中，我們將引導您完成構建基於內存的協作推薦引擎的過程。 該推薦引擎將根據用戶喜歡和不喜歡的內容向用戶推薦電影，其功能類似於前面提到的第二個示例。 對於這個項目，我們將使用基本的集合操作、一些數學知識和 Node.js/CoffeeScript。 與本教程相關的所有源代碼都可以在這裡找到。

集合和方程

在實現基於協同記憶的推薦引擎之前，我們首先要了解這樣一個系統背後的核心思想。 對於這個引擎，每個項目和每個用戶都只是標識符。 因此，在生成推薦時，我們不會考慮電影的任何其他屬性（例如，演員、導演、流派等）。 兩個用戶之間的相似度使用介於 -1.0 和 1.0 之間的十進制數表示。 我們將這個數字稱為相似度指數。 最後，用戶喜歡一部電影的可能性將使用另一個介於 -1.0 和 1.0 之間的十進制數來表示。 現在我們已經使用簡單的術語對這個系統周圍的世界進行了建模，我們可以釋放一些優雅的數學方程來定義這些標識符和數字之間的關係。

在我們的推薦算法中，我們會維護一些集合。 每個用戶將有兩組：一組用戶喜歡的電影，一組用戶不喜歡的電影。 每部電影還將有兩個與之關聯的集合：一組喜歡這部電影的用戶，以及一組不喜歡這部電影的用戶。 在生成推薦的階段，將產生許多集合——主要是其他集合的並集或交集。 我們還將為每個用戶提供有序的建議和相似用戶列表。

為了計算相似度指數，我們將使用 Jaccard 指數公式的變體。 該公式最初被稱為“coefficient de communaute”（由 Paul Jaccard 創造），它比較兩個集合併產生一個介於 0 和 1.0 之間的簡單十進制統計量：

該公式涉及將任一集合中的公共元素的數量除以兩個集合中所有元素的數量（僅計算一次）。 兩個相同集合的 Jaccard 索引始終為 1，而沒有公共元素的兩個集合的 Jaccard 索引始終為 0。現在我們知道如何比較兩個集合，讓我們想一個可以用來比較兩個集合的策略用戶。 如前所述，從系統的角度來看，用戶是三樣東西：一個標識符、一組喜歡的電影和一組不喜歡的電影。 如果我們只根據他們喜歡的電影集來定義用戶的相似度指數，我們可以直接使用 Jaccard 指數公式：

這裡，U1 和 U2 是我們要比較的兩個用戶，L1 和 L2 分別是 U1 和 U2 喜歡的電影集。 現在，如果你想一想，喜歡同一部電影的兩個用戶是相似的，那麼不喜歡同一部電影的兩個用戶也應該是相似的。 這是我們稍微修改方程的地方：

我們現在不僅在公式的分子中考慮常見的喜歡，還添加了常見的不喜歡的數量。 在分母中，我們取用戶喜歡或不喜歡的所有項目的數量。 既然我們已經以獨立的方式考慮了好惡，我們還應該考慮兩個用戶的偏好截然相反的情況。 一個喜歡一部電影另一個不喜歡的兩個用戶的相似度指數不應該為0：

這是一個很長的公式！ 但這很簡單，我保證。 它與我們之前的公式類似，但分子略有不同。 我們現在從兩個用戶的共同好惡數中減去相互衝突的好惡數。 這導致相似性指數公式的值範圍介於 -1.0 和 1.0 之間。 具有相同品味的兩個用戶將具有 1.0 的相似指數，而在電影中具有完全衝突的品味的兩個用戶將具有 -1.0 的相似指數。

既然我們已經知道如何根據兩個用戶的電影品味來比較他們，那麼在開始實施我們自製的推薦引擎算法之前，我們必須再探索一個公式：

讓我們稍微分解一下這個等式。 我們所說的P(U,M)是用戶U喜歡電影M的可能性。 ZL和ZD分別是用戶U與所有喜歡或不喜歡電影M的用戶的相似度指數之和。 |ML|+|MD| 表示喜歡或不喜歡電影M的用戶總數。 結果P(U,M)產生一個介於 -1.0 和 1.0 之間的數字。

就是這樣。 在下一節中，我們可以使用這些公式開始實現我們的基於協作記憶的推薦引擎。

構建推薦引擎

我們將把這個推薦引擎構建為一個非常簡單的 Node.js 應用程序。 前端的工作也會很少，主要是一些 HTML 頁面和表單（我們將使用 Bootstrap 使頁面看起來整潔）。 在服務器端，我們將使用 CoffeeScript。 該應用程序將有一些 GET 和 POST 路由。 即使我們在應用程序中有用戶的概念，我們也不會有任何復雜的註冊/登錄機制。 對於持久性，我們將使用通過 NPM 提供的 Bourne 包，它使應用程序能夠將數據存儲在純 JSON 文件中，並對它們執行基本的數據庫查詢。 我們將使用 Express.js 來簡化管理路由和處理程序的過程。

此時，如果您是 Node.js 開發的新手，您可能希望克隆 GitHub 存儲庫，以便更輕鬆地學習本教程。 與任何其他 Node.js 項目一樣，我們將首先創建一個 package.json 文件並安裝該項目所需的一組依賴包。 如果您正在使用克隆的存儲庫，則 package.json 文件應該已經存在，從那里安裝依賴項將需要您執行“$ npm install”。 這將安裝 package.json 文件中列出的所有包。

這個項目我們需要的 Node.js 包是：

• 異步
• 伯恩
• 咖啡腳本
• 表示
• 玉
• 下劃線

我們將通過將所有相關方法拆分為四個獨立的 CoffeeScript 類來構建推薦引擎，每個類都將存儲在“lib/engine”下：Engine、Rater、Similars 和 Suggestions。 類 Engine 將負責為推薦引擎提供一個簡單的 API，並將其他三個類綁定在一起。 評分者將負責跟踪喜歡和不喜歡（作為評分者類的兩個獨立實例）。 Similars 和 Suggestions 將分別負責為用戶確定和跟踪相似用戶和推薦項目。

跟踪喜歡和不喜歡

讓我們首先從我們的評估者類開始。 這是一個簡單的：

 class Rater constructor: (@engine, @kind) -> add: (user, item, done) -> remove: (user, item, done) -> itemsByUser: (user, done) -> usersByItem: (item, done) ->

如本教程前面所述，我們將有一個 Rater 實例用於表示喜歡，另一個用於表示不喜歡。 為了記錄用戶喜歡某個項目，我們會將它們傳遞給“Rater#add()”。 同樣，要刪除評級，我們會將它們傳遞給“Rater#remove()”。

由於我們使用 Bourne 作為無服務器數據庫解決方案，我們會將這些評分存儲在名為“./db-#{@kind}.json”的文件中，其中 kind 是“likes”或“dislikes”。 我們將在 Rater 實例的構造函數中打開數據庫：

 constructor: (@engine, @kind) -> @db = new Bourne "./db-#{@kind}.json"

這將使添加評分記錄變得像在“Rater#add()”方法中調用 Bourne 數據庫方法一樣簡單：

 @db.insert user: user, item: item, (err) =>

刪除它們也是類似的（“db.delete”而不是“db.insert”）。 但是，在我們添加或刪除某些內容之前，我們必須確保它不存在於數據庫中。 理想情況下，對於一個真實的數據庫，我們可以將它作為一個單一的操作來完成。 使用 Bourne，我們必須先進行手動檢查； 並且，一旦插入或刪除完成，我們需要確保為這個用戶重新計算相似度指數，然後生成一組新的建議。 “Rater#add()”和“Rater#remove()”方法看起來像這樣：

 add: (user, item, done) -> @db.find user: user, item: item, (err, res) => if res.length > 0 return done() @db.insert user: user, item: item, (err) => async.series [ (done) => @engine.similars.update user, done (done) => @engine.suggestions.update user, done ], done remove: (user, item, done) -> @db.delete user: user, item: item, (err) => async.series [ (done) => @engine.similars.update user, done (done) => @engine.suggestions.update user, done ], done

為簡潔起見，我們將跳過檢查錯誤的部分。 這在文章中可能是合理的做法，但不是忽略實際代碼中錯誤的藉口。

其他兩個方法，“Rater#itemsByUser()”和“Rater#usersByItem()”這個類將涉及到他們的名字所暗示的 - 分別查找用戶評分的項目和對項目進行評分的用戶。 例如，當使用kind = “likes”實例化 Rater 時，“Rater#itemsByUser()” 將找到用戶評分的所有項目。

尋找相似用戶

繼續我們的下一堂課：Similars。 這個類將幫助我們計算和跟踪用戶之間的相似度指數。 如前所述，計算兩個用戶之間的相似性涉及分析他們喜歡和不喜歡的項目集。 為此，我們將依靠 Rater 實例來獲取相關項目的集合，然後使用相似度指數公式確定某些用戶對的相似度指數。

就像我們之前的類 Rater 一樣，我們將把所有內容放在名為“./db-similars.json”的 Bourne 數據庫中，我們將在 Rater 的構造函數中打開該數據庫。 該類將有一個方法“Similars#byUser()”，它可以讓我們通過簡單的數據庫查找來查找與給定用戶相似的用戶：

 @db.findOne user: user, (err, {others}) =>

然而，這個類中最重要的方法是“Similars#update()”，它的工作原理是獲取一個用戶併計算一個相似的其他用戶的列表，並將該列表連同他們的相似度指數一起存儲在數據庫中。 它首先找到用戶的好惡：

 async.auto userLikes: (done) => @engine.likes.itemsByUser user, done userDislikes: (done) => @engine.dislikes.itemsByUser user, done , (err, {userLikes, userDislikes}) => items = _.flatten([userLikes, userDislikes])

我們還找到了所有對這些項目進行評分的用戶：

 async.map items, (item, done) => async.map [ @engine.likes @engine.dislikes ], (rater, done) => rater.usersByItem item, done , done , (err, others) =>

接下來，對於每個其他用戶，我們計算相似度索引並將其全部存儲在數據庫中：

 async.map others, (other, done) => async.auto otherLikes: (done) => @engine.likes.itemsByUser other, done otherDislikes: (done) => @engine.dislikes.itemsByUser other, done , (err, {otherLikes, otherDislikes}) => done null, user: other similarity: (_.intersection(userLikes, otherLikes).length+_.intersection(userDislikes, otherDislikes).length-_.intersection(userLikes, otherDislikes).length-_.intersection(userDislikes, otherLikes).length) / _.union(userLikes, otherLikes, userDislikes, otherDislikes).length , (err, others) => @db.insert user: user others: others , done

在上面的代碼片段中，您會注意到我們有一個本質上與我們的相似性指數公式相同的表達式，它是 Jaccard 指數公式的一個變體。

生成推薦

我們的下一節課，建議，是所有預測發生的地方。 與 Similars 類一樣，我們依賴另一個名為“./db-suggestions.json”的 Bourne 數據庫，在構造函數中打開。

該類將有一個方法“Suggestions#forUser()”來查找給定用戶的計算建議：

 forUser: (user, done) -> @db.findOne user: user, (err, {suggestions}={suggestion: []}) -> done null, suggestions

計算這些結果的方法是“Suggestions#update()”。 此方法，如“Similars#update()”，將用戶作為參數。 該方法首先列出與給定用戶相似的所有用戶，以及給定用戶未評分的所有項目：

 @engine.similars.byUser user, (err, others) => async.auto likes: (done) => @engine.likes.itemsByUser user, done dislikes: (done) => @engine.dislikes.itemsByUser user, done items: (done) => async.map others, (other, done) => async.map [ @engine.likes @engine.dislikes ], (rater, done) => rater.itemsByUser other.user, done , done , done , (err, {likes, dislikes, items}) => items = _.difference _.unique(_.flatten items), likes, dislikes

一旦我們列出了所有其他用戶和未評分的項目，我們就可以開始計算一組新的推薦，方法是刪除任何以前的推薦集，迭代每個項目，並根據可用信息計算用戶喜歡它的可能性：

 @db.delete user: user, (err) => async.map items, (item, done) => async.auto likers: (done) => @engine.likes.usersByItem item, done dislikers: (done) => @engine.dislikes.usersByItem item, done , (err, {likers, dislikers}) => numerator = 0 for other in _.without _.flatten([likers, dislikers]), user other = _.findWhere(others, user: other) if other? numerator += other.similarity done null, item: item weight: numerator / _.union(likers, dislikers).length , (err, suggestions) =>

完成後，我們將其保存回數據庫：

 @db.insert user: user suggestions: suggestions , done

公開庫 API

在 Engine 類中，我們將所有內容綁定在一個簡潔的類似 API 的結構中，以便從外部世界輕鬆訪問：

 class Engine constructor: -> @likes = new Rater @, 'likes' @dislikes = new Rater @, 'dislikes' @similars = new Similars @ @suggestions = new Suggestions @

一旦我們實例化了一個 Engine 對象：

 e = new Engine

我們可以輕鬆添加或刪除喜歡和不喜歡：

 e.likes.add user, item, (err) -> e.dislikes.add user, item, (err) ->

我們還可以開始更新用戶相似度指數和建議：

 e.similars.update user, (err) -> e.suggestions.update user, (err) ->

最後，重要的是從各自的“.coffee”文件中導出這個 Engine 類（和所有其他類）：

 module.exports = Engine

然後，通過使用一行創建一個“index.coffee”文件從包中導出引擎：

 module.exports = require './engine'

創建用戶界面

為了能夠在本教程中使用推薦引擎算法，我們希望通過 Web 提供一個簡單的用戶界面。 為此，我們在“web.iced”文件中生成一個 Express 應用程序並處理一些路由：

 movies = require './data/movies.json' Engine = require './lib/engine' e = new Eengine app = express() app.set 'views', "#{__dirname}/views" app.set 'view engine', 'jade' app.route('/refresh') .post(({query}, res, next) -> async.series [ (done) => e.similars.update query.user, done (done) => e.suggestions.update query.user, done ], (err) => res.redirect "/?user=#{query.user}" ) app.route('/like') .post(({query}, res, next) -> if query.unset is 'yes' e.likes.remove query.user, query.movie, (err) => res.redirect "/?user=#{query.user}" else e.dislikes.remove query.user, query.movie, (err) => e.likes.add query.user, query.movie, (err) => if err? return next err res.redirect "/?user=#{query.user}" ) app.route('/dislike') .post(({query}, res, next) -> if query.unset is 'yes' e.dislikes.remove query.user, query.movie, (err) => res.redirect "/?user=#{query.user}" else e.likes.remove query.user, query.movie, (err) => e.dislikes.add query.user, query.movie, (err) => res.redirect "/?user=#{query.user}" ) app.route('/') .get(({query}, res, next) -> async.auto likes: (done) => e.likes.itemsByUser query.user, done dislikes: (done) => e.dislikes.itemsByUser query.user, done suggestions: (done) => e.suggestions.forUser query.user, (err, suggestions) => done null, _.map _.sortBy(suggestions, (suggestion) -> -suggestion.weight), (suggestion) => _.findWhere movies, id: suggestion.item , (err, {likes, dislikes, suggestions}) => res.render 'index', movies: movies user: query.user likes: likes dislikes: dislikes suggestions: suggestions[...4] )

在應用程序中，我們處理四個路線。 索引路由“/”是我們通過渲染 Jade 模板來提供前端 HTML 的地方。 生成模板需要電影列表、當前用戶的用戶名、用戶的好惡以及對用戶的前四項建議。 Jade 模板的源代碼未在文章中提及，但可在 GitHub 存儲庫中找到。

“/like”和“/dislike”路由是我們接受POST請求以記錄用戶的好惡的地方。 如有必要，兩條路線都會通過首先刪除任何衝突的評級來添加評級。 例如，用戶喜歡他們以前不喜歡的東西會導致處理程序首先刪除“不喜歡”評級。 如果需要，這些路線還允許用戶“不喜歡”或“不喜歡”一個項目。

最後，“/refresh”路由允許用戶按需重新生成他們的推薦集。 雖然，只要用戶對項目進行任何評級，此操作就會自動執行。

試駕

如果您嘗試按照本文從頭開始實現此應用程序，則需要先執行最後一步，然後才能對其進行測試。 您需要在“data/movies.json”中創建一個“.json”文件，並使用一些電影數據填充它，如下所示：

 [ { "id": "1", "name": "Transformers: Age of Extinction", "thumb": { "url": "//upload.wikimedia.org/wikipedia/en/7/7f/Inception_ver3.jpg" } }, // … ]

您可能想要復制 GitHub 存儲庫中可用的一個，該存儲庫預先填充了一些電影名稱和縮略圖 URL。

一旦所有源代碼都準備好並連接在一起，啟動服務器進程需要調用以下命令：

 $ npm start

假設一切順利，您應該會在終端上看到以下文本：

 Listening on 5000

由於我們沒有實現任何真正的用戶認證系統，原型應用程序僅依賴於訪問“http://localhost:5000”後選擇的用戶名。 輸入用戶名並提交表單後，您將被帶到另一個頁面，其中包含兩個部分：“推薦電影”和“所有電影”。 由於我們缺乏基於協作記憶的推薦引擎（數據）中最重要的元素，我們將無法向這個新用戶推薦任何電影。

此時，您應該打開另一個瀏覽器窗口到“http://localhost:5000”並在那里以不同的用戶身份登錄。 作為第二個用戶喜歡和不喜歡一些電影。 返回第一個用戶的瀏覽器窗口並對一些電影進行評分。 確保為兩個用戶至少評價幾部常見的電影。 您應該立即開始看到建議。

改進

在本算法教程中，我們構建的是一個原型推薦引擎。 當然有改進這個引擎的方法。 本節將簡要介紹一些需要改進才能大規模使用的領域。 但是，在需要可擴展性、穩定性和其他此類屬性的情況下，您應該始終求助於使用經過時間考驗的良好解決方案。 與本文的其餘部分一樣，這裡的想法是提供一些關於推薦引擎如何工作的見解。 與其討論當前方法的明顯缺陷（例如我們已經實現的一些方法中的競態條件），不如在更高的層次上討論改進。

這裡一個非常明顯的改進是使用真實的數據庫，而不是我們基於文件的解決方案。 基於文件的解決方案在小規模原型中可能工作得很好，但對於實際使用來說，這根本不是一個合理的選擇。 Redis 是眾多選擇中的一種。 Redis 速度很快，並且具有在處理類似集合的數據結構時非常有用的特殊功能。

另一個我們可以簡單解決的問題是，每次用戶製作或更改電影評分時，我們都會計算新的推薦。 我們應該為用戶排隊這些推薦更新請求並在後台執行它們——也許設置一個定時刷新間隔，而不是實時進行重新計算。

除了這些“技術”選擇之外，還可以做出一些戰略選擇來改進建議。 隨著項目和用戶數量的增長，生成推薦的成本將越來越高（在時間和系統資源方面）。 可以通過只選擇一部分用戶來生成推薦來加快速度，而不是每次都處理整個數據庫。 例如，如果這是一個餐廳推薦引擎，您可以將相似用戶集限制為僅包含居住在同一城市或州的用戶。

其他改進可能涉及採用混合方法，其中基於協同過濾和基於內容的過濾生成推薦。 這對於諸如電影之類的內容特別好，其中內容的屬性已明確定義。 例如，Netflix 採用了這條路線，根據其他用戶的活動和電影的屬性來推薦電影。

結論

基於內存的協作推薦引擎算法可能是一個非常強大的東西。 我們在本文中試驗的可能很原始，但也很簡單：易於理解，易於構建。 它可能遠非完美，但推薦引擎的健壯實現，例如 Recommendable，是建立在類似的基本思想之上的。

與大多數其他涉及大量數據的計算機科學問題一樣，獲得正確的推薦很大程度上取決於選擇正確的算法和要處理的內容的適當屬性。 我希望這篇文章能讓您了解在使用協作式基於內存的推薦引擎時會發生什麼。