Chapter 2 이웃 기반 협업 필터링

2.3 이웃 기반 방법론의 평점 예측

이웃 기반 방법론의 기본 아이디어

• 사용자-사용자 유사도를 이용
• 상품-상품 유사도를 이용

여기서 이웃이라는 개념은 예측을 위해 유사한 상품이나 유사한 사용자를 이용한다는 의미

협업 필터링 문제는 분류나 회귀 모델링 문제의 일반화로 볼 수 있다.

2.3.1 사용자 기반 이웃 모델

타깃 유저 i의 이웃을 찾기 위해 모든 사용자와의 유사도가 계산된다. 이 때 계산되는 유사도 함수를 정의해야 한다.

1. 피어슨 상관계수
   1-1. 평균 구하기
   
   - 분자 : 유저가 평가한 아이템의 점수의 합
   - 분모 : 해당 유저가 평가한 모든 아이템의 개수

   1-2. 사용자 u와 v의 피어슨 상관계수 구하기
   
   - 분자 : 사용자 u와 v의 공통된 아이템에 대한 (사용자 u의 아이템의 점수 - 사용자 u의 평균) * (사용자 v의 아이템의 점수 - 사용자 v의 평균)
   - 분모 : sqrt(사용자 u와 v의 공통된 아이템에 대한 (사용자 u의 아이템의 점수 - 사용자 u의 평균)^2) * sqrt(사용자 u와 v의 공통된 아이템에 대한 (사용자 v의 아이템의 점수 - 사용자 v의 평균)^2)
   

1-1의 평균을 구할때, 엄밀한 정의는 사용자 u와 v의 공통된 아이템에 대해서만 평균을 구하게 된다. 이는 사용자 v가 변경될 때 마다 u의 평균이 바뀐다는 뜻. 그렇지만 일반적으로는 u를 한번만 계산할 수 있도록 전체 아이템에 대한 평균을 구한다.

무엇이 더 좋냐는 상황에 따라 다르다. 두 사용자의 공통 아이템 개수가 적을 수록 일반적인 정의의 평균을 사용하고 개수가 많을 수록 전통적인 정의의 평균을 사용하는 것이 좀 더 유익한 결과를 제공한다고 이야기 할 수 있다.

이렇게 타깃 유저와 다른 모든 유저들간의 상관계수를 구하게 되면 상관계수가 가장 높은 k-사용자 집합을 이용할 수 있다. 그렇지만 각각의 k-사용자의 평점들은 아이템에 따라 매우 달라서 각각의 아이템에 대해 개별적으로 평점을 지정한다.

이러한 방법의 문제점은 각각의 사용자마다 편향이 있다는 것이다. 어떤 유저는 주로 3~5점대에 평가를 하는 한편, 어떤 유저는 주로 1~3점대에 평가를 할 수 있다. 이러한 평점들은 평균을 중심으로 재배열해야 한다.

그리고 이를 가지고 평점 예측이 이루어진다. 이 때의 "^" 표기는 관찰된 값이 아닌 예측된 값을 의미한다.

평균에다가 이러한 편향을 제한 값을 더함으로써 평점을 예측한다.

사용자 기반 알고리즘의 예시

사용자 1과 사용자 3의 피어슨과 코사인 값은 각각 0.956, 0.894이다. 피어슨 상관계수가 코사인보다 좀 더 편파적이다. 또한 피어슨의 부호는 유사도와 비유사도를 알려주는 정보이다.

사용자 3과 가장 유사한 사용자는 1과 2이다. 이 때, 사용자 3이 아직 평가하지 않은 아이템 1과 6의 평점 예측값을 top-2를 이용해서 구하면 다음과 같다.

그런데 여기서 잘 보면, 사용자 1과 2는 대부분의 평가가 높다. 반면 사용자 4와 5는 대부분의 평가가 낮다. 또한 기존의 사용자 3이 평가한 아이템들의 점수보다 아이템 1과 6의 점수가 높다.

이런 때에는 편향을 고려할 수 있는데 바로 평균 중심 평점을 이용하는 것이다.

이전 추천과의 큰 차이는 기존 추천은 6번 아이템의 우선순위이다. 3번 사용자가 평가한 아이템들의 점수보다 6번 아이템의 예측 점수가 높았다면, 평균 중심 평점을 이용한 결과는 0.86의 점수로 낮은 점수를 얻었다. 이는 사용자 1과 2가 6번 아이템에 대해 다른 아이템에 비해 상대적으로 낮은 점수를 주었으므로 합리적이다.

이러한 방식의 단점은 1~7점 range의 점수 부여 방식에서 0.86은 그 범위를 벗어난 다는 점이 있다. 순위 지정 방식에서는 이러한 점이 문제가 되지 않으며 예측 값은 보통 최근접 값으로 고치게된다.

2.3.1.1 유사도 함수 변형

몇 가지 유사도 함수의 변형 형태가 있다. 그 중 한가지는 코사인 함수를 평균 중심 평점에 사용하는 것이 아닌, 평점 그 자체에 사용하는 것.

이전에 말한 바와 같이, 일반적인 정의의 평균과 전통적인 정의의 평균처럼 코사인 함수 역시 전체 아이템을 기반으로 할 수도 있다.

피어슨 상관계수를 구할 때는 이미 평균 중심을 적용하기 때문에 바이어스 조정효과가 있다. 따라서 평점 그 자체를 사용할 때는 코사인을 사용하는 것이 더 바람직하다. 이는 각 유저의 평점 편향이 있더라도 이를 관대하게 받아들인다는 뜻이다.

또한, 전통적인 정의의 유사도 함수는 사용자 u와 v의 공통 평점 개수에 영향을 받게된다. 이 때는 특정 임계점을 설정해 유사도에 가중치를 둘 수 있다. 이러한 방법을 중요도 가중이라고 한다. 사용자 a와 b가 유사도가 매우 큰 값을 가진다고 해도, 두 유저의 공통 평점이 없다면 이를 유사하다고 말하기에는 어려운 부분이 있다. 이러할 때 할인이 적용된 유사도 함수를 사용한다.

2.3.1.2 예측함수의 변형

식 2.4에 있는 예측함수에는 다양한 변형이 있다. 평균 중심 방법이 아닌 표준 편차로 나누어주는 Z-스코어 방법이 있다.

모든 아이템에 대해 사용자가 평가한 집단(=모집단)이 아니라 일부 아이템에 대해 평가한 집단(=표본집단)이어서 분모를 1로 빼주는 것 같다.

이럴 경우 예측 평점은 다음과 같이 구할 수 있다.

이 경우 가중 평균이 꼭 표준 편차와 곱해져야 한다. 표준화 과정에서 표준편차로 나누어주었기 때문에 다시 곱해주어야 한다는 것이 저자의 말.

평균중심과 Z-스코어 중심은 뭐가 더 좋다고 말하기는 어렵다. 다만, Z-스코어는 예측 평점이 실제 평점 범위의 밖에 있을수도 있다는 문제점이 있다.

두 번째 문제는 타켓 유저 u에 대해서 많은 유사한 유저들이 서로의 가중치(=유사도)로 평점과 곱해져 반영되고 있다는 것이다. (2.4 참고) 유사도 함수 자체는 피어슨 상관계수 식을 통해 구해지지만, 이 유사도 함수를 지수화하면 어떻게 될까?

두루두루 유사한 유저들과의 가중합 점수에서 이제는 좀 더 엄밀한 기준으로(더 유사하면 더 많은 가중치, 조금 유사하면 더 조금의 가중치) 가중합이 구해지게 될 것이다.

이웃 기반 협업 필터링은 가까운 이웃을 분류 방법론, 회귀 방법론의 일반화이다. 예측값은 연속값이므로 이웃 분류 방법론보다는 이웃 회귀 모델링에 더 가깝다. 반면, 평점이 '매우 좋음', '좋음', '보통', '나쁨', '아주 나쁨' 등의 범주형 값이라면 분류의 방법론으로도 볼 수 있다. 범주형 평점은 평점의 종류가 적어도 효과적이며 평점 값들 사이의 정확한 거리를 구하기 힘든 경우에도 유용하다.

2.3.1.3. 피어 그룹 필터링의 변형

타깃 사용자의 피어 그룹을 구하는 방법은 다양하다. 가장 간단한 방법은 상위-k 유사 사용자 그룹을 이용하는 것. 그러나 이러한 방법은 (애초에 유사한 사용자가 별로 없을 수도 있으므로) 약한 상관관계를 갖거나 음의 상관관계가 있는 사용자들까지 포함될 수 있다. 그리고 음의 상관관계가 있는 평점은 잠재적 예측 가치가 크지 않다. 그래서 특히 음의 상관관계의 경우에는 필터링되는 경우가 있다.

2.4.1.4. 롱테일의 영향

실제 컨텍스트에서 평점 분포는 롱테일 분포를 따른다. 어떤 영화는 매우 유명해서 반복적으로 평점을 받았을 수도 있는데 이러한 컨텐츠는 사용자 간의 차별성이 적기 때문에(사용자의 흥미가 아닌 단순히 유명해서 평점을 받은 것이므로) 추천 품질을 악화시킬 수 있다. 이러한 점은 검색 시스템에서 비정보적인 단어('a', 'an', 'the' 등)에 의한 검색 품질 저하와 유사하다. 해결책은 IDF의 개념을 활용하는 것이다. 만일 아이템 j에 대한 평점 개수가 $m_j$라고 하고, m은 총 사용자 수라면 아이템 j에 대한 가중치 $w_j$는 다음과 같다.

이러한 가중치는 유사도 계산 과정과 추천 과정에서 모두 적용된다. 피어슨 상관계수에 적용된 예는 다음과 같다.

아이템 가중치(=항목 가중치)는 다른 협업 필터링 방법론에서도 적용할 수 있다.

2.3.2 아이템 기반 이웃 모델

아이템 기반 모델은 당연히 아이템간의 유사도가 계산되어야 한다. 아이템 i와 j의 조정된 코사인 유사도는 다음과 같다.

코사인 유사도가 평균 중심으로 조정되었기 때문에 조정된 코사인 유사도, AdjustedCosine 이라고 한다. 이럴 거면 피어슨 상관관계를 사용하여도 되겠지만, 조정된 코사인이 일반적으로 더 우수하다고 한다.

사용자 u의 타겟 아이템 t의 평점이 예측되어야 할 때, 아이템 t와 비슷한 상위-k 아이템들을 $Q_{t}(u)$라고 하자. 이 평점들의 가중 평균 값이 예측값이다. 이 예측값은 이웃 아이템의 평점 * 조정된 코사인 유사도이다.

아이템 기반 알고리즘의 예시

표 2.1 참고

사용자 3의 아이템 1과 6의 평점이 비어있다. 아이템 1은 아이템 2와 3과 유사하고, 아이템 6은 아이템 4와 5와 비슷하다. 따라서 이들은 다음과 같이 예측된다.

이 예측을 통해 아이템 1이 아이템 6보다는 사용자 3에게 더 선호될 것이라는 것을 알 수 있다. 또한, 사용자 3의 평점이 사용되었으므로 비슷한 결(=편향)을 유지할 수 있고 아이템 6에 대한 예측 평점이 제한된 범위를 넘을 일이 없다는 장점이 있다.

2.3.3 효율적 구현 및 계산 복잡성

이전까지 이야기 했던 것들은 특정 사용자-아이템 조합에 대한 평점 예측만 보여줄 뿐 실제 순위 프로세스는 설명하지 않음. 관련있는 모든 사용자-아이템 쌍에 대해 가능한 평점을 모두 예측하고 이들에 대해 순위를 매기는 것이 단도직입적인 방법. 이러한 방법이 가장 기본적인 방법이며, 중간 계산 과정이 계속적으로 재사용된다는 점이 중요하다.

이웃기반 방법론은 항상 온라인/오프라인 단계로 나뉘게 된다.

오프라인

• 사용자-사용자(또는 아이템-아이템) 유사도 값
• 사용자(또는 아이템)의 피어 그룹

온라인

• 오프라인에서 구한 유사도와 피어 그룹을 활용해 예측을 수행

$n$은 한 쌍의 사용자간의 유사도를 계산하기 위한 최대 실행시간이고, $m$은 한 쌍의 아이템 간의 유사도를 계산하기 위한 최대 실행 시간이라고 하자. $n'$은 사용자의 지정된 평점의 최대 수 이며 보통 $n$보다 훨씬 작다($n' << n$). 마찬가지로, $m'$은 아이템의 지정된 평점의 최대 수이며 $m$보다 훨씬 작다.

쉽게 말해 $n$은 아이템의 개수, $m$은 사용자의 개수이며, $n'$은 한 유저가 평가할 수 있는 최대 아이템 개수, $m'$은 한 아이템을 평가할 수 있는 최대 유저 수이다.

사용자 기반 방법론

• 타깃 유저의 평가한 점수 개수(=아이템 개수) $n'$개와 타깃 유저를 제외한 모든 유저 $m-1$명과의 유사도를 구해야 하므로 $O(n' * m)$의 실행시간이 정의된다.
• 따라서, 전체 유저의 피어 그룹을 계산하기 위한 실행 시간은 $O(n' * m^2)$의 실행시간이 정의된다.
  • 전체 유저의 피어 그룹을 살펴보는 것은 $(m-1)(m-2)//2$번이 소요된다.

아이템 기반 방법론도 마찬가지의 원리로 $O(m' * n^2)$의 실행시간이 정의된다.

0이 아닌 유사도 쌍이 다양할 수록 예측에 쓰이는 사용자/아이템 이웃의 크기 k가 다양해지며, 이 때에 사용자 기반 방법론에서는 $O(m^2)$의 공간 요구 사항이, 아이템 기반 방법론에서는 $O(n^2)$의 공간 요구 사항이 요구된다. 일반적으로 아이템 수 보다 사용자의 수가 더 많으므로 사용자 기반 방법론의 요구사항이 아이템 기반 방법론의 요구사항보다 더 크다.

온라인 계산에서는 모두 사용자/아이템 기반 방법론 모두 O(k)의 시간이 필요하다.

• 오프라인에서 구한 유사도를 가지고 k개의 피어 그룹만을 탐색해서 target user A의 3번 아이템에 대한 예측값을 구하면 되기 때문

만약 타깃 사용자의 모든 아이템에 대해서 랭킹이 필요하다면 $O(k * n)$의 시간이, 타깃 아이템의 모든 사용자에 대해서 랭킹이 필요하다면 $O(k * m)$의 시간이 필요하다.

• 위 단일 예측에서 n 또는 m 만큼의 반복이 필요하므로

중요한 점은, 계산상의 복잡성은 주로 오프라인 단계에 있으며, 이웃 기반 방법론은 온라인 예측을 이용할 때 효율적인 경향이 있다. 그래서, 오프라인 단계에서 충분한 시간동안 계산을 해도 괜찮다.

2.3.4 사용자 기반 방법론과 아이템 기반 방법론의 비교

아이템의 경우 한 유저의 공통된 취향으로 여러 아이템이 평가된다. 이 평점이 추천에 활용될 때 한 아이템이 높은 점수를 받고 다른 아이템도 높은 점수를 받는다면 두 아이템은 한 유저의 취향이라는 기준하에 유사성을 증명받는다.

반면, 사용자의 경우 한 아이템의 공통된 특성이 여러 유저에게 평가된다. 이 때의 기준은 서로 다를 가능성이 큰 유저의 취향들이므로 두 유저는 비슷하지만 다를 수 있기에 유사성을 증명받기가 비교적 어렵다.

아이템 기반 방법론

• 높은 정확도를 보임
• 쉴링 공격에 더 강함
• 추천에 대한 구체적인 근거 제시 가능
• 아이템이 다양하지 않을 경우 추천이 어려움
  • 유저가 a 아이템을 싫어하는데, 모두 비슷하면 마땅히 추천할게 없기 때문
• 추천에 있어 참신함, 다양성, 우연성이 없어 추천 항목에 대해 지루할 수 있음
• 평점이 변화해도 추천이 안정적.
  • 아이템의 수가 적기 때문에 한 아이템에 대한 평점 수가 한 유저의 평점 수보다는 많을 것이므로

사용자 기반 방법론

• 추천을 할 때 이웃을 이용해 추천의 근거를 제시할 수 있지만 프라이버시 문제로 실제로는 활용할 수 없음
• 추천에 있어 다양한 결과를 제공 가능
• 몇 개의 평점만 추가되더라도 유사도 값이 크게 바뀜
• 이웃 아이템의 계산은 가끔 이루어져도 되는데 사용자의 경우 신규 사용자가 추가됨에 따라 더 자주 계산되어야 하며, 추천 모델은 점진적 유지 관리가 점점 어려워지는 문제점이 있음

2.3.5 이웃 기반 방법론의 장점과 단점

장점

• 단순함과 직관적인 성격 => 적용하기 쉽고 문제 파악도 쉬움
• 아이템 기반 방법론은 왜 특정 아이템이 추천되었는지 알기 쉬움

단점

• 대규모 환경에서 오프라인 단계가 비효율 적. 아이템이 수천만개(m) 있으면 적어도 $O(m^2)$시간과 공간이 필요. (그치만 온라인 단계는 효율적임)
• sparse matrix로 인해 추천이 제한됨. 터미너이터를 아무도 평가하지 않았으면 견고한 유사도 값 계산은 어려움

2.3.6 사용자 기반과 아이템 기반 방법론의 통합된 관점

사용자 기반은 평점 행렬의 column간의 유사도를, 아이템 기반은 평점 행렬의 row간의 유사도를 무시함. 두 가지 방법을 통합하면 행과 열간의 유사도를 무시하지 않을 수 있고 행과 열간의 유사 정보를 결합할 수 있음

row가 평균 중심으로 설정될 때 사용자 기반과 아이템 기반 방법론이 유사해짐. (해당 사용자의 편향을 무시하겠다는 것)

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

이웃 기반 방법론의 주요 문제점은 오프라인 단계에서의 복잡성

• 사용자 기반 방법론의 실행 시간은 $O(m^2 \cdot n')$
• 사용자의 수 $m = 10^8$, $n' = 100$ 일 경우, 시간 복잡도는 $O(10^{18})$

클러스터링은 오프라인단계에서 가장 근접한 이웃을 찾는 단계를 클러스터링 단계로 대체하는 것!

• 모든 이웃과 비교하는 것이 아니라, 사전에 만들어진 모든 클러스터와 비교하는 방법으로 시간 복잡도를 줄이자!
• 물론, 모든 이웃과 비교하지 않고 각 클러스터의 중심과 먼저 비교하므로 낮은 품질을 가져 정확성이 다소 떨어진다.
• 또한, 클러스터링 세밀도는 정확성과 효율성간의 트레이드오프를 조절하게됨.
  * 클러스터가 세분화되면 효율성은 개선되지만 정확도는 떨어짐
• 그런데, 많은 경우에서 정확도를 조금 떨어뜨리면 효율성이 매우 증가하게된다. 그래서 이러한 방법이 평점 행렬이 매우 큰 경우에서 실용적인 대안으로 작용한다.

k개의 서로 다른 클러스터를 대표하는, k개의 중심 포인트를 이용한다.

• 각 중심은 유사도 혹은 거리 함수를 이용한다
• 보통은 중간이 되는 대표가 클러스터의 평균이면 좋다
• 클러스터의 새로운 원소가 추가되면 새롭게 집합의 중심을 재설정한다.

한 가지 문제점은, 평점 행렬이 불완전하다는 것.

• 이 경우 중점을 완전하게 지정하기는 어렵다.
• 이 때는, 관측된 값들에 대해서만 중심점을 얻고 이러한 중심점들의 중점을 계산한다.
  * 계산되는 과정에서는 적용된 하위차원의 수로 나누어주어야 한다.
  • 서로 다른 개수의 차원이 사용된다는 사실을 조정하기 위해서이다.
• 이러한 맥락에서 맨해튼 거리가 유클리드 거리보다 더 나은 조정을 보이고, 정규화 값은 각 관측치의 평균 거리로써 더욱 쉽게 해석될 수 있다.

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

두 쌍의 유사도가 계산되기 어려운 이유는, matrix가 sparse하기 때문이고 클러스터링에서도 이미 채워진 값들의 차원에 대해서만 중심 거리를 더하고 차원의 개수로 나누어 주는 모습을 보였다. 이럴 때, 차원 축소를 통해서 sparse하더라도 그 거리를 계산할 수 있으며 피어 그룹을 결정하는데 효율적이도록 할 수 있다.

잠재 요인 모델이 추천시스템에 쓰이는 두 가지 방법은 다음과 같다

1. 차원 축소는 희소성 문제를 완화할 수 있다. 어떤 차원을 축소하냐에 따라 사용자 기반 또는 아이템 기반 알고리즘에 사용된다.
2. 평점 행렬의 전체를 한 번에 재구성하는데 사용할 수 있다.

두 번째 방법론은 이웃 기반 방법론을 따르지는 않고 3장 모델기반에서 다루어진다.

사용자 기반 방법론으로 예를 들어보자.

• 기존 $m \times n$ 평점 행렬을 가지고 아이템 차원 n을 d로 줄인 $m \times d$ 행렬로 저차원 변환시킨다.
• 이 때는 sparse matrix가 완전히 채워지는 꼴로 변환되었다고 가정한다.
• 따라서 유사도 계산이 가능하고 차원이 축소되어서 더 효율적이게 된다.

저차원 표현법은 대표적으로 다음의 두 가지 방법이 이용되었다.

1. SVD

• 결측치를 해당 열의 평균 또는 해당 행의 평균으로 채운다. 이러한 행렬을 $R_f$ 라고 하자.
• 그런 다음 아이템 쌍끼리의 $n \times n$ 유사도 행렬인 S = $R_f^T R_f$ 를 계산한다. 이 행렬은 반정부호(원소가 0이거나 양수임)이다.

2. PCA

• SVD와 전체적인 결과는 매우 유사

2.5.1 바이어스 문제 처리