Як побудувати класифікатор дерева рішень з нуля

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

Хорошим прикладом є Клівлендське дослідження захворювань серця, де кожен рядок — це пацієнт, а останній стовпець — це те, що ми хочемо передбачити:

Останній стовпець — відтінений вище — містить спостережувану подію: у цього пацієнта виявилося захворювання серця, а у іншого — ні. Цей стовпець називається міткою; кожен стовпець перед ним описує випадок, і лише цей говорить про те, як завершився випадок. Те, що ми хочемо дізнатися, — це зв’язок між ними — від випадків, коли мітка вже відома, щоб її можна було застосувати до випадків, де вона невідома. Коли мітка є категорією, як тут, це завдання класифікації.

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

На табличних даних виходить два завдання: класифікація, де відповідь — категорія, і регресія, де це число — зарплата, ціна. Дерево рішень обробляє обидва. Ця стаття створює класифікатор; наведіть той самий код на числову ціль, замініть міру домішок на дисперсію цієї цілі, а мітка аркуша враховує їхнє середнє значення, і ви отримаєте регресійну модель, яка передбачає число — більше нічого в коді не змінюється, хоча багато про результуючу модель змінюється, що є предметом супутня стаття.

Підвищення є темою наступної статті. Це зосереджено на тій частині, яку вона повторює сотні разів: як єдине дерево рішень будується з таблиці рядків — звідки беруться запитання, як одне з них вибирається над іншими та коли припиняється поділ. Ми пишемо його на чистому Python, без NumPy і scikit-learn, у п’яти рядках, достатньо малих, щоб перевірити кожне число вручну.

Завантажте повний приклад Python і запустіть python3 heart_tree.py.

Два типи вузлів і області, які вони вирізають

Ми працюватимемо з п’ятьма пацієнтами з Клівлендське дослідження захворювань серця. Повна таблиця містить 303 пацієнтів і тринадцять ознак (прогнозуючих ознак), але ми будемо використовувати лише п’ять рядків і дві ознаки, а також мітку:

training_data = [
    ["normal", 0, "No"],
    ["fixed", 0, "Yes"],
    ["reversable", 2, "Yes"],
    ["reversable", 1, "Yes"],
    ["fixed", 0, "No"],
]

Враховуючи результати стрес-тесту пацієнта та кількість судин, дерево має передбачити, чи є у цього пацієнта захворювання серця — тому варто знати, що записують ці два стовпці.

stress_test (Thal) записує результат тесту на талій: нормальний, фіксований дефект або оборотний дефект. Ми зберігаємо вихідне написання reversable у коді. vessels (Ca) підраховує великі судини, від 0 до 3, забарвлені при рентгеноскопії; це не підрахунок хворих судин. Ці визначення взято з документації набору даних UCI.

Ми візьмемо ці п’ять рядків і розділимо їх на менші й менші групи, використовуючи функції та їхні значення, щоб вирішити, до якої групи належить кожен рядок. Послідовність поділів виглядає як діаграма розгалуження, звідки й походить назва «дерево».

На цій діаграмі є два типи вузлів.

Ромби є вузлами прийняття рішень. Кожен містить запитання «так/ні» та надсилає рядок униз до гілки True або False. Наше дерево у стилі CART завжди ділиться на двох дітей; інші алгоритми дерева можуть використовувати більше гілок.

Коробки листочки. Кожен зберігає кількість міток навчальних рядків, які досягли його: Yes: 2, Yes: 1, No: 1 або No: 1. Поділ на загальну суму дає оцінки частоти класу 100% Так, 50/50 і 100% Ні. Ці крихітні зразки не встановлюють ймовірність захворювання для нового пацієнта.

Вузли прийняття рішень направляють рядки до листків, розділяючи вхідний простір. Для числових функцій поріг розрізає вздовж однієї осі. На малюнку нижче використовується окремий синтетичний набір даних для ілюстрації граничних форм: пряма лінія, плавна крива у стилі нейронної мережі та розбиття дерев є схематичними; панель k-найближчого сусіда обчислюється з нанесених точок.

Отже, що насправді знадобиться, щоб побудувати один із них? Нам знадобляться дві речі.

• Спосіб згенерувати запитання кандидатів із таблиці, оскільки дерево має їх звідкись отримувати.
• Спосіб оцінки цих кандидатів, щоб можна було вибрати найкращого — вузол прийняття рішень містить одне запитання і не більше.

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

Від рядків до питань

Створюйте кандидати, поєднуючи кожну функцію з кожним окремим значенням, яке вона приймає в поточних рядках. Категоричне правило перевіряє рівність, наприклад stress_test == fixed. Числове правило перевіряє порогове значення, наприклад vessels >= 1, яке є вірним для пунктів 1, 2 і 3.

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

Наша реалізація тестує одну функцію за раз і використовує спостережувані значення як числові порогові значення. Це спрощення, а не вимога CART: scikit-learn використовує середини між сусідніми окремими значеннями. Обидва варіанти пропонують однакові навчальні розділи, але можуть по-різному направляти нове значення між двома спостереженнями. Категоричні розбиття CART також можуть тестувати підмножини категорій; наш тестує одну категорію проти решти.

Ці шість — це все, що може задати це дерево — і не всі з них потрапляють у готове дерево. Більшість кандидатів перевіряють, оцінюють і відхиляють; тут лише два виживають, щоб стати питаннями в дереві, яке ми збираємося побудувати, тоді як інші чотири оцінюються та відкидаються. І список є кінцевим — ніколи не перевищує кількість різних значень у таблиці — тому на наступному кроці можна просто спробувати кожне з них.

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

FEATURES = ["stress_test", "vessels", "disease"]

class Rule:
    """One yes/no test: a column, and the value it is compared against."""

    def __init__(self, column, value):
        self.column = column
        self.value = value

    def holds(self, row):
        observed = row[self.column]
        if isinstance(self.value, (int, float)):
            return observed >= self.value     # numeric: threshold
        return observed == self.value         # categorical: equality

    def __repr__(self):
        operator = ">=" if isinstance(self.value, (int, float)) else "=="
        return f"Is {FEATURES[self.column]} {operator} {self.value}?"

Є кілька способів реалізації такої відповідної логіки. Наша перевірка isinstance всередині holds, і саме тому це дерево обробляє стовпець тексту та стовпець чисел поруч без попередньої обробки взагалі. Не всі бібліотеки йдуть цим шляхом.

Scikit-learn потребує числового введення. Для невпорядкованої функції, такої як stress_test, одноразове кодування зберігає категорії без накладення порядку:

Потім дерево запитує is_fixed >= 0.5, де наше запитує stress_test == fixed — той самий розкол, розподілений на три стовпці. 0,5 сам по собі не має сенсу: стовпець містить лише 0 і 1, тому будь-яке розрізання між ними розділяє ті самі рядки, і sklearn розміщує свої порогові значення в середині двох суміжних значень. Стовпець із чотирма категоріями просто стане чотирма такими стовпцями 0/1, у кожному з яких все ще запитуватимуть приблизно 0,5 — кодування зростає вбік, і кожне запитання залишається тестом «так/ні» на одному значенні.

Натомість LightGBM ділиться на підмножини: він перевіряє групу категорій одночасно, що все ще є одним питанням щодо одного стовпця — різниця полягає в тому, що значення, яке перевіряється, є набором, а не окремою категорією:

ours:    Is stress_test == fixed?
theirs:  Is stress_test in {normal, reversable}?

LightGBM і XGBoost підтримують категоріальний розподіл, використовуючи впорядкування статистики категорій для пошуку груп кандидатів. CatBoost використовує впорядковану цільову статистику для багатьох категоріальних функцій і одноразове кодування для деяких функцій з низькою кардинальністю; його лікування залежить від конфігурації. Див. документацію CatBoost.

Вимірювання різноманітності набору даних

Щоб вибрати поділ, ми спочатку вимірюємо, наскільки змішані мітки з домішкою Джіні. Потім ми обчислюємо зменшення домішок, зважених за розміром. Код називає це посиленням; точніше, приріст інформації зазвичай означає відповідне зменшення ентропії.

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

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

А тепер припустімо, що ми не знаємо складу жодного набору — ні підрахунків, ні списку видів, лише можливість простягнути руку та щось витягти. Чи можемо ми поставити цифру до різноманітності?

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

На малюнку показана одна ілюстративна послідовність із десяти пар для кожного набору:

Чотири з пар лівого набору містять два різних види; сім із правого набору роблять. Розділіть на кількість розіграшів, і ви отримаєте оцінку — капелюх на $\hat{d}$ позначає значення, оцінене на основі вибірки, на відміну від обчисленого на основі цілого населення:

Більша частка невідповідностей свідчить про більшу різноманітність. Більш незалежні пари, як правило, покращують оцінку, але десять або навіть сотня пар не гарантують точного значення.

Загалом, однак, вам взагалі не потрібно робити вибірку: коли ви знаєте, що містить набір, невелика теорія ймовірності безпосередньо дає вам це точне значення. Обчисліть ймовірність того, що два вибори погодяться, а потім відніміть його від 1.

Візьміть лівий комплект. Сім із десяти елементів є синіми квадратами, тому один вибір є квадратом із ймовірністю 0,7, а ймовірність вибору двох квадратів поспіль дорівнює $0.7 \times 0.7 = 0.49$. Кола дають $0.3 \times 0.3 = 0.09$. Це єдині два способи, якими можуть збігатися вибірки, тому вони погоджуються $0.49 + 0.09 = 0.58$ часу. Але те, що ми прагнемо, полягає в протилежному — як часто два варіанти вибору повертаються по-різному — і оскільки кожна нічия або збігається, або ні, це один мінус шанс збігу: $1 - 0.58 =$ 0,42.

Правильний набір — це те саме обчислення з чотирма видами замість двох:

Два вибори збігаються в 30% випадків, тому вони відрізняються в 0,70 випадків, що відповідає семи з десяти, отриманих у вибірці, без жодної нічиєї.

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

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

де $p_k$ — частка множини, що належить виду $k$. Дві половинки — це два способи сказати: $\sum_k p_k^2$ — це ймовірність, що розіграші збігаються — для кожного виду — шанс, що обидва випадуть у ньому, сумарно — і один мінус — шанс, що вони відрізняються.

Наші два набори, що проходять через нього, є арифметикою мить тому в її стиснутому вигляді:

Статистика концентрації $\sum_k p_k^2$ також використовується в індексі Сімпсона та індексі Герфіндаля–Гіршмана. Домішка Джіні — це один мінус ця сума, а не та сама статистика.

Джіні в наших п’яти рядах

Тепер ми готові обчислити домішку Джіні для наших п’яти рядків. Спочатку нам потрібен підрахунок видів, який у нашому випадку є мітками: де набори вище містили квадрати, кола, трикутники та зірки, купа рядків містить Yes і No. Тож порахуйте їх, скільки кожної етикетки в даній купі, тому що кожна кількість у цій статті випливає з цього словника.

def label_counts(rows):
    """Tally the labels in a pile — the label is always the last column."""
    counts = {}
    for row in rows:
        counts[row[-1]] = counts.get(row[-1], 0) + 1
    return counts

Початковий аналіз усього набору даних, label_counts(training_data), дає {'No': 2, 'Yes': 3} — наших п’ятьох пацієнтів, підрахованих за типом.

Тепер, маючи під рукою підрахунок, ми можемо обчислити домішку Джіні — п’ять рядків Python:

def gini(rows):
    """Impurity of a pile: 0 when every row in it carries the same label."""
    if not rows:
        raise ValueError("Cannot measure impurity of an empty group")
    impurity = 1
    for count in label_counts(rows).values():
        share = count / len(rows)
        impurity -= share ** 2
    return impurity

Цикл — це формула, по одному терміну на мітку — подайте йому купу пацієнтів, які відповідають усім «Так», і він поверне 0,0, подайте йому один «Так» і один «Ні», і він поверне 0,5. Наш власний набір тренувань, три так проти двох ні, починається о:

gini(training_data) → 0.48

Ми збираємося переглянути кожне запитання кандидата та побачити, яке з них залишає найменше змішування позаду, тому 0,48 – це число, яке потрібно перемогти. Це також висока відправна точка: з двома мітками Джині має максимум 0,5, коли вони розподілені порівну, тому три «Так» проти двох «Ні» залишають нас на рівні 0.48 — приблизно так само переплутано, як можуть бути п’ять рядків.

Приріст Джіні — набирання очок

Оцініть кандидата шляхом віднімання домішки Джіні, зваженої за розміром його дітей, від домішки батька:

Записаний, це один рядок:

І це чотири кроки:

1. розділіть стопку $S$ із запитанням, даючи дві стопки — $S_L$, рядки з відповіддю True, і $S_R$, рядки з відповіддю False;
2. запустіть gini на кожному з них;
3. об’єднайте ці два числа в одне, зваживши кількість рядків, які пішли на кожну сторону: $\frac{|S_L|}{|S|}$ дає нам вагу лівої купи, а $\frac{|S_R|}{|S|}$ – вагу правої; кожне з них – частка батьківських рядків, які пішли туди;
4. відніміть це від батьківської домішки, $\text{Gini}(S)$.

Залишилася домішка, яку питання видалило — чим вона вища, тим краще питання.

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

Варто підкреслити, навіщо взагалі потрібне зважування на кроці 3, адже без нього оцінку легко обдурити. Два з наших кандидатів, Is stress_test == normal? і Is vessels >= 1?, кожен розділив п’ять рядків на один абсолютно чистий дочірній елемент, з Джині точно 0, і один дочірній елемент, який все ще змішаний. Вони відрізняються тим, скільки даних несе чиста дитина: один з них знімає одного пацієнта й залишає чотири змішані рядки позаду, інший бере два й залишає три. Тільки зважування бачить цю різницю. Завдяки цьому чиста дитина враховує рівно стільки, скільки важить, тому дитина з одного ряду ледь реєструється, а безлад, що залишився позаду, встановлює рахунок.

Ось обидва вони розроблені повністю, кожен з двома дочірніми елементами об’єднав два способи — підраховано порівну, а потім зважено за часткою рядків, які тримає кожна дитина:

Тепер таке саме ставлення до іншого кандидата. Is vessels >= 1? також вирізає абсолютно чисту дитину, але ця дитина тримає двох пацієнтів, а не одного, і купа, яку вона залишає, складається з трьох рядів, а не чотирьох — і ще брудніше, 0,444 замість 0,375:

Таким чином, числа на двох малюнках показують щось сильніше, ніж масштабування. При рівному підрахунку Is stress_test == normal? отримує 0,293, а Is vessels >= 1? — 0,258, тому виграє перше запитання. Зважено вони виходять 0,180 і 0,213, а натомість виграє другий. Зважування не просто зменшує бали — воно змінює порядок, і оскільки це корінь, дві відповіді дають дерева, які відрізняються до кінця.

Це те, як ми реалізуємо розподіл і отримання інформації про нього, включаючи зважування. split_rows виконує крок 1, сортуючи рядки у дві купи, які створює запитання, а split_gain виконує кроки 2–4, оцінюючи те, що вийшло, проти того, що увійшло:

def split_rows(rows, rule):
    """Sort every row into the pile where the rule holds, and the pile where it does not."""
    true_pile, false_pile = [], []
    for row in rows:
        (true_pile if rule.holds(row) else false_pile).append(row)
    return true_pile, false_pile

def split_gain(parent_impurity, true_pile, false_pile):
    """What went in, minus the two piles that came out, each weighed by its share."""
    share = len(true_pile) / (len(true_pile) + len(false_pile))
    return parent_impurity - share * gini(true_pile) - (1 - share) * gini(false_pile)

Проведіть їх над двома кандидатами вище, і вони повернуть 0.180 і 0.213 — ті самі числа, які цифри розробили вручну, тепер обчислені, а не намальовані.

Механізм — split, then recurse

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

1. Спробуйте кожне запитання, яке дозволяють дані — кожну функцію, кожне значення, яке ця функція приймає.
2. Оцініть кожне запитання за тим, наскільки воно розмішує мітки в купі — тобто збільшення інформації, засноване на домішці Джіні, саме так, як ми щойно вивели.
3. Якщо жодне запитання не допомогло, зупиніться: стопка стає листком, а кількість її міток стає прогнозом.
4. В іншому випадку використовуйте найкраще запитання, щоб розділити купу на дві менші купки.
5. Виконайте ту саму процедуру на кожній із двох куп.

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

Жадібний означає вибір найкращого поділу на поточному вузлі, не заглядаючи вперед і не переглядаючи попередні варіанти. Поділ без негайного виграшу все ще може активувати корисні поділи під ним, як у XOR. Наше правило зупинки їх пропустить.

Рекурсивність — це те, що вирізає прямокутники з фігури вступу: кожен виклик володіє однією областю простору функцій — рядками, які пережили питання над ним — і або поділяє цю область, або запечатує її як листок. Прямокутники - це купи в нижній частині рекурсії.

Вибір основного розділення — і зв’язок

Перш ніж побудувати всю рекурсивну річ, давайте швидко розглянемо реалізацію частини, яка працює на одному вузлі — пошук найкращого роздільного питання. У корені цей вузол містить усіх п’ятьох пацієнтів, а функція, яка виконує пошук, — choose_split, яка перевіряє кожне значення кожної функції та зберігає найкраще.

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

1. побудувати Rule зі стовпця та значення;
2. передайте його split_rows, який сортує ряди у дві купки, які він створює;
3. забити ці стопки split_gain;
4. порівняйте цю оцінку з найкращою, яку бачили на даний момент, і залиште запитання, якщо вона виграє.

Коли обидва цикли закінчуються, питання, яке все ще має найкращий результат, полягає в тому, що повертає функція.

def choose_split(rows):
    parent_impurity = gini(rows)
    winning_gain, winning_rule = 0, None

    for column in range(len(rows[0]) - 1):
        for value in sorted(set(row[column] for row in rows), reverse=True):
            rule = Rule(column, value)
            true_pile, false_pile = split_rows(rows, rule)

            if not true_pile or not false_pile:
                continue  # this rule doesn't divide the data

            gain = split_gain(parent_impurity, true_pile, false_pile)

            if gain >= winning_gain:
                winning_gain, winning_rule = gain, rule

    return winning_gain, winning_rule

Один виклик у корені оцінює кожне запитання, створене генератором, і повертається з таким:

Шість запитань — два стовпці з трьома різними значеннями в кожному — але лише п’ять із них мають число. Is vessels >= 0? є істинним для кожного пацієнта, оскільки 0 є найменшим значенням, яке приймає стовпець, тому він надсилає всі п’ять рядків у гілку True і жодного – у гілку False. Одна дитина тримає всю купу, а інша нічого не тримає, тобто не розбивка, а копія — нічого не розділили, тому нема за що забивати. Охоронець not true_pile or not false_pile кидає його до того, як split_gain його бачить. Його приріст у будь-якому випадку був би рівно 0 — одна дитина нічого не важить, інша — батько, — але його пропуск також запобігає поверненню нерозділеного питання як найкращого запитання, якщо ніщо інше не має оцінки вище нуля.

Тепер подивіться на вершину цієї таблиці, тому що це цікава частина. Повернулися два різні запитання з однаковою оцінкою 0.2133. Коли це відбувається, пізніший кандидат перезаписує попередній. Така поведінка є деталлю реалізації, і в нашому алгоритмі вона виникає з двох речей: стовпці скануються в порядку індексів, тому stress_test (стовпець 0) потрапляє туди першим, а потім тихо заміщується таким же хорошим vessels (стовпець 1); і порівняння записується з >=, а не з >, що дозволяє зсуву взагалі відбутися:

if gain >= winning_gain:

Тут пов’язані питання вибирають точно такі ж дві групи пацієнтів, які навчаються, тому зв’язок не змінює їхні наступні розділи. Він може змінювати передбачення для невидимих ​​комбінацій, наприклад normal з vessels=3. Ми скануємо різні значення в порядку спадання, щоб зв’язки були відтворюваними; >= все ще дає перемогу останньому кандидату з рівними результатами.

Рекурсія — побудова дерева

Тепер, коли один вузол може знайти своє запитання, ми готові побудувати ціле дерево — рекурсію, яка запускає цей пошук у купі за стопкою та зберігає знайдене. Зберігання займає один клас для кожного типу вузла з початкової діаграми: Leaf зберігає кількість міток будь-яких рядків, які досягли його, а Node зберігає запитання та дві гілки. У словнику підручника це питання — це правило розбиття — один предикат для однієї функції, звідки і назва класу Rule — і вузол прийняття рішень — це правило, з’єднане з блок-схемою, з двома гілками, які дають відповіді «так/ні» кудись. Готове дерево можна уявити як ряд правил розбиття. Починаючи з вершини дерева й застосовуючи на шляху вниз — choose_split вивчає ці правила, а вузли — це місце, де живуть вибрані.

class Leaf:
    def __init__(self, rows):
        self.counts = label_counts(rows)

class Node:
    def __init__(self, rule, if_true, if_false):
        self.rule = rule
        self.if_true = if_true
        self.if_false = if_false

def grow_tree(rows):
    if not rows:
        raise ValueError("Training rows must not be empty")
    gain, rule = choose_split(rows)

    if gain <= 1e-12 or rule is None:
        return Leaf(rows)          # base case: no rule helps anymore

    true_pile, false_pile = split_rows(rows, rule)
    return Node(rule, grow_tree(true_pile), grow_tree(false_pile))

Коли ми перевіряємо п’ятьох пацієнтів, ми отримуємо ось дерево — намальоване з купами, видимими на кожній гілці:

Дерево має глибину 2 і три листки. Корінь надсилає два навчальні рядки з vessels >= 1 до чистого листа Yes. Це описує ці два рядки, а не медичне правило.

На цьому варто зупинитися: ціла група випала з даних без жодної суміші — Gini 0, створена одним запитанням. Рівнем нижче самотній пацієнт normal робить те саме — і зауважте, що stress_test має три значення, тоді як дерево завжди запитує лише про одне з них. stress_test == fixed? відшаровує пацієнтів із фіксованими дефектами, а все, що не виправлено, їздить на гілці False разом, непомітно. Тут виявляється єдиний пацієнт normal, тому що обидва пацієнти reversable залишилися в корені.

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

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

Навчання вибирає структуру дерева, пороги та кількість листя. Після повернення рекурсивних викликів модель готова до прогнозування; у цій реалізації немає оновлень градієнта чи епох навчання.

Класифікація — читання ймовірності з аркуша

Прогноз знову є рекурсією, і він коротший, ніж навчальний код:

def descend(row, node):
    if isinstance(node, Leaf):
        return node.counts

    branch = node.if_true if node.rule.holds(row) else node.if_false
    return descend(row, branch)

def as_percentages(counts):
    total = sum(counts.values())
    return {label: f"{count / total:.0%}" for label, count in counts.items()}

Кожен Node зберігає один Rule — індекс стовпця плюс значення — і holds порівнює з ним запис рядка в цьому стовпці, повертаючи звичайний True або False. Це логічне значення є єдиним, що потрібно descend: True надсилає рядок вниз if_true, False вниз if_false, і рекурсія зупиняється, щойно вона потрапляє на Leaf.

Давайте візьмемо дані одного пацієнта, ['fixed', 0, 'Yes'], і подивимось, як дерево прогнозує, чи є у нього хвороба серця чи ні:

1. корінь запитує Is vessels >= 1?; holds зчитує запис vessels пацієнта — тобто 0 — і, оскільки значення є числовим, він обчислює 0 >= 1, даючи False, тому рядок приймає хибну гілку;
2. цей вузол запитує Is stress_test == fixed?; holds зчитує запис stress_test пацієнта — 'fixed' — і, оскільки значення є рядком, він обчислює 'fixed' == 'fixed', даючи True, тому рядок приймає істинну гілку;
3. ця гілка є Leaf, тому descend повертає збережені там підрахунки: один Yes і один No.

Ці підрахунки, які повертає descend, є прогнозом у необробленому вигляді. Їх можна прочитати як одну мітку, взявши те, що є найпоширенішим у аркуші — це те, що робить predict у бібліотеці, як-от sklearn, і це однозначно у чистих листках, де {'Yes': 2} означає «Так». Їх також можна прочитати як ймовірність, поділивши кожну кількість на загальну суму, яка дорівнює predict_proba, і що тут робить as_percentages.

Змішаний аркуш повідомляє 50/50, оскільки містить один приклад кожного класу. Це емпірична оцінка з двох рядків, а не доказ 50% популяційного ризику чи повної оцінки невизначеності. Ідентичні вхідні дані з суперечливими мітками накладають мінімальну кількість помилок навчання на детерміновані предиктори, які використовують ці функції. Бібліотека, яка повертає один клас, також повинна вибрати правило для зв’язаних підрахунків.

Наведений нижче віджет є трохи більшою іграшкою — дві числові функції, пороги замість наших змішаних типів — але механізм ідентичний, і він показує два види дерева одночасно. Ліва панель - перегородка; Права панель - прогулянка. Два повзунки є значеннями функцій $x_1$ і $x_2$ — їх перетягування створює новий рядок і переміщує його в просторі функцій. У той момент, коли ця точка перетинає пунктирну лінію, це саме той момент, коли шлях крізь дерево змінюється, тому що область і лист — це один і той самий об’єкт, одягнений у різний одяг.

Зауважте також, що це дерево двічі використовує функцію, позначену $x_1$ — один раз у корені, а потім двома рівнями нижче на іншому пороговому значенні. Це два різні питання в одному стовпці — та сама функція, різне значення — тому що функція не витрачається через поділ: перший розріз розділяє те, що вона може, а рядки, що залишилися, все ще можуть бути розділеними вздовж тієї самої осі.

Одну і ту ж функцію можна використовувати на кількох вузлах. Кожен вузол перебудовує своїх кандидатів із рядків, які досягли його, тому значення, відсутнє в цих рядках, більше не є кандидатом. Наприклад, дочірній елемент False нашого кореня не має рядка з vessels=2.

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

patient   2  ['normal',     3]   Actual: Yes.  Predicted: {'Yes': '100%'}
patient   9  ['reversable', 1]   Actual: Yes.  Predicted: {'Yes': '100%'}
patient 266  ['fixed',      0]   Actual: Yes.  Predicted: {'Yes': '50%', 'No': '50%'}
patient  88  ['NA',         0]   Actual: No.   Predicted: {'No': '100%'}
patient 267  ['NA',         0]   Actual: Yes.  Predicted: {'No': '100%'}

Перший тестовий рядок — це ['normal', 3, 'Yes'], і кількість vessels 3 ніколи не з’являлася під час навчання — наші п’ять пацієнтів показували лише 0, 1 і 2. Він все ще потрапляє в аркуш, оскільки vessels >= 1 — це порогове значення, а не пошук: 3 очищає його та йде тим же шляхом, що й 1. Порогові значення безкоштовно узагальнюють свої навчальні значення.

Відсутні значення — це інша історія: модель просто не обробляє їх належним чином. Пацієнти 88 і 267 не мають записаного стрес-тесту — у файлі зазначено NA — і оскільки NA ніколи не з’являвся на тренуванні, він провалює тест stress_test == fixed? і ковзає вниз по гілці False, таким чином пацієнт 267 повертається як {'No': '100%'}, хоча насправді має хворобу.

На практиці ви маєте справу з цим перед навчанням — видаліть незавершені рядки, призначте відсутні записи або зробіть "missing" окремою категорією.

Невидима категорія слідує за тією самою гілкою False, що й будь-яке інше значення, яке не проходить тест на рівність. Наша модель не виявляє цю новинку і не зменшує відображуваний відсоток. У наведеному вище прикладі 100% No базується на аркуші, що містить лише один навчальний рядок.

Підтримка відсутніх значень залежить від реалізації. Деякі бібліотеки вивчають гілку за замовчуванням; оригінальний CART може використовувати сурогатні розбиття. Ці механізми не роблять довільний рядок, такий як "NA", розпізнаним відсутнім значенням: використовуйте подання, яке очікує бібліотека.

Чому одне дерево - це ще не кінець історії

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

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

Для більшого прикладу скористайтеся DecisionTreeClassifier scikit-learn. Він слідує тій самій жадібній ідеї, але його середні пороги, обробка зв’язків і деталі зупинки можуть створити інше дерево від нашого.

Тепер наведіть його на набір даних про рак грудей (398 рядків, 171 тест, 30 ознак):

from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier

data = load_breast_cancer()
X_tr, X_te, y_tr, y_te = train_test_split(
    data.data, data.target, test_size=0.3, random_state=0
)

unpruned = DecisionTreeClassifier(criterion="gini", random_state=0).fit(X_tr, y_tr)
print(unpruned.get_depth(), unpruned.get_n_leaves())
print(unpruned.score(X_tr, y_tr), unpruned.score(X_te, y_te))

for depth in (1, 2, 3, 5, 7):
    pruned = DecisionTreeClassifier(
        criterion="gini", max_depth=depth, random_state=0
    ).fit(X_tr, y_tr)
    print(depth, pruned.score(X_tr, y_tr), pruned.score(X_te, y_te))

Нестримне дерево, яке ніщо не стримує, виходить таким чином:

UNPRUNED (scikit-learn)
  depth      7
  leaves     19
  train acc  1.000
  test acc   0.912

Точність навчання 1000 означає, що всі 398 навчальних етикеток відтворюються. Для цього не потрібна одна стулка в ряду: ця посадка має всього 19 листів. Його точність на 171 проведеному рядку становить 0,912.

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

На цьому розподілі глибина 2 набрала 0,947 на основі даних, що залишилися, порівняно з 0,912 на глибині 7, незважаючи на нижчу точність навчання. Це ілюструє переобладнання; він не встановлює глибину 2 як загалом оптимальну. Якщо ці результати керують вибором глибини, цей відкладений набір служить даними перевірки. Оцініть обрану модель на окремому тестовому наборі.

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

Сортування значень-кандидатів виправляє варіацію від запуску до виконання, спричинену порядком встановлення Python. Це не усуває статистичну нестабільність: перенавчання на іншій вибірці може змінити підібране дерево.

Ці дві поведінки є двома сторонами компромісу зміщення-дисперсії. У статистичному навчанні зміщення — це помилка, яка виникає в результаті наближення складної реальності за допомогою простішої моделі — модель, яка є занадто жорсткою для відображення шаблону, буде неправильною незалежно від того, скільки даних ви їй надаєте. Дисперсія – це величина, яку змінила б підібрана модель, якщо ви оцінили її на основі іншого навчального набору: перенавчайтеся на іншій вибірці пацієнтів, і метод високої дисперсії дає вам помітно іншу модель, допускаючи помітно інші помилки.

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

Існують усталені методи вирішення цих проблем — обмеження глибини, мінімальна кількість рядів на аркуш, мінімальний приріст, заради якого варто розщепити, і скорочення гілок після факту. На практиці ви рідко застосовуєте їх до самотнього дерева; це ручки, які ви налаштовуєте всередині ансамблю — моделі, побудованої з багатьох дерев, чиї відповіді об’єднані в одну, що є випадковим лісом і посиленням градієнта.

Попереднє обрізання обмежує зростання за допомогою таких засобів контролю, як max_depth і min_samples_leaf. Постобрізка спочатку вирощує більше дерево, а потім видаляє гілки. Обрізка витрат і складності CART врівноважує тренувальну домішку зі штрафом за листок; scikit-learn розкриває це покарання як ccp_alpha. Виберіть його значення, використовуючи дані перевірки або перехресну перевірку, зберігаючи остаточний тестовий набір окремо.

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

Де наша версія повільніша за реальну

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

Цикл проходить через кожну функцію та кожне окреме значення, яке приймає ця функція, тому кількість кандидатів становить features × values. Тоді кожен кандидат коштує повного проходу даних: split_rows обходить кожен рядок, щоб сортувати його на дві купи, а split_gain викликає gini для кожної купи, яка підраховує її мітки з нуля. Це $O(\text{features} \times \text{values} \times \text{rows})$. У п’яти рядках із трьома значеннями на стовпець, невидимий. За безперервною характеристикою — скажімо, холестерином — майже кожен рядок містить окреме значення, тому кількість кандидатів зростає разом із даними, тоді як кожен кандидат все ще коштує повного сканування: квадратичного за кількістю рядків і безнадійного за сто тисяч із них.

Візьміть п’ять рядків стовпця cholesterol — 210 (Ні), 233 (Ні), 250 (Так), 286 (Так), 300 (Так). Генератор перетворює їх на п’ять запитань-кандидатів, по одному на спостережене значення, чотири з яких фактично розбивають купу:

Слідкуйте за двома з них, >= 233 і >= 250, через наш код.

Для >= 233 split_rows проходить усі п’ять рядків і скидає 210 у список False, а інші чотири – у список True. Потім split_gain викликає gini на кожній, і gini обходить мітки підрахунку стопи в один ряд, а потім мітки підрахунку купи в чотири ряди. П’ять візитів на розрив, п’ять на рахунок. Для >= 250 він знову починається з тих самих п’яти рядків і так далі за списком:

>= 233:  split_rows 5 rows → gini({210}) + gini({233,250,286,300})   = 10 visits
>= 250:  split_rows 5 rows → gini({210,233}) + gini({250,286,300})   = 10 visits
>= 286:  split_rows 5 rows → gini({210,233,250}) + gini({286,300})   = 10 visits
>= 300:  split_rows 5 rows → gini({210,233,250,286}) + gini({300})   = 10 visits

Сорок відвідувань рядів, і нічого не проноситься між рядами — навіть якщо кожна пара куп відрізняється від пари над нею рівно на один ряд.

Ось ті самі п’ять рядків, відсортованих за рівнем холестерину та з міткою disease, яка виявилася у кожного пацієнта, як виявилося в реальній реалізації:

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

Кожен рядок — це рядок над ним плюс мітка рядка, який щойно пройшов: 210 — це Ні, тому підрахунок відкривається на {No: 1}; 233 – ще одне «Ні», що веде до {No: 2}; 250 – це так, додаючи перше так; і так далі. Один приріст на ряд, п’ять рядів, один прохід.

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

Оскільки формула приросту зважує обидві дочірні групи, необхідні обидві групи, але лише перша відстежується в міру просування розгортки. Групи, які перевищують поріг, ніколи не потребують підрахунку; його можна вивести. Власні суми вузла були визначені під час його створення — {No: 2, Yes: 3} тут — тому все, що не нижче порогу, є вищим за нього. Жодне запитання не перечитує нічого — два пошуки та віднімання в кожному, при цьому Джіні слідує з чотирьох цілих чисел.

Для рядків $n$ і функцій $d$ простий пошук може зайняти роботу $O(dn^2)$ на одному вузлі. Сортування кожної числової функції та її перегляд скорочує це приблизно до $O(dn\log n)$, включаючи сортування, для фіксованої кількості класів. Після сортування кожна розгортка є лінійною. Це порівняння для кожного вузла; вартість будівництва всього дерева також залежить від його форми.