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

Question

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

Здесь, в моем алгоритме построения дерева.

Answer 1

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

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

Answer 2

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

Answer 3

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

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

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

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

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

И вы перестанете если Gain < 0, потому что вы не получаете больше чистоты, разделив ее.