import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

from sklearn.tree import DecisionTreeClassifier, plot_tree

# Ті самі дані, що в лекції: клієнти банку, дві ознаки.
# стаж   — скільки місяців клієнт уже з банком (0…24)
# витрати — скільки тисяч гривень на місяць проходить через картку (0…10)
# Мітка 1 = «лишиться на наступний рік».

def справжня_межа(стаж):
    """Сходинка, за якою насправді влаштовані дані.

    Модель її не знає — вона має здогадатись про неї сама.
    Чим довший стаж, тим менших витрат досить, щоб клієнт лишився."""
    return np.where(стаж < 9, 7.5, np.where(стаж < 17, 4.8, 2.2))


def згенерувати_клієнтів(скільки, генератор):
    стаж = генератор.uniform(0, 24, скільки)
    витрати = генератор.uniform(0, 10, скільки)
    лишиться = (витрати >= справжня_межа(стаж)).astype(int)
    # 10% міток перевертаємо: без шуму перенавчання нема на чому показувати
    перевернути = генератор.random(скільки) < 0.10
    лишиться[перевернути] = 1 - лишиться[перевернути]
    return np.column_stack([стаж, витрати]), лишиться


# зерно підібране так, щоб вибірка збігалася з тією, на якій рахувались числа лекції
генератор = np.random.default_rng(61)
X_навч, y_навч = згенерувати_клієнтів(200, генератор)
X_тест, y_тест = згенерувати_клієнтів(800, генератор)

print(f"навчальна вибірка: {len(y_навч)} клієнтів, з них лишились {y_навч.sum()}")
print(f"тестова вибірка:   {len(y_тест)} клієнтів, з них лишились {y_тест.sum()}")
print(f"частка класу «лишиться» на навчанні: {y_навч.mean():.3f}")

навчальна вибірка: 200 клієнтів, з них лишились 95
тестова вибірка:   800 клієнтів, з них лишились 391
частка класу «лишиться» на навчанні: 0.475

табличка = pd.DataFrame({
    "витрати":  [1.2, 2.0, 3.5, 4.1, 5.0, 6.2, 7.4, 8.8],
    "лишиться": [0,   0,   1,   0,   0,   1,   1,   1],
})

print(табличка.to_string(index=False))
print(f"\nусього обʼєктів: {len(табличка)}, з них клас 1: {табличка['лишиться'].sum()}")

 витрати  лишиться
     1.2         0
     2.0         0
     3.5         1
     4.1         0
     5.0         0
     6.2         1
     7.4         1
     8.8         1

усього обʼєктів: 8, з них клас 1: 4

def ентропія(мітки):
    """Ентропія набору міток у бітах. Порожній набір вважаємо чистим."""
    мітки = np.asarray(мітки)
    if len(мітки) == 0:
        return 0.0
    частки = np.bincount(мітки, minlength=2) / len(мітки)
    # нульові частки викидаємо: log2(0) не існує, а внесок такого класу і так нульовий
    частки = частки[частки > 0]
    # додаємо 0.0, щоб чистий вузол друкувався як 0.0000, а не як «мінус нуль»
    return float(-np.sum(частки * np.log2(частки)) + 0.0)


мітки_таблички = табличка["лишиться"].to_numpy()

print("перевіримо формулу на трьох наборах, які легко порахувати в голові:")
print(f"  усі одного класу [1,1,1,1] -> H = {ентропія([1, 1, 1, 1]):.4f}  (очікуємо 0)")
print(f"  рівно навпіл     [0,0,1,1] -> H = {ентропія([0, 0, 1, 1]):.4f}  (очікуємо 1)")
print(f"  один із чотирьох [0,0,0,1] -> H = {ентропія([0, 0, 0, 1]):.4f}  (очікуємо 0.8113)")
print(f"\nентропія всієї таблички (4 та 4)  -> H = {ентропія(мітки_таблички):.4f}")

перевіримо формулу на трьох наборах, які легко порахувати в голові:
  усі одного класу [1,1,1,1] -> H = 0.0000  (очікуємо 0)
  рівно навпіл     [0,0,1,1] -> H = 1.0000  (очікуємо 1)
  один із чотирьох [0,0,0,1] -> H = 0.8113  (очікуємо 0.8113)

ентропія всієї таблички (4 та 4)  -> H = 1.0000

def приріст_інформації(значення_ознаки, мітки, поріг):
    """IG від розрізу «ознака <= поріг». Повертає (IG, H ліворуч, H праворуч, N ліворуч)."""
    ліворуч = значення_ознаки <= поріг
    праворуч = ~ліворуч
    n = len(мітки)
    n_ліво, n_право = ліворуч.sum(), праворуч.sum()

    # зважене середнє: вузол із трьох обʼєктів не має важити стільки ж, скільки вузол зі ста
    зважена_після = (n_ліво / n) * ентропія(мітки[ліворуч]) + \
                    (n_право / n) * ентропія(мітки[праворуч])
    return (ентропія(мітки) - зважена_після,
            ентропія(мітки[ліворуч]), ентропія(мітки[праворуч]), n_ліво)


витрати_таблички = табличка["витрати"].to_numpy()
# середини між сусідніми значеннями — усі поріг-кандидати
пороги = (витрати_таблички[:-1] + витрати_таблички[1:]) / 2

print(f"H батька = {ентропія(мітки_таблички):.4f}\n")
print("поріг   N ліво  H ліво   H право     IG")
for поріг in пороги:
    ig, h_ліво, h_право, n_ліво = приріст_інформації(витрати_таблички, мітки_таблички, поріг)
    print(f"{поріг:5.2f}   {n_ліво:5d}  {h_ліво:6.4f}   {h_право:6.4f}   {ig:6.4f}")

H батька = 1.0000

поріг   N ліво  H ліво   H право     IG
 1.60       1  0.0000   0.9852   0.1379
 2.75       2  0.0000   0.9183   0.3113
 3.80       3  0.9183   0.9710   0.0488
 4.55       4  0.8113   0.8113   0.1887
 5.60       5  0.7219   0.0000   0.5488
 6.80       6  0.9183   0.0000   0.3113
 8.10       7  0.9852   0.0000   0.1379

def найкращий_розріз(X, y, міра_безладу):
    """Повний перебір: усі ознаки × усі пороги. Повертає (приріст, номер ознаки, поріг)."""
    найкращий = (-1.0, None, None)
    безлад_батька = міра_безладу(y)

    for номер_ознаки in range(X.shape[1]):
        значення = X[:, номер_ознаки]
        # унікальні значення вже відсортовані — беремо середини між сусідніми
        унікальні = np.unique(значення)
        пороги_ознаки = (унікальні[:-1] + унікальні[1:]) / 2

        for поріг in пороги_ознаки:
            ліворуч = значення <= поріг
            n_ліво, n_право = ліворуч.sum(), (~ліворуч).sum()
            зважена_після = (n_ліво / len(y)) * міра_безладу(y[ліворуч]) + \
                            (n_право / len(y)) * міра_безладу(y[~ліворуч])
            приріст = безлад_батька - зважена_після
            if приріст > найкращий[0]:
                найкращий = (приріст, номер_ознаки, поріг)

    return найкращий


назви_ознак = ["стаж", "витрати"]

print("найкращий розріз окремо за кожною ознакою (критерій — ентропія):")
for номер, назва in enumerate(назви_ознак):
    приріст, _, поріг = найкращий_розріз(X_навч[:, [номер]], y_навч, ентропія)
    print(f"  {назва:8s}: IG = {приріст:.4f} біт  при порозі {поріг:.2f}")

приріст, ознака, поріг = найкращий_розріз(X_навч, y_навч, ентропія)
print(f"\nкорінь дерева: «{назви_ознак[ознака]} <= {поріг:.2f}», приріст {приріст:.4f} біт")

найкращий розріз окремо за кожною ознакою (критерій — ентропія):
  стаж    : IG = 0.1007 біт  при порозі 15.52
  витрати : IG = 0.1712 біт  при порозі 4.66

корінь дерева: «витрати <= 4.66», приріст 0.1712 біт

def джині(мітки):
    """Індекс Джині: ймовірність, що два навмання витягнуті обʼєкти будуть різних класів."""
    мітки = np.asarray(мітки)
    if len(мітки) == 0:
        return 0.0
    частки = np.bincount(мітки, minlength=2) / len(мітки)
    return float(1 - np.sum(частки ** 2))


print("Джині на тих самих трьох наборах, що й ентропія:")
print(f"  [1,1,1,1] -> {джині([1, 1, 1, 1]):.4f}   (чистий вузол — нуль)")
print(f"  [0,0,1,1] -> {джині([0, 0, 1, 1]):.4f}   (навпіл — максимум 0.5)")
print(f"  [0,0,0,1] -> {джині([0, 0, 0, 1]):.4f}")

Джині на тих самих трьох наборах, що й ентропія:
  [1,1,1,1] -> 0.0000   (чистий вузол — нуль)
  [0,0,1,1] -> 0.5000   (навпіл — максимум 0.5)
  [0,0,0,1] -> 0.3750

наш_приріст, наша_ознака, наш_поріг = найкращий_розріз(X_навч, y_навч, джині)

пеньок = DecisionTreeClassifier(max_depth=1, random_state=0).fit(X_навч, y_навч)
ознака_sklearn = пеньок.tree_.feature[0]
поріг_sklearn = пеньок.tree_.threshold[0]

print(f"наш перебір : ознака «{назви_ознак[наша_ознака]}», поріг {наш_поріг:.10f}")
print(f"sklearn     : ознака «{назви_ознак[ознака_sklearn]}», поріг {поріг_sklearn:.10f}")
print(f"різниця порогів: {abs(наш_поріг - поріг_sklearn):.2e}")

assert наша_ознака == ознака_sklearn, "обрали різні ознаки!"
assert np.allclose(наш_поріг, поріг_sklearn), "розрахунок розійшовся!"
print("\n✅ збігається")

наш перебір : ознака «витрати», поріг 4.6557172187
sklearn     : ознака «витрати», поріг 4.6557171345
різниця порогів: 8.42e-08

✅ збігається

# tree_.impurity[0] — Джині кореня, [1] і [2] — лівого й правого нащадків
ліворуч_від_порога = X_навч[:, наша_ознака] <= наш_поріг

наші_безлади = [
    джині(y_навч),
    джині(y_навч[ліворуч_від_порога]),
    джині(y_навч[~ліворуч_від_порога]),
]
безлади_sklearn = пеньок.tree_.impurity[:3]

for підпис, наше, бібліотечне in zip(["корінь", "ліво  ", "право "], наші_безлади, безлади_sklearn):
    print(f"{підпис}: наше {наше:.6f}   sklearn {бібліотечне:.6f}")

assert np.allclose(наші_безлади, безлади_sklearn), "Джині у вузлах розійшовся!"
print("\n✅ Джині у всіх трьох вузлах збігається")

корінь: наше 0.498750   sklearn 0.498750
ліво  : наше 0.340265   sklearn 0.340265
право : наше 0.424383   sklearn 0.424383

✅ Джині у всіх трьох вузлах збігається

глибини = list(range(1, 15))
результати = []

for глибина in глибини:
    дерево = DecisionTreeClassifier(max_depth=глибина, random_state=0).fit(X_навч, y_навч)
    точність_навч = дерево.score(X_навч, y_навч)
    точність_тест = дерево.score(X_тест, y_тест)
    результати.append({
        "глибина": глибина,
        "train": точність_навч,
        "test": точність_тест,
        "розрив": точність_навч - точність_тест,
        "листків": дерево.get_n_leaves(),
    })

таблиця_глибин = pd.DataFrame(результати)
print(таблиця_глибин.to_string(index=False, float_format=lambda v: f"{v:.3f}"))

найкраща = таблиця_глибин.loc[таблиця_глибин["test"].idxmax()]
print(f"\nнайкраща тестова точність {найкраща['test']:.3f} при глибині {int(найкраща['глибина'])}")

 глибина  train  test  розрив  листків
       1  0.735 0.749  -0.014        2
       2  0.780 0.771   0.009        4
       3  0.890 0.884   0.006        8
       4  0.905 0.866   0.039       15
       5  0.950 0.838   0.112       25
       6  0.975 0.824   0.151       30
       7  0.980 0.816   0.164       32
       8  0.990 0.820   0.170       35
       9  0.995 0.819   0.176       36
      10  0.995 0.819   0.176       37
      11  1.000 0.810   0.190       38
      12  1.000 0.810   0.190       38
      13  1.000 0.810   0.190       38
      14  1.000 0.810   0.190       38

найкраща тестова точність 0.884 при глибині 3

fig, ax = plt.subplots(figsize=(9, 4.5))

ax.plot(таблиця_глибин["глибина"], таблиця_глибин["train"],
        marker="o", lw=2, color="crimson", label="train (200 клієнтів)")
ax.plot(таблиця_глибин["глибина"], таблиця_глибин["test"],
        marker="o", lw=2, color="teal", label="test (800 нових клієнтів)")

# позначаємо оптимум, щоб було видно, де саме крива розвертається
ax.axvline(найкраща["глибина"], color="gray", ls="--", lw=1.4,
           label=f"оптимум: глибина {int(найкраща['глибина'])}")

ax.set_xlabel("max_depth")
ax.set_ylabel("частка правильних відповідей")
ax.set_title("Глибина проти узагальнення")
ax.legend()
ax.grid(alpha=.25)
plt.tight_layout()
plt.show()

дерево_3 = DecisionTreeClassifier(max_depth=3, random_state=0).fit(X_навч, y_навч)

fig, ax = plt.subplots(figsize=(15, 7))
plot_tree(дерево_3,
          feature_names=назви_ознак,
          class_names=["піде", "лишиться"],
          filled=True,       # колір показує, який клас переважає у вузлі
          rounded=True,
          fontsize=9,
          ax=ax)
ax.set_title("Дерево глибини 3: 200 клієнтів банку")
plt.tight_layout()
plt.show()

print(f"вузлів усього: {дерево_3.tree_.node_count}, листків: {дерево_3.get_n_leaves()}")

вузлів усього: 15, листків: 8

from sklearn.tree import export_text

# те саме дерево словами: інколи текст читати зручніше за картинку
print(export_text(дерево_3, feature_names=назви_ознак, decimals=1))

|--- витрати <= 4.7
|   |--- стаж <= 16.9
|   |   |--- витрати <= 1.1
|   |   |   |--- class: 0
|   |   |--- витрати >  1.1
|   |   |   |--- class: 0
|   |--- стаж >  16.9
|   |   |--- витрати <= 2.3
|   |   |   |--- class: 0
|   |   |--- витрати >  2.3
|   |   |   |--- class: 1
|--- витрати >  4.7
|   |--- стаж <= 8.8
|   |   |--- витрати <= 7.5
|   |   |   |--- class: 0
|   |   |--- витрати >  7.5
|   |   |   |--- class: 1
|   |--- стаж >  8.8
|   |   |--- витрати <= 6.7
|   |   |   |--- class: 1
|   |   |--- витрати >  6.7
|   |   |   |--- class: 1

def карта_відповідей(модель):
    """Прогноз моделі в кожній точці сітки 150×150 — це і є «що модель думає» про всю площину."""
    осі_стажу = np.linspace(0, 24, 150)
    осі_витрат = np.linspace(0, 10, 150)
    сітка_стажу, сітка_витрат = np.meshgrid(осі_стажу, осі_витрат)
    точки = np.column_stack([сітка_стажу.ravel(), сітка_витрат.ravel()])
    return модель.predict(точки)


генератор_підвибірок = np.random.default_rng(2024)
карти = []
рядки = []

for спроба in range(6):
    # беремо 150 клієнтів зі 200 без повернення — «трохи інші дані»
    індекси = генератор_підвибірок.choice(len(y_навч), size=150, replace=False)
    дерево = DecisionTreeClassifier(max_depth=4, random_state=0)
    дерево.fit(X_навч[індекси], y_навч[індекси])

    карта = карта_відповідей(дерево)
    карти.append(карта)
    # порівнюємо з першою спробою: на якій частці площини нове дерево думає інакше
    # (у першому рядку буде нуль — це порівняння дерева з самим собою)
    інша_відповідь = np.mean(карта != карти[0])

    рядки.append({
        "спроба": спроба + 1,
        "корінь": назви_ознак[дерево.tree_.feature[0]],
        "поріг": дерево.tree_.threshold[0],
        "листків": дерево.get_n_leaves(),
        "test": дерево.score(X_тест, y_тест),
        "інша ніж №1": інша_відповідь,
    })

print(pd.DataFrame(рядки).to_string(index=False, float_format=lambda v: f"{v:.3f}"))

 спроба  корінь  поріг  листків  test  інша ніж №1
      1 витрати  4.656       15 0.821        0.000
      2    стаж 15.519       15 0.839        0.149
      3 витрати  4.962       13 0.823        0.082
      4 витрати  4.656       15 0.856        0.098
      5 витрати  4.656       14 0.811        0.063
      6 витрати  4.379       16 0.871        0.110

# наскільки взагалі розходяться між собою шість дерев: беремо всі пари
розбіжності = []
for i in range(len(карти)):
    for j in range(i + 1, len(карти)):
        розбіжності.append(np.mean(карти[i] != карти[j]))

print(f"пар дерев: {len(розбіжності)}")
print(f"розбіжність між парою дерев: від {min(розбіжності):.1%} до {max(розбіжності):.1%}, "
      f"у середньому {np.mean(розбіжності):.1%}")
print("\nДані змінились на чверть — а відповідь моделі змінилась на десяту частину площини.")
print("Жодне з цих дерев не «правильне»: вони просто по-різному вгадують.")

пар дерев: 15
розбіжність між парою дерев: від 3.3% до 16.3%, у середньому 10.3%

Дані змінились на чверть — а відповідь моделі змінилась на десяту частину площини.
Жодне з цих дерев не «правильне»: вони просто по-різному вгадують.

# бачимо цю ж думку очима: межі шести дерев на одній картинці
fig, axes = plt.subplots(2, 3, figsize=(14, 7))
осі_стажу = np.linspace(0, 24, 150)
осі_витрат = np.linspace(0, 10, 150)

for номер, (ax, карта) in enumerate(zip(axes.ravel(), карти)):
    ax.contourf(осі_стажу, осі_витрат, карта.reshape(150, 150),
                levels=[-0.5, 0.5, 1.5], colors=["#ffe3ea", "#d8f3ef"])
    ax.scatter(X_навч[y_навч == 0, 0], X_навч[y_навч == 0, 1], s=10, color="crimson")
    ax.scatter(X_навч[y_навч == 1, 0], X_навч[y_навч == 1, 1], s=10, color="teal")
    ax.set_title(f"підвибірка {номер + 1}", fontsize=11)
    ax.set_xlabel("стаж")
    ax.set_ylabel("витрати")

plt.tight_layout()
plt.show()

Практика 11 · Дерева рішень¶

1. Ентропія руками¶

Перевіримо 0.8113 на папері¶

2. Приріст інформації: перебираємо всі пороги¶

Що видно в таблиці¶

3. Найкращий розріз на справжніх даних¶

4. Звірка з `DecisionTreeClassifier`¶

5. Перенавчання: що робить `max_depth`¶

6. Як виглядає готове дерево¶

7. Нестабільність: та сама задача, інша підвибірка¶

💻 Завдання¶

🟢 Рівень 1 — разом¶

🟡 Рівень 2 — самостійно¶

🔴 Рівень 3 — виклик¶

🧪 Самоперевірка¶

Практика 11 · Дерева рішень¶

1. Ентропія руками¶

Перевіримо 0.8113 на папері¶

2. Приріст інформації: перебираємо всі пороги¶

Що видно в таблиці¶

3. Найкращий розріз на справжніх даних¶

4. Звірка з DecisionTreeClassifier¶

5. Перенавчання: що робить max_depth¶

6. Як виглядає готове дерево¶

7. Нестабільність: та сама задача, інша підвибірка¶

💻 Завдання¶

🟢 Рівень 1 — разом¶

🟡 Рівень 2 — самостійно¶

🔴 Рівень 3 — виклик¶

🧪 Самоперевірка¶

4. Звірка з `DecisionTreeClassifier`¶

5. Перенавчання: що робить `max_depth`¶