Uso da função sigmóide para pertinência em árvores de decisão difusas CLÁUDIO RATKE1 GILVAN JUSTINO 1 PAULO SÉRGIO DA SILVA BORGES 2 1
UFSC – Universidade Federal de Santa Catarina CEP 88.036-655 Florianópolis (SC) {ratke,gilvan}@senior.com.br
2
UFSC – Universidade Federal de Santa Catarina CTC – Departamento de Ciência da Computação Cx. Postal 99 – CEP 88.036-655 Florianópolis (SC)
[email protected]
Resumo: As árvores de decisão são comumente utilizadas para representar conhecimento. Quinlan desenvolveu algoritmos para indução de árvores de decisão a partir de uma massa de dados, entretanto, estes algoritmos são sensíveis à ruídos em dados contínuos. A intenção desde artigo é utilizar a teoria de conjuntos difusos aplicando a função de pertinência sigmóide para lidar com dados contínuos, a fim de aperfeiçoar a generalização da árvore, obtendo assim melhores resultados na classificação. Palavras Chaves: árvore de decisão, indução de regras, dados contínuos, conjuntos difusos. 1. Introdução Os sistemas transacionais provocaram o armazenamento de uma imensa quantidade de dados. Dentre esta grande quantidade de dados, informações valiosas estão escondidas e são desconhecidas. Esta grande quantidade de dados associada a crescente necessidade de conhecimento voltado para a tomada de decisões tem provocado interesse na extração de conhecimento de bases de dados. A mineração de dados (data mining) surgiu para viabilizar a análise destes dados, tendo obtido sucesso especialmente nas áreas de marketing para obtenção de comportamento, padrões e preferências de clientes a partir de um banco de dados. As estratégias utilizadas em data mining são classificação, agregação, associação, regressão e predição. A classificação consiste em descobrir o relacionamento entre os atributos usando exemplos previamente conhecidos. As árvores de decisão são utilizadas com sucesso para esta função (BARBIERRI, 2001).
As árvores de decisão entretanto possuem limitação ao lidar com atributos contínuos pois são sensíveis a ruídos ou instabilidade nos dados (PENG, 2001). Um das alternativas propostas por Peng, é a utilização de conjuntos difusos para tratamento de dados contínuos. Este artigo estuda a proposta do Peng e utiliza função de pertinência alternativa, baseada na função sigmóide, para elaboração de árvores de decisão difusa. Este artigo está dividido em 4 seções: a seção 2 apresenta a indução de árvores de decisão clássica. A terceira seção aborda a teoria de conjuntos difusos e na seção número 4 é apresentado a aplicação de conjuntos difusos na indução e execução da árvore. Um exemplo é demonstrado na seção 5. Ao término deste artigo é exposto conclusões sobre a proposta e sugestões para novas pesquisas. 2. Árvores de decisão A árvore de decisão é um mecanismo para classificar dados, sendo representado graficamente através dos elementos nó raiz, nós decisão e folha, conforme vê-se na Figura 1. O nó de decisão contém um teste sobre o valor de um atributo. Cada valor de um atributo tem um ramo para uma outra sub-árvore ou folha. Cada sub-árvore contém a mesma estrutura de uma árvore. Uma árvore de decisão representa uma série de questões sobre os atributos de um domínio. A busca tem início na árvore pelo nó raiz, e se desenvolve para baixo até chegar a um nó folha, representando uma classe, ou seja, a variável a ser prevista (Figura 1) . A Figura 1 demonstra uma árvore de decisão que auxilia a tomada de decisão sobre jogar ou não jogar golf conforme condições do tempo.
Figura 1 : Árvore de decisão
Na abordagem clássica de árvores de decisão existe apenas um caminho da raiz até a folha. Uma árvore pode ser reescrita no formato de regras de produção, utilizando o percurso da raiz até a folha (ver Figura 1, em destaque). Exemplo: SE Tempo = “Sol” E Umidade = 18 então pessoa_responsável = Sim”, classificaria um indivíduo como responsável somente a partir do dia em que completasse 18 anos. Conforme pode ser observado, uma pequena variação nos dados pode provocar resultados bastante diferentes. 3. Conjuntos difusos Conforme visto anteriormente, o algoritmo de geração de árvore de decisão utiliza uma abordagem precisa, pois um elemento necessariamente pertence ou não a um conjunto. Além disso, a transição entre um conjunto e outro ocorre de forma rígida. Em 1965, Lofti Zadeh introduziu a teoria de conjuntos difusos que tem como objetivo representar conceitos imprecisos ou subjetivos, normalmente expressos na linguagem natural (OCHARD, 2003). A partir da teoria dos conjuntos difusos (ou fuzzy) um determinado elemento pode pertencer a um ou mais conjuntos. Além disso, é possível eliminar a mudança brusca de um conjunto para o outro, pois a transição pode ocorrer de forma gradual. A Figura 2 demonstra a diferença entre um conjunto tradicional e um conjunto difuso.
Figura 2: Conjunto tradicional X conjunto difuso
3.1. Função de pertinência Um conjunto difuso é caracterizado por uma função de pertinência que representa o grau de possibilidade de que determinado elemento venha a pertencer ao conjunto. Na Figura 2 (conjunto difuso) vê-se que, quanto maior for a idade do indivíduo, menor a possibilidade da pessoa ser irresponsável e maior a possibilidade do indivíduo ser responsável. A possibilidade de o indivíduo pertencer aos conjuntos “irresponsável” ou “responsável” é fornecida por uma função de pertinência. A função de pertinência é uma função matemática que resulta um valor numérico compreendido entre 0 e 1, sendo 1 o maior grau de verdade de um elemento pertencer ao conjunto e 0 o menor grau de verdade. As funções de pertinência mais conhecidas são a triangular, trapezóide, gaussiana e sigmóide. A proposta deste artigo utiliza a função sigmóide (3) conforme visto a seguir: sigmoide ( x ; a , c ) =
1 1 + e −a ( x−c)
(3)
O parâmetro a indica o grau de inclinação da função. Além disso, quando a é positivo, a função é aberta para o lado direito, caso contrário, a função é aberta para o lado esquerdo. A função sigmóide é usada freqüentemente para descrever conceitos como “muito grande”, “muito pequeno”, ou seja, quando os dados estão mais concentrados nos limites de um intervalo. 4. Árvore de decisão difusa A árvore de decisão difusa utiliza a teoria de conjuntos difusos no tratamento de atributos contínuos para indução de árvores de decisão, beneficiando-se desta forma da habilidade de se tratar informações vagas ou imprecisas. A produção de árvores de decisão difusas é simular ao algoritmo de árvores original, entretanto devido à introdução da teoria dos conjuntos difusos, algumas alterações precisam ser realizadas: • Um nó de decisão de um atributo contínuo possui conjuntos difusos associados a cada ramo da árvore, por isso as regras de produção passam a utilizar o operador ∈ , ao invés dos operadores >= ou , julho-2003. PENG, Yonghong. Soft discretization to enhance the continuous decision tree induction. In: EUROPEAN CONFERENCE ON MACHINE LEARNING, Albert Ludwigs University – Alemanha, 2001. QUINLAN, J.R. C4.5 Programs for Machine Learning, Morgan-Kaufmann, 1993. QUINLAN, J. R. Improved Use of Continuous Attributes in C4.5. In: Journal Of Artificial Intelligence Research 4, 1996.
