Дерево рішення

Методи побудови дерев рішень. 

 

Існуючі методи (усього їх кілька десятків), в принципі, можуть бути розділені на дві основні  групи. До першої групи відносяться  методи побудови строго-оптимального по заданому критерію якості дерева, до другої групи - методи побудови наближено-оптимального дерева.

Завдання  пошуку оптимального варіанта дерева можна віднести до задачі дискретного  програмування або вибору з кінцевого (але дуже великого) числа варіантів. Це випливає з того, що для кінцевої навчальної вибірки число варіантів  розгалуження (див. нижче) по кожній характеристиці звичайно.

У дискретному  програмуванні розглядаються три  основні види методів: повний перебір, метод динамічного програмування  і метод гілок і меж. Однак  ці методи, в додатку до дерев  рішень, як правило, є дуже трудомісткими, особливо при великій кількості  спостережень і характеристик. Тому ми обмежимося наближеними методами, до числа яких відносяться метод  послідовного розгалуження, метод усікання і рекурсивний метод.

Розглянемо  спочатку основні операції з деревами рішень. Методи побудови дерев будуть являти собою певну послідовність  цих операцій. 

 

  Операція розгалуження (поділу). 

 

Дана операція є основною при побудові дерева. Розглянемо деяку вершину дерева і довільну характеристику Xj. Нехай область визначення цієї характеристики розділена (розбита) на Lj підмножин (способи вибору таких підмножин розглянемо нижче). У разі кількісної характеристики ці підмножини являють собою набір подинтервалов розбиття, в разі якісної

характеристики - довільні підмножини значень, а в разі порядкової характеристики - підмножини, що включають сусідні  по порядку значення.

 

Зіставимо кожному з цих підмножин гілку дерева, що виходить з даної (батьківської) вершини і провідну в нову вершину-нащадок. Таким чином, вершина "розгалузилася" ("розділилася") на Lj нових вершин (рис. 5).

 

 

  

                    

                                                    

 

 

 

 

Мал.1 

 

 

Зауважимо, що для дихотомічних дерев Lj завжди дорівнює двом. Якщо Lj завжди дорівнює трьом, то такі дерева називають тернарного. Якщо Lj завжди дорівнює чотирьом, то отримаємо квадро-дерева.

 

Як отримати розбиття області визначення? Візьмемо безліч спостережень, відповідних даній  вершині і розглянемо значення характеристики Xj для цих спостережень.

  

 

 

  

 

 

                                                                    

Мал.2 

 

Нехай характеристика - кількісна. У цьому випадку визначаються межі - середини інтервалів між сусідніми  значеннями, і поділ проводиться  по цих межах (рис.6). Наприклад, для  прикладу на рис. 7 (значення характеристики для спостережень позначені через  «), у разі дихотомічного дерева, можна розглядати наступні варіанти поділу: Xj <0.5 або Xj> = 0.5, Xj <1.5 або Xj> = 1.5. Якщо характеристика - якісна, то варіанти розбиття виходять безпосередньо за значеннями характеристики, наприклад якщо Xj означає країну, то може бути отримано наступне розбиття: Xj 0 {Канада, Мексика, США} або Xj 0 {Аргентина, Бразилія}. 

 

   

 

 

Мал. 3

 

 

      При наявності великої кількості значень число можливих варіантів стає надто великим, тому для прискорення процесу побудови дерева розглядають не всі варіанти, а тільки деякі з них (наприклад, такі як Xj = «Канада» або Xj ≠ «Канада»).

У разі порядкової характеристики варіанти розбиття складаються  з сусідніх по порядку значень, наприклад  якщо Xj - військове звання, то поділ може бути таке: Xj0 [рядовий - старшина] або Xj0 [лейтенант - майор].

У деяких випадках (при малому числі спостережень) для якісних або порядкових характеристик  може трапитися так, що безліч значень  характеристик для спостережень, відповідних вершині, складає лише частину всій області визначення цієї характеристики. У цьому випадку  необхідно залишилися значення, за яким-небудь правилом приписати небудь з нових гілок. Це потрібно для  того, щоб при прогнозуванні для  об'єкта контрольної вибірки, у якого  зустрілося таке значення, визначити, до якої з гілок він відноситься. Наприклад, можна приписати дані значення тієї гілки, якій відповідає найбільше число спостережень. 

 

Операція  визначення перспективності подальшого розгалуження вершини (правило зупинки).  

 

Розглянемо  висячу вершину дерева, тобто вершину, з якої не виходять гілки, але не ясно, чи буде ця вершина листом або  відбудеться подальше розгалуження. Розглянемо підмножину спостережень, відповідне даній вершині. Вершина  відноситься до безперспективним для  подальшого розгалуження в двох випадках. По-перше, якщо ці спостереження однорідні, тобто в основному належать до одного класу (задача розпізнавання  образів, РО), або розкид значень  Y для них досить малий (задача регресійного аналізу, РА). До цього випадку відноситься і варіант, коли у спостережень збіглися значення всіх X-ів. По-друге, якщо число спостережень досить мало.

Вершина, безперспективна  для подальшого розгалуження, оголошується листом.

Для визначення перспективності можна задати наступні параметри: допустиму помилку для  вершини (задача РВ), допустиму дисперсію (задача РА), поріг на число спостережень.  

 

Операція  присвоювання рішення листу. 

 

Розглянемо довільний лист дерева. Цьому листу відповідає підмножина спостережень Data '. При вирішенні задачі розпізнавання образів листу привласнюється той клас, для якого кількість спостережень із Data 'максимально, в порівнянні з іншими класами. При вирішенні задачі регресійного аналізу рішення, присвоєне листу, дорівнює середньому значенню залежної характеристики Y для спостережень з Data '. 

 

Операція "розростання" вершини. 

 

Ця операція представляє собою послідовність  операцій розгалуження для кожної з  новоутворених вершин дерева. В результаті цієї операції дана вершина замінюється  деяким піддерево (тобто частиною повного  дерева, яка також має вигляд дерева (рис.8)). 

 

 

 

 

  

 

 

  

 

 

 

Мал.4 

 

Складність  поддерева обмежується деяким параметром. Детальніше один із способів розростання  буде описано нижче. 

 

Операція  усікання. 

 

Ця операція зворотна операції розростання, тобто  для даної вершини повністю відсікається відповідне піддерево, для якого  ця вершина є коренем (рис. 9). Вершина  потім оголошується листом і їй присвоюється рішення.

 

 

 

 

 

  

 

Мал.5 

 

Операція "зрощення" вершин або ("склеювання").  

 

Нехай вершина  розділилася на L нових вершин. Візьмемо яку-небудь пару цих вершин і об'єднаємо їх в одну вершину, яку з'єднаємо з батьківської вершиною гілкою (рис. 10). При цьому підмножини значень, відповідні зростаються вершин, об'єднуються.

 

 

 

  

 

 

Мал.6 

 

Для кількісних і порядкових характеристик допускається зрощення вершин, яким відповідають сусідні  подинтервали або підмножини значень  характеристик.