กฎเพื่อนบ้านใกล้ที่สุด (Nearest Neighbour Rule) ให้ประสิทธิภาพสูงบ่อยครั้ง โดยไม่ต้องมีสมมติฐานก่อนหน้าเกี่ยวกับการกระจายที่ตัวอย่างฝึกอบรมถูกดึงมา มันรวมชุดฝึกอบรมของทั้งกรณีบวก (Positive) และลบ (Negative) ตัวอย่างใหม่ถูกจำแนกประเภทโดยการคำนวณระยะทางไปยังกรณีฝึกอบรมที่สะดวก (Convenient) ตัวชี้วัดของจุดนั้นจึงตัดสินใจการจำแนกประเภทของตัวอย่าง
ตัวแบ่งประเภท k-NN ขยายแนวคิดนี้โดยการนำ k จุดที่ใกล้ที่สุด และสร้างเครื่องหมายของส่วนใหญ่ (Majority Sign) มักเลือก k เล็กและคี่ เพื่อแบ่งการเสมอ (Ties) (โดยทั่วไป 1, 3, หรือ 5) ค่า k ที่ใหญ่กว่าช่วยลดผลของจุดสัญญาณรบกวนภายในชุดข้อมูลฝึกอบรม และการเลือก k ถูกนำไปใช้ผ่านการตรวจสอบข้าม (Cross-validation)
ลักษณะเฉพาะของ Nearest-Neighbor
การจำแนกประเภทเพื่อนบ้านใกล้ที่สุดเป็นองค์ประกอบของแนวทางทั่วไปกว่าที่เรียกว่าการเรียนรู้แบบอิงอินสแตนซ์ (Instance-based Learning) มันต้องการอินสแตนซ์ฝึกอบรมเฉพาะเพื่อทำนายโดยไม่ต้องสนับสนุนการนามธรรม (Abstraction) หรือโมเดลที่ได้มาจากข้อมูล
อัลกอริทึมการเรียนรู้แบบอิงอินสแตนซ์ ต้องการขนาดความใกล้ชิด (Proximity Measure) เพื่อตัดสินใจความคล้ายคลึงหรือระยะทางระหว่างอินสแตนซ์ และฟังก์ชันการจำแนกประเภทที่คืนค่าคลาสที่ทำนายของอินสแตนซ์ทดสอบ ขึ้นอยู่กับความใกล้ชิดกับอินสแตนซ์อื่นๆ
ผู้เรียนขี้เกียจ (Lazy Learners) รวมถึงตัวแบ่งประเภทเพื่อนบ้านใกล้ที่สุด ไม่ต้องการการสร้างโมเดล (Model Building) แต่การจำแนกตัวอย่างทดสอบอาจค่อนข้างแพง เพราะต้องคำนวณค่าความใกล้ชิดแยกต่างหากระหว่างทดสอบและตัวอย่างฝึกอบรม ในทางตรงข้าม ผู้เรียนกระตือรือร้น (Eager Learners) ใช้ทรัพยากรการคำนวณส่วนใหญ่สำหรับการสร้างโมเดล เนื่องจากโมเดลถูกสร้างแล้ว การจำแนกตัวอย่างทดสอบเป็นเรื่องรวดเร็วมาก
ตัวแบ่งประเภทเพื่อนบ้านใกล้ที่สุดสร้างการทำนายขึ้นอยู่กับข้อมูลท้องถิ่น (Local Information) ในขณะที่ต้นไม้ตัดสินใจและตัวแบ่งประเภทแบบกฎพยายามค้นหาโมเดลส่วนกลาง (Global Model) ที่เข้ากับพื้นที่อินพุททั้งหมด เนื่องจากการตัดสินใจการจำแนกประเภทถูกสร้างในท้องถิ่น ตัวแบ่งประเภทเพื่อนบ้านใกล้ที่สุดจึงได้รับผลกระทบจากสัญญาณรบกวน (Noise)
ตัวแบ่งประเภทเพื่อนบ้านใกล้ที่สุดสามารถสร้างขอบเขตการตัดสินใจที่มีรูปรنگตามใจชอบ (Arbitrarily Shaped Decision Boundaries) ขอบเขตดังกล่าวสนับสนุนการแสดงโมเดลที่ยืดหยุ่นมากกว่า (More Flexible Model Representation) เหนือกว่าต้นไม้ตัดสินใจและตัวแบ่งประเภทแบบกฎที่ถูกบังคับให้เป็นขอบเขตการตัดสินใจแบบฉากฉับ (Rectilinear Decision Boundaries)
ตัวแบ่งประเภทเพื่อนบ้านใกล้ที่สุดสามารถทำนายผิดได้ เว้นแต่ขนาดความใกล้ชิดที่เหมาะสม (Appropriate Proximity Measure) และขั้นตอนการเตรียมข้อมูลล่วงหน้า (Data Preprocessing) ถูกนำไปใช้ ตัวอย่างพิจารณาว่าต้องการจำแนกชุดคนขึ้นอยู่กับแอตทริบิวต์เช่น ความสูง (วัดเป็นเมตร) และน้ำหนัก (วัดเป็นปอนด์)
แอตทริบิวต์ความสูงมีความแปรปรวนต่ำ อยู่ระหว่าง 1.5 ถึง 1.85 เมตร ในขณะที่แอตทริบิวต์น้ำหนักสามารถเปลี่ยนแปลงได้จาก 90 ถึง 250 ปอนด์ หากสเกลของแอตทริบิวต์ไม่ได้รับการพิจารณาในการประยุกต์ใช้ ขนาดความใกล้ชิดอาจถูกครอบงำโดยความแตกต่างในน้ำหนักของบุคคล
วิเคราะห์ Nearest-Neighbor Classifiers: Instance-based Learning, Lazy Learner (No Model Building), Local Decision Boundaries (Arbitrary Shapes), Noise Sensitivity, Feature Scaling Critical (Height vs Weight Example)
