อัลกอริธึม k-nearest-neighbors เป็นวิธีการจำแนกประเภทที่ไม่สร้างสมมติฐานเกี่ยวกับโครงสร้างของความสัมพันธ์ระหว่างสมาชิกกลุ่ม (Y) และตัวทำนาย X1 , X2 ,…. Xn .
นี่เป็นแนวทางที่ไม่อิงพารามิเตอร์ เนื่องจากไม่ได้รวมการประมาณค่าพารามิเตอร์ในรูปแบบฟังก์ชันที่เสแสร้ง รวมถึงรูปแบบเชิงเส้นที่จำลองในการถดถอยเชิงเส้น วิธีการนี้จะดึงข้อมูลจากความคล้ายคลึงกันระหว่างค่าตัวทำนายของข้อมูลในชุดข้อมูล
แนวคิดในวิธี k-nearest-neighbors คือการรับรู้ k เร็กคอร์ดในชุดข้อมูลการฝึกอบรมที่เหมือนกับข้อมูลใหม่ที่จำเป็นในการจำแนก สามารถใช้เร็กคอร์ดที่คล้ายกัน (เพื่อนบ้าน) เพื่อกำหนดเร็กคอร์ดใหม่ลงในคลาส สร้างข้อมูลใหม่ไปยังคลาสเด่นระหว่างเพื่อนบ้านเหล่านี้ มันระบุค่าของตัวทำนายสำหรับระเบียนใหม่นี้โดย X1 , X2 ,…. Xn .
คำถามสำคัญคือวิธีการคำนวณระยะห่างระหว่างข้อมูลโดยขึ้นอยู่กับค่าตัวทำนาย การวัดระยะทางที่รู้จักกันดีคือระยะทางแบบยุคลิด ระยะทางแบบยุคลิดระหว่างสองระเบียน (X1 , X2 ,…. Xn ) และ (U1 , U2 ,…. คุณn ) คือ
$$\mathrm{\sqrt{(X_1-U_1)^2+(X_2-U_2)^2+...+(X_n-U_n)^2}}$$
อัลกอริธึม k-NN ขึ้นอยู่กับการคำนวณระยะทางหลายแบบ (ระหว่างแต่ละข้อมูลที่จะคาดการณ์กับแต่ละข้อมูลในชุดการฝึก) และด้วยเหตุนี้ระยะทางแบบยุคลิดซึ่งมีราคาไม่แพงนัก จึงเป็นที่นิยมมากที่สุดใน k-NN
มันสามารถปรับสมดุลสเกลที่ตัวทำนายหลายตัวสามารถมีได้ ในกรณีส่วนใหญ่ ตัวทำนายจะต้องเป็นมาตรฐานก่อนที่จะคำนวณระยะทางแบบยุคลิด ค่าเฉลี่ยและค่าเบี่ยงเบนมาตรฐานที่สามารถสร้างมาตรฐานให้กับข้อมูลใหม่ได้มาจากข้อมูลการฝึกอบรม และข้อมูลใหม่จะไม่เกี่ยวข้องกับการคำนวณ ข้อมูลการตรวจสอบความถูกต้อง เช่น ข้อมูลใหม่ จะไม่เกี่ยวข้องกับการคำนวณนี้เช่นกัน
หลังจากคำนวณระยะทางระหว่างข้อมูลที่จะกำหนดและระเบียนปัจจุบัน จำเป็นต้องมีกฎในการกำหนดคลาสให้กับระเบียนเพื่อจัดประเภท ขึ้นอยู่กับชั้นเรียนของเพื่อนบ้าน
กรณีที่ง่ายที่สุดคือ k =1 โดยเราจะค้นหาข้อมูลที่ใกล้เคียงที่สุด (เพื่อนบ้านที่ใกล้ที่สุด) และจัดประเภทข้อมูลใหม่ว่าเป็นของคลาสที่เท่ากันในฐานะเพื่อนบ้านที่ใกล้เคียงที่สุด
เป็นความจริงที่ไม่ธรรมดาที่แนวคิดง่ายๆ ที่เข้าใจได้ของการใช้เพื่อนบ้านที่ใกล้ที่สุดเพียงคนเดียวในการจำแนกประเภทระเบียนจะแข็งแกร่งเมื่อเรามีระเบียนหลายรายการในชุดการฝึก มันเปลี่ยนว่าข้อผิดพลาดในการจัดประเภทที่ไม่ถูกต้องของการออกแบบเพื่อนบ้านที่ใกล้ที่สุด 1 รายการมีอัตราการจัดประเภทที่ไม่ถูกต้องซึ่งไม่เกินสองเท่าของข้อผิดพลาดเมื่อสามารถเข้าใจฟังก์ชันความหนาแน่นของความน่าจะเป็นสำหรับแต่ละชั้นเรียนได้อย่างแม่นยำ
