การทำ Classification Model ด้วยเทคนิค Support Vector Machine ที่ใช้ร่วมกับ Genetic Algorithm

วันนี้ผมจะมาเล่าถึงการทำ Classification Model ด้วยเทคนิค Support Vector Machine ร่วมกับ Genetic Algorithm ในการทำนายว่าข้อมูลที่เรามีสามารถจำแนกออกมาเป็นคลาสนั้นๆ ได้อย่างไร โดยวันนี้เราจะยกตัวอย่างสุดคลาสสิกที่เชื่อว่าสายโมเดลหลายคนน่าจะผ่านตากับ Dataset ชุดนี้มาพอสมควร นั่นคือ Titanic Dataset ทำนายว่าใครจะเป็นผู้รอดชีวิตจากเหตุการณ์เรือล่มครั้งนั้น เราจะแบ่งคลาสออกเป็น 2 คลาส คือผู้รอดชีวิตกับผู้เสียชีวิต แต่ก่อนเริ่ม Implement Code กัน ผมจะขออธิบายเกี่ยวกับแนวคิดของ Algorithm ให้ได้ทำความรู้จักสักหน่อยครับ

Support Vector Machine (Intro)

เริ่มต้นด้วย Support Vector Machine หรือที่รู้จักกันดีในชื่อ SVM เป็นหนึ่งในวิธีการทำ Classification โดยนำข้อมูลที่เรามีมาพล็อตให้อยู่บนกราฟ อาจจะเป็นรูปแบบ 2D หรือมากกว่านั้น ขึ้นอยู่กับจำนวน Feature ที่เราใส่เข้าไป จากนั้นโมเดลจะพยายามแบ่งคลาสด้วยการสร้างเส้นตรง (Hyperplane) ที่สามารถแบ่งข้อมูลออกเป็นกลุ่มได้อย่างแม่นยำที่สุดขึ้นมาบนกราฟ ดังรูปที่ 1

Fig.1 Shown how SVM Classification works

วิธี SVM นี้ได้รับความนิยมอย่างแพร่หลายในการทำโมเดล เนื่องจากมีความแม่นยำที่สูงและสามารถเข้าใจการทำงานได้ง่าย

Genetic Algorithm (Intro)

Genetic Algorithm คืออะไร? แล้วทำไมใช้แค่ SVM ถึงไม่พอ?

Genetic Algorithm (GA) เป็นหนึ่งในวิธีการทำ Feature Selection หรือกระบวนการคัดเลือก Input Variables ในกรณีที่เรามีจำนวน Variables เยอะมากๆ กระบวนการนี้จะช่วยลดจำนวนลง ในขณะที่หลักการทำงานของ SVM คือยิ่งมี Features ใส่เข้ามามาก มิติที่ถูกสร้างเพื่อทำการแบ่งคลาสยิ่งซับซ้อนขึ้น ส่งผลให้กระบวนการ Train Model ช้าลง รวมถึงหากเราไม่มีการคัดเลือกว่า Features ไหนเหมาะที่จะใส่เข้าไปก็อาจยิ่งทำให้โมเดลมีความแม่นยำลดลงไปอีกด้วย คล้ายๆ กับการทำ Optimize Parameter ก่อนเข้า SVM นั่นเอง

GA ถูกคิดค้นมาตั้งแต่ปี 1970 โดยคุณ John Henry Holland ผู้ได้รับแรงบันดาลใจมาจากหลักแนวคิดทางชีววิทยาเรื่องการคัดเลือกโดยธรรมชาติและการวิวัฒนาการของคุณ Charles Darwin ที่หลายคนน่าจะเคยเรียนกันมาบ้างในสมัยม.ปลาย พอได้ยินชื่อนี้ก็มักจะนึกถึงประโยค

“It is not the strongest of the species that survives, nor the most intelligent, but the one most responsive to change”

ทฤษฎีของเราจะคล้ายๆ กับประโยคนี้เลยครับ และต้องเตือนก่อนว่าในบทความนี้เราจะได้เจอคำศัพท์จากทางสายชีววิทยากันเล็กน้อย แต่ไม่ต้องห่วงครับ ผมจะค่อยๆ อธิบายไปพร้อมกับทุกคนเอง

เริ่มแรกผมอยากให้ทุกคนจินตนาการถึงการสร้างสายพันธุ์ขึ้นมาหนึ่งสายพันธุ์ เริ่มจากการสร้างประชากร ทั้งนี้เรายังไม่รู้ว่าจะต้องทำอย่างไรให้สายพันธุ์นั้นแข็งแกร่งต่อไปได้ จะต้องมีกี่มือ กี่ขา หางต้องมีไหม เราจะไม่สามารถล่วงรู้สิ่งเหล่านี้ได้ในช่วงแรก ดังนั้นเราจึงจะต้องทดลองสร้างขึ้นมาทั้งหมดแบบสุ่มๆ และวัดความแข็งแกร่งของแต่ละตัวว่าแบบไหนสามารถรอดชีวิตต่อไปได้ แต่ตัวที่แข็งแกร่งที่สุดในตอนนั้นก็ยังไม่ใช่ตัวที่ถือว่าแข็งแกร่งที่สุดอยู่ดี เพราะเมื่อลูกหลานชุดต่อไปถือกำเนิดขึ้น ยีนก็จะมีการพัฒนาต่อมาและเริ่มวัฎจักรไปเรื่อยๆ โดยท้ายสุดเราหวังว่าลูกหลานชุดสุดท้ายจะเป็นกลุ่มที่แข็งแกร่งที่สุด ทั้งหมดนี้คือกระบวนการของ GA ครับ หากเพื่อนๆ ยังไม่เห็นภาพ มาดู Flow Chart ต่อไปนี้กันครับ

Flowchart of Genetic Algorithm

Initialisation

ขั้นตอนแรกสุดคือการสร้างกลุ่มประชากร หรือการสุ่มสร้างกลุ่มตัวอย่างขึ้นมา เราจะแทนประชากรแต่ละคนว่า Chromosome โดยที่ต่างคนจะมีลักษณะเฉพาะที่แสดงออกไม่เหมือนกัน ส่วนที่เป็นตัวกำหนดบอกว่าเรามีลักษณะเฉพาะแบบไหนคือการรวมกันของชุด Features หรือยีนขึ้นมาชุดหนึ่ง แต่ละยีนจะมีการเข้ารหัสเป็น 0 กับ 1 เพื่อเป็นการบอกว่าประชากรตัวนั้นมียีนดังกล่าวแสดงออกมาหรือไม่ ดังรูปที่ 3

Fig.3 Shown Gene, Chromosome, and Population

Fitness Function

เมื่อถึงเวลาตัดสินว่าประชากรตัวไหนแข็งแกร่งกว่ากัน เราต้องอาศัยตัวช่วยอย่าง Evaluation Metric และตัวที่เราจะใช้กันคือ Fitness Values หรือ Accuracy จากการนำประชากรตัวนั้นมาสร้างโมเดลผ่าน SVM ตามที่บทความนี้ใช้

Selection

หลังจากผ่านกระบวน Fitness Function มาแล้ว ก็เข้าสู่กระบวนการ Selection หรือกระบวนการคัดสรร ประชากรทุกตัวจะได้รับการคัดเลือกว่าใครจะสามารถรอดชีวิตไปสร้างลูกหลานชุดถัดไปได้ โดยกระบวนการคัดสรรมีวิธีที่นิยมใช้กันด้วยกัน 2 วิธี คือ

1. Roulette Wheel เป็นการสุ่มเลือกคล้ายๆ กับเกม Roulette ทั่วไปตามคาสิโน แต่ในกรณีนี้ขนาดของช่องจะไม่เท่ากัน ขึ้นอยู่กับ Fitness Value ของ Chromosome นั้นๆ ยิ่งมีค่ามาก ยิ่งมีโอกาสได้รับการเลือกมาก ดังรูปที่ 4
2. Tournament Selection วิธีนี้เราจะสุ่มเลือกจากประชากรทั้งหมดมา 3 ตัว (แล้วแต่เรากำหนด) จากนั้นจะดูว่าโจทย์ของเราเป็นแบบไหน ถ้าเป็นแบบ Maximization Problem เราจะเลือกตัวที่มีค่ามากสุดจาก 3 ตัวที่สุ่มมาดังในรูปที่ 5 และถือว่า Fitness Value ที่เท่ากับ 9 คือผู้ชนะ แต่ถ้าหากโจทย์ของเราคือ Minimization Problem ผู้ชนะจะกลายเป็น Fitness Value อื่นแทน

Fig.4 Roulette Wheel

Fig.5 Tournament Selection

Crossover

ต่อมาเราจะเรียกประชากรที่รอดชีวิตว่าชุด Parents ด้วยลักษณะที่มากันเป็นคู่ จะมองว่าเป็นพ่อแม่คู่แรกก็ได้ครับ สมมติว่าพ่อและแม่มี 8 Features หรือยีนคนละ 8 ตัว จากการสุ่มของเราในรูปที่ 6 จะเห็นว่า Parents ทั้งสองมียีนเหมือนกันบางคู่ ในขณะที่บางตัวจะมีเฉพาะแค่คนใดคนหนึ่ง การที่เราจะพัฒนาไปสู่ยีนที่ดีกว่าได้คือพ่อแม่คู่นี้จะต้องมีลูก หรือ Offspring ผ่านขั้นตอนที่เรียกว่า Genetic Crossover ในรูปจะพบจุดตัดอยู่ 2 จุดที่เรียกว่า 2-Point Crossover โดยปกติจะเกิดจากการสุ่มตำแหน่งการตัด ซึ่งจำนวนจุดตัดจะขึ้นอยู่กับว่าเราต้องการให้เกิดความเปลี่ยนแปลงมากแค่ไหน สำหรับในกรณีตัวอย่าง เราต้องการให้การเปลี่ยนแปลงในรุ่นลูกค่อยๆ เกิดขึ้น มิเช่นนั้นอาจจะสูญเสียโอกาสที่จะทำให้เราเจอ Solution ดีๆ ไปด้วย

Fig.6 Shown Crossover Process

Mutation

เมื่อได้รุ่นลูกแล้ว กระบวนการถัดไปคือ Mutation หรือกระบวนการกลายพันธุ์เพื่อเพิ่มความหลากหลาย แต่โอกาสการเกิด Mutation นั้นจะต่ำมากเหมือนกับที่เกิดในสิ่งมีชีวิตจริงๆ เราจะตั้งค่าความน่าจะเป็นตรงนี้ไว้ที่ 0.1 (สามารถปรับเปลี่ยนได้แล้วแต่ผู้ใช้) นอกจากนี้ Mutation จะเกิดกับแค่บางยีนเท่านั้น ไม่ได้เกิดกับทั้ง Chromosome โดยเราจะ Random ค่าความน่าจะเป็นไปในยีนแต่ละตัวของรุ่นลูก และไล่เช็คไปทีละยีนว่ามีค่าความน่าจะเป็นต่ำกว่าค่าของการเกิด Mutation หรือไม่ ถ้าดูตามรูปที่ 7 จะเห็นว่ายีนลำดับที่ 1 ถึง 3 ของ Child#1 ไม่ถูกเปลี่ยน แต่ยีนลำดับที่ 4 ถูกเปลี่ยนจาก 1 เป็น 0

Fig.7 Shown Mutation Process

หลังจากที่ผ่านกระบวนการทั้งหมดแล้ว เราจะได้ Chromosome แตกต่างกันไป เราสามารถดูว่าชุด Chromosome ไหนมีค่าเหมาะสมที่สุดที่จะมีชีวิตรอดต่อไปเพื่อสร้างลูกหลาน และวนลูปกระบวนการใหม่อีกครั้งตาม Flowchart ข้างต้น

How to Implement with Python

ได้อ่านคำอธิบายแนวคิดกันไปแล้ว เรามาต่อในส่วนของการทดลองโจทย์จริงอย่าง Titanic Dataset กันบ้างครับ Pipeline ในการเขียนโค้ดจะเป็นตาม Flowchart ข้างล่างนี้

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

Source Code

หลังจากที่รันโมเดลตาม Source Code ที่ลงไว้ด้านบน จะเห็นว่าค่า Accuracy จากการใช้เพียง SVM อย่างเดียวจะได้ประมาณ 69.02% แต่เมื่อใช้ร่วมกับ GA จะทำให้ค่า Accuracy เพิ่มขึ้นเป็น 82.93% รวมถึงตัด Features เหลือเพียง 7 จาก 10 Feature ตั้งต้น

จบไปแล้วนะครับกับการทำ Classification Model เป็นอย่างไรกันบ้างครับกับบทความแรกของผม หวังว่าเพื่อนๆ จะได้เกร็ดความรู้จากบทความนี้ไม่มากก็น้อย และก็อย่าลืมทดลองใช้วิธีการนี้กับ Dataset ตัวเองนะครับ จะได้ดูว่าวิธีการนี้เหมาะสมกับข้อมูลของเราหรือไม่ ยิ่งถ้า Dataset ที่ใช้มี Feature จำนวนมากก็จะยิ่งเหมาะ เพราะเราจะได้ตัด Feature บางส่วนที่ไม่สำคัญทิ้งไปและสามารถอธิบายโมเดลของเราได้ดียิ่งขึ้นครับ

สำหรับชาวเทคคนไหนที่สนใจเรื่องราวดีๆแบบนี้ หรืออยากเรียนรู้เกี่ยวกับ Product ใหม่ๆ ของ KBTG สามารถติดตามรายละเอียดกันได้ที่เว็บไซต์ www.kbtg.tech