Pontifı́cia Universidade Católica de Minas Gerais
Departamento de Ciência da Computação
Análise Formal de Conceitos:
Revisão Conceitual e Estudo da Aplicabilidade
Autor:
João Paulo Domingos Silva
Orientador:
Luis Enrique Zárate
Relatório Técnico RT XX / 04
Belo Horizonte, Minas Gerais, Brasil
Junho de 2004
Folha de Aprovação da Banca Examinadora
Análise Formal de Conceitos:
Revisão Conceitual e Estudo da Aplicabilidade
João Paulo Domingos Silva
Relatório técnico apresentado ao Departamento de Ciência da Computação
do Instituto de Informática da Pontifı́cia Universidade Católica de Minas
Gerais como requisito da disciplina Trabalho de Diplomação do curso de
Ciência da Computação e aprovado pela banca examinadora composta
pelos seguintes membros:
Professor Luis Enrique Zárate
Orientador
Departamento de Ciência da Computação - PUC Minas
Professor Cristiano Leite de Castro
Examinador
Departamento de Ciência da Computação - PUC Minas
Professor Mark Alan Junho Song
Examinador
Departamento de Ciência da Computação - PUC Minas
Belo Horizonte, 20 de junho de 2004
Age apenas segundo aquelas máximas através das quais possas,
ao mesmo tempo, querer que elas se transformem numa lei geral.
Immanuel Kant
Agradecimentos
Meu primeiro “Obrigado!” é evidentemente destinado ao meu orientador
Luis Enrique Zárate. Foi ele quem confiou em mim como pesquisador e me
aceitou na “Salinha de Pesquisa”, de onde foram alcançadas diversas
vitórias em minha Graduação. Foi também ele quem, em nossas filosóficas
conversas, me ensinou que nossa contribuição para o progresso da Ciência
da Computação é bastante humilde, embora seja igualmente valiosa.
Obrigado, Zárate! Agradeço também aos meus colegas graduandos Daniel
Alencar Soares, Leonardo Teixeira Passos e Renato Vimieiro, com quem
vivenciei memoráveis momentos tanto na “Salinha de Pesquisa” como fora
dela. Eis pessoas que fielmente cumprem seus compromissos de amizade e
de honestidade, me fazendo crer no relacionamento pessoal e profissional
baseado em posturas éticas. Desejo que merecidamente sejam pessoas
renomadas na Ciência da Computação. Obrigado, Daniel, Léo e Renato!
Dedicatória
Com todo amor, dedico essa graduação a algumas pessoas de importância
especial em minha vida. São pessoas que, durante o cotidiano, me
permitem perceber que por mais solidamente fundamentados que sejam
nossos argumentos, há coisas que simplesmente não podem ser mensuradas
ou modeladas por quaisquer ciências. Aos meus pais - Reginaldo Eustáquio
da Silva e Anette Domingos Silva. Eis pessoas que me ensinaram as maiores
virtudes do ser humano por meio daquela que é a melhor metodologia de
educação: o exemplo. Agradeço aos dois pela imensurável paciência,
principalmente durante os últimos quatro “loucos” anos de Graduação. À
minha namorada “Bisquinha” - Grazielle Xavier Araújo - e ao meu
maninho “Silipe” - Luiz Felipe Domingos Silva. Eis os grandes parceiros
que arrumei em minha vida, pessoas que me proporcionam imensurável
felicidade e a quem desejo o dobro de tal sentimento (embora seja
imensurável!). Agradeço também aos dois pela paciência que têm comigo...
Os últimos quatro “loucos” anos de Graduação realmente precisaram da
preciosa paciência...
Resumo
A informação desempenha papel essencial tanto em âmbito pessoal como
profissional e, quando devidamente gerenciada, sua interpretação conduz ao
processo de extração de conhecimento. Devido à importância da informação,
pesquisadores sempre exploram metodologias cujos propósitos sejam seu gerenciamento. Entretanto, os dados que compõem a informação têm uma
complexa natureza quando considerados na realidade observada. Embora
seja inerente aos seres humanos o comportamento de determinar conceitos
que modelem a realidade observada, a complexidade da mesma não pode ser
completamente assimilada e podem ser determinados dados inconsistentes,
implicando em inconsistências tanto na informação como no conhecimento.
Análise Formal de Conceitos é aqui proposta como uma metodologia que
procura facilitar a tarefa de extrair conhecimento, devido à sua definição
como ramo da Matemática Aplicada principalmente empregada para processar dados fornecidos. Sua principal vantagem reside na capacidade de
gerar diagramas que facilitam a interpretação da informação. Análise Formal de Conceitos tem seus recursos empregados juntamente com tradicionais
técnicas da Ciência da Computação nesse trabalho. Tal análise é denominada “formal” devido à sua sólida fundamentação matemática e “conceito” é
o nome atribuı́do aos dados analisados, uma vez que conceitos correspondem
a unidades do pensamento humano.
Alguns pesquisadores propõem Análise Formal de Conceitos para extração
de conhecimento, mas tais autores insistem em discutir somente aspectos
teóricos. Em seus trabalhos, os diagramas da Análise Formal de Conceitos
são apresentados como recursos que permitem a extração de conhecimento,
mas nenhuma metodologia envolvendo a exploração de tais diagramas é discutida. Esse trabalho concilia aspectos teóricos e práticos: os fundamentos
da Análise Formal de Conceitos são discutidos por completo, um programa
que foi implementado durante o desenvolvimento desse trabalho tem suas
principais funcionalidades aqui apresentadas e, finalmente, aplicações conciliando Ciência da Computação e Análise Formal de Conceitos são propostas
e têm sua viabilidade analisada.
5
Abstract
Information performs an essential role both in personal and in professional
ambits, and when correctly managed, its interpretation leads to the process
of knowledge extraction. Due to the importance of information, researchers
always explore methodologies that aim at managing it. However, data that
make up information have a complex nature when considered in the observed
reality. Although it is inherent in humans the behavior of determining concepts that model the observed reality, its complexity can not be completely
considered by humans and inconsistent data may be determined, involving
inconsistence in information and, consequently, in knowledge.
Formal Concept Analysis is presented here as a methodology that facilitates the task of knowledge extraction, due to its definition as a field
of Applied Mathematics mostly used for processing given and presumedly
consistent data. Its principal advantage consists in its capacity of generating
diagrams that facilitate information interpretation. Formal Concept Analysis
has its resources used jointly with Computer Science traditional techniques
in this work. Such analysis is called “formal” due to its mathematical foundation and “concept” is the name given to the analized data, since concepts
correspond to units of human thought.
Some researchers propose Formal Concept Analysis for knowledge extraction from databases, but those authors insist on discussing only theoretical
aspects. In their works, diagrams from Formal Concept Analysis are presented as devices that permit knowledge extraction, but no methodologies
involving the exploration of such diagrams are discussed. This work conciliates both practical and theoretical aspects: Formal Concept Analysis foundations are entirely discussed, a software that has been implemented during the
development of this work has its main functions presented here and, finally,
applications conciliating Computer Science and Formal Concept Analysis are
proposed and have their viability investigated.
Sumário
1 Introdução
1.1 Problema . . . . . . . .
1.2 Motivação . . . . . . . .
1.3 Literatura . . . . . . . .
1.4 Objetivos . . . . . . . .
1.5 Estrutura da monografia
.
.
.
.
.
.
.
.
.
.
2 Análise Formal de Conceitos
2.1 Contextos formais . . . . . .
2.2 Conceitos formais . . . . . .
2.3 Reticulados conceituais . . .
2.4 Considerações . . . . . . . .
3 Aplicações
3.1 Programa Sophia . . . .
3.2 Redes Neurais Artificiais
3.3 Mineração de Dados . .
3.4 Bancos de Dados . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4 Conclusões
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7
. 8
. 9
. 9
. 10
. 11
.
.
.
.
.
.
.
.
12
12
13
16
18
.
.
.
.
20
20
24
30
36
.
.
.
.
44
6
Capı́tulo 1
Introdução
Análise Formal de Conceitos é um ramo da Matemática Aplicada, particularmente da denominada Teoria de Reticulados. Tais reticulados podem
ser sucintamente definidos como conjuntos ordenados segundo determinadas
normas de hierarquia. Definições mais precisas a respeito de reticulados excedem o escopo proposto a esse trabalho. Portanto, questões de tal assunto
serão aqui mencionadas somente quando relevantes ao estudo aqui proposto.
Um interessante modo de começar o estudo da Análise Formal de Conceitos é segmentando seu próprio nome [GW98]:
“Análise” sugere observação e manipulação de dados fornecidos;
“Conceitos” determina unidades segundo as quais os dados são estruturados, correspondentes à interpretação humana da realidade (adiante
serão apresentados os conceitos formais);
“Formal” sugere fundamentação matemática referente à análise e aos conceitos, evitando ao máximo o predomı́nio da subjetividade humana em
tarefas de gerenciamento de informação e de conhecimento.
“Dado”, “Informação” e “Conhecimento” são aqui considerados respectivamente como codificação da realidade observada, dados acrescentados de
sentido e interpretação humana da informação [Wil01].
Contribuir para o gerenciamento de informação e de conhecimento pode
ser observado como o principal emprego da Análise Formal de Conceitos.
Como quaisquer ciências necessitam que informação e conhecimento sejam
eficientemente gerenciados, a Análise Formal de Conceitos tem um espaço
abrangente de aplicações. Essa aceitação em diversas ciências é estimulada por sua representação gráfica dos dados, permitindo que os mesmos
e, especialmente, suas relações, sejam analisados com maior proveito. A
7
CAPÍTULO 1. INTRODUÇÃO
8
Figura 1.1 demonstra um exemplo extremamente simples envolvendo os nove
primeiros números inteiros positivos, representados por meio de um diagrama
da Análise Formal de Conceitos. Mesmo para quem desconhece tal diagrama,
sua potencialidade já é notável, pois uma simples observação já permite a
dedução de como os dados se relacionam. Adiante, diagramas como esse serão
detalhadamente abordados, com exemplos mais interessantes, considerando
aspectos como sua estrutura, seu funcionamento, sua análise, suas aplicações
etc.
Figura 1.1: Diagrama de números e suas propriedades.
1.1
Problema
Em qualquer ramo profissional, as pessoas constantemente precisam tomar
decisões fundamentadas na informação que possuem, mas tal informação conterá problemas se os dados armazenados que a compõem também os contiverem. Essa situação ocorre pois a informação fornecida pela realidade ao
ser humano é extremamente complexa. Entretanto, é inerente ao ser humano,
como já observado há séculos por filósofos (como Aristóteles), a necessidade
de determinar conceitos que modelem a realidade observada. Mas toda a
complexidade da informação fornecida por essa realidade não é absorvida
pelo ser humano e, por isso, os dados por ele obtidos certamente precisam
passar por uma análise cuidadosa.
Analisar eficientemente dados certamente é mais proveitoso que simplesmente possuir um grande volume dos mesmos. É evidente não ser razoável
considerar tal análise como sendo tarefa exclusivamente humana. Como conseqüência, tal processo seria lento, caro e inevitavelmente sujeito à subjetividade e equı́vocos humanos. Tais conseqüências seriam esperadas porque um
profundo entendimento do domı́nio do problema seria requerido e porque as
CAPÍTULO 1. INTRODUÇÃO
9
bases de dados podem ter milhares ou milhões de dados. Portanto, como é
tarefa dos computadores armazenar tamanha quantidade de dados, é razoável
o emprego dos mesmos (e metodologias automatizadas) também no gerenciamento da informação [FSS96].
1.2
Motivação
Aprimorar o gerenciamento de informação é a motivação desse trabalho, pois
tanto em âmbito pessoal como profissional, a informação apropriadamente
gerenciada é indispensável. A Ciência da Computação é incontestável parceira da Análise Formal de Conceitos, pois está constantemente lidando com
análise de dados. E nesse trabalho, recursos da Análise Formal de Conceitos
são associados aos da Ciência da Computação (por exemplo: Descoberta de
Conhecimento em Bases de Dados).
Contudo, o emprego da Análise Formal de Conceitos não é isento de determinadas limitações inerentes a quaisquer métodos tradicionais que lidam
com informação e conhecimento. Por exemplo, uma representação de conhecimento é consistente somente se também o forem os dados fornecidos
pelo ser humano. Entretanto, segundo a Filosofia, o conhecimento que o
ser humano tem da realidade é deformado pela necessária mediação de seus
sentidos. Mesmo que os dados do ambiente sejam coletados por um sistema
computacional, esse também foi implementado segundo a interpretação humana. Ou seja, durante o processo de codificação de elementos da realidade,
alguns detalhes inevitavelmente são ignorados ou erroneamente considerados. Portanto, é desejável que formalismos sejam empregados durante a
observação da realidade. Alguns trabalhos [Gua95, Gua98] tratam da Ontologia Formal (apenas mencionada aqui) como meio de suprimir limitações
de interpretação.
1.3
Literatura
Os trabalhos pesquisados para o desenvolvimento desse remetem o leitor
a autores pioneiros ou renomados em suas áreas de atuação. Portanto, o
conteúdo aqui apresentado é diretamente fundamentado em confiáveis fontes
da Análise Formal de Conceitos e assuntos relacionados. Não foi destinado
um capı́tulo exclusivo à revisão literária, pois o Capı́tulo 2 tem como conteúdo
a fundamentação teórica do assunto aqui estudado.
Alguns trabalhos [DP90, Gra98] são constantemente referenciados por
conterem uma profunda abordagem da Teoria de Reticulados e seus princı́pios
CAPÍTULO 1. INTRODUÇÃO
10
matemáticos. Na Teoria de Reticulados, elementos de um conjunto são ordenados segundo suas propriedades e relacionamentos. É um assunto que
parecia ter proveito somente dentro do ambiente abstrato da Matemática.
Mas na década de oitenta, o matemático alemão Rudolf Wille apresentou
a Análise Formal de Conceitos, como uma aplicação prática dos reticulados. Esses começavam agora a auxiliar o ser humano na interpretação de
informação e extração de conhecimento. Um grupo de pesquisadores de uma
universidade alemã contribuiu por anos na propagação do assunto no meio
cientı́fico. Ganter e Wille escreveram o primeiro livro de Análise Formal
de Conceitos [GW96], com consideração especial para sua fundamentação
matemática. Inúmeros outros trabalhos [GW98] tratam mais sucintamente
o assunto, considerando apenas seus pontos mais relevantes. Algoritmos e
programas computacionais foram também objeto de estudo de diversos autores interessados nesse ramo. Não é necessário enumerar muitos trabalhos
de caráter teórico, pois o âmago teórico é abordado por completo pelos pioneiros (demais autores não propõem novidades consideráveis).
Em âmbito prático, os pesquisadores também sugerem aplicações para
Análise Formal de Conceitos. Mineração de Dados e Descoberta de Conhecimento pertencem ao ramo da Ciência da Computação mais próximo
da Análise Formal de Conceitos, mas as pesquisas [Wil01, Stu03, SWW98]
abordam tal assunto de modo extremamente conceitual, sem propôr qualquer
metodologia prática. Bancos de Dados também foram estudados por alguns
pesquisadores [HPLC], que propõem a determinação de conceitos formais de
modelos relacionais. É também apresentado aqui o emprego na descoberta
do conhecimento adquirido por Redes Neurais Artificiais, assunto não encontrado em qualquer trabalho.
1.4
Objetivos
É objetivo desse trabalho, como sugere seu subtı́tulo, estudar conceitualmente Análise Formal de Conceitos e também avaliar sua aplicabilidade na
Ciência da Computação. Esse objetivo geral pode ser descrito em objetivos
especı́ficos, assim enumerados:
• Estudar o estado da arte das pesquisas na área, por meio dos trabalhos de renomados pesquisadores, procurando sumariar fundamentação
teórica proveitosa para vindouros interessados em ingressar nessa área.
• Elaborar e implementar uma ferramenta computacional que trabalhe
com aspectos primordiais do assunto, procurando estudar profunda-
CAPÍTULO 1. INTRODUÇÃO
11
mente os mais importantes algoritmos e proporcionando um recurso
automatizado para tarefas mais comuns.
• Estudar a aplicabilidade da Análise Formal de Conceitos em problemas inerentes à Ciência da Computação, particularmente nas áreas de
Mineração de Dados, Bancos de Dados e Redes Neurais Artificiais.
1.5
Estrutura da monografia
Esse trabalho é organizado segundo os objetivos enumerados na seção 1.4.
Desse modo, é pretendido que o trabalho aborde o assunto em questão segundo diversos ângulos: fundamentos teóricos, implementação e aplicação.
É recomendável, para um melhor proveito, a leitura seqüencial dos capı́tulos,
que assim podem ser brevemente descritos:
• O próximo capı́tulo aborda a fundamentação teórica da Análise Formal
de Conceitos, com o objetivo de ingressar o leitor no entendimento
de tal assunto. Durante todo o capı́tulo, a explanação do assunto é
acompanhada de exemplos.
• O terceiro capı́tulo tem conteúdo situado no escopo do estudo da aplicabilidade da Análise Formal de Conceitos. Nele são apresentados o
programa desenvolvido durante o trabalho e propostas de aplicação na
Ciência da Computação.
• E no último capı́tulo, são apresentadas conclusões e propostas de trabalhos futuros. Nas conclusões, podem ser encontradas observações a
respeito do progresso do trabalho, como pontos positivos, negativos,
objetivos cumpridos etc.
Capı́tulo 2
Análise Formal de Conceitos
2.1
Contextos formais
Definir contexto formal é requisito primordial para o estudo da Análise Formal de Conceitos. Tal contexto tem a notação K := (G, M, I), sendo G e M
conjuntos contendo elementos respectivamente denominados objetos e atributos e sendo I ⊆ G × M uma relação binária chamada incidência. Todo
elemento da incidência tem a notação gIm, que denota uma relação entre
um objeto e um atributo, lida como “o objeto g possui o atributo m”. Para
quaisquer subconjuntos A ⊆ G e B ⊆ M , podem ser determinados seus
conjuntos derivados (que respectivamente são os atributos possuı́dos pelos
objetos e os objetos que possuem os atributos), por meio das operações de
derivação:
A0 := {m ∈ M | gIm ∀ g ∈ A}
B 0 := {g ∈ G | gIm ∀ m ∈ B}
O recurso mais apropriado para representação de um contexto formal é
a chamada tabela cruzada. A Tabela 2.1 contém um exemplo simples de
contexto formal, no qual os objetos são alguns animais, os atributos são
enumerados nas colunas e a incidência contém as células marcadas. Detalhes
pertencentes ao ramo da biologia não serão profundamente considerados aqui;
animais e sua taxonomia são aqui empregados apenas como exemplos para a
apresentação da Análise Formal de Conceitos. É importante mencionar um
caso especial de conjuntos derivados, que acontece quando conjuntos vazios
de objetos ou de atributos são considerados para serem derivados:
A ⊆ G = ∅ ⇒ A0 := M
B ⊆ M = ∅ ⇒ B 0 := G
12
CAPÍTULO 2. ANÁLISE FORMAL DE CONCEITOS
13
Tabela 2.1: Exemplo de contexto formal. Linhas: (1) baleia; (2) cobra;
(3) coruja; (4) humano; (5) jacaré; (6) macaco; (7) pingüim; (8) sapo; (9) tartaruga; (10) tubarão. Colunas: (a) aquático; (b) terrestre; (c) respiração
branquial; (d) respiração pulmonar; (e) membros; (f) pêlos; (g) penas; (h) escamas; (i) glândulas mamárias; (j) raciocı́nio.
1
2
3
4
5
6
7
8
9
10
2.2
a
×
×
b
×
×
×
×
×
×
×
×
×
c
×
d
×
×
×
×
×
×
×
×
×
e
f
g
h
i
×
j
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
Conceitos formais
Um contexto formal determina conceitos formais, cada um com notação
(A, B), sendo A ⊆ G, B ⊆ M , A0 = B e B 0 = A. O conjunto dos objetos
do conceito formal é denominado extensão e o dos atributos, intenção. Cada
elemento da extensão possui todos os da intenção, e é correta a afirmação
análoga para a intenção em relação à extensão. O conjunto de todos os conceitos formais existentes em um contexto formal recebe a notação B(G, M, I).
Eis o algoritmo [Gan] aqui adotado e implementado na tarefa de determinar
todos os conceitos formais existentes em um contexto formal:
booleano conceitoFormal [0 :
booleano variavelAuxiliar [0
inteiro numeroSelecionado :=
booleano variavelControle :=
numeroAtributos - 1] // Todo negativo.
: numeroAtributos - 1] // Todo negativo.
numeroAtributos
falso
enquanto conceitoFormal contém negativo ou variavelControle = verdadeiro
enquanto conceitoFormal [numeroSelecionado] = verdadeiro
numeroSelecionado := numeroSelecionado - 1
fim enquanto
conceitoFormal [numeroSelecionado] := verdadeiro
para i := numeroSelecionado + 1 até i < numeroAtributos
conceitoFormal [i] := falso
fim para
CAPÍTULO 2. ANÁLISE FORMAL DE CONCEITOS
14
// Duas derivaç~
oes (’’): Calcula extens~
ao, depois intenç~
ao.
variavelAuxiliar := conceitoFormal’’
variavelControle := false
para i := 0 até i < numeroSelecionado
se conceitoFormal [i] = falso e variavelAuxiliar [i] = verdadeiro
numeroSelecionado := numeroSelecionado - 1
variavelControle := verdadeiro
interrompe laço
fim se
fim para
se variavelControle = falso
para i := 0 até i < numeroAtributos
conceitoFormal [i] := variavelAuxiliar [i]
fim para
novoConceito := conceitoFormal // DETERMINADO NOVO CONCEITO!
numeroSelecionado := numeroAtributos
fim se
fim enquanto
// Observaç~
ao (leia próximo parágrafo):
// Ver se considerou o conceito formal
// com extens~
ao contendo todos os objetos:
inteiro maiorExtensao := número de objetos na maior extens~
ao
se maiorExtensao < numeroObjetos
novoConceito := (todos os objetos,
sem atributos) // DETERMINADO NOVO CONCEITO!
fim se
Para abordar tal algoritmo em detalhes, seria necessário recorrer a fundamentos da Teoria de Reticulados. Como esse trabalho não abrange tal
teoria em seu escopo, o algoritmo é aqui escrito com o propósito de permitir
que o leitor implemente o mesmo e conheça seu funcionamento. No algoritmo, no instante em que um novo conceito formal é determinado, a variável
novoConceito contém os atributos da intenção B do par (A, B); a derivação de
tal conjunto resulta na extensão A, contendo os objetos do conceito formal.
Como pode ser observado no algoritmo, o conceito formal contendo todos
os objetos em sua extensão não é automaticamente encontrado quando sua
intenção é vazia.
Alguns algoritmos [GW96] que determinam B(G, M, I) são bastante conhecidos e empregados, pois cumprem seu objetivo demandando baixos tempos de processamento. Independentemente de qual algoritmo utilizado, o
contexto formal da Tabela 2.1 determina dezoito conceitos formais, mostra-
CAPÍTULO 2. ANÁLISE FORMAL DE CONCEITOS
15
dos na Tabela 2.2. Para gerar essa tabela, o algoritmo aqui apresentado foi
empregado no contexto formal que envolve animais. Em qualquer conceito
formal (A, B) da tabela, é evidentemente constatável que A0 = B e B 0 = A,
ou seja, que todos os animais pertencentes à mesma extensão possuem todos
os atributos pertencentes à respectiva intenção.
Tabela 2.2: Conceitos formais. Na extensão: (1) baleia; (2) cobra; (3) coruja;
(4) humano; (5) jacaré; (6) macaco; (7) pingüim; (8) sapo; (9) tartaruga;
(10) tubarão. Na intenção: (a) aquático; (b) terrestre; (c) respiração branquial; (d) respiração pulmonar; (e) membros; (f) pêlos; (g) penas; (h) escamas; (i) glândulas mamárias; (j) raciocı́nio.
Índice
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Extensão
1, 2, 3, 4, 5,
2, 5, 9, 10
1, 2, 3, 4, 5,
1, 4, 6
2, 3, 4, 5, 6,
2, 5, 9
3, 4, 5, 6, 6,
5, 9
3, 7
4, 6
4
1, 8, 10
1, 8
1
8, 10
10
8
∅
6, 7, 8, 9, 10
6, 7, 8, 9
7, 8, 9
7, 8, 9
Intenção
∅
h
d
d, i
b, d
b, d, h
b, d, e
b, d, e, h
b, d, e, g
b, d, e, f, i
b, d, e, f, i, j
a
a, d
a, d, i
a, c
a, c, h
a, b, c, d, e
a, b, c, d, e, f, g, h, i, j
Analisar conceitos formais é mais intuitivo que analisar um contexto formal. Em conceitos formais, os objetos são agrupados segundo seus atributos
similares e podem ser ordenados segundo uma hierarquia de atributos, como
será mencionado adiante. Como demonstração do quão intuitivo é analisar
conceitos formais, observando as extensões e as intenções da Tabela 2.2, o
leitor pode perceber que a organização dos animais segundo conceitos formais esboça algo de taxonomia, como os mamı́feros agrupados no conceito
formal de ı́ndice 4. É oportuno que seja também notada a exceção referente
à derivação de conjuntos vazios, no primeiro e no último conceitos formais.
CAPÍTULO 2. ANÁLISE FORMAL DE CONCEITOS
2.3
16
Reticulados conceituais
Quando o conjunto de todos os conceitos formais de um contexto formal
é hierarquicamente ordenado segundo a Teoria de Reticulados Completos
[Gra98, DP90], recebe a denominação de reticulado conceitual e a notação
B(G, M, I). Seus conceitos formais se relacionam como (A1 , B1 ) ≤ (A2 , B2 ),
quando A1 ⊆ A2 e B2 ⊆ B1 , sendo (A1 , B1 ) chamado subconceito e (A2 , B2 )
chamado superconceito. No reticulado conceitual aqui abordado, o conceito
formal de extensão {“humano”} é, por exemplo, subconceito do conceito
formal de extensão {“humano”, “macaco”}; o atributo “raciocı́nio” os difere.
A estrutura de um reticulado conceitual B(G, M, I) é similar à herança de
classes na programação orientada por objetos. Em toda relação (A1 , B1 ) ≤
(A2 , B2 ), a intenção do subconceito contém todos os atributos da intenção
do superconceito e contém também novos atributos, do mesmo modo como
na herança de classes. Retomando o exemplo anterior, o conceito formal
de extensão {“humano”} possui os mesmos atributos do conceito formal de
extensão {“humano”, “macaco”}, mas adiciona “raciocı́nio” à sua intenção.
Eis o algoritmo [Gan] aqui adotado e implementado na tarefa de estruturar
um reticulado conceitual, desde que se tenham os conceitos formais:
para i := 0 até i < numeroConceitosFormais
conceitoFormal1 := conceitosFormais [i]
para j := i + 1 até j < numeroConceitosFormais
conceitoFormal2 = conceitosFormais [j]
se conceitoFormal1.intenç~
ao é subconjunto de conceitoFormal2.intenç~
ao
se conceitoFormal1 e conceitoFormal2
n~
ao possuem conceitos formais entre si
conceitoFormal1 é superconceito de conceitoFormal2
fim se
fim se
fim para
fim para
Tão adequado quanto representar um contexto formal (G, M, I) por meio
de uma tabela cruzada, é representar um reticulado conceitual B(G, M, I)
por meio do chamado diagrama de linhas. O diagrama representa o reticulado
conceitual como um grafo, cujos vértices denotam conceitos formais e cujas
arestas denotam suas relações hierárquicas (A1 , B1 ) ≤ (A2 , B2 ). A Figura 2.1
apresenta o diagrama de linhas dos conceitos formais da Tabela 2.2, referentes
ao contexto formal da Tabela 2.1. Uma vez executados os dois algoritmos
aqui apresentados, é possı́vel desenhar o diagrama de linhas, baseado na
determinação de subconceitos e superconceitos.
Todo conceito formal (A, B) de um reticulado conceitual B(G, M, I) é
representado por um vértice no diagrama de linhas. Quando dois conceitos
CAPÍTULO 2. ANÁLISE FORMAL DE CONCEITOS
17
Figura 2.1: Diagrama de linhas.
formais se relacionam como subconceito (A1 , B1 ) e superconceito (A2 , B2 )
sem que haja qualquer outro conceito formal entre ambos, seus vértices devem
ser conectados por uma aresta no diagrama de linhas. O vértice mais alto
do diagrama representa o conceito formal cuja extensão contém todos os
objetos, enquanto o mais baixo representa o conceito formal com todos os
atributos em sua intenção. Para tornar mais confortável e eficiente a leitura
de um diagrama de linhas, extensões e intenções não precisam ser escritas
por completo.
Na Figura 2.1, nomes de objetos e de atributos são escritos no diagrama
somente uma vez, evitando que os mesmos sejam repetidos como acontece na
enumeração dos conceitos formais. Desse modo, os objetos têm seus nomes
escritos no vértice mais baixo em que primeiro ocorrem, enquanto os nomes
dos atributos são escritos no vértice mais alto em que primeiro ocorrem.
Todos os atributos possuı́dos por um objeto podem ser encontrados nas intenções dos vértices superiores alcançados pelo vértice daquele objeto. Desse
modo, o aspecto mais importante no diagrama de linhas é sua estrutura em
nı́veis, ou seja, as alturas dos vértices devem ser consideradas, pois determinam subconceitos e superconceitos.
Para reforçar o entendimento da estrutura do diagrama de linhas, será
aqui considerado como exemplo o vértice de rótulo “humano” da Figura 2.1.
Subindo pelas arestas, começando pelo vértice em questão e passando por
CAPÍTULO 2. ANÁLISE FORMAL DE CONCEITOS
18
todos aqueles superiores alcançáveis pela origem, pode ser constatado que
o objeto em questão possui o conjunto de atributos {“glândulas mamárias”,
“membros”, “pêlos”, “raciocı́nio”, “respiração pulmonar”, “terrestre”}. Conforme anteriormente mencionado, tal estrutura é similar à herança de classes
na programação orientada por objetos. O vértice considerado seria classe
filha de seus superconceitos e, além de herdar todos seus atributos, teria seu
atributo “raciocı́nio”.
2.4
Considerações
Dado um conjunto de conceitos formais de um reticulado conceitual, ı́nfimo
e supremo são respectivamente o maior subconceito e o menor superconceito comuns a todos os elementos de tal conjunto. As definições de maior
e menor, dentro do escopo de reticulados conceituais, dizem respeito à ordenação hierárquica. Em outras palavras, o primeiro vértice no diagrama de
linhas no qual se cruzam os caminhos de determinados conceitos formais é
chamado ı́nfimo (se o caminho for para baixo) ou supremo (se o caminho for
V
para cima).WO Teorema Básico de Reticulados Conceituais aborda ı́nfimo
e supremo de conceitos formais, cujos ı́ndices estão em T :
^
(At , Bt ) =
t∈T
_
t∈T
\
At ,
t∈T
(At , Bt ) =
[
t∈T
[
00 !
Bt
t∈T
00 \ !
At ,
Bt
t∈T
É interessante observar que mesmo conceitos formais discrepantes entre si
têm ı́nfimo e supremo, ou seja, um ponto em comum no reticulado conceitual.
Por exemplo, os vértices de rótulos “humano‘” e “baleia” têm, no exemplo
considerado, o vértice de rótulo “glândulas mamárias” como supremo e o
vértice mais baixo do diagrama como ı́nfimo. Todo reticulado conceitual
contém um conceito formal maior que todos, denominado elemento unidade,
e um menor que todos, denominado elemento zero. Mesmo vértices sem
nada em comum, como “humano” e “tubarão”, por exemplo, têm o elemento
unidade (vértice mais alto) como supremo e o elemento zero (vértice mais
baixo) como ı́nfimo.
Análise Formal de Conceitos e sua peculiar representação da informação
nos estimula a procurar possibilidades para sua aplicação e também a discorrer a respeito do conhecimento. Analisando o exemplo aqui considerado por
meio de seu diagrama de linhas, poderı́amos facilmente imergir em discussões
a respeito da taxonomia dos seres vivos, pois os mesmos são agrupados e
CAPÍTULO 2. ANÁLISE FORMAL DE CONCEITOS
19
relacionados segundo a similaridade de seus atributos - os animais são dispostos no diagrama segundo sua classificação como anfı́bios, aves, mamı́feros,
peixes e répteis. Há também espaço para até mesmo discussões relacionadas
ao evolucionismo (!), como o fato de macacos e humanos estarem próximos.
Enfim, há possibilidade do contexto em questão ser abordado de diversos
modos, sendo o conhecimento resultado dessas abordagens e da informação
fornecida pelo diagrama.
Capı́tulo 3
Aplicações
Enquanto o Capı́tulo 2 aborda a fundamentação teórica da Análise Formal de
Conceitos, esse novo capı́tulo discute questões de natureza prática, estudando
a aplicabilidade da Análise Formal de Conceitos em problemas tradicionalmente solucionados pela Ciência da Computação. Uma ferramenta computacional implementada durante esse trabalho também compõe o estudo da
aplicabilidade. Tal ferramenta será o assunto principal do próximo tópico,
enquanto Mineração de Dados, Bancos de Dados e Redes Neurais Artificiais
serão relacionados com Análise Formal de Conceitos nos demais tópicos. Os
exemplos de aplicações aqui considerados não são o cerne da questão, mas
têm essencial importância na análise das metodologias propostas.
3.1
Programa Sophia
Elaborar e implementar uma ferramenta computacional que trabalhe com
aspectos primordiais da Análise Formal de Conceitos é um dos objetivos
aqui estabelecidos. Tal objetivo foi cumprido com o desenvolvimento de um
programa que recebeu o nome de “Sophia”1 . Tal programa foi implementado
na linguagem de programação Java e por enquanto executa funcionalidades
primordiais, mas é planejado que seu desenvolvimento não seja abandonado.
Sophia nasceu da necessidade de se estudar profundamente os mais importantes algoritmos da Análise Formal de Conceitos, por meio da implementação, e de proporcionar um recurso automatizado para as tarefas mais
comuns dessa área. Sua principal limitação certamente reside no fato de não
1
Como o assunto aqui abordado envolve conceitos de dados, informação e conhecimento,
“Sophia” é um adequado nome para a ferramenta computacional, pois é traduzido do
grego como “Sabedoria”, cuja definição está intimamente relacionada com conhecimento
e demais termos.
20
CAPÍTULO 3. APLICAÇÕES
21
representar reticulados conceituais por meio de diagramas de linhas. Tal
funcionalidade não é encontrada em Sophia, pois sua implementação demandaria bastante tempo, que poderia ser empregado em outras tarefas desse
trabalho. E também outros programas (mencionados adiante) já implementam diagramas de linhas e foram operados em parceria com Sophia, suprindo
sua limitação nessa questão especı́fica.
Entretanto, Sophia possui vantagens sobre outros programas na questão
de entrada de dados. É recebido como entrada do programa qualquer contexto formal proveniente de um arquivo de texto de extensão “.sph”, cujo
conteúdo contenha o contexto formal como tabela cruzada, sendo linhas e colunas respectivamente objetos e atributos e sendo seu conjunto de incidência
representado por “0” (i.e. objeto sem o atributo) ou “1” (i.e. objeto com
o atributo). Tal conteúdo pode ser primeiramente escrito em um programa
de planilha eletrônica e exportado para um arquivo de texto quando pronto.
Sophia também permite a manipulação de tabelas cruzadas (i.e. contextos
formais) por meio de sua interface gráfica.
Figura 3.1: Janelas do “Sophia” para contextos formais.
A Figura 3.1 retrata um instante na execução de Sophia. O ambiente de
trabalho do programa, como pode ser observado, suporta a manipulação
CAPÍTULO 3. APLICAÇÕES
22
simultânea de diversos contextos formais, representados por suas tabelas
cruzadas nas diversas janelas abertas do exemplo retratado. A janela localizada no canto mais inferior do programa contém a tabela cruzada do
contexto formal empregado como exemplo no Capı́tulo 2, referente a animais
e suas propriedades.
Como pode ser observado na figura, o menu selecionado na barra de ferramentas permite que o usuário crie novos contextos formais e também permite
que contextos formais sejam carregados de arquivos prévia e corretamente estruturados (conforme anteriormente mencionado). E as alterações efetuadas
nos contextos formais podem ser salvas tanto em arquivos “.sph” como “.cxt”
(esse último formato é suportado por outros programas).
Sophia também permite que os contextos formais nele apresentados tenham suas tabelas cruzadas alteradas durante o uso do próprio programa.
Sua interface gráfica fornece ferramentas para adicionar ou remover objetos
ou atributos, para também renomear objetos ou atributos ou o próprio contexto formal e também para alterar o conjunto de incidência, marcando ou
desmarcando as células da tabela cruzada.
Figura 3.2: Janela do “Sophia” para reticulados conceituais.
A Figura 3.2 retrata um segundo instante na execução de Sophia, no
qual o reticulado conceitual de determinado contexto formal é apresentado
CAPÍTULO 3. APLICAÇÕES
23
por meio de uma tabela ao invés do convencional diagrama de linhas. O
contexto formal considerado na figura é novamente o exemplo do Capı́tulo 2,
estando sua tabela cruzada presente na primeira aba da janela em questão
(onde se lê “Tabela”) e seu reticulado conceitual na segunda aba (onde se lê
“Conceitos”).
Uma vez determinado um conceito formal, o usuário simplesmente precisa
selecionar a funcionalidade de montar seu reticulado conceitual, presente no
menu cujo rótulo é “Conceitos”. Uma tabela - parcialmente coberta na figura
por uma janela (a ser mencionada) - apresenta o reticulado conceitual daquele
contexto formal, sendo suas linhas os conceitos formais (i.e. nós do diagrama)
e estando suas colunas apresentando informações a respeito de cada conceito
formal.
Na figura, a janela que parcialmente cobre a tabela do reticulado conceitual foi gerada após o usuário selecionar a funcionalidade do menu “Conceitos” para procurar informações no reticulado conceitual. Tal funcionalidade facilita a exploração da tabela em questão, permitindo que o usuário
consiga as seguintes informações: vizinhos de nós selecionados (inferiores ou
superiores), extensões ou intenções de selecionados nós (completas ou reduzidas2 ).
O processo de trabalho aqui adotado envolvia programas de planilha
eletrônica e aqueles que montam diagramas de linhas, além do próprio Sophia.
Contextos formais eram estruturados em programas de planilha eletrônica,
nos quais os conjuntos de incidência eram representados por “0” ou “1”,
conforme anteriormente mencionado. Sophia era usado para alterar contextos formais, fornecer informações a respeito dos reticulados conceituais e para
gerar arquivos cujo formato é suportado por outros programas de Análise Formal de Conceitos. Tais programas eram empregados somente para a geração
de diagramas de linhas, umas vez que Sophia permite uma manipulação mais
facilitada dos contextos formais.
O programa empregado para a geração de tais diagramas é chamado
“Toscana” e pode ser gratuitamente obtido na Internet no seguinte endereço:
http://toscanaj.sourceforge.net/. Na verdade, Toscana é um renomado conjunto de programas que lidam com diagramas de linhas. Tais programas são empregados e recomendados na grande maioria dos trabalhos de
Análise Formal de Conceitos, pois oferecem diversos modos de explorar diagramas de linhas. As figuras de diagramas de linhas mostradas nesse trabalho
foram geradas em tais programas3 .
2
Extensões e intenções reduzidas correspondem aos rótulos que aparecem no diagrama
de linhas e serão melhor abordadas adiante.
3
Demais figuras aqui mostradas (como a Figura 3.10) foram geradas no programa
chamado “Dia”, disponı́vel em http://dia-installer.sourceforge.net/.
CAPÍTULO 3. APLICAÇÕES
24
Nos próximos tópicos, a aplicabilidade da Análise Formal de Conceitos
em problemas inerentes à Ciência da Computação será investigada, conforme
mencionado na abertura desse capı́tulo. É planejado que, em trabalhos futuros, Sophia tenha seu processo de desenvolvimento continuado de modo
a automatizar as aplicações sugeridas a seguir. Dentre as melhorias planejadas para Sophia, a primeira envolve a geração automática de relatórios que
descrevam em linguagem natural diversas informações referentes aos reticulados conceituais. Essa e demais melhorias serão apresentadas em detalhes
no Capı́tulo 4, quando forem planejados os trabalhos futuros.
3.2
Redes Neurais Artificiais
Redes Neurais Artificiais são consideradas uma poderosa ferramenta computacional dentro do ramo da Inteligência Artificial, na Ciência da Computação. Sua principal vantagem reside na capacidade de solucionar problemas inéditos, uma vez que tenham aprendido problemas similares em um
primeiro momento. Sua estrutura é composta por unidades denominadas
neurônios artificiais, dispostos em camadas na rede neural, conectados por
entradas e saı́das, atribuı́das de pesos. Detalhes a respeito da topologia ou
do funcionamento das Redes Neurais Artificiais não pertencem ao escopo
do trabalho, portanto é presumido que o leitor conheça ao menos aspectos
básicos a respeito desse ramo da Inteligência Artificial.
Redes Neurais4 são comumente aplicadas, e com sucesso, a problemas cujas variáveis possuam comportamento linear ou não. Como exemplo, [ZPS+ 03]
propõe o emprego de Redes Neurais na modelagem de coletores solares. A
Figura 3.3 mostra um esquema da estrutura de um coletor solar. Dependentemente de fatores ambientais e estruturais, a água fria presente no tanque,
localizado na parte superior da estrutura, é aquecida na placa coletora, em
um processo no qual a água circula constante e naturalmente entre tanque e
placa, devido à diferença de densidade da água fria para a aquecida.
Uma vez que as Redes Neurais têm capacidade para modelar coletores
solares, inclusive estimando seu desempenho em possı́veis situações futuras,
qual o emprego da Análise Formal de Conceitos em tal situação? O problema
reside no fato do conhecimento adquirido pela Rede Neural se encontrar
armazenado no formato de pesos das conexões entre seus neurônios. Não
é razoável esperar que o ser humano interprete tais valores de pesos para
compreender qual conhecimento a Rede Neural armazena. É para solucionar
tal problema que é aqui proposto o emprego da Análise Formal de Conceitos,
4
O termo “Artificiais” será omitido de agora em diante, ficando convencionado que o
trabalho não está se referindo a redes neurais biológicas.
CAPÍTULO 3. APLICAÇÕES
25
Figura 3.3: Esquema da estrutura de coletores solares.
mas é necessário primeiramente relatar o processo de modelagem de coletores
solares por meio de Redes Neurais.
A eficiência do coletor solar é a variável mais importante na maioria das
aplicações com tais sistemas. Tal variável pode ser calculada após ter sido
mensurada a temperatura de saı́da água. Esta última, por sua vez, depende,
conforme já mencionado, de fatores ambientais e estruturais. Como somente
um coletor solar está sendo considerado para a modelagem com Redes Neurais, os aspectos estruturais são valores constantes, logo, desconsiderados
como possı́veis entradas da Rede Neural. Desse modo, “temperatura de entrada da água” (Tin ), “temperatura ambiente” (Tamb ) e “irradiação solar”
(G) foram tidas como entradas da Rede Neural e “temperatura de saı́da da
água” (Tout ), como saı́da, como representa a Figura 3.4.
Figura 3.4: Esquema da estrutura de coletores solares.
Durante três dias de um momento no ano apropriado para mensurações
envolvendo coletores solares, aproximadamente 600 dados foram coletados
envolvendo as variáveis de entrada e de saı́da da Rede Neural. Como constatado em [ZPS+ 04], a redução da quantidade de dados a serem empregados
no treinamento da Rede Neural não prejudica o desempenho da mesma, se
o novo e reduzido conjunto de treinamento contiver dados que representem
de modo abrangente o processo em questão. Logo, o conjunto de treinamento original contendo aproximadamente 600 dados foi reduzido para um
CAPÍTULO 3. APLICAÇÕES
26
novo conjunto com somente 20 dados bastante representativos, por meio do
conhecido algoritmo “K-means” de clustering.
Alguns autores [ZPS+ 03, ZPS+ 04] consideram três etapas quando da
aplicação de Redes Neurais. A primeira é denominada fase de treinamento,
quando o chamado conjunto de treinamento, contendo exemplos do problema,
é apresentado para a Rede Neural. Uma vez treinada, a etapa denominada
fase de validação pode ser executada, quando situações inéditas do problema
são apresentadas à Rede Neural com o objetivo de analisar sua capacidade
de generalização, ou seja, de solucionar problemas não considerados durante
o processo de treinamento. Caso a Rede Neural atenda aos requisitos da segunda etapa, a fase de uso pode ser executada, na qual a Rede Neural pode
estimar saı́das para situações futuras.
O conjunto de treinamento contendo 20 dados foi apresentado à Rede
Neural, cuja topologia compreende 7 neurônios na camada oculta e 1 neurônio
na camada de saı́da. Após ser treinada com o mais conhecido algoritmo de
treinamento (“Backpropagation”), valores aceitáveis de erros foram observados na saı́da, como mostra a Tabela 3.1.
Tabela 3.1: Erros obtidos após fase de treinamento.
Erro mı́nimo (◦ C)
0.01717
Erro máximo (◦ C)
0.92959
Erro médio (◦ C)
0.33199
Para a fase de validação, foram aleatoriamente selecionados 30 dados do
conjunto de treinamento original (o que representa 5% em 600 elementos). E
valores de erro aceitáveis foram também observados na produção de saı́das
para o conjunto de validação contendo 30 situações inéditas, como mostra a
Tabela 3.2.
Tabela 3.2: Erros obtidos após fase de validação.
Erro mı́nimo (◦ C)
0.03024
Error máximo (◦ C)
1.35995
Erro médio (◦ C)
0.45854
Como a Rede Neural calculou a maioria das saı́das com menos de 1◦ C
de erro tanto na fase de treinamento como na de validação, tal Rede Neural
pode ser empregada na estimativa do comportamento do coletor solar em
situações futuras. Entretanto, o que interessa no momento é a extração de
conhecimento da Rede Neural treinada. Como pode ser descrito o conhecimento adquirido por uma Rede Neural treinada, sem que tal informação
esteja somente no formato de pesos de conexões, que foram ajustados durante
a fase de treinamento? A Análise Formal de Conceitos é aplicada desse mo-
CAPÍTULO 3. APLICAÇÕES
27
mento em diante, atuando no processo de extração de regras que representem
o conhecimento da Rede Neural.
O procedimento aqui descrito é proposto em recentes pesquisas [VZS+ b,
VZS+ a]. Primeiramente, a Rede Neural treinada recebe novamente o conjunto de treinamento contendo 20 elementos. A Tabela 3.3 mostra os valores
envolvidos nessa fase de operação, estando na última coluna as saı́das produzidas pela Rede Neural.
Tabela 3.3: Resultados da operação da Rede Neural. As saı́das produzidas
são mostradas na última coluna.
Índice
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
Tamb (◦ C)
24
24.3
25
24.5
24.1
24
23.4
24.6
24.8
24.8
23
24.9
23.2
24.4
24.8
23.1
25.9
25.9
26.4
27
Tin (◦ C)
20.8
21
23.7
22.6
23.2
23
22.8
23.7
23
25.7
27.6
27.2
30.2
32.8
32.6
33
33.8
34.9
37.7
38.1
G
769
811.8
770.1
871.8
908.6
925
960.3
884.8
939.6
899.5
907.6
893.6
912.5
868.8
877.5
933.2
996.8
1048.8
1041.2
1043.5
Tout (◦ C)
27.2008
27.8893
29.3379
29.7317
30.4942
30.5380
30.6448
30.7345
31.0864
32.5756
33.4200
33.7477
35.7758
37.8067
37.9606
38.4400
41.1628
42.6359
44.4215
44.8137
Para determinar um reticulado conceitual B(G, M, I) e seu respectivo
diagrama de linhas, é necessário converter a Tabela 3.3 em um ambiente
binário, no qual as células são marcadas por “×” ou não. Portanto, as 4
variáveis Tamb , Tin , G e Tout foram divididas em 4 faixas cada uma, como
mostra a Tabela 3.4. Desse modo, o contexto formal mostrado na Tabela
3.55 foi determinado, mediante a conversão da Tabela 3.3 em um ambiente
binário, segundo as faixas apresentadas na Tabela 3.4.
Uma vez determinado o contexto formal K := (G, M, I), no qual o conjunto G de objetos contém as 20 situações de treinamento e de operação, e o
conjunto M de atributos contém os 16 atributos determinados (Tamb [1 − 4],
Tin [1 − 4], G [1 − 4], Tout [1 − 4]), o diagrama de linhas pode ser desenhado.
A Figura 3.5 retrata tal diagrama de linhas, que contém 35 conceitos formais
5
O contexto formal da Tabela 3.5 possui 16 atributos, mas devido à limitação de espaço
fı́sico da página, a tabela mostra os valores assumidos em cada variável por cada objeto.
CAPÍTULO 3. APLICAÇÕES
28
Tabela 3.4: Faixas de valores para cada variável.
Atributos
Tamb 1
Tamb 2
Tamb 3
Tamb 4
Tin 1
Tin 2
Tin 3
Tin 4
G1
G2
G3
G4
Tout 1
Tout 2
Tout 3
Tout 4
Faixas
[23, 24[
[24, 25[
[25, 26[
[26, 27]
[20, 25[
[25, 30[
[30, 35[
[35, 40]
[769, 839[
[839, 909[
[909, 979[
[979, 1049]
[27, 31[
[31, 35[
[35, 39[
[39, 60]
(A, B). É importante mencionar que, ao invés de rotular os nós com os nomes
dos objetos (na verdade, os nomes são números [1 − 20]), são mostradas as
quantidades de objetos em tais nós.
Figura 3.5: Diagrama de linhas da Rede Neural treinada.
O processo de extração de regras do diagrama de linhas procura observar os relacionamentos dos atributos. Atributos que aparecem no mesmo
vértice (e.g. Tamb 4 e Tin 4, G4 e Tout 4) indicam que objetos que contenham
um desses atributos necessariamente também contêm os demais atributos
daquele vértice. E atributos conectados por arestas (e.g. G1, Tout 1, Tin 1)
indicam relacionamentos unidirecionais, nos quais os atributos dos vértices
inferiores implicam na presença dos atributos dos vértices superiores aos quais
estão conectados. Esse último relacionamento é fundamentado na norma de
CAPÍTULO 3. APLICAÇÕES
29
Tabela 3.5: Contexto formal da Rede Neural treinada. Conforme já mencionado, as 4 variáveis Tamb , Tin , G e Tout representam 16 atributos, sendo 4
para cada variável.
Índice
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
Tamb
2
2
3
2
2
2
1
2
2
2
1
2
1
2
2
1
3
3
4
4
Tin
1
1
1
1
1
1
1
1
1
2
2
2
3
3
3
3
3
3
4
4
G
1
1
1
2
2
3
3
2
3
2
2
2
3
2
2
3
4
4
4
4
Tout
1
1
1
1
1
1
1
1
2
2
2
2
3
3
3
3
4
4
4
4
conceitos formais vizinhos (A1 , B1 ) ≤ (A2 , B2 ) que diz que B2 ⊆ B1 .
Considerando as últimas observações, é possı́vel que sejam estabelecidas
proveitosas regras. Por meio de regras que mais se aproximem da linguagem
natural, o ser humano compreende com mais facilidade qual conhecimento a
Rede Neural armazena. Eis as regras observadas no diagrama de linhas da
Figura 3.5:
Tin 4 ⇒ Tamb 4
Tamb 4 ⇒ Tin 4
Tamb 4 ∨ Tin 4 ⇒ G4 ∧ Tout 4
Tout 1 ⇒ Tin 1
Tin 2 ⇒ G2 ∧ Tout 2
G1 ⇒ Tout 1 ∧ Tin 1
Tout 3 ⇒ Tin 3
Tout 4 ⇒ G4
G4 ⇒ Tout 4
Observando as regras, até mesmo pessoas que desconheçam detalhes do
domı́nio da aplicação são capazes de, no caso abordado, compreender o comportamento do coletor solar modelado. Seria possı́vel, por exemplo, constatar com extrema facilidade que as mais baixas temperaturas de saı́da da
CAPÍTULO 3. APLICAÇÕES
30
água acontecem quando a temperatura de entrada da água também é baixa,
conforme diz a regra Tout 1 ⇒ Tin 1. Obviamente, tais constatações são verdadeiras quando o coletor solar segue normas padronizadas de montagem e
operação. Entretanto, é provável que seja questionado o quão fiel é o diagrama de linhas à realidade modelada, uma vez que são considerados somente
20 dados. A garantia de tal fidelidade reside no fato de que os dados foram
selecionados por meio de clustering, logo, representam todos os dados de
modo abrangente. Um meio de analisar tal garantia é operando a mesma
Rede Neural com novos valores, a fim de observar se as faixas de valores
obtidas respeitam as regras. Tal procedimento está sob desenvolvimento.
3.3
Mineração de Dados
A informação desempenha papel essencial tanto em âmbito pessoal como
profissional, sendo obtida pela interpretação de dados devidamente organizados. Devido à sua importância, os pesquisadores sempre estudam metodologias para gerenciar a informação e dela extrair conhecimento, como o conhecido processo de Descoberta de Conhecimento em Bases de Dados (KDD Knowledge Discovery in Databases). KDD é definido em [FSS96] como processo cujo propósito é a extração de proveitoso conhecimento dos dados. A
Mineração de Dados (Data Mining), importante passo no KDD, é definida em
[FSS96] como aplicação de algoritmos especı́ficos para a extração de padrões
dos dados.
Bases de dados cujos conteúdos descrevem situações reais são aqui mencionadas com o propósito de analisar a viabilidade do emprego da Análise
Formal de Conceitos como alternativa à tradicional Mineração de Dados. O
exemplo aqui considerado contém dados referentes a taxas de mortalidade
brasileiras de 2000. Devido a limitações fı́sicas de espaço, tal base de dados
não é aqui mostrada, mas todos os estados brasileiros são nela registrados:
Norte:={AC, AM, AP, PA, RO, RR, TO};
Nordeste:={AL, BA, MA, CE, PB, PE, PI, RN, SE};
Sul:={PR, RS, SC};
Sudeste:={ES, MG, RJ, SP};
Centro Oeste:={DF, GO, MS, MT}.
Do mesmo modo que os estados são referenciados por seus respectivos
acronônimos, as causas de mortalidade também receberam rótulos, a saber:
CAPÍTULO 3. APLICAÇÕES
31
mortalidade infantil (a), neoplasia (tumores) (b), problemas no sistema circulatório (c), diabete (d), cirrose (e), AIDS (f ), acidentes com transportes
(g), homicı́dios (h) e suicı́dios (i).
De modo a converter a base de dados original para um contexto formal,
a mediana de cada taxa de mortalidade em todos os estados brasileiros foi
calculada. Para que, no contexto formal gerado, um determinado objeto (i.e.
estado) possua um determinado atributo (i.e. mortalidade), é necessário
que, na base de dados, sua taxa naquela mortalidade seja igual ou superior à
mediana daquela taxa no Brasil. Ou seja, o contexto formal, apresentado na
Tabela 3.6, considera estados como objetos, mortalidades como atributos e
adiciona ao conjunto de incidência taxas de mortalidade iguais ou superiores
à mediana nacional, ou seja, altas taxas de mortalidade.
Tabela 3.6: Contexto formal das taxas de mortalidade brasileiras.
AC
AL
AM
AP
BA
CE
DF
ES
GO
MA
MG
MS
MT
PA
PB
PE
PI
PR
RJ
RN
RO
RR
RS
SC
SE
SP
TO
a
×
×
×
×
×
×
b
c
d
×
×
×
×
×
×
×
×
×
×
×
×
×
e
f
g
h
×
×
×
×
×
i
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
×
O reticulado conceitual do contexto formal KBrasil (contexto da Tabela
3.6) foi determinado e contém 73 conceitos formais (A, B). Como retratar
um diagrama de linhas com tamanha quantidade de nós é inapropriado nesse
trabalho (devido ao tamanho fı́sico das folhas), um contexto formal reduzido
KN ordeste , contendo somente os estados brasileiros da região nordeste, será
considerado de agora em diante. Seu reticulado conceitual contém 14 con-
CAPÍTULO 3. APLICAÇÕES
32
ceitos formais (A, B), conforme mostra seu diagrama de linhas, retratado na
Figura 3.6. É importante mencionar que mesmo grandes diagramas de linhas
podem ser explorados, mas foi decidido empregar diagramas menores nesse
trabalho por questões de espaço.
Figura 3.6:
brasileiro.
Diagrama de linhas de taxas de mortalidade no nordeste
Algumas inferências são intuitivas quando se observa o diagrama de linhas. Por exemplo, a mortalidade infantil (atributo a) pertence ao elemento
unidade do diagrama e, por esse motivo, é possuı́da por todos os objetos.
Como o nordeste é a região brasileira na qual problemas sociais e econômicos
são alarmantes, é real e infelizmente esperado que seus estados tenham alta
taxa de mortalidade infantil. Entretanto, esse trabalho não pretende abordar aspectos tão intuitivos, mas discutir a Análise Formal de Conceitos como
metodologia de Mineração de Dados. Algumas pesquisas [SZa] já tentaram
algo parecido, mas a abordagem aqui empregada é retirada de [SZb].
Um dos recursos de Mineração de Dados é chamado modelagem de
dependência, definido em [FSS96] como:
Modelagem de dependência consiste em encontrar um modelo que
descreva dependências significantes entre as variáveis. Modelos
de dependência existem em dois nı́veis: o nı́vel estrutural do modelo especifica (usualmente em forma gráfica) como as variáveis
CAPÍTULO 3. APLICAÇÕES
33
são dependentes entre si conforme suas posições, enquanto o modelo quantitativo especifica as forças das dependências usando alguma escala numérica.
Diagramas de linha incontestavelmente são modelos de dependência em nı́vel
estrutural, pois as posições dos conceitos formais determinam seus relacionamentos.
Um modo de constatar tal afirmação é por meio das definições de ideal
principal e de filtro principal. Considerando um conceito formal (A, B), seu
ideal principal ((A, B)] e seu filtro principal [(A, B)) são definidos pela Teoria
de Reticulados como:
(A, B) := (C, D) ∈ B(G, M, I) | (C, D) ≤ (A, B)
(A, B) := (C, D) ∈ B(G, M, I) | (C, D) ≥ (A, B)
Em reticulados conceituais (representados por diagramas), ideal e filtro
principais desempenham um importante papel. Ambos podem ser aplicados
para determinar extensão A e intenção B de qualquer conceito formal (A, B):
A := g ∈ extensao de qualquer (A, B)
B := m ∈ intencao de qualquer (A, B)
Tais regras confirmam que a estrutura de reticulados conceituais é realmente similar à da orientação por objetos. E a maneira como diagramas
de linha representam tais estruturas hierárquicas confirma seu papel como
modelos de dependência.
Classificação é também um método de Mineração de Dados, definido
em [FSS96] como:
Classificação é determinar uma função que mapeie cada dado em
uma de diversas classes definidas.
Portanto, as classes devem ser definidas antes que o método de classificação
comece. Nesse trabalho, é proposto que definir uma classe consiste em definir
quais atributos são desejados de serem possuı́dos por objetos.
Uma função que determine quais objetos têm o atributo da classe definida
deve ser proposta. Por exemplo, o usuário pode determinar que a classe de
interesse deve conter alta taxa de homicı́dio, selecionando o nó com o atributo
h. Nesse trabalho, a solução proposta consiste em determinar quais objetos
têm o atributo de interesse (i.e. h, no caso). Observando a Figura 3.6,
os objetos em nós inferiores que alcancem o nó selecionado constituem a
resposta.
CAPÍTULO 3. APLICAÇÕES
34
Entretanto, os rótulos de objetos e atributos aparecem somente uma vez
nos diagramas de linha porque, conforme já mencionado, tais diagramas estão
em modo reduzido. Na verdade, cada nó representa um conceito formal
(A, B), com extensão A e intenção B. Portanto, quando o usuário seleciona
um nó, determinando qual atributo lhe interessa, o problema da classificação
tem sua resposta na extensão do próprio nó. No exemplo mencionado, o nó
h contém:
(A, B) := {AL, SE, P E}, {a, d, h}
Tal solução parece ser restrita a problemas cujas classes são definidas
contendo apenas atributos presentes no mesmo nó. Uma solução genérica,
baseada na definição de ı́nfimo, pode solucionar problemas de classificação
que envolvam quaisquer quantidades de nós selecionados. Por exemplo,
alguém pode desejar classes de estados que contenham tanto alta taxa de
homicı́dio como alta taxa de suicı́dio e, para isso, seleciona os nós h e i. A
função “Classes” é proposta aqui para solucionar esse problema, recebendo
os nós selecionados (i.e. conceitos formais) como parâmetros e retornando os
objetos que tenham os atributos de tais nós6 :
Classes
[
^
(At , Bt ) = Extensao
(At , Bt )
t∈T
t∈T
No exemplo envolvendo os nós h e i:
Classes
{AL, SE, P E}, {a, d, h} , {CE, P E}, {a, b, c, i} =
o
{AL, SE, P E}, {a, d, h} , {CE, P E}, {a, b, c, i}
=
= Extensao {P E}, {a, b, c, d, e, f, h, i} = {P E}
= Extensao
^n
Em outras palavras, o problema da classificação é solucionado extraindo a
extensão do ı́nfimo dos nós selecionados, sendo que tais nós contêm em suas
intenções os atributos que interessam àquele que solicitou a classificação.
Obviamente, a função proposta denominada “Classes” retorna apenas os objetos de interesse, mas aqueles objetos que não pertençam a esse retorno
constituem outra classe. Portanto, a função “Classes” pode ser melhorada,
retornando ambas as classes (i.e. objetos que atendam à classe definida e
aqueles que estão fora de tal definição):
Classes
[
t∈T
n
^
^
o
(At , Bt ) = Extensao
(At , Bt ) , G − Extensao
(At , Bt )
t∈T
t∈T
Finalmente, o método clustering , definido em [HK01] como:
6
“Extensao” e “Intencao” são funções que recebem um conceito formal (A, B) como
parâmetro e respectivamente retornam sua extensão A e sua intenção B.
CAPÍTULO 3. APLICAÇÕES
35
O processo de determinar grupos contendo objetos similares é
chamado clustering. Um cluster é uma coleção de objetos que
são similares entre si e discrepantes em relação aos objetos dos
demais clusters.
Diagramas de linhas agrupam em seus nós aqueles objetos que têm os
mesmos atributos, mas clusters não devem conter apenas objetos iguais, mas
também similares. A primeira tentativa de determinar tais conjuntos em
diagramas de linhas considerando a similaridade pode consistir em agrupar
nós vizinhos em um mesmo cluster. Entretanto, tal abordagem considera
similaridade como quantidade de atributos em comum, o que também pode
ocasionar resultados inconsistentes.
Considerar faixas de valores como atributos é proposto aqui para solucionar o problema da similaridade. A Tabela 3.6 implicitamente considera
tais faixas como atributos, uma vez que os estados apresentam alta ou baixa
taxa de mortalidade para cada atributo. Quando lidando com faixas de valores, os nós do diagrama de linhas contêm objetos cujos atributos possuem
valores próximos, ou seja, são objetos cujas propriedades são similares, não
iguais.
Assumindo que objetos em um mesmo nó são similares quando os atributos do contexto formal são organizados em faixas de valores, clusters podem
ser considerados como equivalentes aos próprios nós. É importante mencionar
que somente são clusters aqueles nós que, mesmo com rótulos reduzidos (i.e.
quando nomes de objetos e de atributos aparecem somente uma vez no diagrama), possuı́rem rótulos de objetos. Um conceito formal (A, B) tem seu
rótulo reduzido segundo a função:
o
n
ReducaoRotulo (A, B) =
g∈A|g∈
/ Extensao (C, D) ∀ (C, D) ≤ (A, B) ,
n
o
m∈B |m∈
/ Intencao (E, F ) ∀ (E, F ) ≥ (A, B)
Em outras palavras, nós com rótulos reduzidos mostram somente objetos
que não pertencem à extensão de nenhum subconceito e somente atributos
que não pertencem à intenção de nenhum superconceito. Portanto, clusters
são aqui propostos como conjuntos de objetos cujos rótulos aparecem no
mesmo nó, quando com rótulos reduzidos. A função proposta “Clusters”
recebe um reticulado conceitual B(G, M, I) como parâmetro e retorna seu
conjunto de clusters:
n
Clusters B(G, M, I) = Extensao ReducaoRotulo (A, B) |
o
| Extensao ReducaoRotulo (A, B) 6= ∅ , ∀ (A, B) ∈ B(G, M, I)
CAPÍTULO 3. APLICAÇÕES
36
O reticulado conceitual de KN ordeste , representado pela Figura 3.6, pode
ser recebido pela função “Clusters” como parâmetro. Em tal caso, o conjunto
G contém todos os estados brasileiros do nordeste, o conjunto M contém
todas as causas de mortalidade e o conjunto I contém as ocorrências de alta
taxa de mortalidade, implicitamente dividindo os atributos em faixas (i.e.
baixa ou alta taxa). A função “Clusters” retornaria:
Clusters B(KN ordeste ) = {AL}, {BA, M A, P I}, {CE}, {P B}, {P E}, {RN }, {SE}
Objetos pertencentes ao mesmo cluster não simplesmente têm os mesmos atributos, eles compartilham valores similares para cada atributo. É
importante mencionar que quando mais de duas faixas (baixa ou alta) forem
necessárias, cada faixa deve corresponder a um atributo distinto. Mas para
esse exemplo, os atributos já denotam as faixas de valores dos objetos do
cluster, como no exemplo {BA, MA, PI}, simbolizando valores altos como
“+ ” e baixos como “− ”:
M ortalidade em {BA, M A, P I} = {a+ , b− , c− , d− , e− , f − , g − , h− , i− }
Um novo contexto formal foi determinado para avaliar a função “Clusters”, unindo estados do sul e do nordeste como objetos. Enquanto o sul
apresenta a melhor qualidade de vida no Brasil, a situação oposta pode ser
notada no nordeste. A Figura 3.7 apresenta o diagrama de linhas do novo
contexto formal. É interessante observar que ambas as regiões consideradas
não compartilham clusters. Muito pelo contrário, os estados do sul pertencem
a um cluster exclusivo, por compartilharem similares taxas de mortalidade,
devido à melhor situação social e econômica naquela região:
M ortalidade em {P R, RS, SC} = {a− , b+ , c+ , d+ , e+ , f + , g + , h− , i+ }
3.4
Bancos de Dados
Elaborar uma metodologia que empregasse Análise Formal de Conceitos com
o propósito de converter modelos relacionais de bancos de dados para modelos orientados por objeto era um dos objetivos iniciais nesse trabalho. Foram
estudados alguns trabalhos [Fon] que propõem metodologias para tal conversão empregando recursos que não fossem a Análise Formal de Conceitos.
Contudo, tal objetivo inicial foi adiado para trabalhos futuros, pois elaborar uma metodologia que efetuasse a tarefa mencionada de modo consistente
demandaria mais tempo para estudos detalhados. Uma vez que o tempo
disponı́vel era insuficiente, foi decidido não apresentar propostas incompletamente testadas, sujeitas a resultados inconsistentes.
CAPÍTULO 3. APLICAÇÕES
37
Figura 3.7: Diagrama de linhas de taxas de mortalidade no nordeste e sul
brasileiros.
Embora o objetivo inicial tenha sido adiado, esse tópico apresenta um
trabalho encontrado [HPLC], cuja proposta é converter esquemas lógicos de
bancos de dados para esquemas conceituais. Um estudo de caso a respeito
dessa metodologia foi efetuado, descrevendo a mesma nesse tópico e observando suas vantagens e desvantagens. É esperado que tal trabalho auxilie
na tarefa de conversão para modelos orientados por objeto, pois esquemas
conceituais - resultado da metodologia estudada - podem ser transformados
tanto em modelos relacionais como modelos orientados por objeto. A seguir,
parte do trabalho estudado é brevemente descrita:
Análise Formal de Conceitos é empregada na engenharia reversa de bancos
de dados, segundo metodologia proposta em [HPLC]. A engenharia reversa
de bancos de dados é um processo composto por duas etapas:
Análise de dados: O esquema lógico é semanticamente aprimorado, sendo
recuperadas informações a seu respeito, não explicitamente declaradas
nele, como chaves candidatas e dependências de inclusão.
Abstração conceitual: O aprimorado esquema lógico obtido na análise de
dados é convertido para conceitual, seja esse último um Diagrama Entidade Relacionamento ou um Diagrama de Classes.
CAPÍTULO 3. APLICAÇÕES
38
Em outras palavras, enquanto o processo de modelagem de bancos de
dados apresenta o esquema conceitual sucedido pelo esquema lógico, a engenharia reversa percorre o caminho oposto, convertendo o esquema lógico
para o conceitual por meio das etapas de análise de dados e de abstração
conceitual. É na fase de abstração conceitual que a Análise Formal de Conceitos é inserida, tendo seu diagrama de classes empregado como ferramenta
para efetuar tal conversão. O trabalho [HPLC] enumera diversos possı́veis
empregos da Análise Formal de Conceitos na engenharia reversa de bancos
de dados, mas implementa apenas aquele que converte um esquema lógico
para um Diagrama de Classes.
É presumido aqui que o leitor conheça fundamentos básicos de Bancos
de Dados e também da Linguagem Unificada de Modelagem (UML - Unified
Modeling Language). Questões referentes a ambos os ramos serão aqui explicadas quando consideradas relevantes ao assunto abordado ou importantes
para uma melhor compreensão do leitor.
A Análise Formal de Conceitos, implementada na fase de abstração conceitual, recebe da análise de dados as seguintes informações: listagem de
relações e seus atributos no modelo lógico, chaves estrangeiras, candidatas e
primárias e as dependências de inclusão. Definições a respeito de chaves estrangeiras, candidatas e de dependências de inclusão podem ser encontradas
na literatura de Bancos de Dados [EN02]. É importante mencionar que a fase
de análise de dados requer intensa intervenção humana, pois os resultados
nela obtidos dependem de uma interpretação semântica do esquema lógico.
Já a abstração conceitual é implementada pela Análise Formal de Conceitos,
segundo um processo de duas fases:
Fase 1: É objetivo da primeira fase determinar classes e seus relacionamentos de hierarquia (i.e. especialização e generalização) por meio do
processamento das informações provenientes da análise de dados.
Fase 2: Determinar relacionamentos de associação entre as classes é objetivo
da segunda fase.
O exemplo aqui considerado é similar ao de [HPLC] e apresenta um
possı́vel e simples esquema lógico de banco de dados para uma hipotética
biblioteca, cujos livros são empregados na execução de projetos. Logo abaixo
são enumeradas as relações (i.e. tabelas) do esquema e seus respectivos atributos, sendo precedidos por “@” aqueles que são chaves primárias. E são
enumeradas na Tabela 3.7 as informações do esquema obtidas na fase de
análise de dados.
Autor(@CodigoAutor,Nome,PrimeiroNome)
CAPÍTULO 3. APLICAÇÕES
39
Livro(@CodigoLivro,Titulo,Editora,Resumo)
Autoria(@CodigoLivro,@CodigoAutor)
Exemplar(@CodigoLivro,@NumeroSerie,DataAquisicao,Estado)
Membro(@CodigoMembro,PrimeiroNome,Nome,Telefone)
Endereco(@CodigoEndereco,Logradouro,Cidade)
Projeto(@CodigoProjeto,Nome)
ProjetoExterno(@CodigoProjeto,Duracao)
Emprestimo(@CodigoLivro,@NumeroSerie,DataEmprestimo,
CodigoProjeto,CodigoEndereco)
Devolucao(@CodigoLivro,@NumeroSerie,@DataEmprestimo,
DataDevolucao,CodigoProjeto,CodigoEndereco)
Tabela 3.7: Informações a respeito do esquema lógico da biblioteca. Quando
a restrição é chave estrangeira, a relação da segunda coluna tem o atributo
da última coluna como chave estrangeira proveniente da relação da terceira
coluna. Quando a restrição é dependência de inclusão, a relação da segunda
coluna depende da relação da terceira segundo o atributo da última.
Tipo
Chave Estrangeira
Chave Estrangeira
Chave Estrangeira
Chave Estrangeira
Chave Estrangeira
Chave Estrangeira
Chave Estrangeira
Chave Estrangeira
Chave Estrangeira
Chave Estrangeira
Dependência de Inclusão
Relação 1
Autoria
Autoria
Exemplar
Emprestimo
Emprestimo
Emprestimo
Devolucao
Devolucao
Devolucao
Endereco
ProjetoExterno
Relação 2
Livro
Autor
Livro
Exemplar
Projeto
Membro
Exemplar
Projeto
Membro
Membro
Projeto
Atributos
CodigoLivro
CodigoAutor
CodigoLivro
CodigoLivro, NumeroSerie
CodigoProjeto
CodigoEndereco
CodigoLivro, NumeroSerie
CodigoProjeto
CodigoEndereco
CodigoEndereco
CodigoProjeto
Na primeira fase da abstração conceitual, um primeiro contexto formal
KF ase1 é determinado, contendo as relações do esquema lógico em seu conjunto G e os atributos de tais relações no conjunto M , exceto chaves primárias
ou chaves candidatas. O conjunto I considera relações que contêm os atributos considerados e relações que apresentam dependência de inclusão com
outras relações. Tais informações são melhor descritas de um modo formal,
sendo a operação “Relacao1→Relacao2” lida como “Relacao2 depende da
Relacao1 segundo a dependência de inclusão”:
KF ase1 := G := {Relacao ∈ EsquemaLogico}, M := {Atributo ∈ EsquemaLogico |
| Atributo 6= ChaveP rimaria ∧ Atributo 6= ChaveCandidata},
n
I := (Relacao1, Atributo) ∈ (G × M ) | Relacao1 tem Atributo ∨
o
∨ Relacao2 tem Atributo ∧ Relacao1 → Relacao2, ∀ (Relacao2, Atributo) ∈ (G×M )
CAPÍTULO 3. APLICAÇÕES
40
Com tal norma, é possı́vel determinar o contexto formal KF ase1 apresentado na Tabela 3.8 e seu respectivo diagrama de linhas, retratado na Figura
3.8. Adiante, após a execução da segunda fase da abstração conceitual, será
discutido como diagramas de linhas são convertidos em Diagramas de Classes.
Tabela 3.8: Contexto formal da primeira fase da abstração conceitual.
Rótulos dos atributos (colunas): (a) Nome, (b) PrimeiroNome, (c) Titulo,
(d) Editora, (e) Resumo, (f) DataAquisicao, (g) Estado, (h) Telefone, (i) Logradouro, (j) Cidade, (l) Duracao, (m) DataEmprestimo, (n) CodigoProjeto,
(o) CodigoEndereco, (p) DataDevolucao.
Autor
Livro
Autoria
Exemplar
Membro
Endereco
Projeto
ProjetoExterno
Emprestimo
Devolucao
a
×
×
×
×
b
×
×
c
d
e
×
×
×
f
g
×
×
h
i
j
×
×
l
m
n
o
p
×
×
×
×
×
×
×
×
Na segunda fase da abstração conceitual, um segundo contexto formal
KF ase2 é determinado, contendo as relações do esquema lógico em seu conjunto G e chaves primárias, candidatas ou estrangeiras no conjunto M . O
conjunto I contém pares de relação e atributo, se a relação do par contiver
aquele atributo, no esquema lógico. De um modo formal, KF ase2 pode ser
assim definido:
KF ase2 := G := {Relacao ∈ EsquemaLogico},
M := {Atributo ∈ EsquemaLogico | Atributo = ChaveP rimaria ∨
∨ Atributo = ChaveCandidata ∨ Atributo = ChaveEstrangeira},
I := (Relacao, Atributo) ∈ (G × M ) | Relacao tem Atributo
A Tabela 3.9 apresenta o contexto formal KF ase2 do exemplo aqui considerado, enquanto a Figura 3.9 apresenta seu respectivo diagrama de linhas.
Uma vez montados os diagramas de linhas da fase de abstração conceitual,
o Diagrama de Classes da UML pode ser montado segundo informações dos
diagramas da Análise Formal de Conceitos. O diagrama de linhas da primeira
fase da abstração conceitual determina quais serão as classes do esquema conceitual (i.e. Diagrama de Classes) e seus relacionamentos de generalziação
CAPÍTULO 3. APLICAÇÕES
41
Figura 3.8: Diagrama de linhas da primeira fase da abstração conceitual.
e especialização. Isso é efetuado do seguinte modo: nós (i.e. conceitos formais) representam classes (exceto o nó mais alto e o mais baixo) e arestas
representam hierarquias (i.e. generalização e especialização).
Já o diagrama da segunda fase da abstração conceitual permite que sejam
determinados os relacionamentos de associação entre as classes obtidas no
primeiro diagrama (no caso, 10 classes). O modo como as classes se associarão
é determinado pelas arestas que conectam os nós (i.e. conceitos formais) do
segundo diagrama (Figura 3.9):
Situação 1: Quando um nó é conectado a somente um nó superior e ambos representam classes obtidas no primeiro diagrama, suas respectivas
classes são associadas no esquema conceitual.
Situação 2: Quando um nó é conectado a exatamente dois nós superiores e
ambos os superiores representam classes obtidas no primeiro diagrama,
suas respectivas classes são associadas no esquema conceitual.
Situação 3: Quando um nó é conectado a mais que dois nós superiores e
todos os superiores representam classes obtidas no primeiro diagrama,
todas as classes dos nós superiores são associadas à classe do nó inferior.
No trabalho estudado [HPLC], são detalhados os motivos que levaram a
organizar as classes e seus relacionamentos do modo como foi apresentado
CAPÍTULO 3. APLICAÇÕES
42
Tabela 3.9: Contexto formal da primeira fase da abstração conceitual.
Rótulos dos atributos (colunas): (a) CodigoAutor, (b) CodigoLivro, (c) NumeroSerie, (d) CodigoEndereco, (e) CodigoProjeto, (f) DataEmprestimo.
Autor
Livro
Autoria
Exemplar
Membro
Endereco
Projeto
ProjetoExterno
Emprestimo
Devolucao
a
×
×
b
c
×
×
×
×
d
e
f
×
×
×
×
×
×
×
×
×
×
×
×
×
×
aqui. Entretanto, tais minúcias não serão aqui discutidas, uma vez que são
de autoria alheia. De qualquer modo, é interessante mostrar o Diagrama
de Classes (Figura 3.10) montado após a execução das fases de análise de
dados e abstração conceitual, sendo essa última implementada com recursos
da Análise Formal de Conceitos.
Os relacionamentos de subconceito e superconceito do diagrama de linhas
da Figura 3.8, montado na primeira fase da abstração conceitual, determinam
as hierarquias (i.e. especialização e generalização) no esquema conceitual
mostrado na Figura 3.10. A segunda fase da abstração conceitual tem suas
três situações observadas no diagrama de linhas da Figura 3.9, determinando
todos os relacionamentos de associação mostrados no Diagrama de Classes.
Conforme já mencionado, o exemplo aqui considerado não é idêntico ao do
trabalho estudado, mas é bastante parecido. A diferença consiste em alguns
atributos que aqui foram ignorados, por não serem definidos de modo algum
no trabalho de referência.
O trabalho [HPLC] apresenta uma interessante proposta para solucionar
o problema de engenharia reversa de bancos de dados empregando a Análise
Formal de Conceitos, aproveitando os relacionamentos de diagramas de linhas
para determinar tanto relacionamentos de hierarquia como de associação no
Diagrama de Classes da UML. Entretanto, pequenos problemas foram observados tanto no trabalho de referência como na metodologia proposta. Quanto
ao trabalho, determinadas minúcias referentes à conversão dos diagramas de
linhas para o Diagrama de Classes são simplesmente omitidas, precisando ser
aqui deduzidas. No trabalho estudado, tal omissão implica em determinados
resultados que são simplesmente apresentados sem quaisquer explanações,
como a cardinalidade do Diagrama de Linhas, por exemplo (aqui ignorada).
Quanto à metodologia, um problema observado é de natureza conceitual: por
CAPÍTULO 3. APLICAÇÕES
43
Figura 3.9: Diagrama de linhas da segunda fase da abstração conceitual.
Figura 3.10: Diagrama de Classes obtido com Análise Formal de Conceitos.
exemplo, as especializações de “Projeto” não são razoáveis. Há também associações que poderiam ser aprimoradas: por exemplo, “NovaClasse” poderia
receber as associações de todas suas especializações.
Apesar dos problemas observados, é esperado que a proposta analisada
seja proveitosa para trabalhos futuros. Para o objetivo de converter modelos
relacionais para orientados por objetos, a metodologia apresentada por esses
autores terá seus pontos positivos aproveitados, enquanto as inconsistências
observadas serão minimizadas.
Capı́tulo 4
Conclusões
O Capı́tulo 2 cumpre o objetivo estabelecido de estudar e sumariar a fundamentação teórica da Análise Formal de Conceitos. As definições primordiais do assunto são apresentadas em tal capı́tulo, empregando formalismos
matemáticos e também exemplos, de modo a auxiliar o leitor que desconheça
o assunto a melhor compreender o mesmo. Estudos avançados em pontos
mais complexos da Análise Formal de Conceitos são planejados para trabalhos futuros. Por enquanto, a abordagem teórica do assunto foi bastante
proveitosa para os próprios envolvidos no trabalho, mas é esperado que a
mesma seja também proveitosa para vindouros interessados em ingressar no
estudo dessa área.
O Capı́tulo 3 aborda objetivos de natureza prática. Sophia foi implementado e cumpriu seu compromisso de auxiliar procedimentos da Análise
Formal de Conceitos. É planejado que Sophia continue em desenvolvimento,
cumprindo tarefas mais complexas no processo de gerenciamento do conhecimento, além das funcionalidades básicas que já oferece. Não é cogitado
que, no futuro próximo, Sophia represente reticulados conceituais por meio
de diagramas de linhas, uma vez que diversos programas gratuitos e em constante desenvolvimento já executam tal tarefa. Entretanto, é planejado que
Sophia automatize ao máximo as metodologias aqui apresentadas e a serem
estudadas em trabalhos futuros, oferecendo funcionalidades como a geração
automática de relatórios minuciosos, por exemplo.
O estudo prático continua no Capı́tulo 3, agora abordando a aplicabilidade da Análise Formal de Conceitos em problemas tradicionalmente solucionados pela Ciência da Computação. O primeiro ramo da Ciência da Computação no qual tal aplicabilidade é proposta é o de Redes Neurais Artificiais, atuando na tarefa de extração de regras que descrevam o conhecimento
adquirido por uma rede neural artificial treinada. A metodologia proposta
fornece ao usuário uma descrição compreensı́vel de tal conhecimento, apre44
CAPÍTULO 4. CONCLUSÕES
45
sentando o mesmo como um conjunto de regras e não como valores de pesos
de conexões. Todos os experimentos envolvendo a metodologia proposta geraram resultados satisfatórios.
Entretanto, é importante mencionar os problemas observados durante a
pesquisa que envolve Análise Formal de Conceitos e Redes Neurais Artificiais.
O primeiro requisito é que a rede neural artificial apresente bons resultados
após as fases de treinamento e de validação, pois de nada adiantaria a extração de conhecimento que não fosse consistente. É requisito também que
os conjuntos de dados fornecidos tanto à rede neural artificial como ao contexto formal representem do modo mais fiel possı́vel o processo modelado. Os
dados empregados no exemplo aqui considerado foram cuidadosamente coletados e agrupados por meio de clustering, de modo a garantir que a realidade
não estivesse sendo erroneamente interpretada.
Mineração de Dados é o próximo ramo da Ciência da Computação no
qual foram inseridas aplicações da Análise Formal de Conceitos. Métodos
tradicionais como classificação e clustering foram implementados por meio
de diagramas de linhas, que representavam os dados em questão e os apresentavam de modo mais claro ao usuário. Embora os resultados tenham
sido proveitosos, a pior dificuldade, observada em todas as aplicações aqui
apresentadas, está relacionada ao tamanho do contexto formal considerado.
Dependendo da quantidade de objetos ou de atributos e, principalmente, do
quão irregulares são os valores do conjunto de incidência, explorar diagramas
de linhas passa a ser uma tarefa inviável.
O próximo trabalho planejado tem como objetivo principal implementar,
robusta e completamente, a Análise Formal de Conceitos como um passo do
processo de Descoberta de Conhecimento em Bases de Dados. Devido ao
modo como graficamente representa dados, a Análise Formal de Conceitos
será proposta como alternativa à Mineração de Dados tradicional, embora
ambos possam também ser empregados em conjunto. Em tal trabalho, será
procurado solucionar o problema de tamanho e complexidade do contexto
formal por meio de procedimentos executados nos primeiros passos da Descoberta de Conhecimento em Bases de Dados.
E por fim, foi aqui também proposto que Bancos de Dados empregassem
a Análise Formal de Conceitos. Como o objetivo de converter modelos relacionais de bancos de dados para modelos orientados por objeto não pôde ser
completamente cumprido, foi decidido estudar minuciosamente um trabalho
com propósito similar. O trabalho estudado converte esquemas lógicos para
esquemas conceituais com o emprego da Análise Formal de Conceitos. Pequenas omissões e inconsistências foram observadas em tal trabalho, embora
sua proposta pareça ser bastante proveitosa para trabalhos futuros, quando
o objetivo inicial envolvendo modelos orientados por objeto for retomado.
CAPÍTULO 4. CONCLUSÕES
46
Enfim, a Análise Formal de Conceitos é um assunto em estado incipiente na Ciência da Computação, embora sua aplicação em tal ciência possa
ser bastante valiosa. Sua principal vantagem reside na capacidade de representar a informação por meio de diagramas, cuja compreensão pelo ser humano ocorre de modo intuitivo. Entretanto, a pior limitação nela observada
ocorre quando grandes quantidades de dados de comportamento complexo
são fornecidos como entrada para tais diagramas. Como os diagramas são
fundamentados em princı́pios matemáticos da Teoria de Reticulados, ao invés
de estudar maneiras de alterar tal estrutura, é razoável que sejam estudadas
maneiras de organizar os dados de entrada de modo mais apropriado.
Análise Formal de Conceitos lida com conhecimento e, assim como diversas áreas das ciências que também o fazem, também lida com problemas
extremamente complexos, referentes à fidelidade do conhecimento modelado
à informação fornecida pela realidade. Tentar extrair ou representar conhecimento é uma tarefa bastante ousada e muitos das metodologias que procuram
cumprir tal tarefa não o fazem efetivamente, mas apenas empregam aproximações. Gerenciar conhecimento é uma tarefa que requer o uso do próprio
conhecimento e daı́ surgem os principais problemas. E a Análise Formal
de Conceitos, com sua sólida fundamentação, oferece uma importante contribuição para a execução de tal tarefa.
Referências Bibliográficas
[DP90]
Brian Davey and Hilary Priestley. Introduction to lattices and
order. Cambridge University Press, Cambridge, England, 1990.
[EN02]
Ramez Elmasri and Shamkant Navathe. Sistemas de banco de
dados: Fundamentos e aplicações. Livros Técnicos e Cientı́ficos
Editora, Rio de Janeiro, Brazil, 3 edition, 2002.
[Fon]
Joseph Fong. Converting relational to object oriented databases.
[FSS96]
Usama Fayyad, Gregory Shapiro, and Padhraic Smyth. From data
mining to knowledge discovery in databases. Artificial Intelligence
Magazine, 17(3):37–54, 1996.
[Gan]
Bernhard Ganter. Two basic algorithms in concept analysis.
[Gra98]
George Gratzer. General lattice theory. Birkhäuser Verlag, Basel,
Germany, 1998.
[Gua95]
Nicola Guarino. Formal ontology, conceptual analysis and knowledge representation. International journal of human and computer
studies, 5(43):625–640, 1995.
[Gua98]
Nicola Guarino. Formal ontology and information systems. In
Proceedings of formal ontology in information systems, pages 3–
15, Amsterdam, Netherlands, 1998. IOS Press.
[GW96]
Bernhard Ganter and Rudolf Wille. Formal concept analysis:
Mathematical foundations. Springer Verlag, Berlim, Germany,
1996.
[GW98]
Bernhard Ganter and Rudolf Wille. Applied lattice theory: Formal
concept analysis. In George Grätzer, editor, General lattice theory,
pages 591–605. Birkhäuser Verlag, Basel, Germany, 1998.
47
REFERÊNCIAS BIBLIOGRÁFICAS
48
[HK01]
Jiawei Han and Micheline Kamber. Data Mining: Concepts and
techniques. Morgan Kaufmann Publishers, United States, 2001.
[HPLC]
Carmen Hernández, Félix Prieto, Miguel A. Laguna, and Yania
Crespo. Formal concept analysis support for conceptual abstraction in database reengineering.
[Stu03]
Gerd Stumme. Conceptual knowledge discovery and processing.
International journal of human and computer studies, 59(3):287–
325, 2003.
[SWW98] Gerd Stumme, Rudolf Wille, and Uta Wille. Conceptual knowledge discovery in databases using formal concept analysis methods.
In Proceedings of the second european symposium on principles of
data mining and knowledge discovery, pages 450–458, Heidelberg,
Germany, 1998. Springer Verlag.
[SZa]
João Paulo Domingos Silva and Luis Enrique Zárate. Formal concept analysis for data mining: Discovery of symptoms patterns of
nephrolithiasis. Submitted and under revision.
[SZb]
João Paulo Domingos Silva and Luis Enrique Zárate. Formal concept analysis for data mining: Foundations and applications. Submitted and under revision.
[VZS+ a] Renato Vimieiro, Luis Enrique Zárate, João Paulo Domingos Silva,
Elizabeth Marques Duarte Pereira, and Antônia Sônia Cardoso Diniz. Reasoning based on rules extracted from trained neural networks via formal concept analysis. Submitted and under revision.
[VZS+ b] Renato Vimieiro, Luis Enrique Zárate, João Paulo Domingos Silva,
Elizabeth Marques Duarte Pereira, and Antônia Sônia Cardoso
Diniz. Rule extraction from trained neural networks via formal
concept analysis. Submitted and under revision.
[Wil01]
Rudolf Wille. Why can concept lattices support knowledge discovery in databases? In Proceedings of the concept lattices based
knowledge discovery in databases workshop, pages 7–20, Stanford,
United States, 2001.
[ZPS+ 03] Luis Enrique Zárate, Elizabeth Marques Duarte Pereira, João
Paulo Domingos Silva, Renato Vimieiro, Sérgio Pires, and Antônia
Sônia Cardoso Diniz. Representation of a solar collector via artificial neural networks. In M. H. Hamza, editor, Proceedings of the
REFERÊNCIAS BIBLIOGRÁFICAS
49
third IASTED International Conference on Artificial Intelligence
and Applications, pages 517–522, Benalmádena, Spain, September 2003. International Association of Science and Technology for
Development, ACTA Press.
[ZPS+ 04] Luis Enrique Zárate, Elizabeth Marques Duarte Pereira, João
Paulo Domingos Silva, Renato Vimieiro, Daniel Alencar Soares,
and Antônia Sônia Cardoso Diniz. Optimization of neural networks
training sets via clustering: application in solar collector representation. In Isabel Seruca, Joaquim Filipe, Slimane Hammoudi, and
José Cordeiro, editors, Proceedings of the sixth international conference on enterprise information systems, pages 147–152, Porto,
Portugal, April 2004. Institute for Systems and Technologies of
Information, Control and Communication.