추천-2 이웃 기반 협업 필터링(Nearest Neighbor Collaborative Filtering)

2022.01.15 - [관심있는 주제/Recommendation] - 추천-1 시스템의 목표

2022.01.19 - [관심있는 주제/Recommendation] - 추천-2 이웃 기반 협업 필터링(Nearest Neighbor Collaborative Filtering)

 

 

목차

 

 

Recommeder Systems라는 책을 기반으로 작성되었습니다. 

1. 개요

이웃 기반 협업 필터링 == 메모리 기반 알고리즘

• 협업 필터링의 초기 알고리즘

가정

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

2가지 유형

1. 사용자 기반 협업 필터링

• 타깃 유저 A의 추천 제공을 위해 유사한 유저들의 평점을 이용
• 예측된 A의 평점은 “피어 그룹”의 각 아이템의 평점에 대한 가중 평균으로 산정

2. 아이템 기반 협업 필터링

• 타깃 아이템 B에 대한 추천을 만들기 위해
  1. B와 유사한 아이템 집합 S를 결정
  2. 특정 사용자 A의 아이템 B에 대한 평점을 예측하기 위해서 A에 대한 평점 집합 S의 평점이 결정되어야 함.
  3. 평점들의 가중 평균은 사용자 A의 아이템 B에 대한 평점을 예측할 때 계산됨.

2가지 유형의 주요 차이점

• 사용자 기반 협업 필터링
  • 평점은 이웃 사용자의 평점을 활용해 예측
  • 사용자들 간의 유사도(평점 행렬의 열)으로 결정
• 아이템 기반 협업 필터링
  • 평점은 사용자가 평가한 평점 중 가장 비슷한 아이템에 대한 평점을 활용해 예측
  • 아이템 간의 유사도(평점 행렬의 행)으로 결정
• 상반되기 떄문에 상호 보완적임

2가지의 계산 방식

1. 유저-아이템 조합의 평점 값 예측하기

• 사용자 u에 대한 아이템 j의 누락된 평점을 예측

2. TOP-K 아이템 혹은 TOP-K 사용자 결정하기

• 현실적인 컨텍스트
  • 현실적인 컨텍스트에서는 판매자가 유저-아이템 조합의 특정 평점 값을 찾는 것이 아님
  • 특정 사용자의 가장 관련된 TOP-K 아이템을 찾거나 특정 아이템의 가장 관련된 TOP-K 사용자를 아는 것이 더 중요
    • TOP-K 아이템을 결정하는 문제가 TOP-K 사용자를 찾는 문제보다 더 흔함.
    • 전통적인 추천 알고리즘
      • TOP-K 사용자보다 TOP-K 아이템을 찾는 과정이 언급됨.
      • TOP-K 사용자는 판매자에게는 유용한 정보
        • 누구에게 홍보할 지 정할 수 있기 때문
• 두 문제는 매우 밀접
  • 특정 사용자의 TOP-K 아이템을 결정하기 위해서는 그 사용자의 아이템에 대한 평점을 예측해야 함.
  • TOP-K 아이템은 예측된 평점을 기반으로 선택
• 효율성 개선
  • 이웃 기반 방법론은 예측에 필요한 일부 데이터를 OFFLINE으로 먼저 계산
  • 먼저 계산된 데이터는 순위를 매길 때 더 효율적으로 활용

2장 공부 목적

1. 다양한 이웃 기반 방법론 소개
   1. 클러스터링
   2. 그래프 기반 표현
2. 협업 필터링 알고리즘에서 평점 행렬이 미치는 영향과 추천에서의 효과
3. 효율성 측면의 평점 행렬의 영향도 공부
4. 이웃 기반 방법론과 회귀 모델링 테크닉의 관계
   • 회귀 방법론은 이웃 기반 방법론의 최적화 구조를 제공함.
   • 이웃기반 방법론은 LEAST SQUARE REGRSSION MODEL을 경험적 근사값으로 구할 수 있다.
   • 잠재 요인 모델과 같이 이웃 방법론과 다른 최적화 모델의 결합의 방향을 잡아준다고 함.

2. 평점 행렬의 주요 특징

• 평점 행렬은 $R$
  • 사용자 m
  • 아이템 n
  • m x n 행렬
  • $r_{uj}$ : 사용자 u의 j에 대한 평점
• 엔트리 속하면 학습 데이터 속하지 않으면 테스트 데이터
  • 지정되지 않은 엔트리는 클래스의 변수나 종속 변수
  → 추천 문제는 분류와 회귀 문제의 일반화

평정 방법

1. 연속 평점

• 연속형
• -10 ~ 10 : jester joke 추천 엔진
• 단점
  • 사용자가 실제 값의 무한한 가능성에 대한 부담
    • 굉장히 드문 방식

2. 인터빌 기간 평점

• 5점 스케일 7점 스케일
• 가정
  • 숫자 값은 명시적으로 평점 사이의 거리를 정의하고 평점값 사이의 거리는 같다.

3. 서수 평점

• 인터벌 기간 평점과 유사
  • 선수형의 범주형 값이 사용된다는 것이 차이점
• 예
  • Disagree / Neutral / Agree
• 인터벌 기간 평점과 차이점
  • 평점 쌍 간의 거리가 동일하지 않다고 가정
  • 바이어스를 고려해서 부정과 긍정을 골고루 배치
  • 중립에 대한 옵션 제거
    • 강제 선택 방법

4. 이진 평점

• 긍정 혹은 부정 2개의 응답만 존재
• 특이 케이스
  • 인터벌 기간 평점과 서수 평점의 특별 케이스

5. 단항 평점

• 긍정 선호도를 지정할 수 있게 하지만 부정 선호도를 지정하는 구조는 없음.
• 예
  • 페이스북 좋아요
• 고객 행동에서 파생
  • 아이템 구매 행동은 아이템에 대한 긍정적인 한 표로 생각
  • 아이템을 구매하지 않는다고 해서 불호를 표현한 것은 아님
• 고객이 명시적으로 피드백 제공 x
  • 고객 행동에서 단항 평점을 간접적으로 유도하는 것은 암시적 피드백이라 함.
    • 암시적으로 고객의 행동을 통해 유추됨
• 명시적으로 평가하는 것보다 온라인에서 아이템과 더 활발하게 활동할 수 있기 때문에 쉽게 얻을 수 있음.
  • 묵시적 피드백의 설정(단항 평점)은 분류 및 회귀 모델링에서 양의 미분류(positive-unlabeld) 학습 문제의 행렬 완성으로 간주할 수 있기 때문에 본질적으로 다름

아이템 분포

• 일반적으로 롱테일(long-tail) 형태
  • 아이템 중 극히 일부만이 자주 평가
    • 인기 있는 아이템
  • 평점이 크게 치우쳐있는 상태
• 추천 프로세스에 중요한 영향을 끼친다.

1. 이득 방향

• 많은 경우 잦은 빈도를 보이는 아이템은 판매자에게 이익이 거의 없는 치열한 아이템인 경향이 있음
• 낮은 빈도를 보이는 아이템은 이윤이 크게 남을 수 있음.
  • 이런 경우 판매자는 적은 빈도의 아이템을 추천하는 것이 이득
    • 아마존 사례
      • 롱테일에 위치한 아이템을 팔면서 이윤을 많이 나김

2. 추천 방향

• 롱테일에서의 관찰된 평점은 매우 드문
  • 예측이 어려움
• 많은 추천 알고리즘이 유명한 아이템을 제안하는 경우 많음
  • 다양함에 부정적 영향을 줄 수 있음.
  • 사용자를 지루하게 할 수 있음.

3. 롱테일로 인해서 모델에게 주는 부정적 영향

• 롱테일 분포는 사용자가 자주 평가한 아이템의 수가 적음을 의미
• 이웃한 아이템이 종종 자주 평가된 아이템을 기반으로 정의하므로, 이웃 기반 협업 필터링에 큰 영향을 끼침
• 자주 등장하는 상품과 적게 등장하는 상품은 평점 패턴에 본질적으로 다른 차이를 갖고 있기 때문에 많은 평점을 받은 상품이 적은 평점의 상품을 대변할 수 없음
  • 협업 기반 필터링에 해결 못하는 부분

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

• 기본 아이디어
  • 평점 행렬을 통해 추천을 진행하기 위해 사용자-사용자 유사도를 이용하거나 아이템-아이템 유사도를 이요함.
• 이웃 개념
  • 예측을 위해 유사한 사용자 혹은 유사한 상품을 군집

2가지 원칙

1. 이웃 기반 모델

• 유사한 사용자들은 같은 상품에 대해 비슷한 평점을 줌
• 두 사용자가 유사했을 때 서로 보지 못한 것들에 대해서는 비슷하게 평점을 줄 수 있다

2. 아이템 기반 모델

• 유사한 상품은 동일한 사용자에게 비슷한 방식으로 평점이 매겨진다.
• 한 사용자가 유사한 상품을 평가한 기록이 있다면, 새로운 유사한 상품도 비슷한 평점을 줄 것이다.

1. 사용자 기반 이웃 모델

사용자 기반 이웃은 평점 예측이 계산되는 타깃 유저와 유사한 사용자를 찾기 위해 정의됨.

타깃 유저 i의 이웃을 찾기 위해서는 다른 모든 사용자의 유사도가 계산됨.

따라서 사용자가 평가한 평점간의 유사도 함수가 되어야 함.

• 유사도 계산은 평점 스케일이 다를 수 있기 때문에 까다로운 작업이 될 수 있음.
• 평균 계산
• $$ u와 v에서의 u의 평균 = \frac{u와 v의 공통된 집합의 u의 평점}{전체 u의 집합의 개수} $$
• 유사도
  • 피어슨 상관계수(Pearson(u,v)
    • 전통적 정의
      • u 와 v의 값은 사용자 u와 v 모두가 평점을 매긴 아이템에 대해서만 계산됨.
    • 방법
      • 하나의 평균 사용
      • 2 사용자들의 개별적 평균 사용
    • 방법에 따라 누가 낫다고 주장하기는 어려움
• 피어 그룹 정의
  • 유사도(피어슨 계수)가 가장 높은 k 사용자 집합을 이용
    • 서로 다른 사용자가 평점에 각기 다른 스케일 부여
      • 그래서 피어 그룹의 (가중) 평균 평점을 결정하기 전에 행에 대해서 평균을 중심으로 재배열되어야 함.
        • 사용자 u의 아이템 j에 대한 평균 중심 평점 $s_{uj}은 초기 평점 r_{uj} 에서 사용자의 평균 평점을 뺴는 것$
        • $s_{uj} = r_{uj}-\mu_{u} \\ u \in {1,,,m}$
• 수식
  • 나중에 //

예시

유사도 함수 변형

• Pearson
  • 바이어스 조정 효과 있음
• RawCosine
• DiscountedSim
  • 유사도는 공통 평점 점수에 종종 영향을 받음.
  • 공통적으로 평점을 부여한 수가 적다면, 중요도를 덜 강조하기 위해서 할인 요인(discount factor)를 적용해 낮춤.
    • 중요도 가중(significant weighting)
    • 할인 요인(discount factor)
      • 두 사용자 간의 공통으로 부여한 평점 개수가 특정 임계점 $\beta$보다 작은 경우 사용
  • $DiscountedSim(u,v)=Sim(u,v) \frac{min(공통 상품 개수, \beta)}{\beta}$

예측 함수 변형

• 다양한 변형 존재
  • raw한 평점
  • 한 평점의 평균 대신 $s_{uj}$를 사용한 u의 관측된 평점에 대해서 표준편차로 나눠서 표준화한 평점
    • 가중 평균이 곱해짐
    • 수식(//)
    • 문제점
      • 예측 평점이 실제 평점 범위의 밖에 있을 수 있음.
        • 항목의 선호도 순위를 매길 때 사용됨.
      • 서로 다른 평점에 대한 가중치 계산의 어려움

피어 그룹 필터링의 변형

• 다양한 방법으로 피어 그룹 정의 가능함.
• 간단한 방법
  • 타깃 사용자의 TOP-K 유사 사용자 그룹을 이용
    • 문제점
      • 오류 추가- 약하거나 음의 상관관계 사용자도 포함할 수 있음.
• 약하거나 음의 상관관계 유저
  • 잠재적인 평점 반점의 관점에서 예측가치가 크지 않음
  • 필터링 하는 경우가 많음.

롱테일의 영향

• 실제 컨텍스트에서의 평점 분포는 롱테일 분포
  • 유명한 영화는 다른 사용자들에게 반복적으로 평점
    • 이런 평점은 사용자 간의 차별성이 적기 때문에 추천 품질을 악화시킬 수 있음.
    • 문서 검색 적용 사례에서 비정보적 단어(A ,AN, THE)에서 야기된 검색 품질 저하와 유사
  • 역문서의 개념 사용하여 가중치 적용(항목 가중치)
    • $w_j = log(\frac{m}{m_j})$
  • 아이텀 j에 대한 평점 개수 $m_j$ / m은 총 사용자
• 가중치를 사용하여 피어슨 수식 고려

2. 아이템 기반 이웃 모델

피어 그룹이 아이템으로 구성됨.

아이템 간의 유사도가 계산되어야 함.

• AdjusctedCosine 사용
  • 유사 정도의 값을 계산하기 전 평점이 평균 중심이기 때문에 조정된 코사인 유사도라고 함.
• 단계
  1. 조정된 코사인 유사도를 기반으로 아이템 t와 가장 유사한 TOP-K 아이템 결정
     • 평점들의 가중 평균 값을 예측값
  2. 유사한 항목에 대한 사용자 자신의 평점을 활용
     • 아이템 피어 그룹은 전형적으로 유사한 장르

예시

효율적 구현 및 계산 복잡성

타깃 사용자의 가장 적절한 추천 항목을 결정하는 데 사용

타깃 아이템에 대한 사용자 추천을 결정하는데 쓰임

기본 방법

• 많은 사용자-아이템 조합에 대한 예측 과정이 중간 계산 과정에서도 재사용된다.
  • 이 중간 계산을 저장하고 순위 과정에 사용하기 위해 오프라인 단계를 사용하는 것이 좋다.
• 이웃 기반 방법론 단계
  • 오프라인 단계
    • 사용자-사용자(아이템-아이템_ 유사도 값 사용자(아이템)의 피어 그룹 계산
    • 계산을 해서 사전에 저장
  • 온라인 단계
    • 오프라인에서 계산한 유사도 값과 피어 그룹을 활용해 예측 수행
• 대체로 아이템보다 사용자가 더 많으므로, 사용자 기반 방법론이 공간 요구 사항이 더 큼

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

• 아이템 기반 방법론
  • 사용자 자체 평점을 추천에 활용하기 때문에 더 관련성이 높은 추천 제공
  • 순서
    • 유사 아이템 인지
    • 유사 아이템에 대한 사용자가 지정한 평점 활용하여 타깃 평점 예측
  • 쉴링(shilling) 공격에 강함
  • 사용자 방법론보다는 다양성이 떨어짐
  • 참신성, 다양성, 우연성 면에서 떨어진다.
  • 평점 변화에 안정적
    • 사용자 기반 방법론은 몇 개의 아이템이 추가 되면, 유사도 값이 크게 바뀔 수 있음.
    • 사용자 기반은 주기적으로 바뀌기 때문에 모델 관리 어려움

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

장점

• 단숨함과 직관성으로 문제 풀기 쉬움
• 상대적으로 안정
• 점증적 근사 가능
• 온라인 단계에서는 항상 효율적

단점

• 대규모 환경에서 오프라인 단계가 때로는 비효율적
  • 사용자 기반 방법 오프라인 단계는 $O(m^2)$ 공간 필요
• 희박함에 생긴 제한된 커버리지
  • 누군가는 평가를 해줘야지 사용할 수 있음.
  • 두 사용자가 공통적으로 평가한 아이템의 숫자가 적다면 견고한 유사도 값 얻기 어려움

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

• 사용자 기반 단점
  • 평점 행렬의 행(column)간의 유사도를 무시
• 아이템 기반 단점
  • 평점 행렬의 열(row)간의 유사도를 무시
• 2개의 정보를 고려하는 방식 고려

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

• 주요문제점
  • 오프라인 단게에서의 복잡성
• 클러스터링 기반 방법론 주요 관점
  • 오프라인에서의 가장 근접한 이웃 단계를 클러스터링 단게로 대체
  • 오프라인에서의 가장 근접한 이웃을 찾는 단계는 많은 피어 그룹을 생성하며, 가능한 타깃들의 중심이 되는 것처럼 클러스터링 단계는 각각의 타깃이 중심이 될 필요도 없고 더 작은 피어 그룹을 생성한다.
  • 기존 방식보다 더 효율적
• 차이점
  • 클러스터 안에서의 TOP-K 의 가장 근접한 동료가 예측에 활용됨.
  • 정확성이 다소 떨어질 수 있음.
• 허들
  • 평점 행렬이 불완전함.
• 협업 필터링
  • 사용자 기반 협업 필터링
    • 열을 클러스터링
  • 아이템 기반 협업 필터링
    • 행을 클러스터링

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

• 장점
  • 이웃 기반 방법론의 품질과 효율성을 높이는 데 쓰일 수 있음.
  • 차원 축소는 잠재 요인에 있어 저차원이 가능하도록 함.
    • 잠재 요인 모델
  • 평점을 매긴 아이템이 매우 적다 하더라도, 저차원 잠재 벡터에서는 그 거리가 계산 가능
    • 피어 그룹을 결정하는 데 더욱 효율적
• 잠재 요인 모델이 추천 시스템에 쓰이는 2가지 방법
  1. 데이터의 축소된 형태는 잠재 요인의 행과 열 형태로 만들 수 있음.
     • 아이템 차원에서나 사용자 아이템 차원에서 줄일 수 있음.
     • 축소된 형태의 희소성 문제를 완화
     • 잠재 요인에서 어떤 차원이 축소되냐에 따라서 축소 형태는 사용자 기반 이웃 알고리즘에 쓰이거나 아이템 기반 이웃 알고리즘에 쓰임
  2. 행 공간과 열 공간의 잠재 형태가 동시에 결정
     • 잠재 형태는 이웃 기반 방법론을 쓰지 않은 채 평점 행렬의 전체를 한 번에 재고숭
     • 3장
• 예시) 사용자 기반 협업 필터링
  • 저차원에서의 유사도 계산은 모든 차원이 완전히 지정돼있기 때문에 값이 흔들리지가 않음.
  1. 첫 번째 단계는 누락된 엔트리를 채우기 위해 MXN 의 불완전한 평점 행렬 R을 증가시키기
     • 누락된 엔트리는 행렬 내의 열의 평균
     • 누락된 엔트리는 행렬 내의 행의 평균
  2. 아이템 쌍 끼리의 NXN 유사도 행렬을 계산 ($S = R_f^T R^T)$
     • SVD
     • PCA

5.1 바이어스 문제 처리

• 유의할 점
  • 헁렬 $R_f$ 은 불특정 항목을 행 또는 열을 따라 평균 값으로 작성해 불완전행렬 R 에서 파생된다는 점
  • → 바이어스 문제를 야기함
• 잘못된 대체를 하게 되면, 바이어스가 발생함.
  • 대부분의 항목이 지정되지 않을 때 바이어스는 희소 행렬에서 굉장히 중요한 역할
  • 따라서 지정되지 않은 항목 대신 평균 평점을 사용해 발생하는 바이어스를 줄이기 위한 방법을 설계해야 함.
    • 최대 우도 추정
    • 불완전한 데이터 직접 행렬 인수 분해

1. 최대 우도 추정

• 공분산 행렬 추정하기 위해 EM(Expectation-Maximization) 알고리즘과 같은 확률적 기술의 사용 제안
• 특정 항목 쌍에 대한 평점을 지정한 사용자만의 정보만을 공분산 추정하는 데 사용

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

• 위의 방식으로 바이어스 어느 정도 보정할 수 있지만 평점의 희소성 수준이 높을 떄 완전히 효과적이지 않음.
  • 행렬이 희박하면 공분산 추정치가 통계적으로 신뢰할 수가 없다.
• 행렬을 인수분해 하는 방법 사용
  • SVD 사용
  • 문제점
    • 평점 행렬이 완전히 지정되지 않는다는 것

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

• 사용자 기반 아이템 기반에서의 발견
  • 이웃 사용자의 동일한 항목에 대한 평점 또는 이웃 항목의 동일한 사용자의 평점의 선형함수로 평점을 예측
• 기존 사용자 기반 이웃 방법
  • 유사한 취향을 가진 사용자에게 속하는 항목만을 사용한 후 유사도를 이용하여 가중치로 적용함.
    • 휴리스틱적이고 임의적임
    → 최적화 방법론을 적용해서 가중치를 학습하는 것이 더 좋은 방법일 수 있음.

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

1. 바이어스

문제점

• 크기가 동일한 사용자와 다양항 항목 인덱스에 대해 크게 다를 수 있음
  • 평점 행렬이 내재된 특별한 수준의 희소성 때문에 발생함
• 회귀 계수가 다른 아이템의 평점 예측에 노이즈를 추가할 수 있으므로 과적합 발생할 수 있음.

해결 방안

• 예측 함수를 변경하고, 아이템 J에 대한 회귀가 사용장 U의 아이템 J에 대한 평점의 분수만 예측한다고 가정
  • 회귀 계수가 대상 사용자의 모든 피어를 기반으로 하며 불완전한 정보를 분수로 보간하기

새로운 해결 방안에 대한 문제점

• 계산량이 많음.

아이템 공간이 빠르게 변경되는 설정에 적합하지만, 사용자는 시간이 지남에 따라 상대적으로 안정적 (뉴스 추천 시스팀)

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

아이템-아이템 상관관계를 학습하고 활용함.

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

• 유사한 아이템 뿐만 아니라 유사한 사용자의 관계를 기반으로 평점 예측

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

기존과는 다른 방법

1. 사용자 기반 모델을 사용해 대상 사용자 u의 각 평점을 예측2
2. 동일한 아이템의 관촬된 값과 비교하는 대신 해당 사용자의 다른 아이템의 관촬된 평점과 비교

주목할 점

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

5. 희소 선형 모델(SLIM)

• 정규화 방법을 사용해 회귀 계수의 희소성을 장려하기 때문에 희소 선형 모델이라고 한다고 함.
  • 음수가 아닌 평점 값일 때 작동한다.
• 특이점
  • 평점 행렬이 평균 중심이라고 가정하지 않음.
  • 평균 중심은 싫어하는 것에 대해서 음수 평점을 자동으로 갱신하기 때문에
  • 긍정적인 기본 설정만 표현하는 암시적 피드백 행렬에 가장 적합
    • 클릭 정보 데이터
    • 판매 데이터
  • 누락된 값은 0으로 표현
• 회귀를 구축하는 데 대상 아이템의 주변만 사용된다.
• 주요 목표
  • 일부 정규화 항과 함께 프로베니우스 노름(Frobenius norm)을 최소화
• 함수
  • L1,L2를 결합한 elastic-net을 사용
• 일반 선형 회귀 모델과 차이점 존재
  • SLIM은 최대한 많은 0이 아닌 계수를 사용 가능
    • 과적합을 피하기 위해 0으로 설정
  • SLIM은 명시적 평점이 아닌 암시적 피드백 데이터 세트를 위해 설계됨.
    • 평점이 양수 설정에만 나타내는 임의값인 경우 사용 가능
    • 비음수 행렬 분해
      • 암시적 피드백에 유용
      • 임의적 피드백에 유용하지 않음.
  • SLIM은 계수가 음수가 아닌 계수로 제한됨
    • 암시적 피드백에 맞춰진 알고리즘
    • 직관적이며 결과 해석 사용
    • 회귀 계수는 양수 또는 음수일 수 있다.
  • SLIM은 평점에 대한 예측 모델도 제안하지만 예측 값의 최종 사용은 예측 값의 순서대로 아이템 순위를 매김
    • 평점이 없는 데이터 세트에 사용
    • 예측 값 해석
      • 예측 값을 사용해 평점을 예측하는 대신 아이템의 순위를 지정하는 것이 합리적
      • 각 값을 평점 행렬에서 0이 아닌 평점을 0으로 대체하는 오류
      • 오차가 클수록 평점의 예측 값이 커지게 되서, 아이템은 예측 값의 순서로 정렬될 수 있음.
  • SLIM은 추론 조정 계수와 함께 지정된 다양한 평점을 명시적으로 조정되지 않음.

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

• 평점의 희소성은 이웃 기반 방법의 유사도 계산에 큰 문제 일으킴
• 구조적 전이성 또는 순위 기술을 사용해 이웃 기반 방법론에서 유사도를 정의하기 위해 여러 그래프 모델이 사용됨.
• 그래프 네트워크 도메인의 많은 알고리즘 도구를 가능하게 하는 강력한 추상화 작업임
• 그래프
  • 다양한 사용자 또는 아이템 간의 관계에 관한 구조적 표현 제공
  • 그래프는 아이템 또는 사용자 둘 다 생성할 수 있음.

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

• 지역을 정의할 때 피어슨 상관계수가 아닌 사용자-아이템 그래프에서 구조 측정값을 사용할 수 있다.
  • 가장 자리의 구조적 전이성을 사용할 수 있기 때문에 희소 평점 행렬에 더 효과적
• 사용자-아이템 그래프는 사용자를 나타내는 노드 집합과 아이템을 나타내는 노드들 사이에서 무방향 및 이중 분할 그래프로 정의됨.
  • 모서리 수는 효용 행렬에서 관찰된 아이템 수와 같음.
• 장점
  • 두 사용자 간의 짧은 경로가 많은 만큼 존재하므로, 두 사용자가 동일한 항목 중 많은 부분을 이웃으로 간주할 필요가 없다
    • 노드 간의 간접 연결이라는 개념으로 이웃을 구성할 수 있음.
    • 간접 연결의 개념
  • 경로 또는 걷기 기반 정의가 사용
• 방법
  • 랜덤 워크
  • 카츠 측도
• 링크 예측 문제와 연관됨.

2. 랜덤 워크를 이용한 이웃 정의

• 사용자 이웃 정의
  • 해당 사용자부터 시작되는 랜덤 워크에서 발생하는 사용자 집합에 의해 정의
• 예상 빈도를 어떻게 측정?
  • 랜덤 워크 방법론과 밀접한 연관
• 사용자 기반 협업 필터링 유사 사용자 k
  • 개인화된 PageRank
  • SimRank
• 이 접근 방식이 희소 행렬에 효과적인 이유
  • 2명의 사용자가 의미 있게 정의되기 위해서는 공통 항목 집합에 직접 연결되야 한다.
    • 희소 사용자-아이템 그래프에서는 많은 노드에 대해 직접 연결이 존재하지 않음.
  • 랜덤 워크 방법론을 사용하여 한 노드에서 다른 노드로의 워크가 임의의 단계를 사용할 수 있기 때문에 간접 연결을 고려.

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

• 사용자 이웃 저으이
  • 노드 쌍 간의 가중치 개수를 사용해 노드간의 선호도를 결정
    • 한 쌍의 노드 사이의 보행 가중치 개수를 카츠 척도라고 한다.
  • 가중치 수는 종종 링크 예측 측정 값으로 사용됨.
    • 두 사용자가 걷기 기반 연결을 바탕으로 동일한 이웃에 속하는 경우 둘 사이의 링크가 형성되는 점을 알 수 있다.
• 카츠 척도 정의
  • 노드 사이의 길이
  • 수식 (//)

사용자-사용자 그래프

• 사용자 간의 2-홉 연결을 기반으로 사용자-사용자 그래프를 직접 만들 수 있음.
• 사용자-아이템 대비 사용자-사용자 그래프 장점
  • 그래프의 가장 자리가 더 유익
• 2-홉 연결이 가장자리를 만드는 동안 두 사용자간의 공통 아이템의 수와 유사도를 직접 고려할 수 있음.
• 두 사용자 간의 상호 지정된 평점 개수를 정량화하기 위해 호팅이라는 개념 사용
• 예측 가능성 개념을 사용해 공통 평점 간의 유사도 수준을 정량화

1. 호팅

2. 예측 가능성

공부가 필요(//)

아이템-아이템 그래프

• 아이템-아이템 그래프 = 상관관계 그래프
  • $G=(N,A)$
  • N의 각 노드가 아이템
  • A의 각 가장자리는 아이템 간의 관계에 해당
• ItemRank

 

2022.01.15 - [관심있는 주제/Recommendation] - 추천-1 시스템의 목표

2022.01.19 - [관심있는 주제/Recommendation] - 추천-2 이웃 기반 협업 필터링(Nearest Neighbor Collaborative Filtering)