Estudo de Caso de Mineração de Dados Multi-Relacional:
Aplicação do Algoritmo ConnetionBlock
em um Problema da Agroindústria
Ederson Garcia1, Marina Teresa Pires Vieira2
Faculdade de Ciências Exatas e da Natureza – Universidade Metodista de Piracicaba
(UNIMEP)
Piracicaba – SP – Brasil
1
[email protected]
2
[email protected]
Abstract. This paper presents a case study of multi-relational data mining
using the ConnectionBlock algorithm, applied to the database of a sugar mill.
The algorithm handles multiple tables not explicitly correlated but which
influence one another according to the semantics of the data involved. The
experiment revealed very interesting and useful patterns that are not found
using traditional algorithms. The paper aims to present how the data were
prepared to obtain better expressiveness of the rules generated, showing the
potential of the algorithm to find patterns in semantically related data.
Resumo. Este artigo apresenta um caso de aplicação de mineração de regras
de associação multi-relacional usando o algoritmo ConnectionBlock, em uma
base de dados real de uma indústria de açúcar e álcool. O algoritmo processa
múltiplas tabelas que não são explicitamente relacionadas, mas que têm
influência entre si devido à semântica entre os dados envolvidos. O
experimento revelou padrões interessantes e úteis, impossíveis de serem
encontrados usando algoritmos tradicionais. O artigo tem como objetivo
apresentar como os dados foram preparados para melhor expressividade das
regras geradas e os resultados obtidos, mostrando o potencial do algoritmo
para encontrar padrões em dados que são semanticamente correlacionados.
1. Introdução
As técnicas de mineração de dados tradicionais processam dados que estejam
armazenados em uma única tabela. Se os dados envolvidos pertencem a tabelas
distintas, é necessário que eles sejam transferidos para uma única tabela para que os
algoritmos possam ser utilizados. O processo de transferência dos dados é uma operação
de alto custo e pode levar à perda de informações, além de poder resultar em uma
grande quantidade de dados replicados [Džeroski 2003], [Pizzi,Ribeiro e Vieira 2005].
Um outro problema causado pela junção das tabelas é a grande quantidade de dados
resultante que pode afetar o desempenho do algoritmo de mineração [Jensen e Soparkar 2000]
ou mesmo tornar o processo impraticável [Ng, Fu e Wang 2002].
Os métodos de mineração de dados multi-relacional buscam por padrões que
envolvem múltiplas tabelas (relações) de um banco de dados relacional
[Džeroski 2003], [Han e Kamber 2006]. Esses métodos processam as tabelas
separadamente e são empregados em situações em que o uso de métodos de mineração
que processam uma única tabela não é adequado.
A maioria das técnicas de mineração de regras de associação multi-relacionais
existentes procuram adaptar as técnicas tradicionais de mineração de dados para serem
usadas para descoberta de conhecimento em várias tabelas, em conjunto. Para isso, cada
abordagem propõe uma nova forma de relacionar as várias tabelas envolvidas no
processo de mineração. Geralmente isso requer adaptação das medidas de interesse. As
medidas suporte e confiança, apresentadas inicialmente em [Agrawal, Imielinski e
Swami 1993], são as mais utilizadas na mineração de regras de associação. Em
[Blockeel e Sebag 2003], [Deshape e Raedt 1997], [Džeroski 2003] foram apresentados
trabalhos onde o suporte foi contabilizado de uma maneira diferente da tradicional para
solucionar o problema de relacionar dados de diferentes predicados. Esses trabalhos
mostram que os cálculos das medidas de interesse, da maneira como foram originalmente
propostos, não atendem adequadamente a todos os casos de mineração, necessitando ser
adaptados em muitos casos, de acordo com o tipo do problema envolvido.
Em [Ribeiro e Vieira 2004] é proposto o algoritmo Connection para mineração
de regras de associação multi-relacional, que relaciona múltiplas tabelas fato de um data
warehouse. Os parâmetros de suporte e confiança foram adaptados para considerar os
dados de múltiplas tabelas fato e foi introduzida uma nova medida de interesse chamada
peso. Em [Pizzi, Ribeiro e Vieira 2005] são relatados os resultados obtidos com a
aplicação do algoritmo Connection no conjunto de dados de exames laboratoriais de
pacientes com hepatites B e C, do hospital de Chiba, no Japão. O algoritmo
ConnectionBlock [Garcia 2008], utilizado no experimento apresentado neste artigo, foi
desenvolvido com base no algoritmo Connection, no qual foi adotada uma nova
abordagem mais simples e mais significativa para o cálculo das medidas de interesse
suporte e confiança, eliminando a necessidade da medida peso.
Há trabalhos que tratam a descoberta de regras de associação multi-relacional
que se baseiam em programação lógica indutiva, tendo como principais representativos
os algoritmos WARMR [Dehaspe, Toivonen, 2001] e FARMER [Nijssen e Kok, 2003].
Uma outra abordagem, na qual este trabalho se insere, analisa os dados diretamente nas
diversas tabelas do banco de dados. Os trabalhos que se enquadram nessa última
categoria, em sua maioria, procuram regras de associação entre tabelas que se encontram
relacionadas entre si através de um atributo chave (chave primária/chave estrangeira),
como se verifica nas abordagens apresentadas em [Clare, Williams e Lester, 2004],
[Guo, Bian e Li, 2007], [Seid e Mehrotra, 2004] e [Ng, Fu e Wang 2002]. Esses
trabalhos tratam tabelas que estejam relacionadas por meio de relacionamentos um para
muitos. O algoritmo ConnectionBlock trata os casos de tabelas que possuem pelo menos
um atributo em comum, sendo que esse atributo não representa uma chave primária ou
estrangeira da tabela.
O algoritmo ConnectionBlock endereça o problema de encontrar regras de
associação entre tabelas que não são explicitamente relacionadas, mas que têm
influência entre si devido à semântica entre os dados envolvidos, isto é, elas são
semanticamente relacionadas, no sentido que a informação em uma ou mais tabelas
pode afetar a informação em outras tabelas. Por exemplo, pode-se encontrar esse tipo de
relacionamento semântico entre informações de cartão de crédito e empréstimo de contas
bancárias e entre conceitos de atividades e de provas de estudantes, em um banco de dados
acadêmico.
A exemplo do algoritmo Connection, o ConnectionBlock foi desenvolvido com
base no algoritmo FP-Growth [Han, Pei e Yin 2000]. Para lidar com os dados das várias
tabelas em conjunto o algoritmo agrupa esses dados em blocos e calcula o suporte e
confiança dos blocos. O algoritmo ConnectionBlock usa uma estrutura chamada MFPtree que é uma extensão da FP-tree usada pelo FP-Growth. Cada nó da MFP-tree
corresponde a um item freqüente e cada ramo corresponde a um itemset encontrado em
uma ou mais transações dos blocos de uma tabela.
Para que um algoritmo de mineração de dados apresente resultados expressivos
quando aplicados em um conjunto de dados, é necessário que esses dados passem por
uma fase de pré-processamento para que sejam adequadamente preparados. Existem
alguns recursos para ajudar a melhorar a qualidade dos dados e, consequentemente, os
padrões minerados. Entre as técnicas de pré-processamento dos dados estão [Han e
Kamber 2006]: a limpeza dos dados para remover ruídos e corrigir inconsistências; a
integração dos dados que reune dados de múltiplas fontes em um único repositório;
transformação de dados tais como normalização, redução dos dados por meio de
agregações e eliminação de características redundantes. Nessa fase de pré-processamento é
interessante analisar as características dos dados. Um dos recursos amplamente utilizado
para analisar a distribuição dos dados e auxiliar a agrupar dados numéricos em faixas de
valores é o histograma. Um histograma de frequência é um método gráfico para sumarizar a
distribuição de um determinado atributo, particionando os dados em subconjuntos disjuntos.
Este artigo apresenta um caso de aplicação de mineração de regras de associação
multirelacional usando o algoritmo ConnectionBlock, em uma base de dados real de
uma indústria de açúcar e álcool situada na região de Piracicaba, São Paulo, referentes à
safra de cana de açúcar de 2006/2007. Essa base de dados mantém, entre suas
informações, aquelas referentes às etapas de reforma, plantio, trato e colheita de
diversas variedades de cana de açúcar, bem como da produção de açúcar correspondente
a determinada colheita. Essas etapas envolvem informações relevantes para a análise
visando encontrar possíveis padrões entre as etapas de cultivo da cana de açúcar e a
conseqüente produção de açúcar e álcool e constituem uma situação ideal para a
mineração utilizando o algoritmo ConnectionBlock. São descritas as transformações
realizadas nos dados, na fase de pré-processamento, e os resultados obtidos com o
algoritmo. Os experimentos com essa base de dados revelaram padrões interessantes e
úteis, não viabilizados usando outros algoritmos existentes.
O artigo está organizado como segue: na seção 2 são descritas as etapas do processo
de produção de cana de açúcar; na seção 3 são apresentados os principais aspectos tratados
na fase de preparação de dados, relatando como os dados foram preparados para melhor
expressividade das regras geradas; na seção 4 são apresentados os conceitos sobre mineração
de dados multirelacional adotados pelo algoritmo ConnectionBlock; na seção 5 são
discutidos os padrões obtidos pelo algoritmo; na seção 6 são apresentadas as conclusões.
2. Compreensão do problema
O processo de produção de cana de açúcar comumente é dividido em 4 etapas básicas,
que são: reforma, plantio, trato e colheita, conforme mostrado na figura 1. Na etapa de
reforma são feitas as operações para tirar a cultura que está plantada no local; na de
plantio são feitas as operações para o plantio da cana de açúcar; na etapa de trato são
feitas as operações para tratar a área para dar melhores condições de crescimento para a
cana de açúcar e geralmente é dividida em trato de cana planta que é o trato feito após o
plantio e trato de cana soca, que é o trato feito após a colheita; e a etapa de colheita em
que são feitas as operações de colheita de cana e entrega à usina. Geralmente são feitas 5
colheitas em 1 ciclo de plantio. Na figura 1 é representado um ciclo de 3 cortes na linha
do tempo.
As discussões apresentadas neste artigo concentram-se nos processos de trato e
colheita da cana de açúcar.
Reforma
Tempo
Plantio
Trato Planta
1º corte
Colheita
Trato Soca
12 meses ou
18 meses após
o plantio
2º corte
Colheita
Trato Soca
12 meses após
o corte anterior
3º corte
Colheita
12 meses após
o corte anterior
Figura 1: ciclo da cultura de cana de açúcar.
Na etapa de trato são aplicados os insumos como adubos, herbicida, inseticida,
maturadores, etc. A adubação é realizada com base em uma recomendação agronômica
feita por um engenheiro agrônomo, com base em análises de solo do local. Essa
recomendação indica a necessidade de reposição de nitrogênio (N), fósforo (P) e
potássio (K) no solo para que a cana possa se desenvolver e ser viável economicamente.
O engenheiro agrônomo indica uma fórmula de adubo (N-P-K) para cada local e uma
dose recomendada dessa fórmula por hectare. Por exemplo: No local X deve-se usar o
adubo 10-10-30 na dose de 1.5 toneladas por hectare. Essa indicação é considerada ideal
de acordo com as análises de solo que o engenheiro tem em mãos e de acordo com os
nutrientes que a cultura de cana de açúcar necessita.
A etapa de colheita é executada em 3 ou 4 dias em média. A colheita é planejada
de acordo com algumas restrições, como: capacidade de moagem diária da indústria,
capacidade de corte, carregamento e transporte da empresa e melhor época de colheita
de cada variedade de cana. Para a usina, a época de colheita é a época de produção de
açúcar e álcool, considerando as restrições acima, e varia de acordo com cada região; no
centro oeste essa época vai de abril a dezembro.
Na etapa da colheita existem diversas medidas importantes para o gerenciamento
da área agrícola, entre elas destacam-se a produção de cana, a qualidade da cana (que é a
medida do teor de sacarose da cana) e a produtividade da cana que é a produção dividida
pela área. No centro oeste a medida de área mais comum é o hectare que equivale a
10.000 m2; a produtividade é expressa por TCH (Tonelada de cana por hectare).
O ATR - açúcar total recuperável - é uma das principais medidas de qualidade da
cana de açúcar. É o resultado de uma análise de laboratório que mede a qualidade da cana. O
ATR representa quantos quilos de açúcar é possível extrair de uma tonelada de cana e é
calculado por meio da fórmula: 9,26288 x PC + 8,8 x AR, onde os valores de PC e AR são
fórmulas que envolvem valores obtidos através de análises de laboratório da cana de açúcar.
As normas dessas análises são determinadas pelo CONSECANA-SP - Conselho dos
Produtores de Cana-de-Açúcar, Açúcar e Álcool do Estado de São Paulo. Dessas análises
são extraídas várias medidas como BRIX, POL, PC, FIBRA, AR, ATR, etc.. [Consecana
2004].
Cada variedade de cana tem sua curva de maturação padrão para o primeiro corte
e para os demais e, de acordo com essa curva, a variedade de cana pode ser precoce,
normal ou tardia. Na figura 2 é apresentada a curva de maturação da variedade de cana
RB83-5486, para o primeiro corte de 12 meses.
ATR
Com base na curva de maturação e na produtividade é feito o planejamento de
colheita para todos os talhões, considerando as restrições de capacidade diária de
moagem da usina, capacidade das frentes de corte e transporte, área com aplicação de
maturador, distância, período de colheita, e demais restrições consideradas no
planejamento.
Mês
Figura 2: Curva de maturação da variedade RB83-5486
Diversos fatores influenciam na qualidade da cana. Alguns desses fatores estão
relacionados com as características das variedades, época de colheita, idade da cana, etc.
A principio a aplicação de insumos e fertilizantes não afeta a qualidade da cana e sim a
quantidade de cana produzida. Por isso é comum empresas trabalharem com a curva de
maturação da variedade para tirar o melhor rendimento das variedades plantadas.
3. Preparação dos dados
Entre as diversas informações armazenadas no banco de dados da empresa encontram-se
as referentes às aplicações de insumos e colheitas de cada variedade de cana de açúcar e
os locais de plantio, bem como a curva de maturação de cada variedade. Os dados
relativos a essas informações foram considerados como foco de análise para mineração
de dados. A figura 3 mostra a modelagem dessa parte do banco de dados, contemplando
somente as informações consideradas de interesse para a análise. Para o experimento
aqui relatado definiu-se como meta de análise melhorar a produção de açúcar.
Os dados foram extraídos de um banco de dados Oracle e exportados para 3
planilhas eletrônicas. A figura 4 apresenta uma amostra da tabela Colheita, que possui
os atributos local, tipo de corte, data, toneladas de cana produzida, idade da cana,
quantidade de impureza na cana, ATR, etc. Dessa tabela foram considerados mais
importantes, do ponto de vista do negócio, os atributos tipo de corte e ATR.
Figura 3: Base de dados -produção de cana e aplicação de insumos
Figura 4: Dados de Colheita
A seleção e transformação dos dados, com base na meta de análise definida,
resultou no banco de dados cujo modelo é apresentado na figura 5.
Figura 5: Esquema do banco de dados preparado para a mineração
A tabela Cadastro de Local contém as características do local de produção.
Foram considerados os atributos que pudessem influenciar o resultado da mineração:
Variedade e Ambiente. Variedade representa a variedade de cana que está plantada;
Ambiente é uma classificação feita no talhão levando em consideração as condições para
produção de cana; essa classificação varia entre A e F.
A tabela Aplicação de Insumo contém dados referentes ao assunto de manejo de
insumos realizados no local. Nesse estudo foram considerados os apontamentos de
insumos realizados no período entre o plantio ou corte de cana da safra anterior até o
corte de cana da safra da colheita analisada (safra de 2006/2007). Foi considerado
apenas o atributo Insumo. As quantidades de insumo aplicadas não foram consideradas,
uma vez que elas seguiram as dosagens recomendadas. Todos os registros da tabela
original foram considerados.
Os dados da tabela Colheita original foram agrupados por local e mês de modo a
ficar no mesmo nível de granularidade dos dados da tabela de Curva de Maturação onde
encontra-se o atributo ATR Estimado. Todos os registros dessas tabelas foram
considerados. Os dados dessas duas tabelas foram transformados e geraram a tabela
Colheita da figura 5. Essa tabela contém dados referentes à produção de cana por local,
sumarizados por mês. Foram considerados os atributos:Tipo de Corte: representa como
foi cortada a cana no momento da colheita; Mês: mês em que a cana foi colhida;
FaixaATR: É uma discretização de Diferença%ATR, conforme critério relatado a seguir.
O atributo Diferença%ATR representa a diferença (mensal), em percentual,
entre o ATR realizado (da tabela Curva de Maturação) e o estimado (da tabela
Colheita original):
Diferença%ATR = ((ATR Realizado – ATR Estimado) / ATR Realizado) * 100.
Optou-se por utilizar essa medida para análise do ATR, ao invés de
simplesmente criar faixas de valores para o ATR Realizado, por representar um
indicador importante que mostra quanto a produção real de açúcar, em porcentagem,
diferenciou da quantidade que foi planejada com base na curva de maturação da
variedade de cana analisada.
A distribuição da freqüência de ocorrência dos valores do atributo
Diferença%ATR é semelhante a uma curva normal, conforme mostra o histograma da
figura 6. Com base nessa distribuição criou-se o atributo FaixaATR, com os valores:
“Perda Alta” para as tuplas cujo valor de Diferença%ATR é menor ou igual a -10;
“Perda” para as tuplas cujo valor de Diferença%ATR é maior que -10 e menor ou igual
a -2 e assim sucessivamente, conforme apresentado na figura 7. Essas faixas foram
eleitas por melhor representarem a distribuição dos dados.
Histograma da diferença de ATR entre planejado e realizado
140
Perda Alta
120
Perda
Estável Ganho
Ganho Alto
Frequencia
100
80
60
40
20
30%
26%
23%
20%
17%
14%
11%
8%
5%
2%
-1%
-4%
-7%
-10%
-13%
-16%
-19%
-22%
-26%
-37%
-45%
0
% Atr (Plan/Real)
Diferença de ATR
Figura 6: Histograma da diferença entre o ATR real e estimado
Valor Inicial
-999
-10
-2
2
8
Valor Final
-10
-2
2
8
999
Faixa ATR
Perda Alta
Perda
Estável
Ganho
Ganho Alto
Figura 7: Faixa de valores da diferença de ATR
Com base nesses dados um gestor pode desejar, por exemplo, encontrar padrões
entre os insumos aplicados (adubos, fertilizantes, etc.) e o percentual de ganho ou perda
de ATR em relação ao ATR estimado de acordo com a variedade e a época de colheita.
4. Mineração de dados multirelacional baseada em blocos
Nas discussões apresentadas nesta seção são utilizados os dados das tabelas da figura 8,
que representam uma pequena população dos dados considerados no experimento. O
objetivo do experimento foi analisar conjuntamente essas 3 tabelas para investigar
possíveis influências dos insumos, aplicados nas variedades de cana de açúcar, sobre a
produção de açúcar resultante.
Note-se que as tabelas Aplicação de Insumos e Colheita tratam assuntos distintos que não
estão relacionados entre si, mas possuem um vínculo semântico, sendo de interesse a análise
conjunta. Esse vínculo se deve ao fato de se ter, para um mesmo local (um talhão), a
aplicação de um conjunto de insumos que colaboraram para a produção de uma certa
quantidade de açúcar. Essa é uma situação típica para utilização do algoritmo
ConnectionBlock para encontrar regras de associação multi-relacional.
ID
1
2
3
4
5
6
7
8
9
10
11
ID
1
2
3
4
5
6
6
7
7
8
9
9
10
10
Aplicação de Insumos
INSUMO
Potássio
Nitrogênio (N)
Potássio
Potássio
Potássio
Potássio
Fert. 10-25-25
Potássio
Fert. 10-25-25
Torta de Filtro
Orifer 5
Vinhaça
Fert. 10-25-25
Vinhaça
Cadastro de
VARIEDADE
RB85-5113
RB86-7515
RB86-7515
RB86-7515
SP80-1842
RB85-5113
RB85-5113
RB72-454
SP80-1842
RB72-454
SP80-3280
ID
1
2
3
5
6
6
7
7
7
9
11
Local
AMBIENTE
Ambiente - A
Ambiente - A
Ambiente - F
Ambiente - D
Ambiente - B
Ambiente - B
Ambiente - B
Ambiente - B
Ambiente - E
Ambiente - C
Ambiente - C
Colheita
TIPO DE CORTE
Corte Mec. Picada - CRUA
Corte Manual - CRUA
Corte Manual - CRUA
Corte Mec. Picada - QUEIMADA
Corte Manual - CRUA
Corte Mec. Picada - QUEIMADA
Corte Manual - CRUA
Corte Mec. Picada - CRUA
Corte Mec. Picada - QUEIMADA
Corte Manual - CRUA
Corte Manual - CRUA
MES
nov/06
mai/06
jun/06
jul/06
jul/06
jun/06
jun/06
jul/06
ago/06
abr/06
ago/06
FAIXA
Ganho Alto
Estavel
Perda
Ganho
Ganho
Estavel
Perda
Perda_Alta
Perda
Perda
Ganho
∆ %ATR
11%
-1%
-3%
3%
4%
0%
-8%
-11%
-4%
-4%
5%
Figura 8: dados de exemplo
O ConectionBlock requer que as tabelas possuam pelo menos um atributo em
comum. As características desse algoritmo são apresentadas a seguir.
Considere Id um conjunto de atributos que são comuns em todas as tabelas.
Cada valor distinto de Id identifica um conjunto de transações chamado bloco. Um
bloco contém todas as informações oriundas das diversas tabelas e que são de um valor
específico do atributo comum. Um bloco é a unidade de análise do processo de
mineração multi-relacional do ConnectionBlock.
Para auxiliar nas discussões a seguir considere a figura 9, que mostra, para cada
talhão, todas as suas informações que pertencem às 3 tabelas (na figura 8, essas
informações estão destacadas em linhas com cores alternadas). Cada célula da figura 9
representa um bloco. O valor do atributo comum é o valor de ID_Talhão (representado por
ID na figura 8). Por exemplo, o bloco com ID_Talhão igual a 7 tem as informações:
Cadastro de Local {< 7, RB85-5113, Ambiente-B>}, Aplicação de Insumos { < 7, Potássio>, <7,
Fert. 10-25-25>} e Colheita { < 7, Corte Manual–CRUA, jun/06, Perda, -8%>, <7, Corte Mec.
Picada–CRUA, jul/06, Perda Alta, -11%>, <7, Corte Mec. Picada – QUEIMADA, ago/06, Perda, 4%>}.
Note que na figura 9 existem blocos que não possuem correlação em todas as
tabelas; esses blocos são importantes na contagem do suporte e definição de regra forte.
1
2
Ambiente - A
}
{ RB85-5113,
}
{ Potássio
{ Corte Mec. Picada Crua, nov/06, Ganho Alto, 11% }
{ RB86-7515,
{ Nitrogenio (N)
{ Corte Manual Crua,
4
{ RB86-7515,
{ Potássio
5
{ SP80-1842,
{ Potássio
{ Corte Mec. Picada Quei,
Ambiente - D
}
}
3
Ambiente - A
}
}
mai/06, Estavel,
-1% }
Ambiente - B
}
}
jul/06,
Ganho,
3% }
{ RB86-7515,
{ Potássio
{ Corte Manual - Crua,
6
{ RB85-5113,
{ Potássio,
Ambiente - F
}
jun/06, Perda, -3% }
Ambiente - B
Vinhaça
{ Corte Manual Crua,
}
}
}
jul/06, Ganho, 4%
Corte Mec. Picada Quei, jun/06, Estavel, 0% }
7
{ RB85-5113,
{ Potássio,
Ambiente - B
}
Fert. 10-25-25
Corte Mec. Picada Crua, jul/06,
}
}
9
{ SP80-1842,
{ Orifer 5,
Vinhaça
{ Corte Manual Crua,
-8%
Ambiente - E
}
}
abr/06, Perda, -4% }
Perda Alta, -11%
Corte Mec. Picada Quei, ago/06, Perda,
Vinhaça
Ambiente - B
}
{ Corte Manual - Crua, jun/06, Perda,
10
{ RB72-454,
{ Fert. 10-25-25,
8
{ RB72-454,
{ Torta de Filtro
Ambiente - C
-4% }
}
11
{ SP80-3280,
{ Corte Manual Crua,
Ambiente - C
ago/06, Ganho,
}
5% }
}
Figura 9: Mapa de blocos
A seguir são definidos formalmente os conceitos utilizados pelo algoritmo
ConnectionBlock, onde: R= {R1, R2, ..., Rm} é um conjunto de relações que possuem
pelo menos um atributo em comum e Ri é da forma: Ri(ID, Ai1, ..., Aini), para i=1,m; ID
é um conjunto de atributos comuns às m relações.
Definição 1: Uma regra de associação multi-relacional é uma expressão da forma X→
→Y,
onde X e Y são itemsets, tal que X ∈ Ri e Y ∈ Rj, onde Ri e Rj são relações distintas.
Definição 2: Um bloco1 é o conjunto de tuplas T={t1, t2, ..., ts} de R, tal que para
quaisquer tuplas ti, tj ∈ T tem-se ti(ID)=tj(ID), para 1≤i,j≤ s.
Definição 3: O suporteBL (suporte multi-relacional baseado em blocos) de uma regra
de associação multi-relacional X→
→Y é a razão entre o número de blocos em que X e Y
ocorrem juntos e o número total de blocos, ou seja,
SuporteBL = Blocos_X∪Y/Total_de_Blocos.
Definição 4: A confiançaBL (confiança multi-relacional baseada em blocos) de uma
regra de associação multi-relacional X→
→Y é a razão entre o número de blocos em que X
e Y ocorrem juntos e o número de blocos em que X ocorre:
1
O algoritmo Connection também uso o termo bloco, porém trata-se de um conceito diferente do usado
pelo ConnectionBlock.
ConfiaçaBL =Blocos_X∪Y/Blocos_de_X.
Definição 5: Se uma regra de associação multi-relacional satisfaz os valores mínimos
estabelecidos de suporteBL e confiançaBL, então essa regra é uma regra forte.
Para exemplificar o cálculo de suporteBL, considere a regra a seguir, gerada a
partir dos dados da figura 8:
Ambiente-B e Potássio → Ganho.
O valor do suporteBL para essa regra é 18% (2/11), pois os blocos 5 e 6 possuem
“Ambiente–B, Potássio e Ganho” . O valor de confiançaBL é calculada considerando os
blocos que contém “Ambiente–B, Potássio e Ganho” (blocos 5 e 6) e os blocos que
contém Ambiente–B e Potássio (blocos 5,6,7 e 8); portanto a confiança da regra é 50%
(2/4).
5. Resultados e Discussões
Nesta sessão são apresentados os resultados do algoritmo ConnectionBlock aplicado na
base de dados descrita na seção 3.
Os experimentos foram realizados em um notebook Acer com processador AMD
Turion 64x2 de 1.6 Gigahertz com 512 megabytes de memória RAM e sistema
operacional Windows XP. O algoritmo foi escrito na linguagem de programação Java
com o ambiente de desenvolvimento Eclipse.
Conforme já citado, os dados extraídos são referentes à safra de cana de açúcar
de 2006 / 2007. A relação Cadastro de Local possui 1637 tuplas, Aplicação de insumos
3116 tuplas e Colheita 1935 tuplas.
No contexto da base de dados apresentada, as regras mais expressivas geradas
são as que possuem no lado direito o atributo FaixaATR. Esse atributo indica se houve
algum ganho ou perda de ATR em relação ao planejamento. As discussões e
observações a seguir são centradas nesse tipo de regra.
Uma das regras geradas pelo algoritmo foi:
(SP80-1816) (Potássio) → (Ganho Alto)
s=0,017433414; c=0,9,
significando:
“Os locais que possuem a variedade de cana “SP80-1816” e em que foi aplicado
o insumo “Potássio” apresentaram “Ganho Alto” de ATR maior que 8% em relação ao
planejamento, com um suporteBL de 1,7% e confiançaBL de 90%”.
Outra regra extraída foi:
(SP80-3280) (Vinhaça) → (Perda Alta)s=0,008232445;c=0,8947368,
significando:
“Os locais que possuem a variedade de cana “SP80-3280” e em que foi aplicado
o insumo “Vinhaça” apresentaram “Perda Alta” de ATR menor que 10% em relação ao
planejamento, com um suporteBL de 0,8% e confiançaBL de 89,5%.
Um talhão tem área média de 8 hectares e produz cerca de 640 toneladas de cana
de açúcar, o que corresponde a cerca de 90.000 kg de açúcar por colheita. Existem 2065
talhões, logo a primeira regra envolve 36 talhões (1,7% de 2065) e a segunda envolve 17
talhões (0,8% de 2065). A perda de produção de açúcar acusada pelo experimento
corresponde a uma média de 150.000 kg (soma dos 17 talhões e por volta de 8.800 kg por
talhão). No caso do ganho, a quantidade de açúcar envolvida é de 250.000 Kg (soma dos
36 talhões e cerca de 7.000kg por talhão).
Essas duas regras são interessantes, pois apresentam elementos para se buscar
uma possível melhora na qualidade da cana de açúcar produzida, aumentando com isso
seu ATR. As duas regras mostram que a combinação de certo tipo de variedade de cana
plantada e certo tipo de insumo pode levar a um ganho ou a uma perda do ATR. O que
chama atenção nessas duas regras são os insumos envolvidos. A vinhaça é um
subproduto industrial da fabricação do açúcar e ela é justamente rica em potássio.
Apesar de se tratarem de variedades diferentes de cana, as duas regras mostram duas
situações opostas extremas (ganho alto e perda alta). O que pode estar causando essa
diferença entre perda e ganho é a característica de aplicação da vinhaça; isto é, a
vinhaça, por ser produzida na indústria da usina (não possui custos de fabricação) é
sempre aplicada nos mesmos locais, o que pode estar gerando um estresse e com isso
diminuindo a produção de açúcar dessas variedades. Ou seja, estima-se que existe um
limite na quantidade de potássio aplicada na cana que leva a um ganho na produção de
açúcar e que, se esse limite for excedido, a cana passa a apresentar um decréscimo de
produção de açúcar. A vinhaça é sempre aplicada nos mesmos locais, os mais próximos
da usina, devido ao custo de seu transporte.
Uma conclusão que se pode chegar é que se a aplicação da vinhaça está causando
perda de ATR, isto é, a cana de açúcar com aplicação de vinhaça da variedade de cana
SP80-3280 está produzindo menos açúcar, então é mais lucrativo descartar a vinhaça do
que aplicá-la no canavial. Obviamente estas questões devem ser analisadas mais
profundamente e por engenheiros agrônomos ou pesquisadores da cultura de cana de
açúcar. A importância da mineração multi-relacional foi evidenciar um fato que está
ocorrendo e que era desapercebido pelos gestores.
Com relação ao desempenho do algoritmo, na figura 10 é apresentado um
resumo dos tempos de processamento do ConnectionBlock na base de dados
considerada, com diferentes valores para o suporte mínimo. Nota-se que o tempo de
execução é inversamente proporcional à quantidade de regras geradas.
ConnectionBlock
Suporte Tempo (ms) Qtde Regras Tempo/Regra
7,00%
844
3
281,33
5,00%
1.203
18
66,83
2,00%
5.141
183
28,09
1,00%
10.593
933
11,35
0,50%
21.672
3.354
6,46
0,20%
47.687
11.649
4,09
0,10%
76.922
21.939
3,51
0,05%
116.671
38.844
3,00
Figura 10: Tempo de execução do ConnectionBlock
O algoritmo ConnectionBlock tem complexidade linear. Comparado ao FPGrowth que faz 2 acessos na tabela analisada, o ConnectionBlock realiza um total de 3
acessos em cada tabela, 1 acesso para a determinação dos blocos e mais 2 acessos para
construção da MFP-Tree. A complexidade do algoritmo, para a fase de determinação
dos itemsets frequentes, é O(3t), onde t=Σni, i∈[1,m], sendo m o número de tabelas
envolvidas no processo de mineração e ni o tamanho da tabela Ri. Essa comparação com
o FP-Growth tem o objetivo somente de mostrar a viabilidade de utilização do
algoritmo. Não é do nosso conhecimento a existência de outro algoritmo que lide com
tabelas que estejam relacionadas semanticamente, da forma como as tabelas analisadas
pelo ConnectionBlock, daí não ter sido comparado o desempenho do algoritmo com
outros de mineração de regras de associação multi-relacional.
6. Conclusões
Este artigo apresentou um estudo de caso de aplicação de mineração de regras de
associação multirelacional, usando o algoritmo ConnectionBlock, em uma base de
dados real de uma indústria de açúcar e álcool. Foram descritas as transformações
realizadas nos dados para prepará-los para a mineração e os resultados obtidos com o
algoritmo.
Os experimentos mostram a importância da mineração multi-relacional para
encontrar padrões interessantes, diferentes daqueles viabilizados usando algoritmos
tradicionais de mineração de dados.
Considerando as regras discutidas na seção 5 nota-se que, apesar de terem sido
seguidas as recomendações de aplicação de insumos para conseguir o melhor
rendimento das variedades plantadas e que, a principio, a aplicação de insumos não
afeta a qualidade da cana produzida, os resultados da mineração de dados indicam
evidências de que, na prática, isso pode não estar ocorrendo em alguns casos. Isso
somente foi possível detectar usando a mineração multi-relacional com a abordagem do
algoritmo ConnectionBlock.
Considerando a abrangência do banco de dados estudado, novas análises podem
ser realizadas envolvendo outros relacionamentos semânticos, como, por exemplo,
envolvendo a época da colheita, a idade da cana, a precipitação pluviométrica (chuva),
dados sobre o clima, infestação de pragas, infestação de plantas daninhas, época de
plantio, tipo de plantio, estágio da cana, tipo de solo, retorno financeiro do local, entre
outros.
Referências Bibliográficas
Agrawal, R, Imielinski, T. Swami, A. Mining association rules between sets of items in
large databases. In: Proc. of the ACM SIGMOD Int'l Conf. on Management of Data,
1993. p. 207-216.
Blockeel, H, Sebag, M. Scalability and efficiency in multi-relational data mining. ACM
SIGKDD Explorations Newsletter, v. 5, n. 1. 2003. p. 17-30.
Clare, A. Williams, H.E., Lester, N. Scalable multi-relational association mining. In:
Proc. Of the Fourth IEEE International Conference on Data Minig (ICDM’04), 2004.
p. 355-358.
Consecana. Manual de Instruções Consecana-SP. São Paulo, 2004. Disponível em:
<http://www.unica.com.br/pages/consecana.asp>. Acesso em: 03 Janeiro 2008.
Dehaspe, L, De Raedt, L. Mining association rules in multiple relations. In: Proc. of the
7th International Workshop on Inductive Logic Programming, 1997. p. 125-132.
Dehaspe, L., Toivonen, H. Discovery of relational association rules. In Džeroski, S. and
Lavrac, N., ed. Relational data Mining. Springer-Verlag, 2001. p. 189-212.
Džeroski, S. O. Multi-relational data mining: an introduction. ACM SIGKDD
Explorations Newsletter, v. 5, n. 1, 2003. p. 1 – 16.
Garcia, E. Mineração de regras de associação multi-relacional quantitativa. 96 f.
Dissertação (Mestrado em Ciência da Computação) – Faculdade de Ciências Exatas e
da Natureza, Universidade Metodista de Piracicaba, Piracicaba, SP, 2008.
Guo, J., Bian, W., Li, J. Multi-relational Association Rule Mining with Guidance of
User. In: Proc. of the Fourth International Conference on Fuzzy Systems and
Knowledge Discovery (FSKD 2007), 2007.
Han, J., Pei, J.; Yin, Y. Mining frequent patterns without candidate generation. In Proc.
of the ACM SIGMOD Intl Conf. on Management of Data, 2000. p. 1-12.
Han, J., Kamber, M. Data Mining – Concepts and Techniques. Second edition. New
York: Morgan Kaufmann, 2006.
Jensen, V, Soparkar, N. Frequent itemset counting across multiple tables. In: Proc. of
the 4th Pacific-Asia Conference on Knowledge Discovery and Data Mining, 2000. p.
49-61.
Ng, E, Fu, A, Wang, K. Mining associationrules from stars. In: Proc. of the IEEE
International Conference on Data Mining (ICDM'02), 2002. p. 322-329.
Nijssen, S., Kok, J. Efficient frequent query discovery in FARMER. In: Proc. of the
PAKDD, 2003. p. 350-362.
Pizzi, L. C.; Ribeiro, M. X.; Vieira M. T. P. Analysis of hepatitis dataset using multirelational association rules. In: Proc. of the ECML/PKDD, Discovery Challenge,
2005.p.161-167.
Ribeiro, M. X., Vieira, M. T. P. A new approach for mining association rules in data
warehouses. In: Proc. of the 6th International Conference On Flexible Query
Answering Systems, 2004. p 98-110.
Seid, D.Y., Mehrotra, S. Efficient relashionship pattern mining using multi-relational
iceberg-cubes. In: Proc. Of the Fourth IEEE International Conference on Data Minig
(ICDM’04), 2004.