Ranking Algorithm 관련 논의가 필요합니다

[junwha]

• Ranking 알고리즘을 구현해야합니다.

To rank the relevant movies, you can either create your own algorithm or use an existing algorithm based on the movie ratings of similar users. Here, the “relevancy” and “similarity” should also be measured by your or existing algorithm as well. Do not use random ordering to rank the movies because it won’t be able to produce an effective recommendation list.

• Memory based collaborative filtering를 사용하는 것이 좋을 것으로 생각됩니다.

[핵심] KNN을 활용한 협업필터링
https://eda-ai-lab.tistory.com/527

Memory-based Collaborative Filtering 실제 구현 방식
https://bangseogs.tistory.com/98

Collaborative Filtering Java 구현
https://www.baeldung.com/java-collaborative-filtering-recommendations

우리가 가지고 있는 조건

1. N(Rating) = 1,000,000, N(Movie) = 4,000, N(User): 6000
2. User의 Gender, Age, Occupation
3. Input: Gender, Age, Occupation

다음과 같이 구상해보았습니다.

1. 기존 User 간의 협업 필터링 적용: KNN을 적용해 상관계수(영화 평점 vector 기반)가 높은 유저들의 Rating의 평균으로 각 유저의 모든 영화에 대한 예측 Rating을 측정합니다. (실제 평점과 예측 평점 저장소 구분할 것)
2. 새로운 유저 Input에 대해 KNN을 적용해 상관계수([Gender, Age, Occupation] vector 기반)가 높은 유저들의 Rating의 평균으로 상위 10개를 추출해 추천합니다.

생각해보아야할 부분:

1. KNN에서 상위 K명의 User를 찾기 위해 전체 탐색을 해야하는가?
2. 상위 평점 10개의 영화를 구하기 위해 전체 영화의 예측 평점을 구해야하는가?
3. 기존 User의 Rating 역시 [Gender, Age, Occupation]의 상관계수를 반영할 방법은 없을까?
   (다른 지표로 상관계수를 측정할 경우 biased될 확률이 높아보임)

[queuedq]

우선 "각 유저의 모든 영화에 대한 예측 Rating을 측정합니다" 부분에 큰 시간/공간이 들 것으로 생각되는데, 어떤 해결책이 있을지는 주말에 공부해 보고 코멘트 달도록 하겠습니다.

추가 자료
https://www.analyticsvidhya.com/blog/2020/11/create-your-own-movie-movie-recommendation-system/
https://developers.google.com/machine-learning/recommendation/collaborative/basics

[junwha]

a vector와 b vector의 상관계수를 구할 때, 누락된 데이터가 있을 경우 해당 요소와의 곱은 0으로 처리하면 될 것 같습니다 (누락된 데이터를 0으로 치환하여 연산, 저장시에는 치환 x)

n: # of user, m: #of movie
상관계수 연산의 시간 복잡도가 대략 O(n^2 x m)이니까 144억회...네요

이때 빈 자리가 있는 vector들을 채워넣을 때 결국 또 n-1번의 비교를 하게 되니까
n^2의 연산이 다시...

[junwha]

정말 간단한 구현으로는 단순히 User vector 간의 상관계수를 구해서 KNN으로 평균을 구하면 될 것 같긴 합니다만,
그래도 정확한 추천을 하기 위해서는 Collaborative Filtering을 적용하는 것이 좋을 것 같습니다

[junwha]

User vector 비교만 해도 결국 Collaborative Filtering이긴 하네요.
아니면 채워넣는 것 자체는 O(n^2)이니까 애초에 상관계수부터 User vector로 구하면 연산량이 줄어들긴 할 것 같습니다.

[junwha]

사실 저는 초기 연산량은 클 수 밖에 없을 것 같다고 생각해서, 딥러닝 신경망을 트레이닝할 때처럼 저희가 데이터를 기반으로 CF DB를 만들고, 추가적인 데이터가 있을 때 적은 연산으로 추가하는 편이 좋다고 생각합니다.

[junwha]

추가자료: 당근마켓 딥러닝 개인화 추천

[junwha]

딥러닝 라이브러리: https://deeplearning4j.konduit.ai/getting-started/

[junwha]

계속 생각해봤는데 현재 input으로는 지금까지 저희가 생각한 알고리즘을 적용하기 힘들 것 같다는 생각이 들었습니다.

넷플릭스처럼 유저가 처음에 자신이 긍정적으로 생각하는 영화들을 Rating 해주는 식이 아닌 단순히 유저 정보만으로 판단을 하는 것이기 때문에 유저 정보를 기반으로 추천이 이루어져야할 것으로 생각됩니다.

위에서 했던 논의는 Milestone3에서 저희만의 서비스를 구현할 때 사용하면 좋을 것 같습니다.

[junwha]

다음과 같이 새롭게 구상해보았습니다.

모든 데이터를 Categorical 데이터로 취급하는 것이 좋을 것 같습니다.

Gender: M/F
Age: 0~9, 10~19, ..., 80~89, 90~
Occupation: occupation id

1. Gender, Age, Occupation 카테고리를 기반으로 User 필터링
2. User를 기반으로 Rating 필터링
3. 필터링 된 Rating을 기반으로 모든 Movie에 대해 평균 Rating 도출 (Null -> rating: 0, 평균 rating은 우선순위 큐에 저장)
4. 우선순위 큐로부터 상위 10개 Movie 추출

[junwha]

Age를 단순히 categorical하게 고려하지 않고 input age로부터 +5, -5 범위로 체크하는 것이 좋을 것으로 생각됩니다

[queuedq]

추가 아이디어: 해당하는 카테고리에 충분한 레이팅 정보가 없다면, 전체 레이팅을 바탕으로 추천 영화 10개 채우기?

[junwha]

넵 해당 부분까지 모두 커버해서 구현했습니다

[junwha]

a4b4c2b 에서 우선 RatingService 클래스 구현을 완료했습니다!!
User를 필터링한 후 전체 Movie에서 Rating 평균을 낸 뒤(Rating이 없는 Movie의 Rating 평균은 0으로 초기화)
평점 평균 상위 10개를 리턴하도록 했습니다.

자세한 내용은 Test class까지 작성 후 PR에 포함해 넣도록 하겠습니다.
@jaehwan1912 Main에서 인자개수에 따라 해당 Service의 특정 메소드를 호출하도록 하면 될 것 같습니다.

[junwha]

• 1: "Under 18"
  • 18: "18-24"
  • 25: "25-34"
  • 35: "35-44"
  • 45: "45-49"
  • 50: "50-55"
  • 56: "56+"
    User 객체의 나이가 이걸 통해서 결정되는데 그걸 잊고 있었네요,,,
    해당 부분 추가하도록 하겠습니다

[queuedq]

우선순위 큐를 사용하는 대신 그냥 리스트를 정렬하는 게 낫지 않나요?

[junwha]

TreeMap과 List 정렬(O(nlogn) 모두 시간복잡도는 똑같은 것 같습니다.
자바의 경우 List를 Pair로 정렬하려면 Comparable 객체를 상속해 Pair를 직접 구현해야하기 때문에 TreeMap이 좀 더 적합하다고 생각하는데 혹시 List 정렬의 경우가 시간/공간복잡도가 더 작다면 그쪽으로 리팩토링하는 것도 좋을 것 같습니다.

Complexity with TreeMap
In this case, the backing store is a Tree. For a tree with total k elements, on an average, the time to find the location is O(Log k).

Time to insert first element = O(1)
Time to insert second element = O(Log 1) = 0 = O(1)
Time to insert third element = O(Log 2)
.
.
Time to insert nth element = O(Log (n-1))
Total time = Log 1 + Log 2 + Log 3 + ... + Log (n-1)

Now, Log 1 <= Log n, Log 2 <= Log n ... Log (n-1) <= Log n, leading us to n-1 values each of which is less than or equal to Log n.

This means that the timing for insertion in a treemap sum to a value <= (n-1) * Log (n), leading to the complexity of O(n Log (n)).

[queuedq]

TreeMap은 내부적으로 레드블랙 트리 같은 self-balancing binary search tree를 사용하기 때문에 연산이 느리며, 의미적으로도 상위 10개의 영화를 구하는 데 TreeMap의 연산이 필요한 것이 아니므로 그냥 정렬을 사용하는 것이 낫습니다. 다만 구현상의 번거로움이 있다면 그냥 TreeMap을 사용하도록 합시다.

[junwha]

TreeMap보다 List가 정렬이 빠르다면 현재처럼 average-Movie List의 key - value pair를 유지하는 맵을 만들어놓고, 별도의 리스트에서 average를 정렬한 뒤 다시 해당 맵에서 추출해오는 방법을 적용하면 좋을 것 같습니다.

[junwha]

@jaehwan1912
현재는 특정 input에서 개수가 모자를 경우 전체 레포에서 일괄적으로 가져오는 형태인데
rating된 Movie의 개수가 10보다 작을 경우 일부 인풋의 rating을 생산해 채우는 부분을 추가하면 좋을 것으로 생각됩니다.

ex)
"Gender1" "Occupation1" "Age1"로 검색 결과 => Rating 된 것이 7개일 경우

1. 하나씩 제외 후 재검색
2. 두개씩 제외 후 재검색
3. 완전히 제외 후 재검색 (전체 레이팅 평균)

또한 3번의 연산량을 줄이기 위해서는 Movie 클래스에 average rating 필드를 추가하는 것이 좋겠습니다.