Descoberta de Conhecimento e Mineração de Dados …valdick.com/files/Apostila de DataMining.pdf · - 1 – ICA – Lab. Inteligência Computacional Aplicada , DEE, PUC–Rio (Versäo

- 1 –ICA – Lab. Inteligência Computacional Aplicada , DEE, PUC–Rio (Versäo 26/08/99)

Descoberta de Conhecimento eMineração de Dados

Apostila

ICA – Laboratório de Inteligência Computacional Aplicada

Departamento de Engenharia Elétrica, PUC–Rio

Marco AurélioMarley Vellasco

Carlos Henrique Lopes


1. Introdução ....................................................................................................................................................... 52. Banco de Dados............................................................................................................................................... 63. Data Warehouse .............................................................................................................................................. 94. KDD – Knowledge Discovery Database....................................................................................................... 12

4.1. TAREFAS DE KDD .................................................................................................................................. 124.1.1. Regras de Associação.......................................................................................................................... 124.1.2. Classificação........................................................................................................................................ 144.1.3. Clustering ............................................................................................................................................ 15

4.2. FASES DE KDD........................................................................................................................................ 164.2.1. Data Warehousing: Organização de grandes volumes de dados......................................................... 16

OLAP: Processamento Analítico On-Line (On-Line Analytical Processing) ........................................... 174.2.2. Pré-processamento dos dados.............................................................................................................. 184.2.3. Limpeza dos dados .............................................................................................................................. 184.2.4. Seleção dos dados................................................................................................................................ 184.2.5. Codificação dos dados......................................................................................................................... 194.2.6. Enriquecimento dos dados................................................................................................................... 194.2.7. Mineração de Dados (Data Mining).................................................................................................... 194.2.8. Pós-processamento .............................................................................................................................. 20

5. Data Mining .................................................................................................................................................. 215.1. INTRODUÇÃO ......................................................................................................................................... 215.2. TÉCNICAS E ALGORITMOS PARA A MINERAÇÃO DE DADOS .................................................... 22

5.2.1. Redes Neurais Artificiais..................................................................................................................... 22Introdução às Redes Neurais Artificiais .................................................................................................... 22Modelagem de Redes Neurais Artificiais em Mineração de Dados .......................................................... 24

5.2.2. Algoritmos Genéticos.......................................................................................................................... 25Introdução a Algoritmos genéticos............................................................................................................ 26Modelagem de Algoritmos Genéticos para a Mineração de Dados........................................................... 27

5.2.3. Lógica Indutiva ................................................................................................................................... 295.2.4. Métodos Estatísticos............................................................................................................................ 30

Classificadores Bayesianos ....................................................................................................................... 30Redes Bayesianas ...................................................................................................................................... 32Árvores de decisão .................................................................................................................................... 33

1.1.1.1.1. Indução de Regras.............................................................................................................. 341.1.1.1.2. Algoritmo ID3.................................................................................................................... 34

6. Redes Neurais................................................................................................................................................ 366.1. Fundamentos das Redes Neurais Artificiais ............................................................................................... 36

6.1.1. Histórico.............................................................................................................................................. 366.1.2. O Neurônio Artificial .......................................................................................................................... 376.1.3. Funções de Ativação ........................................................................................................................... 386.1.4. Topologia das Redes Neurais Artificiais ............................................................................................. 396.1.5. Tipos de Treinamento.......................................................................................................................... 40

6.2. Redes Neurais Artificiais Multi-Camadas.................................................................................................. 416.2.1. - Algoritmo de Retropropagação do Erro............................................................................................ 41

6.3. Modelagem de Redes Neurais para Data Mining ....................................................................................... 436.3.1. Seleção de Dados ................................................................................................................................ 436.3.2. Pré-processamento .............................................................................................................................. 44

Atributos derivados ................................................................................................................................... 44Escalamento .............................................................................................................................................. 44Normalização ............................................................................................................................................ 44Mapeamento simbólico e taxonomias ....................................................................................................... 44Translações de simbólicos para numéricos ............................................................................................... 45

6.3.3. Representação dos dados..................................................................................................................... 45Representação Numérica dos dados .......................................................................................................... 45Valores Discretos ...................................................................................................................................... 45Código 1-de-N........................................................................................................................................... 45Código binário........................................................................................................................................... 45Código de temperatura .............................................................................................................................. 46Valores contínuos...................................................................................................................................... 46Representações de Dados Simbólicos ....................................................................................................... 46Impacto da Representação dos Dados no Tempo de Treinamento ............................................................ 47


6.3.4. Gerenciando Conjunto de Treinamento de Dados............................................................................... 476.3.5. Quantidade de Dados .......................................................................................................................... 476.3.6. Qualidade dos dados (Entra Lixo, Sai Lixo) ....................................................................................... 48

7. Neuro Fuzzy .................................................................................................................................................. 487.1. MOTIVAÇÃO ........................................................................................................................................... 487.2. Sistemas Híbridos....................................................................................................................................... 49

7.2.1. Introdução ........................................................................................................................................... 497.2.2. Sistemas Neuro-fuzzy.......................................................................................................................... 51

Taxonomia dos Sistemas Neurofuzzy ....................................................................................................... 52Taxonomia quanto às características fuzzy ............................................................................................... 53Taxonomia quanto às características de aprendizado................................................................................ 64Exemplos de Modelos Neuro-Fuzzy ........................................................................................................ 66Taxonomia dos três sistemas estudados .................................................................................................... 71

7.2.3. LIMITAÇÕES DOS SNF ................................................................................................................... 728. Algoritmos Genéticos.................................................................................................................................... 73

8.1. RESUMO ................................................................................................................................................... 738.2. ALGORITMOS GENÉTICOS: PRINCÍPIOS E APLICAÇÕES .............................................................. 738.3. Fundamentos matemáticos de Algoritmos genéticos ................................................................................. 77

8.3.1. Análise do Efeito da Seleção............................................................................................................... 778.3.2. Análise do Efeito do Crossover........................................................................................................... 798.3.3. Análise do Efeito da Mutação ............................................................................................................. 79

8.4. Desempenho de Algoritmo GenéticoS ....................................................................................................... 808.5. Técnicas, PARÂMETROS e Operadores Genéticos .................................................................................. 80

8.5.1. Técnicas de Reprodução:..................................................................................................................... 808.5.2. Técnicas de Aptidão: ........................................................................................................................... 818.5.3. Técnicas de Interpolação de Parâmetros: ............................................................................................ 818.5.4. Operadores Genéticos.......................................................................................................................... 82

8.6. Modelagem de Algoritmos genéticos para Data Mining ............................................................................ 828.6.1. CLASSIFICAÇÃO POR EVOLUÇÃO DE REGRAS DE ASSOCIAÇÃO....................................... 82

ACURÁCIA E ABRANGÊNCIA DE UMA REGRA.............................................................................. 83MODELAGEM DO ALGORITMO GENÉTICO .................................................................................... 83

8.6.2. Representação de Cromossomas ......................................................................................................... 838.6.3. Operadores Genéticos.......................................................................................................................... 848.6.4. Inicialização da População .................................................................................................................. 858.6.5. Técnicas e Parâmetros ......................................................................................................................... 878.6.6. Funções de Avaliação.......................................................................................................................... 88

Número-Atributos ..................................................................................................................................... 89Distância-Ótima ........................................................................................................................................ 89Recompensa-Atributos .............................................................................................................................. 90CBayesianos .............................................................................................................................................. 90Número-Registros ..................................................................................................................................... 90FAcurácia .................................................................................................................................................. 90FAbrangência ............................................................................................................................................ 90Rule Interest .............................................................................................................................................. 91Chi-Square................................................................................................................................................. 91

8.6.7. Recompesa nas funções de avaliação .................................................................................................. 919. Apêndice ....................................................................................................................................................... 93

9.1. Softwares comerciais e Sites ...................................................................................................................... 939.1.1. AC2 (www.isoft.fr) ............................................................................................................................. 939.1.2. ALICE d’ISoft (www.isoft.fr) ............................................................................................................. 939.1.3. AutoClass C (ic-www.arc.nasa.gov/ic/projects/bayes-group/group/autoclass/autoclass-c-program.html)................................................................................................................................................ 939.1.4. Clementine (www.isl.co.uk/clem.html)............................................................................................... 939.1.5. Data Surveyor (www.ddi.nl) ............................................................................................................... 939.1.6. Data Engine (www.mitgmbh.de)......................................................................................................... 939.1.7. Datasage (www.datasage.com) ........................................................................................................... 949.1.8. DataScope (http://www.tiszanet.hu/cygron/datascp.htm) ................................................................... 949.1.9. Outros softwares e sites ....................................................................................................................... 94

C5.0 / See5 - www.rulequest.com............................................................................................................. 94Commercial tools for data mining - www.cs.bham.ac.uk/~anp/dm_docs/oudshoff.tools.posting ............ 94


DataDetective – www.smr.nl .................................................................................................................... 94dbProphet: neural network data mining tool by Trajecta – www.trajecta.com ......................................... 94Explora - http://orgwis.gmd.de/projects/explora/ ...................................................................................... 94IBM Visualization Data Explorer – www.almaden.ibm.com/dx/ ............................................................. 94LEVEL5 Quest – www.l5r.com ................................................................................................................ 94ModelQuest Enterprise – www.abtech.com.............................................................................................. 94ModelQuest Enterprise – www.data-mine.com......................................................................................... 94PV-WAVE – www.vni.com...................................................................................................................... 94SE-Learn - http://www.isp.pitt.edu/~rymon/SE-Learn.html ..................................................................... 94SPSS Data Mining Software – www.spss.com/datamine/......................................................................... 94SuperQuery – www.azmy.com.................................................................................................................. 94WizRule for Windows – www.wizsoft.com.............................................................................................. 94XpertRule – www.attar.com...................................................................................................................... 94

9.2. Empresas de Data Mining no Brasil ........................................................................................................... 949.2.1. http://www.execplan.com.br/ .............................................................................................................. 959.2.2. http://vidaconsultores.com.br/infovida/............................................................................................... 959.2.3. http://www.rio.com.br/~extend/ .......................................................................................................... 959.2.4. http://www.geocities.com/WallStreet/District/2108/ricvill.htm.......................................................... 95

9.3. Empresas e produtos em Data Mining........................................................................................................ 959.3.1. American Heuristics/Profiler – www.heuristics.com .......................................................................... 959.3.2. Angoss Software/Knowledge Seeker – www.angoss.com .................................................................. 959.3.3. Business Objects/BusinessMiner – www.businessobjects.com .......................................................... 959.3.4. DataMind/DataMindProfessional – www.datamind.com.................................................................... 959.3.5. HNC Software/DataMarksman – www.hncs.com............................................................................... 959.3.6. HiperParallel/Discovery – www.hiperparallel.com............................................................................. 959.3.7. Information Discovery Inc.(IDI)/Information Discovery System – www.datamining.com................ 959.3.8. Lucent Technologies/Interactive Data Visualization – www.lucent.com............................................ 959.3.9. Nestor/Prism – www.nestor.com......................................................................................................... 959.3.10. Pilot Software/pilot Discovery Server – www.pilotsw.com.............................................................. 959.3.11. Seagate Software Systems/Holos 5.0 – www.holossys.com ............................................................. 959.3.12. Thinking Machines/Darwin – www.think.com ................................................................................. 96

Referências............................................................................................................................................................ 96


1. INTRODUÇÃO

Durante os últimos anos tem se verificado um crescimento substancial da quantidade de dadosarmazenados em meios magnéticos. Estes dados, produzidos e armazenados em larga escala, são inviáveis deserem lidos ou analisados por especialistas através de métodos manuais tradicionais [PIAT91], tais comoplanilhas de cálculos e relatórios informativos operacionais, onde o especialista testa sua hipótese contra a basede dados. Por outro lado, sabe-se que grandes quantidades de dados equivalem a um maior potencial deinformação. Entretanto, as informações contidas nos dados não estão caracterizadas explicitamente, uma vez quesendo dados operacionais, não interessam quando estudados individualmente. Diante deste cenário, surge anecessidade de se explorar estes dados para extrair informação - conhecimento implícito, e utilizá-la no âmbitodo problema. Argumenta-se que a necessidade de sistemas para dar suporte a decisão têm se desenvolvido aolongo dos anos cada vez mais dentro de uma granularidade de informações mais refinada, da seguinte maneira:nos anos 60 as exigências e necessidades estavam a nível de mercado; nos anos 70, ao nível de nichos, grupos deinteresse; nos anos 80, a nível de seguimentos de mercado; e nos anos 90, a nível de clientes. Este último nível,naturalmente, requer o uso de mais dados para se extrair conhecimento [KELL95]. A exploração do valor destesdados, ou seja, a informação neles contida implicitamente, depende de técnicas como Regras de Associação[SRIK95], Classificação [MICH94], Clustering [FISH87], entre outras, capazes de gerenciar tarefas complexas.

O processo capaz de descobrir este conhecimento em banco de dados chama-se KDD (KnowledgeDiscovery Database). O processo de KDD foi proposto em 1989 para referir-se às etapas que produzemconhecimentos a partir dos dados e, principalmente, à etapa de mineração dos dados, que é a fase que transformadados em informações [FAYY96]. Este processo envolve encontrar e interpretar padrões nos dados, de modoiterativo e interativo, através da repetição dos algoritmos e da análise de seus resultados. Esse processo contémdiversas fases: definição do problema; seleção dos dados; limpeza dos dados; pré-processamento dos dados;codificação dos dados; enriquecimento dos dados; mineração dos dados (Data Mining) e a interpretação dosresultados.

O processo de KDD é formado pela interseção de diferentes áreas. As áreas mais relacionadas emdescoberta de conhecimento são: Machine Learning [LANG96], [SHAV90], Inteligência Computacional,estatística [ELDE96] e visualização dos dados [LEE 95]. Na área de Inteligência Computacional, em particular,as técnicas mais utilizadas são: Redes Neurais Artificiais [HAYK94], [RUME86], Indução de regras [NILS80] eAlgoritmos Genéticos [GOLD89].

A Inteligência Computacional é uma área da ciência que busca, através de técnicas inspiradas naNatureza, o desenvolvimento de sistemas inteligentes que imitam aspectos do comportamento humano, taiscomo: aprendizado, percepção, raciocínio, evolução e adaptação.

Técnica InspiraçãoRedes Neurais Neurônios biológicosAlgoritmos Genéticos Evolução biológicaLógica Fuzzy Proc. lingüísticoSistemas Especialistas Inferência

Redes Neurais são modelos computacionais não lineares, inspirados na estrutura e operação do cérebrohumano, que procuram reproduzir características humanas, tais como: aprendizado, associação, generalização eabstração. Redes Neurais são efetivas no aprendizado de padrões a partir de dados não lineares, incompletos,com ruído ou compostos de exemplos contraditórios.

Algoritmos Genéticos são algoritmos matemáticos inspirados nos mecanismos de evolução natural erecombinação genética. A técnica de Algoritmos Genéticos fornece um mecanismo de busca adaptativa que sebaseia no princípio Darwiniano de reprodução e sobrevivência dos mais aptos.

Lógica Nebulosa (Fuzzy Logic) tem por objetivo modelar o modo aproximado de raciocínio humano,visando desenvolver sistemas computacionais capazes de tomar decisões racionais em um ambiente de incertezae imprecisão. A Lógica Nebulosa oferece um mecanismo para manipular informações imprecisas, tais como osconceitos de muito, pouco, pequeno, alto, bom, quente, frio, etc, fornecendo uma resposta aproximada para umaquestão baseada em um conhecimento que é inexato, incompleto ou não totalmente confiável.

Sistemas Especialistas são programas computacionais destinados a solucionar problemas em um campoespecializado do conhecimento humano. Usa técnicas de IA, base de conhecimento e raciocínio inferencial.

As técnicas da Inteligência Computacional têm sido empregadas com sucesso no desenvolvimento desistemas inteligentes de previsão, suporte à decisão, controle, otimização, modelagem, classificação ereconhecimento de padrões em geral, aplicados em diversos setores: Energia, Industrial, Econômico, Financeiro,Comercial e Outros, Síntese de Circuitos, Meio Ambiente, entre outros [MARCO].


2. BANCO DE DADOS

Este capítulo introduz banco de dados de uma forma simples. São abordados os pontos que julga-se sero mínimo necessário para deixar o leitor capacitado a entender a necessidade de banco de dados direcionadospara Data Mining. Os tópicos abordados estão mais detalhados na referência citada para banco de dados.

De maneira genérica são abordados em banco de dados: conceitos básicos, tais como definição epropriedades; características, como linguagens de BD e coerência dos dados; arquitetura lógica, esquemasexterno, conceitual e interno; usuários; modelo de Entidade-Relacionamento; linguagens de consulta; linguagemSQL, apresentando os principais comandos; cuidados no projeto do BD e algumas restrições de integridade.

Pode-se definir banco de dados como uma coleção de dados relacionados. Onde dados significam fatosconhecidos que podem ser armazenados e que possuem significado implícito. Por exemplo, considere os nomes,número de telefones, e endereços das pessoas que você conhece. Você pode ter armazenado esse dado numaagenda de endereço indexada, ou você pode ter armazenado ele diretamente em um disquete, utilizando um PC eum software como DBASE IV ou V, PARADOX, ou EXCEL. Isto é uma coleção de dados relacionados com umsignificado implícito, então é um banco de dados.

De maneira genérica um banco de dados possui as seguintes propriedades implícitas:• Um banco de dados representa algum aspecto do mundo real, algumas vezes chamado de mini-mundo

ou Universo do Discurso. Mudanças no mini-mundo são refletidas no banco de dados.• Um banco de dados é uma coleção logicamente coerente de dados como algum significado herdado.

Uma ordenação aleatória de dados não pode ser corretamente referenciada como um banco de dados.• Um banco de dados é modelado, construído, e povoado com dados para uma proposta específica. Ou

seja existe um grupo de usuários e algumas aplicações pré concebidas as quais esses usuários estãointeressados.

Em outras palavras, os bancos de dados tem alguma origem da qual os dados são derivados, algum graude interação com eventos no mundo real, e alguns usuários que estão ativamente interessados no conteúdo dobanco de dados.

Um banco de dados pode ser gerado e mantido manualmente ou por uma máquina. Um banco de dadoscomputadorizado pode ser criado e mantido ou por um grupo de programas de aplicação escritos especialmentepara essa tarefa ou por um sistema gerenciador de banco de dados.

Um sistema gerenciador de banco de dados (SGBD), ou em inglês, DBMS (Database ManagementSystem), é uma coleção de programas habilita usuários a criar e manter um banco de dados. O SGBD é então umsoftware de propósito geral que facilita o processo de definir, construir e manipular banco de dados de váriasaplicações. Onde definir o banco de dados envolve especificar os tipos dos dados, estruturas e restrições para osdados que serão armazenados no banco de dados. Construir o banco de dados é o processo de armazenamento dodado em alguma mídia que é controlada pelo SGBD. E a manipulação do banco de dados inclui algumas funçõescomo queries que buscam por dados específicos, atualizações no banco de dados que refletem mudanças nomini-mundo, e geração de relatórios dos dados.

Programas de Aplicação/ Q u erie s

Softw a re para pro c essarQ u erie s /Program as

Softw a re para acessarD a dos Armazenados

S G B DSOF T W A R E

SISTEM ABD

BDA r maze nado

Meta-DadosDefi nição

U suários/Program adores

Figura 1: Um ambiente simplificado de um sistema de banco de dados


É necessário uma grande quantidade de softwares para manipular o banco de dados além do própriobanco de dados, nesse caso, chama-se sistema de banco de dados o conjunto BD e softwares. A Figura 1 ilustraessas idéias.

Um número de características distinguem a aproximação de banco de dados com a aproximaçãotradicional de programação com arquivos. No tradicional processamento de arquivos, cada usuário define eimplementa os arquivos necessários para uma aplicação específica. Na aproximação por banco de dados, umúnico repositório de dados é mantido e definido uma única vez e então é acessada por vários usuários.

Deste modo as principais características podem ser a definição do banco de dados através da linguagemde definição de dados (LDD) criando e relacionamentos, tipos e restrições nos dados; a utilização de linguagensde manipulação de dados (LMD) fazendo atualizações na base; o suporte ao método de armazenamento,segurança, e acesso eficiente aos dados, além do controle multi-usuário concorrentemente. Entretanto acaracterística fundamental é a que provê um nível de abstração capaz de esconder os detalhes de como os dadosestão armazenados, que para a maioria dos usuários não é de interesse.

Analisando-se as principais características de banco de dados pode-se especificar uma arquitetura parasistemas de banco de dados, chamada de arquitetura em 3 níveis ou esquemas (Figura 2).

EE1 EE2 EEN

Esquema Conceitual

Esquema Interno

NÍVEIS DE ABSTRAÇÃO

Esquema Externo

Figura 2: Arquitetura em 3 níveis

O objetivo dessa arquitetura ilustrada na Figura 2 é separar as aplicações dos usuários e o banco de dadosfisicamente. Nessa arquitetura os esquemas podem ser definidos nos seguintes níveis:

1. O nível interno tem um esquema interno, que descreve a estrutura física de armazenamento do bancode dados. O esquema interno usa o modelo de dados físico e descreve detalhes completos doarmazenamento dos dados e caminhos de acesso para o banco de dados.

2. O nível conceitual tem um esquema conceitual, que descreve a estrutura de todo o banco de dadospara uma comunidade de usuários. O esquema conceitual escondes os detalhes da estrutura dearmazenamento físico e concentra-se na descrição de entidades, tipos de dados, relacionamentos,operações de usuários, e restrições.

3. O esquema externo ou nível de visão inclui um número de esquemas esternos ou visões de usuários.Cada esquema externo descreve a parte do banco de dados que um grupo particular de usuários estáinteressada e esconde o resto do banco de dados para esse mesmo grupo.

Essa arquitetura pode ser utilizada para explicar o conceito de independência dos dados., que pode serdefinido como a capacidade de alterar o esquema em algum nível de um banco de dados sem ter que alterar oesquemas do nível mais alto. Pode-se definir dois tipos de independência, a física e a lógica.

A independência lógica é a capacidade de alterar o esquema conceitual sem ter que alterar o conceitoexterno ou os programas de aplicação. A independência física é a capacidade de mudar o esquema interno semter que mudar o esquema conceitual.

Uma vez que o modelo do banco de dados está definido e um SGBD foi escolhido para implementar obanco de dados, então precisa-se especificar os esquemas conceitual e interno para o banco de dados e qualquermapeamento entre os dois. Uma linguagem chamada Linguagem de Definição de Dados (LDD) é utilizada porum usuário administrador da base e pelos desenvolvedores do modelo para definir ambos os esquemas. EmSGBDs onde existe uma clara diferença entre os níveis conceitual e interno, a LDD é utilizada apenas para omodelo conceitual. Uma outra linguagem (SDL – Storage Definition Data) é usada para especificar o modelointerno. Para completar a arquitetura de 3 níveis é necessário uma terceira linguagem, a VDL (View DefinitionLanguage) que define o esquema de visões. Uma vez que os esquemas do banco de dados são criados e o bancode dados é povoado, os usuários precisam ter meios de manipular os dados. As manipulações típicas incluem


busca, inserção, deleção, e modificação dos dados. Para essa proposta o SGBD propõe a LMD, linguagem demanipulação de dados.

O modelo conceitual de entidade-relacionamento descreve dados como entidades, relacionamentos eatributos. A entidade é o objeto básico representado no modelo ER, que é uma “coisa” do mundo real comexistência independente. Uma entidade pode ser um objeto com existência física – uma pessoa, carro, casa, ouempregado – ou pode ser um objeto com existência conceitual – uma companhia, um trabalho, ou um curso deuniversidade. Cada entidade tem propriedades particulares, chamadas atributos, que a descrevem. Por exemplo,uma entidade empregado pode ser descrita por nome do empregado, idade, endereço, salário e trabalho. Umaentidade particular terá um valor para cada um desses atributos. Os valores dos atributos que descrevem cadaentidade são a maior parte dos dados armazenados no banco de dados.

Informalmente, um relacionamento é uma associação de entidades, onde a associação inclui exatamenteuma entidade de cada participante no tipo da entidade. Por exemplo, suponha o relacionamentoTRABALHA_PARA entre duas entidades EMPREGADO e DEPARTAMENTO, que associa cada empregadoao departamento em que trabalha.

Dado que o banco de dados está concluído, existem as pessoas cujo trabalho necessita acessar o banco dedados para busca de informações, atualizações e gerações de relatórios; o banco de dados inicialmente existepara o uso dessa pessoas. Existem várias categorias para usuários finais:

• Usuário casual – ocasionalmente acessam o banco de dados, mas eles tem necessidades deinformações diferentes a cada acesso. Eles usam uma linguagem sofisticada de busca em banco dedados para especificar seus requisitos e são tipicamente gerentes de nível médio ou alto.

• Naive ou usuários paramétricos – São usuários de grande parte do banco de dados. A funçãoprincipal do seu trabalho faz com que constantemente ele busque e atualize o banco de dados atravésde transações enlatadas que foram cuidadosamente programadas e testadas. Por exemplo, caixas debanco, reservas aéreas, de hotéis, de aluguéis de carros, etc...

• Usuários sofisticados – incluem engenheiros, cientistas, analistas de negócios, e outros que sãofamiliarizados com as facilidades do SGBD e buscam encontrar suas necessidades mais complexas.

• Usuários isolados – mantém um banco de dados pessoal utilizando programas empacotados queprovê facilidade de uso em menus e interfaces gráficas.

Existem várias linguagens que tem sido parcialmente ou completamente implementada e estãodisponíveis em SGBDs comerciais. A mais conhecida delas é a SQL, cujo nome é derivado de Structure QueryLanguage. Variações de SQL tem sido implementadas por vários fabricantes, por isso há um esforço de sepadronizar o SQL coordenado pelo ANSI (American National Standards Institute) e pela ISO (InternationalStandards Organizations).

SQL é uma linguagem compreensiva para banco de dados; ela possui comandos para definição de dados,busca e atualizações. Então, ela é uma LMD e LDD. SQL utiliza os termos tabela, linha, e coluna para relação,tupla e atributo, respectivamente. Os comando de SQL para definição de dados são CREATE, ALTER, e DROP.

O comando CREATE TABLE é usado para especificar uma nova relação dando-se seu nome eespecificando seus atributos e restrições. Os atributos são especificados primeiro, e a cada atributo é dado umnome, um tipo de dados para especificar seu domínio de valores, e possivelmente algumas restrições. A chave, asrestrições de integridade da entidade e referencial são especificadas.

Exemplo:CREATE TABLE EMPLOYEE

(NAME VARCHAR(15) NOT NULL, MINIT CHAR, LNAME VARCHAR(15) NOT NULL, SSN CHAR(9) NOT NULL, BDATEDATE, ADDRESS VARCHAR(30), SEX CHAR, SALARY DECIMAL(10, 2), SUPERSSN CHAR(9), DNO INT NOT NULL,

PRIMARY KEY (SSN),FOREIGN KEY (SUPERSSN) REFERENCES EMPLOYEE (SSN),FOREIGN KEY (DNO) REFERENCES DEPARTAMENT (DNUMBER));

O comando ALTER TABLE pode ser utilizado para alterar a definição de um tabela. As possíveis açõesdesse comando incluem adicionar ou excluir uma coluna (atributo), alterar a definição de uma coluna, e


adicionar ou excluir restrições. Por exemplo, adicionar um atributo para monitorar o trabalho de um empregado.ALTER TABLE EMPLOYEE ADD JOB VARCHAR (12);

SQL tem um comando básico para obter informações da base de dados: SELECT. A forma básica docomando SELECT é formada por 3 cláusulas SELECT, FROM, e WHERE e tem a seguinte forma:

SELECT <lista de atributos>FROM <lista de tabelas>WHERE <condição>,Onde• <lista de atributos> é uma lista de nomes de atributos cujos valores serão obtidos na query.• <lista de tabelas> é uma lista com os nomes das relações requisitadas para processar a query.• <condição> é a condição necessária para identificar expressões que satisfazem as tuplas da query.Exemplo:SELECT BDATE, ADDRESSFROM EMPLOYEEWHERE FNAME = ´JOHN´ AND LNAME = ´SMITH´

3. DATA WAREHOUSE

Os bancos de dados e a teoria de banco de dados estão disponíveis há bastante tempo. As primeirasedições de bancos de dados concentravam-se em um único banco de dados que atendia a todos os propósitosconhecidos pela comunidade de informática – do processamento de transações ao processamento batch (lote) eao processamento analítico. Na maioria dos casos, o enfoque principal dos primeiros sistemas de banco de dadosera o processamento operacional – geralmente transacional. Nos últimos anos, surgiu um conceito de banco dedados mais sofisticados – um que atende as necessidades operacionais e outro que atende as necessidadesinformacionais ou analíticas. Até certo ponto, esse conceito mais evoluído de banco de dados se deve ao adventodos PCs, à tecnologia das linguagens de quarta geração, e ao empowerment do usuário final.

A divisão em banco de dados operacionais e informacionais ocorre por várias razões:• Os dados que atendem a necessidades operacionais são fisicamente diferentes dos dados que atendem a

necessidades informacionais ou analíticas.• A tecnologia de suporte ao processamento operacional é fundamentalmente, diferente da tecnologia

utilizada para prestar suporte a necessidades informacionais ou analíticas.• A comunidade de usuários dos dados operacionais é diferente da que é atendida pelos dados

informacionais ou analíticos.• As características de processamento do ambiente operacional e do ambiente informacional são,

fundamentalmente diferentes.Por essas razões (e por muitas outras!), a maneira moderna de construir sistemas consiste em separar o

processamento e os dados operacionais dos informacionais ou analíticos.Pode-se definir que o processamento informacional ou analítico é o processamento que atende às

necessidades dos gerentes durante o processo de tomada de decisões. Geralmente conhecido como SAD –sistemas de apoio à decisão, o processamento analítico examina amplos espectros de dados para detectartendências. Em vez de considerar um ou dois registros de dados (como ocorre no processamento operacional),quando o analista de SAD executa um processamento analítico, muitos registros são acessados. Além disso, oanalista de SAD muito raramente atualiza dados. Nos dados operacionais, os dados estão constantemente sendoatualizados no nível de registro individual. No processamento analítico, os registros estão constantemente sendoacessados, e seus conteúdos são agrupados para análise, mas ocorre pouca ou nenhuma alteração dos registrosindividuais.

No processamento analítico, os requisitos de tempo de resposta são muito atenuados em comparação como do tradicional processamento operacional. O tempo de resposta analítico alcança de 30 minutos a 24 horas.Para o processamento operacional, tempos de resposta inseridos nessa escala significariam um absoluto desastre.

A rede que atende a comunidade analítica é muito menor do que a que atende à comunidade operacional.Normalmente, há muito menos usuários da rede analítica do que da rede operacional.

Ao contrário da tecnologia que dá suporte ao ambiente analítico, a tecnologia voltada para o ambienteoperacional deve tratar do bloqueio de dados e transações, disputa de dados, deadlock, e assim por diante.


Há portanto, muitas diferenças importantes entre o ambiente operacional e o ambiente analítico. Aqui édado enfoque ao processamento analítico com as seguintes questões:

• Granularidade dos dados• Particionamento dos dados• Metadados• Falta de credibilidade dos dados• Integração dos dados do SAD• Parâmetros de tempo dos dados do SAD• Identificação da fonte dos dados do SAD – o sistema de registro• Migração e tecnologia

O Data Warehouse é o alicerce do processamento dos SADs. Em virtude de haver uma fonte única dedados integrados no DW, e uma vez que os dados apresentam condições de acesso, a tarefa do analista de SADno ambiente de DW é incomensuravelmente mais fácil do que no ambiente clássico.

Um DW é um conjunto de dados baseado em assuntos, integrado, não-volátil, e variável em relação aotempo, de apoio às decisões gerenciais. Os sistemas operacionais clássicos são organizados em torno dasaplicações da empresa. No caso de uma companhia de seguros, as aplicações podem ser automóvel, saúde, vida eperdas. Os principais assuntos ou negócios da empresa podem ser cliente, apólice, prêmio e indenização.

A segunda característica marcante do DW é que ele é integrado. A integração ocorre quando os dadospassam do ambiente operacional baseado em aplicações para o data warehouse.

O processo de introdução dos dados no DW é feita de modo que as muitas inconsistências da aplicaçõessejam desfeitas. As considerações sobre inconsistências são válidas para todas as questões de projeto deaplicações, como as convenções de atribuição de nomes, estruturas de chaves, unidades de medidas de atributose características físicas dos dados.

A terceira característica importante de um DW consiste em que ele é não-volátil. No ambienteoperacional, os dados sofrem atualizações. Contudo, os dados existentes no data warehouse apresentam umconjunto de características muito diferentes. Os dados do DW são carregados (normalmente em grandesquantidades) e acessados. Mas a atualização dos dados (geralmente) não ocorre no ambiente de data warehouse.

A última característica significativa do DW diz respeito ao fato de ele ser variável em relação ao tempo.• O horizonte de tempo válido para o DW é significantemente maior do que o dos sistemas

operacionais. Um horizonte de tempo de 60 a 90 dias é normal para os sistemas operacionais; umhorizonte de tempo de 5 a 10 anos é normal para o DW.

• Bancos de dados operacionais contêm dados de valor corrente – dados cuja exatidão é válida para omomento de acesso. Assim sendo, dados de valor corrente podem ser atualizados. Dados existentesno DW não passam de uma série sofisticada de instantâneos, capturados num determinado momento.

• A estrutura de chaves dos dados operacionais pode conter, ou não, elementos de tempo, como ano,mês, dia, etc. A estrutura de chave do DW sempre contém algum elemento de tempo.

Na estrutura do DW pode-se notar um nível de detalhe mais antigo (geralmente residente em umarmazenamento alternativo, de massa), um nível corrente de detalhe, um nível de dados levemente resumidos eum nível de dados altamente resumidos. Os dados fluem do ambiente operacional para o DW. Na passagem donível operacional pare o nível do DW, geralmente ocorre uma quantidade significativa de transformações dedados.

O DW baseia-se nos principais assuntos ou negócios de interesse da empresa que tenham sido definidosno modelo de dados. Entre as tradicionais áreas de interesse incluem-se: Cliente, produto, transação ou atividade,apólice, indenização, conta, etc. A principal área de interesse termina sendo fisicamente implementada comouma série de tabelas relacionadas inseridas no DW.

Dados que apresentam alta probabilidade de acesso e baixo volume de armazenamento residem em ummeio rápido e relativamente caro. Dados que apresentam baixa probabilidade de acesso e grande volume dearmazenamento residem em um meio menos dispendioso e de acesso mais lento.

O mais importante aspecto do projeto de um DW é a questão da granularidade. A granularidade dizrespeito ao nível de detalhe ou de resumo contido nas unidades de dados existentes no DW. Quanto mais detalhe,mais baixo o nível de granularidade. Quanto melhor detalhe, mais alto o nível de granularidade.

A granularidade de dados tem se mantido como uma questão delicada de projeto. Nos primeiros sistemasoperacionais que foram criados, a granularidade era tido como certa. Quando os dados detalhados eramatualizados, era quase certo que eles seriam armazenados no nível mais baixo de granularidade. No entanto, noambiente de DW, a granularidade não é um pressuposto.


A razão pela qual a granularidade é a principal questão de projeto consiste no fato de que ela afetaprofundamente o volume de dados que residem no DW e, ao mesmo tempo, afeta o tipo de consulta que pode seratendida. O volume de dados contido no DW é balanceado de acordo com o nível de detalhe de uma consulta.

Outro meio utilizado é o particionamento dos dados de detalhe corrente em unidades físicas menores.Pois, unidades físicas menores proporcionam ao pessoal de operação e ao projetista muito mais flexibilidade nogerenciamento dos dados do que é proporcionado pelas unidades maiores.

Quando os dados residem em unidades físicas de tamanho maior, entre outras coisas, eles não podem ser:• Reestruturados facilmente• Indexados livremente• Pesquisados sequencialmente, se necessário• Reorganizados facilmente• Recuperados facilmente• Monitorados facilmenteEm resumo, uma das características essenciais do data warehouse é o acesso flexível aos dados. A

existência de uma grande quantidade de dados frusta boa parte do objetivo do DW. Portanto, todos os dados dedetalhe corrente do DW devem ser particionados. Os dados podem ser divididos de diversas maneiras, as maiscomuns são: por data, por área de negócio, por área geográfica, por unidade organizacional, etc.

Existem dois importantes aspectos vinculados à construção de um DW – o projeto da interface com ossistemas operacionais e o projeto do data warehouse propriamente dito. De certa forma, “projeto” não é umadescrição exata do que acontece durante a construção do DW, uma vez que ele é construído de modo heurístico.Primeiro, o warehouse é povoado com alguns dados. Tais dados são, então, usados e minuciosamenteexaminados pelo analista de SAD. Em seguida, com base no feedback proporcionado pelo usuário final, os dadossão modificados e/ou outros são adicionados ao data warehouse.

O ciclo de feedback tem continuidade por toda a vida do data warehouse. É um engano pensar que osenfoques de projetos que funcionaram no passado serão úteis na construção do DW. Os requisitos para a criaçãodo DW não podem ser conhecidos até que ele esteja parcialmente povoado e sendo usado pelo analista de SAD.Portanto, ele não pode ser projetado do mesmo modo pelo qual são construídos os sistemas clássicos baseadosem requisitos. Por outro lado, também constitui um engano pensar que não prever requisitos seja uma boa idéia.

Antes de qualquer tentativa de aplicar as técnicas convencionais de projeto seja feita, o projetista precisacompreender a aplicabilidade e o os limites dessas técnicas. O modelo de processos se aplica apenas ao ambienteoperacional. O modelo de dados se aplica tanto ao ambiente operacional quanto ao ambiente de data warehouse.A tentativa de utilização de um modelo de dados ou de processos no local inadequado resultará apenas emfrustração.

O escopo de integração estabelece as fronteiras do modelo de dados e deve ser definido antes do inicio doprocesso de modelagem. O escopo é combinado entre o encarregado da modelagem, a gerência e o usuário finaldo sistema. Caso o escopo não seja predeterminado, há uma grande possibilidade de o processo de modelagemprolongar-se por um tempo excessivo. O modelo físico de dados é criado a partir do modelo de nívelintermediário mediante a simples expansão deste de forma que ele passe a apresentar chaves e característicasfísicas. À essa altura, o modelo físico de dados se parece com uma série de tabelas chamadas, em alguns casos,de tabelas relacionais.

Um importante aspecto do ambiente de DW diz respeito aos metadados. Metadados são dados sobredados. Os metadados fazem parte do meio de processamento de informações há tanto tempo quanto osprogramas e os dados. Contudo, é no mundo do data warehouse que os metadados assumem um novo nível deimportância. É por meio dos metadados que a utilização mais produtiva do data warehouse é alcançada. Osmetadados permitem que o usuário final/analista de SAD navegue pelas possibilidades.

Os metadados englobam o warehouse e mantêm informações sobre o que está onde no data warehouse.Tipicamente, os aspectos sobre os quais os metadados mantêm informações são:

• A estrutura dos dados segundo a visão do programador.• A estrutura dos dados segundo a visão do analista de SAD.• A fonte de dados que alimenta o data warehouse.• A transformação sofrida pelos dados no momento de sua migração para o DW.• O modelo de dados.• O relacionamento entre o modelo de dados e o DW.• O histórico de extrações.

De modo geral pode-se resumir que o projeto do data warehouse começa com o modelo de dados. Omodelo corporativo de dados é utilizado para o projeto do ambiente operacional, e uma variante do modelocorporativo de dados é usada para o DW. O data warehouse é construído de forma iterativa. Os requisitos para oDW não podem ser conhecidos antecipadamente. A construção do data warehouse ocorre sob um ciclo de vidado desenvolvimento completamente diferente daquele referente aos sistemas operacionais clássicos.


A principal preocupação do desenvolvedor do data warehouse diz respeito ao gerenciamento de volume.Com relação a isso, a granularidade e o particionamento dos dados são duas questões mais importantes doprojeto de banco de dados. Há, no entanto, muitas outras questões de projeto físico, a maioria das quais,centradas na eficiência de acesso aos dados.

4. KDD – KNOWLEDGE DISCOVERY DATABASE

4.1. TAREFAS DE KDD

A Figura 3 representa de forma hierárquica uma visão sistemática do processo de KDD. Nessa figurapercebe-se as fases e as principais tarefas do processo de KDD, envolvendo: tarefas e algoritmos empregados;fases; e etapas do pré processamento.

Figura 3:Taxonomia do processo de KDD

O desenvolvimento de sistemas de KDD esta relacionado com diversos domínios de aplicações:marketing, análises corporativas, astronomia, medicina, biologia, entre outros. Deste modo, pode-se identificardiversas tarefas de KDD que são, principalmente, dependentes do domínio da aplicação e do interesse dousuário. De modo geral, cada tarefa de KDD extrai um tipo diferente de conhecimento do banco de dados, logocada tarefa requer um algoritmo diferente para a extração de conhecimento. A seguir descreve-se algumas dasprincipais tarefas de KDD.

4.1.1. Regras de Associação

A tarefa de descobrir regras de associação foi introduzida por Agrawal [AGRA93]. Na sua formaoriginal essa tarefa é definida para um tipo especial de dados, frequentemente chamado “basket data”. Nesse tipode dado uma tupla consiste num conjunto de atributos binários chamados itens. Cada tupla corresponde à umatransação, e um item pode assumir um valor verdadeiro ou falso, dependendo se o ele está ou não presente na


transação. A transformação de uma tabela da base de dados para o formato binário é feita de modo que umatributo de cardinalidade K é substituído por K atributos binários [ADRI97].

Uma regra de associação é um relacionamento da forma X ⇒ Y, onde X e Y são conjuntos de itens e ainterseção deles, X ∩ Y, é o conjunto vazio. Cada regra de associação é associada a um fator suporte superior,denominado FSup, e a um fator de confidência, FConf. FSup é definido como a razão do número de tuplassatisfazendo ambos X e Y sobre o número total de tuplas, isto é, FSup = | X ∪ Y | / N, onde N é o número totalde tuplas. FConf é definido como a razão do número de tuplas que satisfazem ambos X e Y sobre o número detuplas que satisfazem X, isto é, FConf = | X ∪ Y | / | X |. A tarefa de descobrir regras de associação consiste emextrair do banco de dados todas as regras com FSup e FConf maiores ou iguais a um FSup e FConf especificadopelo usuário. A definição desses fatores serve para introduzir uma medida capaz de distinguir associaçõesinteressantes, dado que as regras geradas em forma binária elevam em muito o espaço de busca de qualqueralgoritmo minerador.

A descoberta de regras de associação é geralmente executada em 2 passos. Primeiro, um algoritmodetermina todos os conjuntos de itens que têm FSup maior ou igual ao FSup especificado pelo usuário. Estesconjuntos são chamados conjuntos de itens frequentes. Segundo, para cada conjunto de itens frequentes, todas aspossíveis regras candidatas são geradas e testadas com respeito ao FConf. Uma regra candidata é gerada poralgum subconjunto de itens de um conjunto de itens frequentes como antecedente da regra, e os itensremanescentes do conjunto de itens frequentes como o consequente da regra. Apenas regras candidatas comFConf maior ou igual ao FConf especificado pelo usuário são dadas como saída do algoritmo.

Para ilustrar a descoberta de regras de associação, considere o exemplo mostrado na Tabela 1 [FREI98].A primeira coluna nessa tabela mostra um identificador (ID) da transação, e as outras colunas indicam se umdeterminado item foi ou não comprado na transação correspondente. Suponha que o usuário especificou osparâmetros FSup = 0.3 e FConf = 0.8.

Tabela 1: Entrada de dados para a descoberta de regras de associação.

ID LEITE CAFÉ CERVEJA PÃO MANTEIGA ARROZ FEIJÃO1 Não Sim Não Sim Sim Não Não2 Sim Não Sim Sim Sim Não Não3 Não Sim Não Sim Sim Não Não4 Sim Sim Não Sim Sim Não Não5 Não Não Sim Não Não Não Não6 Não Não Não Não Sim Não Não7 Não Não Não Sim Não Não Não8 Não Não Não Não Não Não Sim9 Não Não Não Não Não Sim Sim

10 Não Não Não Não Não Sim Não

Conjunto de itens frequentes: CAFÉ, PÃO. FSup = 0.3Regra: Se (CAFÉ) então (PÃO). FConf = 1.

Conjunto de itens frequentes: CAFÉ, MANTEIGA. FSup = 0.3Regra: Se (CAFÉ) então (MANTEIGA). FConf = 1.

Conjunto de itens frequentes: PÃO, MANTEIGA. FSup = 0.4Regra: Se (PÃO) então (MANTEIGA). FConf = 0.8.Regra: Se (MANTEIGA) então (PÃO). FConf = 0.8

Conjunto de itens frequentes: CAFÉ, PÃO, MANTEIGA. FSup = 0.3Regra: Se (CAFÉ e PÃO) então (MANTEIGA). FConf = 1.Regra: Se (CAFÉ e MANTEIGA) então (PÃO). FConf = 1Regra: Se (CAFÉ) então (PÃO e MANTEIGA). FConf = 1

Figura 4: Regras de associação descobertas dos dados da Tabela 1 (FSup = 0.3 e FConf = 0.8)

A Figura 4 mostra as regras de associação que seriam descobertas dos dados da Tabela 1 utilizando-se osvalores de FSup e FConf maiores ou iguais aos especificados pelo usuário. Na Figura 4 as regras de associaçãosão agrupadas pelos conjuntos de itens frequentes dos quais as regras foram geradas. A Figura 4 mostra apenasconjuntos de itens frequentes com dois ou mais itens.

O algoritmo Apriori, um dos algoritmos disponíveis na literatura [AGRA97], é responsável por descobriro conjunto de itens frequentes através de múltiplos passos na base de dados. Cada passo inicia com um conjuntosemente de itens, e esse conjunto semente gerará novos conjuntos potenciais, chamados conjunto de itenscandidatos. Em linhas gerais, enquanto o conjunto de itens candidatos não ficar vazio, o algoritmo armazena


esses conjuntos e para cada (tupla) do banco de dados testa se um conjunto candidato está ou não contido natupla. Caso um conjunto candidato esteja contido na tupla, então incrementa-se um contador. Se ao final do testepara cada tupla da base de dados uma regra candidata tiver um suporte mínimo especificado, então ela é inseridanum novo conjunto semente (itens candidatos).

O Algoritmo Basic trabalha de forma análoga ao Apriori [AGRA93]. A diferença está nas transações,pois nesse algoritmo criam-se novas transações, ou tuplas, chamadas transações estendidas. Uma transaçãoestendida é uma nova transação tal que nela são adicionados todos os itens antecessores de um dado item. Porexemplo, “Roupas” podem ser divididas em “Roupas de Frio” e “Roupas de Calor”, e as “Roupas de Frio” em“Jaquetas” e “Calças”. Logo, se numa transação aparece o item “Calça”, então essa transação é adicionada dositens “Roupas de Frio” e “Roupas”.

O Algoritmo Cumulate pré computa os antecessores de um item e só os adiciona na transação se essesitens forem relevantes [AGRA93]. Se ao final do processo de geração de itens candidatos existirem conjuntos deitens candidatos que contenham o item e seu antecessor com o mesmo suporte, então um dos conjuntos éretirado. Por exemplo, se o suporte do conjunto {“Jaquetas”, “Roupas de Frio”} for o mesmo que {“Jaquetas”},então é suficiente retirar um desses conjuntos.

Uma vez que se obtém os conjuntos de itens frequentes, o algoritmo que é responsável por descobrir asregras pode ser como o mostrado na Figura 5.Para cada conjunto de itens frequentes f faça Para cada subconjunto c de f faça Se (suporte(f) / suporte(f - c) ≥ MínimoFConf.) então Saída a regra (f - c) ⇒ c com fator de confidência = suporte(f) / suporte(f - c) E suporte = suporte(f)

Figura 5: Algoritmo para descoberta de regras de associação

Mais informações sobre regras de associação e detalhes sobre os algoritmos Apriori, Basic, Cumulate,Stratify, Estimate e EstMerge, responsáveis pela geração de regras e de conjuntos de itens frequentes podem serencontradas em [AGRA94], [AGRA95], [HAN 97].

Recentemente a descoberta de regras de associação tem sido estendida para outros tipos de atributos quenão sejam estritamente binários. Por exemplo, [FUKU96] propõe algoritmos para descobrir regras de associaçãoque se referem à atributos contínuos ou quantitativos.

4.1.2. Classificação

É a tarefa mais estudada em KDD. Nessa tarefa cada tupla pertence a uma classe entre um conjunto pré-definido de classes. A classe de uma tupla, ou registro, é indicada por um valor especificado pelo usuário em umatributo meta, ou atributo objetivo. As tuplas consistem de atributos preditivos e um atributo objetivo, esseúltimo indicando a que classe essa tupla pertence. O atributo objetivo é do tipo categórico, ou discreto, isto é,pode tomar apenas um valor dentro de um conjunto de valores discretos, determinando classes ou categorias.Esse atributo pode ter valores discretos como SIM ou NÃO, um código pertencente a um intervalo de númerosinteiros, tais como {1..10}, etc.

O princípio da tarefa de classificação é descobrir algum tipo de relacionamento entre os atributospreditivos e o atributo objetivo, de modo a descobrir um conhecimento que possa ser utilizado para prever aclasse de uma tupla desconhecida, ou seja, que ainda não possui uma classe definida. Por exemplo, suponha queuma editora de livros publicou um livro chamado “Um guia para restaurantes franceses na Inglaterra”. O livro épublicado em inglês, francês e alemão, de acordo com o país onde ele está sendo vendido. Suponha também quea editora tem um banco de dados contendo dados sobre seus clientes nos três países, Inglaterra, França eAlemanha. Seria interessante utilizar esses dados para prever que tipo de clientes estariam mais interessados emcomprar esse novo livro. A editora pode então concentrar os esforços de vendas nesses clientes.

Para prever se o cliente irá ou não comprar o livro quando eles receberem um material de propaganda, aeditora necessita de alguns dados sobre o efeito dessa técnica de propaganda em alguns de seus clientes na suabase de dados. A partir desses dados um algoritmo de classificação pode descobrir regras que prevêem se umnovo cliente irá ou não comprar esse novo livro. Para coletar esses dados a editora pode enviar o material depropaganda para alguns de seus clientes e monitorá-los para saber se eles compram ou não o livro. Essainformação é então armazenada em um novo atributo, nesse caso o atributo objetivo. Seu valor pode assumirdois possíveis valores: SIM, significando a compra do livro, ou NÃO, caso contrário. Uma vez esse atributodeterminado, o próximo passo é selecionar um subconjunto de atributos preditivos entre todos os atributos dosclientes no banco de dados. Claramente alguns atributos, tal como: nome do cliente, são de modo geral


irrelevantes para a previsão da compra ou não do livro. No exemplo abaixo serão considerados apenas osatributos SEXO, PAÍS e IDADE dos clientes como relevantes para a previsão.

A Tabela 2 [FREI98] mostra os valores dos atributos preditivos selecionados, junto com valor doatributo objetivo, COMPRAR. Esses são dados de dez clientes, aos quais algum material de propaganda foienviado sobre o novo livro. Um algoritmo de classificação pode analisar os dados da Tabela 2 para determinarque valores dos atributos preditivos tendem a ser relacionados, ou associados, com cada um dos atributosobjetivos. Esta descoberta de conhecimento pode então ser aplicada para prever se um cliente da base de dadosda editora comprará ou não o novo livro. Note que esse conhecimento será aplicado nos clientes para o qual ovalor do atributo objetivo ainda é desconhecido.

Tabela 2: Entrada de dados para a tarefa de classificação

SEXO PAÍS IDADE COMPRARMasculino França 25 SimMasculino Inglaterra 21 SimFeminino França 23 SimFeminino Inglaterra 34 SimFeminino França 30 NãoMasculino Alemanha 21 NãoMasculino Alemanha 20 NãoFeminino Alemanha 18 NãoFeminino França 34 NãoMasculino França 55 Não

Se (PAÍS = Alemanha) então COMPRAR = NãoSe (PAÍS = Inglaterra) então COMPRAR = SimSe (PAÍS = França e IDADE ≤ 25) então COMPRAR = SimSe (PAÍS = França e IDADE > 25) então COMPRAR = Não

Figura 6: Regras de classificação descobertas dos dados da Tabela 2

O conhecimento descoberto é frequentemente representado na forma de regras SE-ENTÃO. Essasregras são interpretadas da seguinte maneira: “SE os atributos preditivos de uma tupla satisfazem as condiçõesno antecedente da regra, ENTÃO a tupla tem a classe indicada no consequente da regra”. A Figura 6 mostra asregras extraídas através de um algoritmo de classificação utilizando os dados da Tabela 2.

Mais informações sobre a tarefa de classificação podem ser encontradas em [MEHT96], [SHAF96],[SHOL91] e [MICH94].

4.1.3. Clustering

Instintivamente as pessoas visualizam os dados segmentados em grupos discretos, como por exemplo,tipos de plantas ou animais. Na criação desses grupos discretos pode-se notar a similaridade dos objetos em cadagrupo.

Enquanto a análise de grupos é frequentemente feita manualmente em pequenos conjuntos de dados, paragrandes conjuntos um processo automático de clustering através da tecnologia de mineração de dados é maiseficiente. Em adição, os cenários existentes são muito similares, tornando-os competitivos, requerendo autilização de algoritmos complexos que determinem a segmentação mais apropriada.

Nessa tarefa de KDD, o algoritmo deve criar as classes através da produção de partições do banco dedados em conjuntos de tuplas. Essa partição é feita de modo que tuplas com valores de atributos semelhantes, ouseja, propriedades de interesse comuns, sejam reunidas dentro de uma mesma classe. Uma vez que as classessejam criadas, pode-se aplicar um algoritmo de classificação nessas classes, produzindo assim regras para asmesmas. Um bom agrupamento caracteriza-se pela produção de segmentos de alta qualidade, onde asimilaridade intra-classe é alta e a inter-classe é baixa. A qualidade do resultado do clustering também dependeda medida utilizada para medir a similaridade usada pelo método e de sua implementação, além de suahabilidade de descobrir algum ou todos os padrões escondidos.

As técnicas mais utilizadas para agrupar dados são baseadas em três categorias: Partição, basicamenteenumera várias partições e então cria uma nota para cada uma delas segundo algum critério; Hierarquia, cria umadecomposição hierárquica do conjunto de dados usando algum critério; Modelo, um modelo é hipoteticamentecriado para cada cluster e a idéia é encontrar o que melhor se enquadra quando comparados entre si.


A maioria das ferramentas de clustering trabalham em função de um número pré-definido de gruposespecificado por um usuário. Isso requer um conhecimento detalhado do domínio, transformando assim a tarefade descoberta de conhecimento menos atrativa. Tecnologias mais sofisticadas são capazes de procurar através dediferentes possibilidades de quantidades de grupos e avaliar cada configuração de acordo com a sua importância.Técnicas baseadas em Redes Neurais Auto Organizáveis utilizando algoritmos Kohonen [HAYK94] também sãocapazes de segmentar grupos de dados. Outras discussões sobre métodos de clustering podem ser encontradasem [JAIN88], [ARAB96] e [RAYM94].

Existem outras tarefas de KDD que menos destacadas, são elas:• Descoberta de regras através da semântica da otimização de “queries” – Esta tarefa transforma uma

query do banco de dados em uma outra query utilizando a semântica do conhecimento da base, taiscomo restrições de integridade e dependências funcionais para produzir uma query mais eficiente[KING81].

• Descoberta de dependências do banco de dados – No modelo de dados relacional, as definições dasrelações na base de dados não dizem nada sobre o relacionamento entre seus atributos. Essesrelacionamentos são especificados através das dependências dos dados, ou das restrições deintegridade [FAGI86], essa tarefa busca automaticamente descobrir tais dependências.

• Regressão – Esta tarefa é conceitualmente similar a tarefa de classificação. A maior diferença é quenessa tarefa o atributo meta, ou objetivo, é contínuo, isto é, pode tomar qualquer valor real ouqualquer número inteiro num intervalo arbitrário, ao invés de um valor discreto [QUIN93].

4.2. FASES DE KDD

No processo de KDD cada fase pode possuir uma interseção com as demais. Desse modo, os resultadosproduzidos numa fase podem ser utilizados para melhorar os resultados das próximas fases. Esse cenário indicaque o processo de KDD é iterativo, buscando sempre aprimorar os resultados a cada iteração. Na execução doprocesso de KDD o usuário analisa as informações geradas em cada fase e procura incorporar sua experiência deanalista de dados para obter cada vez mais melhores resultados.

A definição do problema é fundamental para o processo de KDD. Essa definição requer que a pessoa quesolicita a tarefa de KDD entenda perfeitamente o problema existente e tenha um objetivo bem especificado, ouseja, aquilo que se deseja conhecer ou extrair. Para isso, é necessário uma interação com o solicitador da tarefade modo que seja exposto tudo o que se relaciona com o problema. Tendo sido definido o problema, pode-sefixar metas para os objetivos da tarefa de KDD.

4.2.1. Data Warehousing: Organização de grandes volumes de dados

O processo de KDD deve iniciar a construção de um Data Warehousing (DW). Este é um meio efetivo deorganizar grandes volumes de dados para sistemas de suporte a decisão e aplicações de KDD. Pode-se definir umDW como um repositório integrado, orientado para análise, histórico, com dados apenas para leitura, designadopara ser utilizado como base para suporte à decisão e sistemas KDD [INMO93], [POE 96]. Um DW funcionacomo uma base de dados para dar suporte à decisão mantido separadamente das bases de dados operacionais daorganização. Geralmente integra dados de diversas origens heterogêneas e por isso necessita de uma estruturaflexível que suporte queries e geração de relatórios analíticos.

A Figura 7 mostra o ponto crítico em um DW que é a integração de múltiplos dados, provenientes debases de dados heterogêneas. A integração envolve padronizar atributos, formatos e convenções de nomes, alémde remoção de inconsistências.


Figura 7: Visão resumida das fases do processo de KDD incluindo Data Warehousing

Um DW contém dados históricos, variantes no tempo (geralmente por um período de muitos anos). Essesdados são geralmente organizados de modo a facilitar sua análise por um usuário especializado. Umaorganização típica de dados é armazenar informações quantitativas (por exemplo, vendas de produtos) emgrandes tabelas, chamadas tabelas de fatos, e dados qualitativos, informação descritiva (por exemplo, atributosdo produto) armazenados em pequenas tabelas, chamadas tabelas de dimensão. Este modelo é chamado estrela,pois um simples objeto (tabela de fatos) está no centro do modelo conectado a um número de objetos (tabela dedimensão) radialmente. Além desse modelo, também utiliza-se: - Flocos de neve, um refinamento do modeloestrela onde a hierarquia dimensional é representada explicitamente pela normalização das tabelas de dimensão;- Constelações de fatos, múltiplas tabelas de fatos compartilhando as tabelas de dimensões.

Um DW é uma base apenas para leitura no sentido que um item dessa base é raramente alterado. Em umDW o usuário obtém a informação desejada executando queries pré-definidas que fazem junções entre as tabelasde fatos e dimensões. Atualizações no DW geralmente consistem na inserção de novos dados (e as vezes daretirada de dados mais antigos) num período pré-determinado de tempo, por exemplo, uma vez por semana.

As características citadas estão em contraste com SGBD (Sistema Gerenciador de Banco de Dados), osquais tipicamente contém apenas as últimas versões dos dados e onde tuplas estão constantemente sendoinseridas, apagadas ou alteradas. Um SGBD é uma coleção de programas que habilitam usuários a criar e manterum banco de dados. Ou seja, um SGBD é um sistema que facilita os processos de definição, construção, emanipulação de bases de dados para várias aplicações.

OLAP: Processamento Analítico On-Line (On-Line Analytical Processing)

O Processo Analítico On-Line motiva-se pela necessidade de minerar conhecimento e padrões emdiferentes níveis de abstração através de análises multidimensionais dos dados, ou seja, uma visão lógica dosdados. É uma análise interativa dos dados, permitindo ilimitadas visões através de agregações em todasinterseções de dimensões possíveis. Permite obter informações e mostrá-las em tabelas de 2D e 3D, mapas egráficos, com fácil modificação dos eixos. Além disso, deriva-se análises estatísticas (razões, médias, variâncias)envolvendo quaisquer medidas ou dados numéricos entre muitas dimensões. Um OLAP executa queries com umtempo de resposta pequeno, pois procura-se através de otimização do DW manter as informações solicitadas commaior frequência em memória. Abaixo segue a arquitetura de uma ferramenta OLAP:1. A arquitetura Lógica OLAP


• Visão OLAP – multidimensional e apresentação lógica dos dados em um DW para o usuário detrabalho.

• Tecnologia de armazenamento de dados – Indica as opções de tecnologia de como e onde os dadosserão armazenados.

2. Os três principais componentes de serviços• Serviços de armazenamento de dados• Serviços OLAP• Serviços de apresentação para o usuário

3. Arquiteturas de armazenamento de dados• Multidimensional (MOLAP)• Relacional (ROLAP)

4.2.2. Pré-processamento dos dados

Na Figura 7 nota-se que após a fase de DW inicia-se o pré-processamento dos dados. Essa fase,responsável por consolidar as informações relevantes para o algoritmo minerador, buscando reduzir acomplexidade do problema, inclui 3 sub-fases chamadas: limpeza dos dados, seleção dos dados e transformaçãoou codificação dos dados. Essas fases não necessitam ser executadas nessa ordem, algumas dessas operaçõespodem ser parcialmente executadas durante a construção de um DW.

4.2.3. Limpeza dos dados

A limpeza dos dados envolve uma verificação da consistência das informações, a correção de possíveiserros e o preenchimento ou a eliminação de valores nulos e redundantes. Nessa fase são identificados eremovidos os dados duplicados e/ou corrompidos. A execução dessa fase corrige a base de dados eliminandoconsultas desnecessárias que seriam executadas pelo algoritmo minerador e que afetariam o seu processamento.Os métodos de limpeza dos dados são herdados e dependentes do domínio da aplicação, desse modo aparticipação do analista de dados torna-se essencial. Um exemplo simples de limpeza de dados seria a definiçãode um intervalo de possíveis valores para um determinado atributo, {0..10}. Caso surgisse qualquer valordiferente dos definidos no intervalo, esse dado seria retirado.

4.2.4. Seleção dos dados

Na seleção dos dados deseja-se escolher apenas atributos relevantes do conjunto de atributos do banco dedados. Em suma, a seleção de atributos consiste da escolha de um subconjunto de atributos disponíveis para oalgoritmo de KDD que seja relevante para o objetivo da tarefa. O subconjunto selecionado é então fornecidopara o algoritmo de mineração dos dados. Uma motivação para essa seleção é otimizar o tempo deprocessamento do algoritmo minerador, visto que ele apenas trabalhará com um subconjunto de atributos, dessemodo diminuindo o seu espaço de busca.

Existem 2 principais métodos para a seleção de atributos:• Múltiplas iterações – o dado a ser minerado é dividido em 2 subconjuntos: treinamento e avaliação,

então uma busca heurística iterativa é executada no espaço dos subconjuntos dos atributos. Cadaiteração dessa busca consiste basicamente de três passos. Primeiro, um subconjunto de atributos,chamados atributos candidatos, é selecionado de acordo com algum critério. Segundo, um algoritmoé aplicado no subconjunto de treinamento, composto apenas por atributos candidatos. Terceiro, émedido a qualidade da seleção aplicando-se o resultado obtido no subconjunto de avaliação. Esseciclo permanece até que se chegue a um resultado satisfatório. Os métodos básicos mais utilizadospodem ser: Forward Selection (FS) e Backward Elimination (BE). FS inicia com um conjunto vaziode atributos e iterativamente seleciona um atributo por vez até que nenhuma melhora na medida daqualidade do resultado seja obtida. BE inicia com um conjunto com todos os atributos eiterativamente remove um atributo por vez até que nenhuma melhora na medida da qualidade doresultado seja obtida. Métodos mais sofisticados para seleção de atributos podem ser encontrados em[BALA95], utilizando algoritmos genéticos e [AHA 95] utilizando outros métodos de busca.

• Iteração simples – Este método é independente do algoritmo minerador, ou seja o mesmo conjunto deatributos selecionados pode ser fornecido para qualquer algoritmo minerador. Exemplos podem ser


encontrados em [KIRA92], [KONO94] e [KOLL96]. Esses algoritmos se utilizam de métodosestatísticos como probabilidade de distribuição e são menos complexos em eficiência que o métodode múltiplas iterações.

Uma outra maneira de selecionar os dados é de forma determinística. Nesse caso o analista de dadosescolhe os atributos que segundo sua experiência são essenciais e necessários para explicar, ou compor, oobjetivo da tarefa de KDD.

4.2.5. Codificação dos dados

Um algoritmo de codificação divide os valores contínuos dos atributos (inteiros ou reais) numa lista deintervalos representados por um código. Ele efetivamente converte valores quantitativos em valores categóricos.Ou seja, cada intervalo resulta num valor discreto do atributo. Por exemplo, mostra-se uma possível codificaçãopara o atributo IDADE: {0..18} → Faixa 1; {19..25} → Faixa 2; {26..40} → Faixa 3 e assim por diante. Nesseexemplo, os valores contínuos das idades foram discretizados em 3 faixas. Em alguns casos a transformação deum valor em seu equivalente na base binária pode facilitar o algoritmo minerador a encontrar seu objetivo commelhor qualidade de resultados. Em resumo essa fase converte os dados para a forma mais adequada para aconstrução e interpretação do modelo.

A codificação de dados é potencialmente a tarefa onde há a necessidade de grande habilidade no processode KDD. Tipicamente essa etapa exige a experiência do analista de dados e do seu conhecimento nos dados emquestão. Embora o processo de KDD possa ser executado sem essa fase, nota-se que quando efetivada osresultados obtidos são mais intuitivos e valiosos, além de que, na maioria das vezes, facilita a construção domodelo.

Os algoritmos de codificação podem ser de dois tipos: cego para a classe, dirigido para a classe.O algoritmo cego para a classe discretiza um dado atributo sem considerar o atributo objetivo (classe)

[MANN88]. Por exemplo, dividir um intervalo de valores de um atributo em um número pré-determinado deintervalos do mesmo tamanho. Usando o exemplo do atributo IDADE, este método produziria intervalos como:0-10, 10-20, 20-30, etc.

O algoritmo dirigido para a classe [DOUG95] considera o valor da classe quando discretiza o atributo. Aentrada para esse algoritmo é uma relação com o atributo a ser discretizado e o atributo objetivo, cujo valorindica a que classe a tupla pertence.

As vantagens de se codificar um atributo são: melhorar a compreensão do conhecimento descoberto;reduzir o tempo de processamento para o algoritmo minerador, diminuindo o seu espaço de busca; facilitar oalgoritmo a tomar decisões globais, já que os valores dos atributos foram englobados em faixas. Comodesvantagens cita-se a redução da medida de qualidade de um conhecimento descoberto, perdendo assimdetalhes relevantes sobre as informações extraídas.

4.2.6. Enriquecimento dos dados

Essa fase de enriquecimento consiste em agregar aos dados existentes mais informações de modo queessas contribuam no processo de descoberta de conhecimento. Essas informações serão incorporadas ao processocomo um meta conhecimento do analista de dados, ou seja, informações que não estão na base de dados, porémsão conhecidas e ratificadas. Em suma, o enriquecimento dos dados é qualquer processo capaz de aumentar asinformações já existentes que acredita-se melhorar o desempenho do algoritmo minerador.

4.2.7. Mineração de Dados (Data Mining)

É a etapa mais importante do processo de KDD. Caracteriza-se pela existência do algoritmo que dianteda tarefa especificada será capaz de extrair eficientemente conhecimento implícito e útil de um banco de dados.Pode-se dizer que mineração de dados é a fase que transforma dados em informações, consequentemente umsistema de suporte a decisão baseado em algoritmos de mineração de dados é o que transforma os dados empossíveis ações e na percepção de aumento dos lucros.

Nessa fase necessita-se definir a técnica e o algoritmo a ser utilizado em função da tarefa proposta. ATabela 3 mostra as principais tarefas de KDD e as técnicas mais utilizadas para mineração de dados.


Tabela 3: Algumas tarefas de KDD e suas técnicas de mineração de dados

Tarefas de KDD TécnicasAssociação Estatística e Teoria dos Conjuntos

Classificação Algoritmos Genéticos, Redes Neurais e Arvores deDecisão

Clustering Redes Neurais e EstatísticaPrevisão de Séries Temporais Redes Neurais, Lógica Nebulosa e Estatística

Uma vez escolhido o algoritmo a ser utilizado, deve-se implementá-lo e adaptá-lo ao problema proposto.Para finalizar essa etapa deve-se executar o algoritmo a fim de obter resultados que serão analisados na fase depós-processamento.

4.2.8. Pós-processamento

Finalmente, a saída do algoritmo minerador pode ser refinada numa fase de pós-processamento. Essa faseenvolve a interpretação do conhecimento descoberto, ou algum processamento desse conhecimento. Esse pós-processamento deve ser incluído no algoritmo minerador, porém algumas vezes é vantajoso implementá-loseparadamente. Em geral, a principal meta dessa fase é melhorar a compreensão do conhecimento descobertopelo algoritmo minerador, validando-o através de medidas da qualidade da solução e da percepção de umanalista de dados. Esses conhecimentos serão consolidados em forma de relatórios demonstrativos com adocumentação e explicação das informações relevantes ocorridas em cada etapa do processo de KDD.

Uma maneira genérica de obter a compreensão e interpretação dos resultados é utilizar técnicas devisualização [LEE 95]. Existem também outros tipos de técnicas de pós-processamento criados especialmentepara um dado tipo de algoritmo minerador, ou para uma dada tarefa de KDD. Por exemplo, recentemente têmaparecido pesquisas sobre como converter os pesos das conexões de uma rede neural artificial num conjunto deregras [FU 94], [LU 95], [VAUG96].

A Figura 8 [FAYY96] mostra uma visão mais ampla do processo de KDD, onde a fase de DW não éevidenciada. Em um processo de KDD, a fase DW não é absolutamente necessária, podendo, ser executada pelousuário do sistema conforme a necessidade de dados para o algoritmos minerador. O DW é importante paraagilizar e organizar o processo de KDD, não sendo imprescindível para tal. É importante notar que não existe umsistema que implementa um processo de KDD. Existem sistemas intermediários, controlados por um usuário, ecada sistema é bem definido e com o seu objetivo delineado conforme a tarefa solicitada.


Figura 8: Uma visão mais ampla do processo de KDD

5. DATA MINING

5.1. INTRODUÇÃO

A mineração de dados é considerada a principal fase do processo de KDD. Essa fase é exclusivamenteresponsável pelo algoritmo minerador, ou seja, o algoritmo que diante da tarefa especificada, busca extrair oconhecimento implícito e potencialmente útil dos dados. A mineração de dados é, na verdade, uma descobertaeficiente de informações válidas e não óbvias de uma grande coleção de dados [BIGU96].

A proposta de extrair conhecimento de banco de dados surgiu devido a explosão do crescimento daquantidade de dados armazenados em meios magnéticos e da necessidade de aproveitá-los, motivada pela “fomede conhecimento”. Outro fator que contribuiu em muito para aumento do interesse em mineração de dados foi odesenvolvimento das técnicas de machine learning - redes neurais artificiais, algoritmos genéticos, entre outras,que tornaram a descoberta de relações interessantes em bases de dados mais atrativa.

Quando fala-se de mineração de dados não está se considerando apenas consultas complexas e elaboradasque visam ratificar uma hipótese gerada por um usuário em função dos relacionamentos existentes entre osdados, e sim da descoberta de novos fatos, regularidades, restrições, padrões e relacionamentos.

Na fase de mineração dos dados o executor da tarefa pode utilizar várias ferramentas e técnicas para que oseu objetivo seja bem sucedido. Uma das ferramentas mais utilizadas são aquelas baseadas em consulta a basesde dados, linguagem SQL, pois permite que o executor possa obter uma análise preliminar dos dados.

A mineração de dados envolve diversas áreas e técnicas, além dos principais algoritmos. A Figura 9mostra uma taxonomia da fase de mineração de dados. Os algoritmos estão representados pelo símbolo (•),enquanto que as caixas representam áreas e técnicas.


Figura 9: Taxonomia da fase de Mineração de Dados

Neste capítulo, todos os itens da taxonomia são abordados genericamente, de modo a permitir uma visãoampla de como essas técnicas e algoritmos são empregados na mineração de dados.

A seguir, são apresentadas as principais técnicas e algoritmos utilizados em mineração e dados.

5.2. TÉCNICAS E ALGORITMOS PARA A MINERAÇÃO DE DADOS

A mineração de dados possui não só um amplo espectro de aplicações, mas também de técnicas,algoritmos e procedimentos. Nas seções a seguir são mostrados, resumidamente, os fundamentos das principaistécnicas e a sua modelagem para a mineração de dados.

5.2.1. Redes Neurais Artificiais

Introdução às Redes Neurais Artificiais

Uma Rede Neural Artificial (RNA) é uma técnica computacional que constrói um modelo matemático,emulado por computador, de um sistema neural biológico simplificado, com capacidade de aprendizado,generalização, associação e abstração. As RNAs tentam aprender padrões diretamente dos dados através de umprocesso de repetidas apresentações dos dados à rede, ou seja por experiência. Dessa forma, uma RNA procurapor relacionamentos, constrói modelos automaticamente, e os corrige de modo a diminuir seu próprio erro.

Semelhante ao sistema biológico, uma RNA possui, simplificadamente, um sistema de neurônios, ou nós,e conexões ponderadas (equivalente às sinapses), pesos. Numa RNA os nós são arrumados em camadas, comconexões entre elas. A Figura 10 representa conceitualmente a arquitetura de uma RNA simples. Os círculosrepresentam os nós e as linhas representam os pesos das conexões. Por convenção, a camada que recebe os dadosé chamada camada de entrada e a camada que mostra o resultado é chamada camada de saída. A camada interna,onde localiza-se o processamento interno, é tradicionalmente chamada de camada escondida. Uma RNA podeconter uma ou várias camadas escondidas, de acordo com a complexidade do problema [HOLL92], [DHAR97].


Figura 10: A arquitetura de uma Rede Neural Artificial simples

Para entender como uma RNA aprende é necessário saber como os pesos da rede afetam sua saída. Oaprendizado de uma RNA envolve os ajustes dos pesos. A Figura 11 mostra o esquema de um neurônio artificialcriado a partir do modelo simplificado do neurônio biológico [PERE96]. O neurônio artificial possui váriasentradas, que podem ser estímulos do sistema ou saídas de outros neurônios.

W1

W2

W3

Σ

PesosPropagação

Ativação

X1

X2

X3

Figura 11: Esquema simplificado de um neurônio artificial

O neurônio artificial é dividido em 2 seções funcionais. A primeira seção combina todas as entradas quealimenta o neurônio. Essa etapa indica como as entradas serão computadas (regra de propagação). A segundaseção recebe esse valor e faz um cálculo determinando o grau de importância da soma ponderada utilizando umafunção de transferência, ou função de ativação. Essa função determina a que grau uma soma causará umaexcitação ou inibição do neurônio. Os tipos mais comuns de funções de ativação são sigmóide e tangentehiperbólica, pois fornecem a característica de não linearidade para uma RNA.

Uma RNA ajusta seus pesos na fase de treinamento. É fornecido um dado de observação, o qual éprocessado, e uma resposta será produzida. O resultado fornecido é comparado com uma saída desejada, saídacorreta. Se a rede acerta essa saída, então ela não faz nada, entretanto se o resultado não está correto, ocorre umajuste dos pesos de modo que o erro seja minimizado.


As topologias mais comuns de RNAs são as de múltiplas camadas feed-forward e as redes recorrentes. Oaprendizado de uma RNA pode ser dividido em 3 grupos: sem treinamento – os valores dos pesos sinápticos sãoestabelecidos a priori, ou seja, ajustados em um único passo, por exemplo, Redes de Hopfield [DAYH90];treinamento supervisionado – a rede é treinada através do fornecimento dos valores de entrada e dos seusrespectivos valores de saída desejados (procura minimizar o erro médio quadrado); e treinamento não-supervisionado – o sistema extrai as características dos dados fornecidos, agrupando-os em classes (clusters).

Modelagem de Redes Neurais Artificiais em Mineração de Dados

As principais aplicações de Redes Neurais em mineração são classificação, clustering, aproximação defunções, previsão e verificação de tendências.

De um modo geral, a arquitetura de uma RNA recebe uma tupla (atributos preditivos, ou seja, atributosque pertencem a parte SE de uma regra) como entrada através da primeira camada da rede (camada de entrada).

Figura 12: Modelo de um Rede Neural Artificial para mineração de dados

Tratando-se de aprendizado não supervisionado, não existe atributos objetivo que possa ser utilizadopara corrigir os pesos da rede. Esse tipo de aprendizado aplica-se em tarefas de clustering. As redes autoorganizáveis (por exemplo, Kohonen), baseadas em aprendizado competitivo, destacam-se como um bomalgoritmo [FU 94].

Entretanto, em algoritmos supervisionados, os atributos objetivo são modelados pela camada de saídada rede. Deste modo o algoritmo pode estimar o quanto a saída desejada está distante da saída real. O algoritmomais comum em RNAs com aprendizado supervisionado é o back progation. Seu objetivo é minimizar a funçãoerro entre a saída real da rede e a saída desejada utilizando o método do gradiente descendente [HAYK94].Back-propagation é utilizado para classificar, aproximar funções, prever e verificar tendências [DHAR97].Tomando como exemplo a Figura 12, a camada de entrada pode ser tal que cada nó representa um determinadoatributo preditivo de uma tupla e a camada de saída decodifica a que classe essa tupla pertence, ativando umúnico nó. Maiores detalhes podem ser encontrados em [FREE92].

Para a tarefa de classificação também são utilizadas as redes neurais probabilísticas, baseadas emclassificadores bayesianos e as redes RBF (Radio-Basis Function), baseadas em funções gaussianas. Essesalgoritmos geram curvas de densidade de probabilidade, fornecendo resultados com bases estatísticas. Esses


resultados indicam o grau de evidência sobre o qual se baseia a decisão. Entretanto, essa metodologia sófunciona bem se existir um número suficiente de exemplos na base de dados. A Figura 13 se enquadra comoarquitetura desses algoritmos. A principal diferença está na interpretação do resultado, pois cada nó da camadade saída gera um valor que indica a probabilidade da tupla inserida na camada de entrada pertencer a umadeterminada classe.

h( )

h( )

h( )

X1

X2

Xm

u2σ2

umσm

Σ

Σ

Σ

Σ

y2

y8

s

y1/s

y2/s

y8/s

Figura 13: Uma topologia de uma RNA utilizando bases estatísticas

Nesta topologia, RBF, (Figura 13) o número de neurônios da camada escondida é exatamente igual aonúmero de tuplas apresentadas para treinamento. Onde: Xi é um atributo preditivo da tupla apresentada, h( ) é afunção de ativação, ui é o centro da Gaussiana e σi é o desvio padrão.

As redes Hopfield também são utilizadas para classificação. Nesse algoritmo as classes sãoconsideradas estados. Fornecendo-se uma tupla como entrada para a rede, os pesos são atualizados de modo aocorrer uma convergência para um estado estável, que será sua classe.

Tresp destaca o grande interesse em entender o conhecimento intrínseco que a rede neural adquire notreinamento [TRES97]. Nesse trabalho argumenta-se que redes com funções de base gaussiana podem sergeradas de simples regras probabilísticas e, também, que se regras apropriadas de aprendizados são utilizadas,regras probabilísticas podem ser extraídas das redes treinadas. Nessa pesquisa, apresentam-se métodos para aredução da complexidade da rede com o objetivo de obter regras concisas e significantes.

Towell apresenta um método que eficientemente extrai regras simbólicas de uma RNA treinada[TOWE93]. Os resultados obtidos através de testes empíricos desse método permitem concluir que as regrasextraídas 1) reproduzem com proximidade a acurácia da rede a qual foi extraída; 2) são superiores às regrasproduzidas por métodos que diretamente refinam regras simbólicas; 3) são superiores àquelas produzidas portécnicas anteriores para extração de regras de RNAs treinadas; e 4) são compreensíveis. Conclui-se que essemétodo demonstra que uma RNA pode ser utilizada para efetivamente refinar o conhecimento simbólico.

5.2.2. Algoritmos Genéticos

Algoritmos Genéticos são modelos estocásticos e probabilísticos de busca e otimização, inspirados naevolução natural e na genética, aplicados a problemas complexos de otimização.

Problemas de otimização tipicamente envolvem 3 componentes: variáveis, restrições e objetivos. Asvariáveis descrevem os vários aspectos do problema. As restrições monitoram os valores que as variáveis podemter. Por último, as funções objetivas são utilizadas para avaliar a solução. As funções objetivas geralmenteenvolvem a minimização ou a maximização de algum tipo de recurso. São as funções objetivas que medem aqualidade de uma regra gerada num Algoritmo Genético.

As variáveis, as restrições e as funções objetivas, descritas em um problema de otimização definem ageografia básica do espaço de busca, e determinam que técnicas podem ser usadas. Técnicas baseadas emheurísticas como Algoritmos Genéticos não podem garantir a solução ótima, porém conseguem soluções

1.


próximas, ou aceitáveis (sub-ótimas). Além disso, Algoritmos Genéticos são mais facilmente aplicados emproblemas complexos com muitas variáveis e restrições ou com grandes espaços de busca.

Introdução a Algoritmos genéticos

Um Algoritmo Genético (AG) é um modelo de otimização inspirado na teoria biológica, maisprecisamente, no conceito evolucionário da sobrevivência do mais apto, a seleção natural.

A menor unidade de um AG é chamada gene. Um gene representa uma unidade de informação dodomínio do problema, ou no âmbito de mineração de dados, um valor de um atributo. Uma série de genes, ou umcromossoma, representa uma possível solução completa para o problema, ou seja uma regra candidata.

Soluções ou cromossomas são avaliados por uma função capaz de medir através de um valor asqualidades dessas soluções.

Para que um cromossoma seja avaliado é necessário converter o cromossoma numa solução para oproblema, isto é, decodificar o cromossoma.

Uma vez que o cromossoma foi decodificado, o módulo de avaliação determina o quanto soluções sãoboas ou ruins. Esses dois módulos, decodificador e avaliador, são as únicas partes do AG responsáveis porentender o domínio do problema.

Um AG emprega uma população de cromossomas, executando, assim, uma busca de forma paralela.Após a criação da população inicial (em geral, aleatória), tem inicio um processo iterativo de refinamento ouevolução das soluções iniciais. O AG cria novas soluções através da combinação e refinamento das informaçõesdos cromossomas usando três operações: seleção, crossover e mutação. Essas operações produzem novassoluções que formam uma nova população. Cada nova população é chamada de geração.

Durante a seleção, o AG escolhe os cromossomas, privilegiando aqueles com maiores aptidões parapermanecer e se multiplicar na população. Durante o crossover o AG utiliza as informações dos cromossomasselecionados, formando outros cromossomas, enquanto que durante a mutação o AG busca eventualmentemelhorá-las.

Uma forma comum de seleção é uma onde cada cromossoma tem a probabilidade de permanecer napróxima geração proporcional à sua aptidão (método da roleta). Cromossomas com maiores aptidões possuemmais espaço na roleta e consequentemente possuem maiores chances de serem escolhidos para o cruzamento e amutação.

Durante o crossover, dois cromossomas basicamente trocam algumas de suas informações gene a gene.Ou seja, o crossover permite a combinação dos elementos de uma solução com os de outra.

O operador de crossover recombina as informações, porém não é capaz de gerar diversidade numapopulação, essa diversidade é obtida através do operador de mutação. Sua função é alterar o valor de um genepor um outro valor qualquer no domínio da aplicação

A mutação permite explorar novas áreas a procura de melhores soluções.Esses três operadores, seleção, crossover, e mutação, agem no refinamento das soluções e quando

combinados com os módulos de decodificação e avaliação, podem resolver uma vasta variedade de problemas.


Figura 14: Ciclo Básico de Algoritmos Genéticos

A Figura 14 mostra o ciclo de um AG, para o problema da função de maximização f(x) = x2. Nesse casoos cromossomas são palavras de 6 bits de comprimento. Inicialmente cria-se uma população inicial aleatória(cromossoma A, B, C, e D), representados por palavras binárias. Essas palavras são decodificadas (binário →inteiro) e em seguida avaliadas, conhecendo-se suas aptidões. Posteriormente esses cromossomas passam pelomódulo de seleção, definindo-se então os pais que irão se reproduzir. Após a passagem dos cromossomas paispelos módulos de crossover e mutação, finaliza-se uma geração e o ciclo reinicia com a avaliação da aptidãodessa nova população, parando apenas quando algum critério é alcançado (por exemplo: número máximo degerações).

AGs têm sido empregados com sucesso em numa variedade de problemas de busca e otimização[HOLL75], [DASG97]. Trabalhos de AGs em aprendizado tem tradicionalmente sido classificados em uma das2 aproximações gerais. A aproximação de Pitt [SMIT80] utiliza um AG de modo tradicional, a qual cadaentidade da população é um conjunto de regras representando uma solução completa para o problema deaprendizado. Crossover e mutação são aplicados de modo usual para criar novas gerações a partir de umapopulação. E, a aproximação de Michigan [HOLL86] que tem utilizado distintamente diferentes mecanismosevolucionários. A população consiste de regras individuais, cada uma representando uma solução parcial paratoda a tarefa de aprendizado. Apenas através de cooperação com outras regras da população o problema éresolvido.

Mais informações sobre Algoritmos Genéticos e sua base matemática podem ser encontrados em[GOLD89], [HOLL92], [BELE91].

Modelagem de Algoritmos Genéticos para a Mineração de Dados

Os AGs têm sido empregados em mineração de dados para as tarefas de classificação e descrição deregistros de uma base de dados, além da seleção de atributos de bases de dados que melhor caracterizem oobjetivo da tarefa de KDD proposta [KIRA92], [KOLL96].

Na classificação de registros, os modelos de AGs geram regras que exprimem uma realidade do domínioda aplicação. Essas regras são de fácil interpretação, o que incentiva o uso dessa técnica, Algoritmos Genéticos.


A Tabela 4 mostra sucintamente os principais trabalhos encontrados na literatura em mineração de dadospor algoritmos genéticos.

Tabela 4: Principais trabalhos de Algoritmos Genéticos em mineração de dados

Nome Tarefas Representação Características DesempenhoRadcliffe

GA-MINERClassificação eDescoberta de

Padrões através deregras explícitas

Estruturada semcadeia de caracteresutilizando cláusulasque são descriçõesde subconjuntos da

base de dadosSubc = Clausula [ou

Cláusula]Cláusula = Termo [e

Termo]Termo = Valor doatributo | intervalo

do atributo

Utiliza descoberta deconhecimento

direcionada, nãodirecionada e

refinamento dehipóteses utilizando

basicamentemedidas estatísticas

As funções deavaliação mostramque o mecanismosde avaliação geram

resultadosqualitativamente

similares

Smith[SMIT80][SMIT84]

LS-1

Classificação Estruturada nasemântica dodomínio doproblema

Manipula regras deprodução

DeJong[DEJO93]GABIL

Classificação porregras

Binária utilizandoapenas valores

discretos

Aprendizado dadescrição de uma

única classeGreene

[GREE93][GREE94]COGIN


Atributoscodificados em

palavras binárias

Focaliza o problemade domínios demulti-classes

Neri[NERI95][GIOR94]]REGAL


Utiliza lógica deprimeira ordem

Em outros trabalhos, [AUGI95], [NERI95], o AG tem a finalidade de descobrir descrições de classesutilizando lógica de primeira ordem. Já em [ANGL97], [JANI93] destaca-se a criação de operadores genéticosnão convencionais para a tarefa de classificação. Em [IGLE96] pode-se encontrar uma comparação entre AG eindução de regras no contexto de KDD.

GA-MINER é um sistema que pode ser utilizado para tarefas direcionadas de descoberta deconhecimento, como também para as não direcionadas e, para refinamento de hipóteses. Em mineração de dadosnão direcionada o ponto chave é que não é necessário se especificar o tipo de regra desejada. O usuário podeperguntar coisas do tipo: “Diga-me alguma coisa interessante sobre meus dados”. Já em mineração de dadosdirecionada, existe uma forte especificação que direciona o sistema. Uma pergunta específica nesse caso podeser: “Caracterize os clientes que mais consomem em minha empresa”. No caso de refinamento de hipóteses ousuário informa uma hipótese, o sistema avalia, e se a evidência for verdadeira então ele busca refinar. Umusuário pode conceitualmente dizer: “Eu acho que existe uma correlação positiva entre a venda de pêssegos ecreme: Eu estou certo?”.

Um outros trabalho de AG baseado em aprendizado é o LS-1 [SMIT80], [SMIT84], que apresenta umarepresentação estruturada baseada na semântica do domínio do problema com operadores genéticos trabalhandoem diferentes níveis de granularidade, refletindo a semântica da representação. LS-1 utiliza a aproximação dePitt, cuja base de conhecimento do conjunto de produção de regras (população) é manipulado por operadoresgenéticos e, em qualquer instante, a melhor regra dessa base é armazenada como hipótese corrente da solução datarefa de aprendizado. LS-1 age como uma máquina de estado finito, na qual as regras de produção, quegovernam os estados de transição e sua resposta ao ambiente, são envolvidas por um algoritmo Genético.

GABIL [DEJO93] também utiliza a aproximação de Pitt para evoluir o conceito de descrição, o qual édefinido como uma coleção de possíveis sobreposições de regras de classificação, através da interação com oambiente. O lado esquerdo das regras de classificação consistem de conjunções de atributos (conjunto devalores), enquanto o lado direito especifica a classe a qual a regra associará um registro que satisfaça o ladoesquerdo (condição). Apenas atributos discretos são utilizados e o conjunto de valores são codificados em forma


binária. O foco do trabalho está no aprendizado da descrição de uma única classe. Registros não cobertos pornenhuma regra de produção do conceito descrito são ditos como não pertencentes ao conceito. Os problemasfrequentemente especificam aprendizados em multi-conceitos, onde mais de uma classe pode existir e, registrospodem ser cobertos por várias regras de produção conflitantes. O modelo construído baseado em conceito deaprendizado é simples e possui uma arquitetura unificada com algumas qualidades importantes. Primeiro, osistema é robusto mesmo com um mínimo “bias”. Segundo, o sistema pode ser facilmente estendido paraincorporar formas tradicionais de “bias” encontrados em outros conceitos de sistemas de aprendizado.Finalmente, a arquitetura do sistema encoraja a representação explícita dos “bias”, como resultado, provê umaqualidade adicional: a habilidade de dinamicamente ajustar o sistema de “bias”. O conceito de descrição (funçãode avaliação) é medido como o quadrado da porcentagem de registros corretamente classificados.

COGIN [GREE93], [GREE94] focaliza o problema de domínios de multi-classes através da competiçãopelas tuplas do conjunto de exemplos, reduzindo sua complexidade. Utiliza a aproximação de Michigan no quediz respeito a encorajar a população a trabalhar junta para resolver um problema de aprendizado, entretanto seumecanismo evolucionário é distinto da aproximação de Pitt. Cada regra é uma conjunção de atributos,codificados em binário. Diferente de implementações de AG tradicionais, regras são escolhidas pararecombinação aleatoriamente. As novas regras criadas, juntas com a população de regras existentes, são entãoordenadas em função da sua aptidão e, são inseridas uma por uma ordenadamente na próxima geração dapopulação. As regras são inseridas desde que ainda existam registros não cobertos por regras inseridasanteriormente. Quaisquer regras redundantes são excluídas. O tamanho da população muda dinamicamente deacordo com o número de regras requeridas para cobrir todo o conjunto de registros. COGIN é um AG baseadoem sistemas indutivos que explora as convenções de indução dos exemplos. Sua função de avaliação é baseadaem entropia, modificada de acordo com a acurácia da classificação. São utilizados crossover de um ponto euniforme e, a recombinação é utilizada apenas no lado esquerdo da regra, enquanto que o lado direito associa aclasse com a maioria dos registros do conjunto de exemplos cobertos pela regra.

REGAL [NERI95] [GIOR94] utiliza uma aproximação baseada em abrangência para o aprendizado emmúltiplos conceitos, similar ao COGIN. Uma população de descrições conjuntivas para conceitos é mantida,formando um conjunto redundante de soluções parciais e, todo o conceito da tarefa de indução é executada portoda a população de regras. O sistema utiliza lógica de primeira ordem como representação da regra. Foramutilizadas operadores de crossover de dois pontos e uniforme juntamente com operadores de generalização eespecialização.

GA/RULE [PEI 95] é um AG baseado em aprendizado indutivo combinado com um sistema de produçãode regras. Esse AG também é baseado na aproximação de Pitt, e seu foco é na descoberta de padrões através deregras de classificação.

Tratando de seleção de atributos, pode-se dizer que uma seleção apropriada de atributos ajuda a facilitar atarefa de classificação, pois elimina dados ruidosos ou atributos não representativos que podem impedir oreconhecimento do padrão. Mesmo quando alguns atributos possuem alguma informação utilizável, estes podemreduzir a acurácia do classificador quando a quantidade de dados para treinamento é reduzida [TRUN79],[FERR94].

Siedlecki e Skalanski tem aplicado algoritmos genéticos ao problema de seleção de atributos [SIED89].No seu trabalho, o AG, executa a seleção de atributos combinado com um classificador KNN (k-nearest-neighbors), o qual é usado para avaliar a performance de classificação para cada subconjunto de atributosselecionados pelo AG. O AG mantém um vetor binário de atributos selecionados, onde cada bit representa umatributo da base. Quando um bit está ativado, valor igual a 1, indica que o atributo correspondente participa naclassificação do KNN, caso contrário, ele é omitido. O AG procura por um vetor de seleção que possui ummínimo de 1’s, de modo que a taxa de erro do classificador KNN permaneça abaixo de um valor fornecidopreviamente pelo usuário.

Punch e outros e, Kelly e Davis expandiram o modelo de Siedlecki e Skalanski para o uso de AG emseleção de atributos [PUNC93], [KELL91]. Ao invés de existir um vetor binário de atributos selecionados, o AGmanipula um vetor de pesos. Nesse vetor, cada atributo esta associado a um valor real discretizado. A meta doAG é encontrar um vetor de pesos que minimize a taxa de erro do classificador KNN, ao mesmo tempo queprocura reduzir os valores dos pesos a zero.

5.2.3. Lógica Indutiva

Nessa seção é apresentada uma breve introdução sobre Lógica Indutiva. As referências citadas detalhamtodos os aspectos e fundamentos dessa área.

Quando se procura aprendizado de grandes bancos de dados, a redução da complexidade é extremamenteimportante. Dois extremos na construção do processo de KDD são identificados: o primeiro está na escolha deuma linguagem de hipóteses muito simples e, o extremo oposto é selecionar um pequeno conjunto de dados.


Criando-se uma aproximação multi-estratégica, permite-se incluir a maioria das vantagens e excluir grande partedas desvantagens. Algoritmos simples de aprendizado detectam hierarquias que são usadas para estruturar oespaço de hipóteses para um algoritmo de aprendizado mais complexo. Essas características podem ser obtidascombinando lógica indutiva diretamente com o sistema de gerenciamento de base de dados relacionais[MORI97].

Programação por Lógica Indutiva (LI) [MUGG92], [RAED92], [LAVR94], pode ser vista como umamáquina de aprendizado em lógica de primeira ordem, onde as relações são apresentadas no contexto de bancode dados dedutivos [ULLM88]. LI é relevante para a descoberta de conhecimento em base de dados relacionais ededutivas, pois pode descrever padrões envolvendo mais de uma relação.

Desenvolvimentos em aprendizado indutivo focam no problema da construção de uma definição lógicapara uma relação [QUIN90] através do conhecimento de tuplas que pertençam ou não a essa relação. Dessemodo novas relações podem ser especificadas por um número menor de tuplas, as quais são então generalizadaspara induzir uma definição lógica. Alguns sistemas recentes utilizando essa técnica são FOIL [QUIN90] eLINUS [LAVR91], que são capazes de manipular ruídos e atributos contínuos.

5.2.4. Métodos Estatísticos

Analisando os métodos estatísticos, nota-se um foco no trabalho de interpretabilidade como formulaçõesalternativas derivadas do modelo linear. A comunidade estatística está geralmente interessada em interpretar seusmodelos, e possivelmente sacrificando-os de alguma performance para ser capaz de extrair significado de suaestrutura. Daí surgem as teorias da probabilidade penalizada e formulações Bayesianas [SULL86]. Existemdiversos métodos estatísticos, alguns clássicos e outros mais recentes, e todos assumem a existência de umavariável (atributo) resposta, y, e uma coleção de variáveis preditoras, x = (x1, x2, ... xj), além da disponibilidadede dados para treinamento. A meta é encontrar um modelo para prever y de x que funcione bem quando aplicadoa um novo dado. [FRIED95] provê um resumo dos principais modelos aplicados à todas as técnicas de indução.[WEIS91] descreve técnicas para tarefa de classificação utilizando aprendizado de máquina (machine learning),incluindo análise de discriminante linear, árvores de decisão, redes neurais e sistemas especialistas.

A seguir são abordados de maneira concisa alguns dos principais métodos estatísticos. As formulaçõesmatemáticas e alguns conceitos não serão demonstrados, porém estão a disposição nas referências citadas.

Classificadores Bayesianos

O princípio básico desse método está fundamentado na teoria da probabilidade bayesiana [SHEN 93].Assumindo-se a Equação 1 , que estabelece:

Equação 1

P(AB|C) = P(A|C)P(B|AC) = P(B|C)P(A|BC)

Onde P refere-se a probabilidade de um evento. A, B, e C são subconjuntos do espaço de amostras(universo do problema, ou seja, a base de dados) e a notação P(AB|C) significa “a probabilidade dos eventos A eB acontecerem dado que o evento C acontece”. De modo análogo P(A|C) significa “a probabilidade do evento Aacontecer dado que C acontece”.

Desse modo, sejam A1, ..., Ak atributos, [a1, ..., ak] uma tupla do banco de dados, e C uma classe a serprevista. A previsão ótima é uma classe de valor c tal que:

Equação 2

P(C = c | A1 = a1 ∩ ... ∩ Ak = ak)

é máxima.Transformado a Equação 2 através da regra de bayes, que estabelece:

Equação 3

P(A|B) = P(B|A) * P(A) / P(B), tem-se:

Equação 4

P(A1 = a1 ∩ ... ∩ Ak = ak | C = c) * P(C = c) / P(A1 = a1 ∩ ... ∩ Ak = ak)


Pode-se perceber da Equação 4 que:• P(C = c) é fácil de estimar através do conjunto de treinamento, pois simplesmente é a razão do

número de vezes em que c ocorre pelo número de tuplas do conjunto de treinamento;• P(A1 = a1 ∩ ... ∩ Ak = ak) é irrelevante, pois é o mesmo para todos os c, já que independe da

classe a que a tupla pertence, nesse caso uma constante do processo.Resta então descobrir como calcular a parcela referente a Equação 5:

Equação 5

• P(A1 = a1 ∩ ... ∩ Ak = ak | C = c)

Assumi-se que os atributos são independentes, nesse caso a Equação 5 transforma-se em:

Equação 6

P(A1 = a1| C = c) * P(A2 = a2| C = c) * ... P(Ak = ak| C = c)

Onde cada termo da Equação 6 pode ser estimado como:

Equação 7

P(Aj = aj| C = c) = Contador(Aj = aj| C = c) / Contador(C = c)

Contador é uma função que conta o número de vezes, ou a frequência, que um dado evento ocorre na basede dados. A Tabela 5 mostra um exemplo [WEI 98] de um banco de dados que servirá como entrada paraextração de conhecimento utilizando classificadores bayesianos.

Tabela 5: Exemplo de entrada para Classificadores Bayesianos

DIA APARÊNCIA TEMPERATURA UMIDADE VENTO JOGAR TÊNISD1 Ensolarado Quente Alta Fraco NãoD2 Ensolarado Quente Alta Forte NãoD3 Nublado Quente Alta Fraco SimD4 Chuvoso Moderado Alta Fraco SimD5 Chuvoso Fresco Normal Fraco SimD6 Chuvoso Fresco Normal Forte NãoD7 Nublado Fresco Normal Forte SimD8 Ensolarado Moderado Alta Fraco NãoD9 Ensolarado Fresco Normal Fraco Sim

D10 Chuvoso Moderado Normal Fraco SimD12 Ensolarado Moderado Normal Forte SimD12 Nublado Moderado Alta Forte SimD13 Nublado Quente Normal Fraco SimD14 Chuvoso Moderado Alta Forte Não

Através da Tabela 5 pode-se perguntar:• Qual a probabilidade de se jogar tênis dado que o dia está ensolarado, com temperatura quente, umidade

alta e vento fraco? Em termos probabilísticos essa pergunta equivale a P(JOGAR TÊNIS = Sim |[Ensolarado, Quente, Alta, Fraco])

• Qual a probabilidade de NÃO se jogar tênis dado que o dia está ensolarado, com temperatura quente,umidade alta e vento fraco? Em termos probabilísticos essa pergunta equivale a P(JOGAR TÊNIS =Não | [Ensolarado, Quente, Alta, Fraco])

Calculando-se cada evento por meio da Equação 7, tem-se:

Tabela 6: Cálculo das probabilidades dos dados da Tabela 5 utilizando Classificadores Bayesianos

PERGUNTA PROBABILIDADEP(JOGAR = Sim) 9/14P(JOGAR = Não) 5/14P(APARÊNCIA = Ensolarado | JOGAR = Sim) 2/9P(APARÊNCIA = Ensolarado | JOGAR = Não) 3/5P(TEMPERATURA = Quente | JOGAR = Sim) 2/9


P(TEMPERATURA = Quente | JOGAR = Não) 2/5P(UMIDADE = Alta | JOGAR = Sim) 3/9P(UMIDADE = Alta | JOGAR = Não) 4/5P(VENTO = Fraco | JOGAR = Sim) 6/9P(VENTO = Fraco | JOGAR = Não) 2/5

Uma vez que as probabilidades de cada termo foram calculadas, pode-se estimar através da Equação 4que:

• P(JOGAR TÊNIS = Sim | [Ensolarado, Quente, Alta, Fraco]) = [(2/9) * (2/9) * (3/9)*(6/9)] * (9/14) /[(5/14) * (4/14) * (7/14) * (8/14)] = (108/6561) * (9/14) / (1120/38416) = 0,3630 = 36,30%

• P(JOGAR TÊNIS = Não | [Ensolarado, Quente, Alta, Fraco]) = [(3/5) * (2/5) * (4/5) * (2/5)] * (5/14) /[(5/14) * (4/14) * (7/14) * (8/14)] = (48/625) * (5/14) / (1120/38416) = 0,9498 = 94,98%

Esse tipo de método é bastante utilizado por sua facilidade de interpretação, em [CHEE96] apresenta umaexposição detalhada de um modelo utilizando métodos bayesianos, chamado AutoClass.

Redes Bayesianas

Muitas técnicas de KDD baseiam-se apenas nos dados. Em contraste, o conhecimento codificado emsistemas especialistas, geralmente, baseia-se unicamente em um especialista. Uma representação deconhecimento utilizando uma arquitetura baseada em Rede Bayesiana (RB) combina o melhor das duas áreas, ouseja, o conhecimento do domínio do especialista e a estatística dos dados [HECK96], [ALIF94].

O processo de descoberta de conhecimento utilizando RBs segue os seguintes passos. Primeiro,codifica-se o conhecimento existente de um especialista ou um conjunto de especialista numa RB.Posteriormente, utiliza-se uma base de dados para atualizar esse conhecimento, criando uma ou mais novas RBs.O resultado inclui um refinamento do conhecimento original do especialista e algumas vezes da identificação denovos relacionamentos.

A descoberta de conhecimento utilizando RB é similar a descoberta por Redes Neurais Artificiais. Oprocesso empregado em RBs, entretanto, possui duas importantes vantagens. Uma, pode-se facilmente codificarconhecimento de um especialista em RBs e usar esse conhecimento para aumentar a eficiência e a qualidade doconhecimento descoberto. Dois, os nós e arcos em uma RB treinada geralmente correspondem a distinções devariáveis e relacionamentos causais. Consequentemente, pode-se mais facilmente interpretar e entender oconhecimento codificado na representação. A interpretação de uma probabilidade como uma frequência numasérie de repetições de experimentos é tradicionalmente referida como sendo uma interpretação objetiva. Emcontraste, a interpretação de uma probabilidade como um grau de certeza é chamado de subjetiva, ouinterpretação bayesiana. Nessa última interpretação, a probabilidade ou certeza geralmente dependerá do estadode conhecimento da pessoa que provê aquela probabilidade. Essa probabilidade pode ser escrita como P(e|ξ),significando “probabilidade de e dado ξ”. O símbolo ξ representa o estado de conhecimento da pessoa que provêa probabilidade e um evento. Uma variável representa uma distinção sobre o mundo. Ela toma valores de umacoleção de estados mutuamente exclusivos ou coletivamente exaustivos, onde cada estado corresponde a algumevento. Uma RB é um modelo para algum problema de domínio ou universo, o qual consiste de um conjunto devariáveis. Uma RB num determinado domínio U representa uma função distribuição de probabilidade, P(U|ξ).

Para ilustrar essa representação, considere o domínio para o problema de uma carro que não dá partida[HECK96]. O primeiro passo na construção de uma RB é decidir quais são as variáveis e estados do modelo.Uma possível escolha de variáveis para esse domínio é “bateria” com estados bom e ruim, “gasolina” comestados não vazio e vazio, “manômetro” com estados não vazio e vazio, “ligado” com os estados sim e não, e“partida” com os estados sim e não.

O segundo passo é construir um grafo acíclico que codifica asserções de independência condicional.Dado um domínio U = {x1, x2, ..., xn} e uma ordem nas variáveis (x1, x2, ..., xn), pode-se gerar o grafo da funçãodistribuição de probabilidade de U.


Bateria

Mamômetro

LigadoPartida

Gasolina

Figura 15: Exemplo de grafo de independência condicional de Redes Bayesianas

A Figura 15 mostra a estrutura em forma de grafo de independência condicional, nele os arcos sãodirecionados da causa para o efeito.

O passo final na construção de um RB é avaliar as distribuições locais, ou seja, a distribuição deprobabilidade para cada estado do domínio. O problema de computar as probabilidades de interesse da funçãodistribuição de probabilidades é chamada inferência probabilística. Dada qualquer RB, pode-se utilizar a funçãoda distribuição da probabilidade determinada pela rede para fazer a inferência probabilística.

Transformando as variáveis em atributos do banco de dados e os estados como seus possíveis valores,pode-se então utilizar RB para extrair independências condicionais associadas com as asserções de que um bancode dados é um conjunto de exemplos aleatórios para a estrutura x → y.

Maiores detalhes sobre RB e métodos de aprendizados podem ser encontrados em [BUNT95] que é umaguia bem detalhado sobre RB; [CHAR91] apresenta uma introdução de fácil leitura; e [SPIE93] apresentadiscussões de métodos de aprendizado por RBs que trabalham em domínios apenas com variáveis discretas.

Árvores de decisão

Uma árvore de decisão é uma árvore com uma estrutura onde cada nó interno é rotulado com um dosatributos preditivos; cada seta que sai do nó interno é rotulado com valores dos atributos de cada nó; e todo nófolha é rotulado com uma classe (valor do atributo objetivo).

Idade

Alemanha

N

S N

S

InglaterraFrança

País

> 25≤ 25

Figura 16: Uma árvore de decisão construída com os dados da Tabela 2

Por exemplo, a Figura 16 possui uma possível árvore de decisão para o exemplo da Tabela 2,. Cadacaminho da árvore pode ser convertido numa regra. O nó interno e os valores das setas são convertidos noantecedente da regra (parte SE); o nó folha é convertido no consequente da regra (Parte ENTÃO). Uma árvore dedecisão classifica uma nova tupla de maneira top-down. Inicialmente a nova tupla é passada para o nó raiz daárvore, o qual testa que valor a tupla tem no atributo rotulado no nó. Depois a tupla é testada nos nós inferioresseguindo o caminho das setas em função do valor da tupla no atributo rotulado no nó corrente. Esse processo érecursivamente repetido até que a tupla chegue à folha. A tupla <”Masculino”, “França”, “23”, ?>, identifica umcliente. A ? representa o valor que o atributo objetivo, nesse exemplo particular, o atributo COMPRAR, deveráter. Esse atributo informa se o cliente compra ou não o novo livro. Ao percorrer essa tupla na árvore da Figura16, pode-se classificá-la como “Sim” no atributo COMPRAR. O nó raiz da árvore representa o atributo PAÍS,


onde na tupla consta “França”, direcionando então a classificação para o nó representando o atributo IDADE.Verificando a tupla, esse atributo possui o valor “23”, que é menor ou igual a 25, novamente o algoritmodireciona a classificação do atributo COMPRAR, sendo que, dessa vez para o nó folha rotulado por “S”, quesignifica “Sim”.

Uma árvore de decisão é geralmente construída de maneira top-down, utilizando um algoritmo baseadona aproximação “dividir para conquistar” [QUIN93]. Inicialmente todas as tuplas que estão sendo mineradas sãoassociadas ao nó raiz da árvore. Então o algoritmo seleciona uma partição de atributos e divide o conjunto detuplas no nó raiz de acordo com o valor do atributo selecionado. O objetivo desse processo é separar as classespara que tuplas de classes distintas tendam a ser associadas a diferentes partições. Esse processo érecursivamente aplicado a subconjuntos de tuplas criados pelas partições, produzindo subconjuntos de dadoscada vez menores, até que um critério de parada seja satisfeito. Discussões sobre algoritmos de poda de umaárvore de decisão podem ser encontrados nas próximas seções e em [AGRA92], [ESPO95], através dos quaisbusca-se minimizar o tamanho da árvore, sem prejudicar a qualidade da solução.

As principais vantagens de algoritmos baseados em árvores de decisão são sua eficiência computacionale simplicidade. Devido ao uso da aproximação “dividir para conquistar”, entretanto essa aproximação tambémpossui desvantagem. Por exemplo, uma condição envolvendo um atributo que será incluído em todas as regrasdescobertas. Essa situação possivelmente produz regras com informações irrelevantes, além de desperdício deprocessamento. A seguir são apresentados dois dos principais algoritmos baseados em árvores de decisão.

1.1.1.1.1. Indução de Regras

Esse tipo de algoritmo é baseado em duas noções chaves: estado e operador. Um estado é a descrição dasituação de um problema num dado instante, e um operador é um procedimento o qual transforma um estado emoutro. Resolver um problema utilizando essa algoritmo consiste em encontrar uma sequência de operadores osquais transformam um estado inicial num estado objetivo, ou estado meta, [PEAR85], [WINS92].

Nesse contexto, um estado corresponde a uma regra candidata e os operadores correspondem a operaçõesde generalização e/ou especialização que transformam uma regra candidata em outra [MICH83], [HOLS94]. Aescolha do operador que será aplicado a uma dada regra candidata é determinada por uma função heurística queavalia a eficácia de cada operador com respeito a cada regra candidata.

Exemplos de operações de especialização e generalização utilizando indução de regras estão na Figura 17.Essa figura refere-se ao exemplo de classificação mostrado na Tabela 2. A parte (a) mostra que a regra pode serespecializada pela conjunção de “IDADE ≤ 25” ao antecedente. Note que a nova regra é uma especialização daoriginal porque o antecedente da regra é satisfeito por um número menor de tuplas no banco de dados. A regraoriginal acerta 5 registros, enquanto a regra especializada acerta apenas 2.

Na generalização a idéia é estender o intervalo de valores cobertos pelo atributo IDADE, relaxando-o demodo que o antecedente da regra satisfaça um número maior de tuplas na base de dados, nesse caso passou de 2para 3 registros.Regra original: Se (PAÍS = França) então COMPRAR = SimRegra especializada: Se (PAÍS = França e IDADE ≤ 25) então COMPRAR = Sim

(a) Especializando uma regra pela adição da conjunção em seu antecedente

Regra original: Se (PAÍS = França e IDADE ≤ 25) então COMPRAR = SimRegra generalizada: Se (PAÍS = França e IDADE ≤ 30) então COMPRAR = Sim

(b) Generalizando uma regra relaxando uma condição no antecedente

Figura 17: Exemplo da operações de especialização e generalização em indução de regras

A principal vantagem dessa técnica é que geralmente ela produz conhecimento compreensível[LANG95]. Tipicamente, o conhecimento descoberto está na forma de regras “SE-ENTÃO” como mostrado naFigura 17, desse modo ele pode ser facilmente entendido e validado por um usuário.

1.1.1.1.2. Algoritmo ID3

Em termos gerais um algoritmo para construção de uma árvore de decisão pode seguir apenas 3 passos.• Dado um nó na árvore e todas as tuplas do conjunto de treinamento S;• Selecione o melhor atributo A para esse nó;• Para cada valor vi de A, cresça uma sub-árvore (ou uma folha) sob o nó.


A definição do melhor atributo, segue o seguinte critério:Seja S todas as tuplas do conjunto de treinamento, A um atributo, s uma tupla, v um valor, e c o número

de classes, defini-se.

Equação 8

Sv = {s ∈ S | A(s) = v}A Equação 8 representa o conjunto de todas as tuplas do conjunto de treinamento que possuem no

atributo A, o valor v. Defini-se a entropia de S, como:

Equação 9

Entropia(S) = ∑ i=1, ..., c -pi * log(pi)Onde pi é a probabilidade de ocorrência de uma determinada classe. Desse modo pode-se definir o ganho

da escolha de um atributo A com respeito a S como:

Equação 10

Ganho(S, A) = Entropia(S) - ∑ v ∈ valores(A) (|Sv| / |S|) * Entropia(Sv)O algoritmo ID3 recebe como entrada um conjunto de tuplas para treinamento, chamado Exemplos, um

atributo objetivo, Meta, e um conjunto de atributos preditivos, Atributos.Baseando-se nas definições anteriores, o algoritmo caracteriza-se nas seguintes etapas:

ID3(Exemplos, Meta, Atributos) – é a chamada para a execução do algoritmo com seus argumentos pré-definidos anteriormente. Como já mencionado antes, esse algoritmo é recursivo, ou seja, seu procedimento seráexecutado n vezes até que alguma condição seja satisfeita. O texto que segue em itálico é um comentárioresumido sobre a execução de cada etapa do procedimento.

• Criar uma raiz para a árvore – Cria um nó sempre que o procedimento é executado, esse nó será um nócorrente;

• Se o conjunto de Exemplos são positivos, retorna a raiz o rótulo Sim; ou Não, caso negativo – Positivosignifica que todas as tuplas que estão no conjunto de exemplos pertencem a uma mesma classe,negativo, caso contrário;

• Se o conjunto de Atributos está vazio, retorna a raiz o valor da classe mais comum no conjunto deExemplos – Analisa se ainda existem atributos não utilizados;

• Seleciona o melhor atributo A do conjunto de Atributos, e para cada valor vi de A, executa: - o melhoratributo é selecionado segundo a Equação 10 e seu rótulo é colocado no nó raiz, ou nó corrente;

• Adiciona uma nova seta para A = vi e cria um conjunto E’ com todas as tuplas onde oatributo A = vi – Cria-se links do nó raiz com todos os possíveis valores do atributo Apara outros nós;

• Se o conjunto E’ for um conjunto vazio, então adicione um nó folha, senão adicione onó ID3(E’, Meta, Atributos - {A}) – Será criada uma nova sub-árvore. Essa é achamada recursiva do procedimento. Nela pode-se notar que os argumentos deentrada são sempre diferentes para cada chamada;

• Retorne a raiz – Quando uma sub-árvore chega a um nó folha, o procedimento retorna para o nó raiz,continuando sua execução até que toda a árvore seja construída.

Além do algoritmo ID3, podem ser encontrados na literatura os algoritmos CN2 [CLAR91, de aprendizadopara um conjunto de regras de classificação; e FOIDL e CDL3, que utilizam aprendizado com listas de decisãode primeira ordem [SHEN 92].

[KLOE94] apresenta EXPLORA, uma ferramenta interativa de análises estatísticas para descoberta embanco de dados. Nela um número de padrões são definidos permitindo-se selecionar os padrões mais apropriadospara a análise do problema proposto. Subconjuntos da base de dados são selecionados usando construtores delógica proposicional, consistindo de conjunções de testes condicionais nos atributos e valores. A avaliação debons padrões é executado através de testes de significado estatístico, e a busca no espaço de padrões é executadousando uma busca por grafo, combinados com filtros de redundância que asseguram que apenas regrasverdadeiras e não redundantes são gerados.

FORTY-NINER [ZYTK91], [ZYTK93] procura por regularidades em bases de dados, ou seja, um padrãoe os limites ao qual ele se aplica. A representação dos limites é um conjunto de valores de um atributo, e opadrão é uma função (uma equação relacionando os atributos) ou uma tabela de contingência (relacionandocausa e efeito). O algoritmo de busca inicialmente concentra-se nas regularidades entre pares de atributos emsubconjuntos do banco de dados e permite a interação do usuário para aprofundar essa busca, refinando assim asregularidades descobertas.


6. REDES NEURAIS

Este capítulo define os principais conceitos sobre as Redes Neurais Artificiais e suasaplicações. Inicialmente, faz-se um levantamento da história das RNAs. Em seguida, sãoapresentados: uma descrição do funcionamento dos neurônios, as topologias de redes existentes e ostipos de treinamento utilizados. Por fim, destaca-se as RNAs multi-camadas e o algoritmo deretropropagação.

6.1. FUNDAMENTOS DAS REDES NEURAIS ARTIFICIAIS

6.1.1. Histórico

Os primeiros conceitos de máquinas baseadas no comportamento das células nervosas biológicassurgiram no início da década de 40 . Em 1943, Warren McCulloch e Walter Pitts apresentaram a primeiradiscussão sofisticada sobre "neuro-logical network" . Em 1947 eles publicaram o segundo estudo, entitulado"How we know universals" . A partir destas idéias, surgiu o movimento intelectual chamado "Cybernetics" , oqual tentou combinar conceitos de biologia, psicologia, engenharia e matemática. A década terminou com apublicação do livro de Donald Hebb "The Organization of Behavior".

Após a era "Cybernetics" ter aberto a perspectiva de se construir máquinas baseadas no conhecimento,surgiram, no início da década de 50, os primeiros protótipos neste campo, com arquiteturas específicas paradesempenhar tarefas determinadas. Contudo, tendo em vista o fato de que os animais podiam aprender a fazermuitas coisas para as quais eles não tinham sido "construídos" para fazer, passou-se a ter como meta aconstrução de máquinas que fossem capazes de aprender . Com isso, a década de 50 presenciou o surgimento demuitos sistemas que aprendiam baseados em reforço1 e em formas simples de aprendizado, sendo que o primeirodeles, provavelmente, foi feito por Minsky em 1951 . No final dos anos 50, o campo de pesquisa em redesneurais ficou virtualmente dormente, sem nenhuma descoberta de peso na área, enquanto que importantesavanços tinham sido alcançados em sistemas especialistas.

O interesse nas redes neurais ressurgiu, dramaticamente, em 1962 com a publicação do livro de FrankRosenblatt "Principles of Neurodynamics" . Neste livro Rosenblatt definiu máquinas denominadas de"perceptrons", e provou muitas teorias sobre as mesmas. Uma onda de entusiasmo dominou a área e muitospesquisadores passaram a crer que os "perceptrons" seriam a base para uma inteligência artificial. Contudo, estailusão foi logo desaparecendo, pois constatou-se que essas redes falhavam na solução de alguns problemassimples, similares a outros em que elas tinham sucesso. O rápido entusiasmo foi sepultado em 1969 com o livrode Marvin Minsky e Seymour Papert chamado "Perceptrons" , onde eles provaram que as redes neurais de umaúnica camada de Rosenblatt eram incapazes de resolver alguns problemas elementares como o do ou-exclusivo.O prestígio e o brilhantismo de Minsky deram grande credibilidade ao seu livro, levando à quase totalidade dacomunidade científica a abandonar as pesquisas na área por um longo período.

A década de 70 e o início da de 80 foram marcadas por um silêncio quase geral na área. Alguns poucospesquisadores como Grossberg, Kohonen, Anderson, Hopfield, Marr, von der Malsburg e Copper continuarampesquisando e desenvolveram trabalhos interessantes, principalmente nas áreas de memória associativaendereçável pelo conteúdo, sistema visual e reformulações do problema de aprendizado das redes . Em 1982,Hopfield deu uma importante contribuição com a introdução da função energia e pela enfatização da noção dememórias como atratores dinamicamente estáveis . Entretanto, talvez a maior influência desta época ainda tenhavindo dos "perceptrons" de Rosenblatt pois, baseados em suas teorias, vários pesquisadores foramdesenvolvendo algoritmos para o ajustes dos pesos das redes neurais multi-camada, culminando com osurgimento do algoritmo de "Backpropagation" (retropropagação). O "Backpropagation" parece ter sidoprimeiramente proposto por Werbos em 1974 e independentemente redescoberto por volta de 1985 porRumelhart, Hinton e Williams , tendo Parker e Le Cun também propostos algoritmos semelhantes.

Após a descoberta do "Backpropagation" o interesse na área voltou a crescer, desta vez de forma maismadura e consciente. Nos últimos anos, toda a teoria de redes neurais tem sido transformada em aplicações,sendo que novas corporações dedicadas à comercialização desta tecnologia têm aparecido. O crescimento nasatividades de pesquisa tem sido astronômico e novas áreas de atuação das redes neurais têm surgido, tais como:compressão de imagem e voz , reconhecimento de caracteres manuscritos , diagnósticos médicos , conservaçãode energia e previsões de séries temporais, em especial séries econômicas.

1 Reforço - Idéia de reforçar ações que tenham sido feitas no passado com sucesso. Conceito, ainda hoje, popular

em psicologia do comportamento.


6.1.2. O Neurônio Artificial

O cérebro humano é composto por mais ou menos 1011 neurônios de diversos tipos diferentes. A figura2.1 mostra o esquema de um neurônio comum.

Sinapses Dendritos

Axônio

CorpoSomático

Neurônio Biológico

Neurônio Artificial

w1

w2

w3

PesosPropagação Ativação

Figura 18: -Exemplo de um neurônio biológico comum

O núcleo da célula está localizado no corpo da mesma, sendo este último também chamado de soma.Conectados ao corpo da célula estão as fibras nervosas com estruturas similares a raízes, chamadas dendritos.Estendendo-se do corpo da célula existe uma única fibra nervosa mais grossa chamada axônio, da qual surgemramificações e sub-ramificações. No fim destas ramificações estão os pontos de transmissão para os outrosneurônios, chamados de junções sinápticas ou sinapses. Os pontos de recepção onde as sinapses vão se conectaraos outros neurônios podem ser os dendritos ou mesmo o corpo da célula. O axônio de um neurônio típicopossui algumas centenas de sinapses que irão se conectar com outros neurônios.

A transmissão do sinal de uma célula para outra é um complexo processo químico, no qual substânciasespecíficas são liberadas pelo neurônio transmissor. O efeito é um aumento ou uma queda no potencial elétricono corpo da célula receptora. Se este potencial alcançar o limite de ativação da célula, um pulso ou uma açãopotencial de potência e duração fixa é enviada através do axônio. Diz-se então que o neurônio está ativo.

O neurônio artificial foi projetado para imitar as características de primeira ordem de um neurôniobiológico. Essencialmente, um conjunto de entradas são aplicadas ao neurônio artificial, cada uma representandoa saída de outros neurônios (Figura 19). Cada entrada é multiplicada por um peso correspondente (Wij), gerandoentradas ponderadas, de forma análoga à força das sinapses. Em seguida todas estas entradas ponderadas sãosomadas, obtendo-se um valor NET que será comparado com o valor limite para ativação do neurônio (F). Casoeste valor alcance o valor limite de ativação do neurônio, ele se ativará, caso contrário ele ficará inativo. A figura2.2 mostra o modelo que implementa esta idéia.

Wi1

Wi2

Wi3

ΣΝΕΤ

FSAÍDA=F(NET)

NEURÔNIO ARTIFICIAL

Figura 19: Diagrama esquemático de um neurônio artificial


6.1.3. Funções de Ativação

A função de ativação F é a que processa o sinal NET para produzir a saída final do neurônio, SAÍDA.Esta função pode ter várias formas: uma simples função linear; uma função limiar (função degrau); ou ainda umafunção que simule mais precisamente as características não lineares do neurônio biológico. No caso de F seruma função linear, a saída do neurônio é dada por:

Equação 11

SAÍDA=K*(NET)

onde K é uma constante. Caso F seja uma função limiar, a saída seria:

Equação 12

SAÍDA=1 Se NET > T

SAÍDA=0 Caso contrário

onde T é o valor de limiar do neurônio artificial (constante). No caso de se querer imitar com maior precisão osneurônios biológicos, usa-se funções não lineares, chamadas funções "squashing". Elas caracterizam-se por nãodeixarem a SAÍDA exceder certos valores limites, os quais, em geral, são menores que os valores de NET. Afunção "squashing" mais usada é a função logística ou sigmóide (Figura 20 a), a qual é representadamatematicamente por F(x)=1/(1+e-x). Adequando-a ao neurônio artificial tem-se:

Equação 13

SAÍDA=1/(1+e-NET)

Pode-se pensar na função de ativação como definindo um ganho para o neurônio artificial, fazendo umaanalogia a sistemas eletrônicos analógicos. Este ganho é calculado encontrando-se a razão entre a variação dasaída SAÍDA e a variação da entrada NET. Este ganho é a inclinação da curva para um nível de excitaçãoespecífico, podendo variar desde um valor baixo para grandes excitações negativa, passando por valores altospara excitação zero, até voltar a cair quando a excitação se torna grande e positiva (Figura 20). Em 1973Grossberg descobriu que esta característica de ganho não linear resolvia o problema do dilema da saturação comruído. Neste dilema, Grossberg questionava como a mesma rede poderia manipular tanto sinais pequenos comograndes. Pequenos sinais necessitariam de um alto ganho através da rede para produzir saídas usáveis, exigindoum grande número de estágios de alto ganho. Contudo, estes estágios poderiam saturar a saída, amplificando oruído (variáveis randômicas) que está presente em qualquer rede criada. Para sinais de entrada com valores altos,os estágios de alto ganho também iriam saturar a saída, eliminando qualquer saída usável. A região central dealto ganho da função sigmóide resolve este problema do processamento de pequenos sinais, enquanto que suasregiões de ganho decrescente nos extremos negativo e positivo são adequadas a grandes excitações.

F(netj) F(netj)

netjnetj netj

DegrauDegrau Pseudo-LinearPseudo-Linear SigmoidSigmoid


Figura 20: (a) Função sigmóide típica; (b) Função tangente hiperbólica típica

Outra função de ativação "squashing" bastante usada é a tangente hiperbólica (Figura 20 b). Ela possuiuma forma similar a da sigmóide e é frequentemente usada por biólogos para o modelo matemático de ativaçãodas células nervosas. Como função de ativação dos neurônios artificiais a função tem a forma:

Equação 14

SAÍDA = tanh(NET)

Apesar da forma semelhante a da sigmóide, a tangente hiperbólica possui valores de SAÍDA bipolares,característica que é benéfica para certos tipos de RNAs .

É interessante ressaltar que este modelo simples de neurônio artificial ignora diversas características doneurônio natural, tais como a não consideração dos atrasos de tempo que afetam a dinâmica do sistema - asentradas produzem saídas imediatas - e a não inclusão dos efeitos de sincronismo ou de modulação de frequência- característica que alguns pesquisadores acham de fundamental importância. Apesar destas limitações, as RNAsformadas por simples neurônios artificiais possuem atributos semelhantes aos do sistema biológico, como acapacidade de aprendizado e generalização, podendo-se dizer que a essência do funcionamento do neurônionatural foi absorvida.

6.1.4. Topologia das Redes Neurais ArtificiaisAs várias topologias de redes neurais estão divididas, basicamente, em duas classes:

Não-RecorrentesRecorrentes

As RNAs não-recorrentes são aquelas que não possuem realimentação de suas saídas para suas entradas epor isso são também ditas "sem memória". A estrutura das RNAs ditas não-recorrentes é em camadas, podendoestas RNAs serem formadas por uma (RNA de camada única) ou mais camadas (RNA multi-camada). Redesneurais multi-camadas contêm um conjunto de neurônios de entrada, uma camada de saída e uma ou maiscamadas escondidas. A entrada não é considerada uma camada da rede, pelo fato de apenas distribuir os padrões, . A camada com os neurônios que fornecem a saída da rede é chamada camada de saída. As camadas que nãopossuem ligações diretas nem com a entrada, nem com a saída são chamadas de camadas escondidas. Nãoexistem conexões ligando um neurônio de uma camada a outro de uma camada prévia, nem a um neurônio damesma camada (Figura 21). As RNAs de uma camada, também chamadas de "perceptrons" , por possuírem umespectro de representações limitado, não serão tratadas neste trabalho. As RNAs multi-camadas, por suprirem asdeficiências das redes de uma única camada, são utilizadas neste trabalho e serão estudadas com mais detalhesna seção 2..2 e no capítulo 4.

SAÍDAENTRADAS

CAMADA

ESCONDIDA

CAMADA

DE SAÍDA

Figura 21: Exemplo de uma RNA não recorrente

As RNAs recorrentes são redes mais gerais que contêm realimentação das saídas para as entradas, sendosuas saídas determinadas pelas entradas atuais e pelas saídas anteriores. Além disso, suas estruturas não são


obrigatoriamente organizadas em camadas e quando são, estas redes podem possuir interligações entre neurôniosda mesma camada e entre camadas não consecutivas, gerando interconexões bem mais complexas que as RNAsnão-recorrentes (Figura 22)

ENTRADASSAÍDAS

Figura 22: Exemplo de uma RNA recorrente

As RNAs recorrentes, também chamadas de RNAs com memória por possuírem realimentação, respondema estímulos dinamicamente, isto é, após aplicar uma nova entrada, a saída é calculada e então realimentada paramodificar a entrada. Para as redes estáveis, este processo é repetido várias vezes, produzindo pequenas mudançasnas saídas, até estas ficarem constantes. Todavia, as RNAs recorrentes nem sempre são estáveis, mesmo comentradas constantes. O fato de não se conseguir prever quais redes seriam estáveis foi um problema quepreocupou os pesquisadores até o início da década de 80, quando Cohen e Grossberg provaram um poderosoteorema para definir quando as RNAs eram estáveis . Este teorema determina que para as RNAs recorrentesalcançarem um estado estável é necessário que possuam conexões simétricas, melhor dizendo, Wij=Wji, sendoWii=0. Contribuições importantes também foram dadas por John Hopfield , tanto para a teoria como para aprática, sendo que algumas configurações passaram a ser chamadas de redes de Hopfield em sua homenagem.Hinton e Sejnowski também tiveram seus méritos, introduzindo regras gerais de treinamento para redes,denominadas por eles de máquina de Boltzmann devido ao cálculo das saídas dos neurônios artificiais serefetuado através de probabilidade com distribuição de Boltzmann.

6.1.5. Tipos de Treinamento

De todas as propriedades interessantes das redes neurais artificiais, nenhuma captura tão bem acaracterística humana como a habilidade de aprender. Ao invés de especificar todos os detalhes de umacomputação tem-se a possibilidade de treinar uma rede para fazer esta computação. Isto significa que pode-setratar problemas onde regras apropriadas são muito difíceis de se conhecer a priori.

O objetivo do treinamento de uma RNA é fazer com que a aplicação de um conjunto de entradas produzaum conjunto de saídas desejado ou no mínimo um conjunto de saídas consistentes. Cada conjunto de entrada ousaída é chamado de vetor. O treinamento é realizado pela aplicação sequencial dos vetores de entradas (e emalguns casos também os de saída), enquanto os pesos da rede são ajustados de acordo com um procedimento detreinamento pré-determinado. Durante o treinamento, os pesos da rede gradualmente convergem paradeterminados valores, tal que a aplicação dos vetores de entrada produza as saídas necessárias.

Os procedimentos de treinamento que levam as RNAs a aprender determinadas tarefas podem serclassificados em duas classes de treinamento:

SupervisionadoNão Supervisionado

O treinamento supervisionado necessita de um par de vetores composto do vetor de entrada e do vetoralvo que se deseja como saída. Juntos, estes vetores são chamados de par de treinamento ou vetor detreinamento, sendo interessante ressaltar que geralmente a rede é treinada com vários vetores de treinamento.

O procedimento de treinamento funciona da seguinte forma: o vetor de entrada é aplicado. A saída darede é calculada e comparada com o correspondente vetor alvo. O erro encontrado é então realimentado atravésda rede e os pesos são atualizados de acordo com um algoritmo determinado a fim de minimizar este erro. Esteprocesso de treinamento é repetido até que o erro para os vetores de treinamento tenha alcançado níveis bembaixos.


O treinamento não supervisionado, por sua vez, não requer vetor alvo para as saídas e, obviamente, nãofaz comparações para determinar a resposta ideal. O conjunto de treinamento modifica os pesos da rede de formaa produzir saídas que sejam consistentes, isto é, tanto a apresentação de um dos vetores de treinamento, como aapresentação de um vetor que é suficientemente similar, irão produzir o mesmo padrão nas saídas. O processo detreinamento extrai as propriedades estatísticas do conjunto de treinamento e agrupa os vetores similares emclasses. A aplicação de um vetor de uma determinada classe à entrada da rede irá produzir um vetor de saídaespecífico, mas não existe maneira de se determinar, antes do treinamento, qual o padrão que será produzido nasaída para um vetor de entrada de uma determinada classe. Desta forma, a saída de algumas RNAs deve sertransformada em uma forma compreensiva após o processo de treinamento, o que é um simples problema deidentificação da relações entrada-saída estabelecidas pela rede.

No que diz respeito aos algoritmos de treinamento usados, existe uma grande variedade, tanto para otreinamento supervisionado, como para o não supervisionado. Muitos deles baseiam-se no algoritmo propostopor D. O. Hebb em 1961 entretanto, os algoritmos mais eficientes foram desenvolvidos nos últimos trinta anos,baseados nos trabalhos de Rosenblatt (1962), Windrow (1959) e Windrow e Hoff (1960) . Entre estes, o maisdifundido com certeza foi o algoritmo de retropropagação ("Backpropagation"), o qual é utilizado nestetrabalho. Sua descrição detalhada é apresentada na seção 2.2.

6.2. REDES NEURAIS ARTIFICIAIS MULTI-CAMADAS

A capacidade limitada de representação das RNAs com uma única camada foi superada na década de 60, apartir do perfeito entendimento do problema da separabilidade linear . Contudo, apesar de se ter descobertocomo aumentar a capacidade de representação da rede com o acréscimo de novas camadas, faltava ainda umaforma de treinar a rede. Esta forma só foi descoberta em meados da década de 70, com a criação de váriosalgoritmos, entre eles o de retropropagação ("Backpropagation"). O "Backpropagation" se tornou um dosalgoritmos mais populares para o treinamento, sendo em parte responsável pelo ressurgimento do interesse naárea de Redes Neurais Artificiais.

6.2.1. - Algoritmo de Retropropagação do Erro

A técnica de Back-Propagation vem sendo utilizada com sucesso em diversas aplicações de redes neuraisartificiais. O Algoritmo baseia-se no método do gradiente descendente para a minimização do erro entre a saídada rede e a saída desejada. O reajuste ∆Wij de cada peso Wij é fornecido pela seguinte equação:

Equação 15

∆W E Wij ij= − ×η ∂ ∂( / )

onde E é o somatório dos erros quadráticos da rede, o parâmetro η é a taxa de aprendizado (esta taxainfluencia a velocidade do aprendizado da rede neural) e Wij é o peso associado à conexão entre um elementoprocessador i de determinada camada ao processador j da camada imediatamente posterior (Figura 23).

Wij

Neurônio i

Neurônio j

Figura 23: Peso sináptico associado aos processadores i e j

A expressão para E é:

∑=

−=n

1j

2jj )s(t

21

E

onde outj é a saída do processador j, tj é o valor esperado desta saída e n é o número de neurônios nacamada j.

Como a saída de cada neurônio é uma função do Net, tem-se:

∑== )wsF(F(Net)s ijij


onde n é o número de entradas do neurônio j.Como

ij

j

jij W

net*

netE

WE

∂∂

∂∂=

∂∂

e

iij

sWnet =

∂∂

e definindo-se

jj net

Ed

∂∂−=

pode-se reescrever a Equação 15 como:

Equação 16

jiij d*s*??W =

onde si é a saída no neurônio i da camada anterior.Para os elementos da camada de saída tem-se:

Equação 17

)(netF)s(td jjjj ′−=

e, para os elementos da camada escondida:

Equação 18

)(netFWdd j

n

1kikkj ′

= ∑

=

Na Equação 17 e na Equação 18, o termo F’(netj) é a derivada da função de ativação e tj é o valoresperado de saída para o processador j.

Conforme foi mencionado, a taxa de aprendizado η determina a velocidade do treinamento. Embora umvalor alto possa acelerar consideravelmente o treinamento, o mesmo também pode acarretar oscilações. Paraevitar esse tipo de evento, pode ser utilizado o termo de momento α. A Equação 16 torna-se:

Equação 19

(k)a?Ws?ddW ijijij +=

Neste caso, a atualização dos pesos no instante atual (k + 1) é calculada utilizando-se a atualização feitano instante anterior (k). A aplicação do momento tende a filtrar as oscilações do treinamento da rede, pois tendea atenuar os efeitos de mudanças no sentido oposto e a reforçar mudanças no sentido corrente.

Seu treinamento, apesar de lento, permite uma boa generalização. Entretanto deve ser mencionado que aescolha da arquitetura da rede (normalmente feita pelo projetista do sistema) tem uma grande importância no seudesempenho final.

A Figura 24 mostra uma rede multicamada apropriada para o treinamento com o algoritmo deretropropagação.


SAÍDAENTRADAS

..

....

Figura 24: RNA multi-camada

Como dito anteriormente, o objetivo do treinamento da rede é ajustar os pesos, tal que a aplicação de umconjunto de entradas produza um conjunto de saídas desejadas. Antes de iniciar o processo de treinamento, todosos pesos devem ser inicializados randomicamente com valores pequenos, garantindo desta forma que a rede nãoficará saturada com grandes valores de pesos e prevenindo-se contra certas patologias de treinamento.

O treinamento pode ser dividido em passos da seguinte forma:1-Selecionar o próximo par do conjunto de treinamento e aplicar o vetor de entrada a rede.2-Calcular a saída da rede.3-Calcular o erro entre a saída da rede e a saída alvo.4-Ajustar os pesos da rede de maneira a minimizar o erro.5-Repetir o passo 1 até o passo 4 para cada vetor do conjunto de treinamento, até o erro se

tornar aceitavelmente baixo para o conjunto inteiro.

Pode-se observar que os passos 1 e 2 constituem a etapa de propagação para frente, onde o sinal deentrada é transmitido através da rede da entrada até a saída. Os passos 3 e 4, por sua vez, constituem-se na etapade retropropagação, onde o erro calculado é propagado de volta através da rede para ajustar os pesos.

Apesar do grande sucesso das aplicações do algoritmo de retropropagação e da sua enorme popularidade,muitos problemas ainda o acompanham. Entre eles, o que mais se destacam são:

wO longo período de treinamento, principalmente para problemas complexos, sendo quenão há garantias que depois deste tempo o treinamento tenha sido feito com sucesso;

wMínimos locais, já que a superfície do erro geralmente é cheia de vales e desníveis e oalgoritmo emprega um tipo de gradiente descendente, existe sempre a possibilidade de ficarpreso em um mínimo local;

wParalisia da rede, pois durante o treinamento os pesos podem ser ajustados para valoresmuito grandes, os quais vão levar a derivada da função de ativação a zero (no caso de funções "squashing"), impedindo a rede de aprender o conjunto de treinamento.

Devido às deficiências do algoritmo de retropropagação, inúmeras variações têm sido propostas nosúltimos anos , , . Uma alternativa para diminuir o tempo de treinamento, assegurando um maior grau deestabilidade para rede, chamada "momentum", foi proposta por Rumelhart, Hinton e Williams em 1986 e semostrou bastante eficiente em alguns casos. Outras alternativas também foram propostas por Parker em 1987,bem como por Stornetta e Huberman, Todavia, até agora, nenhuma tem solucionado de forma definitiva econfiável os problemas do "Backpropagation".

6.3. MODELAGEM DE REDES NEURAIS PARA DATA MINING

6.3.1. Seleção de Dados

Uma vez selecionado o banco de dados para treinar a rede neural, o próximo passo é decidir que dado éimportante para a tarefa que se deseja automatizar. Talvez o bando de dados tenha 100 atributos, mas apenas 10são utilizados para tomar decisões. Esse é o problema, na maioria dos casos, não sabe-se exatamente queparâmetros são importantes no processo de decisão. Redes neurais podem ser utilizadas para ajudar a determinarquais parâmetros são importantes e contruir o modelo relativo a esses parâmetros.


O processo de seleção de dados possui duas direções (dimensões). A primeira, são as colunas ouparâmetros, os quais serão parte do processo de data mining. A segunda, é a seleção de linhas ou registros,baseado nos valores dos atributos individuais. O mecanismo usado para acessar todos os bancos de dadosrelacionais é o SQL. Entretanto, muitas ferramentas “front-end” permitem que usuários especifiquem que dadosacessarão usando formulários “fill-in-the-blanks”.

Os passos para seleção de dados requerem algum conhecimento do domínio do problema e do dado.Frequentemente o dado é armazenado num banco de dados para ser manipulado antes que o data mining seinicie. Esse pré-processamento é descrito na próxima seção.

6.3.2. Pré-processamento

Pré-processamento dos dados é o passo executado quando tem-se uma base de dados limpa e deseja-semelhorá-la. Algumas vezes esse melhoramento envolve gerar novos dados a partir de um ou mais atributos, ealgumas vezes isso significa trocar vários atributos por apenas um que contenha mais informação. O número deatributos de entrada não é necessariamente uma medida da informação fornecida para o algoritmo de datamining. Alguns dados podem ser redundantes; ou seja, alguns dos atributos são maneiras diferentes de se medir omesmo efeito. Algumas vezes os dados precisam ser transformados para uma forma que é aceitável comoentrada para um algoritmo específico de data mining, tal como a rede neural.

Atributos derivados

Um requisito em data mining é combinar 2 ou mais campos para gerar um novo campo ou atributo. Isto égeralmente criado na forma da razão de 2 valores, mas tambem pode ser soma, produto, ou diferença de valores.Outras transformações podem ser do tipo que transforma data em dia da semana ou dia do ano.

Escalamento

Uma outra transformação envolve um propósito mais geral de transformar os dados para seremapresentados à rede neural. A maioria dos modelos neurais aceitam dados numéricos apenas no intervalo de [0.0à 1.0] ou de [-1.0 à +1.0], dependendo das funções de ativação utilizadas no processamento dos elementos.Consequentemente, os dados precisam ser reduzidos para um intervalo.

Valores escalares que são distribuídos mais ou menos uniforme sobre o intervalo podem ser escaladosdiretamente para o intervalo [0.0 à 1.0]. Se os valores dos dados são descorrelacionados, uma função linear oulogaritma pode ser utilizada para transformar os dados, os quais podem ser escalados para o intervalo desejado.Variáveis discretas podem ser representadas por tipos codificados com valores 0 ou 1, ou elas podem serassociadas a valores em um intervalo contínuo desejado.

Normalização

Vetores de dados numéricos podem algumas vezes ser tratados como um grupo de números. Nessescasos, é necessário normalizar ou escalar os vetores como um grupo. Existem vários métodos para se fazer isso.Talvez o mais comum dos métodos de normalização é somar os quadrados de cada elemento, tirar a raizquadrada da soma, e então dividir cada elemento pela norma. Este é chamado de Normalização Euclidiana. Umsegundo método de normalização de um vetor de dados é simplesmente somar todos os elementos do vetor eentão dividir cada número pela soma. Deste modo, a soma dos elementos normalizados vale 1.0, e cada elementotem um valor que representa percentualmente a sua contribuição nessa soma. Um terceiro método paranormalizar um vetor é dividir cada elemento pelo valor do elemento de máximo valor no array. Esse tipo denormalização é utilizada desde quando se deseja minimizar o custo de processamento.

Mapeamento simbólico e taxonomias

Em muitos casos é necessário executar transformações de símbolos em outros símbolos antes detransformá-los em valores numéricos. Um uso comum seria agregar membros de algumas classes ou grupos numúnico símbolo para a proposta de representação do dado. Por exemplo, uma loja pode vender 100 variedade desucos, todos com uma única medida e identificadores alfanuméricos. Se nos queremos um modelo que comprede várias classes de bebidas, nós precisamos tratar todos esses produtos como apenas um.

Este tipo de mapeamento pode ser utilizado para verificar as categorias em vários níveis de granularidade.Por exemplo, nível de categoria com todos os condimentos, com subcategorias mostarda, catchup, cebolas,


picles; catchup com subcategoria picante e não picante. Ou seja, analisa-se em forma de uma árvore comhierarquias, ou uma taxonomia que verifica os problemas em vários níveis de abstração.

Translações de simbólicos para numéricos

Translações de simbólicos para numéricos são frequentemente requisitos para transformar símbolosdiscretos ou categorias em valores numéricos para o processamento dos algoritmos de data mining. A formamais básica de se fazer isso é procurar numa tabela, onde o símbolo é comparado contra uma lista de símbolos equando ele é encontrado, o correspondente valor numérico é utilizado. Cuidados devem ser tomados paraassegurar que símbolos indefinidos ou ilegais sejam associados a algum valor desconhecido ou irrelevante. Umaa outra aproximação mais sofisticada é utilizar uma função “hashing”, no qual um algoritmo pega uma string etransforma num único valor numérico.

6.3.3. Representação dos dados

Apesar de existirem muitos tipos de dados suportados no sistema de banco de dados relacional, a maioriapode ser facilmente mapeado em três tipos lógicos. Estes tipos incluem valores numéricos contínuos, valoresnuméricos discretos, e categóricos ou valores discretos simbólicos. Tempo e datas apresentam certos desafios,mas eles também podem ser mapeados em valores numéricos utilizando-se funções apropriadas.

Por exemplo: O símbolo “maçã” pode ser mapeado em um inteiro específico utilizando-se uma tabela desímbolos, ou pode-se utilizar uma função hash que transforma a string em um único inteiro. Isto gera um valornumérico discreto (inteiro). Este valor pode ser apresentado a uma rede neural de várias maneiras. Entretanto,deseja-se geralmente que esse número seja codificado ou transformado para um intervalo apropriado. O símbolomaçã pode ser mapeado para o valor “5”. Pode ser transformado para 0.5 se desejarmos uma entrada realcontínua ou pode ser convertida para qualquer um dos três códigos (1 0 0 0 0; 1 1 1 1 1; 0 0 1 0 1). Na seçãoseguinte é descrita a conversão lógica básica desses tipos.

Representação Numérica dos dados

Dados numéricos podem ser simplesmente valores binários (0 ou 1) indicando os estados “ativado” e“desativado”, ou pode ser um intervalo de valores discretos (1 a 10) ou um intervalo contínuo de -1000 a +1000.Em cada caso deve-se decidir como representar cada dado. A maioria das redes neurais aceitam entradas nointervalo de 0 a 1, ou de -1 a +1. Nesse caso, parâmetros binários podem ser representados pelos extremos dointervalo de entrada.

Valores Discretos

Variáveis discretas são aquelas que se associam a apenas um conjunto fixo de valores. Estas, tipicamentedenotam um conjunto pequeno de classes, ou um conjunto de respostas a questões de múltiplas escolhas (porexemplo. A a E), ou um intervalo fixo de números inteiros. O desafio para uma rede neural representar valoresdiscretos é apresentar esses valores de modo que a rede seja capaz de discernir as diferenças entre valores e quepossam dizer a magnitude relativa das diferenças se a informação estiver disponível. Vários tipos codificados sãoutilizados para representar esses valores. Nas seguintes seções são apresentados os códigos utilizados maiscomuns.

Código 1-de-N

Quando uma variável pode tomar um conjunto de valores discretos, ela deve ser transformada numarepresentação que apresenta em um único conjunto de entrada, cada valor discreto distinto. Talvez arepresentação mais comum seja a 1-de-N. O código 1-de-N tem um comprimento igual ao número de categoriasdiscretas permitidas para a variável, onde todo elemento no vetor de código é 0, exceto para um único elemento,que representa o valor do código. Por exemplo, se temos um conjunto com 4 elementos {maçã, pêssego, uva,abacaxi}, pode-se representar maçã como 1 0 0 0, pêssego como 0 1 0 0, uva como 0 0 1 0, e abacaxi como 0 0 01. O lado positivo dessa representação é que ela é simples, fácil de usar, e a rede neural pode facilmente aprendera discriminar entre os vários valores. Usando essa representação, uma única variável pode expandir de 100 ou1000 entradas, ocorrendo uma explosão no número dos pesos de entrada.

Código binário


Uma representação alternativa é o código binário padrão. Nele, cada categoria discreta a um valor de 1 atéN e é representado por uma string de dígitos binários. Ou seja, se temos 64 possíveis valores, podemosrepresentá-los com um vetor binário de comprimento 6. Como os valores discretos não são arbitrários e não sãoordenados, o código binário é um bom modo de representar os dados. Entretanto, note que existem grandesdiferenças nos valores dos bits como números discretos convertidos para código binário. O sétimo item tem ocódigo 0 0 0 1 1 1, enquanto o oitavo tem 0 0 1 0 0 0. A distância de hamming é uma medida de similaridade oudiferença entre duas strings binárias. Neste caso, indo de 7 para 8 resulta numa distancia de hamming de 4. Sedesejamos que a rede neural trate os padrões de entrada com um 7 ou 8 como sendo “similares”, então devemosescolher o termômetro ou código de temperatura.

Código de temperatura

Código de temperatura é utilizado mais frequentemente quando os valores discretos estão relacionados dealgum modo. Por exemplo, uma variável discreta que pode ter um dos seguintes valores {fraco, regular, bom,ótimo}. Nesse caso, desejamos que a diferença entre fraco e ótimo seja grande (na distância de hamming) e adiferença entre bom e ótimo seja menor. Isto é exatamente o que acontece com o código termômetro desde quefraco é representado como 1 0 0 0, enquanto ótimo é representado como 1 1 1 1 (distância de hamming 4),enquanto bom é representado como 1 1 1 0 (de bom para ótimo a distância de hamming é de apenas 1).

Existem outros esquemas de códigos que trabalham com variáveis discretas, mas, em geral, o 1-de-N,binário e termômetro são os mais utilizados.

Valores contínuos

Para valores contínuos, a forma mais comum de transformar dados é fazendo um scaling. Por exemplo,uma variável que pode tomar valores de 0 a 100 pode ser linearmente transformada de 0.0 a 1.0. Portanto, 20tornaria 0.2, enquanto 80 se transformaria em 0.8. Para variável com distribuição como essa, a transformaçãolinear funciona bem.

Mas se o dado não se comporta dessa maneira? Por exemplo, suponha 80% dos dados estão abaixo de 50e precisamos ensinar a rede neural a fazer boas distinções entre valores no intervalo de 0 a 50. Uma opção étransformar o dado utilizando uma aproximação linear para que o dado no intervalo de 0 a 50 seja expandido narepresentação. Enquanto os menos importantes, intervalo de 50 a 100, sejam comprimidos. Isso pode ser feitotomando-se o intervalo 0, 50, 100 e transformando-o em 0.0, 0.8 e 1.0. Neste caso, o valor de entrada 50 ficaassociado ao valor 0.8, enquanto o valor 75 é associado a 0.9. Uma diferença de 25 (75 - 50) no valor de entradatransformasse em 0.1 (0.9 - 0.8) como entrada na rede neural. Entretanto, uma entrada de 10 teria o valor de0.16, enquanto 25 seria 0.4. Aqui a rede neural vê uma diferença maior no valor de entrada e portanto pode maisfacilmente discriminar entre as diferenças nos valores de entrada. Isso pode ou não pode ser importante. Mas éimportante lembrar que se uma diferença pequena na entrada é realmente significante, digamos mudar de 31 para33 graus, então queremos Ter certeza que a nossa representação mostra essa significância para a rede neural.

Uma outra necessidade comum é um threshold nos dados para que os valores fora do intervalo deinteresse não necessariamente diluam a nossa representação. Por exemplo, suponha que temos um intervalo de 0a 300000 reais. Mas estamos apenas checando se uma pessoa tem 35000 ou mais. Nós simplesmente inserimosum threshold para que os valores entre 0 e 35000 sejam transformados para o intervalo de 0.0 a 1.0, enquantovalores acima de 35000 obtêm um threshold de 35000, portanto transformando-se em 1. Não é necessário fazercom que a rede neural tente aprender coisas que ela realmente não precisa, é esforço perdido.

Representações de Dados Simbólicos

Nós encontramos dados simbólicos com frequência em aplicações de redes neurais. O mais comum, emais fácil de trabalhar, são as variáveis booleanas tais como sim e não e masculino e feminino. Entretanto, nósdevemos adicionar uma terceira condição (mesmo para variáveis booleanas), a condição “desconhecida”. Nessecaso podemos utilizar a codificação 1-de-N de comprimento 3 (sim, não, desconhecido) ou um código binário decomprimento 2 (sim, não, desconhecido, <não usado>). Ou nós podemos decidir representar não como 0, simcomo 1 e desconhecido como 0.5. Todas as representações são válidas. Ela depende do que é requerida pelaaplicação. O conflito está entre o tamanho da rede (número de entradas) versus a facilidade de treinamento(tempo reduzido de treinamento).

Para representação de dados simbólicos não relacionados a valores discretos, nós simplesmentemapeamos o símbolo num inteiro de 1 a N. Por exemplo, {maçãs, pêssegos, uva, abacaxi} pode ser mapeadopara 1, 2, 3 e 4. Certamente, podíamos provavelmente transformá-los de 0 a 1, e então teríamos 0, 0.33, 0.66,1.0. Em essência nós temos as mesmas opções de representação discutidas anteriormente no caso numérico


discreto. Dependendo da aplicação, podemos ou não tratar símbolos escritos diferentemente (maçã versus Maçã),por exemplo, como diferentes símbolos.

Para representação simbólica de valores relacionados, tais como {regular, bom, ótimo} devemos tercuidado para mapeá-los como inteiros consecutivos e usar uma representação de dados que preserve estaordenação, tais como termômetro e transformação linear.

Para dados simbólicos de natureza contínua, isto é mais complexo. Por exemplo, se desejamos sersensíveis a diferença de um simples caracter em uma string e notar que ela é similar a outra string, omapeamento de valores numéricos torna-se mais difícil.

Impacto da Representação dos Dados no Tempo de Treinamento

A representação dos dados é importante. Se as decisões sobre a representação dos dados é feitaerroneamente, pode tornar-se impossível que a rede neural aprenda o relacionamento que estamos tentandoensinar. Entretanto, geralmente existe um conjunto de possíveis representação de dados que são suficientes paratreinar a rede. Em todos os casos, é importante entender como as decisões na representação do dado vai afetartanto o treinamento como a acurácia obtida.

Em geral, quanto mais explícita a representação do dado, mais fácil será para a rede neural aprender. Porexemplo, tomando uma variável discreta e uma codificação 1-de-N teremos tipicamente um treinamento maisrápido. Entretanto, o custo é que estamos adicionando N unidades de entrada e um fator N de pesos adicionais arede. De novo, em geral, quanto maior a rede em termos de unidades de processamento e conexões dos pesos,pior será a generalização e mais tempo durará o treinamento. Tomando a mesma variável discreta e associando-aa uma única unidade de entrada, onde cada valor discreto é representado por uma diferença de 0.1 na magnitudede entrada, é certamente a representação mais compacta. Entretanto, a rede neural demorará muito para ajustar osseus pesos de uma simples unidade de entrada, dado que é preciso reconhecer que um décimo de diferença ésignificante e indica completamente um único valor para a variável de entrada.

6.3.4. Gerenciando Conjunto de Treinamento de Dados

Um importante aspecto de utilizar redes neurais para data mining e desenvolvimento de aplicações écomo gerenciar seu material, os dados históricos. A aproximação mais comum é randomicamente dividir osdados em dois ou mais conjuntos de dados. Um subconjunto dos dados é utilizado para treinar a rede neural, e ooutro subconjunto é utilizado para testar a acurácia da rede neural. É importante acreditar que a rede neuralnunca vê o conjunto de teste quando ela esta no modo de treinamento. Ou seja, ela nunca aprende, ou ajusta ospesos utilizando os dados de teste. Algumas pessoas sugerem um terceiro conjunto seja gerado that is withheledeven from the developer of the neural network model (not that anyone would cheat!). Nesse terceiro cenário,usa-se dados de treinamento e teste para construir o modelo e então de modo independente testa-se o modelocom os dados de validação.

Existem alguns casos e, que esse método não é apropriado. Um é quando o dado é temporal. Esse dadodeve ser utilizado de forma contínua de modo a manter a informação que ele contém. Uma seleção aleatóriadesses dados pode ser catastrófica. Nesse caso, é típico utilizar os dados de um certo período de tempo paratreinamento e os dados mais recentes para a fase de teste e/ou validação.

Um outro caso é quando não existem dados suficientes para permitir a criação de um conjunto aleatóriorazoável que possa representar bem todos os dados disponíveis. Nesse caso, técnicas estatísticas devem serrequisitadas que ambos os conjuntos de treinamento e teste contenham dados representativos do universodisponível.

6.3.5. Quantidade de Dados

Desde que dados são os ingredientes mais importantes em dada mining, assegurar que temos suficiente écrucial. Na maioria das aplicações, a quantidade de dados é como um prêmio, e muitas técnicas devem serutilizadas para extrair o máximo de utilidade deles.

Uma regra para redes neurais é que você precisa de dois itens de dados para cada conexão. Portanto umaback propagation com 10 entradas, 5 unidades escondidas, e 5 saídas deve ter aproximadamente “2 * (10 * 5) *(5 * 5) = 150” exemplos de treinamento para ser capaz de treinar com certa precisão. Na prática, muitas redesneurais tiveram sucesso sem o número de dados sugeridos.

Quando utilizando dados reais para treinar a rede neural, é típico ter 98% dos dados representando bonsclientes ou condições normais, e em apenas uma pequena porcentagem de exemplos para os casos que realmente


desejamos detectar (isto é mau cliente ou condição operacional anormal). Uma técnica para aumentar aporcentagem é simplesmente duplicar os exemplos do conjunto de treinamento que contém a classe do padrão detreinamento reduzida. Uma outra técnica é pegar um número pequeno de casos do conjunto de teste e modificá-los adicionando um pequeno ruído nos valores de entrada e então usando esse ruído de entrada como exemplosadicionais de treinamento. Uma outra opção é criar um conjunto de treinamento na mão.

6.3.6. Qualidade dos dados (Entra Lixo, Sai Lixo)

Em adição ao gerenciamento dos dados, o maior concern em redes neurais para data mining é a qualidadedos dados. A maioria dos banco de dados contêm dados incompletos e sem confiança. Dependendo daquantidade de dados disponível, você deve ser capaz de ignorar qualquer registro obviamente duvidoso.Entretanto, em muitos casos você tem uma quantidade de dados limitada, e portanto você tem de tentar melhoraresse dado. A técnica mais comum é preencher os campo duvidosos com a média ou a mediana casos essescampos sejam numéricos ou uma variável discreta.

Como na maioria das análises estatísticas, outliers are a concern. Um simples registro com o valor umaordem um ou dois valores de magnitude maiores ou menores que o resto dos dados podem severamente impactarno desempenho da rede neural. Uma análise gráfica ou um pesquisa pode indicar esse tipo de problema.

Uma rede neural para data mining é altamente dependente da qualidade e da quantidade de dados. Sesempre existisse um sistema onde ELSL fosse a regra (Entra Lixo, Sai Lixo), a rede neural é ele. Eles sãoaltamente esquecidos de ruído e dados incompletos, mas eles são apenas tão bons quanto os dados que foramutilizados para treinar.

7. NEURO FUZZY

7.1. MOTIVAÇÃO

Desde os mais remotos tempos, o ser humano vive envolvido com o problema de lidar com o ambienteque o cerca. A ciência tem evoluído na busca de entender e predizer o comportamento do universo e dossistemas que o compõe. Muito desta arte baseia-se em encontrar modelos adequados que conciliem asobservações feitas sobre os sistemas com os resultados obtidos pelos modelos definidos. Neste aspecto, amodelagem de sistemas tem sido, uma questão importante, seja na área de engenharia ou fora dela.

A abordagem convencional para a modelagem de sistemas apóia-se fortemente em ferramentasmatemáticas que enfatizam a precisão e a descrição exata de cada quantidade envolvida. O uso de ferramentasmatemáticas (equações diferenciais, equações de diferença, funções de transferência, etc.) é apropriado quando osistema é simples ou bem definido. Contudo, à medida que o sistema em foco cresce e torna-se complexo, asferramentas matemáticas tornam-se menos efetivas e, em alguns casos, impróprias. Isto ocorre devido ao fato dasexpressões matemáticas se tornarem muito complicadas para serem tratadas, ou as relações entre as variáveis dosistema tornarem-se pouco claras ou apenas conhecidas com incerteza (imprecisão).

Para contornar os problemas encontrados pelos métodos convencionais de modelagem, propostasalternativas surgiram nas últimas décadas, tais como a modelagem por Lógica Fuzzy (LF) e a modelagem porredes neurais artificiais (RNA). Essas duas técnicas de modelagem têm sido empregadas com sucesso em váriasáreas onde a abordagem convencional tem falhado em fornecer soluções satisfatórias. Essas duas abordagensfazem parte do conjunto de técnicas estudadas na área de Inteligência Computacional, juntamente com osAlgoritmos Genéticos e Sistemas Especialistas.

As RNAs e a LF apresentam características comuns, como operação em paralelo e capacidade detolerância a falhas, embora suas origens sejam bem distintas. A modelagem por lógica fuzzy é baseada na teoriade conjuntos fuzzy e em regras fuzzy (do tipo se-então), propostas por Zadeh e Mamdani, e está intimamenterelacionada à lingüística e à ciência da cognição. Por outro lado, as redes neurais artificiais têm por inspiração osistema de neurônios biológicos. Por causa de suas origens distintas, suas abordagens na solução de problemasde modelagem são em geral complementares. Por exemplo, enquanto as redes neurais são apropriadas para acriação de modelos a partir de um conhecimento implícito (e não óbvio) embutido em um conjunto de dados, ossistemas fuzzy são adequados para a criação de modelos a partir de um conhecimento explícito (racional elingüisticamente tratável), originário de especialistas humanos. Como conseqüência, muitos pesquisadores têmtentado integrar essas duas técnicas de modelagem para gerar um modelo híbrido que possa associar as


vantagens de cada abordagem e minimizar suas deficiências. Com isto, nasceram os sistemas neurofuzzyhíbridos ou, simplesmente, sistemas neurofuzzy (SNF).

Dentre os pesquisadores desta nova área, podemos destacar Jang (um dos pioneiros), Nauck e Vuorimaa,que criaram respectivamente os modelos ANFIS, NEFCLASS e FSOM. Todos esses modelos são sistemasadaptativos, como as redes neurais, e são interpretáveis através de regras da lógicas fuzzy. Um sistemaadaptativo Aw é um sistema com parâmetros internos ajustáveis W, que realiza um mapeamento entre o espaçode entrada X e o espaço de saída Y=Aw (X). Um sistema adaptativo é caracterizado por sua estrutura, seuconjunto de parâmetros, e envolve algum paradigma de representação. Os modelos adaptativos são assimchamados por possuírem um algoritmo de aprendizado capaz de ajustar os seus parâmetros e/ou sua estrutura apartir dos dados. Entre os vários tipos de sistemas adaptativos, os mais interessantes são aqueles capazes de tersua estrutura alterável, isto é, cujo algoritmo de aprendizado é baseado na mudança (crescimento ou decréscimo)de sua estrutura, além do ajuste de seus parâmetros.

Os modelos neurofuzzy existentes, dentre eles os três citados anteriormente, ajustam apenas osparâmetros ou têm uma capacidade muito limitada de ajuste em sua estrutura. Além disso, de modo a evitar oproblema da explosão do número de regras, esses modelos têm sérias restrições quanto ao número máximo deentradas possíveis no sistema. Existe, portanto a necessidade de se criar um SNF que seja capaz de suprir essasdeficiências.

7.2. SISTEMAS HÍBRIDOS

7.2.1. Introdução

Há várias formas de se definir sistemas híbridos. De uma forma simples, sistemas híbridos são aquelesque utilizam mais de uma técnica de identificação de sistemas para a solução de um problema de modelagem.Este capítulo apresenta os sistemas híbridos mais estudados atualmente, dando destaque especial para ossistemas neurofuzzy.

Os modelos híbridos têm vantagens interessantes sobre as técnicas de identificação de sistemasindividuais (por ex., redes neurais, sistemas fuzzy, algoritmos genéticos, técnicas de regressão, sistemasespecialistas, técnicas de agrupamento (“clustering”), etc). O grande interesse que tais sistemas têm despertadona comunidade científica deve-se ao sinergismo obtido pela combinação de duas ou mais técnicas demodelagem. Este sinergismo reflete-se na obtenção de um sistema mais poderoso (em termos de poder deinterpretação, de aprendizado, de estimativa de parâmetros, de generalização, etc) e com menos deficiências.

Existem três formas básicas de se associarem duas técnicas de identificação de sistemas para a construçãode sistemas híbridos.

a) Híbrido Seqüencial - Neste modelo, um subsistema com paradigma 1 atua como a entrada de outrosubsistema com paradigma 2, como ilustrado na Figura 25 a seguir.

Subsistema 1(paradigma 1)


Entrada Saída

Figura 25: Modelo Híbrido Seqüencial


Um exemplo dessa combinação seria o caso de se usar um pré-processador fuzzy ou estatístico acionandouma rede neural. Esta é a forma mais fraca de hibridização, sendo que alguns pesquisadores nem a encaram,efetivamente, como um sistema híbrido.

b) Híbrido Auxiliar - Neste modelo, um subsistema constituído pela técnica do paradigma 2 é chamadopelo subsistema implementado pelo paradigma 1, retornando ou realizando alguma tarefa auxiliar. A Figura 26ilustra este modelo de hibridização.



Entrada Saída

Figura 26: Modelo Híbrido Auxiliar

Como exemplo desta combinação de paradigmas pode-se citar um sistema em que uma rede neural invocaum algoritmo genético para a otimização de seus pesos, ou de sua estrutura. Neste caso, tem-se um maior grau dehibridização em comparação com o primeiro caso (Híbrido Sequencial).

c) Híbrido Incorporado - Nesta forma de se combinar os dois paradigmas não há uma separação visívelentre os dois subsistemas. Pode-se dizer que o primeiro paradigma contém o segundo e vice-versa. A Figura 27traz uma representação deste modelo.

Paradigma 1+

Paradigma 2

Entrada Saída

Figura 27: Modelo Híbrido Incorporado

Um exemplo deste modelo é o caso de um sistema neuro-fuzzy híbrido onde um sistema de inferênciafuzzy é implementado segundo a estrutura de uma rede neural. Aqui a hibridização é a maior possível. Hásistemas em que a hibridização é de um grau tão elevado que não é possível a separação dos dois paradigmas.

A seguir, são descritos os modelos híbridos mais comumente encontrados na área de InteligênciaComputacional.

• Sistema Neuro-Fuzzy

Os sistemas Neuro-Fuzzy estão entre os sistemas híbridos mais pesquisados na atualidade, por associaremvantagens de duas técnicas de modelagem muito populares como as Redes Neurais e a Lógica Fuzzy. Este tipode enquadra-se no tipo híbrido incorporado (tipo (c) na classificação anterior).


• Sistema Neuro-Genético

Constitui-se em uma das hibridizações que ainda carecem de maior atenção dos pesquisadores. Osmétodos de otimização evolucionários podem ser usados para: ajustes dos parâmetros (pesos) da rede; definiçãoda arquitetura da rede; ou ainda para o ajuste dos parâmetros de treinamento (ex. taxa de aprendizado emomentum). Entre os trabalhos que empregam esse tipo de hibridização podem ser citados: Bengio que otimiza,via programação genética, os parâmetros dos algoritmos de aprendizado de redes neurais; Whitley e Fogel queutilizam algoritmos genéticos e programação evolucionária para ajuste dos pesos de redes neurais; e Angelint,Maniezzo que estudam o uso de estratégias evolucionárias na busca de melhores topologias para redes neurais.Todos estes sistemas neuro-genéticos se enquadram no tipo híbrido auxiliar (b).

• Sistema Neural e Estatístico

Este é um dos campos em que ainda há pouco investimento em pesquisa. A análise e a previsão de sériestemporais é uma área de aplicação com forte interseção entre os métodos estatísticos e as redes neurais. Os doisparadigmas, ao seu modo, realizam previsões de sistemas. Do lado estatístico estão os métodos deamortecimento exponencial, os modelos lineares auto-regressivos e de médias móveis (ARMA) e suas extensões.Do lado neural estão as redes do tipo MLP’s (MultiLayer Perceptrons), as redes de funções de bases radiais(RBF - Radial Basis Function), entre outras. Um modelo híbrido (NLARMA/RN) é apresentado por Velloso eenvolve a associação de um modelo ARMA com Redes Neurais, onde estas substituem os coeficientes dospolinômios referentes às partes auto-regressivas e de médias móveis, gerando um modelo não-linear. Um outrotrabalho interessante nesta área é o de Tiozzo que envolve a identificação de um modelo ARIMA através do usode redes neurais. Estes dois sistemas se enquadram no tipo híbrido incorporado (c) .

• Sistema Fuzzy-Genético

A associação de Técnicas Evolucionárias com Sistemas Fuzzy pode-se dar tanto na criação da estrutura ebase de regras deste sistema como no ajuste dos seus parâmetros (perfil dos antecedentes, consequentes e pesosdas regras). Karr um dos primeiros a associar as técnicas de Sistemas de Inferência Fuzzy (SIF) e ComputaçãoEvolucionária, usou um Algoritmo Genético (AG) para otimizar os consequentes das regras de um SIF usado nocontrole de um pêndulo invertido. Os antecedentes eram ajustados manualmente. Evidentemente este sistemanão utilizava toda a potencialidade dos AGs. Lee e Takagi chegaram a um sistema mais complexo em que umAG desenvolvia uma base de regras para o mesmo problema. Uma descrição detalhada dessas possibilidades éencontrada em Leitch. Estes dois sistemas híbridos se enquadram no tipo híbrido auxiliar (b).

• Sistema Genético-Estatístico

A associação destas duas áreas também é pouco explorada, mas alguns trabalhos já despontam nestesentido. Um exemplo dessa associação é o trabalho de Gomes que trata da estimação dos parâmetros de modelosSARMA ou SARIMA por algoritmos genéticos. Outro exemplo é o trabalho de Medeiros, que trata daidentificação de modelos lineares por partes, através de algoritmos genéticos. Estes dois sistemas também seenquadram no tipo híbrido auxiliar (b).

A seguir será apresentada uma descrição mais detalhada dos sistemas híbridos neuro-fuzzy, objetivoprincipal deste trabalho.

7.2.2. Sistemas Neuro-fuzzy

Os Sistemas Neuro-Fuzzy (SNF), conforme mencionado na seção anterior, combinam a capacidade deaprendizado das Redes Neurais Artificiais (RNA) com o poder de interpretação linguístico dos Sistemas deInferência Fuzzy (SIF). Atualmente, estes sistemas estão sob intensa investigação. Tal fato deve-seprincipalmente à confluência dos seguintes fatores: a) aplicabilidade dos algoritmos de aprendizadodesenvolvidos para redes neurais; b) possibilidade de promover a integração de conhecimentos (implícito eexplícito); e c) possibilidade de extração de conhecimento, sob o formato de regras fuzzy, a partir de umconjunto de dados.


A idéia básica de um Sistema Neuro-Fuzzy é implementar um SIF numa arquitetura paralela distribuídade tal forma que os paradigmas de aprendizado comuns às RNAs possam ser aproveitados nesta arquiteturahíbrida. A pesquisa na área dos Sistemas Neuro-Fuzzy busca, portanto, a maximização das propriedadesdesejáveis das RNA e SIF e a minimização de suas limitações e deficiências. O esforço para vencer essaslimitações tem sido umas das principais motivações na criação desses sistemas híbridos inteligentes.

Na próxima seção é proposta uma taxonomia para os SNF baseada na característica dual (Neural e Fuzzy)que estes sistemas possuem.

Taxonomia dos Sistemas Neurofuzzy

Diversas arquiteturas de SNF têm sido propostas na literatura. Devido à natureza dual destes sistemas,propôs-se a divisão da taxonomia desses SNF em duas categorias:

• quanto às características fuzzy do sistema;• quanto às características de aprendizado.

Conforme pode ser observado, uma categoria contempla o lado fuzzy enquanto a outra contempla o ladoneural (referente às características de aprendizado) dos SNF. Os gráficos da Figura 28 e Figura 29 apresentam ataxonomia proposta de acordo com as duas categorias definidas, isto é, de acordo com as características fuzzydos sistemas e com as características de aprendizado, respectivamente.

S.N.F.(SistemasNeuro-Fuzzy)

Formato dasfunções depertinência (FP)

Particionamentodo espaço de E/S

Método deDefuzzificação

- Centro de Área- Média Ponderada- Centro de Somas- Caixa Preta (Black Box)- Outros

- Mamdani- Takagi-Sugeno- Tsukamoto- ClassificaçãoModelo Fuzzy

- Triangular- Trapezoidal- Gaussiano- Sino- Sigmoidal- Singleton- Fuzzy Grid- Adaptive fuzzy Grid- Fuzzy Boxes- Fuzzy Clusters- BSP- Quad Tree

Figura 28: Taxonomia quanto às características fuzzy do sistema


- Aprendizado On Line

- Aprendizado Off Line

- Identificação Prévia

- Identificação Automática

Apresentação dospadrões detreinamento

Identificação daestrutura

- Com apoio de especialista

-Método Auto-Organizado

-Método da distribuição Uniforme das FPs

- Incremental

- Decremental

Identificação dosparâmetros

- Antecedentes

- Antecedentes e Consequentes

- Antecedentes.,Conseqüentes., e Peso das regras

SNF

Figura 29: Taxonomia quanto às características de aprendizado

Taxonomia quanto às características fuzzy

Com relação às características fuzzy dos sistemas Neuro-Fuzzy, dividiu-se a taxonomia em quatro sub-classes:

• Modelo Fuzzy• Formato das funções de pertinência• Particionamento do espaço de entrada/saída• Método de defuzzificação

Essas características estão descritas a seguir.

• Quanto ao Modelo Fuzzy implementado

As regras fuzzy formam a parte fundamental da estrutura de conhecimento em um sistema fuzzy de inferência.Os formatos de regras fuzzy podem ser divididos em quatro grupos principais, conforme mostrado na taxonomiada Figura 28. Os três primeiros - Mamdani, Takagi-Sugeno e Tsukamoto - correspondem ao modelo deinferência fuzzy. A diferença básica entre esses três primeiros modelos recai no tipo de consequente e noprocedimento de defuzzificação. O quarto formato foi incluído para contemplar os sistemas fuzzy declassificação. A seguir são descritos os quatro formatos. Por simplicidade, somente modelosde regras com duas entradas e uma saída são usados nos exemplos.


Mamdani

Regra : If x is A and y is B Then z is C

Este modelo foi proposto, inicialmente, como uma tentativa para controlar um conjunto turbina avapor/boiler, usando regras derivadas de um especialista humano. A Figura 30, a seguir, ilustra como a saída ‘z’de um sistema de inferência do tipo de Mamdani é gerada.

Figura 30: Modelo de Mamdani com composição Min/Max

A saída precisa (crisp) ‘z’ é obtida pela defuzzificação do conjunto fuzzy de saída resultante da aplicaçãoda operação de t-conorm* sobre os conjuntos consequentes que, por sua vez, foram modificados via t-norm*(implicação) pelo grau de disparo (“firing strength”) do antecedente.

* t-norm e t-conorm são definições genéricas de operações que implementam a interseção (AND) e a união (OR)entre conjuntos fuzzy.

Takagi-Sugeno

Regra : If x is A and y is B Then z = f ( x , y )

Neste caso, a saída de cada regra é uma função das variáveis de entrada. Geralmente, a função que mapeiaa entrada e saída para cada regra é uma combinação linear das entradas, isto é z = px1 + qx2 + r. No caso em quep=q=0, temos z = r (fuzzy singleton). A saída do sistema é obtida pela média ponderada (procedimento dedefuzzificação) das saídas de cada regra, usando-se o grau de disparo (firing strength) destas regras como pesosda ponderação. A Figura 31, a seguir, ilustra este modelo.

Regra 1 -

Regra 2 -


Figura 31: Modelo de Takagi-Sugeno


Tsukamoto

Regra : If x is A and y is B Then z is C (monotônica)

Neste sistema fuzzy de inferência o consequente de cada regra é representado por um conjunto fuzzy comuma função de pertinência monotônica. A Figura 32, a seguir, ilustra este modelo e mostra o procedimento parao cálculo da saída ‘z’.

Figura 32: Modelo de Tsukamoto

Modelo fuzzy para Classificação

Regra : If x is A and y is B Then pattern (x,y) belongs to class i

Este último formato de regras fuzzy foi acrescentado aos modelos clássicos anteriores pelo fato dosdemais não serem adequados aos sistemas de inferência fuzzy desenvolvidos para tarefas de classificação. Osmodelos clássicos são mais adequados para aplicações em controle, previsão, reconhecimento de padrões,aproximação de funções, sistemas especialistas , etc. A Figura 33, a seguir, ilustra um exemplo de um sistemafuzzy para classificação com duas entradas e três classes de saída.

Regra 1

Regra 2


Regra 1

Regra 2

Regra 3

Regra 4

Regra 5

Regra 6

xk1 xk

2

mín

w1 => 0,3

mín

w2 => 0,15

mín

w3 => 0,9

mín

w4 => 0,0

mín

w5 => 0,0

mín

w6 => 0,0

Máx, Z1= 0,3

Máx, Z2=0,9

Máx, Z3=0,0

Classe 1

Classe 2 (Classe vencedora)

Classe 3

A1

A1

A2

A2

A3

A3B3

B1

B3

B2

B1

B2

Figura 33: Sistemas Fuzzy de Classificação com duas entradas e três classes de saída

Neste caso as saídas são calculadas diretamente pelas operações de t-conorm aplicadas sobre o grau dedisparo das regras (t-norms). Neste caso não há procedimento de defuzzificação.

•Quanto ao formato das Funções de Pertinência (FPs)

Vários perfis de FPs são encontrados na implementação de sistemas fuzzy e neuro-fuzzy. Nesta seçãoserão apresentados os 5 tipos mais comuns de funções de pertinência.

Triangular - Esse perfil tem a vantagem de ser computacionalmente simples. É descrito por três variáveis : SL,C e SR (Spread Left, Center e Spread Right) e é definido pelas expressões abaixo:

µ( )xx SLC SL

=−− , para SL ≤ x ≤ C

µ( )xx SRC SR

= −− , para C ≤ x ≤ SR

µ( )x = 0 , caso contrário

A Figura 34, abaixo, ilustra um exemplo de uma FP de perfil triangular, com seus parâmetrosdescritores.

µ(x)


SL C SR

1

0 x

Figura 34: Função de pertinência de formato triangular

Trapezoidal - Pode ser descrito por três variáveis: ‘u’, ‘v’ e ‘d’ que regula a inclinação das bordas da FPtrapezoidal (mais crisp ou mais fuzzy). As expressões a seguir definem este perfil.

µ ( ) [ ( , ) ( , )]x g x v d g u x d= − − − −1

onde, g s dse s d

s d se s dse s d

( , ), .

. , ., .

=>≤ ≤<

1 10 1

0 0

A Figura 35, a seguir, ilustra uma FP de formato trapezoidal como descrito pelas expressões dadasacima.

x

1.0µ(x)

0.0 u u+1/d v-1/d v

θ θ

tg θ = d

Figura 35: Função de pertinência com formato trapezoidal

Outras FP trapezoidais utilizam quatro parâmetros, permitindo que as bordas do trapézio tenhamdiferentes inclinações. A Figura 36 ilustra um exemplo de tal FP, descrita pelas expressões seguintes.

0, x ≤ a 1-(b-x)/(b-a) , a < x ≤ b

µ(x) = 1, b < x ≤ c (d-x)/(d-c), c < x ≤ d 0, x>d

Onde ‘a’, ‘b’, ‘c’ e ‘d’, são parâmetros do formato da FP.


x

1.0

µ(x)

0.0 a b c d

Figura 36: Função de pertinência com formato trapezoidal descrita por 4 parâmetros

Gaussiano - Este perfil é descrito pela expressão abaixo, onde m é a média e v é o desvio padrão:

µ( )x ex m

v=− −

2

Este formato de FP é empregado em aplicações de agrupamentos (clusters) que utilizam medidas desimilaridade (por ex. distância euclidiana), ou seja, padrões semelhantes exibem pequenas distância entre si.Quanto mais próximo da média ‘m’ está o padrão, maior o grau de pertinência do mesmo. A Figura 37, a seguir,ilustra este formato.

µ(x)

x

c-v m c+v

1

0

1/e

Figura 37: Função de pertinência de formato gaussiano

Sino - Este perfil de função de pertinência é definido pela expressão abaixo:

onde a variável ‘c’ define o centro da FP, ‘a’ define a largura e ‘b’ o decaimento da FP. Conforme mostrado naFigura 38, seu perfil é bem parecido com o perfil do formato anterior. Entretanto, o esforço computacional para oseu cálculo é menor por não envolver exponenciais.


µ(x)1

0 x

c-a c c+a

1/2θ

tg θ = -b/2a

Figura 38: Função de pertinência com formato sino

Sigmoidal - Este perfil é baseado na função sigmóide tão conhecida no estudo das redes neurais. As FPs destetipo são criadas utilizando-se apenas uma (perfil monotônico) ou duas funções sigmóides superpostas (perfil emformato sino).

Perfil monotônico - Descrito por duas variáveis: ‘a’ que define o grau de nebulosidade (sua inclinação no pontode transição) da FP e ‘b’ que define o ponto de transição. A expressão da FP é dada pela equação abaixo e seuformato é ilustrado na Figura 39, a seguir:

µ( ) ( , , ) ( )x sig x a be a x b= = + − −

11

µ(x)1

0 x

x=b

θ , tg θ ~ a

Figura 39: Função de pertinência com formato sigmoida

Perfil em Formato Sino - Descrito por quatro variáveis ‘a1’, ‘a2’, ‘b1’ e ‘b2’ referentes às duas sigmóidessuperpostas. A definição da FP é dada pelas expressões a seguir:

com b1 < b2. A Figura 40, a seguir, mostra um exemplo deste perfil de FP.


µ(x)1

0 x

Figura 40: Função de pertinência com formato sigmoidal/sino

A principal diferença entre as FPs com formato de sino vistas anteriormente e esta FP implementada porduas sigmóides é o fato de que esta permite a construção de FPs não simétricas, ou seja, o decaimento e a largurade cada lado do sino podem ser diferentes.

As FPs descritas acima podem ser utilizadas tanto nos termos antecedentes quanto nos termosconsequentes das regras. Entretanto, um tipo de FP muito frequente entre os consequentes dos SNF é o chamado‘Fuzzy Singleton’. Este formato compreende uma FP que apresenta o grau de pertinência igual a 1 apenas em umponto de seu domínio, e o grau 0 (zero) nos demais pontos. Sua principal vantagem é simplificar o processo dedefuzzificação do sistema fuzzy. A Figura 41 ilustra um exemplo de FP ‘Fuzzy Singleton’ ou simplesmente‘Singleton’. Nela o grau de pertinência da FP assume o valor 1 apenas para x=a.

µ(x)

0

1

xx=a

Figura 41: Função de pertinência Fuzzy Singleton

•Quanto ao Particionamento do espaço de E/S

As variáveis de entrada/saída dos sistemas de inferência fuzzy são divididas em vários termos lingüísticos(por ex. baixo, médio e alto) que são utilizados pelas regras fuzzy. O particionamento do espaço de entradaindica a forma como as regras fuzzy estão relacionadas com este espaço. O particionamento do espaço de saídacostuma ser mais simples e está associado aos conseqüentes das regras.

A Figura 42, a seguir, mostra vários tipos de particionamentos possíveis para o espaço de entrada. Osexemplos ilustrados nesta figura referem-se a sistemas com duas variáveis de entrada, mas podem sergeneralizados. Desta forma, as variáveis do espaço de entrada correspondem à dimensão horizontal e vertical decada figura.


(a)Fuzzy Grid (b) Adaptive Fuzzy Grid

(c)Fuzzy Boxes (d) Fuzzy Clusters

(e) BSP (f) Quad Treex2

x1

x1,x2 - Variáveis de entrada

Figura 42: Particionamentos possíveis para o espaço de entrada

O particionamento Fuzzy Grid da Figura 42a é fixo, não permitindo ajustes nas funções de pertinência. Ossistemas que o utilizam ajustam apenas os parâmetros dos conseqüentes.

Na Figura 42b, o particionamento Adaptive Fuzzy Grid, como o próprio nome diz, é adaptativo, e permiteajustes nos perfis das funções de pertinência. Os particionamentos Fuzzy Grid são simples e intuitivos, porém, àmedida que o número de variáveis de E/S aumenta, o número de partições cresce combinatoriamente. Em algunscasos isto pode levar a situações em que o tamanho da memória torna-se impraticavelmente grande.

A Figura 42c e a Figura 42d mostram os particionamentos Fuzzy Box e Fuzzy Cluster, respectivamente.O primeiro (Figura 42c) aparece em sistemas que utilizam a versão fuzzy das redes neurais ART, como fuzzyART de Carpenter et al., ou no SNF chamado Fuzzy Self-Organized Map - FSOM - de Vuorimaa. O segundo(Figura 42d) é gerado por redes neurais do tipo das Redes de funções de Bases Radiais (Radial Basis Function -RBFs), que para alguns pesquisadores da área podem ser encaradas também como um SNF. Tanto o FSOMquanto as RBFs usam alguma medida de similaridade entre padrões para o cálculo dos centros de suas funçõesde pertinência.


Os particionamentos das Figura 42e (BSP) e Figura 42f (Quadtree) são flexíveis e minimizam, um pouco,o problema do crescimento exponencial do número de regras pois só criam novas regras localmente, conforme oconjunto de treinamento. Sua vantagem principal é permitir a criação de sistemas que constróem sua própriaestrutura de forma automática (proposta deste trabalho).

•Quanto ao método de defuzzificação

Uma vez feitas as avaliações das proposições (regras) fuzzy, deve-se determinar o valor real da saída dosistema fuzzy. Este processo chama-se Defuzzificação.

Várias estratégias de defuzzificação têm sido propostas. Neste trabalho procurou-se descrever os métodosde defuzzificação mais encontrados nos SNF. Estes são descritos a seguir.

COA ( Centro de Área) - É um dos métodos mais utilizados. Supondo-se um universo de discurso discreto, asaída crisp ‘z’ é produzida pelo cálculo do centro de gravidade do conjunto fuzzy consequente µc obtido pelacomposição das regras. A expressão da saída ‘z’ é dada por:

ZZic Zi

i

m

c Zii

m= =

=

∑

∑

µ

µ

( ) *

( )

0

0

onde ‘m’ é o número de intervalos de quantização da saída, ‘Zi’ é o valor da variável de saída para o intervalo dequantização ‘i’ e µc(Zi) seu grau de pertinência.

MP (Média Ponderada) - Quando apenas ‘singletons’ são usados como consequentes das regras fuzzy, este é ométodo naturalmente indicado, pois combina os consequentes das regras fuzzy com o nível de disparo de cadauma delas, gerando uma saída ‘z’ de acordo com a expressão:

ZZii

i

n

ii

n= =

=

∑

∑

µ

µ

*1

1

onde ‘n’ é o número de regras fuzzy, µi é o nível de disparo da regra ‘i’, e ‘Zi’ é o valor do ‘singleton’ ‘i’. Estemétodo também é utilizado na defuzzificação dos modelos fuzzy de Takagi-Sugeno de 1 a ordem (saída écombinação linear das entradas), conforme ilustrado na figura 2.7, e Tsukamoto que utiliza funções monotônicasnos conseqüentes das regras, conforme mostrado na figura 2.8.

Centro de Somas - Este método é uma simplificação do método do centro de gravidade. Sua vantagem é omenor esforço computacional no cálculo da saída quando comparado ao método do COA. A saída ‘z’ é dada pelaexpressão:

ZC B

Area B

ui

i

n

ii

n

i

i

= =

=

∑

∑

( )

( )

α

α

1

1

onde,• Bi (i =1, ....,n) são os termos linguísticos dos consequentes,•‘αi’ é o nível de disparo da regra ‘i’ ,• Bi

αi é o conjunto fuzzy obtido através do método de implicação de Mamdani, ou seja, Bi cortado em‘αi’ como na Figura 43 abaixo.

• C B Centroid B x Area Bui i ii i i( ) ( ) ( ).α α α=


αi

Bi

x

Biαi

Figura 43: Conjunto fuzzy Biαi obtido pelo corte de Bi no patamar dado por αi

Defuzzificação Caixa Preta - Este método faz uso de uma rede neural para implementar a etapa dedefuzzificação de um SNF. Os métodos mais comuns de defuzzificação (por ex. centro de área) podem serimplementados através de redes neurais. Neste método, os valores dos níveis de disparo de cada regra sãoponderados e somados em neurônios com função de ativação sigmóide, ou seja, são entradas da RNA que realizaa defuzzificação.

Um estudo sobre as propriedades das redes neurais utilizadas para defuzzificação é encontrado em Song.Halgamuge utiliza um método de defuzzificação black-box em seu sistema neuro-fuzzy FuNe I.

Taxonomia quanto às características de aprendizado

Dividiu-se em três subclasses a taxonomia quanto às características de aprendizado dos sistemas neuro-fuzzy:

• quanto à apresentação dos padrões de treinamento;• quanto ao método de identificação da estrutura;• quanto ao aprendizado dos parâmetros.

Essas características estão descritas a seguir.

• Quanto à apresentação dos padrões de treinamento

A apresentação dos padrões de treinamento pode ser realizada de duas formas diferentes: o aprendizadoOff-line e o aprendizado On-line.

Aprendizado Off-line

A atualização dos parâmetros/estrutura acontece somente após a apresentação de todo o conjunto detreinamento, isto é, após uma época ou varredura. Esta forma requer um conjunto de dados de treinamentodisponível antes da identificação da estrutura e dos parâmetros, o que em certas situações pode se constituir emum problema.

Aprendizado On-line

A atualização dos parâmetros acontece logo após cada par de treinamento ter sido apresentado. Estaestratégia de aprendizado é indicada para sistemas com características variantes ou quando não se tem à mão,previamente, um conjunto de dados de treinamento.


• Quanto ao método de identificação da estrutura

A identificação da estrutura está relacionada à determinação de um número adequado de regras fuzzy e deum particionamento de E/S satisfatório, com o esboço inicial das FPs. Há duas vertentes principais parapromover a identificação da estrutura de um SNF: Identificação Prévia e Identificação Automática.

Identificação Prévia

Este tipo de identificação precede o ajuste dos parâmetros do sistema. Utiliza-se para tal umconhecimento prévio do sistema a ser desenvolvido. Pode-se destacar três métodos para realizar tal tarefa:

a)Método com apoio do especialista

Neste método, o conhecimento prévio é explícito e proveniente de especialista(s). A criação das regras e oesboço preliminar das FPs envolve um domínio de conhecimento de interesse específico, o apoio de um ou maisespecialistas neste domínio e um engenheiro do conhecimento capaz de extrair este conhecimento do especialistae expressá-lo em termos de proposições fuzzy e variáveis linguísticas.

b)Método Auto-Organizado e Aprendizado Competitivo

Aqui o conhecimento prévio é implícito e proveniente de um conjunto de dados de treinamento. Utiliza-se, inicialmente, um algoritmo neural não-supervisionado e auto-organizado (por ex. SOM de Kohonen) paradeterminar os valores iniciais dos centros das FPs, ou algum outro método estatístico de agrupamento(‘clustering’). Uma vez achados os centros das FPs, seus parâmetros referentes à largura podem serdeterminados heuristicamente por algoritmos como por exemplo‘k-nearest-neighbors’ ou ‘first-nearest-neighbors’. Em seguida, criam-se algumas regras, a partir dos primeiros padrões apresentados no treinamento. Oantecedente das regras é criado tomando-se os conjuntos fuzzy que tiverem maior grau de pertinência para opadrão sob treinamento. Havendo conflito entre as regras, aplica-se um processo baseado em competição entreestas. Por exemplo aplica-se um padrão na entrada do sistema e verifica-se qual regra exibe maior grau dedisparo. Esta regra será a regra vencedora, daquele padrão, para o algoritmo de aprendizado.

c)Método da Distribuição Uniforme das FPs

Neste método as FPs são criadas através de uma distribuição uniforme sobre o universos de discurso dascaracterísticas do espaço de E/S (particionamento fuzzy grid). Após esta etapa o aprendizado competitivo éusado para a criação das regras fuzzy.

Nada impede que se utilize um dos dois métodos acima descritos (b e c) mesclados com o primeiro (a),promovendo o que se pode chamar de integração do conhecimento.Identificação Automática

Na identificação/geração automática o aprendizado das regras pode ser feito de forma incremental oudecremental.

O aprendizado incremental das regras significa partir inicialmente de uma base de regras vazia (camada deregras vazia) ou de uma regra default (Vuorimaa) e adicionar novas regras segundo uma determinada heurística.Geralmente isto só é possível com o conhecimento da saída desejada (aprendizado supervisionado).

O aprendizado decremental das regras inicia-se com um conjunto superestimado de regras, o que pode gerar umsistema inconsistente. Segue-se então um processo de eliminação de regras supérfluas, tornando o sistemaconsistente. Tal procedimento é computacionalmente dispendioso, mas pode ser feito quando não há informaçãodisponível sobre a saída desejada (o “reinforcement learning” é aplicável).

• Quanto ao aprendizado dos parâmetros

Como identificação dos parâmetros entende-se o ajuste dos parâmetros do sistema, tais como os pesosfuzzy que definem os perfis das FPs dos antecedentes e consequentes das regras fuzzy, e o peso ou importânciarelativa destas regras. Nem todos os SNF utilizam ajuste do peso das regras. Neste caso, o peso é fixo e de valor


unitário, o que permite uma boa interpretação semântica das regras fuzzy levantadas pelo processo deaprendizado.

Após a definição da estrutura (ou durante esta), os pesos fuzzy e, se for o caso, os pesos das regras dosistema NF, devem ser ajustados por algum critério para minimizar o erro. No que se refere a este item dataxonomia, pode-se dividir os SNF em três tipos:

Sistemas com identificação apenas dos antecedentes

São encontrados entre os sistemas voltados para tarefas de classificação. Neste caso não há consequentesa ser ajustados. O perfil das FPs dos antecedentes das regras fuzzy é geralmente ajustado por um algoritmosupervisionado de retropropagação do erro. Um exemplo típico é o NEFCLASS de Nauck.

Sistemas com identificação dos antecedentes e consequentes

Representam a grande maioria dos SNF. Neste caso o peso de cada regra é fixo e de valor unitário, o quepermite uma fácil interpretação do significado das regras. O aprendizado dos antecedentes e consequentes podeser feito simultaneamente, ou em dois passos. Um exemplo inovador desse tipo de SNF é o FSOM (Fuzzy Self-Organized Map) de Vuorimaa. Este utiliza um algoritmo supervisionado chamado LVQ (Learning VectorQuantization) no ajuste dos antecedentes e um algoritmo gradiente decrescente no ajuste dos consequentes.

Sistemas com identificação dos antecedentes, consequentes e peso das regras

Nesses sistemas o aprendizado de todos os parâmetros é realizado de uma forma global através de umalgoritmo supervisionado que os ajusta num mesmo passo. Geralmente é utilizado o algoritmo deretropropagação do erro, em uma versão modificada que visa permitir o treinamento com funções de ativaçãonão diferenciáveis, como por exemplo a operação de mínimo usado como T-norm. No instante daretropropagação do erro verifica-se que antecedente gerou o valor mínimo e ajusta-se apenas o conjunto fuzzydeste antecedente pelo método “Gradient Descent”.

Exemplos de Modelos Neuro-Fuzzy

Nesta seção descrevem-se, de forma sucinta, três dos sistemas Neuro-Fuzzy mais conhecidos: ANFIS,FSOM e NEFCLASS. Com isto espera-se tornar mais clara a compreensão de um sistema Neuro-Fuzzyqualquer.

ANFIS

O sistema Neuro-Fuzzy ANFIS foi criado por Jang e sua sigla significa “Adaptive Network-based FuzzyInference System”. Sua popularidade já o levou a ser inserido no MATLAB©. A figura 2.20, abaixo, ilustra umexemplo de uma arquitetura ANFIS. Esta arquitetura pode ser usada na implementação de sistemas para previsãoe aproximação de funções, embora o autor tenha proposto variantes para outras aplicações.

Funcionalmente esta arquitetura é equivalente a um sistema de inferência fuzzy de Tsukamoto, embora sepossa implementar, também, um sistema de inferência fuzzy de Takagi-Sugeno. Para um melhor entendimentodesta arquitetura as suas camadas são descritas a seguir:

Camada1

Computa o grau de pertinência com que as entradas precisas (“crisp”) x1 , x2 , x3 , satisfazem os termoslinguísticos (Ai = Alto e Bi = Baixo) associados a estes nós. Os parâmetros que definem os perfis de cada termosão encarados como pesos fuzzy. Assim, se o conjunto fuzzy A1 na Figura 44 for de formato sigmóide, osparâmetros ‘a’ e ‘b’ corresponderão aos pesos do 1o. processador fuzzy da camada 1. No exemplo da Figura 44,cada entrada tem apenas dois termos lingüísticos (alto e baixo), porém, nada impede que este número seja maior.

Camada2


Cada nó desta camada corresponde a uma regra e computa o nível de disparo (firing strength) da regra, ouseja, calcula com que grau de pertinência o consequente da regra está sendo atendido. Os neurônios destacamada simbolizam a operação de t-norm. No exemplo da Figura 44 as saídas dos neurônios da camada 2 sãodadas por:

S1=A1(x1) * A2(x2) * A3(x3) S2=B1(x1) * B2(x2) * A3(x3)S3=B1(x1) * B2(x2) * B3(x3)

Onde “*”representa o operador t-norm.

x1

x2

x3

Camada1 Camada2 Camada3 Camada4 Camada5

A1

B3

A3

B2

A2

B1T

T

T

N

N

N

C1

C2

C3

Z

S1

S2

S3

h1

h2

h3

S1’

S2’

S3’

Figura 44: Arquitetura Neuro-Fuzzy (ANFIS)

Camada3

Esta camada realiza uma normalização (nem sempre existente em outras arquiteturas) nos níveis dedisparo das regras. Por isso, cada um de seus nós está rotulado pela letra “N”. A normalização neste sistema éutilizada como um pré-processamento para a defuzzificação. As saídas dos nós desta camada, referentes à Figura44, são dadas por:

S1’=S1/(S1+S2+S3) S2’=S2/(S1+S2+S3) S3’=S3/(S1+S2+S3)

Camada4

Aqui as saídas dos neurônios são calculadas pelo produto entre os níveis de disparo normalizados (Si,i=1,2 e 3) e o valor do conseqüente da regra em si. Os valores de saída de cada nó desta camada (Figura 44) sãodados por:

h1=S1’. C1 h2=S2’. C2 h3=S3’. C3


onde os valores Ci correspondem aos conseqüentes ‘singletons’ou aos conseqüentes de Sugeno de primeiraordem (combinações lineares das entradas).

Camada5

O nó desta última camada da arquitetura da Figura 44 calcula a saída do sistema e, juntamente com os nósdas camadas 3 e 4, promove a defuzzificação. Sua saída é dada por:

Z = h1+h2+h3 =

S1. C1 (S1) + S2. C2 (S2) + S3. C3 (S3) Z =

S1 + S2 + S3

Este sistema utiliza o particionamento Fuzzy-grid Adaptativo. Seu aprendizado (identificação da estruturae parâmetros) é feito em duas etapas que se repetem até que o critério de parada seja alcançado:

Etapa 1 - fixam-se os parâmetros das premissas (antecedentes) e os conseqüentes são ajustados pelo métodoMQO, estimação por mínimos quadrados ordinários.Etapa 2 - fixam-se os parâmetros dos conseqüentes e os parâmetros dos antecedentes são ajustados peloalgoritmo GD.

FSOM

O sistema Neuro-Fuzzy FSOM (Fuzzy Self-Organized Map) foi desenvolvido por Vuorimaa e utiliza oparticionamento fuzzy-box no espaço de entrada. As funções de pertinência utilizadas nos antecedentes dasregras têm perfil triangular e são descritas por três parâmetros: centro (c), largura esquerda (sl) e largura direita(sr). Os conseqüentes das regras são singletons ou combinações lineares das entradas. O formato de uma regrafuzzy ‘i’, neste sistema, é como visto abaixo:

if x1 ∈ Ui,1 and x2 ∈ Ui,2 and x3 ∈ Ui,3 and then y = ai

onde cada condição (xj ∈ Ui,j ) é interpretada como o grau de pertinência µ Ui,j(xj) do valor xj no conjunto fuzzyUi,j . O nível de disparo (firing strength) de cada regra é calculado de acordo com:

αi = min { µ Ui,1(x1), µ Ui,2(x2), .... µ Ui,n(xn) }

O método de defuzzificação empregado é o método da média ponderada. Desta forma, o valor de saída écalculado pela equação abaixo.

ysi i

i

m

ii

m=⋅

=

=

∑∑α

α1

1

onde,

• Si são os singletons referentes à saída de cada regra;• αi são os níveis de disparo das regras;• m é o número de regras.

O método de treinamento deste sistema Neuro-Fuzzy é realizado em três etapas:


1) primeiro os parâmetros dos centros (Ci) dos conjuntos fuzzy são auto-organizados pelo algoritmo SOM deKohonen;

2) em seguida, os conjuntos fuzzy são formados em volta destes centros, usando-se para tal uma larguraconstante w0, de forma que: sl = c - w0 e sr = c + w0. Os valores dos conseqüentes singletons da regras sãocalculados inicialmente segundo a equação abaixo:

sy

i

i k kk

M

i kk

M=⋅

=

=

∑

∑

α

α

,

,

1

1

onde,

yk - é a saída desejada para o padrão k;M - é o número de padrões no conjunto de treinamento;αi,k - é o nível de disparo da regra “i” para o padrão k;Si - é o conseqüente (singleton ou comb. linear) da regra “i” ;

3) por fim, os conjuntos fuzzy dos antecedentes são ajustados por um algoritmo semelhante ao LVQ 2.1 tambémcriado por Kohonen.

A figura 2.21, a seguir, mostra um sistema FSOM com duas entradas e uma saída. Este modelo usacomo conseqüentes combinações lineares das entradas x1 e x2 (camada 4 da Figura 45). A descrição das camadasdeste SNF é semelhante às do sistema ANFIS, exceto pelo fato deste sistema utilizar o particionamento do tipo“fuzzy box”.

x1

x2

Entradas

mín

mín

norm

norm

x1 x2

x1 x2 Σ Saída

y

C1 C2 C3 C4 C5

regra 1

regra 2

α1

α2

Figura 45: Arquitetura de um FSOM com duas entradas e uma saída

Há dois trabalhos relatando a aplicação do FSOM em aproximação de funções e controle.

NEFCLASS

O sistema Neuro-Fuzzy NEFCLASS foi desenvolvido por Nauck e Kruse e sua aplicação básica é emsistemas de classificação. Nauck desenvolveu também dois outros sistemas Neuro-Fuzzy, um para aplicações em


controle - NEFCON e outro para aplicações em previsão e aproximação de funções - NEFPROX. Todos elesestão disponíveis (código e artigos) na internet. Um exemplo de arquitetura desse sistema é ilustrado na Figura46.

As quatro camadas desta arquitetura estão descritas conforme se segue.

Camada de Entrada - Esta camada tem apenas a função de direcionar os valores das entradas x1 e x2 para asentradas das funções de pertinência dos antecedentes das regras.

Camada de Antecedentes - Esta camada gera os graus de pertinência dos antecedentes das regras. O universo dediscurso de cada variável de entrada está dividido em três conjuntos fuzzy (baixo, médio e alto). Oparticionamento do espaço de entrada implementado por esta camada é o “adaptive fuzzy-grid”.

Camada de Regras - Esta camada gera o nível de disparo de cada regra através da operação T-norm realizadaentre os graus de pertinência dos conjuntos fuzzy que antecedem cada elemento desta camada.

Camada de Saída - Esta camada gera cada uma das saídas do classificador. As saídas são obtidas pela operaçãode T-conorm entre os níveis de disparo da camada de regras. Os pesos que interligam a camada de regras e acamada de saída (todos iguais a 1, no caso do NEFCLASS) indicam que cada regra tem um mesmo grau deimportância entre si.

As regras fuzzy que descrevem os dados têm a forma:

if x1 ∈ µ1 and x2 ∈ µ2 and ....and xn ∈ µn then pattern (x1,x2,....xn) belongs to class i

onde µi são conjuntos fuzzy.

O modelo NEFCLASS descobre regras e ajusta o perfil das funções de pertinência dos antecedentes. Oaprendizado deste sistema é realizado em duas etapas separadas. A primeira utiliza um algoritmo para criar acamada de regras. Esta camada pode ser inicializada a partir de um conhecimento prévio ou ser inicializada comum conjunto vazio de regras e crescer com aprendizado incremental de regras. A segunda etapa utiliza umalgoritmo supervisionado de “Gradient Descent” para ajustar os perfis das funções de pertinência dosantecedentes das regras.


µ11

c1 c2

r1 r2 r3 r4 r5

µ21 µ3

1 µ12 µ2

2 µ32

x1 x2

Camada deSaída

Camada deRegras

Camada deAntecedentes

Camada deEntrada

1 1 1 1 1

Figura 46: Sistema NEFCLASS com duas entradas, cinco regras e duas classes de saída

Taxonomia dos três sistemas estudados

Apresentam-se, a seguir, duas tabelas que resumem a classificação dos três sistemas Neuro-Fuzzyanteriormente abordados segundo a taxonomia vista na seção neste capítulo.

Tabela 7 apresenta a classificação dos sistemas ANFIS, FSOM e NEFCLASS segundo suascaracterísticas fuzzy: modelo fuzzy implementado, formato das funções de pertinência (A - para antecedentes eC para conseqüentes), método de particionamento e método de defuzzificação.

Tabela 7: Características fuzzy dos três sistemas em estudo. * Método de deffuzificação: Não existedefuzzificação neste caso

Autor/Sistema/Referência

ModeloFuzzy

FormatodasFPs

Particionamento de E/S

Mét. de

Defuzz.Aplicação

Jang/ANFIS/ Takagi-

SugenoFormato Sino (A) Fuzzy Grid Média

Ponderada

Previsão eAprox. defunções

Vuorimaa/FSOM/ Takagi-

SugenoTriangular (A)Singleton (C)

Fuzzy Box MédiaPonderada

Aprox. defunções econtrole


Nauck/NEFCLASS/ Classificação Triangular (A) Adptive Fuzzy

GridNenhum * Classificação

A Tabela 8 apresenta a classificação dos três sistemas segundo as características de aprendizado(características neurais) : forma de apresentação dos padrões, métodos de identificação da estrutura e deidentificação dos parâmetros.

Tabela 8: Características de aprendizado dos três sistemas em estudo

Autor/Sistema/Referência

Apres.dos

padrões

Identificaçãoda

estrutura

Identificação dos parâmetrosAntecedentes ConseqüentesPeso das

Regras

Observações

Jang/ANFIS/

OFF lineou

ON line

Geração prévia, comparticionamento fuzzygrid.

Passobackward:Conseqüente fixogradientedecrescenteajustaantecedente.

Passoforward:Antecedentefixo. MQOajusta oconsequente

Utilizanormalização donível dedisparodasregras

Ajuste dosparâmetrosrealizado emdois passos :backward eforward.

Vuorimaa/FSOM/

OFF line

Centro das FPs achadospor SOM. FPsformadas em torno doscentros. Regras geradasa partir dosagrupamentos(clusters).

Usa oalgoritmoLVQ2.1para ajustedosantecedentes.

Usa ummétodo deajuste porgradientedecrescentep/ ajuste dosconsequentes.

--------

Sistema inovano uso de umalgoritmosupervisionado(LVQ) paraajuste dosantecedentes.

Nauck/NEFCLASS/

ON lineou

OFF line

Particionamento doespaço de entrada porfuzzy grid. Regras sãocriadas através daheurística de manter as‘R’melhores regras.

Usaalgoritmoderetropropagação doerro(modificado) paraajuste dosantecedentes

---------------

Pesosfixos eiguais a1.

Não háconsequentes aajustar. Pesosdas regraspodem serajustáveis sobpena de perdade significadosemântico dasmesmas.

7.2.3. LIMITAÇÕES DOS SNF

De uma forma geral pode-se atribuir aos SNF duas principais limitações:

1) o número reduzido de entradas com que eles trabalham; 2) e a forma limitada (em alguns casos inexistente) de criar sua própria estrutura e regras.

A primeira limitação ocorre em função da chamada de explosão combinatorial das regras devido aoparticionamento em forma de grade (“fuzzy grid”). Por exemplo, suponha que um determinado SNF tenha cincovariáveis de entrada e cada uma delas tenha seu universo de discurso subdividido em quatro conjuntos fuzzy,conforme ilustrado na Figura 47.


x1

1,0-

0,0-

µ1b µ1

mb µ1ma µ1

a

x2

1,0-

0,0-

µ2b µ2

mb µ2ma µ2

a

x3

1,0-

0,0-

µ3b µ3

mb µ3ma µ3

a

x4

1,0-

0,0-

µ4b µ4

mb µ4ma µ4

a

x5

1,0-

0,0-

µ5b µ5

mb µ5ma µ5

a

Legendaµi

b = baixoi

µimb = médio baixoi

µima = médio altoi

µia = altoi

Figura 47: Particionamento “fuzzy grid” em quatro conjuntos fuzzy para cinco variáveis de entrada

Com este sistema de particionamento, pode-se chegar a um total de 1024 (45) regras. Suponha agora quese tenha 20 entradas. Usando-se a mesma divisão nos universos de discurso para cada variável de entrada, chega-se a um total impraticável de 1.099.511.627.776 (420) regras. Outras formas de particionamento como “fuzzybox”, “fuzzy clusters” e formas recursivas podem minimizar este problema. A forma que desponta como maispromissora para vencer esse problema é o particionamento recursivo.

A segunda limitação está presente nos SNF atuais porque eles exibem (quando tal) uma capacidadelimitada de criar sua própria estrutura. Alguns têm estrutura fixa, arbitrada a priori, e não permitem que ela varie.Outros SNF, mais flexíveis, têm alguma capacidade de alterar sua estrutura, permitindo que se altere o númerode divisões no universo de discurso de algumas de suas variáveis de entrada e, consequentemente, o número deregras. Entretanto, esta habilidade é reduzida e ainda o mantém refém do primeiro tipo de limitação. Umasolução para isto é o uso, novamente, das formas de particionamento recursivas, que permitem a criação de SNFcom uma capacidade ilimitada de crescimento em sua estrutura.

8. ALGORITMOS GENÉTICOS

8.1. RESUMO

Algoritmos Genéticos são inspirados no princípio Darwiniano da evolução das espécies e na genética[GOLD89]. São algoritmos probabilísticos que fornecem um mecanismo de busca paralela e adaptativa baseadono princípio de sobrevivência dos mais aptos e na reprodução. Este capítulo apresenta os princípios básicos dosAlgoritmos Genéticos.

8.2. ALGORITMOS GENÉTICOS: PRINCÍPIOS E APLICAÇÕES

Algoritmos Genéticos constituem uma técnica de busca e otimização, altamente paralela, inspirada noprincípio Darwiniano de seleção natural e reprodução genética [GOLD89].


Os princípios da natureza nos quais os GAs se inspiram são simples. De acordo com a teoria de C.Darwin, o princípio de seleção privilegia os indivíduos mais aptos com maior longevidade e, portanto, commaior probabilidade de reprodução. Indivíduos com mais descendentes têm mais chance de perpetuarem seuscódigos genéticos nas próximas gerações. Tais códigos genéticos constituem a identidade de cada indivíduo eestão representados nos cromossomas.

Estes princípios são imitados na construção de algoritmos computacionais que buscam uma melhorsolução para um determinado problema, através da evolução de populações de soluções codificadas através decromossomas artificiais.

Em GAs um cromossoma é uma estrutura de dados que representa uma das possíveis soluções doespaço de busca do problema. Cromossomas são então submetidos a um processo evolucionário que envolveavaliação, seleção, recombinação sexual (crossover) e mutação. Após vários ciclos de evolução a populaçãodeverá conter indivíduos mais aptos.

A analogia entre Algoritmos Genéticos e o sistema natural é apresentada através da tabela abaixo:

Tabela 9

Natureza Algoritmos Genéticos

Cromossoma Palavra binária, vetor, etcGene Característica do problemaAlelo Valor da característicaLoco Posição na palavra, vetorGenótipo EstruturaFenótipo Estrutura submetida ao problemaIndivíduo SoluçãoGeração Ciclo

Podemos caracterizar os Algoritmos Genéticos através dos seguintes componentes:

1. Problema a ser otimizado2. Representação das Soluções de Problema3. Decodificação do Cromossoma4. Avaliação5. Seleção6. Operadores Genéticos7. Inicialização da População

Algoritmos Genéticos têm sido bem sucedidos em diversas áreas de aplicações, principalmente emproblemas de otimização [DASG97]. Um problema de otimização caracteriza-se fundamentalmente emencontrar uma ou uma série de boas soluções entre um número muito grande de possíveis soluções (espaço debusca). Para alguns problemas, algoritmos de busca baseados em técnicas matemáticas são capazes de encontrarsoluções ótimas. Entretanto, em problemas onde o espaço de busca é intratável ou em problemas complexos dedifícil modelagem matemática, estas técnicas podem falhar [ DHAR97]. Nestes casos, técnicas heurísticas comoAlgoritmos Genéticos podem oferecer uma solução ótima ou sub-ótima para o problema. Um AlgoritmoGenético resolve problemas baseando-se no princípio de Darwin para a sobrevivência dos indivíduos mais aptos(seleção natural), onde indivíduos são soluções que recombinam-se gerando novas soluções que tendem a sermelhores que as anteriores [DAVI96].

Algoritmos Genéticos tornaram-se particularmente interessantes devido ao fato de não ser necessário sedescrever como encontrar uma boa solução. Tais soluções podem ser encontradas de forma paralela, avaliando-se e percebendo-se em que direção devem estar localizadas as melhores soluções, ou soluções potenciais.

O conceito de solução em um Algoritmo Genético na área de mineração de dados pode ser caracterizadopor uma regra de associação [AGRA93]. Esta regra, representada num cromossoma, é da forma SE (A1 e A2 eA3 e ... An) ENTÃO P, onde os itens ou atributos do banco de dados {A1, A2, ,A3, ..., An} estão representadossimbolicamente como condições para que a conclusão da regra, caracterizada por (P), seja verdadeira.Representando regras dessa forma, pode-se então procurar obter padrões que caracterizem um banco de dadosatravés da evolução genética. A busca dessas regras é o ponto crucial desta pesquisa, visto que o espaço de buscaé em geral muito grande e não se conhece, a princípio, métodos não exaustivos de encontrar uma boa solução.

Diante deste cenário, onde tecnologias de banco de dados, mineração de dados e visualização de dadosestão intrinsecamente ligadas, a descoberta de padrões em forma de regras de associação, utilizando AlgoritmosGenéticos, mostra-se como mais um método promissor de extrair conhecimento.


A seguir é apresentada uma breve discussão sobre cada um desses aspectos, exemplificando-se quandoapropriado.

1 – Problema

GAs são particularmente aplicados em problemas complexos de otimização: problemas com diversosparâmetros ou características que precisam ser combinadas em busca da melhor solução; problemas com muitasrestrições ou condições que não podem ser representadas matematicamente; e problemas com grandes espaçosde busca.

GAs têm sido aplicados a diversos problemas de otimização, tais como: [MICH94] Otimização deFunções Matemáticas, Otimização Combinatorial, Otimização de Planejamento, Problema do Caixeiro Viajante,Problema de Otimização de Rota de Veículos, Otimização de Layout de Circuitos, Otimização de Distribuição,Otimização em Negócios e Síntese de Circuitos Eletrônicos.

2 – Representação

A representação de possíveis soluções do espaço de busca de um problema define a estrutura docromossoma a ser manipulado pelo algoritmo. Tipicamente, a representação binária é a mais empregada por sersimples, fácil de manipular através dos operadores genéticos, fácil de ser transformada em inteiro ou real e,ainda, por facilitar a prova de teoremas.

Por exemplo, seja o problema de encontrar o valor máximo da função f(x) = x2 , x inteiro [0,63].Podemos representar as soluções do problema através de um cromossoma de 6 bits.

C1 0 0 1 0 0 1 representa x=9C2 0 0 0 1 0 0 representa x=4

Um binário também pode representar um número real XR ∈ [Xmin,Xmáx], com precisão de p casasdecimais. Para isso são necessários K bits estimados pela relação:

Equação 20

2k ≤ (Xmáx - Xmin) x 10p

A representação binária, entretanto, nem sempre pode ser empregada; o problema muitas vezes exigeum alfabeto de representações com mais símbolos. Qualquer que seja a representação ela deve ser capaz derepresentar todo o espaço de busca que se deseja investigar.

3 – Decodificação

A decodificação do cromossoma consiste basicamente na construção da solução real do problema). Oprocesso de decodificação constrói a solução para que esta seja avaliada pelo problema. A vantagem darepresentação binária é a fácil transformação para inteiro ou real.

Na transformação para número real considera-se o intervalo de valores ou comprimento contínuo dodomínio (C) dos reais de tal forma que

Equação 21

min12X

CXbX

nR −−

×=

Onde XR ∈ [Xmin,Xmáx]; Xb é o inteiro correspondente ao binário; n é o número de bits de do cromossoma; eC, é o comprimento do domínio da variável X, dado por C = |Xmáx – Xmin|.

4 – Avaliação

A avaliação é o elo entre o GA e o mundo externo. A avaliação é feita através de uma função que melhorrepresenta o problema e tem por objetivo fornecer uma medida de aptidão de cada indivíduo na populaçãocorrente. A função de avaliação é para um GA o que o meio ambiente é para seres humanos. Funções deavaliação são específicas de cada problema. No exemplo, a função matemática f(x) = x2 mede aptidão de cadaindivíduo. C1 é um indivíduo mais apto que C2.


Tabela 10

Cromossoma x f(x)C1 0 0 1 0 0 1 9 81C2 0 0 0 1 0 0 4 16

5 – Seleção

O processo de seleção em algoritmos genéticos seleciona indivíduos para a reprodução. A seleção ébaseada na aptidão dos indivíduos: indivíduos mais aptos têm maior probabilidade de serem escolhidos parareprodução.

Assim, se fi é a avaliação do indivíduo i na população corrente, a probabilidade pi do indivíduo i serselecionado é proporcional a

Equação 22

∑=

= n

ji

ii

f

fp

1

Onde n é o número de indivíduos na População.A seleção em GAs é tipicamente implementada por uma roleta onde cada indivíduo é representado por

uma fatia proporcional a sua aptidão relativa.

5 – Operadores Genéticos

Indivíduos selecionados (e reproduzidos na população seguinte) são recombinados sexualmente atravésdo operador de crossover. O operador de crossover é considerada a característica fundamental dos GAs. Pares degenitores são escolhidos aleatoriamente e novos indivíduos são criados a partir da troca do material genético. Osdescendentes serão diferentes de seus pais, mas com características genéticas de ambos os genitores. Porexemplo:

ponto de corte aleatórioG1 1 1 0 0 0 0G2 0 0 0 1 0 0

D1 1 1 0 1 0 0D2 0 0 0 0 0 0

Na sua forma mais simples o crossover de um ponto de corte (one-point crossover) corta os dois genitoresem uma posição aleatoriamente escolhida, criando dois possíveis descendentes:

D1 é um cromossoma mais apto que seus genitores, todavia D2 é um indivíduo medíocre (baixa avaliaçãoem f(x) = x2).

Os cromossomas criados a partir do operador de crossover são então submetidos a operação de mutação.Mutação é um operador exploratório que tem por objetivo aumentar a diversidade na população.

O operador de mutação altera o conteúdo de uma posição do cromossoma, com uma determinadaprobabilidade, em geral baixa (<1%).

C1 1 1 1 1 0 0 antesC1 1 1 1 1 0 1 depois da mutação

Há ainda um terceiro operador genético denominado inversão, que troca de posição dois genesaleatoriamente escolhidos. A importância deste operador é, no entanto, restrita a problemas com epistasia (forteinteração entre genes de um cromossoma) [MICH94].

7 – Inicialização da População

A inicialização da população determina o processo de criação dos indivíduos para o primeiro ciclo doalgoritmo. Tipicamente, a população inicial é formada a partir de indivíduos aleatoriamente criados. Populações


iniciais aleatórias podem ser semeadas com bons cromossomas para uma evolução mais rápida, quando seconhece, a priori, o valor de boas “sementes”.

8 – Parâmetros e Critérios de Parada

Em um algoritmo genético vários parâmetros controlam o processo evolucionário:

• Tamanho da População à número de pontos do espaço de busca sendo considerados em paralelo.• Taxa de Crossover à probabilidade de um indivíduo ser recombinado com outro.• Taxa de Mutação à probabilidade do conteúdo de cada posição/gene do cromossoma ser alterado.• Número de Geraçõesà total de ciclos de evolução de um GA.• Total de Indivíduos à total de tentativas (tamanho da população x número de gerações)

Os dois últimos parâmetros são em geral empregados como critério de parada de um algoritmo genético.Um algoritmo genético pode ser descrito como um processo contínuo que repete ciclos de evolução controladospor um critério de parada, conforme apresentado pela figura abaixo:

Problema PopulaçãoInicial/

Corrente

OperadoresGenéticos

SeleçãoCritério deTérmino

Representação

F(x)

GenitoresDescendentes

Figura 48

8.3. FUNDAMENTOS MATEMÁTICOS DE ALGORITMOS GENÉTICOS

Podemos compreender melhor o princípio de funcionamento de algoritmos genéticos a partir da Teoria deSchema (padrões) formulada por John Holland em 1975.

John Holland definiu schema como um padrão que descreve um conjunto de cromossomas comsimilaridades em algumas posições.

Para representar schemata (plural de schema) utiliza-se um símbolo adicional "S".Assim, para um espaço de busca representado por KL existem (K+1) L schemata.

K ≡ número de símbolos do alfabetoL ≡ comprimento do cromossoma

Seja K = 2 e L = 3 definido em espaço de busca de 8 pontos. Seja o schema H = 11S. H descreve oconjunto de elementos 111 e 110. H refere-se a conjectura que a razão pela qual 111 (ou 110) é um bom (ou mal)indivíduo são os dois bits mais significativos iguais a 1, não importando (don't care) os demais. Esta conjecturapossui dois possíveis representantes que podem ou não estar presentes em determinada geração do GA.

Para compreendermos melhor porque os GAs funcionam, basta analisarmos o efeito dos processos deseleção, recombinação e mutação sobre schemata. Utiliza-se nesta análise duas definições:

• O(H): ordem ou especificidade de um schema, como o número de posições fixas diferentes de S; e• d(H): comprimento do schema, como a distância entre a 1a e a última posições fixas.

8.3.1. Análise do Efeito da Seleção


Seja m(H, t) o número de representações de H em um ciclo t do algoritmo com n indivíduos napopulação. Assim, podemos calcular o número provável de representantes de H no próximo ciclo, seguintecomo:

Equação 23

∑

∑

=

∈×=+ n

jj

Hii

f

f n) m(H, t

1

1

Define-se f(H) como a aptidão média do schema H, dada por:

Equação 24

m(H,t)

ff(H) Hi

i∑∈=

Assim, podemos rescrever m(H, t+1) através da equação abaixo:

Equação 25

∑=

××=+ n

jjf

f(H) n m(H, t) )m(H, t

1

1

A aptidão média da população, dada pela equação a seguir, nos permite fazer uma última transformaçãona fórmula de m(H, t+1).

Equação 26

n

ff

n

jj∑

== 1

Equação 27

fHf

tHmtHm)(

),()1,( ×=+

A interpretação desta equação reflete o efeito da seleção em GAs:

1) Schemata (padrões) com aptidão acima da média tendem a proliferar nas gerações seguintes.2) Schemata com aptidão abaixo da média tendem a desaparecer.

Para estimarmos a eficiência do processo de evolução, suponha um schema H acima (ou abaixo) damédia de um fator C estacionário, a partir de t = 0. Assim temos:

Equação 28

)1(),(),(),( CtHmf

fCftHmtHm +×=+×=

portanto,

Equação 29

tCHmtHm )1()0,(),( +×=


Isto significa que o número de representantes de H em gerações sucessivas cresce (ou decresce)exponencialmente durante a evolução.

8.3.2. Análise do Efeito do Crossover

Seja pd a probabilidade de destruição de um schema H pelo crossover de um ponto:

Equação 30

1)(

)(−

=L

HHpd

δ

Portanto,

Equação 31

1)(

1)(−

−=L

HHps

δ

é a probabilidade de sobrevivência desse padrão.

Sendo pc a taxa de aplicação de crossover e considerando-se que o par genitor de um cromossoma poderecuperar parte de um padrão destruído pelo crossover, temos a desigualdade:

Equação 32

1)(

1−

×−≥L

Hpp cs

δ

Isto significa que schemata curtos tem maior probabilidade de sobrevivência (se manter intacto) após ocrossover.

8.3.3. Análise do Efeito da Mutação

Seja pm a probabilidade do operador de mutação ser aplicado a uma determinada posição do cromossoma.Assim a probabilidade de sobrevivência do cromossoma é

Equação 33

)()1( HOms pp −=

Para taxas de mutação pm << 1, temos

Equação 34

)(1 HOpp ms ×−≅

Isto significa que cromossomas de baixa ordem tem maiores chances de não serem destruídos pelamutação.

Combinando o efeito da seleção, crossover e mutação, temos

Equação 35

[ ])(11)(

1)(

),()1,( HOpL

Hp

fHf

tHmtHm mc ×−×

−×−××≥+ δ

Teorema fundamental de GAs:


“Schemata curtos e de baixa ordem tendem a se proliferar ou desaparecer nas gerações seguintes, deacordo com a aptidão média”.

8.4. DESEMPENHO DE ALGORITMO GENÉTICOS

Algoritmos genéticos são sistemas não lineares com comportamento fortemente ecológico. GAscombinam mudanças aleatórias com processos probabilísticos. GAs são, portanto, estocásticos: dificilmenterepetem um resultado de um experimento para outro.

O desempenho de um algoritmo genético é medido pelo grau de evolução alcançado durante todo oprocesso evolucionário (experimento). Devido à natureza estocástica dos GAs é necessário se avaliar o resultadomédio de vários experimentos de um GA, para se ter uma idéia de seu desempenho.

As principais medidas de desempenho são:

1. Curva da média dos melhores cromossomas a cada ciclo em vários experimentos.2. Curva on-line da média da avaliação de todos os indivíduos até um determinado instante t em um

experimento.3. Curva off-line da média da avaliação do melhores indivíduos até um instante t em um experimento.

A curva média dos melhores indivíduos em vários experimentos apresenta o desempenho médio de umGA e serve para ajuste de parâmetros.

A curva on-line mede a velocidade com que o GA consegue produzir boas soluções para o consumo "on-line" das soluções.

A curva off- line mede o grau de convergência do GA na criação de soluções mais aptas, geradas off- lineem relação ao problema.

8.5. TÉCNICAS, PARÂMETROS E OPERADORES GENÉTICOS

Técnicas, parâmetros e tipos de operadores genéticos afetam significativamente o desempenho de umalgoritmo genético. Em geral, o algoritmo genético é extremamente sensível a introdução ou combinação detécnicas empregadas. A escolha de técnicas, parâmetros e tipos de operadores é empírica, porém em sintoniacom o problema.

Podemos classificar as técnicas empregadas em GAs nas seguintes classes:

1- Técnica de Reprodução2- Técnica de Aptidão3- Técnica de Interpolação de Parâmetros

Quanto aos operadores genéticos, os principais tipos são:

1- Crossover de Um- ponto2- Crossover de Dois- pontos3- Crossover Uniforme.

8.5.1. Técnicas de Reprodução:

Essas técnicas determinam o critério de substituição dos indivíduos de uma população para a próximageração. Existem basicamente os seguintes métodos:

1- Troca de toda população:A cada ciclo, N novos indivíduos são criados substituindo a população anterior: N/2 pares são escolhidos

para o acasalamento, gerando N descendentes.

2- Troca de toda a população com elitismo:Todos os cromossomas são substituídos, sendo o cromossoma mais apto da população corrente copiado

na população seguinte.

3- Troca parcial da população:


Gera M indivíduos (M<N), que substituem os piores indivíduos da população corrente. Técnica elitistaque mantém população mais estática, permitindo, portanto, a utilização de operadores menos conservadorescomo o crossover uniforme.

4- Troca parcial da população sem duplicados:Não permite a presença de indivíduos duplicados na população. Garante, assim, o melhor aproveitamento

do paralelismo intrínseco dos GAs (N pontos diferentes do espaço de busca sendo avaliados a cada ciclo), porémimplica em “overhead” para a detecção de duplicados.

8.5.2. Técnicas de Aptidão:

Diz respeito a maneira pela qual as aptidões dos cromossomas em uma população são numericamenteatribuídas.

Intuitivamente, o método mais simples de atribuir uma aptidão a um cromossoma é utilizar o valornumérico do resultado da avaliação deste cromossoma pela função de avaliação. Há, no entanto, dois problemasimportantes associados a este método:

- competição próxima: indivíduos cuja a aptidão relativa são numericamente próximas.- super indivíduos: indivíduos com avaliação muitas vezes superior a média, capaz de dominar o processo de

seleção, fazendo com que o GA convirja prematuramente para um ótimo local.

Para contornar esses problemas utilizam-se métodos de transformação da avaliação numérica doscromossomas em uma aptidão. Os métodos mais empregados são: “windowing”, "rank- based" e a normalizaçãolinear.[DAVI96]. Dentre estes a normalização linear é a mais simples, eficiente nos dois problemas e, ainda,parametrizável.

O método de normalização linear consiste em ordenar os cromossomas em ordem crescente de avaliação(i = 0 corresponde ao indivíduo menos apto) e atribuir valores de aptidões aos cromossomas, linearmente, entreum valor mínimo e um máximo, distanciados de um valor fixo (taxa de decremento) Equation 17.

Equation 17

)1(1

)( −×−−+≡ i

nmínmáx

mínAi

No exemplo da Tabela 11 o método reduz o domínio exercido por super indivíduos (6) e aumenta apressão seletiva entre indivíduos com avaliação próxima (5, 4, 3, 2) em função da taxa de decremento, emfunção da taxa de incremento.

Tabela 11

CROMOSSOMA 6 5 4 3 2 1Avaliação 200 15 14 13 10 9Aptidão (taxa=1) 100 99 98 97 96 95Aptidão (taxa=20) 100 80 60 40 20 1

8.5.3. Técnicas de Interpolação de Parâmetros:

A interpolação de parâmetros de um GA tem por objetivo buscar o valor ideal de um determinadoparâmetro para cada ciclo, durante toda a evolução. Durante a evolução de um GA alguns aspectos estãofortemente relacionados:- a convergência do algoritmo- a aptidão dos cromossomas- as taxas e parâmetros

Por exemplo, é intuitivamente óbvio que a taxa de aplicação do crossover seja maior nas primeirasgerações quando a população se apresenta dispersar no espaço de busca. Após várias gerações os indivíduos


tendem a apresentar, na sua maioria, características muito similares. Um aumento da taxa de mutação nesta fasede evolução irá dispersas a população, trazendo novo material genético para a formação de melhores indivíduos.

A interpolação de parâmetros pode ser linear ou adaptativa. Na interpolação linear uma taxa ou umparâmetro é variado entre um valor inicial e final, através de ajustes fixos, linearmente a cada K gerações.

A interpolação adaptativa, normalmente empregada para ajuste da taxa de aplicação de operadores,considera o desempenho destes operadores nos ciclos anteriores. Este desempenho é medido em função dosucesso destes operadores na criação de melhores indivíduos. Este esquema requer um processo de pontuação aindivíduos e seus descendentes, envolvendo razoável “overhead” computacional. O efeito, no entanto, é atingirtrajetórias quase ótimas para parâmetro, durante toda a evolução.

8.5.4. Operadores Genéticos

Operadores genéticos se classificam em:- operadores de recombinação (crossover)- operadores de mutação- operadores de inversão (usados em problemas com epistasia)- operadores específicos ao domínio do problema.

Dentre estes, os operadores de crossover, devido a sua importância fundamental nos GAs, apresentamvariações que merecem destaque.

Crossover de Dois Pontos:

Executa a recombinação de dois indivíduos a partir de dois pontos escolhidos aleatoriamente. Esteoperador é capaz de combinar schemata com posições fixas nas extremidades, como no exemplo abaixo.

H1 1 1 S S S S S 0H2 S S S 1 0 1 S S

Crossover Uniforme:

O crossover de dois pontos também apresenta limitações na recombinação de schemata.O crossover uniforme, por sua vez, é capaz de recombinar quaisquer posições entre dois genitores. Este

operador utiliza um padrão (palavra binária) escolhida aleatoriamente para designar os bits selecionados em cadagenitor na criação dos descendentes. Por exemplo:

G1 1 1 0 0 1 0 1G2 0 1 1 1 1 1 0

Padrão 0 1 1 0 1 0 0

D1 0 1 0 1 1 1 0D2 1 1 1 0 1 0 1

O crossover uniforme apresenta um poder de destruição maior que o crossover de um ponto e dois pontosque preservam os códigos (schemata curtos) compactos. O crossover uniforme pode prejudicar a formação depadrões a partir de schemata curtos. Sua utilização deve ser, portanto, em ambientes altamente elitistas como nareprodução parcial da população, que garantem a permanência dos melhores indivíduos.

8.6. MODELAGEM DE ALGORITMOS GENÉTICOS PARA DATA MINING

8.6.1. CLASSIFICAÇÃO POR EVOLUÇÃO DE REGRAS DE ASSOCIAÇÃO

Uma regra de associação caracteriza um relacionamento de atributos preditivos com um atributo objetivo,ou atributo meta. Os atributos preditivos compõem a condição de uma regra (parte SE) e o atributo objetivo, a


consequência (parte ENTÃO). O objetivo do algoritmo genético nesta tarefa é evoluir regras de associação, demodo que uma regra possa representar cada vez melhor as características de um determinado grupo de registros.Uma regra é considerada melhor que outra sempre que esta gerar soluções com mais qualidade. As medidas dequalidade são discutidas a seguir.

ACURÁCIA E ABRANGÊNCIA DE UMA REGRA

A acurácia de uma regra mede o quão boa é a sua solução em função do grau de certeza, ou confiança,obtido através do conjunto de exemplos. Ou seja, é o grau que mede o quão bem a teoria descoberta (neste caso,uma regra) se aplica aos dados [KLÖS96].

Considere C um conjunto de atributos preditivos (condição da regra) e P, a previsão, ou classe do registro.Uma regra de associação da forma SE C ENTÃO P tem uma boa acurácia, sempre que a Equação 36 tiver umvalor “aceitável”.

Equação 36

Acurácia = |C ∩ P| / (|C ∩ P| + |C ∩ ~P|)

A interpretação dessa equação pode ser compreendida como o número de registros que satisfazem C e Pdividido pelo total de registros que satisfazem C. Desse modo o melhor resultado (resultado máximo) é 1(100%), significando que todos os registros que uma determinada regra abrange são da mesma classe, ou seja,não existem conflitos. Entretanto, na ocorrência de conflitos, representado por |C ∩ ~P|, uma regra abrangeregistros que satisfazem C, porém não caracterizam a classe meta/objetivo, P. Nessa situação o valor da acuráciapode compreender o intervalo [0 a 100] e, o usuário, segundo algum critério, perceberá se esse valor é aceitável,ou não.

A abrangência de uma regra é definida como sendo o número de registros que satisfazem C e P divididopelo total de registros que satisfazem P. A Equação 37 representa essa definição.

Equação 37

Abrangência = |C ∩ P| / (|C ∩ P| + |~C ∩ P|)

A interpretação da abrangência indica quantos registros uma determinada regra cobriu. Semelhante aacurácia, seu valor máximo é 100%, significando que todos os possíveis registros de uma determinada classemeta foram cobertos por essa regra. Sempre que a parcela |~C ∩ P| for diferente de zero, o valor da abrangênciaestará no intervalo [0, 100], indicando que ainda existem registros da classe meta não capturados por essa regra.

Baseado nessas definições, acurácia e abrangência, percebe-se que a qualidade de uma regra é acombinação destes dois valores, que quanto maiores melhor. Portanto, a qualidade de uma regra é diretamenteproporcional às estatísticas de acurácia e abrangência.

MODELAGEM DO ALGORITMO GENÉTICO

A modelagem do algoritmo genético envolve principalmente a definição da representação decromossomas, operadores, e função de avaliação. Nas próximas seções são apresentados cada um dessescomponentes do modelo, e ainda métodos de inicialização da população, técnicas evolucionárias e algunsparâmetros que buscam ajustar o modelo para a busca de regras com soluções de boa qualidade.

8.6.2. Representação de Cromossomas

Um cromossoma representa uma regra de associação entre os atributos preditivos e o atributo objetivo, ouclasse. Uma regra de associação é da forma SE (A1 e A2 e ... An) ENTÃO P. O conjunto {A1, A2 , ... An}representa os atributos preditivos e, P o valor da classe meta. Os atributos são representados categoricamente ouquantitativamente. Atributos categóricos, ou discretos representam um conjunto finito de valores, ou valoresmapeados num conjunto de números inteiros [KLÖS96]. Um atributo categórico numa determinada tupla sópode assumir um único valor. Por exemplo, supõe-se o atributo SEXO numa tupla que representa dados de umapessoa; esse atributo só pode assumir os valores “Masculino” ou “Feminino”. Entretanto, atributos quantitativos,ou contínuos, representam faixas de valores no domínio do atributo, os quais são coerentes com um subconjuntode números reais [KLÖS96]. Supõe-se agora o atributo RENDA SALARIAL; uma tupla ou um conjunto detuplas podem representar faixas de renda. Por exemplo, 1 a 5 salários mínimos, 6 a 10, 11 a 15, e assim por


diante. Baseado nessas duas definições de atributos, categóricos e quantitativos, que são suficientes pararepresentar os possíveis domínios do problema, o cromossoma do modelo desenvolvido possui a seguinterepresentação:

Atributo 1 Atributo 2 Atributo N

mím Máx mím Máx mím Máx

Limite inferiorValor mínimo

Limite superiorValor máximo

Figura 49: Representação do cromossoma para a tarefa de classificação

Na Figura 49 um gene representa um atributo preditivo. Cada gene possui dois campos: um valor mínimoe um valor máximo. Os valores mínimo e máximo representam os limites inferiores e superiores da faixa em queum atributo preditivo definido como quantitativo está inserido. No caso de atributos categóricos o campo devalor máximo não tem utilidade.

Com essa representação pode-se formular regras da seguinte forma:SE [ (Atributo 1 ≥ mím 1) e (Atributo 1 ≤ máx 1) e (Atributo 2 ≥ mím 2) e (Atributo 2 ≤ máx 2) e (Atributo 3 = mím 3) . . . e (Atributo N ≥ mím N) e (Atributo N ≤ máx N) ] ENTÃO Atributo Objetivo = P, onde mím X e máx X indicam os valores mínimos e máximos de

cada atributo preditivo definido como quantitativo, e P é o valor do Atributo Objetivo informado como meta noinício do processo. Nesse exemplo o Atributo 3 é considerado categórico e, consequentemente, não aparece umlimite superior.

A escolha dessa representação se deve, principalmente, a sua facilidade de interpretação, visto que éintuitiva a visualização de um domínio de variáveis na forma de intervalo. Além disso, é uma representaçãosimples, capaz de aceitar a utilização de operadores genéticos notoriamente conhecidos, facilitando assim, umafácil manipulação estrutural do modelo. Outro fator importante é a possibilidade caracterizar os dois tipos deatributos, categóricos e quantitativos, em um único tipo de gene. Ou seja, o gene se adapta a qualquer uma dasduas definições.

8.6.3. Operadores Genéticos

Os operadores genéticos atuam no processo de reprodução criando e/ou alterando indivíduos.Operadores genéticos (crossover e mutação) atuam em sintonia com a representação dos cromossomas.

O operador de crossover, proveniente da reprodução de sexuada, foi adaptado aos Algoritmos Genéticoscom o intuito de permitir a recombinação das informações contidas em duas soluções distintas (cromossomas),fazendo com que novas soluções sejam geradas pela “mistura de material genético dos pais” [COST97].

Os tipos de operadores utilizados neste trabalho foram:• Crossover de um ponto• Crossover de dois pontos• Crossover uniforme• Crossover de média

O crossover de um ponto recombina duas soluções em um único ponto de corte; no crossover de doissão dois os pontos escolhidos como referência para a troca de valor dos atributos (genes); enquanto que no


uniforme é utilizada uma máscara determinando em que posições haverá a troca do valor dos genes. Já nocrossover de média, dois genitores recombinam-se gerando “um único filho”. Os genes a partir dos quais écalculada a média, especificamente nesse trabalho, são genes que representam atributos preditivos quantitativos.

Tabela 12: Exemplo de crossover de média

Pai (1)

12 26 80 10 4 0

Filho (1)

21 18 80 15 4 1

30 10 32 20 0 2

Pai (2)

21 18 32 15 0 1

Filho (2)

Antes Depois

Nota-se que a Tabela 12 mostra 2 filhos gerados, que são: Filho (1) e Filho (2), entretanto, nesse modelofoi escolhido apenas um filho. Os valores sublinhados representam valores de atributos quantitativos, que sãopassíveis de cálculo de média.

Dois operadores de mutação foram implementados neste trabalho:• Mutação Simples• Mutação don’t care

Na mutação simples um gene é alterado, inserindo-se um novo valor pertencente ao seu domínio; ooperador de mutação don’t care seleciona aleatoriamente um gene, e este passa a conter valores que representamtodo seu domínio. Em mineração de dados, isso significa que o gene escolhido é considerado don’t care, isto é,não contribui para a representatividade de uma regra. Por exemplo, suponha um banco de dados de empregadoscom os atributos SEXO e IDADE. Observa-se que na regra “SE SEXO é masculino ou SEXO é feminino eIDADE é maior que 20 e menor que 30 ENTÃO é funcionário novo” o atributo SEXO pode ser omitido, pois éum conhecimento sem valor.

Tais operadores foram implementados em função de suas características notoriamente conhecidas.Entretanto, nesse trabalho de mineração de dados, não se conhecia a priori quais operadores eram mais ou menosadequados para a tarefa proposta. Deste modo, o modelo permite que a cada reprodução, um único operador sejaselecionado, em função de uma taxa de probabilidade informada pelo usuário. Esta característica fornece aomodelo a liberdade de poder utilizar todos os operadores disponíveis durante o processo evolutivo.

Outro fator importante na escolha desses operadores genéticos nesse trabalho se deve a sintonia com aestrutura do modelo, visto que um cromossoma, representa uma regra de maneira explicita e, o fato de um generepresentar um intervalo de números inteiros, todos os operadores implementados se ajustam às característicasdesejadas como objetivo da tarefa de KDD.

8.6.4. Inicialização da População

Foram implementados diversos métodos de inicialização da população. Tais métodos ajudam arestringir o espaço de busca do algoritmo genético. A seguir segue os métodos de inicialização implementados.

• Inicialização aleatória sem sementes:Ø Na faixa de valores do atributo que ocorrem para o atributo objetivo especificado;Ø Na faixa de valores do atributo que ocorrem para o atributo objetivo especificado, incluindo

o valor médio;Ø Na faixa de valores do atributo que ocorrem para o atributo objetivo especificado, incluindo

o valor mediano.• Inicialização aleatória com sementes de evoluções anteriores;• Sementes de registros aleatórios do Banco de Dados.Ao especificar o atributo objetivo, que é a parte ENTÃO da regra de associação, pode-se identificar quais

são os valores máximo e mínimo de cada atributo preditivo para registros cujo o atributo objetivo tem valor igualao especificado. Os valores máximo e mínimo de todas as tuplas do banco de dados resulta, em geral, numa faixade valores mais extensa. Desse modo, ao inicializar-se a população “apenas” com genes na faixa de valores que


ocorrem para o atributo objetivo, evita-se a geração de regras cujos valores dos genes não são representativos. ATabela 13 mostra um banco de dados ilustrativo onde o atributo objetivo é representado pelo atributo CLASSE.Os valores máximo e mínimo calculados para o ATRIBUTO 1 são:

Ø (1, 100) considerando-se “todas” as tuplas, indiferente ao valor de sua respectiva classe;Ø (17; 33) considerando-se “apenas” as tuplas com valor do atributo objetivo (CLASSE) igual a 1.

Supondo que a parte ENTÃO da regra especifica o valor 1, nota-se que o domínio do ATRIBUTO 1 ébem menor, diminuindo assim o espaço de busca do AG.

Tabela 13: Banco de dados exemplo para cálculo da inicialização da população

ATRIBUTO 1 ATRIBUTO 2 CLASSE20 99 118 3 11 200 2

25 3 130 800 228 2 133 3 1

100 1 223 3 117 8 1

Na inclusão do valor médio, calcula-se a média encontrada para todos os atributos preditivos apenasconsiderando-se as tuplas que possuem o valor do atributo objetivo igual ao valor especificado. A Figura 50representa esquematicamente a inicialização de um atributo preditivo.

Faixa deValores do

gene Valor Médio

Valor Máximo

Valor Mínimo

Limite Superior Aleatório

Limite Inferior Aleatório

Figura 50: Representação esquemática da inicialização de um atributo preditivo

Uma vez calculado os valores máximo e mínimo e o valor médio de um atributo preditivo, escolhe-sealeatoriamente um valor na faixa [Valor Máximo; Valor Médio] e um valor na faixa [Valor Médio; ValorMínimo]. Esses dois valores são os valores superior e inferior escolhidos para inicializar um determinadoatributo preditivo em um cromossoma (Figura 50). Essa inicialização possui a vantagem de incluir o valor médiode um determinado atributo preditivo, restringindo o espaço de busca. Referindo-se a Tabela 13, o valor médiodo ATRIBUTO 1 é 23,43. Desse modo, o AG procura valores de inicialização que sempre incorporem essevalor.

A vantagem dessa inicialização está diretamente relacionada à probabilidade dos valores dos atributosocorrerem dentro da faixa de valores dos genes e, particularmente englobando o valor médio. Dessa forma,torna-se mais provável a escolha de valores afinados com a instância real da base de dados.

A mediana de um conjunto de medidas é um valor x tal que, no máximo metade das medidas são menoresdo que x e no máximo metade das medidas são maiores do que x. Para encontrar-se o valor mediano de cadaatributo preditivo, primeiro, ordena-se os valores encontrados em cada tupla do banco de dados que possui oatributo objetivo igual ao especificado. Segundo, escolhe-se o valor mediano como sendo o valor encontrado naposição [inteiro(n/2) + 1], onde inteiro representa uma função que retorna a parte inteira do argumento n/2 e, n é


o número de tuplas. Utilizando o ATRIBUTO 2 da Tabela 13 e, a CLASSE como atributo objetivo de valor 1,tem-se o seguinte procedimento:

Tabela 14: Passos para encontrar o valor mediano de um determinado atributo

ATRIBUTO 2 CLASSE ATRIBUTO 2INSTÂNCIA DO BANCO DE DADOS SELECIONAR

Passo 1ORDENAR

Passo 2VALOR

MEDIANO99 1 99 23 1 3 3

200 23 1 3 3

800 22 1 2 3 33 1 3 31 23 1 3 88 1 8 99

O primeiro passo é selecionar apenas os valores dos registros do atributo especificado que possuem oatributo CLASSE com valor 1. O passo seguinte consiste em ordenar esses números. E, no terceiro e últimopasso, escolhe-se o valor da posição [inteiro(7/2) + 1] = valor[4] = 3.

Percebe-se que os valores máximo e mínimo para o ATRIBUTO 2, considerando-se o valor especificadopara o atributo CLASSE = 1 está no intervalo (2; 99), enquanto que os limites considerados para a base completaestá no intervalo (1, 800). Entretanto, o valor com maior frequência é 3. Desse modo, deseja-se que o AG gerevalores para os genes que probabilisticamente estejam com maior proximidade desse valor, sem que o restantedo domínio seja afetado. Esquematicamente, a Figura 50 representa essa inicialização, a única diferença está natroca do Valor Médio pelo Valor Mediano.

A média mede o centro de gravidade de uma conjunto de dados e é consequentemente influenciada porvalores extremos, ao contrário da mediana que os ignora. A mediana qualifica-se como um método deinicialização que busca a localização do ponto que divide os dados em dois grupos: os superiores e os inferioresa x.

O outro tipo de inicialização é através de sementes. Uma semente é um cromossoma evoluído emexecuções anteriores do algoritmo genético. Ao iniciar-se um novo experimento, esse cromossoma é inserido napopulação inicial de modo a contribuir com o seu material genético já refinado. Neste procedimento deinicialização apenas n cromossomas são inseridos, o restante dos cromossomas (Tamanho_pop – n) quecompletam uma população são escolhidos aleatoriamente incluindo o valor mediano.

O último método de inicialização é através da escolha aleatória de registros do banco de dados. Umpercentual da população, fornecido pelo usuário, será povoado com os valores dos registros do banco de dados.Nesse caso, ao preencher um cromossoma, os valores dos campos mínimo e máximo são iguais ao valor doatributo correspondente no bando de dados. O restante da população é escolhido aleatoriamente incluindo o valormediano. A vantagem dessa inicialização está no fato de inicialmente apresentar regras com abrangênciadiferente de zero, acelerando o processo de busca do AG.

8.6.5. Técnicas e Parâmetros

Várias técnicas e parâmetros foram utilizados na construção do modelo com o objetivo de melhorar odesempenho do algoritmo genético.

As principais técnicas e parâmetros empregados são:• Normalização Linear;• Multiplicador do Valor Máximo na Normalização Linear;• Elitismo• Sementes para próximos experimento;• Valores inicial e final para interpolação de taxas de probabilidade;• Parâmetros básicos.A primeira delas foi a Normalização Linear, que classifica os cromossomas de acordo com a ordem de

avaliação, atribuindo aptidões linearmente distribuídas entre os valores: Valor Mínimo a Valor Máximo, que sãoparâmetros da técnica. Desta forma, o cromossoma com pior avaliação tem aptidão igual ao valor mínimo, e o demelhor avaliação, valor máximo. A probabilidade de um cromossoma ser selecionado aumenta linearmente de


acordo com sua posição no ranking [COST97]. Essa técnica reduz a influência de super indivíduos, que sãocromossomas que possuem uma avaliação muito melhor que a dos demais e que portanto, tendem a dominarrapidamente a população e ainda reduzem a competição próxima entre cromossomas quando a população tende aconvergir. Um parâmetro, chamado multiplicador, foi criado para multiplicar o Valor Máximo em função doTamanho da População de modo a alterar a pressão seletiva sobre os melhores.

Outra técnica conhecida e implementada foi a do elitismo, que força a permanência do melhorcromossoma de uma geração, ou dos n melhores cromossomas, na geração seguinte. Essa técnica foi estendida,fazendo-se com que esse, ou esses, melhores cromossomas também permaneçam no próximo experimento,através de um parâmetro chamado semente.

A interpolação de parâmetros procura enfatizar diferentes aspectos da busca em diferentes momentos daconvergência. Dessa forma, os valores das taxas de probabilidade para escolha de cada operador genético nareprodução são alterados linearmente no decorrer da execução do AG, a partir de um valor inicial até um valorfinal, especificados como parâmetros.

Além dos parâmetros já citados, foi implementado o conjunto de parâmetros básicos citados abaixo e sãopressupostos conhecido pelo leitor. Mais detalhes sobre esses parâmetros podem ser encontrados em [COST97],[DASG97].

Parâmetros básicos de um Algoritmo GenéticoNOME FUNÇÃO

Tamanho da População Número de indivíduos ou soluções que são produzidasa cada geração

Taxas de Operadores (crossover, mutação, ...) Taxa de probabilidade de um operador ser escolhidopara reprodução de indivíduos

Total de rodadas/número de experimentos Número de experimentos ou de evoluções completasdo algoritmo genético

Total de gerações Número de populações avaliadas a cada experimento

Por exemplo, supondo um algoritmo genético parametrizado com 40 rodadas, 80 gerações e 100indivíduos na população, esse cria 8000 indivíduos durante uma evolução completa e 320000 durante todo oprocesso.

Tratando-se de objetivos do modelo, criou-se dois tipos. O primeiro busca a evolução da “melhorregra”, enquanto que o segundo busca “todas as regras” que caracterizam o conjunto de exemplos especificado.O primeiro tipo fornece as medidas visuais de performance para avaliar o modelo, tais como: gráficos da médiadas aptidões dos melhores indivíduos, de toda a população, e do melhor indivíduo; além da média da acurácia eabrangência dos melhores indivíduos e, do melhor. No segundo tipo esses dados visuais já não refletem odesempenho do modelo, pois em função da existência de critérios de parada do AG, através de parâmetrosfornecidos pelo usuário, esses dados não possuem consistência para avaliação.

Os critérios de parada do algoritmo genético são:• Tolerância da melhor regra – o usuário informa o número de gerações cujo o algoritmo genético deve

monitorar o melhor indivíduo, a fim de perceber se a melhor regra até o momento não sofreunenhuma alteração. Caso a melhor regra tenha se mantido constante, ou seja, não evoluiu durante asn gerações, essa será armazenada em um banco de regras.

• Número máximo de regras armazenadas no banco de regras – O usuário informa o número máximo deregras que descrevem o conjunto de exemplos especificado. Logo, a medida que a evolução vaiocorrendo, regras vão sendo armazenadas e, caso no número de regras armazenadas chegue ao valormáximo, o AG será finalizado.

• A não existência de registros no conjunto de exemplos especificado – Caso todos os registros já tenhamsido cobertos pelas regras no banco de regras, então o processo é finalizado.

Sempre que uma regra é inserida no banco de regras, o modelo retira os registros cobertos por ela e,inicia uma nova evolução/experimento. Uma regra é inserida no banco de regras sempre que o critério de parada“Tolerância da melhor regra” for atingido, ou pela finalização de um experimento através dos parâmetrosTamanho da População, Total de Rodadas e Total de gerações. Um detalhe importante é que são inseridas apenasregras que possuem abrangência diferente de zero. Em função desses critérios, apenas a visualização textual dasregras refletem a performance do modelo.

8.6.6. Funções de Avaliação


A função de avaliação de um Algoritmo Genético oferece uma medida de aptidão que determina aadequabilidade de uma solução para um problema particular. Portanto, de modo geral, a performance de um AGdepende da medida da aptidão [SANK96]. As seções a seguir descrevem as funções de avaliação utilizadas nomodelo do algoritmo genético para classificação de registros em mineração de dados.

Número-Atributos

Essa função de avaliação acumula ou subtrai o número de atributos cobertos por uma determinada regrano banco de dados, dependendo do valor do atributo objetivo. Ou seja, se o valor do atributo objetivo numdeterminado registro satisfaz a especificação do lado direito da regra (parte ENTÃO), adiciona-se número deatributos cobertos pela regra, caso contrário, subtrai. A Tabela 15 mostra um banco de dados exemplo para ocálculo da aptidão de uma regra, composto por dois atributos preditivos (1 e 2) e um atributo meta, chamadoCLASSE.

Tabela 15: Exemplo fictício de um BD utilizado para cálculo de função de avaliação

ATRIBUTO_1 ATRIBUTO_2 CLASSE10 5 115 38 220 9 1

Suponha a regra:“SE ATRIBUTO_1 ≥ 8 e ATRIBUTO_1 ≤ 18 e ATRIBUTO_2 ≥ 3 e ATRIBUTO_2 ≤ 10 ENTÃO CLASSE = 1”Suponha A, o valor da aptidão dessa regra, inicialmente com valor zero. Essa regra acerta o primeiro e o

segundo atributo do primeiro registro, além do atributo CLASSE, que satisfaz o atributo objetivo especificado,logo A é adicionado do valor 2 (A = 2). No segundo registro apenas o segundo atributo é satisfeito, porém oatributo CLASSE não é o especificado, logo A é subtraído do valor 1 (A = 1). No terceiro registro o segundoatributo e o valor da classe são satisfeitos, incrementando A de mais 1, resultando como aptidão final para essaregra o valor dois (A = 2).

Distância-Ótima

A função de avaliação Distância-Ótima considera o número de atributos satisfeitos por uma regra comoum ponto no espaço N-dimensional. N representa o número de atributos envolvidos na evolução genética. Noexemplo da Tabela 15, N possui o valor 2, visto que apenas 2 atributos preditivos são considerados. Nessecenário, ao estabelecer o valor do atributo objetivo (parte ENTÃO), conhece-se a priori qual o ponto ótimo, poissabe-se exatamente quantos registros do banco de dados satisfazem o valor do atributo objetivo especificado.Supondo CLASSE igual a 1, a Tabela 15 identifica que 2 registros são satisfeitos. A função Distância-Ótimacalcula a distância da regra corrente em relação ao ponto ótimo.

No. Registros comATRIBUTO 1 correto

No. Registros comATRIBUTO 2 correto

Ponto Ótimo

Distância1

1

2

2


Figura 51: Diagrama esquemático para a interpretação da função de avaliação Distância-Ótima

A Figura 51 mostra um gráfico que interpreta o cálculo da distância ótima para a função de avaliação.Considerando o exemplo representado pela regra de associação da seção anterior, “SE ATRIBUTO_1 ≥ 8 eATRIBUTO_1 ≤ 18 e ATRIBUTO_2 ≥ 3 e ATRIBUTO_2 ≤ 10 ENTÃO CLASSE = 1”, pode-se calcular oponto no espaço 2D, que é (0; 2). A primeira cláusula da regra, que se relaciona com o ATRIBUTO_1, emboraacerte dois registros do banco de dados, “apenas” um refere-se a CLASSE 1. Ou seja, o contador de atributoscorretos referente ao ATRIBUTO_1, foi incrementado de 1 por ter acertado o primeiro registro e por satisfazer aclasse especificada; entretanto foi decrementado de 1 por ter acertado o segundo registro que “não” satisfaz aclasse especificada. Na segunda cláusula, dois registros são cobertos e os dois pertencem a “mesma” classe, queé a especificada na parte ENTÃO da regra. Uma vez conhecido o ponto da regra corrente no espaço N-Dimensional, calcula-se a distância Euclidiana desse ponto ao ponto ótimo. A distância Euclidiana é calculadapela Equação 38.

Equação 38: Distância Euclidiana

Recompensa-Atributos

Semelhante a função Número-Atributos, a função Recompensa-Atributos tem o mesmo propósito,maximizar o número de atributos cobertos por uma regra, entretanto sempre que uma regra acerta “todos” osatributos de um registro e sua respectiva classe, sua avaliação é recompensada, caso contrário, é penalizada.Quando uma regra acerta parcialmente os atributos, sua avaliação é incrementada da seguinte parcela: Númerode atributos corretos dividido pelo total de atributos, caso a classe do registro seja a especificada na parteENTÃO da regra; caso contrário a avaliação é penalizada por essa mesma parcela.

CBayesianos

Essa função de avaliação é a Equação 6. Nela são consideradas as probabilidades de um determinadovalor de atributo ocorrer dado que um valor especificado como atributo objetivo ocorre.

P(A1 = a1| C = c) * P(A2 = a2| C = c) * ... P(Ak = ak| C = c)

Número-Registros

A função de avaliação Número-Registros contabiliza a quantidade de registros cobertos por umadeterminada regra. Considerando o exemplo “SE ATRIBUTO_1 ≥ 8 e ATRIBUTO_1 ≤ 18 e ATRIBUTO_2 ≥ 3e ATRIBUTO_2 ≤ 10 ENTÃO CLASSE = 1”, sua avaliação é 1, pois apenas um registro é satisfeito.

FAcurácia

Essa função de avaliação está definida na seção, acurácia = |C ∩ P| / (|C ∩ P| + |C ∩ ~P|). Ela busca porregras que não gerem situações de conflitos, isto é, situações em que registros satisfazem a mais de uma classe.Essa função por si só, é de difícil evolução, já que existe uma dificuldade inicial de se encontrar uma regra que jácubra algum registro, porém é capaz de gerar boas sementes para experimentos futuros.

FAbrangência

Essa função de avaliação também está definida na seção 0, abrangência = |C ∩ P| / (|C ∩ P| + |~C ∩ P|).Seu objetivo é buscar cada vez mais uma quantidade maior de registros satisfeitos por uma regra. Tanto a funçãoFAcurácia quanto a função FAbrangência são utilizadas como noções descritivas que são facilmentecompreendidas, entretanto elas não são geralmente interessantes como funções de avaliação em sua forma nãomodificada [Erro! Indicador não definido.]. Nesse trabalho, buscou-se experimentar essas funções paraidentificar suas qualidades.

∑ −=N

i iiD PCorrentePÓtimo )(2


Rule Interest

Essa função de avaliação foi sugerida por [PIAT91] e é essencialmente representada pela Equação 39.

Equação 39: Rule Interest

( )S

PSCSPCstRuleIntere

∩×∩−∩=

Nela S, C, e P são subconjuntos descritivos que representam especificidade, condição e previsão.Entenda-se especificidade como sendo o banco de dados. Essa função deriva da seguinte situação. Suponha Ruma população, P um grupo de previsão, e C uma condição. Defini-se p = |C ∩ P| / |C|, p0 = |P| / |R|, g = |C| / |R|.Assume-se que C, P ⊂ R. Regras que pertencem a um R e P fixos são avaliadas no espaço p-g, onde p é atendência (fator de certeza) e g é a generalidade (cobertura) de uma condição C. Baseado nisso Piatersky[PIAT91] introduziu 3 axiomas que as funções de avaliação devem satisfazer.

• E(p0, g) = 0• E(p, g0) cresce monotonicamente em p para um g0 fixo• E(p, g) decresce monotonicamente em g para p = constante/gOnde E representa o valor esperado. Mais detalhes podem ser encontrados em [FAYY96].

Chi-Square

Dada uma tabela de contingência 2x2, contendo os contadores n11, n12, n21 e n22 de registros quepertencem a cada um dos subconjuntos, pode-se calcular as somas da coluna c1 e c2, a soma das linhas l1 e l2 e, onúmero total de registros n respectivamente, como mostrado na Tabela 16.

Tabela 16: Tabela de contingência da função de avaliação Chi-Square

S∩ ~P P~C n11 n12 l1 = n11 + n12

C n21 n22 l2 = n21 + n22

c1 = n11 + n21 c2 = n12 + n22 n = n11 + n12 + n21 + n22

Onde ~ significa negação, S o banco de dados, C a condição e P a previsão. Assumindo a independênciade 2 variáveis C e P, o número esperado de registros em cada subconjunto e11, e12, e21, e e22 respectivamentepode ser calculado pelo produto de sua respectiva linha e coluna, utilizando a lei da probabilidade multiplicativa.Uma aritmética simples mostra que o número esperado de registros em cada subconjunto é:

Equação 40:Valor esperado de registros

.2,1,, =×

= jin

cre ji

ij

Pode ser mostrado que assumindo a independência de C e P tem-se:

Equação 41: Chi-Square

∑ ∑= =

−=

2

1

2

1

2)(

i j ij

ijij

een

ChiSquare

8.6.7. Recompesa nas funções de avaliação

Todas as funções de avaliação descritas anteriormente, podem ter suas aptidões acrescidas de umarecompensa. As recompensas podem ser por:

• Acurácia


• Abrangência• Acurácia e/ou AbrangênciaO primeiro tipo de recompensa multiplica a aptidão da regra pela sua respectiva acurácia, similarmente o

segundo tipo multiplica pela sua abrangência. Enquanto que o terceiro tipo multiplica por ambos. Asrecompensas são acrescentadas à avaliação se a acurácia ou abrangência forem diferentes de zero. Asrecompensas ajudam o modelo na busca por melhores regras.


9. APÊNDICE

9.1. SOFTWARES COMERCIAIS E SITES

Segue uma lista de alguns softwares disponíveis na área de mineração de dados:

9.1.1. AC2 (www.isoft.fr)

AC2 é um conjunto de bibliotecas em C/C++ que permite a desenvolvedores e profissionais da áreade TI embutir as funcionalidades de DM em seus próprios softwares. AC2 cobre todos os passos doprocesso de data mining, da modelagem (modelo OO) até a validação cruzada.

9.1.2. ALICE d’ISoft (www.isoft.fr)

É uma poderosa ferramenta de data mining e de fácil utilização. Utiliza árvores de decisão paraexplorar os dados. Gera relatórios, queries, análise “What if”, etc.

9.1.3. AutoClass C (ic-www.arc.nasa.gov/ic/projects/bayes-

group/group/autoclass/autoclass-c-program.html)

AutoClass C é uma versão de domínio público do AutoClass III, com algumas melhoras doAutoClass X, implementada na linguagem C. AutoClass é um sistema de classificação bayesiana nãosupervisionada que procurar a maior probabilidade de classificação. As entradas consistem de atributos deum banco de dados, de valor real ou discreto, e um valor para a classe.

9.1.4. Clementine (www.isl.co.uk/clem.html)

Clementine é uma ferramenta para data mining vencedora por duas vezes do UK Government’s(Department of Trade & Industry) SMART award for innovation. As aplicações do Clementine incluemsegmentação de clientes, deteção de fraudes, análise de crédito, etc.

9.1.5. Data Surveyor (www.ddi.nl)

Data Surveyor é uma ferramenta de DM para usuários especializados. Consiste de vários algoritmose provê suporte para todos os passos do processo de KDD. Data Surveyor permite que o usuário descubraconhecimento interativamente, inspecione os resultados durante a descoberta e guie o processo dedescoberta. As aplicações do Data Surveyor incluem banco de dados de marketing, análise de crédito erisco.

9.1.6. Data Engine (www.mitgmbh.de)

Data Engine é um software para análise de dados usando tecnologias fuzzy, redes neurais, eestatística convencional. Tem sido aplicada com sucesso nas áreas de planejamento, banco de dados demarketing, controle de qualidade, análise de processos, e diagnósticos.


9.1.7. Datasage (www.datasage.com)

Provê módulos em C++ que controlam os dados num BD relacional facilitando o seugerenciamento. Datasage usa as rotinas de C++ para ler e processar os dados em modo batch. Comoresultado, esse produto pode manipular BDs muito grande. Datasage inclui transformação dos dados,modelagem e análises, com tecnologias de redes neurais e análises de fatores.

9.1.8. DataScope (http://www.tiszanet.hu/cygron/datascp.htm)

A chave para o conhecimento é mostrar e gerenciar os seus dados da maneira mais compreensiva. Édifícil utilizar a intuição se estamos perdidos numa montanha de números. Entretanto, desde que opensamento e a compreensão humana é baseada em informações análogas, DataScope transforma umconteúdo orientado a números de um banco de dados em um diagrama. Estes diagramas permitem que seutilize as habilidades intuitivas mais efetivamente.

9.1.9. Outros softwares e sites

C5.0 / See5 - www.rulequest.com

Commercial tools for data mining - www.cs.bham.ac.uk/~anp/dm_docs/oudshoff.tools.posting

DataDetective – www.smr.nl

dbProphet: neural network data mining tool by Trajecta – www.trajecta.com

Explora - http://orgwis.gmd.de/projects/explora/

IBM Visualization Data Explorer – www.almaden.ibm.com/dx/

LEVEL5 Quest – www.l5r.com

ModelQuest Enterprise – www.abtech.com

ModelQuest Enterprise – www.data-mine.com

PV-WAVE – www.vni.com

SE-Learn - http://www.isp.pitt.edu/~rymon/SE-Learn.html

SPSS Data Mining Software – www.spss.com/datamine/

SuperQuery – www.azmy.com

WizRule for Windows – www.wizsoft.com

XpertRule – www.attar.com

9.2. EMPRESAS DE DATA MINING NO BRASIL


9.2.1. http://www.execplan.com.br/

9.2.2. http://vidaconsultores.com.br/infovida/

9.2.3. http://www.rio.com.br/~extend/

9.2.4. http://www.geocities.com/WallStreet/District/2108/ricvill.htm

9.3. EMPRESAS E PRODUTOS EM DATA MINING

9.3.1. American Heuristics/Profiler – www.heuristics.com

9.3.2. Angoss Software/Knowledge Seeker – www.angoss.com

9.3.3. Business Objects/BusinessMiner – www.businessobjects.com

9.3.4. DataMind/DataMindProfessional – www.datamind.com

9.3.5. HNC Software/DataMarksman – www.hncs.com

9.3.6. HiperParallel/Discovery – www.hiperparallel.com

9.3.7. Information Discovery Inc.(IDI)/Information Discovery System –

www.datamining.com

9.3.8. Lucent Technologies/Interactive Data Visualization – www.lucent.com

9.3.9. Nestor/Prism – www.nestor.com

9.3.10. Pilot Software/pilot Discovery Server – www.pilotsw.com

9.3.11. Seagate Software Systems/Holos 5.0 – www.holossys.com


9.3.12. Thinking Machines/Darwin – www.think.com

REFERÊNCIAS

[PIAT91] G. Piatetsky-Shapiro. Knowledge discovery in real databases: A report on the IJCAI-89Workshop. AI Magazine, Vol. 11, No. 5, Jan. 1991, Special issue, 68-70.

[KELL95] S. Kelly. Data Warehouse applications in the telecommunications industry. Proc. Conf.Commercial Parallel Processing. London, IBC, 1995.

[SRIK95] R. Srikant and R. Agrawal. Mining generalized association rules. Proc. 21st Very LargeDatabases (VLDB) Conf., Zurich, Switzerland, 1995.

[MICH94] D. Michie, D. J. Spiegelhalter and C. C. Taylor. Machine Learning, Neural and StatisticalClassification. New York: Ellis Horwood, 1994.

[FISH87] D. H. Fisher. Knowledge acquisition via incremental conceptual clustering . Machine Learning,2, 1987, 139-172.

[FAYY96] Fayyad, U. M., Piatetsky Shapiro, G., Smyth, P. & Uthurusamy, R. – “Advances in KnowledgeDiscovery and Data Mining”, AAAIPress, The Mit Press, 1996.

[LANG96] P. Langley. Elements of Machine Learning. Morgan Kaufmann, 1996.

[SHAV90] J. W. Shavlik and T. G. Diettrich. (Eds.) Readings in Machine Learning. San Mateo, CA:Morgan Kaufmann, 1990.

[ELDE96] J. F. Elder IV and D. Pregibon. A statistical perspective on knowledge discovery in data bases.In: U. M. Fayyad et al. (Ed.) Advances in Knowledge Discovery and Data Mining, 83-113. AAAI/MITPress, 1996.

[LEE 95] H-Y. Lee, H-L. Ong and L-H. Quek. Exploiting visualization in knowledge discovery. Proc. 1st

Int. Conf. Knowledge Discovery and Data Mining (KDD-95), 198-203. AAAI, 1995.

[HAYK94] Haykin, S., Neural Networks: A Comprehensive Foundation, Macmillan College PublishingCompany, New York, NY, 1994.

[RUME86] D. Rumelhart and McClelland. (Eds.) Parallel Distributed Processing: Explorations in theMicrostructure of Cognition. Cambridge, MA: MIT Press, 1986.

[NILS80] N. J. Nilsson. Principles of Artificial Intelligence. Palo Alto, CA: Tioga, 1980.

[GOLD89] D. E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Reading,MA: Addison-Wesley, 1989.

[MARCO] Marco Aurélio Pacheco, Notas de Aula em Computação Evolucionária, (www.ica.ele.puc-rio.br).

[ADRI97] Adriaans, P., Zantinge, D., Data Mining. Addison-Wesley, 1996.

[FREI98] Freitas, A. A., and Lavington, S. H., Mining Very Large Databases with Parallel Processing.Kluwer Academic Publishers. 1998.


[AGRA97] R. Srikant, Q. Vu, R. Agrawal: Mining Association Rules with Item Constraints, Proc. Of 3rd

Int’l Conference on Knowledge Discovery in Databases and Data Mining, Newport Beach, California,August 1997.

[AGRA94] R. Agrawal, R. Srikant: Fast Algorithms for Mining Association Rules in Large Databases,VLDB-94, Santiago, Chile, Sept. 1994.

[AGRA95] R. Agrawal, H. Mannila, R. Srikant, H. Toivonen and A. I. Verkamo: Fast Discovery ofAssociation Rules, In Knowledge Discovery in Databases, Volume II, U. M. Fayyad, G. Piatetsky-Shapiro,P. Smyth, R. Uthurusamy (Eds.), AAAI/MIT Press, 1995.

[HAN 97] E. –H. Han, G. Karypis, V. Kumar: Scalable Parallel Data Mining for Association Rules,SIGMOD-97, Tucson, Arizona, May 1997.

[FUKU96] T. Fukuda, Y. Morimoto and S. Morishita. Data mining using two-dimensional optimazedassociation rules: scheme, algorithms and visualization. Proc. 1996 ACM SIGMOD Int. Conf. Managementof Data, 13-23. 1996.

[MEHT96] M. Mehta, R. Agrawal, J. Rissanen: SLIQ: A Fast Scalable Classifier for Data Mining, EDBT-96, Avignon, France, March 1996.

[SHAF96] J. Shafer, R. Agrawal, M. Mehta: SPRINT: A Scalable Parallel Classifier for Data Mining,VLDB-96, Bombay, India, September 1996.

[SHOL91] Sholon M. Weiss and Casimir A. Kulikowsky, Computer Systems that Learn: Classificationnand Prediction Methods from Statistics, Neural Nets, Machine Learning, and Expert Systems, MorganKaufman, 1991.

[JAIN88] A. K. Jain and R. C. Dubes: Algoritms for Clustering Data, Prentice Hall, 1988.

[ARAB96] Phipps Arabie and Lawrence J. Hubert: An overview of combinatorial data analysis, In P.Arabie, L. J. Hubert, and G. De Soete, editors, Clustering and Classification, pages 5-63. World ScientificPuc., New Jersey, 1996.

[RAYM94] Raymond T.Ng and Jiawei Han: Efficient and effective clustering methods for spatial datamining, Proc. Of VLDB Conference, Santiago, Chile, September 1994.

[KING81] J. J. King. QUIST: a system for semantic query optimization in relational databases. Proc. 7th

Int. Conf. Very Large Databases (VLDB-81), 510-517. Cannes, France, Sep. 1981.

[FAGI86] R. Fagin and M. Y. Vardi. The theory of data dependencies – a survey. In: M. Anshel & W.Gewirtz (Ed.) Mathematics of Information Processing, 19-71. American Mathematical Society, 1986.

[QUIN93] J. R. Quinlan. C4.5: Programs for Machine Learning. San Mateo, CA: Morgan Kaufmann, 1993.

[INMO93] W. H. Inmon. Building the Data Warehousing. John Wiley & Sons, 1993.

[POE 96] V. Poe. Building a Data Warehousing for Decision Suport. Prentice-Hall, 1996.

[BALA95] J. Bala, J. Huang, H. Vafaie, K. Dejong and H. Wechsler. Hybrid learning using geneticalgorithms and decision trees for pattern classification. Proc. 14th Int. Joint Conf. AI (IJCAI-95), 719-724.1995.


[AHA 95] D. W. Aha and R. L. Bankert. A comparative evaluation of sequential feature selectionalgorithms. Proc. 5th Int. Workshop on Artif. Intel. And Statistics, 1-7. Ft. Lauderdale, FL. 1995.

[KIRA92] K. Kira and L. ª Rendell. The feature selection problem: traditional methods and a newalgorithm. Proc 10th Nat. Conf. Artificial Intelligence (AAAI-92), 129-134. Menlo Park, CA: AAAI, 1992.

[KONO94] I. Kononenko. Estimating attributes: analysis and extensions of RELIEF. Proc. 1994. EuropeanConf. Machine Learning., LNAI 784, 171-182. 1994.

[KOLL96] D. Koller and M. Sahami. Toward optimal feature selection. Proc. 13th Int. Conf. MachineLearning, 1996.

[MANN88] M. V. Mannino, P. Chu and T. Sager. Statistical profile estimation in database systems. ACMComputing Surveys, 20(3), Seo./88, 191-221.

[DOUG95] J. Dougherty, R. Kohavi and M. Sahami. Supervised and unsupervised discretization ofcontinuos features. Proc. 12th Int. Conf. Machine Learning, 194-202. 1995.

[FU 94] L. Fu. Neural Networks in Computer Intelligence. MacGraw-Hill, 1994.

[LU 95] H. Lu, R. Setiono and H. Liu. NeuroRule: a connectionist approach to Data Mining. Proc. 21st

Very Large Databases Conf. (VLDB-95). Zurich, 1995.

[VAUG96] M. L. Vaughn. Interpretation and knowledge discovery from de multilayer perceptron network:opening the black box. Neural Comput. & Applic. (1996) 4: 72-82.

[BIGU96] Bigus, J. P., Data Mining with Neural Network – Solving Business Problems from ApplicationDevelopment to Decision Support, McGraw-Hill, 1996.

[PERE96] Perelmuter, G., Redes Neurais Aplicadas ao Reconhecimento de Imagens Bi-dimensionais.Dissertação de Mestrado, DEE, PUC – Rio, 1996.

[DAYH90] Dayhoff, J., Neural Network Architectures: Na Introduction, Van Nostrand Reinhold, NewYork, NY: 1990.

[FREE92] Freeman, J. A., and D. M. Skapura, Neural Networks: Algorithms, Applications, andProgramming Techniques, Addison-Wesley, Reading, MA: 1992.

[TRES97] V. Tresp, J. Hollatz, and S. Ahmad. Representing Probabilistic Rules with Networks of GaussianBasis Functions. Machine Learning, 27, Page 173, 1997. Kluwer Academic Publishers, Boston.

[TOWE93] G. G. Towell, and J. W. Shavlik. Extracting Refined Rules from Knowledge-Based NeuralNetworks. Machine Learning, 13, Page 71, 1993. Kluwer Academic Publishers, Boston.

[HOLL75] John H. Holland, 1975. Adaptation in Natural and Artificial Systems. University of MichiganPress (Ann Arbor).

[HOLL86] John H. Holland, 1986. Escaping brittleness: the possibilities of general purpose learningalgorithms applied to parallel rule-based systems. Machine Learning, an artificial intelligence approach, 2.

[HOLL92] Holland, J. H., Adaptation in Natural and Artificial Systems, MIT Press, Cambridge, MA: 1992.

[BELE91] Belew, R. and L. Booker, ed., Genetic Algorithms: Proceedings of the Fourth InternationalConference, Morgan Kaufmann, CA: 1991.


[AUGI95] S. Augier, G. Venturini and Y. Kodratoff. Learning first order logic rules with geneticalgorithm. Proc. 1st Int. Conf. Knowlede Discovery & Data Mining, 21-26. AAI Press, 1995.

[NERI95] F. Neri and A. Giordana. A parallel genetic algorithm for concept learning. Proc. ICGA-95, 436-443.

[ANGL97] C. Angalno, A. Giordana, G. Lo Bello and L. Saitta. A network genetic algorithm for conceptlearning. Proc. 7th Int. Conf. On Genetic Algorithms, 434-441. Morgan Kaufmann, 1997.

[JANI93] C. Z. Janikow. A knowledge-intensive genetic algorithm for supervised learning. MachineLearning, 13, 1993, 189-228.

[IGLE96] B. de la Iglesia, J. C. W. Debuse and V. J. Rayward-Smith. Discovering knowledge incommercial databases using modern heuristic techniques. Proc. 2nd Int. Conf. Knowledge Discovery &Data Mining. AAAI, 1996.

[SMIT80] Stephen F. Smith, 1980. A Learning System Based Based on Genetic Adaptative Algorithms.Phd Thesis, University of Pittsburgh.

[SMIT84] Stephen F. Smith, 1984. Adaptative learning systems. In Richard Forsyth, editor, ExpertSystems, Principles and case studies. Chapman and Hall Ltd.

[DEJO93] Kenneth A. DeJong, William M. Spears, and Diana F. Gordon, 1993. Using genetic algorithmsfor concept learning. Machine Learning, 13: 161-188.

[GREE93] David Perry Greene and Stephen F. Smith, 1993. Competition-Based Induction of DecisionModels from Examples. Machine Learning, 13, Page 229. Kluwer Academic Publishers, Boston.

[GREE94] David Perry Greene and Stephen F. Smith, 1994. Using coverage as a model building constraintin learning classifier systems. Evolutionary Computation, 2(1).

[GIOR94] A. Giordana, F. Neri, and L. Saiat, 1994. Search-intensive concept induction. Technical report,Università de Torino, Dipartimento de Informatica, Corso Svizzera 185, 10149 Torino, Italy.

[PEI 95] M. Pei, E. D. Goodman, W. F. Punch III, 1995. Pattern Discovery from data using GeneticAlgorithms. Michigan State University’s Center for Microbial Ecology and Beijing Natural ScienceFoundation of China. GARAGe – Genetic Algorithms Research and Applications Group.

[TRUN79] G. V. Trunk, A Problem of Dimensionality: A Simple Example, IEEE Trans. Pattern Anal.Mach. Intelligence, vol. 1, pp. 306-307, 1979.

[FERR94] J. F. Ferri, P. Pudil, M. Hatef, and J. Kittler. Comparative study of techniques for large-scalefeature selection. In: Pattern Recognition in Practice IV, Multiple Paradigms, Comparative Studies andHybrid Systems, eds. . S. Gelsema and L. S. Kanal. Amsterdam: Elsevier, 1994. pp. 403-413.

[SIED89] W. Siedlecki and J. Sklansky, A note on Genetic Algorithms for Large-Scale Selection, PatternRecognition Letters, vol. 10, pp. 335-347, 1989.

[PUNC93] W. F. Punch, E. D. Goodman, M. Pei, L. Chia-Shun, P. Hovland, and R. Enbody, FurtherResearch on Feature Selection and Classification Using Genetic Algorithms, International Conference onGenetic Algorithms 93, pp. 557-564, 1993.

[KELL91] J. D. Kelly and L. Davis, Hybridizing the Genetic Algorithm and the K Nearest NeighborsClassification Algorithms, Proc. Fourth Inter. Conf. Genetic Algorithms and their Applications (ICGA), pp.377-383, 1991.


[MORI97] K. Morik, P. Brockhausen. A Multistrategy Approach to Relational Knowledge Discovery inDatabases. Machine Learning, 27, Page 287. Kluwer Academic Publishers, Boston. 1997.

[MUGG92] Muggleton, S., ed. 1992a. Inductive Logic Programing. London: Academic Press.

[RAED92] DE Raedt, L. 1992. Interative Theory Revision: An Inductive Logic Programing Approach.London: Academic Press.

[LAVR94] Lavrac, N.; and Dzeroski, S. 1994. Inductive Logic Programing: Techniques and Applications.Chichester, UK: Ellis Horwood.

[ULLM88] Ullman, J. 1988. Principles of Database and Knowledge Base Systems, Volume I. Rockville,Mass.: Computer Science Press.

[QUIN90] Quinlan, J. 1990. Learning Logical Definitions from Refations. Machine Learning, 5(3): 239-266.

[LAVR91] Lavrac, N.; Dzeroski, S.; and Grobelnik, M. 1991. Learning Nonrecursive Definitions ofRelations with LINUS. In Proceedings of the Fifth European Working Session on Learning, 265-281.Berlin: Springer-Verlag.

[SULL86] O’Sullivan F., Yandell, B. S., and Raynor, W. J. Jr. 1986. Automatic Smoothing of RegressionFunctions in Generalized Linear Models. Journal of the American Stastical Association 81: 96-103.

[FRIED95] Friedman, J. H. 1995. An Overview of Predictive Learning and Function Approximation. InFrom Statistics to Neural Networks: Theory and Pattern Recognition Applications, ed. V. Cherkassky, J. H.Friedman, and H. Wechsler. Berlin: Springer.

[WEIS91] Weiss, S. M.; and Kulikowsky, C. A. 1991. Computer Systems that Learn: Classification andPrediction Methods from Statistics, Neural Networks, Machine Learning, and Expert Systems. San Mateo,Calif.: Morgan Kaufmann.

[SHEN 93] Shen W. M. 1993. Bayesian probability theory – A general method for machine learning MCC-Carnot-101-93. Microelectronics and Computer Technology Corporation, Austin, TX.

[WEI 98] Wei-Min Shen, Information Sciences Institute, University of Southern California. UCLA DataMining Short Course, 1998.

[CHEE96] Cheeseman P, Stutz, J., Bayesian Classification (AutoClass): Theory and Results. Advances inKnowledge Discovery and Data Mining, U. M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R.Uthurusamy Editors, 6:153-180, 1996.

[HECK96] Heckerman D., Bayesian Networks for Knowledge Discovery. Advances in KnowledgeDiscovery and Data Mining, U. M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy Editors,11:273-305, 1996.

[ALIF94] Aliferes, C.; and Cooper, G. 1994. An Evaluation of an Algorithm for Indutive Learning ofBayesian Belief Networks Using Simulated Data Sets. In Proceedings of Tenth Conference on Uncertaintyin Artificial Intelligence, 8-14. San Francisco: Morgan Kaufmann.

[BUNT95] Buntine, W. 1995. A Guide to the Literature on Learning Graphical Models. Technical ReportIC-95-05, NASA, Ames Research Center.

[CHAR91] Charniak, E. 1991. Bayesian Networks Without Tears. AI Magazine, 12: 50-63.


[SPIE93] Spieglhalter, D.; Dawid, A.; Lauritizen, S.; and Cowel, R. 1993. Bayesian Analysis in ExpertSystems. Statistical Science, 8: 219-282.

[AGRA92] R Agrawal, S. Ghosh, T. Imielinsky, B. Yer and A. Swami. An interval classifier for databasemining applications. Proc. 18th Int.. Conf. Very Large Databases, 560-573. Vancouver, 1992.

[ESPO95] F. Esposito, D. Malerba and G. Semeraro. Simplifying decision trees by prunning and grafting:new results. Proc. 8th European Conf. Machine Learning, ECML-95, 287-290. LNAI-912.

[PEAR85] J. Pearl. Heuristics: Intelligeny Search Strategies for Computer Problem Solving. Reading, MA:Addison-Wesley, 1985.

[WINS92] P.H. Winston. Artificial Intelligence . 3rd Ed. Reading, MA: Addison-Wesley, 1992

[MICH83] R. W. Michalski. A theory and methodology of inductive learning. Artificial Intelligence, Vol.20, 1983, 111-161.

[HOLS94] M. Holsheimer and A. Siebes. Data mining: the search for knowledge in databases. Report CS-R9406. Amsterdam, the Netherlands: CWI, Jan. 1994.

[LANG95] P. Langlay and H. A. Simon. Applications of Machine Learning and Rule Induction. Comm. ofthe ACM 38(11), Nov./95, 55-64

[CLAR91] Clark, P.; and Boswell, R. 1991. Rule Induction with CN2: Some Recent Improvements. InProceedings of Fifth European Working Session on Learning, 151-163. Berlin: Springer-Verlag.

[SHEN 92] Shen W. M. 1992. Complementary discrimination learning with decision lists. Proceedings ofTenth National Conference on Artificial Intelligence. MIT Press.

[KLOE94] W. Klösgen, 1994. Exploration of simulation experiments by discovery. In Proceedings ofKDD-94 Workshop. AAAI.

[ZYTK91] Jam M. Zytkow and John Baker, 1991. Interative mining of regularities in databases. In GregoryPiatetsky-Shapiro and Willian J. Frawley, editors, Knowledge Discovery in Databases, pages 31-53. MITPress.

[ZYTK93] Jam M. Zytkow and Robert Zembowicz, 1993. Database exploration in search of regularities.Journal of Intelligence Information Systems, 2: 39-81.

[DASG97] D. Dasgupta, Z. Michalewicz, Evolutionary Algoritms in Engineering Applications, (Eds.)Springer, 1997.

[DHAR97] V. Dhar, R. Stein, Seven Methods for Transforming Corporate Data into Business Intelligence,Prentice-Hall, 1997.

[DAVI96] L. Davis. (Ed.) Handbook of Genetic Algorithms. Int. Thomson Comp. Press 1996.

[AGRA93] R. Agrawal, T. Imielinski and A. Swami. Mining Association rules between sets of itens inlarge databases. Proc. 1993 Int. Conf. Management of Data (SIGMOD-93), 207-216. May/93.

[MICH94] Z. Michalewicz, Genetic Algorithms+Data Structures=Evolution Programs, Springer-Verlag-1994.


[KLÖS96] Willi Klösgen and Jan M. Zytkow. Knowledge Discovery in Databases Terminology. Advancesin Knowledge Discovery and Data Mining, Usama. M. Fayyad, Gregory. Piatetsky-Shapiro, PadhraicSmyth, and Ramasamy Uthurusamy Editors, 573-592, 1996.

[COST97] Rodrigo M. L. de A. Costa. Um Estudo Sobre o Desempenho e a Convergência de AlgoritmosGenéticos. Dissertação de Mestrado. Pontifícia Universidade Católica do Rio de Janeiro, Departamento deEngenharia Elétrica, 1997.

[SANK96] Sankar K. Pal and Paul P. Wang. Genetic algorithms for pattern recognition. CRC Press, Inc.1996.

Documents

Descoberta de Conhecimento e Mineração de Dados …valdick.com/files/Apostila de DataMining.pdf · - 1 – ICA – Lab. Inteligência Computacional Aplicada , DEE, PUC–Rio (Versäo