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

ขั้นตอนวิธี

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

การคาดคะเนหรือประมาณจุดที่ใกล้ที่สุด (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 ไปยังจุดสองจุดที่ต่างกัน