HARVARD - Um sistema para extracção automática de conhecimento

HARVARD - Um sistema para Extracção Automática de Conhecimento Ruy Cesar Ramos Filho Tese apresentada para o grau de Doutor em Engenharia Electrotécnica e de Computadores Departamento de Engenharia Informática Faculdade de Engenharia Universidade do Porto Portugal Setembro de 2012 HARVARD - Um sistema para Extracção Automática de Conhecimento Ruy Cesar Ramos Filho Professor Doutor Rui Camacho (Orientador) Submetida para obtenção do grau de Doutor em Engenharia Electrotécnica e de Computadores Setembro de 2012 À Dulclerci, Dominique, Guilherme, e minha mãe, Helena (in memoriam) vii Abstract With the use of information technologies in organisations and the widespread use of Internet services (Web, e-mail, newsgroup, among others) the amount of data available in digital form is huge and increases at a high pace each year. It is nowadays barely impossible to extract information from very large amounts of data manually. Analysis of such amounts of data requires a computational approach with large amounts of computational resources. Knowledge Discovery in Databases (KDD) has a valuable and significant contribution in the process of automatic interpretation and analysis of data. KDD techniques enable us to extract valuable knowledge from large data repositories. Using idle computational resources in a Local Area Network (LAN) we may achieve a distributed computational setting able to handle complex knowledge discovery problems. Although there are a lot of data analysis algorithms becomes necessary to combine these algorithms to distributed computing environments to analyze large amounts of data or build complex models. This thesis proposes a computational framework capable of performing knowledge discovery tasks on large amounts of data using Data Mining (DM) techniques. Machine Learning (ML) algorithms like Inductive Logic Programming (ILP) that have a highly expressive representation power can also be used. Our implementation uses several computational environments that include clusters, Grid Computing and p2p (peer-to-peer). ILP algorithms require large computational resources to process large data sets. Processing extensive Databases and providing quick solution usually requires large and expensive computational resources. Our proposal harvard (HARVesting Architecture of idle machines foR Data mining) enables the processing to be carried out using idle computers distributed in a local area network since High Performance Computers (HPC) are highly expensive and only available in a few organisations. This thesis also proposes a new approach to the parallel execution of ILP algorithms that are adequate to be used within in the harvard framework. ix Résumé Avec l’utilisation de technologies d’information dans les organisations et le l’utilisation étendue de services Internet (le Web, l’e-mail, le newsgroup, parmi d’autres) la quantité de données disponible dans la forme numérique est énorme et les augmentations au haut pas chaque année. Il est de nos jours impossible d’extraire les renseignements de très grandes quantités de données manuellement. Cela être beaucoup fait par la machine et bien qu’il exige de grandes quantités de quantificatifs ressources. La Knowledge Discovery in Databases (KDD) a un de valeur et la contribution significative dans le processus d’interprétation automatique et l’analyse de données. Les techniques de KDD nous permettent d’extraire de valeur connaissance de grands ensembles de données. Nous pouvons utiliser paresseux quantificatif les ressources dans un réseau local d’entreprise nous pouvons accomplir un distribué le cadre quantificatif capable de manipuler la découverte de connaissance complexe problèmes. Cette thèse propose un cadre quantificatif capable de l’exécution des tâches de découverte de connaissance sur la grande utilisation de quantités de données Data Mining (DM) techniques. La Machine Learning (ML) les algorithmes comme La Inductive Logic Programming (ILP) qui ont un pouvoir de représentation extrêmement expressif peuvent aussi être utilisé. Notre implémentation utilise plusieurs environnements quantificatifs cela incluez des groupes (cluster), une Grid Computing et p2p (peer-to-peer). ILP les algorithmes exigent à de grandes ressources quantificatives de traiter de grandes données jeux. Le traitement des Bases de données étendues et en fournissant la solution rapide exigez d’habitude des ressources quantificatives grandes et chères. Notre la proposition harvard (HARVesting Architecture of idle machines foR Data mining) permet au traitement d’être réalisée chantent des ordinateurs paresseux distribué dans un réseau local d’entreprise depuis de High Performance Computers (HPC) sont extrêmement chers et seulement disponibles dans quelques organisations. LAN - Local Area Network ML - Machine Learning MPI - Message Passing Interface MRDM - Multi Relational Data Mining OLAP - On-Line Analytical Processing P2P - peer-to-peer PVM - Parallel Virtual Machine QoS - Quality of Service RMI - Remote Method Invocation XML - Extensible Markup Language Conteúdo Abstract vii Résumé ix Resumo xi Agradecimentos xiii Glossário de Termos xv 1 Introdução 1 1.1 Objetivos ................................. 3 1.2 Contribuições ............................... 4 1.3 Avaliação e resultados . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Organizaçãodatese............................ 6 2 Extração de Conhecimento, Aprendizagem Computacional e Computação Distribuída 7 2.1 Extração de Conhecimento - noções básicas . . . . . . . . . . . . . . 10 2.1.1 O Processo de Extração de Conhecimento . . . . . . . . . . . 10 2.1.1.1 Fluxo do processo do KDD . . . . . . . . . . . . . . 13 2.1.2 Diferentes aspectos do processo de KDD . . . . . . . . . . . . 16 2.1.2.1 Tarefas de Data Mining ................ 16 xvii 2.1.3 Medidas de Interesse . . . . . . . . . . . . . . . . . . . . . . . 19 2.1.4 Algoritmos para as tarefas de DM . . . . . . . . . . . . . . . . 21 2.1.4.1 Regras de Associação . . . . . . . . . . . . . . . . . . 21 2.1.4.2 Classificação . . . . . . . . . . . . . . . . . . . . . . 22 2.1.5 Extração de Conhecimento - implementação . . . . . . . . . . 23 2.1.6 Questões de Pré-processamento em Extração de Conhecimento 25 2.2 Extração de Conhecimento - métodos e ferramentas . . . . . . . . . . 29 2.2.1 A metodologia CRISP-DM . . . . . . . . . . . . . . . . . . . . 30 2.2.2 Implementações em SGBD . . . . . . . . . . . . . . . . . . . . 32 2.3 Aprendizagem Computacional . . . . . . . . . . . . . . . . . . . . . . 35 2.3.1 Indução de Árvores de Decisão . . . . . . . . . . . . . . . . . . 36 2.3.2 Indução de Programas em Lógica . . . . . . . . . . . . . . . . 37 2.3.2.1 Implementações ILP em computação distribuída . . . 43 2.3.3 Data Mining Multi-relacional . . . . . . . . . . . . . . . . . . 44 2.3.4 Ferramentas para Aprendizagem Computacional . . . . . . . . 48 2.3.4.1 Linguagem e ambiente R . . . . . . . . . . . . . . . . 48 2.3.4.2 Weka .......................... 49 2.3.4.3 Yale........................... 50 2.3.4.4 Rapidminer . . . . . . . . . . . . . . . . . . . . . . . 51 2.3.4.5 SPSS Clementine . . . . . . . . . . . . . . . . . . . . 51 2.3.4.6 SAS Enterprise Miner . . . . . . . . . . . . . . . . . 52 2.3.4.7 KNIME......................... 53 2.4 Computação Distribuída . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.4.1 Computação em Cluster ..................... 53 2.4.2 GridComputing ......................... 56 2.4.3 Iniciativas Grid Computing ................... 61 2.4.3.1 Globus ......................... 62 2.4.3.2 Condor ......................... 62 Conteúdo xix 2.4.3.3 BOINC ......................... 63 2.4.3.4 Hadoop ......................... 64 2.4.3.5 MapReduce....................... 65 2.4.4 Computação Peer-to-peer(p2p) . . . . . . . . . . . . . . . . . 66 2.4.5 Computação em Nuvem (Cloud Computing) .......... 67 2.5 Conclusões................................. 69 3 Sistema HARVARD 71 3.1 Arquitetura do Sistema harvard .................... 73 3.2 Processo de Análise de Dados no harvard ............... 75 3.3 A especificação das tarefas . . . . . . . . . . . . . . . . . . . . . . . . 77 3.4 O uso da linguagem XML no harvard ................. 79 3.5 A estrutura do harvard ......................... 80 3.5.1 OServidor............................. 80 3.5.2 Cliente............................... 82 3.5.3 Funcionamento guiado por eventos . . . . . . . . . . . . . . . 84 3.6 Extensões ao Sistema harvard ..................... 85 3.6.1 MacroTarefas........................... 85 3.6.2 harvard e o ambiente Grid Computing ............ 88 3.7 Conclusões................................. 97 4 Contribuição para Data Mining Relacional 99 4.1 Uma nova abordagem para uma execução paralela de ILP . . . . . . . 100 4.2 Implementação rápida . . . . . . . . . . . . . . . . . . . . . . . . . . 105 4.3 Avaliando o algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . 107 4.4 Melhoramentos para a implementação . . . . . . . . . . . . . . . . . . 110 4.5 Comparando com outras implementações . . . . . . . . . . . . . . . . 111 4.6 Conclusões.................................111 5 Utilização e Avaliação do Sistema harvard 113 5.1 Utilização em pré-processamento de Data Mining ...........114 5.2 Utilização em tarefas de análise de dados . . . . . . . . . . . . . . . . 119 5.3 Executando um sistema de ILP no harvard ..............121 5.4 Conclusões.................................123 6 Conclusões 125 6.1 Contribuições ...............................126 6.2 Trabalhofuturo..............................127 Bibliografia 131 Apêndices 139 A Lista de Traduções 139 B Resultados do ILP 141 C Exemplos e Scripts 151 Índice 174 Lista de Figuras 2.1 Processo de Extração de Conhecimento [FPSSU96] . . . . . . . . . . 11 2.2 Knowledge Discovery in Databases e as disciplinas envolvidas [FPSSU96] 12 2.3 Etapas de pré-processamento, Data Mining e pós-processamento . . . 14 2.4 Tarefas de Data Mining: classificação (a), clustering (b), regressão (c) e outlier detection (d) ........................ 18 2.5 Etapas da aplicação do algoritmo Apriori conforme [AS94] . . . . . . 23 2.6 Etapas de um algoritmo de Classificação, adaptado de [Han01] . . . . 24 2.7 Data Mining Distribuído. Divisão dos dados inicialmente centralizados. .................................... 26 2.8 Pré-processamento dos dados . . . . . . . . . . . . . . . . . . . . . . 28 2.9 Metodologia CRISP-DM conforme [CCK+00].............. 31 2.10 Representação de Árvore de Decisão . . . . . . . . . . . . . . . . . . . 37 2.11 Representação de dados relacionais em cláusula de 1ªordem em sintaxeProlog ................................ 41 2.12 Uso de técnica ILP para Extracção de Conhecimento . . . . . . . . . 43 2.13 Esquemas simplificados de troca de mensagens dos diferentes tipos de algoritmos paralelos. (figura original de [FSSC09]) . . . . . . . . . . . 45 2.14 Tabela única com dados redundantes . . . . . . . . . . . . . . . . . . 47 2.15 Tabelas de Clientes, de Compras e de Transações Consolidadas representando um processo de junção de dados. . . . . . . . . . . . . . . . 48 xxi 2.16 Interface Explorer doWEKA ...................... 50 2.17 Visualização de resultados no Rapidminer . . . . . . . . . . . . . . . 52 2.18 Visão de um fluxo de análise de dados no KNIME ........... 54 2.19 Representação de um Cluster ...................... 55 2.20 Arquitetura do Projeto Hadoop [Whi09] ................ 65 2.21 Fluxo exemplo de execução das funções de mapeamento (Map) e redução (Reduce) de um conjunto de dados [Whi09] . . . . . . . . . . . 66 2.22 Diagrama de execução das funções de mapeamento (Map) e redução (Reduce) de um conjunto de dados de forma recursiva [Whi09] . . . . 67 3.1 Arquitetura harvard .......................... 73 3.2 Descrição do fluxo do processo KDD em tarefas sequenciais e paralelas. 76 3.3 Descrição em detalhe de uma tarefa de KDD específica. . . . . . . . . 78 3.4 Exemplo de especificação de uma tarefa em UT usando a linguagem XML. ................................... 81 3.5 Exemplo da codificação em XML de descrição da máquina cujo o hostname é“tau4”. ............................ 82 3.6 Arquitetura harvard-g: (1) processamento local do harvard; (2) execução de tarefas em ambiente Grid Computing remoto . . . . . . . 89 3.7 Módulo Conexão Grid (CGrid) e submódulos . . . . . . . . . . . . . 91 3.8 Representação dos módulos do harvard-g (versão Globus) . . . . . . 93 3.9 Representação dos módulos do harvard-g (versão Condor) . . . . . 95 3.10 Classes disponíveis na Condor-API-Java, descrição original . . . . . . 95 3.11 Exemplo de utilização da Condor-API-Java . . . . . . . . . . . . . . . 96 3.12 Diagrama de compartilhamento de recursos: (1) Base de Dados e o Repositório de Algoritmos DM acessíveis para o harvard e o Condor 97 Lista de Tabelas 2.1 Tarefas de Data Mining e algumas técnicas utilizadas . . . . . . . . . 19 2.2 Classificação das funcionalidades de Extração de Conhecimento disponíveis em alguns SGBD . . . . . . . . . . . . . . . . . . . . . . . . 33 4.1 Caracterização dos conjuntos de dados. Os dois valores nas células da coluna "número de exemplos” indicam o número de exemplos positivos e negativos respectivamente. . . . . . . . . . . . . . . . . . . . . . . . 108 4.2 As 5 ilhas identificadas pelo Algoritmo 1 no conjunto de dados mutagenesis. Orecall number não está mostrado nas declarações de modo pois só os tipos são relevantes. . . . . . . . . . . . . . . . . . . . . . . . . . . 108 4.3 As 4 ilhas identificadas pelo Algoritmo 1 no conjunto de dados carcinogenesis. Orecall number não está mostrado nas declarações de modo pois só os tipos são relevantes. . . . . . . . . . . . . . . . . . . . . . . . . . . 109 4.4 Speedups para diferentes valores de parâmetro language no conjunto de dados mutagenesis. Os valores indicados são a média e desvio padrão de 5 sequências de saturação/redução. . . . . . . . . . . . . . 110 5.1 Caracterização do conjunto de dados NSL-KDD usado para ilustrar a macro tarefa de feature subset selection implementada para conjuntos de dados no formato ARFF. . . . . . . . . . . . . . . . . . . . . . . . 116 xxiii 5.2 Caracterização do conjunto de dados relacional carcinogenesis usado para ilustrar a macro de feature subset selection implementada para conjuntos de dados no formato usado pelo Aleph. . . . . . . . . . . . 117 5.3 Caracterização do conjunto de dados CPDBAS usado para ilustrar a macro tarefa de sintonização de parâmetros implementada para conjuntos de dados no formato ARFF. . . . . . . . . . . . . . . . . . 119 5.4 Caracterização do conjunto de dados lowbwt usado para ilustrar a macro tarefa de validação cruzada implementada para conjuntos de dadosnoformatoARFF..........................120 B.1 Ilhas identificadas pelo Algoritmo 1 no conjunto de dados Triazines. Orecall number (número máximo de soluções alternativas para predicados não determinísticos) não está mostrado nas declarações de modo pois só os tipos são relevantes. modeh() é a declaração de modo da cabeça da cláusula. . . . . . . . . . . . . . . . . . . . . . . . 142 B.2 Parte 1 - Ilhas identificadas pelo Algoritmo 1 no conjunto de dados CPDBAS. O recall number não está mostrado nas declarações de modo pois só os tipos são relevantes. . . . . . . . . . . . . . . . . . . 143 B.3 Parte 2 - Ilhas identificadas pelo Algoritmo 1 no conjunto de dados CPDBAS. O recall number não está mostrado nas declarações de modo pois só os tipos são relevantes. . . . . . . . . . . . . . . . . . . 144 B.4 Parte 3 - Ilhas identificadas pelo Algoritmo 1 no conjunto de dados CPDBAS. O recall number não está mostrado nas declarações de modo pois só os tipos são relevantes. . . . . . . . . . . . . . . . . . . 145 B.5 Parte 4 - Ilhas identificadas pelo Algoritmo 1 no conjunto de dados CPDBAS. O recall number não está mostrado nas declarações de modo pois só os tipos são relevantes. . . . . . . . . . . . . . . . . . . 146 Lista de Tabelas xxv B.6 Parte 1 - Ilhas identificadas pelo Algoritmo 1 no conjunto de dados DBPCAN. O recall number não está mostrado nas declarações de modo pois só os tipos são relevantes. . . . . . . . . . . . . . . . . . . 147 B.7 Parte 2 - Ilhas identificadas pelo Algoritmo 1 no conjunto de dados DBPCAN. O recall number não está mostrado nas declarações de modo pois só os tipos são relevantes. . . . . . . . . . . . . . . . . . . 148 B.8 Parte 3 - Ilhas identificadas pelo Algoritmo 1 no conjunto de dados DBPCAN. O recall number não está mostrado nas declarações de modo pois só os tipos são relevantes. . . . . . . . . . . . . . . . . . . 149 B.9 Parte 4 - Ilhas identificadas pelo Algoritmo 1 no conjunto de dados DBPCAN. O recall number não está mostrado nas declarações de modo pois só os tipos são relevantes. . . . . . . . . . . . . . . . . . . 150 1.3 Avaliação e resultados A fim de avaliar o trabalho desenvolvido tanto na construção da plataforma de Extração de Conhecimento como no algoritmo de ILP paralelo desenvolvemos uma série de Casos de Estudo que são detalhados no Capítulo 5. Neste Casos de Estudo foram testadas diversas tarefas de KDD em que a computação distribuída e em particular o sistema harvard pode ser extremamente útil. Foram utilizadas tarefas de pré-processamento, avaliação de modelos, sintonização de parâmetros, escolha automática do melhor conjunto de atributos, entre outros. Foram usadas tarefas de Classificação e Regressão num conjunto diversificado de dados. As avaliações centraram-se não só em algoritmos proposicionais de Aprendizagem Computacional mas também na utilização de sistemas de ILP. Foi ainda utilizada a ligação a um ambiente de Cluster, como o Condor, para a execução das tarefas. Os resultados são bastante promissores. 1.4 Organização da tese Para além deste capítulo introdutório a tese tem a seguinte estrutura. O Capítulo 2 efetua uma revisão dos conceitos básicos e abordagens existentes em termos como Extração de Conhecimento,Aprendizagem Computacional e Computação Distribuída relevantes para a compreensão do trabalho de tese.No Capítulo 3 é apresentado o projeto de ambiente computacional para Extração de Conhecimento denominado harvard. O Capítulo 4, descreve a nova abordagem de ILP Paralelo adequado à execução em ambiente harvard. Exemplos de utilização e a avaliação das propostas apresentadas nesta dissertação são apresentados no Capítulo 5. O último capítulo apresenta as conclusões do trabalho, a sua aplicabilidade e importância no âmbito organizacional e na comunidade científica, e sugestões para futuros trabalhos. Capítulo 2 Extração de Conhecimento, Aprendizagem Computacional e Computação Distribuída “entities should not be multiplied beyond necessity.” –Ockham’s razor. Os avanços da tecnologia da informação nos últimos anos tem permitido às empresas armazenar grandes quantidades de dados em suporte digital. A própria Internet tem contribuído para a geração e armazenamento de uma surpreendente quantidade de informação. Diferentes serviços, entre os quais e-mail, newsgroup, ftp, web, blog, permitem reunir informação de diferente natureza, de caráter pessoal ou organizacional. Em alguns desses serviços o registo e o partilhamento da informação nem sempre está organizado ou estruturado em forma de DB, exigindo um esforço adicional para recuperar a informação desejada. Por outro lado a capacidade humana de analisar e mesmo extrair informação útil é bastante limitada sobretudo quando envolve uma grande quantidade ou complexidade de dados ou quando é diversificado o número de fontes e formatos 7 em que se pode encontrar a informação [Han05]. É habitual a informação estar armazenada em ficheiros com diferentes formatos e conteúdos: textos, áudios, vídeos, imagens ou fotografias. Uma simples consulta ou busca de informação num sítio de indexação eletrônica, como Google ou Yahoo, tende a tornar-se uma tarefa bastante complexa. Há sempre a possibilidade do indexador ou provedor de informação apresentar como resultado um conjunto significativo de páginas Web contendo, ou não, a informação desejada. No contexto da análise de quantidades consideráveis de informação em simultâneo uma variedade de fontes e formatos surgiram estudos recentes que contribuíram para a área denominada de Knowledge Discovery in Database (KDD), ou simplesmente Extração de Conhecimento1(EC). Extração de Conhecimento é definido com sendo o processo de descoberta ou reconhecimento de padrões ou regularidades num determinado conjunto de dados. Os padrões identificados devem apresentar algum significado, permitir insights contribuindo para a tomada de decisões a partir deles, e assim obtendo-se alguma vantagem – quer sejam novas informações ou novos conhecimentos [FPSSU96, FU96, Han01]. A principal motivação para o uso de Extração de Conhecimento é a análise de grandes quantidades de dados para o suporte à tomada de decisão. Há inúmeros campos de aplicação e diversos domínios do conhecimento humano em que as técnicas de Extração de Conhecimento têm sido usadas com bastante sucesso. Essas áreas de conhecimento incluem a síntese de novos medicamentos, a identificação de fraudes ou definição de novas estratégias de vendas de produtos [FPSSU96,Han01]. Alguns outros exemplos que merecem destaque: 1Sempre que não haja ambiguidade usaremos o temo Extração de Conhecimento para designar todo o processo de KDD bem como o seu passo intermédio de Data Mining. Capítulo 2. Extração de Conhecimento, Aprendizagem Computacional e Computação Distribuída 9 •gestão e análise de mercados: algumas estratégias de marketing amplamente usadas como segmentação de mercado, venda cruzada (cross selling), market basket só podem ser implementadas na prática com o uso efetivo de um processo de Extração de Conhecimento sobre BD de clientes, transações, produtos e fornecedores. A análise de uma BD de clientes e suas transações permite identificar os produtos adequados a um determinado grupo e também definir critérios que permitirão atrair novos clientes; •detecção de fraudes financeiras e administrativas: a partir da análise de registos históricos sobre operações financeiras pode-se, por exemplo, construir um modelo de comportamento fraudulento e assim identificar futuros casos similares de fraude. Pode-se identificar padrões incomuns de consumo no uso de um cartão de crédito; detectar grupos de pessoas que possam estar simulando acidentes para receber o prémio do seguro; transações bancárias que demonstrem irregularidades, pacientes ou mesmo médicos que possam estar defraudando o seguro de saúde através de tratamentos incompatíveis com a idade, sexo ou estado do paciente. •text mining: a quantidade de dados e informações disponíveis na Web em diferentes serviços como newsgroup,e-mail e ficheiros eletrônicos e em diferentes formatos como: HTML (Hypertext Markup Language), PDF (Portable Document File), ppt (Microsoft Powerpoint), Postscript, entre outros,torna o processo de classificar e recuperar informação bastante complexo e oneroso. Um exemplo interessante é na área biomédica, onde o volume de publicações tem aumentado consideravelmente, principalmente na geração pós-genoma, chegando a registar a marca de 400.000 artigos por ano, somente na PubMed2 [Cock03]. A simples pesquisa ou análise de resumos, nesta grande BD, pode já não ser tão eficaz para novos avanços na própria área sem uma classificação 2PubMed Central é repositório de artigos da área de ciéncias biomédicas e da vida e é mantido pelo NIH (U.S. National Institutes of Health) mais adequada dos artigos publicados. É requerido identificar relações, buscar novos padrões e conexões entre os vários artigos visando um melhor aproveitamento e seleção da informação, e evitar assim a redundância de esforços. Estes são apenas alguns exemplos e formas de como a Extração de Conhecimento pode auxiliar na tomada de decisão. Outra situação interessante que deverá lançar grandes desafios à comunidade científica é a entrada em operação do LHC (Large Hadron Collider) do CERN3que deverá gerar 10 petabytes de dados por ano. Os dados produzidos a partir de experiências com o acelerador de partículas deverá requerer não só técnicas de Data Mining para “descobrir” novas informações mas também poder computacional relevante. O próprio CERN tem um projeto paralelo de montar um sistema baseado em Grid Computing para suportar todo o processamento dos dados gerados. O próprio armazenamento de todos esses dados é complexo e oneroso. 2.1 Extração de Conhecimento - noções básicas 2.1.1 O Processo de Extração de Conhecimento Knowledge Discovey in Database (KDD) ou Extração de Conhecimento4,é um processo não trivial de identificar, validar e reconhecer padrões de dados que possam prover informação válida gerando conhecimento útil e inexplorado sobre uma determinada Base de Dados. Os dados referem-se a representação de factos e os padrões são definidos por uma expressão que descreve um subconjunto desses mesmos dados [FPSSU96]. 3URL do CERN com detalhe sobre o projeto: http://lcg.web.cern.ch/LCG/ 4Embora a tradução direta de KDD seja Descoberta de Conhecimentos em Base de Dados usaremos a definição Extração de Conhecimento. 2.1. Extração de Conhecimento - noções básicas 11 Figura 2.1: Processo de Extração de Conhecimento [FPSSU96] Segundo Fayyad [FPSSU96], Data Mining especificamente é o núcleo principal do processo mais amplo denominado de KDD.OData Mining utiliza técnicas de várias outras disciplinas conforme apresentado na Figura 2.2. As disciplinas mais influentes incluem a Estatística,as Bases de Dados,Machine Learning, as Ciências da Informação, a Computação de Elevado Desempenho, entre outras. Dependendo do objetivo estabelecido outras técnicas como a Análise Espacial de Dados, Recuperação da Informação, Reconhecimento de Padrões, Análise de Imagens e Processamento de Sinais podem ser usadas para extrair e representar a informação [Han01]. Figura 2.2: Knowledge Discovery in Databases e as disciplinas envolvidas [FPSSU96] Ainda de acordo com Fayyad [FPSSU96] o processo de KDD, conforme ilustrado na Figura 2.1, é composto pelas fases: a) preparação de dados; b) seleção de dados; 2.1. Extração de Conhecimento - noções básicas 13 c) pré-processamento de dados; d) transformação de dados; e) Data Mining; f) interpretação e avaliação do conhecimento. De uma forma mais elaborada e metódica, Han e Kamber [Han01] aglutinam algumas fases e propõem a seguinte organização: •pré-processamento: reúne atividades que visam gerar uma representação conveniente para aplicação de algoritmos de Data Mining. Abrange etapas como seleção, limpeza, integração e transformação de dados; •Data Mining: aplicação dos algoritmos de Aprendizagem Computacional ou Estatística para identificação de novos padrões de dados; •pós-processamento: seleção e ordenação dos padrões de dados descobertos, mapeamentos de representação do conhecimento e geração de relatórios. Na Figura 2.3 é mostrada a correspondência entre as diferentes abordagens de Fayyad [FPSSU96] e Han e Kamber [Han01], mas que consideram as mesmas etapas para o processo como um todo. É comum usar indistintamente KDD como sendo o passo de Data Mining. Nesta tese quando estivermos discutindo Data Mining estaremos referindo ao núcleo principal do processo KDD que trata da aplicação de algoritmos de Aprendizagem Computacional visando extrair novos conhecimentos [FPSSU96]. 2.1.1.1 Fluxo do processo do KDD O fluxo do processo de extração de conhecimento inclui as seguintes etapas [Han01]: Figura 2.3: Etapas de pré-processamento, Data Mining e pós-processamento 1. definir claramente o domínio de conhecimento a ser tratado e os objetivos da aplicação de KDD; 2. definir um subconjunto de dados alvo na etapa de seleção de dados; 3. aplicar técnicas de limpeza e pré-processamento removendo inconsistências ou incoerências nos dados armazenados; 4. aplicar processos de data reduction edata transformation procurando identificar características úteis que possam uniformizar os dados de modo a facilitar a aplicação de alguns algoritmos; 5. escolher entre as tarefas ou funcionalidades de Data Mining: sumarização, classificação, regressão, associação ou clustering; 6. escolher o(s) algoritmo(s) de Data Mining apropriado(s) conforme a tarefa; 2.1. Extração de Conhecimento - noções básicas 15 7. executar o Data Mining para extrair os padrões; 8. avaliar os padrões e representar o conhecimento, utilizando técnicas de visualização, transformação ou remoção de redundâncias; 9. interpretar informações ou conhecimento recém descobertos Ainda de acordo com Han e Kamber [Han01] um ambiente de extração de conhecimento deve ter as seguintes características: •capacidade para extrair diferentes tipos de conhecimento em Bases de Dados; •requerer diferentes níveis de abstração para extrair conhecimento; •possibilidade de incorporar conhecimento prévio; •apresentar linguagens específicas para o processo Extração de Conhecimento; •apresentar e visualizar os resultados obtidos; •manipular dados incompletos, com interferências e inconsistências; •avaliar padrões obtidos quanto ao grau de interesse; •obter eficiência e escalabilidade na aplicação dos algoritmos; •adotar métodos e técnicas de forma distribuída e paralela; •gerir tipos de dados complexos; •extrair informação de bases heterogéneas e da própria Web (Web Mining); •analisar os impactos sociais devido as novas informações descobertas; •proteger os dados quanto a segurança, integridade e privacidade; •aplicar as diferentes tarefas de Data Mining (associação, classificação, agrupamento de dados, análise de tendências, sumarização) O método market basket, por exemplo, considera que, dado um conjunto de transações de vendas, se pode encontrar uma regra que mostre o relacionamento entre os itens de venda. Assim, se um determinado produto A for vendido há, com certo grau de certeza, a possibilidade de se encontrar também um produto B na mesma compra, conforme demonstrado formalmente pela regra: A⇒B [Suporte = 2%,Confiança=60%] Compra(Cliente,Produto_A) ⇒Compra (Cliente,Produto_B) O processo de descoberta de Regras de Associação é implementado em dois passos: (a) procurar os itens mais frequentes; (b) gerar regras de associação entre os itens mais frequentes, respeitando os valores das medidas de interesse especificadas pelos utilizadores para o suporte e a confiança7. As regras de associação podem ser usadas em análises de mercado para estabelecer novas estratégias de venda. Diferentes algoritmos podem ser usados no processo de geração deste tipo de regras. Um dos mais utilizados é o algoritmo Apriori [AS94], que estabelece que se um conjunto de itens é frequente, esse mesmo conjunto de itens estará presente em regras de associação. É possível usar este algoritmo para análise particionada de uma extensa base de dados, conforme passos demonstrados na Figura 2.5 [Han01]. 2.1.4.2 Classificação O processo de classificação inclui geralmente 3 etapas: construção do classificador (aprendizagem); avaliação do classificador (verificação) e; uso do classificador (classificação). Estas etapas estão ilustradas na Figura 2.6 [Han01]. 7Definidos na Secção 2.1.3 2.1. Extração de Conhecimento - noções básicas 23 Figura 2.5: Etapas da aplicação do algoritmo Apriori conforme [AS94] Durante a aprendizagem (a), o “algoritmo de classificação” utiliza uma amostra de dados para treino que lhe permite a geração de um classificador (um classificador pode ser visto como um modelo para os dados). Na avaliação (b), o modelo encontrado é aplicado sobre uma amostra de dados diferente da de treino (conjunto de teste) e verificação nas medidas de interesse. Caso a avaliação não seja satisfatória um novo classificador deve ser construído voltando ao ponto (a). Na última etapa classificação (c), a partir de um modelo gerado e avaliado, o classificador é usado para classificar dados reais. 2.1.5 Extração de Conhecimento - implementação Em alguns casos, a aplicação de técnicas de DM deve ser revista para considerar principalmente os dados dispersos na Internet, por exemplo. A extensão e a alta dimensionalidade de algumas BD - muitos atributos versus muito valores, requerem Figura 2.6: Etapas de um algoritmo de Classificação, adaptado de [Han01] cada vez mais demanda por computação paralela e distribuída. A própria rede de comunicação que interliga diversos ambientes computacionais já é desenvolvida o suficiente para fazer parte de uma arquitetura de computação que permita a implementação de estrutura de Data Mining Distribuído [KC00]. Desenvolver técnicas de DM para arquiteturas distribuídas tem sido um grande desafio atual da comunidade científica de Knowledge Discovery in Databases. O desenvolvimento de um novo estágio do KDD denominado de Distributed and Parallel Knowledge Discovery (DPKDD) está ligado principalmente pelo avanço em tecnologias de armazenamento de dados e redes de telecomunicações [KC00] e uso de novas abordagens em computação distribuída como Grid Computing [FK99]. Além disso, dependendo do domínio de conhecimento a ser tratado por técnicas de DM, uma simples amostra pode não ser suficiente para se obter padrões a serem 2.1. Extração de Conhecimento - noções básicas 25 analisados. Já que alguns comportamentos ditos anómalos podem surgir somente após grandes quantidades de dados serem analisados. Mesmo para algoritmos de Aprendizagem Computacional, a necessidade de registrar um padrão somente terá efeito se aumentarmos o tamanho da amostra de dados de aprendizado [KC00]. Isso conduz a necessidade de analisarmos quantidades significativas de dados e por conseguinte uma maior necessidade em termos computacionais. Para que um processo de KDD possa beneficiar-se do modelo de computação distribuída, devemos adotar o modelo apresentado na Figura 2.7, que prevê um modelo de Data Mining Distribuído, onde uma determinada base de dados é fracionada em sub-bases. A cada fração da base principal podemos aplicar algoritmos de Aprendizagem Computacional garantindo a independência de processamento. Deste modo, um ou mais nós de um ambiente de computação distribuída podem executar processos de forma independente, cabendo a um nó central a tarefa de consolidação dos resultados e apresentação ao utilizador. 2.1.6 Questões de Pré-processamento em Extração de Conhecimento Os dados oriundos de aplicações reais apresentam muitas vezes inconsisténcias porque simplesmente foram armazenados de forma incorreta ou incompleta [Han01]. De um modo geral, e conforme [Han01], os dados podem ser : (a) incompletos, sendo mais frequente o não preenchimento de alguns valores para determinados atributos; (b) apresentar interferéncias ou ruído, quando um determinado valor inserido está sob diferentes designações ou simplificações (abreviaturas), podendo gerar outliers; e (c) apresentar discrepâncias quanto a valores que deveriam estar presentes e entretanto foram substituídos por outros. Além disso, alguns atributos que pode- Figura 2.7: Data Mining Distribuído. Divisão dos dados inicialmente centralizados. riam interessar ao processo de extração de conhecimento não foram planeados ou inseridos na Base de Dados para colecta e armazenamento. Não havendo qualidade nos dados, a etapa de Data Mining fica dificultada e dificilmente teremos qualidade no processo de extração de conhecimento e por conseguinte a tomada de decisão será afetada. A adoção de Data Warehouses (DW) pode eliminar alguns dos problemas encontrados quanto à qualidade dos dados, mas nem sempre há a possibilidade de se ter um DW para aplicar algoritmos de Data Mining [FPSSU96,Han01]. Algumas técnicas que podem ser usadas para minimizar problemas com os dados reais, conforme proposto em [Han01] e que fazem parte do processo KDD, estão ilustradas na Figura 2.8. Entre elas podemos destacar: 2.1. Extração de Conhecimento - noções básicas 27 •Limpeza dos Dados (Data Cleaning): consiste na aplicação de técnicas de limpeza tornando os dados uniformes e estruturados, detectando ausências de valores ou retirando eventuais discrepâncias. Atributos que não foram preenchidos ou apresentem dados inconsistentes podem ter valores substituídos por algo representativo que durante a etapa de DM possa ser compreendido e interpretado. Esses novos valores inseridos podem levar em consideração os demais dados, podem representar uma média ou o valor mais provável para aquele atributo. O fundamental é que nenhuma base de dados deve ser analisada por um algoritmo de DM sem antes ter sido devidamente uniformizada. Caso contrário, isso poderá distorcer os resultados esperados, ou ainda comprometer a eficácia e a eficiência do próprio algoritmo. •Integração de dados (Data Integration): alguns conjuntos de dados podem ser originários de diferentes fontes (DBMS8,ficheiro texto, Web, entre outros) sendo necessário consolidar numa única base para a aplicação do processo de DM. Esta etapa permite ainda reconhecer eventuais redundâncias em termos de atributos e eliminar inconsistências com a manipulação de diferentes bases. A simples implementação de Data Warehouse é um exemplo típico de integração de dados de diferentes fontes e de diferentes formatos. •Transformação de dados (Data Transformation): consiste, basicamente, na normalização dos dados por meio de agregação, generalização ou mesmo criação de novos atributos garantindo eficiência e precisão quando da aplicação dos algoritmos. O simples fato de se combinar dados provenientes de diferentes fontes pode requerer a simplificação de escalas, normalização de valores, fusão de atributos, consolidação de valores médios e ainda normalização para a escala decimal. •Redução de dados (Data Reduction): extensas bases de dados com inúme8DataBase Management System ros atributos podem prejudicar ou mesmo inviabilizar a aplicação de alguns algoritmos de Data Mining. Pode-se reduzir significativamente o tamanho de uma base eliminando redundâncias, agregando determinados atributos ou agrupando determinados valores em intervalos. Aplicando técnicas de segmentação pode-se extrair uma amostra representativa de uma extensa base de dados e assim aplicar as técnicas da etapa de Data Mining. A aplicação dessas técnicas pode contribuir significativamente para aumentar a qualidade dos padrões encontrados e reduzir sensivelmente o tempo de processamento [FPSSU96,Han01]. Figura 2.8: Pré-processamento dos dados 2.2. Extração de Conhecimento - métodos e ferramentas 29 2.2 Extração de Conhecimento - métodos e ferramentas O mercado dispõe atualmente de um conjunto de ferramentas direcionadas ao processo de Extração de Conhecimento completo ou ao DM em particular. A seguir apresentamos um resumo das principais características de algumas das opções disponíveis no mercado, com destaque para os algoritmos implementados e algumas das restrições que cada solução apresenta. Alguns dos produtos são licenciados sem qualquer custo, na forma de GNU - General Public License9, conhecida como Licença GNU-GPL, outros porém requerem o pagamento da licença de uso. É possível ter todo um ambiente de extração de conhecimento sem dispendios financeiros. Cabe salientar que algumas tarefas e algoritmos têm nomes diferentes dependendo do fornecedor, dessa forma de modo a não prejudicar o entendimento optamos por apenas mencionar a tarefa de extração de conhecimento que é implementada sem nos preocuparmos com o rigor do detalhe sobre o algoritmo implementado. Antes no entanto de discorrer sobre as diferentes ferramentas e implementações para uso em projetos de KDD, apresentamos a metodologia conhecida como Cross Industry Standard Process for Data Mining10 (CRISP-DM11) [CCK+00] que por vezes é seguida como modelo de referência para alguns projetos e mesmo ferramentas de KDD. 9Licença de Software Livre promovida pela Free Software Foundation (FSF). A fundação FSF, criada em 1985, dedica-se a promover a liberdade dos utilizadores em geral quanto ao uso, cópia, modificação e re-distribuição de programas de computador sem pagamento de licenças comerciais. Mais informações na URL:http://www.gnu.org/licenses/ 10O termo Data Mining usado na metodologia refere-se ao processo completo de KDD 11URL:http://www.crisp-dm.org 2.2.1 A metodologia CRISP-DM A metodologia CRISP-DM descreve um modelo de referência a ser utilizado em projectos de KDD.Foi inicialmente proposta 1996 por um consórcio formando pela DaimlerChrysler, SPSS e a NCR, e teve sua versão 1.0 tornada disponível em 1999. A metodologia CRISP-DM é composta por seis fases cada uma das quais contém um conjunto de tarefas específicas e com resultados esperados bem definidos. As fases que compõem a metodologia são: •Definição dos objetivos de negócio •Compreensão dos dados •Preparação dos dados •Modelização ou Modelagem •Avaliação dos resultados •Implementação ou desenvolvimento Na Figura 2.9 são ilustradas as várias fases e as respectivas interações entre elas. É mostrado na figura o ciclo de vida de um projeto de KDD de acordo com a metodologia. Apresentamos de seguida uma breve descrição das fases: Definição dos objetivos de negócio Consiste na identificação dos objetivos de negócio que o projeto de KDD deverá satisfazer. Estes objetivos de negócio, uma vez identificados, passarão a ser os objetivos do próprio projeto de KDD segundo a metodologia. Como tarefas principais desta fase temos: identificação dos objetivos de negócio, descrição do contexto (requisitos, recursos, riscos e custos/benefícios), identificação dos objetivos de KDD e produzir um plano do projeto. 2.2. Extração de Conhecimento - métodos e ferramentas 31 Figura 2.9: Metodologia CRISP-DM conforme [CCK+00] Compreensão dos dados Esta fase caracteriza-se por uma análise aprimorada quanto à qualidade dos dados, identificando eventuais problemas que possam prejudicar os resultados do processo de KDD.Esta fase tem como principais tarefas: identificar os dados, descrever os dados, explorar e verificar a qualidade dos dados. Preparação dos dados Nesta fase, os dados são devidamente identificados e tratados para posteriormente serem submetidos aos algoritmos de DM. Como tarefas principais destacamos: selecionar, limpar eventuais inconsistências ou valores ausentes, integrar e formatar os dados conforme os requisitos dos algoritmos a serem aplicados. Modelização Consiste em aplicar os algoritmos de análise de dados e observar os resultados obtidos, e, eventualmente, efetuar ajustes, seja retornando a uma das etapas anteriores ou apenas ajustando eventuais parâmetros dos algoritmos ou ferramentas de Data Mining em uso. As principais tarefas são: selecionar técnicas de modelização, definir testes e aferições, construir e analisar modelos. ILP permite superar estas limitações incorporando conhecimento prévio (background knowledge) sobre o domínio do problema e quando o conhecimento está guardado numa BD. Os métodos AVL obrigam a uma transformação de informação guardada em várias tabelas numa só, com consequente perda de informação. O ILP pode usar “diretamente” as várias tabelas sem transformação. Uma regra do tipo if-then é representada em predicados de 1ªordem e são formalmente representados por cláusulas Horn. Deste modo considerando que: B: Conhecimento prévio (background knowledge) representando por um conjunto de claúsulas Horn; P: conjunto de claúsulas Horn representando exemplos positivos; N: conjunto de claúsulas Horn representando exemplos negativos; Podemos ter uma hipótese (H) representada sob a forma de claúsulas Horn em que temos: ∀p∈P:H∪Bp(completude) ∀n∈N:H∪B2n(consistência) Sistemas ILP permitem armazenar e processar conhecimentos ou informações prévias sobre um domínio de conhecimento na forma de programas lógicos. Um programa lógico é constituído de claúsulas. Uma cláusula consiste basicamente de regras de 1ªordem, onde a conclusão é chamada de “cabeça” da regra. Um exemplo: pai(X, Y )∨mae(X, Y )←pais(X, Y ) Se Xé um dos pais de Yentão Xépai de You Xémae de Y, onde o símbolo ∨indica a operação lógica “ou”. Vantagens do ILP: •elevado poder expressivo; 2.3. Aprendizagem Computacional 39 •permite fornecer conhecimento do domínio; •fácil compreensibilidade dos modelos; •aceita múltiplas relações (tabelas de dados de BD). Entretanto, ILP não permite tratar grandes quantidades de dados; é limitado para manipular e processar dados numéricos, e é principalmente usado para tarefas de classificação em DM. Um dos tipos de sistemas de ILP mais populares é chamado MDIE (Mode Directed Inverse Entailment) da autoria de Stephen Muggleton. São exemplos desta categoria de algoritmos os sistemas Progol [Mug95], Aleph [Sri03], April [FSC06] e IndLog [Cam00,Cam04]. Estes sistemas implementam um algoritmo ganancioso13 de cobertura14. Têm geralmente um ciclo principal em que, em cada iteração constroem a cláusula com maior cobertura, juntam essa cláusula ao modelo (conjunto de hipóteses/cláusulas) e removem os exemplos positivos cobertos pela cláusula construída. Para construir a cláusula com melhor cobertura efetuam dois passos designados por: saturação e redução. Na saturação é construída a cláusula mais específica do espaço de hipóteses que vai ser pesquisado. Esta cláusula mais específica é o limite inferior do espaço de procura e serve também de fonte para os literais que constituem as cláusulas construídas no passo de redução. No passo de redução é feita uma procura desde a cláusula mais geral em direção à cláusula mais específica. Isso é feito começando na cláusula mais geral e especializando-a. Aplicando este refinamento aos descendentes da cláusula mais geral e depois recursivamente aos descendentes dos descendentes o algoritmo pode percorrer o espaço das hipóteses do ponto mais geral para o mais específico. Sempre que é gerada uma cláusula a sua cobertura é avaliada, isto é, calcula-se quantos exemplos positivos e negativos a cláusula permite derivar. Os exemplos deriváveis por cada cláusula são guardados na sua lista 13Greedy algorithm. 14Uma hipótese cobre um exemplo quando, juntamente com o background knowledge, consegue deduzir (explicar) esse exemplo. de cobertura (lista para os positivos e lista para os negativos). Uma cláusula pode ser aceite (pode ser uma possível cláusula resultado) se for consistente, isto é, se não cobrir nenhum exemplo negativo. Como o espaço de hipóteses é geralmente muito grande, os sistemas de ILP usam declarações de determinação para indicar que símbolos de predicado podem ser usados para construir as cláusulas e declarações de modo para indicar tipos para os argumentos dos predicados. A existência de tipos evita combinações inúteis de predicados. Além dos tipos, as declarações de modo indicam, para cada argumento, se este é de entrada, saída ou se vai ter uma constante. Os sistemas de ILP usam também parâmetros como o clauselength que indica um limite para o número de literais numa cláusula, o nodes que indica um limite para o número de cláusulas construídas e o language que indica um limite para o número de repetições de símbolos de predicado numa cláusula. Representar a informação em ILP - ILP tem sido uma área que permite que análises sejam feitas considerando os dados nas suas tabelas de origem sem a necessidade de junção dos dados ou supressão de atributos. A forma de representar os dados de uma base de dados relacional num sistema ILP é bastante simples, bastando identificar a tabela como sendo o predicado da cláusula e os atributos as variáveis, conforme ilustrado na Figura 2.11, e demonstrado a seguir: <Nome_da_Tabela> ( < v1> . . . < vn>), onde <Nome_da_Tabela> é chamado de predicado e < v1> . . . < vn>as variáveis que correspondem as colunas da tabela. Para representar uma informação disponível numa tabela que tem atributos incompletos ou que requeiram uma busca para completar usamos a notação: 2.3. Aprendizagem Computacional 41 Figura 2.11: Representação de dados relacionais em cláusula de 1ªordem em sintaxe Prolog Clientes (-,-,-,F,-). onde o símbolo “-” representa que não há informação disponível. Exemplos de representação de uma relação: Clientes(C, −,−, F, −)∧Compras(C, −,−,−, Dinheiro)→BomConsumidor(C) ou em a sintaxe Prolog: BomConsumidor(C) : −Clientes(C, −,−, F, −), Compras(C, −,−,−, Dinheiro). ILP é um método que se aplica a tarefa de classificação, onde o background knowledge (B) é expresso como sendo: - um conjunto de definição de predicados - um conjunto de exemplos positivos (E+) - um conjunto de exemplos negativos (E-) Uma aplicação ILP segue 3 passos: 1. definir um conjunto eficaz e representativo de exemplos (positivos e negativos); 2. definir um “background knowledge” relevante; 3. utilizar um sistema ILP genérico para processar o “background knowledge” e os exemplos positivos e negativos de modo a elaborar uma teoria (hipótese). Esta teoria ou hipótese é apresentada na forma de regras que permitem validar o “background knowledge” usando os exemplos dados (positivos e negativos). Na Figura 2.12 ilustramos as fases da aplicação do método, as quais descrevemos como: •todos os exemplos positivos são logicamente derivados de B e H; •todos os exemplos negativos são logicamente derivados de B e H; •que a fórmula que descreve a hipótese (H) representa alguma regularidade dos exemplos positivos e é construída usando o Background Knowledge (B) •a fórmula (H) pode ser descoberta por métodos ILP. Um conjunto de cláusulas pode ser construída pelo sistema ILP para representar a hipótese (H). •a busca para satisfazer a regularidade (H) é organizada usando a lógica de inferência em PROLOG. •numa aplicação de ILP em Data Mining o B, o E+, o Ee o H estão geralmente codificados em PROLOG. 2.3. Aprendizagem Computacional 43 Figura 2.12: Uso de técnica ILP para Extracção de Conhecimento 2.3.2.1 Implementações ILP em computação distribuída Em [FSSC09], é descrito o estado da arte das principais formas de implementação de sistemas ILP utilizando técnicas de paralelismo. Há basicamente duas formas de implementação do ILP em paralelo: sharedmemory edistributed memory. O modelo shared-memory consiste de implementar o sistema ILP num ambiente de cluster, onde há a partilha da memória por vários processadores. Por outro lado, o modelo distributed memory consiste de aplicar o sistema ILP num ambiente computacional distribuído, ou seja, tanto o processador como a memória estão disponíveis em ambientes distintos e unidos por sistemas de comunicação (rede). Do ponto de vista da aplicação dos algoritmos de implementação do ILP em paralelo, o autor [FSSC09] destaca ainda, que basicamente existem técnicas que simplesmente constroem modelos em paralelo em cada processador (worker) usando um subconjunto de dados e, em seguida, combinam os modelos encontrados em um único processador (master). Essa técnica costuma produzir os melhores resultados. As estratégias de paralelismo são mostradas na Figura 2.13 e descritas em [FSSCC05], [Fon06] e [FSSC09]. As abordagens de ILP paralelo baseam-se num tipo de algoritmo designado por MDIE (Mode-Directed Inverse Entailment) [Mug95]. São exemplos desta categoria de algoritmos os sistemas Progol [Mug95], Aleph [Sri03], April [FSC06] e IndLog [Cam00,Cam04]. Existem também estratégias de implementação de sistemas ILP paralelo que consideram os estágios de "busca", armazenamento dos dados (distribuído ou centralizado) e avaliação do modelo (cláusulas), de forma independente. Observa-se uma forte tendência em tratar os algoritmos ILP-paralelo em único ambiente sem considerar que melhores resultados, como a redução do ciclo de processamento, por exemplo, pode ser otimizada. Para que isso ocorra são necessárias algumas estratégias no momento da implementação, dentre elas, considerar que cada estágio de execução de um sistema ILP possa ser tratado em ambientes distribuídos, ou seja, utilizando a abordagem distributed memory. 2.3.3 Data Mining Multi-relacional Sob a perspectiva do KDD, podemos dizer que o ILP contribui para o desenvolvimento de técnicas e ferramentas de Relational Data Mining (RDM). É designado assim por que os dados e os relacionamentos são alocados na forma de tabelas relacionais. Quando temos apenas uma tabela para representar os dados, dizemos que esta está na forma não normalizada. Enquanto as técnicas tradicionais de Aprendizagem Computacional buscam extrair ou encontrar padrões de dados em tabelas únicas, o RDM procura identificar novos padrões ou regularidades nos dados em Bases de Dados Relacionais. Os dados em Bases de Dados Relacionais estão distribuídos em múltiplas tabelas, deste modo a técnica de ILP consiste em identificar padrões que utilizam na sua definição relações existentes entre os dados distribuídos em múltiplas tabelas. A análise decorrente desta forma evita o problema causado pela agregação de dados, onde se junta os dados dispersos em múltiplas tabelas 2.3. Aprendizagem Computacional 45 Master Worker 1 Worker p ... <E ,E ,B> + 1 - 1 <E ,E ,B> +- <E ,E ,B> + p - p Broadcast eval rule eval rule eval rule Send Result Send Result Collect Results Broadcast load() + - Partition E and E Master Worker 1 Worker p ... <E ,E ,B> + 1- <E ,E ,B> +- <E ,E ,B> + pBroadcast load() Broadcast learn rule learn rule learn rule Send Rule Send Rule Broadcast Eval Rules Eval Rules Eval Rules Collect Rules Send Result Send Result Collect Results Broadcast AddRule AddRule 2theory AddRule 2theory + Partition E a) EP-CT b) DP-LR Master Worker 1 Worker p ... <E ,E ,B> +- <E ,E ,B> +- <E ,E ,B> +- Broadcast radial search radial search radial search Send Rule Send Rule Collect Rules Broadcast AddRule... AddRule 2theory AddRule 2theory Master Worker 1 Worker p ... <E ,E ,B> +- Collect Theories Broadcast induce induce induce Send Theory Send Theory <E ,E ,B> + 11 <E ,E ,B> + pp Combine Theories c) SP-RRR d) DP-LT Figura 2.13: Esquemas simplificados de troca de mensagens dos diferentes tipos de algoritmos paralelos. (figura original de [FSSC09]) numa única, conforme ilustrado na Figura 2.14. Este processo de agregar dados de diferentes tabelas ocorre geralmente na etapa de pré-processamento e é requisito para algumas técnicas de Data Mining. Suponhamos a seguinte situação ilustrada na Figura 2.15, onde na Tabela 1 - Clientes temos os atributos: Id_Cliente, Nome, Idade, Sexo, Renda; e na Tabela 2 - Compras temos os atributos: Id_Cliente, Id_Prod, Data_Compra, Valor_Prod, Modo_Pagto. Na etapa de pré-processamento, anterior a aplicação de técnicas de Data Mining, observa-se que decorre a junção de alguns atributos dando origem a outros, de modo a permitir uma melhor aplicação dos algoritmos. Neste caso ilustrado, temos a Tabela 3 - Transações Consolidadas com os atributos: Id_Cliente, Idade, Renda, Qtde_Itens_Comprados, Valor_Total_Compras. Neste processo de agregar atributos, alguns padrões de dados deixam de ser encontrados, como por exemplo, a relação entre o atributo “Sexo” e a forma de pagamento preferida (“Modo_Pagto”). Contudo, preservando-se as tabelas 1 e 2 tal como estão definidas na base de dados relacional, e utilizando-se técnicas de ILP, o resultado já poderá ser outro. Por exemplo, se desejamos identificar a preferência de pagamento dos clientes versus a renda ou outro atributo qualquer escolhido, não há como não ter que repetir o atributo “Modo_Pagto” também na tabela única, resultando na duplicação de outras informações. Neste caso em particular observamos a necessidade de tratarmos os dados na forma mais primitiva, sem agregação do dados. Tal consideração representa que uma determinada compra pode dizer mais sobre o perfil do cliente do que o conjunto de todas as transações do cliente agrupadas. A análise de dados via técnicas de Data Mining numa única tabela pode resultar em: •ignorar informações relevantes dadas as condições de pré-processamento, principalmente na etapa de junção de atributos; 2.3. Aprendizagem Computacional 47 Figura 2.14: Tabela única com dados redundantes •provocar redundância de informação e com isso prejudicar o desempenho de alguns algoritmos, influenciando em termos de eficiência e mesmo eficácia; Vantagens de sistemas Relational Data Mining O RDM permite reduzir a necessidade de pré-processamento já que não necessita que os dados dispersos em diferentes tabelas de uma BDR sejam transferidos para uma única tabela ou exportados para um ficheiro único. A junção dos dados numa única tabela pode omitir eventuais padrões de dados. Outra vantagem relevante do RDM é descobrir regularidades e padrões de dados diretamente em várias tabelas de uma BDR e assim, identificar padrões nas relações existentes entre as tabelas. Com isso, evita-se a redundância de dados decorrente do processo de junção de tabelas. Figura 2.18: Visão de um fluxo de análise de dados no KNIME um desafio bastante oneroso e não acessível para qualquer empresa ou universidade. Por outro lado, o aperfeiçoamento das redes de computadores permitiu o surgimento de um novo paradigma computacional: a computação em Cluster [BBH99,BB99]. Acomputação em cluster consiste em reunir um conjunto de computadores (> 2) de configuração heterogênea numa rede local única, conforme apresentado na Figura 2.19. Para o utilizador, a impressão é que trata-se de um único computador virtual de elevado desempenho capaz de processar as mais exigentes tarefas computacionais. Cada computador pertencente ao conjunto chama-se nó de cluster, sendo que há um nó principal responsável pelo gerenciamento, controle e distribuição das tarefas para os demais. Um requisito relevante aos computadores pertencentes ao mesmo cluster é que todos os nós estejam configurados para rodar o mesmo sistema operativo. A aplicação da computação em cluster pode ter finalidades específicas, como: •necessidade de elevado desempenho computacional (high performance); •necessidade de alta disponibilidade de recursos (high availability/failover); ou 2.4. Computação Distribuída 55 Figura 2.19: Representação de um Cluster ainda, •necessidade de balanceamento de carga (load balancing) requerida para processamento contínuo. Em quaisquer desses casos é necessário que o sistema gerenciador do cluster seja capaz de detectar erros ou falhas, permitir ajustes e providenciar correções. Todas estas atividades devem ser executadas sem interromper o funcionamento do cluster. Um dos sistemas gerenciadores de cluster, muito conhecido no meio académico, é o Beowulf [SBS99]. Este sistema inicialmente proposto por Thomas Sterling23 é composto por uma biblioteca de funções de comunicação, chamada de Message Passing Interface (MPI), que permite aos programadores desenvolver programação 23http://www.cct.lsu.edu/~tron/Welcome.html paralela em linguagens como: C/C++ e FORTRAN, e também Python,Java ePerl. Com o uso da MPI, os programas podem ser executados em diferentes CPUs com a troca de mensagens e partilhamento de dados entre os nós. O Beowulf é um grande exemplo de um sistema de computação paralela com a implementação do conceito de PVM (Parallel Virtual Machine). OBeowulf é composto de um nó central ou mestre denominado de front-end, cuja função principal é controlar o cluster, monitorando e distribuindo as tarefas, atua ainda como servidor de arquivos e permite a ligação entre os utilizadores e o cluster. Os demais nós são conhecidos como clientes ou backends (ou ainda nós escravos), e são exclusivamente dedicados para processamento das tarefas enviadas pelo nó central. 2.4.2 Grid Computing A procura de computação de elevado desempenho para tratar problemas que requerem intenso processamento numérico ou o processamento de grande quantidade de dados em áreas como as ciências, as engenharias e os negócios tém crescido nos últimos tempos [FK99]. Alguns requisitos de processamento vão além dos disponíveis em centros de computação disponíveis nas universidades ou nas empresas, requerendo muitas vezes avultados investimentos para se ter acesso a super-computadores. Por outro lado, integrar centros de processamento dispersos geograficamente para tirar proveito de um processamento cooperativo e paralelo não é tarefa trivial, e envolve desde questões técnicas até sociais [FK99]. Surge um novo conceito na computação distribuída com o advento da Internet, a chamada meta-computação (metacomputing) [FK97]. A meta-computação ou computação omnipresente integrando diferentes recursos dispersos geograficamente tornou-se realidade a partir de conceitos implementados via Grid Computing, que consiste em integrar recursos computacionais distribuídos como sendo um único computador virtual capaz 2.4. Computação Distribuída 57 de processar os mais rigorosos processos. Um meta-computador acaba por ser um super-computador virtual à disposição do utilizador em qualquer lugar em qualquer tempo [BBL02]. A ideia original de Grid Computing era a de integrar centros de computação de elevado desempenho, mas com a Internet este conceito passou a ser amplamente utilizado para integrar diferentes computadores distribuídos pela Internet para resolver problemas comuns ou de interesse geral. Com um ambiente de Grid Computing recursos computacionais heterogéneos reais (físicos) passam a ser um único recurso computacional virtual [FK99]. Um ambiente de Grid Computing inclui toda a infra-estrutura de software e hardware que permita ao utilizador ter acesso às facilidades de um ambiente de computação avançada a custos reduzidos. Deve ser totalmente transparente ao utilizador o facto de se estar usando vários computadores simultaneamente espalhados por uma rede na execução de determinada tarefa que exija HPC (High Performance Computing) [FK99]. De acordo com Foster et al [FK99],o conceito de Grid Computing pressupõe algumas características: •não há um controle centralizado rígido como em grandes centros de processamento, pois os recursos devem estar dispersos numa rede. Entretanto, deve atender a requisitos de segurança, disponibilidade, integridade, confidencialidade no processamento de alguma tarefa; •deve ser concebido em plataformas abertas e protocolos não proprietários de modo a que se possa facilmente escalar a sua esfera de atuação. Conectar duas universidades num único Grid pode exigir esforço adicional se determinados padrões e protocolos não forem cumpridos; •a qualidade de serviço deve ser garantida, ou seja, tempo de resposta, disponibilidade, segurança e desempenho adequados; •cada centro de processamento é autónomo na sua administração; •não se pode comprometer a segurança dos utilizadores ou dos centros remotos; •não é necessário alterar a configuração do sistema operativo ou protocolos de rede; •os elementos distribuídos podem deixar de colaborar ao ambiente Grid deliberadamente; •é tolerante a falhas e seguro; •suporta componentes de hardware esoftware heterogéneos; •utiliza padrões e tecnologias existentes e pode interagir com aplicações legadas; •proporciona adequada sincronização entre os componentes da aplicação; Ainda de acordo com Foster et al [FK99] os princípios que um ambiente Grid Computing devem seguir são: •Escalabilidade: disponibilizar mais processamento com o acréscimo de mais recursos computacionais à medida do necessário. •Dinamismo e adaptabilidade: num ambiente Grid, o recurso não estar disponível pode ser a regra e não a exceção. Temos portanto, um ambiente dinámico e flexível capaz de atender as demandas adaptando-se as diferentes configurações e disponibilidades de recursos. •Heterogeneidade de recursos: tratar diferentes recursos de diferentes características e funcionalidades dispersos numa rede; 2.4. Computação Distribuída 59 Foster [FK99] e Baker [BBL02] advogam quando o Grid Computing deve incluir as seguintes funcionalidades: (a) administração hierárquica: cada centro gere os seus próprios recursos mas permite o uso pelo ambiente como todo; (b) serviços de comunicação: tudo que se refere a QoS24, banda de comunicação instalada, latência e tolerância a falhas em termos de comunicação é garantido por essa camada; (c) serviços de informação: gerir recursos e serviços disponíveis e o estado de utilização; (d) serviço de nomes: cada recurso disponível num ambiente Grid deve ter um nome único que permita a sua identificação por todo o ambiente; (e) sistema de arquivos distribuído: o acesso aos dados distribuídos deve ser transparente aos utilizadores, não importando onde os dados estão e estar sempre disponíveis; (f) controle de segurança e autorização: requisitos de segurança como confidencialidade, autenticação, integridade e disponibilidade da informação são fundamentais; (g) controle de disponibilidade e tolerância a falhas; (h) sistema de gestão de recursos e agendamento (programação de eventos); (i) economia computacional e negociação de recursos; (j) novas ferramentas e paradigmas de programação num ambiente Grid requerem bibliotecas, interfaces, API (Application Program Interface); 24Quality of Service (k) interface com o utilizador deve ser amigável, intuitiva e apresentar todos os recursos disponíveis. Deve estar disponível em qualquer plataforma em qualquer altura. Pode-se usar a Web para submeter e acompanhar uma tarefa; Um processo Grid Computing inclui as seguintes etapas [FK99]: 1. integrar recursos de software ehardware numa única rede como um recurso virtual único à disposição do utilizador; 2. implementar uma camada intermédia (middleware) para gerir recursos disponíveis e torná-los disponíveis de forma transparente; 3. desenvolver ferramentas para gerir as aplicações e a infra-estrutura disponível; 4. adaptar as aplicações de forma a usufruírem dos recursos Grid; Segundo [FK99], um Grid Computing pode ser sistematizado em quatro componentes principais: a) Grid Fabric: detectar e configurar recursos disponíveis numa rede (lan,wan, man) tais como: computadores pessoais, server,clusters,mainframes em diferentes sistemas operativos. b) Middleware: gerir a qualidade de serviço (QoS), alocação de recursos remotos, gestão de segurança e armazenamento; c) Grid development environment and tools: dispor de bibliotecas para desenvolver aplicações distribuídas; d) Grid Applications and Portals: desenvolver aplicações distribuídas em linguagens específicas, uso de interfaces com o utilizador via Web, uso de bibliotecas. 2.4. Computação Distribuída 61 2.4.3 Iniciativas Grid Computing Embora um ambiente Grid Computing deva ser usado para reduzir investimentos computacionais com a partilha de recursos computacionais, algumas iniciativas atualmente não têm previsto o lucro ou não remuneram o utilizador pelo uso de sua estação conectada à Internet. O SETI@home (SETI - Search for Extraterrestrial Intelligence) procura inteligência extra-terrestre a partir da análise de informações colectadas pelo radiotelescópio Arecibo [KWA+01]. Este aparato situado em Porto Rico analisa constantemente o espaço via sinais de rádio, gerando e armazenando extensas bases de dados para posterior análise. Outro projeto é o distributed.net que conecta o equivalente a 160.000 computadores (Pentium II 266MHz) trabalhando 24 horas por dia, 7 dias por semana, 365 dias por ano para simplesmente decifrar o algoritmo de criptografia de dados RSA25, sendo que a versão de RC5-64 foi decifrada em Julho de 2002 decorridos 1757 dias de intenso processamento [KWA+01]. A demanda por computação avançada é crescente, principalmente para tratar grandes quantidades de dados. O potencial da abordagem Grid demonstra que num futuro não muito distante teremos a disposição o fornecimento de unidades de processamento como temos na rede de distribuição de energia eléctrica. Bastará conectar nossa estação à Internet num site de fornecimento e poderemos executar complexos cálculos matemáticos ou proceder extensas análises de dados pagando alguma taxa de uso. É possível até que em sendo nós fornecedores de um ciclo de processamento possamos ser remunerados pela iniciativa [FK99]. 25RSA é o acrónimo dos nomes dos criadores do algoritmo: Ronald Rivest, Adi Shamir e Leonard Adleman 2.4.3.1 Globus É considerado um framework de meta-computação e abrange todos os serviços definidos para um ambiente Grid Computing padrão [FK99] conforme descrito na secção anterior. É composto por um elemento central chamado de Globus Metacomputing Toolkit (GMT) que fornece uma série de ferramentas para o desenvolvimento das aplicações distribuídas. Há um conjunto de módulos que implementam os diferentes serviços de um ambiente Grid tais como: gestão de recursos e serviços, detecção de falhas, comunicações, segurança, gestão de ficheiros, entre outros. Cada uma dessas funcionalidades está implementada em módulos específicos, entre os quais: GRAM, GSI, MDS, HBM, GASS, GEM, GARA. Cada um desses módulos é baseado num conjunto de API que implementam os respectivos serviços de um Grid [FK97]. Oframework Globus26 é flexível, multiplataforma e modular e segue a arquitectura padronizada pelo Open Grid Services Architecture (OGSA) do Global Grid Forum (GGF), permitindo assim que infra-estruturas tecnológicas diferentes possam compartilhar recursos de forma transparente ao utilizador. É um produto que está disponível sob a licença GNU General Public License (GPL), sendo as versões binárias e respectivos códigos fontes fornecidos para diferentes sistemas operativos. 2.4.3.2 Condor O ambiente Condor [LLM88] é um projecto de pesquisa da Universidade de WisconsinMadison27 e caracteriza-se por gerir um ambiente composto de vários computadores servidores ou desktop, dedicados ou não, e/ou também ambientes computacionais que utilizam sistemas em cluster, como o Beowulf 28. É basicamente um ambiente 26URL:http://www.globusconsortium.org/ 27URL:http://www.cs.wis.edu/condor 28URL: http://www.beowulf.org/ 2.4. Computação Distribuída 63 Grid Computing para gerir a capacidade de processamento de recursos computacionais de um “campus” ou de uma organização, permitindo executar tarefas que exigem alta disponibilidade e alto desempenho computacional. Tem como características principais a gestão de jobs, definição de políticas de uso do ambiente distribuído e gestão e monitoramento dos recursos computacionais. Há uma variante denominada Condor-G [FTL+01] que facilita a integração com ambientes Grid Computing baseado no Globus Toolkit [FK97]. É um produto que está disponível sem custo de licença, sendo as versões binárias e respectivos códigos fontes fornecidos para diferentes sistemas operativos (Linux, Windows). 2.4.3.3 BOINC O BOINC (Berkeley Open Infrastructure for Networking Computing)29 [And04] é uma arquitectura computacional distribuída que utiliza recursos computacionais registados voluntariamente a partir da Internet. Pode ser implementado num ambiente de intranet. É uma plataforma que permite aos cientistas gerir recursos computacionais públicos disponíveis na Internet em benefício de projetos científicos de grande dimensão. A arquitectura é composta por servidores de projetos que operam suas próprias aplicações e bases de dados, e partilham processamento voluntário disponível a partir de estações ligadas à Internet que “doam” ciclos de processamento por intermédio de software cliente instalado para esta finalidade. Alguns projetos como o SETI@home30,Folding@home31 utilizam a plataforma BOINC. Um exemplo de iniciativa regional é o projeto Ibercivis32. O Ibercivis é uma plataforma de computação voluntária que permite a colaboração dos cidadãos na investigação científica. Neste projeto, o utilizador é convidado a partilhar ciclos de 29URL: http://boinc.berkeley.edu/ 30URL: http://setiathome.berkeley.edu/ 31URL: http://folding.stanford.edu/ 32Ibercivis - www.ibercivis.pt a necessidade de manter infra-estruturas computacionais, custosas e complexas. Capítulo 3 Sistema HARVARD No Capítulo 2 tivemos a oportunidade de discorrer sobre os principais avanços nas áreas de Extração de Conhecimento, Aprendizagem Computacional e Computação Distribuída. A sinergia destas áreas permite propor soluções para questões de análise de grandes quantidades de dados com objetivo de extrair informações úteis à tomada de decisão, ou seja extrair conhecimento a partir de dados brutos. Uma análise de dados eficaz, e também eficiente, requer uma infra-estrutura capaz de suportar técnicas e algoritmos avançados definidos para o KDD. Entretanto, se de um lado temos o desafio de aprimorar o processo de análise de dados nas atuais organizações, temos também o desafio de viabilizar economicamente este mesmo processo. A utilização de recursos computacionais distribuídos para aplicações complexas tem sido uma tendência principalmente em campus universitários para apoiar projetos de investigação. Com isso reduz-se a necessidade de investimentos adicionais em termos de recursos computacionais ou aquisição de super computadores a custos elevados. O sistema harvard cujo o acrónimo significa HARVesting Architecture of idle machines foR Data mining é um ambiente computacional distribuído preparado para suportar tarefas de extração de conhecimento de grandes quantidades de dados utilizando técnicas de Data Mining com recurso aos algoritmos de Aprendizagem 71 Computacional. Com o harvard podemos ter disponível como que um “supercomputador virtual” usando computadores convencionais dispersos e ociosos numa rede. E assim, como diz o ditado popular: “a união faz a força”, já que a natural ociosidade de computadores numa rede local, em determinados períodos de tempo, pode ser convertida em processamento útil, gerando a possibilidade de novas aplicações. Alguns autores, entre eles [FK99], defendem que quaisquer aplicações que necessitem de computação de elevado poder computacional, onde determinado problema possa ser subdividido em pequenas porções para a busca de uma solução integrada, pode usufruir dos benefícios de um “super-computador virtual”. Com esta abordagem desenhamos uma plataforma computacional que tem como características essenciais, quanto ao uso de recursos, a escalabilidade e a adaptabilidade. É escalável enquanto puder fazer uso de recursos disponíveis, gerando um poder computacional compatível com a exigência das aplicações de KDD. Em complemento, é adaptativo por fazer uso de recursos computacionais em diferentes sistemas operativos (Linux e Windows) com a adoção da plataforma Java como ambiente de integração e portabilidade. Além disso, o harvard é uma plataforma de baixo custo pois utiliza recursos computacionais disponíveis e ociosos de uma organização, e portanto não perturba o normal uso dos recursos na rotina diária. É uma plataforma flexível e versátil pois utiliza diferentes ferramentas pré-existentes de análise de dados sem re-programações ou adaptações, sendo independente quanto à ferramenta requerida para a tarefa de KDD. É também uma plataforma fiável já que incorpora características de segurança e controle das operações e com esquemas de tolerância a falhas. E é ainda fácil de utilizar já que dispõe de uma linguagem de especificação de tarefas de KDD simultaneamente poderosa e de fácil compreensão por não especialistas. 3.1. Arquitetura do Sistema harvard 73 3.1 Arquitetura do Sistema harvard A infra-estrutura básica do harvard é composta por dois tipos de nós: um "nó" servidor e vários "nós" clientes. Para além destes “componentes principais” a arquitetura pode aceder a um servidor Web para obter programas de análise de dados e ainda a um sistema gestor de BD para obter os dados e armazenar os resultados e efetuar um back-up atualizado de informação sobre os nós clientes e o estado geral de desenvolvimento da execução das tarefas. Uma visão global da arquitetura da infra-estrutura básica pode ser vista na Figura 3.1. Figura 3.1: Arquitetura harvard A arquitetura inclui as seguintes características: •Plataforma baseada numa arquitetura Servidor/Cliente (Master/Worker); •Os nós Cliente estão sujeitos a uma política de utilização que permite a sua ativação/desativação sempre que essa política o determinar; •A arquitetura é modular, o que facilita a inclusão de novas funções; •A linguagem de programação da infra-estrutura dos módulos do Servidor e Cliente é o Java, o que concede elevada portabilidade à arquitetura; •A infraestrutura básica é independente do(s) algoritmo(s) de análise de dados; •Qualquer Cliente ou o Servidor pode ser executado tanto em sistemas operativos Linux como Windows; •Em caso de falha de um qualquer nó a tarefa em execução nesse nó é reinicializada num outro nó (tolerância a falhas dos Clientes); •Em caso de falha do Servidor um dos Clientes (previamente designado) assume o papel de servidor (tolerância a falhas do Servidor); •Permite acesso direto a Bases de Dados e a repositórios Web para transferência de dados ou de programas 3.2. Processo de Análise de Dados no harvard 75 3.2 Processo de Análise de Dados no harvard Oharvard inicia o processo de Análise de Dados lendo, de um ficheiro, a especificação do fluxo do processo (workflow) juntamente com a descrição de cada uma das tarefas do processo KDD. O fluxo do processo é representado por um grafo com dois tipos de nós: sequenciais e paralelos. Cada nó regista o conjunto de tarefas a serem executadas, representadas e designadas como UT (unidades de trabalho). Na Secção 3.5, que descreve a arquitectura do harvard, as UT são descritas em maior detalhe. No caso de um nó sequencial, as tarefas deverão necessariamente ser executadas em ordem de precedência devido à sua interdependência. Por outro lado, os nós paralelos podem ter tarefas executadas em simultâneo. Na Figura 3.2 é apresentado um exemplo de descrição de um processo KDD. A figura mostra ainda em detalhe um conjunto de tarefas definidas T1∼T15 que abrangem todo o processo, desde o pré-processamento, selecionando os atributos mais relevantes, até à consolidação dos resultados (T15). A descrição de cada tarefa Tn está codificada em XML1em ficheiros distintos que serão processados pelo módulo Gestor de Tarefas (GT) do harvard, conforme detalhado na Secção 3.5.1. 1Extensive Markup Language # This is the Task control description # using the Task Control Language (.tcl file) seq # execute tasks sequentially T1 # choose a 70%/30% train/test set par # execute the tasks in parallel seq T2 # generate a dataset without Att1 par T3 # eval dataset without Att1 using m = 10 T4 # eval dataset without Att1 using m = 50 endpar endseq seq T5 # generate a dataset without Att5 par T6 # eval dataset without Att2 using m = 10 T7 # eval dataset without Att2 using m = 50 endpar endseq barrier T[3-4], T[6-7] # wait for all of the tasks to finish T8 # choose the best set of attributes T9 # produce a 5-fold CV blocks par T[10-14] # do each CV i barrier T[10-14] # wait for all CV folds T15 # run with all data to produce the final theory endseq Figura 3.2: Descrição do fluxo do processo KDD em tarefas sequenciais e paralelas. 3.3. A especificação das tarefas 77 3.3 A especificação das tarefas A linguagem de especificação das tarefas, conforme ilustrado na Figura 3.3 é XML. A partir deste contexto são definidas variáveis com seus respectivos parâmetros que posteriormente serão interpretadas pelo harvard num dos seus módulos que trata da especificação da tarefa - o Gestor de Tarefas (GT). Na especificação de cada tarefa, o utilizador do harvard deverá informar em detalhe toda a informação relevante. Isso inclui descrever entre outros ítens: •local e nome(s) do(s) ficheiro(s) que contém os dados para análise; •algoritmo(s) a ser(em) usado(s) com respectivos parâmetros de análise; •nome da aplicação que implementa o algoritmo escolhido (p.ex: C4.5) •ferramentas de pré-processamento a serem usadas (p.ex: aplicação de script “Perl” para eliminar ou consolidar atributos); •local e formato de representação dos resultados. <?xml version="1.0" encoding="ISO-8859-1"?> <!DOCTYPE tasks SYSTEM ’’tasks.dtd’’ > # Run C4.5 on a data set stored in a Data Base and return the # result in a "results table" of the same DB ##### Task Description Language (.tdl) file ##### <workunit> <id> T1 </id> ### data ### <fetch-data> <method> jdbc </method> <server> dbserver </server> <user> dmuser </user> <db> kdd99 </db> <password> _______</password> <db-access> <source-data> <query> select *FROM data LIMIT 5000 OFFSET 100 </query> <file> kdd99.data </file> </source-data> ... </db-access> </fetch-data> ### source code ### <fetch-code> <source-code> # C4.5 code to construct the Decision Tree <getMethod> http </getMethod> <url> http://www.fe.up.pt/~rcamacho/c4.5 </url> </source-code> ... </fetch-code> ### sub-tasks execution ### <execution> <results-storage> <method> jdbc </method> <server> dbserver </server> <user> dmuser </user> <db> kdd99 </db> <password> _______ </password> </results-storage> ### sub-task 1 ### <subtask> <exec-mode> noninteractive </exec-mode> <exec-command> c4.5 -f kdd99 -m 100 -u </exec-command> <results-file> c45.output </results-file> <exec-time> 30 </exec-time> </subtask> ### sub-task 2 ### ... </execution> ### required resources ### <resources> <hd> 10 </hd> <ram> 0.5 </ram> <opsystem> linux </opsystem> </resources> </workunit> Figura 3.3: Descrição em detalhe de uma tarefa de KDD específica. 3.4. O uso da linguagem XML no harvard 79 3.4 O uso da linguagem XML no harvard A linguagem XML usada no harvard permite que o utilizador possa especificar claramente o processo de KDD pois "faculta um conceito para descrever, armazenar, permutar e manipular dados estruturados” [Hei01,Bra06]. Isso é possivel porque o XML permite estruturar a informação de forma hierárquica e independente, facilita a edição devido à sintaxe simples (qualquer editor de texto pode ser usado), e permite a fácil compreensão dos dados estruturados, já que não requer nenhuma sofisticada ferramenta de tratamento ou visualização. No caso do harvard os dados estruturados em XML permitem a fácil interpretação pelos diferentes módulos da plataforma, e também a geração dos resultados para posterior integração com outras ferramentas de análise de dados que importem formato XML, e facilita o armazenamento em bases de dados. Considerando que o harvard é desenvolvido em Java, há completa facilidade de processamento de ficheiros em XML devido às bibliotecas (classes) disponíveis. E considerando as características do XML, alterações em ficheiros XML não significam necessariamente alterações em código de programação Java. Pode-se, por exemplo, acrescentar novas "tags" como requisito de um novo módulo do harvard, ou simplesmente para melhor apresentar os resultados. O utilizador pode, através de um simples editor ou de qualquer outra ferramenta de edição/visualização para XML, especificar o processo de análise de dados bastando para isso carregar um “template” de tarefa do harvard que define todos os atributos passíveis de especificação com seus respectivos parâmetros. Uma vez escrito o ficheiro de especificação de tarefas este é inserido como parâmetro de ativação do harvard. Cabe destacar que os resultados do harvard por serem representados em XML, não necessitam de tratamento especial para apresentação ao utilizador, sendo visualizados em qualquer browser compatível. selection), sintonização de parâmetros, validação cruzada, execução dos algoritmos numa abordagem de Ensemble, etc. Estas oportunidades de paralelizar/distribuir a execução podem ainda ocorrer em situações menos frequentes mas não menos interessantes/importantes. Alguns algoritmos, por exemplo, têm um carácter estocástico. Para estes uma possibilidade seria efetuar várias execuções em paralelo e reportar resultados médios. Sistemas em que a semente inicial, por exemplo, determina a solução podem ser lançados em paralelo, por meio de várias execuções com sementes diferentes. Ainda algoritmos cuja solução seja dependente da ordem de processamento de exemplos podem usufruir de computação distribuída em que se faz N shufflings aos dados antes de executar o algoritmo e se apresentam no final as médias dos resultados individuais. Algoritmos de clustering como o k-means em que o utilizador tem que especificar o valor de K pode ser automatizado executando em paralelo o mesmo algoritmo com vários valores de k e depois num nó final escolhemos o melhor k usando uma medida de avaliação de clusters como por exemplo asilhouette. Embora estas situações, acabadas de referir, tirem facilmente vantagem de um sistema distribuído como o harvard em alguns casos o utilizador pode ter bastante trabalho a especificar todos as sub-tarefas em XML necessárias para distribuição da computação. Para agilizar esta tarefa de especificação do workflow de computação foi desenvolvido e incluído no harvard o conceito de macro tarefa que definiremos em seguida. Uma macro tarefa é uma tarefa com um nome reservado e que aceita um conjunto de parâmetros de acordo com a sua utilização. As macro tarefas são expandidas num passo de pré-processamento antes de o sistema ler o ficheiro de workflow das tarefas que o utilizador especificou. Associado a cada macro tarefa está um conjunto de programas e scripts que geram o grafo de tarefas necessário à implementação da macro tarefa. Este grafo pode conter um número grande de nós (tarefas a serem diretamente executadas pelo harvard). Por exemplo, numa macro tarefa de vali- 3.6. Extensões ao Sistema harvard 87 dação cruzada, o pré-processamento recebe o conjunto de dados original e o número CV de partições (folds) pretendido e gera CV+1 tarefas básicas do harvard em que CV delas contêm cada uma um par treino/teste típico da validação cruzada bem como o script para executar o algoritmo nesse par. Estas CV tarefas são executadas em paralelo. E tem uma última tarefa que espera pelo término de todas as tarefas inicias e utiliza os resultados da execução delas para calcular o resultado final da validação cruzada. Este esquema permite ainda uma extensão fácil do número de macro tarefas disponibilizadas pelo harvard. Para tal é preciso que o investigador responsável pelo harvard desenvolva os scripts necessários à super tarefa, defina a sua sintaxe e atualize o pré-processador. As situações referidas no início desta sub-secção podem facilmente ser implementadas como macro tarefas. Nesta secção descrevemos de modo abstrato algumas das macro tarefas implementadas. Exemplos concretos de implementação destas macro tarefas para vários tipos/classes de algoritmos são ilustradas no Capítulo 5. Cross validation - uma das macro tarefas implementadas é a validação cruzada. Os scripts que implementam estabelecem as N partições requeridas pelo utilizador e produzem N tarefas harvard que vão executar em paralelo correndo o algoritmo nos dados de cada partição. Após esse N nós existe uma barrier para que no nó N+1 que se segue este possa recolher os resultados de todas as N execuções anteriores e produzir o resultado. Feature subset selection - a versão de seleção dos melhores atributos implementada realiza uma procura primeiro-em-largura começando com todos os atributos e terminando no limite de profundidade especificado pelo utilizador. Na implementação desta estratégia são primeiro calculadas, nível a nível, todas as combinações de atributos a remover. E no final desta contagem são produzidas tarefas harvard num número igual ao número total de combinações mais uma tarefa final de recolha do resultado. Estas tarefas (menos a final) são executadas em paralelo e existe uma barrier para que a tarefa final espere pela conclusão de todas a anteriores para produzir o resultado final. Sintonização de parâmetros - esta macro tarefa recebe o nome do algoritmo a avaliar e um ficheiro com os valores a experimentar para cada parâmetro do algoritmo. Num passo inicial calcula todas as combinações desses parâmetros e de modo semelhante às macro tarefas anteriores cada combinação dá lugar a uma tarafa harvard que vai executar em paralelo com todas as restantes combinações. Existe também, uma barrier que antecede a tarefa final de cálculo do resultado global. 3.6.2 harvard e o ambiente Grid Computing Para a integração do sistema harvard com ambientes de processamento em Grid, criamos uma extensão à estrutura básica do próprio sistema. "-g" é a versão do harvard com a ligação a Grid. A conexão com um ambiente Grid permite extender as capacidades e funcionalidades do sistema harvard com a utilização de recursos computacionais adicionais. A vantagem deste modelo, ilustrado na Figura 3.6, é distribuir tarefas além do ambiente local do harvard. Algumas tarefas podem ter alguma restrição, seja pela complexidade ou mesmo pelo acesso a determinados dados remotos; e assim não podem ser executadas no ambiente local. A integração com um ambiente remoto Grid permite executar tarefas KDD usando um conjunto muito vasto de recursos computacionais. Entretanto, caberá ao harvard a consolidação dos resultados para apresentação ao utilizador. O importante neste modelo é agregar maior poder de processamento a partir da integração do harvard com ambientes Grid Computing. 3.6. Extensões ao Sistema harvard 89 Figura 3.6: Arquitetura harvard-g: (1) processamento local do harvard; (2) execução de tarefas em ambiente Grid Computing remoto Módulo de Conexão ao Grid na estrutura harvard Este módulo é agregado à estrutura do Sistema harvard apresentada na Secção 3.5. O módulo de Conexão ao Grid (CGrid) agrega, para além das funcionalidades básicas da implementação Grid compatível com o harvard (discutidas na Secção 3.6.2), as funcionalidades de tratamento das UT (Unidades de Trabalho) a serem encaminhadas para processamento em Grid. O módulo CGrid está baseado inicialmente na mesma máquina que hospeda o Servidor do harvard e tem interação com todos os demais módulos. Conforme a Figura 3.7 mostra, o módulo CGrid comportase de forma similar a um nó cliente e também tem alguns sub-módulos seja para monitorizar o estado da Grid (MONg), acompanhar a execução das tarefas recebidas do servidor (TRABg), monitorizar o estado dos recursos da Grid (GRg) e intermediar a comunicação entre o Grid (COMg) e o harvard. O CGrid interpreta as mensagens vindas do servidor e que são de três tipos: execução de uma unidade de trabalho, terminação da tarefa atual ou terminação de toda a atividade junto ao Grid. No caso de uma mensagem para execução de uma tarefa este módulo interpreta os campos da especificação da UT, codifica na forma compatível com a implementação Grid e submete a UT para processamento. A UT codificada na forma compatível do Grid deve especificar previamente a aplicação a executar. Caso o Grid não disponha da aplicação a executar, vai buscar o programa aplicação num repositório de algoritmos Data Mining implementados em Java, e também buscar os dados em uma Base de Dados usando JDBC. O resultado da execução da tarefa no ambiente Grid é colocado numa tabela da BD e comunicado ao servidor e aos demais sub-módulos do CGrid a conclusão da tarefa. Implementações Grid Neste caso, desenvolvemos conexão com sistemas compatíveis com o Globus Toolkit 4.0 (GT4) que dispõe de ferramentas de conectividade, entre elas o Commodity Grid (CoG) Kit [vLFGL01] [vLH05] que facilita a interconexão de ambientes heterogé- 3.6. Extensões ao Sistema harvard 91 Figura 3.7: Módulo Conexão Grid (CGrid) e submódulos neos, neste caso particular utilizamos a biblioteca compatível com Java chamada de jGlobus. A fim de extender o uso a outros ambientes Grid Computing também incluímos a versão harvard-g a conexão ao Condor [FTL+01,TWML01,TTL05] com a utilização da biblioteca Condor-API-Java3. A biblioteca Condor-API-Java permite submeter, monitorizar e controlar tarefas submetidas um Grid Computing baseado em Condor a partir de uma interface Java. Como o harvard é todo desenvolvido em Java a adaptação torna-se facilitada a partir do uso dessa API. As bibliotecas jGlobus eCondor-API-Java fazem parte da implementação do módulo CGrid conforme o caso da plataforma Grid a ser utilizada. Conexão ao Globus O Sistema harvard-g, na versão de conexão Globus, conforme representado na Figura 3.8 , inclui conexão com ambientes Grid Computing configurados para a plataforma Globus Toolkit (versão GT-4) [Fos05]. A biblioteca jGlobus para aplicações em Java contém uma API básica que permite o acessso remoto de dados (gridFTP), a submissão e monitorização de tarefas (GRAM), a implementação de recursos de segurança (GSI), e ainda, inclui o cliente myProxy (certificate store). OCoG Kit na versão Java facilita a integração de programas escritos em Java com o Globus Toolkit. Como o harvard é escrito em Java, para o harvard-g foi adicionado um módulo extra chamado de Conexão-Grid, junto ao nó Mestre do harvard.Este módulo utiliza basicamente a biblioteca (API) jGlobus [vLFGL01], e permite que uma tarefa originalmente definida para o harvard seja adaptada aos requisitos de submissão de tarefas num ambiente Grid Computing. O módulo Conexão Grid implementa as seguintes classes: (a) harvard.grid.autentica: sistema de autenticação e uso dos recursos do ambiente Grid, com uso das classes org.globus.myproxy eorg.globus.gsi, (b) harvard.grid.recursos: especificação dos recursos a serem utilizados ("stdin", 3http://code.google.com/p/condor-java-api/ 3.6. Extensões ao Sistema harvard 93 Figura 3.8: Representação dos módulos do harvard-g (versão Globus) "stdout", "stderr", programas a executar e diretório de trabalho), com uso da classe org.globus.rsl, (c) harvard.grid.ftp: transferência de ficheiros de dados e/ou programas a executar, com uso da classe org.globus.ftp, e (d) harvard.grid.tarefa: submissão de tarefas no ambiente Grid, com uso da classe org.globus.gram. Os resultados de submissão de tarefas num ambiente Grid são encaminhados ao Módulo Escalonador com status “finalizado”. O módulo Conexão Grid utiliza o certificado padrão x.509 do utilizador para permitir a submissão de tarefas ao ambiente Grid na plataforma Globus. Como o GT4, uma vez adequadamente configurado, aceita programas escritos em linguagem JAVA, o harvard-g encaminha previamente os algoritmos Data Mining codificados em “.jar” necessários a execução de tarefas KDD. Como exemplo, temos utilizado os algoritmos codificados para o ambiente WEKA [Han01,SR08,KFR08, WF05] e Yale [MWK+06]. Assim, uma vez escolhido o algoritmo, este é transferido e executado no ambiente Grid Computing previamente configurado para operar com Globus, de forma transparente ao utilizador. Para além do requisito dos algoritmos Data Mining estarem codificados em Java, o utilizador do sistema harvard deve ter necessariamente um certificado x.509 [CSF+08] válido e aceito no ambiente GT4 conectado ao harvard-g. Conexão ao Condor O sistema harvard-g, na versão de conexão ao Condor, conforme representado na Figura 3.9 , inclui conexão com ambientes Grid Computing que utilizam-se da arquitetura e solução Condor [TTL05]. A API Condor-Java viabiliza a integração de programas escritos em Java com um ambiente Grid Computing baseado em Condor. Nesta versão de integração ao Condor foi adicionado um módulo extra chamado de Conexão-Grid-Condor, junto ao nó Mestre do harvard.Este módulo é composto das classes, conforme ilustrado na Figura 3.10 , da biblioteca Condor-API-Java,e permite que uma tarefa 3.6. Extensões ao Sistema harvard 95 Figura 3.9: Representação dos módulos do harvard-g (versão Condor) Figura 3.10: Classes disponíveis na Condor-API-Java, descrição original com cobertura positiva [2-2,15-25] e cobertura negativa [10-60]. Se definimos C3 pela combinação de C1e C2obtemos: C3= ativa(Farmaco) ←atomo(Farmaco, A), pesoAtomico(A, 12), logp(Farmaco, LogP), menorQue(LogP, 0.2) com cobertura positiva [2-2,15-20] e cobertura negativa [10-40] A cobertura de C3pode ser obtida pela intersecção das coberturas positivas e negativas de C1e C2. Isto permite uma maior eficiência quanto à avaliação de cláusulas, que é a parte mais dispendiosa de um sistema ILP. O sistema pode gerar separadamente (em paralelo) cláusulas que não partilham variáveis entre si e, em seguida, calcular novas cláusulas combinando as previamente geradas. A cobertura de uma cláusula posterior poderá ser calculada pela intersecção das listas de cobertura das cláusulas iniciais e, portanto, sem usar chamadas ao Prolog para derivar os exemplos. Uma vez que é demorado analisar em cada cláusula a identificação desses grupos independentes de literais em runtime, precisamos de um processo eficiente. Em vez de analisar os literais, analisamos as declarações de modo. Declarações de modo que têm informações sobre os tipos de argumentos e, portanto, se dois conjuntos de literais não compartilham entre eles qualquer tipo de argumento, então eles não podem ter variáveis comuns e, portanto, eles podem ser considerados como duas ilhas separadas. Isto é a base para o algoritmo proposto. Por simplicidade chamamos ilha a um conjunto de declarações de modo que partilham tipos entre si e não partilham tipos com outras ilhas. O conjunto de declarações de modo de um conjunto de dados é dividido em ilhas em que uma declaração de modo de um ilha não partilha tipos com qualquer outra declaração de outra ilha. Isso garante que os literais gerados usando declarações de modo de ilhas diferentes não partilhem variáveis. 4.1. Uma nova abordagem para uma execução paralela de ILP 103 Resultados para esta implementação inicial parecem muito promissores. O pontochave para uma execução distribuída é que cada "nó" (ilha) funciona como um sistema MDIE (Mode-Directed Inverse Entailment) completamente independente, que permite a saturação/redução da operação de busca em menor tempo. Não há necessidade de comunicação entre "nós" ou "ilhas" de processamento. Uma possível explicação para esta abordagem produzir speedups em relação à execução sequencial reside no fato de na execução sequencial todas as cláusulas são avaliadas usando um demonstrador de teoremas (o Prolog engine) para calcular quais os exemplos (positivos e negativos) que a nova cláusula (a hipótese) cobre. Este processo é o ponto mais oneroso em termos computacionais do ciclo principal de um sistema de ILP. Com a divisão em ilhas, só as cláusulas construídas com as declarações de modo de cada ilha são avaliadas usando o processo “tradicional” de derivação dos exemplos. A cobertura de todas as cláusulas que resultem da combinação de cláusula entre ilhas diferentes são eficientemente calculadas pela operação de intersecção das listas de cobertura. Quanto maior for o número deste último tipo de cláusulas maior será o speedup em relação a uma execução sequencial. Como exemplo para a implementação do algoritmo, desenvolvemos uma etapa de pré-processamento que calcula o conjunto de declarações de modo e de determinação para cada ilha uma única vez para cada conjunto de dados e então podemos realizar qualquer análise utilizando um algoritmo paralelo como o Algoritmo 1. A vantagem do Algoritmo 1 é que o espaço de busca de toda a execução sequencial é particionada entre as ilhas, o que vai exigir menos requisitos de memória para fazer a computação. O pseudo-código do Algoritmo 1 efetua um ciclo (ciclo while da função CalculaIlhas()) em que escolhe como semente uma declaração que não tenha tipos de entrada e chama a função CompletaIlha() para recolher todas as declarações que tenham tipos comuns a qualquer declaração que esteja na ilha em construção. O Algoritmo 1 Calcula as ilhas a partir das declarações de modo function CalculaIlhas(TodosOsModos) ConjuntoDeIlhas ← ∅ Modos ←removeTiposEntradaCabeca(TodosOsModos) .passo de pré-processamento while Modos 6=∅do .processa todos os modos Modo ←semTipoDeEntrada(Modos) Modos ←Modos \{ Modo } Ilha ←CompletaIIha({Modo}, Modos) ConjuntoDeIlhas ←ConjuntoDeIlhas ∪{ Ilha } end while return ConjuntoDeIlhas end function function CompletaIlha(Ilha, Modos) repeat Modo ←ConectaSemIODeTipo(Modos) .retorna ∅se nenhum foi encontrado Modos ←Modos \{ Modo } Ilha ←Ilha ∪{ Modo } until Modo = ∅ return Ilha .Ilha com conjunto de modos end function 4.2. Implementação rápida 105 ciclo termina quando todas as declarações forem utilizadas. A função CompletaIlha() recebe uma declaração semente e vai acrescentando declarações até que não haja declarações que partilhem tipos com as declarações do conjunto em construção. O pseudo-código do Algoritmo 2 implementa um algoritmo tipo Cobertura Gananciosa3. Basicamente, o algoritmo executa um ciclo principal até não haver exemplos positivos cobertos. Em cada iteração deste ciclo é construída a cláusula que cobre o maior número de exemplos positivos (ainda não cobertos na altura). Antes de passar a uma nova iteração, os exemplos positivos cobertos pela cláusula construída são removidos da lista atual de exemplos positivos, a cláusula é adicionada ao modelo e o ciclo repete-se (até não haver mais exemplos positivos para cobrir). A busca pela cláusula com maior cobertuta é realizada evocando todas as ilhas para efetuarem a sequência tradicional de saturação/redução (característica dos sistemas MDIE em que é feita a busca da melhor cláusula no espaço de hipóteses). No final de cada ciclo principal as ilhas atualizam também a lista dos exemplos positivos ainda não cobertos. 4.2 Implementação rápida Outra vantagem do Algoritmo 1 é que pode ser fácil e rapidamente implementado em sistemas MDIE existentes como Progol [Mug95], Aleph [Sri03] ou IndLog [Cam04]. Com poucas alterações, é possível re-utilizar estas implementações para reduzir o ciclo de processamento das cláusulas, reduzindo os passos que visem atingir a saturação/redução dos objetivos. Para que a implementação seja possível, é necessário um sistema de ficheiros para armazenar (em um ficheiro, por exemplo) todas as cláusulas úteis mas ainda inconsistentes e ainda considerar a melhor e mais consistente cláusula que tenha sido encontrada quando da saturação/redução do processo de 3Tradução de Greedy Cover Induction algorithm Algoritmo 2 Algoritmo de Indução do tipo Cobertura Gananciosa function InduzTeoria(ConjuntoDeDados, Clientes) Ilhas ←CalculaIlhas(GetModes(ConjuntoDeDados)) .GetMode() retorna uma lista de declarações de modos definida para o conjunto de dados Teoria ← ∅ Exemplos ←ExemplosPositivos(ConjuntoDeDados) .conjunto inicial de exemplos positivos broadCast(Clientes, loadIslandsConjuntoDeDados) .cada cliente carrega os dados sem os modos while Exemplos 6=∅do .cobertura de todos os exemplos positivos IlhasTmp ←Ilhas while IlhasTmp 6=∅do .todas as ilhas processados no ciclo if Clientes 6=∅then W←cliente(Clientes) .verifica cliente disponível Clientes ←Clientes \{ W } I←island(IlhasTmp) .seleciona ilha não processada IlhasTmp ←IlhasTmp \{ I } enviaMsg(W, I) .cliente processará ilha I end if if (W ←ClienteTerminou) 6=∅then Clientes ←Clientes ∪{ W } .cliente disponível end if end while h←ResultadosDasIlhas() .retorna o melhor h das ilhas Cobertos ←Cobertura(h, Exemplos) .calcula exemplos positivos cobertos por h Exemplos ←Exemplos \Cobertos .nó mestre remove os exemplos positivos cobertos por h if Exemplos 6=∅then broadcast(Clientes, removeExemplos(Cobertos)) . nós clientes removem exemplos positivos cobertos end if Teoria ←Teoria ∪{ h } end while return Teoria end function 4.3. Avaliando o algoritmo 107 análise. Todo o resto da análise pode ser feito com um programa Prolog e alguns poucos comandos reunidos em um script. 1. No primeiro passo, usamos um script e/ou um programa Prolog para gerar as ilhas, mais especificamente os ficheiros que contenham as conclusões para cada uma das cláusulas tratadas nas ilhas. Não há nenhuma alteração nos arquivos de exemplos. 2. Neste passo, utiliza-se um pequeno programa em Prolog que executa o sistema MDIE em cada ilha e reúne os conjuntos de cláusulas geradas (consistentes e inconsistentes). Este programa, em seguida, produz todas as cláusulas consistentes realizando a intersecção das listas de cobertura das cláusulas combinadas e retorna a melhor cláusula consistente. Nesta etapa, pode-se utilizar o código de intersecção de listas de cobertura de cláusulas implementadas em sistemas MDIE existentes. 3. No passo final, precisamos de um programa ou script que implemente a etapa que busque a saturação/redução das cláusulas, a atualização dos exemplos positivos, e ainda removendo os exemplos cobertos até que não haja exemplos mais positivos em aberto. 4.3 Avaliando o algoritmo O Algoritmo 1 foi testado em cinco conjuntos de dados que estão caracterizados na Tabela 4.1. Os resultados são apresentados na Tabela 4.2 e Tabela 4.3 para os conjuntos mutagenesis (descrito em [SMKS94]) e carcinogenesis (descrito em [SKMS97]). Todas as ilhas foram corretamente identificadas em todos os conjuntos de dados. As ilhas identificadas para o conjunto CPDBAS (descrito em [CPC+11]) é mostrada nas Tabelas B.2 a B.5 do Apêndice B, para o conjunto DBPCAN (descrito em [CPC+11]) é mostrada na Tabela B.6 a B.9 do Apêndice B e para o conjunto triazines (descrito em [KMLS92]) na Tabela B.1 do Apêndice B. conjunto de dados número número de número de de exemplos declarações de modo ilhas mutagenesis 125/63 22 5 carcinohenesis 162/136 34 4 DSSTox-CPDBAS 843/966 218 37 DSSTox-DBPCAN 80/98 218 37 triazines 17063/17063 40 2 Tabela 4.1: Caracterização dos conjuntos de dados. Os dois valores nas células da coluna "número de exemplos” indicam o número de exemplos positivos e negativos respectivamente. modeh(active(+drug)) modeb(lumo(+drug,-energy)) modeb(lteq(+energy,#energy)) modeb(gteq(+energy,#energy)) modeb(methyl(+drug,-ring)) modeb(nitro(+drug,-ring)) modeb(ring_size_5(+drug,-ring)) modeb(ring_size_6(+drug,-ring)) modeb(hetero_aromatic_5_ring(+drug,-ring)) modeb(hetero_aromatic_6_ring(+drug,-ring)) modeb(carbon_6_ring(+drug,-ring)) modeb(carbon_5_aromatic_ring(+drug,-ring)) modeb(benzene(+drug,-ring)) modeb(logp(+drug,-hydrophob)) modeb(lteq(+hydrophob,#hydrophob)) modeb(gteq(+hydrophob,#hydrophob)) modeb(bond(+drug,-atomid,-atomid,#int)) modeb(atm(+drug,-atomid,#element,#int,-charge)) modeb(lteq(+charge,#charge)) modeb(gteq(+charge,#charge)) modeb(ball3(+drug,-ringlist)) modeb(phenanthrene(+drug,-ringlist)) modeb(anthracene(+drug,-ringlist)) Tabela 4.2: As 5 ilhas identificadas pelo Algoritmo 1 no conjunto de dados mutagenesis. O recall number não está mostrado nas declarações de modo pois só os tipos são relevantes. 4.3. Avaliando o algoritmo 109 modeh(active(+drug)) modeb(five_ring(+drug,-ring)) modeb(connected(+ring,+ring)) modeb(non_ar_hetero_5_ring(+drug,-ring)) modeb(non_ar_5c_ring(+drug,-ring)) modeb(six_ring(+drug,-ring)) modeb(non_ar_hetero_6_ring(+drug,-ring)) modeb(non_ar_6c_ring(+drug,-ring)) modeb(ar_halide(+drug,-ring)) modeb(alkyl_halide(+drug,-ring)) modeb(ester(+drug,-ring)) modeb(phenol(+drug,-ring)) modeb(alcohol(+drug,-ring)) modeb(sulfide(+drug,-ring)) modeb(ether(+drug,-ring)) modeb(ketone(+drug,-ring)) modeb(amine(+drug,-ring)) modeb(amine(+drug,-ring)) modeb(methoxy(+drug,-ring)) modeb(methyl(+drug,-ring)) modeb(sulfo(+drug,-ring)) modeb(sulfo(+drug,-ring)) modeb(nitro(+drug,-ring)) modeb(nitro(+drug,-ring)) modeb(ashby_alert(#alert,+drug,-ring)) modeb(mutagenic(+drug)) modeb(has_property(+drug,#property,#propval)) modeb(ames(+drug)) modeb(ind(+drug,#alert,-nalerts)) modeb(gteq(+nalerts,#nalerts)) modeb(lteq(+nalerts,#nalerts)) modeb(atm(+drug,-atomid,#element,#integer,-charge)) modeb(gteq(+charge,#charge)) modeb(lteq(+charge,#charge)) modeb(symbond(+drug,+atomid,-atomid,#integer)) Tabela 4.3: As 4 ilhas identificadas pelo Algoritmo 1 no conjunto de dados carcinogenesis. O recall number não está mostrado nas declarações de modo pois só os tipos são relevantes. conjunto de dados clauselength = 6, nodes=1000000 language=2 language=3 mutagenesis 2.9(2.2) 1.4(1.0) Tabela 4.4: Speedups6para diferentes valores de parâmetro language no conjunto de dados mutagenesis. Os valores indicados são a média e desvio padrão de 5 sequências de saturação/redução. O Algoritmo 2 foi ensaiado num dos conjunto de dados mais emblemáticos do ILP, o mutagenesis4O algoritmo foi testado sobre as etapas básicas do algoritmo de cobertura MDIE, especificamente os passos centrais do ciclo de “cobertura gananciosa”, que são também os passos onde é dispendido mais tempo de computação: a saturação seguida da redução. As experiências foram realizadas numa máquina com dois processadores do tipo Xeon quad Core com 32 GB de RAM. Nestas experiências foi variado o limite máximo de repetições de um símbolo de predicado numa cláusula (parâmetro language) e os resultados são a média de saturar e reduzir 5 exemplos. Embora o nosso interesse seja a independência das ilhas, que permite a execução de forma completamente independente, os resultados mostram-se promissores para máquinas de memória partilhada. 4.4 Melhoramentos para a implementação A implementação foi realizada utilizando, tanto quanto possível código já disponível, de modo a obter um protótipo rapidamente. Para esta implementação devemos considerar que podem haver melhorias na eficiência, incluindo uma estrutura de dados mais elaborada. Observando a operação do sistema, podemos perceber dois pontos de melhoria: otimização do espaço de armazenamento das cláusulas inconsistentes e otimização do tempo dispensado na intersecção dos resultados intermédios. Para comprovar estas melhorias observamos que cada "nó" cliente gerou em um ficheiro as cláusulas inconsistentes (cobrindo mais exemplos positivos do que o necessário) 4É também designado humoristicamete como a Drosófila do ILP. 4.5. Comparando com outras implementações 111 e também a melhor cláusula consistente. Podemos ainda observar que há uma grande quantidade de estruturas comuns nas cláusulas produzidas por um sistema ILP. Como sugerido em [CtCR08], o conjunto de cláusulas pode ser armazenado de forma eficiente numa Trie (prefix tree) poupando uma quantidade considerável de espaço em termos de armazenamento. Esta economia é conseguida sobretudo porque entre cada cláusula e as suas especializações varia no máximo um literal que está localizado no final da cláusula. Como numa Trie os prefixos comuns das estruturas são guardados uma única vez consegue-se uma enorme economia de espaço de armazenamento Se observarmos que a principal atividade do "nó" Mestre é realizar interseções entre os intervalos de cobertura, para gerar a cobertura de novas cláusulas, podemos acelerar a operação de interseção se codificarmos as listas de cobertura das cláusulas como vetores de bits (bit vectors). 4.5 Comparando com outras implementações Das estratégias de implementação do ILP paralelo proposto por Fonseca [FSSC09] somente a abordagens designada por DP-LT (Data Parallel Learn Theory) é adequada para computação distribuída desde que as tarefas (ou sub-tarefas) possam ser processadas de forma independente. A principal desvantagem é que cada sub-tarefa representa uma parte dos exemplos utilizados. No modelo proposto pelo algoritmo paralelo todas as ilhas podem referenciar todos os dados necessários e a execução da ilha é completamente independente, sem nenhuma interação entre elas. 4.6 Conclusões O algoritmo proposto neste capítulo tem a vantagem de processar sub-tarefas de forma independente, o que o torna adequado para sistemas distribuídos em máquinas independentes, e o uso de ambientes de computação como o Condor ou Compu- A execução teve o seguinte resultado: Best accuracy = 0.59 Remove the following determinations to get the best result: determination(active/1,has_property/3). determination(active/1,non_ar_6c_ring/2). Escolha de um bom conjunto de valores para os parâmetros de um algoritmo O desempenho de um algoritmo de Aprendizagem Computacional depende, em muitos casos, fortemente da combinação de valores dos seus parâmetros para analisar determinado conjunto de dados. Os valores por omissão nem sempre são os melhores para todos os conjuntos de dados. O harvard disponibiliza uma macro tarefa para sintonização de parâmetros de algoritmos de classificação disponíveis no Weka. Utilização do Weka A implementação foi realizada com o script principal (Tabela C.5 do Apêndice C) que gera os nós, chamado por vezes scripts auxiliares como o script “getResults” (Tabela C.6 do Apêndice C) que analisa os resultados dos nós que avaliam cada combinação e devolve o resultado final. Este resultado inclui as medidas avaliadas pelo Weka: accuracy, true positives, false positives, precision, recall, F measure , e ROC. Nesta experiência foi utilizado o conjunto de dados CPDBAS referido já no Capítulo 4 (descrito em [CPC+11]) e que contém um conjunto de moléculas e seus resultados em estudos de toxicidade, caracterizado na Tabela 5.3. O comando executado para criar o código e dados para cada tarefa harvard foi mkParameterTuning j48 . conf 1D2D_CPDBAS_v5c_1547_29Apr2008_md_Train . a r f f 1 D2D_CPDBAS_v5c_1547_29Apr2008_md_Test . a r f f 4 5.2. Utilização em tarefas de análise de dados 119 número de atributos número de classes número de exemplos 564 2 (activo/inactivo) 2292 Tabela 5.3: Caracterização do conjunto de dados CPDBAS usado para ilustrar a macro tarefa de sintonização de parâmetros implementada para conjuntos de dados no formato ARFF. em que se indica um ficheiro com o nome do algoritmo a usar e os valores para cada parâmetro do algoritmo (primeiro argumento), o conjunto de treino (segundo argumento), o conjunto de avaliação (turnig set – terceiro argumento) e a posição da classe (quarto argumento). Com este comando foram gerados 72 nós, cada um com uma combinação diferente de parâmetros, que foram, executados em paralelo e um nó final que calcula o melhor resultado e que é executado depois de uma barrier esperar pelas execuções paralelas. A execução teve o seguinte resultado: Best accuracy = 62.81 [-M 25 -C 0.2 -A] Best true positives = 0.63 [-M 25 -C 0.2 -A] Best false positives = 0.37 [-M 25 -C 0.2 -A] Best precision = 0.62 [-M 25 -C 0.2] Best recall = 0.63 [-M 25 -C 0.2 -A] Best F measure = 0.62 [-M 25 -C 0.2] Best ROC = 0.67 [-M 25 -C 0.2 -A] Indicando valores para as várias medidas disponibilizadas pelo Weka e o correspondente conjunto de parâmetros. 5.2 Utilização em tarefas de análise de dados Validação Cruzada Validação cruzada é uma técnica largamente utilizada para estimar a qualidade de um classificador. Para conjunto de dados grandes o processo pode ser acelerado correndo cada um dos componentes da validação cruzada em paralelo e calculando número de atributos número de exemplos 10 189 Tabela 5.4: Caracterização do conjunto de dados lowbwt usado para ilustrar a macro tarefa de validação cruzada implementada para conjuntos de dados no formato ARFF. no final o resultado. É esta abordagem que descrevemos para o caso de ficheiros ARFF usando algoritmos do Weka e para ILP. Utilização do Weka A implementação foi realizada com o script principal (Tabela C.7 do Apêndice C) que gera os nós, chamado por vezes scripts auxiliares como o script “getResults” (Tabela C.8 do Apêndice C) que analisa os resultados dos nós que avaliam cada combinação e devolve o resultado final. Este resultado inclui as medidas avaliadas pelo Weka: accuracy, true positives, false positives, precision, recall, F measure , e ROC. Nesta experiência foi utilizado o conjunto de dados de regressão [KCJ98] sobre estimação do risco de “dar à luz” crianças com baixo peso, caracterizado na Tabela 5.4. O comando executado para criar o código e dados para cada tarefa harvard foi mkCV weka lowbwt.arff weka.classifiers.functions.SMOreg 3 10 em que se indica um ficheiro de dados (primeiro argumento), o algoritmo a usar treino (segundo argumento), o número de “folds”(terceiro argumento) e a posição da classe (quarto argumento). Com este comando foram gerados 4 nós, cada um com um par treino/teste correspondente a um “fold”, que foram, executados em paralelo e um nó final que calcula o melhor resultado e que é executado depois de uma barrier esperar pelas execuções paralelas. 5.3. Executando um sistema de ILP no harvard 121 A avaliação desta macro tarefa utilizou a ligação ao Condor com a configuração um nó servidor e três clientes. A execução teve o seguinte resultado: RMSerr = 448.026(43.146) Que representa o Root Mean Square Error. Utilização do Aleph A implementação foi realizada com o script principal (Tabela C.9 do Apêndice C) que gera os nós, chamado por vezes scripts auxiliares como o script “getResults” (Tabela C.10 do Apêndice C) que analisa os resultados dos nós que avaliam cada combinação e devolve o resultado final. Este resultado inclui a medida avaliada pelo Aleph (Accuracy). Nesta experiência foi utilizado o conjunto de dados carcinogenesis referido já no Capítulo 4. O comando executado para criar o código e dados para cada tarefa harvard foi mkCV carcinogenesis 10 em que se indica o conjunto de dados e o número de folds, Com este comando foram gerados 10 nós, cada um com um par treino/teste correspondente a um “fold”, que foram, executados em paralelo e um nó final que calcula o melhor resultado e que é executado depois de uma barrier esperar pelas execuções paralelas. A execução teve o seguinte resultado: accuracy = 0.597(0.109) 5.3 Executando um sistema de ILP no harvard O algoritmo de ILP proposto no Capítulo 4 foi adaptado para poder utilizar o sistema harvard. Para realizar a adaptação foi feita uma alteração do ciclo principal característico (de cobertura ganaciosa) de sistemas como Aleph. A questão é que a linguagem de workflow do harvard não tem a definição de ciclos pelo que foi preciso pensar um processo alternativo. Esta foi a principal questão para a adaptação conforme descrevemos a seguir. A implementação do Algoritmo 1 de identificação das ilhas não sofreu qualquer alteração pois as ilhas são independentes da parte de execução do algoritmo. A parte relativa aos Clientes consistiu em torná-los autónomos. Isto é, correm do princípio ao fim sem precisarem de receber mensagens para trabalhar. O código original de um cliente recebe o conjunto de dados em que o ficheiro de background knowledge só tem as declarações de determinação e modo correspondentes a uma ilha e recebe como parâmetro o número de exemplos positivos que vai usar na saturação/redução. Corre do princípio ao fim de forma independente e devolve as cláusulas consistentes e inconsistentes aceitáveis. As cláusulas aceitáveis satisfazem as restrições de cobrir um número mínimo de exemplos positivos (parâmetro minpos), ter um número de literais inferior ao limite (parâmetro clauselength) e não excederem o limite de repetições do mesmo símbolo de predicado (parâmetro language). O ponto mais elaborado do processo de adaptação deriva, como se disse, de não haver ciclos na linguagem de workflow do harvard. Para contornar este problema o ciclo principal do processo de “cobertura gananciosa” foi implementado no código do processo final (antigo nó Mestre). Usando o código inicial do nó Mestre da implementação MPI descrita no Capítulo 4 foi retirado todo o processo de troca de mensagens pois agora este nó corre de modo independente e quando é executado já tem todos os dados (cláusulas produzidas por todas as ilhas) para produzir o modelo final. É construída inicialmente uma lista “global” dos exemplos positivos. O processo implementado é um ciclo em que cada iteração é calculada a melhor cláusula consistente. Esta cláusula é adicionada ao modelo e os exemplos positivos cobertos por essa cláusula são retirados à lista “global” de positivos. Se a lista “global” ficar vazia, o processo termina pois não há mais exemplos positivos por cobrir. No caso contrário simula- 5.4. Conclusões 123 se a remoção destes exemplos positivos fazendo a intersecção da lista “global” de positivos com a lista de positivos da cada cláusula individual. O resultado desta interseção é uma lista idêntica à avaliação da cláusula pelo método tradicional de “teste contra os exemplos” com os exemplos positivos, já cobertos, removidos do conjunto de dados. Esta implementação foi avaliada no conjunto de dados mutagenesis tendo sido executados (em 10 máquinas da LAN da FEUP) 625 nós clientes em paralelo e um nó final que construiu o resultado. O resultado de accuracy foi semelhante à execução sequencial. Esta implementação tem como principal limitação a necessidade de efetuar a saturação/redução em todos os exemplos. Num sistema como o Aleph é definida uma amostra limitada (3 a 5 exemplos), os exemplos desta amostra são usados para a saturação/redução e depois a melhor cláusula é logo aceite, os exemplos cobertos removidos e o ciclo continua até não haver positivos por cobrir. Neste processo geralmente são efetuados muito menos passos de saturação/redução do que na implementação harvard que tem que usar todos os positivos. No entanto, o fato de termos os resultados da saturação/redução para todas as cláusulas permite implementar (o que não foi ainda feito) uma procura ao nível da teoria (descrita como theory-level search no manual do Aleph). Isto é evitar a procura gananciosa habitual e encontrar uma teoria que, por exemplo, cubra todos os exemplos positivos com o menor número de cláusulas. 5.4 Conclusões Neste capítulo utilizamos uma gama variada de conjuntos de dados com características distintas de modo a explorar e demonstrar a utilidade das funcionalidades disponíveis no harvard. Foi mostrada a utilidade das macro tarefas codificando tarefas frequentes em análise de dados utilizando algoritmos de Aprendizagem Computacional, facilitando enormemente a tarefa do utilizador. A utilização do harvard com sistemas de ILP torna mais viável a utilização deste tipo de algoritmos de Data Mining Multi Relational possibilitando tanto análises mais complexas em tempo útil, uma vez que a linguagem de descrição tanto de dados como dos modelos é, no ILP, bastante poderosa, como tempos de resposta mais rápidos. Capítulo 6 Conclusões A quantidade de dados disponíveis em suporte digital é imensa e cresce a taxas exponenciais, e portanto, extrair informação de grandes quantidades de dados é hoje em dia uma tarefa virtualmente impossível de realizar manualmente e que requer, quando realizado por máquinas, elevada capacidade computacional. O sistema harvard (HARVesting Architecture of idle machines foR Data mining) apresentado nesta tese, mostra como o processo de Extração Automática de Conhecimento pode ser viável economicamente em qualquer organização, e pode ser feito usando recursos computacionais distribuídos numa rede local. Na verdade com o harvard temos à disposição um "super-computador virtual" usando computadores convencionais dispersos por uma organização e que por vezes, em alguns períodos de tempo, estão ociosos. Esta ociosidade pode ser convertida em processamento útil em benefício das organizações interessadas em utilizar KDD para análise de grandes quantidades de dados e assim obter alguma vantagem competitiva. A arquitetura proposta, juntamente com a proposta que foi feita nesta tese para uma implementação paralela de um algoritmo de ILP, aumenta as possibilidades de KDD pelo menos em três vertentes. O processo de análise de grandes quantidades de dados passa a ser economicamente viável pois não requer hardware especial e caro. O processo de KDD pode ser exequível para grandes quantidades de dados 125 pois pode ser realizado em tempo útil. Pode ser viável a utilização de algoritmos como os de ILP em análises de MRDM construindo modelos bastante complexos e, consequentemente, realizar análises mais profundas nos dados. 6.1 Contribuições Oharvard é um ambiente de baixo custo pois utiliza recursos computacionais disponíveis e ociosos de uma organização, e portanto não perturba o normal uso dos recursos na rotina diária. É uma plataforma flexível e versátil que pode utilizar diferentes ferramentas pré-existentes de análise de dados sem re-programações ou adaptações, sendo independente quanto à ferramenta requerida para a tarefa de KDD. É ainda uma plataforma fiável já que incorpora características de segurança e controle das operações e com esquemas de tolerância a falhas. Fácil de utilizar dispondo de uma linguagem de especificação de tarefas de KDD simultaneamente poderosa e de fácil utilização por não especialistas. Como diferencial deste trabalho podemos destacar: (a) proposta de um novo algoritmo de execução paralelo de ILP; (b) interligação do ambiente com um sistema de ILP permite a utilização de Relational Data Mining (RDM) para aplicações KDD em grandes bases de dados do mundo real superando as questões da exigência de elevado poder computacional; (c) o uso de recursos computacionais distribuídos e ociosos como uma alternativa para aplicações que necessitam elevado poder computacional; (d) o desenvolvimento de uma linguagem de descrição do processo de KDD pode viabilizar a disseminação desta tecnologia entre investigadores não habituados com o assunto, mas interessados em explorar conhecimentos “desconhecidos” em bases de dados; 6.2. Trabalho futuro 127 (e) interligação do harvard com ambientes Grid Computing, que permite extender ainda mais as funcionalidades do ambiente básico, e assim prover análises de dados ainda mais complexas, compartilhando de recursos computacionais externos à organização. (f) utilização de macro tarefas que facilitam o uso do sistema em tarefas de KDD. O uso de macro tarefas torna o sistema extensível pois basta desenvolver os scripts de implementação da macro tarefa e atualizar o pré-processador. 6.2 Trabalho futuro Um projeto da dimensão do harvard pode sempre ser aperfeiçoado e aumentado a fim de despertar maior interesse e uso prático nas organizações interessadas em se beneficiar desta plataforma. Melhoria de interface e interação com o utilizador É necessário que algumas melhorias sejam implementadas no harvard a fim de se tornar um ambiente ainda mais facilmente manipulável por utilizadores em geral. Afinal, certos utilizadores estão interessados apenas em analisar dados sem preocupação com configurações e requisitos técnicos extras para determinados ambientes computacionais. Para isso, é desejável desenvolver um ambiente com uma interface gráfica de modo a facilitar ainda mais a interação com o utilizador. Para além disso, a criação de uma interface gráfica baseada em objetos padronizados a serem organizados na forma de um workflow que sistematicamente podem originar os ficheiros de tarefas KDD utilizados como entrada junto ao harvard. Isso pode contribuir para que o utilizador se preocupe ainda menos com a sintaxe e comandos do harvard. Bibliotecas e repositórios de algoritmos Data Mining Outra possibilidade relevante é criar uma biblioteca de técnicas e tarefas KDD num repositório interno à