Algoritmos: regressões, árvores, Random Forest × XGBoost, SVM, KNN, K-Means

A ideia que organiza o assunto

Este tópico parece pedir a memorização de uma lista de algoritmos. Não pede. Dos vinte e dois itens medidos, catorze descrevem um mecanismo corretamente e apenas perguntam a que nome esse mecanismo pertence — e, dos oito itens errados, quatro mantêm a descrição inteira certa e trocam só o nome da família. Um deles chama de regressão linear múltipla o modelo cuja saída fica entre 0 e 1; outro chama de técnica de regressão o método que “determina a categoria de um objeto”; o terceiro define regressão sem mencionar a variável de saída; e o quarto descreve “classificação de dados rotulados e predição de resultados futuros”, que é aprendizado supervisionado, e assina o k-means.

Daí a única regra que organiza o assunto: o nome do algoritmo é a última coisa a ler. Antes de decidir se o enunciado está certo, identifique o que ele diz que o modelo produz. A saída classifica o item sozinha:

• um valor numérico contínuo — regressão;
• uma classe, uma categoria, um rótulo de um conjunto finito — classificação;
• grupos que o próprio algoritmo descobre e não sabe nomear — agrupamento.

Só depois de ter enquadrado a saída você olha para o nome que o item assinou. Se os dois não baterem, o item está errado, por mais correta que esteja a frase inteira.

A segunda consequência é igualmente barata: a saída de um algoritmo é propriedade dele, o nome é etiqueta. Regressão logística produz probabilidade — qualquer frase com “valor entre 0 e 1” ou “probabilidade do evento” está falando dela, assine quem assinar. Agrupamento produz grupos anônimos — qualquer frase que faça um algoritmo de agrupamento devolver rótulos com significado (pessoa, local, spam) inventou uma capacidade que ele não tem.

Duas fronteiras deste tópico, para não procurar aqui o que está em outro lugar. Por que um modelo erra em dados novos — superajuste, subajuste, viés e variância, regularização, validação cruzada — é da nota de ML: pipeline, ainda que seja ela que explique por que florestas e métodos de conjunto funcionam. Como se mede o acerto — matriz de confusão, precisão, revocação, AUC — é da nota de Métricas. E o que torna um aprendizado supervisionado ou não é da nota de Tipos de aprendizado; aqui a rotulação aparece apenas como característica de cada algoritmo.

Por que se usa (e o que custa)

Não existe algoritmo melhor: existe troca. Cada família deste tópico compra uma coisa e paga em outra, e reconhecer o par é o que permite julgar itens que anunciam “uma das vantagens” ou “uma das limitações”.

Regressão linear compra interpretação. Cada coeficiente diz quanto a resposta muda quando a preditora anda uma unidade, o que é raro e valioso. Paga em rigidez: só captura relação linear, é sensível a valores discrepantes e sofre quando as preditoras são correlacionadas entre si — a multicolinearidade, que inflaciona e desestabiliza os coeficientes.

Árvore de decisão compra legibilidade: o caminho da raiz até a folha é uma regra em português, auditável por quem não é estatístico, e ela lida com atributos numéricos e categóricos sem normalização. Paga em instabilidade. A construção é gulosa — escolhida uma divisão, ela nunca é revista — e por isso um corte indevido no topo contamina toda a subárvore abaixo dele. Sem poda, a árvore cresce até memorizar o treinamento.

Métodos de conjunto — floresta aleatória, boosting — compram exatamente a correção dessa instabilidade, combinando muitas árvores para que o erro de uma não decida o resultado. Pagam em opacidade e em custo: ganha-se acurácia e perde-se a regra legível que era a razão de usar a árvore, e treinar centenas de árvores custa o que custa uma só, multiplicado. O que sobra de interpretação é a importância das variáveis — quanto cada preditora reduziu a impureza ao longo da floresta, ou quanto a acurácia cai quando ela é embaralhada. Guarde esse resíduo, porque é dele que sai o item errado do tópico: negar que a floresta diferencie as variáveis é negar o pouco de interpretação que ela ainda devolve. Três dos vinte e dois itens do tópico cobram floresta aleatória; boosting, nenhum.

SVM compra fronteira ótima e bom desempenho em espaços de muitas dimensões, inclusive quando há mais atributos que exemplos. Paga em custo de treinamento sobre bases grandes, em sensibilidade à escala dos atributos e na escolha do núcleo e de seus parâmetros — e entrega um lado da fronteira, não uma probabilidade.

Naive Bayes compra velocidade e robustez com pouco dado, e aceita naturalmente atributos textuais. Paga com uma suposição que quase nunca é verdadeira: a independência entre os atributos. Funciona bem apesar disso, o que é justamente o que o torna cobrável.

Agrupamento compra estrutura onde não há rótulo nenhum. Paga em ambiguidade: não existe resposta certa contra a qual comparar, a partição encontrada depende da medida de distância e da inicialização, e a interpretação do que cada grupo significa é sempre humana.

Como funciona

Regressão linear. Ajusta uma reta — ou um hiperplano, no caso múltiplo — entre as variáveis independentes e uma variável dependente contínua, escolhendo os coeficientes que minimizam a soma dos quadrados dos resíduos. A previsão é um número na escala da própria resposta, sem limite superior nem inferior. É supervisionada: o treinamento exige exemplos com o valor da resposta já conhecido.

Regressão logística. Apesar do nome, é classificador. Aplica a função logística à combinação linear das preditoras, o que comprime o resultado no intervalo de 0 a 1 e permite lê-lo como probabilidade de ocorrência do evento; um limiar converte essa probabilidade em classe. Toda vez que um enunciado fala em “valor entre 0 e 1”, está descrevendo esta, não a linear.

Árvore de decisão. Particiona recursivamente o espaço dos atributos. Em cada nó, escolhe o atributo e o ponto de corte que melhor separam os dados segundo um critério de impureza, e repete dentro de cada partição criada. O objeto é classificado percorrendo-se a árvore da raiz até a folha, e a folha carrega a classe — é o que os enunciados chamam de “atribuir informação de tipo”. Serve também para regressão, quando a folha guarda um valor numérico em vez de uma classe.

Floresta aleatória. Método de conjunto sobre árvores de decisão, e supervisionado: cada árvore é treinada com a resposta conhecida. Tem duas aleatoriedades, e é delas que vem tudo o que se cobra. A primeira está nos dados: cada árvore recebe uma amostra aleatória com reposição do conjunto de treinamento — o bootstrap do bagging —, de modo que nenhuma árvore vê exatamente os mesmos exemplos, e os que ficam de fora de cada amostra servem de validação sem custo. A segunda está nos atributos: em cada divisão, a árvore só pode escolher entre um subconjunto sorteado das preditoras, o que impede que uma variável muito forte domine todas as árvores e as torne cópias umas das outras. As árvores são construídas em paralelo e são independentes entre si; a decisão final é por voto majoritário na classificação e por média na regressão. O ganho é redução de variância — o erro de uma árvore isolada não decide o resultado —, e por isso a floresta faz as duas tarefas que a árvore faz: classifica e regride. Como as variáveis competem divisão a divisão e são avaliadas pelo mesmo critério de impureza, a floresta produz ainda um ranking de importância das variáveis, por redução média de impureza ou por permutação: importância desigual por construção, e nunca a mesma para todas.

SVM — máquina de vetores de suporte. Entre os infinitos hiperplanos que separam duas classes, escolhe aquele de margem máxima, isto é, o mais distante dos pontos mais próximos de cada lado. Esses pontos são os vetores de suporte, e o hiperplano é escrito em função apenas deles — daí a descrição consagrada de que a SVM combina um modelo linear com aprendizagem baseada em instâncias. É não probabilística: devolve o lado da fronteira, não a chance de pertencer à classe. Para dados que não são linearmente separáveis, a função de núcleo projeta o problema em um espaço de dimensão maior, onde um hiperplano volta a servir — por isso a SVM realiza classificações lineares e não lineares. Existe a versão para regressão, a SVR.

Classificadores bayesianos. São estatísticos: decidem por probabilidade. Aplicam o teorema de Bayes para calcular, a partir das evidências observadas no objeto, a probabilidade a posteriori de ele pertencer a cada classe, e atribuem a de maior probabilidade. O Naive Bayes é o caso simplificado: supõe que os atributos são condicionalmente independentes entre si dada a classe, o que permite multiplicar probabilidades individuais em vez de estimar a distribuição conjunta. É o “ingênuo” do nome. Tem variantes conforme o atributo — gaussiana para numéricos contínuos, multinomial para contagem de termos, que é o uso clássico em filtragem de spam.

k-means. Agrupamento por particionamento, baseado em centroides. Recebe k como entrada obrigatória, sorteia k centroides iniciais e itera: cada objeto é atribuído ao centroide mais próximo, cada centroide é recalculado como a média dos objetos que recebeu, e repete-se até estabilizar. É uma heurística — encontrar a melhor partição é intratável, e o algoritmo converge para um ótimo local, dependente da inicialização. Não usa rótulo algum e não sabe o que os grupos que encontrou significam.

Agrupamento hierárquico. Dois sentidos opostos e um mesmo produto, o dendrograma. O aglomerativo vai de baixo para cima: começa com cada objeto em seu próprio grupo e funde sucessivamente os mais próximos até restar um único cluster com todos dentro. O divisivo vai de cima para baixo: começa com todos os objetos em um grupo só e o subdivide até uma regra de parada. Não exige o número de grupos previamente: o dendrograma é cortado depois, na altura que se quiser.

Outros métodos de agrupamento. Agrupar não é sinônimo de k-means. A literatura de mineração de dados reúne sob análise de agrupamentos, além dos métodos estatísticos de particionamento e hierárquicos, as redes neurais de mapas auto-organizáveis, a lógica difusa do agrupamento com pertinência parcial e os algoritmos genéticos que buscam a melhor partição por evolução.

Boosting e kNN — o que resta do vocabulário do título. O boosting treina árvores em sequência, cada uma corrigindo os erros da anterior, e o ganho é redução de viés — é a família do XGBoost, e é o contraponto exato da floresta, que treina em paralelo e reduz variância. O kNN não constrói modelo nenhum: guarda os exemplos e, diante de um caso novo, olha os k vizinhos mais próximos e decide por maioria (ou média); é supervisionado e classifica. Em vinte e dois itens medidos, nenhum dos dois é cobrado pelo nome — mas o kNN decide um item por ausência, porque é ele, e não o k-means, o dono da descrição que um enunciado errado assinou.

O que decide os itens

A saída decide a família. É o eixo mais cobrado do tópico e resolve sozinho cinco dos itens:

o item diz que o modelo produz	família	vocabulário que a acompanha
valor numérico contínuo, sem limite	regressão	contínuo, valor, quantidade, previsão numérica
valor entre 0 e 1, probabilidade do evento	regressão logística (classificação)	probabilidade, chance, limiar
categoria de um conjunto finito	classificação	classe, rótulo, tipo, finito, discreto
grupos que o algoritmo descobre	agrupamento	natural, similaridade, distância, sem rótulo

Cada algoritmo e a tarefa que faz — a coluna da direita é onde a banca mora:

algoritmo	faz	não faz
regressão linear	prevê valor contínuo	não devolve probabilidade nem classe
regressão logística	classifica, devolvendo probabilidade	não prevê valor contínuo ilimitado
árvore de decisão	classifica e também faz regressão	não evita a propagação de erro de divisão
floresta aleatória	classifica e faz regressão; mede a importância das variáveis	não trata as variáveis como igualmente importantes; não treina em sequência
SVM	classifica (linear e não linear) e também faz regressão	não é probabilística; não faz apenas regressão
Naive Bayes	classifica atributos numéricos e textuais	não exige independência real entre atributos
k-means	agrupa objetos não rotulados	não classifica dado rotulado nem nomeia os grupos
hierárquico	agrupa e produz o dendrograma	não exige o número de grupos previamente
kNN	classifica por vizinhança (supervisionado)	não agrupa em k clusters

Pares que a banca troca de lado:

	primeiro	segundo
linear × logística	saída contínua, escala da resposta	saída entre 0 e 1, probabilidade
regressão × classificação	espaço de saída contínuo e infinito	conjunto finito de hipóteses e categorias
aglomerativo × divisivo	de baixo para cima: cada objeto um grupo → um grupo só	de cima para baixo: um grupo só → subdivisões
k-means × hierárquico	k é entrada obrigatória	número de grupos sai do corte do dendrograma
k-means × kNN	agrupa, não supervisionado, k = nº de grupos	classifica, supervisionado, k = nº de vizinhos
probabilístico × não	Naive Bayes, redes bayesianas, logística	SVM, árvore, k-means
floresta × boosting	árvores em paralelo, reduz variância	árvores em sequência, reduz viés

O verbo do enunciado. Uma regularidade medida e barata de aplicar: dos sete itens do corpus cujo verbo é permissivo — “incluem”, “podem ser usadas”, “poderia ser utilizado”, “são comuns em”, “são utilizados algoritmos”, “pode ser usado tanto… quanto”, “pode ser utilizado para” — os sete são Certo. Do outro lado, os dois itens que fecham a porta — “realizam apenas tarefas de regressão”, “a mesma importância para todas as variáveis” — são os dois Errado. Enunciado que abre possibilidade não tem o que exceder; enunciado que exclui alternativas ou nivela o que o algoritmo distingue precisa sobreviver a um único contraexemplo.

Mas o verbo não protege contra o nome errado. A regularidade acima vale para quem restringe; ela não vale para quem apenas descreve. Três dos itens errados do tópico são descrições impecáveis, sem nenhuma palavra absoluta, que falham só porque a assinatura não corresponde ao mecanismo — “na regressão linear múltipla, a previsão é um valor entre 0 e 1”, “o algoritmo de aprendizagem supervisionada K-means é amplamente utilizado para a classificação de dados rotulados”. Modalidade permissiva é bom sinal; modalidade descritiva não é sinal nenhum, e é aí que este tópico mora.

A frase de identidade de cada algoritmo, na forma em que a banca a escreve:

algoritmo	a frase que o identifica
SVM	hiperplano de margem máxima; classificador não probabilístico; combina modelo linear com aprendizagem baseada em instâncias
Naive Bayes	supõe independência entre as variáveis
classificador bayesiano	classificador estatístico que prediz a probabilidade de pertinência a uma classe
k-means	baseado em centroides; refinamento iterativo; exige k
agrupamento	algoritmos com heurísticas para descobrir agregações naturais
árvore de decisão	atribui informação de tipo; da raiz à folha
floresta aleatória	aprendizado de conjunto; múltiplas árvores; amostra aleatória com reposição; decisão por voto
regressão linear	relação entre variáveis independentes e uma dependente contínua

Como a CEBRASPE derruba você aqui

Medido sobre os vinte e dois itens do tópico: catorze Certo e oito Errado. A proporção já é informação — a maioria dos enunciados descreve corretamente um algoritmo, e a leitura desconfiada demais custa itens.

Trocar o nome e manter a descrição — quatro dos oito itens errados. É o padrão dominante e sempre a mesma engenharia: a frase descreve um mecanismo real, sem um erro sequer, e assina o nome do vizinho de vocabulário. “Na regressão linear múltipla”, seguido da saída entre 0 e 1 que é da logística. “As técnicas de regressão”, seguidas de “conjunto finito de hipóteses” e “determinar a categoria de um objeto”, que são de classificação. “O algoritmo de aprendizagem supervisionada K-means”, seguido de “classificação de dados rotulados e predição de resultados futuros” — a tarefa descrita é de supervisionado, e o algoritmo assinado é o único da lista que nunca vê um rótulo; trocado o nome por kNN, a frase inteira fica de pé. E a versão por subtração: “uma relação entre as variáveis de entrada de um algoritmo” como definição de regressão linear — faltou o outro lado da relação, a variável dependente, e sem ele o que sobra descreve multicolinearidade, que é um problema do modelo e não o objetivo dele. A defesa é uma ordem de leitura: classifique a saída descrita, decida de que família se trata, e só então leia o nome que o item assinou.

Anunciar como vantagem o que é limitação conhecida. “Uma das vantagens da técnica de árvore de decisão para regressão é evitar a propagação de erros, mesmo que uma divisão ocorra indevidamente.” É exatamente ao contrário: a árvore é gulosa e hierárquica, a divisão escolhida nunca é revista, e o corte indevido no topo contamina todos os ramos abaixo. Sempre que o item abrir com “uma das vantagens” ou “uma das características positivas”, confira se o que vem depois não é, na literatura, a fraqueza clássica do método — e as da árvore são três: propagação do erro de divisão, instabilidade diante de pequenas mudanças nos dados e superajuste sem poda.

Fechar a lista de tarefas com “apenas”. “Os algoritmos SVM realizam apenas tarefas de regressão.” A SVM nasceu classificadora; a SVR existe, mas não é a única coisa que a técnica faz. Neste tópico, quase toda restrição de tarefa está errada, porque as famílias principais atravessam mais de uma: SVM e árvores classificam e regridem, redes neurais fazem as duas e ainda agrupam. Localize a palavra de exclusão — apenas, somente, exclusivamente, unicamente — e teste-a com um contraexemplo antes de ler o resto.

Inventar o mecanismo dentro de um “pois”. “É correto utilizar o NER, pois, por meio da utilização do algoritmo K-means, os grupos relacionados aos termos que se deseja segmentar — no caso, pessoa e local — podem ser encontrados.” A conclusão é verdadeira: NER é mesmo a técnica que marca Paulo como pessoa e Ceará como local. A justificativa é falsa, e isso basta. O k-means reparte objetos por distância e não sabe nomear o que encontrou; rotular entidades é rotulação de sequências, treinada sobre texto anotado. Quando o enunciado liga tarefa e algoritmo com pois, porque ou uma vez que, julgue a ligação, não a tarefa.

Mas nem todo uso semântico do agrupamento é armadilha. Compare o item do NER com este, que é Certo: “O algoritmo de agrupamento K-means […] pode ser utilizado para, a partir de uma base de dados de uma rede social, identificar comunidades de usuários com interesses comuns.” Os dois mandam o k-means para uma tarefa de significado, e só um cai. A diferença é quem nomeia: no segundo, o algoritmo apenas separa usuários parecidos e a leitura de que aquilo é uma comunidade de interesse é do analista, depois; no primeiro, o algoritmo teria de saber, sozinho, que um grupo é pessoa e o outro é local — categorias definidas de antemão, que só o rótulo entrega. Descobrir grupo, pode; devolver rótulo previamente definido, não pode.

Floresta aleatória: três itens, e o errado nivela o que o método distingue. Dos três, dois descrevem o mecanismo e estão certos — que é conjunto de árvores com amostra aleatória com reposição, e que serve tanto a regressão quanto a classificação. O terceiro afirma que a floresta “atribui a mesma importância para todas as variáveis ao fazer as predições”, e é Errado por negar exatamente o que ela mede: as preditoras competem em cada divisão pelo critério de impureza, o subconjunto sorteado muda de nó para nó, e o método devolve um ranking de importância. Achatar em “mesma importância”, “mesmo peso” ou “tratados da mesma forma” um mecanismo cuja razão de existir é discriminar é a forma econômica de negar uma função sem parecer que se está negando — o mesmo movimento do “apenas”, por outra porta. Os dois pontos vizinhos, quando a floresta voltar a cair: a reamostragem dos dados é com reposição, e as árvores são construídas em paralelo — em sequência é o boosting.

O que o título promete e ainda não caiu. Em vinte e dois itens, zero cobram boosting ou XGBoost e zero cobram kNN pelo nome. O corpus tem dois itens de kNN fora deste tópico, e os dois foram anulados, inclusive um que dizia que o kNN “agrupa os dados em k clusters, de forma não supervisionada”, que é a confusão com o k-means em estado puro. Estude o par mesmo assim, porque ele já decidiu um item aqui por ausência — o enunciado que descreve classificação de dados rotulados e assina k-means: k-means agrupa sem rótulo, kNN classifica com rótulo; o k de um é o número de grupos, o do outro é o número de vizinhos.

Erros clássicos

Ler “regressão logística” como técnica de regressão. É classificador. O nome vem da função logística, não da tarefa. Saída entre 0 e 1 lida como probabilidade é sempre ela.

Confundir k-means com kNN pela letra k. São opostos em tudo: um é agrupamento não supervisionado e o k conta grupos; o outro é classificação supervisionada e o k conta vizinhos.

Achar que agrupamento devolve rótulos com significado. Devolve partições anônimas. Quem batiza os grupos é o analista, depois. Todo item que faça um algoritmo de agrupamento identificar “pessoa”, “local”, “spam” ou “empregado” está errado pela mesma razão. Cuidado com a leitura larga demais, porém: usar agrupamento para uma finalidade semântica — segmentar clientes, encontrar comunidades de usuários com interesses comuns — está certo, porque aí o algoritmo só separa os semelhantes e o significado é atribuído depois, por quem lê. O erro é exigir que a categoria saia nomeada do próprio algoritmo.

Supor que a SVM devolve probabilidade. Devolve o lado do hiperplano. Quem devolve probabilidade de pertinência são os métodos bayesianos e a logística.

Entender a suposição de independência do Naive Bayes como exigência. O algoritmo assume independência; ele não a exige. Funciona bem mesmo quando ela é violada, e é por isso que continua em uso.

Tomar “agrupamento” por “k-means”. Redes neurais, lógica difusa, métodos estatísticos e algoritmos genéticos também são métodos de análise de agrupamentos, e enumerações abertas com “incluem” costumam estar certas.

Achar que o hierárquico precisa do número de grupos. Não precisa. É o k-means que precisa. O hierárquico produz o dendrograma inteiro e a decisão vem do corte.

Esperar do agrupamento a partição ótima. Os algoritmos são heurísticos e convergem para ótimos locais. Item que prometa a melhor partição garantida confundiu heurística com solução exata.

Achar que a floresta aleatória pesa todas as variáveis igualmente. Não pesa, e ainda mede o quanto cada uma vale. Voto igual entre as árvores não é peso igual entre as variáveis: a árvore vota, a variável compete.

Trocar as duas aleatoriedades da floresta. A amostra de dados de cada árvore é sorteada com reposição; o subconjunto de atributos é sorteado a cada divisão. Item que diga amostragem sem reposição, ou que sorteie os atributos uma vez só por árvore, mexeu no mecanismo.

Confundir paralelo com sequência. Floresta aleatória treina árvores independentes em paralelo e reduz variância; boosting treina em sequência, cada árvore corrigindo a anterior, e reduz viés. É a troca mais provável assim que o boosting aparecer no tópico.