Почему мера энтропии Шеннона используется в ветвях дерева решений?Мера энтропии Шаннона в деревьях принятия решений
Энтропия (S) = - р (+) журнал (р (+)) - р (-) журнал (р (-))
Я знаю, что это мера ни в , бит, необходимый для кодирования информации; чем более равномерное распределение, тем больше энтропия. Но я не понимаю, почему это так часто применяется при создании деревьев решений (выбор точки ветвления).
Потому что вы хотите задать вопрос, который даст вам больше информации. Цель состоит в том, чтобы минимизировать количество решений/вопросов/отраслей в дереве, поэтому вы начинаете с вопроса, который даст вам наибольшую информацию, а затем воспользуйтесь следующими вопросами, чтобы заполнить детали.
Для деревьев решений забудьте о количестве бит и просто сосредоточьтесь на самой формуле. Рассмотрим двоичную (+/-) задачу классификации, в которой у вас есть равное количество + и - примеров в ваших данных обучения. Первоначально энтропия будет равна 1 с p(+) = p(-) = 0.5. Вы хотите разбить данные на атрибут, который больше всего уменьшает энтропию (т. Е. Делает распределение классов наименее случайным). Если вы выберете атрибут A1, который полностью не связан с классами, то энтропия будет по-прежнему равна 1 после разделения данных на значения A1, поэтому нет сокращения энтропии. Теперь предположим, что другой атрибут, A2, отлично разделяет классы (например, класс всегда + для A2="yes" и всегда - для A2="no". В этом случае энтропия равна нулю, что идеальный случай.
В практических случаях, атрибуты обычно не классифицируют категоризацию данных (энтропия больше нуля). Таким образом, вы выбираете атрибут, который «наилучшим образом» классифицирует данные (обеспечивает наибольшее сокращение энтропии). Как только данные разделены таким образом, другой атрибут выбирается для каждой из ветвей с первого разделения аналогичным образом, чтобы дополнительно уменьшить энтропию вдоль этой ветви. Этот процесс продолжается для построения дерева.
Вы, кажется, имеете понимание математики за этим методом, но вот простой пример, который может дать вам некоторую интуицию, почему используется этот метод: представьте, что вы находитесь в классе, в котором участвуют 100 учеников. Каждый студент сидит за письменным столом, а столы организованы таким образом, что есть 10 строк и 10 столбцов. 1 из 100 студентов имеет приз, который вы можете получить, но вы должны догадаться, какой студент должен получить приз. Улов в том, что каждый раз, когда вы догадываетесь, выигрыш уменьшается в цене. Вы можете начать с того, чтобы спросить каждого студента отдельно, есть ли у них выигрыш. Однако изначально у вас есть только вероятность угадывать в 1/100, и вполне вероятно, что к тому времени, когда вы найдете приз, это будет бесполезно (подумайте о каждой догадки как ветке в дереве решений). Вместо этого вы можете задать широкие вопросы, которые значительно уменьшают пространство поиска с каждым вопросом. Например: «Является ли студент где-то в строках 1, хотя 5?» Является ли ответ «Да» или «Нет», вы уменьшили количество потенциальных ветвей в своем дереве наполовину.
В соответствии с вашими объяснениями вы можете объяснить, почему нужно использовать функцию журнала? – kamaci
Если вы заметили, что 'p (+) = 1 - p (-)', имеющая функцию «log» в уравнении, дает ему свойство nice, что функция имеет свой минимум (ноль), когда 'p (+)' нуль или один, и имеет максимум (1), когда 'p (+)' равно 1/2 (т. е. когда оба класса одинаково вероятны). Нет необходимости в функции «log» в самой формуле. Вы можете использовать альтернативную симметричную функцию, которая равна нулю, когда 'p (+)' равно нулю или один, имеет максимальный максимум 0,5 и монотонно уменьшается с расстоянием от p (+) = 0,5'. – bogatron