Collaborative Filtering 에서의 유사도 지표 제안 논문.

 

 CF 알고리즘에서 새로운 유사도 지표를 제안하여 기존 보다 나은 성능을 내도록 연구한 논문에 대한 간략한 정리. 이번 장에서는 2개의 논문에 대한 정리를 한다. 

 기존의 어떤 문제를 해결하고자 하는지,  제안하려는 유사도 지표가 주는 이점, 한계점 등에 대해 간략하게 정리한다.

 

 

1. A new similarity measure for collaborative filtering based recommender systems  2019, Achraf Gazdar, Lotfi Hidri.

 요약: CF 알고리즘은 유사도 지표를 토대로 유사한 사용자 집단을 구성하고, 이를 토대로 추천이 이루어진다. 이 때, 유사도를 측정하는 부분에 있어서 지금껏 다양한 유사도를 제안해왔고, 이 논문은 심플하고 효율적인 유사도 지표를 제안한다. 1) 유사도 측정에 의해 충족되어야하는 직관적이고 정성적인 조건을 수학식으로 표현하는것. 2) 유사도 측정에 대해서 커널함수를 사용하여 방정식을 푸는 것. 제안한 방법은 다른 유사도 측정 연구들에 대해 정확성 측면에서 매우 경쟁적이다.

 

 제안한 similarity measure.

 

본 논문이 제안한 유사도 지표는 아래의 $sim_{uv}^{OS}$ 와 같다. 

 

우선 $sim_{u}^{PNCR}$ 의 경우는 지수함수로 유사도 값을 내는 식이다. 그래프는 function이 주황색 곡선으로 나타난 아래의 그래프와 같다. 

$e^{-x}$에서 input $x$에 들어가는 부분은 $\frac{N - |I_{u} \cap I_{v}|}{N}$ 로써 co-rated 가 아닌 비율을 가리킨다. (Percentage Non Common Ratings) 우선 input $x$는 식을 보아도 거의 1에 가까운 값을 대입하게 된다. 만약 co-rated 가 0개인 두 쌍에 대해서는 $x$가 1이 되고, 매핑되면 약 0.3678 의 값을 갖고, 만약 전체의 10%가 공통 평가 항목이라면, $x$가 0.9 가 되고, 매핑된 값 약 0.4065 의 값을 출력한다. 전체의 10% 가 공통항목이면 굉장히 큰 평점 행렬로 보면 상당히 큰 수치임에도 유사의 차이는 소수점에서의 미세한 차이를 보일 뿐이다.

 

 

$y=e^{-x}$ 그래프

 

 

$sim_{uv}^{ADF}$ 는 $rad_{uvi}$ 값을 지수함수 매핑 값들의 평균을 낸 값이다. 본 논문에서는 $rad_{uvi}$를 relative absolute difference(상대 절대 차이)로 부른다. 기존의 absolute difference의 경우에는 예를 들어 1과 2의 차이는 1, 그리고 4와 5의 차이도 역시 1이다. 둘 다 값이 1 차이라는 것말고는 다른 정보가 없다. 하지만 $rad_{uvi}$를 사용하게 되면 각각 0.5와 0.2가 된다. 이 말인 즉슨, 4와 5의 차이가 1과 2의 차이 보다 덜 민감하다는 것이다. 4와 5의 차이가 상대적으로 덜하다고 나타내는 것이다. 

 

 

 우선 absolute difference를 왜 relative absolute difference로 고려를 하였는지 표를 만들어 확인을 해보았다. 아래의 표를 보면 동일한 평점을 내린 경우를 제외한 나머지 모든 경우의 수에 대한 값을 계산한 결과이다. 두 사용자의 절대 차이가 1인 경우들만 보면 절대 차이는 1로 동일하지만 분모의 max 값이 커짐에 따라 $rad_{uvi}$ 값이 줄어듦을 알 수 있다. max값을 분모에 넣음으로써 weight를 달리한다는 것을 알 수 있다. 좀 더 직관적으로 설명해보면, 두 평점 쌍이 평균적으로 점수가 높을수록 둘 사이의 차이를 조금 덜 민감하게 반영하겠다는 소리이다.

그리고 이어서 지수함수의 input으로 삽입한 합을 0~1사이로 표현하기위해 co-rated 개수로 나누어 준다.

 

 

정리해보면, $sim_{uv}^{PNCR}$ 같은 경우에는 co-rated 의 비율을 지수함수를 사용하여 표현하고, $sim_{uv}^{ADF}$의 경우는 상대 절대 차이를 사용해서 동일한 절대 차이에서도 상대적으로 sensitivity를 반영한다. 

기존의 traditional 한 유사도 지표인 자카드 유사도와 MSD가 가진 장점을 둘 다 활용할 수 있고, 변형으로 더 디테일하게 두 평점 쌍의 관계를 고려했다고 볼 수 있다.

 

2. A new method to find neighbor users that improves the performance of Collaborative Filtering 2017, Hamidreza Koohi, Kourosh Kiani.

 

 요약: 본 논문은 사용자의 유사도를 구하기 위해서 3가지 sub space를 사용하게 된다. 그 sub space라 함은 첫번째, 흥미를 가지는 아이템에 대한 매트릭스이고, 두번째 흥미를 가지지도 안가지지도 않은 매트릭스이고, 마지막은 흥미를 가지지 않은 아이템에 대한 매트릭스이다. 이 세 매트릭스를 구성하여 최종적으로 target user와의 유사도 값을 계산하는데 사용한다.

 

 세가지 매트릭스를 구성한다 하였는데, 어렵지 않게 구성이 가능하다. 기존의 rating 매트릭스가 존재할텐데, 이를 세 개의 binary 매트릭스로 구성한다. 

- 첫번째 흥미있다고 여겨지는 4, 5 점에 대해서 1을 주고 아니면 0을 기입하는 방식.

- 두번째 흥미있지도 없지도 않다고 여겨지는 3점에 대해서는 1을 주고 아니면 0을 기입하는 방식.

- 세번째 흥미없다고 여겨지는 1,2점에 대해서는 1을 주고 아니면 0을 기입하는 방식.

아래의 그림처럼 나타낸다고 보면 된다. 여기서 NIU 는 Neighbor Iterested Nor Uninterested(좋아하지도 안좋아하지도 않은.)을 말한다.

 $U_{1}$을 기준으로 보면,  (a)의 경우에는 2, 4, 6번 아이템이 interesting 항목으로, 7번 아이템이 NIU 항목에 체크가 되고, uninteresting은 항목이 없는 것을 알 수 있다.

 

 

Fig.3 을 구성하였다면 아래의 행렬처럼 subspaces 들로 구성된 Fig.4 행렬을 만든다. 아래의 예는 interesting (a) 에 대한 것으로만 구성된 행렬이다. .

 

Fig.4 는 Fig.3의 (a)에서 뽑아낸 subset 들이다. Fig.4 를 만드는 방법은 $u_{i}$와 $u_{i}$가 아닌 user들과 비교하면서 교집합들을 구하는 식으로 만들게 된다.

Fig.3의 (a)를 기준으로 subset을 구성해보자.

$u_{1}$ = {$i_{2}$, $i_{4}$,$i_{6}$, ($i_{2}$, $i_{4}$)}

$u_{2}$ = {$i_{4}$, ($i_{4}$, $i_{7}$)}

$u_{3}$ = {$i_{4}$, $i_{8}$, ($i_{4}$, $i_{8}$)}

$u_{4}$ = {$i_{8}$, ($i_{3}$, $i_{8}$)}

$u_{5}$ = {$i_{4}$, $i_{8}$, ($i_{2}$, $i_{4}$), ($i_{4}$, $i_{7}$), ($i_{2}$, $i_{8}$), ($i_{4}$, $i_{8}$)}

$u_{6}$ = {$i_{2}$, $i_{8}$, ($i_{2}$, $i_{8}$)}

$u_{7}$ = {$i_{6}$, $i_{8}$, ($i_{3}$, $i_{8}$)}

7 명의 user에 대하여 자신을 제외한 나머지 user와 공통으로 포함된 집합들을 전부 체크한 후, 중복된 것만 빼고 나면 Fig.4 와 같이 9개의 subset을 얻어낼 수 있다.

 

이 후, Fig.4 를 아래의 Fig.5 와 같이 중복되는 부분을 제거한다. 더 큰 부분집합에 속해 있으면 기존의 작은 element는 제거를 한다. 그래서 (a) 에서 (b)와 같이 9개에서 6개의 subset 으로 바뀌게 된다.

Fig.4와 Fig.5 는 interesting에 대해서만 했기 때문에 NIU와 uninteresting 경우에 대해서도 진행해주어야 한다.

 

 

Fig. 6은 위의 만들어진 global table을 활용해서 user 별로 subset을 매칭해서 neighbor pair를 구성한다. 이 때 내림차순으로 정렬된 기준은 subset의 크기이다. subset이 더 큰 것을 동시에 포함하고 있으면 당연히 더 유사하다고 판단할 수 있기 때문이다.

 

이어서 Fig.7 은 한 user가 여러 user과 중복으로 이웃으로 적용되는 경우 빨간색으로 표시하고, 맨 아래에 파란색으로 표시된 것은 indirectly neighbor라고 해서 말 그대로 직접적으로 유사도를 표현하기 힘든 부분들이다. 공통적으로 평가한 부분이 적기 때문이라고 생각한다.

 

 

Fig.8 의 트리는 새로운 User가 interested in 2번, 3번, 4번 인 경우를 예를 들어 나타낸 그림이다. 2번, 4번을 가진 1,5번 user와 가장 유사하게 먼저 이어주고, 각 1, 5번에 해당하는 indirect neighbor을 그리게 된다.

 

 

Fig.8 만 보아도, 새로운 User가 들어오면 위에 1, 5번 user와 같이 2단계에 위치한 user들과의 유사도를 구하면 된다. PCC를 사용한다. 이 PCC가 가장 성능이 좋단다. 

 본 논문에서 제안한 부분은 direct한 user와의 유사도에 대한 것이 아닌 이어서 indirectly similar user와의 유사도 계산에 대한 부분을 develop한 것이다. 위의 예를 보면은 3단계에 위치한 친구들은 오직 하나의 값만 공통으로 갖는 것을 알 수 있고, 이것이 의미하는 것은 곧 고전적인 유사도 측정 지표로는 유사도 계산을 할 수 없다는 것을 의미한다. 

 

 이에 유사도를 구하기 위해 아래와 같은 수식을 제안한다.

 $u_{a}$는 target user를 말하며, $u_{i}$는 indirect neighbor을 의미한다. $u_{a}$와 $u_{i}$ 는 joint direct neighbor $u_{x}$ 와 비교될 것이기 때문에,  $p$는 direct neighbor $u_{a}, u_{x}$ 또는 $u_{x}, u_{i}$ 사이의 $w$, $L$의 조합으로 나타내지게 된다. 

그리고 $w$와 $L$은 아래에 설명이 되어있다.

 

 우선 $L$의 경우에는 아래와 같은데, $|I_{i} \cap I_{j}|$ 는 $i, j$가 동시에 평가한 항목들의 개수이고, $|I_{i} \cup I_{j}|$는 각각의 아이템의 합집합이다. 여기서 $i$는 target이고, $j$는 direct neighbor user이다. 자카드 유사도에 $\alpha$ constant를 붙여서 동시평가항목이 많음에 2 같은 가중치를 준다. 

$w$의 경우는 분자에는 sum of square difference 라는 것을 MSD를 이미 알기에 알 것이고, 분모 부분에서 단순이 $n$으로 나누는 데에다가 가중치 $\beta$를 붙였다. 즉, 위의 자카드 유사도에 동시평가항목이 많을 수록 높은 가중치를 부여하게 되는 것이다.

$L$ 과 $w$를 살펴 보았는데, 좀 정리가 필요한 것 같다. 트리구조를 기반으로 정리해보면 active User가 있을 때, direct neighbor(2단계)와는 PCC로 쉽게 유사도를 계산할 수 있는 반면에 3단계부터 indirect neighbor를 만나면 유사도를 측정 불가하니, 2단계의 direct neighbor과 indirect neighbor의 유사도를 활용하는 것이다. 그렇기 때문에 애초에 제안한 유사도에 iteration이 $p$ 라는 direct, indirect neighbor이 섞인 횟수로 돌린다. 

 

 

 행렬 자체가 sparse하다 보니 동시평가항목을 구하는 것도 일인데, 이렇게 동시평가항목이 부족하거나 없을 지라도 이방법을 사용하게 된다면, 물론 당연히 계산량은 늘겠지만 구하지 못하거나 어줍잔히 구하는 것보다 나은 결과를 얻는 것같다. 

 

 

 

 

 

[1] A new similarity measure for collaborative filtering based recommender systems (2019)

[2] A new method to find neighbor users that improves the performance of Collaborative Filtering (2017)