Faiss를 활용한 고차원 벡터 유사도 구하기

강현태·2022년 7월 4일
0
post-thumbnail

Faiss

https://github.com/facebookresearch/faiss


What is Faiss

Faiss는 Facebook에서 개발 및 배포한 밀집 벡터의 유사도 측정과 클러스터링에 효율적인 라이브러리이다. RAM에 구애받지 않고 어떤 크기의 벡터이건 탐색 및 측정을 지원한다. 평가나 파라미터 조정을 위한 코드도 지원한다. C++ 기반이지만, Python으로도 사용할 수 있다.


Installing

https://github.com/facebookresearch/faiss/blob/main/INSTALL.md

📌 Installing Faiss via conda

# CPU-only version
$ conda install -c pytorch faiss-cpu

# GPU(+CPU) version
$ conda install -c pytorch faiss-gpu

# or for a specific CUDA version
$ conda install -c pytorch faiss-gpu cudatoolkit=10.2 # for CUDA 10.2

Faiss github 계정에서는 conda를 통한 설치 방법을 권장했다.
CPU-only package는 현재 Linux, OSX, Windows에서 모두 가능하지만
CPU, GPU를 모두 포함하는 패키지는 Linux에서만 가능하다고 한다.

📌 Installing from conda-forge

# CPU version
$ conda install -c conda-forge faiss-cpu

# GPU version
$ conda install -c conda-forge faiss-gpu

conda-forge로도 지원한다.
이 외의 추가적인 설치 방법은 위의 깃헙 계정을 참고하길 바람!


Getting started

https://github.com/facebookresearch/faiss/wiki/Getting-started

📌 Building, Adding, Searching

Faiss는 Index Object를 기반으로 작업이 진행된다. 데이터 베이스의 벡터를 저장하고, searching하는데 효율적이게끔 전처리도 진행된다.

많은 인덱스들이 존재하지만, Getting Started에서는 가장 기본적인 Brute-force algorithm을 활용한 IndexFlatL2 인덱스(Euclidean Distance)를 사용했다.
그 외의 추가적인 인덱스 매트릭스는 아래 깃헙 링크를 참조하면 된다.
https://github.com/facebookresearch/faiss/wiki/Faiss-indexes

import faiss   # make faiss available

index = faiss.IndexFlatL2(dimension)   # build the index
index.add(vector)    # add vectors to the index

k = 4  # we want to see 4 nearest neighbors
D, I = index.search(query vecotr, k) 
print(I[:5])   # neighbors of the 5 first queries
print(I[-5:])  # neighbors of the 5 last queries
  • IndexFlatL2에 vector의 차원을 부여하여 Index를 생성한다.
  • 생성한 Index에 vector를 부여한다.
  • 비교할 query vector, 원하는 neighbors를 파라미터로 설정한 후 search
  • D는 Distances, I는 Indicies다.

보다 정확한 이해를 위해서는 Faiss github의 메뉴얼을 보며 직접 코딩해보는 편이 좋아 보인다.


📌 Cosine Similarity

위의 IndexFlatL2는 가장 기초적인 brute-force algorithm이며, Euclidean Distance에 근거한다.
Faiss를 통해 Cosine Similarity도 구할 수 있는데 몇 줄의 간단한 코드만 추가하면 된다.

import faiss

index = faiss.IndexFlatIP(dimension) # IndexFlatL2 대신에 IndexFlatIP
faiss.normalize_L2(vector) # vector를 add하기 전에 normalize_L2
index.add(vector) # 정규화를 마친 후에 add

k = 4  
D, I = index.search(query vecotr, k) # 이후 search는 똑같다.

Index를 FlatL2 대신 FlatIP를 사용하고, add 하기 전에 정규화를 진행해주면 된다.
그럼 Distances에 distance 대신 cosine similarity가 저장되어 있다.

만약 동일한 벡터 집합 내에서 유사도를 측정하고 싶다면?
vector를 add한 후에 query vector 대신에 vector를 search하면 된다.


📌 Clustering

https://github.com/facebookresearch/faiss/wiki/Faiss-building-blocks:-clustering,-PCA,-quantization

Faiss에서는 간단한 kmeans clustering도 지원한다.

ncentroids = 1024
niter = 20
verbose = True
d = vector.shape[1]
kmeans = faiss.Kmeans(d, ncentroids, niter=niter, verbose=verbose)
kmeans.train(vector)

📍 ncentroids = centroid의 개수

  • centroid?
    • K-Means 의 “K”는 그룹화 할 그룹, 클러스터의 수.
    • “Means”는 각 클러스터의 중심과 데이터들의 평균 거리.
    • 이 때 클러스터의 중심이 centroids

📍 niter = iteration 숫자
📍 verbose = 상세한 로깅 logging 을 출력할지 말지
📍 d = dimension

이 외의 파라미터에 대한 상세한 설명은 역시 공식 깃헙 계정을 참조!

nlist = 20  # how many cells
quantizer = faiss.IndexFlatL2(d)
index = faiss.IndexIVFFlat(quantizer, d, nlist)

index.train(vector)

index.add(vector)
D, I = index.search(kmeans.centroids, 20)

이번에는 IndexIVFFlat을 Index로 사용했다.
해당 Index는 quantizer와 nlist라는 파라미터가 필요해 지정함.
이후 train 과정을 거친 후 add하여 search하게 된다.

Sampling a subset of 5120 / 7000 for training
Clustering 5120 points in 220D to 20 clusters, redo 1 times, 10 iterations
  Preprocessing in 0.00 s
  Iteration 9 (0.02 s, search 0.02 s): objective=2545.12 imbalance=2.185 nsplit=0 

실행하면 이런 식으로 몇 개의 클러스터를 형성할지, 몇 번 반복했는지 .. 등등의 log도 같이 출력된다.

profile
데이터 분석, ML/DL, 통계 지식을 공부하고 저장하는 공간

0개의 댓글