Алгоритм «Деревья решений»
Сегодня мы расскажем об одном замечательном алгоритме – деревьях решений. Его применяют для задач классификаций и прогнозирования. Когда был изобретен первый прототип алгоритма сказать сложно, им пользовались задолго до появления компьютеров. Деревья решений настолько популярны, что иногда ими пользуются, не подозревая, для решения повседневных задач.
На практике часто встречаются задачи, когда нужно учесть множество характеристик (признаков) объекта и на их основе выбрать оптимальное решение. С помощью признаков можно разбивать объекты на группы, в зависимости их значений. Таким образом, можно получить подробное разбиение объектов на группы и в зависимости от принадлежности к группе судить об их поведении.
Часто бывают ситуации, когда известны поведения некоторого множества объектов и их признаки, требуется по признакам нового объекта спрогнозировать его поведение. Чтобы это сделать, производят разбиение на группы старые, с уже известными метками о поведении, и по принадлежности нового объекта к выделенной группе старых делают предположение о его поведении. Но как произвести разбиение оптимально, когда признаки объектов могут принимать вещественные (числовые и непрерывные) значения? Для этого существуют специальные критерии, позволяющие организовывать группы, которые наилучшим образом отделяют объекты с похожими поведенческими особенностями от остальных. Они оценивают чистоту разбиения объектов на группы. Один из таких критериев известен как энтропия, которая имеет строгое математическое определение. Разбиение на группы подбирается таким образом, чтобы минимизировать эту величину.
Может показаться, что чем больше групп организованно описанным выше образом на известном множестве объектов, тем лучше мы обучили модель. Однако это не так. Сильно большим дроблением объектов на группы можно достичь переобучение – когда модель дает плохую точность на новых данных, при хорошей на обучающем наборе. В случае переобучения модель больше запоминает обучающую выборку, теряя при этом обобщающую способность. О том, как бороться с переобучением и как проверить, способна ли модель делать обобщения, расскажем в следующий раз.