อัลกอริทึม k-เพื่อนบ้านใกล้ที่สุด (k-Nearest-Neighbors) เป็นแนวทางการจำแนกประเภทที่ไม่สร้างสมมติฐานเกี่ยวกับโครงสร้างของความสัมพันธ์ระหว่างการเป็นสมาชิกคลาส (Y) และตัวทำนาย X1, X2,… Xn
นี่เป็นแนวทางแบบไม่พารามิเตอร์ (Nonparametric) เพราะไม่มีการประมาณค่าพารามิเตอร์ในรูปแบบฟังก์ชันที่แฝงไว้ รวมถึงรูปแบบเชิงเส้นที่แฝงไว้ในการถดถอยเชิงเส้น วิธีนี้ดึงข้อมูลจากความคล้ายคลึงระหว่างค่าตัวทำนายของข้อมูลในชุดข้อมูล
ข้อได้เปรียบของวิธี k-NN คือความสมบูรณ์ (Integrity) และไม่ต้องการสมมติฐานพารามิเตอร์ ในทุติยภูมิของชุดฝึกอบรมขนาดใหญ่ วิธีเหล่านี้ทำงานได้ดีมาก โดยเฉพาะเมื่อแต่ละคลาสมีลักษณะเฉพาะโดยการผสมผสานหลายแบบของค่าตัวทำนาย
ตัวอย่างเช่น ในฐานข้อมูลอสังหาริมทรัพย์ น่าจะมีหลายเซตของ {ประเภทบ้าน, จำนวนห้อง, ย่าน, ราคาขาย, ฯลฯ} ที่เป็นลักษณะเฉพาะของบ้านที่ขายเร็วเทียบกับที่ค้างอยู่ในตลาดนาน
มีสามความยากลำบากกับการใช้ประโยชน์จริงของพลังวิธี k-NN
แม้ไม่มีเวลาที่ต้องการในการคำนวณพารามิเตอร์จากข้อมูลฝึกอบรม (เหมือนกรณีของโมเดลพารามิเตอร์รวมถึงการถดถอย) เวลาในการค้นหาเพื่อนบ้านใกล้ที่สุดในชุดฝึกอบรมขนาดใหญ่สามารถเป็นข้อจำกัดได้ หลายแนวคิดได้ถูกนำมาใช้เพื่อเอาชนะความยากลำบากนี้ แนวคิดหลักมีดังนี้:
- สามารถลดเวลาที่ใช้คำนวณระยะทางโดยการทำงานในมิติลดลง (Reduced Dimension) ใช้เทคนิกลดมิติ (Dimension Reduction) เช่น การวิเคราะห์องค์ประกอบหลัก (Principal Components Analysis)
- สามารถใช้โครงสร้างข้อมูลที่ซับซ้อน (Sophisticated Data Structures) เช่น ต้นไม้ค้นหา (Search Trees) เพื่อเร่งการระบุเพื่อนบ้านใกล้ที่สุด วิธีนี้มักยอมรับ "เพื่อนบ้านเกือบใกล้ที่สุด" (Almost Nearest Neighbor) เพื่อเพิ่มความเร็ว ตัวอย่างคือการแบ่งถัง (Bucketing) ที่ข้อมูลถูกรวมเป็นถัง เพื่อข้อมูลภายในแต่ละถังอยู่ใกล้กัน
ข้อมูลจำนวนมากที่ต้องการในชุดฝึกอบรมเพื่อให้คุณสมบัติเป็นขนาดใหญ่ เพิ่มขึ้นแบบเอ็กซ์โพเนนเชียลกับจำนวนตัวทำนาย p เนื่องจากระยะทางที่คาดหวังไปยังเพื่อนบ้านใกล้ที่สุดเพิ่มขึ้นอย่างรุนแรงกับ p เว้นแต่จำนวนชุดฝึกอบรมจะเพิ่มขึ้นแบบเอ็กซ์โพเนนเชียลกับ p ปรากฏการณ์นี้เรียกว่าคลาสสิกของมิติ (Curse of Dimensionality) ปัญหาพื้นฐานที่เกี่ยวข้องกับการจำแนกประเภท การทำนาย และการจัดกลุ่มบางอย่าง
k-NN เป็น "Lazy Learner" (ผู้เรียนขี้เกียจ) — การคำนวณที่ใช้เวลาถูกเลื่อนไปถึงเวลาการทำนาย สำหรับข้อมูลแต่ละชิ้นที่จะทำนาย สามารถคำนวณระยะทางจากชุดฝึกอบรมทั้งหมดได้เฉพาะในเวลาทำนาย พฤติกรรมนี้จำกัดการใช้อัลกอริทึมนี้สำหรับการทำนายแบบเรียลไทม์ของข้อมูลหลายชิ้นพร้อมกัน
วิเคราะห์ k-NN Algorithm: ข้อได้เปรียบ Nonparametric Approach ทำงานดีกับ Training Set ใหญ่ ข้อจำกัด: Curse of Dimensionality, Computational Cost, Lazy Learner จำกัด Real-time Prediction
