카카오 뮤직 추천시스템 깃허브 구경하기 _ programming assignment (3) mini_reco

https://github.com/kakao/recoteam/tree/master/programming_assignments/mini_reco

공개 리포지토리라서 보다가 이 문제가 흥미로워보여서 공부해봤다.

1. User-based Collaborative Filtering 개요

User-based Collaborative Filtering은 사용자 간의 유사도를 기반으로 추천을 수행하는 방식

1. 유사도 계산 : 사용자들 간의 유사도를 계산
2. 이웃 선정 : 가장 유사한 N명의 사용자를 선택
3. 평점 예측 : 선택된 이웃들의 평점을 기반으로 새로운 아이템에 대한 평점 예측
4. 추천 : 예측된 평점이 높은 순서대로 아이템 추천

핵심 수식 설명

1. 기본 평점 예측 공식

$r_{u,i} = \bar{r_u} + k\sum_{u' \in U}simil(u,u')(r_{u',i} - \bar{r_{u'}})$

• $r_{u,i}$: 사용자 u의 아이템 i에 대한 예측 평점
• $\bar{r_u}$: 사용자 u의 평균 평점
• $k$: 정규화 factor
• $U$: 유사한 이웃 사용자들의 집합
• $simil(u,u')$: 사용자 u와 u' 사이의 유사도

2. Cosine Similarity (코사인 유사도)

코사인 유사도는 두 사용자의 평점 패턴이 얼마나 유사한지를 측정하는 방법

수식

$simil(x,y) = cos(\vec{x},\vec{y}) = \frac{\vec{x} \cdot \vec{y}}{||\vec{x}|| \times ||\vec{y}||} = \frac{\sum_{i \in I_{xy}}r_{x,i}r_{y,i}}{\sqrt{\sum_{i \in I_x}r_{x,i}^2}\sqrt{\sum_{i \in I_y}r_{y,i}^2}}$

구성 요소 설명

기호	의미
$I_{xy}$	사용자 x와 y가 모두 평가한 아이템들의 집합
$r_{x,i}$	사용자 x가 아이템 i에 준 평점
$r_{y,i}$	사용자 y가 아이템 i에 준 평점
$I_x$	사용자 x가 평가한 모든 아이템 집합
$I_y$	사용자 y가 평가한 모든 아이템 집합

특징

1. 결과값의 범위 : -1 ~ 1
2. 1에 가까울수록 두 사용자의 평점 패턴이 유사
3. 0은 관계가 없음을 의미
4. -1에 가까울수록 반대되는 패턴

이제 코드야!!!!
코드 들어가기 전에 궁금할까봐... 미리 정리한...

3. 데이터 입력 및 기본 구조 설정

import sys

# 데이터 입력
num_sim_user_top_N = int(sys.stdin.readline())  # 유사도 top N 사용자
num_item_rec_top_M = int(sys.stdin.readline())  # 예측 평점 top M 아이템
num_users = int(sys.stdin.readline())  # 전체 사용자 수
num_items = int(sys.stdin.readline())  # 전체 아이템 수
num_rows = int(sys.stdin.readline())   # 입력 row 개수

데이터 저장 구조

rating_data = {}  # {사용자 ID: {아이템 ID: 평점}}
items = set()     # 모든 아이템을 모아놓은 set

# 데이터 입력 받기
for _ in range(num_rows):
    user, item, rating = sys.stdin.readline().split(' ')
    user = int(user)
    item = int(item)
    rating = float(rating)
    if user not in rating_data:
        rating_data[user] = {}
    rating_data[user][item] = rating
    items.add(item)

데이터 구조 설명

1. rating_data 구조
2. { user1: { item1: rating1, item2: rating2, ... }, user2: { item1: rating1, item3: rating3, ... }, ... }
3. 사용자 평균 평점 계산
4. user_average_rating = dict() # {사용자 ID: 평균 평점} for user, item_ratings in rating_data.items(): user_average_rating[user] = sum(item_ratings.values()) / len(item_ratings)

주요 포인트

1. 중첩 딕셔너리 구조를 사용하여 빠른 접근이 가능
2. 아이템 집합을 별도로 관리하여 전체 아이템 목록 유지
3. 사용자별 평균 평점을 미리 계산하여 저장

4. 유사도 계산 및 이웃 선정

num_reco_users = int(sys.stdin.readline())  # 추천할 사용자 수
for _ in range(num_reco_users):
    query_user = int(sys.stdin.readline())  # 추천할 사용자 ID
    user_sim = dict()  # {사용자 ID: 유사도}

    # 코사인 유사도 계산
    for user in rating_data.keys() - {query_user}:
        user_ratings = rating_data[user]
        query_user_ratings = rating_data[query_user]

        # 공통 아이템 찾기
        intersection_items = rating_data[query_user].keys() & rating_data[user].keys()

        # 분자 계산: 공통 아이템에 대한 평점의 곱의 합
        numerator = sum(user_ratings[item] * query_user_ratings[item] 
                       for item in intersection_items)

        # 분모 계산
        denominator = sum(rating ** 2 for rating in user_ratings.values()) ** 0.5
        denominator *= sum(rating ** 2 for rating in query_user_ratings.values()) ** 0.5

        # 유사도 저장
        user_sim[user] = numerator / denominator if denominator > 0.0 else 0.0

코드 분석

1. 유사도 계산 과정:

   단계	코드	수식
   공통 아이템 찾기	intersection_items = rating_data[query_user].keys() & rating_data[user].keys()	$I_{xy}$
   분자 계산	numerator = sum(user_ratings[item] * query_user_ratings[item])	$\sum_{i \in I_{xy}}r_{x,i}r_{y,i}$
   분모 계산	denominator = sum(rating ** 2 for rating in user_ratings.values()) ** 0.5	$\sqrt{\sum_{i \in I_x}r_{x,i}^2}$

2. 이웃 선정:
3. # 유사도 기준으로 정렬 nearest = sorted(user_sim.items(), key=lambda x: x[1], reverse=True)

5. 평점 예측 및 추천 리스트 생성

predicted_rating = list()  # [(아이템 ID, 예측 평점), ...] 형태로 저장

# 아직 평가하지 않은 모든 아이템에 대해 예측
for item in items - rating_data[query_user].keys():
    sum_k = 0  # normalizing factor k 계산용
    sum_u = 0  # 유사도 가중치 합계

    # 유사도 상위 N명의 사용자들에 대해 계산
    for user, similarity in nearest[:num_sim_user_top_N]:
        # 해당 사용자가 아이템을 평가했을 경우만 계산
        if item not in rating_data[user]:
            continue

        # 예측식의 합계 부분 계산
        sum_u += similarity * (rating_data[user][item] - user_average_rating[user])
        sum_k += abs(similarity)

    # 최종 예측 평점 계산
    r_ui = (user_average_rating[query_user] + 
            (1 / sum_k) * sum_u if sum_k > 0.0 else 0.0)

    predicted_rating.append((item, r_ui))

수식과 코드 매핑

$r_{u,i} = \bar{r_u} + k\sum_{u' \in U}simil(u,u')(r_{u',i} - \bar{r_{u'}})$

수식 요소	코드 구현	설명
$\bar{r_u}$	user_average_rating[query_user]	추천 대상 사용자의 평균 평점
$k$	1 / sum_k	정규화 계수
$simil(u,u')$	similarity	사용자 간 유사도
$r_{u',i}$	rating_data[user][item]	이웃 사용자의 아이템 평점
$\bar{r_{u'}}$	user_average_rating[user]	이웃 사용자의 평균 평점

최종 추천 리스트 생성

# 예측 평점 기준으로 정렬
predicted_rating.sort(key=lambda x: x[1], reverse=True)

# Top M 아이템의 ID만 추출하여 출력
print(' '.join(str(item_rating[0]) 
              for item_rating in predicted_rating[:num_item_rec_top_M]))

이게 끝이 아니라....

---

질문도 있음... 징하다 징해
https://github.com/kakao/recoteam/blob/master/paper_review/recsys/recsys2021/Next-item%20Recommendations%20in%20Short%20Sessions.md

recoteam/paper_review/recsys/recsys2021/Next-item Recommendations in Short Sessions.md at master · kakao/recoteam

 

 

1. 첫 번째 질문: 기본 추천 수식의 이해

User-based Collaborative Filtering 설명의 식 (1)을 보고 추천 결과가 어떻게 생성되는지 설명해주세요.

$r_{u,i} = \bar{r_u} + k\sum_{u' \in U}simil(u,u')(r_{u',i} - \bar{r_{u'}})$

1. 우변 첫 번째 항: $\bar{r_u}$
   • 사용자의 평균 평점
   • 해당 사용자의 기본 평점 성향을 반영
2. 우변 두 번째 항: $k\sum_{u' \in U}simil(u,u')(r_{u',i} - \bar{r_{u'}})$
   • 이웃들의 평점 편차에 대한 가중 평균
   • 편차($r_{u',i} - \bar{r_{u'}}$): 각 이웃의 평균 대비 해당 아이템 평점 차이
   • 가중치($simil(u,u')$): 이웃과의 유사도

2. 두 번째 질문: 평균 항 제거의 영향

User-based Collaborative Filtering 설명의 식 (1)이 다음과 같이 바뀐다면( ru¯, ru′¯ 항이 사라진다면) 추천 결과가 어떻게 달라질까요?

$r_{u,i} = k\sum_{u' \in U}simil(u,u')(r_{u',i})$

1. 평점 스케일 무시
   • 낮은 평점 성향의 사용자 불이익
   • 높은 평점 성향의 사용자 과대 평가
2. 예시 시나리오:
   • 원본 수식: 사용자 A에게는 좋은 평점
   • 변경 수식: 이웃 기준으로는 낮은 평점
3. 사용자 A: 평균 2점 부여 이웃들: 평균 4.5점 부여 특정 아이템에 이웃들이 3점 부여

3. 세 번째 질문: 유사도 가중치 제거의 영향

User-based Collaborative Filtering 설명의 식 (1)이 다음과 같이 바꾸려고 한다면( simil⁡(u,u′) 항이 사라진다면) 식을 어떻게 수정해야할까요?

$r_{u,i} = \bar{r_u} + k\sum_{u' \in U}(r_{u',i} - \bar{r_{u'}})$

1. 유사도 가중치($simil(u,u')$) 제거
   • 모든 이웃의 의견을 동등하게 취급
   • 단순 산술 평균으로 변경
2. 해결 방법
3. k = 1/|U|로 설정 |U|: 이웃 집합의 크기

각 수식의 비교 표

수식 버전	특징	장단점
원본 (1)	평균, 유사도 모두 반영	가장 개인화된 추천 가능
변형 (1-1)	평균 제거	개인의 평점 성향 무시
변형 (1-2)	유사도 제거	이웃 간 중요도 차이 무시

핵심 시사점

1. 평균 평점의 중요성
   • 사용자별 평점 성향 반영 필요
   • 편향(bias) 보정 역할
2. 유사도 가중치의 의미
   • 이웃 간 영향력 차등화
   • 더 유사한 사용자의 의견을 더 중요하게 반영

---

혹시 아까 수식을 이해하지 못했다면,
User-based Collaborative Filtering 기본 수식 이해하기
예제 상황 |

• 추천을 받을 사용자 (user A)가 아직 보지 않은 영화 X에 대한 예측 평점을 계산하려고 합니다.

1. 초기 데이터

# 각 사용자의 영화 평점 데이터
rating_data = {
    'User A': {'영화1': 4, '영화2': 2, '영화3': 5},  # 평균: 3.67
    'User B': {'영화1': 5, '영화2': 3, '영화X': 4},  # 평균: 4.00
    'User C': {'영화2': 1, '영화3': 3, '영화X': 2},  # 평균: 2.00
    'User D': {'영화1': 3, '영화3': 4, '영화X': 5}   # 평균: 4.00
}

2. 단계별 계산

Step 1: 코사인 유사도 계산

https://www.lgcns.com/blog/cns-tech/ai-data/15526/

User A와 다른 사용자들의 유사도:
- A-B: 0.98 (매우 유사)
- A-C: 0.45 (약간 유사)
- A-D: 0.88 (꽤 유사)

Step 2: Top-2 이웃 선정 (N=2)

• User B (유사도: 0.98)
• User D (유사도: 0.88)

Step 3: 예측 평점 계산

$r_{u,i} = \bar{r_u} + k\sum_{u' \in U}simil(u,u')(r_{u',i} - \bar{r_{u'}})$

구성요소	값	설명
$\bar{r_u}$	3.67	User A의 평균 평점
$k$	0.54	1/(0.98 + 0.88)
User B 기여분	0.98 × (4 - 4.00)	유사도 × (영화X 평점 - B의 평균)
User D 기여분	0.88 × (5 - 4.00)	유사도 × (영화X 평점 - D의 평균)

Step 4: 최종 계산

3.67 + 0.54 × [0.98 × (4 - 4.00) + 0.88 × (5 - 4.00)]
= 3.67 + 0.54 × [0.98 × 0 + 0.88 × 1]
= 3.67 + 0.54 × 0.88
= 4.14

따라서 User A의 영화 X에 대한 예측 평점은 4.14가 됩니다.

해석

1. User A의 기본 성향(3.67)을 시작점으로 합니다.
2. 유사한 이웃들의 평가를 반영:
   • User B는 자신의 평균과 같게 평가 (영향 없음)
   • User D는 자신의 평균보다 1점 높게 평가 (긍정적 영향)
3. 이 영향들을 정규화해서 더함