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

Bạn sở hữu hiểu được nhập cuộc sống thường ngày từng ngày, chúng ta vẫn đang được dùng cách thức Decision Tree (Cây quyết định). Chẳng hạn, chúng ta cho tới khu chợ mua sắm sữa cho tất cả mái ấm gia đình. Câu thứ nhất nhập đầu các bạn sẽ là: quý khách hàng cần thiết mua sắm từng nào sữa?

Bạn tiếp tục xác định: Nếu là ngày thông thường thì mái ấm gia đình các bạn sẽ dùng không còn 1 lít sữa, còn vào ngày cuối tuần thì tiếp tục là một trong những,5 lít. Như vậy, dựa trên ngày, các bạn sẽ đưa ra quyết định lượng đồ ăn thức uống cần thiết mua sắm mang lại mái ấm gia đình chúng ta.

Bạn đang xem: decision tree la gi

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

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

Cây đưa ra quyết định (Decision Tree) là một trong những cây phân cấp cho sở hữu cấu hình được dùng để làm phân lớp những đối tượng người sử dụng phụ thuộc vào mặt hàng những luật. Các tính chất của đối tượngncó thể với những loại tài liệu không giống nhau như Nhị phân (Binary) , Định danh (Nominal), Thứ tự động (Ordinal), Số lượng (Quantitative) trong những khi bại tính chất phân lớp nên sở hữu loại tài liệu là Binary hoặc Ordinal.

Tóm lại, mang lại tài liệu về những đối tượng người sử dụng bao gồm những tính chất cùng theo với lớp (classes) của chính nó, cây đưa ra quyết định tiếp tục sinh rời khỏi những luật để tham gia đoán lớp của những tài liệu chưa chắc chắn.

Ta hãy xét một ví dụ 1 tầm cỡ không giống về cây đưa ra quyết định. Giả sử dựa trên khí hậu nhưng mà chúng ta nam giới tiếp tục đưa ra quyết định lên đường đá bóng hoặc không?

Những điểm lưu ý lúc đầu là:

Thời tiết
Độ ẩm
Gió

Dựa nhập những vấn đề bên trên, bạn cũng có thể xây cất được quy mô như sau:

Dựa bám theo quy mô bên trên, tớ thấy:

Nếu trời nắng nóng, nhiệt độ thông thường thì kĩ năng chúng ta nam giới đi dạo bóng tiếp tục cao. Còn nếu như trời nắng nóng, nhiệt độ cao thì kĩ năng chúng ta nam giới sẽ không còn đi dạo bóng.

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

Thuật toán ID3

Giờ tất cả chúng ta hãy nằm trong dò xét hiểu phương thức sinh hoạt của thuật toán cây đưa ra quyết định trải qua thuật toán giản dị và đơn giản ID3.

ID3 (J. R. Quinlan 1993) dùng cách thức tham lam lam dò xét kiếm kể từ bên trên xuống trải qua không khí của những nhánh rất có thể không tồn tại backtracking. ID3 dùng Entropy và Information Gain nhằm xây cất một cây đưa ra quyết định.

Ta xét ví dụ 2:

Bạn ham muốn kiểm tra sự thành công xuất sắc của một bộ phim truyền hình trải qua nhị yếu ớt tố: trình diễn viên chủ yếu của phim và chuyên mục phim:

Lead Actor	Genre	Hit(Y/N)
Amitabh Bacchan	Action	Yes
Amitabh Bacchan	Fiction	Yes
Amitabh Bacchan	Romance	No
Amitabh Bacchan	Action	Yes
Abhishek Bacchan	Action	No
Abhishek Bacchan	Fiction	No
Abhishek Bacchan	Romance	Yes

Giả sử, mình thích xác lập phỏng thành công xuất sắc của bộ phim truyền hình chỉ bên trên 1 nguyên tố, các bạn sẽ sở hữu nhị cơ hội tiến hành sau: qua chuyện trình diễn viên chủ yếu của phim và qua chuyện chuyên mục phim.

Qua sơ trang bị, tớ rất có thể thấy rõ rệt rành rành, với cách thức loại nhất, tớ phân loại được rõ nét, trong những khi cách thức loại nhị, tớ sở hữu một thành quả lộn xộn rộng lớn. Và tương tự động, cây đưa ra quyết định tiếp tục tiến hành như bên trên Khi tiến hành việc lựa chọn những trở thành.

Có thật nhiều thông số không giống nhau nhưng mà cách thức cây đưa ra quyết định dùng nhằm phân loại. Dưới phía trên, tôi tiếp tục thể hiện nhị thông số thông dụng là Information Gain và Gain Ratio (ngoài rời khỏi còn thông số Gini).

Entropy nhập Cây đưa ra quyết định (Decision Tree)

Entropy là thuật ngữ nằm trong Nhiệt động lực học tập, là thước đo của sự việc chuyển đổi, láo loàn hoặc tình cờ. Năm 1948, Shannon đang được không ngừng mở rộng định nghĩa Entropy thanh lịch nghành nghề dịch vụ phân tích, tổng hợp với công thức như sau:

Với một phân phối phần trăm của một trở thành tách rạc x có thể nhận n giá trị không giống nhau x₁,x₂,…,x_n.

Giả sử rằng phần trăm để x nhận những độ quý hiếm này là p_i=p(x=x_i).

Ký hiệu phân phối này là p=(p₁ ,p₂ ,…,p_n). Entropy của phân phối này được khái niệm là:

H(p)= – ∑ⁿ_n=1 p_i log(p_i)

Giả sử chúng ta tung một đồng xu, entropy sẽ tiến hành tính như sau:

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

Hình vẽ bên trên màn trình diễn sự thay cho thay đổi của hàm entropy. Ta rất có thể thấy rằng, entropy đạt tối nhiều Khi phần trăm xẩy ra của nhị lớp cân nhau.

P tinh anh khiết: p_i = 0 hoặc p_i = 1
P vẩn đục: p_i = 0.5, Khi bại hàm Entropy đạt đỉnh điểm nhất

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

Information Gain dựa vào sự hạn chế của hàm Entropy Khi tập luyện tài liệu được phân loại bên trên một tính chất. Để xây cất một cây đưa ra quyết định, tớ nên dò xét toàn bộ tính chất trả về Infomation gain tối đa.

Để xác lập những nút nhập quy mô cây đưa ra quyết định, tớ tiến hành tính Infomation Gain bên trên từng nút bám theo trình tự động sau:

•Bước 1: Tính toán thông số Entropy của trở thành tiềm năng S sở hữu N thành phần với N_c thành phần nằm trong lớp c mang lại trước:

H(S)= – ∑^c_c=1 (N_c/N) log(N_c/N)

•Bước 2: Tính hàm số Entropy bên trên từng nằm trong tính: với tính chất x, những điểm tài liệu nhập S được chia nhỏ ra K child node S₁, S₂, …, S_K với số điểm trong những child node theo lần lượt là m_1, m₂ ,…, m_K , tớ có:

H(x, S) = ∑^K_k=1 (m_k / N) * H(S_k )

Xem thêm: tiểu ma vương tìm chồng cho mẹ

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

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

Với ví dụ 2 bên trên, tớ tính được thông số Entropy như sau:

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

Hệ số Entropy bám theo cách thức phân tách loại nhất:

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

Ta rất có thể tính thông số Information Gain như sau:

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

Hệ số Entropy với cách thức phân tách loại nhị như sau:

Entropy_left= -(.67*ln(0.67) + 0.33*ln(0.33)) = 0.63
Entropy_middle= -(.5*ln(0.5) + 0.5*ln(0.5)) = 0.69
Entropy_right= -(.5*ln(0.5) + 0.5*ln(0.5)) = 0.69

Hệ số Information Gain:

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

So sánh thành quả, tớ thấy nếu như phân tách bám theo cách thức 1 thì tớ giá tốt trị thông số Information Gain to hơn cấp 4 phen đối với cách thức 2. Như vậy, độ quý hiếm vấn đề tớ nhận được bám theo cách thức 1 cũng nhiều hơn nữa cách thức 2.

Thuật toán C4.5

Thuật toán C4.5 là thuật toán nâng cấp của ID3.

Trong thuật toán ID3, Information Gain được dùng thực hiện phỏng đo. Tuy nhiên, cách thức đó lại ưu tiên những tính chất sở hữu con số rộng lớn những độ quý hiếm nhưng mà không nhiều xét cho tới những độ quý hiếm nhỏ rộng lớn. Do vậy, nhằm xử lý điểm yếu bên trên, tớ dùng phỏng đo Gain Ratio (trong thuật toán C4.5) như sau:

Đầu tiên, tớ chuẩn chỉnh hoá information gain với trị vấn đề phân tích (split information):

Trong đó: Split Info được xem như sau:

Giả sử tất cả chúng ta phân loại trở thành n nút cón và Di thay mặt mang lại con số bạn dạng ghi nằm trong nút bại. Do bại, thông số Gain Ratio tiếp tục kiểm tra được Xu thế phân phối Khi phân tách cây.

Áp dụng mang lại ví dụ bên trên và với cơ hội phân tách loại nhất, tớ có

Split Info = – ((4/7)*log₂(4/7)) – ((3/7)*log₂(3/7)) = 0.98

Gain Ratio = 0.09/0.98 = 0.092

Tiêu chuẩn chỉnh dừng

Trong những thuật toán Decision tree, với cách thức phân tách bên trên, tớ tiếp tục phân tách mãi những node nếu như nó đang chưa tinh anh khiết. Như vậy, tớ tiếp tục nhận được một tree nhưng mà từng điểm nhập tập luyện huấn luyện và giảng dạy đều được Dự kiến đích thị (giả sử rằng không tồn tại nhị input như thể nhau này mang lại output không giống nhau). Khi bại, cây rất có thể tiếp tục rất rất phức tạp (nhiều node) với khá nhiều leaf node chỉ tồn tại một vài ba điểm tài liệu. Như vậy, nhiều kĩ năng overfitting tiếp tục xẩy ra.

Để tách ngôi trường họp này, tớ rất có thể ngừng cây bám theo một số trong những cách thức sau đây:

nếu node bại sở hữu entropy vì thế 0, tức từng điểm nhập node đều nằm trong một class.
nếu node bại sở hữu số thành phần nhỏ rộng lớn một ngưỡng này bại. Trong tình huống này, tớ gật đầu sở hữu một số trong những điểm bị phân lớp sai nhằm tách overfitting. Class mang lại leaf node này rất có thể được xác lập dựa vào class cướp hầu hết nhập node.
nếu khoảng cách kể từ node bại cho tới root node đạt cho tới một độ quý hiếm này bại. Việc hạn chế chiều thâm thúy của tree này thực hiện hạn chế phỏng phức tạp của tree và phần này chung tách overfitting.
nếu tổng số leaf node vượt lên vượt một ngưỡng này bại.
nếu việc phân loại node bại ko thực hiện hạn chế entropy rất nhiều (information gain nhỏ rộng lớn một ngưỡng này đó).

Ngoài rời khỏi, tớ còn tồn tại cách thức hạn chế tỉa cây.

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

Ngoài ID3, C4.5, tớ còn một số trong những thuật toán không giống như:

Thuật toán CHAID: tạo ra cây đưa ra quyết định bằng phương pháp dùng tổng hợp chi-square nhằm xác lập những phân tích tối ưu. Các trở thành tiềm năng nguồn vào rất có thể là số (liên tục) hoặc phân loại.
Thuật toán C&R: dùng phân vùng đệ quy nhằm phân tách cây. Tham trở thành tiềm năng rất 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 đưa ra quyết định là một trong những thuật toán giản dị và đơn giản và thông dụng. Thuật toán này được dùng thoáng rộng bươi những quyền lợi của nó:

Mô hình sinh rời khỏi những quy tắc dễ dàng nắm bắt cho những người gọi, tạo nên cỗ luật với từng nhánh lá là một trong những luật của cây.
Dữ liệu nguồn vào rất có thể tà tà tài liệu missing, ko cần thiết chuẩn chỉnh hóa hoặc tạo ra trở thành fake
Có thể thao tác với tất cả tài liệu số và tài liệu phân loại
Có thân xác thực quy mô bằng phương pháp dùng những đánh giá tổng hợp
Có kĩ năng là sự việc với tài liệu rộng lớn

Nhược điểm

Xem thêm: tien vo truyen ky

Kèm với bại, cây đưa ra quyết định cũng có thể có những điểm yếu cụ thể:

Mô hình cây đưa ra quyết định dựa vào rất rộng lớn nhập tài liệu của công ty. Thạm chí, với cùng một sự thay cho thay đổi nhỏ nhập cỗ tài liệu, cấu hình quy mô cây đưa ra quyết định rất có thể thay cho thay đổi trọn vẹn.
Cây đưa ra quyết định hoặc bắt gặp yếu tố overfitting