Decision Tree Concepts and Implementation

Cấu trúc dữ liệu cây: Cây quyết định

1. Lí thuyết về cây quyết định 1.1 Cây quyết định là gì? Cây quyết định là một mô hình máy học dạng phân cấp giống như sơ đồ luồng, trong đó mỗi nút bên trong đại diện cho một bài kiểm tra trên một thuộc tính (hoặc đặc điểm), mỗi nhánh đại diện cho kết quả của bài kiểm tra đó, và mỗi nút lá đại diện cho nhãn lớp (hoặc quyết định được đưa ra sau khi tính toán tất cả các thuộc tính). Nó có thể được sử dụng cho cả nhiệm vụ phân loại và hồi quy, cho phép người dùng đưa ra quyết định dựa trên dữ liệu một cách dễ dàng.

1.2 Ứng dụng của cây quyết định

• Phân loại: Cây quyết định có thể phân loại các điểm dữ liệu thành các danh mục đã định nghĩa dựa trên các đặc điểm của chúng. Ví dụ, nó có thể phân loại email thành "thư rác" hoặc "không thư rác".

• Hồi quy: Trong bối cảnh này, cây quyết định dự đoán các kết quả liên tục, chẳng hạn như dự đoán giá nhà dựa trên các đặc điểm như diện tích, số phòng, v.v.

• Chẩn đoán y tế: Các chuyên gia y tế có thể sử dụng cây quyết định để xác định các căn bệnh dựa trên triệu chứng và lịch sử bệnh nhân, tạo ra một con đường cho chẩn đoán và điều trị.

• Tài chính: Các tổ chức tài chính sử dụng cây quyết định để đánh giá khả năng khách hàng vỡ nợ một cách chính xác, hỗ trợ trong quản lý rủi ro và ra quyết định.

2. Chỉ số Gini trong cây quyết định 2.1 Chỉ số Gini là gì? Chỉ số Gini (hoặc độ tinh khiết Gini) định lượng khả năng của một phần tử được chọn ngẫu nhiên bị gán nhãn sai nếu nó được gán nhãn ngẫu nhiên theo phân phối nhãn trong tập dữ liệu. Nó đóng vai trò quan trọng trong cây quyết định, vì nó đo lường sự ô nhiễm hoặc tinh khiết của một tập dữ liệu, hỗ trợ trong việc chọn thuộc tính thông tin nhất để chia nhỏ tập dữ liệu trong quá trình xây dựng cây.

2.2 Công thức chỉ số Gini Chỉ số Gini được tính bằng công thức: [Gini = 1 - \Sigma (p_i^2)] Trong đó: ( p_i ) đại diện cho tỷ lệ mẫu thuộc về lớp ( i ) trong tập dữ liệu. Tổng số lớp được đại diện bởi ( n ). Một tập dữ liệu chỉ chứa một lớp cho giá trị chỉ số Gini là 0, cho thấy tinh khiết hoàn hảo, trong khi một lớp phân phối đều dẫn đến chỉ số Gini là 0.5, cho thấy ô nhiễm tối đa.

2.3 Ví dụ tính toán chỉ số Gini Xem xét một tập dữ liệu phân loại nhỏ:

Tỷ lệ cho các lớp: ( p_{Có} = \frac{3}{6} = 0.5 ) ( p_{Không} = \frac{3}{6} = 0.5 ) Tính toán: [ Gini = 1 - (0.5^2 + 0.5^2) = 1 - (0.25 + 0.25) = 0.5 ]

3. Sử dụng chỉ số Gini với cây quyết định 3.1 Các bước xây dựng cây quyết định bằng chỉ số Gini

• Tính toán chỉ số Gini của tập dữ liệu ban đầu để đánh giá độ tinh khiết của nó.

• Chia nhỏ tập dữ liệu thành các nút con dựa trên thuộc tính dẫn đến chỉ số Gini thấp nhất.

• Tính toán trung bình có trọng số chỉ số Gini của các nhóm con kết quả.

• Tiếp tục chọn thuộc tính để chia nhỏ trong khi lặp lại quá trình cho đến khi các điều kiện dừng được đáp ứng (ví dụ, độ sâu cây tối đa, hoặc số mẫu tối thiểu cho mỗi lá).

4. Triển khai cây quyết định bằng cách sử dụng chỉ số Gini 4.1 Ví dụ mã trong Python

import numpy as np

def gini_index(groups, classes):
    """ Tính toán chỉ số Gini cho một tập dữ liệu """
    total_samples = float(sum([len(group) for group in groups]))  
    gini = 0.0
    for group in groups:
        size = float(len(group))
        if size == 0:
            continue
        score = sum([(row[-1] == c) for row in group for c in classes]) / size
        gini += (1.0 - sum([score ** 2 for c in classes])) * (size / total_samples)
    return gini

4.2 Dữ liệu ví dụ Tập dữ liệu được sử dụng để triển khai chỉ số Gini trong một cây quyết định:

dataset = [[2.8, 'Có'], [1.2, 'Không'], [3.6, 'Có'], [4.5, 'Không'], [5.1, 'Có']]

5. Ví dụ: Xây dựng một cây quyết định bằng OOP 5.1 Lớp TreeNode - Đại diện cho một nút

class TreeNode:
    def __init__(self, feature_index=None, threshold=None, left=None, right=None, label=None):
        """ Khởi tạo một nút trong cây quyết định. """
        self.feature_index = feature_index  # Chỉ số của thuộc tính được sử dụng để chia nhỏ
        self.threshold = threshold          # Giá trị ngưỡng được sử dụng để chia nhỏ
        self.left = left                    # Cây con bên trái
        self.right = right                  # Cây con bên phải
        self.label = label                  # Nhãn lớp tại nút lá này

5.2 Lớp DecisionTree - Xây dựng cây quyết định

class DecisionTree:
    def __init__(self, max_depth=3):
        """ Khởi tạo cây quyết định với độ sâu tối đa """
        self.max_depth = max_depth
        self.root = None
        
    # Các phương thức bổ sung cho các chức năng như chỉ số Gini, chia nhỏ dữ liệu, phân nhánh tốt nhất, xây dựng cây, v.v.

6. Bài tập thực hành 6.1 Bài tập 1: Tính toán chỉ số Gini cho một tập dữ liệu Tính toán chỉ số Gini cho tập dữ liệu sau:

6.2 Bài tập 2: Mở rộng cây quyết định Thêm nhiều thuộc tính vào tập dữ liệu (ví dụ, Tuổi, Điểm tín dụng). Cải thiện thuật toán để xây dựng một cây với nhiều thuộc tính. In cây theo định dạng dễ đọc hơn để phân tích quyết định một cách hiệu quả.