Xu Hướng 3/2024 # Cây Quyết Định (Decision Tree) Là Gì? Ví Dụ Về Cây Quyết Định # Top 8 Xem Nhiều

Bạn đang xem bài viết Cây Quyết Định (Decision Tree) Là Gì? Ví Dụ Về Cây Quyết Định được cập nhật mới nhất tháng 3 năm 2024 trên website Bac.edu.vn. Hy vọng những thông tin mà chúng tôi đã chia sẻ là hữu ích với bạn. Nếu nội dung hay, ý nghĩa bạn hãy chia sẻ với bạn bè của mình và luôn theo dõi, ủng hộ chúng tôi để cập nhật những thông tin mới nhất.

Khái niệm

Cây quyết định trong tiếng Anh là Decision tree.

Cây quyết định là một phương tiện hỗ trợ cho việc ra quyết định trong điều kiện bất định. Nó chỉ ra nhiều đường lối hàng động khác nhau và hậu quả kinh tế của mỗi đường lối. Thông thường, mỗi đường lối hành động được gắn với một xác suất chủ quan về khả năng phát sinh các sự kiện trong tương lai.

Ví dụ về cây quyết định

Căn cứ vào Cây quyết định trên, người bán lẻ có hai phương án hành động là mở cửa hàng và không mở cửa hàng. Anh ta phải cân nhắc hai trạng thái tự nhiên, tức hai sự kiện có thể xảy ra: nền kinh tế phát triển mạnh hoặc suy thoái.

Người bán lẻ phải đánh giá khả năng xuất hiện mỗi sự kiện và trong tình huống này, anh ta dựa trên kinh nghiệm và hiểu biết để nhận định rằng khả năng xuất hiện mỗi sự kiện bằng 50%. Cuối cùng, người bán lẻ ước tính hậu quả tài chính là nếu mở cửa hàng sẽ có lãi 40.000 đồng khi kinh tế phát triển mạnh và lỗ 30.000 đồng nếu có suy thoái.

Để ra quyết định, người bán lẻ cần một tiêu chuẩn ra quyết định cho phép anh ta lựa chọn phương án hành động tốt nhất trong các phương án có thể có. Vì sự lựa chọn này gắn với yếu tố rủi ro, nên chúng ta cần biết thái độ của người bán lẻ đối với rủi ro.

Nếu người bán lẻ không chú ý đến rủi ro, chúng ta có thể tính toán tính xác định tương đương với hành vi “mở cửa hàng” bằng cách căn cứ vào hậu quả tài chính của mỗi kết cục và gia quyền nó theo xác suất xuất hiện của nó. Ví dụ:

Kết cục này chắc chắn lớn hơn 0 trong trường hợp không mở cửa hàng và nó biện minh cho việc tiếp tục thực hiện dự án này.

Song nếu người bán lẻ là người ghét rủi ro, tiêu chuẩn giá trị bằng tiền có thể không phải là tiêu chuẩn thích hợp, vì anh ta cần nhận được phần thưởng cho sự rủi ro để chấp nhận hành động. Việc tận dụng tiêu chuẩn cẩn thận hơn tiêu chuẩn tương đương với tính xác định sẽ làm giảm tiêu chuẩn tương đương với tính xác định của nhánh “mở cửa hàng” và điều này cũng dẫn đến quyết định tiếp tục mở cửa hàng.

Cây Quyết Định Là Gì? Ví Dụ Về Cây Quyết Định

Cây quyết định là gì?

Cây quyết định (decision tree) là một phương tiện hỗ trợ cho việc ra quyết định trong điều kiện bất định. Nó chỉ ra nhiều đường lối hành động khác nhau và hậu quả kinh tế của mỗi đường lối. Thông thường, mỗi đường lối hành động được gắn với một xác suất chủ quan về khả năng phát sinh các sự kiện trong tương lai.

Ví dụ về cây quyết định

Giả sử, có một người bán lẻ cần một tiêu chuẩn ra quyết định cho phép anh ta lựa chọn phương án hành động tốt nhất trong các phương án có thể có. Vì sự lựa chọn này gắn với yếu tố rủi ro. Nếu người bán lẻ không chú ý đến rủi ro, chúng ta có thể tính toán tính xác định tương đương của hành vi “mở cửa hàng” bàng cách sử dụng tiêu chuẩn giá trị bằng tiền dự kiến – một tiêu chuẩn căn cứ vào hậu quả tài chính của mỗi kết cục và gia quyền nó theo xác suất xuất hiện của nó.

Anh ta có hai phương án hành động là mở cửa hàng và không mở cửa hàng. Anh ta phải cân nhắc hai trạng thái tự nhiên, tức hai sự kiện có thể xảy ra: nền kinh tế phát triển mạnh hoặc suy thoái. Người bán lẻ phải đánh giá khả năng xuất hiện mỗi sự kiện và trong tình huống này, anh ta dựa trên kinh nghiệm và hiểu biết để nhận định rằng khả năng xuất hiện mỗi sự kiện bằng 50%. Cuối cùng, người bán lẻ ước tính hậu quả tài chính là nếu mở cửa hàng sẽ có lãi 40.000 đồng khi kinh tế phát triển mạnh vè lỗ 30.000đ nếu có suy thoái. Như vậy ta có công thức sau:

0,5 x (+40.000)đ= +20.000đ

0,5 x (-30.000)đ = -15.000đ

+20.000đ – 15.000đ = +5.000đ

Kết cục này chắc chắn lớn hơn 0 trong trường hợp không mở của hàng và nó biện minh cho việc tiếp tục thực hiện dự án này.

Song nếu người bán lẻ là người ghét rủi ro, tiêu chuẩn giá trị bằng tiền có thể không phải là tiêu chuẩn thích hợp, vì anh ta cần nhận được phần thưởng cho sự rủi ro để chấp nhận hành động. Việc vận dụng tiêu chuẩn cẩn thận hơn tiêu chuẩn tương đương với tính xác định sẽ làm giảm tiêu chuẩn tương đương với tính xác định của nhánh “mở cửa hàng” và điều này cũng dẫn đến quyết định tiếp tục mở cửa hàng.

Cây Quyết Định (Decision Tree)

Bạn có biết rằng trong cuộc sống hàng ngày, bạn vẫn đang sử dụng phương pháp Decision Tree (Cây quyết định). Chẳng hạn, bạn đến siêu thị mua sữa cho cả gia đình. Câu đầu tiên trong đầu bạn sẽ là: Bạn cần mua bao nhiêu sữa?

Bạn sẽ xác định: Nếu là ngày thường thì gia đình bạn sẽ sử dụng hết 1 lít sữa, còn cuối tuần thì sẽ là 1,5 lít. Như vậy, dựa theo ngày, bạn sẽ quyết định lượng thực phẩm cần mua cho gia đình bạn.

Đó chính là một dạng của cây quyết định nhị phân.

Khái niệm Cây quyết định (Decision Tree)

Cây quyết định ( Decision Tree) là một cây phân cấp có cấu trúc được dùng để phân lớp các đối tượng dựa vào dãy các luật. Các thuộc tính của đối tượngncó thể thuộc các kiểu dữ liệu khác nhau như Nhị phân (Binary) , Định danh (Nominal), Thứ tự (Ordinal), Số lượng (Quantitative) trong khi đó thuộc tính phân lớp phải có kiểu dữ liệu là Binary hoặc Ordinal.

Tóm lại, cho dữ liệu về các đối tượng gồm các thuộc tính cùng với lớp (classes) của nó, cây quyết định sẽ sinh ra các luật để dự đoán lớp của các dữ liệu chưa biết.

Ta hãy xét một ví dụ 1 kinh điển khác về cây quyết định. Giả sử dựa theo thời tiết mà các bạn nam sẽ quyết định đi đá bóng hay không?

Những đặc điểm ban đầu là:

Dựa vào những thông tin trên, bạn có thể xây dựng được mô hình như sau:

Dựa theo mô hình trên, ta thấy:

Nếu trời nắng, độ ẩm bình thường thì khả năng các bạn nam đi chơi bóng sẽ cao. Còn nếu trời nắng, độ ẩm cao thì khả năng các bạn nam sẽ không đi chơi bóng.

Thuật toán Cây quyết định (Decision Tree) Thuật toán ID3

ID3 (J. R. Quinlan 1993) sử dụng phương pháp tham lam tìm kiếm từ trên xuống thông qua không gian của các nhánh có thể không có backtracking. ID3 sử dụng Entropy và Information Gain để xây dựng một cây quyết định.

Ta xét ví dụ 2:

Bạn muốn xem xét sự thành công của một bộ phim thông qua hai yếu tố: diễn viên chính của phim và thể loại phim:

Giả sử, bạn muốn xác định độ thành công của bộ phim chỉ trên 1 yếu tố, bạn sẽ có hai cách thực hiện sau: qua diễn viên chính của phim và qua thể loại phim.

Qua sơ đồ, ta có thể thấy rõ ràng ràng, với phương pháp thứ nhất, ta phân loại được rõ ràng, trong khi phương pháp thứ hai, ta có một kết quả lộn xộn hơn. Và tương tự, cây quyết định sẽ thực hiện như trên khi thực hiện việc chọn các biến.

trong Cây quyết định (Decision Tree)

Entropy là thuật ngữ thuộc Nhiệt động lực học, là thước đo của sự biến đổi, hỗn loạn hoặc ngẫu nhiên. Năm 1948, Shannon đã mở rộng khái niệm Entropy sang lĩnh vực nghiên cứu, thống kê với công thức như sau:

Với một phân phối xác suất của một biến rời rạc x có thể nhận n giá trị khác nhau x 1,x 2,…,x n.

Giả sử rằng xác suất để x nhận các giá trị này là p i=p(x=x i).

Ký hiệu phân phối này là p=(p 1 ,p 2 ,…,p n). Entropy của phân phối này được định nghĩa là:

Giả sử bạn tung một đồng xu, entropy sẽ được tính như sau:

H = -[0.5 ln(0.5) + 0.5 ln(0.5)]

Hình vẽ trên biểu diễn sự thay đổi của hàm entropy. Ta có thể thấy rằng, entropy đạt tối đa khi xác suất xảy ra của hai lớp bằng nhau.

Information Gain trong Cây quyết định (Decision Tree)

Information Gain dựa trên sự giảm của hàm Entropy khi tập dữ liệu được phân chia trên một thuộc tính. Để xây dựng một cây quyết định, ta phải tìm tất cả thuộc tính trả về Infomation gain cao nhất.

Để xác định các nút trong mô hình cây quyết định, ta thực hiện tính Infomation Gain tại mỗi nút theo trình tự sau:

* Bước 1: Tính toán hệ số Entropy của biến mục tiêu S có N phần tử với N c phần tử thuộc lớp c cho trước:

* Bước 2: Tính hàm số Entropy tại mỗi thuộc tính: với thuộc tính x, các điểm dữ liệu trong S được chia ra K child node S 1, S 2, …, S K với số điểm trong mỗi child node lần lượt là m 1, m 2 ,…, m K , ta có:

Bước 3: Chỉ số Gain Information được tính bằng:

G(x, S) = H(S) – H(x,S)

Với ví dụ 2 trên, ta tính được hệ số Entropy như sau:

EntropyParent = -(0.57*ln(0.57) + 0.43*ln(0.43)) = 0.68

Hệ số Entropy theo phương pháp chia thứ nhất:

Entropyleft = -(.75*ln(0.75) + 0.25*ln(0.25)) = 0.56Entropyright = -(.33*ln(0.33) + 0.67*ln(0.67)) = 0.63

Ta có thể tính hệ số Information Gain như sau:

Information Gain = 0.68 – (4*0.56 + 3*0.63)/7 = 0.09

Hệ số Entropy với phương pháp chia thứ hai như sau:

Hệ số Information Gain:

Information Gain = 0.68 – (3*0.63 + 2*0.69 + 2*0.69)/7 = 0.02

So sánh kết quả, ta thấy nếu chia theo phương pháp 1 thì ta được giá trị hệ số Information Gain lớn hơn gấp 4 lần so với phương pháp 2. Như vậy, giá trị thông tin ta thu được theo phương pháp 1 cũng nhiều hơn phương pháp 2.

Thuật toán C4.5

Thuật toán C4.5 là thuật toán cải tiến của ID3.

Trong thuật toán ID3, Information Gain được sử dụng làm độ đo. Tuy nhiên, phương pháp này lại ưu tiên những thuộc tính có số lượng lớn các giá trị mà ít xét tới những giá trị nhỏ hơn. Do vậy, để khắc phục nhược điểm trên, ta sử dụng độ đo Gain Ratio (trong thuật toán C4.5) như sau:

Đầu tiên, ta chuẩn hoá information gain với trị thông tin phân tách (split information):

Trong đó: Split Info được tính như sau:

Giả sử chúng ta phân chia biến thành n nút cón và Di đại diện cho số lượng bản ghi thuộc nút đó. Do đó, hệ số Gain Ratio sẽ xem xét được xu hướng phân phối khi chia cây.

Áp dụng cho ví dụ trên và với cách chia thứ nhất, ta có

Split Info = – ((4/7)*log2(4/7)) – ((3/7)*log2(3/7)) = 0.98 Gain Ratio = 0.09/0.98 = 0.092

Tiêu chuẩn dừng

Trong các thuật toán Decision tree, với phương pháp chia trên, ta sẽ chia mãi các node nếu nó chưa tinh khiết. Như vậy, ta sẽ thu được một tree mà mọi điểm trong tập huấn luyện đều được dự đoán đúng (giả sử rằng không có hai input giống nhau nào cho output khác nhau). Khi đó, cây có thể sẽ rất phức tạp (nhiều node) với nhiều leaf node chỉ có một vài điểm dữ liệu. Như vậy, nhiều khả năng overfitting sẽ xảy ra.

Để tránh trường họp này, ta có thể dừng cây theo một số phương pháp sau đây:

nếu node đó có entropy bằng 0, tức mọi điểm trong node đều thuộc một class.

nếu node đó có số phần tử nhỏ hơn một ngưỡng nào đó. Trong trường hợp này, ta chấp nhận có một số điểm bị phân lớp sai để tránh overfitting. Class cho leaf node này có thể được xác định dựa trên class chiếm đa số trong node.

nếu khoảng cách từ node đó đến root node đạt tới một giá trị nào đó. Việc hạn chế chiều sâu của tree này làm giảm độ phức tạp của tree và phần nào giúp tránh overfitting.

nếu tổng số leaf node vượt quá một ngưỡng nào đó.

nếu việc phân chia node đó không làm giảm entropy quá nhiều (information gain nhỏ hơn một ngưỡng nào đó).

Ngoài ra, ta còn có phương pháp cắt tỉa cây.

Một số thuật toán khác

Ngoài ID3, C4.5, ta còn một số thuật toán khác như:

Thuật toán CHAID: tạo cây quyết định bằng cách sử dụng thống kê chi-square để xác định các phân tách tối ưu. Các biến mục tiêu đầu vào có thể là số (liên tục) hoặc phân loại.

Thuật toán C&R: sử dụng phân vùng đệ quy để chia cây. Tham biến mục tiêu có thể dạng số hoặc phân loại.

MARS

Conditional Inference Trees

Ưu/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 bới những lợi ích của nó:

Mô hình sinh ra các quy tắc dễ hiểu cho người đọc, tạo ra bộ luật với mỗi nhánh lá là một luật của cây.

Dữ liệu đầu vào có thể là là dữ liệu missing, không cần chuẩn hóa hoặc tạo biến giả

Có thể làm việc với cả dữ liệu số và dữ liệu phân loại

Có thể xác thực mô hình bằng cách sử dụng các kiểm tra thống kê

Có khả năng là việc với dữ liệu lớn

Nhược điểm

Kèm với đó, 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 rất lớn vào dữ liệu của bạn. Thạm chí, với một sự thay đổi nhỏ trong bộ dữ liệu, cấu trúc mô hình cây quyết định có thể thay đổi hoàn toàn.

Cây quyết định hay gặp vấn đề overfitting

Cài đặt cây quyết định với sklearn

Hãy theo dõi https://trituenhantao.io/ để có thêm những bài viết hay mới.

Phản hồi hoàn thiện nội dung

Machine Learning Decision Tree (Cây Quyết Định)

Cây quyết định (Decision Tree) là một cây phân cấp có cấu trúc được dùng để phân lớp các đối tượng dựa vào dãy các luật (series of rules). Khi cho dữ liệu về các đối tượng gồm các thuộc tính cùng với lớp (classes) của nó, cây quyết định sẽ sinh ra các luật để dự đoán lớp của các đối tượng chưa biết (unseen data).

I. CẤU TRÚC DECISION TREES Decision Trees gồm 3 phần chính: 1 node gốc (root node), những node lá (leaf nodes) và các nhánh của nó (branches). Node gốc là điểm bắt đầu của cây quyết định và cả hai node gốc và node chứa câu hỏi hoặc tiêu chí để được trả lời. Nhánh biểu diễn các kết quả của kiểm tra trên nút. Ví dụ câu hỏi ở node đầu tiên yêu cầu câu trả lời là “yes” hoặc là “no” thì sẽ có 1 node con chịu trách nhiệm cho phản hồi là “yes”, 1 node là “no”.

ID3 (Iterative Dichotomiser 3) Algorithm Thuật toán ID3 có thể được tóm tắt như sau:

Chọn thuộc tính có entropy lớn nhất

Nối node với thuộc tính đó

ID3 (Examples, Target_Attribute, Attributes)

Tạo node gốc

Nếu tất cả các examples (ví dụ) đều nằm cùng một lớp là dương thì return một nút lá được gán nhãn bởi lớp đó (lớp +).

Nếu tất cả các examples (ví dụ) đều nằm cùng một lớp là âm thì return một nút lá được gán nhãn bởi lớp đó (lớp -).

Nếu tập thuộc tính Attributes là rỗng thì return Cây quyết định có nút Root được gắn với nhãn lớp bằng giá trị chung nhất trong tập thuộc tính ở tập ví dụ (Examples).

Chọn thuộc tính A – Thuộc tính trong tập Attributes có khả năng phân loại “tốt nhất” đối với Examples

Thuộc tính kiểm tra cho nút Root ← A và lấy nó làm gốc cho cây hiện tại

Với mỗi giá trị vi của A:

Bổ sung một nhánh cây mới nằm phía dưới node gốc, tương ứng với trường hợp A = vi

Xác định Examples(vi) sao cho tập con của Examples có giá trị vi cho A

Nếu Examples(vi) rỗng

# Tạo một nút lá được gắn nhãn = giá trị đích phổ biến nhất trong Examples. Sau đó gắn nút lá này vào nhánh cây mới vừa tạo.

Ngược lại, gắn vào nhánh cây mới vừa tạo một cây con sinh ra bởi ID3 (Examples(vi), Target_Attribute, Attributes – {A})

C4.5 là thuật toán phân lớp dữ liệu dựa trên cây quyết định hiệu quả và phổ biến trong những ứng dụng khai phá cơ sở dữ liệu có kích thước nhỏ. C4.5 xây dựng cây quyết định từ tập training data tương tự như ID3.

Tập training data S gồm các mẫu đã được phân loại sẵn s1, s2,… Mỗi mẫu si = x1,x2,… với x1, x2 là 1 vector biểu diễn cho thuộc tính hoặc đặc điểm của mẫu. Một tập vector C = c1,c2,… với c1, c2 biểu diễn cho mỗi lớp mà mỗi mẫu thuộc về.

Với mỗi lớp của cây, C4.5 chọn một thuộc tính của dữ liệu mà phân chia tập các mẫu thành nhiều tập con, được nâng cao chất lượng một cách hiệu quả nhất. Tiêu chuẩn của nó là thu được information gain (sự khác biệt về entropy) – kết quả từ việc chọn một thuộc tính cho việc chia tách dữ liệu. Quyết định đưa ra dựa trên tập thuộc tính với information gain được chuẩn hóa cao nhất. Thuật toán C4.5 sau đó sẽ lặp lại với các danh sách con nhỏ hơn.

Một vài trường hợp cơ bản:

– Tất cả các mẫu đều thuộc cùng một lớp. Khi điều này xảy ra, nó chỉ đơn giản tạo ra một nút lá cho cây quyết định và cho biết chọn lớp đó.

– Không có tính năng nào cung cấp bất kỳ information gain. Trong trường hợp này, C4.5 tạo ra một node quyết định (decision node) bằng cách sử dụng giá trị kì vọng của lớp đó.

– Với các trường hợp khác, C4.5 lần nữa tạo ra một node quyết định bằng cách sử dụng giá trị kì vọng của lớp đó.

Thuật toán được giải mã như sau:

ComputerClassFrequency(T);

Kiểm tra các trường hợp cơ bản rồi tạo ra node quyết định

Create a decision node N;

Gán chúng tôi = Thuộc tính với information gain được chuẩn hóa cao nhất

N.test=AttributeWithBestGain;

Thuật toán C4.5 sau đó sẽ lặp lại với các danh sách con nhỏ hơn và gán những node như là các node con

if (N.test is continuous)

ForEach T’ in the splitting of T

Ví dụ mô tả cách tính information gain:

Trong tập dữ liệu trên: S1 là tập những bản ghi có giá trị phân lớp là yes, S2 là tập những bản ghi có giá trị phân lớp là no. Khi đó:

Tính G(S,A) với A lần lượt là từng thuộc tính:

Tính tương tự với các thuộc tính khác ta được: – A = income: Gain (S, income) = 0.029 – A = student: Gain (S, student) = 0.151 – A = credit_rating: Gain ( S, credit_rating) = 0.048 Thuộc tính age là thuộc tính có độ đo Information Gain lớn nhất. Do vậy age được chọn làm thuộc tính phát triển tại node đang xét.

Hiệu của phân lớp của cây quyết định (Series of Rules) phụ thuộc rất lớn vào training data. Chẳng hạn cây quyết định được tạo ra bởi chỉ giới hạn 10 samples training data trong ví dụ trên thì hiệu quả ứng dụng cây quyết định để dự đoán các trường hợp khác là không cao (thường training data phải đủ lớn và tin cậy)Cây quyết định là một phương pháp phân lớp rất hiệu quả và dễ hiểu. Tuy nhiên có một số chú ý khi sử dụng cây quyết định trong xây dựng các mô hình phân lớp như sau:

Có rất nhiều thuật toán phân lớp như ID3, J48, C4.5, CART (Classification and Regression Tree),… Việc chọn thuật toán nào để có hiệu quả phân lớp cao tùy thuộc vào rất nhiều yếu tố, trong đó cấu trúc dữ liệu ảnh hưởng rất lớn đến kết quả của các thuật toán. Chẳng hạn như thuật toán ID3 và CART cho hiệu quả phân lớp rất cao đối với các trường dữ liệu số (quantitative value) trong khi đó các thuật toán như J48, C4.5 có hiệu quả hơn đối với các dữ liệu Qualititive value (ordinal, Binary, nominal).

Machine learning decision tree (cây quyết định)

Cây Quyết Định (Decision Tree) Là Gì? Tìm Hiểu Thuật Toán Id3

Cây quyết định là gì?

DT được áp dụng vào cả 2 bài toán: Phân loại ( Classification) và Hồi quy ( Regression). Tuy nhiên bài toán phân loại được sử dụng nhiều hơn.

Có nhiều thuật toán để xây dựng DT, trong bài này ta tìm hiểu một thuật toán nổi tiếng và cơ bản nhất của DT là thuật toán ID3.

Thuật toán ID3

Iterative Dichotomiser 3 (ID3) là thuật toán nổi tiếng để xây dựng Decision Tree, áp dụng cho bài toán Phân loại ( Classification) mà tất các các thuộc tính để ở dạng category.

Để dễ hiểu ta cùng tìm hiểu thuật toán này qua ví dụ.

Ta có tập Training Data như bảng dưới:

Data của ta có 4 thuộc tính: Engine, Type, Color, 4WD. Để tính toán được DT, ta cần phân chia các thuộc tính vào các node đánh giá. Vậy làm sao để biết được thuộc tính nào quan trọng, nên đặt ở gốc, thuộc tính nào ở nhánh…

Trong thuật toán ID3, các thuộc tính được đánh giá dựa trên Hàm số Entropy, hàm số phổ biến trong toán học xác suất.

Hàm số Entropy

Cho một phân phối xác suất của một biến rời rạc $x$ có thể nhận $n$ giá trị khác nhau $x_1, x_2, dots, x_n$. Giả sử rằng xác suất để $x$ nhận các giá trị này là $p_i = p(x = x_i)$

Ký hiệu phân phối này là $mathbf{p} = (p_1, p_2, dots, p_n)$. Entropy của phân phối này là:

$$ H(mathbf{p}) = -sum_{i=1}^n p_i log_2(p_i)quadquad $$

Hàm Entropy được biểu diễn dưới dạng đồ thị như sau:

Từ đồ thị ta thấy, hàm Entropy sẽ đạt giá trị nhỏ nhất nếu có một giá trị $p_i = 1$, đạt giá trị lớn nhất nếu tất cả các $p_i$ bằng nhau. Hàm Entropy càng lớn thì độ ngẫu nhiên của các biến rời rạc càng cao (càng không tinh khiết).

Với cây quyết định, ta cần tạo cây như thế nào để cho ta nhiều thông tin nhất, tức là Entropy là cao nhất.

Information Gain

Bài toán của ta trở thành, tại mỗi tầng của cây, cần chọn thuộc tính nào để độ giảm Entropy là thấp nhất. Người ta có khái niệm Information Gain được tính bằng $$ Gain(S,f) = H(S) – H(f,S) $$ trong đó: $H({S})$ là Entropy tổng của toàn bộ tập data set $S$. $H(f, S)$ là Entropy được tính trên thuộc tính $f$.

Do $H({S})$ là không đổi với mỗi tầng, ta chọn thuộc tính $f$ có Entropy nhỏ nhất để thu được $Gain(S,f)$ lớn nhất.

Tính Entropy của các thuộc tính Xét thuộc tính Engine

Thuộc tính này có thể nhận 1 trong 2 giá trị 1000cc, 2000cc, tương ứng với 2 child node. Gọi tập hợp các điểm trong mỗi child node này lần lượt là $S_1$, $S_2$.

Sắp xếp lại theo thuộc tính Engine ta có 2 bảng nhỏ.

Engine 1000cc ($S_1$)

Engine 2000cc ($S_2$)

Child node ứng với Engine 1000cc sẽ có Entropy = 0 do tất cả các giá trị đều là Yes. Ta chỉ việc tính Entropy với Engine 2000cc. Sau đó tính Entropy trung bình. Cụ thể như sau:

$$ begin{aligned} H(S_1) &=& 0 cr H(S_2) &=& -frac{2}{4}mathcal{log}_2left(frac{2}{4}right) – frac{2}{4}mathcal{log}_2left(frac{2}{4}right) = 1 cr H({engine}, S) &=& frac{4}{8}H(S_1) + frac{4}{8}H(S_2) = 0.5 end{aligned} $$

Xét thuộc tính Type

Thuộc tính này có thể nhận 1 trong 3 giá trị SUV, Senda, Sport tương ứng với 3 child node. Gọi tập hợp các điểm trong mỗi child node này lần lượt là $S_u$, $S_e$, $S_p$.

Sắp xếp lại theo thuộc tính Type ta có 3 bảng nhỏ.

Type SUV ($S_u$)

Type Sedan ($S_e$)

Type Sport ($S_p$)

Tương tự, ta lần lượt tính Entropy như bên dưới:

$$ begin{aligned} H(S_u) &=& 0 cr H(S_e) &=& -frac{2}{3}mathcal{log}_2left(frac{2}{3}right) – frac{1}{3}mathcal{log}_2left(frac{1}{3}right) approx 0.918 cr H(S_p) &=& -frac{1}{2}mathcal{log}_2left(frac{1}{2}right) – frac{1}{2}mathcal{log}_2left(frac{1}{2}right) = 1 cr H({type}, S) &=& frac{3}{8}H(S_u) + frac{3}{8}H(S_e) + frac{2}{8}H(S_p) approx 0.594 end{aligned} $$

Xét thuộc tính Color

Thuộc tính này có thể nhận 1 trong 2 giá trị Silver, Blue tương ứng với 2 child node. Gọi tập hợp các điểm trong mỗi child node này lần lượt là $S_s$, $S_b$.

Sắp xếp lại theo thuộc tính Color ta có 2 bảng nhỏ.

Color Silver ($S_s$)

Color Blue ($S_b$)

Dễ thấy, 2 giá trị Silver và Blue đều có tỉ lệ Yes, No như nhau là 3⁄ 4 và 1⁄ 4. Do đó ta tính luôn Entropy trung bình:

$$ begin{aligned} H({color}, S) &=& -frac{3}{4}mathcal{log}_2left(frac{3}{4}right) – frac{1}{4}mathcal{log}_2left(frac{1}{4}right) approx 0.811 end{aligned} $$

Xét thuộc tính 4WD

Thuộc tính này có thể nhận 1 trong 2 giá trị Yes, No tương ứng với 2 child node. Gọi tập hợp các điểm trong mỗi child node này lần lượt là $S_y$, $S_n$.

Sắp xếp lại theo thuộc tính 4WD ta có 2 bảng nhỏ.

4WD Yes ($S_y$)

4WD No ($S_n$)

Tương tự Color, ta tính Entropy trung bình:

$$ begin{aligned} H({4wd}, S) &=& -frac{3}{4}mathcal{log}_2left(frac{3}{4}right) – frac{1}{4}mathcal{log}_2left(frac{1}{4}right) approx 0.811 end{aligned} $$

Chọn thuộc tính có Entropy nhỏ nhất

Sau khi tính Entropy trung bình của 4 thuộc tính ta thu được: $H({engine}, S) = 0.5$ $H({type}, S) approx 0.594$ $H({color}, S) approx 0.811$ $H({4wd}, S) approx 0.811$

Thuộc tính Engine có giá trị Entropy nhỏ nhất nên ta chọn là node đánh giá đầu tiên. Với Engine 1000cc, tất cả các data đều có giá trị Yes, vì vậy ta thu được node là Yes ở nhánh 1000cc. Ta tiếp tục tính cho nhánh Engine 2000cc với tập data nhỏ hơn là

Tương tự ta lần lượt tính Entropy cho 3 thuộc tính là: Type, Color, 4WD

Với thuộc tính Type: $$ begin{aligned} H(S_u) &=& 0 cr H(S_e) &=& 0 cr H(S_p) &=& -frac{1}{2}mathcal{log}_2left(frac{1}{2}right) – frac{1}{2}mathcal{log}_2left(frac{1}{2}right) = 1 cr H({type}, S) &=& frac{1}{4}H(S_u) + frac{1}{4}H(S_e) + frac{2}{4}H(S_p) = 0.5 end{aligned} $$

Với thuộc tính Color: Do 2 giá trị Silver và Blue có cùng tỉ lệ Yes, No là 1⁄ 2 và 1⁄ 2. $$ begin{aligned} H({color}, S) &=& -frac{1}{2}mathcal{log}_2left(frac{1}{2}right) – frac{1}{2}mathcal{log}_2left(frac{1}{2}right) = 1 end{aligned} $$

Với thuộc tính 4WD: $$ begin{aligned} H(S_y) &=& -frac{2}{3}mathcal{log}_2left(frac{2}{3}right) – frac{1}{3}mathcal{log}_2left(frac{1}{3}right) approx 0.918 cr H(S_n) &=& 0 cr H({4wd}, S) &=& frac{3}{4}H(S_y) + frac{1}{4}H(S_n) approx 0.688 end{aligned} $$

Vậy ta chọn Type là node đánh giá tiếp theo.

Với trường hợp Type là SUV hoặc Sedan, ta có ngay node lá vì chỉ có một kết quả. Với trường hợp Type là Sport, do thuộc tính Color là giống nhau với tất cả data, ta chọn node đánh giá tiếp theo là 4WD.

Kết quả

Ta thu được Decision Tree như hình bên dưới.

Kiểm tra (Validation)

Ta sẽ tiến hành kiểm tra mô hình DT ta vừa tạo được bằng tập Test Data như bên dưới:

Ta có bảng mapping đánh giá kết quả như sau:

Dựa vào DT ta vừa tạo được, ta tiến hành đánh giá như sau:

Các thông số áp dụng để đánh giá được tính như sau: $$ begin{aligned} Accuracy &=& frac{TP+TN}{TP+FP+TN+FN} = 0.5 cr Recall &=& frac{TP}{TP+FN} = 0.5 cr Precision &=& frac{TP}{TP+FP} = 1 cr F-Measure &=& frac{2 times Recall times Precision}{Recall + Precision} approx 0.667 end{aligned} $$

Nhìn chung Decision Tree tìm được có độ chính xác không cao khi chạy thử với Test Data. Nguyên nhân chính có lẽ là do tập Training Data quá ít.

Mặt Yếu Của Cây Quyết Định Là Gì?

Câu trả lời của tôi được chuyển đến GIỎ HÀNG (việc triển khai C 4.5 / C 5) mặc dù tôi không nghĩ là bị giới hạn. Tôi đoán rằng đây là những gì OP có trong đầu – đó thường là ý nghĩa của ai đó khi họ nói “Cây quyết định”.

Hạn chế của cây quyết định :

Hiệu năng thấp

Bởi ‘hiệu suất’ tôi không có nghĩa là độ phân giải, nhưng tốc độ thực hiện . Lý do tại sao nó nghèo là vì bạn cần phải ‘vẽ lại cây’ mỗi khi bạn muốn cập nhật mô hình GIỎ HÀNG – dữ liệu được phân loại bởi Cây đã được đào tạo, sau đó bạn muốn thêm vào Cây (nghĩa là sử dụng như một điểm dữ liệu đào tạo) yêu cầu bạn bắt đầu từ hơn – không thể thêm các trường hợp đào tạo, vì chúng có thể được áp dụng cho hầu hết các thuật toán học có giám sát khác. Có lẽ cách tốt nhất để nói điều này là Cây quyết định không thể được đào tạo ở chế độ trực tuyến, thay vì chỉ ở chế độ hàng loạt. Rõ ràng là bạn sẽ không nhận thấy giới hạn này nếu bạn không cập nhật trình phân loại của mình, nhưng sau đó tôi sẽ mong đợi rằng bạn sẽ thấy độ phân giải giảm.

Điều này rất quan trọng vì ví dụ, đối với Perceptionron nhiều lớp, khi được đào tạo, nó có thể bắt đầu phân loại dữ liệu; dữ liệu đó cũng có thể được sử dụng để ‘điều chỉnh’ trình phân loại đã được đào tạo, mặc dù với Cây quyết định, bạn cần phải đào tạo lại với toàn bộ tập dữ liệu (dữ liệu gốc được sử dụng trong đào tạo cộng với bất kỳ trường hợp mới nào).

Giải quyết kém về dữ liệu với các mối quan hệ phức tạp giữa các biến

Cây quyết định phân loại theo đánh giá từng bước một điểm dữ liệu của lớp chưa biết, một nút tại thời điểm, bắt đầu từ nút gốc và kết thúc bằng nút cuối. Và tại mỗi nút, chỉ có hai khả năng (trái-phải), do đó có một số mối quan hệ khác nhau mà Cây quyết định không thể học được.

Thực tế giới hạn trong phân loại

Cây quyết định hoạt động tốt nhất khi chúng được đào tạo để gán điểm dữ liệu cho một lớp – tốt nhất là một trong số ít các lớp có thể. Tôi không tin rằng mình đã từng có bất kỳ thành công nào khi sử dụng Cây quyết định trong chế độ hồi quy (nghĩa là đầu ra liên tục, chẳng hạn như giá hoặc doanh thu trọn đời dự kiến). Đây không phải là một giới hạn chính thức hoặc vốn có mà là một thực tế. Hầu hết thời gian, Cây quyết định được sử dụng để dự đoán các yếu tố hoặc kết quả riêng biệt.

Độ phân giải kém với các biến kỳ vọng liên tục

Một lần nữa, về nguyên tắc, bạn có thể có các biến độc lập như “thời gian tải xuống” hoặc “số ngày kể từ lần mua trực tuyến trước” – chỉ cần thay đổi tiêu chí chia tách của bạn thành phương sai (thường là Thông tin Entropy hoặc Gini tạp chất cho các biến rời rạc) nhưng trong tôi kinh nghiệm Cây quyết định hiếm khi hoạt động tốt trong những trường hợp này. Trường hợp ngoại lệ là các trường hợp như “tuổi của học sinh” trông có vẻ liên tục nhưng trong thực tế, phạm vi của các giá trị là khá nhỏ (đặc biệt nếu chúng được báo cáo là số nguyên).

Cập nhật thông tin chi tiết về Cây Quyết Định (Decision Tree) Là Gì? Ví Dụ Về Cây Quyết Định trên website Bac.edu.vn. Hy vọng nội dung bài viết sẽ đáp ứng được nhu cầu của bạn, chúng tôi sẽ thường xuyên cập nhật mới nội dung để bạn nhận được thông tin nhanh chóng và chính xác nhất. Chúc bạn một ngày tốt lành!