ID3 (алгоритм)

Можливе дерево рішень, побудоване алгоримом ID3. Атрибути розташовуються у вигляді вузлів за здатністю класифікувати приклади. Значення атрибутів представлені гілками.

ID3 (Iterative Dichotomiser 3) — це алгоритм, розроблений Росом Куінланом^[en], який використовується для генерації дерев рішень у машинному навчанні з деякого набору даних.[1] ID3 є попередником алгоритму C4.5 та зазвичай використовується в областях машинного навчання і обробки природної мови.

Алгоритм

На початку роботи алгоритму будується дерево з початковою множиною ${\displaystyle S}$ у кореневому вузлі. На кожній ітерації алгоритму, він перебирає усі невикористані атрибути множини ${\displaystyle S}$ та обчислює ентропію ${\displaystyle \mathrm {H} {(S)}}$ (або інформаційний приріст^[en] ${\displaystyle IG(S)}$) цих атрибутів. Потім він вибирає атрибут з найменшим значенням ентропії (або найбільшим інформаційним виграшем). Потім проводиться розбиття множини ${\displaystyle S}$ за вибраним атрибутом для отримання підмножин даних. (Наприклад, вузол може бути розбитий на дочірні вузли на підставі підмножин населення, вік яких менше 50, від 50 до 100 і більше 100.) Алгоритм продовжує рекурсивно виконуватись на кожній підмножині, враховуючи лише ті атрибути, які раніше не були вибрані.

Рекурсія на підмножині може зупинитися в одному з таких випадків:

• Кожен елемент у підмножині належить до одного класу; в цьому випадку вузол перетворюється в листовий вузол і позначається класом прикладів.
• Більше немає атрибутів для вибору, але приклади ще не належать до одного класу. У цьому випадку вузол стає листовим вузлом і позначається найпоширенішим класом прикладів у підмножині.
• У підмножині немає прикладів: це трапляється, коли жодного прикладу у батьківській множині не знайдено, щоб відповідати певному значенню вибраного атрибута. Прикладом може бути відсутність особи серед населення віком понад 100 років. Потім створюється листовий вузол, який позначається найпоширенішим класом прикладів у множині батьківського вузла.

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

Опис

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}$ для створення дерева рішень, яке зберігається в пам'яті. Під час виконання^[en], це дерево рішень використовується для класифікації нових тестових даних (векторів ознак) шляхом обходу дерева рішень, використовуючи ознаки початкових даних, щоб прийти до листового вузла. Тестові дані класифікуються класом термінального вузла.

Метрики

Ентропія

Ентропія ${\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 — це жадібний евристичний алгоритм, що виконує пошук за першим найкращим збігом для локально оптимальних значень ентропії. Його точність можна поліпшити шляхом попередньої обробки даних.

Інформаційний приріст

Інформаційний приріст^[en] ${\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}$.

Див. також

• Дерева рішень у машинному навчанні
• Модель дерева рішень
• C4.5 (алгоритм)

Примітки

1. Quinlan, J. R. 1986. Induction of Decision Trees. Mach. Learn. 1, 1 (Mar. 1986), 81–106
2. Taggart, Allison J; DeSimone, Alec M; Shih, Janice S; Filloux, Madeleine E; Fairbrother, William G (17 червня 2012). Large-scale mapping of branchpoints in human pre-mRNA transcripts in vivo. Nature Structural & Molecular Biology. 19 (7): 719—721. doi:10.1038/nsmb.2327. ISSN 1545-9993. PMC 3465671. PMID 22705790.

Література

• Mitchell, Tom Michael (1997). Machine Learning. New York, NY: McGraw-Hill. с. 55—58. ISBN 0070428077. OCLC 36417892.
• Grzymala-Busse, Jerzy W. (February 1993). Selected Algorithms of Machine Learning from Examples (PDF). Fundamenta Informaticae. 18(2): 193—207. Архів оригіналу (PDF) за 9 жовтня 2018. Процитовано 16 квітня 2019 — через ResearchGate.

Посилання

• Семінари — http://www2.cs.uregina.ca/ [Архівовано 25 жовтня 2008 у Wayback Machine.]
• Опис та приклади — http://www.cise.ufl.edu/ [Архівовано 5 грудня 2008 у Wayback Machine.]
• Опис та приклади — http://www.cis.temple.edu/ [Архівовано 10 грудня 2008 у Wayback Machine.]
• Дерева рішень та класифікація політичних партій [Архівовано 16 квітня 2019 у Wayback Machine.]
• Реалізація ID3 на Python [Архівовано 20 вересня 2020 у Wayback Machine.]
• Реалізація ID3 на Ruby [Архівовано 9 жовтня 2016 у Wayback Machine.]
• Реалізація ID3 на Common Lisp
• Реалізація ID3 на C#
• Реалізація ID3 на Perl
• Реалізація ID3 на Prolog [Архівовано 5 березня 2016 у Wayback Machine.]
• Реалізація ID3 на C (Коментарі на італійській мові) [Архівовано 5 листопада 2019 у Wayback Machine.]
• Реалізація ID3 на R [Архівовано 30 квітня 2015 у Wayback Machine.]
• Реалізація ID3 на JavaScript [Архівовано 11 червня 2018 у Wayback Machine.]