knn search algorithm comparison下載 - knn search algorithm comparison源代碼下載

knn search algorithm comparison

其他源碼

1.0.0

下載

KNN搜索算法比較

1951年推出的K-Nearest鄰居（K-NN）算法已被廣泛用於分類和回歸任務。核心概念涉及將K最相似的實例（鄰居）識別到數據集中的給定查詢點，並使用這些鄰居進行預測或分類。近年來，矢量數據庫和向量索引的重要性已經增長，特別是在處理大量文本和其他數據數據集中，信息檢索以支持大型語言模型（LLMS）。該應用程序的一個突出例子是檢索儀器（RAG）。

該項目比較了各種數據集大小和尺寸的不同K-NN搜索算法的性能。比較的算法是：

KD-Tree
球樹
蠻力（完整的KNN）
HNSW（層次可導航的小世界）

算法解釋

KD-Tree（K維樹）：
- 用於在K維空間中組織點的空間分分數據結構。
- 通過遞歸將空間沿不同的維度劃分為二進制樹。
- 低維空間的有效效率（通常<20維）。
- 搜索的平均時間複雜度：O（log n），其中n是點數。
- 由於“維度的詛咒”，在高維空間中的有效性較差。示例：在2D空間中，KD-Tree可能會垂直劃分平面，然後在每個級別上交替：
```
   y
   |
4  |    C
   |  A   D
2  |    B
   |___________
   0    2    4  x
```
點：A（1,3），B（3,1），C（4,3），D（3,3）樹結構：root（x = 2） - >左（y = 2） - >右（x = 3）
球樹：
- 將分區的二進制樹數據結構指向嵌套的超球。
- 每個節點代表一個包含點子集的球（超孔）。
- 對於高維空間，比KD-Tree更有效。
- 搜索的平均時間複雜性：O（log n），但恆定因子的恆定因子比KD-Tree更高。
- 當尺寸> 20時，通常比KD-Tree的表現更好。例如：在2D空間中，球樹可能會產生嵌套圓：
```
   y
   |
4  |    (C)
   |  (A)  (D)
2  |    (B)
   |___________
   0    2    4  x
```
外圓包含所有點，內圓圈劃分子集。
完整的KNN（蠻力）：
- 計算從查詢點到數據集中所有其他點的距離。
- 易於實現，但對於大型數據集而言，計算昂貴。
- 時間複雜度：O（n * d），其中n是點的數量，d是尺寸的數量。
- 隨著數據集大小或維數的增加而變得效率低下。
- 保證找到最接近的鄰居。示例：對於查詢點q（2,2）和k = 2：
```
   y
   |
4  |    C
   |  A   D
2  |----Q--B
   |___________
   0    2    4  x
```
計算距離：QA = 1.41，QB = 1，QC = 2.24，QD = 1.41結果：最近的2個鄰居是B和A（或D）
HNSW（層次可通航的小世界）：
- 一個大約最近的鄰居搜索算法。
- 構建一個多層圖結構，以進行有效的導航。
- 提供搜索速度和準確性之間的權衡。
- 在高維空間和大數據集中表現良好。
- 搜索的平均時間複雜性：O（log n），但常數比基於樹的方法更好。
- 通過犧牲一些準確性，可以更快地進行搜索。示例：HNSW層的簡化2D表示：
```
 Layer 2:   A --- C
           |
Layer 1:   A --- B --- C
           |    |    |
Layer 0:   A --- B --- C --- D --- E
```
搜索從頂層的隨機點開始，然後下降，探索每個級別的鄰居直到到達底部。

這些算法之間的選擇取決於數據集大小，維度，所需的準確性和查詢速度。 KD-Tree和Ball樹提供了精確的結果，並且對於低到中等的尺寸有效。完整的KNN很簡單，但對於大型數據集而言變得很慢。 HNSW在速度和準確性之間提供了良好的平衡，尤其是對於高維數據或大型數據集提供了良好的平衡。

安裝

克隆這個存儲庫：

 git clone https://github.com/yourusername/knn-search-comparison.git
cd knn-search-comparison

創建虛擬環境（可選但建議）：

 python -m venv venv
source venv/bin/activate  # On Windows, use `venvScriptsactivate`

安裝所需的依賴項：
```
 pip install -r requirements.txt
```
這將安裝requirements.txt文件中列出的所有必要軟件包，包括numpy，scipy，scikit-learn，hnswlib，tabulate和tqdm。

用法

使用默認參數運行比較測試：

 python app.py

您還可以使用命令行參數自定義測試參數：

 python app.py --vectors 1000 10000 100000 --dimensions 4 16 256 --num-tests 5 --k 5

可用參數：

--vectors ：測試矢量計數列表（默認值：1000，2000，5000，10000，20000，50000，100000，200000）
--dimensions ：要測試的尺寸列表（默認值：4 16 256 1024）
--num-tests ：每種組合要運行的測試數（默認值：10）
--k ：搜索最近的鄰居數（默認：10）

該腳本將在執行過程中顯示進度條，使您估算剩餘時間。

可以隨時按CTRL+C來中斷該腳本。即使在耗時的操作中，例如構建HNSW索引，它也將嘗試優雅地退出。

輸出

該腳本將在控制台中顯示進度並結果。完成後，您會看到：

矢量數和維度的每種組合的結果摘要，包括：
- 為KD-Tree，Ball Tree和HNSW索引建立時間
- 每種算法的平均搜索時間
所有結果表
包含詳細結果的CSV文件的位置

單個組合的示例輸出：

 Results for 10000 vectors with 256 dimensions:
KD-Tree build time:       0.123456 seconds
Ball Tree build time:     0.234567 seconds
HNSW build time:          0.345678 seconds
KD-Tree search time:      0.001234 seconds
Ball Tree search time:    0.002345 seconds
Brute Force search time:  0.012345 seconds
HNSW search time:         0.000123 seconds

最終結果表和CSV文件將包括每種算法的構建時間和搜索時間，從而可以全面比較不同矢量計數和維度的性能。