Blockdit Logo (Mobile)
เขียนโค๊ดกับมากะปิ
•
25 ธ.ค. 2021 เวลา 17:53 • การศึกษา
Machine Hee-hee 101 EP4
Decision Tree EP 1
สวัสดีครับ ผมกะว่าจะโพสในช่วงคริสมาสแต่คงไม่ทัน เพราะว่าผมลืม Save ไว้แล้วต้องทำไม เศร้าจัด
แต่ไม่เป็นไรครับเพราะว่า ผมบันทึกฉบับ Demo ไว้ เศร้าเลย
ก็ขอให้ทุกคนเที่ยวให้สนุกนะครับ แล้วก็ขอให้ผ่านช่วงลำบากนี้ไปได้ด้วยดีครับ
สำหรับบทความครั้งก่อนเราพูดถึง Tree คร่าวๆแล้วนะครับ
สำหรับวันนี้เราจะพูดถึงการเลือก feature เข้ามาแต่ละ (node/block)
เพื่อทำนายผลลัพธ์จาก leaf
โดยครั้งนี้ผมว่าทุกคนคงปวดหัวโดยไม่น้อยเลย เพราะเราจะเข้าสู่การคำนวณกัน
เอาละเพื่อไม่ให้เป็นการเสียเวลา เรามาเริ่มกันเลย
ก่อนอื่นผมอยากให้ทุกคนรู้จัก ทฤษฎีสาระสนเทศ (Information Theory) ก่อนนะครับ
Information Theory
ทฤษฎีนี้ถูกคิดค้นโดย Claude Shannon ปี 1948
ซึ่งนำไปประยุกต์ในด้านการสื่อสาร
โดยทฤษฎีนี้ได้มีการสร้างฟังก์ชันชื่อ Entropy
Claude Shannon
What is Entropy ?
Entropy เป็นฟังก์ชันที่วัดคุณสมบัติของข้อมูลว่ามีการปะปนกันหรือไม่ (วัดว่ามันมีค่าเหมือนกันหรือไม่)
แล้วมันเกี่ยวอะไรกับ Decision Tree ?
คำตอบ : เราเอาทฤษฎีนี้มาใช้เป็นส่วนหนึ่งของการหา feature ที่สามารถแยกผลลัพธ์จากข้อมูลได้
  • 1.
    Pi คือสัดส่วนของข้อมูลในแต่ละคลาส
  • 2.
    C คือ ประเภทคลาสทั้งหมด
Note : สัดส่วนนี้จะคล้ายในวิชาสถิติ ในส่วนของความน่าจะเป็น
สรุปสูตรได้ดังนี้
สัดส่วน = ส่วนที่เราสนใจ/จำนวนทั้งหมด
Note 2 : คุณสมบัติของสัดส่วน
  • 1.
    สัดส่วนมีค่า 0 - 1 เท่านั้น
  • 2.
    มีความสัมพันธ์แบบ p = 1 - q โดย q คือสัดส่วนที่เราไม่สนใจ และ p คือสัดส่วนที่เราสนใจ
ตัวอย่างการคำนวณ Entropy
ข้อมูล = {no,no,no,no,no,no,no,yes,yes,yes}
ในข้อมูลนี้มี class เป็น 2 ประเภท คือ no และ yes
no มีทั้งหมด 7 ตัวอย่าง และ yes มีทั้งหมด 3 ตัวอย่าง
รวมแล้วมีข้อมูลทั้งหมด 10 ตัวอย่าง
เราสามารถหา Entropy จากสูตรได้ดังนี้
log ฐาน 2 นะครับ
7/10 คือสัดส่วนของ No (มี no เป็น 7 ในข้อมูลที่มีจำนวนทั้งหมด 10 ตัวอย่าง)
เราสามารถหา สัดส่วนของ yes โดยตรงหรือจะใช้คุณสมบัติก็ได้
p = 1 - q
ถ้าเราสนใจ no แล้ว p = 7/10 เราสามารถหาสิ่งที่ตรงกันข้ามได้ (q)
q = 1 - 7/10 => 3/10
เราสามารถสรุปสมบัติของ Entropy ได้ดังนี้
  • 1.
    Entropy = 0 แปลว่าไม่มีการปะปนของข้อมูล (ข้อมูลเหมือนกันทั้งหมด)
  • 2.
    Entropy = 1 แปลว่ามีการปะปนของข้อมูล (ข้อมูลแบ่งเท่ากัน)
  • 3.
    Entropy มีค่า 0 - 1
นอกจาก Entropy ที่สามารถแยกการปะปนของข้อมูลได้แล้ว ก็ยังมีอีกฟังก์ชันหนึ่งที่สามารถแยกการปะปนของข้อมูลได้เหมือนกัน นั้นคือ ...
Gini index
K คือ ประเภทคลาสทั้งหมด
Pi คือ สัดส่วนของข้อมูลในแต่ละคลาส
ถ้าเราใช้ตัวอย่างเดิม เราสามารถคำนวณได้ตามนี้ครับ
โอเคร เรารู้จักการหาค่าการปะปนของข้อมูลแล้ว ต่อไปเรามารู้จักฟังก์ชันที่ใช้ Gini หรือ Entropy ในการหา feature เพื่อเอามาสร้างเป็น node/block ดีกว่าครับ
ฟังก์ชันต่อไปที่จะเอามาใช้เรียกว่า function "Gain"
Gain
นิยามคือฟังก์ชันที่จะเลือก feature มาสร้างเป็น Node ในต้นไม้ ถ้า feature นั้นสามารถลดการปะปนของข้อมูลได้
Gain ที่ใช้ Entropy
Gain ที่ใช้ Gini
Gain จะใช้ Gini หรือ Entropy ก็ได้แต่ว่าต้องใช้อย่างใดอย่างหนึ่งตามสูตร
S คือ ข้อมูลทั้งหมด
A คือ feature
values(A) คือ ประเภทใน feature
V คือ สมาชิกประเภทใน feature
Sv คือ ข้อมูลประเภท V ที่อยู่ใน feature A
ผมเข้าใจว่าทุกคนคงสงสัยกับเครื่องหมายและสูตรของมัน แต่ไม่ต้องตกใจครับ ผมขอให้ทุกคนเข้าใจ 3 สิ่งนี้ก่อนครับ
  • 1.
    Entropy และ Gini เป็นตัวหาค่าการปะปนกันของข้อมูล
  • 2.
    Gain จะเป็นฟังก์ชันที่เอา Entropy หรือ Gini มาช่วยในการเลือก feature
  • 3.
    Gain สามารถเลือกใช้ได้ทั้ง Entropy และ Gini แต่ใช้ได้แค่ตัวเดียว
หลักการนำ Gain ไปใช้สำหรับ Decision Tree
Decision Tree จะมีการนำไปใช้ 2 วิธีคือ ID3 และ C4.5
  • ●
    ID3 จะเป็นการหา max Gain (ค่า gain ที่มากที่จาก feature ที่คำนวณมา)
  • ●
    C4.5 จะเพิ่มสูตรอีกนิดหน่อยเรียกว่า Gain Ratio ซึ่งใช้แทน max Gainโดยมันถูกสร้างมาแก้ปัญหา ID3 ดังนี้
  • 1.
    ขั้นตอน C4.5 สามารถเรียนรู้ชนิดตัวเลขได้
  • 2.
    ขั้นตอน C4.5 จะเพิ่มกระบวนการตัดเล็มต้นไม้ (Tree pruning) เพื่อแก้ปัญหา overfitting (พยายามทำให้เป็นต้นไม้ที่เล็กที่สุด)
ส่วนทำไมต้องเป็นต้นไม้ที่เล็กที่สุดผมได้กล่าวไปในบทที่แล้ว สามารถย้อนกลับไปอ่านได้นะครับ
ในคอร์สนี้จะแสดงการคำนวณแบบ C.45 และ ใช้ Gini เป็นหลักครับ
โอเคร เรามาดูสูตรของ Gain Ratio กัน
Feature ที่มีค่า Gain Ratio มากที่สุดจะคัดเลือกมาสร้าง Decision Tree
สำหรับบทความนี้ก็มีเท่านี้ครับ โดยตอนนี้เราก็มีเครื่องมือในการสร้าง Decision Tree ครบแล้วครับ
บทความหน้าผมจะพาทุกคนไปสร้างต้นไม้ดูครับ และ ต่อไปก็จะเป็นในส่วนการเขียนโปรแกรม
สำหรับคนที่ไม่เข้าใจสูตรก็ไม่เป็นไรครับ ขอแค่เข้าใจ 3 สิ่งที่ผมกล่าวไป,
ความแตกต่างระหว่า C.45 กับ ID3 และที่มาของ GainRatio ก็พอครับ
ครั้งหน้าผมจะอธิบายความหมายจากตัวอย่าง ซึ่งจะทำให้ทุกคนเข้าใจมากขึ้น
สำหรับวันนี้ขอบคุณผู้อ่านทุกท่าน หากมีข้อสงสัยหรือเพิ่มเติมสิ่งที่ผมพลาดลงไปสามารถเข้ามาคอมเม้น inbox ทั้งใน blockdit และ ทางเพจ FB นะครับสำหรับวันนี้สวัสดีครับ Merry Christmas Hee-Hee

ดูเพิ่มเติมในซีรีส์

โฆษณา