อัลกอริทึม k-เพื่อนบ้านใกล้ที่สุด (K-nearest Neighbors Algorithm) คืออะไร

อัลกอริทึม k-เพื่อนบ้านใกล้ที่สุด (k-Nearest-Neighbors) เป็นแนวทางการจำแนกประเภทที่ไม่สร้างสมมติฐานเกี่ยวกับโครงสร้างของความสัมพันธ์ระหว่างการเป็นสมาชิกคลาส (Y) และตัวทำนาย X₁, X₂,… X_n

นี่เป็นแนวทางแบบไม่พารามิเตอร์ (Nonparametric) เพราะไม่รวมการประมาณค่าพารามิเตอร์ในรูปแบบฟังก์ชันที่แฝงไว้ รวมถึงรูปแบบเชิงเส้นที่แฝงไว้ในการถดถอยเชิงเส้น วิธีนี้ดึงข้อมูลจากความคล้ายคลึงระหว่างค่าตัวทำนายของข้อมูลในชุดข้อมูล

แนวคิดในวิธี k-เพื่อนบ้านใกล้ที่สุดคือการระบุ k ระเบียนในชุดข้อมูลฝึกอบรมที่เหมือนกับข้อมูลใหม่ที่ต้องการจำแนกประเภท สามารถใช้ระเบียนที่คล้ายคลึงกัน (เพื่อนบ้าน) เหล่านี้เพื่อจัดข้อมูลใหม่เข้าไปในคลาส โดยมอบข้อมูลใหม่ให้กับคลาสส่วนใหญ่ระหว่างเพื่อนบ้านเหล่านี้ มันระบุค่าของตัวทำนายสำหรับระเบียนใหม่นี้โดย X₁, X₂,… X_n

คำถามกลางคือวิธีคำนวณระยะทางระหว่างข้อมูลขึ้นอยู่กับค่าตัวทำนายของพวกเขา ขนาดระยะทางที่รู้จักดีคือระยะทางยุคลิด (Euclidean Distance) ระยะทางยุคลิดระหว่างสองระเบียน (X₁, X₂,… X_n) และ (U₁, U₂,… U_n) คือ

$$\mathrm{\sqrt{(X_1-U_1)^2+(X_2-U_2)^2+...+(X_n-U_n)^2}}$$

อัลกอริทึม k-NN ขึ้นอยู่กับการคำนวณระยะทางหลายครั้ง (ระหว่างข้อมูลแต่ละชิ้นที่จะทำนายและข้อมูลแต่ละชิ้นในชุดฝึกอบรม) และเพราะฉะนั้นระยะทางยุคลิด ซึ่งมีค่าใช้จ่ายในการคำนวณต่ำ คือที่นิยมที่สุดใน k-NN

สามารถทำให้สเกลที่ตัวทำนายหลายตัวอาจมี สมดุลได้ ในส่วนใหญ่ ตัวทำนายต้องถูกมาตรฐาน化 (Standardized) ก่อนคำนวณระยะทางยุคลิด ค่าเฉลี่ยและส่วนเบี่ยงเบนมาตรฐานที่สามารถมาตรฐานข้อมูลใหม่ได้ คือของข้อมูลฝึกอบรม และข้อมูลใหม่ไม่ได้เกี่ยวข้องกับการคำนวณพวกมัน ข้อมูลตรวจสอบ (Validation Data) เหมือนกับข้อมูลใหม่ ก็ไม่ได้เกี่ยวข้องกับการคำนวณนี้เช่นกัน

หลังจากคำนวณระยะทางระหว่างข้อมูลที่จะกำหนดและระเบียนที่มีอยู่แล้ว จำเป็นต้องมีกฎเพื่อมอบคลาสให้กับระเบียนที่จะจำแนก ขึ้นอยู่กับคลาสของเพื่อนบ้านของมัน

กรณีที่เรียบง่ายที่สุดคือ k = 1 ที่เรามองหาข้อมูลที่ใกล้ที่สุด (เพื่อนบ้านใกล้ที่สุด) และจำแนกข้อมูลใหม่ว่าเป็นของคลาสเดียวกับเพื่อนบ้านใกล้ที่สุดของมัน

เป็นข้อเท็จจริงที่น่าประหลาดใจที่แนวคิดเรียบง่าย ตรงไปตรงมา นี้ของการใช้เพื่อนบ้านเดียวเพื่อจำแนกระเบียน สามารถแข็งแกร่งได้เมื่อเรามีระเบียนหลายระเบียนในชุดฝึกอบรม มันเปลี่ยนออกมาว่าอัตราการจำแนกผิดของแบบจำลอง 1-เพื่อนบ้านใกล้ที่สุด มีอัตราการจำแนกผิดที่ไม่เกินสองเท่าของข้อผิดพลาดเมื่อสามารถเข้าใจฟังก์ชันความหนาแน่นความน่าจะเป็น (Probability Density Functions) สำหรับแต่ละคลาสอย่างแม่นยำ