Khai thác dữ liệu - Cảm ứng cây quyết định

Cây quyết định là một cấu trúc bao gồm nút gốc, các nhánh và các nút lá. Mỗi nút bên trong biểu thị một phép thử trên một thuộc tính, mỗi nhánh biểu thị kết quả của một phép thử và mỗi nút lá chứa một nhãn lớp. Nút trên cùng trong cây là nút gốc.

Cây quyết định sau dành cho khái niệm buy_computer cho biết liệu khách hàng tại một công ty có khả năng mua máy tính hay không. Mỗi nút bên trong đại diện cho một thử nghiệm trên một thuộc tính. Mỗi nút lá đại diện cho một lớp.

Những lợi ích của việc có một cây quyết định như sau:

Nó không yêu cầu bất kỳ kiến thức miền nào.
Nó rất dễ hiểu.
Các bước tìm hiểu và phân loại của cây quyết định rất đơn giản và nhanh chóng.

Thuật toán cảm ứng cây quyết định

Một nhà nghiên cứu máy tên J. Ross Quinlan vào năm 1980 đã phát triển một thuật toán cây quyết định được gọi là ID3 (Iterative Dichotomiser). Sau đó, ông trình bày C4.5, là phiên bản kế nhiệm của ID3. ID3 và C4.5 áp dụng cách tiếp cận tham lam. Trong thuật toán này, không có backtracking; cây được xây dựng theo cách phân chia và chinh phục đệ quy từ trên xuống.

Generating a decision tree form training tuples of data partition D
Algorithm : Generate_decision_tree

Input:
Data partition, D, which is a set of training tuples 
and their associated class labels.
attribute_list, the set of candidate attributes.
Attribute selection method, a procedure to determine the
splitting criterion that best partitions that the data 
tuples into individual classes. This criterion includes a 
splitting_attribute and either a splitting point or splitting subset.

Output:
 A Decision Tree

Method
create a node N;

if tuples in D are all of the same class, C then
   return N as leaf node labeled with class C;
   
if attribute_list is empty then
   return N as leaf node with labeled 
   with majority class in D;|| majority voting
   
apply attribute_selection_method(D, attribute_list) 
to find the best splitting_criterion;
label node N with splitting_criterion;

if splitting_attribute is discrete-valued and
   multiway splits allowed then  // no restricted to binary trees

attribute_list = splitting attribute; // remove splitting attribute
for each outcome j of splitting criterion

   // partition the tuples and grow subtrees for each partition
   let Dj be the set of data tuples in D satisfying outcome j; // a partition
   
   if Dj is empty then
      attach a leaf labeled with the majority 
      class in D to node N;
   else 
      attach the node returned by Generate 
      decision tree(Dj, attribute list) to node N;
   end for
return N;

Tỉa cây

Việc cắt tỉa cây được thực hiện để loại bỏ các bất thường trong dữ liệu huấn luyện do nhiễu hoặc các yếu tố ngoại lai. Các cây được cắt tỉa nhỏ hơn và ít phức tạp hơn.

Phương pháp cắt tỉa cây

Có hai cách cắt tỉa cây -

Pre-pruning - Cắt tỉa cây bằng cách tạm dừng thi công sớm.
Post-pruning - Cách tiếp cận này loại bỏ một cây con khỏi một cây đã phát triển đầy đủ.

Chi phí phức tạp

Độ phức tạp của chi phí được đo bằng hai tham số sau:

Số lượng lá trên cây và
Tỷ lệ lỗi của cây.