推薦功能的兩種算法

openkk 12年前發布 | 1K 次閱讀 Mageia 4

    最近做了一個類似淘寶的根據用戶的操作，判斷出用戶對哪些產品感興趣，并按照一定關系推薦給用戶其它產品。查詢了一些資料，結果發現時下，很多地方都用到 了推薦，淘寶，優酷，迅雷等等，有時候確實讓人稱心如意，推薦的產品非常和你的胃口，不過也有時推薦的讓你莫名其妙。其實推薦的算法有很多種，而且不一定 有固定的模式，它會根據產品的特性，推薦的目的，以及其它方面的要求而不同。
不過具體的不一樣，但是其原理性的大概有以下幾種算法。專門研究算法的人寫的太深奧了，全部都是數學術語，太難懂了，我還是以自己的理解來說明下吧。
1、Apriori算法
    Apriori算法是很復雜的，基本思想如下：
    首先找出所有的已收集到的集合，即根據操作記錄的集合。然后由這個集合產生強關聯規則。然后使用第1步的集合產生期望的規則，產生只包含集合的項的所有規 則，其中每一條規則的右部只有一項，這里采用的是中規則的定義。一旦這些規則被生成，那么只有那些大于用戶給定的最小可信度的規則才被留下來。為了生成所 有頻集，使用了遞推的方法。
    我理解的基本步驟如下。
    基本步驟是
    a、根據操作收集對象的屬性；

    b、根據已收集的屬性為條件，從包含所有數據的庫中搜索與之相關的對象；

    c、按照一定的規則過濾，剩下的向用戶推薦。

    舉例來說，例如在淘寶買東西，用戶買了手機，電腦，衣服等，每買一件都記錄下來，作為推薦的依據；那么如何推薦呢，手機和電腦屬于數碼類，那么推薦就可以 推薦相機等數碼產品，同時，還可以推薦其它品牌的手機或電腦。根據衣服推薦亦相同。當然了，這只是很簡單的推薦，不一定能對用戶的心思。要想做準確的推薦 在每一步中都要進行處理。
    2、Slope One算法
    使用基于Slope One算法的推薦需要以下數據:
    1. 有一組用戶
    2. 有一組Items(文章, 商品等)
    3. 用戶會對其中某些項目打分(Rating)表達他們的喜好
    Slope One算法要解決的問題是, 對某個用戶, 已知道他對其中一些Item的Rating了, 向他推薦一些他還沒有Rating的Items, 以增加銷售機會. :-)

    一個推薦系統的實現包括以下三步:
    1. 計算出任意兩個Item之間Rating的差值
    2. 輸入某個用戶的Rating記錄, 推算出對其它Items的可能Rating值
    3. 根據Rating的值排序, 給出Top Items;

    第一步:例如我們有三個用戶和4個Items, 用戶打分的情況如下表.

 
    Ratings User1 User2 User3   
    Item1 5 4 4   
    Item2 4 5 4   
    Item3 4 3 N/A   
    Item4 N/A 5 5

    在第一步中我們的工作就是計算出Item之間兩兩的打分之差, 也就是使說計算出以下矩陣:

    Item1 Item2 Item3 Item4   
    Item1 N/A 0/3 2/2 -2/2   
    Item2 0/3 N/A 2/2 -1/2   
    Item3 -2/2 -2/2 N/A -2/1   
    Item4 2/2 1/2 2/1 N/A

    考慮到加權算法, 還要記錄有多少人對這兩項打了分(Freq), 我們先定義一個結構來保存Rating:

    public class Rating

       {

           public float Value { get; set; }

           public int Freq { get; set; }



       public float AverageValue  
       {  
           get {return Value / Freq;}  
       }  
   }  </pre><br />



</div>


   用一個Dictionary來保存這個結果矩陣:


    public class RatingDifferenceCollection : Dictionary<string, Rating>

    {

        private string GetKey(int Item1Id, int Item2Id)

        {

            return Item1Id + "/" + Item2Id;

        }



    public bool Contains(int Item1Id, int Item2Id)  
    {  
        return this.Keys.Contains<string>(GetKey(Item1Id, Item2Id));  
    }  

    public Rating this[int Item1Id, int Item2Id]  
    {  
        get {  
                return this[this.GetKey(Item1Id, Item2Id)];  
        }  
        set { this[this.GetKey(Item1Id, Item2Id)] = value; }  
    }  
}  </pre><br />



</div>


    接下來我們來實現SlopeOne類. 首先創建一個RatingDifferenceCollection來保存矩陣, 還要創建HashSet來保持系統中總共有哪些Items:


     public class SlopeOne

        {

            public RatingDifferenceCollection _DiffMarix = new RatingDifferenceCollection();  // The dictionary to keep the diff matrix

            public HashSet<int> _Items = new HashSet<int>();  // Tracking how many items totally



    方法AddUserRatings接收一個用戶的打分記錄(Item-Rating): public void AddUserRatings(IDictionary<int, float> userRatings)  
AddUserRatings中有兩重循環, 外層循環遍歷輸入中的所有Item, 內層循環再遍歷一次, 計算出一對Item之間Rating的差存入_DiffMarix, 記得Freq加1, 以記錄我們又碰到這一對Items一次:  
    Rating ratingDiff = _DiffMarix[item1Id, item2Id];  
    ratingDiff.Value += item1Rating - item2Rating;  
    ratingDiff.Freq += 1;  

    對每個用戶調用AddUserRatings后, 建立起矩陣. 但我們的矩陣是以表的形式保存:  
Rating Dif Freq   
Item1-2 0 3   
Item1-3 1 2   
Item2-1 0 3   
Item2-3 1 2   
Item3-1 -1 2   
Item3-2 -1 2   
Item1-4 -1 2   
Item2-4 -0.5 2   
Item3-4 -2 1   
Item4-1 1 2   
Item4-2 0.5 2   
Item4-3 2 1   

    第二步:輸入某個用戶的Rating記錄, 推算出對其它Items的可能Rating值:  
public IDictionary<int, float> Predict(IDictionary<int, float> userRatings)  
    也是兩重循環, 外層循環遍歷_Items中所有的Items; 內層遍歷userRatings, 用此用戶的ratings結合第一步得到的矩陣, 推算此用戶對系統中每個項目的Rating:  
    Rating itemRating = new Rating(); // Prediction of this user"s rating   
    ...  
    Rating diff = _DiffMarix[itemId, inputItemId]:  
    itemRating.Value += diff.Freq * (diff.AverageValue + userRating.Value);  
    itemRating.Freq += diff.Freq;  

    第三步:得到用戶的Rating預測后,就可以按rating排序, 向用戶推薦了. 測試一下:  
    Dictionary<int, float> userRating userRating = new Dictionary<int, float>();  
    userRating.Add(1, 5);  
    userRating.Add(3, 4);  
    IDictionary<int, float> Predictions = test.Predict(userRating);  
    foreach (var rating in Predictions)  
    {  
        Console.WriteLine("Item " + rating.Key + " Rating: " + rating.Value);  
    }      
    輸出:  
Item 2 Rating: 5  
Item 4 Rating: 6  

    改進:  
    觀察之前產生的矩陣可以發現, 其中有很多浪費的空間; 例如: 對角線上永遠是不會有值的. 因為我們是用線性表保存矩陣值, 已經避免了這個問題;  
對角線下方的值和對角線上方的值非常對稱,下方的值等于上方的值乘以-1; 在數據量很大的時候是很大的浪費. 我們可以通過修改RatingDifferenceCollection來完善. 可以修改GetKey方法, 用Item Pair來作為Key:  
    private string GetKey(int Item1Id, int Item2Id) {  
        return (Item1Id < Item2Id) ? Item1Id + "/" + Item2Id : Item2Id + "/" + Item1Id ;;  
    }  </pre> <p>C#實現代碼：<a href="/misc/goto?guid=5033828204671719905" target="_blank" target="_blank">http://download.csdn.net/detail/yysyangyangyangshan/4097454</a></p>



轉自：http://blog.csdn.net/yysyangyangyangshan/article/details/7303183



                    

                        
 本文由用戶 openkk 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

                        
 轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

                        
 本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！
寫博客

博客分類