Учебники

Интеллектуальный анализ данных — индукция дерева решений

Июнь 24, 2018

Дерево решений — это структура, которая включает в себя корневой узел, ветви и конечные узлы. Каждый внутренний узел обозначает тест для атрибута, каждая ветвь обозначает результат теста, а каждый конечный узел содержит метку класса. Самым верхним узлом в дереве является корневой узел.

Следующее дерево решений относится к понятию buy_computer, которое указывает, может ли клиент в компании купить компьютер или нет. Каждый внутренний узел представляет собой тест для атрибута. Каждый листовой узел представляет класс.

Древо решений

Преимущества наличия дерева решений следующие:

  • Не требует никаких знаний в предметной области.
  • Это легко понять.
  • Этапы обучения и классификации дерева решений просты и быстры.

Алгоритм индукции дерева решений

Исследователь машин по имени Дж. Росс Куинлан в 1980 году разработал алгоритм дерева решений, известный как ID3 (Итеративный дихотомайзер). Позже он представил C4.5, который был преемником ID3. 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;

Обрезка деревьев

Обрезка деревьев выполняется для устранения аномалий в данных тренировки из-за шума или выбросов. Обрезанные деревья меньше и менее сложны.

Подходы для обрезки деревьев

Есть два подхода, чтобы обрезать дерево —

  • Предварительная обрезка — дерево обрезается за счет преждевременного прекращения строительства.

  • Постобрезка — этот подход удаляет поддерево из полностью выросшего дерева.

Предварительная обрезка — дерево обрезается за счет преждевременного прекращения строительства.

Постобрезка — этот подход удаляет поддерево из полностью выросшего дерева.

Стоимость Сложность

Сложность стоимости измеряется следующими двумя параметрами:

70
Share: