Slope One 之一 : 簡單高效的協(xié)同過濾算法(轉(zhuǎn))(
      原文地址：http://blog.sina.com.cn/s/blog_4d9a06000100am1d.html

       現(xiàn)在做的一個(gè)項(xiàng)目中需要用到推薦算法, 在網(wǎng)上查了一下. Beyond Search介紹了一個(gè)協(xié)同過濾算法(Collaborative Filtering) : Slope One;和其它類似算法相比, 它的最大優(yōu)點(diǎn)在于算法很簡單, 易于實(shí)現(xiàn), 執(zhí)行效率高, 同時(shí)推薦的準(zhǔn)確性相對很高;
     
基本概念
       Slope One的基本概念很簡單, 例子1, 用戶X, Y和A都對Item1打了分. 同時(shí)用戶X,Y還對Item2打了分, 用戶A對Item2可能會打多少分呢?

User	Rating to Item 1	Rating to Item 2
X	5	3
Y	4	3
A	4	?

        根據(jù)SlopeOne算法, 應(yīng)該是:4 - ((5-3) + (4-3))/2 = 2.5.
        解釋一下. 用戶X對Item1的rating是5, 對Item2的rating是3, 那么他可能認(rèn)為Item2應(yīng)該比Item1少兩分. 同時(shí)用戶Y認(rèn)為Item2應(yīng)該比Item1少1分. 據(jù)此我們知道所有對Item1和Item2都打了分的用戶認(rèn)為Item2會比Item1平均少1.5分. 所以我們有理由推薦用戶A可能會對Item2打(4-1.5)=2.5分;

        很簡單是不是? 找到對Item1和Item2都打過分的用戶, 算出rating差的平均值, 這樣我們就能推測出對Item1打過分的用戶A對Item2的可能Rating, 并據(jù)此向A用戶推薦新項(xiàng)目.
        這里我們能看出Slope One算法的一個(gè)很大的優(yōu)點(diǎn), 在只有很少的數(shù)據(jù)時(shí)候也能得到一個(gè)相對準(zhǔn)確的推薦, 這一點(diǎn)可以解決Cold Start的問題.

       加權(quán)算法
       接下來我們看看加權(quán)算法(Weighted Slope One). 如果有100個(gè)用戶對Item1和Item2都打過分, 有1000個(gè)用戶對Item3和Item2也打過分. 顯然這兩個(gè)rating差的權(quán)重是不一樣的. 因此我們的計(jì)算方法是
      (100*(Rating 1 to 2) + 1000(Rating 3 to 2)) / (100 + 1000)。更詳細(xì)的加權(quán)算法實(shí)例：請看這里

       上面討論的是用戶只對項(xiàng)目的喜好程度打分.還有一種情況下用戶也可以對項(xiàng)目的厭惡程度打分. 這時(shí)可以使用雙極SlopeOne算法(BI-Polar SlopeOne). 我還在研究這篇論文,搞懂了再寫吧, 呵呵;

       
        Slope One 算法是由 Daniel Lemire 教授在 2005 年提出. 這里可以找到論文原文(PDF);上面也列出了幾個(gè)參考實(shí)現(xiàn). 現(xiàn)在有Python, Java和Erlang, 還沒有C#.這篇: tutorial about how to implement Slope One in Python是一個(gè)很好的怎么實(shí)現(xiàn)SlopeOne并使用它來推薦的例子。

      Slope One 算法 (三) ：加權(quán)平均實(shí)例
原文地址：http://blog.sina.com.cn/s/blog_4d9a06000100am69.html

1. 例子：
2.  
3. 首先計(jì)算item1和item2的平均差值，((5-3)+(3-4))/2=0.5，還有item1和item3的平均差值，就是5-2=3，然后推算lucy對item1的評分，根據(jù)item1和item2的平均差值來看lucy對item1的評分可能為2+0.5=2.5，同理根據(jù)item1和item3的平均差值lucy對item1的評分可能為5+3=8.
4. 現(xiàn)在如何取舍那？使用加權(quán)平均數(shù)應(yīng)該是一種比較好的方法:（因?yàn)?.5是根據(jù)兩個(gè)值推算的，8是通過一個(gè)只推算的）
5. slope one 算法差不多真的就是這么簡單了！
6. 有一個(gè)開源的Java程序taste里面有一個(gè)完整的slope one算法的實(shí)現(xiàn)，包括程序和一個(gè)關(guān)于grouplens數(shù)據(jù)的實(shí)例程序（或者說是驗(yàn)證程序……）。
7. 個(gè)人覺得slope one 很好、很強(qiáng)大呀！足夠簡單，推薦準(zhǔn)確度也不遜色與其他復(fù)雜的推薦算法（當(dāng)然，這個(gè)東西更大程度上取決與數(shù)據(jù)樣本）。而且taste程序?qū)懙囊埠懿诲e(cuò)，稍加改造應(yīng)該就可以用了。

 Slope One 之二: C#實(shí)現(xiàn) 
        原文地址：http://blog.sina.com.cn/s/blog_4d9a06000100am69.html

        
上一篇簡單介紹了Slope One算法的概念, 這次介紹C#實(shí)現(xiàn)
使用基于Slope One算法的推薦需要以下數(shù)據(jù):
1. 有一組用戶
2. 有一組Items(文章, 商品等)
3. 用戶會對其中某些項(xiàng)目打分(Rating)表達(dá)他們的喜好
Slope One算法要解決的問題是, 對某個(gè)用戶, 已知道他對其中一些Item的Rating了, 向他推薦一些他還沒有Rating的Items, 以增加銷售機(jī)會. :-)

一個(gè)推薦系統(tǒng)的實(shí)現(xiàn)包括以下三步:
1. 計(jì)算出任意兩個(gè)Item之間Rating的差值
2. 輸入某個(gè)用戶的Rating記錄, 推算出對其它Items的可能Rating值
3. 根據(jù)Rating的值排序, 給出Top Items;

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

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

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

	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

考慮到加權(quán)算法, 還要記錄有多少人對這兩項(xiàng)打了分(Freq), 我們先定義一個(gè)結(jié)構(gòu)來保存Rating:
    public class Rating
    {
        public float Value { get; set; }
        public int Freq { get; set; }

        public float AverageValue
        {
            get {return Value / Freq;}
        }
    }
我決定用一個(gè)Dictionary來保存這個(gè)結(jié)果矩陣:
    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; }
        }
    }

接下來我們來實(shí)現(xiàn)SlopeOne類. 首先創(chuàng)建一個(gè)RatingDifferenceCollection來保存矩陣, 還要創(chuàng)建HashSet來保持系統(tǒng)中總共有哪些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接收一個(gè)用戶的打分記錄(Item-Rating): public void AddUserRatings(IDictionary<int, float> userRatings)
AddUserRatings中有兩重循環(huán), 外層循環(huán)遍歷輸入中的所有Item, 內(nèi)層循環(huán)再遍歷一次, 計(jì)算出一對Item之間Rating的差存入_DiffMarix, 記得Freq加1, 以記錄我們又碰到這一對Items一次:
    Rating ratingDiff = _DiffMarix[item1Id, item2Id];
    ratingDiff.Value += item1Rating - item2Rating;
    ratingDiff.Freq += 1;

對每個(gè)用戶調(diào)用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

第二步:輸入某個(gè)用戶的Rating記錄, 推算出對其它Items的可能Rating值:
public IDictionary<int, float> Predict(IDictionary<int, float> userRatings)
也是兩重循環(huán), 外層循環(huán)遍歷_Items中所有的Items; 內(nèi)層遍歷userRatings, 用此用戶的ratings結(jié)合第一步得到的矩陣, 推算此用戶對系統(tǒng)中每個(gè)項(xiàng)目的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預(yù)測后,就可以按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

改進(jìn):
觀察之前產(chǎn)生的矩陣可以發(fā)現(xiàn), 其中有很多浪費(fèi)的空間; 例如: 對角線上永遠(yuǎn)是不會有值的. 因?yàn)槲覀兪怯镁€性表保存矩陣值, 已經(jīng)避免了這個(gè)問題;
對角線下方的值和對角線上方的值非常對稱,下方的值等于上方的值乘以-1; 在數(shù)據(jù)量很大的時(shí)候是很大的浪費(fèi). 我們可以通過修改RatingDifferenceCollection來完善. 可以修改GetKey方法, 用Item Pair來作為Key:
    private string GetKey(int Item1Id, int Item2Id) {
        return (Item1Id < Item2Id) ? Item1Id + "/" + Item2Id : Item2Id + "/" + Item1Id ;;
    }
完整代碼在這里,在.net 3.5上調(diào)試通過;

 

 

Reference:
Tutorial about how to implement Slope One in Python
Slope One Predictors for Online Rating-Based Collaborative Filtering
Recommender Systems: Slope One


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SlopeOne
{
    public class Rating
    {
        public float Value { get; set; }
        public int Freq { get; set; }

        public float AverageValue
        {
            get { return Value / Freq; }
        }
    }

    public class RatingDifferenceCollection : Dictionary<string, Rating>
    {
        private string GetKey(int Item1Id, int Item2Id)
        {
            return (Item1Id < Item2Id) ? Item1Id + "/" + Item2Id : Item2Id + "/" + Item1Id ;
        }

        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; }
        }
    }

     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

        public void AddUserRatings(IDictionary<int, float> userRatings)
        {
            foreach (var item1 in userRatings)
            {
                int item1Id = item1.Key;
                float item1Rating = item1.Value;
                _Items.Add(item1.Key);

                foreach (var item2 in userRatings)
                {
                    if (item2.Key <= item1Id) continue; // Eliminate redundancy
                    int item2Id = item2.Key;
                    float item2Rating = item2.Value;

                    Rating ratingDiff;
                    if (_DiffMarix.Contains(item1Id, item2Id))
                    {
                        ratingDiff = _DiffMarix[item1Id, item2Id];
                    }
                    else
                    {
                        ratingDiff = new Rating();
                        _DiffMarix[item1Id, item2Id] = ratingDiff;
                    }

                    ratingDiff.Value += item1Rating - item2Rating;
                    ratingDiff.Freq += 1;
                }
            }
        }

        // Input ratings of all users
        public void AddUerRatings(IList<IDictionary<int, float>> Ratings)
        {
            foreach(var userRatings in Ratings)
            {
                AddUserRatings(userRatings);
            }
        }

        public IDictionary<int, float> Predict(IDictionary<int, float> userRatings)
        {
            Dictionary<int, float> Predictions = new Dictionary<int, float>();
            foreach (var itemId in this._Items)
            {
                if (userRatings.Keys.Contains(itemId))    continue; // User has rated this item, just skip it

                Rating itemRating = new Rating();

                foreach (var userRating in userRatings)
                {
                    if (userRating.Key == itemId) continue;
                    int inputItemId = userRating.Key;
                    if (_DiffMarix.Contains(itemId, inputItemId))
                    {
                        Rating diff = _DiffMarix[itemId, inputItemId];
                        itemRating.Value += diff.Freq * (userRating.Value + diff.AverageValue * ((itemId < inputItemId) ? 1 : -1));
                        itemRating.Freq += diff.Freq;
                    }
                }
                Predictions.Add(itemId, itemRating.AverageValue);               
            }
            return Predictions;
        }

        public static void Test()
        {
            SlopeOne test = new SlopeOne();

            Dictionary<int, float> userRating = new Dictionary<int, float>();
            userRating.Add(1, 5);
            userRating.Add(2, 4);
            userRating.Add(3, 4);
            test.AddUserRatings(userRating);

            userRating = new Dictionary<int, float>();
            userRating.Add(1, 4);
            userRating.Add(2, 5);
            userRating.Add(3, 3);
            userRating.Add(4, 5);
            test.AddUserRatings(userRating);

            userRating = new Dictionary<int, float>();
            userRating.Add(1, 4);
            userRating.Add(2, 4);
            userRating.Add(4, 5);
            test.AddUserRatings(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);
            }
        }
    }
}