การค้นหาเพื่อนบ้านใกล้สุด

การค้นหาเพื่อนบ้านที่ใกล้ที่สุด () เป็นที่รู้จักในนามอื่น ๆ อาทิ การค้นหาความใกล้ชิด การค้นหาความคล้ายคลึง หรือการค้นหาจุดที่ใกล้ที่สุด เอ็นเอ็นเอส คือ เทคนิคที่ใช้ในการแก้ปัญหาที่ใช้สำหรับหาจุดที่ใกล้ที่สุดในปริภูมิเมทริกซ์ ยกตัวอย่างจากโจทย์ต่อไปนี้ เมื่อให้เซต 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

เรขาคณิตไม่ต่อเนื่อง
การเรียนรู้ของเครื่อง
ขั้นตอนวิธีการค้นหา
การประมวลผลภาพ
การหาค่าเหมาะสมที่สุดทางคณิตศาสตร์
การวิเคราะห์เชิงตัวเลข
ขั้นตอนวิธีเชิงเรขาคณิต
ขั้นตอนวิธีการประมาณ
การค้นหา