Получение информации (дерево решений)

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

Прирост информации о случайной величине X, полученный в результате наблюдения за случайной величиной A, принимающей значение ⁠ $A=a$ ⁠ определен $IG_{X,A}{(X,a)}=D_{\text{KL}}{\left(P_{X}{(x|a)}\|P_{X}{(x|I)}\right)},$ расхождение Кульбака – Лейблера априорного распределения $P_{X}{(x|I)}$ для x из апостериорного распределения $P_{X|A}{(x|a)}$ для x с учетом a .

Ожидаемая ценность прироста информации – это взаимная информация ⁠ $I(X;A)$ ⁠ X путем и A т.е. уменьшение энтропии X , достигаемое изучения состояния случайной величины A. –

чтобы наиболее быстро сузить состояние X. В машинном обучении эту концепцию можно использовать для определения предпочтительной последовательности атрибутов для исследования , Такая последовательность (которая зависит от результата исследования предыдущих атрибутов на каждом этапе) называется деревом решений и применяется в области машинного обучения, известной как обучение дерева решений . Обычно атрибут с высоким уровнем взаимной информации предпочтительнее других атрибутов. ^{[ почему? ]}

Общее определение

В общих чертах, ожидаемый прирост информации — это уменьшение информационной энтропии $Η$ от предыдущего состояния до состояния, которое принимает некоторую информацию как заданную:

IG(T,a)=\mathrm {H} {(T)}-\mathrm {H} {(T|a)},

где $\mathrm {H} {(T|a)}$ это энтропия условная $T$ учитывая значение атрибута $a$ .

Это интуитивно правдоподобно при интерпретации энтропии $Н$ как меры неопределенности случайной величины. $T$ : изучая (или предполагая) $a$ о $T$ , наша неуверенность в $T$ снижается (т.е. $IG(T,a)$ положительно), если, конечно, $T$ не зависит от $a$ , в этом случае $\mathrm {H} (T,a)=\mathrm {H} (T)$ , значение $IG(T,a)=0$ .

Формальное определение

Пусть $T$ обозначает набор обучающих примеров , каждый из которых имеет форму $({\textbf {x}},y)=(x_{1},x_{2},x_{3},...,x_{k},y)$ где $x_{a}\in \mathrm {vals} (a)$ это ценность $a^{\text{th}}$ или особенность примера атрибут ${\textbf {x}}$ и $y$ — соответствующая метка класса. Прирост информации для атрибута $a$ определяется в терминах энтропии Шеннона. $\mathrm {H} (-)$ следующее. Для значения $v,$ принимаемого атрибутом $a$ , пусть $S_{a}{(v)}=\{{\textbf {x}}\in T|x_{a}=v\}$ быть определен как набор обучающих входных данных $T,$ для которых атрибут $a$ равен $v$ . Тогда информационный выигрыш $T$ для атрибута $a$ представляет собой разницу между априорной энтропией Шеннона $\mathrm {H} (T)$ обучающего набора и условной энтропии $\mathrm {H} {(T|a)}$ .

$\mathrm {H} (T|a)=\sum _{v\in \mathrm {vals} (a)}{{\frac {|S_{a}{(v)}|}{|T|}}\cdot \mathrm {H} \left(S_{a}{\left(v\right)}\right)}.$

IG(T,a)=\mathrm {H} (T)-\mathrm {H} (T|a)

Взаимная информация равна общей энтропии атрибута, если для каждого значения атрибута можно выполнить уникальную классификацию результирующего атрибута. В этом случае относительные энтропии, вычтенные из полной энтропии, равны 0. В частности, значения $v\in vals(a)$ определяет разделение данных обучающего набора $T$ на взаимоисключающие и всеобъемлющие подмножества , вызывая категориальное распределение вероятностей ${\textstyle P_{a}{(v)}}$ о ценностях ${\textstyle v\in vals(a)}$ атрибута $a$ . Распределение дано ${\textstyle P_{a}{(v)}:={\frac {|S_{a}{(v)}|}{|T|}}}$ . В этом представлении прирост информации от $T$ при заданном $a$ может быть определен как разница между безусловной энтропией Шеннона $T$ и ожидаемой энтропией $T$ , обусловленной $a$ , где математическое ожидание берется относительно индуцированного распределения значений $а$ . ${\begin{alignedat}{2}IG(T,a)&=\mathrm {H} (T)-\sum _{v\in \mathrm {vals} (a)}{P_{a}{(v)}\mathrm {H} \left(S_{a}{(v)}\right)}\\&=\mathrm {H} (T)-\mathbb {E} _{P_{a}}{\left[\mathrm {H} {(S_{a}{(v)})}\right]}\\&=\mathrm {H} (T)-\mathrm {H} {(T|a)}.\end{alignedat}}$

Еще один взгляд на получение информации с примером

Для лучшего понимания получения информации давайте разберем его. Как мы знаем, прирост информации – это уменьшение информационной энтропии, что такое энтропия? По сути, энтропия — это мера примеси или неопределенности в группе наблюдений. В инженерных приложениях информация аналогична сигналу, а энтропия аналогична шуму. Он определяет, как дерево решений выбирает разделение данных. ^{[ 1 ]} Крайняя левая фигура ниже очень загрязнена и имеет высокую энтропию, что соответствует более высокому беспорядку и более низкой ценности информации. По мере движения вправо энтропия уменьшается, а ценность информации увеличивается.

Теперь ясно, что прирост информации — это мера того, сколько информации о классе предоставляет функция. Давайте визуализируем получение информации в виде дерева решений, как показано справа:

Узел t является родительским узлом, а подузлы t _L и t _R являются дочерними узлами. В этом случае родительский узел t имеет коллекцию раковых и нераковых образцов, обозначенных как C и NC соответственно. Мы можем использовать полученную информацию, чтобы определить, насколько хорошо разделение узлов в дереве решений. С точки зрения энтропии прирост информации определяется как:

Прирост = (Энтропия родительского узла) – (средняя энтропия дочерних узлов) ^{[ 2 ]}

( я )

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

Образцы	Мутация 1	Мутация 2	Мутация 3	Мутация 4
С1	1	1	1	0
С2	1	1	0	1
С3	1	0	1	1
С4	0	1	1	0
NC1	0	0	0	0
NC2	0	1	0	0
NC3	1	1	0	0

В этом наборе данных 1 означает, что в образце есть мутация (Истина), а 0 означает, что в образце ее нет (Ложь). Образец с буквой C означает, что он подтвержден как раковый, а NC означает, что он не раковый. Используя эти данные, можно создать дерево решений, используя полученную информацию для определения кандидатов на разделение для каждого узла.

На следующем этапе энтропия в родительском узле t приведенного выше простого дерева решений вычисляется как:

H( t ) = −[ p _C,t log ₂ ( p _C,t ) + p _NC,t log ₂ ( p _NC,t )] ^{[ 3 ]}
где,
вероятность выбора выборки класса «C» в узле t, p _C,t = n ( t, C) / n ( t ),
вероятность выбора выборки класса 'NC' в узле t, p _NC,t = n ( t, NC) / n ( t ),

n ( t ), n ( t, C) и n ( t, NC) — общее количество выборок, выборок «C» и выборок «NC» в узле t соответственно .

Используя это на примере обучающего набора, процесс поиска информации начинается с $\mathrm {H} {(t)}$ для мутации 1 выглядит следующим образом:

р _{С, t} = 4/7

р _{НЗ, t} = 3/7

\mathrm {H} {(t)}

= -(4/7 × log ₂ (4/7) + 3/7 × log ₂ (3/7)) = 0,985

Примечание : $\mathrm {H} {(t)}$ будет одинаковым для всех мутаций в корне.

Относительно высокое значение энтропии $\mathrm {H} {(t)}=0.985$ (1 — оптимальное значение) предполагает, что корневой узел сильно загрязнен и составляющие входных данных в корневом узле будут выглядеть как крайняя левая фигура на приведенной выше энтропийной диаграмме . Однако такой набор данных хорош для изучения атрибутов мутаций, используемых для разделения узла. В определенном узле, когда возникает однородность составляющих входных данных (как показано на крайнем правом рисунке на приведенной выше диаграмме энтропии), набор данных больше не будет пригоден для обучения.

Двигаясь дальше, энтропия в левом и правом дочерних узлах приведенного выше дерева решений вычисляется по формулам:

H( t _L ) = -[ п _C,L log ₂ ( п _C,L ) + п _NC,L log ₂ ( п _NC,L )] ^{[ 1 ]}

H( t _R ) = −[ п _C,R log ₂ ( п _C,R ) + п _NC,R log ₂ ( п _NC,R )] ^{[ 1 ]}

где,

вероятность выбора выборки класса «C» в левом дочернем узле , p _C,L = n ( t _L , C) / n ( t _L ),

вероятность выбора выборки класса 'NC' в левом дочернем узле , p _NC,L = n ( t _L , NC) / n ( t _L ),

вероятность выбора выборки класса «C» в правом дочернем узле , p _C,R = n ( t _R , C) / n ( t _R ),

вероятность выбора выборки класса 'NC' в правом дочернем узле , p _NC,R = n ( t _R , NC) / n ( t _R ),

n ( t _L ), n ( t _L , C) и n ( t _L , NC) — общее количество выборок, выборок «C» и выборок «NC» в левом дочернем узле соответственно,

n ( t _R ), n ( t _R , C) и n ( t _R , NC) — общее количество выборок, выборок «C» и выборок «NC» в правом дочернем узле соответственно .

Используя эти формулы, H(t _L ) и H(t _R ) для мутации 1 показаны ниже:

H( t _L ) = -(3/4 × log ₂ (3/4) + 1/4 × log ₂ (1/4)) = 0,811

H( t _R ) = -(1/3 × log ₂ (1/3) + 2/3 × log ₂ (2/3)) = 0,918

После этого средняя энтропия дочерних узлов из-за разделения в узле t вышеуказанного дерева решений вычисляется как:

ЧАС ( s , т ) знак равно п _L ЧАС ( т _L ) + п _р ЧАС ( т _р )
где,
вероятность выборки у левого ребенка, P _L = n ( t _L ) / n ( t ),
вероятность выборки у правого ребенка, P _R = n ( t _R ) / n ( t ),

H(s,t) вместе с P _L и PR _{Наконец ,} для мутации 1 выглядит следующим образом:

П _Л = 4/7

П _Р = 3/7

H( s, t ) = (4/7 × 0,811) + (3/7 × 0,918) = 0,857

Таким образом, по определению из уравнения (i):

(Прирост информации) = H( t ) - H( s , t )

После всех шагов, коэффициент усиления( s ), где s — возможное разделение для примера, равен:

выигрыш( ы ) = 0,985 – 0,857 = 0,128

Использование того же набора формул с тремя другими мутациями приводит к таблице расщеплений-кандидатов, ранжированных по приросту информации:

Мутация	Прирост(ы)
3	0.522
4	0.292
1	0.128
2	0.006

Мутацией, которая предоставит наиболее полезную информацию, будет Мутация 3, поэтому она будет использоваться для разделения корневого узла дерева решений. Корень можно разделить, и все образцы можно передать и добавить к дочерним узлам. Слева показано дерево, описывающее разделение.

Образцы, находящиеся в левом узле дерева, будут классифицированы деревом как раковые, а образцы справа — нераковые. Это дерево относительно точно классифицирует образцы, которые использовались для его построения (что является случаем переобучения ), но оно все равно будет неправильно классифицировать образец C2. Чтобы исправить это, дерево можно снова разбить на дочерние узлы, чтобы, возможно, добиться чего-то еще более точного.

Чтобы разделить правильный узел, необходимо снова рассчитать прирост информации для всех возможных вариантов разделения, которые не использовались для предыдущих узлов. Итак, на этот раз единственными вариантами являются мутации 1, 2 и 4.

Примечание : $\mathrm {H} {(t)}$ На этот раз все по-другому, поскольку у правого дочернего элемента есть только четыре образца.

П _{С, t} = 1/4

П _{НЗ, t} = 3/4

\mathrm {H} {(t)}

= -(1/4 × log ₂ (1/4) + 3/4 × log ₂ (3/4)) = 0,811

Из этого нового $\mathrm {H} {(t)}$ , кандидаты на расщепления могут быть рассчитаны по тем же формулам, что и корневой узел:

Мутация	Выигрыш( а )
4	0.811
1	0.311
2	0.123

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

Чтобы разделить левый узел, процесс будет таким же, за исключением того, что для проверки потребуется только 3 выборки. Иногда узел может вообще не нуждаться в разбиении, если это чистый набор , где все образцы в узле являются просто раковыми или нераковыми. Разделение узла может привести к тому, что дерево будет более неточным, и в этом случае оно не будет разбито.

Теперь дерево достигнет 100% точности, если протестировать образцы, которые использовались для его построения. Однако это не очень хорошая идея, поскольку дерево будет соответствовать данным. Лучше всего попробовать протестировать дерево на других образцах, не входящих в исходный набор. Два внешних образца приведены ниже:

Образцы	Мутация 1	Мутация 2	Мутация 3	Мутация 4
NC10	0	1	0	0
С15	1	1	0	0

Следуя дереву, NC10 был классифицирован правильно, а C15 был классифицирован как NC. Для других образцов это дерево уже не будет на 100% точным. Однако это можно было бы улучшить с помощью таких опций, как увеличение глубины дерева или увеличение размера обучающего набора.

Преимущества

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

Концепция функции получения информации подпадает под алгоритм C4.5 для создания деревьев решений и выбора оптимального разделения для узла дерева решений. ^{[ 1 ]} Некоторые из его преимуществ включают в себя:

Он может работать как с непрерывными, так и с дискретными переменными.
Из-за фактора –[p ∗ log(p)] в определении энтропии, данном выше, листовым узлам с небольшим количеством экземпляров присваивается меньший вес, и это способствует разделению остальных данных на более крупные, но однородные группы. Таким образом, по мере того, как мы копаем глубже в глубину дерева, набор данных становится более однородным. Этот подход обычно более стабилен и выбирает наиболее эффективные функции на узлах. ^{[ 4 ]}

Недостатки и решения

Хотя получение информации обычно является хорошим показателем для определения релевантности атрибута, оно не является идеальным. Заметная проблема возникает, когда получение информации применяется к атрибутам, которые могут принимать большое количество различных значений. Например, предположим, что кто-то строит дерево решений для некоторых данных, описывающих клиентов компании. Полученная информация часто используется для принятия решения о том, какие из атрибутов являются наиболее релевантными, поэтому их можно проверить вблизи корня дерева. Одним из входных атрибутов может быть номер участника клиента, если он является участником программы членства компании. Этот атрибут имеет высокую взаимную информацию, поскольку он однозначно идентифицирует каждого клиента, но мы не хотим включать его в дерево решений. Решение о том, как обращаться с клиентом на основе его членского номера, вряд ли будет распространяться на клиентов, которых мы раньше не видели ( переоснащение ). Эта проблема также может возникнуть, если тестируемые образцы имеют несколько атрибутов с множеством различных значений. В этом случае это может привести к тому, что информационная выгода каждого из этих атрибутов будет намного выше, чем у тех, у которых не так много различных значений.

Чтобы решить эту проблему, Росс Куинлан предложил вместо этого выбирать атрибут с самым высоким коэффициентом прироста информации среди атрибутов, чей прирост информации средний или выше. ^{[ 5 ]} Это смещает дерево решений против рассмотрения атрибутов с большим количеством различных значений, но при этом не дает несправедливого преимущества атрибутам с очень низкой информационной ценностью, поскольку информационная ценность выше или равна приросту информации. ^{[ 6 ]}

См. также

Получение информации в более широком смысле
Обучение дереву решений
Информационное содержание , отправная точка теории информации и основа энтропии Шеннона.
Коэффициент получения информации
Алгоритм ID3
- Алгоритм C4.5
Неожиданный анализ

Ссылки

^ Jump up to: ^а ^б ^с ^д Лароуз, Дэниел Т. (2014). Обнаружение знаний в данных: введение в интеллектуальный анализ данных . Хобокен, Нью-Джерси: Уайли . стр. 174–179. ISBN 9780470908747 .
^ Jump up to: ^а ^б Гопалан, Бхуванесвари (10 декабря 2020 г.). «Что такое энтропия и прирост информации? Как они используются для построения деревьев решений?» . Нампи Ниндзя . Проверено 28 ноября 2021 г.
^ Джотикумар, Р. (2018). «Прогнозирование продолжительности жизни пациента с сердечным приступом с использованием улучшенного алгоритма классификации C4.5» . Научно-исследовательский журнал фармации и технологий . 11 (5): 1951–1956. дои : 10.5958/0974-360X.2018.00362.1 .
^ «Машинное обучение. Почему мы используем прирост информации вместо точности в качестве критерия разделения в дереве решений?» . Обмен стеками науки о данных . Проверено 9 декабря 2021 г.
^ Куинлан, Дж. Росс (1986). «Индукция деревьев решений» . Машинное обучение . 1 (1): 81–106. дои : 10.1007/BF00116251 .
^ Мильман, Орен (6 августа 2018 г.). «Каков диапазон коэффициента усиления информации?» . Обмен стеками . Проверено 9 октября 2018 г.

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

Новозин, Себастион (18 июня 2012 г.). «Улучшенная оценка получения информации для индукции дерева решений». arXiv : 1206.4620v1 .
Шуман, Май (2011). «Использование дерева решений для диагностики пациентов с сердечно-сосудистыми заболеваниями» (PDF) . Материалы девятой Австралазийской конференции по интеллектуальному анализу данных . 121 : 23–30.
Митчелл, Том М. (1997). Машинное обучение . Mc-Graw-Hill Companies, Inc. ISBN компании 978-0070428072 .

[:2-1] Jump up to: ^а ^б ^с ^д Лароуз, Дэниел Т. (2014). Обнаружение знаний в данных: введение в интеллектуальный анализ данных . Хобокен, Нью-Джерси: Уайли . стр. 174–179. ISBN 9780470908747 .

[:1-2] Jump up to: ^а ^б Гопалан, Бхуванесвари (10 декабря 2020 г.). «Что такое энтропия и прирост информации? Как они используются для построения деревьев решений?» . Нампи Ниндзя . Проверено 28 ноября 2021 г.

[3] Джотикумар, Р. (2018). «Прогнозирование продолжительности жизни пациента с сердечным приступом с использованием улучшенного алгоритма классификации C4.5» . Научно-исследовательский журнал фармации и технологий . 11 (5): 1951–1956. дои : 10.5958/0974-360X.2018.00362.1 .

[4] «Машинное обучение. Почему мы используем прирост информации вместо точности в качестве критерия разделения в дереве решений?» . Обмен стеками науки о данных . Проверено 9 декабря 2021 г.

[5] Куинлан, Дж. Росс (1986). «Индукция деревьев решений» . Машинное обучение . 1 (1): 81–106. дои : 10.1007/BF00116251 .

[6] Мильман, Орен (6 августа 2018 г.). «Каков диапазон коэффициента усиления информации?» . Обмен стеками . Проверено 9 октября 2018 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]