나를 잃지 말자

가장 기본적인 clustering algorithm, unsupervised.

k는 cluster의 개수를 나타낸다.(hyperparameter)

최적의 k개의 centroids를 찾는 것이 알고리즘의 목표

알고리즘:

Assignment-step과 Update-step으로 나뉘어져있다.

각 data마다 가장 가까운 centroid을 갖는 cluster로 assign

위의 loop를 다 돌면 centroid를 해당 cluster내의 point average를 통해 update

위 2과정을 반복 후 converge하면 알고리즘 종료

특징:

Optimum으로 convergence가 보장되어 있지 않다.

L2 distance가 아닌 distance는 더 converge가 보장 안된다.

->data의 scatter가 Sphere모양이 아닌 경우에는 clustering이 잘 되지 않는다. 

->이 때는 DBSCAN을 사용하자.(DBSCAN은 다음에 알아보자.)

NP-hard for any k >= 2

복잡도가 O(n^(dk+1)), where n:데이터 개수, d:데이터 차원, k:cluster개수

->따라서 변형인 Lloyd's algorithm을 대개 사용한다. (이는 다음에 알아보자.)

metric:

clustering이 얼마나 잘됐나 평가하는 데에 있어 

각 클러스터 내의 data가 해당 centroid까지의 distance,

그리고 이를 전체 data에 대해 평균내린 값을 metric으로 잡아 사용(낮을 수록 좋은)

이러한 metric을 average diameter라 한다.

최적의 k찾기:

average diameter가 k가 클수록 낮아지는 경향이 있다. 이 때 낮아지는 "폭이" 줄어들 때의 k를 최적의 k로 택한다.

참고자료:

en.wikipedia.org/wiki/K-means_clustering

www.secmem.org/blog/2019/05/17/clustering/

Faiss란,

Faiss is a library for efficient similarity search and clustering of dense vectors. It contains algorithms that search in sets of vectors of any size, up to ones that possibly do not fit in RAM. It also contains supporting code for evaluation and parameter tuning. Faiss is written in C++ with complete wrappers for Python/numpy. Some of the most useful algorithms are implemented on the GPU. It is developed by Facebook AI Research.

Faiss의 특징

즉, dense vector databases에서 query vector와 가장 유사한 vector를 뽑는 효율적인 알고리즘이다.

CPU, GPU 기반으로 작동하게 할 수 있으며,

IVF(InVerted File index)를 활용

L2 distance, Dot product(L2 normalization하면 cosine similarity도 가능)가 가능

binary vectors and compact quantization vectors(PCA, Product Quantization사용)를 활용

따라서 original vectors를 keep하지 않아 낮은 RAM으로도 billions vector database에 적용 가능

Multi-GPU 사용도 제공

Batch processing 제공

L2, inner product, L1, Linf 등의 distance 제공

query vector의 radius 내의 모든 vectors in DB를 return할 수도 있음

index(=DB)를 RAM이 아니라 DISK에 store

Faiss 설치

pypi.org/project/faiss-gpu/#files

에서 환경에 맞는 whl파일을 받아(file.whl)

pip3 install file.whl을 치면 된다.

Faiss의 tutorial을 보며 각 용어들을 정리하자.

Tutorial(Getting started, IndexFlatL2 사용)

Tutorial(Faster search, IndexIVFFlat 사용)

IndexIVFFlat이란

"Index":index객체를 만들것인데

"IVF":각 vector(word)마다 voronoi cell(document)가 무엇인지 mapping하는 quantiser를 활용할 것이고

"Flat":product quantization으로 vector를 compress하지 않고 raw vector를 활용하는

Index객체를 만들 것이다.

Tutorial(Faster search, PCA사용)

Tutorial(Faster search, Product Quantization사용)

실제 사용에서는 Batch + GPU 등으로 돌리니, github->wiki에서 더 많은 tutorial, basics 등을 참고하자.

참고자료:

github.com/facebookresearch/faiss

pypi.org/project/faiss-gpu/#files

github.com/facebookresearch/faiss/tree/master/tutorial/python

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

github.com/facebookresearch/faiss/wiki/Faster-search

medium.com/dotstar/understanding-faiss-part-2-79d90b1e5388

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