YD's blog

Posted 五 12 8月 2016

Model-Based Collaborative Filtering

其實協同過濾的就是分類法（回歸）的進階延伸而已。(a) 表一般的分類法所用到的資料概念，資料被分為訓練集和測試集，獨變項和依變項的關係，作法不外乎就是利用訓練集的獨變項依變項建模，再對測試集的依變項做預測。而 (b) 協同過濾，灰色條目即為未知的數值（即將被預測），散落在二維空間中，因此獨、依變項並沒有限定在行或列中，所以才會說協同過濾類似於分類法的延伸版本。也因此， model-based 協同過濾也會用到各種監督、非監督式的學習方法（如決策樹、關聯性規則、貝氏模型、回歸、神經網絡模型、支持向量機）

儘管前一章節已經提到 Neighborhood-based methods，非常直觀，但仍有一些計算效率問題。在此我們介紹 Model-based methods 比起 Neighborhood-based methods 多了哪些特色：

  1. 空間維度上的縮減，空間複雜度可以降低
  2. 減少 pre-processing stage 的時間 （off-line phase）
  3. 避免 over-fitting

接下來會簡介各個 model-based 的應用情境

Decision and Regression Trees

這兩種樹的目的都是在對資料進行分類，差別在於前者針對的是類別變項、後者為數值變項。接下來皆以決策樹作為實例。 針對 m (user) x n (item) 的稀疏矩陣，決策樹的生成做法是將某一 $item_j$ 固定（依變項），其他的 item 為獨變項 （feature），但這時會問如果獨變項內含missing value怎辦？最直接且合理的方式即下一個節點無論是分到哪個分支，所有缺值都會在下一個節點的所有分之出現。 假設情境為 一 m (user) x n (item) 的稀疏矩陣，條目 (entries) 內可能為0或1的二元數值或是missing。做法就是固定某一維度（依變項），例如 $item_j$ ，我們希望對 $item_j$ 進行物件的推薦，這時借用 其他 item 為 獨變項 （features），就可以開始建樹了！但其實這樣只建了針對 $item_i$ 的樹，所以等於是要建 n 個樹。這裏補充一下，對於樹長的歪不歪可以利用吉尼係數 (Gini Index) 作為一個判斷依據，又可以有整體的吉尼係數或是各節點的算法：


3.1式 表整體的吉尼係數，又 $p_i$ 為各分類中所含資料筆數的佔比。此係數的值越小越好。 3.2式 表某一節點 S 的吉尼係數，透過 S 節點的 子節點 S1 ， S2的吉尼係數權重而得。 

#3.1
#overall gini index: 50 ,if class a to class d with 30, 5, 5 ,10 data records respectively.
Gini <- 1- sum((c(30,5,5,10)/50)^2)


#total: 50 ,if class a to class e with 10, 10 ,10 ,10 ,10 data records respectively.
Gini <- 1- sum((rep(10,5)/50)^2)


#total: 50 ,if class a to class d with 40, 1, 4 ,5 data records respectively.
Gini <- 1- sum((c(40,1,4,5)/50)^2)


#3.2
#child node gini index: if attribute X is splited into classA and classB
GiniX <- (40(1-(40/50)^2)+1(1-(1/50)^2))/50

如果是非連續數值型且數目選擇較少 （例如李克3點量表評分）的評分方式，也可以用決策樹來試做看看。決策樹只是其中一種分類的方式，不一定要這麼做，接下來也會介紹其他分類的方法。

Rule-Based Collaborative Filtering

Rule-Based Collaborative Filtering 和 關聯性規則 (association rules) 關係密切。關聯性規則原則上處理的是二元 （0 或 1）的資料型態，最有名的例子當然就是「購物籃分析」。 想像一下，有一個交易資料庫 $T$ $=$ {$T_1, T_2, …, T_m$}，即含有 m 筆交易數據。我們另外定義 $I$ 是一個含有 n 個商品的集合，則這每筆交易數據 $T_i$ 都應含有 I 的子集的商品。 關聯性規則的判斷非常有趣，第一個定義為 「support」，第二個定義為 「confident」，如定義 3.3.1及定義 3.3.2。



我們直接看到定義3.3.3，要符合關聯性規則，必須滿足兩點個條件：

  1. $X, Y$ 分別為 I 的子集，如果 $P(X\lor Y)$ 大於自定義的最小support值 舉例來說，我們自定義support值最小為.2，則 {麵包、奶油} 和 {牛奶} 同時發生的筆數佔所有筆數 的比例 $> .2$ 則成立。
  2. $X, Y$ 分別為 I 的子集，如果 $P(Y|X)$ 大於自定義的最小confidence值 舉例來說，我們自定義confidence值最小為.6，則在發生{麵包、奶油} 的筆數中，同時發生 {牛奶}的比例 $> .6$ 則成立。

商業應用：

「YD 已經購買了奶油和麵包，根據符合資料庫計算的關聯性規則，發現奶油和麵包出現後，應該要推薦 YD 買牛奶。」

關聯性規則特別適用於 unary ratings 矩陣（數值只有 0 或 1），其實應該說是購物行為的資料就是 unary ratings，而關聯性規則就是要處理這種屬性的資料。因此在屬於 unary ratings matrix 中若出現缺值，直接補上 0 非常合理且不被詬病的方式（其他的矩陣用 0 補缺值會造成極大的偏誤產生）。 實作 Rule-Based Collaborative Filtering 的第一步，就是先調配自定義的 support 和 confidence 找出所有的關聯性規則。（此時的 support 和 confidence 是參數），因此只要某個顧客A產生了一筆交易數據，就可以馬上匹配所有關聯性規則，找出其他可能購買的清單列表。 這裏可能會疑惑，有沒有可能關聯性規則能反過來避免推薦不喜歡的東西？假如有個少選項、或少數值所形成的矩陣（例如 {-1,0,1} 或 {不喜歡、普通、喜歡}），這時我們就可以在物件清單多貼一個標籤，例如{item = 牛奶, tag = 不喜歡}、{item = 牛奶, tag = 喜歡}，這時這兩個「牛奶」就可以視為「不同的商品」，然後再依循的關聯性規則來做判斷。不過這時又會出現一個問題，那就是當 Andy 購買了 {麵包、奶油}，推薦系統會排序給予推薦的商品，此時可能都會推薦 {item = 牛奶, tag = 不喜歡}、{item = 牛奶, tag = 喜歡}，有個簡單的做法就是將 top-k 的推薦的清單去做多數決投票，端看 {item = 牛奶, tag = 不喜歡}、{item = 牛奶, tag = 喜歡} 誰佔大宗了！

Naive Bayes Collaborative Filtering

貝氏協同過濾適合小量的間斷數值型態的資料（例如：{0, 1, 2}），也可將其視作類別型態的資料。貝氏模型主要用來做分類，不過在協同過濾的框架下使用貝氏模型的最大挑戰，就是任何的特徵（feature，即 item），都可被看作是被分類的對象。 設想一個情境， u 個用戶對 I 集合中的 n 個物件評分為 {$v_1, v_2, v_3,…, v_l$}， $r_{uj}$ 表用戶i 對 物件j的評分。 根據貝氏定理：

將式子改寫成：

又因右式的分母為已知評分的邊際機率，可以忽略化簡成：

$P(r_{uj} = v_s)$ 為 Prior probabilities，$P(Observed ratings in I_u | r_{uj} = v_s)$ 為 Likelihood。這裡有個假設，那就是評分彼此是獨立的，因此可以將 Likelihood改寫成：

整條式子就會變成，

而我們的預測值就會是，所有可能的分數中，最大概率的那個值：

然而因為稀疏矩陣的關係，無論是計算$P(r_{uj} = v_s)$ 為 Prior probabilities，$P(Observed ratings I_u | r_{uj} = v_s)$ 為 Likelihood，很可能都是一堆0的值，為了解決這個問題，拉普拉斯平滑 (Laplacian Smoothing) 可以解決這樣的問題：

不僅$P(r_{uj} = v_s)$ 需要在分子、分母加上參數。$P(Observed ratings I_u | r_{uj} = v_s)$ 也是同樣的做法。當 $\alpha$ 越大 ，越平滑，換句話說，原本的資料影響力就越小。 R腳本如下： 

#naive bayes
set.seed(1125)
(raw <- matrix(sample(c(NA,1:3),20,replace = T),4,5))
#if we want to predict r_(4,2)
#p(r_(4,2) = 1|observed) = prior * likelihood = 0 * likelihood = 0
#p(r_(4,2) = 2|observed) = 1/2 * (1/1 * 0/1 * 1/1 * 0/1)
#p(r_(4,2) = 3|observed) = 1/2 * (0/1 * 0/1 * 1/1 * 0/1)
# laplacian smoothing
l <- .5
alpha <- .3
#p(r_(4,2) = 2|observed) =
p4.2Eq2 <- (1+alpha)/(2+lalpha) * (1+alpha)/(1+lalpha) * (0+alpha)/(1+lalpha) * (1+alpha)/(1+lalpha) * (0+alpha)/(1+lalpha)
p4.2Eq3 <- (1+alpha)/(2+lalpha) * (0+alpha)/(1+lalpha) * (0+alpha)/(1+lalpha) * (1+alpha)/(1+lalpha) * (0+alpha)/(1+lalpha)

Using an Arbitrary Classification Model as a Black-Box

除了上述兩種方法，一般現成的model也可以用來填補缺值。做法可以用迭代的方式來填補並更新缺值。第一步先將矩陣轉成 row (column) -centering mean。再來就先固定某一 column作為依變項，其他列為獨變項，算出來的預測值，填補至原本的缺值的位置（0的位置）。接著再依序將其他的column重複此步驟，簡言之， n 個 column 就要有 n 次的 training procedure，跑完後才算為一次的迭代。 以 regression model 為例，R腳本如下： 

#3.5 updating ratings matrix with regression model
set.seed(1122)
raw <- matrix(sample(c(0:3),40,replace=T),10,4) # assume 0 means centered by rows
#example 1: only raw[,4] as the target variable
y <- raw[,4]
x <- raw[,1:3]
results <- lm(y ~ x) #regression
w <- as.matrix(results$coefficients[2:length(results$coefficients)]) #weight
y.hat <- x %*% w + results$coefficients[1] #prediction
raw[which(y==0),4] <- y.hat[which(y==0)] #replace shaded entries with predictions
rm(raw,y.hat,w,result,x,y)
#example 2: let raw [,41:3] as the target variable with 4 training procedures in the first iteration
set.seed(1122)
raw <- matrix(sample(c(0:3),40,replace=T),10,4) # assume 0 means centered by rows
check <- raw #compare to raw
  for(targetCol in 1:ncol(raw)){
    y <- raw[,targetCol]
    x <- raw[,-targetCol]
    results <- lm(y ~ x) #regression
    w <- as.matrix(results$coefficients[2:length(results$coefficients)]) #weight
    y.hat <- x %*% w + results$coefficients[1] #prediction
    raw[which(y==0),targetCol] <- y.hat[which(y==0)] # replace shaded entries with predictions
  }

Neural Network as Black-Box

神經網絡也可以用來做迭代更新模型的方法，同樣以簡單回歸為例， W 為權重， X 為輸入，b為截距項，Z 為輸出（預測值）：

更新權重的方式：

$\alpha$ 為大於 0 的值， learning rate 也是 step size 。 t 為第 t 次的迭代。 R腳本如下： 

#one-dimension:Qlearning
i <- c(1,5,6,3,4) #input
w <- c(.2,.4,.1,.7,.5) #coe weight
o <- i * w


alpha <- 1
w_new <- w - alpha * (i-o) * i
o2 <- i * w_new

Latent Factor Models

潛在類別模型的想法是將原本的評分矩陣的維度進行去蕪存菁的動作，使得資料維度減少，只利用些許的潛在因子作為表徵。常見的方法有主成份分析 (Pricipal Component Analysis)、奇異值分解 (Singular Value Decomposition)等。 我們來圖解一下潛在類別模型的意義，這裡使用奇異值分解作為範例 （原因是將因子向量為正交，彼此垂直比較好畫圖）。 設想一個情境，所有的用戶對於 Nero, Gladiator, Spartacus 三部電影進行評分，所有的評分分數為介於 [-1,1] 的連續值。我們將所有的評分分數化成三維的圖：

從圖中發現，若評分分數都呈正相關，則可以將分數化簡到一個維度向量（1-dimensional line, 又稱為潛在因子）。因此，只要我們知道 Spartacus 的分數（0.5分），就可以將該分數映射到與 Nero, Gladiator 平行的超平面上，得到對應的 Nero, Gladiator 分數，利用這種方式就可以推論未知的條目了。 因此我們可以發現，創建這條潛在因子向量其實不需要 full matrix 就可以得到，只需要少數的點，就可以創建這條向量。 但潛在類別模型的假設是：資料間的評分必須有相關性，否則無法找出合適的潛在類別因子。（不過如果原始評分沒有相關性，那推薦系統根本就沒有用了啊XD）

Understanding the Matrix Factorization Family

上述是以空間維度來說明降維的概念，而實際上為得到潛在因子向量，我們透過 factoriztion 來做運算：

此為通式，左式為評分矩陣，又式為兩個矩陣的乘積，在推薦系統的框架下， U 為用戶的潛在向量、 V 為物件的潛在向量，我們會藉由排序將重要的向量 k 保留， $k << min${$m,n$} 以達到降維的真實效果，式子會變成：

因為是估計值，所以我們其實可以算出殘差陣列：

$|| R- UV^T||^2$ 表條目中的估計與實際條目的 sum of squares。我們會希望透過利用各種方法 (Objective funtion) 使殘差陣列的數值越小越好，這裡總整列表如下：

R腳本 Q-learning 結果範例 

#creating full entries matrix with neural network(Q-learning) iteration
set.seed(1122)
raw <- matrix(sample(c(0:3),40,replace=T),10,4) # assume 0 means centered by rows
iraw <- t(raw) #item-based
y <- iraw[4,] #only raw[,4] as the target variable
x <- iraw[-4,]
w <- rep(1/dim(x)[1],dim(x)[2])#uniform default weights
y.hat <- colSums(w*x[1:dim(x)[1],])#sum by column


alpha <- .05 #set learning rate


repeat{
  if((sum(y.hat-y)^2) < .01){# sum of square error
    y <- y.hat;print(y); break;
  }
  nextW <- w - alpha * (y-y.hat) * y
  y <- y.hat
  w <- nextW
  y.hat <- colSums(w*x[1:dim(x)[1],])#sum by column
}

商業情境

如何應用 model-based collaborative filtering 處理 unary matrix ，得到比較好的 full entries matrix 的結果? 以下是我自己的一些心得：

  1. 若為explicit Matrix (例如：1–5分)，將其視為 “購買次數” ，若為缺值補 0 表沒購買: Centering to means by row → Update “0” entries by Regression 並透過 Q-learning model 得到收斂結果→ run Non-negative Matrix Factorization

R腳本試算 Update “0” entries by Regression 並透過 Q-learning model 得到收斂結果 

###Combining Regression adjustion for centering mean with Neural Network iteration
#Run regression model for creating new full matrixs by 4 training procedures in the first iteration
set.seed(1122)
raw <- matrix(sample(c(0:3),40,replace=T),10,4) # assume 0 means centered by rows
#check <- raw #compare to raw
for(targetCol in 1:ncol(raw)){
  y <- raw[,targetCol]
  x <- raw[,-targetCol]
  results <- lm(y ~ x) #regression
  w <- as.matrix(results$coefficients[2:length(results$coefficients)]) #weight
  y.hat <- x %*% w + results$coefficients[1] #prediction
  raw[which(y==0),targetCol] <- y.hat[which(y==0)] # replace shaded entries with predictions
}
#Update full matrix with neural network(Q-learning) iterations
iraw <- t(raw) #item-based
y <- iraw[4,] #only raw[,4] as the target variable
x <- iraw[-4,]
w <- rep(1/dim(x)[1],dim(x)[2])#uniform default weights
y.hat <- colSums(w*x[1:dim(x)[1],])#sum by column


alpha <- .05


repeat{
  if((sum(y.hat-y)^2) < .01){
    y <- y.hat;print(y); break;
  }
  nextW <- w - alpha * (y-y.hat) * y
  y <- y.hat
  w <- nextW
  y.hat <- colSums(w*x[1:dim(x)[1],])#sum by column
}
y

  1. 若為explicit Matrix (例如：1–5分): Asymmetric Factor Model or SVD++ ，將 matrix 轉成 $[FY]V^T$ (user factors and item factors)
  2. 若為explicit Matrix (例如：1–5分)，將其視為 “購買次數” ，若為缺值補 0 表沒購買， 再用 (3.29) 將購買次數轉換成權重 → run svd

  1. 若為explicit Matrix (例如：1–5分)，將其視為 “購買次數，並以 (3.31) 用相對頻率表示 → run svd → run PLSA

Ref: Aggarwal, C. C. (2016). Recommender Systems: The Textbook. Springer.

Category: Stat
Tags: Recommender System Stat