7.3 Kompromissoppgjørets virkning overfor
7.3.3 Spesialvilkår
A mineração de dados por regra de associação permite encontrar padrões de relacionamento entre atributos ou itens de dados que ocorram com uma determinada frequência. O objetivo do algoritmo é descobrir regras para quantificar o relacionamento entre dois os mais atributos ou itens (LAROSE, 2005).
Assim, dado um conjunto de itens I = {i1, i2,...in} e um conjunto de transações T
= {t1, t2, ...,tn}, no qual cada transação contém um conjunto de itens, existe a implicação
da forma A=>B que descreve uma correlação entre os eventos A e B. Assim, tem-se uma regra no formato: se conjunto A, então conjunto B. No qual A é denominado o antecedente ou a premissa e B o consequente ou conclusão, sendo ambos subconjuntos de I e mutuamente excludentes.
Para avaliar a importância de uma regra, normalmente, utilizam-se os indicadores: suporte e confiança.
O suporte é a proporção de transações em que A e B ocorrem em relação ao total de transações em T (ver Fórmula 1). Assim, tal indicador representa quanto a regra cobre do conjunto de dados analisados. Quanto maior for o valor do suporte, maior será a representatividade daquela regra no conjunto de dados.
(1)
Por outro lado, a confiança é a frequência com que A e B ocorrem, entre as instâncias que contêm A (ver Fórmula 2). Este indicador determina o grau de precisão de uma regra. Assim, quanto maior for o valor, maior será a expectativa de encontrar itens que obedecem à regra A=>B.
(2)
Uma regra é considerada forte quando a combinação dos indicadores atende a valores mínimos especificados pelo usuário. Podem-se exigir valores altos destes indicadores quando, por exemplo, da análise de quais itens de supermercado são comprados em conjunto. Neste caso, quanto maior for o suporte e a confiança, ou seja, itens com grande frequência de combinação, melhor será o resultado. Assim, por exemplo, dado o conjunto de transações de possíveis itens comprados em conjunto, Figura 8:
Figura 8 - Exemplo 1
t1: Feijão, Arroz, Leite
t2: Feijão, Queijo
t3: Queijo, Detergente
t4: Feijão, Arroz, Queijo
t5: Feijão, Arroz, Tomate, Queijo, Leite
t6: Arroz, Tomate, Leite
O usuário define como suporte mínimo de 30% e a confiança mínima de 50%, para que a regra seja considerada forte. Assim, dada a regra de associação Arroz, Feijão => Queijo (Suporte = 33,33%, Confiança=66,67%), é considerada válida por ter um suporte e uma confiança acima dos mínimos definidos pelo usuário.
Contudo, conforme destacado por Larose (2005), na detecção de transações fraudulentas ou relacionadas com terrorismo, quanto menor for o suporte, melhor será o resultado. Normalmente, reduze-se o nível de suporte para menos de 1%, uma vez que, comparativamente, transações fraudulentas ou relacionadas com terrorismo são minoria em relação às demais. Assim, ao contrário do exemplo do mercado, neste tipo de objetivo de mineração busca-se identificar as exceções ao padrão de comportamento no conjunto de transações. Selvi e Tamilarasi (2011) destacam que tais tipos de associações
Número de transações contendo A e B Suporte =
Número total de transações
Número de transações contendo A e B Confiança =
são denominadas interesting rare association8 e são caracterizadas por ter suportes baixos e confianças altas.
Para a identificação de associações raras, normalmente utilizam-se múltiplos suportes mínimos, uma vez que, um único suporte mínimo para toda a base, implica em assumir que todos os itens de dados têm natureza e frequência semelhantes. No entanto, conforme destacado por Liu, Hsu e Ma (1999), raramente é o caso em bases de dados, em que, normalmente, alguns itens aparecem com mais frequência que outros. Para encontrar as regras que envolvem itens tanto frequentes quanto raros, o suporte mínimo deve ser definido com valores muito baixos. Isto pode causar explosão combinatória, pois existirão mais itens freqüentes, que podem ocasionar maior número de possibilidade de associações. Para solucionar este problema, Liu, Hsu e Ma (1999) utilizaram múltiplos suportes mínimos para refletir a natureza e as diferentes frequências de itens. A técnica mostrou-se efetiva para detecção de associações raras.
No trabalho de Selvi e Tamilarasi (2011), combinou-se a utilização de múltiplos suportes com uma confiança de 100%. Com tal configuração foi possível detectar as associações raras, como também melhorar a performance computacional.
Já no estudo de Szathmary, Valtchev e Napoli (2010), estabeleceram-se não somente limites mínimos, como também máximos de suporte, conjugados com valores altos de confiança, para detectar associações raras em diagnósticos de doenças.
Também, são utilizados para analisar regras, medidas de grau de interesse como:
lift e conviction.
O lift mensura a performance do modelo ao classificar as transações (AZEVEDO; JORGE, 2007). Assim, valores iguais a 1 indicam que a ocorrência de um antecedente e um consequente foi independente, ou seja, não existe uma relação. Valores maiores que 1 denotam que existe alguma dependência positiva entre as variáveis. Valores inferiores a 1 indicam a existência de uma relação negativa entre a premissa e a conclusão. Assim, o lift é dado pela Fórmula 3.
(3)
8 Associações Raras Interessantes (tradução nossa).
Confiança Lift =
Outra medida de grau de interesse é o conviction, que determina o grau da premissa que implica na conclusão. Diferentemente do lift, este indicador é sensível à direção da regra. Assim, os valores podem variar de 0.5 até o infinito quando a confiança for igual a 1. Similar ao lift, valores iguais a 1 indicam que a premissa e a conclusão são independentes e valores maiores que 1 indicam regras interessantes (AZEVEDO; JORGE, 2007). Desta forma, o conviction é definido conforme a Fórmula 4.
(4)
Existem vários algoritmos para a extração de regras de associação. Contudo, todos seguem o princípio de geração com definição de suportes e confianças mínimas, dado um conjunto de transações. A diferença entre um método e outro advém principalmente da eficiência de processamento computacional e da quantidade de memória necessária para processar o algoritmo. Inclusive, a utilização de qualquer algoritmo deve gerar o mesmo conjunto de regras, para o mesmo suporte e confiança (LIU, 2007).
Para este estudo, fez-se a opção de utilizar o algoritmo FP-Growth, que é um aprimoramento do Apriori. Assim, foi detalhado em primeiro lugar o algoritmo Apriori e, depois, destacaram-se as diferenças entre os algoritmos que ocasionam um processamento mais otimizado pelo FP-Growth.
5.2.1 Algoritmo Apriori
No algoritmo Apriori a tarefa de mineração de regras de associação é dividida em duas fases. Na primeira etapa cria-se um conjunto de itens, denominados conjuntos itens frequentes, que são aqueles que têm suporte mínimo maior ou igual ao determinado pelo usuário. Depois, estabelece-se uma relação de regras de associação, com base no conjunto de itens frequentes, respeitando a confiança mínima estipulada (AGRAWAL'; IMIELINSKI; SWAMI, 1993).
Para estabelecer o conjunto de itens frequentes, ou seja, aquele que alcance o suporte mínimo, primeiro determina-se F1, que é a frequência de ocorrência de cada um
1 - Suporte de A Conviction =
dos itens do conjunto separadamente, ou seja, a quantidade de vezes que cada item aparece no conjunto de transações. Utilizando o exemplo da Figura 8, tem-se o conjunto de frequências dos itens.
Tabela 01 - Suporte para Candidatos C1
Candidatos (C1) Suporte Feijão 66,67% Arroz 66,67% Leite 50,00% Queijo 50,00% Detergente 16,17% Tomate 33,33%
Posteriormente, define-se F2, que são pares de itens frequentes. Nesta fase parte-
se da premissa, dado que um conjunto de itens Z não é frequente; então, a adição de outro item A ao conjunto de itens Z não tornará Z mais frequente. Esta característica reduz a quantidade de combinações que serão processadas pelo algoritmo. Assim, no exemplo seria eliminado desta fase o Detergente que não alcançou a frequência mínima de 30% na etapa anterior. Assim, tem-se o conjunto candidatos de dois itens C2 (ver
Tabela 2).
Tabela 2 - Suporte para Candidatos C2
Candidatos (C2) Suporte Feijão, Arroz 50,00% Feijão, Leite 33,33% Feijão, Queijo 50,00% Feijão, Tomate 16,67% Arroz, Leite 50,00% Arroz, Queijo 33,33% Arroz, Tomate 33,33% Tomate, Queijo 16,67% Tomate, Leite 33,33% Leite, Queijo 16,67%
Ao final, retiradas as combinações que não alcançaram suporte mínimo de 30%, tem-se que o conjunto de itens frequentes F2 = {(Feijão, Arroz), (Feijão, Leite), (Feijão,
Queijo), (Arroz, Leite), (Arroz, Tomate), (Arroz, Queijo), (Tomate, Leite)}. Para gerar o
conjunto de candidatos C3, de 3 itens, compará-se os pares de F2 que tenham um item
Tabela 3 - Suporte para Candidatos C3
Candidatos (C3) Suporte
Feijão, Arroz, Leite 33,33% Feijão, Tomate, Queijo 16,67% Feijão, Arroz, Queijo 33,33% Feijão, Arroz, Tomate 16,67% Feijão, Tomate, Leite 16,67% Arroz, Queijo, Leite 16,67% Arroz, Tomate, Leite 33,33% Arroz, Tomate, Queijo 16,67%
Desta forma, retirados aqueles itens não frequentes, o resultado de F3 = {(Feijão,
Arroz, Leite), (Feijão, Arroz, Queijo), (Arroz, Tomate, Leite)}. Esta é a última etapa
para criação de conjuntos de itens frequentes, uma vez que, caso fosse gerado F4, não
existiria nenhum conjunto de quatro itens que atenderia o suporte mínimo de 30%. Na última fase de processamento do algoritmo, criou-se as regras de associação, com base no conjunto de itens frequentes achados no item anterior, respeitando a confiança mínima de 50%. Assim, no exemplo, têm-se regras com um ou dois antecedentes, conforme Tabela 4.
Tabela 4 - Regras de Associação Geradas do Exemplo
Regra Suporte Confiança
Se Feijão, então Arroz. 3/6 = 50,00% 3/4 = 75,00%
Se Arroz, então Feijão. 3/6 = 50,00% 3/4 = 75,00%
Se Feijão, então Leite. 2/6 = 33,33% 2/4 = 50,00%
Se Leite, então Feijão. 2/6 = 33,33% 2/3 = 66,67%
Se Feijão, então Queijo. 3/6 = 50,00% 3/4 = 75,00%
Se Queijo, então Feijão. 3/6 = 50,00% 3/3 = 100,00%
Se Arroz, então Leite. 3/6 = 50,00% 3/4 = 75,00%
Se Leite, então Arroz. 3/6 = 50,00% 3/3 = 100,00%
Se Arroz, então Queijo. 2/6 = 33,33% 2/4 = 50,00%
Se Queijo, então Arroz. 2/6 = 33,33% 2/3 = 66,67%
Se Arroz, então Tomate. 2/6 = 33,33% 2/4 = 75,00%
Se Tomate, então Arroz. 2/6 = 33,33% 2/2 = 100,00%
Se Tomate, então Leite. 2/6 = 33,33% 2/2 = 100,00%
Se Leite, então Tomate. 2/6 = 33,33% 2/3 = 66,67%
Se Feijão e Arroz, então Leite. 2/6 = 33,33% 2/3 = 66,67%
Se Feijão e Leite, então Arroz. 2/6 = 33,33% 2/2 = 100,00%
Se Arroz e Leite, então Feijão. 2/6 = 33,33% 2/3 = 66,67%
Se Feijão e Arroz, então Queijo. 2/6 = 33,33% 2/3 = 66,67%
Se Feijão e Queijo, então Arroz. 2/6 = 33,33% 2/3 = 66,67%
Se Arroz e Queijo, então Feijão. 2/6 = 33,33% 2/2 = 100,00%
Se Arroz e Tomate, então Leite. 2/6 = 33,33% 2/2 = 100,00%
Se Arroz e Leite, então Tomate. 2/6 = 33,33% 2/3 = 66,67%
As regras geradas atendem os parâmetros de suporte e confiança especificados inicialmente pelo usuário. Contudo, normalmente ocorrem regras que fogem aos indicadores esperados; assim, devem ser descartadas na fase da análise dos dados.
Apesar de gerar regras com os parâmetros estabelecidos pelo usuário, o algoritmo Apriori apresenta alguns vieses de performance de processamento, quando trabalhando com suportes baixos. Nessa situação, o algoritmo gera um grande número de itens candidatos resultando em muitas varreduras pela base de dados, portanto aumentando o tempo de processamento. Assim, foram desenvolvidos algoritmos, como o FP-Growth, que criam estruturas mais compactas e melhoram o tempo de processamento das regras (HAN et al, 2004). A seguir é detalhado o funcionamento do algoritmo FP-Growth.
5.2.2 Algoritmo FP-Growth
Semelhante ao Apriori, FP-Growth faz um pré-processamento das transações para achar os itens frequentes. Todos não frequentes, isto é, com suporte inferior ao estabelecido, são descartados. Contudo, o algoritmo ordena o resultado em ordem decrescente de frequência, conforme exemplo no Quadro 1.
Quadro 1 - Exemplo 2
Tr Itens Comprados Itens Frequentes Ordenados (FList)
t1 f, a, c, d, g, i,m,p f, c, a,m, p t2 a, b, c, f, l,m,o f, c, a, b,m t3 b, f, h, j,o f, b
t4 b, c, k, s,p c, b, p t5 a, f, c, e, l, p,m,n f, c, a,m, p
Fonte: HAN et al (2004), adaptado pelo Autor.
Posteriormente, o FP-Growth utiliza o frequent-pattern tree (FP-Tree), ao invés da geração de itens candidatos, o que melhora consideravelmente a performance, pois reserva as informações numa estrutura mais compacta. Conforme Han et al (2004), a otimização é significativa, especialmente quando se utiliza nível de suporte mínimo muito baixo. Neste caso, o número de candidatos gerados aumenta consideravelmente no Apriori, o que aumenta o tempo de processamento.
O FP-Tree é construído seguindo as etapas a seguir, considerando-se o exemplo acima, que tem como nível mínimo de suporte 3 operações (Han et al, 2004):
1. A verificação da primeira transação leva à construção do primeiro ramo da árvore: (f:1), (c:1), (a:1), (m:1) e (p:1). Observe que os itens frequentes na transação são listados de acordo com a ordem na lista de itens frequentes.
2. Para a segunda transação, existem três itens em comum com a transação anterior (f, c, a). Assim, é somado 1 à contagem de cada um dos itens (f:2), (c:2), (a:2). Como existem dois itens novos, é criado um nó (b:1) subordinado a (a:1) e outro nó (m:1) subordinado a (b:1).
3. Para a terceira transação, somente (f, b) são itens frequentes, divide-se o nó (f) e é adicionado 1 à contagem; e um novo nó é criado (b:1) subordinado a (f:3).
4. Para a quarta transação, cria-se um segundo ramo da árvore, (c:1), (b:1), (p:1).
5. Para a última operação, como os itens frequentes são iguais ao da primeira transação, cada um dos itens recebe um incremento de 1: (f:4), (c:3), (a:2), (m:2) e (p:2).
A FP-Tree criada para o exemplo ficaria conforme Figura 9. Figura 9 - FP-Tree Exemplo 2
Fonte: HAN et al (2004).
Desta forma, após encontrar os itens frequentes e colocá-los na ordem decrescente, cria-se a raiz da árvore, denominada Null e seguem-se as etapas detalhadas
anteriormente. Considerando as etapas descritas acima, se uma transação tem itens semelhantes já apresentados na árvore, o item deve ser incrementado e, se apresentar nodos diferentes, estes devem ser incluídos como novos ramos na árvore.
Cada transação da base de dados é mapeada na árvore com as frequências dos itens armazenados. Assim, cada caminho da árvore pode representar múltiplas transações.
Depois de criada a árvore, são gerados os padrões frequentes por meio da mineração do FP-tree. O processo consiste em gerar a conditional pattern base 9 para cada item presente na tabela header (ver Figura 10). Assim, por exemplo, para o item “m” como sufixo (último item da sequência) existem dois caminhos: (f:4, c:3, a:3, m:2) ou (f:4, c:3, a:3, b:1, m:1). O primeiro caminho indica que existem 2 transações na base de dados que apresentaram o padrão; e, no segundo, existe apenas uma operação. Assim, os dois prefixos do item “m” formam as bases de padrões condicionais {(fca:2), (fcab:1)}. Essas bases são utilizadas para a construção das FP-tree condicionais, que catalogam os caminhos frequentes que se conectam aos nós correspondentes ao item em questão. Assim, para o item “m” seria construída uma FP-Tree condicional, gerada da mesma forma do exemplo inicial. Para “m” tem-se {(f:3, c:3, a:3)}|m, com um FP-Tree composto por 3 nós, uma vez que somente estes itens atingiram o suporte mínimo de 3 operações. Assim, para o exemplo acima tem-se FP-Tree condicional do item “m”:
Figura 10 - FP-Tree Condicional do item m
Fonte: HAN et al (2004).
Posteriormente, o algoritmo minera os padrões de forma recursiva. Como o exemplo da Figura 9, que, após achar a base condicional de “m”, repete o processo para a sequência “am” e assim sucessivamente. Destaca-se que o processo sempre se inicia
na base árvore e progressivamente sobe para os demais itens. Assim, para o exemplo do Quadro 2, tem-se o seguinte resultado:
Quadro 2 - Resultado Exemplo 2
Item Base de Transações Condicionais FP-Tree Condicional
P {( f cam:2), (cb:1)} {(c:3)}|p
M {( f ca:2), (fcab:1)} {( f :3, c:3, a:3)}|m
B {( f ca:1), ( f :1), (c:1)} Vazio
A {( f c:3)} {( f :3, c:3)}|a
C {( f :3)} {( f :3)}|c
F Vazio Vazio
Fonte: HAN et al (2004), adaptado pelo Autor.
A forma diferenciada de reservar a informação em uma estrutura compacta, como o FP-Tree, permite um tempo de processamento melhor, comparado ao Apriori, quando se utilizam grandes bases de dados e empregam-se suportes baixos (Han et al, 2004). Assim, optou-se neste estudo por utilizar o FP-Growth, pelo volume de dados trabalhados e pelo nível de suporte baixo necessário para detecção de indícios de ilícitos.
6 METODOLOGIA
Neste capítulo, descrevem-se as fontes utilizadas na revisão de literatura, a classificação do estudo, a metodologia utilizada para análise e a amostra empregada para a realização desta pesquisa.