Conceitos de Mineração de Dados na tulo 2 Conceitos de

  • View
    212

  • Download
    0

Embed Size (px)

Text of Conceitos de Mineração de Dados na tulo 2 Conceitos de

  • Captulo

    2Conceitos de Minerao de Dados na Web

    Rafael Santos

    Resumo

    J no mais possvel apresentar a Web como uma novidade, comentando sobre suascaractersticas bsicas sua pervasividade e ubiqidade a tornam uma ferramenta co-nhecida de todos, sendo praticamente o maior repositrio de dados publicamente aces-sveis na atualidade. Alguns aspectos e colees de contedo da Web so parcialmenteindexados, e existem mecanismos relativamente efetivos de fazer pesquisas em seus da-dos, mas a maioria destes so passivos ou reativos, dependendo de indexao manualpor palavras-chave ou semi-automtica por contedo (que podem ser enriquecidas porinformaes auxiliares) para oferecer resultados aceitveis.

    Outras tcnicas mais eficientes e inteligentes podem ser usadas para aumentaro potencial de descoberta de conhecimento usando os dados existentes na Web. Algu-mas tcnicas que tem sido investigadas e aplicadas com algum sucesso so tcnicas deminerao de dados.

    Minerao de Dados (Data Mining) o nome dado a um conjunto de tcnicas eprocedimentos que tenta extrair informaes de nvel semntico mais alto a partir de da-dos brutos, em outras palavras, permitindo a anlise de grandes volumes de dados paraextrao de conhecimento. Este conhecimento pode ser na forma de regras descritivasdos dados, modelos que permitem a classificao de dados desconhecidos a partir deanlise de dados j conhecidos, previses, deteco de anomalias, visualizao anotadaou dirigida, etc. Embora muitas destas tcnicas tratem com dados tabulares, possvelextrair informaes tabulares de dados estruturados de forma diferente (como encontra-dos na Web) ou mesmo usar algoritmos especficos para minerar dados da Web comoconjuntos de links entre documentos.

    Este curso apresenta alguns conceitos bsicos de minerao de dados e desco-berta de conhecimento em bases de dados, com nfase em dados estruturados como osda Web: textos (estruturados de diversas formas e em diversos graus, como hiperdo-cumentos, e-mail, arquivos XML e outros tipos), imagens e vdeos, registros de acesso aservidores, metadados (como redes ou grafos que representam ligaes entre documentose objetos como participantes de redes sociais), etc.

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

    Megatendncias, 1982.

    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 terabytes em computadores pessoais a um custo acessvel. Umaquantidade quase incomensurvel de informaes de diversos tipos, origens, formatos efinalidades esto disponveis na Internet, podendo ser acessadas a partir destes dispositi-vos comuns.

    O baixo custo dos dispositivos e do acesso a redes de computadores fez tambmcom que o nmero de usurios destes sistemas aumentasse consideravelmente. Novasferramentas permitem que estes usurios criem contedo digital de forma relativamentesimples e barata, o que s faz aumentar a quantidade de informaes disponveis paraoutros usurios.

    Esta vasta quantidade de informaes, embora facilmente acessvel, nem sem-pre facilmente localizvel. Alguns sites na Internet indexam informaes de deter-minadas categorias de forma controlada e organizada a um certo custo computacionale/ou humano, como, por exemplo, sites especializados como o Internet Movie Database(www.imdb.com) ou SourceForge (sourceforge.net). Outros indexam contedoexterno permitindo a busca usando palavras-chave ou opes mais complexas de busca,como o Google (www.google.com) ou Bing (www.bing.com). Ainda outros funci-onam como portais apresentando informaes externas (em outros sites) de forma cate-gorizada e com contedo personalizado.

    Podemos observar ento que existe um esforo considervel, em vrias frentes eexercido de vrias formas, de tentar organizar, indexar e categorizar informaes j exis-tentes na Internet. Um problema enfrentado por estes esforos que as informaes nemsempre so facilmente organizveis (justamente e paradoxalmente por causa da facili-dade com que podem ser coletadas e distribudas; e por causa de sua prpria estrutura enatureza).

    Outro problema a quantidade e variedade de informaes que devem ser organi-zadas. Alguns exemplos mais especficos do volume de informaes so apresentados aseguir1:

    De acordo com algumas estimativas2, o site YouTube continha 45 terabytes de v-1Algumas destas estatsticas foram obtidas de stios oficiais e algumas de fontes no confirmveis como

    blogs. 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 International Data Corporation, IDC (http://www.idc.com/) fornecem relatrioscom estatsticas e estimativas de uso regional e mundial de armazenamento e uso de banda de rede, a custosbastante elevados.

    2http://www.businessintelligencelowdown.com/2007/02/top_10_largest_.html

  • deos em 2006. O site Flickr tinha 2 bilhes de fotografias digitais3 em 2007 (e umteste rpido mostrou que j podem ser ao menos 3.7 bilhes).

    O banco de dados GenBank contm colees anotadas de sequncias de nucleot-deos e protenas de mais de 100.000 organismos, em um total de 360 gigabytes4.

    O site CiteSeerX (citeseerx.ist.psu.edu) indexa mais de 1.400.000 ar-tigos cientficos e 27.000.000 citaes, e contm muitas informaes adicionais,inclusive referncias cruzadas.

    O site da editora Springer (www.springerlink.com/content) contm maisde 4.400.000 artigos cientficos completos, tambm com muitas informaes adici-onais.

    O site de relacionamentos Facebook (www.facebook.com) contm 250 milhesde usurios que participam de alguns dos 45 milhes de grupos de interesse nosite. O site recebe um bilho de fotografias digitais por ms, e tem um bilho deinformaes como notcias, links, blogs, etc. compartilhados por ms5.

    O j mencionado Sourceforge contm 230.000 projetos de software aberto, cadaum com cdigo fonte, pginas, documentos, listas de e-mails etc. indexados eorganizados.

    De acordo com uma estimativa da Nielsen (www.blogpulse.com), existiam,em Agosto de 2009, mais de 114 milhes de blogs, com quase 90 mil novos blogscriados por dia.

    O site Internet Movie Database contm informaes categorizadas sobre quase1.500.000 de filmes, mais de 3.000.000 de pessoas envolvidas com os filmes, emais de 1.600.000 links para documentos relacionados.

    importante ento ter ferramentas que possibilitem a procura de informao entreesta avalanche de dados. A distino entre dado e informao sutil mas importante:dados podem ser coletados de forma rpida, simples e automtica, e armazenados emgrande volume a baixo custo; informaes so de nvel semntico mais alto. De formasimplista podemos considerar texto como sendo dados, e o contedo deste texto comosendo informaes.

    Informaes podem ser obtidas a partir de dados atravs de tcnicas de interpreta-o, anotao, classificao, agrupamento, sumarizao, etc. destes dados ou de tcnicasque permitam a associao e correlao de outras informaes (possivelmente de outrasfontes). Vrias destas tcnicas fazem parte do conjunto de tcnicas, ferramentas, procedi-mentos e algoritmos conhecidos comumente como Minerao de Dados (Data Mining),que por sua vez faz parte de um processo conhecido como Descoberta de Conhecimentoem Bancos de Dados (KDD, Knowledge Discovery in Databases). Estes conceitos serodetalhados na seo 2.2.

    3http://www.techcrunch.com/2007/11/13/2-billion-photos-on-flickr4ftp://ftp.ncbi.nih.gov/genbank/gbrel.txt5http://www.facebook.com/press/info.php?statistics

  • Tcnicas de minerao de dados tem sido usadas com sucesso para resolver v-rios problemas relacionados com extrao e representao de conhecimento a partir dedocumentos e estruturas da Web, como, por exemplo, extrao de contedo a partir de hi-perdocumentos [8, 31, 39, 73]; identificao de padres nas estruturas dos hiperdocumen-tos [17, 48, 92]; aplicaes em redes sociais e sistemas de recomendao [4, 26, 94, 100];minerao de metadados como registros (logs) [7, 57, 77]; etc. Estas e outras aplicaessero detalhadas na seo 2.6.

    O sucesso de algumas aplicaes e a necessidade de solues melhores, mais r-pidas, mais escalveis e mais precisas (ou simplesmente melhor desenhadas para deter-minada aplicao) para a extrao de conhecimento a partir da Web motiva investimentode empresas, a participao de cientistas e o envolvimento de professores, estudantes eprofissionais que usam a Web para coletar ou fornecer informaes.

    O restante deste captulo organizado da seguinte forma: a seo 2.2 apresentacom detalhes os conceitos de minerao de dados e descoberta de conhecimento em ban-cos de dados. A seo 2.3 apresenta as tcnicas mais usadas e conhecidas de minerao dedados, que podem ser aplicadas a algumas categorias de dados da Web e a seo 2.4 mos-tra como estes dados da Web so representados e como dados podem ser extrados paraminerao. Outra categoria de dados da Web so dados estruturais, que frequentementeso representados como grafos; este tpico ser apresentado na seo 2.5. A seo 2.6apresenta vrios exemplos de aplicao de tcnicas de minerao de dados para aplica-es na Web como modelagem de usurios, anlise de contedo, etc. e outras possveisreas de aplicao. Finalmente a seo 2.7 apresenta algumas ferramentas para testes eprototipao de algoritmos.

    2.2. Conceitos de Minerao de DadosMinerao de Dados (em ingls Data Mining) uma das fases do processo chamado Des-coberta de Conhecimento em Bancos de Dados (ou KDD, do ingls Knowledge Discoveryin Databases). Este processo frequentemente confundido com minerao de dados emsi, mas envolve outros passos e tcnicas igualmente interessantes para o contexto destecurso, portanto merecendo uma desc