Utilizando técnicas de programação lógica indutiva para mineração de banco de dados relacional

Abstract

Resumo: As empresas estão sendo sobrecarregadas rapidamente com grandes volumes de dados e ao mesmo tempo estão se tornando, predominantemente, orientadas ao conhecimento. O aumento do domínio do conhecimento não melhora apenas os produtos, mas também é uma fonte para decisões estratégicas. Do ponto de vista da ciência da computação, os requisitos de conhecimento exigidos pelas empresas sempre dão mais ênfase a "conhecer que" (conhecimento declarativo) do que "conhecer como" (conhecimento procedural). A lógica matemática tem sido a representação preferida para o conhecimento declarativo e portanto, técnicas de descoberta do conhecimento são utilizadas, as quais geram fórmulas lógicas a partir dos dados. Programas lógicos oferecem uma representação poderosa e flexível para restrições, gramáticas, equações e relacionamentos temporais e espaciais. A técnica que induz conceitos a partir de dados gerando programas lógicos é chamada de Programação Lógica Indutiva (ILP - Inductive Logic Programming). Este trabalho descreve a implementação de um sistema para a descoberta do conhecimento (mineração de dados) em bancos de dados relacionais utilizando fundamentos de ILP e SQL. Esse sistema, DBILP (DataBase miner based on ILP), trabalha com dois mecanismos básicos: um que, baseado em ILP, especializa e, em seguida, generaliza as regras construídas, e outro que instância e valida essas regras, baseado em comandos SQL. ILP e SQL foram escolhidos pois o primeiro é uma técnica relativamente moderna e expressiva para a mineração de dados, e o segundo permite que grande volume de dados sejam manipulados, graças ao controle feito por um Sistema Gerenciador de Banco de Dados (SGBD). O funcionamento do DBILP é discutido ao longo desse trabalho, apresentando os módulos que o compõe, a sintaxe da linguagem de entrada definida, e a forma que as regras são construídas dentro do espaço de busca. A eficiência do DBILP é apresentada através de um experimento utilizando três outros sistemas bem conceituados no meio acadêmico, dois orientados a atributo-valor: C4.5 e CN2; e um sistema ILP: Progol. A análise desse experimento indica que o DBILP é particularmente útil no processo de descoberta do conhecimento em banco de dados (KDD - Knowledge Discovery in Databases).

Abstract: Industry is increasingly overwhelmed by large-volume-data. Industry is also becoming predominantly knowledge driven. Increased understanding not only improves products, but strategic decision making. From Computer Science point of view, the knowledge requirements within industry often give higher emphasis to "knowing that" (declarative knowledge) rather than "knowing how" (procedural knowledge). Mathematical logic has always been the preferred representation for declarative knowledge and thus knowledge discovery techniques are required which generate logical formulae from data. Logic programs provide a powerful and flexible representation for constraints, grammars, equations and temporal and spatial relationships. The technique that induces concepts from data building logic programs is called Inductive Logic Programming (ILP). This work describes a system implementation for knowledge discovery (data mining) in relational databases using ILP e SQL techniques. This system, DBILP (DataBase miner based on ILP) works with two basic engines: the first one, based on ILP, specializes and, afterwards, generalizes the built rules; the second one grounds and validates those rules, using SQL statements. ILP and SQL were chosen because the former is a new and expressive technique to mine data and the latter allows DBILP to work with a large data volume, since Database Management Systems (DBMS) controls data access and manipulation. Throughout this work DBILP mecanisms are described, its modules presented, input language sintax defined, and the way the system builds the rules in search space is described. DBILP's effectiveness is shown by an experiment using three well-known systems, two attribute-value oriented: C4.5 and CN2; and a ILP system: Progol. The experiment analysis points out that DBILP is particularly well suited for Knowledge Discovery in Databases (KDD) tasks.