Критерии завершения при построении дерева решений

Question

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

Вот мой алгоритм построения дерева.

Answer 1

Поскольку дерево решений производит несбалансированные разбиения, одна часть дерева может быть тяжелее, чем другая. Следовательно, не разумно использовать высоту дерева, потому что это останавливается везде на одном уровне. Гораздо лучше использовать минимальное количество наблюдений, необходимое для разделения поиска. Это более детально проработано на http://zyxo.wordpress.com/2011/07/04/how-to-use-the-settings-to-control-the-size-of-decision-trees/

Answer 2

В вашем вопросе мало контекста, но я предполагаю, что вы строите дерево из большого набора данных? В этом случае решение является дополнением к «LearnSet», чтобы взять «StopSet» примеров и регулярно проверять ваш процесс принятия решений на этом StopSet. Если качество снижается, это свидетельствует о том, что вы переучиваетесь через LearnSet.

Я намеренно использую «StopSet», а не «TestSet», потому что после этого вы должны применить свое дерево решений к TestSet для оценки реального качества.

Answer 3

Это довольно старый вопрос, но я думаю, что могу улучшить ответы.Теория заключается в том, что вы останавливаетесь, когда расщепление является чистым (т.е. примесь = 0) или все члены в левом или правом узле имеют одинаковое выходное значение.Например, если вы пытаетесь предсказать сердечный приступ или нет, и в данном случае, если в группе есть все сердечные приступы или нет сердечного приступа, вы можете спокойно прекратить разбивать эту группу, потому что все одинаково, и вы можете безопасно предсказатьобщая ценностьЭта теория поддерживается процессом сокращения, потому что вы можете построить очень высокое дерево, и если узел не способствует точности, он обрезается.

Теперь это редкость, когда вы получаете полностью чистые разбиения.И часто для того, чтобы разделить данные на полностью чистые наборы, вы будете разбивать множество на меньшие и меньшие наборы, пока не доберетесь до одного наблюдения в каждом узле.Высокие деревья, как правило, не выдерживают процесса обрезки, и в любом случае, вы, скорее всего, перегоните тренировочные данные.Поэтому обычной практикой является экономить дополнительное время в алгоритме отсечения, чтобы просто ограничить количество наблюдений, на которые вы хотите разделить, и установить минимум для числа из полученного разделения.Вы не собираетесь держать раскол, который приведет к 1 и 999 наблюдениям.Это плохой раскол, попробуйте еще раз.

Таким образом, вы добавляете параметр конфигурации для минимального количества наблюдений в узле (т.е. после разделения) и минимального количества узлов, необходимых для разделения (до разделения), которое может быть настроено пользователем.

Окончательный критерий - это также, если ваши расщепления не улучшаются по сравнению с последним измерением чистоты.Если узел не может быть разделен, чтобы произвести более чистый набор, чем он имел прежде.Вы можете остановиться, потому что вы идете в неправильном направлении.Что по сути означает, что если I (s) - это показатель чистоты узла, который вы разделяете.И I (s [l]) - это чистота левого набора разбиений, I (s [r]) - это чистота правого набора разбиений, а p (s) - это часть этого набора для родительского набора:

Gain = I(s) - p(s[r]) * I(s[r]) - p(s[l]) * I(s[l])

И вы останавливаетесь, если это усиление <0, потому что вы больше не получаете чистоту, разбивая его. </p>