Алгоритм ID3 - ID3 algorithm

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

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

Алгоритм

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

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

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

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

Резюме

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

Псевдокод

ID3 (Примеры, Target_Attribute, Атрибуты) Создайте корневой узел для дерева. Если все примеры положительны, Верните одноузловой корень дерева с меткой = +. Если все примеры отрицательны, верните одноузловой корень дерева с меткой = -. Если количество прогнозируемых атрибутов пусто, то возвращается корень дерева с одним узлом, с меткой = наиболее распространенное значение целевого атрибута в примерах. В противном случае Begin A ← Атрибут, который лучше всего классифицирует примеры. Атрибут дерева решений для Root = A. Для каждого возможного значения  $v я$ , of A, Добавьте новую ветку дерева под Root, соответствующую тесту A =  $v я$ . Пусть Примеры ( $v я$ ) быть подмножеством примеров, которые имеют значение  $v я$  для A Если Примеры ( $v я$ ) пуста. Затем под этой новой ветвью добавьте листовой узел с меткой = наиболее распространенное целевое значение в примерах. Еще ниже этой новой ветки добавьте поддерево ID3 (Примеры ( $v я$ ), Target_Attribute, Attributes - {A}) End Return Root

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

Сгенерированное ID3 дерево решений используется для определения того, соответствует ли конкретная пара нуклеотидов в последовательности пре-мРНК сайту сплайсинга мРНК. Было показано, что это дерево дает 95% правильных прогнозов.^[2]

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

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

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

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

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

Показатели ID3

Энтропия

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

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

Где,

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

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

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

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

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

Получение информации ${ Displaystyle IG (A)}$ это мера разницы в энтропии от до и после множества ${ displaystyle S}$ разбивается по атрибуту ${ displaystyle 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 mathrm {H} (S)}$ - Энтропия набора ${ displaystyle S}$
${ displaystyle T}$ - Подмножества, созданные из набора разделения ${ displaystyle S}$ по атрибуту ${ displaystyle A}$ такой, что ${ Displaystyle S = bigcup _ {т in T} т}$
${ displaystyle p (t)}$ - Пропорция количества элементов в ${ displaystyle t}$ к количеству элементов в наборе ${ displaystyle S}$
${ Displaystyle mathrm {H} (т)}$ - Энтропия подмножества ${ displaystyle t}$

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

Смотрите также

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

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

внешняя ссылка

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

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

[1]

[2]

Алгоритм ID3 - ID3 algorithm

Содержание