88
Sistemas de Apoio à Decisão 1 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. Subsistema de gestão de dados

Data mining Metáfora :

  • Upload
    misu

  • View
    82

  • Download
    0

Embed Size (px)

DESCRIPTION

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. - PowerPoint PPT Presentation

Citation preview

Sistemas de Apoio à Decisão 1

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 2

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 3

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 4

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 5

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;

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 6

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 7

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 8

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 9

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

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 10

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?"

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 11

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 12

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 13

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 14

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 15

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 16

Subsistema de gestão de dados

Nome Data nascimento

Rendimento Crédito Carro Casa

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 17

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 18

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 19

Subsistema de gestão de dados

Nº Clientec

Data nascimento

Rendimento Crédito Carro Casa Morada Data subscrição

Revista

12003 13-04-76 3.000.000 1.100.000 Não Não R. Alegria 12

15-04-94 Auto

12003 13-04-76 3.000.000 1.100.000 Não Não R. Alegria 12

21-06-93 Música

12003 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 20

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 21

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 22

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 23

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 24

Subsistema de gestão de dados

Nº Cliente

Idade Rendimento Crédito Carro Casa Região Mês subscrição

Revista

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 25

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

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 26

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 27

Subsistema de gestão de dados

Nº Cliente

Idade Rendimento Crédito Carro Casa Região Auto Mús. Bd Desp. Decor.

23003 20 3000 1000 0 0 1 1 1 1 0 1

23009 30 6000 2000 1 0 1 0 0 1 0 0

Sistemas de Apoio à Decisão 28

Processo de descoberta do conhecimento

Data miningNã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

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 29

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 30

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 31

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 32

Processo de descoberta do conhecimento

Data mining

Subsistema de gestão de dadosSubsistema de gestão de dados

Adriaans P. And Zantinge D., 1996

Sistemas de Apoio à Decisão 33

Processo de descoberta do conhecimento

Data miningTécnicas estatísticasPodemos 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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 34

Subsistema de gestão de dados

Média

Idade 46,9

Rendimento 3000

Crédito 2000

Carro 0,59

Casa 0,59

Revistas

Auto 0,329

Música 0,146

Desporto 0,447

BD 0,081

Decoração 0,702

Sistemas de Apoio à Decisão 35

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 36

Subsistema de gestão de dados

0

50

100

150

200

250

300

350

400

0 1 2 3 4 5Nº revistas subscritas

Nº clientes

Sistemas de Apoio à Decisão 37

Subsistema de gestão de dados

0

20

40

60

80

100

120

140

160

10 20 30 40 50 60Idade dos compradores

Nº subscrições

70 80 90

180

Sistemas de Apoio à Decisão 38

Subsistema de gestão de dados

0

20

40

60

80

100

120

140

160

10 20 30 40 50 60Idade dos compradores de revistas de automóveis

Nº subscrições

70 80 90

180

Sistemas de Apoio à Decisão 39

Subsistema de gestão de dados

0

10

20

30

40

50

60

70

80

10 20 30 40 50 60Idade dos compradores de revistas de desporto

Nº subscrições

70 80 90

90

100

Sistemas de Apoio à Decisão 40

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 41

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 42

Processo de descoberta do conhecimento

Data mining

Métodos de visualização

Subsistema de gestão de dados

Cliente 1

Cliente 2

Idade Rendimento Crédito

Cliente 1 32 40.000 10.000Cliente 2 24 30.000 2.000

8 10 8

(82 + 102 + 82) = 15

Sistemas de Apoio à Decisão 43

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 44

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 45

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 46

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 47

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 48

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 49

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.

 

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 50

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

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 51

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 52

Processo de descoberta do conhecimento

Data mining

Regras de associação

Exemplo:

Subsistema de gestão de dados

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 => sumoprevalê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 53

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 54

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 55

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 56

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ê?).

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 57

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 58

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 59

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.

Subsistema de gestão de dados

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 60

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

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 61

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 62

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 63

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 64

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 65

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 66

Processo de descoberta do conhecimento

Algoritmos genéticos

Terminologia

Subsistema de gestão de dados

11100101100010

gene

cromossoma

X1, X2,…Xn 1453

Variáveis de decisão

fitness

Sistemas de Apoio à Decisão 67

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 68

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).

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 69

Processo de descoberta do conhecimento

Algoritmos genéticos

Exemplo: selecção usando torneio binário

Subsistema de gestão de dados

Estrutura Fitness

A 8

B 2

C 4

D 5

Estrutura Fitness

A 8

C 4

A 8

D 5

Antes Depois

4 torneios: (A,D) (B,C) (A,B) (C,D) 

4 vencedores: A C A D

Sistemas de Apoio à Decisão 70

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).

Subsistema de gestão de dados

No exemplo anterior, A recombina-se com C e A recombina-se com D.

Sistemas de Apoio à Decisão 71

Processo de descoberta do conhecimento

Algoritmos genéticos

“Crossing-over”

Subsistema de gestão de dados

1110100111 010

0011011010 100

Antes de recombinar

pai

mãe

filho 2

filho 1

1110100111

0100011011010

100

Depois de recombinar

Sistemas de Apoio à Decisão 72

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 73

Processo de descoberta do conhecimento

Algoritmos genéticos

Mutação

Subsistema de gestão de dados

           

Depois da mutação

gene 9 sofreu uma mutação

Antes da mutação

1100101111 1100101101

Sistemas de Apoio à Decisão 74

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.

Subsistema de gestão de dados

           

Sistemas de Apoio à Decisão 75

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

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 76

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 77

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 78

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 79

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 80

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 81

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 82

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 83

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).

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 84

Processo de descoberta do conhecimento

Algoritmos genéticos

Subsistema de gestão de dados

Adriaans P. And Zantinge D., 1996

Sistemas de Apoio à Decisão 85

Processo de descoberta do conhecimento

Algoritmos genéticos

Subsistema de gestão de dados

Diagrama de Voronoi

Ponto guia

Sistemas de Apoio à Decisão 86

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.

Subsistema de gestão de dados

Sistemas de Apoio à Decisão 87

Subsistema de gestão de dadosProcesso de descoberta do conhecimento

Classification tasks

Problem solving tasks

Knowledge engineering

tasks

• Genetic algorithms

• Inductive logic programming

• Association rules• K-nearest neighbor• Decision trees

• Neural networks

Sistemas de Apoio à Decisão 88

Subsistema de gestão de dadosProcesso 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.