Visualizar - Polis Educacional

Marcia Aparecida Armelim Armentano
RA 0200258 4° Ano
UMA METODOLOGIA UTILIZANDO ALGORITMO GENÉTICO
NA SELEÇÃO DE ATRIBUTOS EM MINERAÇÃO DE DADOS.
Jaguariúna
2005
1
Marcia Aparecida Armelim Armentano
RA 0200258 4° Ano
UMA METODOLOGIA UTILIZANDO ALGORITMO GENÉTICO
NA SELEÇÃO DE ATRIBUTOS EM MINERAÇÃO DE DADOS.
Monografia apresentada disciplina Trabalho de
Graduação do Curso de Ciência da Computação da
Faculdade de Jaguariúna, sob orientação do Prof.
Silvio Petroli Neto, como exigência parcial para
conclusão do curso de graduação.
Jaguariúna
2005
2
ARMENTANO, Marcia Aparecida Armelim. Uma Metodologia na Utilização de Algoritmos
Genéticos na Seleção de Atributos em Mineração de Dados. Monografia defendida e aprovada
na FAJ em 14 de dezembro de 2005 pela banca examinadora constituída pelos professores:
Prof. Silvio Petroli Neto – FAJ Orientador
Prof. Ademário Araújo Júnior
José Arnaldo G. Nunes
3
Ao meu amado filho Juan Pablo
Por todo amor, compreensão e carinho.
4
Agradecimentos
A Deus, por sempre estar presente no meu coração e na minha vida, permitindo que eu
fizesse as minhas escolhas.
À minha família, por toda compreensão e paciência, em especial a minha mãe e a Edna
pela colaboração irrestrita em todos os momentos, e ao meu pai que me ensinou a nunca
desistir e deixar que o meu coração me guiasse.
Aos meus irmãos, que sempre estiveram presentes na minha vida.
Ao Marcelo, por ter dado o primeiro passo para que isso se tornasse realidade.
Ao Juan Pablo, que é a luz dos meus olhos e a inspiração de cada instante.
Aos amigos sempre presentes, em especial ao Emerson por toda ajuda prestada, e a
Michele e ao Cezare por estarem comigo nos momentos de alegrias e principalmente os de
tristezas, sempre me lembrando que amanhã será um novo dia.
A minha sincera gratidão ao Prof. Silvio, pela competente orientação, pelos
conhecimentos transmitidos, por toda paciência dispensada na consolidação deste trabalho.
A FAJ, por contribuir com o banco de dados para a realização deste trabalho.
Que Deus esteja presente na vida de cada um de vocês.
5
ARMENTANO, Marcia Aparecida Armelim. Uma Metodologia na Utilização de Algoritmos
Genéticos na Seleção de Atributos em Mineração de Dados. 2005 Monografia. (Bacharelado
em Ciência da Computação) – Curso Ciência da Computação da Faculdade de Jaguariúna,
Jaguariúna.
RESUMO
Mineração de dados é hoje o termo associado à busca de conhecimento compreensível,
útil ou surpreendente em grandes bases de dados, e sua aplicação dispensa a presença de um
número significativo de atributos ou mesmo registros presentes nas bases de dados originais, e
que em certos casos, se não forem removidos, podem até “atrapalhar” o processo de
aprendizagem. Os Algoritmos Genéticos podem ser aplicados em várias áreas científicas
principalmente onde pode-se notar que há problemas de otimização, desenvolvimento de
estratégias e formas matemáticas, na área de análise econômico, biológica, ecossistemas entre
outras. O principal objetivo é fazer um estudo sobre Algoritmo Genético e Data Mining,
verificando como o Algoritmo Genético Simples se comporta com o Data Mining. Foi utilizado
então o Perfil de Cliente, verificando se o algoritmo proposto mostra-se eficaz. A Mineração de
Dados será utilizada para a extração de regras e agrupamentos necessárias para que o
Algoritmo Genético possa selecionar os melhores indivíduos de cada geração formada. Assim
sendo é possível gerar um classificador que é capaz de agir como um especialista,
classificando os casos desconhecidos. É esperado como resultado fazer um estudo da
performance do Algoritmo de Mineração de Dados, e analisar o comportamento do Algoritmo
Genético Simples na seleção de atributos, verificando-se assim, se é possível à utilização
desses algoritmos em conjunto, ou seja, utilizar algoritmos genéticos para a seleção de
atributos em mineração de dados.
PALAVRA CHAVE: MINERAÇÃO DE DADOS, ALGORITMOS GENÉTICOS, SELEÇÃO DE
ATRIBUTOS.
6
SUMÁRIO
LISTAS ................................................................................................................................... 09
1- INTRODUÇÃO ................................................................................................................... 11
2 – DATA MINING .................................................................................................................. 13
2.1 – Processo de descoberta de conhecimento..................................................................... 14
2.2 – Tarefas do KDD ............................................................................................................. 15
2.2.1 – Associação ................................................................................................................. 15
2.2.2 – Classificação............................................................................................................... 16
2.2.3 – Agrupamento .............................................................................................................. 17
2.3 – Seleção de atributos ...................................................................................................... 17
2.4 – Bi – Business Intelligence e Data Mining........................................................................ 18
3 – COMPUTAÇÃO EVOLUTIVA ........................................................................................... 21
4 – ALGORITMO GENÉTICO................................................................................................. 22
4.1 – População...................................................................................................................... 23
4.2 – Codificação do indivíduo ................................................................................................ 24
4.3 – Função de avalição (fitness) .......................................................................................... 24
4.4 – Métodos de seleção ....................................................................................................... 25
4.4.1 – Seleção por roleta....................................................................................................... 25
4.4.2 – Seleção por torneio..................................................................................................... 26
4.4.3 – Seleção de ranking ..................................................................................................... 27
4.4.4 – Elitismo ....................................................................................................................... 27
4.5 – Operadores genéticos.................................................................................................... 27
4.5.1 – Cruzamento ................................................................................................................ 28
4.5.2 – Mutação ...................................................................................................................... 29
5 – DIVERSIDADE NA POPULAÇÃO..................................................................................... 31
5.1 – Direção Comum Para o Mesmo Ponto........................................................................... 31
5.1.1 – Sharing ....................................................................................................................... 31
5.1.2 – Evolução Cooperativa ................................................................................................. 32
5.1.3 – Abordagens Híbridas .................................................................................................. 34
6 – METODOLOGIA ............................................................................................................... 35
7 – IMPLEMENTAÇÃO........................................................................................................... 37
8 – CONCLUSÃO ................................................................................................................... 40
9 – REFERÊNCIAS BIBLIOGRÁFICAS .................................................................................. 41
7
ANEXO 1 ................................................................................................................................ 43
8
LISTA DE FIGURAS
Figura 01 – Fases do processo KDD ...................................................................................... 12
Figura 02 – Algoritmo Genético Básico................................................................................... 22
Figura 03 – Seleção por Roleta .............................................................................................. 24
Figura 04 – Implementação da Roleta segundo Mitchell......................................................... 25
Figura 05 – Implementação Seleção por Torneio segundo Mitchell. ....................................... 26
Figura 06 – Cruzamento em um ponto.................................................................................... 27
Figura 07 – Cruzamento em dois pontos ................................................................................ 28
Figura 08 – Cruzamento Uniforme .......................................................................................... 28
Figura 09 – Mutação............................................................................................................... 30
Figura 10 – Sharing Compartilhamento de Recursos.............................................................. 32
Figura 11 – Algoritmo Básico da Evolução Cooperativa (Potter, 2000) ................................... 33
Figura 12 – Dados Alunos FAJ ............................................................................................... 37
Figura 13 - bdados.prn ........................................................................................................... 37
Figura 14 – Cromossomo ....................................................................................................... 38
Figura 15 – Avaliação ............................................................................................................. 38
9
LISTA DE TABELAS
Tabela 1 - Soluções candidatas para o problema de x² .......................................................... 25
10
LISTAS DE ABREVIAÇÕES
AG
Algoritmo Genético
KDD
Knowledge Discovery in Databases
FAJ
Faculdade de Jaguariúna
XML
Extensible Markup Language
PMML
Predictive Modeling Markup Language
OLAP
On Line Analitical Processing
CRM
Resource Center for Data MIning
BI
Business Intelligence
HCN
BW
Business Warehousing
SAP
SGBD
Sistema de Gerenciamento de Banco de Dados
11
1. INTRODUÇÃO
Com o passar do tempo, o homem descobriu que poderia guardar eletronicamente os
dados.
Com os anos, esses bancos de dados foram crescendo e se tornaram gigantescos. Com o
avanço da tecnologia e os estudos para o aprimoramento e a utilização das informações, surgiu o
Data Mining, que poderíamos definir como a busca de conhecimento até então perdidos e
desprezados nesses grandes bancos de dados.
Esses conhecimentos podem ser informações inovadoras, gerando novas tendências e
descobrindo diferentes comportamentos que, se bem utilizados, irão fazer a diferença nas
tomadas de decisão das empresas.
O Data Mining possui hoje uma série de ferramentas disponíveis no mercado.
A informação faz a diferença, podendo ser utilizada em diversas áreas.
Esse trabalho propõe a utilização de Algoritmos Genéticos na Seleção de Atributos em
Mineração de Dados.
A seleção de atributos é uma das tarefas que são realizadas no processo do KDD
(Knowlege Data Discovery), mais especificamente na fase de pré-processamento. Essa seleção é
essencial para o bom desempenho do Data Mining. Os atributos, na maioria das vezes, são
coletados para diferentes classificações e se não forem bem selecionados quando chegam à fase
de mineração esses atributos podem até atrapalhar o desempenho do algoritmo.
A Mineração é uma tecnologia que é formada por um conjunto de ferramentas que,
através do uso de algoritmos de aprendizado ou baseados em redes neurais e estatísticas, são
capazes de explorar um grande conjunto de dados, extraindo destes conhecimentos na forma
de hipóteses e de regras. Diariamente, as empresas acumulam diversos dados em seus bancos
de dados, tornando-os verdadeiros tesouros de informação sobre os vários processos e
procedimentos das funções da empresa, inclusive com dados e hábitos de seus clientes, suas
histórias de sucesso e fracassos. Todos estes dados podem contribuir com a empresa,
sugerindo tendências e particularidades pertinentes a ela e seu meio ambiente interno e
externo, visando uma rápida ação de seus gestores (FELDENS, 1999).
Entre os anos 50 e 60 foi quando ocorreu o desenvolvimento de simulação de sistemas
genéticos. Mas foi em 1975 que John Holland contribuiu para a partida inicial dos Algoritmos
12
Genéticos. Nos anos 80 David E. Goldberg obteve o seu primeiro sucesso em uma aplicação
industrial utilizando algoritmo genético, depois disso, os Algoritmos Genéticos vem sendo
utilizados para solucionar problemas de otimização e aprendizado de máquinas.
Esses algoritmos simulam o processo natural das espécies, ou seja, baseiam-se numa
população, na qual há sobrevivência, reprodução e a evolução de cada indivíduo.
Os Algoritmos genéticos são muito utilizados na solução de tarefas onde o espaço de
busca é grande e tem demonstrado bastante eficácia e esse foi um dos principais motivos para
a escolha do mesmo nesse trabalho.
Com a geração de informações e conhecimentos úteis para as empresas, podemos
também ver mais além, ou seja, podemos visualizar a lucratividade das empresas, pois
trabalhos que levariam dias ou meses poderão ser feitos em horas.
13
2. DATA MINING
Podemos definir Mineração de Dados como busca por relacionamentos e padrões
interessantes que estão de certa forma escondidas numa grande base de dados.
A diferença entre dados e informação é ainda maior quando nos referimos a sistemas de
banco de dados. Com o intuito de transformar dados em informação, e posterior conhecimento
útil, surgiu o processo de descoberta de conhecimento em bases de dados, ou KDD
(Knowledge Discovery in Databases). Associado a esse processo surgiu o termo mineração de
dados (Data Mining).
A Mineração de Dados pode ser aplicada em qualquer área, como por exemplo,
financeira, comercial, médica, etc, desde que tenha dados disponíveis para o processamento.
Hoje, profissionais da área de estatística, analista de dados, desenvolvedores de
sistemas de informação gerais, segundo Fayyaed utilizam o termo Mineração de Dados e os
pesquisadores da área de Inteligência Artificial utilizam KDD.
Figura 01 – Fases do processo KDD
A Mineração de Dados tem como objetivo responder uma pergunta particular do usuário
e para isso é necessário que seja informado o problema que se queira resolver.
Para ilustrarmos isso poderíamos considerar um banco de dados de uma empresa de veículos.
Uma consulta poderia ser: “Quantos veículos X foram vendidos pelo vendedor Y?”, esse
exemplo seria uma operação comum e simples. Porém as técnicas de Mineração de Dados
tendem a atender aplicações administrativas como Marketing, Planejamento de Estoque,
Abertura de Novas Filiais, Decisões Estratégicas, no caso de um Banco um exemplo seria o
serviço de Aprovação de Financiamento.
A área científica como biologia molecular, modelagem de mudanças climáticas globais,
etc vem cada vez mais utilizando a Mineração de Dados.
Existem diversas técnicas de Mineração de Dados para a extração de conhecimento
como Indução e ou Extração de Regras, Redes Neurais, Algoritmos Evolutivos, Técnicas
estatísticas (Rede Bayesianas), Conjuntos Difusos, etc. Essas técnicas podem ser utilizadas em
14
diversas tarefas da Mineração de Dados como extração de regras de associação, classificação,
análise de agrupamento, etc.
Fayyad (1996) previne que existem critérios estabelecidos para a decisão em relação
aos métodos que devem ser usados em dada circunstância e que muitas abordagens são
aproximações heurísticas para evitar o alto custo de processamento que seria necessário para
se encontrar soluções ótimas.
Existem alguns componentes que, segundo Fayyad (1996) são essenciais para o
Algoritmo de Mineração:
•
Representação do Modelo: Linguagem que será utilizada para descrever os
padrões que tem por objetivo serem descobertos.
•
Critérios de Avaliação do Modelo: Função de Aptidão da qualidade que um
padrão específico possui, ou seja, alcançar as metas do KDD.
•
Método de Busca: Seria a busca de parâmetro e a busca do modelo. Depois que
é feito a escolha da representação do critério de avaliação do modelo o problema
de Mineração de Dados é reduzido a tarefa de otimização.
Portanto, na escolha do Algoritmo, deve-se priorizar a otimização do critério de avaliação
do modelo.
2.1 Processo de Descoberta de Conhecimento
KDD é o processo não trivial de identificação, a partir de dados de padrões que seja
válidos, novos, potencialmente úteis e compreensíveis (Fayyad, 1996).
A Mineração de Dados é a etapa principal, porém o processo de descoberta de
conhecimento em banco de dados não se limita apenas em minerar os dados.
Fayyaed (1996) classifica o processo geral do KDD em etapas:
•
Entendimento do Domínio de Aplicação: Nessa etapa é identificado-o
conhecimento que interessa, e a meta do processo de KDD a partir do ponto de
vista do usuário.
•
Pré-Processamento: inclui a operação como seleção de atributos relevantes,
remoção de ruído, tratamento da ausência de valores de atributos e conversão
de dados categóricos ou contínuos;
•
Redução de Dados: Reduz os dados em relação ao objetivo da tarefa.
•
Algoritmo: Escolha de um algoritmo apropriado de Mineração de Dados.
•
Mineração de Dados: Realização da Mineração de Dados.
15
•
Interpretação: Nessa etapa é feita a interpretação dos padrões descobertos,
podendo assim retornar para um dos passos anteriores.
•
Consolidação: É o conhecimento descoberto, a conferência, solução possível de
conflitos com conhecimentos anteriores.
O processo de KDD, assim sendo, utiliza o banco de dados para a realização da seleção
de atributos e as transformações necessárias sobre os dados na fase de pré-processamento.
As fases do KDD segundo Lui e Motoda:
•
Data Warehousing: É possível que dos dados de diferentes formatos e fontes sejam
coletados. Depois esses dados são reunidos e utilizados na mesma aplicação.
•
Pré-Procesamento: seleciona, a partir dos dados gerados pela fase de Data
Warehousing, aqueles considerados úteis para a tarefa que se pretende realizar, dando
origem a uma base de dados. A essa nova base de dados são então aplicados métodos
de remoção de ruídos e de projeção e redução dos dados, remodelando-os de acordo
com a aplicação em que serão utilizados.
•
Mineração de Dados: Na etapa denominada mineração de dados, escolhe-se um
algoritmo propício para a aplicação em questão, que será utilizado para procurar por
padrões interessantes e úteis nos dados.
•
Pós-Processamento: A fase de Pós-Processamento compreende a validação e
interpretação dos resultados, além da organização da informação encontrada, de
maneira que ela possa ser verificada e reusada.
2.2 Tarefas do KDD
Entre as principais tarefas realizadas pelo KDD estão:
2.2.1 Associação
Tem como principal objetivo encontrar a partir de um conjunto de exemplos E, um conjunto
de regras de associação, ou seja, descobrir quais atributos aparecem com maior freqüência
nesses exemplos. Uma regra de associação é um relacionamento do tipo Se (x) então (y), onde
x Е X e y ЕY são conjuntos de itens, e X ∩Y = ø (LIU E MOTODA, 1998)
Um registro normalmente corresponde a uma transação de um cliente, em que cada
item tem valor verdadeiro ou falso, de acordo com a compra ou não do item pelo cliente. Esse
tipo de dado é normalmente coletado através de tecnologias, como a de código de barras
(FREITAS E LAVINGTON, 1998).
16
2.2.2 Classificação
Uma das tarefas mais comumente resolvidas com técnicas de mineração de dados. Um
sistema de classificação é utilizado para prever a classe de um objeto baseado em seus
atributos. Um dos principais objetivos na tarefa de classificação é maximizar a taxa de
classificações corretas nos dados de teste, que corresponde à razão entre o número de seus
exemplos corretamente classificados e o número total de exemplos disponíveis no conjunto de
testes.
Os dados utilizados para resolução da classificação consistem em um conjunto de
atributos denominados previsores e um atributo denominado meta, que define a classe a que
esse registro pertence. O objetivo dessa tarefa é descobrir um relacionamento entre os atributos
previsores e o atributo meta, usando registros cuja classe é conhecida, para que posteriormente
esses atributos previsores possam ser utilizados para prever a classe de um registro cuja classe
é desconhecida (HAND, 1997).
Quando trabalhamos com um classificador, os exemplos disponíveis para criação de um
modelo de classificação são divididos em dois conjuntos mutuamente exclusivos: um conjunto
de treinamento e um conjunto de teste. O conjunto de treinamento fica disponível para o
classificador, que analisa as relações entre os atributos de previsões e os de meta. Os
relacionamentos descobertos, a partir desses exemplos, são então utilizados para prever a
classe dos registros presentes no conjunto de teste. Para o classificador, o atributo meta do
conjunto de teste fica indisponível. Após prever a classe dos exemplos do conjunto de teste, as
classes previstas são então comparadas com as classes reais dos exemplos, definidas pelo
atributo meta. Se a classe prevista for igual a real, a previsão foi correta, caso contrário, a
previsão foi incorreta.
O conhecimento descoberto pelo classificador, através dos exemplos de treinamento,
pode ser representado de várias formas.
Depois que for identificada a necessidade de se resolver um problema, o próximo passo
será escolher um dos diversos métodos existentes para a classificação. Para que seja feita
essa escolha, podemos comparar esses métodos segundos os critérios:
•
Acurácia: é o grau de certeza de uma determinada informação,ou seja, reflete o quanto
um valor estimado está próximo do valor real. Quanto maior a acurácia maior será a
precisão dos resultados finais. É considerado ruim abaixo de 50%, média entre 50% e
75%, e alta acima de 75%.
17
•
Desempenho: Refere-se aos recursos computacionais utilizados na geração e na
utilização do modelo.
•
Robustez: É a habilidade do modelo chegar a fazer predições corretas tanto com a falta
de atributos ou não.
•
Escalabilidade: É a habilidade de fazer com que o modelo construído seja eficiente em
grandes quantidades de dados.
•
Interpretabilidade: É a habilidade de fazer com que o conhecimento adquirido pelo
modelo seja compreensível
2.2.3 Agrupamento
Tem a tarefa de agrupar e dividir os dados em grupos formados por elementos com
características semelhantes (Fayyad et al 1996). Nesse tipo de problema, o sistema deve
particionar o conjunto de dados em subconjuntos. Um algoritmo de agrupamento deve ser
capaz de maximizar a semelhança entre elementos de um mesmo grupo e minimizar as
semelhanças entre exemplos pertencentes a grupos diferentes. Normalmente não existe uma
resposta correta para um problema de agrupamento.
É o agrupamento que possibilita o entendimento inicial dos dados. Na maioria das vezes
após o agrupamento, os métodos de classificação são aplicados com o objetivo de obter regras
de classificação e distinguir os registros pertencentes a classes diferentes ou regras que
caracterizam cada grupo ou classe.
2.3 Seleção de Atributos
Algoritmos genéticos vêm sendo muito utilizados na resolução de problemas de Seleção
de Atributos, principalmente por sua aplicação ser vantajosa em situações em que o espaço de
busca é grande. Tratando-se de seleção de atributos, a dimensão do espaço de busca está
diretamente relacionada ao número M de atributos contidos na base de dados, e é definida
como 2M.
Quanto maior o número de atributos em uma base de dados, maior o poder do
classificador de discriminar, sem contar com a maior facilidade de extrair modelos de
conhecimento da base.
A quantidade de dados ou atributos presentes em uma base de dados é indiferente na
seleção de atributos, e é hoje uma das principais tarefas de pré-processamento utilizadas para
preparar dados que serão posteriormente minerados. Ela tem como principal objetivo selecionar
18
um subconjunto de atributos relevantes para a tarefa alvo, dentre todos os atributos disponíveis.
Um dos objetivos da seleção de atributos é a melhoria da performance do algoritmo de
mineração de dados (velocidade de aprendizagem, taxa de classificações corretas e/ou
simplicidade das regras), e diminuir a dimensionalidade dos dados.
Independente da quantidade de dados ou atributos que estão numa base de dados a
seleção de atributos ainda é uma das principais tarefas de pré-processamento onde é feita a
preparação dos dados para que depois possam ser minerados.
Podemos definir um atributo relevante, caso ele seja capaz de distinguir exemplo que
faça parte de classes diferentes.
Além disso a seleção de atributos garante que os dados que chegam a fase de
mineração sejam de boa qualidade (LIU E MOTODA, 1998).
A seleção de Atributos se baseiam praticamente em duas etapas que são elas:
1. Busca dos subconjuntos de atributos
2. Avaliação dos subconjuntos encontrados
Além disso, a seleção também é útil quando temos muitos atributos ou poucos registros.
2.4 BI-Business Intelligence e Data Mining
Com o grande crescimento dos conceitos de BI-Business Intelligence, a qual teve forte
propensão as aplicações em diversos segmentos da industria,os produtores de ferramentas de
Data Mining preparam-se para disputar esse mercado que rende cada vez mais crescer.
Uma pesquisa feita em outubro de 2000, realizada pela empresa Cutter Consortium,
com 94 empresas no mundo inteiro apontou as seguintes projeções, em relação ao uso do Data
Mining:
•
20% dos entrevistados já estão usando ferramentas de Data Mining;
•
16% planejam usá-las dentro de um ano;
•
10% planejam usá-las dentro de um tempo superior a um ano;
•
21% estão analisando as ferramentas, mas não tem planos para seu uso a curto prazo;
•
33% não estão considerando o seu uso.
De modo geral os produtos de Data Mining podem ser classificados em:
•
Ferramentas Independentes de aplicação genérica: essas ferramentas oferecem um
amplo conjunto de técnicas e mecanismos de visualizações. Oferecem também
abordagens simples, como Análise de Regressão, até as mais complexas como Redes
Neurais, passando por regras de Associação e Análise de Agrupamentos (clustering).
19
Porém tudo isso requer uma equipe com formação estatística para a preparação dos
dados a serem garimpados, o que implica num tempo maior para a implantação do
projeto. Entre os principais representantes estão: IBM Intelligent Miner, da IMB Copr.,
Enterprise Miner, do SAS Institute Inc., Clementine, da SpSS e Knowledge Studio, da
Angoss Software Corp. Alguns produtos, como Clementine, permitem que todo o projeto
de Mining, desde a extração dos dados até a publicação do modelo, seja exportado
como um programa em C, por exemplo. O produto da IBM apresenta-se em duas
versões: exclusivamente para textos (IMB D2Intelligent Miner for Text) e outro para
garimpagem de dados em geral (IBM DB2 Intelligent Minerfor Data).
•
Ferramentas orientadas para Algoritmos: essas ferramentas são voltadas para a
aplicação de certos algoritmos, e o que faz com que ofereçam um melhor desempenho.
O entendimento do problema a ser resolvido é fundamental para que seja encontrada e
aplicada a melhor técnica. Assim sendo, ela pode oferecer um resultado melhor se
comparado com outros alternativos. Vejamos alguns produtos dessa classe: Knowledge
Seeker da Angoss, com ênfase em Árvores de Decisão; e NeuralWorks, da NeuralWare,
para as aplicações que requerem os complexos algoritmos de Redes Neurais. Algumas
dessas ferramentas específicas também são oferecidas com add-in de ferramentas de
desktop, com o SGDB, Acess e Excel. Por exemplo a Angoss, Kwnowledge Access e
Knowlewdge Excelerator para o Access e Excel (produtos Microsoft).
•
Ferramentas orientadas a aplicações específicas: essas ferramentas sofreram certas
adaptações para trabalharem com segmentos específicos de aplicações orientadas por
tutoriais, porém não permite uma grande variação. Um dos produtos dessa classe é o
IBM-Intelligent Miner para CRM e texto; o DecisionHouse para CRM da Quadstome; e o
DataBase Mining Marksman da HNC Software Inc., para aplicações de Data Base
Marketing.
•
Ferramentas embutidas em soluções OLAP: São ferramentas associadas a produtos de
banco de dados e de aplicações de BI-Bussiness Inelligence ou OLAP. Oferecem
aplicação simples com algoritmos triviais e são de fácil aplicação. Os representantes
são: Bussines Miner da Bussiness Object; o Scenário, da cognos; o Analysis Service,
embutido no SQL/Server2000® da Microsoft; e a suite de Data Mining da Oracle,
baseado em Darwin adquirido da Thinking Machines.
•
Algumas soluções de Mining trazem a proposta de um padrão para definição de
modelos preditivos, baseados Em XML É o PMML definido pelo Data Mining group, que
permite a definição e o compartilhamento de modelos de mining entre as aplicações de
20
origem tecnológicas diferentes. A SAP, por exemplo, com o crescimento de seu BWBusiness Warehouse, como instrumento de BI, oferece também ferramentas de
mineração na sua arquitetura, isso é possível através de soluções próprias ou de
acoplamento com terceiros. A Microsoft, apresenta algoritmos de mineração (arvore de
decisão e clustering) que são oferecidos no SQL-Server/2000®.
•
Ferramentas e serviços de provedores externos: Representam soluções completas, pois
englobam a prestação de serviço de mineração, além da utilização das ferramentas. Os
serviços compreendem desde a abordagem de metodologia para a mineração até o
“hosting” dos serviços de garimpagem de dados. Exemplo de servidores desses
serviços: IBM Global Business Solution, Epiphany, PricewaterHouse Coopers,etc.
21
3. COMPUTAÇÃO EVOLUTIVA
A Computação Evolutiva é um dos ramos da Inteligência Artificial que propõem uma
solução de problemas inspirado na seleção natural.
Na Computação Evolutiva encontramos um conjunto de técnicas de busca e otimização
baseados na evolução natural das espécies, ou seja cria-se uma população de indivíduos que
vão se reproduzir, depois da reprodução eles se encontram numa fase de competição onde os
indivíduos mais fortes irão sobreviver.
Dentro da Computação Evolutiva encontramos os Algoritmos Genéticos e a
Programação Genética que foram concebidos em 1960 por John Holland (Holland 1975), que
teve como objetivo principal estudar os fenômenos relacionados as espécies e suas formas de
adaptação e seleção natural que ocorre na natureza e com base nessas características naturais
incorporou esses conceitos na área computacional. Os Algoritmos Genéticos e a Programação
Genética vêem do mesmo conceito, porem não mantêm vínculos ou dependências entre si.
22
4. ALGORITMO GENÉTICO
Os algoritmos genéticos são algoritmos de busca e otimização baseados na analogia
com os processos de seleção natural e genética evolucionária (Goldberg, 1989). A essência do
método consiste em manter uma população de indivíduos (cromossomos), onde cada indivíduo
representa uma possível solução para um problema específico. A melhor solução é atingida
através de um processo de seleção competitiva, envolvendo cruzamentos e mutações (Herrera
et al., 1996).
Um dos motivos para o sucesso dos Algoritmos Genéticos se relaciona a busca global
que eles realizam. Os algoritmos Genéticos se baseiam nos métodos de seleção natural e
assim sendo envolvem a sobrevivência do indivíduo mais apto, dessa forma se tornam
especialmente atrativos por não exigirem que se saiba como encontrar uma solução, mas sim
como reconhecê-la sendo uma ótima solução para o problema.
Para chegarmos numa aplicação para a resolução de um problema é necessário
seguirmos alguns passos fundamentais:
- criar um indivíduo (cromossomo) no qual será definida uma representação da solução.
Em seguida devemos definir como a avaliação dessa solução será realizada (função fitness).
- Obter uma população inicial com indivíduos criados aleatoriamente, e com isso
escolher como e quais operadores genéticos serão aplicados.
- depois utilizar um indivíduo (cromossomo) no qual será definida uma representação da
solução.
- Através do operador de seleção é obtido uma nova geração, ou seja, escolhe-se os
indivíduos de melhor valor.
- Quando é criada uma nova geração, aplica-se nos indivíduos que foram selecionados,
operações onde misturam suas características que chamamos de genes, através dos
operadores de cruzamento (crossover) e mutação.
23
Figura 02 – Algoritmo Genético Básico
4.1 População
Podemos definir uma população como um conjunto de indivíduos. Essa população é de
suma importância, pois ela esta cogitada como solução, e também, será usada para a criação de
uma nova população ou conjunto de indivíduo.
Outro ponto importante é o tamanho da população que pode afetar o desempenho e a
eficiência do AG.
Quando a população é pequena ela pode perder a diversidade que é importante para de
chegar a uma boa solução. Porque ela fornece uma cobertura de espaço de busca muito
pequena. Por outro lado, se a população tiver uma grande quantidade de indivíduos, o
algoritmo poderá se tornar ineficiente pela demora na avaliação de aptidão e também irá
precisar de um recurso computacional maior.
24
4.2 Codificação do Indivíduo
Existem várias maneiras de representar um indivíduo em um Algoritmo Genético. Os
indivíduos têm um papel importante, representando uma possível solução para o problema.
Podemos representar os indivíduos de várias formas, uma delas e a mais utilizada é a
representação binária de tamanho fixo, onde segundo Hinterding, (2000) um indivíduo é uma
cadeia de bits que são representados por 0 ou 1. Já Freitas, (2002) nos diz que quando as
variáveis assumem valores contínuos podem ter problemas.
Um AG convencional nunca conhece as informações que ele carrega e isso independe
do tipo de codificação que estará sendo utilizada (DHAR e STEIN, 1997).
Existem outras formas de codificação como a usada pelo próprio alfabeto do atributo que
se deseja representar como letras, números, códigos e outros mais.
A representação utilizada nesse trabalho será a representação binária de tamanho fixo,
onde um indivíduo é uma cadeia de bits que assumem valores 0 ou 1, por ser considerada a
mais simples e a mais utilizada e também a que melhor representa o problema a ser tratado.
4.3 Função de Avaliação (Fitness)
Utilizamos a função de avaliação para determinar o quanto é boa uma solução candidata
é para que se chegue na resolução do problema. Quando falamos em população natural o
fitness é que determina a capacidade do indivíduo sobreviver e depois se reproduzir.
Se o fitness tiver uma precisão baixa, uma solução ótima pode ser deixada de lado
durante a execução do algoritmo, também poderá gastar mais tempo analisando solução não
tão boas.
Consideremos um exemplo clássico de um AG simples dado por Goldberg (Goldberg,
1989), no qual queremos encontrar o valor de x que resulte em um valor máximo da função x²
no intervalo [0,31]. Podemos codificar indivíduos para a solução desse problema com 5 bits,
que representam o valor binário de qualquer número no intervalo [0,31]. Nesse caso,
poderíamos considerar a função de avaliação como sendo próprio x² (função objetivo), visto que
quanto maior o valor dessa função, melhor a qualidade de um indivíduo.
A Tabela abaixo traz exemplos de soluções candidatas para o problema proposto por
Goldberg. Dentre as soluções apresentadas, a solução 2 apresenta função de avaliação maior, e
por isso pode ser considerada, entre as soluções encontradas, a melhor solução para o problema.
Tabela 1 - Soluções candidatas para o problema de x²
25
Código Indivíduo X
X2
1
1101
13
169
2
11000
24
576
3
1000
8
64
4
10011
19
361
4.4 Métodos de Seleção
Como os Algoritmos Genéticos se baseiam na seleção natural, eles devem ter a
capacidade de identificar os indivíduos mais aptos para que esses continuem no processo de
evolução e os mais fracos sejam excluídos.
Um dos objetivos da seleção é propagar material genético dos indivíduos mais
adaptados, tomando cuidado para que não se valorize demais um indivíduo em adaptado no
começo, e assim, se despreze os indivíduos que se apresentam ruins.
Pode-se utilizar vários métodos como: seleção proporcional (roleta),seleção por ranking,
torneio, elitismo, entre outros.
4.4.1 Seleção por Roleta
Cada indivíduo da população é representado na roleta de acordo com a proporção do serem
índice de aptidão. Assim, os indivíduos com maior índice de aptidão tomam uma porcentagem
maior na roleta.
Figura 03 – Seleção por Roleta
26
Esse método exige suas passagens por todos os indivíduos da população o que faz aumentar o tempo de
processamento. A figura abaixo mostra um exemplo implementado segundo Mitchell (1997).
Figura 04 – Implementação da Roleta segundo Mitchell.
4.4.2 Seleção por Torneio
Um número de N indivíduos da população é escolhido aleatoriamente para formar uma
sub-população (temporária). Nesse grupo, para que seja selecionado um indivíduo, depende de
uma probabilidade K definida previamente. Esse é o mais utilizado, pois oferece a vantagem de
não exigir que a comparação seja feita entre todos os indivíduos da população (BANZHAL,
1998).
27
Figura 05 – Implementação Seleção por Torneio segundo Mitchell.
4.4.3 Seleção de Ranking
Para entendermos melhor a seleção de Ranking vamos dividi-lo em duas partes:
1- As soluções são ordenadas de forma crescente de acordo com os valores da função
de avaliação, isto é, se o objetivo for maximizar a função de avaliação, agora se o objetivo for
minimizá-la será feito em ordem decrescente. Quando a lista estiver ordenada será dado a cada
individuo um novo valor da função de avaliação equivalente à sua posição no ranking.
2- É feito um procedimento parecido com a seleção proporcional, quanto maior for a posição do indivíduo no ranking, maior será as chances
desse indivíduo ser selecionado.
4.4.4 Elitismo
O indivíduo de melhor desempenho é selecionado automaticamente. O elitismo conserva os Nelit melhores indivíduos da população atual
copiando-os para a próxima geração sem nenhuma alteração, os outros N - Nelit indivíduos são gerados normalmente utilizando-se do método
de seleção e posteriormente são aplicados os operadores genéticos. Com isso ele garante que as melhores soluções sejam passadas para a
próxima geração e ainda participam da criação dos novos indivíduos da nova geração.
4.5 Operadores Genéticos
O objetivo principal dos operadores genéticos é transformar a população através de sucessivas gerações até que se chegue num resultado
satisfatório.
28
Os operadores genéticos são necessários para que se haja diversidade entre os
indivíduos da população e para que se mantenham as características das adaptações
adquiridas durante as gerações anteriores. Os operados genéticos são constituídos de
operadores de cruzamento e mutação que trazem com eles o papel fundamental em um AG.
4.5.1 Cruzamento
O cruzamento (crossover) é o operador genético que predomina. É através dele que são criados novos indivíduos, ou seja, utiliza-se de dois
indivíduos (pais) para fazer o cruzamento, misturando as suas características. Podemos dizer, de forma abstrata, que esse cruzamento tenta
imitar a reprodução de genes em células. O resultado desta operação é um indivíduo (filho) no qual foram combinadas as melhores
características usadas como base.
O crossover de um ponto é muito simples. Primeiramente é sorteado aleatoriamente um
ponto do cromossomo, Depois é feira a troca de material genético, essa troca é realizada na
região a direita em relação ao ponto escolhido. Podemos ver isso melhor na figura abaixo:
Figura 06 – Cruzamento em um ponto
Já o Cruzamento em Dois Pontos é feito com dois pontos de cruzamento, seleciona-se
pontos de corte para o cromossomo, nos quais cada um dos dois descendente.
29
Figura 07 – Cruzamento em dois pontos
Outro tipo de cruzamento é o Cruzamento Uniforme. Nesse método, cada gene do
cromossomo (indivíduo) pode ser trocado de acordo com uma probabilidade fixa p e então,
quanto maior for o valor de p, maior será o número de genes trocados ente os dois pais. A
figura mostra um cruzamento uniforme no qual o valor padrão de p é 0,5 e os genes trocados
estão destacados em negrito (Freitas 2000).
X1 X2 X3 X4 X5 X6
X1 Y2 X3 Y4 Y5 X6
Y1 Y2 Y3 Y4 Y5 Y6
Y1 X2 Y3 X4 X5 Y6
Antes do Cruzamento
Depois do Cruzamento
Figura 08 – Cruzamento Uniforme [FREITAS, 2002]
4.5.2 Mutação
É necessário para a introdução e manutenção da diversidade genética da população.
Esta operação modifica aleatoriamente alguma característica do indivíduo sobre o qual é
aplicado, assim criando novos valores de características, porém, são aplicadas através de uma
taxa de mutação geralmente pequena.
30
No caso de um indivíduo ser representado por string binário, ela consiste em escolher
aleatoriamente um gene do cromossomo e inverter seu valor de 1 para 0 ou 0 para 1.
A mutação assegura que a probabilidade de se chegar a um espaço de busca
possivelmente não seja zero.
Figura 09 – Mutação
Quanto à geração de um novo conjunto de indivíduo, é gerado a partir da população
anterior, assim, a este novo conjunto dá-se o nome de geração e através de uma grande
quantidade de geração é possível obter resultados dos algoritmos genéticos.
31
5. DIVERSIDADE NA POPULAÇÃO
5.1 Direção Comum Para o Mesmo Ponto
Quando alguns genes tomam uma direção comum para o mesmo ponto se torna um
problema em Algoritmo Genético, contudo esses indivíduos são relativamente adaptados porem
não ótimos podem levar a população a convergi a um local. Para que isso não aconteça pode
ser utilizados juntamente com os algoritmos genéticos o compartilhamento de recursos
(sharing), da Evolução Cooperativa e da Hibridização.
5.1.1 Sharing
Na natureza existem vários nichos, e neles podemos ter várias espécies, o número
dessas espécies podem aumentar de acordo com a fertilização e a eficiência de toda a
organização.
Um dos primeiros estudos foi feito por Caviccho (1970) o qual criou um mecanismo
chamado preselection onde um indivíduo adolescente substitui o indivíduo pai,se o valor de
aptidão dele for maior do que o valor de aptidão do pai, assim se manteria a diversidade da
população porque estaria substituindo os seus similares.
Depois De Jog (1975) criou crowding onde o método proposto para se manter a
diversidade, ele substituía os indivíduos da população fazendo com que os novos indivíduos
substituam outros similares com menor valor para a função de aptidão dentro da população.
O compartilhamento de Recursos também conhecido como Sharing foi introduzido por
Goldeberg e Richadson (Golderg 1989). O objetivo desse mecanismo é reduzir o valor de
aptidão de indivíduos que tem membros altamente similares dentro da população. A Sharing é
usada para determinar os vizinhos e o grau de compartilhamento para cada indivíduo da
população.
O grau de compartilhamento é determinado para um determinado indivíduo onde é
somado os valores da função Sharing que foi contribuídos por todos os outros indivíduos na
população.
Os indivíduos muito similares requerem um grau de compartilhamento próximo de 0.0.
Caso o indivíduo seja idêntico a um outro indivíduo, seu grau de comparação será igual a 1.0.
Depois e acumular o número total de compartilhamentos, o indivíduo que está sendo
avaliado terá o seu valor de aptidão reduzido, através da divisão de seu valor de aptidão pela
soma acumulada do total de compartilhamento.
32
Figura 10 – Sharing compartilhamento de recursos
Assim o Algoritmo Genético tradicional é modificado no módulo de avaliação com isso
cada indivíduo terá o seu valor de aptidão reduzido de acordo com a quantidade de indivíduos
idênticos ou similares dentro da população.
Assim o Algoritmo Genético terá uma probabilidade menor que muitos indivíduos sejam
selecionados de um mesmo nicho, chegando a uma diversidade populacional maior.
5.1.2 Evolução Cooperativa
A Evolução Cooperativa é tida com problemas complexos, proposta feita por De Jong
(2000).
Nessa arquitetura encontramos um ecossistema de duas ou mais espécies.
Essa técnica consiste em cruzar os indivíduos apenas com a sua própria espécie, ou
seja, são geneticamente isoladas.
As restrições de cruzamento são forçados simplesmente por evoluir as espécies em
população separadas.
33
As espécies tem um relacionamento cooperativo, inteiramente em modelo de domínio
compartilhado.
Figura 11 – Algoritmo Básico da Evolução Cooperativa (Potter 2000)
Cada espécie é evoluída em sua própria população. Para a avaliar uma população são
formadas colaboração com representantes.
Segundo Potter De Jong isso seria como uma colaboração porque quando os indivíduos
chegarem ao final será analisado a forma que eles trabalharam juntos para resolver o problema.
Caso aconteça da evolução estacionar, ou seja, parar a possibilidade de construir uma
boa solução será mínima, então será criada aleatoriamente uma nova população. Para
descobrir se houve uma parada podemos analisar a qualidade e a colaboração feita através da
equação:
34
F(t)-f(t-k)<C,
Onde f(t) é o valor de aptidão da melhor colaboração no tempo, C é uma constante que
mostra o aumento do valor de aptidão (se houver uma melhoria), K é uma constante que
especifica o tamanho de uma janela evolutiva onde deve haver uma melhoria que deve ser
realizada.
Há cada geração realizada é feita uma cooperação entre as populações. Assim cada n
gerações a população foi avaliada tiver um valor de aptidão muito baixo ela será descartada, e
então será criada uma nova população a qual substituirá as próximas gerações.
5.1.3 Abordagens Híbridras
A hibridização utiliza outros métodos de otimização que é utilizado em conjunto com o
Algoritmo Genético, já que o AG tradicional não apresenta uma boa otimização. Como por
exemplo Hill-Climbing, Busca Tabu, entre outros.
A Busca Tabu por exemplo faz uma busca agressiva dentro do espaço de solução do
problema de otimização com o objetivo de encontrar as melhores alternativas para que não
sejam consideradas um Tabu.
35
6. Metodologia
Foi feito levantamento bibliográfico do material utilizado na pesquisa principalmente
livros. Realizou-se um estudo sobre o Data Mining, abrangendo as ferramentas da Data Mining,
suas etapas e aplicações de classificação.
De acordo com o objetivo desse trabalho foi utilizado Algoritmo Genético em conjunto
com o Data Mining, no qual foi feito um estudo sobre a utilização dos Algoritmo Genético, dando
ênfase de como utilizar algoritmo genético para a seleção de atributos. Contudo, o estudo
realizado sobre algoritmo genético abordou desde um estudo sobre o algoritmo tradicional, a
população, codificação do indivíduo, função fitness, métodos de seleção (Roleta,Torneio,
Ranking, etc), Cruzamento, Mutação, técnicas para manter a diversidade da população.
Para a implementação foi utilizado o programa Matlab 6.0.
Com o estudo realizado notou-se que a seleção de atributos é uma das etapas mais
importantes da Mineração de Dados. Notou-se isso devido ao processo do KDD, onde é
necessário uma boa seleção de atributos na fase de pré-processamento para que os dados
cheguem a fase de Mineração de Dados com boa qualidade, senão isso pode fazer com que a
mineração não obtenha o resultado esperado.
Ficou definido que o método para gerar a população inicial para o desenvolvimento
desse trabalho foi gerar a população aleatoriamente.
A representação utilizada nesse trabalho será a representação binária de tamanho fixo,
onde um indivíduo é uma cadeia de bits que assumem valores 0 ou 1, por ser considerada a
mais simples e a mais utilizada.
Como fitness utilizou-se a acurácia.
O cruzamento e a mutação fazem dois papéis diferentes porém com a finalidade de se
obter diversidade na população, criando, a partir dos indivíduos pais, os indivíduos filhos que
assim gerarão uma nova população.
36
7. IMPLEMENTAÇÃO
Para a realização desse trabalho foi utilizado o banco de dados dos alunos da FAJ, do
qual foram utilizados somente os campos: curso, data de nascimento, sexo, estado civil,
naturalidade, nacionalidade e cidade. Esses dados foram transmitidos através de uma tabela do
Excel contendo inicialmente 4817 registros. Alguns destes registros não continham todos os
dados necessários e foram eliminados, restando para a realização desse trabalho 4802
registros.
Houve a necessidade de transformar cada dado num número, por exemplo curso
Ciência da Computação, foi atribuído o código 1, o mesmo aconteceu com os campos cidade,
naturalidade, nacionalidade, sexo, estado civil. Isso foi feito no Excel.
A data de nascimento também foi tratada. Foi necessário transformar o seu formato de
data para geral, onde foi obtido uma numeração. Depois de gerado, essa numeração no
programa Excel, foi também necessário transformar uma data do mês de novembro em
numeração da mesma forma feita com a data de nascimento de cada aluno, o valor obtido foi
subtraído da data de nascimento e multiplicado por 365 (dias/ano), assim sendo, foi obtido a
idade de cada aluno.
Foi necessário fazer um levantamento de cada tipo de curso, sexo, estado civil, cidade
de naturalidade, nacionalidade e cidade de moradia, para garantir que esses dados possam ser
interpretados pela fase KDD destinada a isso, bem como para o entendimento do algoritmo, as
tabelas estão em Anexo.
Todas as alterações necessárias para a implementação do software em si foram
realizadas. Como já dito, foi utilizado o Matlab por se tratar de um software que facilita o
trabalho com matrizes.
A tabela de dados da FAJ foi transformada em um arquivo bdados.prn separado por
tabulação, para que assim fosse possível ser carregado e interpretado pelo Matlab. Porém esse
arquivo foi transformado em um arquivo bdados.m (arquivo do Matlab). Vejamos na figura
abaixo um trecho da tabela com dos dados dos alunos FAJ, em seguida vejamos a figura do
arquivo dados.prn.
37
Figura 12 - Dados Alunos FAJ
38
Figura 13 - bdados.prn
Para a verificar a performance dos algoritmos genéticos na mineração de dados seguires
basicamente alguns passos:
Ler o arquivo com os dados;
Gerar a população inicial aleatória;
Ordenação dos dados segundo a o valor da acurácia;
Seleção dos mehores indivíduos;
Cruzamento;
Mutação;
A população inicial será criada de forma aleatória. Podemos ver um trecho logo abaixo.
for i=1:pop
xnl(i) = floor(100*rand(1)); %idade 1
xn2(i) = (floor(3*rand(1))+1)*xnl(i); %idade 2
xn3(i) = floor(2*rand(1)); %sexo
xn4(i) = floor(6*rand(1)); %estado civil
xn5(i) = floor(414*rand(1)); %Naturalidade
xn6(i) = floor(4*rand(1)); %Nacionalidade
xn7(i) = floor(94*rand(1)); %Cidade
Com isso é possível a identificação cada cromosso de acordo com os dados, ou seja, serão
atribuído valores aleatórios aos dados. Vejamos um exemplo, de um cromossomo criado pela
população aleatório.
Um cromossomo seria identificado como na figura, abaixo.
Idade1 Idade2
18
30
Sexo
1
Estado civil
3
Naturalidade Nacionalidade
1
199
Cidade
62
Figura 14 - Cromossomo
Para a codificação de cada indivíduo, cada número, gerado será transformado em um
código binário.
A avaliação é uma das fases importantes pois é nela que será avaliada as condições
dos indivíduos. Para isso utilizaremos a acurácia da seguinte maneira:
39
Figura 15 – Avaliação
Onde C são os registros que satisfazem as condições da regra. Exemplo para o
cromossomo 1, quantos registros satisfazem o curso, idade, sexo, estado civil, naturalidade,
nacionalidade, cidade?
P- são os registros que satisfazem o objetivo, exemplo para a regra 1, quantos registros são de Ciência da Computação.
Portanto a acurácia de uma regra é dada por Acurácia igual percentual dos registros que
satisfazem C então P dentre todos os registros que satisfazem P.
Já a abrangência é Abrangência igual ao percentual dos registros que satisfazem C
então P dentro de todos os registros que satisfazem P.
O Cluster, ou seja, o agrupamento foi formado pelos respectivos grupos que
representam os cursos.
Cada curso gera um cluster.
A avaliação dos clusters é feita de acordo com uma regra, a qual identificará o aluno
pertencente ou não a cada grupo.
Depois da avaliação e da definição da qualidade dos indivíduos, quando o arquivo com
os dados for lido e passado por todos os processos necessários para a mineração de dados o
arquivo gerado será como uma lista, então ainda será necessário uma rotina para a ordenação
dos resultados, ou seja, será ordenado o resultado da acurácia. Com a separação dos clusters
os dados já passaram pela fase de mineração de dados e irão para a fase final do KDD que
será a pós-processamento onde será obtido a interpretação dos resultados, e a organização
das informações encontradas.
40
8. CONCLUSÕES
O principal objetivo deste trabalho era fazer um estudo sobre Data Mining e Algoritmo
Genético.
O objetivo da implementação, que foi realizada é verificar como o Algoritmo Genético
Simples se comporta com o Data Mining e foi utilizado então o Perfil de Cliente, que nesse caso
se encaixa melhor como o Perfil do aluno de Ciência da Computação.
Esse trabalho foi extremamente complexo, por se tratar de dois assuntos atuais, e
difíceis de trabalhar, porém interessantes e que vêm sendo muito utilizados. Uma outra
dificuldade para a realização desse trabalho foi conseguir o banco de dados, por geralmente
esses bancos conterem informações pessoais de seus clientes. Mesmo na FAJ foi muito difícil
de conseguir apesar de se tratar de um trabalho de conclusão de curso da mesma, e só foi
possível com a persistência e colaboração do Prof. e Orientador Silvio.
Com o estudo realizado, verificou-se que existe a necessidade de utilizar algoritmos para
melhorar os dados que saem da fase de Data Warehounsig e que chegam à fase de PréProcessamento, ou seja, a Seleção de Atributos e foi utilizado para isso o Algoritmo Genético
Simples.
A Acurácia foi utilizada como Função de Aptidão e notou-se que, para esse caso ela
mostra-se muito “forte” porque a acurácia verifica se todos os campos satisfazem a regra, se
algum campo não satisfizer a regra ele não fará parte no caso dos alunos de Ciência da
Computação.
Uma solução seria usar o número de campos que satisfazem ao invés de todos. Assim
seria verificado cada cromossomo, identificando qual seria mais forte de acordo com a
quantidade de campos que satisfazem a regra, ou mesmo utilizando um outro método em vez
da acurácia como a escabilidade ou interpretabilidade.
Notou-se também que para utilizar a acurácia a população não poderia ser aleatória
porque desde o início das gerações teria que se manterem indivíduos mais aptos.
Notou-se também a falta de diversificação da população, o que poderia ser resolvido
com a utilização de um algoritmo próprio para isso como o Sharing, por exemplo, mas nesse
caso não poderíamos mais estar classificar esse algoritmo como Algoritmo Genético Simples.
41
9. REFERÊNCIAS BIBLIOGRÁFICAS
AMARAL, FERNANDA. Data Mining, Futura. Futura, 2004. (Visão sobre a Mineração de
Dados e suas aplicações).
BANZHAF, W; NORDIN, P.; KELLER, R. E. & FRANCONE, F. D. Genetic Programming: an
introduction. ISBN 155860510X. Morgan Kaufmann, 1998.
BARBIERI, CARLOS. BI-Business Intelligence Modelagem & Tecnologia, 2001. Axcel Books
do Brasil.
CAVICCHIO, JR., D. J. Adaptive search using simulated evolution. Doctoral dissertation,
University of Michigan, Ann Arbor, MI. (University Microlms No. 25-199), 1970.
DHAR, V.; STEIN, R., Seven Methods for Transforming Corporative Data into Business
Intelligence, Prentice Hall, Londres, 1997.
DE JONG, K. A. An Analysis of the Behavior of a Class of Genetic Adaptative Systems.
PhD thesis, University of Michigan, 1975.
FAYYAD, U.M.; PIATITSKY-SHAPIRO, G.; SMYTH, P.; UTHURUSAMY, R. (Eds), American
Association for Artificial Intelligence, Inglaterra, 1996.
FREITAS, A.A.; LAVINGTON, S. H., Mining Very LargeDatabases with parallel Processing,
Kluwer, 1998.
GOLDBERG, D. E. Genetic Algorithms in Search, Optimization, and Machine. earning,
Addison-Wesley Publishing Company, 1989. (Algoritmo Genético e otimização).
HOLSHEIMER, M.; SIEBES, A., Data Mining – The Search for Knowledge in Databases,
Report CS-R9406, Amsterdam, 1991.
42
LIU, H; MOTODA, H. Feature Selection for Knowledge Discovery and Data Mining, Kluwer
Academic Publishers, 1998. (Fases do processo do KDD)
LUGER, GEORGE. Inteligência Artificial: Estruturas e Estratégias para a Solução de
Problemas Complexos. Bookman, 2004. (A Inteligencia Artificial como solução para problemas
complexos).
MITCHELL, M. An introduction to genetic algorithms. Cambridge: Mit Press. 1997. (207 p.)
NORVIG, Peter; RUSSEL, Stuart. Inteligência Artificial. Campus, 2004.
POTTER, M. A.; DE JONG, K. Cooperative coevolution: an architecture for evolving
coadapted subcomponents. In: Proceedings EVOLUTIONARY COMPUTATION, 8(1),2000,
pp.1-29.
43
ANEXO 1
Tabela 2 - Curso
0
1
2
3
4
5
6
7
8
9
10
11
Curso
Administração
Ciência da Computação
Ciências Contábeis
Direito
Educação Física
Enfermagem
Fisioterapia
Letras
Medicina Veterinária
Nutrição
Psicologia
Turismo
Tabela 3 – Sexo
Sexo
0 Feminino
1 Masculino
Tabela 4 - Estado Civil
0
1
2
3
4
5
Estado Civil
Amasiado
Casado
Divorciado
Solteiro
Separado
Viúvo
44
Tabela 5 – Naturalidade
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
Naturalidade
Imperatriz
1 de maio
A dos Dourados
Adamantina
Aguaí
Águas da Prata
Águas de Lindóia
Alegrete
Alfenas
Alterosa
Alto Piqueri
Alto Rio Doce
Altos
Americana
Amparo
Ananindeua
Andradas
Andradina
Angatuba
Aparecida do Norte
Apiai
Apucarana
Aracatú
Araçatuba
Arapiraca
Arapongas
Araras
Arcadas
Argentina
Artur Nogueira
Arujá
Assis
Assis Chateaubriand
Astorga
Ataleia
Avaré
Barão Geraldo
Barbacena
Barbosa Ferraz
Bariri
Barra da Estiva
Barra do Pirai
45
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
Barra Mansa
Barretos
Barueri
Bastos
Batatais
Bauru
Bebedouro
Belém
Belo Horizonte
Benedito Leite
Bernardino de Campos
Bicas
Boa Esperança
Boa Esperança do Sul
Bocaiuva
Boituva
Borda da Mata
Botucatu
Bragança Paulista
Brazopolis
Brotas
Brumado
Bueno Brandão
C. do Oeste
Cabo Verde
Caçapava
Cachoeira de Minas
Caetite
Caimbra
Cajuru
Cambé
Camboriu
Cambuquira
Campanha
Campina Lagoa
Campinas
Campo do Meio
Campo Grande
Canoinhas
Capivari
Caraguatatuba
Caratinga
Cardoso
Caririaçu
Carmo da Mata
Carmo de Minas
Carmo do Rio Claro
Carnauba dos Dantas
Carneirinho
46
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
Casa Branca
Cascavel
Castro
Caxias
Caxias do Sul
Charqueada
Cianorte
Clementina
Conceição Aparecida
Concepcion
Conchal
Coração de Jesus
Cordeirolopolis
Corinto
Cornélio Procópio
Coromandel
Coronel Fabriciano
Cosmopolis
Cosmorama
Coxim
Cruz Alta
Cruzeiro
Cruzeiro do Oeste
Cruzeiro do Sul
Cuiabá
Curitiba
Curitibanos
Descalvado
Diadema
Divinolândia
Dourados
Dracena
Duque de Caxias
Elias Fausto
Engenheiro Coelho
Espírito Santo do Pinhal
Estiva Gerbi
Fabriciano
Farias Brito
Faxinal
Feira de Santana
Felizburgo
Fernandópolis
Ferraz de Vasconcelos
Florai
Florida Paulista
Formoda do Oeste
Fortaleza
Franca
47
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
Franco da Rocha
Franscisco Alves
Galia
Garça
General Salgado
Goiânia
Grandes Rios
Guaimbe
Guaira
Guape
Guaraci
Guaranésia
Guarapuava
Guaratinga
Guaratinguetá
Guareí
Guarulhos
Guaxupé
Guimarães
Guimarania
Holambra
Holanda
Hortolândia
Ibertioga
Ibitinga
Icó
Igarapava
Ilha solteita
Imperatriz
Indaiatuba
Independência
Ipatinga
Ipero
Iporã
Ipuiuna
Iretama
Itabaianinha
Itaberaba
Itaci
Itajubá
Itamogi
Itanhaém
Itapagipe
Itapetininga
Itapeva
Itapicuru
Itapira
Itapolis
Itararé
48
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
Itatiba
Itatinga
Itaú de Minas
itu
Ituiutaba
Itupeva
Itaiporã
Jaboti
Jaboticabal
Jacarei
Jacuí
Jaguariúna
Jales
Jandaia do Sul
Jandira
Janiopolis
Japira
Jardim Alegre
Jau
Jd. Novo Mundo
Jesuitas
João Monlevade
João Pessoa
Juazeiro do Norte
Jundiai
Junqueiropolis
Juramento
Juranda
Jureia
Kaloré
Lages
Leme
Limeira
Lindóia
Lins
Londrina
Lupionopolis
Macatuba
Machado
Mairiporã
Manaus
Mandaguari
Manga
Mar de Espanha
Marechal Deodoro
Marília
Maringá
Martinópolis
Maua
49
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
Mineiros do Tietê
Mirandópolis
Mirassol
Mococa
Mogi das Cruzes
Mogi Mirim
Mogi-Guaçu
Mongaguá
Monte Alegre do Sul
Monte Alto
Monte Azul
Monte Belo
Monte Mor
Monte Sião
Montes Claros
Moreilandia
Morungaba
Munhoz
Muzambinho
Natal
Natércia
Navegantes
Nigéria
Niteroi
Nova Esperança
Nova Friburgo
Nova Lima
Nova Odessa
Osasco
Osvaldo Cruz
Ourinhos
Ouro Fino
Ouro Verde
Padre Paraíso
Palmares
Palmeirais
Palmeiras D Oeste
Panema
Paraguaçu
Paraguaçu Paulista
Paraná
Paranacity
Paranaguá
Paranapanema
Paranavai
Passo Fundo
Passos
Patrocinio
Pauliceia
50
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
Paulinia
Paulistano
Peabiru
Peçanha
Pedreira
Pelotas
Penapolis
Perdizes
Pereira Barreto
Pilar do Sul
Pindai
Pindamonhangaba
Pindorama
Piracicaba
Pirangi
Pirapozinho
Pirassununga
Piratininga
Piui
Ponta Porã
Poção de Pedras
Poços de Caldas
Pojuca
Pombal
Ponta Grossa
Populina
Porto Velho
Porto Alegre
Porto Ferreira
Pouso Alegre
Pratapolis
Pres. Venceslau
Presidente Alves
Presidente Eptacio
Presidente Prudente
Promissão
Prudentópolis
Rancho Alegre
Recife
Remanso
Residente Alves
Resnede
Resplendor
Ribeirão Pires
Ribeirão Preto
Rio de Janeiro
Rio Claro
Rio das Pedras
Rio de Janeiro
51
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
Rio Negrinho
Rio Pardo de Minas
Rolandia
Ronda Alta
S Bernado do Campo
S. Caetano do Sul
S. João do Caiua
S. José do Rio Pardo
S.Bento do Sapucaí
S.Bernardo do Campo
S.Caetano do Sul
S.José do Rio Pardo
S.Vicente de Minas
Sacramento
Salto
Salto Grande
Salvador
Santa
Santa Amelia
Santa Barbara D Oeste
Santa Cruz do Rio Pardo
Santa Fé
Santana de Parnaíba
Santiago
Santo Amaro
Santo Andre
Santo Antonio da Posse
Santos
São Bernardo
São João da Boa Vista
São José dos Campos
Sao Paulo
São Pedro
São Sebastião do Paraíso
Serra Negra
Sete Lagoas
Socorro
Sorocaba
Sumaré
Suzano
Taboão da Serra
Taiobeiras
Tambaú
Tamboara
Tambobril
Tapejara
Tapira
Taquaritinga
Tatuí
52
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
Taubate
Telêmaco Borba
Teofilo Otoni
Terra Boa
Terra Roxa
Tietê
Toledo
Três Fronteiras
Tres Lagoas
Tupã
Umuarama
Unaí
Urania
Uruguaiana
Vale Paraíso
Valinhos
Valparaíso
Vargeão
Vargem Grande
Vargem Grande do Sul
Vazea Paulista
Vicentina
Viçosa
Vinhedo
Vitória
Volta Redonda
Votuporanga
Wenceslau-Bras
Wervershoof
Tabela 6 – Nacionalidade
0
1
2
3
Nacionalidade
Argentina
Brasileira
Chilena
Holandesa
Tabela 7 – Cidade
0
1
2
3
4
5
6
7
8
Cidade
Águas de Lindóia
Americana
Amparo
Apiai
Araçatuba
Arcadas
Areado
Artur Nogueira
Barão Geraldo
53
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
Bariri
Bauru
Bragança Paulista
Campinas
Capivari
Casa Branca
Caxias do Sul
Conchal
Cosmópolis
Curitibanos
Elias Fausto
Embu
Engeheiro Coelho
EspÍrito Santo do Pinhal
Estiva Gerbi
Guaranésia
Guaratinguetá
Guareí
Holambra
Indaiatuba
Itanhaém
Itapetininga
Itapira
Itaquaquecetuba
Itatiba
Itobi
Itu
Itupeva
Jacareí
Jaguariuna
Jd. Novo Mundo
Jundiaí
Limeira
Lindóia
Louveira
Mococa
Mogi das Cruzes
Mogi Mirim
Mogi-Guaçu
Monte Alegre do Sul
Monte Mor
Morungaba
Muzambinho
Navegantes
Nova Lima
Nova Odessa
Osasco
Ouro Fino
Pauliceia
54
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
Paulinia
Pedreira
Pilar do Sul
Pinhalzinho
Piracicaba
Pouso Alegre
Pres. Venceslau
Ribeirão Preto
Rio Claro
Rio das Pedras
Salto
Santa Barbara D Oeste
Santo Antonio da Posse
Santos
São Bernardo do Campo
São João da Boa Vista
São José dos Campos
São Lourenço
São Paulo
São Pedro
São Roque
São Sebastião do Paraíso
Serra Negra
Sete Lagoas
Socorro
Sorocaba
Sumaré
Taboão da Serra
Tietê
Tremembé
Urania
Valinhos
Vargem Grande do Sul
Venacio Aires
Vinhedo
Votorantim