[R] 推薦系統實作（Item Base）

圖片來源：http://betanews.com/2013/09/25/twitter-updates-magicrecs-recommendation-system-for-mobile-users/

承繼上一篇文章[R] 推薦系統實作（User Base） 這篇要介紹的是使用Item Base的角度來推薦使用者物品．

本文大綱

• 推薦系統比較（User base vs Item base CF）
  • • 本文大綱
    • 什麼是Item Base推薦
    • 範例data
      • 資料來源
      • 資料集概況
    • 演算法實作：
      • 演算法流程
    • 結果比較
      • 硬體環境
      • 指標：
      • 評比方法：
      • 結果表格
    • 小結
    • 原始碼
      • 前置處理
      • 主要的方法
      • 評比

什麼是Item Base推薦

與User Base剛好相反，是透過相似的產品來推薦給你．比如說有名的尿布和啤酒，當兩個物品常被一起購買時，當你買了尿布，便會推薦啤酒給你．

範例data

資料來源

• Movielens

資料集概況

ml-100k
評分筆數：100000
不重複使用者數：943人
不重複電影數：1682部
ml-1m
評分筆數：100209
不重複使用者數：6040人
不重複電影數：3706部
ml-10m
評分筆數：10000054
不重複使用者數：69878人
不重複電影數：10678部

演算法實作：

參考資料：A Collaborative Filtering Recommendation Algorithm Based on User Clustering and Item Clustering

演算法流程

• 根據評分紀錄，將電影分組．這是使用K-means演算法，將物品分成K組，用來分組的維度為使用者對於電影的評分（如果有943人，則分組維度為943）
• 計算特定電影與同組電影的相似程度
• 相似性公式：
  $$sim_{(t,r)} = \frac{\sum_{i=1}^m R_{it}R_{ir}}{\sqrt{\sum_{i=1}^m R_{it}^2\sum_{i=1}^m R_{ir}^2}}$$

Rit為使用者i給電影t的評分，Rir為使用者對於其他電影的評分，m為使用者同時有為t及r評分的數量．

推薦時，根據同一組產品的相似程度計算評分

評分公式：
$$P_{ut} = \frac{\sum_{i=1}^c (R_{ui} * sim(t,i))}{\sum_{i=1}^c sim(t,i)}$$

這邊Rui為目標使用者u對於i電影的評分，sim(t,i)為目標的item t與其他同組電影的相似程度，c為共同評分電影的數量

K-means分組組數

• 分組組數一直是Kmean的重點，這裏我們簡單的採用$\sqrt(使用者人數 / 2 )$來作為組數．未來還可以透過機器學習的方式來評估組數的好壞．

抽樣

• 由於1m的資料量（6040人），在分群時維度太過龐大，計算能力無法負荷，因次1m和10m的電影分組的使用者，是透過抽樣決定．（樣本數為1000人）

結果比較

硬體環境

• Mac Air 13”
  
  • i5 1.4G
  • 8G Ram

指標：

1. K-means時間
2. 預測時間：程式執行時間
3. 預測結果準確度：預測值與實際值的差異平方（RMSE）

評比方法：

1. 分別對二組資料隨機抽出30個使用者
2. 隨機預測使用者對於特定電影的評分
3. 測量上述步驟所花費時間
4. 計算使用者原始評分，以及與預測評分之間的差異

結果表格

ml-100k
分組時間(未抽樣，分為20組)：2.46s

Time	SE
0.08	2.10
1.22	0.00
1.01	0.01
1.08	0.00
0.05	2.31
1.09	0.00
0.18	0.08
1.10	0.01
0.19	0.08
以下省略…
0.57	1.09 (RMSE)

ml-1m
分組時間（取1000個樣本，分為22組）：15s

Time	SE
0.62	0.00
2.66	0.00
10.13	0.00
2.60	0.00
0.26	0.00
9.72	0.00
2.64	0.01
10.23	0.00
2.60	0.00
以下省略…
5.58	0.55 (RMSE)

K-means分群數比較（以100k的資料為例）

組數	分組時間	平均推薦時間	RMSE
20	2.46s	0.57	1.09
40	5.03s	0.49	0.57
60	8.62s	0.37	0.65
80	16.95s	0.28	1.36
100	17.18s	0.13	1.92

小結

• 由於Item Base在推薦商品時，只有計算特定商品與其相似群組中的相似度，因此在計算單一商品的評分上可以大幅縮短推薦時間．推薦的時間與組中的商品數量成正比，如果分組數量夠多時，組中商品數量越少，推薦所需時間越短．
• 從分群數比較來看，分組並非是越多越好，合適的組數可以透過機器學習方式優化．
• User Base的推薦方式需要事先將item分群，當資料太大(3706 * 6040)時，也很難計算，因此使用抽樣方式處理，但是會犧牲分組的精確性．

原始碼

前置處理

##R code

library(reshape2)
library(Matrix)

##read file
base <- read.delim("~/Documents/Data/Vpon/ml-100k/u.data", header = FALSE)

colnames(base) <- c("userID", "itemID", "rating", "timestamp")

##clean data
base[,"rating"] <- as.numeric(base[,"rating"]) 

##see if duplicate user-item 
base <- base[!duplicated(base[,1:2]),]

##transfer to User-Item Matrix
ratingDF <- dcast( base, userID ~ itemID, value.var = "rating" , index="userID")
ratingDF <- ratingDF[,2:ncol(ratingDF)]
ratingDF[is.na(ratingDF)] <- 0
ratingMat <- Matrix(as.matrix(ratingDF), sparse = TRUE)  ## cast data frame as matrix 轉成Sparse能降低佔用的空間(以10m的資料為例，原始的矩陣為5.6G, 經過sparse轉換後僅剩115m)

主要的方法

## cluster
## Kmeans cluster number http://www.ee.columbia.edu/~dpwe/papers/PhamDN05-kmeans.pdf
user_sample <- sample(nrow(ratingMat), 1000) ##使用抽樣避免樣本太大分群跑不出來
colnames(ratingMat) <- seq(1, ncol(ratingMat))
system.time(item_model <- 
              kmeans(t(ratingMat[user_sample,]),
                     centers = sqrt(length(user_sample)/2), ## k = sqrt(n/2)
                     algorithm = "Lloyd",iter.max = 100))

item_cluster <- item_model$cluster ## for quering items cluster

## cosine similarity between two vectors
getCosine <- function(x, y){
  cosine <- sum(x * y) / (sqrt(sum(x * x)) * sqrt(sum(y * y)))
  return(cosine)
}

getItems <- function(x){   ## input a group id , output items in the same group 
  as.integer(names(item_cluster[item_cluster==x]))
}

## computing similarity among the items of group
getCosine <- function(x, y){
  cosine <- sum(x * y) / (sqrt(sum(x * x)) * sqrt(sum(y * y)))
  return(cosine)
}

getSim <- function(target){     #input a item output the similarity with the others in the same group
  group <- item_cluster[target]  # query the group id
  items <- getItems(group)  # query items in the group
  sim <- sapply(items, function(item){
    getCosine(ratingMat[, target], ratingMat[, item])
  })
  names(sim) <- items # item names
  return(sim)
}

## computing rating

getRating <- function(user, target){  ##input a user id and item id, output the rating
  sim <- getSim(target)
  (ratingMat[user, as.integer(names(sim))] %*% sim) / sum(sim)
}

getRatings <- function(user){  # input a user id, output all items ratings
  ratings <- sapply(seq(1:ncol(ratingMat)), function(item){
    getRating(user,item)
  })
  return(ratings)
}

## computing RMSE
getRMSE <- function(x, pred) {
  sqrt(sum((x - t(pred))^2)/length(x))
}

評比

評比部分有兩個指標
1. 運算效率
2. 預測與實際值的差異（RMSE）

user_index <- 1: nrow(ratingMat) ##隨機取個使用者
item_index <- 1: ncol(ratingMat) ##隨機指定商品

evaluation <- sapply(seq(1, 30), function(x){ ## input how many runs
  sampleUser <- sample(user_index, 1)            ## input users per run
  sampleItem <- sample(item_index, 1)            ## input items per user
  startTime <- proc.time()
  pred <- sapply(sampleItem, function(item){
    pred <- getRating(user, item)  
    }
  )
  endTime <- proc.time()-startTime
  result = rbind(time = endTime[1], SE = (ratingMat[sampleUser,sampleItem] -pred)^2)
  }
)
evaluation <- t(evaluation)
colnames(evaluation) <- c("time", "SE")
evaluation <- rbind(evaluation, mean = colMeans(evaluation))
evaluation <- rbind(evaluation, sqrt = sqrt(evaluation[31,]))