Алгоритм ID3

В обучении дерева решений ID3 ( Итеративный дихотомизатор 3 ) — это алгоритм, изобретенный Россом Куинланом. ^[1] используется для создания дерева решений из набора данных. ID3 является предшественником алгоритма C4.5 и обычно используется в областях машинного обучения и обработки естественного языка .

Алгоритм

Алгоритм ID3 начинается с исходного набора $S$ в качестве корневого узла . На каждой итерации алгоритма он перебирает каждый неиспользуемый атрибут набора. $S$ и вычисляет энтропию $\mathrm {H} {(S)}$ или получение информации $IG(S)$ этого атрибута. Затем он выбирает атрибут, который имеет наименьшее значение энтропии (или наибольший прирост информации). Набор $S$ затем разбивается или секционируется по выбранному атрибуту для создания поднаборов данных. (Например, узел можно разделить на дочерние узлы на основе подмножеств населения, чей возраст меньше 50, от 50 до 100 и больше 100.) Алгоритм продолжает рекурсивно работать с каждым подмножеством, рассматривая только атрибуты, которые никогда не учитываются. выбрано ранее.

Рекурсия на подмножестве может остановиться в одном из следующих случаев:

каждый элемент подмножества принадлежит одному и тому же классу; в этом случае узел превращается в листовой узел и помечается классом примеров.
атрибутов для выбора больше нет, но примеры по-прежнему не принадлежат одному и тому же классу. В этом случае узел делается листовым узлом и помечается наиболее распространенным классом примеров в подмножестве.
, в подмножестве нет примеров что происходит, когда в родительском наборе не найден пример, соответствующий определенному значению выбранного атрибута. человека Примером может служить отсутствие среди населения в возрасте старше 100 лет. Затем создается листовой узел и помечается наиболее распространенным классом примеров в наборе родительского узла.

На протяжении всего алгоритма дерево решений строится с каждым нетерминальным узлом ( внутренним узлом ), представляющим выбранный атрибут , по которому были разделены данные, и конечными узлами (листовыми узлами), представляющими метку класса последнего подмножества этой ветви.

Краткое содержание

Вычислить энтропию каждого атрибута $a$ набора данных $S$ .
Разделить («разделить») набор $S$ на подмножества с использованием того признака, для которого результирующая энтропия после разделения минимизирована ; или, что то же самое, прирост информации максимален .
Создайте узел дерева решений , содержащий этот атрибут.
Рекурсивно работать с подмножествами, используя оставшиеся атрибуты.

Характеристики

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

ID3 может соответствовать обучающим данным. Чтобы избежать переобучения, следует отдавать предпочтение меньшим деревьям решений, чем большим. ^{[ нужны дальнейшие объяснения ]} Этот алгоритм обычно создает небольшие деревья, но он не всегда создает минимально возможное дерево решений.

ID3 сложнее использовать для непрерывных данных, чем для факторизованных данных (факторизованные данные имеют дискретное количество возможных значений, что уменьшает количество возможных точек ветвления). Если значения любого заданного атрибута непрерывны , то существует гораздо больше мест для разделения данных по этому атрибуту, и поиск наилучшего значения для разделения может занять много времени.

Использование

Алгоритм ID3 используется при обучении на наборе данных. $S$ для создания дерева решений , которое хранится в памяти . Во время выполнения это дерево решений используется для классификации новых тестовых случаев ( векторов признаков ) путем обхода дерева решений с использованием особенностей исходных данных для достижения конечного узла.

Метрики ID3

Энтропия

Энтропия $\mathrm {H} {(S)}$ является мерой степени неопределенности в наборе (данных) $S$ (т.е. энтропия характеризует набор (данных) $S$ ).

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

Где,

$S$ $S$ – Текущий набор данных , для которого рассчитывается энтропия.
- Это меняется на каждом этапе алгоритма ID3 либо на подмножество предыдущего набора в случае разделения по атрибуту, либо на «родственный» раздел родительского элемента, если рекурсия завершилась ранее.
$X$ — Набор занятий в $S$
$p(x)$ – Пропорция количества элементов в классе $x$ к количеству элементов в наборе $S$

Когда $\mathrm {H} {(S)}=0$ , набор $S$ идеально классифицирован (т.е. все элементы в $S$ относятся к одному классу).

В ID3 энтропия рассчитывается для каждого оставшегося атрибута. Атрибут с наименьшей энтропией используется для разделения множества. $S$ на этой итерации. Энтропия в теории информации измеряет, сколько информации ожидается получить при измерении величины случайной ; как таковой, его также можно использовать для количественного определения суммы, для которой неизвестно распределение значений величины. Постоянная прекрасно величина имеет нулевую энтропию, так как ее распределение известно . Напротив, равномерно распределенная случайная величина ( дискретно или непрерывно однородная) максимизирует энтропию. Следовательно, чем больше энтропия в узле, тем меньше информации известно о классификации данных на этом этапе дерева; и, следовательно, тем больше потенциал для улучшения классификации здесь.

Таким образом, ID3 представляет собой жадную эвристику , выполняющую энтропии в порядке очереди значений поиск локально оптимальных . Его точность можно повысить путем предварительной обработки данных.

Получение информации

Получение информации $IG(A)$ является мерой разницы в энтропии до и после набора $S$ делится по атрибуту $A$ . Другими словами, насколько велика неопределенность в $S$ было уменьшено после разделения набора $S$ по атрибуту $A$ .

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

Где,

$\mathrm {H} (S)$ – Энтропия множества $S$
$T$ – Подмножества, созданные из набора разделения $S$ по атрибуту $A$ такой, что $S=\bigcup _{t\in T}t$
$p(t)$ – Пропорция количества элементов в $t$ к количеству элементов в наборе $S$
$\mathrm {H} (t)$ – Энтропия подмножества $t$

В ID3 можно рассчитать прирост информации (вместо энтропии) для каждого оставшегося атрибута. Атрибут с наибольшим приростом информации используется для разделения набора. $S$ на этой итерации.

См. также

Ссылки

^ Куинлан, младший 1986. Индукция деревьев решений. Мах. Учиться. 1, 1 (март 1986 г.), 81–106.
^ Таггарт, Эллисон Дж; Дезимоун, Алек М; Ши, Дженис С; Филлу, Мадлен Э; Фэйрбратер, Уильям Дж. (17 июня 2012 г.). «Крупномасштабное картирование точек ветвления в транскриптах пре-мРНК человека in vivo» . Структурная и молекулярная биология природы . 19 (7): 719–721. дои : 10.1038/nsmb.2327 . ISSN 1545-9993 . ПМЦ 3465671 . ПМИД 22705790 .

Дальнейшее чтение

Митчелл, Том Майкл (1997). Машинное обучение . Нью-Йорк, штат Нью-Йорк: МакГроу-Хилл. стр. 55–58 . ISBN 0070428077 . OCLC 36417892 .
Гржимала-Буссе, Ежи В. (февраль 1993 г.). «Избранные алгоритмы машинного обучения на примерах» (PDF) . Фундамента информатики . 18 (2): 193–207 – через ResearchGate.

Внешние ссылки

Семинары – http://www2.cs.uregin.ca/
Описание и примеры – http://www.cite.ufl.edu/
Описание и примеры – http://www.cis.temple.edu/
Деревья решений и классификация политических партий

[1] Куинлан, младший 1986. Индукция деревьев решений. Мах. Учиться. 1, 1 (март 1986 г.), 81–106.

[2] Таггарт, Эллисон Дж; Дезимоун, Алек М; Ши, Дженис С; Филлу, Мадлен Э; Фэйрбратер, Уильям Дж. (17 июня 2012 г.). «Крупномасштабное картирование точек ветвления в транскриптах пре-мРНК человека in vivo» . Структурная и молекулярная биология природы . 19 (7): 719–721. дои : 10.1038/nsmb.2327 . ISSN 1545-9993 . ПМЦ 3465671 . ПМИД 22705790 .

[1]

[2]