背景：當前問答模塊思路是通過BERT將用戶問題向量化后與收集的問答數(shù)據(jù)的問題也全部向量化宪萄，然后通過比較向量相似度象缀，找出最相似的問題，進而給出該問題下的答案周伦。
原有方法通過逐一比較余弦相似度郑现，每個新的輸入實例都需要與所有的訓練實例計算一次相似度并排序湃崩。當訓練集非常大的時候，計算就非常耗時接箫、耗內(nèi)存攒读，導致算法的效率降低，系統(tǒng)響應(yīng)時間過長辛友。
那么如何快速從一個大規(guī)模的向量集合中找到與待比較向量最相似的向量呢薄扁？
問題描述：從向量集合A{x1, x2, x3, x4,,,xn},找到與向量y最相似的向量
以下是博主的一些探索：
從一個集合中找到與其最相似的元素，很容易可以想到KNN的思路废累，我們可以訓練一個每個集合為單一元素的KNN模型邓梅，然后直接通過y找到最相似的即可。
當然沒有這么簡單邑滨。
我們直接用了更高級的KD-Tree日缨。
kd樹（k-dimensional樹的簡稱），是一種對k維空間中的實例點進行存儲以便對其進行快速搜索的二叉樹結(jié)構(gòu)掖看。利用kd樹可以省去對大部分數(shù)據(jù)點的搜索匣距，從而減少搜索的計算量。
kd 樹是每個節(jié)點均為k維數(shù)值點的二叉樹哎壳，其上的每個節(jié)點代表一個超平面毅待，該超平面垂直于當前劃分維度的坐標軸，并在該維度上將空間劃分為兩部分归榕，一部分在其左子樹尸红，另一部分在其右子樹。即若當前節(jié)點的劃分維度為d刹泄，其左子樹上所有點在d維的坐標值均小于當前值外里，右子樹上所有點在d維的坐標值均大于等于當前值，本定義對其任意子節(jié)點均成立特石。
from sklearn.neighborsimport KDTree
print('構(gòu)建KD tree')
k_dtree = KDTree(A, leaf_size=2)
dist, index = k_dtree.query(y, k=3)
但是發(fā)現(xiàn)實際效果并不好级乐，找到的最相似的向量并不是我們期望的最相似向量，也就是我們通過余弦相似度比較的向量县匠。
推測可能是由于kd-tree在高維數(shù)據(jù)上效果不好的原因（這里向量維度在768維），因此使用了BallTree
print('構(gòu)建Ball tree')
ball_tree = BallTree(A, leaf_size=2)
dist, index = ball_tree.query(y, k=3)
發(fā)現(xiàn)效果仍然不好。
考慮kd tree原理乞旦，其實要做的是二分查找的思路贼穆，也就是給數(shù)據(jù)做了排序，如果可以排序兰粉，我們完全就可以用二叉搜索樹故痊，進而直接排序成列表然后二分查找也可以。而排序是基于歐式距離排序的玖姑，通過查看源碼愕秫，我們知道KD tree的距離計算方式可以選擇歐式距離，閔科夫斯基距離焰络，曼哈頓距離等戴甩。
因此這里推測，可能由于BERT在構(gòu)建詞向量的時候就是通過cosine比較闪彼，而不是通過歐式距離的甜孤，所以導致轉(zhuǎn)化成的向量不適合用歐式距離的計算方式去比較其相似度。
hanxiao的bert-as-service項目中比較句子相似度也是采用余弦相似度的比較方式畏腕，可能也是這種原因缴川，沒有采用比較歐式距離的方法。
whileTrue:
?????query=input('your question:')?
?????query_vec=bc.encode([query])[0] #compute normalized dot productasscore
? ? ?score=np.sum(query_vec*doc_vecs,axis=1)/np.linalg.norm(doc_vecs,axis=1)?
?????topk_idx=np.argsort(score)[::-1][:topk]
? ? ?for idx in topk_idx:
? ? ? ? ? print('>%s\t%s'%(score[idx], questions[idx]))
