Trong cuộc sống hàng ngày, chúng ta liên tục đưa ra các quyết định dựa trên nhiều yếu tố khác nhau. Vô hình chung, chúng ta đang sử dụng một phương pháp quen thuộc trong lĩnh vực khoa học dữ liệu, đó là Cây Quyết định (Decision Tree). Ví dụ đơn giản như việc bạn đi siêu thị mua sữa: “Hôm nay là ngày thường hay cuối tuần? Nếu là ngày thường, mua 1 lít; nếu cuối tuần, mua 1.5 lít.” Đó chính là ứng dụng trực quan của cây quyết định nhị phân.
Mục Lục
Khái Niệm Cây Quyết Định (Decision Tree)
Cây Quyết định (Decision Tree) là một cấu trúc dạng cây phân cấp, được sử dụng để phân loại các đối tượng dựa trên một loạt các quy tắc. Các thuộc tính của đối tượng có thể thuộc nhiều kiểu dữ liệu khác nhau như Nhị phân (Binary), Định danh (Nominal), Thứ tự (Ordinal), Số lượng (Quantitative). Tuy nhiên, thuộc tính phân lớp thường là kiểu dữ liệu Binary hoặc Ordinal.
Tóm lại, với dữ liệu về các đối tượng, bao gồm các thuộc tính và lớp (classes) của chúng, cây quyết định sẽ tạo ra các quy tắc để dự đoán lớp của dữ liệu mới.
Ví dụ, các bạn nam thường quyết định đi đá bóng dựa trên các yếu tố thời tiết, độ ẩm và gió. Dựa trên những yếu tố này, ta có thể xây dựng một mô hình cây quyết định đơn giản: Nếu trời nắng và độ ẩm bình thường, khả năng đi đá bóng cao; nếu trời nắng và độ ẩm cao, khả năng đi đá bóng thấp.
Các Thuật Toán Cây Quyết Định Phổ Biến
Thuật Toán ID3
ID3 (Iterative Dichotomiser 3) là một thuật toán đơn giản sử dụng phương pháp tìm kiếm tham lam từ trên xuống, không có backtracking. ID3 sử dụng Entropy và Information Gain để xây dựng cây quyết định.
Ví dụ, bạn muốn đánh giá sự thành công của một bộ phim dựa trên diễn viên chính và thể loại. Nếu bạn chỉ chọn một yếu tố, việc phân loại theo diễn viên chính có thể rõ ràng hơn so với phân loại theo thể loại. Cây quyết định cũng hoạt động tương tự, chọn các biến phân chia dựa trên khả năng phân loại tốt nhất.
Có nhiều hệ số được sử dụng để phân chia, trong đó phổ biến nhất là Information Gain và Gain Ratio.
Entropy trong Cây Quyết Định
Entropy, trong lĩnh vực Nhiệt động lực học, là thước đo sự biến đổi, hỗn loạn hoặc ngẫu nhiên. Shannon đã mở rộng khái niệm này sang lĩnh vực nghiên cứu thống kê, với công thức:
H(p)= – ∑nn=1 pi log(pi)
Trong đó, p là phân phối xác suất của biến rời rạc x, nhận n giá trị khác nhau x1, x2, …, xn, và pi là xác suất để x nhận giá trị xi.
Ví dụ, khi tung một đồng xu, entropy được tính: H = -[0.5 ln(0.5) + 0.5 ln(0.5)]. Entropy đạt giá trị tối đa khi xác suất xảy ra của hai lớp bằng nhau (p = 0.5, vẩn đục), và tối thiểu khi một lớp chắc chắn xảy ra (p = 0 hoặc p = 1, tinh khiết).
Information Gain trong Cây Quyết Định
Information Gain đo lường sự giảm của Entropy khi tập dữ liệu được phân chia dựa trên một thuộc tính. Để xây dựng cây quyết định, chúng ta cần tìm thuộc tính mang lại Information Gain cao nhất.
Các bước tính Information Gain:
- Tính Entropy của biến mục tiêu S: H(S)= – ∑cc=1 (Nc/N) log(Nc/N)
- Tính Entropy tại mỗi thuộc tính x: H(x, S) = ∑Kk=1 (mk / N) * H(Sk )
- Tính Information Gain: G(x, S) = H(S) – H(x,S)
Ví dụ, giả sử EntropyParent = 0.68. Với phương pháp chia thứ nhất, Entropyleft = 0.56 và Entropyright = 0.63. Khi đó, Information Gain = 0.68 – (4*0.56 + 3*0.63)/7 = 0.09.
So sánh với một phương pháp chia khác có Information Gain thấp hơn, ta thấy phương pháp đầu tiên mang lại nhiều thông tin hơn.
Thuật Toán C4.5
C4.5 là một cải tiến của ID3. Trong ID3, Information Gain ưu tiên các thuộc tính có nhiều giá trị. Để khắc phục điều này, C4.5 sử dụng Gain Ratio:
Gain Ratio = Information Gain / Split Info
Trong đó, Split Info đo lường sự phân tán của dữ liệu:
Split Info = – ∑ni=1 (Di/N) * log2(Di/N)
C4.5 giúp xem xét xu hướng phân phối dữ liệu khi chia cây.
Ví dụ, với cách chia thứ nhất, Split Info = 0.98 và Gain Ratio = 0.09/0.98 = 0.092.
Tiêu Chuẩn Dừng
Để tránh overfitting (mô hình quá khớp với dữ liệu huấn luyện), các thuật toán Decision Tree cần có tiêu chuẩn dừng:
- Entropy của node bằng 0.
- Số phần tử trong node nhỏ hơn một ngưỡng.
- Độ sâu của cây đạt một giá trị giới hạn.
- Tổng số leaf node vượt quá một ngưỡng.
- Information Gain khi phân chia node quá nhỏ.
Ngoài ra, phương pháp cắt tỉa cây cũng được sử dụng để giảm độ phức tạp của cây.
Các Thuật Toán Cây Quyết Định Khác
Ngoài ID3 và C4.5, còn có các thuật toán khác như:
- CHAID: Sử dụng thống kê chi-square để xác định các phân tách tối ưu.
- C&R: Sử dụng phân vùng đệ quy.
- MARS
- Conditional Inference Trees
Ưu và Nhược Điểm Của Cây Quyết Định
Ưu điểm:
- Dễ hiểu, dễ diễn giải.
- Không yêu cầu chuẩn hóa dữ liệu.
- Có thể làm việc với cả dữ liệu số và phân loại.
- Có khả năng làm việc với dữ liệu lớn.
Nhược điểm:
- Dễ bị overfitting.
- Có thể không ổn định, thay đổi nhỏ trong dữ liệu có thể làm thay đổi cấu trúc cây.
Kết Luận
Cây Quyết định là một công cụ mạnh mẽ và dễ sử dụng trong phân tích và dự đoán. Việc hiểu rõ các thuật toán, ưu nhược điểm, và cách ứng dụng của Decision Tree sẽ giúp bạn đưa ra những quyết định thông minh hơn trong nhiều lĩnh vực khác nhau.
Từ khóa: cây quyết định, decision tree, machine learning