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

Выгода от наблюдения за другой случайной величиной

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

Прирост информации случайной величины, полученный в результате наблюдения за случайной величиной, принимающей значение , определяется как: ${\displaystyle X}$ ${\displaystyle A}$ ${\displaystyle A=a}$

$${\displaystyle IG_{X,A}{(X,a)}=D_{\text{KL}}{\left(P_{X}{(x|a)}\|P_{X}{(x|I)}\right)}}$$

т.е. расхождение Кульбака–Лейблера ( априорного распределения для ) от ( апостериорного распределения для заданного ). ${\displaystyle P_{X}{(x|I)}}$ ${\displaystyle x}$ ${\displaystyle P_{X|A}{(x|a)}}$ ${\displaystyle x}$ ${\displaystyle a}$

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

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

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

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

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

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

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

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

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

$${\displaystyle \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)}.}$$

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

Взаимная информация равна полной энтропии для атрибута, если для каждого из значений атрибута можно сделать уникальную классификацию для результирующего атрибута. В этом случае относительные энтропии, вычитаемые из полной энтропии, равны 0. В частности, значения определяют разбиение обучающего набора данных T на взаимоисключающие и всеохватывающие подмножества , индуцируя категориальное распределение вероятностей для значений атрибута a . Распределение задано . В этом представлении прирост информации T при заданном a можно определить как разницу между безусловной энтропией Шеннона T и ожидаемой энтропией T , обусловленной a , где ожидаемое значение берется относительно индуцированного распределения для значений a . ${\displaystyle v\in vals(a)}$ ${\textstyle P_{a}{(v)}}$ ${\textstyle v\in vals(a)}$ ${\textstyle P_{a}{(v)}:={\frac {|S_{a}{(v)}|}{|T|}}}$ $${\displaystyle {\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] Крайний левый рисунок ниже очень нечист и имеет высокую энтропию, соответствующую более высокому беспорядку и более низкой информационной ценности. По мере продвижения вправо энтропия уменьшается, а информационная ценность увеличивается.

Диаграмма энтропии ^[2]

Простое дерево решений

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

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

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

В этом наборе данных 1 означает, что образец имеет мутацию (True), а 0 означает, что образец не имеет мутации (False). Образец с 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 соответственно .

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

п _{С, t} = 4/7

р _{НК, т} = 3/7

${\displaystyle \mathrm {H} {(t)}}$= −(4/7  ×  логарифм ₂ (4/7) + 3/7  ×  логарифм ₂ (3/7)) = 0,985

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

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

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

H( t _L ) = −[ p _C,L log ₂ ( p _C,L ) + p _NC,L log ₂ ( p _NC,L )] ^[1]

H( t _R ) = −[ p _C,R log ₂ ( p _C,R ) + p _NC,R log ₂ ( p _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 приведенного выше дерева решений вычисляется как:

H( _s , t ) = PL H ₍ t L ₎ + PR _H ( t R )

где,

вероятность выборки у левого потомка, P _L = n ( t _L ) / n ( t ),

вероятность выборки у правого ребенка, P _R = n ( t _R ) / n ( t ),

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

П _Л = 4/7

П _Р = 3/7

H( с,т ) = (4/7  ×  0,811) + (3/7  ×  0,918) = 0,857

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

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

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

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

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

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

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

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

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

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

П _{С, t} = 1/4

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

${\displaystyle \mathrm {H} {(t)}}$= -(1/4  ×  log ₂ (1/4) + 3/4  ×  log ₂ (3/4)) = 0,811

Обновленное дерево с правым дочерним узлом, разделенным на основе мутации 4.

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

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

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

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

Тестирование дерева решений с двумя новыми образцами.

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

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

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

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

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

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

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

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

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

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

Ссылки

1. Larose, Daniel T. (2014). Discovering Knowledge in Data: An Introduction to Data Mining . Hoboken, New Jersey: Wiley . pp. 174–179. ISBN 9780470908747.
2. Gopalan, Bhuvaneswari (2020-12-10). "Что такое энтропия и прирост информации? Как они используются для построения деревьев решений?". Numpy Ninja . Получено 28.11.2021 .
3. Джотикумар, Р. (2018). «Прогнозирование продолжительности жизни пациента с сердечным приступом с использованием улучшенного алгоритма классификации C4.5». Research Journal of Pharmacy and Technology . 11 (5): 1951–1956. doi : 10.5958/0974-360X.2018.00362.1.
4. "машинное обучение - почему мы используем прирост информации, а не точность в качестве критерия разделения в дереве решений?". Data Science Stack Exchange . Получено 2021-12-09 .
5. Куинлан, Дж. Росс (1986). «Индукция деревьев решений». Машинное обучение . 1 (1): 81–106. doi : 10.1007/BF00116251 .
6. Милман, Орен (6 августа 2018 г.). «Каков диапазон коэффициента прироста информации?». Stack Exchange . Получено 2018-10-09 .

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

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