Conforme mencionado anteriormente, o algoritmo FOntGAR utiliza estruturas taxonômicas onde os graus de especialização/generalização podem variar no intervalo [0,1]. Dessa forma, de acordo com Wei e Chen (1999), os cálculos de suporte e confiança devem ser estendidos, de forma a considerar os valores dos graus mencionados. Conforme apresentado no Capítulo 5, o grau de um termo x em relação ao seu ancestral y pode ser calculado usando a combinação max-min, através da Equação 1 (seção 5.3):
( )
Onde representa um dos caminhos entre x e y, em é uma das arestas do acesso , é o grau na aresta em . Se não houver nenhum acesso entre x e y, . Assim, pela Figura 6.7, existem dois caminhos possíveis entre tomate e Hortifrúti: tomate → Fruta → Hortifrúti, com grau mínimo do caminho = 0.7, e tomate → Legume → Vegetal → Hortifrúti, com grau mínimo do caminho = 0.6, portanto, tomate é um Hortifrúti com grau 0.7, pois max(0.7, 0.6) = 0.7.
Figura 6.7 - Exemplo de Figura e Legenda (Yaguinuma, 2007).
Considere um exemplo, extraído de Wei e Chen (1999). Suponha um banco de dados de um supermercado, como mostrado na Tabela 6.1, o suporte mínimo 30% (duas transações), a confiança mínima é 60%, e uma taxonomia fuzzy, conforme apresentado na Figura 6.8. De acordo com a Equação 1, são encontrados os graus dos nós folhas em relação aos seus ancestrais, que são os valores da tabela 6.2. Por exemplo, o grau de Tomate em relação a Pratos Vegetais é calculado como a seguir:
∊ =
Tabela 6.1 – Exemplo Simples de Base Transacional.
Transação Itens #100 Maçã #200 Tomate, carneiro #300 Repolho, carneiro #400 Tomate, porco #500 Porco #600 Repolho, porco
Tabela 6.2 – Representação dos Graus entre Folhas e Ancestrais.
Nós folhas Graus entre eles e os ancestrais
Maçã 1/maçã, 1/fruta, 1/pratos vegetais Tomate 1/tomate, 0.3/vegetal, 0.7/fruta, 0.7/pratos vegetais Repolho 1/repolho, 1/vegetal, 1/pratos vegetais
Porco 1/porco, 1/carne
Figura 6.8 – Taxonomia Simples de Domínio Alimentício.
Utilizando os conceitos apresentados, antes de iniciar a geração de candidatos, FOntGAR utiliza o reasoner da ontologia difusa para obter os graus dos nós folha em relação a todos os seus ancestrais. Esse processamento é realizado em etapa inicial para que na etapa subsequente seja possível obter o grau em que cada transação do banco de dados suporta um ancestral da ontologia, e posteriormente o suporte e confiança estendidos das regras generalizadas possam ser calculados.
As etapas de geração de candidatos, e geração das regras tradicionais são efetuados como no algoritmo Apriori, entretanto, durante a varredura inicial da base (que ocorre na etapa de geração de candidatos), o algoritmo converte a mesma do formato horizontal para um formato vertical, incluindo também os ancestrais da ontologia nessa conversão. Essa estratégia permite acesso indexado às ocorrências de um elemento. A Figura 6.9 ilustra uma base de dados em formato vertical.
Além do exposto, o algoritmo FOntGAR suporta situações onde a relação entre itens da base e folhas da ontologia não é total, ou seja, situações em que nem toda folha da estrutura taxonômica representa um item da base de dados, e/ou nem todo item da base de dados possui um representante na estrutura. Nesse sentido, em relação à utilização do parâmetro de generalização mínima mingen, o processo de verificação do percentual de descendentes de cada ancestral foi adaptado ao novo conceito. Por exemplo, suponha que existam cinco tipos de leite descendentes do ancestral “leite” ( , , , e ), mas apenas quatro estão presentes na base ( , , , e ). Como não está no banco, ele jamais ocorrerá nas regras, sendo irrelevante a situação explorada. É como se não existisse na estrutura, podendo inclusive ser removido da mesma.
Com base nesse exemplo, considerou-se que, em situações onde ocorra relação parcial, 100% dos descendentes de um ancestral devam ser apenas os elementos que, de fato, estão presentes no banco de dados. No exemplo anterior, teríamos que 100% dos ancestrais de “leite” são: , , , e , e não , , , e , , e isso faz total diferença na verificação do mingen. Nesse sentido, dependendo da complexidade, e também do tamanho da ontologia, tal verificação pode se tornar extremamente complexa, pois vários itens podem ser inúteis ao contexto.
Sendo assim, para facilitar a verificação mencionada, na varredura que é realizada no banco de dados durante a fase de geração de candidatos, o algoritmo armazena todos os diferentes itens do banco em um vetor de itens. Com base nesses elementos, e na estrutura taxonômica da ontologia difusa, por meio de uma estratégia “bottom-up” é gerada uma taxonomia reduzida, que corresponde à ontologia principal, mas possui apenas os elementos presentes no banco de dados. Por exemplo, considerando um item “a” presente no banco, verificam-se na ontologia quais são os ancestrais imediatos (pais) do mesmo, os ancestrais dos pais encontrados, e assim sucessivamente, até que se chegue à raiz. Isso é feito para todos os diferentes itens encontrados no banco de dados, que estão presentes do vetor de itens mencionado anteriormente.
A Figura 6.10 ilustra a ideia proposta. Os nós circulados representam itens ausentes no banco de dados. Portanto, note que, embora a estratégia de geração da taxonomia relativa seja bottom-up, ela permite que os itens irrelevantes não estejam presentes na nova estrutura. No entanto, é importante salientar que a taxonomia
relativa é utilizada apenas na verificação do parâmetro de generalização mínima (mingen) e, portanto não são inseridos os graus de especialização/generalização da ontologia difusa na mesma.
Figura 6.10 – Redução de uma Ontologia a uma taxonomia relativa onde todos os
itens folhas estrutura extraída estejam presentes na base de dados.
Ao final do processo tradicional de extração de padrões, obtém-se o conjunto de regras especializadas que serão utilizadas no tratamento de generalização. Conforme dito, dentre outras coisas, o tratamento de generalização utiliza uma função de agrupamento groupingRules (linha 5 da Figura 6.12), que trabalha de acordo com a metodologia apresentada na subseção anterior. Sendo assim, as regras geradas, e o lado da generalização (valor do parâmetro side) são passados como parâmetros para a função mencionada.
Ao realizar o agrupamento, para cada grupo, FOntGAR guarda quais são os pais referentes ao antecedente, e consequente das regras do grupo, e também quais são os itens das regras do grupo (no antecedente, e no consequente) que não possuem pais, ou seja, ele já associa ao grupo sua regra generalizada correspondente (Figura 6.11). Essa regra será aqui denominada regra generalizada representante (linha 8), que é o padrão que irá substituir os demais.
Além disso, o tratamento de generalização também realiza os seguintes processamentos:
1 - verifica se o parâmetro mingen foi satisfeito (linha 9);
2 - realiza duas verificações no padrão representante (substituto) (linha 10): Na primeira, é checado se os lados antecedente e consequente são disjuntos, e na
segunda é verificado se nenhum item consequente possui pai no lado antecedente, e vice-versa. Isso é feito para confirmar se os critérios conceituais de regras generalizadas estão sendo satisfeitos (seção 2.5).
Após as verificações mencionadas existem três ações possíveis de serem executadas, dependendo do resultado obtido:
1. Se essas verificações são satisfeitas (linha 11), então o cálculo de suporte da regra representante é realizado. Nesse caso, se a regra geral é
frequente, então todas as regras do grupo são descartadas e, de fato, substituídas pela regra representante (generalizada), que é armazenada para posteriormente ser apresentada ao usuário.
2. Se as verificações são satisfeitas (linha 11), mas após o cálculo de suporte da regra generalizada verifica-se que a mesma não é frequente (linha 17), então a generalização não pode ocorrer. Nesse caso, as regras do grupo não são descartadas, pois poderão ser apresentadas ao usuário (linha 19). 3. Por outro lado, se as verificações apresentadas não forem atendidas, o
suporte da regra representante não chega a ser calculado (linha 21), e as regras do grupo também não são descartadas. Portanto a generalização não ocorre.
Figura 6.11 – Ilustração de grupos de regras com uma regra mais geral
Figura 6.12 – Pseudocódigo Tratamento de Generalização.
A generalização é feita nível a nível, ou seja, primeiro generaliza-se das folhas para os pais, e assim sucessivamente. Sendo assim, as regras generalizadas obtidas em cada nível são exploradas no nível subsequente de generalização, sendo que a cada iteração elas são fornecidas como parâmetro para a função groupingRules. O laço é repetido até que se chegue a um nível abaixo da raiz, ou até que não seja possível obter regras generalizadas em qualquer nível anterior.
Após o tratamento de generalização, o algoritmo usa o reasoner da ontologia para obter as relações de similaridade, inserindo as mesmas nos padrões gerados. Diferente do que é feito nos trabalhos relacionados, não ocorre inserção de itens difusos no conjunto de candidatos.
Por fim, após a identificação das similaridades, FOntGAR entra em seu estágio final, que é a organização do resultado. O conjunto final de regras é composto de padrões generalizados e tradicionais e, além disso, as regras são apresentadas ordenadamente de acordo com o nível de generalização. Sendo assim, o resultado é apresentado como a seguir:
Figura 6.13 – Formato em que o Resultado é Apresentado.
6.2.4 Calculando Graus de Suporte e Confiança Estendidos no Pós-