協作過濾/推薦系統的性能和方法

Question

我真的很感興趣瞭解人們如何處理協作過濾和推薦引擎等。我的意思是腳本的性能比任何其他更多。我已經說過閱讀編程集體智慧，這是非常有趣的，但往往更注重事物的算法方面。

我目前只有2k用戶，但我現在的系統已被證明完全不是未來的證明，而且已經在服務器上徵稅了。整個系統基於向用戶提供帖子的建議。我的應用程序是PHP/MySQL，但我使用一些MongoDB進行協作過濾 - 我在一個大的Amazon EC2實例上。我的設置實際上是一個2步驟的過程。首先我計算項目之間的相似度，然後使用這些信息來提出建議。以下是它的工作原理：

首先我的系統計算用戶帖子之間的相似度。該腳本運行一個算法，該算法返回每對的相似度分數。該算法檢查信息，例如 - 常見標籤，常見評論者和常見類似者，並且能夠返回相似性分數。過程如下：

• 每次添加帖子，添加了標籤，評論或喜歡我將它添加到隊列中。
• 我通過cron處理這個隊列（每天一次），找出每個帖子的相關信息，例如，評論者和相似者的user_id's以及tag_id的。我將這些信息以這種結構保存到MongoDB：{「post_id」：1，「tag_ids」：[12,44,67]，「commenter_user_ids」：[6,18,22]，「liker_user_ids」：[87， 6]}。這使我最終可以建立一個MongoDB集合，使我能夠方便快捷地訪問所有相關信息，以便在我嘗試計算相似度時使用
• 然後運行另一個cron腳本（每天一次，但在之前）再次通過隊列。這一次，對於隊列中的每個帖子，我從MongoDB集合中獲取條目，並將其與其他所有條目進行比較。當2個條目具有一些匹配信息時，我根據相似性給他們+1。最後，我對每對帖子都有一個總分。我將分數保存到具有以下結構的不同MongoDB集合中：{「post_id」：1，「similar」：{「23」：2，「2」：5，「7」：2}}（'similar'是一個key => value數組，其中的post_id爲key，相似度分數爲value。

我有5k個帖子，所以上述都很難在服務器上有大量的讀寫操作現在，這只是問題的一半，然後我使用這些信息來確定哪些帖子會對特定用戶感興趣，因此，我每運行一小時一個cron腳本，它運行一個腳本，計算網站上每個用戶的推薦帖子。過程如下：

• 該腳本首先決定用戶將獲得哪種類型的建議。這是一個50-50的變化 - 1.類似於你的一個帖子的帖子或者2.類似於你已經與之交互的帖子的帖子。
• 如果是1，那麼腳本從MySQL獲取用戶post_ids，然後使用它們從MongoDB獲取類似的帖子。該腳本採用最相似的帖子，尚未推薦給用戶。
• 如果是2，腳本抓取用戶在MySQL中評論或喜歡的所有帖子，並使用它們的ID在上面1中執行相同的操作。

不幸的是，每小時推薦腳本變得非常耗費資源，並且正在慢慢花費更多的時間來完成......目前需要10-15分鐘。我擔心在某些時候我無法再提供小時推薦。

我只是想知道如果有人覺得我可以接近這更好嗎？

Answer 1

我開始計劃如何做到這一點。 第一件事是可能擺脫你的數據庫技術，或者用triplestore或graph技術來補充它。這應該爲分析類似的喜好或主題提供更好的性能。

接下來是得到一個子集。獲取用戶的一些興趣並獲得一小羣擁有類似興趣的用戶。

然後以某種有意義的順序建立喜歡的索引並計算倒數（分割和征服 - 這與合併排序非常相似，無論如何，您都想排序來計算拆分倒數）。

我希望有所幫助 - 你不想把所有事情都與其他事情進行比較，或者肯定是N2。你應該能夠用常數和線性之間的某些東西來取代它，如果你把那些有相似喜歡並使用它們的人組合起來。

例如，從圖表的角度來看，他們最近喜歡的東西，看看邊緣，然後去追蹤它們，並分析這些用戶。也許可以在最近的一些最喜歡的文章上做這件事，然後從中找到一組普通的用戶，並使用它來進行協作過濾，以查找用戶可能喜歡的文章。那麼你處於一個可行的問題大小 - 特別是在沒有指數增長的圖表中（儘管可能在文章中有更多的邊緣遍歷 - 儘管只是給你找到可用數據的更多變化）

更好的是是要自己鍵入文章，以便如果文章被某人所喜歡，則可以基於其他用戶（即亞馬遜的「購買該文章的用戶也購買了」）來查看他們可能會喜歡的文章。

希望給出一些想法。對於圖形分析，有一些框架可以幫助像faunus的統計和派生。

Answer 2

有5000個帖子，那就是25,000,000個關係，增加O（n^2）。

您的第一個問題是您如何避免在批次運行時檢查如此多的關係。使用標籤或關鍵字將有助於內容匹配 - 並且您可以使用日期範圍來限制常見的「喜歡」。除此之外......我們將更多地瞭解lot更多關於建立關係的方法。

另一個考慮是當你建立關係。爲什麼你要等到批量運行時才能比較新的帖子和現有的數據？當然，爲了確保請求得到快速處理是非常有意義的 - 但是（除了平臺所施加的限制之外）爲什麼要在建立關係之前等待批處理啓動？使用異步消息隊列。

事實上，取決於處理消息需要多長時間，甚至可能會在檢索項目時而不是在創建時重新生成緩存關係數據。

如果我正在編寫一個平臺來測量與數據的關係，那麼我肯定會傾向於一個關係數據庫，在這個關係數據庫中，連接很容易，而且大部分邏輯都可以在數據庫上實現層。

當然可以減少系統交叉引用數據的時間長度。這正是map-reduce打算解決的問題 - 但這樣做的好處主要來自在多臺機器上並行運行算法 - 在一天結束時，它只需要很多時鐘週期。