K-Nearest Neighbors (KNN)
ขั้นตอนวิธีการเพื่อนบ้านใกล้ที่สุด (K-Nearest Neighbour Algorithm) เป็นวิธีที่ใช้ในการจัดแบ่งคลาส โดยเทคนิคนี้จะตัดสินใจว่า คลาสใดที่จะแทนเงื่อนไขหรือกรณีใหม่ๆ ได้บ้าง โดยการตรวจสอบจำนวนบางจำนวน ในขั้นตอนวิธีการเพื่อนบ้านใกล้ที่สุด ของกรณีหรือเงื่อนไขที่เหมือนกันหรือใกล้เคียงกันมากที่สุด โดยจะหาผลรวม (Count Up) ของจำนวนเงื่อนไข หรือกรณีต่างๆ สำหรับแต่ละคลาส และกำหนดเงื่อนไขใหม่ๆ ให้คลาสที่เหมือนกันกับคลาสที่ใกล้เคียงกันมากที่สุด
K- Nearest Neighbor เป็นอัลกอลิทึ่มที่ใช้ในการจัดกลุ่มข้อมูล (Classification) ซึ่งเป็นอัลกอลิทึ่มที่อยู่ในกลุ่มของ Supervised learning
ชุดตัวอย่างของเราคือละครต่าง ๆที่เราแบ่งประเภทไว้แล้วพร้อมระบุจำนวน (attributes) คือจำนวนฉากจูบและฉากตบ ดังนี้
เราทราบได้ทันทีว่าละครตบแล้วจูบที่เราไม่ทราบประเภทอยู่ใกล้กับละครเรื่องแรงเงา นั่นคือละครทั้งสองเรื่องทีจำนวนฉากตบและฉากจูบใกล้เคียงกันมากที่สุด เพราะว่าแรงเงาเป็นละครโรแมนติก เราจึงอนุมานได้ว่าตบแล้วจูบก็ควรเป็นละครโรแมนติกเช่นกัน เพราะว่าการจำแนกประเภทของเราอาศัยการเทียบเคียงกับข้อมูลตัวที่อยู่ใกล้สุด เราจึงเรียกวิธีการนี้ว่า Nearest Neighbor นั่นเองดั่งเช่นในรูป
K-NN Algorithm
การกำหนดจำนวน K กรณีที่เรามี attributes ให้พิจารณาเพียงสองตัว เช่นจำนวนฉากตบและจำนวนฉากจูบ เช่นนี้เราควรเลือก k ให้เป็นเลขคี่ เช่น 3, 5, 7, … เพื่อป้องกันปัญหาที่ข้อมูลเราเป็นได้ทั้งสองประเภท เช่น หากเลือก k = 4 (เลขคู่) ย่อมมีโอกาสที่ข้อมูลที่จะทดสอบอยู่ใกล้ข้อมูล 2 ตัวที่มาจากประเภท A และอยู่ใกล้ข้อมูลอีก 2 ตัวที่มาจากประเภท B ที่นำไปสู่ข้อสรุปที่ไม่ลงตัวว่าสุดท้ายจะเป็นประเภท A หรือ B ดีนั่นเอง
สมการเพื่อวัดระยะทาง
เมื่อพิจารณาที่ k = 3 จึงได้ว่าละครเรื่องตบแล้วจูบมีระยะทางใกล้สุดสามอันดับคือ แรงเงา, พิษสวาท และนาคี จึงสรุปได้ว่าละครเรื่องตบแล้วจูบเป็นละครประเภทโรแมนติกนั่นเอง
Weighted Nearest Neighbors
เนื่องจากภายใต้ k = 5 ทำให้จุดที่เป็นลบ (-) มีจำนวนมากกว่าจุดที่เป็นบวก (+) จึงสรุปได้ว่าจุดสีชมพูของเราเป็นข้อมูลประเภทเดียวกันกับข้อมูลลบ (-)
จากตัวอย่างข้างต้น หากระยะทางจากจุดสีชมพูไปยังจุดต่างๆเป็นดังนี้
เมื่อเรียงน้อยไปหาน้อย จะได้ 2, 3, 5, 6, 8 นั่นคือ d1=2, d2=3, d3=5, d4=6, d5=8
สมการหาน้ำหนัก
สำหรับประเภทลบ (-) น้ำหนักรวมเท่ากับน้ำหนักของ d3+d4+d5=0.5+0.33+0=0.83 สำหรับประเภทบวก (+) น้ำหนักรวมเท่ากับน้ำหนักของ d1+d2=1+0.83=1.83
พบว่าน้ำหนักรวมของประเภทบวกมากกว่าน้ำหนักรวมของประเภทลบ ด้วยวิธีการของ Weighted Nearest Neighbors จึงสรุปได้ว่า จุดสีชมพูเป็นประเภทเดียวกับข้อมูลบวก (+)
สรุป k-Nearest Neighbors
■K-NN Algorithm
■1.กำหนดขนาดของ k
■2.คำนวณระยะห่าง (Distance) ของข้อมูลที่ต้องการพิจารณากับกลุ่มข้อมูลตัวอย่าง
■3.จัดเรียงลำดับของระยะห่าง และเลือกพิจารณาชุดข้อมูลที่ใกล้จุดที่ต้องการพิจารณาตามจำนวน k ที่กำหนดไว้
■4.พิจารณาข้อมูลจำนวน k ชุด และสังเกตว่ากลุ่ม (Class) ไหนที่ใกล้จุดที่พิจารณาเป็นจำนวนมากที่สุด
■5.กำหนด Class ให้กับจุดที่พิจารณา
■k-Nearest Neighbors ทำให้เราทราบประเภทข้อมูลของสิ่งของที่เรายังไม่เคยจำแนกมาก่อนได้ ในการใช้งานจริงยังมีเงื่อนไขบางอย่างที่เราต้องพิจารณาเป็นพิเศษ
K-nearest neighbor
จัดทำโดย
นที ไทยธรรม
ภาสกร สุวรรณโท
