Neighborhood-Based Collaborative Filtering
Introduction
協同過濾可視為「類聚法」或是「回歸」的概化版本（generalization）。Neighborhood-based method的概念源自於 nearest neighbor classification 和 regression，又被稱為「memory-based algorithms」。
Neighborhood based框架下的假設（核心概念）：「相似的用戶會有相似的評分行為，且相似的物件會得到相似的評分結果」。最主要的兩種演算模型：
- User-Based collaborative filtering: 基於相似於目標用戶A的用戶們之評分分數，用來預測Ａ的評分，並藉此達到推薦的排序。
- Item-Based collaborative filtering: 基於相似於目標物件B的物件們之被評分數，預測任一目標用戶A對目標物件B的評分。
為了達成上述的目的，我們建立一m為用戶、n個物件的 user-item ratings matrix（m x n維度）。因為每個用戶的評分資訊很少，往往矩陣為稀疏矩陣。 藉由協同過濾，我們希望得到兩種目標：
- 預測user-item矩陣的缺值：即各用戶的評分預測
- 決定top-k 物件或是 top-k 用戶：一般又被稱為「top-k problem」。傳統而言，會比較在意尋找top-k 物件而不是top-k 用戶，原因是希望推薦“應該被推薦”的商品給用戶才是商業需求。然而尋求top-k物件也有一些好處，例如可以探索商品的潛在客群為何。
Key properties of Ratings Matrices
評分矩陣 (m x n Ratings matrix) 上述介紹過了，因為矩陣中已知的數值所佔的條目 (entry)非常少，為稀疏矩陣。若欲求出尚未擁有數值的條目，就好像是依變項是以條目為單位 (同時含行、列); 另一方面而言類聚法或回歸，通常都只有一個維度為依變項，這也是為何推薦系統又被視為「類聚法」或「回歸」的概化版本。在推薦系統的所分析的原始資料：評分分數(rating)，又有下列幾種型態：
- 連續型評分分數：評分的方式可能為一條-10至10分的拉霸，用戶可選擇其中的任一實數，缺點是會讓用戶增加評分上的負擔。
- 等距型評分分數：例如李克式5點、7點評分。等距型評分有個很重要的假設，即每個點之間的距離是等距的，舉例來說，-1至1的心理距離和1至3是一樣的。
- 次序型評分分數：例如「不同意」、「普通」、「同意」。次序型並沒有距離一樣的假設。但通常推薦系統分析的處理上便利性，還是會當成一樣的。
- 二元評分分數：可以看作是等距型和次序型的特例
- 單元評分分數：這非常特別，好比說臉書的「按讚」，這類的資訊只抓取用戶的行為(implicit feedback)
Predicting Ratings with Neighborhood-Based Methods
Neighborhood-based methods 的基本原則就是”用戶- 物件矩陣”中利用用戶間相似、物件間相似進行推薦。
User-Based neighborhood models 算矩陣中的相似性有兩種方式 1.Cosine 2.Pearson。舉例來說，我們想要得到Table2.1內user3對於item1, item6 的評分預測，先去算user3與其他用戶間的相似性(row-based Similarity)。舉例來說，user3對於user1的相似性的兩種算法： 我們須得到各用戶的mean rating：
$I_u$ 為該用戶對於所有“已經評分“的物件的集合。舉例user3，他的評分均數為 (3+3+1+1)/4 = 2。
所有對於user3的相似結果在Table2.1最後兩欄，接著我們若選擇top-2 最鄰近user3的兩位user作為預測基準，我們可以得到預測分數如下：
然而這樣的算法儘管已經利用相似性考量其他用戶評分分數的權重，但是仍用其他用戶的原始分數做完基準，這樣會導致預測值容易受到其他用戶決策風格的影響。為減少這樣的狀況，我們可以用centering to mean的方式來解決，也就是所有的原始分數減去user的均數。 因此我們可將上表的數值轉換成：
接著再利用上表重算預測值：
上述的預測分數的通式為：
大體而言，經由mean-centering後的偏誤修正，Pearson correlation coefficient會比 raw cosine表現更好。 另外也有做法是利用z分數來估計預測分數：
利用z分數算法可能會導致所估計的預測值落在實際評分的範圍外，仍被使用的原因是仍可以依照評分大小做物件的排序進行推薦。 另外一種加強權重的方式即在相似性中放一個指數參數放大權重效果：
然而多數情況除了原始資料的資料殘缺外，用戶的評分可能集中在少數的幾個物件上，而導致長尾現象：
這樣一來產生一個問題：用「受歡迎」的物件來對「鮮為人知」的物件進行評分有失準度的，這些過多的受歡迎評分就好比文本分析的無用字詞（例如「的」、「他」、「是」）。因此處理方式類似 Inverse Document Frequency (idf) ：
$m_j$ 為物件 $j$ 被評次數，$m$為總評次數。藉此我們就能將預測公式修改成：
Item-Based Neighborhood Models 算法的邏輯類似 User-Based Neighborhood Models：
乍看之下很類似Pearson Correlation，但不同的地方在於$S_{uj}$是row-based centering mean，即「用戶」的評分均數，item-base最基本的概念最終是用到「該用戶」自己的評分分數對相似的物件進行評分預測。
我們目標是希望對目標用戶user3進行物件推薦，因此必須得出item1, item6的預測值。 首先先得出row-based centering mean，然後再去算item1、item6與其他物件間的相似，結果如下表的倒數兩列。若是top-2 最鄰近item的想法，可得item1和item2,3有較高的相似; item6和item4,5有較高的相似，最後我們再用user3的原始評分分數 （item-based的核心概念）作為基準得到預測值：
若比User-based 和 Item-based兩種算法，Item-based methods往往會推薦比較相關的物件，且比較準確，原因是最後的預測分數用到的是「該用戶」自己的評分。Item-based methods還有個好處，就是推薦的同時，可以呈現比較具體的理由，例如 Netflix 會說，因為你看了 Alien ，所以我們推薦你 Predator。若User-based要呈現推薦理由的話，因為預測分數的基準來自其他匿名用戶，若要呈現理由，可以利用圖表：
然而，反過來說，Item-based的也容易推薦一些常見的物件，難以推薦「新穎的」物件。
雖然上述兩種算法非常直觀，但缺陷是計算效率的問題，時間複雜度太高。Neighborhood-based methods又可拆成兩個階段: 離線與線上階段。離現階段是要計算用戶間相似（物件間相似），以及預備top-k的臨近用戶（物件）。線上階段則是算出預測值。而neighborhood-based methods計算上的困難往往卡在離線階段。
Clustering and Neighborhood-Based Methods 因為計算效率的問題，所以我們在離線階段，將原本的 nearest-neighborhood computation 改為 clustering computation。實際做法和clustering analysis相似：
- 先在每個row決定群集$c_1$,…$c_k$，表徵 均數 $y_i$。 可用歐幾里德或曼哈頓距離來算相似
- 對所有的$i$ $in$ { $1..k$ }，重設均數 $y_i$ 重新計算新的中心點。
最大的問題是矩陣是稀疏矩陣，資料殘缺不全，計算點之間的距離會較困難，在這樣的情況下，比較建議用曼哈頓距離來計算。
Dimensionality Reduction and Neighborhood Methods 降維也是一個提升neighborhood-based methods 品質和效能的方法。降維的目的是將原始的用戶-物件矩陣降到低維度，利用潛在變項作為表徵，這樣的降維方法指的即「潛在變項模型」(Latent Factor Model)。降維方法的好處是即使兩用戶沒有太多共同的評分物件，仍可以算出彼此間的潛在向量。將為方式可以有兩種，第一種是根據行或列的單維度降維，另外一種是同時行列的降維。因為後者非屬於Neighborhood based methods，在此不討論。降維方法的另外一個好處是維度上並不會有缺值的情形。一般而言降維的方法可用SVD-like methods 或是 PCA ，我們以 SVD-like作為說明。
Singular Value Decomposition-Like 以下為實作方式
- 必須先把缺值補齊 （這裏會有偏誤，之後會講），一般做法就是填入 row-based mean 或是 column-based mean。
- 如果有個m x n 的評分矩陣R，我們先計算 $S = R^T \cdot R$，
- 接著計算$S$之特徵值與特徵向量，並依照特徵值的大小排序，取出前d個特徵值$val_d$，標準為 $d$ $<=$ $min${$m,n$}，並得到對應的特徵向量$vec_d$
- $S \cdot vec_d$ 就會是m x d的矩陣，表示每個用戶都用這d維度來表示了。
- 可以用下面的R 腳本來理解。
r <- matrix(sample(10,500,replace=T),100,5) #create matrix s <- t(r) %*% r vec <- eigen(s)$vectors val <- eigen(s)$values newR <- r %*% vec[,1:2] #d = 2
PCA和SVD概念相似，只是PCA利用的是共變矩陣而不是 $R^T \cdot R$。 SVD文件參考連結
上述實作步驟1.會產生偏誤，下述為原始矩陣：
首先依照步驟1. 根據row-based 算出Nero的均數 (1+7+1+7)/4 = 4，因此缺值接以4取代。以PCA來說，因為算的是共變矩陣，會得到：
理論上Gladiator和Nero的共變應比高Nero和Godfather高，但因為補上均數的關係，造成資料偏誤。但當稀疏矩陣實在太過稀疏時，利用上述方法的估計值來填補缺值是非常不可信的。利用Expectation-Maximization Algorithm (EM-Algorithm)降低偏誤會變成是個很好的辦法。EM-Algorithm如來估計共變矩陣。因此在計算共變矩陣時，缺值應該先不補，而是在算共變時只計算物件間已有評分的交集：
#handling the bias god <- c(1,7,3,5,3,5,3,5,3,5,3,5) gla <- c(1,7,1,7,1,7,1,7,1,7,1,7) nero <- c(1,7,1,7) fillin <- cov(gla[1:4],nero[1:4]) fillin <- cov(god[1:4],nero[1:4])
再將結果補回共變矩陣：
我們可以利用這種不補值的方式得到上述的共變矩陣，接著可以利用這個共變矩陣萃取出特徵值和特徵向量，已達到原始評分矩陣降維的效果： 實作方式為：
- 根據共變矩陣得到特徵向量和特徵值
- 依照特徵值的大小排列特徵向量_d，只取出 top-d
- 在此需借用2.17公式，此公式只是將原始的矩陣相乘，忽略缺值的計算。
參考R的實作腳本
#handling the bias
god <- c(1,7,3,5,3,5,3,5,3,5,3,5)
gla <- c(1,7,1,7,1,7,1,7,1,7,1,7)
nero <- c(1,7,1,7,NA,NA,NA,NA,NA,NA,NA,NA)
fillin1 <- cov(gla[1:4],nero[1:4])
fillin2 <- cov(god[1:4],nero[1:4])
adjustedCov <- matrix(c(cov(god,god),cov(god,gla),fillin2,cov(god,gla),cov(gla,gla),fillin1,fillin2,fillin1,fillin1),3,3)
#2.17
df <- data.frame(god,gla,nero)
raw <- as.matrix(df)
m<- adjustedCov
s <- t(m) %*% m
(vec <- eigen(s)$vectors)
val <- eigen(s)$values
#calculate a_(12,3) for example
u=12
i=3
a_12.3 <- (raw[u,c(1:length(which(!is.na(raw[u,]))))] %\*% vec[c(1:length(which(!is.na(raw[u,])))),i]) / length(which(!is.na(raw[u,])))
#calculate m x d matrix A = [a_(ui)]m x d
tempdf <- data.frame()
for(u in 1:nrow(raw)){
tempRow <- c()
for(i in 1:ncol(vec)){
tempVal <- (raw[u,c(1:length(which(!is.na(raw[u,]))))] %\*% vec[c(1:length(which(!is.na(raw[u,])))),i]) / length(which(!is.na(raw[u,])))
tempRow <- c(tempRow,tempVal)
}
print(tempRow)
tempdf <- rbind(tempdf,tempRow)
rm(tempRow)
}
上述方法雖然可以解決共變矩陣偏誤的狀況，但如果還是太稀疏的話，仍是不可信的。這時可採取Direct Matrix Factorization methods如 singular value decomposition，若步驟1.的缺值透過非線性最佳化取得會讓模型表現更好。
Regression model view of Neighborhood Methods 我們可將user-based nearest neighborhood 和 item-based nearest neighborhood 的公式視為現性函數：
以user-based nearest neighbor regression為例，我們將權重改為未知的參數改寫上述的公式：
公式2.20或2.21計算鄰近的k個用戶或物件因為是有值的 (top-k)。但因為 regression 的方式是先決定k個最近的用戶（物件），再去將「已經評分的」計入回歸式中，因此k的數量比會大幅減少。又因為w是估計值，因此 $w_{uv}$ 和 $w_{vu}$ 的係數值可能不同。 檢驗回歸式的方式可用最小平方法。實際作法只去計算「已知的評分」與「預測的評分」：
不過因為回歸式容易受到「”用戶的數量” 對於 item_j 的評分」的影響。比如說$user_u$ 評了電影A和電影B，除了$user_u$外，其他人都評了電影A，但只有一人（姑且稱做$user_x$）評了電影B，此時$user_x$對於建立模型的係數影響非常大，導致模型的不可信。因此我們必須稀釋這樣極端的效果：
k為總人數，$|P_{u}(j)|$為 $item_j$ 被評次數。
另外一種常見的調整方式為：
加入一個未知的”偏誤參數”$b_u$。但要特別注意，此時的模型已為非線性模型。
除了加入參數 user bias ，也可以結合 item bias：
Item-based nearest neighbor Regression也是類似的作法，將2.21的公式改為：
檢驗模型及預測調整類似於 user-based regression：
上述的兩種回歸式仍面臨和傳統的 neighborhood-based 一樣的問題，那就是計算效率的狀況。回歸式比較適合應用於當物件時常被更新，而用戶的狀態比較穩定的狀態的場景。
另外，同時結合 user-based 和 item-based方法的公式為：
Joint neighborhood-based model 還有其他的方法計算相似性的權重，基於公式2.22，但不再以用戶間對於同一物件的評分比較，而是以該用戶對於其他物件的評分作為比較：
Sparse Linear Models (SLIM) 此模型是基於 item-item 回歸方法，特色是處理 非負數值的評分。也因此它並不能做 cetering-mean（否則會有負值產生）。也因為這個特色，它特別適合處理單元評分 unary ratings （implicit feedback），例如臉書按讚這類型的資料：
此公式和2.27最大的不同是，不只計算交集的部分，而是所有的 item 都進去建模了。
Graph models for neighborhood-based methods 利用圖模型可以呈現用戶與物件間彼此連結的狀況，一般常見的方式為 隨機路徑 (random-walk) 或是最短路徑 (shorest-path methods)。 圖模型的優點為不需要兩用戶的直接連結（例如共同評分的物件），可以藉由間接的關係，如兩用戶的最短路徑來表示用戶間的關係（方法可能為 隨機路徑或是 Katz measure）。
Neighborhoods with the random walk 以 random walks 來得出user-item graph為例：
左邊為原始評分，右邊則為圖模型的結果。這裏只計算連結數，而不考慮數值
Neighborhoods with the Katz measure
$n_{ij}^{(t)}$表示節點 $i$, $j$ 之間長度 $t$ 的數量，$\beta$ < 1 為一discount自定義參數 (discount factor)。
$A$ 為 節點間的非間接網絡矩陣（對稱矩陣），可以依照上述的公式得到 Katz 係數矩陣。
2.35
m <- matrix(c(1,4,4,1),2,2) beta <- 0.5 k <- solve(diag(2)-beta*m)-diag(2)#solve(A) Inverse of A where A is a square matrix.
一般而言我們可以設定設定最長路徑 閾值，因為過長的路徑反而是資訊上的干擾。 特別注意的是，Katz measure 只用於計算用戶間的關係，而不同於先前提到的neighborhood methods，這裡是去的資訊是用戶和物件的連結數，屬於 path-based methods。
User-User Graphs
Item-Item Graphs 物件間的圖模型又被稱為「Correlation graph」：
(a)為原始資料 (b)為未正規化的相關圖譜，計算方式是同一用戶同時評了 $item_i$ 和 $item_j$，這樣算成 $item_i$ 和 $item_j$一筆。若同一用戶同時評了三個物件，則會有三個連結產生。最後再去加總 $item_i$,$item_j$之間的連結數。 (c)正規化的相關圖譜，計算方式則是將連結數除上「該節點輸出」的數量，此正規化的結果可視為隨機路徑的機率。 這邊一樣要提醒路徑圖譜並沒有用到評分的數值。
Ref: Aggarwal, C. C. (2016). Recommender Systems: The Textbook. Springer.