Lab 4: Decision Tree Classification

วัตถุประสงค์การเรียนรู้

เข้าใจหลักการทำงานของ Decision Tree Classifier
สามารถคำนวณ Entropy และ Information Gain
สามารถคำนวณ Gini Index
สามารถใช้ scikit-learn เพื่อสร้างและใช้งาน Decision Tree
สามารถแสดงผลและตีความ Decision Tree ที่สร้างขึ้น

ทฤษฎีเบื้องต้น

Decision Tree Classifier

Decision Tree เป็นอัลกอริทึมการจำแนกประเภท (Classification) ที่ใช้โครงสร้างแบบต้นไม้ในการตัดสินใจ โดยแต่ละ node ภายในจะเป็นการทดสอบเงื่อนไขของ feature และแต่ละ leaf node จะเป็นผลลัพธ์การจำแนกประเภท

ข้อดีของ Decision Tree:

เข้าใจและตีความได้ง่าย
ไม่ต้องการการปรับ scale ของข้อมูล
สามารถจัดการกับข้อมูลทั้ง numerical และ categorical ได้
สามารถมองเห็นกระบวนการตัดสินใจได้ชัดเจน

Entropy

Entropy เป็นการวัดความไม่แน่นอน (Uncertainty) หรือความไม่เป็นระเบียบ (Impurity) ของข้อมูล

สูตร Entropy:

H (S) = - \sum_{i = 1}^{c} p_{i} {log}_{2} (p_{i})

โดยที่:

$H (S)$ = Entropy ของเซต S
$c$ = จำนวนคลาสทั้งหมด
$p_{i}$ = สัดส่วนของตัวอย่างที่อยู่ในคลาส i

คุณสมบัติของ Entropy:

เมื่อข้อมูลทั้งหมดอยู่ในคลาสเดียวกัน: H(S) = 0 (Pure)
เมื่อข้อมูลกระจายเท่าๆ กันทุกคลาส: H(S) มีค่าสูงสุด

Information Gain

Information Gain คือการวัดว่าการแบ่งข้อมูลตาม feature ใด feature หนึ่งช่วยลด Entropy ได้มากเพียงใด

สูตร Information Gain:

IG (S, A) = H (S) - \sum_{v \in Values (A)} \frac{| S_{v} |}{| S |} H (S_{v})

โดยที่:

$IG (S, A)$ = Information Gain เมื่อแบ่งเซต S ด้วย feature A
$Values (A)$ = เซตของค่าที่เป็นไปได้ของ feature A
$S_{v}$ = เซตย่อยของ S ที่มีค่า feature A เท่ากับ v

Gini Index (Gini Impurity)

Gini Index เป็นอีกวิธีหนึ่งในการวัดความไม่เป็นระเบียบของข้อมูล

สูตร Gini Index:

Gini (S) = 1 - \sum_{i = 1}^{c} p_{i}^{2}

Gini Index สำหรับการแบ่ง:

{Gini}_{split} (S, A) = \sum_{v \in Values (A)} \frac{| S_{v} |}{| S |} Gini (S_{v})

คุณสมบัติของ Gini Index:

เมื่อข้อมูลทั้งหมดอยู่ในคลาสเดียวกัน: Gini(S) = 0 (Pure)
เมื่อข้อมูลกระจายเท่าๆ กันทุกคลาส: Gini(S) มีค่าสูงสุด

อัลกอริทึม ID3 และ CART

ID3 (Iterative Dichotomiser 3):

ใช้ Information Gain ในการเลือก feature
เหมาะกับ categorical features
สร้าง multi-way splits

CART (Classification and Regression Trees):

ใช้ Gini Index เป็นค่าเริ่มต้น
สร้าง binary splits เท่านั้น
รองรับทั้ง categorical และ numerical features
เป็นอัลกอริทึมที่ scikit-learn ใช้

การตัดแต่งต้นไม้ (Pruning)

เพื่อป้องกันปัญหา Overfitting สามารถใช้เทคนิค Pruning:

Pre-pruning (Early Stopping):

กำหนดความลึกสูงสุด (max_depth)
กำหนดจำนวนตัวอย่างขั้นต่ำในการแบ่ง (min_samples_split)
กำหนดจำนวนตัวอย่างขั้นต่ำใน leaf (min_samples_leaf)

Post-pruning:

สร้างต้นไม้เต็มก่อน แล้วค่อยตัดกิ่งที่ไม่จำเป็นออก

คำสั่ง

ให้นักศึกษาเขียนโปรแกรมภาษา Python เพื่อทำนายสภาพอากาศว่าฝนจะตกหรือไม่ โดยใช้ Decision Tree Classifier จากข้อมูลที่กำหนดให้

สิ่งที่ต้องทำ

อ่านข้อมูล Training Set จากไฟล์ weather_data.csv
แปลง Categorical Data เป็น Numerical Data โดยใช้ Label Encoding หรือ One-Hot Encoding
สร้าง Decision Tree Model โดยใช้ scikit-learn:
- สร้างโมเดลด้วย criterion = 'entropy' (Information Gain)
- สร้างโมเดลด้วย criterion = 'gini' (Gini Index)
แสดงโครงสร้าง Decision Tree ที่สร้างขึ้น
คำนวณค่า Entropy และ Information Gain ด้วยตนเอง (ไม่ใช้ library) สำหรับการแบ่งครั้งแรก
ทดสอบกับ Test Cases ที่กำหนดให้
แสดง Feature Importance และ Visualize Decision Tree

ข้อกำหนด

Features (ตัวแปรอิสระ)

Feature	ค่าที่เป็นไปได้	คำอธิบาย
เมฆ (Cloud)	มาก, ปานกลาง, น้อย	ปริมาณเมฆบนท้องฟ้า
อากาศ (Temperature)	ร้อน, อบอุ่น, เย็น	อุณหภูมิของอากาศ
ความชื้น (Humidity)	มาก, ปานกลาง, น้อย	ระดับความชื้นในอากาศ

Class (ตัวแปรตาม)

Class	คำอธิบาย
ฝนไม่ตก	ไม่มีฝนตก
ฝนตกเล็กน้อย	มีฝนตกเบาๆ หรือฝนปรอย
ฝนตกหนัก	มีฝนตกหนักมาก

ข้อกำหนดทางเทคนิค

ภาษา: Python 3.x
อนุญาตใช้ Library: scikit-learn, pandas, numpy, matplotlib, graphviz
ต้องคำนวณ Entropy และ Information Gain ด้วยตนเอง อย่างน้อย 1 ครั้งเพื่อแสดงความเข้าใจ
ต้องแสดง Decision Tree ในรูปแบบ Text หรือ Graphical
แสดงค่า Feature Importance
ปัดทศนิยม 6 ตำแหน่ง

ชุดข้อมูล Training Set (50 รายการ)

id,cloud,temperature,humidity,rain
1,มาก,เย็น,มาก,ฝนตกหนัก
2,มาก,อบอุ่น,มาก,ฝนตกหนัก
3,ปานกลาง,อบอุ่น,ปานกลาง,ฝนตกเล็กน้อย
4,น้อย,ร้อน,น้อย,ฝนไม่ตก
5,น้อย,ร้อน,ปานกลาง,ฝนไม่ตก
6,มาก,เย็น,ปานกลาง,ฝนตกเล็กน้อย
7,ปานกลาง,ร้อน,มาก,ฝนตกเล็กน้อย
8,น้อย,อบอุ่น,น้อย,ฝนไม่ตก
9,มาก,อบอุ่น,ปานกลาง,ฝนตกเล็กน้อย
10,ปานกลาง,เย็น,มาก,ฝนตกหนัก
11,น้อย,เย็น,น้อย,ฝนไม่ตก
12,มาก,ร้อน,มาก,ฝนตกหนัก
13,ปานกลาง,อบอุ่น,น้อย,ฝนไม่ตก
14,มาก,เย็น,มาก,ฝนตกหนัก
15,น้อย,ร้อน,น้อย,ฝนไม่ตก
16,ปานกลาง,เย็น,ปานกลาง,ฝนตกเล็กน้อย
17,มาก,อบอุ่น,มาก,ฝนตกหนัก
18,น้อย,อบอุ่น,ปานกลาง,ฝนไม่ตก
19,ปานกลาง,ร้อน,ปานกลาง,ฝนตกเล็กน้อย
20,มาก,เย็น,ปานกลาง,ฝนตกเล็กน้อย
21,น้อย,ร้อน,มาก,ฝนตกเล็กน้อย
22,มาก,อบอุ่น,ปานกลาง,ฝนตกเล็กน้อย
23,ปานกลาง,เย็น,มาก,ฝนตกหนัก
24,น้อย,เย็น,ปานกลาง,ฝนไม่ตก
25,มาก,ร้อน,ปานกลาง,ฝนตกเล็กน้อย
26,ปานกลาง,อบอุ่น,มาก,ฝนตกเล็กน้อย
27,น้อย,อบอุ่น,น้อย,ฝนไม่ตก
28,มาก,เย็น,มาก,ฝนตกหนัก
29,ปานกลาง,ร้อน,น้อย,ฝนไม่ตก
30,มาก,อบอุ่น,มาก,ฝนตกหนัก
31,น้อย,เย็น,มาก,ฝนตกเล็กน้อย
32,ปานกลาง,เย็น,ปานกลาง,ฝนตกเล็กน้อย
33,มาก,ร้อน,มาก,ฝนตกหนัก
34,น้อย,ร้อน,ปานกลาง,ฝนไม่ตก
35,ปานกลาง,อบอุ่น,ปานกลาง,ฝนตกเล็กน้อย
36,มาก,เย็น,ปานกลาง,ฝนตกเล็กน้อย
37,น้อย,อบอุ่น,มาก,ฝนตกเล็กน้อย
38,มาก,อบอุ่น,น้อย,ฝนไม่ตก
39,ปานกลาง,เย็น,มาก,ฝนตกหนัก
40,น้อย,ร้อน,น้อย,ฝนไม่ตก
41,มาก,เย็น,มาก,ฝนตกหนัก
42,ปานกลาง,ร้อน,ปานกลาง,ฝนตกเล็กน้อย
43,น้อย,อบอุ่น,ปานกลาง,ฝนไม่ตก
44,มาก,อบอุ่น,มาก,ฝนตกหนัก
45,ปานกลาง,เย็น,น้อย,ฝนไม่ตก
46,น้อย,เย็น,ปานกลาง,ฝนตกเล็กน้อย
47,มาก,ร้อน,ปานกลาง,ฝนตกเล็กน้อย
48,ปานกลาง,อบอุ่น,มาก,ฝนตกเล็กน้อย
49,น้อย,ร้อน,มาก,ฝนตกเล็กน้อย
50,มาก,เย็น,มาก,ฝนตกหนัก

สรุปการกระจายของข้อมูล

Class	จำนวน	สัดส่วน
ฝนไม่ตก	15	30%
ฝนตกเล็กน้อย	20	40%
ฝนตกหนัก	15	30%

ตัวอย่าง Input และ Output

Test Case 1

Input:

เมฆ: มาก
อากาศ: เย็น
ความชื้น: มาก

Output:

===============================================
       Decision Tree Weather Prediction
===============================================

Input Features:
  - เมฆ: มาก
  - อากาศ: เย็น
  - ความชื้น: มาก

-----------------------------------------------
Manual Entropy Calculation (Root Node)
-----------------------------------------------
การกระจายของ Class:
  - ฝนไม่ตก: 15/50 = 0.300000
  - ฝนตกเล็กน้อย: 20/50 = 0.400000
  - ฝนตกหนัก: 15/50 = 0.300000

H(S) = -0.3×log₂(0.3) - 0.4×log₂(0.4) - 0.3×log₂(0.3)
H(S) = 1.570951

-----------------------------------------------
Information Gain for Each Feature
-----------------------------------------------
IG(S, Cloud)       = 0.246750
IG(S, Temperature) = 0.094678
IG(S, Humidity)    = 0.395753

Best Feature to Split: Humidity (IG = 0.395753)

-----------------------------------------------
Decision Tree Prediction (Entropy)
-----------------------------------------------
Decision Path:
  humidity = มาก → cloud = มาก → ฝนตกหนัก

Prediction: ฝนตกหนัก
Probability: [0.000, 0.200, 0.800]

-----------------------------------------------
Decision Tree Prediction (Gini)
-----------------------------------------------
Decision Path:
  humidity = มาก → cloud = มาก → ฝนตกหนัก

Prediction: ฝนตกหนัก
Probability: [0.000, 0.200, 0.800]
===============================================

Test Case 2

Input:

เมฆ: น้อย
อากาศ: ร้อน
ความชื้น: น้อย

Output:

===============================================
       Decision Tree Weather Prediction
===============================================

Input Features:
  - เมฆ: น้อย
  - อากาศ: ร้อน
  - ความชื้น: น้อย

-----------------------------------------------
Decision Tree Prediction (Entropy)
-----------------------------------------------
Decision Path:
  humidity = น้อย → ฝนไม่ตก

Prediction: ฝนไม่ตก
Probability: [0.857, 0.143, 0.000]

-----------------------------------------------
Decision Tree Prediction (Gini)
-----------------------------------------------
Decision Path:
  humidity = น้อย → ฝนไม่ตก

Prediction: ฝนไม่ตก
Probability: [0.857, 0.143, 0.000]
===============================================

Test Case 3

Input:

เมฆ: ปานกลาง
อากาศ: อบอุ่น
ความชื้น: ปานกลาง

Output:

===============================================
       Decision Tree Weather Prediction
===============================================

Input Features:
  - เมฆ: ปานกลาง
  - อากาศ: อบอุ่น
  - ความชื้น: ปานกลาง

-----------------------------------------------
Decision Tree Prediction (Entropy)
-----------------------------------------------
Decision Path:
  humidity = ปานกลาง → cloud = ปานกลาง → ฝนตกเล็กน้อย

Prediction: ฝนตกเล็กน้อย
Probability: [0.000, 1.000, 0.000]

-----------------------------------------------
Decision Tree Prediction (Gini)
-----------------------------------------------
Decision Path:
  humidity = ปานกลาง → cloud = ปานกลาง → ฝนตกเล็กน้อย

Prediction: ฝนตกเล็กน้อย
Probability: [0.000, 1.000, 0.000]
===============================================

Test Case 4

Input:

เมฆ: มาก
อากาศ: ร้อน
ความชื้น: น้อย

Output:

===============================================
       Decision Tree Weather Prediction
===============================================

Input Features:
  - เมฆ: มาก
  - อากาศ: ร้อน
  - ความชื้น: น้อย

-----------------------------------------------
Decision Tree Prediction (Entropy)
-----------------------------------------------
Decision Path:
  humidity = น้อย → ฝนไม่ตก

Prediction: ฝนไม่ตก
Probability: [0.857, 0.143, 0.000]

-----------------------------------------------
Decision Tree Prediction (Gini)
-----------------------------------------------
Decision Path:
  humidity = น้อย → ฝนไม่ตก

Prediction: ฝนไม่ตก
Probability: [0.857, 0.143, 0.000]
===============================================

Test Case 5

Input:

เมฆ: น้อย
อากาศ: เย็น
ความชื้น: มาก

Output:

===============================================
       Decision Tree Weather Prediction
===============================================

Input Features:
  - เมฆ: น้อย
  - อากาศ: เย็น
  - ความชื้น: มาก

-----------------------------------------------
Decision Tree Prediction (Entropy)
-----------------------------------------------
Decision Path:
  humidity = มาก → cloud = น้อย → ฝนตกเล็กน้อย

Prediction: ฝนตกเล็กน้อย
Probability: [0.000, 1.000, 0.000]

-----------------------------------------------
Decision Tree Prediction (Gini)
-----------------------------------------------
Decision Path:
  humidity = มาก → cloud = น้อย → ฝนตกเล็กน้อย

Prediction: ฝนตกเล็กน้อย
Probability: [0.000, 1.000, 0.000]
===============================================

โครงสร้างโปรแกรมที่แนะนำ

import pandas as pd
import numpy as np
from sklearn.tree import DecisionTreeClassifier, export_text, plot_tree
from sklearn.preprocessing import LabelEncoder
import matplotlib.pyplot as plt
import math

class DecisionTreeWeatherClassifier:
    def __init__(self):
        """
        Initialize classifier with encoders and models
        """
        self.label_encoders = {}
        self.target_encoder = LabelEncoder()
        self.dt_entropy = None
        self.dt_gini = None
        self.feature_names = ['cloud', 'temperature', 'humidity']
        self.class_names = []
        
    def load_and_preprocess_data(self, filename):
        """
        Load data from CSV and preprocess
        """
        # TODO: Implement data loading and preprocessing
        # - Read CSV file
        # - Encode categorical features using LabelEncoder
        # - Return X (features) and y (target)
        pass
    
    def calculate_entropy(self, y):
        """
        Calculate entropy of a dataset
        H(S) = -Σ p_i × log₂(p_i)
        """
        # TODO: Implement entropy calculation
        pass
    
    def calculate_information_gain(self, X, y, feature_idx):
        """
        Calculate information gain for a feature
        IG(S, A) = H(S) - Σ (|S_v|/|S|) × H(S_v)
        """
        # TODO: Implement information gain calculation
        pass
    
    def calculate_gini(self, y):
        """
        Calculate Gini index of a dataset
        Gini(S) = 1 - Σ p_i²
        """
        # TODO: Implement Gini index calculation
        pass
    
    def fit(self, X, y):
        """
        Train Decision Tree models with both entropy and gini criteria
        """
        # TODO: Implement model training
        # - Create DecisionTreeClassifier with criterion='entropy'
        # - Create DecisionTreeClassifier with criterion='gini'
        pass
    
    def predict(self, features, criterion='entropy'):
        """
        Make prediction using specified criterion
        Returns: (predicted_class, probabilities)
        """
        # TODO: Implement prediction
        pass
    
    def get_decision_path(self, features, criterion='entropy'):
        """
        Get the decision path for a prediction
        """
        # TODO: Implement decision path extraction
        pass
    
    def visualize_tree(self, criterion='entropy', filename='decision_tree'):
        """
        Visualize the decision tree
        """
        # TODO: Implement tree visualization
        pass
    
    def get_feature_importance(self, criterion='entropy'):
        """
        Get feature importance scores
        """
        # TODO: Implement feature importance extraction
        pass
    
    def print_tree_rules(self, criterion='entropy'):
        """
        Print decision tree rules in text format
        """
        # TODO: Implement tree rules printing
        pass

def main():
    # Create classifier instance
    classifier = DecisionTreeWeatherClassifier()
    
    # Load and preprocess data
    X, y = classifier.load_and_preprocess_data('weather_data.csv')
    
    # Train models
    classifier.fit(X, y)
    
    # Manual entropy calculation for demonstration
    print("=" * 50)
    print("Manual Entropy and Information Gain Calculation")
    print("=" * 50)
    
    # Calculate entropy of root node
    root_entropy = classifier.calculate_entropy(y)
    print(f"Root Entropy H(S) = {root_entropy:.6f}")
    
    # Calculate information gain for each feature
    for i, feature in enumerate(['cloud', 'temperature', 'humidity']):
        ig = classifier.calculate_information_gain(X, y, i)
        print(f"IG(S, {feature}) = {ig:.6f}")
    
    # Print tree rules
    print("\n" + "=" * 50)
    print("Decision Tree Rules (Entropy)")
    print("=" * 50)
    classifier.print_tree_rules('entropy')
    
    print("\n" + "=" * 50)
    print("Decision Tree Rules (Gini)")
    print("=" * 50)
    classifier.print_tree_rules('gini')
    
    # Feature importance
    print("\n" + "=" * 50)
    print("Feature Importance")
    print("=" * 50)
    importance = classifier.get_feature_importance('entropy')
    for feature, imp in importance.items():
        print(f"{feature}: {imp:.6f}")
    
    # Test cases
    test_cases = [
        {'cloud': 'มาก', 'temperature': 'เย็น', 'humidity': 'มาก'},
        {'cloud': 'น้อย', 'temperature': 'ร้อน', 'humidity': 'น้อย'},
        {'cloud': 'ปานกลาง', 'temperature': 'อบอุ่น', 'humidity': 'ปานกลาง'},
        {'cloud': 'มาก', 'temperature': 'ร้อน', 'humidity': 'น้อย'},
        {'cloud': 'น้อย', 'temperature': 'เย็น', 'humidity': 'มาก'},
    ]
    
    # Make predictions
    print("\n" + "=" * 50)
    print("Test Case Predictions")
    print("=" * 50)
    
    for i, test in enumerate(test_cases, 1):
        print(f"\nTest Case {i}:")
        print(f"  Input: {test}")
        
        # Entropy prediction
        pred_entropy, prob_entropy = classifier.predict(test, 'entropy')
        print(f"  Entropy Prediction: {pred_entropy}")
        print(f"  Probabilities: {prob_entropy}")
        
        # Gini prediction
        pred_gini, prob_gini = classifier.predict(test, 'gini')
        print(f"  Gini Prediction: {pred_gini}")
        print(f"  Probabilities: {prob_gini}")
    
    # Visualize tree
    classifier.visualize_tree('entropy', 'decision_tree_entropy')
    classifier.visualize_tree('gini', 'decision_tree_gini')
    print("\nDecision trees saved as images.")

if __name__ == "__main__":
    main()

ส่วนเพิ่มเติม: ตัวอย่างการ Visualize Decision Tree

การใช้ matplotlib

from sklearn.tree import plot_tree
import matplotlib.pyplot as plt

plt.figure(figsize=(20, 10))
plot_tree(
    classifier.dt_entropy,
    feature_names=['cloud', 'temperature', 'humidity'],
    class_names=['ฝนไม่ตก', 'ฝนตกเล็กน้อย', 'ฝนตกหนัก'],
    filled=True,
    rounded=True,
    fontsize=10
)
plt.title('Decision Tree (Entropy)')
plt.tight_layout()
plt.savefig('decision_tree_entropy.png', dpi=150)
plt.show()

การใช้ graphviz

from sklearn.tree import export_graphviz
import graphviz

dot_data = export_graphviz(
    classifier.dt_entropy,
    feature_names=['cloud', 'temperature', 'humidity'],
    class_names=['ฝนไม่ตก', 'ฝนตกเล็กน้อย', 'ฝนตกหนัก'],
    filled=True,
    rounded=True,
    special_characters=True
)
graph = graphviz.Source(dot_data)
graph.render('decision_tree_entropy', format='png', cleanup=True)

ภาคผนวก: สูตรคณิตศาสตร์

Entropy

H (S) = - \sum_{i = 1}^{c} p_{i} {log}_{2} (p_{i})

Information Gain

IG (S, A) = H (S) - \sum_{v \in Values (A)} \frac{| S_{v} |}{| S |} H (S_{v})

Gini Index

Gini (S) = 1 - \sum_{i = 1}^{c} p_{i}^{2}

Gini Split

{Gini}_{split} (S, A) = \sum_{v \in Values (A)} \frac{| S_{v} |}{| S |} Gini (S_{v})

Gini Gain

{Gini}_{gain} (S, A) = Gini (S) - {Gini}_{split} (S, A)

เกณฑ์การให้คะแนน

หัวข้อ	คะแนน
การอ่านและแปลงข้อมูลถูกต้อง	10
การคำนวณ Entropy ด้วยตนเอง	15
การคำนวณ Information Gain ด้วยตนเอง	15
การสร้าง Decision Tree ด้วย scikit-learn	15
การทำนายถูกต้องตาม Test Cases	15
การแสดง Feature Importance	10
การ Visualize Decision Tree	10
ความเรียบร้อยและ Comment ในโค้ด	10
รวม	100

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

Quinlan, J. R. (1986). Induction of decision trees. Machine Learning, 1(1), 81-106.
Breiman, L., Friedman, J., Stone, C. J., & Olshen, R. A. (1984). Classification and regression trees. CRC press.
scikit-learn Documentation: Decision Trees. https://scikit-learn.org/stable/modules/tree.html