[Machine Learning#2] รู้จักการจำแนกประเภทข้อมูลด้วย k-Nearest Neighbors

ละครน้ำเน่าอยู่คู่สังคมไทยนานหลายสิบปีไม่ว่าจะเป็นละครแนวแอคชันหรือละครรักสุดโรแมนติกจิกหมอนขาด หากเราชอบละครซักเรื่องจนต้องแนะนำให้เพื่อนของเราดู สิ่งแรกที่เพื่อนเรามักจะถามก็คือ เห้ยแกมันเป็นละครแนวไหนแว๊

จากความจริงที่ว่าละครทั้งสองประเภทล้วนขาดไม่ได้ซึ่งฉากตบและฉากจูบ แม้ละครเรื่องนาคีจะมีฉากตบเราก็สรุปไม่ได้ว่านาคีคือละครบู้ เพราะในความจริงแล้วนาคีเป็นละครโรแมนติกต่างหาก แหมรอสามีมา 1,000 ปี แก่ขนาดนี้ถ้าปล่อยตะขาบได้ด้วยจะนึกว่าเป็นคุณยายวรนาฏจากเรื่องทายาทอสูร

เมื่อเราตัดสินประเภทละครด้วยการพิจารณาว่ามีแค่ฉากตบหรือจูบไม่ได้ ถ้างั้นเราพิจารณาด้วยการนับจำนวนครั้งในการตบหรือจูบเป็นไง? ถ้าละครไหนตบเยอะกว่าจูบแสดงว่าเป็นละครแอคชัน ตบทีหน้าหมุนไป 270 องศา ในทางกลับกันหากละครเรื่องนั้นฉากจูบเยอะกว่าฉากตบมันสมควรเป็นละครโรแมนติก วิธีการนี้เหมือนจะดีนะครับแต่ลองพิจารณาสถานการณ์ที่จำนวนฉากจูบเท่าฉากตบดูซิ ใครว่าไม่มี? ก็ตอนที่นางเอกตบพระเอกแล้วจูบ ตบแล้วจูบ ตบอีกก็จูบอีก จำนวนตบเท่ากับจำนวนจูบเช่นนี้ไปต่อไม่ถูกกันเลยทีเดียว

จำนวนครั้งของฉากตบและจูบอาจจำแนกประเภทละครได้ไม่สมบูรณ์ แต่ถ้าเราเทียบเคียงกับข้อมูลละครที่เรามีอยู่ การจำแนกประเภทละครของเราก็จะสมบูรณ์มากขึ้น ตัวอย่างเช่น เรามีละครที่เราไม่ทราบว่ามันคือละครแอคชันหรือโรแมนติก แต่เราทราบว่าละครเรื่องดังกล่าวมีจำนวนฉากจูบและฉากตบใกล้เคียงกับละครรักแบบนาคี เราจึงอนุมานจากความคล้ายกันนี้ได้ว่า ละครเรื่องที่เราไม่ทราบประเภทก็คงเป็นละครรักจูบจนปากแฉะเช่นกัน

บทความนี้ผมจะพาเพื่อนๆรู้จักกับวิธีจำแนกประเภทด้วยวิธี k-Nearest Neighbors และเพื่อให้แน่ใจว่าเพื่อนๆจะไม่งงในศัพท์แสงบางอย่าง ผมแนะนำให้เพื่อนๆอ่านบทความเรื่อง Machine Learning คืออะไร? รู้จักประเภทต่างๆของ Machine Learning ก่อนครับ

ทบทวนความหมายของ Classification

Classification หรือการจัดประเภทเป็นหนึ่งในวิธีการเรียนรู้แบบมีผู้สอน (Supervised Learning) ที่เราต้องเตรียมตัวอย่าง (Traning examples) ให้กับระบบก่อน โดยแต่ละตัวอย่างของเราจะมีป้ายกำกับ (Label) เพื่อบอกว่าตัวอย่างแต่ละตัวของเราเป็นประเภทใด เช่น ชุดตัวอย่างของเราคือละครต่างๆที่เราแบ่งประเภทไว้แล้วพร้อมระบุจำนวนสิ่งที่เราสนใจ (attributes) คือจำนวนฉากจูบและฉากตบ ดังนี้

อาศับชุดตัวอย่างที่กำหนด เมื่อเรามีละครเรื่องใหม่ชื่อตบแล้วจูบที่เราไม่ทราบประเภท เราสามารถถามคอมพิวเตอร์เพื่อจัดประเภทละครเรื่องนี้แก่เราได้

รู้จักการจำแนกประเภทแบบ Nearest Neighbor

เราไม่ทราบว่าตบแล้วจูบของเราเป็นละครประเภทใด อาศัยความจริงที่ว่าถ้าจำนวนฉากตบและจูบของละครเรื่องตบแล้วจูบ ใกล้เคียงกับละครเรื่องใด ประเภทของละครเรื่องตบแล้วจูบก็น่าจะเป็นประเภทเดียวกับละครเรื่องนั้น เรานำข้อมูลนี้มาวาดเป็นกราฟเพื่อให้เกิดความเข้าใจมากขึ้นได้ดังนี้

จากการสังเกตด้วยตาเปล่า เราทราบได้ทันทีว่าละครตบแล้วจูบที่เราไม่ทราบประเภทอยู่ใกล้กับละครเรื่องแรงเงา นั่นคือละครทั้งสองเรื่องทีจำนวนฉากตบและฉากจูบใกล้เคียงกันมากที่สุด เพราะว่าแรงเงาเป็นละครโรแมนติก เราจึงอนุมานได้ว่าตบแล้วจูบก็ควรเป็นละครโรแมนติกเช่นกัน เพราะว่าการจำแนกประเภทของเราอาศัยการเทียบเคียงกับข้อมูลตัวที่อยู่ใกล้สุด เราจึงเรียกวิธีการนี้ว่า Nearest Neighbor นั่นเอง

ก้าวเข้าสู่ k-Nearest Neighbors

โลกความจริงไม่เป็นอย่างที่เราคิด ถ้าคุณเห็นเพื่อนคนนึงของลูกเป็นเด็กเกเร เราก็สรุปไม่ได้ว่าเพื่อนคนอื่นของลูกต้องเกเรตามไปด้วย เช่นเดียวกันการเลือกจะเชื่อข้อมูลเพียงตัวเดียวที่อยู่ใกล้สุด แล้วสรุปทันทีว่าข้อมูลของเราน่าจะเป็นประเภทนั้นก็ไม่เหมาะสมเช่นกัน

ถ้าให้ดาวสีชมพูคือสิ่งที่เราต้องการจำแนกประเภท ด้วยหลักการของ Nearest Neighbor จะได้ว่า วงกลมสีม่วงทางซ้ายมืออยู่ใกล้สุด หากเราใช้ข้อสรุปนี้เป็นผลลัพธ์ย่อมผิดทันที ข้อมูลในกราฟทำให้เราทราบว่าดาวสีชมพูของเราแท้จริงแล้วควรเป็นประเภทเดียวกับวงกลมสีเขียว นั่นเพราะดาวของเราถูกล้อมไปด้วยวงกลมสีเขียวมากกว่านั่นเอง

เมื่อข้อมูลเพียงตัวเดียวไม่เพียงพอต่อการสรุปผล เราจึงต้องการข้อมูลมากกว่าหนึ่งตัว หากเราใช้ข้อมูลทั้งหมด 3 ตัวในการพิจารณาผลลัพธ์ของเราจะถูกต้องมากขึ้น ดังนี้

จากกราฟเมื่อพิจารณาข้อมูลที่อยู่ใกล้ดาวสีชมพูมากสุด 3 ตัว พบว่าประกอบด้วย วงกลมสีเขียว 2 วง และวงกลมสีม่วงอีก 1 วง เนื่องจากจำนวนวงกลมสีเขียวมีมากกว่า จึงสรุปได้ว่าดาวสีชมพูจำแนกได้ประเภทเดียวกับวงกลมสีเขียวนั่นเอง

วิธีการที่แสดงในหัวข้อนี้ เพื่อนๆจะพบว่าเราใช้ข้อมูลมากกว่าหนึ่งตัวในการพิจารณา วิธีการนี้จึงเรียกว่า k-Nearest Neighbors เมื่อ k คือจำนวนข้อมูลที่อยู่ใกล้สิ่งที่เราต้องการพิจารณามากสุด

เราควรเลือกจำนวน k เป็นเท่าไหร่?

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

กรณีที่เรามี attributes ให้พิจารณาเพียงสองตัว เช่นจำนวนฉากตบและจำนวนฉากจูบ เช่นนี้เราควรเลือก k ให้เป็นเลขคี่ เช่น 3, 5, 7, ... เพื่อป้องกันปัญหาที่ข้อมูลเราเป็นได้ทั้งสองประเภท เช่น หากเลือก k = 4 (เลขคู่) ย่อมมีโอกาสที่ข้อมูลที่จะทดสอบอยู่ใกล้ข้อมูล 2 ตัวที่มาจากประเภท A และอยู่ใกล้ข้อมูลอีก 2 ตัวที่มาจากประเภท B ที่นำไปสู่ข้อสรุปที่ไม่ลงตัวว่าสุดท้ายจะเป็นประเภท A หรือ B ดีนั่นเอง

การเลือก k เป็นจำนวนคี่ไม่สามารถแก้ปัญหาดังกล่าวได้สำหรับจำนวน attributes ที่มากกว่าสองตัว เช่น เลือก k = 7 สำหรับ attributes 3 ตัว มีโอกาสที่่ข้อมูลทดสอบจะใกล้ข้อมูลจากประเภท A จำนวน 2 ตัว, ใกล้เคียงข้อมูลจากประเภท B จำนวน 2 ตัว และใกล้เคียงกับข้อมูลจากประเภท C อีก 1 ตัว จึงสรุปไม่ได้ว่าข้อมูลทดสอบควรเป็นประเภท A หรือ B ดี?

สมการเพื่อวัดระยะทาง

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

ทฤษฎีบทของปิทาโกรัสกล่าวไว้ว่า กำลังสองของด้านตรงข้ามมุมฉาก = ผลรวมของกำลังสองของด้านประชิดมุมฉาก

อาศัยทฤษฎีบทปิทาโกรัส เราสามารถหาระยะทางจากจุดในกราฟสองจุดใดๆได้ ดังนี้

เมื่อเราต้องการหาระยะทางจากจุด $(x_1, y_1)$ ไปยังจุด $(x_2, y_2)$ เมื่อกำหนดให้ d แทนระยะทาง จะได้ว่า

$d^2 = {(x_2 - x_1)}^2 + ({y_2 - y_1 })^2$ จากทฤษฎีบทปิทาโกรัส

จะได้ $d = \sqrt{{(x_2 - x_1)}^2 + ({y_2 - y_1 })^2}$

จากสมการดังกล่าวเป็นการหาระยะทางที่เรียกว่า Euclidean Distance ในระบบพิกัดฉากสองมิติ จึงใช้ได้กับการหาระยะของข้อมูลที่ attributes เป็นจำนวน 2 ตัวเท่านั้น หาก attributes มีจำนวน 3 ตัว ก็จะอิงจากปริภูมิสามมิติแทน

ระยะทางระหว่างสองข้อมูลที่มี 2 attributes = $\sqrt{{(x_2 - x_1)}^2 + ({y_2 - y_1 })^2}$ (ผู้อ่านที่ไม่สันทัดคณิตศาสตร์ สามารถข้ามย่อหน้านี้ได้ครับ) โดยทั่วไปการหาระยะทางในปริภูมิ n ใดๆ Euclidean Distance ระหว่างจุด $x = (x_1,...,x_n)$ และ $y = (y_1,...,y_n)$ จะเท่ากับ $d_E(x, y) = \sqrt{\sum_{i=1}^{n}(x_i - y_i)^2}$

กลับมาที่ตัวอย่างของเรากันครับ เมื่อเราต้องการหาระยะทางจากละครเรื่องตบแล้วจูบไปยังละครเรื่องอื่นๆด้วยวิธีการของ Euclidean Distance จะได้

สมการ: $d = \sqrt{(จำนวนฉากตบ - 9)^2 + (จำนวนฉากตบ - 4)^2}$ โดย 9 คือจำนวนฉากตบของเรื่องตบแล้วจูบ และ 4 คือจำนวนฉากจูบของละครตบแล้วจูบ

เมื่อพิจารณาที่ k = 3 จึงได้ว่าละครเรื่องตบแล้วจูบมีระยะทางใกล้สุดสามอันดับคือ แรงเงา, พิษสวาท และนาคี จึงสรุปได้ว่าละครเรื่องตบแล้วจูบเป็นละครประเภทโรแมนติกนั่นเอง

การจัดการกับข้อมูลที่ไม่ใช่ตัวเลข

Attribute ของเราไม่จำเป็นต้องเป็นแค่ตัวเลขเสมอไป กรณีที่เราศึกษา attributes สองตัวคือ กินวิตามินซีเป็นประจำหรือไม่ กับ อุณหภูมิของอากาศขณะนั้น (หน่วยเป็น Celcius) พบว่า attribute ตัวแรกให้ผลเป็น boolean คือค่าจริงหรือเท็จเท่านั้น เพราะว่า attribute นี้มีค่าไม่ใช่ตัวเลข เราจึงต้องเปลี่ยนแปลงค่าดังกล่าวให้เป็นตัวเลขเสียก่อน เพื่อให้สามารถคำนวณหาระยะทางได้

กรณีของค่า boolean เราสามารถเปลี่ยนค่า true ให้เป็น 1 และค่า false ให้เป็น 0 ได้ ดังนี้

ปัญหาจากช่วงกว้างของ Attributes ที่ต่างกัน

จากตารางแสดงผลของการกินวิตามินซีเป็นประจำและสภาพอากาศที่มีผลต่ออาการหวัด เมื่อเทียบข้อมูลที่เราต้องการจำแนกประเภท (ข้อมูลตัวสุดท้ายของแถว) กับข้อมูลแถวแรกสุด จากสมการของ Euclidean Distance จะได้ว่า

$d = \sqrt{{(1 - 0)}^2 + ({25 - 8})^2}$

เนื่องจาก attribute ชื่อ กินวิตามิน C เป็นประจำ มีค่าเป็น 1 หรือ 0 ได้เท่านั้น แต่ค่าของอุณหภูมิมีช่วงที่กว้างกว่า จากสมการข้างบนจึงทำให้เห็นว่าเราให้ความสำคัญกับอุณหภูมิมากกว่าการกินวิตามินซีเป็นประจำตามไปด้วย (พจน์แรกคือ 1 - 0 มีค่าน้อยกว่าพจน์หลังคือ 25 - 8 อย่างมีนัยสำคัญ)

วิธีการ Normalize Attributes

เพื่อแก้ปัญหาดังกล่าว เราจึงต้องทำให้ช่วงกว้างของแต่ละ attributes มีค่าเท่ากัน นั่นคือให้ช่วงของข้อมูลเริ่มตั้งแต่ 0 แต่ไม่เกิน 1 เรียกว่าการทำ Normalize Attributes

ก่อนการทำ Normalize Attributes ข้อมูลที่เรามีอยู่จะมีช่วงกว้างจาก MIN ถึง MAX เช่น อุณหภูมิตามตารางข้างบนต่ำสุดคือ 5 (MIN) และสูงสุดคือ 30 (MAX) ภายหลังจากการทำ Normalize Attributes เราต้องการให้ข้อมูลต่ำสุดมีค่าเป็น 0 และข้อมูลสูงสุดมีค่าเป็น 1

ให้วงกลมสีชมพูคือตำแหน่งของข้อมูล จากกฎของสัดส่วนจะได้ว่า

$\frac{d_0}{MAX - MIN} = \frac{d_1}{1 - 0}$

$\frac{X_0 - MIN}{MAX - MIN} =d_1$

$d_1 = \frac{X_0 - MIN}{MAX - MIN}$

นั่นคือ ค่าใหม่ของข้อมูล ($d_1$) = $\frac{X_0 - MIN}{MAX - MIN}$

จากตารางข้างต้น พบว่าค่าสูงสุดของ กินวิตามินซีเป็นประจำ คือ 1 โดยมีค่าต่ำสุดคือ 0 สำหรับค่าสูงสุดของ อุณหภูมิ คือ 30 โดยมีค่าต่ำสุดคือ 5 อาศัยความจริงข้อนี้สามารถ Normalize Attributes ได้ดังนี้

จะพบว่าหลังผ่านการ Normalize ค่าใหม่ของแต่ละข้อมูลจะมีค่าตั้งแต่ 0 แต่ไม่เกิน 1 สำหรับค่าของ กินวิตามิน C ประจำ มีค่าข้อมูลเป็นเพียง 0 และ 1 เท่านั้นอยู่แล้ว จึงถือว่าเป็นการ Normalize ข้อมูลแล้ว

เมื่อกระทำการ Normalize Attributes เป็นที่เรียบร้อย ค่าข้อมูลใหม่ที่ได้จะอยู่ในช่วงกว้างเดียวกัน ทำให้การคำนวณระยะทางไม่เทน้ำหนักไปที่ตัวแปรใดตัวแปรหนึ่ง หลังจากผ่านขั้นตอนนี้แล้วจึงนำเข้าสู่การหา k-Nearest Neighbors ต่อไป

Weighted Nearest Neighbors คืออะไร

พิจารณาการจำแนกประเภทต่อไปนี้ที่ k = 5

เราต้องการทราบว่าจุดสีชมพูถือเป็นข้อมูลประเภทใด เราจึงเลือก k = 5 มาพิจารณา เนื่องจากภายใต้ k = 5 ทำให้จุดที่เป็นลบ (-) มีจำนวนมากกว่าจุดที่เป็นบวก (+) จึงสรุปได้ว่าจุดสีชมพูของเราเป็นข้อมูลประเภทเดียวกันกับข้อมูลลบ (-)

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

เพื่อให้การคำนวณของเราแม่นยำมากขึ้น เราต้องมีการให้น้ำหนักแต่ละจุดของเรา สำหรับ k neighbors ใดๆ เราจะเรียงระยะทางจากน้อยไปมาก นั่นคือ $d_1,...d_k$ จะเป็นระยะทางที่เราเรียงจากน้อยไปมาก โดย $d_1$ เป็นระยะทางที่น้อยที่สุด

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

$w_i = \frac{d_k - d_i}{d_k - d_1}$

กรณีของสูตรข้างต้น เราจะพิจารณาเมื่อ $d_k \neq d_1$ หาก $d_k = d_1$ แล้วจะได้ว่า $w_i = 1$ จึงสรุปได้ว่า

$w_i =\begin{cases}\frac{d_k - d_i}{d_k - d_1} , d_i \neq d_k\\ 1, d_1 = d_k\end{cases}$

จากสมการถ่วงน้ำหนักนี้ทำให้น้ำหนักของเรามีค่าอยู่ตั้งแต่ 0 แต่ไม่เกิน 1 วิธีการจำแนกประเภทถ่วงน้ำหนักนี้เรียกว่า Weighted Nearest Neighbors

เมื่อได้น้ำหนักของแต่ละจุดแล้ว ให้รวมน้ำหนักของจุดแต่ละประเภทเข้าด้วยกัน น้ำหนักของจุดประเภทไหนมากกว่ากัน ถือว่าข้อมูลที่เราต้องการสอบถามมีประเภทเดียวกับชุดข้อมูลนั้น

จากตัวอย่างข้างต้น หากระยะทางจากจุดสีชมพูไปยังจุดต่างๆเป็นดังนี้

เมื่อเรียงลำดับระยะทางแต่ละจุดจากน้อยไปหามาก จะได้ 2, 3, 5, 6, 8 นั่นคือ $d_1 = 2$, $d_2 = 3$, $d_3 = 5$, $d_4 = 6$ และ $d_5 = d_k = 8$ โดย $d_i$ คือค่าระยะทางเดิมของแต่ละจุด แทนค่าลงในสมการจะได้การถ่วงน้ำหนักใหม่ดังนี้

จาก $w_i = \frac{d_k - d_i}{d_k - d_1}$

สำหรับจุดบวก (+) แรก จะได้

$d_1 = \frac{8 - 2}{8 - 2} = 1$

สำหรับจุดบวก (+) ที่สอง จะได้

$d_2 = \frac{8 - 3}{8 - 2} = 0.83$

คำนวณน้ำหนักสำหรับจุดลบ (-) จะได้

$d_3 = \frac{8 - 5}{8 - 2} = 0.5$

$d_4 = \frac{8 - 6}{8 - 2} = 0.33$

$d_5 = \frac{8 - 8}{8 - 2} = 0$

เมื่อคำนวณน้ำหนักเรียบร้อย เราจะมานับน้ำหนักตามประเภทกันครับ

สำหรับประเภทลบ (-) น้ำหนักรวมเท่ากับน้ำหนักของ $d_3 + d_4 + d_5 = 0.5 + 0.33 + 0 = 0.83$ สำหรับประเภทบวก (+) น้ำหนักรวมเท่ากับน้ำหนักของ $d_1 + d_2 = 1 + 0.83 = 1.83$

พบว่าน้ำหนักรวมของประเภทบวกมากกว่าน้ำหนักรวมของประเภทลบ ด้วยวิธีการของ Weighted Nearest Neighbors จึงสรุปได้ว่า จุดสีชมพูเป็นประเภทเดียวกับข้อมูลบวก (+)

สรุป

อาศัยข้อมูลที่เราจำแนกประเภทไว้ก่อนแล้ว k-Nearest Neighbors ทำให้เราทราบประเภทข้อมูลของสิ่งของที่เรายังไม่เคยจำแนกมาก่อนได้ ในการใช้งานจริงยังมีเงื่อนไขบางอย่างที่เราต้องพิจารณาเป็นพิเศษ เช่นการกำจัดข้อมูลที่ไม่จำเป็นหรือข้อมูลที่มีแล้วจะทำให้ผลลัพธ์ผิดพลาด และนี่คือสิ่งที่เราจะศึกษากันในหัวข้อถัดไปกับเทคนิคที่มีชื่อว่า Tomek Links โปรดติดตามครับ

เอกสารอ้างอิง

Miroslav Kubat. (2015). An Introduction to Machine Learning. Coral Gables: Springer.

Peter Harrington. (2012). Machine Learning in Action. Shelter Island: Manning.