Power production

Por exemplo, para o conjunto de pares (x, f (x)) mostrados na Figura 2.21, deseja-se encontrar uma fun¸c˜ao h(x), chamada de hip´otese, que se aproxime de f . Podem existir diferentes hip´oteses para um mesmo conjunto de exemplos. No exemplo da Figura 2.21, pode-se aproximar h a uma reta ou a uma fun¸c˜ao senoidal. O grau de qualidade das hip´oteses depende do tamanho do espa¸co de amostras utilizado para aproximar f .

Figura 2.21: Aproxima¸c˜oes de f (x) a partir de pares (x, f (x))

Mitchell (1997) coloca que a aprendizagem, por meio da qual o sistema deduz o conhe- cimento pela observa¸c˜ao do seu ambiente, possui duas abordagens: a aprendizagem su- pervisionada e a aprendizagem n˜ao supervisionada. Na aprendizagem supervisionada, o sistema modela uma fun¸c˜ao (ou classificador) com base em dados de treinamento compostos por um valor de entrada (tipicamente um vetor de valores) e um valor de sa´ıda (ou classe). A fun¸c˜ao deve inferir o valor de sa´ıda para qualquer entrada v´alida. Mesmo que os valores de entrada sejam incompletos ou desconhecidos, o sistema deve estimar razoavelmente os valores de sa´ıda por meio de generaliza¸c˜oes e abstra¸c˜oes. J´a na aprendizagem n˜ao supervisionada, o sistema ´e provido com dados de treinamento compostos apenas por valores de entradas, ou seja, nenhum valor de sa´ıda ´e definido. O sistema deve observar os exemplos e reconhecer padr˜oes autonomamente, resultando em um conjunto de regras para as classes.

2.6.1 Arvores de Decis˜´ ao ´

Arvores de decis˜ao s˜ao m´etodos de aprendizado simb´olico bastante utilizados para a inferˆencia indutiva. Podem ser usadas para dar ao agente a capacidade de aprender, bem como para tomar decis˜oes. A aprendizagem ´e indutiva, pois cria uma hip´otese baseada em instˆancias particulares que gera conclus˜oes gerais (RUSSELL; NORVIG, 1995). Os algoritmos de ´arvores de decis˜ao basicamente dividem um problema com- plexo em partes menores e mais simples e, ap´os isso, refazem o mesmo processo com os subproblemas encontrados e assim sucessivamente at´e chegar na solu¸c˜ao.

A Figura 2.22 (a) mostra a representa¸c˜ao gr´afica de uma ´arvore de decis˜ao. No topo, temos o n´o raiz. Cada n´o de decis˜ao contem um teste de um atributo. Os ramos descendentes correspondem aos valores poss´ıveis do respectivo atributo. As folhas est˜ao associadas `as classes. Cada percurso da ´arvore - do n´o raiz `a folha - corresponde a uma regra de classifica¸c˜ao.

X1

X2 X2

X1

<a1 >a1

>a3

<a3 <a2 >a2

<a4 >a4 a2 a3 X2 a4 a1 X1 S (a) (b)

Figura 2.22: Exemplo de ´arvore de decis˜ao

A capacidade de classifica¸c˜ao das ´arvores de decis˜ao vem da divis˜ao do espa¸co definido pelos atributos em subespa¸cos conforme mostrado na Figura 2.22 (b). Cada subespa¸co corresponde a uma classe. Note que a classe referente `a regi˜ao em xadrez pode ser definida pela regra: X1 < a1 ∧ X2 < a3. O espa¸co de todos valores dos atributos S pode ser representado pela Equa¸c˜ao 2.6. Pode-se notar que uma ´arvore de decis˜ao representa uma disjun¸c˜ao de conjun¸c˜oes, na qual cada ramo ´e uma conjun¸c˜ao.

S = ( X1 < a1 ∧ X2 < a3 ) ∨ (2.6) ( X1 < a1 ∧ X1 > a3 ∧ X1 < a4 ) ∨

( X1 < a1 ∧ X2 > a3 ∧ X1 > a4 ) ∨ ( X1 > a1 ∧ X2 < a2 ) ∨ ( X1 > a1 ∧ X2 > a2 )

A implementa¸c˜ao de ´arvores de decis˜ao ´e similar a de regras if-then, sendo estruturas muito usadas em sistemas especialistas e em problemas de classifica¸c˜ao. As ´arvores de decis˜ao tomam como entrada uma situa¸c˜ao descrita por um conjunto de atributos e retornam uma decis˜ao ap´os o processamento das regras. Os atributos de entrada podem

ser discretos ou cont´ınuos. O aprendizado de valores discretos ´e chamado classifica¸c˜ao (RUSSELL; NORVIG, 1995).

Mitchell (1997) afirma que o aprendizado utilizando ´arvore de decis˜ao ´e indicado para problemas com as seguintes caracter´ısticas:

• Instˆancias s˜ao representadas atrav´es de pares atributo-valor: Instˆancias s˜ao descritas por um conjunto fixo de atributos (por exemplo: Temperatura) e seus respectivos valores (por exemplo: Quente). A situa¸c˜ao mais f´acil de apren- dizado utilizando ´arvore de decis˜ao ´e quando cada atributo assume um n´umero pequeno de poss´ıveis valores disjuntos (por exemplo, Quente, Moderado, Frio). Por´em, extens˜oes para o algoritmo b´asico permitem atribuir valores reais, por exemplo, representando Temperatura numericamente.

• A fun¸c˜ao tem valores discretos: A ´arvore de decis˜ao classifica com valores l´ogicos (Verdadeiro: sim ou Falso: n˜ao) para cada exemplo. M´etodos de ´arvore de decis˜ao podem ser facilmente estendidos para fun¸c˜oes com mais de dois va- lores poss´ıveis. Uma extens˜ao mais significativa permite utilizar fun¸c˜oes reais, entretanto a aplica¸c˜ao de ´arvores de decis˜ao neste tipo de caso ´e menos comum. • Permitem descri¸c˜oes disjuntas Como notado acima, ´arvores decis˜ao natural- mente representam express˜oes disjuntas. Os dados de treinamento podem conter erros. As ´arvores de decis˜ao s˜ao robustas a erros, tanto erros nas classifica¸c˜oes dos exemplos de treinamento, quanto erros nos valores dos atributos que descrevem estes exemplos.

• Os dados de treinamento podem conter valores de atributo indefini- dos: Podem ser usados m´etodos de ´arvore de decis˜ao at´e mesmo quando alguns exemplos de treinamento tˆem valores desconhecidos (por exemplo, se a Umidade do dia ´e conhecida somente em alguns dos exemplos de treinamento).

Muitos problemas pr´aticos possuem estas caracter´ısticas. Aprendizado utilizando ´arvore de decis˜ao foi aplicado ent˜ao a problemas como classificar os pacientes m´edicos pela doen¸ca, causa de maus funcionamentos de equipamentos, e a probabilidade de candida- tos a empr´estimo ficarem inadimplentes. Tais problemas, nos quais a tarefa ´e classificar exemplos em poss´ıveis categorias discretas, s˜ao frequentemente chamados de problemas de classifica¸c˜ao.

Para a constru¸c˜ao de ´arvores de decis˜ao, deve-se selecionar o atributo que ´e mais eficiente para dividir os exemplos em subconjuntos de exemplos. Esse processo se d´a de forma descendente - come¸cando pelo n´o raiz (i.e., o primeiro n´o de decis˜ao), passando pelos ramos (i.e., os n´os de decis˜ao subordinados) at´e chegar `as folhas (i.e., as classes). A parada ocorre quando a ´arvore classifica todos os exemplos de treinamento ou at´e que todos os atributos sejam usados (MITCHELL, 1997). Duas medidas estat´ısticas s˜ao empregadas para auxiliar na tarefa de descoberta dos atributos mais eficientes - a entropia e o ganho de informa¸c˜ao - discutidas nas pr´oximas subse¸c˜oes.