Please enable JavaScript.
Coggle requires JavaScript to display documents.
Aula 07 - Arvores de Decisão, image - Coggle Diagram
Aula 07 - Arvores de Decisão
Arvores de Decisão
O que é?
Considerando um conjunto de atributos e uma classe alvo, podemos montar uma árvore de decisão que representa o conjunto de atributos que nos levam a classe alvo em cada cenário
São representações simbólicas dos possíveis resultados de uma série de escolhas
Utiliza uma técnica do paradigma de aprendizado simbólico, onde os padrões gerados são facilmente interpretados
Composição de uma AD
Nós internos
Atributos avaliados
Ramos
São os valores que resultam da avaliação do atributo, ou seja, os possíveis valores que o atributo pode conter
Nós folhas
Atribui uma classe para um determinado ramo
Algoritmos de Indução
Os algoritmos das AD geralmente utilizam uma estrategia gulosa que opera da raiz para as folhas (top-down)
Caracteristicas dessa estrategia
Diminuição do Espaço de Busca
Avaliar todas as possíveis variações de árvores de decisão é impraticável, logo, a abordagem gulosa é bem aceita
Dividir e Conquistar
É uma estrategia recursiva, onde o conjunto de dados é particionado em subconjuntos conforme a árvore é construída
Arvore com Bom Desempenho
Por não avaliar todas as possíveis variações, nem sempre a estratégia gulosa leva a melhor árvore de decisão, porém, é uma solução ótima
Representação no Hiperplano
As arvores de decisão criam hiperplanos com o objetivo de separar exemplos de classes distintas
Cada decisão sobre um atributo gera hiperplanos de separação perpendiculares aos eixos dos atributos
Após o treinamento/construção da AD, se um novo exemplo "cair" em uma das regiões demarcadas, ele receberá a classe da região
Ao selecionar o primeiro critério de divisão, devemos chamar a função de criação de ramos da AD, para verificar se é necessário realizar um novo particionamento/ramos
Tipos de atributos na tomada de decisão
Atributo numérico
Maior ou menor que um limiar
Atributo discreto
Pertence ou não a um subconjunto de valores
Generalização de Arvore de Decisão
Durante a construção da arvore de decisão usaremos apenas parte das informações da nossa base de dados
Isso deve acontecer pois a avaliação da AD usará exemplos novos, que não foram vistos no treinamento
Dessa forma a AD não pode ser muito ajustada aos dados de treinamento, pois podemos ter um overfitting
Para permitir a generalização da AD, podemos usar a poda dos ramos para que ela não se ajuste demais aos exemplos de treinamento
O objetivo da poda é remover nós da AD e simplificar os hiperplanos gerados
Tipos de Poda
Pré-poda
Aplicada durante a construção da AD
Durante a construção um critério pré-definido é analisado e define ou não particionar mais o conjunto de treinamento
Se um nó é criado para atender a 1 único exemplo, a AD está se ajustado demais para conjunto de dados, portanto, cortamos o nó em questão
Essa situação pode levar a um mau desempenho no momento dos testes
É comum permitir que a AD possua um nível de erro aceitável durante a sua construção, pois isso permitirá a generalização para os demais casos
Caracteristicas da pré-poda
Evita gastar tempo/recursos
Pois as podas são feitas em tempo de execução, economizando recurso computacional
Analisa a melhor forma de particionar um subconjunto
Usa medidas como significância estatística, ganho de informação, redução de erro
A definição do valor limite não é simples
Depende muito do valor utilizado
Valor grande
Pode terminar o particionamento antes que alcance os beneficios de divisões subsequentes
Valor baixo
Pode resultar em pouca simplificação
Pós-poda
Aplicada após a construção da AD
Normalmente é definido um nível máximo da arvore e todos os ramos mais profundos que esse nível serão podados
Quantos mais nós a AD possui, mas ela está ajustada aos exemplos de treinamento, ao remover parte dos nós, teremos uma AD com maior generalização e menor risco de overfitting
Caracteristicas da pós-poda
Custo computacional
O custo computacional será descartado pois parte da arvore será descartada após a poda
Construir a arvore para depois podar, é mais lento, porém, é mais confiável
Seleção de Atributos
O método de divisao determina o critério de divisão, ou seja, qual atributo será utilizado como teste em um nó da arvore
Os algoritmos de AD são gulosos e não retrocedem uma vez que um teste foi selecionado para particionar o conjunto atual de exemplos, a escolha é fixada e escolhas alternativas não são exploradas
A seleção de atributos pode ser feita das seguintes formas
Aleatoria
Seleciona qualquer atributo aleatoriamente
Menos valores
Seleciona o atributo com a menor quantidade de valores possíveis
Mais valores
Seleciona o atributo com a maior quantidade de valores possíveis
Medidas de seleção de atributos
Ganho de informação máximo
Sendo
info(X,D)
--> O valor da entropia esperada
gain(X,D)
--> O valor do ganho de informação
info(D)
--> O valor da entropia
Exemplo
Ganho de informação
1 more item...
Entropia do conjunto
1 more item...
Razão de ganho
Índice Gini
Ponto importante antes das medidas de seleção abaixo!!!!
Entropia
A entropia indica o nível de desordem nos dados, quanto maior a desordem, maior a entropia
Para dados de classificação a entropia indica a mistura de classes em um conjunto de exemplos, quanto mais misturados maior a entropia
Exemplo
1 more item...
Sendo
log(pi)
2 more items...
pi
--> A probabilidade de (
xi
) acontecer no conjunto
H
--> O valor da entropia
