1.Locality Sensitive Hashing (LSH) 使用 Shingling + MinHashing 進(jìn)行查找

左側(cè)是字典，右側(cè)是 LSH。目的是把足夠相似的索引放在同一個(gè)桶內(nèi)。

LSH 有很多的版本，很靈活，這里先介紹第一個(gè)版本，也是原始版本

---

1. Shingling

   

2. one-hot

   

3. MinHash

   

   從 shingled 等于 1 的那一行找，找哈希值最小的，四個(gè)顏色里面得到的最終簽名是 2412.

4. 根據(jù)簽名劃分桶，對(duì)桶進(jìn)行哈希

   

5. 最后讓兩個(gè)向量在同一個(gè)桶內(nèi)進(jìn)行相似檢索

   

6. 不同的 b 值的相似度對(duì)比

   

在 FAISS 中的實(shí)現(xiàn)

import numpy as np
import faiss# 生成隨機(jī)數(shù)據(jù)集（10000個(gè)128維向量）
np.random.seed(42)
d = 128  # 向量維度
nb = 10000  # 數(shù)據(jù)集大小
nq = 5  # 查詢數(shù)量
xb = np.random.random((nb, d)).astype('float32')  # 數(shù)據(jù)庫(kù)向量
xq = np.random.random((nq, d)).astype('float32')  # 查詢向量# 創(chuàng)建 LSH 索引
**n_bits = 16  # 每個(gè)哈希簽名的比特?cái)?shù)（控制分布的細(xì)粒度）
nlist = 100  # 哈希桶的數(shù)量**# 使用余弦相似度的 LSH 索引
index = faiss.IndexLSH(d, n_bits)  # d 是向量維度，n_bits 是每個(gè)哈希簽名的比特?cái)?shù)# 為數(shù)據(jù)集添加索引
index.add(xb)# 執(zhí)行查詢
k = 5  # 要找到的最近鄰數(shù)量
D, I = index.search(xq, k)  # 查詢xq中k個(gè)最近鄰

1. n_bits(哈希簽名比特?cái)?shù))
   1. 較大的 n_bits 的值意味著哈希分布更精細(xì)，每個(gè)哈希簽名的長(zhǎng)度更長(zhǎng)，從而減少哈希沖突，提升檢索的準(zhǔn)確度。
2. nlist(桶的數(shù)量)
   1. 代碼中未顯示 nlist 調(diào)節(jié)，但你可以通過構(gòu)建帶有倒排表（IVF）的 LSH 來設(shè)置 nlist。增加 nlist 可以減少每個(gè)桶中的向量數(shù)量，提高查詢速度，但會(huì)增加空間分配的細(xì)粒度。

2.PQ

補(bǔ)充概念

code

code 指數(shù)據(jù)點(diǎn)被量化后生成的一個(gè)索引值，表示該數(shù)據(jù)點(diǎn)在量化器所創(chuàng)建的 碼本(codebook) 中的位置

當(dāng)數(shù)據(jù)經(jīng)過量化之后，他被映射到碼本中的一個(gè) 質(zhì)心(centroid),每個(gè)質(zhì)心有一個(gè)對(duì)應(yīng)的索引，這個(gè)索引就是 code

例如，如果有 64 個(gè)質(zhì)心，那么每個(gè)數(shù)據(jù)點(diǎn)的 code 將是 0 到 63 之間的一個(gè)整數(shù)，表示該數(shù)據(jù)點(diǎn)最接近哪個(gè)質(zhì)心。

Codebook

碼本（codebook） 是一組質(zhì)心的集合，用于表示數(shù)據(jù)集中的典型向量或原型。碼本中的每個(gè)質(zhì)心是一個(gè)向量，代表了量化后的數(shù)據(jù)點(diǎn)可以映射到的“典型”位置。

質(zhì)心（centroid） 是通過聚類算法（如 k-means）在訓(xùn)練階段學(xué)到的，用來表示數(shù)據(jù)點(diǎn)的分布。

碼本的大小由質(zhì)心的數(shù)量決定。例如，一個(gè)碼本可能包含 64 個(gè)質(zhì)心，表示數(shù)據(jù)可以被量化為 64 種不同的狀態(tài)。

總結(jié)

Code 是數(shù)據(jù)點(diǎn)量化后對(duì)應(yīng)質(zhì)心的索引，用來表示該數(shù)據(jù)點(diǎn)最接近的質(zhì)心。

Codebook 是質(zhì)心的集合，表示數(shù)據(jù)點(diǎn)被聚類后可以映射到的典型位置。

1.摘要

其思想是將空間分解為低維子空間的笛卡爾積，并分別對(duì)每個(gè)子空間進(jìn)行插值。

向量由其子空間量化索引組成的短碼表示。

兩個(gè)向量之間的歐氏距離可以有效地從它們的代碼估計(jì)。非對(duì)稱版本提高了精度，因?yàn)樗?jì)算了向量和代碼之間的近似距離。

實(shí)驗(yàn)結(jié)果表明，我們的方法有效地搜索最近的鄰居，特別是在與倒排文件系統(tǒng)相結(jié)合。

2.引言

已經(jīng)提出了幾種多維索引方法，例如流行的 KD樹[5]或其他分支和界限技術(shù)，以減少搜索時(shí)間。然而，對(duì)于高維，事實(shí)證明這種方法并不比窮舉距離計(jì)算更有效，其復(fù)雜度為$O(nD)$。

在本文中，我們利用量化來構(gòu)造短碼。

目標(biāo)是使用向量到質(zhì)心距離來估計(jì)距離，例如，查詢向量不被量化，code 僅被分配給數(shù)據(jù)庫(kù)向量。這減少了量化噪聲，并隨后提高了搜索質(zhì)量。為了獲得精確的距離，必須限制量化誤差。因此，質(zhì)心的總數(shù)k應(yīng)該足夠大。這就提出了關(guān)于如何學(xué)習(xí)碼本和分配向量的若干問題。

首先，學(xué)習(xí)量化器所需的樣本數(shù)量是巨大的，即，幾次 K。

其次，算法本身的復(fù)雜性是禁止的。

最后，地球上可用的計(jì)算機(jī)內(nèi)存量不足以存儲(chǔ)表示質(zhì)心的浮點(diǎn)值。

3.背景

1. 向量量化

   向量量化是一個(gè)破壞的過程，他會(huì)減少表示空間的基數(shù)，尤其是輸入數(shù)據(jù)是實(shí)數(shù)的時(shí)候

   形式上，量化器是將 D 維向量 $x$ 映射到向量 q ( x ) ∈ C = { c i , i ∈ I } , I = 0... k ? 1 q(x)\in C = \{c_i, i\in I\}, I=0...k-1 q(x)∈C={ci?,i∈I},I=0...k?1 的函數(shù) $q$。

   再現(xiàn)值 $c_i$ 被稱為質(zhì)心。再現(xiàn)值的集合 $C$ 是大小為 $k$ 的碼本。

   映射到給定索引 $i$ 的向量的集合 $V_i$ 被稱為（Voronoi）單元

   量化器的 $k$ 個(gè)單元形成 $R^D$ 的分區(qū)。根據(jù)定義，位于相同單元 $V_i$ 中的所有向量由相同質(zhì)心 $c_i$ 重構(gòu)。

   量化器的評(píng)價(jià)指標(biāo)通常通過輸入向量 $x$ 和其再現(xiàn)值 $q(x)$ 之間的均方誤差 MSE 來測(cè)量。

   

   其中，$d(x,y)=||x?y||$，$p(x)$ 是相關(guān)變量 X 的概率分布函數(shù)

   為了使量化器是最佳的，它必須滿足兩個(gè)屬性稱為 Lloyd 最優(yōu)性條件。首先，向量 x 必須量化到其最近的碼本質(zhì)心，根據(jù)歐幾里得距離：

   

   因此，單元由超平面界定。

   第二個(gè) Lloyd 條件是重建值必須是位于 Voronoi 單元中的向量的期望：

   

   Lloyd 量化器對(duì)應(yīng)于 k 均值聚類算法，通過迭代地將訓(xùn)練集的向量分配給質(zhì)心并從分配的向量重新估計(jì)這些質(zhì)心來找到接近最優(yōu)的碼本。

   在沒有任何進(jìn)一步處理（熵編碼）的情況下，存儲(chǔ)索引值的存儲(chǔ)器成本是 $lo{g}_{2}k$ bit 。因此，對(duì)于k使用2的冪是方便的，因?yàn)榱炕鳟a(chǎn)生的代碼存儲(chǔ)在二進(jìn)制存儲(chǔ)器中。

2. 乘積量化

   考慮 128 維向量。一個(gè)量化器產(chǎn)生 64bits 的 code，即包含 $2^{64}$ 個(gè)質(zhì)心。大的離譜，內(nèi)存不能接受。

   乘積量化是一個(gè)處理這種問題的解決方案。

   輸入向量 $x$ 被分成 $m$ 個(gè)不同的子向量 $u_j$, 維度為 $D^{?}=D/m$，$D$ 需要是 $m$ 的倍數(shù)。

   使用 $m$ 個(gè)不同的量化器分別量化 子向量。

   

   D 維向量 x 的被量化如圖

   乘積量化器的再現(xiàn)值由乘積索引集合 $I=I_1\times ...\times I_m$ 的元素來標(biāo)識(shí)。因此，碼本被定義為笛卡爾積

   

   并且該集合的質(zhì)心是 M 個(gè)子量化器的質(zhì)心的級(jí)聯(lián)。

   從現(xiàn)在開始，我們假設(shè)所有的子量化器都有相同的有限數(shù)量 k 的再現(xiàn)值。在這種情況下，質(zhì)心的總數(shù)由下式給出：

   

   注意，在 m = D的極端情況下，向量 x 的分量全部被單獨(dú)量化。然后，乘積量化器變成標(biāo)量量化器，其中與每個(gè)分量相關(guān)聯(lián)的量化函數(shù)可以不同。

   乘積量化器的優(yōu)點(diǎn)是從幾個(gè)小的質(zhì)心集合中產(chǎn)生一個(gè)大的質(zhì)心集合：與子量化器相關(guān)聯(lián)的質(zhì)心集合。

   

   k 是質(zhì)心數(shù)，假設(shè) $k=2^{64}$ 的情況下，效果還是相當(dāng)可觀的

4.量化搜索

見圖2。
對(duì)稱和非對(duì)稱距離計(jì)算的圖解。利用距離$d(q(x),q(y))$（左）或距離$d(x,q(y))$（右）來估計(jì)距離 $d(x,y)$。
距離上的均方誤差平均地由量化誤差限定。

最近鄰搜索取決于查詢向量和數(shù)據(jù)庫(kù)向量之間的距離，或者等效地平方距離。

1. 使用量化 code 計(jì)算距離

   讓我們考慮查詢向量 x 和數(shù)據(jù)庫(kù)向量 y。我們提出了兩種方法來計(jì)算這些向量之間的近似歐氏距離，對(duì)稱和非對(duì)稱的。有關(guān)說明，請(qǐng)參見圖2。

   Symmetric distance computation (SDC):

   向量 x 和 y 都由它們各自的質(zhì)心 q(x) 和 q(y) 表示，距離 d(x,y) 近似為距離$d(q(x)，q(y))$.

   

2. Asymmetric distance computation (ADC)

   數(shù)據(jù)庫(kù)向量 $y$ 由 $q(y)$ 表示，但查詢 $x$ 未被編碼。距離 $d(x，y)$ 近似為距離$d(x,q(y))$，其使用分解計(jì)算

   

   表 II 總結(jié)了不同步驟中的復(fù)雜度，涉及了 $x$ 的 $k$ 個(gè)最近鄰鄰居，在 $n=|y|$ 的數(shù)據(jù)集 $Y$中?？梢钥闯?#xff0c;SDC 和 ADC 具有相同的查詢準(zhǔn)備成本，這與數(shù)據(jù)集大小 n 無(wú)關(guān)。

   

   與 ADC 相比，SDC 的唯一優(yōu)點(diǎn)是限制了與查詢相關(guān)的內(nèi)存使用，因?yàn)椴樵兿蛄渴怯?code 定義的。這是大多數(shù)情況下不相關(guān)的，然后應(yīng)該使用非對(duì)稱版本，它獲得了類似的復(fù)雜性較低的距離失真。我們將在本節(jié)的其余部分重點(diǎn)介紹 ADC。

3. 非詳盡搜索

   

   圖5.基于非對(duì)稱距離計(jì)算的倒排文件（IVFADC）索引系統(tǒng)概述。上圖：插入載體。底部：搜索。

5.總結(jié)

上面有點(diǎn)亂，總結(jié)一下

1. 核心思想

   PQ 的關(guān)鍵思想是將一個(gè)高維向量分成若干低維的子向量，然后對(duì)每個(gè)子向量分別進(jìn)行量化。

   • 高維向量分割：假設(shè)你有一個(gè) $D$ 維的向量，PQ 會(huì)將這個(gè)向量分成 $m$ 個(gè)子向量。每個(gè)子向量的維度為 $D/m$ 。
   • 每個(gè)子向量獨(dú)立量化：每個(gè)子向量分別用自己的碼本(codebook)進(jìn)行量化。每個(gè)碼本有 k 個(gè)質(zhì)心(centroid)，也就是 k 種可能的量化結(jié)果
   • 存儲(chǔ)方式：每個(gè)高維向量的量化結(jié)果是 m 個(gè)子向量的量化碼(code)的組合。這樣。存儲(chǔ)一個(gè)向量時(shí)，不再存儲(chǔ)整個(gè)向量。而是存儲(chǔ) m 個(gè)索引

2. 工作流程

   假設(shè)有一個(gè) D 維向量 x，使用 PQ 進(jìn)行量化。

   1. 分割向量：將 x 劃分為 m 個(gè)子向量 $x=(x_1,\dots ,x_m)$，每個(gè)子向量維度時(shí) $D/m$
   2. 對(duì)每個(gè)子向量進(jìn)行獨(dú)立量化：
      • 為每個(gè)子向量訓(xùn)練一個(gè)量化器，生成對(duì)應(yīng)的碼本(centroid)
      • 將每個(gè)子向量 $x_i$ 用碼本中的質(zhì)心替代，即找到與該子向量最近的質(zhì)心，返回質(zhì)心的索引
   3. 存儲(chǔ)結(jié)果：量化后，將 x 表示為一個(gè)由 m 個(gè)量化索引組成的組合，這些索引指向各自子向量的質(zhì)心
      1. 查詢階段：在查詢時(shí)，將查詢向量分塊，分別與每個(gè)子向量的碼本進(jìn)行距離計(jì)算。最后，將每個(gè)子向量的距離累加，得到總距離。

6.faiss 中實(shí)現(xiàn)

import faiss# 維度
d = 128# 定義PQ量化器，分成m個(gè)子空間，每個(gè)子空間使用k個(gè)質(zhì)心
m = 8  # 子空間數(shù)量
k = 256  # 每個(gè)子空間使用256個(gè)質(zhì)心（8比特碼）# 創(chuàng)建PQ索引
index = faiss.IndexPQ(d, m, k)# 訓(xùn)練PQ索引（假設(shè)有xb作為訓(xùn)練數(shù)據(jù)）
index.train(xb)# 添加數(shù)據(jù)
index.add(xb)# 查詢
D, I = index.search(xq, k)  # 查詢xq中的k個(gè)近鄰

1. m（子空間數(shù)量）
   1. 將 原始向量劃分為 m 個(gè)子空間，每個(gè)空間獨(dú)自量化。
   2. m 需要被 d 整除
   3. m 越大，單個(gè)子向量維度越小，量化誤差可能越大；存儲(chǔ)開銷和搜索速度可能降低。
   4. 較小的 m 會(huì)保留更多原始向量的結(jié)構(gòu)信息，但會(huì)增加存儲(chǔ)和查詢的計(jì)算復(fù)雜度。
2. k（碼表大小）
   1. 每個(gè)子空間使用的質(zhì)心數(shù)，即每個(gè)子向量被量化為 k 種不同的值。常見的選擇是 k = 256（8 比特編碼），也可以選擇其他值
   2. k 越大，量化的精度越高，但存儲(chǔ)需求和計(jì)算復(fù)雜度也會(huì)增加。常見的值為 256

3.HNSW

1.解決的問題

• 高維空間中的最近鄰搜索問題：在高維空間中，傳統(tǒng)的最近鄰搜索算法（如K-Nearest Neighbor Search，K-NNS）由于“維度的詛咒”而變得低效。HNSW 通過引入層次結(jié)構(gòu)來克服這個(gè)問題，提供了更好的搜索性能。
• 近似搜索中的準(zhǔn)確性與效率平衡：在近似最近鄰搜索中，需要在搜索的準(zhǔn)確性（召回率）和搜索效率之間找到平衡。HNSW 通過層次化的結(jié)構(gòu)和啟發(fā)式鄰居選擇策略，提高了搜索的效率和準(zhǔn)確性。
• 大規(guī)模數(shù)據(jù)集的可擴(kuò)展性：隨著數(shù)據(jù)集規(guī)模的增長(zhǎng)，傳統(tǒng)的ANNS算法可能會(huì)遇到性能瓶頸。HNSW 通過其層次化的設(shè)計(jì)，實(shí)現(xiàn)了對(duì)大規(guī)模數(shù)據(jù)集的可擴(kuò)展性。

2.原理

HNSW 的核心思想是構(gòu)建一個(gè)多層次的圖結(jié)構(gòu)，每個(gè)層次包含一個(gè)嵌套的鄰近圖（proximity graph），用于存儲(chǔ)元素的子集。

Fig. 1 HNSW的圖解。
搜索從頂層的元素開始（顯示為紅色）。紅色箭頭顯示貪婪算法從入口點(diǎn)到查詢的方向（顯示為綠色）。

每個(gè)元素在圖中的最大層數(shù)是隨機(jī)選擇的，遵循指數(shù)衰減的概率分布。這種設(shè)計(jì)允許在保持圖的連通性的同時(shí)，通過不同長(zhǎng)度尺度的鏈接分離來提高搜索性能。

搜索過程從最高層（具有最長(zhǎng)鏈接的層）開始，然后根據(jù)需要逐步向下層搜索，直到達(dá)到底層。

這種“放大-縮小”（zoom-out and zoom-in）的策略有助于快速定位到目標(biāo)區(qū)域，并在局部區(qū)域內(nèi)進(jìn)行精確搜索。

HNSW還采用了一種啟發(fā)式方法來選擇鄰近圖中的鄰居節(jié)點(diǎn)，這種方法不僅考慮了候選節(jié)點(diǎn)與查詢點(diǎn)的距離，還考慮了候選節(jié)點(diǎn)之間的距離，以創(chuàng)建多樣化的連接。這有助于在高度聚集的數(shù)據(jù)中保持全局連通性，并提高搜索的準(zhǔn)確性。

圖2.用于為兩個(gè)孤立的集群選擇圖鄰居的啟發(fā)式圖示。
在簇 1 的邊界上插入一個(gè)新的元素，該元素的所有最近鄰居都屬于簇 1，因此丟失了簇之間的 Delaunay 圖的邊。然而，試探法從簇 2 中選擇元素 e2，從而在插入的元素與來自簇 1 的任何其他元素相比最接近 e2 的情況下保持全局連通性。

3.總結(jié)

HNSW 會(huì)構(gòu)建一個(gè) 分層的 導(dǎo)航小世界圖 來加速搜索。

1. 小世界網(wǎng)絡(luò)

   

   這是一個(gè)NSW圖，圖中兩個(gè)頂點(diǎn)的距離為 4 跳。

   如圖，這允許通過少數(shù)跳躍，能夠快速遍歷網(wǎng)絡(luò)中的大部分節(jié)點(diǎn)

2. 分層導(dǎo)航結(jié)構(gòu)

   HNSW 使用多層圖結(jié)構(gòu)，其中每一層是一個(gè)稀疏圖，越往上層圖越稀疏、節(jié)點(diǎn)數(shù)越少，而下層的圖更密集，包含更多節(jié)點(diǎn)：

   • 頂層（高層）：包含少數(shù)數(shù)據(jù)點(diǎn)，節(jié)點(diǎn)之間的連通性較弱。這里的作用是快速瀏覽整個(gè)數(shù)據(jù)集。
   • 底層（低層）：連接更密集的數(shù)據(jù)點(diǎn)，允許更精確的搜索。

   每一個(gè)數(shù)據(jù)點(diǎn)都會(huì)隨機(jī)分配到不同的層中，層次越高，點(diǎn)的密度越低。搜索從最頂層開始，依次向下跳轉(zhuǎn)，逐漸進(jìn)入更加密集的底層圖，最終完成近似最近鄰搜索。

3. 鄰居連接和隨機(jī)跳躍

   為了在各層圖中有效進(jìn)行導(dǎo)航，HNSW 使用了“隨機(jī)鄰居連接”的策略。

   每個(gè)點(diǎn)通過固定數(shù)量的邊與其他點(diǎn)連接，形成鄰居節(jié)點(diǎn)集。這些連接不僅僅局限于靠近的點(diǎn)，還包含一定的隨機(jī)性，從而確保圖的連通性和避免局部最優(yōu)。

   • 隨機(jī)性：初始構(gòu)建圖時(shí)，每個(gè)節(jié)點(diǎn)根據(jù)一定的概率與其他節(jié)點(diǎn)連接，特別是在高層圖中，隨機(jī)連接允許跨越較大距離的跳躍。
   • 局部連接：在較低層次圖中，節(jié)點(diǎn)之間的連接更多是局部的，與幾何上相近的節(jié)點(diǎn)形成密集連接。

4. 搜索過程

   搜索過程可以分為以下幾個(gè)階段：

   1. 從最高層開始：從頂層的一個(gè)起始節(jié)點(diǎn)出發(fā)，使用貪心搜索逐步尋找距離目標(biāo)向量最近的鄰居。
   2. 逐層向下跳躍：一旦在頂層找到距離目標(biāo)較近的節(jié)點(diǎn)，搜索算法會(huì)轉(zhuǎn)移到下一層，繼續(xù)在下一層尋找更接近目標(biāo)的鄰居。這種逐層跳躍過程可以加速搜索，因?yàn)槊繉拥膱D連接性不同，可以提供全局導(dǎo)航和局部細(xì)化。
   3. 局部搜索：當(dāng)搜索到最底層時(shí)，圖的密度更高，搜索會(huì)在局部鄰居之間進(jìn)行更精確的距離計(jì)算，最終找到目標(biāo)的近似最近鄰。

4.代碼

M = 16 # 每個(gè)頂點(diǎn)的連接數(shù)
ef_search = 8 # 搜索的深度
ef_construction = 64 # 構(gòu)建時(shí)的擴(kuò)展因子，決定了在構(gòu)建圖時(shí)為每個(gè)點(diǎn)找到最近鄰的搜索深度index = faiss.IndexHNSWFlat(d, M)index.hnsw.efSearch = ef_search
index.hnsw.efConstruction = ef_constructionindex.add(xb)D, I = index.search(xq, k)

1. M(最大連接數(shù))
   1. 每個(gè)節(jié)點(diǎn)最大的連接邊數(shù)。
   2. 值越大，搜索的結(jié)果更精確，但構(gòu)建和查詢的成本會(huì)變大。通常 16 - 48
2. efConstruction(構(gòu)建階段的擴(kuò)展因子）)
   1. 控制圖的構(gòu)建質(zhì)量
   2. 值越大，構(gòu)建的圖結(jié)構(gòu)越精細(xì)，精度越高，但構(gòu)建時(shí)間增加。
   3. efConstruction 通常設(shè)定為大于 M 的值。
   4. 其實(shí)設(shè)置一個(gè)比較大的值最好
3. efSearch(查詢階段的擴(kuò)展因子)
   1. 控制查詢階段的搜索廣度。
   2. 值越大，搜索的鄰居節(jié)點(diǎn)越多，精度越高，但查詢速度變慢
   3. 常為 50 - 200

4.IVF

1.解決的問題

IVF（Inverted File Index）主要是為了解決大規(guī)模、高維向量數(shù)據(jù)集的最近鄰搜索問題。

在高維數(shù)據(jù)集上，執(zhí)行精確的最近鄰搜索代價(jià)極高，尤其是當(dāng)數(shù)據(jù)量大、維度高時(shí)，計(jì)算距離的成本成指數(shù)級(jí)增長(zhǎng)，導(dǎo)致搜索時(shí)間和內(nèi)存占用都難以接受。

2.原理

1. 數(shù)據(jù)分簇(clustering)

   IVF 的核心思想是聚類。通過將數(shù)據(jù)點(diǎn)分成多個(gè)簇，算法可以大大減少在查詢時(shí)需要計(jì)算的向量數(shù)量。

   1. 使用聚類進(jìn)行分簇：常用 k-means。將數(shù)據(jù)集劃分為多個(gè)簇，每個(gè)簇用一個(gè)質(zhì)心(centroid) 表示。
   2. 構(gòu)建倒排文件：一旦聚類完成，算法會(huì)為每個(gè)簇構(gòu)建一個(gè)倒排列表。每個(gè)倒排索引列表中存儲(chǔ)了歸屬于該簇的所有向量的 ID。這類似于搜索引擎中倒排索引的結(jié)構(gòu)，用于快速定位相關(guān)文檔
   3. 數(shù)據(jù)劃分：數(shù)據(jù)集中的每個(gè)向量會(huì)被分配到某個(gè)簇，即它與該簇的質(zhì)心距離最近。這樣，整個(gè)數(shù)據(jù)集被劃分為多個(gè)部分，每部分對(duì)應(yīng)一個(gè)簇。

   倒排索引
   倒排索引是一種數(shù)據(jù)結(jié)構(gòu)，它將向量空間中的特征（通常是聚類中心或代表向量）映射到包含該特征的所有數(shù)據(jù)點(diǎn)（向量）的列表。這種結(jié)構(gòu)通過預(yù)先對(duì)數(shù)據(jù)進(jìn)行分組，實(shí)現(xiàn)了快速的近似最近鄰搜索，特別適用于高維向量空間中的大規(guī)模數(shù)據(jù)檢索。
   例如

   傳統(tǒng)索引（正向索引）：

   • 條目：“番茄炒蛋的做法 A” -> 頁(yè)碼：10-20頁(yè)

   倒排索引：

   • “番茄” -> 條目列表：{“番茄炒蛋的做法 A”, …}
   • “炒蛋” -> 條目列表：{“番茄炒蛋的做法 A”, …}

2. 查詢階段

   在進(jìn)行搜索時(shí)，IVF 只需在部分簇中執(zhí)行最近鄰搜索，從而大大減少了距離計(jì)算的次數(shù)。搜索過程如下：

   1. 查找最近的質(zhì)心：首先，查詢向量會(huì)與所有質(zhì)心進(jìn)行距離計(jì)算，從中選出與查詢向量距離最近的幾個(gè)質(zhì)心。這一步用于粗略定位查詢向量可能所在的簇。通常選擇距離最近的 nprobe 個(gè)質(zhì)心，而不是所有質(zhì)心。
   2. 在對(duì)應(yīng)的簇中搜索：選定最近的質(zhì)心后，搜索會(huì)在這些對(duì)應(yīng)的簇中查找最近鄰。由于這些簇包含的數(shù)據(jù)點(diǎn)較少，算法只需在這些簇內(nèi)進(jìn)行精細(xì)的距離計(jì)算，從而有效減少了搜索范圍。
   3. 返回最近鄰：通過在選中的簇中執(zhí)行最近鄰搜索，最終返回最接近查詢向量的幾個(gè)數(shù)據(jù)點(diǎn)

3.代碼

nlist = 128 # 質(zhì)心數(shù)量quantizer = faiss.IndexFlatIP(d) # 可以減少內(nèi)存占用，并提高搜索速度
index = faiss.IndexIVFFlat(quantizer, d, nlist)index.train(xb) # 需要訓(xùn)練！index.add(xb)index.nprobe = 1%%time
D, I = index.search(xq, k)

1. nlist(聚類數(shù)量)
   1. 在訓(xùn)練階段創(chuàng)建的聚類(桶)的數(shù)量
   2. nlist 的值越大，劃分的簇越多，簇內(nèi)的向量數(shù)量就越少，查詢速度更快，但索引構(gòu)建時(shí)間和內(nèi)存占用可能會(huì)增加。
   3. 通常 nlist 的選擇取決于數(shù)據(jù)的規(guī)模，經(jīng)驗(yàn)上建議 nlist 與數(shù)據(jù)量的平方根成比例
2. nprobe（探測(cè)簇的數(shù)量）
   1. 在查詢時(shí)，nprobe 控制查詢向量要搜索的簇的數(shù)量。
   2. nprobe 值越大，查詢精度越高，但計(jì)算成本也相應(yīng)增加。
   3. 一般而言，可以通過調(diào)節(jié) nprobe 來在搜索精度和速度之間找到平衡