(https://www.sciencemag.org/news/2017/04/how-many-tree-species-are-there-more-you-can-shake-stick-new-database-reveals)

Tree-based Algorithms แบบ High Level

บทความนี้มีจุดประสงค์เพื่ออธิบาย Tree-based Algorithms แบบสั้นๆ เข้าใจง่าย (ไม่มี Math) เหมาะสำหรับคนทั่วไป หรือคนที่กำลังเริ่มทำงานสาย Data จะประกอบไปด้วย Algorithms อย่าง Decision Tree ไปจนถึง Random Forest และ Gradient Boosting Decision Tree

ก่อนจะไปถึงเนื้อหา ผมขอเกริ่นการทำงานของอาชีพสายงาน Data Science คร่าวๆ ให้ผู้อ่านทั่วไปเข้าใจเสียหน่อย การทำงานของ Data Science ส่วนใหญ่เราจะนำข้อมูลมาวิเคราะห์ เพื่อให้เกิดประโยชน์ต่อองค์กรหรือหน่วยงานที่เราทำอยู่ ไม่ว่าจะเป็นการทำนายเครดิตของคนที่จะมาขอเงินกู้ การหาว่าลูกค้าคนไหนสมควรได้รับผลิตภัณฑ์ตัวไหนบ้าง การทำนายราคาอสังหาริมทรัพย์ หรือการตรวจจับความผิดปกติของสัญญาณ ซึ่งเราจะใช้

คณิตศาสตร์ + ข้อมูล

มายำรวมกัน จนเกิดสิ่งที่เรียกว่า Model ซึ่งเจ้าสิ่งนี้จะสามารถทำนายค่าต่างๆ ออกมาได้นั่นเอง โดยส่วนใหญ่โจทย์ในสายงานนี้จะเป็นโจทย์ที่ต้องใช้ Model แบบ Supervised Learning

อธิบายเพิ่มเติม

Supervised Learning: การที่ Model เรียนรู้แบบมีคำตอบ คือการที่เราสอน Model ว่ามีค่า Input มาแบบนี้ จะได้คำตอบเป็นเท่าไหร่ เช่น มีข้อมูล Input เป็น รูป/ลักษณะของสัตว์ต่างๆ และเรามีเฉลยว่าแต่ละรูป/ลักษณะคือสัตว์ประเภทไหน เป็นหมาหรือแมว

Unsupervised Learning: การให้ Model เรียนรู้แบบไม่มีคำตอบ คือให้ Model หาคำตอบในสิ่งที่เราต้องการ เช่น เราอยากได้การจัดกลุ่มประเภทของสัตว์ โดยมีข้อมูล Input รูป/ลักษณะของสัตว์คล้ายๆ กันกับข้อก่อนหน้านี้ ที่นี้ Model จะบอกได้แค่ว่ากลุ่ม 1 จะมีลักษณะแบบนี้ กลุ่ม 2 จะมีลักษณะอีกแบบหนึ่ง ซึ่งเราต้องมาหาคำตอบต่อเองว่ากลุ่ม 1 และกลุ่ม 2 มีลักษณะเป็นหมาหรือแมว

Supervised Learning vs Unsupervised Learning (Source)

กลับมาที่หัวข้อกันดีกว่า

สิ่งที่ทำให้ผมสนใจและอยากนำเสนอ Tree-based Algorithms นั้น เป็นเพราะว่า Model ที่ใช้ Algorithms ประเภทนี้ จะเก่งในการแก้ปัญหาแบบ Supervised มีประสิทธิภาพในการทำนายแม่นยำมาก และค่อนข้างอธิบายได้ง่าย เหมาะสำหรับการนำผลลัพธ์ไปอธิบายคนอื่นที่ไม่ได้อยู่วงการนี้ ให้ผู้ฟังสามารถเข้าใจการทำงานหรือคำตอบของ Model ได้อย่างดี

ด้วยเหตุนี้เองจึงเป็นสิ่งที่ฮิตในหมู่ของ Data Scientist อย่างมาก อย่างเจ้า XGBoost ก็ตระเวนกวาดรางวัลชนะเลิศอันดับ 1 ใน Kaggle มามากมายเลยทีเดียว (แพลตฟอร์มที่มีการแข่งขันทางด้าน Data Science)

Tree-based Algorithms คืออะไร

ชื่อก็บอกแล้วครับว่าไอเดียริเริ่มมาจากต้นไม้แน่นอน เริ่มจากลำต้น จากนั้นก็แตกเป็นกิ่งเป็นใบออกมา ซึ่งแต่ละใบเปรียบเสมือนคำตอบที่ Algorithms จะทำนายออกมา ซึ่งคำตอบจะขึ้นอยู่กับการแบ่งของกิ่งและใบ Tree-based Algorithms ยุคแรกๆ เนี่ยเกิดจากต้นไม้เพียงต้นเดียวที่เรียกว่า…

Decision Tree (DT) หรือ ต้นไม้ตัดสินใจ

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

เรามาลองดูตัวอย่างเพื่อทำความเข้าใจมากขึ้นดีกว่าครับ

ตัวอย่าง

สมมุติเรามีโจทย์อยู่ว่า “ประชากรแบบไหนมีพฤติกรรมชอบเล่นเกมบ้าง?”

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

เมื่อ Model เรียนรู้เสร็จแล้ว แต่ละส่วนของต้นไม้จะเสมือนเป็น Rule-based ดังรูปตัวอย่าง

ตัวอย่าง ประชากรแบบไหนมีพฤติกรรมชอบเล่นเกมบ้าง ของ Decision Tree

จากรูปตัวอย่างจะเห็นได้ว่า DT นั้นก็คือ Rule Base หลายๆ ข้อมาใช้ร่วมกันครับ เช่น การแบ่งส่วนแรก (ราก/ลำต้น หรือ Root Node) ของต้นไม้จะเห็นว่า อายุ > 40 ปี จะถูกแบ่งกลุ่มข้อมูลออกมาเป็น 2 กลุ่ม ซึ่งการแบ่งครั้งนี้ยังไม่สามารถตอบได้ชัดเจนว่ากลุ่มไหนเล่นเกมบ้าง จึงต้องมีการแบ่งกลุ่มต่อไปอีก โดยจะใช้ข้อมูลระยะเวลาอ่านหนังสือในแต่ละวัน (Decision Node) ในการแบ่งต่อไป

เมื่อแบ่งรอบ 2 แล้วจะเห็นว่า คนที่อายุ > 40 ปีและอ่านหนังสือ > 2 ชม./วัน (ก้านขวา) จะเป็นคนที่ไม่เล่นเกม แต่ถ้าอ่าน ≤ 2 ชม./วัน จะถูกจำแนกเป็นกลุ่มของคนเล่นเกม

อธิบายเพิ่มเติม

Root Node: ที่อยู่ของข้อมูลทั้งหมด หรือกลุ่มตัวอย่างที่เราต้องการทำนายอะไรสักอย่างหนึ่ง

Decision Node: ที่อยู่ของกลุ่มที่ถูกแบ่งออกมาจากกิ่งแรกเริ่มหรือกิ่งก่อนหน้า

Leaf/ Terminal Node: กลุ่มที่จะไม่ถูกแบ่งอีกแล้ว หรือก็คือกลุ่มของคำตอบ

สำหรับเพื่อนๆ คนไหนที่สงสัยว่าเจ้าต้นนี้รู้ได้อย่างไรว่าควรใช้คุณลักษณะไหนก่อนไหนหลัง (อายุ เป็นคุณลักษณะแบ่งแรก) แล้วแบ่งด้วยค่าเท่าไหร่ดี (ใช้อายุ 40 ปี เป็นค่าแบ่ง) จะเอาค่าอะไรมาวัด

แนวคิดการเลือกคุณลักษณะและค่าแบ่งข้อมูลที่ดีที่สุดนั้นเกิดจากคำว่า…

“Impurity” หรือ ความไม่บริสุทธิ์

เป็นค่าที่ใช้วัดว่าข้อมูลที่ถูกแบ่งนั้นแบ่งได้ดีแค่ไหน (แบ่งแล้วยังมีคนเล่นเกมปนกับคนไม่เล่นอยู่มากหรือน้อย) นอกจากจะใช้เพื่อหาคุณลักษณะและค่าแบ่งข้อมูลที่ดีที่สุดในแล้ว ยังใช้เพื่อหยุดการเจริญเติบโตของต้นไม้อีกด้วย โดยการวัด Impurity มี 3 วิธี ได้แก่ Entropy and Information Gain, Gini index และ Misclassification Error

ในบทความนี้ผมขอไม่ลงลึกเรื่องการคำนวณนะครับ แต่ถ้าเพื่อนๆ คนไหนสนใจคณิตศาสตร์ การคำนวณในการแบ่งของ DT สามารถอ่านต่อได้ที่ลิงก์นี้ครับ

จริงๆ แล้ว เจ้า DT ยังมีทางที่จะพัฒนาต่อไปได้อีก แต่เนื่องจากบางครั้งอาจเกิดปัญหา Over/Underfitting มากเกินไป จึงมีการพัฒนา DT ต่อยอดขึ้นไปอีกด้วยวิธีการที่เรียกว่า “Ensemble”

อธิบายเพิ่มเติม

Overfitting: การที่เราให้ Model เรียนรู้และจดจำจากข้อมูลมากเกิน จนทำให้ Model นั้นทำนายถูกทั้งหมดเมื่อใช้ข้อมูลที่สอนไป กลับกันเมื่อเจอข้อมูลที่ไม่เคยเห็นมาก่อน Model ก็จะทำนายผิดพลาด

Underfitting: การสอนให้ Model เรียนรู้น้อยเกินไป ทำให้ไม่สามารถทำนายได้ถูกต้องเท่าที่ควร

ลักษณะของ Model ที่มี Prediction แบบ Over/Under fitting, เส้นประคือค่าที่ Model ทำนาย และจุดเขียวคือค่าที่ควรจะเป็น (Source)

Ensemble Methods หรือ วิธีรวมเข้าด้วยกัน

วิธีการ Ensemble พูดง่ายๆ คือ การรวมกันของหลายๆ Model นั่นเอง สามารถแบ่งได้เป็น 2 กลุ่มแนวคิด

1. แนวคิดที่สร้าง Model หลายๆ Model ที่เป็น “อิสระ” ต่อกันมาช่วยกันทำนายผลลัพธ์ให้ได้ดียิ่งขึ้นโดยใช้ค่าเฉลี่ยหรือโหวต (Parallel Ensemble Methods)
2. แนวคิดที่สร้าง Model “ขึ้นอยู่กับ” Model ก่อนหน้ามาทำนาย โดยมีการให้น้ำหนักผลทำนายที่ผิดพลาดของ Model ก่อนหน้าเพิ่มมากขึ้น ทำให้ผลการทำนายในปัจจุบันดียิ่งขึ้น (Sequential Ensemble Methods)

การประยุกต์ Ensemble กับ Decision tree มี 2 สายหลักๆ คือ Bagging (Bootstrap Aggregation) และ Boosting

Bagging จะมาช่วยในเรื่องของการลด Overfitting
ส่วน Boosting จะช่วยในการลด Underfitting

สาย Bagging

เมื่อนำมารวมกับ DT จะก่อให้เกิด Algorithm ชื่อดังอย่าง Random Forest

Random Forest (RF) หรือ ป่าแบบสุ่ม

หลักการของ RF นั้นเริ่มจาก Bagging Decision Tree ที่ทำเพียงแค่สร้าง DT หลายๆ ต้นแบบอิสระต่อกัน โดยสุ่มข้อมูลมาให้ Model เรียนรู้ และสามารถสุ่มซ้ำได้ด้วย ทั้งนี้ไม่ใช่แค่สุ่มแค่ข้อมูลมาสอน Model เพียงอย่างเดียวเท่านั้น แต่ RF จะมีการเพิ่มการสุ่มคุณลักษณะ (Feature) เพื่อใช้ในการแบ่งกลุ่มตัวอย่างเข้ามาอีกที

ขั้นตอนนี้จะถูกใช้ตอนสร้าง Model ว่าจุดแบ่งไหนควรใช้คุณลักษณะไหน โดยปกติแต่ละจุดแบ่งนั้นจะทำการเลือกคุณลักษณะที่ดีที่สุดในการแบ่ง แต่ของ RF คุณลักษณะตรงนี้จะถูกจำกัดการเลือกโดยการสุ่มไว้ เช่น คุณลักษณะที่สามารถเลือกใช้เพื่อแบ่งเหลือแค่ 70% จากคุณลักษณะทั้งหมด (Ex. การสุ่มเลือกคุณลักษณะ 70 ตัว จากทั้งหมด 100 ตัว และนำ 70 ตัวนี้ไปหาคุณลักษณะในการแบ่งที่ดีที่สุด)

จากนั้นแต่ละต้นก็จะทำนายผลลัพธ์ออกมา ซึ่งผลลัพธ์สุดท้ายจะมาจากการโหวตค่าที่เหมือนกันมากที่สุด หรือค่าเฉลี่ยของทุกต้นนั่นเอง

Random Forest Structure

จะเห็นได้ว่าแนวคิด DT ที่มีการ Ensemble แบบ Bagging นั้นจะมาแก้ปัญหาการ Overfitting ของการทำนาย จากการพยายามใช้ต้นไม้หลายๆ ต้นที่มีอิสระต่อกันมาถ่วงน้ำหนักเพื่อลดการ Overfitting

สาย Boosting

ในส่วนของ DT นั้นจะมี Algorithm ชื่อดังอย่าง Gradient Boosting Tree

Gradient Boosting Decision Tree (GBDT) หรือ …?

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

Gradient Boosting Decision Tree Structure

แนวโน้มของ ความผิดพลาด (Error) กับ จำนวน Model ที่เพิ่มขึ้น

จะเห็นได้ว่าจากแนวคิด DT ที่มีการ Ensemble แบบสาย Boosting จะทำให้ Model มีประสิทธิภาพการทำนายแม่นยำกว่าสาย Bagging แต่ก็มีข้อเสียคือต้องแลกมากับการทำให้ Model มีโอกาส Overfitting ได้ง่ายมากขึ้น

ก่อนจะจบบทความผมขอแถม Tree-based Algorithms อีกสักตัวหนึ่ง เป็นตัวที่ผมชื่นชอบอย่างมากครับ

eXtreme Gradient Boosting (XGBoost)

XGBoost เป็น Algorithm สาย Boosting ที่เรียกได้ว่าฮิตกันมากในวงการ Data Science มีการนำไปใช้และได้รับรางวัลอันดับ 1 ในการแข่งขันมากมาย

หลักการของ XGBoost คล้ายกับ GBDT เลยครับ เพราะถูกพัฒนามาจาก GBDT เพียงแต่ว่า XGBoost มีการทำ Regularization เพื่อลด Overfitting เข้ามา ช่วยแก้ปัญหาของ GBDT ที่ Overfitting ได้ง่ายมาก รวมถึงความเร็วในการเรียนรู้ของ Model ที่เร็วกว่า GBDT อีกด้วย

Regularization ของ XGBoost

ผมขอย้อนไปที่ GBDT สักนิดครับ เพื่อนๆ พอจะรู้คร่าวๆ แล้วว่า GBDT นั้น เวลาสร้าง Model ขึ้นมาจะเกิดจากต้นไม้ หลายต้นต่อกัน ต้นปัจจุบันจะพยายามเอาการทำนายที่ผิดพลาดของต้นก่อนมาทำนายให้ถูกต้องด้วยการปรับน้ำหนักของต้นไม้ ซึ่งการปรับน้ำหนักตรงนี้แหละที่ XGBoost มีการใส่ตัวแปร Regularized เข้าไปเพื่อลด Overfitting

ขั้นตอนการคำนวณหาค่าถ่วงน้ำหนักของ GBDT จะมี 2 ขั้นตอน 1) การคำนวณหาความผิดพลาดของรอบก่อน 2) การคำนวณหาค่าน้ำหนักของการปรับน้ำหนักของต้นไม้ ซึ่งในจุดนี้ XGBoost ได้ทำการรวบ 2 ขั้นตอนของ GBDT เข้าด้วยกัน และเพิ่มตัวแปร Regularized เข้ามาครับ

กล่าวได้ว่า GDBT พยายามจะลดการทำนายผิดของต้นก่อนหน้า โดยการปรับน้ำหนักที่ผลลัพธ์สุดท้ายของต้นปัจจุบันให้มีการทำนายที่ผิดพลาดน้อยที่สุด (ส่วนใบของต้นไม้) แต่ XGBoost จะมองถอยออกมา 1 ขั้น (ส่วนกิ่งและใบของต้นไม้) คือพยายามปรับโครงสร้างต้นไม้และค่าถ่วงน้ำหนักเพื่อให้สิ่งที่ทำนายพลาดในรอบก่อนถูกต้องมากขึ้น ส่งผลให้ Overfitting ของ XGBoost น้อยกว่า GDBT

ถ้าเพื่อน ๆ สนใจรายละเอียด XGBoost มากกว่านี้ สามารถตามอ่านต่อได้ที่บทความ “ชวนกันมาอ่าน Paper ที่ชนะ Kaggle กัน” ซึ่งเป็นบทความที่มาที่ไปของ XGBoost

สรุป

จะเห็นได้ว่าจุดเริ่มต้นของ Algorithms สาย Tree นั้นเป็นเพียงแค่ Rule-based แล้วมีการพัฒนาต่อยอดตามแนวคิดต่างๆ มากมายออกเป็นหลายแขนง แต่ละ Algorithms มีข้อดีข้อเสียแตกต่างกันไป ซึ่งสามารถนำไปใช้งานเพื่อตอบโจทย์ปัญหาลักษณะ Supervised ได้เป็นอย่างดี

จริงๆ แล้ว Tree-based Algorithms มีมากกว่าเนื้อหาที่ผมเอามาเขียนครับ ซึ่งบาง Algorithms ก็เป็นที่นิยมไม่แพ้กัน ไม่ว่าจะเป็น LightGBM, AdaBoost, CatBoost เป็นต้น

ก่อนจากกันไป

รู้สึกยังไงกันบ้างกับบทความนี้ คอมเม้นต์บอกผมได้เลยครับ นี่เป็นบทความแรกของผม ผมหวังว่าทุกคนที่เข้ามาอ่านบทความนี้จะได้รับแนวคิดไม่มากก็น้อยสำหรับ Tree-based Algorithms นะครับ อาจจะมีบางจุดที่งงๆ บ้าง ขออภัยมา ณ ที่นี้ด้วยครับ ผมจะนำคำวิจารณ์ไปปรับปรุงเพื่อให้ดียิ่งขึ้นสำหรับบทความหน้าๆ ครับ 😃

References
Tree-Based Algorithms: https://www.analyticsvidhya.com/blog/2016/04/tree-based-algorithms-complete-tutorial-scratch-in-python/
Supervised vs Unsupervised Learning:
https://www.boozallen.com/assets/boozallen_site/sig/pdf/infographic/how-do-machines-learn.pdf
Overfitting/Underfitting:
https://www.educative.io/edpresso/overfitting-and-underfitting
Decision Tree:
http://mlwiki.org/index.php/Decision_Tree_(Data_Mining)
Ensemble methods:
https://blog.statsbot.co/ensemble-learning-d1dcd548e936
Bagging/Boosting tree:
https://medium.com/analytics-vidhya/mathematics-behind-random-forest-and-xgboost-ea8596657275
The math behind GBM and XGBoost:
https://medium.com/analytics-vidhya/math-behind-gbm-and-xgboost-d00e8536b7de

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