Entendendo pela Implementação: Árvore de Decisão

Imagem do autor

Muitos modelos avançados de aprendizado de máquina, como florestas aleatórias ou algoritmos de aumento de gradiente, como XGBoost, CatBoost ou LightGBM (e até codificadores automáticos!) contam com um ingrediente comum crucial: o árvore de decisão!

Sem entender as árvores de decisão, é impossível entender também qualquer um dos algoritmos avançados de ensacamento ou aumento de gradiente mencionados acima, o que é uma vergonha para qualquer cientista de dados! Então, vamos desmistificar o funcionamento interno de uma árvore de decisão implementando uma em Python.

Neste artigo, você aprenderá

• por que e como uma árvore de decisão divide os dados,
• o ganho de informação e
• como implementar árvores de decisão em Python usando NumPy.

Você pode encontrar o código em meu Github.

Para fazer previsões, as árvores de decisão dependem splitting o conjunto de dados em partes menores de forma recursiva.

Imagem do autor

Na imagem acima, você pode ver um exemplo de divisão — o conjunto de dados original é separado em duas partes. Na próxima etapa, ambas as partes são divididas novamente e assim por diante. Isso continua até que algum tipo de critério de parada seja atingido, por exemplo,

• se a divisão resultar em uma parte vazia
• se uma certa profundidade de recursão foi atingida
• se (após as divisões anteriores) o conjunto de dados consistir apenas em alguns elementos, tornando desnecessárias outras divisões.

Como encontramos essas divisões? E por que nos importamos? Vamos descobrir.

Motivação

Suponhamos que queremos resolver um binário problema de classificação que nós mesmos criamos agora:

import numpy as np
np.random.seed(0) X = np.random.randn(100, 2) # features
y = ((X[:, 0] > 0) * (X[:, 1] < 0)) # labels (0 and 1)

Os dados bidimensionais se parecem com isso:

Imagem do autor

Podemos ver que existem duas classes diferentes — roxo em cerca de 75% e amarelo em cerca de 25% dos casos. Se você alimentar esses dados para uma árvore de decisão classificador, esta árvore tem inicialmente os seguintes pensamentos:

“Existem dois rótulos diferentes, o que é muito confuso para mim. Quero limpar essa bagunça dividindo os dados em duas partes — essas partes devem ser mais limpas do que os dados completos anteriores.” — árvore que ganhou consciência

E assim a árvore faz.

Imagem do autor

A árvore decide fazer uma divisão aproximadamente ao longo do x-eixo. Isso tem o efeito de que a parte superior dos dados agora está perfeitamente limpar \ limpo, o que significa que você só encontra uma única classe (roxo neste caso) lá.

No entanto, a parte inferior ainda é bagunçado, ainda mais confuso do que antes em certo sentido. A proporção de classe costumava ser de cerca de 75:25 no conjunto de dados completo, mas nesta parte menor é de cerca de 50:50, o que é o mais confuso possível

 Observação: Aqui, não importa que o roxo e o amarelo estejam bem separados na foto. Apenas o quantidade bruta de rótulos diferentes na contagem de duas partes.

Imagem do autor

Ainda assim, isso é bom o suficiente como primeiro passo para a árvore, e assim ela continua. Embora não crie outra divisão no topo, limpar parte, ele pode criar outra divisão na parte inferior para limpá-la.

Imagem do autor

Et voilà, cada uma das três partes separadas é completamente limpa, pois encontramos apenas uma única cor (etiqueta) por peça.

É realmente fácil fazer previsões agora: se um novo ponto de dados chegar, basta verificar em qual dos três partes encontra-se e dar-lhe a cor correspondente. Isso funciona tão bem agora porque cada parte é limpar. Fácil, certo?

Imagem do autor

Tudo bem, estávamos falando sobre limpar e bagunçado dados, mas até agora essas palavras representam apenas uma ideia vaga. Para implementar qualquer coisa, temos que encontrar uma maneira de definir limpeza.

Medidas de Limpeza

Vamos supor que temos alguns rótulos, por exemplo

y_1 = [0, 0, 0, 0, 0, 0, 0, 0] y_2 = [1, 0, 0, 0, 0, 0, 1, 0]
y_3 = [1, 0, 1, 1, 0, 0, 1, 0]

Intuitivamente, você₁ é o conjunto de rótulos mais limpo, seguido por você₂ e depois y₃. Até aí tudo bem, mas como podemos colocar números sobre esse comportamento? Talvez a coisa mais fácil que vem à mente seja a seguinte:

Basta contar a quantidade de zeros e a quantidade de uns. Calcule sua diferença absoluta. Para torná-lo mais agradável, normalize-o dividindo o comprimento dos arrays.

Por exemplo, você₂ tem 8 entradas no total — 6 zeros e 2 uns. Portanto, nossa definição personalizada pontuação de limpeza seria |6 – 2| / 8 = 0.5. É fácil calcular que pontuações de limpeza de você₁ e y₃ são 1.0 e 0.0, respectivamente. Aqui, podemos ver a fórmula geral:

Imagem do autor

Aqui, n₀ e n₁ são os números de zeros e uns, respectivamente, n = n₀ + n₁ é o comprimento da matriz e p₁ = n₁ / n é a parte dos 1 rótulos.

O problema com essa fórmula é que ela é especificamente adaptado ao caso de duas classes, mas muitas vezes estamos interessados ​​na classificação multiclasse. Uma fórmula que funciona muito bem é a Medição de impureza de Gini:

Imagem do autor

ou o caso geral:

Imagem do autor

Funciona tão bem que o scikit-learn adotou como medida padrão por sua DecisionTreeClassifier classe.

Imagem do autor

 Observação: Gini medidas bagunça em vez de limpeza. Exemplo: se uma lista contiver apenas uma única classe (=dados muito limpos!), todos os termos da soma serão zero, portanto a soma será zero. O pior caso é se todas as classes aparecerem o número exato de vezes, caso em que o Gini é 1–1/C onde C é o número de aulas.

Agora que temos uma medida de limpeza/bagunça, vamos ver como ela pode ser usada para encontrar boas divisões.

Encontrando Divisões

Existem muitas divisões que escolhemos, mas qual é a boa? Vamos usar nosso conjunto de dados inicial novamente, juntamente com a medida de impureza de Gini.

Imagem do autor

Não vamos contar os pontos agora, mas vamos supor que 75% são roxos e 25% são amarelos. Usando a definição de Gini, a impureza do conjunto de dados completo é

Imagem do autor

Se dividirmos o conjunto de dados ao longo do x-eixo, como feito antes:

Imagem do autor

A parte superior tem uma impureza Gini de 0.0 e a parte de baixo

Imagem do autor

Em média, as duas partes têm uma impureza de Gini de (0.0 + 0.5) / 2 = 0.25, o que é melhor do que os 0.375 anteriores de todo o conjunto de dados. Também podemos expressá-lo em termos do chamado ganho de informação:

O ganho de informação desta divisão é 0.375 – 0.25 = 0.125.

Fácil assim. Quanto maior o ganho de informação (isto é, quanto menor a impureza de Gini), melhor.

Observação: Outra divisão inicial igualmente boa seria ao longo do eixo y.

Uma coisa importante a ter em mente é que é útil pesar as impurezas Gini das peças pelo tamanho das peças. Por exemplo, suponhamos que

• a parte 1 consiste em 50 pontos de dados e tem uma impureza Gini de 0.0 e
• a parte 2 consiste em 450 pontos de dados e tem uma impureza Gini de 0.5,

então a impureza Gini média não deve ser (0.0 + 0.5) / 2 = 0.25, mas sim 50 / (50 + 450) * 0.0 + 450 / (50 + 450) * 0.5 = 0.45.

Ok, e como encontramos a melhor divisão? A resposta simples, mas séria, é:

Apenas experimente todas as divisões e escolha aquela com o maior ganho de informação. É basicamente uma abordagem de força bruta.

Para ser mais preciso, as árvores de decisão padrão usam divide ao longo dos eixos coordenados, Isto é, xᵢ = c para algum recurso i e limiar c. Isto significa que

• uma parte dos dados divididos consiste em todos os pontos de dados x de xᵢce
• a outra parte de todos os pontos x de xᵢ ≥ c.

Essas regras simples de divisão provaram ser boas o suficiente na prática, mas é claro que você também pode estender essa lógica para criar outras divisões (ou seja, linhas diagonais como xᵢ + 2xⱼ = 3, por exemplo).

Ótimo, esses são todos os ingredientes que precisamos para começar agora!

Vamos implementar a árvore de decisão agora. Uma vez que consiste em nós, vamos definir um Node aula primeiro.

from dataclasses import dataclass @dataclass
class Node: feature: int = None # feature for the split value: float = None # split threshold OR final prediction left: np.array = None # store one part of the data right: np.array = None # store the other part of the data

Um nó conhece o recurso que ele usa para dividir (feature) bem como o valor de divisão (value). value também é usado como um armazenamento para a previsão final da árvore de decisão. Como vamos construir uma árvore binária, cada nó precisa conhecer seus filhos esquerdo e direito, conforme armazenados em left e right .

Agora, vamos fazer a implementação da árvore de decisão real. Estou tornando-o compatível com o scikit-learn, por isso uso algumas classes de sklearn.base . Se você não está familiarizado com isso, confira meu artigo sobre como construir modelos compatíveis com o scikit-learn.

Vamos implementar!

import numpy as np
from sklearn.base import BaseEstimator, ClassifierMixin class DecisionTreeClassifier(BaseEstimator, ClassifierMixin): def __init__(self): self.root = Node() @staticmethod def _gini(y): """Gini impurity.""" counts = np.bincount(y) p = counts / counts.sum() return (p * (1 - p)).sum() def _split(self, X, y): """Bruteforce search over all features and splitting points.""" best_information_gain = float("-inf") best_feature = None best_split = None for feature in range(X.shape[1]): split_candidates = np.unique(X[:, feature]) for split in split_candidates: left_mask = X[:, feature] split X_left, y_left = X[left_mask], y[left_mask] X_right, y_right = X[~left_mask], y[~left_mask] information_gain = self._gini(y) - ( len(X_left) / len(X) * self._gini(y_left) + len(X_right) / len(X) * self._gini(y_right) ) if information_gain > best_information_gain: best_information_gain = information_gain best_feature = feature best_split = split return best_feature, best_split def _build_tree(self, X, y): """The heavy lifting.""" feature, split = self._split(X, y) left_mask = X[:, feature] split X_left, y_left = X[left_mask], y[left_mask] X_right, y_right = X[~left_mask], y[~left_mask] if len(X_left) == 0 or len(X_right) == 0: return Node(value=np.argmax(np.bincount(y))) else: return Node( feature, split, self._build_tree(X_left, y_left), self._build_tree(X_right, y_right), ) def _find_path(self, x, node): """Given a data point x, walk from the root to the corresponding leaf node. Output its value.""" if node.feature == None: return node.value else: if x[node.feature] node.value: return self._find_path(x, node.left) else: return self._find_path(x, node.right) def fit(self, X, y): self.root = self._build_tree(X, y) return self def predict(self, X): return np.array([self._find_path(x, self.root) for x in X])

E é isso! Você pode fazer todas as coisas que adora no scikit-learn agora:

dt = DecisionTreeClassifier().fit(X, y)
print(dt.score(X, y)) # accuracy # Output
# 1.0

Como a árvore não é regularizada, ela está superajustada, daí a pontuação perfeita do trem. A precisão seria pior em dados não vistos. Também podemos verificar a aparência da árvore via

print(dt.root) # Output (prettified manually):
# Node(
# feature=1,
# value=-0.14963454032767076,
# left=Node(
# feature=0,
# value=0.04575851730144607,
# left=Node(
# feature=None,
# value=0,
# left=None,
# right=None
# ),
# right=Node(
# feature=None,
# value=1,
# left=None,
# right=None
# )
# ),
# right=Node(
# feature=None,
# value=0,
# left=None,
# right=None
# )
# )

Como uma imagem, seria isso:

Imagem do autor

Neste artigo, vimos em detalhes como as árvores de decisão funcionam. Começamos com algumas ideias vagas, mas intuitivas, e as transformamos em fórmulas e algoritmos. No final, conseguimos implementar uma árvore de decisão do zero.

Uma palavra de cautela: nossa árvore de decisão ainda não pode ser regularizada. Normalmente, gostaríamos de especificar parâmetros como

• profundidade máxima
• tamanho da folha
• e ganho mínimo de informação

entre muitos outros. Felizmente, essas coisas não são tão difíceis de implementar, o que torna este um dever de casa perfeito para você. Por exemplo, se você especificar leaf_size=10 como um parâmetro, nós contendo mais de 10 amostras não devem mais ser divididos. Além disso, essa implementação é não eficiente. Normalmente, você não deseja armazenar partes dos conjuntos de dados em nós, mas apenas os índices. Portanto, seu conjunto de dados (potencialmente grande) está na memória apenas uma vez.

O bom é que você pode enlouquecer agora com este modelo de árvore de decisão. Você pode:

• implementar divisões diagonais, ou seja, xᵢ + 2xⱼ = 3 em vez de apenas xᵢ = 3,
• mude a lógica que acontece dentro das folhas, ou seja, você pode rodar uma regressão logística dentro de cada folha ao invés de apenas fazer uma votação majoritária, o que te dá uma árvore linear
• altere o procedimento de divisão, ou seja, em vez de usar força bruta, tente algumas combinações aleatórias e escolha a melhor, o que lhe dará uma classificador de árvore extra
• e muito mais.

 
 
Dr. Robert Kubler é Cientista de Dados da Publicis Media e Autor da Towards Data Science.

 
Óptimo estado. Original. Republicado com permissão.
 

• Conteúdo com tecnologia de SEO e distribuição de relações públicas. Seja amplificado hoje.
• Platoblockchain. Inteligência Metaverso Web3. Conhecimento Ampliado. Acesse aqui.
• Fonte: https://www.kdnuggets.com/2023/02/understanding-implementing-decision-tree.html?utm_source=rss&utm_medium=rss&utm_campaign=understanding-by-implementing-decision-tree