Upload
internet
View
108
Download
4
Embed Size (px)
Citation preview
Descoberta de Conhecimento em BDDescoberta de Conhecimento em BD
Jacques Robin e Ricardo Bezerra
Motivação: da seca de dados até o Motivação: da seca de dados até o diluviodiluvio
Informatização dos meios produtivos permitiu a geração de grandes volumes de dados:• Transações eletrônicas;• Novos equipamentos científicos e industriais para
observação e controle;• Dispositivos de armazenamento em massa;
Aproveitamento da informação permite ganho de competitividade: “conhecimento é poder (e poder = $$!)”
Recursos de análise de dados tradicionais são inviáveis para acompanhar esta evolução: • processo iterativo de criação, teste e refinamento de
hipóteses;
Motivação: inundação de informaçãoMotivação: inundação de informação
“Morrendo de sede por conhecimento em um oceano de dados”
Gigantismo do problema de análise de dados para tomada de decisão:• BD da Wal-Mart: 20 milhões de transações por dia• Data Warehouse da Mobil: 100 TB• BD da NASA: recebe de satélites 50 GB por hora
Solução: • ferramentas de automatização das tarefas repetitivas e
sistemática de análise de dados• ferramentas de auxílio para as tarefas cognitivas da análise• integração das ferramentas em sistemas apoiando o processo
completo de descoberta de conhecimento para tomada de decisão
Exemplo preliminarExemplo preliminar
Problema do mundo dos negócios, entender o perfil dos clientes:• desenvolvimento de novos produtos;• para controle de estoque em postos de distribuição;• propaganda mal direcionada gera maiores gastos e
desestimula o possível interessado a procurar as ofertas adequadas;
Situação:• empresa possui registro de todas as transações efetuadas;• mas como aproveitar dessa riqueza de dados?
Categorias: • produtos de esporte; • eletrodomésticos;• produtos de entretenimento;• produtos para o lar;
Processo mínimo de Processo mínimo de descoberta de conhecimentodescoberta de conhecimento
Compreensão do domínio e dos objetivos da tarefa;Criação do conjunto de dados envolvendo as variáveis necessárias;
Operações como identificação de ruídos, outliers, como tratar falta de dados em alguns campos, etc.
Redução de dimensionalidade, combinação de atributos;
Escolha e execução do algoritmo de acordo com a tarefa a ser cumprida
Interpretação dos resultados, com possível retorno aos passos anteriores;
Consolidação: incorporação e documentação do conhecimento e comunicação aos interessados;
1. Seleção de dados e 2. pré-1. Seleção de dados e 2. pré-processamentoprocessamento
Com seu conhecimento do domínio, analista humano decide:
• que as informações relevantes a-priori encontram-se nas seguintes tabelas: clientes: nome, identificação, idade, sexo, estado civil,
endereço, renda, proprietário da casa; produtos: nome, identificação, preço, categoria, quantidade em
estoque, quantidade encomendada; transações: identificador de cliente, identificador de produto,
data e hora, quantidade;
• Eliminar registros incompletos, inconsistentes, etc.
3. Transformação de dados3. Transformação de dados
Agrupando informações em uma única tabela;
4. Data mining stricto sensus4. Data mining stricto sensus
Decidiu-se aplicar um algoritmo de aprendizado para agrupar os clientes em quatro conjuntos• ex.: rede de Kohonen do tipo vector quantization;
Idéia do algoritmo é dispor, em conjuntos, clientes que apresentem aspectos similares;
Posteriormente, os dados são organizados em uma planilha, onde o número do grupo (1, 2, 3, ou 4) é utilizado como chave primária;
A planilha calcula estatísticas de cada grupo, comparando-as com toda população;
5. Apresentação dos resultados5. Apresentação dos resultados
Analista humano:• ainda precisa do seu conhecimento do domínio • para interpretar esses resultados em conhecimento marketing
Descoberta de Conhecimento em BDDescoberta de Conhecimento em BD
“O processo:• não trivial de extração de informações implícitas, • anteriormente desconhecidas, • e potencialmente úteis de uma fonte de dados”;
“Torture os dados até eles confessarem”; O que é uma descoberta, afinal?
• Exibir todos os empregados que ganham dentro de uma determinada faixa salarial é uma descoberta?
O que é um padrão interessante?• Válido, Novo, Útil, Interpretável (objetividade difícil)• que é conhecimento?: { X | f(X, V, N, U, I) > T}
KDD x KDD x Data MiningData Mining
Mineração de dados: passo do processo de KDD que produz um conjunto de padrões sob um custo computacional aceitável;
KDD: • utiliza algoritmos de data mining para extrair padrões
classificados como “conhecimento”• incorpora também tarefas como escolha do algoritmo
adequado, processamento e amostragem de dados e interpretação de resultados;
O perigo da falta de interpretaçãoO perigo da falta de interpretação
Hospital A Hospital B
MorreramSobreviveram
632037
16784
Total 2100 800
3% 2%
O hospital A parece ser o menos adequado.
O perigo da falta de interpretação (cont.)O perigo da falta de interpretação (cont.)
Números x Bom-senso: 1. Mentiras, 2. Mentiras danadas, 3. Estatísticas
... e data mining?
Hosp. A Hosp. B
MorreramSobreviveram
6594
Total 600 600
8592
Hosp. A Hosp. B
MorreramSobreviveram
571443
Total 1500 200
8192
1% 1.3%
3.8% 4%
Boas condições
Más condições
O hospital A é melhor!
A busca por causalidadeA busca por causalidade
Correlação não é o mesmo que causalidade• “lama” e “chuva” são dois conceitos relacionados, mas como
inferir que um é causa do outro?• A média de idade da Flórida é grande. O clima da Flórida faz
as pessoas viverem mais? Explicação plausível: muitas pessoas mudam-se pra lá quando se
aposentam;
Experimentos controlados KDD necessariamente:
• processo exploratório, iterativo e interativo • envolvendo em cada passo um especialista humano• tanto (se não mais) importante do que método de mineração:
auxílio ao gerenciamento do processo (Knowledge Management) integração transparente de ferramentas
Processo mais abrangente de Processo mais abrangente de descoberta de conhecimentodescoberta de conhecimento
TaskDiscovery
Goal
DataDiscovery
OutputGeneration
DataAnalysis
ModelDevelopment
DataCleaning
DomainModel
Report
Action
Model
MonitorQuerytools
Statistic & AI tools
Visua-lization
tools
Presen-tationtools
Data transfor-mationtools
Database
KeyInputOutputToolProcess task
Process flowData flowTool usage
KDD: problema pluridisciplinarKDD: problema pluridisciplinar
Inteligência Artificial• aprendizado de máquina;• representação de conhecimento e inferência;• geração automática de resumos textuais;
Estatística: análise exploratória de dados; Computação gráfica: visualização de dados; Bancos de dados:
• integração, consolidação e remodelagem de dados para processamento analítico (data warehousing)
• linguagens de consulta para: hipercubos de dados (OLAP) funções de mineração (OLAM)
Integração:• APIs entre ferramentas, disponibilização na Web, • BD dedutivos, ativos, temporais, OOs, de restrições
Camada 4: tecnologia deProcessamento de Linguagem Natural e Lingüística Computacional
Gramática Computacional
Léxico Computacional
Estratégias de planejamento
de hipertexto
HYSSOP: Gerador automático de hipertexto emlinguagem natural
Hipertexto em linguagem natural resumindo os insights descobertos
Regras de exploração de hipercubo de dados
SGBD dedutivo orientado a objetos
Regras de seleção de conteúdo de resumos
Camada 3: tecnologias deSistemas EspecialistasDedução AutomáticaBD Dedut DOivosBD Orientada a Objetos
Conteúdo selecionado para o resumo: conjunto de predicados de objetos
Camada 2: tecnologias deAprendizagem de MàquinaIndução AutomáticaMineração de Dados
ExceptionMiner: minerador de células e subcubos atípicos em hipercubos de dados
Outros aplicativos de mineração de dados
conectados via Java
DOODCI: API SGBDDOO / Java para OLAP e mineração de exceções
Servidor OLAPCamada 1: tecnologias deBD AtivosData Warehousing BD Dimensionais e OLAP
JDCI: API Java / Servidor OLAP
Esquema Relacional
BD operacional(para OLTP)
Esquema Dimensional
Data Warehouse:Hipercubo de dados
Assistente de Remodelagem de Dados
Regras de carga e atualização de dados
SGBD ativo
Arquivos de log:Servidor WebGerenciador de BannersServidor RoboCup
integrada
Exemplo de
Arquitetura
Ex, conhecimento extraído de um BD de supermercado:• No ano passado, as variações de vendas mais incomuns foram:
Soda Diet com decrescimento de 40% na região nordeste de julho a agosto Cerveja Bavaria com crescimento de 42% nacional de setembro a outubro; ...
Outro exemplo de passos e saída de KDDOutro exemplo de passos e saída de KDD
BD Relacion
al
Base de
Conhecimento
Data Warehou
seDimensio
nal
AprendizagemMineraçãode Dados
Arquivos de Log
Páginas Web
Geração de Linguagem
Natural
•A diminuição de 40% das vendas de soda diet de julho a agosto na região nordeste foi realmente atípica porque:
para as outras regiões, a variação média das vendas desse produto no mesmo período foi um aumento de 9%;
para o ano todo, as vendas desse produto nessa mesma região decresceram de apenas 7%;
as vendas globais, de todos os produtos, nessa região e no mesmo periódo, decresceram de apenas 2%
Volta
Tarefas básicasTarefas básicas
Previsão• Cálculo de variáveis de interesse a partir dos valores de um
conjunto de variáveis de explicação;• É comunamente visada em aprendizado de
máquina/estatística;• Exemplos: classificação e regressão;
Descrição• Reportar relações entre as variáveis do modelo de forma
simétrica;• À princípio, está mais relacionada ao processo de KDD;• Exemplos: agrupamento, sumarização (incluindo sumário de
textos), dependências, análise de desvio;
Exemplo de previsão (I)Exemplo de previsão (I)
Um hiperplano paralelo de separação: pode ser interpretado diretamente como uma regra:• se a renda é menor que t,
então o crédito não deve ser liberado
Exemplo: • árvores de decisão;• indução de regras
renda
déb
ito
xx
xx
x
x
x
o
oo
oo
o
o
o
o
t
sem crédito
o
o: exemplo aceitox: exemplo recusado
Análise de crédito
Exemplo de previsão (II)Exemplo de previsão (II)
Hiperplano oblíquo: melhor separação:
Exemplos: • regressão linear;• perceptron;
Análise de crédito
renda
déb
ito
xx
xx
x
x
x
o
oo
oo
o
o
o
o
t
sem crédito
o
o: exemplo aceitox: exemplo recusado
Exemplo de previsão (III)Exemplo de previsão (III)
Superfície não linear: melhor poder de classificação, pior interpretação;
Exemplos: • perceptrons
multicamadas;• regressão não-linear;
Análise de crédito
renda
déb
ito
xx
xx
x
x
x
o
oo
oo
o
o
o
o
t
sem crédito
o
o: exemplo aceitox: exemplo recusado
Exemplo de previsão (IV)Exemplo de previsão (IV)
Métodos baseado em exemplos;
Exemplos:• k-vizinhos mais
próximos;• raciocínio baseado em
casos;
Análise de crédito
renda
déb
ito
xx
xx
x
x
x
o
oo
oo
o
o
o
o
t
sem crédito
o
o: exemplo aceitox: exemplo recusado
Exemplo de descrição (I)Exemplo de descrição (I)
Agrupamento Exemplo:
• vector quantization;
renda
déb
ito
++
++
+
+
+
+
++
++
+
+
+
+
t
+
+: exemplo
Análise de crédito
Exemplo de descrição (II)Exemplo de descrição (II)
Regras de associação• “98% dos consumidores que adquiriram pneus e acessórios
de automóveis também se interessaram por serviços automotivos”;
• descoberta simétrica de relações, ao contrário de métodos de classificação
qualquer atributo pode ser uma classe ou um atributo de discriminação;
Métodos
Exemplo de descrição (III)Exemplo de descrição (III) Previsão de séries temporais
Iden
tifi
caçã
o d
os in
vest
imen
tos
mai
s p
rom
isso
res
nos
pró
xim
os 3
0 d
ias;
Garimpando resultadosGarimpando resultados
Transformar 1.000.000 de registros em mil regras é bom, mas... o que fazer com estas 1000 regras?
Mineração de Conhecimento Medidas de utilidade:
• subjetivas dependentes de domínio; demanda especialistas com tempo livre;
• objetivas mais independentes; ex, grau de surpresa;
• Validade utilizando limiares de confiança, apenas as regras (por
exemplo) mais importantes seriam apresentadas;• E as exceções?
ruído ou pepita de conhecimento
Distinguir pepitas de ruídoDistinguir pepitas de ruído
Regras cobrindo cobrem apenas uma pequena quantidade de dados:• potencial para descrever relações interessantes e
anteriormente despercebidas;• porém, são facilmente descartadas em filtragens por limiar
de grau de cobertura; como distingui-las de ruído?
Idéia do algoritmo: • criar pequenas generalizações das regras em estudo e
comparar a cobertura obtida;
Algoritmo para regras de pequeno Algoritmo para regras de pequeno alcancealcance
para cada antecedente a de uma regra• se a é categórico, retire-o da regra;• se a é contínuo, aumente o intervalo no qual o antecedente é
válido;• conte o número D de vezes em que a classe obtida é diferente da
classe da regra original; calcule uma medida M em função de D e do total de
antecedentes N.• exemplo: M = D/N;
valores altos de M tenderão a capturar as relações mais úteis;
EscalabilidadeEscalabilidadetécnicas para acelerar a mineração de BD gigantestécnicas para acelerar a mineração de BD gigantes
Amostragem• redução de precisão;
Algoritmos distribuídos• particionar o banco de dados em p partições;• utilizar um processador diferente para cada partição;• utilizar um método de combinação de resultados;
Paralelismo (intra-algorítimico)
Aplicabilidade de KDDAplicabilidade de KDD
Onde o processo de descoberta de conhecimento deve ser aplicado?• A tarefa é propícia ao estudo de novos experimentos;• não há nenhuma outra boa alternativa de análise de dados;• disponibilidade de dados suficientes;
com nível aceitável de ruído; sem problemas de ordem jurídica;
• especialistas disponíveis para avaliação do grau de interesse das descobertas obtidas; seleção de atributos; descrição de conhecimento a priori em geral;
Kefir (Key Findings Reporter)Kefir (Key Findings Reporter)
Análise de desvios• descoberta de diferenças significativas entre valores
medidos e valores anteriores ou padrões; Funções do Kefir
• descobrir, explicar e relatar derivações chave; Finding
• Conjunto de valores relacionados (atual, anteriores, padrão) de uma dada medida;
Health-KefirHealth-Kefir Motivação: organizações precisam controlar gastos com
saúde, planejando medidas que venham a diminuir gastos futuros. MAS,...• gasta-se muito tempo preparando-se relatórios, perdendo-
se oportunidade importantes; Oportunidade para análise automática de dados:
• métodos do mercado de saúde baseiam-se em medidas padrões de vários aspectos, como preço, uso e qualidade;
• dimensões principais: população: empregados de uma empresa, moradores de um
bairro...; área de estudo: nascimentos prematuros, internações...; medidas: tempo de internação...
Health-KefirHealth-Kefir
O grau de interesse em um desvio está diretamente relacionado ao benefício atingível através das ações possíveis;• os desvios interessantes são aqueles que indicam
problemas que podem ser corrigidos;• significância estatística;
Pagamentos_por_caso• desvios crescentes desta medida são altamente relevantes
para o sistema Health-Kefir;• como reduzir custos futuros;
Health-KefirHealth-Kefir
Cálculo de desvio para cada setor e subsetor;• extrapolação linear;
92 93 94 95
valores padrões
valores reais
desvio
tempo
med
ida
Health-KefirHealth-Kefir
Explicações• identificação do subsetor(es) mais responsável(is) pelo
desvio encontrado;• recursivo;
internação
morte admissão
cirurgia clínica mental gravidez
Health-KefirHealth-Kefir
Recomendação• os relatórios preparados precisam indicar soluções;• uso de conhecimento de domínio para realizar tal tarefa:
SE medida = admissão_por_1000 E setor = partos_prematuros E percentagem_mudança > 0.10RECOMENDE “Iniciar um programa de acompanhamento pré-natal”COM percentagem_de_economia = 0.6
Health-Kefir: exemplo de saídaHealth-Kefir: exemplo de saída
Admissões médicas
O tempo médio de permanência nesta área de estudo cresceu 22,6%, de 4,1 a 5,1. Em torno de $36.000 poderiam ser economizados se o tempo médio de permanência se mantivesse no valor esperado de 4,9. Se esta tendência permanecer, resultará em gastos adicionais de $263.000 de despesas adicionais.
Explicações: o aumento desta medida está relacionada ao aumento do tempo médio de permanência, no Medical Nervous System, em 247,9%, de 4.4 para 15.2.
Recomendação: ...
Economia prevista: $79.000
SKICAT SKICAT (Sky Image Cataloging and Analysis Tool)(Sky Image Cataloging and Analysis Tool)
Digital Palomar Observatory Sky Survey• banco de dados com três terabytes de imagens da ordem
de dois bilhões de objetos celestes; Tarefas:
• diferenciar estrelas de galáxias uma vez classificadas, análise científicas mais específicas são
aplicadas;
• classificar objetos de brilho fraco
SKICAT: SKICAT: algoritmo de aprendizadoalgoritmo de aprendizado
Regras extraídas de algoritmos de geração de árvores originam-se de uma única árvore;
RULER• alternativa: geração de várias árvores. Somente as
melhores regras de cada árvore são mantidas;• Divide-se a base de dados em vários conjuntos treinamento
(para árvores) e teste (para regras);• Podando regras: calcula-se a chance de que uma dada
premissa esteja correlacionada com a classe especificada por pura sorte;
• Produz-se, assim, uma base robusta de regras;• Redução da base por um algoritmo de cobertura de
conjuntos;
SKICAT: pré-processamentoSKICAT: pré-processamento
“Em problemas de classificação, a escolha dos atributos utilizados para definir exemplos é o fator mais determinante do sucesso ou fracasso do processo de aprendizado”• garbage in, garbage out;
Uso de um programa público de processamento de imagens:• baseado nos agrupamentos de pixels constituindo cada objeto
detectado, produzem-se os atributos básicos discriminadores ex,: brilho e orientação;
SKICAT: SKICAT: Gerenciando o conhecimentoGerenciando o conhecimento
Catálogo de objetos on-line utilizando-se um gerenciador de banco de dados• permitir ao usuário localizar corpos celestes e consultar
informações dos mesmos; Casamento de objetos obtidos de fontes diferentes;
Endereços interessantesEndereços interessantes
KDNuggets Directory• http://www.kdnuggets.com
The Data Mine• http://www.cs.bham.ac.uk/~anp/TheDataMine.html
Microsoft Decision Theory and Adaptive Systems• http://research.microsoft.com/dtas/
DBMiner: demonstração• http://db.cs.sfu.ca/DBMiner/dbmdemo.html
ReferênciasReferências Bigus, J. (1995). Data Mining with Neural Networks. McGraw-Hill. Fayyad, U.; Haussler, D.; Stolorz, P. (1996). "KDD for Science Data
Analysis: Issues and Examples”. Proceedings of Second International Conference on Knowledge Discovery and Data Mining (KDD-96), AAAI Press. Disponível no endereço http://research.microsoft.com/ ~fayyad.
Fayyad, U. M.; Piatesky-Shapiro, G.; Smyth, P. (1995). “From Data Mining to Knowledge Discovery: An Overview”, em Advances in Knowledge Discovery and Data Mining. AAAI Press.
Freitas, A. A. (1997). “On objective measures of rule surprisingness”. Em Proceedings of the 2nd European Symposium Principles of Data Mining and Knowledge Discovery. Disponível no endereço http://dainf.cefetpr.br/~alex/thesis.html.
ReferênciasReferências
Imielinski, T; Mannila, H. (1996). “A Database Perspective on Knowledge Discovery”. Communications of the ACM, volume 39, número 11.
Matheus, C.; Piateteky-Shapiro, G.; McNeill, D. (1995). ”Selecting and Reporting What is Interesting”. Em Advances in Knowledge Discovery and Data Mining. AAAI Press.
Spirtes, P.; Glymour, C; Scheines, R. (1993). Causation, Prediction and Search. Lecture Notes in Statistics, 83. Springer-Verlarg. Disponível no endereço http://hss.cmu.edu/html/departments/ philosophy/TETRAD.BOOK/book.html