Introdução à Mineração de Dados com ... - INPE/ .Introdução à Mineração de Dados com Aplicações em Ciências Espaciais Escola de Verão do Laboratório Associado de Computação

  • View
    213

  • Download
    0

Embed Size (px)

Text of Introdução à Mineração de Dados com ... - INPE/ .Introdução à Mineração de Dados com...

  • ELAC 2012 http://www.lac.inpe.br/~rafael.santos Dia 1: 1 / 56

    Introduo Minerao de Dados com Aplicaes em Cincias Espaciais

    Escola de Vero do Laboratrio Associado de Computao e Matemtica Aplicada

    Rafael Santos

  • ELAC 2012 http://www.lac.inpe.br/~rafael.santos Dia 1: 2 / 56

    Programa Dia 1: Apresentao dos conceitos de minerao de dados,

    motivao e alguns exemplos. Dia 2: Algoritmos de classificao supervisionada e

    aplicaes. Dia 3: Algoritmos de classificao no-supervisionada e

    aplicaes. Algoritmos de minerao de associaes. Dia 4: Visualizao e minerao de dados. Outros algoritmos

    e idias. Onde aprender mais.

  • ELAC 2012 http://www.lac.inpe.br/~rafael.santos Dia 1: 3 / 56

    Objetivo Apresentar conceitos, tcnicas e exemplos de aplicao de

    minerao de dados. Descrever alguns dos algoritmos mais utilizados com

    exemplos de aplicao. Parte reduzida do material da disciplina CAP-359 do

    Programa de Ps-Graduao em Computao Aplicada. Math-Lite!

  • ELAC 2012 http://www.lac.inpe.br/~rafael.santos Dia 1: 4 / 56

    Introduo e Motivao

  • ELAC 2012 http://www.lac.inpe.br/~rafael.santos Dia 1: 5 / 56

    O Tsunami de Dados

    O que e como nos afeta?

    We are drowning in information but starved for knowledge. John Naisbitt, Megatrends (1984).

  • ELAC 2012 http://www.lac.inpe.br/~rafael.santos Dia 1: 6 / 56

    Introduo e Motivao

  • ELAC 2012 http://www.lac.inpe.br/~rafael.santos Dia 1: 7 / 56

    Introduo e Motivao

  • ELAC 2012 http://www.lac.inpe.br/~rafael.santos Dia 1: 8 / 56

    Introduo e Motivao Armazenamento do RAMAC

    (Random Access Method of Accounting and Control), IBM, 1956.

    50 discos de 24 pol. de dimetro.

    Quase 5 megabytes. Custo: Us$ 50.000

    Leia mais em http://en.wikipedia.org/wiki/RAMAC e http://www-03.ibm.com/ibm/history/exhibits/650/650_album.html

  • ELAC 2012 http://www.lac.inpe.br/~rafael.santos Dia 1: 9 / 56

    Introduo e Motivao

    http:/

    /www

    .little

    techs

    hopp

    e.com

    /ns16

    25/w

    inche

    st.htm

    l

    1950 1960 1970 1980 1990 2000 2010 20200.00001

    0.00010

    0.00100

    0.01000

    0.10000

    1.00000

    10.00000

    100.00000

    1000.00000

    10000.00000

  • ELAC 2012 http://www.lac.inpe.br/~rafael.santos Dia 1: 10 / 56

    Introduo1981

    ww

    w.v

    inta

    geco

    mpu

    ting.

    com

    2010

    Us$ 370/M Us$ 0.00009/MUs$ 180.

  • ELAC 2012 http://www.lac.inpe.br/~rafael.santos Dia 1: 11 / 56

    Aquisio de Dados Crescimento explosivo na capacidade de gerar, coletar e

    armazenar dados: Cientficos: imagens, sinais. Sociais: censos, pesquisas. Econmicos e comerciais: transaes bancrias e comerciais, compras,

    ligaes telefnicas, acessos web, transaes com cdigo de barras e RFID.

    Segurana: acessos sistemas em rede ( logs), e-mails corporativos, registro de atividades.

    Justificativas para este aumento: Barateamento de componentes e ambientes computacionais. Exigncias cientficas/sociais. Mudana de paradigmas (em particular na Web)!

  • ELAC 2012 http://www.lac.inpe.br/~rafael.santos Dia 1: 12 / 56

    Aquisio de Dados (Cientficos/Espaciais) Max Planck Institute for Meteorology: 220 terabytes de dados

    de pesquisa sobre o clima. LHC: Large Hadron Collider do CERN: 15 petabytes de

    dados por ano. SDSS (Sloan Digital Sky Survey): 40 terabytes de dados

    (imagens mais catlogo de 200 milhes de objetos mais outros dados).

    LSST (Large Synoptic Survey Telescope): meio petabyte de imagens por ms, catlogo de 300 terabytes por ano.

    Microsoft TerraServer: 5 terabytes (1999). INPE: 130 terabytes de imagens de sensoriamento remoto.

  • ELAC 2012 http://www.lac.inpe.br/~rafael.santos Dia 1: 13 / 56

    Aquisio de Dados (Web) CiteSeerX: 1.400.000 artigos cientficos, 27.000.000 citaes. Springer: 4.400.000 artigos cientficos. Sourceforge: 230.000 projetos de software aberto. YouTube: 45 terabytes de vdeos em 2006. Flickr: 3.7 bilhes de imagens. Facebook: 250.000.000 usurios, 45.000.000 grupos de

    interesse, 1.000.000.000 fotos por ms. Wayback machine: 2 petabytes, 20 terabytes/ms, 55 bilhes

    de pginas.

  • ELAC 2012 http://www.lac.inpe.br/~rafael.santos Dia 1: 14 / 56

    Aquisio de Dados Mdia impressa, filmes, mdia magntica e tica produziram

    aproximadamente 5 exabytes de novos dados em 2002. 1 exabyte = 1.024 petabytes = 1.048.576 terabytes.

    Consumidor americano tpico gera 100G de dados em sua vida: = 26 exabytes para a populao presente.

    Quantos registros de ligaes telefnicas? Quantas transaes de cartes por dia? Quantos acessos a diversos servidores de informao?

    O que voc tem no seu disco rgido?

  • ELAC 2012 http://www.lac.inpe.br/~rafael.santos Dia 1: 15 / 56

    Aquisio de Dados Mas o que feito destes dados? Como olhar estes dados?

    Localizar, filtrar relativamente simples... Indexar pode ser mais complicado.

    Como identificar.. Padres (X acontece se...) Excees (isto diferente de... por causa de...) Tendncias (ao longo do tempo, Y deve acontecer...) Correlaes (se M acontece, N tambm deve acontecer.)

    O que existe de interessante nestes dados? Como definir interessante?

    Informao, e no dados, valem dinheiro / tempo / conhecimento!

  • ELAC 2012 http://www.lac.inpe.br/~rafael.santos Dia 1: 16 / 56

    Dados, Informaes, Conhecimento

  • ELAC 2012 http://www.lac.inpe.br/~rafael.santos Dia 1: 17 / 56

    Minerao de Dados Parte do processo de descoberta de conhecimentos em

    bancos de dados (Knowledge Discovery in Databases, KDD). KDD: Processo geral de descoberta de conhecimentos teis

    previamente desconhecidos a partir de grandes bancos de dados (adaptado de Fayyad et al).

  • ELAC 2012 http://www.lac.inpe.br/~rafael.santos Dia 1: 18 / 56

    Minerao de Dados No SQL nem OLAP, embora estas tcnicas possam ser

    parte do processo.

  • ELAC 2012 http://www.lac.inpe.br/~rafael.santos Dia 1: 19 / 56

    Knowledge Discovery in Databases

    Dados Brutos

    Conhecimento

    Dados Selecionados

    DadosPr-Processados

    DadosTransformados

    Padres

    Seleo

    Pr-processamento

    Transformao

    Minerao

    Interpretao e Avaliao

  • ELAC 2012 http://www.lac.inpe.br/~rafael.santos Dia 1: 20 / 56

    Passos do Processo De acordo com Fayyad et. al.

    1. Compreenso do domnio da aplicao.2. Criao de conjunto de dados para descoberta.3. Limpeza e pr-processamento dos dados.4. Reduo e reprojeo.5. Escolha da tarefa de minerao de dados.6. Escolha dos algoritmos de minerao e de seus parmetros.7. Minerao de dados.8. Interpretao.9. Consolidao e avaliao.

  • ELAC 2012 http://www.lac.inpe.br/~rafael.santos Dia 1: 21 / 56

    Definies Data mining is the analysis of (often large) observational data sets to

    find unsuspected relationships and to summarize the data in novel ways that are both understandable and useful to the data owner (Hand, Mannila and Smyth, Principles of Data Mining).

    Data mining is an interdisciplinary field bringing together techniques from machine learning, pattern recognition, statistics, databases, and visualization to address the issue of information extraction from large data bases (Evangelos Simoudis, citado em Daniel T. Larose, Discovering Knowledge in Data An Introduction to Data Mining).

  • ELAC 2012 http://www.lac.inpe.br/~rafael.santos Dia 1: 22 / 56

    Definies Interseo com outras tcnicas e cincias. No a nova estatstica! Usa muitos conceitos e tcnicas de estatstica,

    reconhecimento de padres, aprendizado por mquina, inteligncia artificial, bancos de dados, processamento de alto desempenho, visualizao, etc.

    Tem carter exploratrio e prtico. No dispensa interao e superviso humanas!

  • ELAC 2012 http://www.lac.inpe.br/~rafael.santos Dia 1: 23 / 56

    Casos (Comerciais) Amazon.com: melhoria da customizao da interface com o

    usurio (melhoria de vendas por indicao), eliminao de fraudes.

    1-800-FLOWERS.com: compreenso e antecipao de comportamento de clientes, descoberta de tendncias e explicao de observaes (CRM).

    U.S. Census Bureau: anlise de dados espaciais (com SAS e software da ESRI) de ensino pblico para determinar polticas para melhoria na educao.

    Japan Credit Bureau: melhoria da resposta a campanhas de marketing, reteno de clientes, identificao de novos segmentos de mercado.

    SAS Success stories: http://www.sas.com/success/technology.html

  • ELAC 2012 http://www.lac.inpe.br/~rafael.santos Dia 1: 24 / 56

    Casos (Comerciais) Columbia Interactive/Columbia University: Anlise de visitas a

    sites, coletando trilhas de usurios (como usam o site, que pginas so mais atraentes para usurios, quando usurios deixam o site) para melhorar interatividade e planejar contedo.

    Casino: cadeia com 115 hipermercados, 400 supermercados, mais de 4000 lojas e 260 lanchonetes. Criou programa de cartes de fidelidade e tem coletado dados dos cartes e hbitos de consumo.

    TIM (Telecom Italia Mobile): reduo de churn, anlise de comportamento do usurio e segmentao do banco de dados de usurios.

    SAS Success stories: http://www.sas.com/success/technology.html

  • ELAC 2012 http://www.lac.inpe.br/~rafael.santos Dia 1: 25 / 56

    Casos (Comerciais) IMS America: Empresa de pesquisa de mercado farmacutico,

    mantm um banco de dados de 1.5 bilhes de prescries de 600.000 mdicos, usadas em 33.000 farmcias. Usa o banco para verificar que mdicos mudaram seu padro de prescries para informar companhias farmacuticas, que podem decidir por campanhas de marketing d