Ainda falando sobre os algoritmos baseados em árvores (tree-based algorithms), temos uma nova variação das Árvores de Decisão (ou Decision Trees), com uma aleatoriedade ainda mais forte. Essa variação é conhecida como as Árvores Extremamente Aleatórias (Extremely Randomized Trees), ou apenas Extra-Trees.
Se você ainda não leu os outros posts sobre algoritmos baseados em árvores e não conhece estes tipos de algoritmos, recomendo fortemente a leitura. Os conceitos introduzidos lá precisam estar bem claros para o entendimento desse novo tipo de algoritmo. Mesmo se você conhece os algoritmos de árvores, a leitura pode ser uma revisão bem bacana e didática.
Recomendo ler primeiro o post Árvores de Decisão: Algoritmos Baseados em Árvores e em seguida o post Random Forests: Algoritmos Baseados em Árvores. Acredito que após a leitura destes, o entendimento das Extra-Trees irá ficar bem simples e intuitivo.
Aleatoriedade Extrema
Quando falamos sobre as Random Forests, falamos também sobre a Lei dos Grandes Números (LGN). Este teorema dos estudos da probabilidade nos descreve o resultado da realização do mesmo experimento repetidas vezes. Com isso, classificadores fracos, com taxa de acerto de apenas pouco mais de 50% (“cara ou coroa”), podem trazer acurácias muito positivas se combinados em grandes quantidades.
Um ponto crucial, porém, é que todos os experimentos (modelos classificadores, ou Estimators) precisam ser independentes. Eles precisam cometer erros não correlacionados. Já ressaltamos que se todos os modelos fracos forem treinados sobre os mesmos dados, muito provavelmente cometerão os mesmos tipos de erros. Isso irá levar a muitos votos na classe incorreta. A acurácia do modelo irá diminuir.
E a forma de manter os modelos classificadores independentes entre si é aumentando a sua aleatoriedade. Daí vem o nome “Extremamente Aleatórias”.
Random Forests vs Extra-Trees
No caso das Random Forests, nós aumentamos a aleatoriedade usando da técnica de Amostragem com Reposição e selecionando apenas um subconjunto aleatório de características/atributos (features, ou colunas) para cada Árvore de Decisão construída.
Temos então um subconjunto de dados aleatório e o subconjunto de características aleatórias. Nos algoritmos de Random Forest, as Árvores de Decisão selecionam os melhores atributos para divisão. As árvores são construídas normalmente.
Para as Extra-Trees adicionamos mais um fator aleatório. Além do subconjunto de dados aleatório e o subconjunto de características aleatórias, as Árvores de Decisão não decidem qual o melhor atributo/característica para fazer cada divisão da árvore. Estes limiares de decisão são escolhidos de forma aleatória.
Entendendo as Extra-Trees
Temos basicamente uma Floresta Aleatória (Random Forest), porém mais aleatória ainda. Cada árvore construída no algoritmo de Extra-Trees irá escolher aleatoriamente qual limiar de atributo será usado em cada divisão. Em termos de código, é como se criássemos objetos de Árvores de Decisão: DecisionTreeClassifier(); mas com o parâmetro splitter="random".
Vamos visualizar o processo de construção do modelo final com este algoritmo.
Usamos uma imagem similar ao modelo de Random Forest para classificação de Spam. Note porém que os Nós de Decisão (Decision Nodes) das árvores estão com uma interrogação (?). Isto é para reforçar que cada decisão em cada Nó é aleatória. Não é necessariamente a decisão que traz um maior ganho de informação.
Esta técnica irá sacrificar um pouco da capacidade de aprendizado do modelo (tendência ao Underfitting) para garantir uma boa generalização em dados novos (diminuição do Overfitting).
Nós podemos facilmente criar modelos de Extra-Trees usando a classe ExtraTreesClassifier() da biblioteca Scikit-Learn. A API para uso da classe é idêntica ao uso da classe RandomForestClassifier(), exceto que por padrão temos bootstrap=False. Da mesma forma, a classe ExtraTreesRegressor() é idêntica ao uso da RandomForestRegressor().
A documentação é sempre o melhor ponto de partida. Mas iremos compartilhar aqui no BRAINS em breve como treinar modelos de Árvores de Decisão e Random Forests usando Python e Scikit-Learn.
Conclusão
O fato de não ter que buscar sempre o melhor ponto de divisão torna o algoritmo de Extra-Trees muito mais rápido de se treinar. Encontrar o melhor ponto de divisão de cada árvore é o processo que mais consome recursos e tempo de um modelo Random Forest. Entretanto, é difícil dizer qual modelo terá um desempenho melhor.
O desempenho em termos de taxas de acerto das Random Forest e das Extra-Trees são comparáveis. É sempre bom treinar ambos os modelos, testá-los e compará-los sobre os seus dados. É muito difícil dizer com antecedência qual será melhor. Para ter certeza, apenas testando.
No geral, as Extra-Trees têm as mesmas vantagens das Random Forests, porém com o benefício de serem mais eficientes em termos de recursos computacionais e tempo.
Deixe comentários caso tenha dúvidas sobre o nosso post. Caso queira se aprofundar no tema das Extra-Trees, recomendo a leitura do artigo Extremely Randomized Trees (Pierre Geurts, Damien Ernst & Louis Wehenkel).
Nós esperamos ter ao nosso lado, colaborando com a nossa comunidade, estudantes dos mais iniciantes aos mais avançados. Para saber mais sobre como colaborar, visite o nosso post BRAINS – Brazilian AI Networks.
#NoBrains #NoGains 🧠
