[annoy] annoy 사용방법: 추천시스템에서 유사 아이템 찾기

annoy: Approximate Nearest Neighbors

 

annoy는 스포티파이에서 개발한 라이브러리로, 벡터들 간의 거리를 계산하여 빠르게 유사한 벡터들을 찾아주는 라이브러리이다. Approximate Nearest Neighbors Oh Yeah의 줄임말로, 직역하자면 근사한 이웃 찾기 아싸? 만세(?) 정도가 될 것 같다.

 

이름에서부터 느끼다 시피 annoy는 최근접 이웃 알고리즘을 사용한다. annoy를 추천시스템에 적용하기 위해 최근접 이웃을 찾아야하는 경우를 생각해보자.

 

1. 사용자의 로그가 없을 때: 일반적인 프로필 내용(성별, 나이, 지역 등)을 이용해 사용자와 유사한 특성을 가진 다른 유저들 찾기 → 다른 유저들이 선호했던 아이템들을 사용자에게 추천

 

2. 사용자의 로그가 쌓인 후 

• Collaborative Filtering: 사용 기록(history)을 벡터화하여 다른 유저들의 사용 기록과 비교 → 사용 기록 벡터들끼리 거리를 구하고 유사한 사용 기록 찾기 → 유사한 사용 기록에 기록된 아이템을 추천
• Content based Filtering: 사용자가 관심있어 한 아이템들의 특징을 벡터화하여 다른 아이템과 비교 → 아이템 벡터들끼리 거리를 구하고 유사한 아이템 찾기 → 사용자가 클릭하지 않았지만 유사한 아이템을 추천

 

추천시스템은 수집한 벡터들끼리 거리를 계산한 후에 특정 벡터와 거리가 가까운, 즉 유사한 벡터를 찾아서 제공한다. 그런데 벡터들이 많아지고 차원도 커지면 계산량이 기하급수적으로 늘어나게 된다. 이 계산량을 줄이기 위해 spotify에서 개발한 알고리즘이 바로 annoy이다. annoy는 트리 기반 알고리즘으로 빠르게 유사한 벡터를 검색할 수 있다.

 

 

annoy 작동방식

 

먼저 전체 벡터에서 랜덤하게 두 벡터를 선택하고, 두 지점 사이의 거리를 정확히 동일하게 나누는 hyperplane(초평면)을 찾는다. 초평면을 기준으로 하나의 공간은 두 공간으로 나누어진다. 이때 특정 벡터를 주면 그 벡터는 두 공간 중 하나의 공간에 속하게 될 것이다. 그 후 해당 공간에 속한 다른 벡터들과의 거리를 구하고, 유사한(=가까운) 벡터를 N개 찾는 방식이다.

 

그런데 그 공간에 속하는 벡터가 너무 적어서, 원하는 N개만큼 아이템이 없을 수도 있다. 또는 실제로는 유사한데, 랜덤하게 공간을 분리하다보니 우연하게 다른 space에 속하게 되는 가능성도 있다. annoy는 tree를 여러개 만들어 이 문제를 해결한다. 각각의 트리가 랜덤하게 공간을 분리한 후, 모든 트리에서 서치를 한다. 모든 트리에서 추천할 후보들이 추려지면, 그 중 중복된 아이템은 제거하고, 가장 유사한 N개만 반환하는 방식이다.

 

출처: https://erikbern.com/2015/10/01/nearest-neighbors-and-vector-models-part-2-how-to-search-in-high-dimensional-spaces.html

 

annoy는 C++으로 구현되어 계산이 매우 빠른데, 이때문에 C++이 설치되어 있어야 이후에 파이썬에서 annoy를 설치할 수 있다.

 

출처: https://erikbern.com/2015/10/01/nearest-neighbors-and-vector-models-part-2-how-to-search-in-high-dimensional-spaces.html

 

 

annoy 사용방법

파이썬 및 라이브러리 version
파이썬: 3.7.4
annoy: 1.17.1

import pandas as pd
import numpy as np
from sklearn.datasets import load_boston
import annoy

 

데이터 준비

data = load_boston()
df = pd.DataFrame(data.data, columns = data.feature_names)
display(df.shape, df.head())

사용한 데이터는 sklearn에서 기본으로 제공하는 보스턴 부동산 데이터이다. 

• CRIM: 타운별 1인당 범죄율
• ZN: 25,000 평방 피트 이상의 부지에 대해 구획된 주거용 토지의 비율.
• INDUS: 타운별 비소매업 에이커의 비율.
• CHAS: Charles River 여부
• NOX: 일산화질소 농도
• RM: 주거당 평균 객실 수
• AGE: 1940년 이전에 제작된 자가용 유닛의 비율
• DIS: 5개의 보스턴 고용 센터까지의 DIS 가중 거리
• RAD: 방사형 고속도로 접근성 지수
• TAX: $10,000당 전체 가치 재산세율
• PTRATIO: 타운별 학생-교사 비율
• B: 1000(Bk - 0.63)^2, Bk는 타운별 흑인의 비율
• LSTAT: 저소득층 비율

 

annoy 모델 초기화

annoy_index = annoy.AnnoyIndex(f=df.shape[1], metric='angular')
df_arr = df.to_numpy()

for idx in range(df_arr.shape[0]):
    vector = df_arr[idx, :]
    annoy_index.add_item(idx, vector)

 

annoy의 AnnoyIndex 를 이용해 모델을 구축할 수 있다. 모델 구축에 앞서 초기화를 위해 먼저 f, 피처의 개수와 metric, 거리계산 방법을 지정해주었다.

 

거리 계산 방법으로는 5가지 방식(augular, euclidean, manhattan, hamming, dot) 중 하나를 사용할 수 있다.

 

본 예제에서는 angular distance를 사용하였다. angular라고 하길래 cosine 거리의 다른 이름인가? 싶었는데 검색해보니 차이가 있는 것 같다. 두 벡터 사이의 각도가 작을 때 cosine similarity가 큰 차이를 보이지 않아 이를 보완한 것이 angular distance라고 한다. 자세한 내용은 아래 사이트를 통해 확인해보시길..

 

https://math.stackexchange.com/questions/2874940/cosine-similarity-vs-angular-distance 

Cosine similarity vs angular distance

 

annoy 초기화 후에는 add_item 함수를 이용해 인덱스마다 벡터를 할당한다. 거리계산하려는 벡터마다 라벨을 달아주는 건데, 유사한 벡터를 찾은 output을 라벨로 제공하기 때문에 필요한 과정이다.

 

annoy 모델 구축

annoy_index.build(n_trees=5) 
annoy_index.save('test.ann')

 

built 함수를 통해 annoy 모델을 만들 수 있다. n_tree는 모델링 시 만드는 트리 수를 지정하는 것으로, 많은 트리를 만들수록 정확도가 올라간다고 한다. 한번 build한 후에는 인덱스와 아이템을 추가할 수 없으니 주의해야 한다.

 

만든 annoy 모델을 저장하고 싶다면 save 함수를 사용한다.

 

유사 벡터 검색

 

본 예제에서는 get_nns_by_vector 함수를 이용하여 컬럼별 중앙값 벡터와 유사한 벡터들을 찾아보겠다

 

med_value = df.median()
med_value

 

get_nns_list = annoy_index.get_nns_by_vector(vector=med_value, n=5, include_distances=True)
get_nns_list

 

중앙값 벡터와 유사한 벡터들을 5개 찾고, 계산한 결과도 함께 제공하게 하였다. 위 함수는 결과로 유사한 벡터의 라벨을 제공한다. 때문에 기존 벡터 목록으로 돌아와 라벨을 이용해 유사한 벡터가 그래서 무엇이었는지를 확인할 수 있다.

 

df.iloc[get_nns_list[0]]

 

사용해보니 annoy는 정말 빠르긴 하지만, 데이터가 적은 경우에는 numpy나 scipy를 이용해 직접 계산하나, annoy를 사용하나 시간은 비슷하게 걸리는 듯 했다. 다만 알고리즘 구조 상 공간 내에서 유사한 벡터를 찾는다는 점에서 데이터가 아주 많은 경우에 매우 유용하게 쓰일 것 같다. 

 

 

참고

https://github.com/spotify/annoy

GitHub - spotify/annoy: Approximate Nearest Neighbors in C++/Python optimized for memory usage and loading/saving to disk

https://scikit-learn.org/stable/datasets/toy_dataset.html

7.1. Toy datasets

https://erikbern.com/2015/10/01/nearest-neighbors-and-vector-models-part-2-how-to-search-in-high-dimensional-spaces.html

Nearest neighbors and vector models – part 2 – algorithms and data structures