Conceitos de Mineração de Dados Multimí ão de dados

  • View
    212

  • Download
    0

Embed Size (px)

Text of Conceitos de Mineração de Dados Multimí ão de dados

  • Captulo

    1Conceitos de Minerao de Dados Multimdia

    Rafael Santos

    Resumo

    Avanos recentes em vrias reas tecnolgicas possibilitaram um crescimento ex-plosivo na capacidade de gerar, coletar e armazenar dados. O barateamento e popular-izao de dispositivos de coleta e reproduo multimdia e a Internet colaboram para queexista uma quantidade vastssima de dados prontos para uso, mas em muitos casos semuma estruturao que facilite a busca de informaes interessantes ou relevantes.

    Minerao de Dados (Data Mining) o nome dado a um conjunto de tcnicase procedimentos que tenta extrair informaes de nvel semntico mais alto a partir dedados brutos, em outras palavras, permitindo a anlise de grandes volumes de dadospara extrao de conhecimento. Este texto apresenta conceitos de minerao de dadosmultimdia, (imagens, sons, vdeos e outros), algumas aplicaes existentes e possveisreas de aplicao e pesquisa.

    1.1. IntroduoEstamos nos afogando em informao mas com sede de conhecimento John Naisbitt,

    Megatendncias.

    Avanos recentes em vrias reas tecnolgicas possibilitaram um crescimento ex-plosivo na capacidade de gerar, coletar, armazenar e transmitir dados digitais. Na primeiradcada do sculo 21 j temos a possibilidade de armazenar vrios gigabytes em disposi-tivos portteis e alguns poucos terabytes em computadores pessoais a um custo acessvel.

    Sistemas interligados em rede permitem a coleta de dados de terminais simples,que so armazenados em grandes bases de dados centralizadas. Cmeras e filmadoras dig-itais permitem a captura de dados multimdia em vastas escalas a custo baixssimo, pro-gramas de rdio e televiso podem ser armazenados digitalmente de forma relativamentesimples, e a prpria Internet uma fonte praticamente inesgotvel de dados multimdiaque so coletados e armazenados de forma distribuda.

  • Dados coletados e armazenados podem ser de diversas naturezas e servir a diversasfinalidades. Alguns exemplos de esforos de coleta de dados envolvendo grandes volumesso apresentados a seguir:1

    O LHC (Large Hadron Collider) um acelerador de partculas instalado prximoda fronteira entre Sua e Frana. Ele contm quatro detetores de partculas queregistram 40 milhes de eventos por segundo, registrados por 150 milhes de sen-sores. O volume de dados pr-processados aproximadamente igual a 27 terabytespor dia2.

    O Instituto Nacional de Pesquisas Espaciais tem uma base de dados de imagens desatlite com mais de 130 terabytes [29].

    O projeto Internet Archive3 mantm um arquivo de diversos tipos de mdia, con-tendo 2 petabytes e crescendo cerca de 20 terabytes por ms, com aproximadamente130.000 vdeos, 330.000 arquivos de udio, quase 500.000 documentos de texto eindexando 85 bilhes de pginas em vrias verses.

    De acordo com algumas estimativas4, o site YouTube continha 45 terabytes devdeos em 2006. O site Flickr tinha 2 bilhes de fotografias digitais5 em 2007 (eum teste rpido mostrou que j so ao menos 2.2 bilhes). Considerando que umaimagem, suas variantes criadas pelo site e outros dados como comentrios ocupemum mnimo de 300 kilobytes, toda a coleo usa mais de 614 terabytes no total.

    O banco de dados GenBank contm colees anotadas de sequncias de nucleotdeose protenas de mais de 100.000 organismos, em um total de 360 gigabytes6.

    O Large Synoptic Survey Telescope contm uma cmera digital de aproximada-mente 3.2 gigapixels e deve coletar 20 a 30 terabytes de imagens por noite7. Oprojeto Pan-STARRS, quando completo, usar quatro telescpios, cada um comuma cmera de 1.4 gigapixels, para coletar aproximadamente 4 petabytes de im-agens por ano. Como o levantamento ser refeito vrias vezes, poder criar umfilme de 10 terapixels em cinco bandas do espectro com 50 cenas, para detectarmudanas no espao visvel8.

    1Algumas destas estatsticas foram obtidas de stios oficiais e algumas de fontes no confirmveis comoblogs. No existe maneira de obter algumas informaes sobre volume de bancos de dados de algunsservios como YouTube, Google, etc. para uma estimativa mais atualizada sugiro fazer novas buscas emsites especializados.Algumas empresas como IDC (http://www.idc.com/) fornecem relatrios com estatsticas e estimativas deuso regional e mundial de armazenamento e uso de banda de rede, a custos bastante elevados.

    2http://gridcafe.web.cern.ch/gridcafe/animations/LHCdata/LHCdata.html3http://www.archive.org/index.php4http://www.businessintelligencelowdown.com/2007/02/top_10_largest_.html5http://www.techcrunch.com/2007/11/13/2-billion-photos-on-flickr6ftp://ftp.ncbi.nih.gov/genbank/gbrel.txt7http://www.on.br/glimpse/presentations/C-Smith.ppt8http://www.on.br/newastronomy/presentations/J-Tonry.ppt

  • Um levantamento feito pela Winter Corporation9 menciona algumas bases de dadosde grande porte em uso (em 2005): Yahoo! (100 terabytes), AT&T (93 terabytes),Amazon (24 terabytes), Cingular (25 terabytes).

    Para ter uma idia aproximada do que representam terabytes e petabytes usandooutras medidas para comparao, consideremos:

    Um disco de um terabyte custa aproximadamente 200 dlares. Um ano de ar-mazenamento dos dados do LHC custa ento quase dois milhes de dlares semconsiderar a necessidade de armazenamento redundante.

    Para transmitir um petabyte de dados em uma rede com velocidade de 100 Megabits/segundoseriam necessrios 86 milhes de segundos, ou quase 2 anos e 9 meses.

    Um petabyte pode ser gravado em 223.000 DVDs (4.7 gigabytes por DVD), quecolocados dois por capa formariam uma pilha de 1.12 quilmetros de altura. Se otempo de criao de cada DVD for de 15 minutos e tivssemos cem computadorespara criar os DVDs, seriam necessrios mais de 23 dias para completar a gravao.

    Apesar destes nmeros apresentados serem relacionados a grandes projetos com-erciais e cientficos, podemos tambm observar efeitos da avalanche de dados no dia-a-dia: qualquer usurio de computadores com uso moderado da Internet tende a armazenarimagens, mensagens, documentos, vdeos em seus computadores, que podem facilmenteocupar dezenas de gigabytes. O nmero tende a aumentar para usurios frequentes demquinas fotogrficas e filmadoras digitais e apreciadores de msica. Frequentementeestes usurios tentam impor uma organizao sua coleo particular de dados, e estaorganizao tende a ser feita usando metadados informaes sobre o contedo dosarquivos obtida de alguma forma, geralmente atravs da associao automtica de in-formaes relativas aos dados (por exemplo, nome de uma msica) ou da anlise dosmesmos (por exemplo, com uma nota de preferncia ou estilo da msica).

    A capacidade de poder extrair informaes contidas nos prprios dados digitais(com isto aumentando a quantidade e qualidade dos metadados) altamente desejvel,e pode ser atingida parcialmente com tcnicas de busca baseadas em contedo (content-based retrieval). Recentemente tcnicas de minerao de dados tem sido usadas [83, 100,118] para derivar novos conhecimentos, conceitos ou estruturas a partir de dados digitais,em especial, multimdia; mostrando-se promissoras para pesquisa e aplicao.

    O objetivo deste captulo familiarizar o leitor com os conceitos gerais de min-erao de dados (e com o processo mais genrico de descoberta de conhecimento embancos de dados) e com tcnicas de minerao de dados aplicveis dados multimdiacomo imagens, sons e documentos na World Wide Web. Vrios exemplos de aplicaessero apresentados com referncias para que o leitor possa obter mais detalhes.

    Este captulo est dividido nas seguintes sees: esta introduo mostra o prob-lema da avalanche de dados. A seo 1.2 apresenta os conceitos de minerao de dadose suas principais tcnicas, de forma genrica, com uma breve descrio de algoritmos

    9http://www.wintercorp.com/VLDB/2005_TopTen_Survey/TopTenWinners.pdf

  • clssicos representativos das principais tcnicas. A seo 1.3 comenta sobre os diver-sos tipos de dados e suas formas de representao, contrastando dados tabulares simples(mais usados em tcnicas de minerao de dados) com dados multimdia, e mostrandocomo pode ser possvel converter de um tipo para o outro. A seo 1.4 comenta sobreexemplos reais de minerao de dados multimdia e de tarefas semelhantes, contendoreferncias para artigos para aprofundamento. A seo 1.5 indica software que pode serusado para minerao de dados em geral e a seo 1.6 apresenta algumas concluses esugestes de pesquisa.

    1.2. Definio e Tcnicas de Minerao de Dados1.2.1. Definio

    Minerao de Dados (em ingls Data Mining) uma das fases do processo chamado De-scoberta de Conhecimento em Bancos de Dados (ou KDD, do ingls Knowledge Discov-ery in Databases). Este processo frequentemente confundido com minerao de dadosem si, mas envolve outros passos e tcnicas igualmente interessantes para o contexto destecurso, portanto merecendo uma descrio mesmo que simplificada.

    O processo de descoberta de conhecimentos em bancos de dados definido comoo processo no-trivial de identificao de padres vlidos, novos, potencialmenteteis e compreensveis a partir de dados (adaptado de [32]). O processo de descobertade conhecimentos em bancos de dados ilustrado na Figura 1.1.

    Dados Brutos

    Conhecimento

    Dados Selecionados

    DadosPr-Processados

    DadosTransformados

    Padres

    Seleo

    Pr-processamento

    Transformao

    Minerao

    Interpretao e Avaliao

    Figura 1.1. Processo de Descoberta de Conhecimento em Bancos de Dados(adaptado de [32])

    Ainda de acordo com [32], e usando a Figura 1.1 como referncia, podemos enu-merar os passos do processo de descoberta de conhecimentos com a lista a seguir. Ospassos da lista correspondentes s etapas do processo mostrado na Figura 1.1 so desta-

  • cados em negrito.

    1. Compreenso do domnio da aplicao, do conhecimento prvio relevante e dosobjetivos do usurio final do processo;

    2. Criao de um conjunto de dados para uso no processo de descoberta atravs daseleo dos