데이터 마이닝-의사 결정 트리 유도

의사 결정 트리는 루트 노드, 분기 및 리프 노드를 포함하는 구조입니다. 각 내부 노드는 속성에 대한 테스트를 나타내고 각 분기는 테스트 결과를 나타내며 각 리프 노드에는 클래스 레이블이 있습니다. 트리의 최상위 노드는 루트 노드입니다.

다음 의사 결정 트리는 회사의 고객이 컴퓨터를 구매할 가능성이 있는지 여부를 나타내는 buy_computer 개념에 대한 것입니다. 각 내부 노드는 특성에 대한 테스트를 나타냅니다. 각 리프 노드는 클래스를 나타냅니다.

의사 결정 트리를 갖는 이점은 다음과 같습니다.

도메인 지식이 필요하지 않습니다.
이해하기 쉽습니다.
의사 결정 트리의 학습 및 분류 단계는 간단하고 빠릅니다.

의사 결정 트리 유도 알고리즘

1980 년에 J. Ross Quinlan이라는 이름의 기계 연구원이 ID3 (반복 이분법)이라는 의사 결정 트리 알고리즘을 개발했습니다. 나중에 그는 ID3의 후속 제품인 C4.5를 발표했습니다. ID3와 C4.5는 탐욕스러운 접근 방식을 채택합니다. 이 알고리즘에는 역 추적이 없습니다. 나무는 하향식 반복 분할 및 정복 방식으로 구성됩니다.

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;