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

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

Алгоритм

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

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

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

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

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

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

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

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

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

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

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

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

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

Метрики ID3

Энтропия

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

ЧАС ( С ) = ∑ х ∈ Х − п ( х ) бревно 2 ⁡ п ( х ) {\displaystyle \mathrm {H} {(S)}=\sum _{x\in X}{-p(x)\log _{2}p(x)}}

Где,

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

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

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

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

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

Прирост информации — это мера разницы в энтропии до и после разделения набора по атрибуту . Другими словами, насколько уменьшилась неопределенность в после разделения набора по атрибуту . я Г ( А ) {\displaystyle ИГ(А)} С {\displaystyle S} А {\displaystyle А} С {\displaystyle S} С {\displaystyle S} А {\displaystyle А}

я Г ( С , А ) = ЧАС ( С ) − ∑ т ∈ Т п ( т ) ЧАС ( т ) = ЧАС ( С ) − ЧАС ( С | А ) . {\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 Т} – Подмножества, созданные путем разбиения набора по атрибуту таким образом, что С {\displaystyle S} А {\displaystyle А} С = ⋃ т ∈ Т т {\displaystyle S=\bigcup _{t\in T}t}
  • п ( т ) {\displaystyle p(t)} – Отношение числа элементов к числу элементов в наборе т {\displaystyle т} С {\displaystyle S}
  • ЧАС ( т ) {\displaystyle \mathrm {H} (т)} – Энтропия подмножества т {\displaystyle т}

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

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

Ссылки

  1. ^ Куинлан, Дж. Р. 1986. Индукция деревьев решений. Mach. Learn. 1, 1 (март 1986), 81–106
  2. ^ Taggart, Allison J; DeSimone, Alec M; Shih, Janice S; Filloux, Madeleine E; Fairbrother, William G (2012-06-17). "Крупномасштабное картирование точек ветвления в транскриптах пре-мРНК человека in vivo". Nature Structural & Molecular Biology . 19 (7): 719– 721. doi :10.1038/nsmb.2327. ISSN  1545-9993. PMC 3465671.  PMID 22705790  .

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

  • Митчелл, Том Майкл (1997). Машинное обучение . Нью-Йорк, Нью-Йорк: McGraw-Hill. С. 55–58. ISBN 0070428077. OCLC  36417892.
  • Гржимала-Буссе, Ежи В. (февраль 1993 г.). «Избранные алгоритмы машинного обучения на примерах» (PDF) . Fundamenta Informaticae . 18 (2): 193–207 – через ResearchGate.
  • Семинары – http://www2.cs.uregina.ca/
  • Описание и примеры – http://www.cise.ufl.edu/
  • Описание и примеры – http://www.cis.temple.edu/
  • Деревья решений и классификация политических партий
Получено с "https://en.wikipedia.org/w/index.php?title=ID3_algorithm&oldid=1232052944"