Розглянемо докладно ID3 алгоритму класифікації. Дуже просто, ID3 будує дерево рішень з фіксованим набором прикладів. В результаті дерево використовується для класифікації майбутніх зразків. Наприклад має кілька атрибутів і належить до класу (наприклад, так чи ні). Листя дерева рішень містити ім'я класу, в той час як не-лист вузол є рішенням вузла. Рішення вузол є атрибутом тесту з кожної гілки (в іншій дерево рішень), що є можливим значенням атрибута. ID3 використовує інформацію посилення, щоб допомогти йому вирішити, який атрибут входить у вирішенні вузла. Перевага навчання дерева рішень є те, що програми, а не знання інженера, викликає знань від експерта.
Вступ
Дж. Росс Quinlan спочатку розроблений ID3 в Університеті Сіднея. Він вперше представлений ID3 в 1975 році в книзі, Machine Learning, вип. 1, немає. 1. ID3 базується Концепція системи навчання (CLS) алгоритм. Основний алгоритм CLS над безліччю підготовки випадків C:
Крок 1: Якщо всі екземпляри в C позитивні, то створіть YES вузлів і зупинився.
|
|
Якщо всі екземпляри в C негативні, створити NO вузлів і зупинився.
В іншому випадку виберіть функцію, F зі значеннями v1,..., Vn і створити рішення вузла.
Крок 2: Розділ підготовки випадках, C на підмножини, C1, C2,..., Cn відповідно до значень В.
Крок 3: застосувати алгоритм рекурсивно для кожного з множин Ci.
Відзначимо, що тренер (експерт) вирішує, які маються для вибору.
ID3 покращує CLS, додавши евристичного вибору функції. ID3 пошуку по атрибутах підготовки випадках і екстракти атрибут, який відділяє кращих наведені приклади. Якщо атрибут прекрасно класифікує навчання встановлюється потім ID3 зупинках, в іншому випадку рекурсивно діє на N (де N = число можливих значень атрибутів) розподіляють підмножини, щоб отримати свої "кращі" атрибут. Алгоритм використовує жадібний пошук, тобто, він вибирає кращий атрибут і ніколи не оглядається назад, щоб переглянути раніше вибори.