Subsistema de gestão de dados
Data mining
Metáfora :
Minas – para extrair um diamante é necessário extrair primeiro uma
série de escombros.
Information overload - “procurar uma agulha num palheiro”
Exemplo: search engines.
Descoberta automática de informação.
Processo “mágico” que transforma matéria em bruto em diamantes.
Sistemas de Apoio à Decisão
1
Subsistema de gestão de dados
Data mining
Principais características:
• Revela dados escondidos, encobertos, não óbvios;
• As ferramentas de data mining são normalmente usadas em
ambientes cliente/servidor;
• O utilizador é normalmente o utilizador final da informação que
através de ferramentas de query pretende construir queries e
receber respostas sem ter de recorrer à programação;
• Obtêm-se muitas vezes resultados inesperados;
• Devido às grandes quantidades de dados é muitas vezes
necessário usar processamento paralelo.
Sistemas de Apoio à Decisão
2
Subsistema de gestão de dados
Data mining
Principais objectivos:
• Previsão - Ex: alguns padrões da ondas sísmicas podem prever
um tremor de terra com grande probabilidade; prever o que os
clientes irão comprar com certos descontos.
• Identificação - Certos padrões podem identificar a existência de
um objecto, evento ou actividade. Ex: Intrusos de um sistema
informático podem ser identificados pelos programas
executados, ficheiros acedidos, tempo de CPU por sessão.
Sistemas de Apoio à Decisão
3
Subsistema de gestão de dados
Data mining
Principais objectivos (continuação):
• Classificação - Podemos dividir os dados de modo a identificar
diferentes classes ou categorias baseadas em combinações de
parâmetros. Ex: os clientes de um supermercado podem ser
classificados em compradores assíduos, compradores
ocasionais, compradores à caça de promoções. A classificação
pode ser usada para decompôr o problema em problemas mais
simples.
• Optimização - Podemos querer optimizar o uso de recursos
limitados, tais como tempo, espaço, dinheiro ou matérias
primas e maximizar os lucros obedecendo a determinadas
restrições.
Sistemas de Apoio à Decisão
4
Subsistema de gestão de dados
Data mining
Aplicações:
• Marketing - previsão de quantos clientes vão comprar um
produto, classificação de clientes;
• Banca - previsão de crédito mal parado e utilização fraudulenta
de cartões de crédito;
• Retalhistas - previsão de vendas e calendarização da
distribuição;
• Seguros - Previsão do número de queixas e dos custos
correspondentes, detecção de fraudes;
• Polícia - Reconhecimento de padrões nos crimes, no
comportamento criminal;
Sistemas de Apoio à Decisão
5
Subsistema de gestão de dados
Data mining
Aplicações (continuação):
• Hardware/software - Previsão de avarias e de potenciais
violações de segurança;
• Companhias aéreas - Recolha de informação dos destinos mais
escolhidos em vôos com escala, calendarização de tripulações;
• Saúde - Correlacionamento da morada dos doentes com as
doenças que têm;
• Broadcasting - Definição da grelha de programas - o que é
melhor para o prime time, maximização de lucro pela
publicidade;
• Indústria - optimização da capacidade de produção.
Sistemas de Apoio à Decisão
6
Subsistema de gestão de dados
Data mining
Formas de conhecimento:
• Regras de associação - estas regras correlacionam a presença de
um conjunto de items com a presença de outro conjunto de
valores para outro conjunto de variáveis. Ex: um cliente que
compra queijo e fiambre também compra pão.
• Categorização ou segmentação - Um conjunto de dados pode
ser separado em grupos com características semelhantes. Ex: os
possiveis tratamentos para uma doença podem ser dividdos em
grupos baseados nos efeitos secundários produzidos.
Sistemas de Apoio à Decisão
7
Subsistema de gestão de dados
Data mining
Formas de conhecimento (continuação):
• Padrões sequenciais - detectar associações entre eventos que
ocorrem dentro de certos períodos de tempo. Ex: um doente que
faz um bypass e posteriormente desenvolve uma concentração
elevada de ureia no sangue e provável que sofra de
insuficiência renal nos próximos 18 meses.
• Padrões de séries temporais - Ex: 2 produtos têm o mesmo
padrão de vendas durante o verão, mas diferentes no inverno;
encontrar um período de tempo em que inflação desceu.
Sistemas de Apoio à Decisão
8
Subsistema de gestão de dados
Processo de descoberta do conhecimento
• Selecção de dados
• Limpeza
• Enriquecimento
• Codificação
• Data mining (verdadeira fase de descoberta)
• Relatório e apresentação da informação descoberta
Sistemas de Apoio à Decisão
9
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Exemplo:
Uma editora vende 5 tipos de revistas: automóveis, decoração,
desporto, música e banda desenhada. O objectivo do processo de
data mining é descobrir novos agrupamentos de clientes de modo a
definir uma política de marketing. Estão interessados em questões
como:
• "Qual é o perfil típico de leitor das revistas de automóveis?“
•
"Existe alguma correlação entre o gosto por automóveis e o
gosto por banda desenhada?"
Sistemas de Apoio à Decisão
10
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Selecção de dados
Consiste na selecção de dados operacionais do sistema de
facturação, que contêm informação acerca das pessoas que
subscreveram as diferentes revistas. De modo a facilitar o processo
de descoberta de conhecimento é feita uma cópia dos dados
operacionais e guardada numa base de dados separada.
Sistemas de Apoio à Decisão
11
Subsistema de gestão de dados
Nº
Cliente
Nome
Morada
Data
subscrição
Revista
12003
Santos
R. Alegria 12
15-04-94
Auto
12003
Santos
R. Alegria 12
21-06-93
Música
12003
Santos
R. Alegria 12
30-05-92
Bd
12009
Lopes
Av. Lberdade 1
01-01-01
Bd
12013
Dias
Pr. Flores 34
30-02-95
Desporto
12018
Santo
R. Alegria 12
10-08-98
Decoração
Sistemas de Apoio à Decisão
12
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Limpeza
Problemas: erros de dactilografia, o cliente muda de residência e
não avisa, o cliente fornece informação incorrecta, falta de
consistência.
Algoritmos de reconhecimento de padrãos podem ser usados para a
limpeza dos dados.
Se o data mining for executado numa data warehouse o processo
de limpeza já estará efectuado.
Sistemas de Apoio à Decisão
13
Subsistema de gestão de dados
Nº
Cliente
Nome
Morada
Data
subscrição
Revista
12003
Santos
R. Alegria 12
15-04-94
Auto
12003
Santos
R. Alegria 12
21-06-93
Música
12003
Santos
R. Alegria 12
30-05-92
Bd
12009
Lopes
Av. Lberdade 1
NULL
Bd
12013
Dias
Pr. Flores 34
30-02-95
Desporto
12003
Santos
R. Alegria 12
10-08-98
Decoração
Sistemas de Apoio à Decisão
14
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Enriquecimento
Suponhamos que compramos informação extra acerca dos clientes
(data de nascimento, rendimento, quantidade de crédito, possuem
carro e casa).
Pela morada (bairro) pode inferir-se um rendimento.
Podem também entrevistar-se uma amostra de clientes da base de
dados, o que nos dará informação detalhada acerca do
comportamento dos clientes.
Há que incorporar esta informação na nossa base de dados.
Sistemas de Apoio à Decisão
15
Subsistema de gestão de dados
Nome
Data
nascimento
Rendimento
Santos
13-04-76
3.000.000
1.100.000
Não
Não
Lopes
20-10-71
6.000.000
2.400.000
Sim
Não
Sistemas de Apoio à Decisão
Crédito
Carro
Casa
16
Subsistema de gestão de dados
Nº
Cliente
Nome
Data
nascimento
Rendimento
Crédito
Carro
Casa
Morada
Data
subscrição
Revista
12003
Santos
13-04-76
3.000.000
1.100.000
Não
Não
R. Alegria
12
15-04-94
Auto
12003
Santos
13-04-76
3.000.000
1.100.000
Não
Não
R. Alegria
12
21-06-93
Música
12003
Santos
13-04-76
3.000.000
1.100.000
Não
Não
R. Alegria
12
30-05-92
Bd
12009
Lopes
20-10-71
6.000.000
2.400.000
Sim
Não
Av.
Lberdade 1
NULL
Bd
12013
Dias
NULL
NULL
NULL
NULL
NULL
Pr. Flores
34
30-02-95
Desporto
12003
Santos
13-04-76
3.000.000
1.100.000
Não
Não
R. Alegria
12
10-08-98
Decoração
Sistemas de Apoio à Decisão
17
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Codificação
Nesta fase selecciona-se apenas os registos que têm suficiente
informação. Muitas vezes existem registos em que faltam muitos
dados e que não é possível completá-los. Temos que decidir se vale
a pena manté-los ou se os podemos apagar, uma vez que dado a
falta de dados não servem para nada. Nalguns casos, especialmente
na detecção de fraudes, a falta de informação pode ser um indício.
Vamos agora fazer uma projeccção dos registos. Assumimos que
não estamos interessados nos nomes dos clientes, uma vez que só
queremos identificar certos tipos de clientes. Assim eliminamos os
seus nomes.
Até aqui a codificação consistiu apenas em operações de SQL.
Sistemas de Apoio à Decisão
18
Subsistema de gestão de dados
Nº
Clientec
Data
nascimento
Rendimento
12003
13-04-76
3.000.000
12003
13-04-76
12003
Carro
Casa
1.100.000
Não
Não
R. Alegria
12
15-04-94
Auto
3.000.000
1.100.000
Não
Não
R. Alegria
12
21-06-93
Música
13-04-76
3.000.000
1.100.000
Não
Não
R. Alegria
12
30-05-92
Bd
12009
20-10-71
6.000.000
2.400.000
Sim
Não
Av.
Lberdade 1
NULL
Bd
12003
13-04-76
3.000.000
1.100.000
Não
Não
R. Alegria
12
10-08-98
Decoração
Sistemas de Apoio à Decisão
Crédito
Morada
Data
subscrição
Revista
19
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Codificação (continuação)
Neste momento, a informação da nossa base de dados é ainda
muito detalhada para ser usada como input de um algoritmo de
reconhecimento de padrões.
Ex:
data de nascimento  classes de idades
Morada  código postal.
Data de subscrição  poderiam ser agrupadas em meses
começando em 1990 ou anos.
Sistemas de Apoio à Decisão
20
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Codificação (continuação)
Poderiamos encontrar dependências do género:
Um cliente com rendimento > 15.000 euros e idade entre 20 e 30 anos
que subscreveu revistas de banda desenhada no mês M aparentemente
irá subscrever uma revista de automóveis 5 anos depois.
Ou identificar tendências como:
O nº de revistas de decoração vendidas a clientes com rendimento
entre 10.000 e 20.000 euros que vivem na região R está a aumentar.
O modo como codificamos os dados determina o tipo de padrões e
relações que vamos encontrar.
Sistemas de Apoio à Decisão
21
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Codificação (continuação)
Exemplos de codificação:
• Endereço - compressão da morada em 4 códigos de regiões.
Quantos códigos e definição de regiões?
• Data de nascimento - divisão em 10 classes discretas de 10 anos.
• Rendimento - divisão em classes de 1000. Não só simplifica a
informação, como cria classes de rendimento com a mesma
ordem de magnitude das classes de crédito, o que facilita as
comparações.
Sistemas de Apoio à Decisão
22
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Codificação (continuação)
Exemplos codificação:
• Crédito - divisão em classes de 1000.
• Conversão de posse de carro “sim” ou “não” em 1 ou 0 codificação binária melhora a eficiência dos algoritmos de
reconhecimento de padrões.
• Conversão da data de subscrição no nº do mês a partir de 1990 facilita a análise de séries temporais. A codificação em dias seria
detalhada demais, mas permitiria a análise de datas especiais
como o dia de Natal, Páscoa, ou feriados nacionais.
Sistemas de Apoio à Decisão
23
Subsistema de gestão de dados
Nº
Cliente
Idade
Rendimento
Crédito
Carro
Casa
Região
Mês
subscrição
12003
20
3000
1000
0
0
1
52
Auto
12003
20
3000
1000
0
0
1
42
Música
12003
20
3000
1000
0
0
1
29
Bd
12009
30
6000
2000
1
0
1
NULL
Bd
12003
20
3000
1000
0
0
1
104
Decoração
Sistemas de Apoio à Decisão
Revista
24
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Codificação (continuação)
A cada subscrição corresponde um registo.
Não muito apropriado para encontrar relações entre as diferentes
revistas.
Mais eficiente ter uma ideia de todas as revistas subscritas por cada
cliente.
Um registo apenas por cliente.
Indexação por bitmaps
Sistemas de Apoio à Decisão
25
Subsistema de gestão de dados
Bitmap indexing
Consiste na construção de um vector de bits para cada valor do
domínio a ser indexado (coluna) (bom para domínios pequenos).
Facilita a comparação, agregação e o cruzamento de dados.
O bit 1 é colocado na posição n do vector se a linha n contiver o
valor a ser indexado.
Exemplo: Um inventário de 100 000 carros com um bitmap para
indexar o tamanho do carro. Se tivermos 4 tamanhos possíveis económico, compacto, gama média e gama alta - teriamos 4
vectores de bits cada um com 100 000 bits (12,5 K) para um
tamanho de índice de 50 K.
Sistemas de Apoio à Decisão
26
Subsistema de gestão de dados
Nº
Cliente
Idade
Rendimento
Crédito
Carro
Casa
Região
Auto
Mús.
23003
20
3000
1000
0
0
1
1
1
23009
30
6000
2000
1
0
1
0
0
Sistemas de Apoio à Decisão
Bd
Desp.
Decor.
1
0
1
1
0
0
27
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Data mining
Não é uma técnica única. Várias técnicas são usadas para permitir
a extracção de informação a partir dos dados existentes:
• Ferramentas de query
• Técnicas de estatística
• Métodos de visualização
• Online analytical processing (OLAP)
• Case-based learning - k vizinhaças mais próximas
• Árvores de decisão
• Regras de associação
• Redes neuronais
• Algoritmos genéticos
Sistemas de Apoio à Decisão
28
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Data mining
Ferramentas de query versus data mining
As ferramentas de query ajudam os utilizadores a encontrar factos
novos e interessantes a partir de dados que eles armazenaram numa
base de dados.
Permitem-lhe fazer perguntas como: Qual o nº de automóveis
vendidos no norte e no sul de portugal?
Ao fazer esta pergunta o utilizador já sabe ou desconfia que o
volume de vendas é afectado pela dinâmina do mercado regional.
O utilizador fez uma suposição.
Sistemas de Apoio à Decisão
29
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Data mining
Ferramentas de query versus data mining
Num estudo de data mining o utilizador não sabe o que pode
influenciar o volume de vendas. Em vez de assumir uma relação
entre a localização geográfica e o volume de vendas, ele pede à
ferramenta de data mining que tente descobrir que factores mais
influenciam o volume de vendas.
Uma ferramenta de data mining não exige nenhuma suposição, ela
tenta descobrir relações e padrões escondidos que nem sempre são
óbvios.
Sistemas de Apoio à Decisão
30
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Data mining
Ferramentas de query versus data mining
Data mining descobre padrões que guiam os utilizadores para as
perguntas correctas a efectuar com as ferramentas de query
tradicionais. Muitos vendedores de ferramentas de query já
incluem componentes de data mining no seu software.
80% da informação de interesse pode ser conseguida através de
uso de ferramentas de SQL.
Os restantes 20% de informação escondida (encoberta) requere
técnicas mais avançadas e estes 20% são de grande importância
para muitas operações empresariais.
Sistemas de Apoio à Decisão
31
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Data mining
Adriaans P. And Zantinge D., 1996
Sistemas de Apoio à Decisão
32
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Data mining
Técnicas estatísticas
Podemos começar por extrair informação simples como as médias de vendas
das diversas revistas (329 clientes em cada 1000 subscrevem revistas de
automóveis) ou a média dos atributos (média de idades dos clientes 46,9 anos).
Estes dados são importantes, pois dão-nos uma ideia de como avaliar a
performance dos algoritmos de reconhecimento de padrões. Suponhamos que
queriamos prever quantos clientes irão comprar uma revista de automóveis.
Um algoritmo que indique sempre que o cliente não vai comprar uma revista
de automóveis estará correcto para 671 casos em cada 1000 (cerca de 70% das
vezes).
Um resultado trivial que se consegue através de um método extremamente
simples chama-se previsão naife. Qualquer outro algoritmo deverá fazer
melhor.
Sistemas de Apoio à Decisão
33
Subsistema de gestão de dados
Média
Idade
46,9
Rendimento
3000
Crédito
2000
Carro
0,59
Casa
0,59
Revistas
Sistemas de Apoio à Decisão
Auto
0,329
Música
0,146
Desporto
0,447
BD
0,081
Decoração
0,702
34
Subsistema de gestão de dados
Revista
Médias
Idade
Rendimento
Crédito
Carro
Casa
Auto
29,3
3000
2200
0,48
0,53
Música
24,6
2200
1500
0,30
0,45
Desporto
42,2
3300
2100
0,70
0,60
BD
21,4
3100
1700
0,62
0,60
Decoração
48,1
3400
2500
0,58
0,76
Sistemas de Apoio à Decisão
35
Subsistema de gestão de dados
Nº clientes
400
350
300
250
200
150
100
50
0
0
1
2
3
4
5
Nº revistas subscritas
Sistemas de Apoio à Decisão
36
Subsistema de gestão de dados
Nº
subscrições
180
160
140
120
100
80
60
40
20
0
10
20
30
40
50
60
70
80
90
Idade dos compradores
Sistemas de Apoio à Decisão
37
Subsistema de gestão de dados
Nº
subscrições
180
160
140
120
100
80
60
40
20
0
10
20
30
40
50
60
70
80
90
Idade dos compradores de revistas de automóveis
Sistemas de Apoio à Decisão
38
Subsistema de gestão de dados
Nº
subscrições
100
90
80
70
60
50
40
30
20
10
0
10
20
30
40
50
60
70
80
90
Idade dos compradores de revistas de desporto
Sistemas de Apoio à Decisão
39
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Data mining
Métodos de visualização
Este métodos são muito úteis na identificação de padrões.
Realidade virtual permite ao utilizador navegar em espaços artificiais.
Animação pode ser usada para analisar dados históricos que evoluem
ao longo do tempo.
Busca de projecções de dados que revelem informação importante.
Ambiente 3D interactivos, permitem ao utilizador alterar os dados a
visualizar e escolher o ponto de vista.
Sistemas de Apoio à Decisão
40
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Data mining
Métodos de visualização
Metáfora do espaço:
Podemos determinar a distância entre 2 registos no espaço de dados: os
registos que estiverem mais próximos uns dos outros terão mais coisas
em comum; os registos mais afastados entre si pouco têm em comum.
Para isto os dados devem estar normalizados.
Os registos tornam-se pontos no espaço multidimensional e a distância
entre eles pode ser pode ser quantificada (distância Euclidiana). Podem
visualizar-se nuvens de dados.
Sistemas de Apoio à Decisão
41
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Data mining
Métodos de visualização
Idade
Cliente 1
Cliente 2
Rendimento
32
24
40.000
30.000
8
Crédito
10.000
2.000
10
8
Cliente 2
 (82
+
102
+
82) = 15
Cliente 1
Sistemas de Apoio à Decisão
42
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Data mining
Ferramentas de OLAP - Multidimensionalidade
Podemos querer saber que tipo de revista é vendida numa determinada
região por mês e por grupo de idade.
Os decisores pode querer saber a resposta a um nº infindável de
questões: agora querem saber as vendas ordenadas por região, idade e
rendimento e amanhã os mesmos dados ordenados por crédito e idade.
Normalmente estes dados fazem parte de uma enorme base de dados
que deve ser acedida online. As ferramentas OLAP tentam resolver
estas questões. Esta ferramentas guardam os dados em formato
multidimensional.
Sistemas de Apoio à Decisão
43
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Data mining
Ferramentas de OLAP - Multidimensionalidade
As ferramentas de OLAP não "aprendem" nada, não criam informação
nova. Apenas facilitam o acesso e a visualização da informação
existente.
As ferramentas de data mining não necessitam de um formato de dados
especial, podem trabalhar directamente sobre os dados da base de
dados relacional. São mais poderosas.
OLAP pode ser usados nos estados iniciais do processo de data mining
revelando possíveis padrões a procurar.
Sistemas de Apoio à Decisão
44
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Data mining
Case-based learning - k vizinhaças mais próximas
Quando interpretamos os registos como pontos no espaço de dados
podemos definir o conceito de vizinhança:
Os registos que estão próximos vivem na mesma vizinhança.
Se quisermos prever o comportamento de um determinado indivíduo,
começamos por analisar o comportamento de 10 indivíduos que estão
próximos deste no espaço de dados. Calculamos a média do
comportamento destes 10 indivíduos e este valor será a previsão do
comportamento do nosso indivíduo.
K é o nº de vizinhos que analisamos para prever o comportamento do
nosso individuo.
Sistemas de Apoio à Decisão
45
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Data mining
Case-based learning - k vizinhaças mais próximas
Este método é mais um método de busca que uma técnica de
aprendizagem, embora o mais puro, pois o próprio conjunto de dados é
usado como referência.
Para grandes conjuntos de dados este algoritmos atinge uma
complexidade elevada, por isso usa-se normalmente em sub-conjuntos
da base de dados de tamanho limitado.
Os algoritmos de data mining não devem ultrapassar a complexidade n
(log n), onde n é nº de registos.
Sistemas de Apoio à Decisão
46
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Data mining
Árvores de decisão
São adequadas para a classificação dos dados.
(var1  […]) and (var 2  […]) and…(var n  […]) =>Objecto O pertence à classe C
A ideia é descobrir as classes e as condições que as definem.
A tentativa de prever se um dado cliente terá um dado comportamento
implica a suposição que esse cliente pertence a um determinado tipo de
grupo de clientes.
Sistemas de Apoio à Decisão
47
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Data mining
Árvores de decisão
Se quisermos saber quem comprará revistas de automóveis, temos que
determinar que atributos serão mais significativos - idade ou
rendimento?
Temos que investigar se existe algum limiar no valor da idade que
separa os compradores dos não compradores.
Sistemas de Apoio à Decisão
48
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Data mining
Regras de associação
As regras de associação são sempre definidas com base em atributos
binários.
Mus, Decor => Auto
Quem lê revistas de música e de decoração muito provavelmente lê
revistas de automóveis.
O nº de regras de associação que podemos encontrar numa base de
dados é quase infinito. É dificil separar o que é realmemente
importante do que não serve para nada. É necessário medidas que
permitam fazer esta distinção.
Sistemas de Apoio à Decisão
49
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Data mining
Regras de associação
Support (prevalência) - associações que tenham muitos registos na
base de dados.
nº de registos de respeitam a regra / nº de registos da base de dados
Confidence (confiança)
nº reg. RHS da regra /nº reg. LHS da regra
nº de registo para automoveis / nº de registos para música e decoração
Sistemas de Apoio à Decisão
50
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Data mining
Regras de associação
Não existe nenhum algoritmo que automaticamente nos dê todas as
regras importantes que se podem inferir da base de dados. As regras de
associação são úteis em data mining quando já tivermos uma ideia do
que andamos à procura.
A ideia é gerar todas as possíveis regras que excedem um determinado
valor, definido pelo utilizador, para a prevalência e para a confiança.
Começa-se com as regras com apenas um item. Muitas vezes, quando a
base de dados é muito grande, recorre-se ao uso de amostragens.
Sistemas de Apoio à Decisão
51
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Data mining
Regras de associação
Exemplo:
Cod. Transacção
Hora
Produtos comprados
101
6:35
leite, pão, sumo
792
7:38
leite, sumo
1130
8:05
leite, ovos
1735
8:40
pão, bolachas, café
leite => sumo
prevalêcia - 50%
(registos que contêm ao mesmo tempo leite e sumo (2) / total de registos (4))
confiança - 66,7%
(nº registos que contêm o RHS (2)/ nº registos que contêm o LHS(3))
Sistemas de Apoio à Decisão
52
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Data mining
Redes neuronais
O cérebro humano consiste num grande nº de neurónios, cerca de 1011,
ligados uns aos outros através de um grande nº de sinapses. Um único
neurónio está ligado a outros neurónios por alguns milhares de
sinapses.
A analogia com o nosso cérebro originou o desenvolvimento das redes
neuronais artificiais. Estas redes podem ser construidas utilizando
hardware especial, mas muitas são apenas software que pode correr em
computadores vulgares.
Sistemas de Apoio à Decisão
53
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Data mining
Redes neuronais
As redes neuronais consistem numa série de nós :
• nós de entrada que recebem os sinais de entrada;
• nós de saída que fornecem os sinais de saída;
• e um nº indeterminado de camadas intermédias que contêm
os nós intermédios.
Sistemas de Apoio à Decisão
54
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Data mining
Redes neuronais
Estado de codificação - Quando a rede é treinada para
desempenhar uma determinada tarefa. Fase de apreendizagem.
Estado de descodificação - Quando a rede é utilizada para
classificar exemplos ou fazer previsões.
Sistemas de Apoio à Decisão
55
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Data mining
Redes neuronais
O conjunto de dados para treino tem que ser muito grande.
Os outputs são altamente quantitativos e não são fáceis de
compreender.
Embora elas aprendam alguma coisa e nos forneçam essa
informação, não fornecem qualquer explicação acerca dessa
informação (como? porquê?).
Sistemas de Apoio à Decisão
56
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Data mining
Redes neuronais
Perceptrons - Frank Rosenblatt, 1958. Um perceptron é uma rede
simples de 3 camadas. Nós de entrada (photo-receptors), nós
intermédios (associators) e nós de saída (responders). Podem ser
usados para executar tarefas de classificação simples.
Back propagation networks - Além dos nós de entrada e saída
possuem uma série de camadas de nós intermédios escondidos.
Sistemas de Apoio à Decisão
57
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
• Os algoritmos genéticos foram inventados por John Holland no
final dos anos 60 na Uni. de Michigan.
• Nos anos 80 e 90 apareceram as primeiras aplicações de
algoritmos genéticos a problemas reais.
• Ainda se faz muita investigação para melhorar o funcionamento
dos algoritmos genéticos.
• Estes algoritmos estão na sua infância.
Sistemas de Apoio à Decisão
58
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
• Baseiam-se nos processos genéticos e na teoria da evolução das
espécies de Darwin.
O DNA é constituído por genes formados por combinações de
nucleótidos (Adenina, Citosina, Timina, Guanina).
Ao longo do tempo, a evolução selecciona os indivíduos melhor
adaptados (Selecção natural). A evolução é um processo de
optimização: cada espécie produz um número excedente de
indivíduos, mas apenas os melhor adaptados ao meio ambiente
irão sobreviver.
Sistemas de Apoio à Decisão
59
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
Um algoritmo genético tem 2 componentes essenciais:
• Selecção - sobrevivência do mais forte
• Recombinação
Sistemas de Apoio à Decisão
60
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
De que modo é que os algoritmos genéticos diferem de outras
técnicas?
Trabalham com uma população de soluções, em vez de uma só
solução.
Usam regras de transição probabilísticas em vez de regras
determinísticas.
Sistemas de Apoio à Decisão
61
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
Quando é que se deve usar o algoritmo genético?
• Quando o “search space” é muito grande (nestes casos, a
enumeração de todas as possíveis soluções torna-se
impracticável);
• Quando os métodos tradicionais (ex: programação linear) não
são aplicáveis.
Sistemas de Apoio à Decisão
62
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
Limitações:
• Grande número de soluções possíveis (indivíduos) produzidas
ao longo do processo;
• Carácter aleatório do processo de busca;
• Requerem grande capacidade de processamento.
Sistemas de Apoio à Decisão
63
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
Como funcionam?
1) Determinar a codificação a utilizar para cada solução;
2) Inicializar aleatóriamente uma população com N indíviduos;
3) Calcular fitness de todos os indíviduos da população;
4) Criar uma nova população através do operador de selecção;
5) Efectuar “crossing-over” entre cada par de indivíduos;
6) Efectuar mutação em cada gene, com probabilidade Pm.
Sistemas de Apoio à Decisão
64
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
Codificação
• Uma solução do problema é codificada numa estrutura
(tradicionalmente, uma sequência de dígitos binários).
• A cada estrutura (solução) é associado um valor numérico
(fitness) que representa a qualidade dessa estrutura.
• Valor de “fitness” é obtido através da função objectivo.
Sistemas de Apoio à Decisão
65
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
Terminologia
11100101100010
X1, X2,…Xn
1453
gene
fitness
cromossoma
Sistemas de Apoio à Decisão
Variáveis de
decisão
66
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
Selecção
• Simula o conceito de “survival of the fittest”.
• Os mais fortes vão ter oportunidade de se reproduzirem.
• Os mais fracos tendem a desaparecer da população.
• Existem vários métodos para implementar este operador.
Sistemas de Apoio à Decisão
67
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
Exemplo: selecção usando torneio binário
• Escolhe-se um par de indivíduos da população.
• Melhor sobrevive, o pior morre.
• Repete-se este processo N vezes (N é o tamanho da população).
Sistemas de Apoio à Decisão
68
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
Exemplo: selecção usando torneio binário
Depois
Antes
Estrutura
Fitness
Estrutura
Fitness
A
8
A
8
B
2
C
4
C
4
A
8
D
5
D
5
4 torneios: (A,D) (B,C) (A,B) (C,D)
4 vencedores: A
Sistemas de Apoio à Decisão
C
A
D
69
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
“Crossing-over”
• Recombina-se 2 indivíduos (pai e mãe) e obtém-se 2 novos
indivíduos (os filhos).
No exemplo anterior, A recombina-se com C e A recombina-se
com D.
Sistemas de Apoio à Decisão
70
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
“Crossing-over”
Antes de recombinar
pai
1110100111 010
mãe
0011011010 100
Depois de recombinar
Sistemas de Apoio à Decisão
1110100111
100
filho 1
0011011010
010
filho 2
71
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
Mutação
• Com probabilidade Pm, mudar um gene de 0 para 1, ou de 1
para 0.
• Este operador costuma ser usado com uma probabilidade muito
baixa (ex: 0.001).
• É útil para manter a diversidade na população.
Sistemas de Apoio à Decisão
72
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
Mutação
Antes da mutação
Depois da mutação
1100101111
1100101101
gene 9 sofreu uma mutação
Sistemas de Apoio à Decisão
73
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
Exemplo:
A D.Amélia tem uma pastelaria e todos os dias de manhã tem que
preparar croissants e merendas. O preço de cada croissant é 0,60 €
e de cada merenda é 0,50 €.
Cada croissant leva 2 minutos a preparar e requer 10 gr de massa.
Cada merenda leva 1 minuto e requer 30 gr. A D.Amélia apenas
dispôe de 2 horas e possui 1,8 kg de massa.
Sistemas de Apoio à Decisão
74
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
Exemplo (continuação):
• Variáveis de decisão: X1 - nº de croissants a produzir
X2 - nº de merendas a produzir
• Função objectivo: 0,60 X1 + 0,50 X2
• Tamanho do cromossoma: 12
(6 dígitos binários para X1 e 6 para X2)
Exemplo:
001101101001 ---> 13 croissants e 41 merendas
Sistemas de Apoio à Decisão
75
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
Exemplo (continuação):
Restrições:
Selecção com torneio binário:
• Se os dois indivíduos são admissíveis, ganha o melhor dos
dois;
• Se só um dos indivíduos é admissível, ganha aquele que é
admissível;
• Se nenhum dos dois indivíduos é admissível, ganha aquele
que viola menos as restrições.
Sistemas de Apoio à Decisão
76
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
Exemplo (continuação):
ATENÇÃO !
Para a resolução deste problema não são precisos algoritmos
genéticos.
Para resolver este problema, nunca se iria utilizar um algoritmo
genético. Este problema resolve-se com programação linear.
… e mesmo que não fosse linear, fazia-se uma busca exaustiva e
descobria-se a solução óptima. O “search space” não é grande
(212 = 4096).
Calcular 4096 vezes a função objectivo é trivial para um computador.
Sistemas de Apoio à Decisão
77
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
Como terminar o algoritmo genético?
• Após um número pré-determinado de gerações.
• Quando não houver melhoras durante um número prédeterminado de gerações.
Sistemas de Apoio à Decisão
78
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
Valor para o tamanho da população N?
• Quanto maior for N, maior é a possibilidade de se encontrar uma
melhor solução...
• … mas quanto maior for N, mais tempo o algoritmo genético
demora.
• Existe o compromisso qualidade da solução versus tempo.
Sistemas de Apoio à Decisão
79
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
Por que é que funcionam?
• Intuitivamente, podemos fazer um paralelo com o modo como os
seres humanos são criativos e inovadores.
• Os seres humanos não criam ideias novas a partir do nada.
• Os seres humanos são criativos e inovadores quando combinam
noções que funcionam bem num contexto, com noções que
funcionam bem noutro contexto.
• Do mesmo modo, os algoritmos genéticos são inovadores quando
combinam um bocado de uma solução que funciona bem com um
bocado de outra solução que também funciona bem.
Sistemas de Apoio à Decisão
80
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
Exemplos de aplicações
• Design de estruturas de engenharia (turbina de gás do Boing 747),
• Problema de expansão de redes,
• Detecção de criminosos,
• Análise de imagens,
• Os algoritmos genéticos têm aplicação em quase todas as áreas de
engenharia, e também noutras áreas tais como finanças, medicina,
e até mesmo nas artes.
Sistemas de Apoio à Decisão
81
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
Suponhamos agora que queremos descobrir uma boa categorização
para a base de dados de revistas usando os algoritmos genéticos.
O 1º passo é encontrar uma codificação apropriada para o problema.
Uma maneira de o fazer consiste em descrever a segmentação
através de um conjunto de pontos no nosso espaço de dados (guias).
Estes pontos (guias) descrevem áreas de segmentação do espaço de
dados. A fronteira entre 2 pontos guia é definida por uma linha
equidistante a ambos os pontos.
Sistemas de Apoio à Decisão
82
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
A divisão em diferentes áreas resultante da definição destas
fronteiras chama-se diagrama de Voronoi.
No nosso caso obtivemos 5 regiões que determinam a segmentação
do nosso espaço de dados.
Um indivíduo do nosso espaço de busca consiste em 10 números
reais que descrevem as coordenadas dos 5 pontos guia (2
coordenadas cada ponto).
Sistemas de Apoio à Decisão
83
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
Adriaans P. And Zantinge D., 1996
Sistemas de Apoio à Decisão
84
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
Diagrama de Voronoi
Ponto guia
Sistemas de Apoio à Decisão
85
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Algoritmos genéticos
Procedimento:
• Seleccionar aleatoriamente um nº de indivíduos que descrevam
cada um dos 5 pontos do espaço de busca.
• Encontrar um função de fitness apropriada: distância média dos
pontos do espaço de busca ao ponto guia mais próximo.
• Definir boas relações de cross-over e mutações: Recombinamos 2
pontos de um indivíduo com 3 pontos de outro.
• Depois de algumas gerações encontraremos uma segmentação
estável para o nosso espaço de dados.
Sistemas de Apoio à Decisão
86
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Knowledge
engineering
tasks
• Inductive
logic
programming
• Association rules
• K-nearest neighbor
• Decision trees
Classification
tasks
Sistemas de Apoio à Decisão
• Neural
networks
• Genetic
algorithms
Problem solving
tasks
87
Subsistema de gestão de dados
Processo de descoberta do conhecimento
Nenhuma técnica de "machine learning" ou reconhecimento de
padrões pode ser considerada a melhor: diferentes tarefas
pressupõem diferentes tipos de técnicas.
Um sistema de data mining deve, portanto, disponibilizar diferentes
tipos de técnicas (híbrido). Durante as várias etapas da análise de
dados pode ser necessário usarem-se diversas técnicas de
descoberta de informação.
Abordagem de estratégia múltipla.
Sistemas de Apoio à Decisão
88