해당 포스트는 실시간 추천엔진 머신한대에 구겨넣기 슬라이드를 기반으로 작성했습니다.

추천시스템?

추천 시스템은 사용자에게 개인화된 서비스를 제공한다.
유저의 행동 혹은 정보를 기반으로 어떤 아이템을 좋아할지 등등의 정보를 제공해준다.

예시로

• Netflix : 대여되는 영화의 2/3가 추천으로부터 발생
• Google News : 38% 이상의 조회가 추천에 의해 발생
• Amazon : 판매의 35% 가 추천으로부터 발생
• Netflix Prize (~2009) Netflix에서 주관하는 경연대회로, 영화 선호도를 가장 잘 예측하는 협업 필터링 알고리즘에 수상 (US$1,000,000)
  라고 한다

추천 시스템 분류

내용 기반(Content-based) 추천

말그대로 컨텐츠 자체의 내용을 기반으로 비슷한 컨텐츠를 추천한다.

간단하게 생각하면 텍스트 기반의 컨텐츠에선 TF-IDF와 같은 방식으로 추천한다
비교적 간단한 방법이지만 한계가 명확하다

그리고 실제로 사용하기 어렵다.

사전 지식도 있어야하고
개별 컨텐츠별 메타 데이터도 별로 없고
상품에서 뽑아내기도 어렵고

협업 필터링 (Collaborative Filtering)

그래서 많은 유저들로부터 모은 정보들을 기반으로 스스로 에측하는 방법이다.

예를 들어 A 유저가 한 이슈에 관해서 B 유저와 같은 의견을 갖는다면
다른 이슈에 대해서도 비슷한 의견을 가질 확률이 높을 것을 전제로 한다.

크게

• Memory-based
• Model-based
• Hybrid
  로 구분된다

또

• User-Based

• Item-Based
  로 나눠지는데

• 사용자 기반 : 비슷한 고객들이 ~한 제품을 구매했다.

• 아이템 기반 : ~ 상품을 구매한 고객들은 다음 상품도 구매했다.

사용자 기반

두 사용자가 얼마나 유사한 항목을 선호했는지를 기준으로 한다.
한 사용자가 선택한 항목들의 점수들을 백터로 나타낸다
보통 코사인 유사도, 피어슨 유사도를 사용한다.

유저 간 코사인 유사도 (공통 평가 기준)

코사인 유사도:

$$
\text{sim}(u, v) = \frac{\mathbf{r}_u \cdot \mathbf{r}_v}{|\mathbf{r}_u| \cdot |\mathbf{r}_v|}
$$

예측 평점 (weighted sum):

$$ \hat{r}_{u,i} = \frac{\sum_{v \in N(i)} \text{sim}(u, v) \cdot r_{v,i}}{\sum_{v \in N(i)} \left| \text{sim}(u, v) \right|} $$

예를들어
user_2 점수가 (1, 0, 1, x, 4)
user_4 점수가 (x, 2, 1, 4, 3)
이라면 공통적으로 평가한 아이템들(item_2, item_3, item_5)에 대해서 판단한다.

A=(0, 1, 4), B=(2, 1, 3)이고, 코사인 유사도는 다음과 같이 정의된다.

$$A = (0, 1, 4), \quad B = (2, 1, 3)$$
$$A \cdot B = 0 \cdot 2 + 1 \cdot 1 + 4 \cdot 3 = 0 + 1 + 12 = 13$$
$$|A| = \sqrt{0^2 + 1^2 + 4^2} = \sqrt{0 + 1 + 16} = \sqrt{17}$$
$$|B| = \sqrt{2^2 + 1^2 + 3^2} = \sqrt{4 + 1 + 9} = \sqrt{14} $$
$$\cos(\theta) = \frac{A \cdot B}{|A| |B|} = \frac{13}{\sqrt{17} \cdot \sqrt{14}} = \frac{13}{\sqrt{238}}$$
$$\cos(\theta) \approx \frac{13}{15.427} \approx 0.8425$$

요렇게 유사도를 측정한다면??

미평가 항목 예측 평점 (weighted sum)

요런식으로 간단하게 계산할 수 있다

아이템 기반#

아이템 간 코사인 유사도 행렬

아이템 기반 예측 평점 (미평가 항목)

코사인 유사도의 문제?

(5, 5, 5, 5, 5, 5), (1, 1, 1, 1, 1, 1). 이 때, 이 둘간의 유사도는 1이다
그래서 피어슨 유사도, 혹은 약간의 보정 과정을 거친 코사인 유사도를 사용하기도 한다..

간단하게 구현해보기 (MinHash + LSH)

내용은 해당 슬라이드를 기반으로 합니다.

• 실시간 추천엔진 머신한대에 구겨넣기

메모리 기반 추천을 만들때 결국 문제는 모든 유저, 항목에 대해서 유사도를 계속 계산해야한다는 부분이다.
물론 하둡 같은게 있긴한데 역시 하둡으로도 무리

그래서 슬라이드에서는 MinHash + LSH를 이용한 방식을 설명한다.

기본적인 컨셉은 Jaccard Similarity를 사용하는 것인데

• 집합을 사용하여 정확도를 어느정도 포기하고 속도를 챙긴 방식이라고 생각하면 쉬울듯?

sparse한 데이터에 적합한가..?

• 집합이니까 오히려 좋아
• 다만 이진 데이터가 아닌 경우에는 바로 사용하기 어려울듯 - 요걸 MinHash로?

Minhash이란?

1. 집합을 행으로 놓은 행렬에서, 각 열은 어떤 요소가 포함되어 있는지를 나타낸다 (즉, sparse binary matrix).

2. 여러 개의 무작위 해시 함수를 적용하여 각 집합(열)에 대해 “처음으로 등장하는 원소의 인덱스(최소값)“을 기록한다.

3. 이렇게 만든 여러 개의 최소값 리스트가 MinHash 서명 값이 된다.

따라서 MinHashing을 사용하여 희소성을 제거하고 유사성을 유지함으로써 공간복잡성 문제를 해결할 수 있다.

→ 두 집합의 서명에서 동일한 해시값을 가지는 비율 ≈ Jaccard 유사도

요렇게 간단하게 유사도를 계산해줄 수 있다.

LSH

LSH는 Minhash를 통해 구한 signature matrix의 한 컬럼을 가지고 어떻게 비슷한 다른 컬럼을 찾을 수 있을지이다.
간단히 말하면 전체 검색 없이 유사한 데이터를 찾기 위한 기법이다.

LSH (Locality Sensitive Hashing) 는 고차원 공간에서 유사한 데이터끼리 같은 버킷에 들어가도록 설계된 해싱 기법

핵심 컨셉은

• 일반 해시는 완전히 다른 값도 같은 버킷에 넣을 수 있고, 유사한 값도 완전히 떨어진 버킷에 들어갈 수 있음.
• LSH는 특별히 설계된 해시 함수를 사용해서, 유사한 벡터일수록 같은 해시값을 가질 확률이 높음.

길이가 n인 signature matrix를 b등분 해서 b bands로
각 Band는 r의 행을 가짐

b * r = n

각 밴드는 k개의 버킷을 가지고 있고, 밴드별로 할당된 시그니처의 열을 k개의 버킷에 해싱

이때 b와 r을 결정해야 한다.

1. b가 커지면 similarity threshold가 낮다. 이는 FP가 높다는 것을 의미.
2. b가 작아지면 similarity threshold가 높다. 이는 FN가 높다는 것을 의미.

FP : False Positive = 비슷하지 않은데 비슷하다고 판단하는 오류
FN : False Negative = 비슷한데 비슷하지 않다고 판단하는 오류

위 설명을 참고하자면 n은 고정이기 때문에 b가 커지면 r은 작아진다.

알고리즘에서는 하나의 band에 들어있는 모든 row를 해시한 값이 일치하면 비슷한 문서라고 판단

그러므로 r이 낮을 수록 문서를 비슷하다고 판단할 확률이 높아진다고 볼 수 있음...

어렵다..
그냥 이런 구조 쓰면 빠르게 탐색이 가능하다 정도로 이해하면 될듯..

그럼 슬라이드 이어서..

실제로는 Random permutation 만드는것도 리소스가 꽤 든다
universal hash 를 랜덤 생성해서 proxy로 사용??

• 어떠한 키 유니버스가 주어져도 충돌의 개수를 줄여서 가장 큰 chain 의 크기를 상수로 만드는 해쉬 함수

hash 되어 나온 값을 시그니처라하고 적당히 concate 시켜서 cluster id 삼아서 한다는데
Signature Matrix 말하는듯?? 문서의 핑거 프린트 같은 느낌

그담에 LSH의 Banding하는걸
적당히 concate 시키다..

슬라이드에서 말하는 후보 등록, 추천의 순서는 다음과 같다

# 클러스터 만들기
for 후보 in 모든 후보:
	그 호부의 모든 클릭 스트림 로딩
	로딩한것으로 MinHash Signature 생성
	Signature들을 concate해서 다량의 cluster id 생성
	후보들 해당 Cluster Id들에 집어넣기
for cluster in 만들어진 클러스터들:
	if length(클러스터) > threshold:
		클러스터의 멤버십 정보 저장

# 클러스터 정보로 추천하기
if 타겟 Item이 존재:
	타겟 Itemdml minhash 값을 가져옴
	Minhash 값을 Concate해서 Cluster id 리스트 작성
	통해 cluster 다 찾기
	for cluster in 타겟이 포함된 클러스터들:
		클러스터내 다른 item 로딩
		Item들의 클릭스트림 로딩
		기초로 pair 유사도 계산
	각 클러스터들로 부터 모은 유사도 top N개 추출
	적절히 소팅 후 추천

근데 이걸 개선??

너무 느려

요건 느리다
minhash로 클러스팅, 추천하기
모두 Heavy I/O 가 잦음

클러스터를 쓰면

• 장점: 후보 한정 - speed UP
• 단점: 후보 한정 - qualitiy Loss

I/O 문제는 왜 나오는가

상품과 유저의 부익부 빈익빈 때문에

그니까 서비스 기준으로 보면
스와이프 많이 하는 사람과 적게하는 사람이 존재하고
스와이프를 많이 받는 사람과 적게 받는 사람이 존재함

인기 있는 유저가 있다면
비교대상으로 자주 등장
ㄴ 엄청 긴 클릭스트림
ㄴ 로딩하는데 오래걸림
ㄴ 공간 모잘라서 캐싱도 날라감
ㄴ 각종 page out..
ㄴ 퍼모먼스 저하

왜 느린데? 긴 클릭스트림..

그니까 결국 인기 아이템(유저)의 클릭스트림 길이를 어케 해야한다

클릭 스트림 원본 말고 차원 축소한 어떤 값이 필요함
대체본끼리 비교해 유사도를 알아야함
ㄴ minhash

hash function 수 n만큼 signatrue 생성?
ㄴ 모두 같은 길이를 가짐

signature이 겹치는 sig의 비율이 곧 jaccard

signature의 길이가 어느정도 되어야하는가?

슬라이드에 따르면 100개 정도면 근사한다고 한다

• 요건 테스트 필요할듯??

장점은?

자료구조 상 실시간 데이터 반영이 가능하다
MinHash의 결합, 멱등 법칙을 이용하면

새로운 클릭 스트림만 계산해서 넣어주면 된다

추천할 때 그래도 느린데?

그러면 각 Item들에 대한 비교를 하기 위해
시그니처를 n^2의 계산이 들어가게된다

요건 슬라이드 내용을 그대로 가져왔다

Secondary Index 를 보는것 만으로도 Jaccard 유사도 계산이 가능해진다

어따 올려. Redis

결국 Secondary Index를 in-memory 상에서 들고 계산해야한다

고럼 Redis

• key: signature
• value: [item1, item2]
  요런 형태의 데이터를 쭉 저장해야하는데

set을 쓰면 너무 느리다

String으로 mget + pipe 를 써서 atomic하게 처리가 가능해진다

CS의 중요성..

결론 + 후기

추천 시스템을 간단하게 구현하는 방법에 대해서 알아봤는데
실제로는 Cold Start 문제, 인기 아이템 등등
여러 문제가 있어서 다양한 방법들을 섞어서 사용한다고 한다

추천 시스템 구축할때 아마 대부분 직접 구현하기 보다는 Amazon Personalize 같은 서비스를 쓸텐데
비용이 부담스럽다면 위 슬라이드에서 말하는 방식이 처음 가볍게 추천 시스템을 적용하기엔 너무 좋은것 같다

그리고.. 저런 아이디어를 어떻게 생각하는지... 신기하다........
역시 자료구조, 알고리즘 등등. CS가 기본이라는 생각이 든다

참고

• https://www.slideshare.net/slideshow/261-52784785/52784785
• https://criling.tistory.com/61
• https://trivia-starage.tistory.com/192
• https://medium.com/h-document/자카드-거리-jaccard-distance-e5b246603775
• https://coding-wonderland.tistory.com/14