Bạn có biết rằng bạn vẫn sử dụng phương pháp cây quyết định trong cuộc sống hàng ngày của mình. Ví dụ, bạn đi siêu thị để mua sữa cho cả gia đình. Những từ đầu tiên trong đầu bạn sẽ là: Bạn cần mua bao nhiêu sữa?
Bạn sẽ chắc chắn rằng: Gia đình bạn sẽ hết 1 lít sữa vào các ngày trong tuần và 1,5 lít vào cuối tuần. Vì vậy, bạn sẽ quyết định mua bao nhiêu thực phẩm cho gia đình của bạn dựa trên ngày.
Đây là cây quyết định nhị phân.
Khái niệm cây quyết định
Cây quyết định là một cây phân cấp có cấu trúc được sử dụng để phân loại các đối tượng theo một trình tự các quy tắc. Thuộc tính đối tượng có thể thuộc các kiểu dữ liệu khác nhau như nhị phân, định danh, thứ tự, định lượng, trong khi các thuộc tính lớp phải thuộc kiểu dữ liệu nhị phân hoặc thứ tự.
Nói tóm lại, dữ liệu đối tượng đã cho bao gồm các thuộc tính và danh mục của chúng, cây quyết định sẽ tạo ra các quy tắc để dự đoán danh mục dữ liệu không xác định.
Hãy xem xét một ví dụ cây quyết định điển hình khác. Giả sử các chàng trai quyết định chơi bóng dựa trên thời tiết?
Các tính năng ban đầu là:
- Thời tiết
- Độ ẩm
- Gió
Dựa trên thông tin trên, có thể xây dựng các mô hình sau:
Dựa trên mô hình ở trên, chúng tôi thấy:
Nếu thời tiết trong xanh và độ ẩm bình thường, cậu bé sẽ có cơ hội chơi bóng tốt. Nếu trời nắng và ẩm ướt, các chàng trai có thể sẽ không chơi bóng.
Thuật toán cây quyết định
thuật toán id3
Bây giờ, hãy hiểu cách thuật toán cây quyết định hoạt động với một thuật toán đơn giản id3.
id3 (j. r. quinlan 1993) sử dụng tìm kiếm tham lam từ trên xuống của không gian nhánh có thể có mà không cần theo dõi ngược lại. id3 sử dụng entropy và thu thập thông tin để xây dựng cây quyết định.
Chúng tôi xem xét ví dụ 2:
Bạn muốn xem xét thành công của một bộ phim theo hai yếu tố: dàn diễn viên chính của phim và thể loại phim:
Giả sử rằng bạn chỉ muốn xác định thành công của một bộ phim bằng một yếu tố, bạn sẽ có hai cách để làm điều đó: theo dàn diễn viên chính của bộ phim và theo thể loại của bộ phim.
Từ hình vẽ, chúng ta có thể thấy rõ rằng với phương pháp đầu tiên, chúng ta nhận được sự phân loại rõ ràng, trong khi với phương pháp thứ hai, chúng ta nhận được kết quả lộn xộn hơn. Tương tự như vậy, cây quyết định thực hiện điều này khi chọn các biến.
Phương pháp cây quyết định sử dụng nhiều hệ số để phân chia. Dưới đây, tôi sẽ đưa ra hai hệ số phổ biến, Mức tăng thông tin và Tỷ lệ tăng (ngoài hệ số Gini).
Entropy
trong Cây Quyết định
Entropy là một thuật ngữ nhiệt động lực học được sử dụng để đo sự biến thiên, hỗn loạn hoặc ngẫu nhiên. Năm 1948, Shannon mở rộng khái niệm entropy để nghiên cứu và thống kê với công thức sau:
Một phân phối xác suất với biến rời rạc x có thể nhận n giá trị khác nhau x1, x2, …, xn.
Giả sử rằng xác suất x nhận các giá trị này là pi = p (x = xi).
Kí hiệu cho phân phối này là p = (p1, p2,…, pn). Entropy của phân phối này được định nghĩa là:
h (p) = – ∑nn = 1 pi log (pi)
Giả sử bạn lật một đồng xu, entropy được tính như sau:
h = – [0,5 ln (0,5) + 0,5 ln (0,5)]
Biểu đồ trên cho thấy sự thay đổi trong hàm entropy. Chúng ta có thể thấy rằng entropy cực đại khi cả hai lớp có xác suất xuất hiện bằng nhau.
- p tinh khiết: pi = 0 hoặc pi = 1
- p vẩn đục: pi = 0,5, sau đó là đỉnh entropi
Thu thập thông tin
trong Cây Quyết định
Thông tin thu được dựa trên việc giảm hàm entropy khi tập dữ liệu được phân chia theo các thuộc tính. Để xây dựng cây quyết định, chúng ta phải tìm tất cả các thuộc tính trả về mức thu được thông tin cao nhất.
Để xác định các nút trong mô hình cây quyết định, chúng tôi tính toán mức tăng thông tin cho mỗi nút theo thứ tự sau:
• Bước 1 : Tính hệ số entropy của biến mục tiêu s, n phần tử và nc phần tử của một lớp c cho trước:
h (s) = – cc = 1 (nc / n) log (nc / n)
• Bước thứ hai : Tính hàm entropy tại mỗi thuộc tính: với thuộc tính x, chia các điểm dữ liệu trong s thành k nút con s1, s2, …, sk với số điểm Trong mỗi nút con tương ứng là m1, m2, …, mk, ta có:
h (x, s) = ∑kk = 1 (mk / n) * h (sk)
Bước 3 : Tính toán thông tin thu được:
g (x, s) = h (s) – h (x, s)
Qua ví dụ 2 ở trên, chúng ta có thể tính toán hệ số entropy như sau:
Entropy Parent = – (0,57 * ln (0,57) + 0,43 * ln (0,43)) = 0,68
Entropy bậc nhất:
entropyright = – (. 75 * ln (0,75) + 0,25 * ln (0,25)) = 0,56entropyright = – (. 33 * ln (0,33) + 0,67 * ln (0,67)) = 0,63
Chúng tôi có thể tính toán thu được thông tin như sau:
Mức tăng thông tin = 0,68 – (4 * 0,56 + 3 * 0,63) / 7 = 0,09
Yếu tố entropy của phép chia bậc hai như sau:
entropyleft = – (. 67 * ln (0,67) + 0,33 * ln (0,33)) = 0,63entropymiddle = – (. 5 * ln (0,5) + 0,5 * ln (0,5)) = 0,69entropyright = – (. 5 * ln (0,5) + 0,5 * ln (0,5)) = 0,69
Yếu tố Thu thập thông tin :
Mức tăng thông tin = 0,68 – (3 * 0,63 + 2 * 0,69 + 2 * 0,69) / 7 = 0,02
So sánh kết quả, chúng ta thấy rằng nếu chúng ta chia cho phương pháp 1, chúng ta nhận được giá trị hệ số khuếch đại thông tin gấp 4 lần so với phương pháp 2. Do đó, giá trị thông tin thu được theo phương pháp 1 cũng lớn hơn so với phương pháp 2.
thuật toán c4.5
Thuật toán C4.5 là một thuật toán cải tiến của id3.
Trong thuật toán id3, mức tăng thông tin được sử dụng làm thước đo. Tuy nhiên, phương pháp này ưu tiên các thuộc tính có số lượng giá trị lớn và hiếm khi xem xét các giá trị nhỏ hơn. Do đó, để khắc phục những thiếu sót trên, chúng tôi sử dụng hệ số đo hệ số khuếch đại (trong thuật toán c4.5) như sau:
Đầu tiên, chúng tôi bình thường hóa việc thu được thông tin với giá trị thông tin phân tách:
Trong đó: Thông tin phân tách được tính như sau:
Giả sử chúng ta chia biến thành n nút và di đại diện cho số lượng bản ghi thuộc về nút đó. Do đó, hệ số khuếch đại có tính đến xu hướng phân phối khi chia cây.
Áp dụng cho ví dụ trên, với phép chia đầu tiên, chúng ta có
Thông tin phân tách = – ((4/7) * log2 (4/7)) – ((3/7) * log2 (3/7)) = 0,98
Tỷ lệ lợi nhuận = 0,09 / 0,98 = 0,092
Tiêu chí dừng
Trong thuật toán cây quyết định, sử dụng phương pháp tách ở trên, nếu nút không thuần túy, chúng ta sẽ chia nút mãi mãi. Vì vậy, chúng tôi nhận được một cây trong đó mọi điểm trong tập huấn luyện được dự đoán chính xác (giả sử không có hai đầu vào giống hệt nhau cho các đầu ra khác nhau). Khi đó cây có thể rất phức tạp (nhiều nút) với nhiều nút lá và chỉ một vài điểm dữ liệu. Do đó, việc mặc trang phục quá mức dễ xảy ra hơn.
Để tránh điều này, chúng ta có thể ngăn cây bằng cách:
- Nếu entropy của nút bằng 0, thì mỗi điểm trong nút thuộc về một lớp.
- Nếu số phần tử của nút nhỏ hơn một ngưỡng nhất định. Trong trường hợp này, chúng tôi chấp nhận rằng một số điểm được phân loại sai để tránh trang bị quá mức. Lớp của nút lá này có thể được xác định theo lớp trội trong nút.
- Nếu khoảng cách từ nút này đến nút gốc đạt một giá trị nào đó. Hạn chế độ sâu của cây này sẽ làm giảm độ phức tạp của cây và giúp tránh bị quá mức.
- Nếu tổng số nút lá vượt quá một ngưỡng nhất định.
- Nếu nút không được phân chia, entropi bị giảm quá nhiều (mức tăng thông tin nhỏ hơn một ngưỡng nhất định).
Ngoài ra, chúng ta có cách cắt tỉa cây.
Một số thuật toán khác
Ngoài id3, c4.5, chúng tôi còn có một số thuật toán khác, chẳng hạn như:
Thuật toán
- chaid: Sử dụng thống kê chi-square để tạo cây quyết định nhằm xác định phép phân chia tốt nhất. Biến mục tiêu đầu vào có thể là số (liên tục) hoặc phân loại.
- c & amp; r Thuật toán: Sử dụng phân vùng đệ quy để tách một cây. Tham số mục tiêu có thể là số hoặc phân loại.
- sao chép
- Cây lý luận có điều kiện
Ưu và nhược điểm của thuật toán Cây quyết định
Ưu điểm
Cây quyết định là một thuật toán đơn giản và phổ biến. Thuật toán này được sử dụng rộng rãi vì những ưu điểm của nó:
- Mô hình tạo ra các quy tắc dễ hiểu cho người đọc, tạo ra một tập hợp các quy tắc trong đó mỗi nhánh lá là một cây quy tắc.
- Dữ liệu đầu vào có thể là dữ liệu bị thiếu, không cần chuẩn hóa hoặc tạo biến giả
- Có thể xử lý dữ liệu số và dữ liệu phân loại
- li>
- Có thể được xác thực sử dụng kiểm tra thống kê Mô hình
- có thể áp dụng cho dữ liệu lớn
Nhược điểm
Do đó, cây quyết định cũng có những nhược điểm cụ thể:
- Mô hình cây quyết định phụ thuộc nhiều vào dữ liệu của bạn. Cấu trúc của mô hình cây quyết định có thể thay đổi hoàn toàn ngay cả với những thay đổi nhỏ trong tập dữ liệu.
- Cây quyết định thường có vấn đề quá mức
Sử dụng sklearn để triển khai cây quyết định
Trên đây là những điểm chính cần lưu ý khi triển khai thuật toán cây quyết định.
Theo dõi https://trituenhantao.io/ để biết thêm nhiều bài viết mới hấp dẫn.