Literatura sobre o algoritmo para uma divisão ideal no cultivo de árvores de classificação

Na ESL , Seção 9.7, há um parágrafo declarando que o tempo de computação de uma divisão no crescimento de uma árvore de classificação (ou regressão) geralmente escala como que é o número de preditores e é o número de amostras.$p N \log N$$p$$N$

Uma abordagem ingênua resulta em uma escala , e não consegui encontrar nenhuma referência à literatura que explique os detalhes da parte dividida do algoritmo e como se consegue uma escala pN típica .$pN^2$ $p N \log N$

Na abordagem ingênua, a divisão ideal para uma dada variável, após uma ordem inicial dos valores observados, é procurada entre os pontos médios entre os valores observados, e o cálculo da perda para cada divisão pode ser feito em um tempo que escala como .$N-1$$N$

Eu poderia (e provavelmente estudarei) o código-fonte para algumas das implementações que conheço, mas uma referência à literatura seria boa em particular em relação à complexidade do tempo.$-$

Vou dar uma resposta diferente, já que é demais para um comentário e trata uma abordagem mais geral.

Portanto, na ESL, eles descrevem de fato o tempo de computação para um branch-and-bound (mais precisamente, isso me parece uma divisão e conquista).

Denotamos com o número de observações e com o número de nós filhos, quando cultivamos uma árvore. Suponho que não perdemos em geral se considerarmos que é fixo. Além disso, podemos denotar com o tempo de processamento para calcular pontos de divisão em um determinado nó.$N$$K$$K$$f(N)$

Assim, podemos escrever recursivamente a fórmula para o tempo de execução como: que consideramos aqui que os nós filhos dividem o conjunto de dados de entrada do tamanho nos subconjuntos de igual tamanho . Sabemos que esse é o melhor caso.

No entanto, podemos ver que esta é uma aplicação bem conhecida do Teorema Mestre. Isso está bem documentado no livro do CLRS . Eu tenho a 3ª edição e os detalhes estão na seção 4.5 e a prova está na próxima seção. Não me lembro bem dos detalhes, mas lembro que não é muito complicado se se expande a recursão e agrupa alguns termos.

No entanto, o que é importante para este caso é que, quando - tempo linear, o tempo resultante do algoritmo é . Esse tempo é calculado para uma única variável de entrada, portanto, nosso tempo total para variáveis seria$f(N)=O(N)$$T(N) = O(N logN)$$P$$O(P N logN)$

Esse tempo é possível para o crescimento da árvore, se todas as entradas forem classificadas inicialmente em , e encontrar o valor de divisão leva tempo linear nessas entradas classificadas. Aqui podemos aplicar o algoritmo de variância on-line, como mencionei na resposta anterior para . Paraé ainda mais fácil encontrar mediana. Confesso que nunca experimentei outra função de perda de árvores.$O(P N logN)$$L_2 = \frac{1}{N}(y-\hat{y})^2$$L_1 = \frac{1}{N}|y-\hat{y}|$

Observe, porém, que o teorema mestre se aplica ao melhor caso, se as divisões forem iguais em tamanho. O pior caso é quando a divisão é muito desequilibrada. Lá, pode-se aplicar um caso diferente de Teorema Mestre e o tempo se tornará .$O(P N^2)$

Como conclusão, presumo que os autores de ESL usem o termo normalmente de uma maneira usada para descrever o algoritmo de classificação rápida. Normalmente, a classificação rápida fornece tempo de execução de , com o pior caso , para algumas configurações de dados específicas.$O(N logN)$$O(N^2)$

Espero que ajude.

Veja minha resposta de outra pergunta aqui . Embora eu não possua referências em papel, você pode facilmente achar que, para entradas numéricas de comprimento é necessário:$p$$N$

• itera sobre todas as entradas -$p$$O(p)$
• classificação ascendente de cada entrada -$O(N log(N))$
• calcular 2 variâncias em execução, uma começando da esquerda e outra começando da direita em tempo linear -$O(N)$

O tempo dominante para cada atributo é o tempo de classificação, portanto, temos .$O(p N log(N))$