Implementação em Java de um Algoritmo de Árvore de Decisão Acoplado a um SGBD Relacional

Prévia do material em texto

Implementação em Java de um Algoritmo de Árvore de Decisão Acoplado a 
um SGBD Relacional 
 
 
Mauricio Onoda & Nelson F. F. Ebecken 
COPPE/UFRJ – Universidade Federal do Rio de Janeiro 
monoda@uninet.com.br nelson@ntt.ufrj.br 
 
 
Resumo 
Atualmente um dos tópicos mais pesquisados em data mining é a sua integração com banco de dados. Os 
reflexos destes esforços já aparecem nos grandes bancos de dados comerciais, que estão fornecendo soluções 
integradas de data mining. Este trabalho avalia o acoplamento de um algoritmo de árvore de decisão não usual 
com um sistema gerenciador de banco de dados relacional e analisa o desempenho da sua implementação em 
Java. 
 
Abstract 
Nowadays one of the most researched topics in data mining is its integration with database. The reflexes of these 
efforts already appear in the major commercial databases, which are supplying integrated solutions of data 
mining. This work evaluates the coupling of an unusual decision tree algorithm to a relational database 
management system, and analyzes the performance of the implementation in Java. 
 
 
1. Introdução 
 
As pesquisas iniciais em data mining foram concentradas na definição de novas 
operações de mineração e no desenvolvimento de algoritmos, sendo a maioria dos sistemas de 
data mining implementada utilizando sistema de arquivos e estrutura de dados específica. 
Estes sistemas que operam diretamente num arquivo de dados (normalmente todo carregado 
na memória principal) tornaram-se insuficientes à medida que as aplicações envolveram a 
mineração de grandes data warehouses. Apesar da utilização de SGBD (Sistema Gerenciador 
de Banco de Dados) em data mining não ser nova, a maioria das aplicações ainda utiliza a 
arquitetura fracamente acoplada, onde os dados são lidos diretamente do banco de dados, 
tupla a tupla, usando a interface de cursor do SGBD. Este acoplamento fraco caracteriza-se 
pelo sistema de banco de dados ser executado num espaço de endereçamento diferente do 
processo de data mining. 
Este trabalho avalia o desempenho da implementação em Java de um algoritmo de 
árvore de decisão não usual, em ambiente de microinformática, numa abordagem fracamente 
acoplada. Este algoritmo, denominado PUBLIC (PrUning and BuiLding Integrated in 
Classification) [1], diferencia-se dos demais por realizar a poda da árvore durante a fase de 
crescimento. No PUBLIC, a fase de crescimento é baseada no algoritmo SPRINT (Scalable 
PaRallelizable INduction on decision Trees) [2], considerado o estado da arte na classificação 
de grande volume de dados, e a fase de poda baseia-se no princípio do MDL (Minimum 
Description Length) [3]. Estas características tornam este algoritmo adequado para o ambiente 
computacional escolhido. A utilização do Java proporciona uma solução mais versátil e 
abrangente, uma vez que a maioria dos grandes bancos de dados comerciais já possui versões 
onde está embutida uma máquina virtual Java (JVM - Java Virtual Machine). Para
comparação de desempenho com o Java, o mesmo algoritmo também foi implementado em 
PL/SQL, aproveitando-se das características do banco de dados Oracle utilizado. 
O trabalho está organizado como apresentado a seguir. A seção 2 mostra uma 
classificação das principais arquiteturas para integração entre data mining e banco de dados. 
A seção 3 apresenta um resumo sobre árvores de decisão. O detalhamento da implementação 
deste trabalho está na seção 4. A seção 5 contém a descrição das bases de dados utilizadas 
para testes e os resultados obtidos. Finalmente, na seção 6 são reunidas as conclusões deste 
trabalho. 
 
2. Arquiteturas para integração entre data mining e SGBD 
 
Uma classificação abrangente para as diversas alternativas de arquiteturas para 
acoplamento entre data mining e um sistema de banco de dados é apresentada em BEZERRA 
et al. [4], onde as abordagens foram divididas em três catego rias principais: convencional, 
fortemente acoplada e caixa-preta (black box). Na categoria convencional, também chamada 
de fracamente acoplada, não há integração entre o SGBD e a aplicação de data mining. Os 
dados são lidos, tupla a tupla, do banco de dados utilizando o mecanismo de cursor do SGBD. 
Na categoria fortemente acoplada, as operações intensivas de dados e as operações que 
consomem muito tempo do algoritmo de data mining são inseridas no SGBD. Esta categoria 
pode ser subdividida em duas abordagens : SQL aware e Extensions aware. Na abordagem 
SQL aware, estas operações são mapeadas em SQL padrão, enquanto que na Extensions 
aware as aplicações de data mining utilizam extensões do banco de dados e extensões do 
SQL. A abordagem Extensions aware agrega as seguintes opções: 
 
- Funções internas: uma função interna é um pedaço de código escrito como UDF (user-
defined function), no IBM DB2/CS, ou como stored procedure, no Oracle PL/SQL. Nesta 
abordagem, parte do algoritmo de data mining é expressa como uma coleção de UDF ou de 
stored procedures, os quais são apropriadamente utilizados em expressões SQL. 
- Tipos de dados: neste caso, as aplicações de data mining utilizam alguns tipos de dados 
específicos do SGBD para melhorar o tempo de execução do algoritmo. 
- Extensões do SQL: o SQL é estendido para permitir execuções de operações intensivas de 
dados no SGBD na forma de primitivas. Assim, as vantagens das extensões do SQL são 
utilizadas pelas aplicações para realizar suas tarefas de mineração. Uma vantagem da 
utilização de extensões do SQL sobre o SQL padrão (SQL aware) é que algumas 
informações, como por exemplo sumários estatísticos, que poderiam ser obtidas através de 
uma seqüência de comandos SQL, podem ser conseguidas através de um número menor de 
requisições ao SGBD. 
 
Na categoria caixa-preta, os algoritmos de data mining são totalmente inseridos no 
SGBD. Neste caso, a aplicação envia ao SGBD uma simples requisição, que normalmente é 
uma expressão de consulta, solicitando a extração de determinado conhecimento. A maior 
desvantagem desta abordagem é devido ao fato que nenhum algoritmo de data mining é o 
mais adequado para todos os conjuntos de dados. Assim, não há meios do algoritmo 
implementado no SGBD ser o melhor em todas as situações. 
 
3. Árvores de decisão 
 
Árvores de decisão são modelos estatísticos utilizados em problemas de predição 
supervisionada, onde um conjunto de atributos é utilizado para predizer o valor de um atributo 
de saída (resultado), sendo o mapeamento destas entradas para a saída denominado modelo 
preditivo. Os dados usados para estimar um modelo preditivo são um conjunto de casos 
(observações, exemplos) que contém valores das entradas e do resultado. Este modelo é 
aplicado em novos casos onde o resultado é desconhecido. Uma árvore de decisão possui este 
nome pois o modelo preditivo pode ser representado numa estrutura semelhante a uma árvore. 
A árvore de decisão é sempre lida de forma descendente, iniciando-se pelo nó raiz. Cada nó 
interno representa uma quebra baseada nos valores de um atributo de entrada, o qual pode 
aparecer em outras quebras na árvore. Os nós terminais de uma árvore são chamados folhas, 
que representam o resultado predito. Quando o resultado é discreto, o modelo é chamado de 
árvore de classificação, onde as folhas fornecem a classe predita e a sua probabilidade. 
Quando o resultado é contínuo, o modelo é chamado de árvore de regressão. Neste caso, as 
folhas fornecem apenas uma predição de valor do resultado. 
O método padrão usado no crescimento da árvore de decisão é baseado em partições 
recursivas, que é um algoritmo guloso descendente. Começando no nó raiz, um número de 
quebras pertinentes a um atributo de entrada é examinado. Para entradas contínuas, as 
divisões são segmentos disjuntos dos valores de entrada, enquanto que para entradas discretas 
as divisões são subconjuntos disjuntos das categorias de entrada.Várias estratégias podem ser 
utilizadas para determinar o conjunto de pontos de quebra, sendo que um critério é usado para 
escolher qual a melhor opção. Então, os casos no nó raiz são divididos de acordo com a 
quebra selecionada. A divisão é repetida para cada nó filho como se ele fosse a raiz de uma 
nova árvore. A profundidade da árvore é controlada pelo critério de parada. 
Uma árvore de decisão pode crescer até todo nó ser puro (árvore máxima), quando ela 
terá 100% de precisão nos dados de treinamento. A árvore máxima é o resultado de 
overfitting, pois ela se adapta à variação sistemática do resultado (sinal) e da variação 
aleatória (ruído). Com isso, ela não generaliza bem os novos dados, os quais normalmente 
contém muito ruído. Ao contrário, uma árvore pequena com somente poucos ramos pode 
subaproveitar os dados (underfitting) e, conseqüentemente, pode falhar na adaptação ao sinal. 
Isto resulta numa generalização pobre. Para evitar estes problemas, é necessário executar a 
poda da árvore, que pode ser do tipo descendente ou ascendente. Na poda descendente (top-
down pruning), ou pré-poda (pre pruning), podem ser utilizados os seguintes critérios de 
parada: limite na profundidade da árvore, limite na quantidade de fragmentação (por exemplo, 
não dividir um nó se o número de casos ficar abaixo de determinado limite) ou significância 
estatística (quando o teste chi-quadrado é utilizado como critério de quebra). Na poda 
ascendente (bottom-up pruning), também chamada de pós-poda (post pruning), uma grande 
árvore é gerada e então os ramos são cortados de maneira reversa usando um critério de 
seleção de modelo. A pré-poda normalmente é mais rápida, mas é consideravelmente menos 
eficiente que a pós-poda. 
 
4. Implementação 
 
Existem vários classificadores que constroem árvore de decisão, sendo que geralmente 
eles geram toda a árvore para depois podá- la. Esta fase de poda serve para melhorar a precisão 
e prevenir contra o overfitting. Entretanto, a geração de uma árvore de decisão em duas fases 
distintas pode resultar num desperdício de esforço considerado se uma subárvore inteira 
construída na primeira fase for podada na segunda fase. Se durante a fase de construção, antes 
de dividir um nó, puder ser concluído que ele será podado na próxima fase, este esforço pode 
ser evitado. Desta forma, como as leituras dos dados são repetidas várias vezes para gerar uma 
subárvore, pode-se conseguir reduções significativas de I/O e melhorar o desempenho do 
processo. 
Este trabalho está baseado no PUBLIC, que é um classificador tipo árvore de decisão 
que integra as duas fases. Se ele parar a expansão de um nó somente quando determinado que 
o mesmo será podado na próxima fase, há a garantia de que a árvore gerada é exatamente a 
mesma do que a obtida pela execução das duas fases separadamente, uma após a outra. 
Entretanto, determinar, durante a fase de construção, se um nó será podado na outra fase é 
problemático porque a árvore ainda está parcialmente gerada. Isto requer que seja estimado 
para cada folha desta árvore parcial, baseado nos registros contidos na folha, o menor custo da 
subárvore originada por esta folha. Quanto maior este valor, maior a quantidade de poda 
possível na fase de construção da árvore. Apesar do PUBLIC utilizar a entropia para 
selecionar o melhor ponto de divisão dos dados, neste trabalho utilizou-se o índice Gini, 
originalmente proposto por BREIMAN et al. [5], como definido no SPRINT. A grande 
vantagem deste índice é que seus cálculos necessitam somente da distribuição dos valores de 
classes em cada partição. 
Enquanto que os conhecidos classificadores CART [5] e C4.5 [6] utilizam o 
crescimento da árvore em profundidade (depth-first), no PUBLIC o crescimento da árvore é 
feito em largura (breadth-first) para permitir que a poda possa ser realizada de forma 
integrada. Durante esta fase de crescimento, o objetivo em cada nó é determinar o ponto de 
quebra que melhor divide os dados de treinamento pertencentes a esta folha. Para descobrir a 
melhor quebra para um nó são avaliadas todas as quebras dos atributos, sendo escolhido para 
dividir o nó o atributo que contém o ponto de quebra com o menor valor de índice Gini. Neste 
trabalho, como são utilizadas somente árvores binárias, um algoritmo guloso é aplicado em 
atributos discretos para dividir os valores sempre em dois grupos. 
Para prevenir o overfitting, o princípio do MDL é utilizado para a poda da árvore, 
tornando-a menos específica. A poda baseada no MDL possui as seguintes vantagens em 
comparação com outros algoritmos de poda: produz árvores com boa precisão para uma 
grande variedade de conjuntos de dados, produz árvores de menor tamanho e é 
computacionalmente eficiente. O princípio do MDL afirma que a melhor árvore é aquela que 
pode ser codificada usando o menor número de bits [1]. Assim, o desafio para a fase de poda 
é achar a subárvore de uma árvore que pode ser codificada com o menor número de bits. O 
custo de codificação de árvore compreende três custos separados: o custo para codificar a 
estrutura de uma árvore, o custo para codificar cada divisão, com o atributo e o respectivo 
valor e o custo para codificar as classes dos registros em cada folha da árvore. 
A estrutura de uma árvore pode ser codificada usando um simples bit para cada nó pois 
precisa especificar apenas se é um nó interno ou é uma folha. Como no PUBLIC são 
consideradas somente árvores binárias, esta técnica de codificação para representar árvores é 
quase ótima [1]. No custo para codificar cada divisão, o atributo a ser dividido pode ser 
codificado usando log2a bits (a é o número de atributos), enquanto que o valor do atributo 
depende se ele é contínuo ou discreto. Sendo v o número de valores distintos para o atributo a 
ser dividido, se o mesmo for contínuo, há v-1 pontos diferente onde o nó pode ser dividido, e 
log2(v-1) bits são necessários para codificar o ponto de quebra. Se o atributo for discreto, 
existem 2v subconjuntos diferentes de valores, sendo seu custo de divisão log2(2v-2). Para um 
nó interno N, seu custo de divisão será denotado por Csplit(N). O custo para codificar os 
registros em cada folha é dado pela Equação 4.1 [3], sendo S um conjunto que contém n 
registros pertencentes a uma das k classes e ni o número de registros com classe i. 
 
å
÷
ø
ö
ç
è
æG
+-+=
i
k
i
i k
nk
n
nnSC
2
log
2
log
2
1log)(
2
222
p (4.1) 
 
Depois de formulado o custo de uma árvore, o objetivo é calcular o custo mínimo de 
uma árvore gerada na fase de construção. Sendo S um conjunto de registros em N e N1 e N2 
são filhos de N, a subárvore de custo mínimo de raiz N, se N é uma folha, é ele mesmo. O 
custo da subárvore de N com menor valor é C(S)+1 (é requerido 1 bit para especificar se o nó 
é uma folha). Se N é um nó interno da árvore com dois filhos N1 e N2, então há duas opções 
para a subárvore de custo mínimo: somente o nó N (isto corresponde a podar os dois filhos do 
nó N e convertê- lo numa folha), ou N junto com seus dois filhos e as subárvores de custo 
mínimo de N1 e N2. Destas duas opções, a que possui menor custo será a subárvore de custo 
mínimo para o nó N. O custo da primeira opção é C(S) +1. Para calcular o custo da segunda 
opção, o procedimento é chamado recursivamente para processar o custo mínimo da 
subárvore de cada um dos filhos. O custo desta segunda opção fica então 
Csplit (N)+1+minCustoN1+minCustoN2. Neste algoritmo, os filhos de um nó N são podados se 
o custo para codificar os registros de dados em N é menor que o custo de codificação da 
subárvore de custo mínimo de N. 
Como no PUBLIC a poda deve ser realizada numa árvore parcial, não se pode assumir 
que o custo da subárvore de menor valor de uma folha N seja C(S)+1. Isto é verdade para uma 
árvore já totalmente construída, mas falso para uma árvore parcialpois esta folha pode ainda 
ser dividida posteriormente. Conseqüentemente, o custo da subárvore de N pode ser um pouco 
menor que C(S)+1 como resultado da sua divisão. Se C(S)+1 sobre-estimar o custo da 
subárvore de menor valor de N, pode ocorrer o over-pruning, ou seja, nós podem ser podados 
durante a fase de construção, mas que não seriam realmente durante a fase de poda. Isto é 
indesejável, pois a proposição do PUBLIC é que a árvore induzida por este classificador seja 
a mesma que a construída por um classificador tradicional. RASTOGI et al. [1] propõem que 
seja subestimado o custo mínimo da subárvore de cada nó folha que ainda pode ser 
expandido. Com a subestimação deste custo, os nós podados são um subconjunto daqueles 
nós que, de qualquer forma, teriam sido podados durante a fase de poda. Assim, a poda 
executada em PUBLIC distingue três tipos de nós folha: o primeiro tipo de folhas são aquelas 
que ainda precisam ser expandidas, o segundo tipo são aquelas que já são resultantes de uma 
poda e o terceiro consiste naquelas que não precisam ser expandidas pois são nós puros. No 
primeiro tipo, é determinado um limite inferior dos custos das subárvores destas folhas. Nos 
outros dois tipos, é utilizado o custo de C(S)+1. Além disso, quando os filhos de um nó N são 
podados, todos os seus descendentes são removidos da fila Q utilizada pelo procedimento de 
construção. Desta forma fica garantido que eles não serão expandidos por este procedimento. 
O algoritmo de poda do PUBLIC mostrado na Figura 4.1 é chamado pelo programa de 
construção da árvore periodicamente, ou depois que um certo número de nós é dividido (este 
pode ser um parâmetro definido pelo usuário), a partir do nó raiz da árvore parcialmente 
gerada. Neste trabalho a poda está sendo executada da segunda forma. É importante ressaltar 
que, depois de concluída a fase de construção, não existirá nenhum nó folha que ainda precisa 
ser expandido. 
 
Procedimento ProcessaCusto&PodaPUBLIC(Nó N) 
 
 1. Se N é uma folha ainda a ser expandida 
 2. Retornar o limite inferior do custo da subárvore de N 
 3. Se N é uma folha já podada ou uma folha não expansível 
 2. Retornar C(S)+1 
 3. minCustoN1 = ProcessaCusto&PodaPUBLIC(N1) 
 4. minCustoN2 = ProcessaCusto&PodaPUBLIC(N2) 
 5. minCustoN = min{C(S)+1, Csplit(N)+1+minCustoN1+minCustoN2} 
 6. Se minCustoN = C(S)+1 
 7. Podar nós filhos N1 e N2 da árvore 
 8. Remover nós N1 e N2 e todos os seus descendentes da fila Q 
 9. Marcar o nó N como já podado 
10. Retornar minCustoN 
 
Figura 4.1 – Algoritmo de poda do PUBLIC 
 
Qualquer subárvore de um nó N deve ter um custo de pelo menos 1, e este valor unitário 
é uma simples, mas conservadora, estimativa para o custo da subárvore de menor valor de um 
nó folha que ainda poderá ser expandido. Dois outros algoritmos foram testados por 
RASTOGI et al. [1] para melhorar esta estimativa de custo mínimo das subárvores dos nós 
folhas. Estes dois estimadores foram bem melhores mas não o suficiente para promover 
ganhos significativos no número de nós podados com relação à primeira estimativa. Os 
resultados indicaram que uma significativa melhora do desempenho pode ser realizada 
somente utilizando o custo unitário. 
 
4.1. Ambiente computacional 
 
Com o intuito de avaliar o desempenho do algoritmo PUBLIC implementado em Java 
utilizou-se o Oracle 8i v.8.1.7 (release 3) configurado em um microcomputador Pentium II 
350Mhz com 128MB de memória principal e executando o Windows NT Server 4.0, onde foi 
instalado o pacote Java SDK 2 v.1.3.0. O acesso da aplicação Java ao banco de dados Oracle é 
realizado através do driver JDBC Thin. Com o objetivo de ter uma referência para 
comparação de desempenho, este algoritmo PUBLIC também foi implementado numa 
arquitetura fortemente acoplada, onde os procedimentos foram escritos em Oracle PL/SQL, 
que é uma extensão do SQL, e armazenados dentro do dicionário de dados do Oracle. A 
utilização da linguagem PL/SQL só foi possível devido à sua capacidade de trabalhar com 
SQL dinâmico, não possuindo similar em outros bancos de dados. Uma característica 
operacional do PL/SQL é que, por ser uma linguagem de programação proprietária, sua 
utilização fica restrita aos bancos de dados da Oracle. Uma avaliação de desempenho de uma 
abordagem fortemente acoplada com PL/SQL em ambiente Oracle paralelo é mostrada em 
SOUSA et al. [7]. Observa-se que, em ambas as implementações (Java e PL/SQL), os 
comandos SQL executados são os mesmos. 
 
4.2. Java 
 
Em três anos, o Java passou de uma linguagem de programação usada no 
desenvolvimento de simples programas com interface gráfica que podiam ser enviados pela 
Web para uma plataforma para desenvolvimento e disponibilização de aplicações corporativas 
e de Internet. O Java tornou-se muito popular entre os desenvolvedores de aplicação porque 
os deixou mais produtivos e por ser uma linguagem moderna, robusta e orientada a objeto. 
Além disso, segundo ORACLE [8], a popularidade sem precedentes do Java é decorrente de 
três benefícios: 
 
1. O desenvolvimento de aplicações é mais simples: o Java oferece características como o 
suporte para rede e para programação concorrente (multithreading), que tornam o 
desenvolvimento de aplicações mais simples que a maioria dos seus predecessores; 
2. As aplicações são independentes de plataforma: o mesmo código binário Java pode ser 
executado em qualquer plataforma que suporta uma máquina virtual Java, incluindo 
mainframes; 
3. As aplicações podem ser desenvolvidas como componentes: o Java oferece um modelo de 
componentes, o JavaBeans, que permite aos desenvolvedores definir e encapsular 
componentes que podem ser montados com componentes escritos por outros 
desenvolvedores. 
 
Através de um programa Java, há duas opções para acessar banco de dados: o JDBC 
e/ou o SQLJ, onde ambos são APIs (também denominados drivers, pacotes). O JDBC (Java 
Database Connectivity) é um padrão independente de fabricante, desenvolvido pela empresa 
Javasoft, o qual foi modelado com base no ODBC, desenvolvido pela Microsoft. O JDBC é 
atualmente o método "de facto" para acessar banco de dados com o Java. Muitas empresas, 
entre as quais Oracle, Intersolv e Weblogic, desenvolveram tipos de drivers JDBC. O SQLJ é 
um padrão para embutir SQL diretamente em programas Java. Ele é um produto de uma 
junção de esforços da Oracle, IBM, Sybase, Tandem e Informix. Apesar do JDBC e do SQLJ 
serem complementares, o JDBC é necessário quando se utiliza SQL dinâmico, que é o caso 
desta aplicação, enquanto que o SQLJ é utilizado para SQL estático. 
A Oracle oferece dois drivers JDBC para o lado cliente, o Thin e o OCI, e um driver 
JDBC para servidor (dentro do Oracle JServer). O Thin é um driver tipo 4, escrito totalmente 
em Java, enquanto o OCI é um driver tipo 2, que é um nível implementado no topo do Oracle 
Call Interface (biblioteca C para acessar o SGBD Oracle). O driver JDBC para servidor é 
executado no mesmo espaço de endereçamento e processo do banco de dados, acessando 
diretamente SQL e PL/SQL. 
 
5. Estudo de casos 
 
Para avaliar a implementação realizada neste trabalho, foram conduzidos experimentos 
utilizando as seguintes bases de dados: base de dados real de domínio público, base de dados 
de meteorologia e base de dados de companhia de seguro. Estas duas últimas bases, que 
também contêm dados reais, foram consideradas pois possuem uma dimensionalidade 
adequada aos testes pretendidos, uma vez que as bases de dados reais de domínio público 
geralmente são pequenas. Estes experimentos utilizaram o método denominado holdout [9] 
para a estimativa de taxa de erro, onde uma parte dos dados é reservada para treinamento e o 
restante é utilizado para teste. Na prática, foi selecionado aleatoriamente 30% dos dados para 
teste, ficandoos 70% restantes para treinamento. 
 
- Base de dado real de domínio público: foi utilizada a base de dados denominada “Adult”, 
uma das maiores do UCI Machine Learning Repository [10], com 48.842 registros. Esta 
base possui 8 atributos discretos e 6 atributos contínuos, com 2 classes de saída. Além 
disso, também possui valores ausentes. 
- Base de dados meteorológicos: são dados adquiridos no Aeroporto do Rio de Janeiro, cuja 
finalidade é a previsão de nevoeiro. Os arquivos texto gerados, um para cada ano, com o 
registro da observação meteorológica horária de superfície com informações de 36 
atributos coletados diariamente foram concatenados numa única base de dados, 
totalizando 28.596 registros. COSTA [11] realizou uma limpeza nestes dados devido ao 
grande número de inconsistências e ruídos, o que resultou num conjunto com 18 atributos 
de entrada e 1 atributo de saída, para um total de 26.492 registros. 
- Base de dados de companhia de seguro: estes dados foram extraídos de um data 
warehouse que coleta e analisa dados de uma companhia privada de seguro de vida. Os 
arquivos disponibilizados pela companhia descrevem o relacionamento entre clientes, 
contratos de seguro e componentes de tarifa, sendo que a identificação de alguns atributos, 
bem como a explicação sobre o conteúdo dos mesmos, estão protegidas por questões de 
sigilo. As tabelas inicialmente armazenadas no servidor paralelo Oracle do NACAD/UFRJ 
foram agrupadas numa única tabela, com 80 atributos e 147.478 registros. Após a limpeza 
dos dados realizada por COSTA [11], o conjunto resultante ficou com 130.143 registros e 
64 atributos, assim distribuídos: 9 atributos com informações de clientes, 33 atributos de 
características de família, 13 atributos de contratos de seguro, 15 atributos de 
componentes de tarifa e 1 atributo contendo a classificação do cliente. 
 
5.1. Resultados 
 
O desempenho da implementação em Java e o erro calculado para as bases de dados 
avaliadas estão mostrados na Tabela 5.1. Nestes resultados, como as árvores geradas são 
binárias, o tamanho de cada árvore (número de nós) é a medida da sua complexidade. 
 
Base de dados 
Tamanho 
da árvore 
(nós) 
Tempo de 
execução (s) 
Java 
Erro 
(%) 
Adult 105 717 18,32 
Meteorologia 183 379 36,75 
Seguro 267 39.006 30,86 
 
Tabela 5.1 – Resultados da implementação em Java 
 
Na Tabela 5.2 compara-se o desempenho do algoritmo PUBLIC implementado em Java 
e em PL/SQL. 
 
Base de dados 
Tempo de 
execução (s) 
Java 
Tempo de 
execução (s) 
PL/SQL 
Adult 717 797 
Meteorologia 379 398 
Seguro 39.006 38.413 
 
Tabela 5.2 – Comparação entre Java e PL/SQL 
 
6. Conclusões 
 
Enquanto a maioria das pesquisas envolvendo a integração de SGBD com data mining 
direciona-se a melhorar a escalabilidade e o desempenho das técnicas de análise de dados, 
este trabalho mostrou que é completamente viável a execução de data mining em ambiente de 
microinformática com Java. A característica de poda integrada do algoritmo PUBLIC foi 
fundamental para o sucesso nas execuções dos experimentos pois, devido à capacidade de 
processamento do microcomputador, é inviável aguardar o final da construção da árvore para 
grandes bases de dados no caso de pós-poda. 
Um ponto que ressaltou nos experimentos realizados foi o desempenho semelhante 
entre o Java e o PL/SQL. No início deste trabalho alguns desenvolvedores experientes 
afirmaram que, neste tipo de aplicação, o Java seria muito mais lento que o PL/SQL. Este fato 
mostra que a utilização do Java deve ser considerada em soluções de data mining integradas 
com SGBD pois também garante à aplicação uma grande portabilidade, uma vez que os 
principais bancos de dados comerciais já interagem com o Java. 
Os resultados desta implementação abrem possibilidades para pesquisas na área de data 
mining incremental utilizando este tipo de plataforma, cujo conjunto aproximar-se-ia das 
necessidades das corporações, onde a repetição de todo o processo de mineração para uma 
determinada base de dados devido à inclusão de novos registros é computacionalmente 
onerosa. 
 
Referências bibliográficas 
 
[1] RASTOGI, R., SHIM, K., “PUBLIC: A Decision Tree Classifier that Integrates 
Building and Pruning”. In: Proceedings of the 24th International Conference 
on Very Large Databases (VLDB), New York, USA, 1998. http://www.bell-
labs.com/user/rastogi/pub.html. 
[2] SHAFER, J., AGRAWAL, R., MEHTA, M., “SPRINT: A Scalable Parallel 
Classifier for Data Mining”. In: Proceedings of the 22nd International 
Conference on Very Large Databases (VLDB), Mumbai (Bombay), India, 
1996. http://www.almaden.ibm.com/cs/quest/PUBS.html. 
[3] MEHTA, M., RISSANEN, J., AGRAWAL, R., “MDL-based Decision Tree 
Pruning”. In: Proceedings of the International Conference on Knowledge 
Discovery in Databases and Data Mining (KDD), Montreal, Canada, 1995. 
http://www.almaden.ibm.com/cs/quest/PUBS.html. 
 
[4] BEZERRA, E., MATTOSO, M., XEXÉO, G., “An analysis of the integration 
between data mining applications and database systems”, In: Proceedings of 
the 2nd International Conference on Data Mining (Data Mining II), pp. 151-
160, Cambridge, UK, 2000. 
[5] BREIMAN, L., FRIEDMAN, J. H., OLSHEN, R. A., et al., Classification and 
Regression Trees, First CRC Press reprint, Boca Raton, USA, Chapman & 
Hall / CRC, 1998. 
[6] QUINLAN, J. R., C4.5: Programs for Machine Learning, 7 ed., San Mateo, 
USA, Morgan Kaufmann Publishers, 1993. 
[7] SOUSA, M. S. R., MATTOSO, M., EBECKEN, N. F. F., “Mining a large 
database with a parallel database server”, IDA – Intelligent Data Analysis, 
n.3 (1999), pp. 437-451, Oct.1999. 
[8] ORACLE CORPORATION, Developing Stored Procedures In Java, Oracle 
Technical White Paper, Redwood Shores, USA, 1999. 
[9] WITTEN, I. H., FRANK, E., Data Mining – Practical Machine Learning Tools 
and Techniques with Java Implementations, 1st ed., San Francisco, USA, 
Morgan Kaufmann Publishers, 2000. 
[10] UCI MACHINE LEARNING REPOSITORY. http:///www.ics.uci.edu/~mlearn/ 
MLRepository.html. 
[11] COSTA, M. C. A, Data Mining em Computadores de Alto Desempenho 
Utilizando-se Redes Neurais, Tese de D.Sc., COPPE/UFRJ, Rio de Janeiro, 
1999.