Сбор информации в деревьях решений - Information gain in decision trees

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

Информационный прирост случайной величины Икс получено из наблюдения случайная переменная А принимая ценность ${\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)}}$ для x из апостериорное распределение ${\displaystyle P_{X|A}{(x|a)}}$ за Икс данный а.

В ожидаемое значение получения информации взаимная информация ${\displaystyle I(X;A)}$ из Икс и А - то есть уменьшение энтропия из Икс достигается путем изучения состояния случайная переменная А.

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

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

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

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

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

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

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

$${\displaystyle S_{a}{(v)}=\{{\textbf {x}}\in T|x_{a}=v\}}$$

быть определенным как набор обучающих материалов ${\displaystyle T}$ для какого атрибута ${\displaystyle a}$ равно ${\displaystyle v}$. Тогда информационный прирост ${\displaystyle T}$ для атрибута ${\displaystyle a}$ есть разница между априорной энтропией Шеннона ${\displaystyle \mathrm {H} (T)}$ обучающего набора и условная энтропия ${\displaystyle \mathrm {H} {(T|a)}}$.

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

$${\displaystyle {\begin{alignedat}{2}IG(T,a)&=\mathrm {H} (T)-\sum _{v\in 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), больны, а пациенты, классифицированные как ложные (F), не болеют. В настоящее время мы находимся в корневом узле дерева и должны рассмотреть все возможные разбиения с использованием данных.

Набор данных обучения

Пациент	Симптом А	Симптом B	Симптом C	Классификация
1	Т	Т	Т	F
2	Т	F	Т	Т
3	F	F	Т	Т
4	F	Т	Т	F
5	F	Т	F	Т

Разделение кандидатов определяется путем рассмотрения каждой переменной, составляющей пациента, и возможных ее состояний. В этом примере все симптомы могут быть истинными (T) или ложными (F).

Разделение кандидатов

Расколоть	Дочерние узлы
1	Симптом A = T, Симптом A = F
2	Симптом B = T, Симптом B = F
3	Симптом C = T, Симптом C = F

Теперь для расщепления №1 мы определяем энтропию до расщепления, которая определяется с использованием классификации каждого пациента.

${\displaystyle H(T)=-3/5\log _{2}(3/5)-2/5\log _{2}(2/5)=0.971}$

Условная энтропия расщепления №1 определяется путем нахождения энтропии каждого состояния симптома A и их объединения.

${\displaystyle H(T|a)=2/5(-1/2\log _{2}(1/2)-1/2\log _{2}(1/2))+3/5(-2/3\log _{2}(2/3)-1/3\log _{2}(1/3))=2/5(1)+3/5(0.918)=0.951}$

Затем можно определить информационный выигрыш, найдя разницу в априорной энтропии и условной энтропии.

${\displaystyle IG(T,a)=H(T)-H(T|a)=0.971-0.951=0.02}$

Пример разделения корневого узла

Эти шаги повторяются для всех групп кандидатов, чтобы получить их информацию. Все возможные разделения для узла используют одно и то же значение для ${\displaystyle H(T)}$.

Разделение кандидатов на получение информации

Расколоть	Получение информации
1	0.020
2	0.419
3	0.171

Разделение кандидатов №2 имеет наибольшее информационное усиление, поэтому оно будет наиболее благоприятным для корневого узла. В зависимости от достоверности классификации дочерних узлов, получение информации может применяться к дочерним узлам, но не может использовать одно и то же разбиение-кандидат.

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

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

Рекомендации

1. Куинлан, Дж. Росс (1986). «Индукция деревьев решений». Машинное обучение. 1 (1): 81–106. Дои:10.1007 / BF00116251.
2. Мильман, Орен (6 августа 2018 г.). «Каков диапазон коэффициента передачи информации?». Обмен стеком. Получено 2018-10-09.

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

• Митчелл, Том М. (1997). Машинное обучение. Компании Mc-Graw-Hill, Inc. ISBN  978-0070428072.