อัลกอริธึม k-nearest-neighbors เป็นวิธีการจำแนกประเภทที่ไม่สร้างสมมติฐานเกี่ยวกับโครงสร้างของความสัมพันธ์ระหว่างสมาชิกกลุ่ม (Y) และตัวทำนาย X1 , X2 ,…. Xn .
นี่เป็นแนวทางที่ไม่อิงพารามิเตอร์ เนื่องจากไม่มีการประมาณค่าพารามิเตอร์ในรูปแบบฟังก์ชันที่เสแสร้ง รวมถึงรูปแบบเชิงเส้นที่จำลองในการถดถอยเชิงเส้น วิธีนี้จะดึงข้อมูลจากความคล้ายคลึงกันระหว่างค่าตัวทำนายของข้อมูลในชุดข้อมูล
ประโยชน์ของวิธี k-NN คือความสมบูรณ์และความจำเป็นในการสันนิษฐานแบบพารามิเตอร์ เมื่อมีชุดฝึกอบรมขนาดใหญ่ วิธีการเหล่านี้จะทำงานได้ดีเป็นพิเศษ เมื่อแต่ละชั้นเรียนประกอบด้วยค่าตัวทำนายหลายค่าผสมกัน
ตัวอย่างเช่น ในฐานข้อมูลอสังหาริมทรัพย์ มีแนวโน้มว่าจะมี {ประเภทบ้าน จำนวนห้อง ละแวกบ้าน ราคาเสนอ ฯลฯ} หลายชุดที่แสดงลักษณะบ้านที่ขายได้เร็ว เทียบกับบ้านที่ยังคงอยู่ในช่วงเวลาสูง อุตสาหกรรม
มีปัญหาสามประการกับการใช้ประโยชน์จากพลังของวิธี k-NN อย่างสมจริง
แม้ว่าจะไม่จำเป็นต้องใช้เวลาในการคำนวณพารามิเตอร์จากข้อมูลการฝึกอบรม (เช่นเดียวกับแบบจำลองพารามิเตอร์รวมถึงการถดถอย) เวลาในการค้นหาเพื่อนบ้านที่ใกล้ที่สุดในชุดการฝึกขนาดใหญ่อาจมีการจำกัด มีการใช้แนวคิดหลายอย่างเพื่อเอาชนะความยากลำบากนี้ แนวคิดหลักมีดังนี้ −
-
สามารถลดเวลาในการคำนวณระยะทางโดยทำงานในมิติที่ลดลงโดยใช้เทคนิคการลดขนาด เช่น การวิเคราะห์ส่วนประกอบหลัก
-
สามารถใช้โครงสร้างข้อมูลที่ซับซ้อน เช่น ค้นหาต้นไม้ เพื่อเร่งการระบุเพื่อนบ้านที่ใกล้ที่สุด วิธีนี้มักจะใช้กับเพื่อนบ้านที่ "ใกล้เคียงที่สุด" เพื่อเพิ่มความเร็ว อินสแตนซ์กำลังใช้การฝากข้อมูล โดยที่ข้อมูลจะถูกรวมเข้าในที่เก็บข้อมูลเพื่อให้ข้อมูลภายในที่เก็บข้อมูลแต่ละอันอยู่ใกล้กัน
ข้อมูลหลายรายการที่จำเป็นในชุดการฝึกอบรมเพื่อให้มีคุณสมบัติเป็นการเพิ่มขึ้นอย่างมากแบบทวีคูณด้วย p ของตัวทำนายหลายตัว นี่เป็นเพราะระยะทางที่คาดหวังไปยังเพื่อนบ้านที่ใกล้ที่สุดเพิ่มขึ้นไม่ดีด้วย p เว้นแต่ว่าจำนวนของชุดการฝึกจะเพิ่มขึ้นแบบทวีคูณด้วย p ปรากฏการณ์นี้เรียกว่าคำสาปแห่งมิติ ซึ่งเป็นปัญหาพื้นฐานที่เกี่ยวข้องกับการจำแนกประเภท การทำนาย และการจัดกลุ่ม
k-NN คือ “ขี้เกียจเรียน” − การคำนวณที่ใช้เวลานานจะล่าช้าจนถึงเวลาที่คาดการณ์ สำหรับแต่ละข้อมูลที่จะทำนาย มันสามารถคำนวณระยะทางจากชุดข้อมูลการฝึกที่สมบูรณ์เฉพาะในเวลาที่คาดการณ์เท่านั้น ข้อจำกัดพฤติกรรมนี้ใช้อัลกอริธึมนี้สำหรับการคาดการณ์แบบเรียลไทม์ของข้อมูลหลายรายการพร้อมกัน
