Оскільки всі об’єкти були заздалегідь віднесені до відомих нам класів, такий процес побудови дерева рішень називається навчанням із учителем (supervised learning). Процес навчання також називають індуктивним навчанням або індукцією дерев (tree induction).
На сьогодні існує значне число методів, що реалізують дерева рішень: CART, C4.5, NewId, ITrule, CHAID, CN2 і т. д. Але найбільше поширення і популярність дістали:
• C4.5 — метод побудови дерева рішень, де кількість нащадків у вузла є необмеженою. Метод не вміє працювати з неперервними цільовими змінними, тому вирішує тільки задачі класифікації;
• CART (Classification and Regression Tree) — метод побудови бінарного дерева рішень — дихотомічної класифікаційної моделі. Кожен вузол дерева при розбитті має тільки двох нащадків. Як видно з назви методу, він вирішує задачі класифікації і регресії.
Більшість з відомих методів є «жадібними методами». Якщо один раз був обраний атрибут, і за ним було зроблено розбиття на підмножини, то не можна повернутися назад і вибрати інший атрибут, який уможливив би краще розбиття. І тому на етапі побудови не можна визначити, чи дасть обраний атрибут, в остаточному підсумку, оптимальне розбиття.
При побудові дерев рішень особлива увага приділяється вибору критерію атрибута, за яким відбуватиметься розбиття, припинення навчання і відсікання гілок.
Правило вибору ознаки для розбиття. Для побудови дерева на кожному внутрішньому вузлі необхідно знайти таку умову (перевірку), яка б розбивала множину, асоційовану з цим вузлом, на підмножини. Як така перевірка має бути обраний один з атрибутів. Загальне правило для вибору атрибута можна сформулювати в такий спосіб: обраний атрибут має розбити множину так, щоб одержувані в підсумку підмножини складалися з об’єктів, що належать до одного класу, або були максимально наближені до цього, тобто кількість об’єктів з інших класів («домішок») у кожній з цих множин була якнайменшою. Відомі різні критерії.
— Теоретико-інформаційний критерій для вибору найбільш придатного атрибута запропонований Р. Куінленом (R. Quinlean) і використовується в методі C4.5 — удосконаленій версії методу ID3 (Iterative Dichotomizer): де Info(T) — ентропія множини T, а |T| — потужність множини; T — кількість прикладів у множині T.
Множини T
1 , T
2 ,...,T n , отримані при розбитті вихідної множини T за перевіркою X. Вибирається атрибут, що дає максимальне значення за критерієм Gain(X).
— Статистичний критерій — індекс Gini (на честь італійського економіста C. Gini)
— оцінює «відстань» між розподілами класів і використовується в методі CART, запропонованому Л. Брейманом (L. Breiman): () ? = ?= k j j pc
2
1Gini, де c — поточний вузол, а p j — імовірність класу j у вузлі c.
1
Правило зупинки визначає, чи розбивати далі вузол або позначити його як лист. На додаток до основного методу побудови дерев рішень були запропоновані такі правила:
— Рання зупинка (prepruning) — використання статистичних методів для оцінки доцільності подальшого розбиття. Рання зупинка процесу побудови приваблива в плані економії часу навчання, але цей підхід дозволяє будувати менш точні класифікаційні моделі й тому рання зупинка вкрай небажана. Рекомендується замість зупинки використовувати відсікання.
— Обмеження глибини дерева: подальшу побудову зупиняють, якщо розбиття веде до дерева з глибиною, яка перевищує задане значення.
— Розбиття має бути нетривіальним, тобто вузли, що вийшли в результаті, мають містити не менше заданої кількості прикладів.
Цей список евристичних правил можна продовжити, але на сьогодні не існує правила, яке б мало велику практичну цінність. До даного питання варто підходити обережно, оскільки більшість цих правил є застосовними лише в якихось окремих випадках.
Правило відсікання визначає, яким чином гілки дерева мають відтинатися.
Оскільки бажано мати дерево, що складається з малої кількості вузлів, яким би відповідала велика кількість об’єктів з навчаючої вибірки, виникає задача побудови всіх можливих дерев, що відповідають навчаючій множині, і вибору з них дерева з найменшою глибиною. На жаль, ця задача є NP-повною, що було показано Л. Хайфілем (L. Hyafill) та Р. Ривестом (R. Rivest), і, як відомо, цей клас задач не має ефективних методів розв’язання. Для вирішення даної проблеми часто застосовується відсікання гілок (pruning).
Під точністю розпізнавання для дерева рішень розуміється відношення правильно класифікованих об’єктів при навчанні до загальної кількості об’єктів з навчаючої множини, а під помилкою — кількість неправильно класифікованих. Припустимо, що нам відомий спосіб оцінки помилки для дерева, гілок і листків. Тоді можна використовувати таке просте правило: 1) побудувати дерево; 2) відітнути або замінити піддеревом ті гілки, що не приведуть до зростання помилки.
На відміну від процесу побудови, відтинання гілок відбувається знизу вгору, рухаючись з листків дерева, відзначаючи вузли як листки, або заміняючи їх піддеревом. Хоча відтинання не є панацеєю, але в більшості практичних задач дає гарні результати, що свідчить про правомірність використання подібної методики. Іноді навіть усічені дерева можуть бути усе ще складними для сприйняття. У такому разі можна вдатися до методики витягу правил з дерева з подальшим створенням наборів правил, що описують класи. Для витягу правил необхідно досліджувати всі шляхи від кореня до кожного листка дерева. Кожен такий шлях надасть правило, де умовами будуть перевірки з вузлів, що трапилися на шляху.
Метод C4.5 передбачає такі вимоги до структури і значень даних. Дані, необхідні для роботи методу, мають бути подані у вигляді плоскої таблиці. Вся інформація про об’єкти із ПРГ має описуватися у вигляді кінцевого набору ознак. Кожний атрибут повинен мати дискретне або числове значення.
Самі атрибути не слід змінюватися від прикладу до прикладу і кількість атрибутів має бути фіксованою для всіх прикладів. Кожен приклад має бути асоційований з конкретним класом, тобто один з атрибутів має бути обраний як мітка класу.
Класи мають бути дискретними, тобто мати кінцеве число значень. Кожен приклад має однозначно належати до конкретного класу. Випадки, коли приклади належать до класу з імовірнісними оцінками, виключаються. Кількість класів має бути значно меншою від кількості прикладів.
Метод побудови дерева. Нехай нам задана множина прикладів T, де кожний елемент цієї множини описується m атрибутами та мітка класу набуває значення C
1 , C
2 ,...,C k .
Наше завдання буде полягати в побудові ієрархічної класифікаційної моделі у вигляді дерева із множини прикладів T.
Процес побудови дерева відбуватиметься зверху вниз. Спочатку створюється корінь дерева, потім нащадки кореня і т. д. На першому кроці ми маємо порожнє дерево (є тільки корінь) і вихідну
Розглянемо докладніше критерій вибору атрибута, за яким має піти розгалуження. Очевидно, що в нашому розпорядженні m (за числом атрибутів) можливих варіантів, з яких ми повинні обрати найбільш придатний. Деякі методи виключають повторне використання атрибута при побудові дерева, але в нашому випадку ми таких обмежень накладати не будемо. Будь-який з атрибутів можна використовувати необмежену кількість разів при побудові дерева.
Нехай ми маємо перевірку X (як перевірка може бути обраний будь-який атрибут), що приймає n значень A
1 , A
2 ,...,A n . Тоді розбиття T за перевіркою X дасть нам підмножини T
1 , T
2 ,...,T n , при X рівному відповідно A
1 , A
2 ,...,A n . Єдина доступна інформація — яким чином класи розподілені в множині T та її підмножинах, одержуваних при розбитті за X. Це й використовують для визначення критерію.
Нехай freq(C j ,S) — кількість прикладів з деякої множини S, що належать до того самого класу C j . Тоді імовірно, що випадково обраний приклад із множини S буде належати до класу C j : P = freq(C j ,S) / |S|.
Відповідно до теорії інформації, кількість інформації, що міститься в повідомленні, залежить від їїімовірності log
2 (P –1 ). Оскільки ми використовуємо логарифм із двійковою основою, то цей вираз дає кількісну оцінку в бітах.
Вираз: () ()() ? ? ? ? ? ? ? ? ?= ? = T TC T TC T j k j j ,freg log ,freg Info
2
1 дає оцінку середньої кількості інформації, необхідної для визначення класу прикладу із множини T. У термінології теорії інформації цей вираз називається ентропією множини T.
множину T (асоційовану з коренем). Потрібно розбити вихідну множину на підмножини. Це можна зробити, вибравши один з атрибутів як перевірку. Тоді в результаті розбиття виходять n (по числу значень атрибута) підмножин і, відповідно, створюються n нащадків кореня, кожному з яких співставлено у відповідність свою підмножину, отриману при розбитті множини T. Потім ця процедура рекурсивно застосовується до всіх підмножин (нащадків кореня) і т. д.
Ту саму оцінку, але тільки вже після розбиття множини T за X, дає вираз:
Тоді критерієм для вибору атрибута буде така формула:
Цей критерій обчислюється для всіх атрибутів. Вибирається атрибут, що максимізує даний вираз. Цей атрибут буде перевіркою в поточному вузлі дерева, а потім за цим атрибутом здійснюється подальша побудова дерева. Тобто у вузлі буде перевірятися значення за цим атрибутом і подальший рух по дереву буде здійснюватися залежно від отриманої відповіді.
Таке саме міркування можна застосувати до отриманих підмножин T
1 , T
2 , ..., T n і продовжити рекурсивно процес побудови дерева доти, поки у вузлі не виявляться приклади з одного класу.
Якщо в процесі роботи методу отримано вузол, асоційований з порожньою множиною (тобто жоден приклад не потрапив у даний вузол), то він позначається як лист, і як рішення листка обирається клас, що найбільш часто трапляється у безпосереднього предка даного листка. Із властивостей ентропії нам відомо, що максимально можливе значення ентропії досягається тоді, коли всі його повідомлення є рівноймовірними. У нашому випадку ентропія Info X (T) досягає свого максимуму, коли частота появи класів у прикладах множини T є рівноймовірною. Нам же слід обрати такий атрибут, щоб при розбитті за ним один із класів мав найбільшу імовірність появи. Це можливо в тому випадку, коли ентропія Info X (T) буде мати мінімальне значення і, відповідно, критерій Gain(X) досягне свого максимуму.
У випадку числових атрибутів варто обрати деякий поріг, з яким мають порівнюватися всі значення атрибута. Нехай числовий атрибут має кінцеве число значень. Позначимо їх {v
1 , v
2 ,...,v n }. Попередньо відсортуємо всі значення. Тоді будь-яке
ii+1 множини: ті, котрі лежать ліворуч від цього значення {v
1 , v
2 , ..., v i }, і ті, що праворуч {v i+1 , v i+2 , ..., v n }. Як поріг можна вибрати середнє між значеннями v i і v i+1 : TH i = 0,5(v i + v i+1 ).
Отже, ми істотно спростили задачу знаходження порога, і привели до розгляду усього n – 1 потенційних граничних значеньi i+1 i+2 n реднє між значеннями v i і v i+1 : TH i = 0,5(v i + v i+1 ).
Отже, ми істотно спростили задачу знаходження порога, і привели до розгляду усього n – 1 потенційних граничних значеньii+1 iii+1
Отже, ми істотно спростили задачу знаходження порога, і привели до розгляду усього n – 1 потенційних граничних значеньреднє між значеннями v i і v i+1 : TH i = 0,5(v i + v i+1 ).
Отже, ми істотно спростили задачу знаходження порога, і привели до розгляду усього n – 1 потенційних граничних значеньзначення, що лежить між v i і v i+1 , поділяє всі приклади на дві множини: ті, котрі лежать ліворуч від цього значення {v
1 , v
2 , ..., v i }, і ті, що праворуч {v i+1 , v i+2 , ..., v n }. Як поріг можна вибрати середнє між значеннями v i і v i+1 : TH i = 0,5(v i + v i+1 ).
Отже, ми істотно спростили задачу знаходження порога, і привели до розгляду усього n – 1 потенційних граничних значень
1 , TH
2 ,..., TH n–1 . Послідовно для всіх потенційних граничних значень установлюють значення критерію Gain(TH i ) і серед них вибирається те, що дає максимальне значення критерію. Далі це значення порівнюють зі значеннями критерію, підрахованими для інших атрибутів. Якщо з’ясується, що серед усіх атрибутів даний числовий атрибут має максимальне значення критерію, то як перевірка обирається саме він.
Слід зазначити, що всі числові тести є бінарними, тобто поділяють вузол дерева на дві гілки. CART (Classification And Regression Tree
— дерево класифікації і регресії) — метод бінарного дерева рішень, призначений для розв’язання задач класифікації і регресії. Уперше опубліковано 1984 року Л. Брейманом та ін.
Основними відмінностями методу CART від методів сімейства ID3 є: бінарне подання дерева рішень; функція оцінки якості розбиття; механізм відсікання дерева; метод обробки пропущених значень; побудова дерев регресії.
Бінарне подання дерева рішень — у методі CART кожен вузол дерева рішень має двох нащадків. На кожному кроці побудови дерева правило, сформоване у вузлі, поділяє задану множину прикладів (навчаючу вибірку) на дві частини: частину, в якій виконується правило (правий нащадок — right) і частину, в якій правило не виконується (лівий нащадок — left). Для вибору оптимального правила використовується функція оцінювання якості розбиття.
Кожен вузол (структура або клас) повинен мати посилання на двох нащадків Left і Right
— аналогічні структури. Також вузол повинен містити ідентифікатор правила, певним чином описувати праву частину правила, містити інформацію про кількість або відношення прикладів кожного класу навчаючої вибірки, що пройшла через вузол, і мати ознаку термінального вузла — листка.
Функція оцінювання якості розбиття — критерій, що дозволяє оцінити якість поточного розбиття.
Навчання дерева рішень належить до класу навчання з учителем, тобто навчаюча і тестова вибірки містять класифікований набір прикладів. Оцінна функція, використовувана методом CART, базується на інтуїтивній ідеї зменшення невизначеності у вузлі.
У методі CART ідея невизначеності формалізована в індексі Gini(T), де Т — набір даних, що містить дані n класів.
TH
Якщо набір Т розбивається на дві частини Т
1 і Т
2 з числом прикладів у кожній N
1 і N
2 відповідно, тоді показник якості розбиття буде дорівнювати: ()()()
2 2
1 split GiniGiniGiniT N N T N N T+=.
Найкращим вважається те розбиття, для якого Gini split (T) є мінімальним.
Позначимо N — число прикладів у вузлі — предка, L, R — число прикладів відповідно в лівому і правому нащадках, l i та r i — число екземплярів i-го класу в лівому та правому нащадках, відповідно. Тоді якість розбиття оцінюється за формулою: .min11Gini
Щоб зменшити обсяг обчислень, формулу можна перетворити так: .max
У результаті, кращим буде те розбиття, для якого величина G split є максимальною.
Правила розбиття — визначають принцип прийняття рішень у вузлах дерева рішень.
Вектор предикторних змінних, подаваний на вхід дерева, може містити як числові (порядкові), так і категоріальні змінні. У будь-якому випадку в кожному вузлі розбиття відбувається тільки за однією змінною. Якщо змінна числового типу, то у вузлі формується правило виду x i ? c, де c — деякий поріг, що найчастіше вибирається як середнє арифметичне двох сусідніх упорядкованих значень змінної x i навчаючої вибірки. Якщо змінна категоріального типу, то у вузлі формується правило x i ? V(x i ), де V(x i ) — деяка непорожня підмножина множини значень змінної x i у навчаючій вибірці. Отже, для n значень числового атрибута метод порівнює n – 1 розбиттів, а для категоріального (2 n–1 – 1). На кожному кроці побудови дерева метод послідовно порівнює всі можливі розбиття для всіх атрибутів і вибирає найкращий атрибут і найкраще розбиття для нього.
Нехай джерело даних, необхідних для роботи методу, подане плоскою таблицею. Кожен рядок таблиці описує один приклад навчаючої/тестової вибірки.
Кожен крок побудови дерева фактично складається із сукупності трьох трудомістких операцій.
1. Сортування джерела даних за стовпцем є необхідним для обчислення порога, коли розглянутий у поточний момент часу атрибут має числовий тип. На кожному кроці побудови дерева число сортувань буде як мінімум дорівнювати кількості атрибутів числового типу.
2. Поділ джерела даних. Після того, як знайдено найкраще розбиття, необхідно розділити джерело даних відповідно до правила формованого вузла і рекурсивно викликати процедуру побудови для двох половинок джерела даних.
Обидві ці операції пов’язані (якщо діяти прямо) з переміщенням значних обсягів пам’яті. Тут навмисно джерело даних не називається таблицею, оскільки можна істотно знизити часові витрати на побудову дерева, якщо використовувати індексоване джерело даних. Звертання до даних у такому джерелі відбувається не прямо, а за допомогою логічних індексів рядків даних. Сортувати і розділяти таке джерело можна з мінімальною втратою продуктивності.
3. Обчислення індексів G split для всіх можливих розбиттів — операція, що займає 60—80 % часу виконання програми. Якщо є n числових атрибутів і m прикладів у вибірці, то виходить таблиця n ? (m – 1) — індексів, що займає великий обсяг пам’яті. Цього можна уникнути, якщо використовувати один стовпець для поточного атрибута й один рядок для кращих (максимальних) індексів для всіх атрибутів. Можна й зовсім використовувати тільки кілька числових значень, одержавши швидкий код, але такий, що погано читається. Значно збільшити продуктивність можна, якщо використовувати L = N – R, l i = n i – r i , а l i та r i змінюються завжди і тільки на одиницю при переході на наступний рядок для поточного атрибута. Тобто підрахунок числа класів, а це основна операція, буде виконуватися швидко, якщо знати число екземплярів кожного класу всього в таблиці та при переході на новий рядок таблиці змінювати на одиницю тільки число екземплярів одного класу — класу поточного прикладу.
Усі можливі розбиття для категоріальних атрибутів зручно подавати за аналогією з двійковим поданням числа. Якщо атрибут має n унікальних значень, то буде 2 n розбиттів. Перше (де всі нулі) і останнє (усі одиниці) нас не цікавлять, одержуємо 2 n – 2. І оскільки порядок множин тут теж неважливий, дістаємо (2 n – 2)/2 або (2 n–1 – 1) перших (з одиниці) двійкових подань. Якщо {A, B, C, D, E} — усі можливі значення деякого атрибута X, то для по-
жуємо правило X in {C, E} для правої гілки та [ not {0, 0, 1, 0, 1} = = {1, 1, 0, 1, 0} = X in {A, B, D} ] для лівої гілки.
Часто значення атрибута категоріального типу подані в базі як строкові значення. У такому разі швидше і зручніше створити кеш усіх значень атрибута і працювати не зі значеннями, а з індексами в кеші.
Механізм відсікання дерева (minimal cost-complexity tree pruning) — найбільш серйозна відмінність методу CART від інших методів побудови дерева. CART розглядає відсікання як одержання компромісу між двома проблемами: одержанням дерева оптимального розміру й одержанням точної оцінки імовірності помилкової класифікації.
Основна проблема відсікання — велика кількість усіх можливих відсічених піддерев для одного дерева. Більш точно, якщо бінарне дерево має |T| листків, тоді існує ~[1,5028369
|T| ] відсічених піддерев. І якщо дерево має хоча б 1000 листків, тоді число відсічених піддерев стає просто величезним.
Базова ідея методу — не розглядати всі можливі піддерева, обмежуючись тільки кращими представниками відповідно до наведеної нижче оцінки.
Позначимо |T| — число листків дерева, R(T) — імовірність помилки класифікації дерева, що дорівнює відношенню числа неправильно класифікованих прикладів до числа прикладів у навчаючій вибірці. Визначимо повну вартість (оцінку / показник витрат — складність) дерева Т як: C ? (T) = R(T) + ?|T|, де ? — деякий параметр, що змінюється від 0 до + ?. Повна вартість дерева складається з двох компонентів — помилки класифікації дерева і штрафу за його складність. Якщо помилка класифікації дерева є незмінною, тоді зі збільшенням ? повна вартість дерева буде збільшуватися. Тоді залежно від ? менш гіллясте дерево, що дає велику помилку класифікації, може «коштувати» менше, ніж те, що дає меншу помилку, але є більш гіллястим.
Визначимо T max — максимальне за розміром дерево, що має бути «обрізане». Якщо ми зафіксуємо значення ?, тоді існує найменше мінімізоване піддерево ?, що задовольняє таким умовам. ()()() TCTC TT ? ? ? =? max min.
2. Якщо C ? (T) = C ? (T(?)), то T(?) ? T.
Перша умова вказує на те, що не існує такого піддерева дерева T max , що мало б меншу вартість, ніж Т(?) при цьому значенні ?. Друга умова вказує, що коли існує більше одного під-= {1, 1, 0, 1, 0} = X in {A, B, D} ] для лівої гілки.
Часто значення атрибута категоріального типу подані в базі як строкові значення. У такому разі швидше і зручніше створити кеш усіх значень атрибута і працювати не зі значеннями, а з індексами в кеші.
Механізм відсікання дерева (minimal cost-complexity tree pruning) — найбільш серйозна відмінність методу CART від інших методів побудови дерева. CART розглядає відсікання як одержання компромісу між двома проблемами: одержанням дерева оптимального розміру й одержанням точної оцінки імовірності помилкової класифікації.
Основна проблема відсікання — велика кількість усіх можливих відсічених піддерев для одного дерева. Більш точно, якщо бінарне дерево має |T| листків, тоді існує ~[1,5028369
|T| ] відсічених піддерев. І якщо дерево має хоча б 1000 листків, тоді число відсічених піддерев стає просто величезним.
Базова ідея методу — не розглядати всі можливі піддерева, обмежуючись тільки кращими представниками відповідно до наведеної нижче оцінки.
Позначимо |T| — число листків дерева, R(T) — імовірність помилки класифікації дерева, що дорівнює відношенню числа неправильно класифікованих прикладів до числа прикладів у навчаючій вибірці. Визначимо повну вартість (оцінку / показник витрат — складність) дерева Т як: C ? (T) = R(T) + ?|T|, де ? — деякий параметр, що змінюється від 0 до + ?. Повна вартість дерева складається з двох компонентів — помилки класифікації дерева і штрафу за його складність. Якщо помилка класифікації дерева є незмінною, тоді зі збільшенням ? повна вартість дерева буде збільшуватися. Тоді залежно від ? менш гіллясте дерево, що дає велику помилку класифікації, може «коштувати» менше, ніж те, що дає меншу помилку, але є більш гіллястим.
Визначимо T max — максимальне за розміром дерево, що має бути «обрізане». Якщо ми зафіксуємо значення ?, тоді існує найменше мінімізоване піддерево ?, що задовольняє таким умовам. ()()() TCTC TT ? ? ? =? max min.
2. Якщо C ? (T) = C ? (T(?)), то T(?) ? T.
Перша умова вказує на те, що не існує такого піддерева дерева T max , що мало б меншу вартість, ніж Т(?) при цьому значенні ?. Друга умова вказує, що коли існує більше одного під-витрат — складність) дерева Т як: C ? (T) = R(T) + ?|T|, де ? — деякий параметр, що змінюється від 0 до + ?. Повна вартість дерева складається з двох компонентів — помилки класифікації дерева і штрафу за його складність. Якщо помилка класифікації дерева є незмінною, тоді зі збільшенням ? повна вартість дерева буде збільшуватися. Тоді залежно від ? менш гіллясте дерево, що дає велику помилку класифікації, може «коштувати» менше, ніж те, що дає меншу помилку, але є більш гіллястим.
Визначимо T max — максимальне за розміром дерево, що має бути «обрізане». Якщо ми зафіксуємо значення ?, тоді існує найменше мінімізоване піддерево ?, що задовольняє таким умовам. ()()() TCTC TT ? ? ? =? max min.
2. Якщо C ? (T) = C ? (T(?)), то T(?) ? T.
Перша умова вказує на те, що не існує такого піддерева дерева T max , що мало б меншу вартість, ніж Т(?) при цьому значенні ?. Друга умова вказує, що коли існує більше одного під-який параметр, що змінюється від 0 до + ?. Повна вартість дерева складається з двох компонентів — помилки класифікації дерева і штрафу за його складність. Якщо помилка класифікації дерева є незмінною, тоді зі збільшенням ? повна вартість дерева буде збільшуватися. Тоді залежно від ? менш гіллясте дерево, що дає велику помилку класифікації, може «коштувати» менше, ніж те, що дає меншу помилку, але є більш гіллястим.
Визначимо T max — максимальне за розміром дерево, що має бути «обрізане». Якщо ми зафіксуємо значення ?, тоді існує найменше мінімізоване піддерево ?, що задовольняє таким умовам. ()()() TCTC TT ? ? ? =? max min.
2. Якщо C ? (T) = C ? (T(?)), то T(?) ? T.
Перша умова вказує на те, що не існує такого піддерева дерева T max , що мало б меншу вартість, ніж Т(?) при цьому значенні ?. Друга умова вказує, що коли існує більше одного під-
1. TCTC TT ? ? ? =? max min.
2. Якщо C ? (T) = C ? (T(?)), то T(?) ? T.
Перша умова вказує на те, що не існує такого піддерева дерева T max , що мало б меншу вартість, ніж Т(?) при цьому значенні ?. Друга умова вказує, що коли існує більше одного під-
2. Якщо C ? (T) = C ? (T(?)), то T(?) T.
Перша умова вказує на те, що не існує такого піддерева дерева T max , що мало б меншу вартість, ніж Т(?) при цьому значенні ?. Друга умова вказує, що коли існує більше одного під-жуємо правило X in {C, E} для правої гілки та [ not {0, 0, 1, 0, 1} = = {1, 1, 0, 1, 0} = X in {A, B, D} ] для лівої гілки.
Часто значення атрибута категоріального типу подані в базі як строкові значення. У такому разі швидше і зручніше створити кеш усіх значень атрибута і працювати не зі значеннями, а з індексами в кеші.
Механізм відсікання дерева (minimal cost-complexity tree pruning) — найбільш серйозна відмінність методу CART від інших методів побудови дерева. CART розглядає відсікання як одержання компромісу між двома проблемами: одержанням дерева оптимального розміру й одержанням точної оцінки імовірності помилкової класифікації.
Основна проблема відсікання — велика кількість усіх можливих відсічених піддерев для одного дерева. Більш точно, якщо бінарне дерево має |T| листків, тоді існує ~[1,5028369
|T| ] відсічених піддерев. І якщо дерево має хоча б 1000 листків, тоді число відсічених піддерев стає просто величезним.
Базова ідея методу — не розглядати всі можливі піддерева, обмежуючись тільки кращими представниками відповідно до наведеної нижче оцінки.
Позначимо |T| — число листків дерева, R(T) — імовірність помилки класифікації дерева, що дорівнює відношенню числа неправильно класифікованих прикладів до числа прикладів у навчаючій вибірці. Визначимо повну вартість (оцінку / показник витрат — складність) дерева Т як: C ? (T) = R(T) + ?|T|, де ? — деякий параметр, що змінюється від 0 до + ?. Повна вартість дерева складається з двох компонентів — помилки класифікації дерева і штрафу за його складність. Якщо помилка класифікації дерева є незмінною, тоді зі збільшенням ? повна вартість дерева буде збільшуватися. Тоді залежно від ? менш гіллясте дерево, що дає велику помилку класифікації, може «коштувати» менше, ніж те, що дає меншу помилку, але є більш гіллястим.
