ID3 (алгоритм)

1. Обчислити ентропію кожного атрибута ${\displaystyle a}$ набору даних ${\displaystyle S}$.
2. Розділити множину ${\displaystyle S}$ на підмножини, використовуючи атрибут, для якого вислідна ентропія після розбиття зведена до мінімуму; або, що еквівалентно, інформаційний приріст є максимальним.
3. Створити вузол дерева рішень, що містить цей атрибут.
4. Повторити алгоритм на підмножинах, використовуючи атрибути, що залишилися.

ID3 (Приклади, Цільові_Атрибути, Атрибути)
    Створити кореневий вузол для дерева.
    Якщо всі приклади додатні, повернути дерево з міткою = «+».
    Якщо всі приклади від'ємні, повернути дерево з міткою = «-».
    Якщо множина атрибутів порожня, повернути дерево з міткою = найбільш поширене значення цільового атрибута в прикладах.
    Інакше
        ${\displaystyle A}$ ← Атрибут, який найкраще класифікує приклади.
        Встановити значення кореня = ${\displaystyle A}$.
        Для кожного можливого значення ${\displaystyle v_{i}}$ множини ${\displaystyle A}$
            Додати нову гілку під коренем, що відповідає перевірці ${\displaystyle A=v_{i}}$.
            Нехай ${\displaystyle Examples(v_{i})}$ буде підмножиною прикладів зі значенням ${\displaystyle A=v_{i}}$.             
            Якщо множина ${\displaystyle Examples(v_{i})}$ порожня, тоді
                Додати під новою гілкою листовий вузол з міткою = найбільш поширене значення цільового атрибута в прикладах.
            Інакше
                Додати під новою гілкою піддерево ID3 (${\displaystyle Examples(v_{i})}$, Цільові_Атрибути, Атрибути ${\displaystyle \setminus }$ ${\displaystyle \{A\}}$)
    Повернути корінь

Дерево рішень, побудоване алгоритмом ID3, використовується для визначення відповідності конкретної нуклеотидної пари всередині pre-mRNA послідовності до місця сплайсингу mRNA. Це дерево правильно прогнозує з ймовірністю 95 %.[2]

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

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

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

Алгоритм ID3 навчається на наборі даних ${\displaystyle S}$ для створення дерева рішень, яке зберігається в пам'яті. Під час виконання, це дерево рішень використовується для класифікації нових тестових даних (векторів ознак) шляхом обходу дерева рішень, використовуючи ознаки початкових даних, щоб прийти до листового вузла. Тестові дані класифікуються класом термінального вузла.

Ентропія ${\displaystyle \mathrm {H} {(S)}}$ — це міра невизначеності в наборі даних ${\displaystyle S}$ (тобто ентропія характеризує набір даних ${\displaystyle S}$).

${\displaystyle \mathrm {H} {(S)}=\sum _{x\in X}{-p(x)\log _{2}p(x)}}$

Де

• ${\displaystyle S}$ — набір даних, для якого розраховується ентропія.
• ${\displaystyle X}$ — множина класів у ${\displaystyle S}$.
• ${\displaystyle p(x)}$ — відношення числа елементів у класі ${\displaystyle x}$ до числа елементів у множині ${\displaystyle S}$.

Коли ${\displaystyle \mathrm {H} {(S)}=0}$, множина ${\displaystyle S}$ відмінно класифікована (тобто всі елементи ${\displaystyle S}$ належать до одного класу).

У алгоритмі ID3 ентропія обчислюється для кожного атрибута. На кожній ітерації атрибут з найменшою ентропією використовується для розбиття множини ${\displaystyle S}$. У теорії інформації ентропія вимірює кількість інформації, яку очікують отримати при вимірюванні випадкової величини. Постійна величина має нульову ентропію, оскільки її розподіл відомий. Навпаки, рівномірно розподілена випадкова величина (дискретно або неперервно рівномірна) має максимальну ентропію. Тому, чим більше ентропія у вузлі, тим менше ми маємо відомої інформації про класифікацію даних та більший потенціал для поліпшення класифікації на даному етапі дерева.

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

Інформаційний приріст ${\displaystyle IG(A)}$ — це міра різниці ентропії початкової множини ${\displaystyle S}$ та ентропії множини ${\displaystyle S}$ після розбиття за атрибутом ${\displaystyle A}$.

${\displaystyle IG(S,A)=\mathrm {H} {(S)}-\sum _{t\in T}p(t)\mathrm {H} {(t)}=\mathrm {H} {(S)}-\mathrm {H} {(S|A)}.}$

Де

• ${\displaystyle T}$ – підмножини, створені після розбиття множини ${\displaystyle S}$ за атрибутом ${\displaystyle A}$ такі, що ${\displaystyle S=\bigcup _{t\in T}t}$.
• ${\displaystyle \mathrm {H} (S)}$ – ентропія множини ${\displaystyle S}$.
• ${\displaystyle \mathrm {H} (t)}$ – ентропія підмножини ${\displaystyle t}$.
• ${\displaystyle p(t)}$ – відношення числа елементів у ${\displaystyle t}$ до числа елементів у множині ${\displaystyle S}$.

У ID3 для кожного атрибута замість ентропії може бути обчислений інформаційний приріст. Атрибут з найбільшим інформаційним приростом використовується для розбиття множини ${\displaystyle S}$.