經典演算法題每日演練——第六題協同推薦SlopeOne 演算法

相信大家對如下的 Category 都很熟悉，很多網站都有類似如下的功能，“商品推薦”,” 猜你喜歡 “，在實體店中我們有導購來為我們服務，在互聯網上
我們需要同樣的一種替代物，如果簡簡單單的在資料庫裏面去撈，去比較，幾乎是完成不了的, 這時我們就需要一種協同推薦演算法，來高效的推薦瀏覽者喜
歡的商品。

一：概念
SlopeOne 的思想很簡單，就是用均值化的思想來掩蓋個體的打分差異，舉個例子説明一下：

在這個圖中，系統該如何計算 “王五 “對” 電冰箱 “的打分值呢？剛才我們也説了，slopeone 是採用均值化的思想, 也就是：R 王五 =4-{[(5-10)+(4-5)]/2}=7 。
下面我們看看多於兩項的商品，如何計算打分值。
rb = (n * (ra – R(A->B)) + m * (rc – R(C->B)))/(m+n)
注意： a,b,c 代表 “商品” 。
ra 代表 “商品的打分值” 。
ra->b 代表 “A 組到 B 組的平均差（均值化）” 。
m,n 代表人數。

根據公式，我們來算一下。
r王五 = (2 * (4 – R(洗衣機->彩電)) + 2 * (10 – R(電冰箱->彩電))+ 2 * (5 – R(空調->彩電)))/(2+2+2)=6.8
是的，slopeOne 就是這麼簡單，實戰效果非常不錯。

二：實現
1：定義一個評分類 Rating 。

1 ///

2 /// 評分實體類
3 ///

4 public class Rating
5 {
6 ///

7 /// 記錄差值
8 ///

9 public float Value { get; set; }
10
11 ///

12 /// 記錄評分人數，方便公式中的 m 和 n 的值
13 ///

14 public int Freq { get; set; }
15
16 ///

17 /// 記錄打分使用者的 ID
18 ///

19 public HashSet hash_user = new HashSet();
20
21 ///

22 /// 平均值
23 ///

24 public float AverageValue
25 {
26 get { return Value / Freq; }
27 }
28 }

2：定義一個產品類

1 ///

2 /// 產品類
3 ///

4 public class Product
5 {
6 public int ProductID { get; set; }
7
8 public string ProductName { get; set; }
9
10 ///

11 /// 對產品的打分
12 ///

13 public float Score { get; set; }
14 }

3：SlopeOne 類
參考了互聯網上的例子，將二維矩陣做成線性表，有效的降低了空間複雜度。

1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5
6 namespace SupportCenter.Test
7 {
8 #region Slope One 演算法
9 ///

10 /// Slope One 演算法
11 ///

12 public class SlopeOne
13 {
14 ///

15 /// 評分系統
16 ///

17 public static Dictionary dicRatingSystem = new Dictionary();
18
19 public Dictionary dic_Martix = new Dictionary();
20
21 public HashSet hash_items = new HashSet();
22
23 #region 接收一個使用者的打分記錄
24 ///

25 /// 接收一個使用者的打分記錄
26 ///

27 /// 28 public void AddUserRatings(IDictionary> userRatings)
29 {
30 foreach (var user1 in userRatings)
31 {
32 //遍歷所有的 Item
33 foreach (var item1 in user1.Value)
34 {
35 //該產品的編號（具有唯一性）
36 int item1Id = item1.ProductID;
37
38 //該專案的評分
39 float item1Rating = item1.Score;
40
41 //將產品編號字存放在 hash 表中
42 hash_items.Add(item1.ProductID);
43
44 foreach (var user2 in userRatings)
45 {
46 //再次遍歷 item，用於計算倆倆 Item 之間的差值
47 foreach (var item2 in user2.Value)
48 {
49 //過濾掉同名的專案
50 if (item2.ProductID <= item1Id) 51 continue; 52 53 //該產品的名字 54 int item2Id = item2.ProductID; 55 56 //該專案的評分 57 float item2Rating = item2.Score; 58 59 Rating ratingDiff; 60 61 //用表的形式構建矩陣 62 var key = Tools.GetKey(item1Id, item2Id); 63 64 //將倆倆 Item 的差值存放到 Rating 中 65 if (dic_Martix.Keys.Contains(key)) 66 ratingDiff = dic_Martix[key]; 67 else 68 { 69 ratingDiff = new Rating(); 70 dic_Martix[key] = ratingDiff; 71 } 72 73 //方便以後以後 userrating 的編輯操作，（add) 74 if (!ratingDiff.hash_user.Contains(user1.Key)) 75 { 76 //value 儲存差值 77 ratingDiff.Value += item1Rating - item2Rating; 78 79 //説明計算過一次 80 ratingDiff.Freq += 1; 81 } 82 83 //記錄操作人的 ID，方便以後再次新增評分 84 ratingDiff.hash_user.Add(user1.Key); 85 } 86 } 87 } 88 } 89 } 90 #endregion 91 92 #region 根據矩陣的值，預測出該 Rating 中的值 93 ///

94 /// 根據矩陣的值，預測出該 Rating 中的值
95 ///

96 /// 97 ///
98 public IDictionary Predict(List userRatings)
99 {
100 Dictionary predictions = new Dictionary();
101
102 var productIDs = userRatings.Select(i => i.ProductID).ToList();
103
104 //迴圈遍歷_Items 中所有的 Items
105 foreach (var itemId in this.hash_items)
106 {
107 //過濾掉不需要計算的產品編號
108 if (productIDs.Contains(itemId))
109 continue;
110
111 Rating itemRating = new Rating();
112
113 // 內層遍歷 userRatings
114 foreach (var userRating in userRatings)
115 {
116 if (userRating.ProductID == itemId)
117 continue;
118
119 int inputItemId = userRating.ProductID;
120
121 //獲取該 key 對應專案的兩組 AVG 的值
122 var key = Tools.GetKey(itemId, inputItemId);
123
124 if (dic_Martix.Keys.Contains(key))
125 {
126 Rating diff = dic_Martix[key];
127
128 //關鍵點：運用公式求解（這邊為了節省空間，對角線兩側的值呈現奇函式的特性）
129 itemRating.Value += diff.Freq * (userRating.Score + diff.AverageValue * ((itemId < inputItemId) ? 1 : -1)); 130 131 //關鍵點：運用公式求解累計每兩組的人數 132 itemRating.Freq += diff.Freq; 133 } 134 } 135 136 predictions.Add(itemId, itemRating.AverageValue); 137 } 138 139 return predictions; 140 } 141 #endregion 142 } 143 #endregion 144 145 #region 工具類 146 ///

147 /// 工具類
148 ///

149 public class Tools
150 {
151 public static string GetKey(int Item1Id, int Item2Id)
152 {
153 return (Item1Id < Item2Id) ? Item1Id + "->” + Item2Id : Item2Id + “->” + Item1Id;
154 }
155 }
156 #endregion
157 }

4: 測試類 Program
這裏我們灌入了 userid=1000，2000，3000 的這三個人，然後我們預測 userID=3000 這個人對 “彩電” 的打分會是多少？

1 public class Program
2 {
3 static void Main(string[] args)
4 {
5 SlopeOne test = new SlopeOne();
6
7 Dictionary> userRating = new Dictionary>();
8
9 //第一位使用者
10 List list = new List()
11 {
12 new Product(){ ProductID=1, ProductName=” 洗衣機”,Score=5},
13 new Product(){ ProductID=2, ProductName=” 電冰箱”, Score=10},
14 new Product(){ ProductID=3, ProductName=” 彩電”, Score=10},
15 new Product(){ ProductID=4, ProductName=” 空調”, Score=5},
16 };
17
18 userRating.Add(1000, list);
19
20 test.AddUserRatings(userRating);
21
22 userRating.Clear();
23 userRating.Add(1000, list);
24
25 test.AddUserRatings(userRating);
26
27 //第二位使用者
28 list = new List()
29 {
30 new Product(){ ProductID=1, ProductName=” 洗衣機”,Score=4},
31 new Product(){ ProductID=2, ProductName=” 電冰箱”, Score=5},
32 new Product(){ ProductID=3, ProductName=” 彩電”, Score=4},
33 new Product(){ ProductID=4, ProductName=” 空調”, Score=10},
34 };
35
36 userRating.Clear();
37 userRating.Add(2000, list);
38
39 test.AddUserRatings(userRating);
40
41 //第三位使用者
42 list = new List()
43 {
44 new Product(){ ProductID=1, ProductName=” 洗衣機”, Score=4},
45 new Product(){ ProductID=2, ProductName=” 電冰箱”, Score=10},
46 new Product(){ ProductID=4, ProductName=” 空調”, Score=5},
47 };
48
49 userRating.Clear();
50 userRating.Add(3000, list);
51
52 test.AddUserRatings(userRating);
53
54 //那麼我們預測 userID=3000 這個人對 “彩電” 的打分會是多少？
55 var userID = userRating.Keys.FirstOrDefault();
56 var result = userRating[userID];
57
58 var predictions = test.Predict(result);
59
60 foreach (var rating in predictions)
61 Console.WriteLine(“ProductID= ” + rating.Key + ” Rating: ” + rating.Value);
62 }
63 }