การค้นหาเพื่อนบ้านใกล้สุด
การค้นหาเพื่อนบ้านที่ใกล้ที่สุด (อังกฤษ: nearest neighbor search) เป็นที่รู้จักในนามอื่น ๆ อาทิ การค้นหาความใกล้ชิด การค้นหาความคล้ายคลึง หรือการค้นหาจุดที่ใกล้ที่สุด เอ็นเอ็นเอส คือ เทคนิคที่ใช้ในการแก้ปัญหาที่ใช้สำหรับหาจุดที่ใกล้ที่สุดในปริภูมิเมทริกซ์ ยกตัวอย่างจากโจทย์ต่อไปนี้ เมื่อให้เซต S คือเซตของจุดในปริภูมิเมทริกซ์ M และ จุดที่กำหนด q ∈ M ต้องการหาจุดที่ใกล้ที่สุดของ S กับ q ในหลายกรณี M นั้นจะถูกแทนค่าเป็นมิติในปริภูมิของยูคลิด และระยะทางนั้นสามารถวัดได้จากระยะทางยูคลิด หรือ ระยะทางแมนฮัตตัน ในหนังสือของ โดนัลด์ คนูธ เล่มที่สามที่มีชื่อว่า The Art of Computer Programming เรียกโจทย์ปัญหาแบบนี้ว่า ปัญหาไปรษณีย์ โดยอ้างอิงถึงระบบการแนะนำผู้อยู่อาศัยเกี่ยวกับไปรษณีย์ที่ใกล้ที่สุด
การประยุกต์
เอ็นเอ็นเอสได้ถูกนำไปใช้ในการแก้ปัญหาและตอบโจทย์ในหลายๆด้าน อาทิเช่น
- การจำแนกรูปแบบ โดยเน้นไปที่ Optical Character recognition
- การแบ่งให้เป็นหมวดหมู่ของตัวเลขสถิติ ยกตัวอย่างเช่น ขั้นตอนวิธีการหาค่า k ที่ใกล้เคียงที่สุด
- การมองเห็นของเครื่องคอมพิวเตอร์
- ฐานข้อมูล อาทิ การจัดข้อมูลโดยการอ้างอิงและค้นหาจากรูปปภาพ
- ทฏษฎีการเขียดโค้ด
- การย่อขนาดข้อมูล
- ระบบแนะนำ
- การตลาดทางอินเทอร์เน็ต
- การจัดเรียงกันของดีเอ็นเอ
- ระบบสะกดคำ
- การจับทุจริตในการเขียนเรียงความ
- สมการที่ใช้สำหรับการค้นหาพื้นที่สัมผัส ในเอฟอีเอ (Finite Element Analysis)
- การเทียบเคียงผลการแข่งขันเพื่อที่ใช้สำหรับคาดคะเนความสำเร็จในด้านกีฬาของนักกีฬา
- การวิเคาระห์ข้อมูลที่ถูกจัดเป็นกลุ่มไว้แล้ว
ขั้นตอนวิธี
มีหลายวิธีการที่สามารนำไปใช้ในการค้นหาคำตอบสำหรับโจทย์เอ็นเอ็นเอส ได้ถูกคิดต้นขึ้น ค่าประสิทธิภาพของแต่ละวิธีนั้นสามารถหาได้จากเวลาและความซับซ้อนของโครงสร้างข้อมูลที่ถูกบันทึกไว้ การสังเกตอย่างไม่เป็นทางการ หรืออีกชื่อหนึ่งว่าคำสาปของมิติ(curse of dimensionality) กล่าวว่าไม่มีผลลัพธ์ของจุดประสงค์ได้อย่างชัดเจนสำหรับเอ็นเอ็นเอสในปริภูมิของยูคลิดที่มีมิติสูงๆ โดยการใช้การแก้สมการทีมีมากกว่าหนึ่งตัวแปรและ เวลาค้นหาแบบพหุนามล็อคการิทึม
การค้นหาแบบเส้นตรง
การหาวิธีแก้โจทย์เอ็นเอ็นเอสที่ง่ายที่สุดสามารถกระทำโดยเริ่มจากการหาค่าระยะทางจากจุดที่กำหนด ถึงจุดอื่นๆในฐานข้อมูล และเก็บข้อมูลเส้นทางที่ดีที่สุดอยู่เสมอ การหาค่าแบบนี้บางครั้งถูกตราหาเป็นวิธีที่พื้นฐานเกินไปและใช้เวลาทำงานเท่ากับ O( Nd ) โดย N คือ จำนวนสมาชิกของ S และ d คือมิติของ M วิธีการค้นหาแบบเส้นตรงนั้นไม่จำเป็นที่จะต้องรักษาโครงสร้างของข้อมูล เพราะฉะนั้นวิธีการค้นหาแบบเส้นตรงนั้นไม่ได้มีความสัมพันธ์กับความซับซ้อนของฐานข้อมูล เป็นที่น่าประหลาดใจว่า วิธีการค้นหาแบบเส้นตรงนั้นมีประสิทธิภาพมากกว่า อีกสองวิธีที่จะกล่าวถึงซึ่งก็คือ การแบ่งปริภูมิบนปริภูมิที่มีมิติสูงกว่า
การแบ่งส่วนปริภูมิ
ตั้งแต่ปี 1970 วิธีการขยายและจำกัดเขต (branch and bound) ได้ถูกมาใช้ในการแก้ปัญหา ในกรณีของปริภูมิของยูคลิด วิธีของการแบ่งปริภูมิ (space-partitioning) นั้นรู้จักในนามว่าวิธีตำแหน่งเชิงพื้นที่ (spatial index) หรือการเข้าถึงชิงพื้นที่ ในหลายวิธีของการแบ่งปริภูมิ ได้ถูกพัฒนาขึ้นเพื่อใช้ในการแก้โจทย์เอ็นเอ็นเอส บางทีวิธีที่ง่ายและมีความซับซ้อนน้อยที่สุดคือ k-d tree วิธีนี้คือการแบ่งแยกข้อมูลออกเป็นสองฝั่ง โดยฝั่งที่ถูกแบ่งนั้นจะมีจุดครึ่งหนึ่งจากทั้งหมดของตอนแรกที่ยังไม่ถูกแบ่ง จะแก้ปัญหาผ่านทางการแวะผ่านต้นไม้เริ่มตั้งแต่รากถึงใบโดยการแก้จุดที่กำหนด ในทุกๆที่ที่ถูกแบ่ง วิธีการนี้ขึ้นอยู่กับระยะทางที่กล่าวถึงในคำถาม กิ่งเพื่อนบ้านที่มีตัวที่กำลังค้นหาอยู่นั้นอาจจะต้องถูกนำมาวิเคาระห์ด้วย โดยช้เวลาในการหาคำตอบเท่ากับ O(log N) ในกรณีที่เลวร้ายที่สุด คือมีจุดกระจายกันอย่างไม่เป็นระเบียบ อีกทางเลือกหนึ่งคือ การใช้โครงสร้างข้อมูลแบบ R-tree ที่ได้ถูกออกแบบมาเพื่อรองรับการค้นหาจุดที่ใกล้ที่สุด แบบพลวัตสืบเนื่องจากว่ามันมีวิธีที่มีประสิทธิภาพในการเพิ่มและลบของข้อมูล ในกรณีทั่วไปของปริภูมิเมทริกซ์ วิธีการขยายและจำกัดเขต(branch and bound) รู้จักกันภายใต้ชื่อว่า ต้นไม้เมทริกซ์ ยกตัวอย่างจาก vp-tree และ BK-tree โดยการใช้กลุ่มตัวเลขจากปริภูมิสามมิติและใส่เข้าไปในต้นไม้บีเอสพี และให้จุดที่กำหนดที่มาจากปริภูมิเดียวกัน การหาผลลัพธ์ที่เป็นไปได้สำหรับปัญหาการหาจุดที่ใกล้เคียงที่สุดระหว่างกลุ่มของจุดและ ดังคำอธิบายของการแก้สมการต่อไปนี้ ในทางปฏิบัติ เรานั้นสนใจแค่การหาค่าสับเซตอันใดก็ได้ของกลุ่มของจุดทั้งหมดที่ปรากฏให้เห็นในระยะทางที่สั้นที่สุดจากจุดที่กำหนดไว้ก่อนหน้า จุดประสงค์ของแต่ละกิ่งของต้นไม้นี้คือการเดาว่าจุดที่ใกล้ที่สุดจากในกลุ่มที่ตั้งอยู่ในครึ่งหนึ่งของปริภูมิที่ประกอบไปด้วยจุดที่ต้องการรู้ วิธีนี้อาจไม่ได้ผลเสมอไปแต่มันเป็นการเริ่มต้นในการแก้ไขปัญหาของตัวเองที่ดี หลังจากที่ใช้วิธีนี้วนซ้ำครบทุกกิ่งแล้ว เราจะสามารถเปรียบเทียบว่าระยะทางที่ได้จากผลลัพธ์กับระยะทางที่สั้นที่สุดจากจุดที่ต้องการถึงระนาบที่แบ่งไว้ ว่ากิ่งไหนนั้นใช้ระยะทางที่สั้นที่สุด โดยระยะทางที่สั้นที่สุดอาจจะเกิดขึ้นอีกจากฐานข้อมูลอีกอันที่ถูกแบ่งก็ได้เพราะฉะนั้นบางทีคุณอาจจะต้องพิจารณาทั้งสองฝั่งที่ถูกแบ่ง แต่ถึงอย่างไรก็ตามถ้าระยะทางไปกลับจากจุดที่ต้องการกับระนาบที่แบ่งไว้ นั้นยาวกว่าระยะทางที่ถูกค้นหาก่อนหน้านี้ เราก็ไม่จำเป็นที่จะต้องวิเคราะห์อีกฝั่งนึงแล้ว วิธีนี้ใช้เวลาสั้นกว่าวิธีการค้นหาแบบเส้นตรงเพราะว่าระยะทางระหว่าง จุดที่ต้องการทราบกับกลุ่มของจุดที่ใกล้ที่สุดนั้นเกือบจะเทียบเท่ากับศูนย์ วิธีนี้จะใช้ได้ผลก็ต่อเมื่อมีการค้นหาโดยใช้จุดที่ต้องการทราบ
Locality sensitive hashing
แอลเอสเอช (Locality sensitive hashing) คือขั้นตอนที่ใช้สำหรับจับกลุ่มจุดต่างๆที่อยู่ในที่ว่างให้อยู่เป็นที่ โดยอ้างอิงจากระยะทางจากการกระทำการเมทริกซ์บนจุดเหล่านั้น จุดที่ใกล้กันในเมทริกซ์ ที่ถูกเลือกนั้นจะถูกจัดเข้าไปอยู่ในที่ๆเดียวกันโดยที่มีสถิติความน่าจะเป็นที่สูงกว่า
การค้นหาเพื่อนบ้านที่ใกล้ที่สุดในปริภูมิที่มีมิติน้อย
รูปแบบโดยกว้างของต้นไม้นั้นอ้างอิงมาจากการเพิ่มค่าขึ้นเป็นสองเท่าของฐานข้อมูลที่คงที่ เส้นรอบนอก ในเวลาของการค้นหานั้นเท่ากับ O(c12 log n) โดย c นั้นเท่ากับการขยายตัวที่คงที่ของข้อมูลนั้น
Vector Approximation Files
ในโลกหลายๆมิติ รายละเอียดภายในของต้นไม้นั้นไม่สามารถนำมาใช้ประโยชน์ได้เพราะว่าค่าเปอร์เซ็นต์ของจุดนั้นจะต้องถูกนำมาตรวจสอบด้วย ในการเพิ่มประสิทธิภาพให้กับวิธีค้นหาเป็นเส้นตรง รูปแบบการบีบอัดของการเก็บเวกเตอร์ในแรม นั้นได้ถูกใช้ในการคัดจำแนกข้อมูลในการประเมินในครั้งแรก ตัวเลือกสุดท้ายนั้นสามารถหาได้จากในขั้นตอนที่สองโดยการใช้การปลดปล่อยข้อมูลจากดิสก์เพื่อการคำนวณระยะทาง Compression/Clustering Based Search การจำลองการเข้าถึงไฟล์นั้นเป็นวิธีเฉพาะที่ใช้สำหรับการข้นหาข้อมูลแบบย่อ โดยที่องค์ประกอบของข้อมูลที่ถูกย่อนั้นได้ถูกย่อจากเวอร์ชันเต็มโดยไร้ข้อบังคับใช้เทคนิคการย่อและบีบอัดในโลกหลายๆมิตินั้นเรียกว่า Vector Quantization (VQ)ที่สร้างโดยการจัดกลุ่ม ฐานข้อมูลได้ถูกหั่นและย่อลงมาจนเหลือแค่ชิ้นข้อมูลที่น่าเชื่อถือที่สุด ประโยชน์ของเทคนิคนี้นั้นมากกว่าVA-File, tree-based indexes และ sequential scan
สิ่งที่แปรผัน
มีค่าแปรผันมากมายในโจทย์เอ็นเอ็นเอสแต่ค่าแปรผันสองตัวที่พบเจอบ่อยที่สุดคือ การค้นหาเพื่อนบ้านที่ใกล้ที่สุดเป็นระยะทาง k (k-nearest neighbor search) และการประมาณหาเพื่อนบ้านที่ใกล้ที่สุด(ε-approximate nearest neighbor search)
k เพื่อนบ้านที่ใกล้ที่สุด (k-nearest neighbor)
การค้นหาเพื่อนบ้านที่ใกล้ที่สุด k ตัว(k-nearest neighbor search) แสดงค่าเพื่อนบ้านที่ใกล้กับจุดที่ต้องการทราบที่สุด k ตัว เทคนิคนี้ใช้อย่างเพร่หลายใจการวิเคราะห์คาดคะเนเพื่อที่จะประมาณหรือจำแนกจุดโดยอ้างอิงจากข้อสรุปของจุดอื่นในละแวกใกล้เคียง กราฟของเพื่อนบ้านที่ใกล้ที่สุด k เพื่อนบ้าน คือกราฟที่ทุกๆจุดได้ถูกเชื่อมต่อเข้ากับ k ที่ใกล้สุดในระแวกเดียวกัน
การคาดคะเนหรือประมาณจุดที่ใกล้ที่สุด (Approximate nearest neighbor)
ในการประยุกต์ใช้ในบางอย่าง มันอาจเป็นที่ยอบรับสำหรับการค้นเจอการคาดเดาที่ดีของจุดที่ใกล้ที่สุดในละแวกนั้น สำหรับกรณีเหล่านั้นเราสามารถใช้สมการที่ไม่รับรองการค้นหาจุดที่ใกล้ที่สุดที่แท้จริงโดยเสมอไป แต่ข้อดีของมันก็คือมันสามารถนำไปใช้ในการพัฒนาความเร็วในด้านการค้นหาและจัดเก็บข้อมูล แต่ถึงอย่างไรก็ตามสมการที่ว่าวามารถค้นหาจุดรอบๆที่ใกล้ที่สุดได้อยู่บ่อยๆแต่ทั้งนี้ทั้งนั้นมันก็ขึ้นอยู่กับข้อมูลที่ใช้ในการวิเคราะห์ ขั้นตอนวิธีที่รองรับการค้นหาเพื่อนบ้านที่ใกล้ที่สุดแบบคาดคะเน อาทิเช่น locality-sensitive hashing , best bin first และ balanced box-decomposition tree based search การประมาณหาเพื่อนบ้านที่ใกล้ที่สุด (ε-approximate nearest neighbor search) นั้นกำลังเป็นที่นิยมสำหรับต่อกรกับคำสาปของมิติ (curse of dimensionality)
อัตราส่วนระยะทางของเพื่อนบ้านที่ใกล้ที่สุด (Nearest neighbor distance ratio)
อัตราส่วนระยะทางของเพื่อนบ้านที่ใกล้ที่สุด (Nearest neighbor distance ratio) นั้นใช้ไม่ได้กับระยะทางโดยตรงระหว่างจุดเริ่มแรกกับจุดที่อยู่ในละแวกเดียวกันแต่สัดส่วนของแต่ละจุดนี้ขึ้นอยู่กับระยะทางของจุดก่อนหน้านี้ที่อยู่ในละแวกเดียวกัน เทคนิคได้ถูกนำไปใช้กับ CBIR ในการค้นหารูปภาพผ่านจากตัวอย่างคำถาม โดยอ้างอิงจากความใกล้เคียงของคุณสมบัติต่างๆของรูปภาพเหล่านั้น ในเชิงลึกเทคนิคนี้ได้นำไปใช้ในปัญหาสำหรับการจับคู่
ทุกเพื่อนบ้านที่ใกล้ที่สุด (All nearest neighbors)
สำหรับขั้นตอนอื่น ตัวอย่างเช่น entropy estimation เราอาจมี N จุดข้อมูลและเราต้องการที่ทราบว่าจุดในละแวกไหนที่อยู่ใกล้จุดข้อมูล N เหล่านั้น เราอาจสามารถแก้ปัญหานี้ได้โดยการใช้วิธีเอ็นเอ็นเอสกับทุกจุด แต่แผนการ์ณที่ดีกว่านั้นคือการใช้ข้อมูลที่ซับซ้อนระหว่าง Nจุดที่ต้องการทราบ เพื่อที่จะสร้างการค้นหาที่มีประสิทธิภาพที่มากยิ่งขึ้น ดังเช่นตัวอย่างที่ง่ายที่จะกล่าวถึงต่อไปนี้ เมื่อไรเราได้หาระยะทางระหว่าจุด X กับ จุด Y เราก็สามารถรู้ระยะทางระหว่าง Y กับ X ในเวลาเดียวกัน เพราะฉะนั้นขั้นตอนการคำนวณที่เหมือนกันสามารถนำไปใช้ได้อีกเมื่อเราต้องการหาระยะทางจากจุด X ไปยังจุดสองจุดที่ต่างกัน
อ้างอิง
- Andrews, L.. A template for the nearest neighbor problem. C/C++ Users Journal, vol. 19 , no 11 (November 2001), 40 - 49, 2001, ISSN:1075-2838, www.ddj.com/architect/184401449
- Arya, S., D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu. An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions. Journal of the ACM, vol. 45, no. 6, pp. 891–923
- Beyer, K., Goldstein, J., Ramakrishnan, R., and Shaft, U. 1999. When is nearest neighbor meaningful? In Proceedings of the 7th ICDT, Jerusalem, Israel.
- Chung-Min Chen and Yibei Ling - A Sampling-Based Estimator for Top-k Query. ICDE 2002: 617-627
- Samet, H. 2006. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann. ISBN 0123694469
- Zezula, P., Amato, G., Dohnal, V., and Batko, M. Similarity Search - The Metric Space Approach. Springer, 2006. ISBN 0-387-29146-6