Найти лучший атрибут в дереве решений

Я столкнулся с одним вопросом

Color   Flavor  Edibility
Red   Grape     Yes
Red   Cherry    Yes
Green   Grape     Yes
Green   Cherry    No
Blue     Grape     No
Blue     Cherry    No

В этом вопросе он говорит, что просто анализ без каких-либо расчетов, угадать лучший атрибут (либо цвет, либо вкус)

Может кто-нибудь объяснить, как угадать это без расчета энтропии и так далее

Источник

2 ответа

Я знаю, что этот вопрос немного старше, но на тот случай, если вам все еще интересно: в общем, более короткое и широкое дерево было бы "лучше". Примите во внимание тот факт, что для достижения узла в высоком дереве потребуются дополнительные решения.

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

Энтропия - это количество неопределенности или случайности с определенной переменной. Если подумать о другом, это мера того, насколько однородны обучающие образцы в конкретном узле. Например, рассмотрим классификатор с двумя классами, YES и NO (true или false в вашем случае). Если конкретная переменная или атрибут, скажем, x, имеет три обучающих примера класса YES и три обучающих примера класса NO (всего шесть), энтропия будет равна 1. Это потому, что для этого класса имеется равное число обоих классов. переменная и является наиболее "перепутанной", которую вы можете получить. Аналогично, если бы у x было все шесть обучающих примеров конкретного класса, скажем, YES, то энтропия была бы равна 0, потому что эта конкретная переменная была бы чистой, что делало бы ее листовым узлом в нашем дереве решений.

Энтропия может быть рассчитана следующим образом:

http://dms.irb.hr/tutorial/images/entropy_eq.gif

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

http://dms.irb.hr/tutorial/images/gain_eq.gif

В то время как вопросы просят вас не рассчитывать ни выигрыш, ни энтропию, объяснение было необходимо, чтобы показать, почему я выбираю тот или иной атрибут. В вашем случае я предполагаю, что съедобность - это усвоенный атрибут.

Если вы выбираете либо аромат, либо цвет, обратите внимание, что у вас энтропия 1 [0-1] в обоих случаях, потому что у вас есть одинаковое количество обучающих экземпляров с съедобностью "да" и "нет" независимо от атрибута. На данный момент, вы должны смотреть на усиление. Если вы прикрепите свое дерево к атрибуту "цвет", у вас будет меньше энтропии, поскольку доля каждого атрибута, принадлежащего множеству S, будет меньше. Например, обратите внимание, что листовые узлы для "Red" и "Green" уже чистые, со всеми "yes" и "no" соответственно. С этого момента у вас остается один атрибут, аромат. Очевидно, что если у вас осталось более одного, вам нужно будет рассчитать усиление для каждого атрибута, чтобы выяснить, какой из них лучше, и использовать его в качестве следующего "слоя".

Кроме того, попробуйте нарисовать его и закрепить дерево с помощью атрибута Color и рассчитать усиление - вы обнаружите, что быстрее сходитесь к своему ответу (чистый узел).

Источник

Энтропия и выгоды - определенно лучшая эвристика из теории информации, которая помогает в выборе лучшей функции. Тем не менее, один из способов выбора лучшего атрибута, который менее точен, чем энтропия, но работает хорошо, - это одноэтапное рассмотрение, которое работает следующим образом:

CHOOSEBESTATTRIBUTE(S)
choose j to minimize J, computed as follows:
    S0 = all <x,y> in S with xj = O;
    S1 = all <x,y> in S with xj = 1;
    Y0 = the most common value of y in S0
    Y1 = the most common value of y in S1
    J0 = number of examples <x, y> in S0 with y not equal to y0
    J1 = number of examples (x, y) in S1 with y not equal to y1
    Ji = J0 + J1 (total errors if we split on this feature)
return j

Источник: Машинное обучение: Том М. Митчелл, глава 3

Источник
Другие вопросы по тегам