การค้นหาแบบเบสท์บินเฟิร์สท์

การค้นแบบเบสท์บินเฟิร์สท์ (อังกฤษ: Best Bin First) เป็นขั้นตอนวิธีการค้นหาที่ใช้ในการหาจุดที่อยู่ใกล้ที่สุด (nearest neighbor search) โดยประมาณในปริภูมิหลายมิติ โดยขั้นตอนวิธีนี้มีการประยุกต์มาจากต้นไม้เคดี (k-d tree) ทำให้การค้นมีประสิทธิภาพและเร็วมากขึ้น นอกจากนี้ยังเป็นขั้นตอนวิธีการค้นหาที่สามารถนำไปใช้ได้จริงในทางปฏิบัติ อย่างเช่น ใช้กับการตรวจหาลักษณะเด่นแบบซิฟท์ (SIFT) ซึ่งเป็นหนึ่งในขั้นตอนวิธีในการตรวจหาลักษณะเด่น (feature detection) ในเรื่องคอมพิวเตอร์วิทัศน์ (computer vision)

ที่มา[แก้]

การค้นแบบเบสท์บินเฟิร์สท์นี้มีที่มาจากปัญหาการหาจุดที่อยู่ใกล้ที่สุด (nearest neighbor search) ซึ่งขั้นตอนวิธีการค้นหานี้ถูกคิดค้นขึ้นมาเพื่อเพิ่มความเร็วในการค้นในปริภูมิที่มีหลายมิติ และมีความแม่นยำมากพอที่จะนำไปใช้จริง โดยหลักการสำคัญอย่างหนึ่งที่เบสท์บินเฟิร์สท์นำมาใช้คือการเก็บข้อมูลจุดในปริภูมิด้วยต้นไม้เคดี (k-d tree)

ปัญหาการหาจุดที่อยู่ใกล้ที่สุด[แก้]

ปัญหาการหาจุดที่อยู่ใกล้ที่สุด (nearest neighbor search) เป็นปัญหาทางวิทยาการคอมพิวเตอร์ในการหาจุดที่อยู่ใกล้จุดที่กำหนดมากที่สุดในปริภูมิมิติต่าง ๆ โดยระยะทางที่ใช้วัดระยะระหว่างจุดอาจจะเป็นระยะทางแบบยุคลิด (Euclidean distance) หรือเป็นระยะทางแบบแมนฮัตตัน (Manhattan distance) ก็ได้ ซึ่งปัญหานี้ได้มีความพยายามในการออกแบบขั้นตอนวิธีให้มีประสิทธิภาพในการค้นมากที่สุด กล่าวคือ สามารถค้นจุดดังกล่าวได้เร็วและแม่นยำ คลาดเคลื่อนน้อยที่สุด ในปัจจุบันมีขั้นตอนวิธีสำหรับปัญหานี้หลายวิธี และมีทั้งการค้นจุดที่อยู่ใกล้ที่สุดแบบแม่นยำและแบบประมาณ ตัวอย่างเช่น ถ้าเป็นการค้นแบบตรง ๆ ก็จะเป็นการค้นแบบเส้นตรง (linear search) ที่ใช้วิธีการค้นแบบเทียบทุกจุด มีประสิทธิภาพในการทำงานเป็น O(Nd) โดยที่ N แทนจำนวนจุด และ d แทนจำนวนมิติของปริภูมิ อย่างไรก็ดี การค้นในปริภูมิที่มีจำนวนมิติที่สูงขึ้นก็จะมีความซับซ้อนเพิ่มขึ้น ทำให้ต้องมีการคิดค้นขั้นตอนวิธีใหม่ ๆ ในการค้น วิธีหนึ่งที่ถูกนำมาใช้ในการช่วยค้นคือการใช้ตารางแฮช แต่วิธีนี้ไม่เหมาะกับปัญหาที่มีจำนวนมิติสูง อีกวิธีหนึ่งที่ถูกนำมาใช้งานและให้ผลเป็นที่น่าพอใจเมื่อมีจำนวนมิติสูง ๆ คือการใช้ต้นไม้เคดี (k-d tree) ซึ่งเป็นการแบ่งปริภูมิออกเป็นส่วน ๆ เพื่อเก็บข้อมูลเป็นต้นไม้ (tree) การเก็บข้อมูลเป็นต้นไม้นี้ก็ทำให้สามารถค้นข้อมูลได้รวดเร็วเช่นกัน และถูกนำมาใช้ในการค้นแบบเบสท์บินเฟิร์สท์ด้วย

ต้นไม้เคดี[แก้]

ต้นไม้เคดี (k-d tree) เป็นโครงสร้างข้อมูลที่ใช้ในการแบ่งส่วนในปริภูมิในรูปของต้นไม้ (tree) เพื่อเพิ่มประสิทธิภาพในการค้น หลักการทำงานโดยย่อคือจะเริ่มแบ่งส่วนของจุดในปริภูมิจากมิติที่มีความแปรปรวน (variance) ของจุดสูงที่สุด แล้วแบ่งจุดออกเป็น 2 กลุ่มที่มีจำนวนจุดในแต่ละกลุ่มเท่ากัน แล้วในแต่ละกลุ่มก็จะทำการแบ่งเช่นนี้ลงไปเรื่อย ๆ จนสุด ซึ่งจะเหลือจุดเพียงจุดเดียว แล้วเก็บข้อมูลการแบ่งแต่ละขั้นเป็นปม เชื่อมกันเป็นต้นไม้ อย่างไรก็ตาม รายละเอียดในการนำไปใช้งานจริงอาจจะไม่ตายตัว ขึ้นอยู่กับการออกแบบของนักเขียนโปรแกรมด้วย อย่างเช่น หลักในการแบ่งครึ่งว่าจะหาจุดที่อยู่กึ่งกลางที่สุดในมิตินั้นแล้วแบ่งครึ่งที่จุดนั้นหรือแบ่งที่ค่ามัธยฐานของจุดในมิตินั้นแทน ซึ่งจะได้จุดอยู่ในปมใบ (leaf node) ของต้นไม้แทนที่จะได้จุดอยู่ประจำปมทุกปมในต้นไม้ โดยสำหรับการค้นแบบเบสท์บินเฟิร์สท์นี้จะใช้วิธีการแบ่งอย่างหลัง คือแบ่งที่ค่ามัธยฐาน เพื่อให้ปมที่มีจุดเป็นใบของต้นไม้ แต่ให้สังเกตด้วยว่าปมใบแต่ละปมนี้ ไม่ได้แทนจุด 1 จุด แต่แทนส่วนของปริภูมิที่ถูกแบ่งจนเหลือส่วนที่มีจุดอยู่ภายในเพียง 1 จุด

ขั้นตอนวิธีของเบสท์บินเฟิร์สท์[แก้]

ขั้นตอนวิธีในการค้นแบบเบสท์บินเฟิร์สท์นี้จะเป็นการนำต้นไม้เคดี (k-d tree) มาประยุกต์ใช้กับการค้นหาจุดที่อยู่ใกล้ที่สุดโดยประมาณ โดยข้อมูลที่ได้รับมาคือเซตของจุดในปริภูมิ d มิติ และจุด q ซึ่งเป็นจุดที่ต้องการสอบถาม (query point) สิ่งที่ขั้นตอนวิธีนี้จะคืนกลับมาคือจุดในเซตที่อยู่ใกล้กับจุด q มากที่สุด เริ่มจากทำการแบ่งส่วนของปริภูมิตามข้อมูลจุดที่ได้รับมาเพื่อสร้างเป็นต้นไม้เคดีดังที่ได้กล่าวไว้ในหัวข้อต้นไม้เคดี เมื่อสร้างเสร็จจะได้ว่าข้อมูลของจุดทุกจุดในเซตจะเป็นใบของต้นไม้ (tree) นั่นคือ ปมใบทุกปมของต้นไม้จะมีจุดในเซตเพียง 1 จุดเท่านั้น ยกเว้นปมที่มีจุด q อยู่ จะมี 2 จุด ได้แก่ จุดในเซตและจุด q ให้หาว่าจุด q นั้นอยู่ในปมใบใดของต้นไม้แล้วกำหนดทรงกลม n มิติที่มีรัศมีเป็นระยะจากจุด q ถึงจุดที่อยู่ในปมใบเดียวกันเป็นการจำกัดระยะจากจุด q ที่จะใช้ค้นหาจุดที่อยู่ใกล้ที่สุด แล้วก็จะวนหาจุดดังกล่าวโดยการท่องไปในต้นไม้เพื่อที่จะไปยังปมใบแต่ละปมที่อยู่ภายในรัศมี อย่างไรก็ตาม เนื่องจากเบสท์บินเฟิร์สท์เป็นการค้นหาโดยประมาณ จึงมีการจำกัดจำนวนครั้งที่จะใช้ค้นหา หรือพูดในอีกนัยหนึ่งก็คือจำกัดจำนวนปมใบที่จะทำการเทียบหาระยะกับจุด q นั่นเอง นอกจากนี้ เพื่อเพิ่มประสิทธิภาพในการค้น จะมีการใช้แถวคอยลำดับความสำคัญ (priority queue) ในการจัดลำดับปมใบที่จะค้นด้วย โดยจัดลำดับจากระยะจากขอบของปมใบนั้นในปริภูมิไปยังจุด q ดังนั้นนอกจากจะมีการจำกัดจำนวนครั้งที่จะใช้ค้นแล้ว ยังเริ่มค้นจากปมใบที่อยู่ใกล้ที่สุดก่อนด้วย (วัดระยะจากจุด q ถึงขอบส่วนของปมใบ ไม่ใช่วัดถึงจุดกึ่งกลางของปมใบ) จึงเป็นที่มาของชื่อเบสท์บินเฟิร์สท์ (best bin first) โดยที่คำว่าบิน (bin) มาจากคำว่าทวิภาค (binary) ซึ่งหมายถึงการแบ่งส่วนของปริภูมิตามหลักของต้นไม้เคดีที่จะแบ่งออกครั้งละสองส่วนลงไปเรื่อย ๆ จนถึงส่วนของปริภูมิที่มีจุดเพียงจุดเดียว (ไม่นับจุด q) โดยที่มีการทดลองแล้วว่าค่าของจุดที่อยู่ใกล้ที่สุดโดยประมาณที่ได้จากขั้นตอนวิธีของเบสท์บินเฟิร์สท์นั้นมีความแม่นยำสูงพอที่จะนำไปประยุกต์ใช้ในทางปฏิบัติ และสามารถสรุปการทำงานเป็นรหัสเทียม (pseudocode) ได้ดังนี้

BestBinFirst(S,q)
input: S = เซตของจุดในปริภูมิ d มิติ, q = จุดที่ต้องการสอบถาม (query point)
output: c = จุดที่อยู่ในเซต S ที่อยู่ใกล้จุด q มากที่สุด
1: ให้ kdtree เป็นต้นไม้เคดี (k-d tree) ที่เกิดจากการแบ่งส่วนปริภูมิตามเซต S
2: ให้ c เป็นจุดที่อยู่ในปมใบเดียวกันกับจุด q
3: ให้ Dc เป็นระยะจากจุด q ไปยังจุด c
4: ให้ Em เป็นจำนวนปมใบที่จะทำการค้น
5: ให้ PQ เป็นแถวคอยลำดับความสำคัญ (priority queue) ที่เรียงลำดับตามความใกล้จากจุด q ถึงขอบของปมใบ
6: ทำการ enqueue ปมใบที่มีระยะจากจุด q ภายในรัศมี Dc
7: สำหรับ i = 1 ถึง Em {
8: ถ้า PQ.empty() ให้ break
9: ให้ b = PQ.removeMin()
10: ถ้า จุด b อยู่ใกล้จุด q มากกว่าจุด c ให้ c = b }
11: return c

ประสิทธิภาพในการทำงาน[แก้]

จากรหัสเทียม (pseudocode) ด้านบน จะเห็นว่าภาระในการทำงานของขั้นตอนวิธีนี้จะตกอยู่ที่บรรทัดที่ 1 คือการสร้างต้นไม้เคดี (k-d tree) ซึ่งมีประสิทธิภาพในการทำงานเป็น O(n log² n) เมื่อมีการใช้ขั้นตอนวิธีการเรียงลำดับที่มีประสิทธิภาพเป็น O(n log n) ในการหาค่ามัธยฐาน ส่วนบรรทัดที่ 5 นั้นจริง ๆ ก็มีภาระการทำงานที่หนักเช่นกัน แต่เนื่องจากได้มีการคัดปมใบออกไปจากการจำกัดค่ารัศมี Dc ซึ่งสามารถคัดกรณีที่ไม่จำเป็นออกไปได้จำนวนมาก ภาระในการทำงานส่วนนี้จึงเบาขึ้นมาก และส่วนที่ใช้ในการค้นจุดที่อยู่ใกล้ที่สุดจริง ๆ มีประสิทธิภาพในการทำงานเป็น O(1) เนื่องจากมีการจำกัดจำนวนครั้งในการหาแน่นอนว่าไม่เกิน Em ครั้ง เพราะฉะนั้นโดยรวมแล้วขั้นตอนวิธีนี้จึงค้นได้เร็วมาก

ตัวอย่างการใช้งาน : การรู้จำวัตถุโดยใช้การตรวจหาลักษณะเด่นแบบซิฟท์[แก้]

การตรวจหาลักษณะเด่นแบบซิฟท์ (SIFT) เป็นวิธีการทางคอมพิวเตอร์วิทัศน์ (computer vision) ในการตรวจหาลักษณะเด่น (feature detection) ซึ่งสามารถนำมาประยุกต์ใช้ในเรื่องการรู้จำวัตถุ (object recognition) โดยที่จะทำการแปลงข้อมูลรูปภาพที่ได้มาเพื่อหาจุดที่มีลักษณะเด่น (keypoint) ของรูปนั้น โดยที่ข้อมูลของจุดลักษณะเด่นนี้สุดท้ายจะถูกแปลงเป็นจุดในปริภูมิ 128 มิติ เพื่อใช้เป็นตัวบอกจุดลักษณะสำคัญ (keypoint descriptor) ที่มีความเป็นเอกลักษณ์สูง เมื่อต้องการเทียบรูปวัตถุกับรูปภาพที่ได้มาว่ามีวัตถุอยู่ในรูปภาพดังกล่าวหรือไม่ ก็จะทำการหาจุดลักษณะเด่น (keypoint) และตัวบอกจุดลักษณะสำคัญ (keypoint descriptor) แล้วนำมาหาระยะทางแบบยุคลิด (Euclidean distance) ระหว่างตัวบอกจุดลักษณะสำคัญด้วยกัน ถ้าจุดที่อยู่ใกล้ที่สุดอยู่ใกล้กว่าระยะที่กำหนดไว้ก็จะถือว่าจุดลักษณะเด่นของทั้ง 2 รูปเป็นจุดเดียวกัน โดยจะสังเกตได้ว่าตัวบอกจุดลักษณะสำคัญนี้เป็นการเก็บข้อมูลจุดในปริภูมิที่มีจำนวนมิติสูงมาก คือ 128 มิติ ดังนั้นเพื่อเพิ่มประสิทธิภาพในการค้น จึงใช้การค้นแบบเบสท์บินเฟิร์สท์เพื่อค้นจุดที่อยู่ใกล้ที่สุดดังกล่าว

ดูเพิ่ม[แก้]

อ้างอิง[แก้]

Beis, J. and Lowe, D. G. 1997. Shape indexing using approximate nearest-neighbour search in high-dimensional spaces. Conference on Computer Vision and Pattern Recognition, Puerto Rico, pp. 1000–1006.