Árvores de decisão e florestas aleatórias

Um pouco da teoria de um dos mais robustos métodos de machine learning

As florestas aleatórias (ou random forests) são métodos de aprendizado para regressão e classificação muito robustos, e que são base para algoritmos avançados em machine learning. Elas são baseadas nas árvores de decisão (ou decision trees), outro método mais básico, também muito bom, e que por vez se baseia no conceito de árvore.

Por isso, podemos construir nosso conhecimento em blocos, começando por árvores.

Photo by Jeremy Bishop on Unsplash

Terminologia básica de árvores

As árvores em computação são inspiradas obviamente, nas árvores da vida real, mas existem alguns conceitos mais específicos que foram definidos, considere o seguinte exemplo:

Árvore exemplo

Vamos à lista de definições:

• Cada bolinha é um nó;
• Cada linha uma aresta;
• A é o nó raiz;
• Se pegarmos alguns nós com algumas arestas, temos uma subárvore;
• Começando por um ponto e andando nos nós: um caminho;
• A é ancestral de B, C e E, que são descendentes de A. A mesma lógica se aplica para os outros nós;
• Os nós D, F e G são chamados folhas o restante são chamados de internos;
• Essa árvore tem 2 níveis (se contarmos A como nível 0);
• A altura da árvore é definida como número de arestas até a folha mais distante (nesse caso 2 também).

Árvore de decisão

A árvore de decisão pode ser definida como um conjunto de nós com a seguinte estrutura:

• Nós internos possuem atributos;
• Folhas possuem as classes;
• Ramos são rotulados com valores (atributos categóricos) ou com intervalos (atributos numéricos).

Exemplo de árvore de decisão

Processo de construção (descrição)

Para construir a árvore de decisão nós precisamos dos exemplos de dados, então considerando que temos esse exemplos os seguintes procedimentos são realizados:

• Todos os exemplos começam no nó raiz;
• Verifica se são da mesma classe, caso sejam a árvore é finalizada apenas com um nó, caso contrário continua;
• Procura o atributo que pode melhor dividir as classes e cria um nó com esse atributo;
• Para cada nó criado é realizado o mesmo processo que aconteceu a partir do nós raiz, até que todos os exemplos sejam de apenas uma classe.

A partir da árvore criada a classificação de um novo objeto é extremamente simples, é só olhar os atributos nos nós e o limiar determinado para divisão até chegar no nó raiz, onde estará a classificação.

Após a criação é aconselhável realizar o processo chamado de poda, que evita o overfitting, já que alguns nós poderiam ser muito granulares, ficando com poucos exemplos. Esse processo agrega os nós folhas em um nó ancestral.

Existem outros tipos de poda, critérios de parada, funções de rotulação das classes e de divisão dos nós na construção da árvore, mas focaremos apenas no conceito geral nesse artigo.

Dentre as principais vantagens desse método, podemos destacar:

• Interpretabilidade;
• Seleção de atributos automática;
• Não paramétrica, ou seja, não assume nenhuma família de distribuição;
• Consegue lidar com missing values;
• Consegue lidar com atributos numéricos e categóricos.

E as principais desvantagens:

• Instabilidade;
• Possui dificuldades se existem relações complexas entre os atributos.

Florestas aleatórias

O conceito de florestas aleatórias (ou pelo menos a ideia inicial) surge justamente de uma das desvantagens que listamos em relação às árvores: a instabilidade.

Bagging

Inicialmente foi desenvolvido um comitê de classificadores (várias árvores de decisão), cada uma treinada para uma parte da amostra de treinamento. A classificação era definida pela classificação majoritária de todas as árvores.

Random Forests

Já as random forests são muito semelhantes ao bagging, com a diferença que apenas um subconjunto aleatório dos atributos participa da subdivisão de um nó, o que tornar esse método é mais estável que bagging.

Existe uma métrica para estimação de erro especial nesse caso chamado out of bag, como cada árvore é construída a partir de um subconjunto de exemplos de treinamento, ela pode ser testada com os exemplos restante, daí o nome. Essa métrica não pode ser utilizada para comparação com outros classificadores, já que ela é específica para esse caso.

Apesar desse tipo de erro não ser utilizado para comparação com outros métodos, ele pode ser utilizado na hora de testar diversos parâmetros afim de encontrar a combinação ideal da random forest.

Durante a calibração de parâmetros é possível variar:

• O número máximo de atributos que será selecionado em cada árvore;
• A profundidade máxima da árvore;
• O número de instâncias a serem sorteadas em cada árvore;
• Se permite reposição ou não das instâncias em cada sorteio;
• O número mínimo de observações no nó terminal;
• O número de árvores na floresta;
• A regra de divisão das árvores.

Gostou do conteúdo?

Siga a Luna no Medium. E não se esqueça de deixar alguns aplausos 👏🏽Qualquer dúvida ou sugestão é só deixar nos comentários!

Thanks!