UNIVERSIDADE FEDERAL DE SANTA MARIACENTRO DE TECNOLOGIA

CURSO DE CINCIA DA COMPUTAO

MINERAO DE DADOS DISTRIBUDAE ESCALVEL USANDO APACHE

MAHOUT

TRABALHO DE GRADUAO

Adriano Pereira

Santa Maria, RS, Brasil

2010

MINERAO DE DADOS DISTRIBUDA EESCALVEL USANDO APACHE MAHOUT

por

Adriano Pereira

Trabalho de Graduao apresentado ao Curso de Cincia da Computaoda Universidade Federal de Santa Maria (UFSM, RS), como requisito

parcial para a obteno do grau deBacharel em Cincia da Computao

Orientador: Profa. Andrea Schwertner Charo

Trabalho de Graduao N. 298

Santa Maria, RS, Brasil

2010

Universidade Federal de Santa MariaCentro de Tecnologia

Curso de Cincia da Computao

A Comisso Examinadora, abaixo assinada,aprova o Trabalho de Graduao

MINERAO DE DADOS DISTRIBUDA E ESCALVELUSANDO APACHE MAHOUT

elaborado porAdriano Pereira

como requisito parcial para obteno do grau deBacharel em Cincia da Computao

COMISSO EXAMINADORA:

Profa. Andrea Schwertner Charo(Presidente/Orientador)

Profa. Iara Augustin (UFSM)

Fernando Pires Barbosa (CPD/UFSM)

Santa Maria, 06 de Dezembro de 2010.

A vida uma tragdia quando vista de perto, mas uma comdia quando vistade longe.

CHARLES CHAPLIN

AGRADECIMENTOS

Primeiramente, gostaria de agradecer minha famlia, por estarem sempre comigo.Ao meu pai, Paulo, que sempre foi um exemplo, minha me, Leda, que sempre acreditouem mim, mesmo quando todos duvidavam, e minha irm, Aline, por aguentar o seuirmozinho caula.

Agradeo, tambm, aos amigos, que estavam presentes nos momentos bons e ruins.queles que cresceram comigo, com os quais compartilhei minha infncia; aos colegas,que viraram amigos, do Ensino Mdio; aos, mais que, vizinhos do parque Amaral; aoscolegas de faculdade e, especialmente, dos grupos PET da UFSM, meu sincero muitoobrigado.

No posso esquecer de mencionar os professores que contriburam para minha forma-o. Em especial, agradeo professora Andrea, pela tutoria e orientao ao longo demais de trs anos da graduao.

Enfim, agradeo a todos aqueles que estiveram presentes em minha caminhada e que,de alguma ou outra forma, contriburam para o meu crescimento.

RESUMO

Trabalho de GraduaoCurso de Cincia da Computao

Universidade Federal de Santa Maria

MINERAO DE DADOS DISTRIBUDA E ESCALVEL USANDO APACHEMAHOUT

Autor: Adriano PereiraOrientador: Profa. Andrea Schwertner Charo

Local e data da defesa: Santa Maria, 06 de Dezembro de 2010.

Grandes volumes de dados vm sendo gerados por ferramentas computacionais. Nes-tes dados, podem haver padres implcitos, a partir dos quais pode ser possvel extrairnovos conhecimentos. A minerao de dados preocupa-se com a busca de relaes, es-pecialmente, em grandes quantidades de dados, possibilitando a extrao de novas infor-maes teis. O uso de computao distribuda permite a descentralizao dos dados e aacelerao do processo de minerao. Apache Mahout uma ferramenta para a minera-o de dados distribuda, que faz uso do modelo de programao MapReduce, prometendoescalabilidade ao dividir a carga de trabalho em tarefas independentes entre si. Este traba-lho tem como objetivo verificar o desempenho do Apache Mahout, atravs da seleo dealgoritmos implementados pela ferramenta, preparao de um conjunto de dados, e exe-cuo destes algoritmos, neste conjunto de dados, em diferentes ambientes distribudos,analisando a escalabilidade da ferramenta, quanto ao ganho de desempenho em relaoao acrscimo de nodos ou ncleos ao processamento.

Palavras-chave: Minerao de Dados; Minerao de Dados Distribuda; Apache Mahout.

ABSTRACT

Trabalho de GraduaoUndergraduate Program in Computer Science

Universidade Federal de Santa Maria

SCALABLE AND DISTRIBUTED DATA MINING WITH APACHE MAHOUTAuthor: Adriano Pereira

Advisor: Profa. Andrea Schwertner Charo

Huge data sets have been generated from computing tools. Implicit patterns couldbe present in this data. Data mining worries in look for relationship, specially, in largedata sets, enabling the extration of useful new information. Distributed computing allowsthe data decentralization and speeds up the data mining process. Apache Mahout is adistributed data mining tool, which uses MapReduce program model, promising scala-bility by spliting the workload in independents tasks, among themselves. This work hasas objective to verify Apache Mahouts performance, through a implemented algoritmschoice, data set preparation and mining of these data in differents distributed environ-ments, analyzing the tools scalability, as the performance improvement due to nodes orcores addition to the processing.

Keywords: Data Mining, Distributed Data Mining, Apache Mahout.

LISTA DE FIGURAS

Figura 2.1 Minerao de dados como um passo da descoberta do conhecimento(FAYYAD; PIATETSKY-SHAPIRO; SMYTH, 1996) . . . . . . . . . . . . . . . . 18

Figura 2.2 CRISP-DM: metodologia para minerao de dados (LAROSE, 2005) . 20Figura 2.3 Etapas do pr-processamento dos dados (HAN; KAMBER, 2006) . . . . 21

Figura 3.1 Ambiente distribudo com Apache Hadoop executando Apache Mahout 30Figura 3.2 Exemplo de execuo do K-Means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33Figura 3.3 Exemplo de execuo do FPGrowth (adaptado de Han e Kamber (2006)) 33Figura 3.4 Exemplo de execuo do algoritmo de clculo de similaridade . . . . . . . . 34Figura 3.5 Mapeamento de ndices utilizado para a integrao dos dados . . . . . . . . 36

Figura 4.1 Tempo de execuo do algoritmo K-Means - cluster Gates (em ms) . . . 42Figura 4.2 Acelerao do algoritmo K-Means - cluster Gates . . . . . . . . . . . . . . . . . . . 42Figura 4.3 Tempo de execuo do algoritmo K-Means - cluster Atlntica (em ms) 43Figura 4.4 Acelerao do algoritmo K-Means - cluster Atlntica . . . . . . . . . . . . . . . . 43Figura 4.5 Tempo de execuo do algoritmo FPGrowth - cluster Gates (em ms) . . 44Figura 4.6 Acelerao do algoritmo FPGrowth - cluster Gates . . . . . . . . . . . . . . . . . . 45Figura 4.7 Interface Hadoop - Tasktracker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45Figura 4.8 Tempo de execuo do algoritmo FPGrowth - ambiente heterogneo

(em ms) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46Figura 4.9 Acelerao do algoritmo FPGrowth - ambiente heterogneo . . . . . . . . . . 46Figura 4.10 Tempo de execuo do algoritmo de clculo de similaridade de itens

- cluster Atlntica (em ms) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47Figura 4.11 Acelerao do algoritmo de clculo de similaridade de itens - cluster

Atlntica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48Figura 4.12 Tempo de execuo do algoritmo de clculo de similaridade de itens

- cluster Gates (em ms) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49Figura 4.13 Acelerao do algoritmo de clculo de similaridade de itens - cluster

Gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49Figura 4.14 Tempo de execuo do algoritmo de clculo de similaridade de itens

- ambiente heterogneo (em ms) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50Figura 4.15 Acelerao do algoritmo de clculo de similaridade de itens - ambi-

ente heterogneo - execues distribudas . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

LISTA DE TABELAS

Tabela 4.1 Mquinas - ambiente heterogneo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39Tabela 4.2 Desempenho K-Means - cluster Gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41Tabela 4.3 Desempenho K-Means - cluster Atlntica . . . . . . . . . . . . . . . . . . . . . . . . . . . 42Tabela 4.4 Desempenho FPGrowth - cluster Gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44Tabela 4.5 Desempenho FPGrowth - ambiente heterogneo . . . . . . . . . . . . . . . . . . . . . 46Tabela 4.6 Desempenho clculo de similaridade de itens - cluster Atlntica . . . . . . 47Tabela 4.7 Desempenho clculo de similaridade de itens - cluster Gates . . . . . . . . . 48Tabela 4.8 Desempenho clculo de similaridade de itens - ambiente heterogneo . 49

LISTA DE ABREVIATURAS E SIGLAS

API Application Programming Interface

ARFF Attribute-Relation File Format

CPD Centro de Processamento de Dados

CF Collaborative Filtering

CRISP-DM Cross-Industry Standard Process for Data Mining

CSV Comma-Separated Values

FPG Parallel FPGrowth

FPM Frequent Pattern Mining

HDFS Hadoop Distributed File System

PUCRS Pontifcia Universidade Catlica do Rio Grande do Sul

JAR Java ARchive

JVM Java Virtual Machine (Mquina Virtual Java)

LAD Laboratrio de Alto Desempenho

SSH Secure Shell

UFSM Universidade Federal de Santa Maria

URI Uniform Resource Identifier

SUMRIO

1 INTRODUO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.1 Justificativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.2 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151.3 Estrutura do Texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2 FUNDAMENTAO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.1 Minerao de Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.1.1 Descoberta do Conhecimento em Bases de Dados . . . . . . . . . . . . . . . . . . . . . . . . 172.1.2 Modelo de Processo CRISP-DM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.1.3 Pr-processamento dos dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.1.4 Tarefas de Minerao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.2 Minerao de Dados Distribuda e Escalvel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.2.1 Conceituao. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.2.2 Ferramentas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.3 Ferramentas Utilizadas no Trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.3.1 Apache Hadoop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.3.2 Apache Mahout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3 DESENVOLVIMENTO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.1 Instalao e Configurao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.1.1 Requisitos do Apache Mahout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303.1.2 Requisitos do Apache Hadoop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.1.3 Configurao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.2 Escolha dos Algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.3 Utilizao do Mahout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.4 Preparao dos Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353.4.1 Integrao. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.4.2 Transformao dos Dados. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4 RESULTADOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394.1 Ambientes de Teste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394.2 Casos de Teste e Desempenho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404.2.1 Caso I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414.2.2 Caso II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424.2.3 Caso III . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454.3 Avaliao dos Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5 CONCLUSO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

REFERNCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

APNDICE A CDIGOS FONTE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

1 INTRODUO

A evoluo da tecnologia de informao, a partir da dcada de 60, transformou siste-

mas simples de processamentos de arquivos em sofisticadas bases de dados. O progresso

contnuo das tecnologias de hardware visualizado nas ltimas trs dcadas culminou com

a criao de poderosas ferramentas computacionais. Estas ferramentas impulsionaram a

indstria de informao, gerando uma grande quantidade de bases de dados (HAN; KAM-

BER, 2006). O crescimento da quantidade de dados disponveis ocorre em todas as reas

de esforo humano, como em dados de transaes de mercado, uso de cartes de crdito,

detalhes de chamadas de telefone, estatsticas de governo, bases de dados moleculares e

registros mdicos (HAND; MANNILA; SMYTH, 2001).

Com a disponibilidade de grandes volumes de dados digitais, surge interesse em in-

vestigar teorias e ferramentas para auxiliar a extrao de informao e conhecimento teis

deles (FAYYAD; PIATETSKY-SHAPIRO; SMYTH, 1996). Manter bases de dados ape-

nas para realizao de consultas e processamento de transaes no mais visto de ma-

neira satisfatria. Dessa forma, o prximo alvo trata da investigao avanada dos dados

(HAN; KAMBER, 2006), a partir da qual possvel encontrar relaes e padres implci-

tos, descobrindo informaes teis. Neste ponto est a minerao de dados, um processo

de descoberta de novas relaes, tendncias e padres significativos, atravs da filtragem

de grandes quantidades de dados armazenados em repositrios, utilizando tecnologias de

reconhecimento de padres, matemticas e estatsticas (LAROSE, 2005).

Diferentes razes levam distribuio geogrfica dos dados de interesse, como ques-

tes de segurana e uso de diferentes bases de dados, tornando invivel a aplicao cen-

tralizada dos processos de minerao (KARGUPTA et al., 1999). O uso de tcnicas cen-

tralizadas no adequado aos cenrios atuais, devido complexidade das tarefas de mine-

rao. Nestes caso, tcnicas de sistemas distribudos podem ser utilizadas, possibilitando

14

a distribuio dos dados e acelerando o processo (PREZ et al., 2007).

Inspirado nas primitivas map e reduce das linguagens funcionais, o modelo de progra-

mao MapReduce foi proposto por Dean e Ghemawat (2008), prometendo escalabilidade

ao dividir a carga de trabalho em tarefas que podem ser executadas de forma independente

e paralela. A ferramenta Apache Hadoop possui um framework, distribudo como cdigo

fonte aberto, que implementa este modelo (The Apache Software Foundation, 2007a).

Existem vrias ferramentas para a minerao de dados, especialmente, que executam

os algoritmos de forma distribuda. Neste trabalho ser feita uma anlise do desempenho

do software Apache Mahout, uma soluo recente de ferramenta para emprego de mine-

rao de dados em ambiente distribudo e escalvel. O Apache Mahout uma biblio-

teca de algoritmos de minerao de dados e aprendizagem de mquina, escrita utilizando

o framework MapReduce disponibilizado pelo Apache Hadoop (The Apache Software

Foundation, 2010a).

1.1 Justificativa

Este trabalho justifica-se ao passo da necessidade visualizada para a execuo de al-

goritmos de minerao de dados, utilizando ferramentas computacionais. Tcnicas e fer-

ramentas de minerao de dados so utilizadas em vrios tipos de aplicao, como em

marketing, vendas, aplicaes mdicas e processo de controle industrial (BERRY; LI-

NOFF, 2004).

Com o surgimento de novas tecnologias, dispostas a implantar a minerao de forma

distribuda, visualiza-se a necessidade da realizao de testes, para verificar o comporta-

mento, quanto ao desempenho, dessas novas abordagens. A partir da escolha de algorit-

mos de minerao, preparao de um conjunto de dados e execuo destes algoritmos,

analisando o conjunto de dados preparado, em diferentes ambientes distribudos, pode-se

verificar o desempenho da ferramenta.

A escolha pela ferramenta Apache Mahout deu-se em funo de ser uma soluo

recente, distribuda como cdigo fonte aberto, e que faz uso do modelo de programao

MapReduce para a implementao dos algoritmos, prometendo, com isso, ser escalvel.

15

1.2 Objetivos

Este trabalho tem como objetivo geral investigar a ferramenta Apache Mahout como

soluo para minerao de dados distribuda e escalvel. Para realizar esta anlise, ser

feita a preparao de um conjunto de dados a serem minerados, escolhidos e executados

algoritmos de minerao implementados pela ferramenta, e feita a anlise do desempenho

obtido em diferentes ambientes de execuo.

Especificamente, o trabalho tem como objetivos:

Estudar o funcionamento do Apache Mahout, identificando os algoritmos suporta-dos pela ferramentas e os requisitos para seu funcionamento em ambientes centra-

lizado e distribudo;

Selecionar um conjunto de algoritmos de minerao implementados pela ferra-menta;

Preparar uma fonte de dados, selecionando e convertendo os dados de forma a seremsuportados pela ferramenta; e

Avaliar os resultados de desempenho obtidos, a partir da execuo do aplicativo emdiferentes ambientes distribudos.

1.3 Estrutura do Texto

Este trabalho est organizado da seguinte maneira: o captulo 2 traz uma fundamen-

tao terica acerca dos assuntos abordados no trabalho, tratando da minerao de dados,

minerao de dados distribuda e escalvel, e das ferramentas utilizadas. O captulo 3 fala

sobre o desenvolvimento do trabalho, indicando os requisitos para a instalao e confi-

gurao das ferramentas, sobre os algoritmos selecionados para os testes, as formas de

utilizao da ferramenta e os passos realizados para a preparao dos dados investigados.

O captulo 4 fala sobre os testes realizados e os resultados obtidos. Por fim, o captulo 5

conclui o trabalho, indicando sua contribuio e possveis trabalhos futuros.

2 FUNDAMENTAO

Neste captulo esto descritos conceitos tericos que fundamentam este trabalho, as-

sim como as ferramentas utilizadas para o desenvolvimento dele.

2.1 Minerao de Dados

A existncia de grandes quantidades de dados sem a disponibilidade de ferramentas

para anlise pode ser vista como uma situao de "dados ricos, mas informaes pobres",

uma vez que humanamente impossvel analisar esse imenso volume sem o uso de fer-

ramentas computacionais (HAN; KAMBER, 2006). O interesse em analisar esses dados

cresce com a possibilidade de extrao de informaes potencialmente teis para seus

donos. Essa uma preocupao da minerao de dados (HAND; MANNILA; SMYTH,

2001), cujas ferramentas podem descobrir padres teis, contribuindo em reas como es-

tratgias de negcios, bases de conhecimento, alm de pesquisas cientficas (HAN; KAM-

BER, 2006).

Segundo Hand et al. (2001) , minerao de dados a "anlise de conjuntos de dados,

geralmente grandes, para encontrar relaes no suspeitas e resumir os dados em novas

maneiras, compreensveis e teis para seu dono". Para Han e Kamber (2006) , minerao

de dados refere-se extrao, ou minerao, de conhecimento a partir de grandes volumes

de dados.

Os algoritmos de minerao de dados envolvem tcnicas de estatstica, aprendizagem

de mquina, reconhecimento de padres, inteligncia artificial, recuperao de informa-

o, processamento de sinais e anlise espacial ou temporal de dados. A minerao de

dados considerado um dos mais promissores desenvolvimentos interdisciplinares nas

tecnologias de informao (LAROSE, 2005).

17

2.1.1 Descoberta do Conhecimento em Bases de Dados

A minerao de dados uma das etapas do processo de descoberta de conhecimento

em bases de dados (knowledge discovery in databases). A descoberta do conhecimento

vista como a extrao de conhecimento til a partir de um conjunto de dados, enquanto

que minerao de dados a aplicao de algoritmos especficos para encontrar padres

nesses dados (FAYYAD; PIATETSKY-SHAPIRO; SMYTH, 1996).

Como um processo, descoberta de conhecimento em bases de dados consiste em uma

sequncia iterativa de passos (HAN; KAMBER, 2006). Este processo inicia com a de-

finio de seus objetivos, onde entendido o domnio da aplicao. Na segunda etapa,

constroi-se o conjunto de dados que ser alvo da descoberta. A terceira fase trata de lim-

par e pr-processar os dados, removendo rudos e decidindo estratgias para lidar com

a falta de campos. No quarto passo, o volume de dados reduzido e projetado, dimi-

nuindo o nmero de variveis a serem analisadas e encontrando formas de representao

em funo dos objetivos do processo. Em seguida, na quinta etapa, encontra-se uma ta-

refa de minerao apropriada ao processo de descoberta realizado. A sexta etapa consiste

em escolher algoritmo e mtodo de minerao apropriados para a anlise, com base na

tarefa de minerao. O stimo passo a minerao de dados em si, no qual so busca-

dos padres de interesse, em uma forma de representao particular. A oitava etapa trata

da interpretao dos padres minerados, envolvendo a visualizao da sada de dados da

etapa anterior. Por fim, o nono passo engloba o uso do conhecimento descoberto a partir

de todo o processo (FAYYAD; PIATETSKY-SHAPIRO; SMYTH, 1996). A figura 2.1

ilustra as etapas da descoberta do conhecimento.

2.1.2 Modelo de Processo CRISP-DM

Em meio necessidade de padronizao de processos e modelos de minerao de da-

dos, a construo de um modelo no proprietrio, livre e bem documentado, possibilitaria

a organizaes obterem melhores resultados no processo. Diante deste contexto, surge,

em 1996, o Cross-Industry Standard Process for Data Mining (CRISP-DM) (SHEARER,

2000), um projeto que desenvolveu um modelo de processo de minerao de dados neutro

em termos de indstria e ferramenta (DATA MINING, 2010). CRISP-DM prov um pro-

cesso padro para que a minerao de dados seja realizada apropriadamente na resoluo

de problemas, tanto em pesquisa quanto em aplicaes comerciais (LAROSE, 2005).

18

Figura 2.1: Minerao de dados como um passo da descoberta do conhecimento(FAYYAD; PIATETSKY-SHAPIRO; SMYTH, 1996)

CRISP-DM um modelo de processo e metodologia para a conduo completa de

um projeto de minerao de dados, dividindo-o em seis fases (SHEARER, 2000). A

sequncia de execuo adaptativa, estando as fases subsequentes atreladas s sadas

das fases precedentes. A figura 2.2 ilustra o ciclo de vida de um projeto que segue o

CRISP-DM. Nela, as setas internas indicam as dependncias mais comuns, enquanto que

as externas indicam o ciclo natural (LAROSE, 2005). As seis fases do processo esto

descritas a seguir, segundo Larose (2005) e Shearer (2000).

A primeira fase trata do entendimento do negcio, onde se deve compreender os obje-

tivos e requirimentos do projeto, em uma perspectiva de negcio ou pesquisa. Com isso,

pode-se traduzi-los para uma definio de problema de minerao de dados. Nesta fase,

deve-se preparar uma estratgia preliminar para atingir os objetivos do projeto. O enten-

dimento do negcio compreende a determinao dos objetivos do negcio, avaliao da

situao, determinao dos objetivos da minerao e produo do plano do projeto.

O entendimento dos dados a segunda fase do processo. O analista passa a familiarizar-

se com os dados, a partir de uma coleo inicial. Nesta etapa, pode-se identificar proble-

mas nestes dados, encontrar conhecimento inicial e detectar subconjuntos que possam

ser utilizados para formular hipteses acerca da falta de dados, ou ainda que contenham

padres adicionais. Esta etapa formada por quatro passos principais: compilao dos

dados iniciais, descrio, explorao e verificao da qualidade dos dados.

Na terceira fase do processo, preparao dos dados, esto as atividades de construo

do conjunto final de dados, a partir dos dados brutos iniciais. Nesta fase, so selecionados

casos e variveis apropriados e de interesse analise. Quando necessrio, so realizadas

19

transformaes nestes dados, que tambm devem ser limpos para que estejam apropria-

dos para as ferramentas de modelagem. A fase de preparao compreende os passos de

seleo, limpeza, construo, integrao e formatao dos dados.

Modelagem a quarta fase do processo CRISP-DM. Nesta etapa, so selecionadas

tcnicas de modelagem, e suas configuraes so calibradas para otimizar os resultados.

Em geral, mais de uma tcnica pode ser utilizada para o mesmo problema de minerao

de dados. Algumas delas necessitam que os dados estejam em um formato especfico;

portanto, pode ser necessrio voltar fase de preparao dos dados. Os passos envolvidos

nesta etapa abrangem a seleo da tcnica de modelagem, a gerao de caso de teste,

criao e avaliao de modelos.

Na quinta fase, avaliao, verifica-se se os modelos escolhidos na fase de modelagem

esto de acordo com os objetivos do negcio, avaliando-os em termos de efetividade e

qualidade. Por fim, pode-se decidir sobre a utilizao dos resultados da minerao. A

fase de avaliao conta com os passos de avaliao dos resultados, reviso do processo e

determinao dos passos posteriores.

A ltima fase do processo o desenvolvimento, onde feito uso do modelo gerado

anteriormente. Nesta etapa, o conhecimento descoberto deve ser apresentado de modo

que o interessado na minerao tome conhecimento das formas em que pode utilizar este

conhecimento. Os passos da sexta fase do processo so: planejar o desenvolvimento, o

monitoramento e a manuteno, produzir o relatrio final e revisar o projeto.

2.1.3 Pr-processamento dos dados

necessrio preparar os dados para a minerao, pois, em geral, eles tendem a ser

incompletos, inconsistentes, e contem rudos (HAN; KAMBER, 2006). A minerao de

dados muitas vezes realizada em bases com dados antigos, nas quais h campos expira-

dos, no mais relevantes ou, ainda, faltam valores. Com o pr-processamento, espera-se

minimizar o "lixo" que entra na anlise, para minimizar a sada de "lixo" no resultado

(LAROSE, 2005). Dados incompletos podem ocorrer em virtude da ausncia de atributos

de interesse minerao, ou do desinteresse por estes atributos no momento da modela-

gem ou insero dos dados. Rudos so referentes a atributos contendo valores incorretos,

o que pode acontecer por erro de mquina ou mesmo erros humanos durante a entrada dos

dados. A inconsistncia dos dados pode ocorrer em virtude do uso de diferentes fontes de

20

Figura 2.2: CRISP-DM: metodologia para minerao de dados (LAROSE, 2005)

dados, com nomenclaturas prprias, diferentes daquelas de outras fontes. A seguir, so

descritas as etapas de pr-processamento dos dados, segundo Han e Kamber (2006) . A

figura 2.3 ilustra estas etapas.

Limpeza. Nesta etapa, valores ausentes so preenchidos, rudos so removidos, anoma-

lias e inconsistncias so identificadas ou removidas. Usurios no confiam na

minerao de dados que no estejam "limpos". Alm disso, minerar dados que no

passaram por um processo de limpeza pode provocar resultados inconsistentes.

Integrao. A necessidade da anlise de diversas fontes de dados distintas torna necess-

ria a integrao desses dados. A etapa de integrao dos dados consiste em unificar

diferentes bases de dados, padronizando nomes de atributos e identificando incon-

sistncias.

Transformao. Os algoritmos de minerao necessitam que os dados estejam em for-

matos especficos, como, por exemplo, normalizados. Para tanto, necessrio trans-

21

formar a base de dados investigada, de forma que os dados analisados estejam em

um formato apropriado.

Reduo. A grande quantidade de dados disponveis para anlise pode tornar o processo

de minerao demasiadamente custoso. Neste caso, necessrio reduzir o grande

volume de dados em um conjunto menor, ou selecionar atributos de interesse, do

qual ainda seja possvel obter resultados iguais, ou semelhantes.

Figura 2.3: Etapas do pr-processamento dos dados (HAN; KAMBER, 2006)

Vale salientar que o sucesso da minerao de dados depende da correta preparao

e populao da base que ser investigada. O processo de coleta deve estar consolidado,

22

garantindo a integridade e corretude dos dados (BERNARDI, 2010), para que o processo

de minerao possa ser executado corretamente, possibilitando s etapas posteriores a

extrao de conhecimento til.

2.1.4 Tarefas de Minerao

Com base nos objetivos da anlise dos dados, pode-se categorizar a minerao de

dados em tipos de tarefas (HAND; MANNILA; SMYTH, 2001). A seguir so descritas

os tipos de tarefa comumente classificados:

Agrupamento (clustering), consiste no agrupamento de registros em classes de objetos

similares. Denomina-se cluster um conjunto de registros similares entre si, e dife-

rentes dos registros presentes nos outros clusters. A tarefa de agrupamento busca

segmentar a entrada de dados em subgrupos (clusters) homogneos, maximizando a

similaridade entre os registros de um mesmo cluster, e minimizando a similaridade

entre registros de diferentes clusters (LAROSE, 2005).

Classificao (classification), trata da classificao de registros em relao a uma vari-

vel de categoria. A partir dessa varivel, so delimitadas classes discretas, s quais

estaro relacionados os registros da base de dados analisada. Primeiramente, reali-

zada uma anlise dos dados j classificados, a partir dos quais possvel "aprender"

o mtodo utilizado para classificar os registros (LAROSE, 2005); feito isso, pos-

svel examinar as caractersticas de novos registros, associando-os, devidamente, a

uma das classes pr-definidas (BERRY; LINOFF, 2004).

Estimativa (estimation), consiste em estimar o valor de uma varivel desconhecida em

um novo registro. Pode-se considerar que se trata de uma tarefa de classificao

com valores contnuos, enquanto que a classificao em si trata de valores discretos

(BERRY; LINOFF, 2004). A estimativa realizada a partir da anlise das variveis

conhecidas do registro, em relao aos valores dos registros j presentes na base de

dados (LAROSE, 2005).

Predio (prediction), tarefa semelhante classificao e estimativa, porm com os

valores previstos para o futuro. Pode-se considerar uma adaptao das tcnicas

de estimativa e classificao, onde os casos de treinamento utilizam histricos dos

23

valores dos registros. Os comportamento histrico dos dados utilizado na cons-

truo do modelo, de forma que, quando o modelo utilizado em novos registros,

o resultado uma previso para o futuro (BERRY; LINOFF, 2004).

Associao (association), busca descobrir relaes entre dois ou mais atributos, veri-

ficando quais deles "devem estar juntos" (LAROSE, 2005). Tambm conhecida

como grupos de afinidade, uma abordagem simples para gerar regras a partir de

dados (BERRY; LINOFF, 2004).

Descrio (description), consiste em descrever padres e tendncias em um conjunto de

dados, possibilitando explicaes acerca desses padres e tendncias (LAROSE,

2005). Uma boa descrio pode, ao menos, sugerir por onde comear a busca por

explicaes a respeito dos dados (BERRY; LINOFF, 2004).

Recomendao (recommendation), atravs da anlise dos dados, auxilia usurios reco-

mendando itens, que possam vir a ser de interesse (SARWAR et al., 2001).

2.2 Minerao de Dados Distribuda e Escalvel

2.2.1 Conceituao

Em geral, tcnicas de minerao de dados so centralizadas e monolticas. Esse tipo

de abordagem tem se tornado inadequada para diversos cenrios atuais, em virtude da

complexidade das tarefas de minerao e de problemas relacionados segurana dos da-

dos, os quais podem estar distribudos entre vrias organizaes (PREZ et al., 2007).

Neste contexto, verifica-se a necessidade de processos de minerao de dados distribu-

dos e com alto desempenho, permitindo cenrios com volumes de dados cada vez maiores

(WEGENER et al., 2009).

Segundo Wegener et al. (2009), abordagens utilizando o sistema de arquivos distri-

budo Google File System e o modelo de programao MapReduce provaram-se eficazes

na anlise de grandes quantidades de dados paralelamente, em clusters de computadores.

Sendo assim, pode-se construir sistemas de minerao de dados distribuda, os quais uti-

lizam mltiplos processadores e bases de dados para acelerar a execuo do processo de

minerao, possibilitando, tambm, a distribuio dos dados (PREZ et al., 2007).

Sistemas distribudos podem trabalhar em diferentes escalas. Um sistema dito es-

calvel se continua eficiente frente ao aumento do nmero de recursos e usurios (COU-

24

LOURIS; DOLLIMORE; TIM, 2000). Segundo Jogalekar e Woodside (2000), um sis-

tema considerado escalvel se pode ser implementado efetiva e economicamente sobre

uma srie de diferentes "tamanhos", devidamente definidos.

Escalabilidade est relacionada com o aumento do desempenho de um sistema, em

virtude de seu crescimento. Em aplicaes de minerao de dados, escalabilidade signi-

fica tirar proveito do gerenciamento de bases de dados paralelas e processadores adicio-

nais, possibilitando trabalhar com volumes maiores de dados, construir mais modelos e

aumentar sua corretude apenas adicionando processadores. Idealmente, a escalabilidade

deveria ser linear: dobrando o nmero de processadores, o processo deveria ser executado

na metade do tempo original (SMALL; EDELSTEIN, 1997).

2.2.2 Ferramentas

Exites vrias ferramentas que implementam algoritmos de minerao de dados de

forma distribuda. Em sua maioria, as ferramentas tentam utilizar a ferramenta Weka

em ambientes distribudos, tornando paralelas algumas de suas operaes (WEGENER

et al., 2009). Em seguida, so listadas algumas ferramentas para minerao de dados

distribuda:

Weka-Parallel, trata-se de uma modificao da ferramenta Weka, permitindo a execu-

o da minerao de dados em ambientes distribudos, atravs da implementao

paralela da metodologia de validao cruzada. Tcnicas de classificao, regresso,

agrupamento e seleo utilizam a metodologia de validao cruzada, a qual ine-

rentemente paralelizvel. Assim como a ferramenta Weka, Weka-Parallel escrita

em linguagem de programao Java (CELIS; MUSICANT, 2002).

Grid-enabled Weka, realiza a minerao de dados de forma distribuda, atravs da dis-

tribuio da execuo das tarefas, em um ambiente de grade. A arquitetura do

Grid-enabled Weka baseada em vrios servidores que realizam a execuo da mi-

nerao de tarefas. Estas tarefas so divididas e distribudas, entre os servidores

disponveis, pelos clientes (KHOUSSAINOV; ZUO; KUSHMERICK, 2004).

Weka4WS, um framework que estende a ferramenta Weka, suportando minerao de

dados distribuda em ambientes de grade, de modo a explorar a distribuio dos

dados e aumentar o desempenho da aplicao. Para permitir a minerao distri-

25

buda, cada algoritmo de minerao de dados disponibilizado pela biblioteca Weka

exposto como um Web Service. Embora a minerao seja feita em um ambi-

ente distribudo, as fases de pr-processamento e visualizao dos dados so feitas

localmente (TALIA; TRUNFIO; VERTA, 2005).

MapReduce Weka, trata-se de uma nova arquitetura para sistemas de minerao de gran-

des volumes de dados, apresentada em Wegener et al. (2009). Implementa uma

interface grfica para os usurios, e utiliza o modelo de programao MapReduce,

em clusters ou grades computacionais. A arquitetura baseada em um Data Mining

Client, que realiza requisies, atravs de interface grfica baseada na ferramenta

Weka (Weka Explorer), para o cluster. Para cada requisio, criada uma ins-

tncia de Data Mining Server, responsvel pela execuo da minerao de dados,

executando a parte sequencial do algoritmo e submetendo tarefas paralelizveis ao

framework MapReduce, da ferramenta Apache Hadoop.

GridMiner, um framework que traz como objetivo facilitar a minerao de dados em

um ambiente de grade, provendo uma interface que abstraia a complexidade da

grade, embora permita o controle e a visualizao das tarefas de minerao. Grid-

Miner uma aplicao orientada a servios, implementada sobre a ferramenta Glo-

bus (PETER et al., 2004), uma tecnologia utilizada para a construo de grades

computacionais (GLOBUS, 2010).

2.3 Ferramentas Utilizadas no Trabalho

Nesta seo esto descritas as ferramentas Apache Hadoop e Apache Mahout, utiliza-

das neste trabalho. A ferramenta Apache Mahout realiza a minerao dos dados utilizando

recursos do Apache Hadoop, para que essa minerao possa ser executada em um ambi-

ente distribudo. O Apache Hadoop est descrito primeiramente, pois um requisito para

a execuo distribuda do Apache Mahout.

2.3.1 Apache Hadoop

O projeto Apache Hadoop um conjunto de programas, de cdigo aberto, voltados

computao distribuda e escalvel (The Apache Software Foundation, 2007b). Dentre

os subprojetos do Apache Hadoop, destacam-se o sistema de arquivos distribudo, Ha-

doop Distributed File System (HDFS), e o framework MapReduce, para processamento

26

distribudo de grandes volumes de dados.

2.3.1.1 Hadoop Distributed File System

O Hadoop Distributed File System (HDFS) um sistema de arquivos distribudo,

tendo entre seus objetivos ser tolerante a falhas e permitir o armazenamento de grandes

quantidades de dados.

O modelo de arquitetura do HDFS mestre/escravo. Em um infraestrutura que utilize

HDFS, existe um mestre onde h uma instncia de NameNode; alm de vrias instncias

de DataNode, em geral, uma em cada n escravo.

Os arquivos gerenciados pelo HDFS so divididos em blocos, sendo armazenados

pelos DataNodes. As tarefas de manipulao de arquivos e diretrios, como operaes

de abrir, fechar e renomear, e de mapeamento dos blocos aos DataNodes so realizadas

pelo mestre NameNode. As operaes com blocos, como criao, remoo e replicao,

so realizadas pelos escravos DataNodes, a partir das instrues do mestre NameNode.

Tambm responsabilidade dos DataNodes servir requisies de leitura e escrita, a partir

dos sistemas de arquivos dos clientes (The Apache Software Foundation, 2007c).

responsabilidade do NameNode gerenciar o espao de nomes do sistema de arqui-

vos, mantendo a rvore de diretrios. O NameNode deve conhecer em qual DataNode

est cada bloco, possibilitando a localizao dos arquivos. Os DataNodes armazenam e

recuperam blocos, quando solicitado pelos clientes ou pelo NameNode, alm de comu-

nicar ao NameNode, periodicamente, a lista de blocos que est armazenando (WHITE,

2009).

A implementao do HDFS feita em linguagem de programao Java, possibilitando

que qualquer mquina com suporte Java Virtual Machine possa executar tanto DataNode

quanto NameNode.

2.3.1.2 MapReduce

O modelo de programao MapReduce foi introduzido por Dean e Ghemawat (2008),

sendo voltado ao processamento paralelo de grandes volumes de dados, em arquiteturas

distribudas, abstraindo detalhes de paralelizao, tolerncia a falhas, distribuio dos

dados e balanceamento de carga.

Inspirado nas primitivas map e reduce das linguagens funcionais, o modelo MapRe-

duce base-se em aplicar uma operao, map, em cada registro do volume de dados de

27

entrada. Dessa forma, gera-se um conjunto intermedirio de pares chave/valor, sendo

aplicada uma operao reduce nos pares que compartilham a mesma chave.

Hadoop MapReduce um modelo de programao e framework (The Apache Soft-

ware Foundation, 2007a); uma implementao de cdigo fonte aberto para o modelo de

programao MapReduce. O processamento de uma tarefa divide a entrada em partes

independentes, as quais so processadas paralelamente pela operao de map. A sada

desta operao utilizada como entrada para a operao reduce. Este modelo promete

escalabilidade em virtude de os processamentos de map e reduce serem feitos de maneira

independente, permitindo a distribuio dessas tarefas em diferentes nmeros de nodos,

presentes no sistema.

O framework Hadoop MapReduce composto por um nodo mestre, onde executado

o JobTracker, e um conjunto de nodos escravos, sendo executada, em cada escravo, uma

instncia de TaskTracker (The Apache Software Foundation, 2007a). Para o framework,

um job uma unidade de trabalho solicitada pelo cliente. O job dividido em tasks, do

tipo map e reduce. O JobTracker coordena os jobs em execuo no sistema, escalonando

as tasks para serem executadas nos TaskTrackers. Os TaskTrackers executam essas tasks,

reportando o progresso da execuo ao JobTracker. Em caso de falha, o JobTracker pode

re-escalonar a task, para ser executada em outro TaskTracker (WHITE, 2009).

2.3.2 Apache Mahout

O Apache Mahout uma biblioteca de algoritmos de minerao de dados e aprendi-

zagem de mquina escalvel, escrita em linguagem de programao Java, de cdigo fonte

aberto (The Apache Software Foundation, 2010a). Esta biblioteca foi implementada uti-

lizando o modelo de programao MapReduce; para tanto, faz uso da infraestrutura ofe-

recida pelo Apache Hadoop, descrito na seo 2.3.1.

Atualmente, a ferramenta Apache Mahout suporta principalmente quatro casos de uso:

(i) recomendao, onde se tenta encontrar itens com potencial interesse dos usurios, a

partir de seus comportamentos; (ii) agrupamento, em que itens so agrupados a partir

de tpicos comuns; (iii) classificao, que, com base em uma categorizao existente,

capaz de escolher em qual grupo incluir determinado item; (iv) minerao por frequncia

de grupos de itens, onde se identifica, a partir de um conjunto de grupos de itens, quais

itens aparecem juntos.

28

Em virtude de sua implementao utilizar o framework MapReduce do Apache Ha-

doop e o sistema de arquivos distribudos HDFS, os algoritmos do Apache Mahout podem

ser executados em ambientes distribudos e escalveis, desde que o Apache Hadoop es-

teja configurado. Sem a configurao do Apache Hadoop, a computao ser centralizada

localmente.

O termo escalvel da definio da ferramenta est relacionado com suporte a grandes

conjuntos de dados, em virtude de seus algoritmos de minerao serem implementados

sobre a ferramenta Apache Hadoop, utilizando o paradigma MapReduce; com os casos

de interesse dos usurios, devido ao uso de uma licena comercialmente amigvel; e co-

munidade desenvolvedora e utilizadora da ferramenta (The Apache Software Foundation,

2010a).

A ferramenta Apache Mahout oferece uma Application Programming Interface (API),

para a utilizao de seus algoritmos no desenvolvimento de mineradores de dados. Ela

est implementada em linguagem de programao Java. A ferramenta tambm pode ser

utilizada atravs de um executvel em linha de comando, a partir do qual possvel rea-

lizar a minerao de dados. Ambas formas de utilizao suportam execuo distribuda e

local.

3 DESENVOLVIMENTO

Este captulo ir descrever os passos realizados durante o desenvolvimento deste tra-

balho. Com base nas etapas descritas pela metodologia CRISP-DM, para alcanar os

objetivos deste trabalho, devem ser realizados os passos de preparao dos dados e mo-

delagem. Primeiramente, o captulo descrever os requisitos para instalar e configurar as

ferramentas Apache Mahout e Apache Hadoop. Em seguida, sero expostos os algorit-

mos implementados pelo Mahout que foram selecionados para a execuo dos testes, e

justificada essa escolha. Ento, sero tratadas as formas de utilizao do Mahout, como

uma API Java e como um aplicativo em linha de comando. Por fim, sero abordadas as

tarefas executadas para a preparao dos dados a serem minerados.

3.1 Instalao e Configurao

Os requisitos para o correto funcionamento do Apache Mahout esto relacionados

linguagem de programao na qual foi escrito e infraestrutura fornecida pelo Apache

Hadoop. Os requisitos do Hadoop so decorrentes da linguagem de programao em que

foi escrito, e da forma de comunicao entre os nodos do ambiente.

O ambiente distribudo onde o sistema executado pode ser composto por nodos com

diferentes capacidades de processamento e armazenamento, desde que estejam devida-

mente configurados com o Apache Hadoop. Em geral, adota-se um nodo como mestre,

onde se executam instncias de NameNode, gerenciando o HDFS, e JobTracker, geren-

ciando os jobs de MapReduce. Os demais nodos so escravos, em que so executadas

instncias de DataNode e TaskTracker, para o gerenciamento dos blocos do sistema de ar-

quivo e execuo das tarefas de map e reduce, respectivamente. Neste sistema, executa-se

a ferramenta Apache Mahout, ou um sistema desenvolvido a partir de sua API, o qual re-

aliza a minerao em um conjunto de dados presente no HDFS. Dessa forma, so criados

30

jobs, contendo tasks de map e reduce, escalonadas pelo JobTracker entre os TaskTrackers.

Por fim, a sada da minerao obtida em um conjunto de arquivos, salvos no HDFS. A

figura 3.1 ilustra esse tipo de situao.

Figura 3.1: Ambiente distribudo com Apache Hadoop executando Apache Mahout

A seguir, so descritos os requisitos necessrios para o correto funcionamento das

ferramentas Apache Mahout e Apache Hadoop.

3.1.1 Requisitos do Apache Mahout

Com relao linguagem de programao, Apache Mahout escrito em Java. Por-

tanto, necessrio que o dispositivo computacional onde ele ser executado possua uma

Mquina Virtual Java (JVM). Recomenda-se o uso de verses superiores a 1.6.0 para a

JVM.

Para que o Mahout seja executado de forma distribuda, necessrio que o ambi-

ente computacional esteja configurado, corretamente, com o Apache Hadoop, em verso

0.20.0 ou superior. Dessa forma, os requisitos so os da ferramenta Apache Hadoop, des-

critos na prxima seo. Para executar o Mahout de forma centralizada, no necessrio

que o Hadoop esteja configurado.

Requisitos de hardware, como processador, tamanho em disco e memria, so de-

pendentes da aplicao que utilizar o Mahout, no havendo padro pr-definido (The

31

Apache Software Foundation, 2010a).

3.1.2 Requisitos do Apache Hadoop

O Apache Hadoop tambm escrito em linguagem de programao Java, sendo ne-

cessria a disponibilidade de JVM em cada nodo do ambiente de execuo, em verso

igual, ou superior, a 1.6.0.

Quanto forma de comunicao entre os nodos, Apache Hadoop utiliza o protocolo

de comunicao SSH. Para que no haja a necessidade de autenticao interativa utili-

zando senha, utiliza-se o esquema de chaves pblica para a autenticao. Dessa forma, os

componentes do sistema devem ter suporte ao protocolo e estar devidamente configurados

para que a comunicao seja realizada corretamente.

Apesar de ser suportado tanto pela plataforma GNU/Linux, quanto pela Win32, re-

comenda-se que esta seja utilizada apenas como uma plataforma de desenvolvimento.

Aquela pode ser utilizada como plataforma de desenvolvimento e produo (The Apache

Software Foundation, 2007b).

3.1.3 Configurao

3.1.3.1 Apache Hadoop

A configurao do Apache Hadoop realizada a partir de arquivos, localizados den-

tro do diretrio conf. As alteraes realizadas neste trabalho, para ter-se um ambiente

distribudo, foram nos seguintes arquivos:

core-site.xml definio da URI e porta do NameNode (mestre).

hdfs-site.xml definio do nmero de blocos replicados, definido como o valor unitrio.

mapred-site.xml definio do hostname do JobTracker (mestre).

masters definio do nodo mestre, onde so executados NameNode e JobTracker.

slaves definio dos nodos escravos, onde so executados DataNode e TaskTracker.

Tambm deve-se definir a varivel de ambiente JAVA_HOME, no arquivo hadoop-

env.sh, apontando para o diretrio contendo os arquivos da JVM.

Para que seja possvel realizar a comunicao entre os nodos do sistema, necessrio

que eles estejam aptos a aceitar conexo pelo protocolo SSH, utilizando o esquema de

32

autenticao de chave pblica. Para tanto, deve-se criar chave pblica para o nodo mestre

do sistema, onde esto executando NameNode e JobTracker, e adicion-la na lista de

chaves conhecidas pelos nodos escravos.

3.1.3.2 Apache Mahout

O Apache Mahout pode ser executado de duas maneiras: como um aplicativo em linha

de comando, ou como um API para programas escritos em Java.

A configurao necessria para ser utilizado da primeira maneira consiste na definio

das variveis de ambiente HADOOP_HOME, a qual deve conter o diretrio onde esto os

arquivos do Apache Hadoop, e HADOOP_CONF_DIR, contendo o caminho para diret-

rio conf do Hadoop.

Para ser utilizado como uma API, deve-se construir um arquivo JAR, passado como

parmetro ao arquivo executvel do Hadoop, sem necessidade de outros tipos de configu-

rao, alm das necessrias ao Apache Hadoop.

3.2 Escolha dos Algoritmos

Para a realizao do teste de desempenho da ferramenta, escolheram-se trs algorit-

mos de minerao, sendo eles: K-Means, Parallel FPGrowth (FPG), e o algoritmo de

clculo da similaridade de itens. O algoritmo K-Means um algoritmo de agrupamento.

J o FPG um algoritmo de minerao de padres frequentes (Frequent Pattern Mining,

FPM), enquadrando-se na tarefa de associao, enquanto que o algoritmo de similaridade

de itens faz parte dos algoritmos de filtragem colaborativa baseada em itens (Collabora-

tive Filtering, CF), executando uma tarefa de recomendao.

O algoritmo K-Means foi escolhido por ser um algoritmo simples e efetivo para a

tarefa de agrupamento (LAROSE, 2005). A similaridade no cluster medida atravs do

valor mdio dos objetos presentes nele, o que pode ser visto como o centro de gravidade

ou centride. O funcionamento do K-Means segue os seguintes passos (HAN; KAMBER,

2006), os quais esto, parcialmente, ilustrados pela figura 3.2:

1. Definir um nmero k de classes (clusters), em que os dados sero divididos;

2. Escolher k registros, aleatoriamente, para serem os centrides iniciais dos clusters;

3. Encontrar, para cada registro, o centride mais prximo. Para tanto, utiliza-se al-

33

guma mtrica para encontrar a distncia do registro analisado em relao aos cen-

trides;

4. Aps agrupar todos os registros, encontrar o novo centride para cada cluster;

5. Repetir os passos 3 a 5 at o limite de execuo, ou convergir.

Figura 3.2: Exemplo de execuo do K-Means

Escolheu-se avaliar o desempenho do algoritmo FPGrowth, por ser considerado um

mtodo eficiente e escalvel para minerao de grandes e pequenos padres, sendo um

dos mais populares algoritmos de minerao de frequncia de padres (HAN et al., 2004)

(BORGELT, 2005). O funcionamento do FPGrowth consiste em verificar, primeiramente,

a frequncia de cada valor dos campos de registros de entrada. Ento, so eliminados os

valores cujas frequncias sejam menores que um mnimo definido. Por fim, encontram-se

os k padres mais altos, para cada um dos n registros resultantes, sem os valores elimi-

nados, gerando-se um total de n x k padres (The Apache Software Foundation, 2010b).

Um exemplo de execuo do algoritmo FPGrowth, contendo os valores de entrada e a

respectiva sada, encontra-se na figura 3.3.

Figura 3.3: Exemplo de execuo do FPGrowth (adaptado de Han e Kamber (2006))

Optou-se por analisar um algoritmo de CF por ser uma tcnica difundida entre empre-

sas de comrcio virtual (INGERSOLL, 2009). Analisando-se histrico de preferncias, e

34

tendo como base a similaridade de grupos de usurios, so fornecidas sugestes de itens,

em forma de recomendao (BERRY; LINOFF, 2004). O algoritmo verifica um conjunto

de itens e calcula a similaridade deles, dois a dois, de forma a selecionar os itens mais

similares. Para realizar este clculo, verificam-se os usurios que esto, de alguma forma,

relacionados a ambos os itens, aplicando-se alguma tcnica para determinar a similari-

dade entre eles (SARWAR et al., 2001). A figura 3.4 ilustra um exemplo de entrada e

sada para a aplicao do algoritmo de clculo de similaridade entre itens.

Figura 3.4: Exemplo de execuo do algoritmo de clculo de similaridade

3.3 Utilizao do Mahout

A ferramenta Apache Mahout possui uma API (Application Programming Interface),

contendo um conjunto de classes que implementam os algoritmos de minerao de da-

dos e classes auxiliares. Os algoritmos foram desenvolvidos utilizando recursos da API

fornecida pelo Apache Hadoop, de modo a fazer uso do sistema de arquivos distribudo,

HDFS, e do framework MapReduce.

A listagem 3.1 ilustra um trecho de cdigo de um programa que utiliza a API do

Mahout, para executar o algoritmo de agrupamento K-Means. A classe KMeansDriver

possui um mtodo esttico para a execuo do algoritmo, chamado run. O mtodo recebe

como parmetros os locais onde esto os dados de entrada, os clusters iniciais, o local

onde sero salvos os arquivos de sada do processo, e outros argumentos prprios do

algoritmo. A classe Path originria da API do Apache Hadoop, sendo utilizada para

referenciar a um arquivo, ou diretrio, dentro do HDFS, se executado em um ambiente

configurado com o Hadoop, ou dentro do sistema de arquivos local, se o Hadoop no

35

estiver em execuo.

Listing 3.1: Exemplo de cdigo utilizando a API do MahoutPath vectorsPath = new Path("vectors");Path clustersInitPath = new Path("clustersInit");Path saidaPath = new Path("output");DistanceMeasure measure = new EuclideanDistanceMeasure();double convergenceDelta = 0.01;int maxIterations = 5;boolean runClustering = true;boolean runSequential = false;

KMeansDriver.run(vectorsPath, clustersInitPath, saidaPath, measure,convergenceDelta, maxIterations, runClustering, runSequential);

Tambm possvel utilizar o Apache Mahout atravs de um aplicativo em linha de

comando. Trata-se de um script, que faz uso de um aplicativo desenvolvido com base na

API da ferramenta, disponibilizando algoritmos de minerao e funcionalidades de trans-

formao e visualizao de dados. Para utiliz-lo, informam-se a funcionalidade desejada

e os parmetros necessrios para o seu funcionamento. O aplicativo calcula o tempo gasto

durante o processamento e, se configurada a varivel de ambiente HADOOP_HOME, re-

aliza o processamento de forma distribuda.

3.4 Preparao dos Dados

Os dados analisados neste trabalho so provenientes de um sistema de informaes

acadmicas, do Centro de Processamento de Dados (CPD), da Universidade Federal de

Santa Maria (UFSM). Os dados esto em formato Comma-Separated Values (CSV), sendo

referentes a alunos, bolsistas e projetos da instituio; emprstimos realizados pelos alu-

nos nas bibliotecas e candidatos a ingressar na UFSM. Dados de identificao pessoal

foram embaralhados, para preservar a anonimidade.

Conforme mencionado na seo 2.1.3, necessrio pr-processar os dados antes de

executar a minerao. Em especial, necessrio integrar e transformar os dados, gerando

maiores volumes de informao para os testes, e possibilitando a correta utilizao dos

dados como entrada dos algoritmos de minerao implementados pelo Mahout, testados

neste trabalho.

36

3.4.1 Integrao

Para a integrao dos dados, desenvolveram-se aplicativos, em linguagem de pro-

gramao Java, que geram um novo conjunto, a partir da juno dos dados iniciais.

Realizaram-se junes entre informaes de alunos e bolsistas, alunos e projetos, alu-

nos e emprstimos e alunos e candidatos. A juno foi realizada atravs de atributos de

relao, existentes nas estruturas dos dados.

O algoritmo utilizado para a integrao dos dados consiste em, dados dois conjuntos

de dados, denominados mestre e escravo, primeiramente, mapear os registros do escravo

atravs de ndices, referentes a cada atributo de relao. A figura 3.5 ilustra esse mape-

amento. A partir da, percorre-se os registros do mestre, verificando, nos ndices de atri-

butos de relao, quais registros de escravos podem ser integrados ao registro do mestre

analisado. Com isso, gera-se um novo conjunto de dados, cujos registros so compostos

pelos valores dos registros do mestre, mais os valores dos registros dos escravos relacio-

nados. A listagem A.2 traz o trecho de cdigo que ilustra esse processo de integrao.

O novo conjunto de dados foi gerado em formato CSV. Utilizou-se a biblioteca Java

CSV (DUNWIDDIE, 2006) para a manipulao dos conjuntos iniciais de informaes.

Figura 3.5: Mapeamento de ndices utilizado para a integrao dos dados

3.4.2 Transformao dos Dados

Algoritmos de minerao necessitam que os dados estejam em formato especfico, o

que vlido para a ferramenta Apache Mahout. Algoritmos de agrupamento e classifi-

cao necessitam que os dados estejam em formato de vetor n-dimensional de nmeros

37

reais, onde n indica o nmero de atributos utilizados para descrever os objetos no cluster

(The Apache Software Foundation, 2010a). Dessa forma, para a correta execuo do al-

goritmo K-Means, faz-se necessrio converter os dados de entrada, que esto no formato

CSV, para o formato vetorial aceito pela ferramenta.

Apache Mahout oferece trs formas automticas de transformao dos dados para o

formato vetorial, alm da possibilidade de criao manual dos vetores. Em virtude de o

objetivo deste trabalho no ser o resultado final da minerao, mas o desempenho da fer-

ramenta, optou-se por analisar e selecionar a melhor forma automatizada para criao dos

vetores, ao invs de ger-los manualmente. A seguir so descritas as formas automticas

de criao dos vetores.

A partir de texto, onde os vetores so gerados em funo da frequncia das palavras

presentes em arquivos de texto analisados.

A partir de ndice Lucene. Lucene uma ferramenta para indexao e busca em arqui-

vos texto (The Apache Software Foundation, 2010c). Os vetores podem ser gerados

a partir de um ndice Lucene, de forma semelhante criao a partir de texto. Leva-

se em considerao um atributo de busca do ndice.

A partir de arquivos ARFF. Attribute-Relation File Format (ARFF) o formato de ar-

quivo utilizado pela ferramenta Weka. Trata-se de um arquivo texto que descreve

um conjunto de registros, formados por uma lista de atributos. Um arquivo ARFF

composto por um cabealho, que descreve os atributos, e pelos registros de dados

(ARFF, 2008). Para cada registro, gera-se um vetor. A dimenso dos vetores a

quantidade de atributos presentes.

Optou-se por adotar a forma de gerao dos vetores a partir de arquivos ARFF, por

ser a mais apropriada aos tipos de dados analisados. As outras duas formas de criao de

vetores (a partir de texto e ndice Lucene) so apropriadas para a minerao de arquivos

de texto puro. Foi desenvolvido um aplicativo, em Java, para a transformao dos dados,

do formato CSV, para o formato ARFF.

Para a execuo do algoritmo FPGrowth, os arquivos de entrada devem estar em for-

mato texto, onde cada linha um registro, composto por vrios valores de campos, separa-

dos por algum caractere especial. Dessa forma, desenvolveu-se um aplicativo para trans-

formar os dados do formato CSV para o formato aceito pelo FPGrowth. Basicamente,

38

eliminam-se os cabealhos e substituem-se os delimitadores e separadores de campos, do

arquivo CSV, por algum caractere especial especificado, gerando arquivos compatveis

com o formato esperado pela entrada do algoritmo FPGrowth.

A entrada para os algoritmos de CF consiste em um conjunto de registros, cujas tuplas

so formadas por identificador de usurio, identificador de item e um valor de preferncia

do usurio por aquele item. Estes dados devem compor um arquivo CSV, onde cada linha

um registro, e os valores so separados por vrgula. Para a transformao dos dados

para este formato, desenvolveu-se um aplicativo que recebe, alm dos dados dos registros

de entrada, a indicao de qual campo referente ao identificador de usurio, e qual faz

referncia ao item. Dessa forma, gera-se um novo arquivo CSV, onde o primeiro campo

de cada registro o identificador de usurio, o segundo o identificador do item, e o

terceiro a quantidade de vezes que o usurio est relacionado quele item.

4 RESULTADOS

A fim de alcanar os objetivos deste trabalho, investigou-se o desempenho da ferra-

menta Apache Mahout em diferentes ambientes distribudos, sendo verificado seu fun-

cionamento em mquinas mono e multiprocessadas. Foram analisados trs algoritmos

implementados pela ferramenta, para verificar o comportamento de diferentes classes de

minerao disponibilizadas. Os testes foram realizados a partir da incluso de ns, ou

aumento da capacidade de processamento, atravs da alterao do nmero de tasks de

map/reduce aceitas, ao sistema distribudo, para verificar o comportamento da ferramenta,

em relao escalabilidade.

4.1 Ambientes de Teste

Para a verificao do desempenho da ferramenta Apache Mahout, utilizaram-se trs

ambientes de teste. Um deles composto por mquinas heterogneas, e os outros dois

so clusters de mquinas idnticas. Conforme recomendao verificada pela seo 3.1.2,

utilizaram-se mquinas com plataforma GNU/Linux para realizao dos testes. A seguir,

so descritas as configuraes de cada ambiente.

Ambiente Heterogneo. Este ambiente composto por duas mquinas heterogneas, co-

nectadas por rede ethernet. As mquinas que compem este ambiente so:

Tabela 4.1: Mquinas - ambiente heterogneo

Nome Mquina Processador Ncleos Clock Cache RAMHaroldo Intel Xeon E5335 8 2.00GHz 4MB 4GBVostro Intel Core 2 Duo CPU T7250 2 2.00GHz 2MB 2GB

Neste ambiente, a mquina Vostro foi definida como mestre, onde se executaram

instncias de NameNode e JobTracker. A mquina Haroldo foi definida como es-

40

cravo, executando instncias de DataNode e TaskTracker. Nesta mquina, alterou-

se as configuraes do Apache Hadoop, no arquivo mapred.xml, de forma a suportar

de uma a oito tarefas de map e reduce, possibilitando execues em paralelo, apro-

veitando a quantidade de ncleos disponveis. Mediram-se os tempos de execuo

com cada uma dessas oito configuraes, assim como a execuo local, com a pos-

sibilidade de uso dos oito ncleos.

Cluster Gates. O cluster Gates composto por 6 mquinas idnticas, interligadas. Trata-

se de um cluster do Laboratrio de Alto Desempenho (LAD), da Pontifcia Uni-

versidade Catlica do Rio Grande do Sul (PUCRS). Neste ambiente, alterou-se o

nmero de mquinas testadas, de modo a verificar a escalabilidade em termos de

nmeros de nodos e tempo de execuo. A configurao das mquinas do cluster

Gates a seguinte: processador AMD Opteron Processor 246, 2.00GHz de clock,

1MB de memria cache e 8GB memria RAM.

Cluster Atlntica. O cluster Atlntica composto por 8 mquinas idnticas, interligadas.

Tambm faz parte do LAD, da PUCRS. Assim como no cluster Gates, alterou-se

o nmero de mquinas durante a execuo dos testes no Atlntica. As mquinas

deste cluster possuem processador Intel Xeon E5520, 2.27GHz de clock, 8MB de

memria cache e 16GB de memria RAM.

Para realizar a configurao automtica do Apache Hadoop, em ambos os clusters,

desenvolveu-se um script, em linguagem Shell. Dada uma lista de nodos disponveis para

a realizao da computao, so gerados os arquivos de configurao descritos na seo

3.1.3.1. O primeiro nodo da lista definido como mestre, e os demais, como escravos.

Definiu-se que no haveria replicao de blocos no sistema de arquivos distribudo, ou

seja, h apenas uma cpia de cada bloco de arquivo no HDFS. A listagem A.1 ilustra o

cdigo desse script.

4.2 Casos de Teste e Desempenho

Foram definidos trs casos de teste, nos quais foram executados os algoritmos defini-

dos na seo 3.2, em diferentes ambientes distribudos. Para cada teste de desempenho,

foram realizadas trs execues, sendo informada a mdia entre elas. A seguir, so des-

critos os casos de teste, e os resultados obtidos em cada um deles.

41

4.2.1 Caso I

No primeiro caso de teste, executou-se o algoritmo K-Means, para o agrupamento

dos dados em 5 clusters, num total de 5 iteraes mximas. Os dados testados foram

provenientes da integrao entre as informaes de alunos com emprstimos, totalizando

508MB em arquivo texto, e 157.6MB no arquivo de vetores correspondente. O arquivo

formado por 961635 registros, compostos por 45 campos. Os testes foram realizados nos

clusters Gates e Atlntica, sendo realizadas execues local, sem utilizao do Hadoop, e

distribuda. No Gates, fez-se uso de um a seis nodos, enquanto que, no Atlntica, utilizou-

se de um a oito nodos. Em ambos, fez-se uso de um processador em cada nodo.

A tabela 4.2 traz o resultado da execuo do primeiro caso de teste, para a execuo

no cluster Gates. O resultado tambm est resumido no grfico da figura 4.1. Percebe-

se que houve ganho de desempenho adicionando-se nodos ao ambiente. O ganho mais

significativo deu-se entre as trs primeiras situaes, onde se passou da execuo local

para uma execuo distribuda, com dois e trs nodos. A partir da execuo com quatro

nodos, o ganho no foi to significativo. A curva de acelerao, exposta no grfico da

figura 4.1, ilustra a situao, estando mais acentuada no incio, e tendendo a se estabilizar

a partir dos quatro nodos.

Tabela 4.2: Desempenho K-Means - cluster Gates

Nmero de Nodos Tempo de Execuo (ms) Acelerao1 (Local) 399163 1

2 374279 1,06643 299217 1,33404 276054 1,44595 269658 1,48026 261492 1,5264

O desempenho obtido pela execuo no cluster Atlntica, para o primeiro caso de tes-

tes, est resumida na tabela 4.3 e no grfico da figura 4.3. Percebe-se que houve pequeno

ganho ao adicionar nodos ao ambiente, apesar de a execuo com dois nodos ter desem-

penho semelhante execuo local. At a execuo com quatro nodos, houve pequena

melhora, no observada em relao ao quinto nodo, cujo desempenho foi semelhante

execuo com quatro. Com sete e oito nodos, houve ligeira queda no desempenho,

comparadas execuo com seis, verificando uma tendncia de estabilizao, o que est

ilustrado no grfico da acelerao, na figura 4.4.

42

Local 1 escravo 2 escravos 3 escravos 4 escravos 5 escravos200000

250000

300000

350000

400000

450000

Figura 4.1: Tempo de execuo do algoritmo K-Means - cluster Gates (em ms)

Local 1 escravo 2 escravos 3 escravos 4 escravos 5 escravos1

1,1

1,2

1,3

1,4

1,5

1,6

Figura 4.2: Acelerao do algoritmo K-Means - cluster Gates

Tabela 4.3: Desempenho K-Means - cluster Atlntica

Nmero de Nodos Tempo de Execuo (ms) Acelerao1 (Local) 207694 1

2 208151 0,99783 193547 1,07304 189230 1,09755 190377 1,09096 185176 1,12167 194152 1,06978 186802 1,1118

4.2.2 Caso II

O segundo caso de teste consistiu na execuo do algoritmo FPGrowth, eliminando

valores de campos com frequncia menor que 2, verificando os 50 padres mais altos.

43

Local 1 escravo 2 escravos 3 escravos 4 escravos 5 escravos 6 escravos 7 escravos100000

120000

140000

160000

180000

200000

220000

240000

Figura 4.3: Tempo de execuo do algoritmo K-Means - cluster Atlntica (em ms)

Local 1 escravo 2 escravos 3 escravos 4 escravos 5 escravos 6 escravos 7 escravos

0,6

0,8

1

1,2

1,4

Figura 4.4: Acelerao do algoritmo K-Means - cluster Atlntica

Utilizou-se os dados provenientes da integrao dos dados de alunos com candidatos, to-

talizando 6MB em arquivo, com 9984 registros de 52 campos. Os testes foram realizados

no cluster Gates, sendo realizadas execues local, sem utilizao do Hadoop, e distri-

buda, fazendo uso de dois a seis nodos, utilizando um processador em cada nodo; e no

ambiente heterogneo, distribudo, variando-se a capacidade de execuo de tasks de map

e reduce entre um e oito, alm de uma execuo local, sem utilizao do Apache Hadoop.

A tabela 4.4 e o grfico da figura 4.5 ilustram os resultados obtidos com o segundo

caso de teste, no cluster Gates. Neste caso, verificou-se que o desempenho piorou do

ambiente de execuo local para o distribudo e que o tempo de execuo distribuda,

com diferentes nmeros de nodos, foi semelhante. Isso se deve ao fato de que a execuo,

mesmo no ambiente distribudo, foi realizada de forma sequencial, o que foi verificado

visualizando-se os rastros da execuo, atravs da interface Web disponibilizada pelo

44

Hadoop. Nesta interface, ilustrada pela figura 4.7, pode-se verificar os jobs e as tasks

que esto em execuo, a cada instante. Assim, os atrasos da comunicao e o nus

trazido pela distribuio fsica dos dados, no HDFS, fizeram com que o tempo de execuo

distribuda fosse maior que o tempo de execuo local. No houve grandes diferenas

entre as execues distribudas, o que pode ser visualizado pela curva de acelerao, na

figura 4.6, que praticamente constante.

Tabela 4.4: Desempenho FPGrowth - cluster Gates

Nmero de Nodos Tempo de Execuo (ms) Acelerao1 (Local) 2391794 1

2 2553442 0,93663 2551015 0,93754 2515010 0,95105 2574364 0,92906 2565894 0,9321

Local 1 escravo 2 escravos 3 escravos 4 escravos 5 escravos2000000

2200000

2400000

2600000

2800000

3000000

Figura 4.5: Tempo de execuo do algoritmo FPGrowth - cluster Gates (em ms)

Os resultados obtidos pela execuo do segundo caso de teste, no ambiente hetero-

gneo, esto resumidos pela tabela 4.5 e pelo grfico da figura 4.8. Verificou-se que,

assim como no cluster Gates, no houve diferenas na execuo distribuda do algoritmo,

mesmo variando-se o nmero de tarefas de map e reduce suportadas, visto que a execuo

foi feita de forma sequencial. Com isso, o desempenho local foi superior aos desempe-

nhos das execues distribudas. A curva de acelerao das execues distribudas, na

figura 4.9, ilustra a baixa variao de tempo das execues com diferentes nmeros de

tarefas de map/reduce suportadas.

45

Local 1 escravo 2 escravos 3 escravos 4 escravos 5 escravos0

0,2

0,4

0,6

0,8

1

1,2

1,4

Figura 4.6: Acelerao do algoritmo FPGrowth - cluster Gates

Figura 4.7: Interface Hadoop - Tasktracker

4.2.3 Caso III

O terceiro caso de teste consistiu na aplicao do algoritmo de clculo de similaridade

de itens, utilizando a classe de similaridade "COOCCURRENCE", limitando o nmero

de itens similares entre si a 50. Utilizou-se como entrada os dados referentes aos emprs-

timos de alunos na biblioteca, cujo arquivo original possui 78.5MB, e o arquivo gerado

pela transformao, 6MB. O arquivo formado por 424844 registros, com 3 campos

46

Tabela 4.5: Desempenho FPGrowth - ambiente heterogneo

No de Tasks Suportadas Tempo de Execuo (ms) Acelerao1 2067429 12 2066970 1,00023 2113763 0,97804 2074813 0,99645 2066942 1,00026 2073745 0,99697 2104256 0,98248 2065882 1,0007

8 (Local) 1935254 #

Local 1 tarefa 2 tarefas 3 tarefas 4 tarefas 5 tarefas 6 tarefas 7 tarefas 8 tarefas1000000

1200000

1400000

1600000

1800000

2000000

2200000

2400000

Figura 4.8: Tempo de execuo do algoritmo FPGrowth - ambiente heterogneo (em ms)

1 tarefa 2 tarefas 3 tarefas 4 tarefas 5 tarefas 6 tarefas 7 tarefas 8 tarefas0,4

0,6

0,8

1

1,2

1,4

Figura 4.9: Acelerao do algoritmo FPGrowth - ambiente heterogneo

cada. Realizaram-se testes nos clusters Atlntica e Gates, e no ambiente heterogneo, ha-

vendo execuo local, sem configurao do Hadoop, e execues distribudas. No cluster

Atlntica, utilizou-se de um a oito nodos; no Gates, de um a seis. Em ambas execues,

47

utilizou-se um processador por nodo. No ambiente heterogneo, variou-se a capacidade

de execuo de tasks de map e reduce, de forma a suportar de uma a oito tarefas de cada

tipo (map ou reduce).

Os resultados obtidos com as execues do terceiro caso de teste, no cluster Atlntica,

esto ilustrados na tabela 4.6 e no grfico da figura 4.10. Percebeu-se que a execuo local

deste algoritmo foi mais rpida que a execuo distribuda, o que pode ter acontecido em

virtude da relativa baixa quantidade de dados analisada. Com relao ao processamento

distribudo, pode-se verificar que houve ganho de desempenho at as execues com cinco

nodos. As maiores diferenas de ganho esto entre as execues com dois, trs e quatro

nodos. Entre quatro e cinco, no houve diferena significativa na execuo. Entre cinco e

seis, houve ganho de desempenho, que no foi observado com a execuo nos ambientes

com sete e oito mquinas, comparados com a execuo com seis. O grfico de acelerao,

ilustrado na figura 4.11, mostra essa situao.

Tabela 4.6: Desempenho clculo de similaridade de itens - cluster Atlntica

Nmero de Nodos Tempo de Execuo (ms) Acelerao1 (Local) 564605 1

2 756292 0,74653 699585 0,80704 652646 0,86515 656677 0,85976 628270 0,89867 624400 0,90428 629413 0,8970

Local 1 escravo 2 escravos 3 escravos 4 escravos 5 escravos 6 escravos 7 escravos300000

400000

500000

600000

700000

800000

Figura 4.10: Tempo de execuo do algoritmo de clculo de similaridade de itens - clusterAtlntica (em ms)

48

Local 1 escravo 2 escravos 3 escravos 4 escravos 5 escravos 6 escravos 7 escravos0,5

0,6

0,7

0,8

0,9

1

1,1

1,2

Figura 4.11: Acelerao do algoritmo de clculo de similaridade de itens - cluster Atln-tica

Para o cluster Gates, o desempenho est ilustrado pela tabela 4.7 e pelo grfico da

figura 4.12. Verificou-se que o desempenho da execuo distribuda, entre dois a quatro

nodos, foi pior que a execuo local, havendo melhora do desempenho relativo entre eles.

Com cinco nodos, o desempenho foi equivalente execuo local, e, com seis, teve-se

ligeira melhora. A curva de acelerao, na figura 4.13, mostra essa queda de desempenho

inicial, no ambiente distribudo, e a crescente melhora.

Tabela 4.7: Desempenho clculo de similaridade de itens - cluster Gates

Nmero de Nodos Tempo de Execuo (ms) Acelerao1 (Local) 1032848 1

2 1209943 0,85363 1118437 0,92344 1044602 0,98875 1027764 1,00496 985982 1,0475

A tabela 4.8 e o grfico da figura 4.14 ilustram os resultados obtidos pela execuo

do terceiro caso de teste, no ambiente heterogneo. Verificou-se ganho de desempenho,

relativo ao aumento da capacidade de execuo de tarefas de map/reduce e, consequen-

temente, uso de vrios ncleos para o processamento. Os ganhos foram obtidos at a

definio de cinco tarefas. A partir da execuo com seis, o desempenho manteve-se

constante, o que pode ser visto na curva do grfico de acelerao, que compara as execu-

es distribudas, na figura 4.15. Ainda assim, a execuo distribuda, com capacidade de

execuo de oito tarefas, foi 14% mais lenta que a execuo local. Isso deve ser observado

49

Local 1 escravo 2 escravos 3 escravos 4 escravos 5 escravos600000

800000

1000000

1200000

1400000

Figura 4.12: Tempo de execuo do algoritmo de clculo de similaridade de itens - clusterGates (em ms)

Local 1 escravo 2 escravos 3 escravos 4 escravos 5 escravos

0,6

0,8

1

1,2

1,4

Figura 4.13: Acelerao do algoritmo de clculo de similaridade de itens - cluster Gates

em virtude do custo da comunicao e transferncia dos dados.

Tabela 4.8: Desempenho clculo de similaridade de itens - ambiente heterogneo

No de Tasks Suportadas Tempo de Execuo (ms) Acelerao1 1420529 12 1183433 1,20033 1092270 1,30054 1072038 1,32505 1028090 1,38176 1025862 1,38477 1033030 1,37518 1037381 1,3693

8 (Local) 909959 #

50

Local 1 tarefa 2 tarefas 3 tarefas 4 tarefas 5 tarefas 6 tarefas 7 tarefas 8 tarefas

400000

600000

800000

1000000

1200000

1400000

Figura 4.14: Tempo de execuo do algoritmo de clculo de similaridade de itens - ambi-ente heterogneo (em ms)

1 tarefa 2 tarefas 3 tarefas 4 tarefas 5 tarefas 6 tarefas 7 tarefas 8 tarefas

0,8

1

1,2

1,4

1,6

Figura 4.15: Acelerao do algoritmo de clculo de similaridade de itens - ambienteheterogneo - execues distribudas

4.3 Avaliao dos Resultados

A partir dos desempenhos obtidos pela execuo dos trs casos de teste delimitados,

verificou-se que a ferramenta Apache Mahout possui comportamentos diferenciados para

os algoritmos analisados, K-Means, FPGrowth e clculo de similaridade de itens, bem

como em relao ao poder de processamento do ambiente utilizado. A execuo do al-

goritmo K-Means, no primeiro caso de teste, mostrou um ganho mais significativo no

acrscimo de mquinas ao ambiente de processamento do cluster Gates, se comparado

com o Atlntica, sendo que os nodos do primeiro possuem um poder de processamento

menor que os do segundo. Neste caso, a execuo local foi pior que as execues distri-

budas, nos dois clusters, apesar de as diferenas no desempenho terem sido menores no

51

Atlntica que no Gates.

Pode-se verificar que o algoritmo FPGrowth, implementado pela ferramenta, no faz

uso da paralelidade e escalabilidade oferecidas pelo modelo de programao MapReduce.

O segundo caso de teste ilustra essa situao, pois no houve diferenas entre as execues

distribudas, com diferentes nmeros de nodos, ou entre as execues com diferentes

capacidades de processamento, em uma mquina com mais de um ncleo. Verificou-se

que o algoritmo FPGrowth tem uma execuo sequencial, uma vez que apenas uma task

de map, ou reduce, lanada pelo JobTracker por vez, sendo escalonada em qualquer um

dos nodos disponveis.

Tambm visualizou-se situaes onde a execuo local foi mais vantajosa que a dis-

tribuda, em termos de desempenho. O terceiro caso de teste, com a execuo do algo-

ritmo de clculo de similaridade de itens, mostra isso. Essa situao pode ter ocorrido

em virtude da pequena quantidade de dados analisada, onde o custo para a distribuio

das tarefas e manuteno dos dados, no HDFS, acabam sendo superiores ao benefcio da

execuo distribuda.

Com exceo do segundo caso de teste, onde a execuo foi realizada de forma se-

quencial, pode-se verificar que houve um comportamento de escalabilidade da ferramenta,

ao adicionar-se nodos ou aumentar a capacidade de processamento em ambientes multi-

processados. Essa escalabilidade tem um limite, o que foi verificado pelos resultados ob-

tidos nos casos de teste I e III. Alm disso, pode-se verificar que possvel tirar proveito

do uso de mquinas com mais de um ncleo, alterando-se as configuraes do Apache

Hadoop. O terceiro caso de teste, quando executado no ambiente heterogneo, mostra

esta situao.

Apesar de a anlise dos resultados da minerao fugir do escopo deste trabalho, pode-

se observar que, para algoritmos de agrupamento e, consequentemente, classificao, o

formato de vetores utilizado dificulta a visualizao dos resultados obtidos. As informa-

es analisadas que, muitas vezes, so oriundas de bases de dados, devem ser transfor-

madas para um formato de vetores, cujos campos so formados por nmeros de ponto

flutuante. Embora haja formas automticas de converso dos arquivos para este formato

vetorial, no se encontraram formas de converso dos vetores resultantes e, consequente-

mente, do resultado obtido, para o formato inicial.

5 CONCLUSO

Este trabalho apresentou uma anlise de desempenho do Apache Mahout, para a mine-

rao de dados distribuda e escalvel, utilizando o modelo de programao MapReduce.

Conjuntos de dados, provenientes do sistema de informaes acadmicas de alunos da

UFSM, foram preparados para serem investigados pela ferramenta. Selecionaram-se trs

algoritmos, K-Means, FPGrowth e cculo de similaridade de itens, para a realizao dos

testes. Realizaram-se testes em trs ambientes distintos, um deles composto por duas

mquinas heterogneas, e os outros sendo clusters com diferentes capacidadedes de pro-

cessamento. Verificou-se o comportamento de escalabilidade da ferramenta, em relao

ao desempenho obtido com o aumento do nmero de mquinas disponveis, e variao da

capacidade de processamento, em mquinas multiprocessadas.

Verificou-se que os algoritmos K-Means e de clculo de similaridade de itens, im-

plementados pela ferramenta, so capazes de tirar proveito de uma execuo distribuda.

Tambm observou-se ser possvel utilizar-se mquinas com vrios ncleos de processa-

mento para aumentar o desempenho da execuo destes algoritmos. Identificou-se um

comportamento de escalabilidade neles, embora em pequena escala, devido pequena

quantidade de mquinas disponveis para o processamento, e ao tamanho dos dados. Para

os dois algoritmos, os ganhos, ao adicionar-se nodos ao processamento, foram mais sig-

nificativos em um ambiente formado por mquinas com menor poder de processamento.

Para o K-Means, as execues distribudas obtiveram melhor desempenho que as centra-

lizadas, o que no foi visualizado, em geral, para o clculo de similaridade de itens, pro-

vavelmente em virtude da menor quantidade de dados analisada. Encontrou-se, tambm,

situao onde a execuo realizada de forma sequencial, com o algoritmo FPGrowth.

Embora faa uso do modelo MapReduce, a execuo sequencial do FPGrowth torna indi-

ferente a quantidade de ns, ou ncleos, disponveis para o processamento, uma vez que

53

ele no aproveita a paralelidade e escalabilidade promovidas por este modelo.

A ferramenta Apache Mahout uma soluo recente para minerao de dados distri-

buda. A falta de testes do comportamento desta ferramenta torna vlido este trabalho, que

tem como contribuio a exposio do comportamento da ferramenta, para a minerao

de um conjunto real de dados, em diferentes ambientes distribudos.

Como trabalhos futuros, sugere-se uma investigao da ferramenta em ambientes onde

haja a disponibilidade de um nmero maior de mquinas, e com uma quantidade maior

de dados. Tambm pode-se investigar o desempenho da ferramenta em outros tipos de

sistemas distribudos, como em um ambiente de computao em nuvem.

54

REFERNCIAS

ARFF. Attribute-Relation File Format (ARFF). Disponvel em: http://www.cs.

waikato.ac.nz/~ml/weka/arff.html. Acesso em: novembro de 2010.

BERNARDI lder. Uma Arquitetura para Suporte Minerao de Dados Paralela

e Distribuda em Ambientes de Computao de Alto Desempenho. 2010. Dissertao

(Mestrado) Pontifcia Universidade Catlica do Rio Grande do Sul.

BERRY, M. J.; LINOFF, G. S. Data Mining Techniques: for marketing, sales, and cus-

tomer relationship management. [S.l.: s.n.], 2004.

BORGELT, C. An implementation of the FP-growth algorithm. In: OSDM 05: PROCE-

EDINGS OF THE 1ST INTERNATIONAL WORKSHOP ON OPEN SOURCE DATA

MINING, 2005, New York, NY, USA. Anais. . . ACM, 2005. p.15.

CELIS, S.; MUSICANT, D. R. Weka-Parallel: machine learning in parallel. [S.l.]: Car-

leton College, CS TR, 2002.

COULOURIS, G.; DOLLIMORE, J.; TIM, K. Distributed Systems - Concepts and

Design. 3.ed. [S.l.: s.n.], 2000.

DATA MINING, C. I. S. P. for. CRISP-DM - Home. Disponvel em: http://www.

crisp-dm.org/ Acesso em: setembro de 2010.

DUNWIDDIE, B. Java CSV Library. Disponvel em: http://sourceforge.

net/projects/javacsv/. Acesso em: novembro de 2010.

FAYYAD, U. M.; PIATETSKY-SHAPIRO, G.; SMYTH, P. From data mining to kno-

wledge discovery: an overview. Advances in knowledge discovery and data mining,

Menlo Park, CA, USA, p.134, 1996.

55

GLOBUS. Welcome to the Globus Toolkit Homepage. Disponvel em: http://www.

globus.org/toolkit/. Acesso em: setembro de 2010.

HAN, J.; KAMBER, M. Data Mining: concepts and techniques. [S.l.: s.n.], 2006.

HAN, J.; PEI, J.; YIN, Y.; MAO, R. Mining Frequent Patterns without Candidate Ge-

neration: a frequent-pattern tree approach. Data Mining and Knowledge Discovery,

Hingham, MA, USA, v.8, n.1, p.5387, January 2004.

HAND, D.; MANNILA, H.; SMYTH, P. Principles of Data Mining. [S.l.: s.n.], 2001.

INGERSOLL, G. Introducing Apache Mahout. Disponvel em: http://www.ibm.

com/developerworks/java/library/j-mahout/. Acesso em: novembro de

2010.

KARGUPTA, H.; BYUNG-HOON; HERSHBERGER, D.; JOHNSON, E. Collective

Data Mining: a new perspective toward distributed data analysis. In: ADVANCES IN

DISTRIBUTED AND PARALLEL KNOWLEDGE DISCOVERY, 1999. Anais. . . AA-

AI/MIT Press, 1999. p.133184.

KHOUSSAINOV, R.; ZUO, X.; KUSHMERICK, N. Grid-enabled Weka: a toolk