Что делает рекурсивное разбиение на разделы 2^n комбинаций из n уровней данных?

Question

При запуске случайного леса он не разрешит более 32 уровней в одной переменной, так как в результате получается 2^n комбинаций/разделов данных. Я полагал, что это будет следовать классическому комбинаторному уравнению n!/K! (N-k)! для n выбираем k. Может ли кто-нибудь объяснить, почему это так? Например, если бы у меня было 4 уровня в переменной, они разбивались на 2^4 = 16, где я мог бы предположить, что это должно быть 16/4 = 4.

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

Answer 1

Я считаю, что вы путаете два случая. Вы смотрите на «Сколько способов выбрать данный номер, k, предметы из набора n штук?" Фактический вопрос: «Сколько способов я могу выбрать набор предметов от n элементов?"

Второй вопрос - суммирование решений первого, при k = 0 - n. Эта сумма составляет 2^п.

Другой способ взглянуть на это - наличие или отсутствие какого-либо элемента в выбранном вами наборе. Имея два варианта для каждого элемента, мы имеем 2^n общих возможностей.

Вот иллюстрация: давайте просто возьмем набор {1, 2, 3, 4}.

Дело 1: сколько способов выбрать k = 2 элемента из этого набора?

1 2 
1 3 
1  4 
    2 3 
    2 4 
    3 4 

который, действительно, 4!/(2! 2!) = 6 возможностей

Однако, когда мы смотрим на общих разделов для всех значений к, получим

. . . . (empty set) 
     4 
    3 
    3 4 
    2 
    2 4 
    2 3 
    2 3 4 
1 
1  4 
1 3 
1 3 4 
1 2 
1 2 4 
1 2 3 
1 2 3 4 

что 2^4 = 16 вариантов. Заметим, что это также суммирование по различным значениям k: 1 + 4 + 6 + 4 + 1