이웃 기반 협업 필터링 (3)

4. 클러스터링과 이웃 기반 방법론

이웃 기반 방법론의 주요 문제점은 오프라인 단계에서의 복잡성이다. 사용자와 아이템의 수가 늘어날수록 시간복잡도와 공간복잡도는 기하급수적으로 늘어나기 때문이다. 이를 해결하기 위한 방법 중 하나가 클러스터링을 이용하는 것이다.

클러스터링 기반 방법론의 주요 관점은 오프라인에서 가장 근접한 이웃 단계를 클러스터링 단계로 대체하는 것이다. 오프라인에서의 가장 근접한 이웃을 찾는 단계는 많은 피어 그룹을 생성하며 가능한 타깃들이 중심이 되는 것처럼, 클러스터링 단계는 각각의 가능한 타깃이 중심이 될 필요도 없고 더 작은 피어 그룹을 생성한다. 클러스터링 단계는 모든 가능 타깃에 대해 $O(m^2n’)$(사용자 기반 이웃 모델 복잡도)시간을 요구하는 것보다 훨씬 효율적이다. 클러스터가 한 번 생기면, 평점을 예측하는 단계는 이웃 기반 방법론과 유사한 방법으로 진행된다. 큰 차이점은 클러스터 안에서의 상위 -$k$의 가장 근접한 동료가 예측에 활용된다는 점이다. 쌍에 대한 유사도 계산은 같은 클러스터 안에서만 작용해야 하므로 훨씬 더 효율적이다.

다만 클러스터 내 각 대상에 가장 이웃한 이웃 집합이 전체 데이터보다 더 낮은 품질을 가지기 때문에 정확성이 다소 떨어진다. 또한 클러스터링 세밀도는 정확성과 효율성 사이의 trade-off를 제공한다. 클러스터가 세분화되면 효율성은 개선되지만 정확도는 떨어진다. 많은 경우 효율성에서의 큰 증가는 정확도의 작은 감소로 이루어지므로, 평점 행렬이 큰 경우 클러스터링을 이용하면 적은 비용으로 실용적인 대안을 제공한다.

이 방법론의 한 가지 문제점은 평점 행렬이 불완전하다는 것이다. 따라서 클러스터링 방법론은 아주 큰 불완전한 데이터 세트에서 적용된다. 많이 사용하는 클러스터링 방법은 K-means 클러스터링 방법으로, $k$개의 대표 집합을 형성후 각 클러스터 별 결과값을 클러스터에 속하는 데이터의 평균으로 대체하는 방법이다. 이를 평점 행렬에 적용한 방법은 다음과 같다.

1. $m\times n$ 행렬의 각 열에 대해 근접한 $\bar Y_1, …, \bar Y_k$를 할당함으로써 클러스터 $C_1, …, C_k$를 결정한다. 대체로 유사도 계산에 있어서 유클리드 거리 혹은 맨해튼 거리를 이용한다.
2. 각 $i \in {1, …, k}$에 대해 $C_i$의 현재 포인트의 집합의 중심에 대해 $\bar Y_i$를 재설정한다.

이 방법을 사용할 때 주된 문제점은 $m\times n$ 평점 행렬이 불완전하다는 것이다. 따라서 평균과 거리는 정의되지 않을 수 있으므로, 클러스터 내 관측된 값만을 이용해 평균을 계산한다. 경우에 따라 클러스터 내의 하나 이상의 아이템에 대한 평점이 지정되지 않았다면 중점은 완전하게 지정되지 않는다. 거리 값은 데이터 포인트와 클러스터의 대표에 대해, 차원의 하위 집합만을 사용해 계산된다. 거리는 차원의 수로 나눠진다. 모든 중점이 완전히 지정되지 않았ㄷ을 때, 여러 개의 중심점에 대한 데이터 포인트의 거리를 계산하기 위해 서로 다른 개수의 차원이 사용된다는 사실을 조정하기 위해서이다. 이러한 맥락에서 맨해튼 거리가 유클리드 거리보다 더 나은 조정을 보이며, 정규화 값은 각 관측치의 평균 거리로서 더우 쉽게 해석될 수 있다. (정리하면, 클러스터와 데이터 포인트 사이의 거리를 계산함에 있어, 관측된 변수만을 기준으로 거리를 계산하고, 이후 관측된 변수 개수(변수 차원)만큼 나누어서 거리를 계산함.)

위의 방법은 사용자 기반 협업 필터링을 위해 열에 클러스터링을 지정하며, 아이템 기반 방법론에서는 행을 클러스터링해야한다.

5. 차원 축소와 이웃 기반 방법론

차원 축소 방법론은 이웃 기반 방법론의 품질과 효율성을 높이는 데 쓰일 수 있다. 차원 축소는 잠재 요인 모델이라고도 하는데, 비록 두 사용자가 공통으로 평점을 매긴 아이템이 매우 적다 하더라도, 저차원 잠재 벡터에서는 그 거리가 계산될 수 있따. 더 나아가, 피어 그룹을 결정하는 데 더욱 효율적이다. 잠재 요인 모델이 추천 시스템에 쓰이는 두 가지 방법은 다음과 같다.

1. 데이터의 축소된 형태는 잠재 요인의 열과 행 형태로 만들 수 있다. 즉 아이템 차원에서 차원을 줄이거나 사용자 차원에서 차원을 줄일 수 있다. 이렇게 축소된 형태는 이웃 기반 모델의 희소성 문제를 완화할 수 있다. 잠재 요인에서 어떤 차원이 축소됐냐에 따라, 축소된 형태는 사용자 기반 이웃 알고리즘에 사용되거나 아이템 기반 이웃 알고리즘에 쓰인다. (축소된 행렬을 이용하여 유사도를 구하고, 이를 활용해 이웃 기반 협업 필터링에 사용한다.)
2. 행 공간과 열 공간의 잠재 형태는 동시에 결정된다. 잠재 형태는 이웃 기반 방법론을 쓰지 않은 채 평점 행렬의 전체를 한 번에 재구성하는데 사용된다.

이 중 이웃 기반 방법론에서 사용할 수 있는 방법은 첫 번째 방법이고, 두 번째 방법은 모델 기반 협업 필터링 방법론 중 하나이다.

사용자 기반 협업 필터링 방법론의 기본 구조는 행렬 $R$의 $m\times n$ 평점 형렬을 주성분 분석을 이용해 저차원으로 변화시킨다. 결과 행렬 $R’$은 $d«n$을 가지는 $m \times d$ 행렬이다. 즉 $n$ 차원의 평점 벡터는 $d$차원 공간으로 축소되었으며, $d$차원의 벡터는 완벽히 지정되어 있다. 이 $d$차원 형태의 각 사용자가 결정이 되면 타깃 사용자와의 유사도를 계산할 수 있게 된다. 저차원에서의 유사도 계산은 모든 차원이 완전히 지정돼 있기 때문에, 그 값은 강건하고, 차원이 축소됨에 따라 유사도 산출은 더욱 효율적이게 된다.

각 데이터 포인트의 저차원 표현법은 SVD나 PCA를 이용한다. SVD를 이용하는 경우는 다음과 같다.

첫 번째 단계는 누락된 엔트리를 채우기 위해 $m\times n$의 불완전한 평점 행렬 $R$을 증가시키는 것이다. 누락된 엔트리는 행렬 내 해당 행의 평균(해당 유저의 평점의 평균)과 동일한 값으로 예측하거나, 해당 열의 평균(해당 아이템의 평점의 평균)과 동일한 값으로 예측한다. 이 후 결과 행렬을 $R_f$라 하면, 다음 아이템 쌍끼리의 유사도행렬 $S=R_f^TR_f$를 계산할 수 있다. 이를 대각화시키면

\[S = P\Delta P^T\]

를 얻을 수 있다. 여기서 $\Delta$의 diagonal element는$S$의 eigenvalue를 크기 순으로 나열한 값이고, $P$의 column은 $\Delta$의 각 diagonal entry에 대응하는 eigenvector이다. 여기서, 값이 큰 eigenvalue entry와 이에 해당하는 eigenvector 열은 제거하고, 남은 matrix를 각각 $P_d, \Delta_d,$라 하면 차원이 축소된 matrix $S_d$는 다음과 같이 나타낼 수 있다.

\[S_d = P_d \Delta_d P_d^T\]

여기서 $R_f$에 대한 저차원 축소 표현 행렬 $R_d$는 다음과 같이 나타낼 수 있다.

\[R_d = R_f P_d\]

따라서 $R_f$가 아닌 $R_d$를 이용하여 사용자 기반 이웃 모델을 사용할 수 있다. 마찬가지로, $R_f^T$에 위와 같은 SVD 방법을 적용하여 축소시킨 $R_d$에 대해서 아이템 기반 이웃 모델을 사용할 수 있다.

PCA 방법론도 위 방법론과 비슷하며, $R_f$가 아닌 열을 따라 평균 중심 행렬을 이용하는 경우 같은 결과를 얻을 수 있다. 평균 중심은 bias를 줄이는 측면에서 이점이 있다. 다른 방법은 먼저 각 행을 따라 중심을 평균한 다음 각 열에 따라 중간 중심을 지정하는 것이다. 이 후 SVD를 적용하며, 강력한 결과를 제공한다.

1) Bias 문제 처리

행렬 $R_f$는 불특정 항목을 행 또는 열을 따라 평균 값으로 작성해 불완전행렬 $R$에서 파생된다는 점에 유의해야 한다. 이러한 접근 방식은 상당한 bias를 일으킬 가능성이 있다. 다음 example을 통해 bias 문제에 대해 자세히 알아보도록 하자.

example

대부, 글래디에이터, 네로 이 세 영화에 12명의 사용자가 제공한 평점 표가 다음과 같다.

	대부	글래디에이터	네로
user 1	1	1	1
user 2	7	7	7
user 3	3	1	1
user 4	5	7	7
user 5	3	1	?
user 6	5	7	?
user 7	3	1	?
user 8	5	7	?
user 9	3	1	?
user 10	5	7	?
user 11	3	1	?
user 12	5	7	?

위 문제에서 $R_f$를 만들 때 열을 기준으로 빈 칸을 채운다면, 네로의 8개의 칸은 $(1+7+1+7)/4=4$의 값으로 채워진다. 위와 같이 채우게 될 경우, 네로와 글레디에이터 간의 예상 공분산은 크게 감소된다. (이는 user 1부터 user 4까지 평점이 모두 같았기 때문이다.). 누락된 평점을 입력한 후 세 영화 간의 공분산은 다음과 같이 추정할 수 있다.

	대부	글래디에이터	네로
대부	2.55	4.36	2.18
글래디에이터	4.36	9.82	3.27
네로	2.18	3.27	3.27

앞서 언급한 추정에 따르면, 대부와 글래디에이터 사이의 공분산은 글래디에이터와 네로 사이의 공분산보다 크다. 여기서, 모두 채워진 평점으로 보았을 때 네로와 글래디에이터는 값이 똑같았기 때문에, 대부와 글래디에이터 간의 공분산보다 글래디에이터와 네로 간의 공분산이 더 클 것이라고 생각할 수 있는데, 열의 평균으로 관측되지 않은 값을 채웠기 때문에 위와 같은 결과가 발생하였다. 따라서, 빈 칸을 행이나 열의 평균값으로 대체하기 때문에, bias가 발생하게 된다. 이러한 bias를 해결하기 위한 방법론으로 최대 우도 추정, 불완전한 데이터의 직접 행렬 인수 분해 두 방법이 있다.

(1) 최대 우도 추정

개념적 재구성 방법은 공분산 행렬을 추정하기 위해 EM 알고리즘과 같은 확률적 기술의 사용을 제안한다. 데이터에 대해 생성 모델이 가정되고 지정된 항목은 생성 모델의 결과로 간주된다. 공분산 행렬의 maximum likelihood estimate가 계산되는데, 이 때 각 항목 쌍 간의 공분산의 mle은 지정된 항목 간의 공분산으로 추정된다. 즉, 특정 항목 쌍에 대한 평점을 지정한 사용자만의 정보만 공분산을 추정하는 데 사용된다. 한 쌍의 항목 간에 공통된 사용자가 없는 경우 공분산은 0으로 추정된다. 이 방법을 사용하면 위 예시의 데이터에 대해 다음과 같은 공분산 행렬이 추정된다.

	대부	글래디에이터	네로
대부	2.55	4.36	8
글래디에이터	4.36	9.82	12
네로	12	12	12

이 경우 글래디에이터와 네로의 공분산이 대부와 글래디에이터 사이의 거의 세 배라는 것을 바로 알 수 있다. 또한 영화 네로는 원래 예상했던 것보다 3배 이상의 분산 값을 보이며 모든 영화 중 평점의 분산이 가장 크다. 대부와 글래디에이터 사이의 쌍별 공분산은 평균 채우기 방법을 사용하는 다른 모든 쌍별 공분산 중 가장 컸지만, 위 쌍은 이제 모든 쌍별 공분산 중 가장 작게 나타난다.

평점 행렬에서 지정되지 않은 항목의 비율이 클수록 평균 채우기 방법의 bias가 커지게 된다. 따라서 지정된 항목만 활용하는 수정된 기법은 공분산 행렬을 계산하는 데 사용된다. 이러한 기술이 항상 효과적인 것은 아니지만 평균 채우기 방법보다 우수하다. 축소된 $n\times d$ 기초 행렬 $P_d$는 생성된 공분산 행렬의 최상위 $d$ 고유 벡터를 선택해 계산된다.

Bias를 더욱 줄이기 위해 불완전행렬 $R$이 $R_f$ 대신 직접 $P_d$에 porjection될 수 있다. 아이디어는 $P_d$의 각 잠재 벡터에 $R$의 관측된 평점을 projection 시켰을 때의 기여도를 계산하고, 그 후 평점의 기여도에 대해 평균을 취한다.

$\bar e_i$를 $P_d$의 $i$ 번째 column(eigenvector)이고, $j$th entry를 $e_{ji}$라 하자. $R$에서 관측된 사용자 $u$의 $j$번 째 아이템에 대한 평점을 $r_{uj}$라 하면, $i$번 째 잠재 벡터 $\bar e_i$로의 $r_{uj}$의 projection에 대한 기여도는 $r_{uj}e_{ji}$로 나타낼 수 있다. 이 후 $I_u$를 사용자 $u$가 평점을 매긴 아이템 index라 할 때, 사용자 $u$의 $i$번 째 잠재 벡터에서의 평균 기여도 $a_{ui}$는 다음과 같다. (정리하면, $R_fP_d$를 계산하는 대신에, $R$에서 기록된 평점에 대해서만 계산에 활용함.)

\[a_{ui} = \frac{\sum_{j \in I_u}r_{uj}e_{ji}}{\begin{vmatrix} I_u \end{vmatrix}}\]

위 방법의 평균 정규화는 다른 사용자가 서로 다른 평점 수를 지정한 경우에 특히 유용하다. 생성된 $m \times d$ 행렬 $A = [a_{ui}]_{m\times d}$는 기본 평점 행렬의 축소된 표현으로 사용된다. 축소된 행렬은 사용자 기반 협업 필터링에서 타깃 유저의 이웃을 계산하는데 효율적으로 사용된다. 마찬가지로 사용자 차원을 줄이기 위해 $R^T$에 위의 방법을 이용할 수 있고, 아이템 기반 협업 필터링에서 사용이 가능하다.

2) 불완전한 데이터의 direct matrix factorization

첫 번째 방법은 평점 행렬의 희소성이 높은 경우는 완전히 효과적이지는 않다. 이는 공분산 행렬 추정이 강력한 추정을 위해서는 각 항목 쌍에 대해 충분한 수의 관찰된 평점을 필요로 하기 때문이다.

좀 더 직접적인 방법은 matrix factorization 방법을 이용하는 것이다. $m\times n$ 평점 행렬 $R$이 모두 지정돼 있다고 가정한다면, 행렬 $R$은 다음과 같이 factorization이 된다.

\[R = Q\Sigma P^T\]

여기서 $Q$는 $m\times m$ orthogonal matrix이고, $P$는 $n \times n$ orthogonal matrix이다. 또한 $\Sigma$의 diagonal element는 $R$의 singular value로 이루어져 있다.

여기서 $d\leq \min{m, n}$ 개의 가장 큰 singular value를 이용하여 위 행렬을 자를 수 있다.

\[R \approx Q_d \Sigma_d P_d^T\]

여기서 $Q_d$는 $m \times d$, $\Sigma_d$는 $d \times d$, 그리고 $P_d$는 $n\times d$ matrix이다. 이러한 방법의 matrix factorization은 다른 factorization에 비해 근사한 항목의 mean squared error가 가장 작다는 것을 알 수 있다. 따라서 불완전한 평점 행렬 $R$에 대해서 위와 같이 factorization할 수 있다면, 축소된 basis 뿐만 아니라 해당 basis에 대한 평점 또한 알 수 있다. 하지만 문제는 $R$은 불완전한 matrix이므로, 위와 같이 factorization이 될 수 없다. 따라서 평점 행렬에서 관측된 항목에 대해서만 factorization의 mean squared optimization을 진행해 최적화 문제를 재구성할 수 있다. 또는 비선형 최적화 기술을 이용해 수정된 공식을 명시적으로 해결할 수 있다. 이 결과로 robust하고 unbiases된 낮은 차원이 생성되고, 평점 행렬을 직접 추정하는 데 사용될 수 있다.