ดาวน์โหลด knn search algorithm comparison - ดาวน์โหลดซอร์สโค้ด knn search algorithm comparison

knn search algorithm comparison

ซอร์สโค้ดอื่น ๆ

1.0.0

ดาวน์โหลด

การเปรียบเทียบอัลกอริทึมการค้นหา KNN

อัลกอริทึมเพื่อนบ้าน K-Nearest (K-NN) ซึ่งเปิดตัวในปี 1951 ได้ถูกนำมาใช้อย่างกว้างขวางสำหรับการจำแนกประเภทและงานการถดถอย แนวคิดหลักเกี่ยวข้องกับการระบุอินสแตนซ์ที่คล้ายกันมากที่สุด K (เพื่อนบ้าน) ไปยังจุดค้นหาที่กำหนดภายในชุดข้อมูลและการใช้เพื่อนบ้านเหล่านี้เพื่อทำการคาดการณ์หรือการจำแนกประเภท ในช่วงไม่กี่ปีที่ผ่านมาความสำคัญของฐานข้อมูลเวกเตอร์และดัชนีเวกเตอร์ได้เพิ่มขึ้นโดยเฉพาะอย่างยิ่งสำหรับการดึงข้อมูลเพื่อรองรับแบบจำลองภาษาขนาดใหญ่ (LLMS) ในการประมวลผลชุดข้อมูลที่กว้างขวางของข้อความและข้อมูลอื่น ๆ ตัวอย่างที่โดดเด่นของแอปพลิเคชันนี้คือการเรียกคืนการเพิ่มขึ้น (RAG)

โครงการนี้เปรียบเทียบประสิทธิภาพของอัลกอริทึมการค้นหา K-NN ที่แตกต่างกันในขนาดและขนาดชุดข้อมูลต่างๆ อัลกอริทึมที่เปรียบเทียบคือ:

KD-Tree
ต้นบอล
พลังเดรัจฉาน (เต็ม knn)
HNSW (โลกขนาดเล็กที่นำทางได้ตามลำดับชั้น)

คำอธิบายอัลกอริทึม

KD-Tree (K-dimensional Tree):
- โครงสร้างข้อมูลการแบ่งพื้นที่สำหรับการจัดระเบียบจุดในพื้นที่ K-mimensional
- สร้างต้นไม้ไบนารีโดยแยกพื้นที่ออกซ้ำตามมิติที่แตกต่างกัน
- มีประสิทธิภาพสำหรับช่องว่างมิติต่ำ (โดยทั่วไป <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) โครงสร้างต้นไม้: รูท (x = 2) -> ซ้าย (y = 2) -> ขวา (x = 3)
ต้นไม้บอล:
- โครงสร้างข้อมูลต้นไม้ไบนารีที่พาร์ติชันชี้ไปที่ hyperspheres ซ้อนกัน
- แต่ละโหนดแสดงถึงลูกบอล (hypersphere) ที่มีส่วนย่อยของจุด
- มีประสิทธิภาพมากกว่าต้นไม้ KD สำหรับพื้นที่มิติสูง
- ความซับซ้อนของเวลาเฉลี่ยสำหรับการค้นหา: O (log n) แต่มีปัจจัยคงที่สูงกว่า KD-Tree
- โดยทั่วไปจะทำงานได้ดีกว่า KD-Tree เมื่อขนาด> 20. ตัวอย่าง: ในพื้นที่ 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) แต่มีค่าคงที่ที่ดีกว่าวิธีการตามต้นไม้
- ช่วยให้การค้นหาเร็วขึ้นโดยการลดความแม่นยำบางอย่าง ตัวอย่าง: การเป็นตัวแทน 2D ที่เรียบง่ายของเลเยอร์ HNSW:
```
 Layer 2:   A --- C
           |
Layer 1:   A --- B --- C
           |    |    |
Layer 0:   A --- B --- C --- D --- E
```
การค้นหาเริ่มต้นที่จุดสุ่มในชั้นบนสุดและลงมาสำรวจเพื่อนบ้านในแต่ละระดับจนกระทั่งถึงด้านล่าง

ตัวเลือกระหว่างอัลกอริทึมเหล่านี้ขึ้นอยู่กับขนาดชุดข้อมูลมิติความแม่นยำที่ต้องการและความเร็วในการสืบค้น KD-Tree และ Ball Tree ให้ผลลัพธ์ที่แน่นอนและมีประสิทธิภาพสำหรับมิติต่ำถึงปานกลาง Full 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 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 : รายการของเวกเตอร์นับเพื่อทดสอบ (ค่าเริ่มต้น: 1,000, 2000, 5000, 10,000, 100000, 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 จะรวมทั้งเวลาสร้างและเวลาการค้นหาสำหรับแต่ละอัลกอริทึมเพื่อให้สามารถเปรียบเทียบประสิทธิภาพที่ครอบคลุมในการนับและมิติที่แตกต่างกัน