USO DE ÁRVORES DE DECISÃO NA GERAÇÃO DE HIPÓTESES INDUTIVAS EM APRENDIZADO DE MÁ...
10.11606/D.55.2018.tde-04072018-091501
Martins, Claudia Aparecida (Catálogo USP)
USO DE ÁRVORES DE DECISÃO NA GERAÇÃO DE HIPÓTESES INDUTIVAS EM APRENDIZADO DE MÁQUINA
Aprendizado Indutivo é uma técnica utilizada em Aprendizado de Máquina cujo objetivo é induzir uma descrição geral de conceitos - hipóteses - através de instâncias destes conceitos - exemplos de treinamento. Entre vários paradigmas de aprendizado indutivo, um bastante difundido é o uso de árvores de decisão. Árvores de decisão são utilizadas como linguagem de descrição de conceitos quando os exemplos são descritos como vetores de pares atributo-valor. A indução de uma árvore de decisão é realizada através do conjunto de treinamento que tenta classificar os exemplos na árvore de forma a acomodá-los. Os algoritmos de construção da árvore de decisão podem operar de dois modos: no modo não incremental, no qual o algoritmo infere o conceito de uma vez, baseado no conjunto total de instâncias disponíveis, e no modo incremental, no qual o algoritmo revê a definição do conceito corrente, se necessário. em resposta a cada nova instância de treinamento observada. Uma questão importante a ser observada na indução de árvores de decisão, através de exemplos, é que muitas vezes os atributos iniciais - features primitivas - não são relevantes para descrever os conceitos, mas quando convenientemente combinados, gerando novas, features, podem tornar-se altamente representativos para expressar um conceito. Este processo de construção de features é denominado de Indução Construtiva e seu objetivo é ampliar os limites de uma linguagem baseada em atributos. Este trabalho apresenta dois algoritmos de indução de árvores de decisão , um no modo incremental , e o outro não incremental, para um conjunto de instâncias de treinamento com atributos booleanos. É apresentado, também, um algoritmo de pós-poda para árvore de decisão binária com o objetivo de melhorar a confiabilidade estatística da árvore. Referente à indução construtiva, três algoritmos para a construção automática de features de funções booleanas são apresentados. As implementações realizadas foram integradas a dois ambientes de aprendizado experimental denominados Ambiente Experimental TDIDT para Atributos Booleanos e Ambiente Experimental Construtivo para Atributos Booleanos, respectivamente.
Inductive learning systems aim to induce a general description hyphotesis of concepts from instances examples of these concepts. Among the wide variety of techniques used in inductive learning systems, the decision tree-structured paradigm has been established as the determinant form for rule-based data analysis. Although decision trees are a simple formalism, they are capable of capturing knowledge which is useful to solve new problems. A tree induction program takes a set of examples training set and generates a decision tree classifying them. The examples in the training set are described as vectors of attribute-value. This description is called attribute base. The induction algorithms can operate in a non incremental or incremental mode. In the former case, the algorithm infers a concept once, based on the entire set of available training instances. In the incremental case, the algorithm revises the current concept definition, if necessary, in response to each newly observed training instance. Sometimes the initial attributes referenced as primitive features used to describe the examples are not directly relevant to the concept but, when conveniently combined generating new features, can become highly representative for the expression of the concept. When new features are constructed and then used to form generalized concept descriptions, the feature construction process becomes a form of constructive induction. This works presents two algorithms for induction of decision trees. One incremental, the other non incremental, for set of training instances having boolean-value attributes. An algorithm for prunning the binary decision tree to give statistical reliability is also presented. It also presents tree constructive induction algorithms for automatic feature construction for boolean-value attributes which improve the decision tree induced by the two previous algorithms. The implementations gave rise to two experimental learning environments.