2015年2月9日 星期一

[R] 推薦系統實作(Item Base)

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

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

本文大綱



什麼是Item Base推薦

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

範例data

資料來源

資料集概況

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)
  • 計算特定電影與同組電影的相似程度
  • 相似性公式:
Rit為使用者i給電影t的評分,Rir為使用者對於其他電影的評分,m為使用者同時有為t及r評分的數量.


  • 推薦時,根據同一組產品的相似程度計算評分
  • 評分公式:

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

  • K-means分組組數
    • 分組組數一直是Kmean的重點,這裏我們簡單的採用來作為組數.未來還可以透過機器學習的方式來評估組數的好壞.
    抽樣
    • 由於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,]))