[Project] 칵테일 추천 알고리즘 설계 - 협업 필터링 구상-

 

앞선 포스팅으로, 비교적 간단하고 직관적인 칵테일 추천 알고리즘을 만들었다.

대부분의 사용자들이 관심있어하는 칵테일, 또 웹 페이지에서 도출된 사용자들의 행동을 바탕으로 칵테일을 추천해주는 방식이었는데, 이러한 방식은 모든 사용자들에게 동일한 추천 알고리즘이 적용된다.

 

이에 좀 더 개인화된 추천 알고리즘 설계를 위해 넷플릭스의 협업 필터링 알고리즘에서 아이디어를 얻어, 보다 개인적인 취향에 맞는 칵테일을 추천할 수 있는 알고리즘을 설계해보고자 한다.

즉 비슷한 취향의 다른 사용자들이 좋아한 콘텐츠를 추천하는 알고리즘을 만들어 보자. ( A와 B가 비슷한 콘텐츠를 시청한 경우, A가 아직 보지 않은 B가 좋아한 콘텐츠를 추천한다)

이러한 설계로 보다 차별화된 알고리즘을 만들어서 웹 페이지의 특징을 살리고, 시간복잡도 및 DB 쿼리 사용을 적절하게 이용하는 법을 공부하도록 하자.

 

1. 개인화된 추천 알고리즘 구상

1-1 자료의 셋팅

• Map1<String, Integer> cocktails 구조를 사용하여 칵테일명과 점수를 저장한다. 
  점수는 Google Trend 의 점수 G 와 Naver Trend의 점수 N 에 대하여 가중치를 곱하여 합한다.
  Integer =   G * 0.92 + N * 0.70 
• 내가 좋아요를 표시한 칵테일 목록을 가져온다. (목록A)
• Map1 에서 내가 좋아요를 표시한 칵테일을 삭제한다. (목록 A 와 비교하여 삭제한다)
• Map1 에는 내가 좋아요를 누르지 않은 칵테일들만 남게 된다.
• 내가 좋아요를 표시한 칵테일 목록에서 랜덤으로 1개를 선택한다. (변수를 선언하여 자장)

1-2 가중치 부여

• 내가 좋아하는 칵테일 1개에 대하여, 해당 칵테일에 좋아요를 누른 사용자 계정 목록을 가져온다.
• 사용자 계정마다 좋아요를 누른 칵테일의 목록을 가져온다. (목록B)
• 목록B 에서 Map1 과 비교하여, 같은 칵테일명이 있다면 점수를 10점 더한다 (가중치 작업)
• 가중치 작업을 while 문 이나 반복문을 사용하여, 사용자 계정 목록의 수 만큼 진행한다.

1-3 자료구조 소팅 

• Map1 을 점수를 기준으로 정렬한다.
• 추천을 위해 0번~4번 칵테일의 이름을 반환한다.

1-4 예외 상황

• 만약 좋아요를 누르지 않은 칵테일의 갯수가 5개보다 적다면 에러가 발생하기 때문에, 사전에 좋아요를 누른 칵테일 갯수와, 전체 칵테일 갯수에 대해 검증을 한다.
• 좋아요를 누르지 않은 칵테일이 5개 이상이라면 해당 알고리즘대로 동작을 수행하고, 5개 미만일 경우 모자란 칵테일 갯수만큼 좋아요를 표시한 칵테일에서 랜덤으로 충당한다.

 

2. 자료구조 사용

 

1. 자료 셋팅: Map<String, Integer>

• 칵테일명과 점수를 저장하기 위해 Map<String, Integer> 자료구조를 사용한다.
• Map은 키(칵테일 명)를 통해 점수에 빠르게 접근할 수 있는 구조이다. 이를 통해 칵테일 이름으로 점수를 조회하거나 수정하는 작업이 효율적일 것이다.
• Google Trend와 Naver Trend의 점수를 가져와 가중치를 곱한 후, 간단히 Map에 저장하여 관리할 수 있다.
• Google Trend와 Naver Trend의 점수는 DB에서 직접 조회하는 쿼리를 사용하여 한 번에 가져오도록 한다. (API 요청 횟수를 줄이고, 데이터의 일관성을 유지할 수 있다)

2. 가중치 부여: List<String>

• 사용자가 좋아요를 누른 칵테일 목록을 저장하기 위해 List<String>을 사용한다.
• List는 순서가 중요하지 않다. List 는 사용자가 좋아요를 누른 칵테일을 간편하게 저장하고 관리할 수 있다.
• 사용자의 칵테일 목록을 반복문을 활용해 간단하게 처리할 수 있어, 점수를 추가하는 과정이 직관적이다.
• 이 단계에서도 사용자 계정 목록과 그들이 좋아요를 누른 칵테일 목록을 DB에서 가져오는 쿼리를 활용하면, 데이터베이스의 JOIN 기능을 이용해 여러 테이블의 데이터를 효율적으로 조회할 수 있다.

3. 자료구조 소팅: List<Map.Entry<String, Integer>>

• 추천 알고리즘에서 점수를 기준으로 칵테일을 정렬하기 위해 List<Map.Entry<String, Integer>>를 사용한다.
• Java의 Collections.sort() 메서드를 사용하여 Map의 엔트리 리스트를 쉽게 정렬할 수 있다. 이를 통해 높은 점수를 가진 칵테일을 손쉽게 우선적으로 추천할 수 있다.
  
  

3. 각 단계별 시간 복잡도 및 보완 사항

 

1. 자료 셋팅 : Map<String, Integer>

• 시간 복잡도: O(1)
• Map에 값을 추가하거나 조회하는 작업은 평균적으로 O(1)의 시간 복잡도를 가지지만, 해시 충돌이 발생할 경우 최악의 경우 O(n)까지 증가할 수 있다.

2. 가중치 부여: List<String>

• 시간 복잡도: O(m * n)
  m은 사용자가 좋아요를 누른 칵테일의 수, n은 사용자 계정 수.
• 각 사용자에 대해 좋아요를 누른 칵테일 목록을 반복하며 점수를 추가하는 작업이 필요하므로, 이중 반복문을 사용하게 된다.

사용자 수와 좋아요 수가 많아질 경우 처리 시간이 급격히 증가하기 때문에 아래와 같은 보완사항을 고려해야 한다.

• 비동기 처리: 사용자 요청을 비동기적으로 처리하여 서버의 부하를 줄일 수 있다.
• 캐싱: 자주 조회되는 데이터를 메모리에 캐시하여 DB 호출 횟수를 줄이고, 성능을 향상시킬 수 있다.
• 데이터베이스 최적화: 쿼리를 최적화하여 데이터베이스의 성능을 높이고, 필요한 데이터만 불러오도록 설정할 수 있다.

3. 자료구조 소팅: List<Map.Entry<String, Integer>>

• 시간 복잡도: O(k log k)
  k는 Map의 엔트리 수 이다. Java의 Collections.sort() 메서드는 일반적으로 O(n log n) 알고리즘을 사용하므로, 엔트리 수에 따라 로그 복잡도가 발생한다.
• 사용자 수가 많아질 경우, 이 단계가 가장 큰 성능 저하를 초래할 수 있다. 사용자 수가 증가하면 반복문이 늘어나고, 이로 인해 O(m * n)의 시간 복잡도로 인해 처리 시간이 크게 증가한다.
• Map의 엔트리 수가 많아질 경우, 소팅 작업도는 O(k log k)로 시간이 소요된다. 사용자가 많아지면 추천할 칵테일의 수가 증가하므로, 이 단계에서도 성능 저하가 발생할 수 있다.