Como (melhor) discretizar dados contínuos em árvores de decisão?

Algoritmos de árvore de decisão padrão, como ID3 e C4.5, têm uma abordagem de força bruta para escolher o ponto de corte em um recurso contínuo. Cada valor é testado como um possível ponto de corte. (Por testado, quero dizer que, por exemplo, o ganho de informação é calculado em todos os valores possíveis.)

Com muitos recursos contínuos e muitos dados (portanto, muitos valores para cada recurso), essa abordagem parece muito ineficiente!

Estou assumindo que encontrar uma maneira melhor de fazer isso é um tópico importante no Machine Learning. De fato, minha pesquisa no Google Scholar revelou algumas abordagens alternativas. Como discretizar com k-means. Parece haver muitos trabalhos que abordam problemas específicos em domínios específicos.

Mas há um artigo de revisão recente, publicação em blog ou livro que fornece uma visão geral sobre abordagens comuns para discretização? Não consegui encontrar um ...

Ou então, talvez um de vocês seja um especialista no assunto e esteja disposto a escrever uma pequena visão geral. Isso seria tremendamente útil!

Não, você provavelmente não deseja tentar todos os pontos de corte possíveis em uma implementação séria. É assim que a descrevemos em introduções simples ao ID3, porque é mais fácil de entender, mas geralmente não é como é realmente implementado, porque é lento. Em particular, se houver$n$ pontos de dados, você precisará testar $n-1$limiares de candidatos; usando o algoritmo ingênuo para calcular o ganho de informação de cada um desses limites candidatos$O(n)$ tempo por candidato, para um total de $O(n^2)$ Tempo.

Na prática, existem otimizações que aceleram isso significativamente:

1. Não tente todos os limites possíveis. Em vez disso, escolha uma amostra aleatória de 1.000 limites de candidatos (escolhidos uniformemente aleatoriamente no conjunto de$n-1$ candidatos), calcule o ganho de informações para cada um e escolha o melhor.

2. Use programação dinâmica para calcular com eficiência o ganho de informações de todos $n-1$ divisões, no total de $O(n)$tempo, reutilizando a computação. O algoritmo é bastante simples de derivar.