Como inventar o algoritmo de árvore de decisão do zero

Parte um · construa à mão

Aprendizado de máquina não é um único método

Quando alguém diz aprendizado de máquina, pode parecer o nome de uma única tecnologia. É mais parecido com uma caixa de ferramentas. A área está cheia de algoritmos diferentes, e cada um aprende padrões a partir de exemplos do seu próprio jeito, para depois fazer previsões sobre exemplos que nunca viu.

As redes neurais são a família famosa. Elas estão por trás de resultados impressionantes em texto, imagem, áudio e vídeo. Mas fama não é o mesmo que adequação. Uma enorme parte dos dados do cotidiano vive em tabelas — clientes, casas, plantas, empréstimos, medições médicas — e, em tabelas, osmétodos baseados em árvores costumam ser a escolha forte e prática. Para entender o motivo, comece pelo que torna uma tabela diferente dos outros formatos de dados.

Cada linha descreve uma coisa

Uma frase é uma sequência de palavras: a ordem importa. Uma imagem é uma grade de pixels: a posição importa. Na nossa tabela, cada linha descreve uma semente e as colunas registram propriedades dela. Embaralhar essas linhas não mudaria seu significado porque nenhuma semente depende da linha anterior.

Pense nas pessoas em uma festa. Uma pessoa é alta, loira e usa óculos. Outra é baixa, morena e não usa óculos. Esse tipo de dado convida a perguntas de sim ou não — a pessoa é alta? usa óculos? — e cada resposta divide o grupo em dois. Uma tabela funciona da mesma forma: uma pergunta sobre uma coluna envia algumas linhas para um lado e o restante para o outro.

Guarde essa observação. Perguntas simples são uma maneira natural de organizar dados tabulares e — como veremos em seguida — talvez bastem para prever algo que ainda não sabemos.

Nosso exemplo recorrente

Dez sementes e uma previsão

Imagine que plantamos dez sementes. Cada uma recebeu um certo número de horas de luz solar por dia e uma certa quantidade de litros de água por semana. No final do experimento, cada semente estava saudável ou com dificuldade.

Entidade

uma semente

Características

luz solar e água

Rótulo

saudável ou com dificuldade

Agora, uma pessoa amiga nos traz a semente K. Ela receberá 3 horas de luz solar por dia e 2 litros de água por semana. As dez sementes antigas podem nos ajudar a prever o que acontecerá com a nova?

Essa tarefa se chama classificação: não estamos prevendo uma altura exata, estamos escolhendo entre dois rótulos — saudável ou com dificuldade.

A primeira invenção

Uma divisão é uma pergunta

Encarar a tabela linha por linha é difícil, então vamos distribuí-la em dois eixos. A luz solar corre da esquerda para a direita; a água, de baixo para cima. Os círculos são sementes saudáveis; os quadrados, sementes com dificuldade.

Uma linha neste gráfico pode funcionar como uma pergunta de sim ou não. Uma linha vertical pergunta se a luz solar é menor ou igual a algum corte. Uma linha horizontal faz o mesmo tipo de pergunta sobre a água. Ainda não escolhemos a característica nem o valor de corte.

Sua primeira tarefa é apenas visual: encontre uma linha que deixe círculos e quadrados menos misturados nos dois lados. Pode haver várias tentativas razoáveis. Escolha uma antes de pedir ao experimento a resposta mais clara.

A revelação verifica todas as posições disponíveis e retornaluz solar ≤ 3,5 horas. As sementes de A a E respondem sim: quatro estão saudáveis e D está com dificuldade. As outras cinco respondem não, e todas estão com dificuldade.

Essa pergunta transformou um grupo misto em dois grupos menos misturados. O grupo da direita está pronto porque todas as sementes nele estão com dificuldade. O da esquerda ainda contém os dois resultados. Um corte como 3,5 é umlimiar. Uma pergunta formada por característica e limiar que divide um grupo é uma divisão.

Transforme uma pergunta em estrutura

Uma região mista pode responder a outra pergunta

Uma linha é apenas o começo. Depois que uma pergunta divide o gráfico, cada região guarda uma versão menor do problema original. Uma região em que todas as sementes têm o mesmo resultado pode parar. Uma região mista pode fazer outra pergunta — usando apenas as sementes que estão dentro dela.

É aqui que as linhas se tornam uma árvore. No experimento abaixo, selecione uma região, escolha uma característica e corte somente essa região. O painel à direita registra exatamente a mesma sequência de perguntas como uma estrutura ramificada: o primeiro corte é a raiz, e cada corte seguinte fica pendurado na resposta que levou até ele.

O ponto de virada desta lição

Pare e observe o que você acabou de fazer

Quer você tenha concluído a árvore por conta própria, quer tenha aberto a solução guiada, a construção não usou fórmulas. Um nó é uma pergunta, suas duas respostas são ramos e cada região final é uma folha que faz uma previsão. A construção usou exatamente três habilidades:

1. Propor. Você deslizou uma linha pela região e ela se encaixou entre sementes vizinhas.
2. Julgar. Você olhou para os dois lados e decidiu se os resultados ficaram mais parecidos.
3. Repetir. Dentro de qualquer região que continuou mista, você fez tudo de novo.

Duas dessas habilidades são mecânicas. Propor linhas é um laço sobre posições. Repetir é o mesmo procedimento aplicado a um grupo menor. Um computador faz as duas coisas sem nenhuma criatividade.

A terceira habilidade é o obstáculo. “Este lado parece mais limpo” é um julgamento, não uma instrução. Para automatizar o processo inteiro, precisamos substituir os seus olhos por um número — uma pontuação que responda: quão bem esta pergunta separou os resultados? Essa única substituição é toda a segunda metade desta lição. Todo o resto você já inventou.

Parte dois · automatize

Só algumas perguntas valem a pena

Antes de pontuar perguntas, vale contá-las. Um limiar como 2,25 pode parecer arbitrário — por que não 2,3, ou 2,31? Olhe para a coluna de luz solar: 2,0 e 2,5 são valores vizinhos. Toda linha traçada entre eles envia as mesmas linhas da tabela para os mesmos lados. Todos esses limiares são a mesma pergunta com números diferentes, então testamos apenas um deles: o ponto médio.

Isso torna a busca finita. Ordene os valores distintos de uma coluna e tome o ponto médio de cada par vizinho: dez valores distintos geram nove limiares candidatos. Duas características, nove limiares cada — na raiz existem exatamente18 perguntas que valem a pena testar, e não infinitas. Os experimentos acima já estavam encaixando a sua linha nesses pontos médios.

Portanto, o computador consegue gerar todas as perguntas que valem a pena. O que ele ainda não consegue é escolher a melhor. “Esta parece mais limpa” precisa virar um número.

Primeiro passo: medir a mistura de um único grupo

Esqueça as divisões por um instante e olhe para um grupo de sementes. O que os seus olhos realmente verificaram, lado a lado, foi o quão misto cada grupo estava. Uma pontuação de mistura útil deve seguir três regras:

1. Um grupo puro vale 0. Se toda semente tem o mesmo resultado, não há mistura.
2. Uma mistura igualitária vale o máximo. Um grupo 50/50 é o mais misto que duas classes permitem.
3. Só as contagens de rótulos importam. A pontuação não deve se importar com a posição nem com a ordem das sementes.

A escolha padrão para árvores de classificação é a impureza de Gini, e ela tem um significado concreto. Imagine sortear o rótulo de uma semente, devolvê-lo à tigela e sortear novamente. A devolução mantém as mesmas chances nos dois sorteios. O Gini é a chance de os dois rótulos discordarem.

Nosso grupo completo tem quatro sementes saudáveis e seis com dificuldade. A discordância pode acontecer em duas ordens: saudável e depois com dificuldade, ou com dificuldade e depois saudável:

Em um grupo puro, a discordância é impossível, então o Gini é 0. Em um grupo com duas classes divididas igualmente, ela é a maior possível, então o Gini chega a 0,5.

Esse valor está perto do máximo possível de 0,5 para duas classes. Não significa que um modelo erra 48% das vezes — ainda nem existe um modelo. Significa apenas que o grupo ainda contém uma mistura forte dos dois rótulos.

Segundo passo: pontuar uma pergunta, não apenas um grupo

Uma pergunta cria dois grupos, então precisamos combinar dois valores de Gini em uma única pontuação. Tome a primeira pergunta mais clara, luz solar ≤ 3,5. O lado sim tem quatro sementes saudáveis e uma com dificuldade. O lado não tem cinco sementes com dificuldade — puro, Gini 0:

Cada lado é ponderado pela fração de linhas que recebeu. Aqui, por acaso, a divisão envia cinco linhas para cada lado, então os pesos são iguais; a mesma regra também funciona quando divisões posteriores criam grupos de tamanhos diferentes:

Antes da pergunta, o Gini do grupo era 0,48. Depois dela, a mistura ponderada é 0,16. A melhora é chamada de ganho de Gini:

Este é o número que substitui os seus olhos. Um ganho maior significa que a pergunta removeu mais mistura. Ele usa apenas contagens de rótulos, então um computador consegue avaliá-lo para qualquer pergunta candidata com poucas multiplicações.

A pontuação compara quaisquer duas candidatas

Para sentir a pontuação funcionando, mantenha a característica fixa e mova apenas o limiar. Antes de ler os números abaixo, olhe para as duas imagens e preveja qual pergunta deixa menos mistura para trás.

O algoritmo inteiro

Dois laços e uma memória

Agora todos os ingredientes estão na mesa, e o algoritmo quase se escreve sozinho. No grupo atual de linhas:

1. Para cada característica — luz solar e depois água —
2. para cada limiar de ponto médio dessa característica,
3. calcule o ganho de Gini da pergunta que eles formam
4. e lembre a melhor vista até agora.

Essa é a busca inteira: dois laços aninhados e uma vencedora na memória. Não há nenhuma esperteza lá dentro — o computador faz exatamente o que você fez no primeiro experimento, exceto que ele testa todas as 18 perguntas e se recusa a ter gosto próprio. Veja a busca rodar.

Se você rodou a busca até o fim, a vencedora numérica confirmou o padrão que os seus olhos podiam ver: luz solar ≤ 3,5 mantém juntas as cinco sementes com muita luz em um grupo puro com dificuldade e obtém ganho 0,320. O laço não inventou uma ideia nova; ele mediu todas as linhas possíveis e confirmou a mais clara.

A terceira habilidade: repetir em cada folha mista

Uma busca produz uma pergunta, e uma pergunta ainda não é uma árvore. A divisão vencedora deixa F, G, H, I e J em uma folha pura com dificuldade — esse lado está pronto. O outro lado ainda contém os dois rótulos, então rodamos exatamente a mesma busca apenas em A, B, C, D e E. Água ≤ 3,1 separa D das quatro sementes saudáveis, e todas as folhas ficam puras.

Esse padrão — um procedimento que se aplica aos problemas menores que ele mesmo cria — é chamado de recursão. A regra nunca muda; apenas o conjunto de linhas ativas diminui. Avance passo a passo abaixo e tente prever qual grupo será dividido em seguida.

A estrutura final merece um olhar completo:

Compare com a árvore que você construiu à mão. O computador pode não ter feito os seus cortes exatos, mas seguiu exatamente o seu método — e agora os dois vocabulários se alinham:

Teste o mecanismo

As mesmas perguntas pequenas podem criar fronteiras complexas

O conjunto das sementes terminou depois de duas perguntas porque o padrão era incomumente cooperativo. O algoritmo não está limitado a dois cortes. Cada nova pergunta atua apenas dentro de uma região existente, então linhas verticais e horizontais podem se combinar em faixas, escadas, caixas e muitos retângulos menores.

Escolha abaixo um padrão de pontos e tente prever do que a árvore precisará antes de executá-la. Depois, percorra a mesma busca por Gini que você acabou de aprender: percorra x e y, teste cada limiar de ponto médio, mantenha o maior ganho e repita dentro das regiões que ainda estão misturadas.

Agora o invariante fica mais nítido. Uma fronteira mais elaborada não exige um tipo mais elaborado de pergunta; exige mais rodadas da mesma busca. A diagonal vira uma escada porque esta árvore só faz perguntas alinhadas aos eixos e sobre uma característica por vez. A ilha central exige cortes aninhados porque nenhuma pergunta vertical ou horizontal consegue isolar sozinha o grupo do meio.

Mais divisões também significam mais oportunidades de ajustar acidentes nos pontos de treino. É por isso que a complexidade da árvore não pode crescer sem uma regra de parada.

Quando a árvore deve parar?

Nossos dados de brinquedo ficam puros depois de duas perguntas. Dados reais são mais ruidosos, e uma árvore que continua dividindo pode acabar memorizando pequenos acidentes do conjunto de treino. Por isso, árvores práticas param de crescer um ramo quando qualquer uma destas condições vale:

1. O nó é puro. Todas as linhas ativas têm o mesmo rótulo.
2. Nenhuma divisão tem ganho positivo. As perguntas disponíveis não melhoram o grupo.
3. O limite de profundidade foi atingido. Recusamo-nos a fazer mais perguntas aninhadas.
4. Restam poucas linhas. Evitamos criar uma regra a partir de um grupo frágil.

Quando um ramo para, sua folha prevê o rótulo mais comum entre as linhas dela. A folha também pode guardar as contagens de classe: uma folha com oito sementes saudáveis e duas com dificuldade é menos confiante do que uma com dez saudáveis, ainda que as duas prevejam saudável.

A árvore é gulosa

Em cada nó, a busca mantém a melhor divisão que consegue ver naquele momento. Ela nunca pergunta se uma primeira divisão um pouco pior permitiria divisões muito melhores depois — testar todas as árvores completas possíveis seria astronomicamente caro. Esse atalho torna o treino rápido, e seu custo é a honestidade sobre a palavra “melhor”: a divisão vencedora é apenas a melhor escolha local, segundo a pontuação atual, para as linhas atuais.

A previsão percorre as perguntas concluídas

O treino pesquisou muitas perguntas; a previsão responde apenas às que sobreviveram. Uma nova linha começa na raiz e segue um ramo de cada vez até chegar a uma folha.

Um resultado perfeito no treino pode ser um alerta

Esta árvore classifica corretamente as dez sementes de treino. Isso é conveniente para ensinar, porque todas as etapas ficam visíveis. Em dados reais, a perfeição costuma ser um sintoma: a árvore pode ter memorizado as linhas de treino em vez de aprender um padrão. Essa falha se chama sobreajuste, e nós a detectamos testando com dados rotulados que a árvore nunca usou ao escolher seus limiares. Limites de profundidade, tamanhos mínimos de grupo, ganho mínimo e poda expressam o mesmo princípio: um novo ramo precisa merecer sua complexidade.

Além do plano

Mais características, os mesmos dois laços

Todos os experimentos até aqui usaram duas características, e essa foi uma escolha de cenário, não de método. Duas características cabem em uma tela, então cada pergunta podia ser desenhada como uma linha. Mas repare no que a busca de fato consumiu: ela ordenou uma coluna, tomou pontos médios, contou rótulos e calculou um ganho. Em nenhum momento o algoritmo olhou para o desenho. Ele leu colunas.

Então deixe que ele leia mais colunas. A tabela abaixo descreve doze mudas de estufa com três medições cada — luz solar, água e temperatura. Uma terceira característica já exigiria um gráfico tridimensional, e uma quarta inviabilizaria o desenho por completo. A tabela não tem esse limite, então desta vez a própria tabela é o espaço dos dados.

Nada na receita muda. Para cada característica — agora três — epara cada limiar de ponto médio dessa característica, calcule o ganho de Gini da pergunta que elas formam e lembre a melhor vista até agora. Doze valores distintos por coluna geram onze pontos médios, então a busca na raiz testa exatamente 3 × 11 = 33 candidatas. Depois, a pergunta vencedora divide as linhas em dois grupos, e a mesma busca roda de novo dentro de qualquer grupo que continue misturado.

A pergunta vencedora da raiz veio da coluna de temperatura — uma característica que nenhum gráfico bidimensional de luz solar e água conseguiria sequer mostrar. O laço não precisou saber disso de antemão; a temperatura simplesmente produziu o maior ganho, e a memória a manteve. A recursão então rodou mais duas vezes: dentro do grupo quente, a água separou as três mudas com pouca água, e dentro do grupo quente e irrigado, a luz solar isolou a única muda sombreada. Três buscas, três características, quatro folhas puras — cada coluna conquistou seu nó vencendo uma busca local.

Essa é toda a generalização. O laço nunca pergunta quantas colunas a tabela tem; ele só pede a próxima. Dez características significariam dez pistas no registro e um laço mais longo — não uma ideia nova. Os gráficos de duas características desta lição foram um andaime para os seus olhos. O algoritmo esteve lendo a tabela o tempo todo.

Guarde o menor modelo mental que ainda seja útil

Você construiu a árvore primeiro e conheceu o algoritmo depois — e essa ordem era o ponto central. A fórmula não trouxe nenhuma ideia nova; o ganho de Gini apenas transformou o julgamento que os seus olhos já faziam em um número que um laço consegue maximizar. O diagrama nunca foi o ponto de partida. Ele foi o resultado.