머신러닝에서 모델의 성능을 측정할 때, recall, precision, MAE, RMSE와 같은 평가 지표를 흔히 사용합니다. 추천 시스템에서도 이러한 지표들을 사용하기는 하지만 추천 작업에 조금 더 특화된 방법을 사용합니다. 본 포스팅에서는 유저의 구매 여부, 클릭 여부와 같은 implicit feedback을 활용한 추천 모델을 기반으로 이러한 평가 지표에 대해 알아보겠습니다. "Collaborative Filtering for Implicit Feedback Datasets" 논문을 바탕으로 movielens 데이터로 구현한 뒤, NDCG와 MAP 평가 지표를 통해 모델의 성능을 측정하겠습니다. 먼저 앞서 설명한 implicit data에 사용되는 두 지표에 대해 알아보겠습니다.
- NDCG (Normalized Discounted Cumulative Gain): NDCG는 모델이 예측한 순위를 반영한 측정 지표입니다. 예측한 추천 목록을 사용자가 선호하는 항목 순으로 정렬하여 순위에 대한 평가를 측정합니다. NDCG는 각 항목의 relevance와 해당 항목의 순위에 따라 가중치를 부여합니다. 더 높은 순위에 있고, relevance가 높은 항목일수록 더 높은 점수를 받습니다. NDCG는 이 점수들을 정규화하여 최종 점수를 계산합니다. 높은 NDCG는 모델의 높은 랭킹 성능을 의미합니다.
- MAP (Mean Average Precision): MAP는 추천 목록의 정확성을 측정하는 데 사용됩니다. MAP는 정밀도(Precision)의 평균값을 계산하는 방식을 사용합니다. 높은 MAP 점수는 정확성이 높은 추천 목록을 의미합니다.
본 포스팅에서 참고하는 "Collaborative Filtering for Implicit Feedback Datasets"에서 말하는 핵심 내용은, 기존 협업 필터링에서 사용하던 사용자와 아이템의 explicit data (예: 평점)뿐만 아니라, 구매 여부, 클릭 기록과 같은 implicit data를 활용한 추천이 필요하다는 것입니다. 또한 이러한 데이터를 위한 새로운 측정 방식도 필요하다고 말합니다. 예를 들어, explicit data인 평점을 예측하는 문제에서는 mae와 rmse같은 지표를 사용하지만, 구매 여부(0 or 1) 예측을 위한 문제에서는 새로운 측정 방식이 필요합니다. 이진 데이터이기 때문에 단순히 accuracy 관점으로 본다면, implicit data는 sparse한 데이터이기 때문에 단순히 0으로만 예측해도 높은 성능을 보일 것입니다.
Implicit 데이터에는 새로운 손실 함수도 필요합니다. 이러한 데이터는 평점이 아니기 때문에 등급이 없습니다. 단순히 0 or 1 관점으로 나타낸 것입니다. 새로운 손실 함수는 아래와 같이 표현할 수 있습니다.
\(p_{ui}\)는 유저 u의 아이템 i에 대한 선호도를 의미합니다. 아래 코드에서는 movielens 데이터에서 레이팅이 존재하는 데이터를 1, 존재하지 않는 데이터를 0으로 전환했습니다.
그러나 \(p_{ui}\)가 0이라고 해서 사용자가 해당 아이템에 대해 부정적인 선호도를 갖는 것은 아닙니다. 따라서 해당 데이터에는 낮은 신뢰도(confidence)를 부여하는 방법을 적용합니다.따라서 \(p_{ui}\)에 대한 신뢰도 수준을 나타내는 \(c_{ui}\)를 추가 변수로 적용합니다.
$$ c_{ui} = 1+\alpha r_{ii}$$
이러한 개념을 바탕으로 행렬 분해 방법인 ALS(Alternating Least Squares)를 적용한 모델을 통해 implicit 데이터에 대한 NDCG와 MAP를 구해보겠습니다. ALS는 사용자-항목 행렬을 분해하여 사용자와 항목을 잠재 요인(latent factor) 공간으로 매핑합니다. ALS는 일반적으로 희소한 사용자-항목 행렬에 대해 잘 동작하며, 추천 시스템에서 널리 사용되는 대표적인 알고리즘 중 하나입니다.
다음으로는 위의 내용들을 코드로 구현해보겠습니다.
먼저 movielens 데이터셋을 불러옵니다. 이 데이터는 영화에 대한 평점 데이터이기 때문에 explicti data라고 할 수 있습니다. 그러나 데이터를 전처리하여 implicit 데이터로 간주하겠습니다. 데이터는 아래 사이트에서 다운 받을 수 있습니다. https://grouplens.org/datasets/movielens/
import numpy as np
import pandas as pd
from math import ceil
from tqdm import trange
from subprocess import call
from scipy.sparse import csr_matrix, dok_matrix
import pandas as pd
df = pd.read_csv('Movies/ml-latest-small/ratings.csv')
df.rename(columns={'movieId':'item_id', 'userId':'user_id'}, inplace=True)
df.head()
### result ###
user_id item_id rating timestamp
0 1 31 2.5 1260759144
1 1 1029 3.0 1260759179
2 1 1061 3.0 1260759182
3 1 1129 2.0 1260759185
4 1 1172 4.0 1260759205
사용자 - 아이템 매트릭스를 생성합니다. 생선된 행렬은 값이 대부분 0인 sparse 데이터 입니다. 따라서 scipy의 scr_matrix를 사용했습니다. 이 행렬은 [n_users, n_items]의 형상을 가집니다.
사용되는 함수의 파라미터는 다음과 같습니다.
- data : DataFrame implicit rating data
- user_col : (str) user column name
- item_col : (str) item column name
- ratings_col : (str) implicit rating column name
반환되는 결과는 다음과 같습니다.
- ratings : scipy sparse csr_matrix [n_users, n_items] user/item ratings matrix
- data : (DataFrame) the implict rating data that retains only the positive feedback (if specified to do so)
def create_matrix(data, user_col, item_col, rating_col):
# map each item and user to a unique numeric value
for col in (item_col, user_col):
data[col] = data[col].astype('category')
# create a sparse matrix of using the (rating, (rows, cols)) format
rows = data[user_col].cat.codes
cols = data[item_col].cat.codes
rating = data[rating_col]
ratings = csr_matrix((rating, (rows, cols)))
ratings.eliminate_zeros()
return ratings, datauser_col = 'user_id'
item_col = 'item_id'
rating_col = 'rating'
X, df = create_matrix(df, user_col, item_col, rating_col)
X
### result ###
<943x1682 sparse matrix of type '<class 'numpy.int64'>'
with 100000 stored elements in Compressed Sparse Row format>
데이터를 train-test로분할합니다.
먼저 test_size 비율이 0보다 크고, 1보다 작은지를 확인합니다.
이후 rating 데이터에서 train 데이터를 복사하고 todok을 적용하여, dictionary를 통해 sparse matrix를 표현합니다.
test set을 나누는 과정을 다음과 같습니다.
- 모든 사용자에 대해 임의로 선택된 상호작용을 테스트로 할당합니다.
- 테스트로 할당되는 상호작용은 학습에서 0으로 할당됩니다.
- 테스트 세트에 들어갈 상호작용을 계산할 때, 숫자를 반올림해야 합니다.
예를 들어, 사용자가 4개의 평가를 가지고 있고, test_size가 0.2인 경우, 0.8개의 평가가 테스트로 들어가야 하므로, 반올림하여 테스트 세트가 적어도 1개의 평가를 받을 수 있도록 해야 합니다.
def create_train_test(ratings, test_size = 0.2, seed = 1234):
assert test_size < 1.0 and test_size > 0.0
train = ratings.copy().todok()
test = dok_matrix(train.shape)
rstate = np.random.RandomState(seed)
for u in range(ratings.shape[0]):
split_index = ratings[u].indices
n_splits = ceil(test_size * split_index.shape[0])
test_index = rstate.choice(split_index, size = n_splits, replace = False)
test[u, test_index] = ratings[u, test_index]
train[u, test_index] = 0
train, test = train.tocsr(), test.tocsr()
return train, test위 sparse matrix가 똑같은 943x1682 형상을 가졌지만, 100,000개의 데이터가 아니라, 79,619개의 train 데이터로 분할되었습니다.
seed = 42
test_size = 0.2
X_train, X_test = create_train_test(X, test_size, seed)
X_train
### result ###
<943x1682 sparse matrix of type '<class 'numpy.int64'>'
with 79619 stored elements in Compressed Sparse Row format>
추천 모델로 사용할, ALSWR (Alternating Least Squares with Weighted Regularization for implicit feedback)을 위한 파라미터는 다음과 같습니다.
- n_iters : (int) number of iterations to train the algorithm
- n_factors : (int) number/dimension of user and item latent factors
- alpha : (int) scaling factor that indicates the level of confidence in preference
- reg : (int) regularization term for the user and item latent factors
- seed : (int) seed for the randomly initialized user, item latent factors
class ALSWR:
def __init__(self, n_iters, n_factors, alpha, reg, seed):
self.reg = reg
self.seed = seed
self.alpha = alpha
self.n_iters = n_iters
self.n_factors = n_factors
def fit(self, ratings):
"""
ratings : scipy sparse csr_matrix [n_users, n_items]
sparse matrix of user-item interactions
"""
Cui = ratings.copy().tocsr()
Cui.data *= self.alpha
Ciu = Cui.T.tocsr()
self.n_users, self.n_items = Cui.shape
rstate = np.random.RandomState(self.seed)
self.user_factors = rstate.normal(size = (self.n_users, self.n_factors))
self.item_factors = rstate.normal(size = (self.n_items, self.n_factors))
for _ in trange(self.n_iters, desc = 'training progress'):
self._als_step(Cui, self.user_factors, self.item_factors)
self._als_step(Ciu, self.item_factors, self.user_factors)
return self
def _als_step(self, Cui, X, Y):
"""
when solving the user latent vectors,
the item vectors will be fixed and vice versa
"""
YtY = Y.T.dot(Y)
data = Cui.data
indptr, indices = Cui.indptr, Cui.indices
for u in range(self.n_users):
# initialize a new A and b for every user
b = np.zeros(self.n_factors)
A = YtY + self.reg * np.eye(self.n_factors)
for index in range(indptr[u], indptr[u + 1]):
# indices[index] stores non-zero positions for a given row
# data[index] stores corresponding confidence,
# we also add 1 to the confidence, since we did not
# do it in the beginning, when we were to give every
# user-item pair and minimal confidence
i = indices[index]
confidence = data[index] + 1
factor = Y[i]
A += (confidence - 1) * np.outer(factor, factor)
X[u] = np.linalg.solve(A, b)
return self
def predict(self):
"""predict ratings for every user and item"""
prediction = self.user_factors.dot(self.item_factors.T)
return prediction
def _predict_user(self, user):
"""
returns the predicted ratings for the specified user,
this is mainly used in computing evaluation metric
"""
user_pred = self.user_factors[user].dot(self.item_factors.T)
return user_predals = ALSWR(n_iters = 15, n_factors = 20, alpha = 15, reg = 0.01, seed = 1234)
als.fit(X_train)
### result ###
training progress: 100%|██████████| 15/15 [01:01<00:00, 4.11s/it]
<__main__.ALSWR at 0x7fb3d9066710>
RANKING METRICS
이제 추천 엔진을 구축했으므로, 다음으로 모델의 성능 평가를 알아보겠습니다. 순위 평가를 위해 사용되는 MAP(Mean Average Precision)와 NDCG(Normalized Discounted Cumulative Gain)를 적용하겠습니다.. 두 지표의 주요 차이점은 MAP는 이진 분류(관심 있는지 여부, 예: 사용자가 링크를 클릭하거나 비디오를 시청하거나 제품을 구매했는지)을 가정하는 반면, NDCG는 추천된 항목에 관련성 점수를 할당할 수 있는 경우(이진, 정수 or 실수) 어떤 경우에도 사용할 수 있다는 것입니다.
MAP
MAP를 직관적으로 이해하면 다음과 같습니다. @k는 각 사용자마다 최대 k개의 항목을 추천할 수 있다는 것을 의미합니다. 여기서 잘못된 예측은 패널티를 받습니다. 또한 순서가 중요하기 때문에, 보다 확실한 예측을 먼저 제시하고, 덜 확실한 예측을 그 뒤에 제시하는 것이 좋습니다
조금 더 자세히 살펴보면, 우선 @k를 무시하고 M을 처리해 보겠습니다. MAP는 모든 사용자의 평균 정밀도(AP)의 평균입니다. 예를 들어, 1000명의 사용자가 있다면 각 사용자의 AP를 합산하여 1000으로 나눈 것이 MAP가 됩니다. 그렇다면 AP 또는 평균 정밀도란 무엇인가요?
우리가 Google에 검색어를 입력하면 10개의 결과가 표시됩니다. 모든 결과가 우리가 관심이 있어하는 내용을 담는 것이 가장 좋은 결과입니다. 만약 적합한 결과가 일부만 있다면(예: 5개), 관련된 항목이 먼저 표시되는 것이 훨씬 좋습니다. 첫 다섯 개가 관련이 없고 좋은 결과는 여섯 번째부터 시작된다면 좋지 않을까요? AP를 계산하기 위한 공식은 다음과 같습니다
sum i=1:k of (precision at i * change in recall at i)
여기서 precision at i는 첫 i개 추천 중 올바른 항목의 비율입니다. change in recall은 i번째 항목이 올바른 경우 (올바른 항목마다) 1/k이고, 그렇지 않은 경우에는 0입니다.
예를 들어, 실제 데이터가 [1 2 3 4 5]이고 [6 4 7 1 2]를 추천했다고 가정해 봅시다. 이 경우, 4, 1, 2를 올바로 추측했지만 중간에 일부 잘못된 추측이 있습니다. 이제 AP@2를 계산한다고 가정해 보겠습니다. 따라서 첫 번째 예측인 6은 잘못되었으므로 precision@1은 0입니다. 두 번째 예측인 4는 올바르므로 precision@2는 0.5입니다. 변경된 재현율은 각각 0과 0.5입니다(이는 1/k입니다). 따라서 AP@2 = 0 0 + 0.5 0.5 = 0.25입니다. 같은 추천 목록에 대한 재현율이더라도, @k를 고려할 때, 올바른 예측이 앞에 나오는 것이 유리합니다.
def compute_apk(y_true, y_pred, k):
"""
average precision at k, y_pred is assumed
to be truncated to length k prior to feeding
it to the function
"""
# convert to set since membership
# testing in a set is vastly faster
actual = set(y_true)
# precision at i is a percentage of correct
# items among first i recommendations; the
# correct count will be summed up by n_hit
n_hit = 0
precision = 0
for i, p in enumerate(y_pred, 1):
if p in actual:
n_hit += 1
precision += n_hit / i
avg_precision = precision / min(len(actual), k)
return avg_precision
정의한 MAP 함수에 예시 데이터를 적용했습니다.
# example 1
k = 2
y_true = np.array([1, 2, 3, 4, 5])
y_pred = np.array([6, 4, 7, 1, 2])
compute_apk(y_true, y_pred[:k], k) # 0.25
### result ###
0.25
###################################################
# example 2
k = 5
y_true = np.array([1, 2])
y_pred = np.array([6, 4, 7, 1, 2])
compute_apk(y_true, y_pred[:k], k) # 0.325
### result ###
0.325
이제 ALS 모델에 적용해보겠습니다.
def mapk_score(model, ratings, k):
"""
mean average precision at rank k for the ALS model
Parameters
----------
model : ALSWR instance
fitted ALSWR model
ratings : scipy sparse csr_matrix [n_users, n_items]
sparse matrix of user-item interactions
k : int
mean average precision at k's k
Returns
-------
mapk : float
the mean average precision at k's score
"""
# compare the top k predictions' index to the actual index,
# the model is assumed to have the _predict_user method
mapk = 0
n_users = ratings.shape[0]
for u in range(n_users):
y_true = ratings[u].indices
u_pred = model._predict_user(u)
y_pred = np.argsort(u_pred)[::-1][:k]
mapk += compute_apk(y_true, y_pred, k)
mapk /= n_users
return mapkk = 5
mapk_train = mapk_score(als, X_train, k)
mapk_test = mapk_score(als, X_test, k)
print('mapk training:', mapk_train)
print('mapk testing:', mapk_test)
### result ###
mapk training: 0.16900149031296557
mapk testing: 0.04004595131644308
NDCG
NDCG는 순위를 반영한 측정 지표입니다. 모델이 예측한 결과의 순서에 relevance 점수를 부여합니다. 이를 gain(G)이라고 합니다. 사용자의 피드백이 없는 항목의 경우, 보통 gain을 0으로 설정합니다. 이제 이 점수들을 합산하여 Cumulative Gain (CG)을 얻을 수 있습니다. 특정 순위 k에서의 CG는 다음과 같이 정의됩니다
$$ CG_k = \sum_{i=1}^k rel_i$$
\(rel_i\)는 i번째 위치에서의 고정된 relevance를 의미합니다. 공식에서 알 수 있듯이, 이 함수로 계산된 값은 검색 결과의 순서 변경에 영향을 받지 않으므로, 결과의 순위에 대한 유용성을 더 정확하게 측정하기 위해 CG 대신 DCG를 사용합니다.
순위를 평가할 때, 우리는 가장 관련성이 높은 아이템이 우선적으로 표시되기를 선호합니다. 즉, 검색 결과에서 첫 번째 결과가 두 번째 결과보다 중요하고, 두 번째 결과가 세 번째 결과보다 중요한 것입니다. 따라서 점수를 합산하기 전에 각각을 증가하는 수인 discount (D)로 나눕니다. 각 점수를 순위로 나누어서 위치 1을 더 중요하게 만드는 것입니다. 실제로는 항목 위치의 로그를 사용하여 discount을 적용하는 것이 더 일반적이므로 다음과 같습니다.
$$ DCG_k = \sum_{i=1}^k \frac{rel_i} { log_2 (i+1) }$$
k가 의미하는 순위가 증가할수록 분모에 의해 discount가 적용됩니다.
def dcg_at_k(score, k = None):
if k is not None:
score = score[:k]
discounts = np.log2(np.arange(2, score.size + 2))
dcg = np.sum(score / discounts)
return dcg
score = np.array([2, 0, 3, 2])
dcg_at_k(score)
### result ###
4.361353116146786결과 예측 길이가 인풋 데이터에 따라 다를 수 있기 때문에, DCG 값을 비교하는 것은 공정하지 않습니다. 이러한 점수를 정규화한 NDCG는, 만약 랭킹 예측이 최상의 결과일때의 점수와 현재 예측 점수 DCG를 나눕니다. \(IDCG_k\)는 k개의 랭킹 예측에서의 이상적인 결과입니다.
$$ NDCG_k = \frac{DCG_k}{IDCG_k} $$
def ndcg_at_k(score, k = None):
actual_dcg = dcg_at_k(score, k)
sorted_score = np.sort(score)[::-1]
best_dcg = dcg_at_k(sorted_score, k)
ndcg = actual_dcg / best_dcg
return ndcg
ndcg_at_k(score)
### result ###
0.7497534568197889최종적으로 앞서 설계한 ALS 추천 모델에 필요한 평가 척도 모듈을 정리했습니다.
def ndcg_score(model, ratings, k):
"""
Normalized discounted cumulative gain (NDCG) at rank k
for the ALS model; which computes the ndcg score for
each users' recommendation and does a simply average
Parameters
----------
model : ALSWR instance
fitted ALSWR model
ratings : scipy sparse csr_matrix [n_users, n_items]
sparse matrix of user-item interactions
k : int
rank k's k
Returns
-------
avg_ndcg : float
ndcg at k's score averaged across all users
"""
ndcg = 0.0
n_users, n_items = ratings.shape
for u in range(n_users):
y_true = np.zeros(n_items)
y_true[ratings[u].indices] = 1
u_pred = model._predict_user(u)
ndcg += ndcg_at_k(y_true, u_pred, k)
avg_ndcg = ndcg / n_users
return avg_ndcg
def ndcg_at_k(y_true, y_score, k = 10):
"""
Normalized discounted cumulative gain (NDCG) at rank k
Parameters
----------
y_true : array-like, shape = [n_samples]
Ground truth (true relevance labels)
y_score : array-like, shape = [n_samples]
Predicted scores
k : int
Rank
Returns
-------
ndcg : float, 0.0 ~ 1.0
"""
actual = dcg_at_k(y_true, y_score, k)
best = dcg_at_k(y_true, y_true, k)
ndcg = actual / best
return ndcg
def dcg_at_k(y_true, y_score, k = 10):
"""
Discounted cumulative gain (DCG) at rank k
Parameters
----------
y_true : array-like, shape = [n_samples]
Ground truth (true relevance labels)
y_score : array-like, shape = [n_samples]
Predicted scores
k : int
Rank
Returns
-------
dcg : float
"""
order = np.argsort(y_score)[::-1]
y_true = np.take(y_true, order[:k])
gains = 2 ** y_true - 1
discounts = np.log2(np.arange(2, gains.size + 2))
dcg = np.sum(gains / discounts)
return dcg결과는 다음과 같습니다.
k = 5
ndcg_train = ndcg_score(als, X_train, k)
ndcg_test = ndcg_score(als, X_test, k)
print('ndcg training:', ndcg_train)
print('ndcg testing:', ndcg_test)
### result ###
ndcg training: 0.2959125755797325
ndcg testing: 0.11226091289209723
Reference
Hu, Y., Koren, Y., & Volinsky, C. (2008, December). Collaborative filtering for implicit feedback datasets. In 2008 Eighth IEEE international conference on data mining (pp. 263-272). Ieee.
https://en.wikipedia.org/wiki/Discounted_cumulative_gain
http://fastml.com/evaluating-recommender-systems/
https://gist.github.com/mblondel/7337391
http://ethen8181.github.io/machine-learning/recsys/2_implicit.html
'Recommender System' 카테고리의 다른 글
| Yelp 데이터로 NCF 코드 밑바닥부터 구현하기 with PyTorch (0) | 2023.06.28 |
|---|---|
| 그래프 기반 추천시스템의 이해 (0) | 2023.06.21 |
| [코드 리뷰] PyTorch로 NCF 모델 구현하기 (without pre-training) (0) | 2022.11.28 |