📌 개요

이웃 기반 협업 필터링

• 메모리 기반 알고리듬으로도 알려져 있다.

비슷한 이용자들이 평점을 주는 방식에 비슷한 패턴을 보이고, 비슷한 아이템에는 유사한 평점을 주는 사실을 기반으로 한다.

이웃 기반 협업 필터링 알고리듬 유형

1. 사용자 기반 협업 필터링 : 이웃 사용자 평점을 활용해 예측한다.
2. 아이템 기반 협업 필터링 : 사용자가 평가한 평점 중 가장 비슷한 아이템에 대한 평점을 이용하여 예측한다.

이웃 기반 협업 필터링 알고리듬 계산 방법

1. 유저-아이템 조합의 평점 값 예측
2. 상위-k 아이템 혹은 상위-k 사용자 결정

📌 평점 행렬의 주요 특징

평점 행렬

R이라고 표현하며, m 명의 사용자와 n 개의 아이템을 가지고 있는 m x n 행렬이다.

• 행렬의 지정된 엔트리는 학습 데이터라 하며,
  행렬의 지정되지 않은 엔트리는 테스트 데이터라 한다.
  따라서 추천 문제는 분류와 회귀 문제의 일반화로 볼 수 있다.

평점 방법

1. 연속 평점 : 평점은 역속형이며 아이템에 대한 좋음과 싦음을 나타낸다.
2. 인터벌 기반 평점 : 인터벌 기반 평점은 5점이나 7점 스케일을 주로 쓴다.
3. 서수 평점 : 순서형의 범주형 값을 쓴다.
4. 강제 선택 방법 : 서수 평점 중 "Neutral" 옵션을 제공하지 않는 경우이다.
5. 이진 평점 : 긍정 혹은 부정의 응답인 두 개의 옵션만이 존재한다.
6. 단항 평점 : 사용자에게 아이템에 대해 긍정 선호도를 지정할 수 있게 하지만 부정 선호도를 지정하는 구조는 없다.

평점 빈도표의 롱테일

• 아이템에 대한 평점 분포는 롱테일 형태로 실제 환경의 속성을 반영한다.
  이 속성에 따르면 아이템 중 극히 일부만이 자주 평가되며,
  대부분의 아이템은 거의 평가되지 않는다.
  

• 평점 빈도표의 롱테일의 영향

1. 많은 경우 잦은 빈도를 보이는 아이템은 판매자에게는 이익이 거의 없는 치열한 아이템인 반면 낮은 빈도를 보이는 아이템은 이윤이 더 크게 남는다.
2. 롱테일에서의 관찰된 평점은 매우 드문 경우이기 때문에 롱테일에서의 견고한 평점 예측은 일반적으로 더 어렵다.
3. 이웃한 아이템이 종종 자주 평가된 아이템을 기반으로 정의되지만, 자주 등장하는 상품과 적게 등장하는 상품은 평점 패턴에 있어서 본질적으로 다른 차이를 갖고 있기 때문에 위의 방식으로 상품을 정의 할 경우 잘못된 결과를 낳을 수 있다.

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

📖 사용자 기반 이웃 모델

1. 예측 단계

1. 이미 명시된 평점을 이용해 각 사용자 마다 평점의 평균 값을 계산한다.
   
2. 각 사용자에 대한 계산된 평점의 평균 값을 해당 사용자의 모든 평점에서 빼줌으로써 행렬을 평균 중심으로 재배열한다.
   
3. 타깃 사용자와 다른 사용자가 평가한 아이템 중 겹치는 아이템을 가지고 피어슨 상관계수를 계산한다.
   
4. 계산된 피어슨 상관계수를 가중치로 활용해 이웃한 사용자의 평점과 곱한 후 처음에 계산한 타깃 사용자 평점의 평균 값을 더해 값을 예측한다.
   

평균 중심 과정

가장 큰 문제점은 서로 다른 사용자가 평점에 각기 다른 스케일을 부여할 수 있다는 점이다.
 Ex> 어떤 사용자는 모든 아이템에 대해서 높은 점수를 부여하고, 또 다른 사용자는 모든 아이템에 대해 부정적으로 평가할 수 있다.
 * 이를 해결하기 위해 피어슨 상관계수를 계산하기 전 기존 행렬을 평균 중심 행렬로 재배열한다.
 * 평균 중심 과정은 이미 평가된 평점에 대해 훨씬 좋은 상대적 예측을 가능하게 한다.
 * 유일한 약점 : 예측 값이 주어진 평점의 범위에서 벗어날 수 있다.

2. 사용자 기반 알고리듬의 예시

1. 기존 행렬
   
2. 평균 중심 행렬 : 예측 단계에서 첫 번째와 두 번째 단계를 통해 나온 결과이다.
   
3. 유사도 계산 : 예측 단계에서 세 번째 단계의 과정이다.
   
4. 예측 값 계산 : 예측 단계에서 네 번째 단계의 과정이다.
   

3. 유사도 함수 변형

• 코사인 함수를 평균 중심 평점에 쓰는 것이 아닌 평점 그 자체에 사용
  
• 중요도 가중

만일 두 명의 사용자가 공통적으로 평점을 부여한 수가 적다면, 유사도 함수는 두 사용자 쌍의 중요도를 덜 강조하기 위해 할인 요인을 적용해 낮춘다.

4. 예측함수의 변형

• Z-스코어 사용

사용자 u의 관측된 평점을 표준편차로 나눠준다.
 * 평균 중심과 Z-스코어 중 어떤 결과가 더 나은 결과물을 제공하는지에 대한 생각은 다양하다.

1. 표준 편차에 관한 식
   
2. 표준화된 평점의 계산식
   
3. 타깃 사용자 u의 아이템 j의 예측 평점의 식
   

• α의 지수 사용

피어슨 상관계수를 α의 지수로 지수화해 가중치를 증폭한다.
 * 장점 : 평균 평점의 값보다는 가장 정답에 가까운 평점을 준다.
 * 평점의 종류가 적을 때 더 효과적이다.

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

타깃 사용자에 대한 피어 그룹은 다양한 방법으로 정의되고 필터링 될 수 있다.
 * 가장 간단한 방법 : 타깃 사용자의 상위-k 유사 사용자 그룹을 이용하는 것
  * 이러한 방법은 타깃가 약하너가 음의 상관관계가 있는 사용자들까지 포함하게 될 수 있다.
    이들은 예측에 오류를 추가할 수 있기 때문에 필터링 돼 제외되는 경우가 많다.

6. 롱테일의 영향

유명한 아이템은 서로 다른 사용자들로부터 반복적으로 평점을 받았을 수 있어 사용자 간의 차별성이 적어져 추천 품질을 악화시킬 수 있다.

• 이 개념은 원칙적으로 문서 검색 적용 사례에서의 대중적이고 비정보적인 단어
  (a, an, the)에서 야기된 검색 품질 저하와 유사하다.
  따라서 이 경우 검색 문헌에 쓰이는 해결책 역문서빈도(idf)를 활용할 수 있다.
• 역문서 빈도 활용한 아이템 j 에 대해 가중치 계산
  
• 가중치를 포함한 피어슨 상관계수의 변형
  

📖 아이템 기반 이웃 모델

1. 예측 단계

1. 사용자 기반의 평점의 경우처럼 평점 행렬의 각 아이템에 대한 평균 평점이 각 평점에서 차감돼 평균 중심 행렬을 생성한다.
   

2. 두 아이템을 모두 평가한 사용자들의 평점을 통해 유사도를 계산한다
   

   • 이 유사도는 유사 정도의 값을 계산하기 전 평점이 평균 중심이기 때문에 조정된 코사인 유사도라 한다.
   • 아이템 기반 방법론의 경우 피어슨 상관 관계를 열에서 활용할 수 있지만, 조정된 코사인이 일반적으로 더 우수한 결과를 보인다.

3. 유사한 항목에 대한 사용자 자신의 평점과 조정된 코사인 유사도를 가중치로 활용해 값을 예측한다.
   

2. 아이템 기반 알고리듬의 예시

1. 기존 행렬
   
2. 평균 중심 행렬 : 예측 단계에서 첫 번째 단계에 해당한다.
   
3. 유사도 계산 : 예측 단계에서 두 번째 단계에 해당한다.
   
4. 예측 값 계산 : 예측 단계에서 세 번째 단계에 해당한다.
   

3. 효율적 구성 및 계산 복잡성

• 이웃 기반 방법론은 항상 오프라인 단계와 온라인 단계로 나눠진다.

1. 오프라인 단계 : 사용자-사용자(또는 아이템-아이템) 유사도 값과 사용자(또는 아이템)의 피어 그룹을 계산 후 사전에 저장한다.
2. 온라인 단계 : 유사도 값과 피어 그룹을 활용해 예측을 수행한다.
 * 이웃 기반 방법론의 주요한 계산상의 복잡성은 종종 수행돼야 하는 오프라인 단계에 있기 떄문에 온라인 예측을 이용할 때 효율적인 경향이 있다.

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

1. 아이템 기반 방법론은 사용자 자체 평점을 추천에 활용하기 때문에 관련성이 높은 추천을 제공한다.
2. 아이템 기반 방법론은 추천 시스템에서 쉴링 공격에 더 강한 반면, 추천 과정에서 사용자 기반 방법론이 다양해질 수 있다.
3. 아이템 기반 방법론은 추천에 구체적인 근거를 제공한다.
4. 아이템 기반 방법론은 사용자 수가 대체로 아이템의 수보다 크다는 점과 신규 사용자는 상용 시스템에서 신규 아이템보다 더 자주 추가된다는 점에서 평점의 변화에 더 안정적이다.

5. 이웃 기반 방법론의 장단점

1. 장점 : 단순함과 직관적인 성격 때문에 적응하기도 쉽고 문제를 파악하기도 쉽다.
2. 단점 : 대규모 환경에서 오프라인 단계가 때로는 비효율과 희박함에 생긴 제한된 커버리지이다.

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

• 사용자 기반 방법론은 평점 행렬의 행간의 유사도를 무시하는 반면
  아이템 기반 방법론은 열간의 유사도를 무시한다는 단점이 있다.

1. 열이 평균 중심으로 설정되면 사용자 기반과 아이템 기반 방법론이 거의 같아진다.
2. 열이 평균 중심이면 열간의 피어슨 상관계수는 코사인 계수와 동일하다.
 * 이 가정을 기반으로 사용자 기반과 아이템 기반 방법론을 통합해 평점 행렬 R의 엔트리를 예측할 수 있다.

• 예측 단계

1. 행과 열간의 코사인 계수를 이용해 평점 행렬의 타깃 엔트리와 가장 유사한 행, 열을 결정한다. 사용자 기반 방법론에서는 열을 이용하고, 아이템 기반 방법론에서는 행을 이용한다.
2. 위의 단계에서 찾은 행과 열의 평점의 가중 조합을 이용해 타깃 엔트리를 예측한다.

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

• 이웃 기반 방법론 주요 문제 : 오프라인 단계에서의 복잡성으로 사용자의 수나 아이템의 수가 굉장히 클 때 더 크게 나타난다.

클러스터링 기반 방법론의 주요 관점은 오프라인에서의 가장 근접한 이웃 단계를 클러스터링 단계로 대체하는 것이다.
 * 쌍에 대한 유사도 계산은 같은 클러스터 안에서만 작용해야 하고 따라서 이 접근 방법은 훨씬 더 효율적이다.
 * 클러스터링 세밀도는 정확성과 효율성 간의 트레이드 오프를 조절한다.

1. K-Means 방법론

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

• 단계

1. 데이터 공간 범위 내에서 랜덤하게 선택된 대표의 집합으로 시작한다.
2. 대표를 이용해 클러스터 파티션을 반복적으로 계산하고 결과 클러스터를 중심으로 다시 대표를 계산한다.
3. 이 두 단계의 반복 작업은 점차 수렴하게 된다.
 * 사용자 기반 협업 필터링을 위해 열을 클러스터링 한다.
 * 아이템 기반 협업 필터링을 위해 행을 클러스터링 한다.

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

• 차원 축소 방법론은 이웃 기반 방법론의 품질과 효율성을 높이는 데 쓰일 수 있다.
• 차원 축소는 저차원이 가능하도록 하며 이러한 경우는 잠재 요인 모델이라고도 한다.
• 축소된 형태는 이웃 기반 모델의 희소성 문제를 완화할 수 있다.

1. 잠재 요인 모델이 추천 시스템에 쓰이는 두 가지 방법

1. 데이터의 축소된 형태는 잠재 요인의 열과 행 형태로 만들 수 있다.
2. 평점 행렬의 전체를 한 번에 재구성하는 데 쓰인다.

2. 저차원 표현법

1. SVD 방법론
2. PCA 방법론
 * 전체적인 결과는 매우 유사하다.

3. 바이어스 문제

• 차원 축소 전 누락된 엔트리는 행렬 내 열 또는 행의 평균과 동일한 값으로 예측되며 이는 상당한 바이어스를 일으킬 가능성이 높다.
  <예시>
  
  • <글래디에이터>와 <네로>의 평점 간의 상관관계는 평점이 지정된 네 가지 경우에서 매우 유사하다.
  • <네로>의 평균 평점 4가 지정되지 않은 평점을 대체한다면 <글래디에이터>와 <네로> 사이의 예상 공분산은 크게 감소한다.
    

4. 두 가지 해결 방법

1. 최대 우도 추정법

각 항목 쌍간의 공분산의 최대 우도 추정치는 지정된 항목 간의 공분산으로 추정된다.
 Ex> 한 쌍의 항목 간에 공통된 사용자가 없는 경우 공분산은 0으로 추정된다.
 * 다만 행렬이 희박하면 공분산 추정치가 통계적으로 신뢰할 수 없다.

• 이 방법을 사용하면 다음 공분산 행렬이 추정된다.
  

2. 불완전한 데이터의 직접 행렬 인수 분해

Truncated SVD를 사용해 행렬을 대략적으로 인수분해 할 수 있다.
 * 다음 식을 이용해 평점 행렬 R을 대략적으로 인수분해 할 수 있다면 축소된 기저 뿐만이 아닌 축소된 기저에 해당하는 평점도 알 수 있다.

• 주요 문제점 : 평점 행렬이 완전히 지정되지 않는다.
• 해결 방법 : 이 식을 평점 행렬의 관찰된 항목에 대해서만 인수분해의 제곱 오차 최적화를 진행해 최적화 문제로 재구성할 수 있다.

📖 이웃 방법론의 회귀 모델링 관점

• 예측 평점은 동일한 아이템의 다른 평점의 가중 선형 조합이다.
  
• 선형 회귀에서 평점은 다른 평점의 가중 조합으로 예측되며 가중치는 최적화 모델을 사용해 결정되는 반면 이웃 기반 접근 방식에서는 선형 함수의 계수가 최적화 모델을 사용하는 대신 사용자-사용자 유사도와 추론 방식으로 선택된다.
• 사용자 기반 모델은 동일한 열에서 평점의 선형 조합으로 예측된 평점을 표현하는 반면 아이템 기반 모델은 동일한 행의 선형 평점 조합으로 예측된 평점을 표현한다.

1. 사용자 기반 최근접 이웃 회귀

• 항목 j에 대한 대상 사용자 u의 예측 평점을 모델링 하기 위해 알 수 없는 매개변수와 유사도 계수를 대체할 수 있다.
  
• 전체 오차를 최소화하기 위해 매개변수의 알지 못하는 값에 대해 최소 제곱 최적화 문제를 설정할 수 있다.
  
• 위의 최적화 문제는 대상 사용자 u에 대해 별도로 공식화 되있기 때문에 서로 다른 타깃 사용자에 대한 통합 최적화 문제로 만들어야 한다.
  

희소성 및 바이어스 문제

회귀 접근 방식의 문제 : 회귀 계수는 사용자 u와 함께 특정 아이템 j를 평가한 피어 사용자 수에 크게 의존하게 된다.
 Ex> 대상 사용자 u가 <글래디에이터>를 평가 했을 때 대상 사용자 u의 k 최근접 이웃 중 한 명의 사용자만 영화 <글래디에이터>를 평가했다면 회귀 계수는 한 명의 사용자에 큰 영향을 받게 된다.

• 회귀 계수가 대상 사용자의 모든 피어를 기반으로 하며 불완전한 정보를 분수로 보간해야 한다는 것이다.
  
• 상수 상쇄 역할의 행의 평균을 최적화 프로세스에서 학습돼 바이어스 변수로 대체하는 것이다.
  

2. 아이템 기반 최근접 이웃 회귀

아이템 기반 접근 방식은 회귀가 사용자-사용자 상관관계가 아닌 아이템-아이템 상관관계를 학습하고 활용한다는 점을 제외하면 사용자 기반 접근 방식과 유사하다.

• 대상 아이템 t에 대한 사용자 u의 평점 예측을 모델링하기 위해 알 수 없는 매개변수를 유사도 계수로 대체할 수 있다.
  
• 행렬에서 공지된 평점을 사용해 전체 오차를 최소화하기 위해 매개변수의 알 수 없는 값에 대해 최소 제곱 최적화 문제를 설정할 수 있다.
  
• 위의 최적화 문제는 대상 아이템 t에 대해 별도로 공식화 되있기 때문에 서로 다른 대상 아이템에 대한 통합 최적화 문제로 만들어야 한다.
  
• 사용자-사용자 모델은 아이템-아이템 모델보다 약간 더 나은 성능을 보이는 것으로 알려져 있다.
• 그러나 아이템 기반 모델은 사용자 수보다 아이템 수가 훨씬 적은 설정에서 더 계산적이고 공간 효율적이다.

3. 사용자 기반 및 아이템 기반 방법 결합

• 사용자 및 아이템 기반 모델을 통합 회귀 프레임워크에 결합하는 것은 자연스러운 일이다.
• 사용자 기반 및 아이템 기반 모델의 융합이 일반적으로 개별 모델보다 더 잘 수행된다는 것이 보고됐다.
  

4. 유사도 가중치를 이용하는 조인트 보간법 (Joint Interpolation)

사용자 기반 모델을 사용해 대상 사용자 u의 각 평점을 예측할 때 동일한 항목의 관찰된 값과 비교하는 대신 해당 사용자의 다른 항목의 관찰된 평점과 비교한다.

• 동일한 대상 사용자 u에 의해 유사한 아이템 s에 주어진 관찰된 평점에서 멀리 떨어져 있는 아이템 j의 예측 평점이면 불이익을 받는 객관적인 함수를 설정한다.
  
• 접근 방식에서 사용자 및 항목 유사도가 모두 사용되지만 다른 방식으로 사용된다.

1. 아이템-아이템 유사도 : 예측된 평점이 유사한 항목의 관찰된 평점과 더 유사하도록 강제하기 위해 객관적인 함수에서 항의 곱셈 인자로 사용된다.
2. 사용자-사용자 유사도 : 표적 사용자 u의 관련 피어 그룹으로 회귀 계수를 제한함으로써 평점을 예측하는 데 사용된다.

5. 희소 선형 모델 (SLIM)

정규화 방법을 사용해 회귀 계수의 희소성을 장려한다.
 * 음수가 없는 평점에서 작동하도록 설계됐다.
 * 긍정적인 기본 설정만 표현하는 암시적 피드백 행렬에 가장 적합하다.

• 음수가 아닌 평점 값으로 작동하기 때문에 평점 행렬이 가중 중심이라고 가정하지 않는다.
• 암시적 피드백 설정에서 흔히 볼 수 있듯이 누락된 값은 최적화 공식에서 학습을 위해 0으로 처리된다.
• 회귀 계수를 대상 아이템 t의 이웃으로만 제한하지 않는다.
  
• 아이템-아이템 회귀 대각선 요소의 값이 0으로 제한된다고 가정하면 다른 사용자 및 대상 아이템에 대해 위의 식의 인스턴스화를 쌓아 다음 행렬 기반 예측함수를 만들 수 있다.
• 
  • 주요 목표는 일부 정규화 항과 함께 프로베니우스 노름을 최소화하는 것이다.
• 대상 아이템 t에 대한 객관적인 함수다.
  
  • 마지막 두 용어는 L1 및 L2 정규화를 결합한 일래스틱넷 정규화에 해당하다.
• 선형 회귀 모델과 SLIM 모델의 주요 차이점

1. 선형 회귀 모델은 특징 선택을 위한 추론적 접근 방식을 사용하는 데 반해, SLIM은 특징 선택을 위한 학습 접근 방식을 사용한다.
2. SLIM은 주로 명시적 평점이 아닌 암시적 피드백 데이터 세트를 위해 설계됐다.
3. 선형 회귀 모델의 회귀 계수는 양수 또는 음수 일 수 있는 반면 SLIM의 계수는 음수가 아닌 계수로 제한된다.
4. SLIM은 일반적으로 평점이 없는 데이터 세트에 사용되므로 예측 값을 사용해 평점을 예측하는 대신 항목의 순위를 지정하는 것이 합리적이다.
5. 선형 회귀 모델과 달리 SLIM은 추론 조정 계수와 함께 지정된 다양한 평점을 명시적으로 조정하지 않는다.
 * 모델은 세부 수준에서 몇 가지 차이점이 있지만 여러 가지 개념적 유사도를 공유한다.

📖 이웃 기반 방법에 대한 그래프 모델

그래프는 다양한 사용자 또는 항목 간의 관계에 관한 구조적 표현을 제공한다.

1. 사용자-아이템 그래프

사용자-아이템 그래프는 사용자를 나타내는 노드 집합과 아이템을 나타내는 노드 집합의 무방향 및 이중 분할 그래프로 정의된다.
 * 장점 : 두 사용자가 동일한 항목에 대해 많은 평가를 내리지 않아도 두 사용자 사이에 많은 짧은 경로가 존재한다면 이웃으로 간주될 수 있다는 점입니다.

• 노든 간의 간접 연결이라는 개념으로 이웃을 구성할 수 있다.
• 간접 연결의 개념은 경로 또는 걷기 기반 정의가 사용되며 이 목표를 달성하기 위해 랜덤위크 측정 값 또는 카츠 척도가 사용된다.

1. 랜덤 워크를 위한 이웃 정의

랜덤 워크 방법론은 한 노드에서 다른 노드로의 워크가 임의의 단계를 사용할 수 있기 때문에 간접 연결을 고려한다.
 * 사용자-아이템 그래프의 많은 부분이 연결돼 있는 한 이웃을 의미 있게 정의할 수 있기 때문에 희소 행렬에 효과적이다.

2. 카츠 척도를 이용한 이웃 정의

한 쌍의 노드 사이의 가중치 개수를 사용해 노드 간의 선호도를 결정한다.
 * 두 사용자가 걷기 기반 연결을 바탕으로 동일한 이웃에 속하는 경우 사용자-아이템 그래프에서 둘 사이의 링크가 형성된다.
 * 성향의 정도는 그들 사이의 걷기의 수로 측정된다.

2. 사용자-사용자 그래프

사용자-아이템 그래프에서 사용자-사용자 연결은 사용자-아이템 그래프의 짝수 번째 홉으로 정의된다.
사용자-아이템 그래프를 생성하는 대신 사용자 간의 2-홉 연결을 기반으로 사용자-사용자 그래프를 직접 그릴 수 있다.
 * 장점 : 2-홉 연결이 선을 만드는 동안 두 사용자 간의 공통 항목의 수와 유사도를 직접 고려할 수 있기 때문에 그래프의 선이 더 유익하다.

• 호팅과 예측 가능성

1. 알고리듬은 두 사용자 간의 상호 지정된 평점 개수를 정량화하기 위해 호팅이라는 개념을 사용한다.
2. 알고리듬은 예측 가능성 개념을 사용해 공통 평점 간의 유사도 수준을 정량화한다.
 * 그래프의 선은 호팅의 개념으로 정의되며, 호팅은 사용자 간의 비대칭 관계이다.
 * 호팅과 예측 가능성의 방향은 서로 반대다.

• 아래 내용이 참이라면, 사용자 u가 레벨 (F,G)에서 사용자 v를 호트했다고 할 수 있다.
  • F와 G는 알고리듬 매개변수다.
  • 호팅의 개념은 예측 가능성을 더욱 자세히 정의하는 데 사용된다.
    
• 사용자 u가 v를 호트하고, 선형 변환 함수가 다음과 같이 있는 경우 사용자 v는 사용자 u를 예측한다.
  • U는 알고리듬 매개변수다.
  • 선형 변환은 선의 시작 부분에 있는 평점을 사용해 선의 끝에 있는 부분의 평점을 예측할 수 있다.
    
• 아이템 k에 대한 사용자 u의 평점의 예측 평점은 사용자 u부터 v까지의 경로에 해당하는 r 선형 매핑의 조합으로 만들어진다.
  • 아이템 k에 대한 대상 사용자 u의 평점은 아이템 k에 대해 평가를 한 다른 모든 사용자의 가장 짧은 경로를 결정함으로써 계산된다.
    
• 예측에 사용할 수 있는 최대 경로 길이에 임계값이 부과된다.
  • 아이템 k를 평가한 사용자가 대상 노드 u의 임계값 길이 D 내에 없는 경우 알고리듬은 실패로 종료된다.
  • 매우 긴 경로 길이에 따라 선형 변환이 평점 예측에 있어 왜곡을 증가시킬 수 있기 때문에 효율성을 높이기 위해 임계 값을 부과하는 것이다.
• 이 방법론은 전이성을 사용해 평점을 예측하기 때문에 매우 희소한 행렬에서 작동할 수 있다.
  • 경쟁 방법론에 비해 더 나은 커버리지를 갖고 있다는 것이 장점이다.

3. 아이템-아이템 그래프

• 아이템-아이템 그래프를 활용해 추천을 진행할 수 있으며 이러한 그래프는 상관관계 그래프라고도 한다.

가중치 및 지시된 네트워크가 생성되며 각 노드가 아이템에 해당하고 선은 아이템 간의 관계에 해당한다.
 * 항목 j와 i가 적어도 하나의 일반 사용자에 의해 평가된 경우 방향이 지시된 선 (i,j) 및 (j,i)가 모두 네트워크에 존재한다.
 * 지향되는 네트워크는 선(i,j)d의 가중치가 반드시 선(j,i)와 동일하지 않기 때문에 비대칭이다.

알고리듬 계산

1. 아이템 i를 평가한 사용자 집합과 아이템 j를 평가한 사용자 집합의 공통 부분의 수로 각각의 선의 가중치를 초기화 한다.
 * 이 시점에서 선의 가중치는 대칭이다.
2. 선의 가중치가 정규화돼 선 가중치 합계가 1이 되게 한다.
 * 각 선의 가중치가 다른 수량으로 나눠지기 때문에 이 정규화는 비대칭 가중치이다.

• 이렇게 하면 가장자리의 가중치가 랜덤 워크 확률에 해당하는 그래프가 생성된다.
• 상관관계 그래프의 구성에 평점 값이 사용되지 않는다는 점은 주목할 만하다.