Перегляд вихідного коду сторінки ID3 (алгоритм)

[[Файл:ID3 algorithm decision tree.png|thumb|Можливе дерево рішень, побудоване алгоримом ID3. Атрибути розташовуються у вигляді вузлів за здатністю класифікувати приклади. Значення атрибутів представлені гілками.]]

'''ID3 (Iterative Dichotomiser 3)'''&nbsp;— це алгоритм, розроблений {{Нп|Рос Куінлан|Росом Куінланом||Ross Quinlan}}, який використовується для генерації [[Дерева рішень у машинному навчанні|дерев рішень у машинному навчанні]] з деякого набору даних.<ref>Quinlan, J. R. 1986. Induction of Decision Trees. Mach. Learn. 1, 1 (Mar. 1986), 81–106</ref> ID3 є попередником [[C4.5 (алгоритм)|алгоритму C4.5]] та зазвичай використовується в областях [[Машинне навчання|машинного навчання]] і [[Обробка природної мови|обробки природної мови]].

== Алгоритм ==
На початку роботи алгоритму будується дерево з початковою множиною <math>S</math> у кореневому вузлі. На кожній [[Ітерація|ітерації]] алгоритму, він перебирає усі невикористані [[Ознака (машинне навчання)|атрибути]] множини <math>S</math> та обчислює [[Інформаційна ентропія|ентропію]] <math>\Eta{(S)}</math> (або {{Нп|Інформаційний приріст у деревах рішень|інформаційний приріст||Information gain in decision trees}} <math>IG(S)</math>) цих атрибутів. Потім він вибирає атрибут з найменшим значенням ентропії (або найбільшим інформаційним виграшем). Потім проводиться розбиття множини <math>S</math> за вибраним атрибутом для отримання підмножин даних. (Наприклад, вузол може бути розбитий на дочірні вузли на підставі підмножин населення, вік яких менше 50, від 50 до 100 і більше 100.) Алгоритм продовжує [[Рекурсія (програмування)|рекурсивно]] виконуватись на кожній підмножині, враховуючи лише ті атрибути, які раніше не були вибрані.

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

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

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

=== Опис ===
# Обчислити [[Інформаційна ентропія|ентропію]] кожного [[Ознака (машинне навчання)|атрибута]] <math>a</math> [[Набір даних|набору даних]] <math>S</math>.
# Розділити множину <math>S</math> на підмножини, використовуючи атрибут, для якого [[Апостеріорна ймовірність|вислідна]] ентропія після розбиття зведена до [[Екстремум|мінімуму]]; або, що еквівалентно, інформаційний приріст є [[Екстремум|максимальним]].
# Створити вузол дерева рішень, що містить цей атрибут.
# Повторити алгоритм на підмножинах, використовуючи атрибути, що залишилися.

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

=== Властивості ===
[[Файл:ID3 decision tree- splicing.png|thumb|Дерево рішень, побудоване алгоритмом ID3, використовується для визначення відповідності конкретної нуклеотидної пари всередині pre-mRNA послідовності до місця [[сплайсинг]]у mRNA. Це дерево правильно прогнозує з ймовірністю 95&nbsp;%.<ref>{{Cite journal|last=Taggart|first=Allison J|last2=DeSimone|first2=Alec M|last3=Shih|first3=Janice S|last4=Filloux|first4=Madeleine E|last5=Fairbrother|first5=William G|date=2012-06-17|title=Large-scale mapping of branchpoints in human pre-mRNA transcripts in vivo|journal=Nature Structural & Molecular Biology|volume=19|issue=7|pages=719–721|doi=10.1038/nsmb.2327|issn=1545-9993|pmc=3465671|pmid=22705790}}</ref>]]

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

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

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

=== Використання ===
Алгоритм ID3 навчається на [[Набір даних|наборі даних]] <math>S</math> для створення дерева рішень, яке зберігається в [[Комп'ютерна пам'ять|пам'яті]]. Під {{Нп|Час виконання (фаза життєвого циклу програми)|час виконання||Run time (program lifecycle phase)}}, це [[Дерево рішень|дерево рішень]] використовується для [[Задача класифікації|класифікації]] нових тестових даних ([[Ознака (машинне навчання)|векторів ознак]]) шляхом обходу дерева рішень, використовуючи ознаки початкових даних, щоб прийти до листового вузла. Тестові дані класифікуються класом термінального вузла.

== Метрики ==

=== Ентропія ===
[[Інформаційна ентропія|Ентропія]] <math>\Eta{(S)}</math>&nbsp;— це міра невизначеності в [[Набір даних|наборі даних]] <math>S</math> (тобто ентропія характеризує набір даних <math>S</math>).

: <math> \Eta{(S)} = \sum_{x \in X}{-p(x) \log_{2}p(x)} </math>

Де
* <math>S</math>&nbsp;— набір даних, для якого розраховується ентропія.
* <math>X</math>&nbsp;— множина класів у <math>S</math>.
* <math>p(x)</math>&nbsp;— [[Пропорційність (математика)|відношення]] числа елементів у класі <math>x</math> до числа елементів у множині <math>S</math>.

Коли <math>\Eta{(S)} = 0</math>, множина <math>S</math> відмінно класифікована (тобто всі елементи <math>S</math> належать до одного класу).

У алгоритмі ID3 ентропія обчислюється для кожного атрибута. На кожній ітерації атрибут з '''найменшою''' ентропією використовується для розбиття множини <math>S</math>. У [[Теорія інформації|теорії інформації]] ентропія вимірює кількість інформації, яку [[Математичне сподівання|очікують]] отримати при вимірюванні [[Випадкова величина|випадкової величини]]. Постійна величина має нульову ентропію, оскільки її [[Розподіл ймовірностей|розподіл]] відомий. Навпаки, рівномірно розподілена випадкова величина ([[Дискретний рівномірний розподіл|дискретно]] або [[Неперервний рівномірний розподіл|неперервно]] рівномірна) має максимальну ентропію. Тому, чим більше ентропія у вузлі, тим менше ми маємо відомої інформації про класифікацію даних та більший потенціал для поліпшення класифікації на даному етапі дерева.

ID3&nbsp;— це [[Жадібний алгоритм|жадібний]] [[Евристичний алгоритм|евристичний]] алгоритм, що виконує [[Пошук за першим найкращим збігом|пошук за першим найкращим збігом]] для локально оптимальних значень ентропії. Його точність можна поліпшити шляхом попередньої обробки даних.

=== Інформаційний приріст ===
{{Нп|Інформаційний приріст у деревах рішень|Інформаційний приріст||Information gain in decision trees}} <math>IG(A)</math>&nbsp;— це міра різниці ентропії початкової множини <math>S</math> та ентропії множини <math>S</math> після розбиття за атрибутом <math>A</math>.

: <math> IG(S, A) = \Eta{(S)} - \sum_{t \in T} p(t)\Eta{(t)}
    = \Eta{(S)} - \Eta{(S|A)}. </math>

Де
* <math>T</math>&nbsp;– підмножини, створені після розбиття множини <math>S</math> за атрибутом <math>A</math> такі, що <math>S = \bigcup_{t \in T} t</math>.
* <math>\Eta(S)</math>&nbsp;– ентропія множини <math>S</math>.
* <math>\Eta(t)</math>&nbsp;– ентропія підмножини <math>t</math>.
* <math>p(t)</math>&nbsp;– [[Пропорційність (математика)|відношення]] числа елементів у <math>t</math> до числа елементів у множині <math>S</math>.

У ID3 для кожного атрибута замість ентропії може бути обчислений інформаційний приріст. Атрибут з '''найбільшим''' інформаційним приростом використовується для розбиття множини <math>S</math>.

== Див. також ==
* [[Дерева рішень у машинному навчанні]]
* [[Модель дерева рішень]]
* [[C4.5 (алгоритм)]]

== Примітки ==
{{примітки}}

== Література ==
* {{Cite book|url=https://www.worldcat.org/oclc/36417892|title=Machine Learning|last=Mitchell|first=Tom Michael|publisher=McGraw-Hill|year=1997|isbn=0070428077|location=New York, NY|pages=55-58|oclc=36417892}}
* {{Cite journal|last=Grzymala-Busse|first=Jerzy W.|date=February 1993|title=Selected Algorithms of Machine Learning from Examples|url=https://people.eecs.ku.edu/~jerzygb/j24-sel.pdf|journal=Fundamenta Informaticae|volume=18(2)|pages=193-207|via=ResearchGate|accessdate=16 квітня 2019|archive-date=9 жовтня 2018|archive-url=https://web.archive.org/web/20181009092708/https://people.eecs.ku.edu/~jerzygb/j24-sel.pdf}}

== Посилання ==
* Семінари&nbsp;— [http://www2.cs.uregina.ca/~hamilton/courses/831/notes/ml/dtrees/4_dtrees1.html http://www2.cs.uregina.ca/] {{Webarchive|url=https://web.archive.org/web/20081025192401/http://www2.cs.uregina.ca/~hamilton/courses/831/notes/ml/dtrees/4_dtrees1.html |date=25 жовтня 2008 }}
* Опис та приклади&nbsp;— [http://www.cise.ufl.edu/~ddd/cap6635/Fall-97/Short-papers/2.htm http://www.cise.ufl.edu/] {{Webarchive|url=https://web.archive.org/web/20081205001124/http://www.cise.ufl.edu/~ddd/cap6635/Fall-97/Short-papers/2.htm |date=5 грудня 2008 }}
* Опис та приклади&nbsp;— [http://www.cis.temple.edu/~ingargio/cis587/readings/id3-c45.html http://www.cis.temple.edu/] {{Webarchive|url=https://web.archive.org/web/20081210074304/http://www.cis.temple.edu/~ingargio/cis587/readings/id3-c45.html |date=10 грудня 2008 }}
* [http://jeremykun.com/2012/10/08/decision-trees-and-political-party-classification/ Дерева рішень та класифікація політичних партій] {{Webarchive|url=https://web.archive.org/web/20190416121613/https://jeremykun.com/2012/10/08/decision-trees-and-political-party-classification/ |date=16 квітня 2019 }}
* [https://github.com/tofti/python-id3-trees Реалізація ID3 на Python] {{Webarchive|url=https://web.archive.org/web/20200920120208/https://github.com/tofti/python-id3-trees |date=20 вересня 2020 }}
* [http://ai4r.org/machineLearning.html Реалізація ID3 на Ruby] {{Webarchive|url=https://web.archive.org/web/20161009053755/http://www.ai4r.org/machineLearning.html |date=9 жовтня 2016 }}
* [https://web.archive.org/web/20171225121804/http://www.pvv.ntnu.no/~oyvinht/static/OSS/cl-id3/ Реалізація ID3 на Common Lisp]
* [https://web.archive.org/web/20061109050158/http://www.codeproject.com/cs/algorithms/id3.asp Реалізація ID3 на C#]
* [https://metacpan.org/module/AI::DecisionTree Реалізація ID3 на Perl]
* [http://ftp.cs.stanford.edu/cs/robotics/shoham/prolog.tar.Z Реалізація ID3 на Prolog] {{Webarchive|url=https://web.archive.org/web/20160305152357/http://ftp.cs.stanford.edu/cs/robotics/shoham/prolog.tar.Z |date=5 березня 2016 }}
* [http://id3alg.altervista.org Реалізація ID3 на C (Коментарі на італійській мові)] {{Webarchive|url=https://web.archive.org/web/20191105090753/http://id3alg.altervista.org/ |date=5 листопада 2019 }}
* [http://ipub.ch/id3-with-data-tree Реалізація ID3 на R] {{Webarchive|url=https://web.archive.org/web/20150430050331/http://ipub.ch/id3-with-data-tree/ |date=30 квітня 2015 }}
* [https://github.com/willkurt/ID3-Decision-Tree Реалізація ID3 на JavaScript] {{Webarchive|url=https://web.archive.org/web/20180611001659/https://github.com/willkurt/ID3-Decision-Tree |date=11 червня 2018 }}

[[Категорія:Алгоритми класифікації]]
[[Категорія:Дерева (структури даних)]]