2015年2月7日 星期六

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

圖片來源：https://www.betterment.com/resources/personal-finance/goals-and-advice/8-financial-tools-i-recommend-to-friends/

推薦系統目的在於根據使用者個人化的特質，推薦使用者喜好的商品或廣告，其中最常使用的演算法為協同式過濾（collaborative filtering）．協同式過濾是根據已知的消費行為或是客戶對於商品評價，來猜測客戶對於未購買或未評價的商品可能的評價．協同式過濾中，又以User-base以及Item-base為主要的評價方法．

本文大綱



什麼是User Base推薦

顧名思意，就是透過使用者之間，對於相同產品評價相似程度，來猜測對於其他產品的評價．例如我們兩個人都喜歡吃香蕉，蘋果，芭樂，如果我還喜歡吃芒果，我就會覺得你可能也喜歡吃芒果．(Item Base可以參考http://bryannotes.blogspot.tw/2015/02/r-item-base.html)

範例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

演算法流程


  • 根據評分紀錄，找出與特定十個最相似的User（N-Top）
  • 相似性公式：
Rik為使用者i給電影k的評分，n為兩個使用都有看過的電影









  • 根據這十個User，推論產品評分
  • 評分公式：

    這邊Au為目標使用者的平均評分，Rit為相似使用者i的對電影t的評分．Am為使用者i的平均評分，sim(u,i)為目標使用者與相似使用者i的相似程度，最後c是相似使用者的人數．
    （以下範例相似使用者取相似度最高的前10名）

    • 結果比較

    硬體環境

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

    指標：

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

    評比方法：

    1. 分別對三組資料抽出十個使用者
    2. 分別計算這十個使用者，與最相似的10個人
    3. 根據這十個人的評分以及相似性，預設使用者的評分
    4. 測量上述步驟所花費時間
    5. 計算使用者原始評分，以及與預測評分之間的差異（RMSE）

    表格

    ml-100k
    Time RMSE
    2.17 1.15
    1.84 0.58
    1.90 1.04
    1.91 0.92
    1.88 0.55
    1.83 1.33
    1.99 0.36
    1.81 0.96
    2.03 1.07
    1.86 1.04
    1.92 0.90 (平均)
    ml-1m
    Time RMSE
    67.32 1.04
    67.51 0.89
    68.53 0.33
    63.82 0.61
    64.75 0.64
    69.34 0.90
    66.28 0.47
    65.93 0.79
    64.35 0.70
    66.41 0.69

    小結

    • 速度是最明顯的差異，這個差異主要來自計算相似性的時候（就算只想預測單一的商品），是把使用者跟其他所有人掃過一次，再找出相似性最高的十個人．所以當產品(3707/1682 ＝ 2.2)與使用者（6040/943 = 6.4）增加的時候，所花時間會跟兩者成正比．
    • 隨著使用者以及產品人數上升，RMSE差異也減少了23%(0.69 / 0.9)．差異減少的幅度顯然不如增加的執行時間．
    • 透過實作，可以證實文獻中，對於User-base演算法的缺點，的確在於當使用者的人數大幅度增加時，可能大量降低的效能(10M的資料單機電腦跑不動，放了兩個小時還是算不出單一使用者的結果)．因此也有了許多改進的做法，例如先使用cluster將使用者分群(但是10M的資料放到K-means中跑分群還是掛)，可以先縮減Top-N計算相似性的時間，或是試試看Item Base CF．

    原始碼

    前置處理

    ##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)

    主要的方法

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

## cosine between every user
getNeighbors <- function(x) {  # input a user id
  uuCosin <- sapply(seq(1:nrow(ratingMat)), 
                    function(y) cosine <- getCosine(ratingMat[x,], ratingMat[y,]))
  y = order(uuCosin, decreasing = TRUE)[2:11] ## first is self-Cosin, get Top-10 neibor
  simXy = uuCosin[y] ## Top-10 similarity
  rbind(y,simXy)
}

## get ratings of single y
getRating <- function(x, y, sim){
  meanY = sum(y)/sum(y>0)
  predict = ((y-meanY)*sim)
  return(predict)
}

## get ratings of mean y
getRatings <- function(x, neighbor){ ##input user id,  neighbor id( as a matrix)
  ratings = 0
  for (i in 1: ncol(neighbor)){
    y = ratingMat[neighbor[1,i],]
    sim = neighbor[2,i]
    ratings <- ratings + getRating(x, y, sim)
  }
  meanX = sum(x)/sum(x>0)
  ratings <- meanX + ratings/sum(neighbor[2,])
}

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




<div class="se-preview-section-delimiter"></div>

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





<div class="se-preview-section-delimiter"></div>

```R
index <- 1: nrow(ratingMat)

evaluation <- sapply(seq(1, 10), function(x){ ## input how many runs
  sampleData <- sample(index, 1)            ## input users per run
  startTime <- proc.time()
    pred <- sapply(sampleData, function(i){
      x = ratingMat[i,]
      neighbor = getNeghbors(i) ## 計算neighbor時間增加 n倍user  
      pred <- getRatings(x, neighbor)  
      }
  )
  endTime <- proc.time()-startTime
  result = rbind(time = endTime[1], RMSE = getRMSE(ratingMat[sampleData,], pred))
  }
)
evaluation <- t(evaluation)
colnames(evaluation) <- c("time", "RMSE")
evaluation <- rbind(evaluation, mean = colMeans(evaluation))
    標籤： , , , ,
    
    

    2 則留言:

    1. 匿名2015年3月24日 晚上11:42

      請問你知道R是否有實作ALS_WR的演算嗎?

      回覆刪除
      回覆
      1. Bryan Yang2015年3月25日 下午5:40

        不太確定你說的WR是指什麼，但是ALS的話倒是可以參考
        http://cran.r-project.org/web/packages/ALS/ALS.pdf

        刪除

    訂閱： 張貼留言 (Atom)