坑挖太多了，已經沒時間填。那就再挖一個吧
faiss是為稠密向量提供高效相似度搜索和聚類的框架。由Facebook AI Research研發。 具有以下特性。
1、提供多種檢索方法
2、速度快
3、可存在記憶體和磁碟中
4、C++實現，提供Python封裝呼叫。
5、大部分演算法支援GPU實現
#簡單的cosine_similarity的計算
import
faiss
from
faiss
import
normalize_L2
import
numpy
as
np
def
cosine_similar
（）：
‘’‘
cosine_similarity
use
：return：
’‘’
d
=
64
# dimension
nb
=
105
# database size
#主要是為了測試不是歸一化的vector
training_vectors
=
np
。
random
。
random
（（
nb
，
d
））
。
astype
（
‘float32’
）
*
10
（
‘just compare with skearn’
）
from
sklearn。metrics。pairwise
import
cosine_similarity
#主要是為了與sklearn 比較結果
ag
=
cosine_similarity
（
training_vectors
）
fe
=
np
。
sort
（
ag
，
axis
=
1
）
（
‘normalize_L2’
）
normalize_L2
（
training_vectors
）
（
‘IndexFlatIP’
）
index
=
faiss
。
IndexFlatIP
（
d
）
index
。
train
（
training_vectors
）
（
index
）
（
‘train’
）
（
index
。
is_trained
）
（
‘add’
）
（
index
）
index
。
add
（
training_vectors
）
（
‘search’
）
D
，
I
=
index
。
search
（
training_vectors
［：
100
］，
5
）
（
I
［：
5
］）
# 表示最相近的前5個的index
（
D
［：
5
］）
# 表示最相近的前5個的相似度的值
cosine_similar
（）
結論
：sklearn 和 FAISS的IndexFlatIP模式的計算結果是一模一樣的，IndexFlatIP這個模式就是精確的暴力的計算模式。
效率上，實際應用，embedding後向量計算相似度，在200w條的資料中，計算每一條前100最相似的鄰居，全量計算肯定是不合適的，如果全量計算要等10h+才能出最後的結果，所以是分批計算，每次只計算若干條，經試驗：計算1W條160s左右，計算2W條329s，計算1k條24s左右，經過測算1w條算一次是比較合適的，具體時間如下圖：
上面暴力算是精度高了，但是search time 也邊長了，因此引入倒排版的相似度計算：
建立IndexIVFFlat時需要指定一個其他的索引作為量化器（quantizer）來計算距離或相似度。
這裡同使用
IndexFlatL2
對比，在
add
方法之前需要先訓練。
下面簡述示例中的幾個引數。
faiss。METRIC_L2
： faiss定義了兩種衡量相似度的方法（metrics），分別為
faiss。METRIC_L2
、
faiss。METRIC_INNER_PRODUCT
。一個是歐式距離，一個是向量內積（餘弦相似度）。
nlist
：聚類中心的個數
k
：查詢最相似的k個向量
index。nprobe
：查詢聚類中心的個數，預設為1個
#加速版的cosine_similarity的計算
def IndexIVFFlat（）：
d = 64 # dimension
nb = 100005 # database size
np。random。seed（1234） # make reproducible
training_vectors= np。random。random（（nb， d））。astype（‘float32’）*10
normalize_L2（training_vectors）
nlist = 1000 # 聚類中心的個數
k = 50 #鄰居個數
quantizer = faiss。IndexFlatIP（d） # the other index，需要以其他index作為基礎
index = faiss。IndexIVFFlat（quantizer， d， nlist， faiss。METRIC_INNER_PRODUCT）
# by default it performs inner-product search
assert not index。is_trained
index。train（training_vectors）
assert index。is_trained
index。nprobe = 300 # default nprobe is 1， try a few more
index。add（training_vectors） # add may be a bit slower as well
t1=time。time（）
D， I = index。search（training_vectors［：100］， k） # actual search
t2 = time。time（）
print（‘faiss kmeans result times {}’。format（t2-t1））
# print（D［：5］） # neighbors of the 5 first queries
print（I［：5］）
IndexIVFFlat（）
IndexIVFFlat這個模式就是Inverted file with exact post-verification，翻譯過來叫倒排檔案，其實是使用K-means建立聚類中心，然後透過查詢最近的聚類中心，然後比較聚類中的所有向量得到相似的向量。
這個模式的Python的 寫法不對的如下：
def
make_index
（）：
index_sub
=
faiss
。
IndexFlatL2
（
10
）
index
=
faiss
。
IndexIDMap
（
index_sub
）
return
index
# CRASH！
正確的寫法：
def make_index（）：
index_sub = faiss。IndexFlatL2（10）
index = faiss。IndexIDMap（index_sub）
index_sub。this。disown（）
index。own_fields = True
return index
具體原因facebookresearch/faiss
如下2個圖是IndexFlatIP模式的計算結果search time 0。9045s
暴力算的，結果是準確可靠的
如下2個圖是IndexIVFFlat模式的計算結果，search time 0。0818s
暴力模式下的第4，7。。。個鄰居（第一個鄰居是自己本身）在倒排模式沒了，速度是快了，但是找最相鄰的鄰居有丟三落四的情況。看相似度結果，能找到的鄰居，相似度都與暴力模式是相同，所以相似度結果是準確的。
對比與結論
：1。找最相鄰的鄰居有丟三落四的情況，2。計算的相似度結果是準確的（不會出現說原來排名靠後的鄰居，現在變成排名靠前）。
效率上，
一些引數的敏感性：
nprobe越大，召回效果越好。
C=10 to give an idea ncentroids = C * sqrt （n）
index。nprobe 改成3，search time 0。0404949s，結果有點慘不忍睹了，第二居的相似度到了0。8851595，0。9以上的直接丟了。
暴力模式下的，和前面的圖是一模一樣的，只是複製了一份下來
index。nprobe =3的對比暴力模式的，直接丟棄很多
nlist 改成 2500 ，index。nprobe 還是300，search 時間0。0766s
這個是nlist 改成 2500
第3個鄰居丟了，往後也丟了好長一段鄰居，難道這nlist ，index。nprobe這兩個有個合適的搭配？
改成nlist500 ，index。nprobe 還是300，search 時間0。107s，結果比最開始的nlist=1000 ，index。nprobe =300還要好，但是到了第二行還是可以看到丟了幾個
結果好很多
nlist改成2500 ，index。nprobe改成1500，search 時間0。106s，這種改法比前面的結果還要好，全對。
資料總結：
base line ：nlist=1000 ，index。nprobe=300，search =0。0818s，
nlist=500 ，index。nprobe=300，search =0。107s，召回效果比baseline好，同時search time 增加。
nlist=1000 ，index。nprobe=3，search time 0。0404949s，結果有點慘不忍睹了，同時search time 下降。
nlist=2500 ，index。nprobe=300，search =0。0766s，召回效果比baseline差好多，同時search time下降。
nlist=2500 ，index。nprobe=1500，search =0。106s，召回效果比baseline好非常多，同時search time上升，也比nlist=500 ，index。nprobe=300召回效果好，時間短。+
結論：
1。index。nprobe 越大，search time 越長，召回效果越好。
2。nlist=2500，不見得越大越好，需要與nprobe 配合，這兩個引數同時大才有可能做到好效果。
3。不管哪種倒排的時間，在search 階段都是比暴力求解快很多，0。9s與0。1s級別的差距。
以上的時間都沒有包括train的時間。也暫時沒有做記憶體使用的比較。
IndexIVFPQ
這個是少記憶體條件下使用的。
歸一化後計算的歐式距離是關於餘弦相似的單調函式，可以認為歸一化後，餘弦相似與歐式距離效果是一致的（歐式距離越小等價於餘弦相似度越大），具體證明如下（一定是L2歸一化後）。
因此可以將
求餘弦相似轉為求歐式距離
，餘弦相似的計算複雜度過高，轉為求歐式距離後，可以藉助KDTree（KNN演算法用到）或者BallTree（對高維向量友好）來降低複雜度。
