Os progressos recentes nas tecnologias das ciências da
informação tem permitido o armazenamento de vastos conjuntos
de dados em todos os domínios da atividade humana.
Atualmente, assiste-se ao surgimento de diferentes abordagens
para descobrir regularidades, extrair conhecimentos ou
simplificar as informações armazenadas nessas enormes bases de dados.
A nossa abordagem inicialmente consiste em construir automaticamente
grupos homogêneos à partir dessas bases de dados definindo assim novas
entidades, chamadas de objetos simbólicos, que descrevem esses grupos.
A obtenção desses objetos simbólicos deve conservar um máximo de informações,
ao mesmo tempo em que reduz consideravelmente a tabela de dados inicial.
O resultado disso são novas tabelas de dados, chamadas de "tabelas de
dados simbólicos", de estrutura mais complexa pois cada uma das células
dessas tabelas não necessariamente contem, como usualmente, um valor
simples quantitativo ou qualitativo, mas pode conter informações
complexas tais como subconjuntos, intervalos, funções de diferentes
semânticas (probabilista, possibilista, credibilista, etc.) ligadas
eventualmente por dependências e taxonomias.
As colunas dessas tabelas são as variáveis simbólicas, usadas para descrever
os objetos, e as linhas são chamadas de "descrições simbólicas" desses
objetos pois elas não são vetores de valores quantitativos ou categóricos
simples, como é usual. Os objetos dessa tabela podem descrever
indivíduos (observações individuais), levando ou não em conta a
imprecisão ou a incerteza, ou podem descrever itens mais complexos, tais como grupos de indivíduos.
Os dados simbólicos podem ser obtidos pelo menos da seguinte maneira:
Uma vez obtidas as tabelas de dados simbólicos, a fase seguinte consiste na passagem da "mineração de dados"
para a "mineração de conhecimentos" através da extensão das ferramentas usuais de extração de conhecimentos
(classificação supervisionada e não supervisionada, métodos fatoriais, arvores de decisão, etc.)
à esse tipo de objeto bem como a criação de novas ferramentas.
| Estado da Arte |
Os primeiros trabalhos com os princípios básicos da abordagem simbólica em classificação
e métodos afins apareceram no final dos anos 80 (Diday (1987, 1989) e desde então vários
outros trabalhos foram realizados em diversas direções:
Análise Fatorial: Cazes, P. et al (1997) introduziram um método geométrico de classificação não supervisionada (analise de componentes principais) em que os indivíduos são descritos por vetores de intervalos numéricos. Na mesma direção, Verde, R. and De Carvalho, F.A.T. (in press) desenvolveram uma abordagem para levar em conta regras de dependências entre as variáveis descritoras quando da utilização de um método de classificação geométrica não supervisionada. Nagabhushan et al (1995) apresentam uma outra abordagem para a redução de dimensionalidade para dados simbólicos;
Medidas de similaridade e dissimilaridade: Na literatura diversas medidas de dissimilaridade tem sido propostas: Gowda and Diday (1991) apresentaram uma nova medida considerando posição, extensão e conteúdo dos objetos. Ichino and Yaguchi (1994) propuseram uma generalização da métrica de Minkowski para dados complexos. De Carvalho (1994) introduziu medidas de proximidade inspiradas na combinação dos índices de variáveis binarias como uma função de comparação com a métrica de Minowsky como função de agregação, levando em conta regras de dependências entre variáveis. De Carvalho (1998) propôs uma família de medidas que utiliza apenas funções de comparação baseadas no potencial de descrição global. De Carvalho and Souza (1998) apresentaram uma extensão da medida de Ichino and Yaguchi (1994) onde são introduzidas dependências lógicas entre as variáveis e De Carvalho e Souza (in press) combinam histogramas e dependências lógicas para definir medidas de proximidade dependentes do contexto.
Seleção de variáveis: Ichino (1981) apresentou um método de seleção de variáveis não paramétrico aplicável para problemas de reconhecimento padrões baseado em informações estatísticas sobre a estrutura interclasse. Em Ichino (1984) foi descrito um método onde a seleção de variáveis é representada por um problema de programação inteira zero-um. Nos anos seguintes ele generalizou os seus métodos para tratar variáveis simbólicas (1994). Vignes (1991) desenvolveu uma outra abordagem para a seleção de variáveis simbólicas booleanas que foi estendido por Ziani (1996) para levar em conta regras de dependência entre esse tipo de variável;
Estatísticas descritivas: De Carvalho (1995) introduziu a noção de histogramas para dados simbólicos booleanos. Bertrand and Goupil (1998) introduziram métodos para calcular a distribuição de freqüência para uma variável simbólica e estenderam, para cada esse tipo de variável, os conceitos de média, desvio padrão e mediana;
Classificação não supervisionada: Chavent. (1998) propôs um método de agrupamento hierárquica de tipo divisivo para dados simbólicos. Brito (1994) introduziu uma abordagem para a classificação ascendente hierárquica e piramidal. Em Gowda and Diday (1991) encontra-se uma metodologia de agrupamento simbólico para aprendizagem não supervisionada, que foi aplicada a vetores de médias de dados normais multivariados. Gowda and Ravi (1995) apresentam um algoritmo aglomerativo usando conceitos de similaridade e disssimilaridade;
Classificação supervisionada: Rasson and Lissoir (1998) utilizaram uma função de Kernel para medir a concentração de dados simbólicos e solucionar problemas de discriminação. Périnel and Lechevallier (1998) apresentaram regras de decisão usando dados simbólicos do tipo probabilístico. Recentemente Ichino et al (1998) apresentou um classificador simbólico cuja etapa de aprendizagem é baseada em um Grafo de Vizinhos Mútuos e cuja etapa de alocução é baseada em uma medida de similaridade entre as descrições dos grupos e as novas observações a classificar. Souza (1999) apresentou uma modificação do algoritmo de Ichino (1997) e aplicou esse método para imagens SAR (Synthetic Aperture Radar).
| Investigações a Serem Desenvolvidas |
No contexto da abordagem simbólica em classificação e métodos afins, varias iniciativas serão realizadas:
Forma Normal Simbólica
Participantes envolvidos:
Os objetos simbólicos são melhor adaptados do que os objetos usuais para descrever grupos de indivíduos,
levando em conta a variabilidade enquanto disjunção de valores relativos a uma variável. Os objetos
simbólicos são representados geometricamente como hipercubos onde cada dimensão corresponde aos
valores assumidos por cada variável. A presença de regras de dependências entre as variáveis pode
restringir e / ou reduzir as dimensões do espaço de descrição dos objetos simbólicos.
Um objeto simbólico, quando não ha dependências entre as variáveis, descreve um subconjunto do produto
cartesiano que é justamente a definição de uma relação no contexto do modelo relacional em base de
dados. Para estruturar mais eficientemente o esquema da base de dados relacional, E. Codd introduziu
as formas normais, sobretudo a terceira que diz respeito ao caso em que existe dependências funcionais
entre variáveis. As formas normais são usadas em base de dados relacionais para oferecer uma melhor
fatorização dos dados, fornecendo assim uma maneira simples e fácil de atualização dos mesmos.
O objetivo dessa investigação é o desenvolvimento da Forma Normal Simbólica (NSF), inspirada da terceira
forma normal de Codd, que consiste em fatorizar os objetos simbólicos segundo as restrições expressas
por regras entre as variáveis de tal maneira que somente a parte coerente desse objeto é representada
(Csernel, M. and De Carvalho, F. A. T. (1997, 1998)). Com essa forma de organização dos objetos
simbólicos é evitada a combinatória inerente a diversas aplicações tais como o calculo de distancias
e a seleção de variáveis.
A Forma Normal que estamos introduzindo é diferente da usual em base de dados, pois nesse ultimo caso a matriz
de dados é a relação e cada linha da mesma representa um indivíduo. No nosso caso, cada linha da matriz
representa um objeto simbólico, ele mesmo uma relação.
Desejamos nos dois próximos anos trabalhar nas seguintes direções:
caracterizar as regras que exprimem o conhecimento do domínio e avaliar sua influencia sobre a fatorização dos dados;
uma outra via que será explorada é uma vez colocada a tabela de dados sob a forma NSF, desenvolver métodos e algoritmos para o calculo de distancias, classificação, seleção de variáveis discriminantes, etc;
pretendemos também iniciar o desenvolvimento da NSF para o caso em que as regras de dependência entre as variáveis são expressas através de outras estruturas (grafos, reticulados). A colocação de uma tabela de dados simbólicos em NSF é sempre possível se as regras formam uma arvore de decisão. Caso contrario, restarão ainda regras que acompanham os dados. Dentre as varias soluções possíveis, pensamos que a introdução de variáveis suplementares permitira, ao menos em certos casos, a recolocação na forma NSF. Outras estratégias serão também estudadas.
Nos algoritmos de classificação não supervisionada de tipo nuvens dinâmicas, os dados são estruturados
na forma de uma partição em um numero predefinido k de grupos. Esses algoritmos otimizam um critério
que se exprime pela adequação entre os grupos e a maneira de representa-los (Diday and Simon(1976)).
As sementes usuais, em torno das quais os indivíduos são agregados, são substituídas pela representação do grupo
(centros de gravidade, eixos fatoriais, leis de probabilidade, etc.) para ressaltar a inovação principal
desse tipo de algoritmo de classificação não supervisionada: procurar simultaneamente a partição e a
melhor representação dos grupos que constituem essa partição, isto é, procurar simultaneamente uma
partição e uma representação de cada grupo dessa partição tal que minimiza-se um critério de ajustamento
entre essa partição e a representação de cada grupo.
Esse tipo de algoritmo executa iterativamente, até a convergência em um mínimo local que depende da inicialização
dos grupos, duas fases:
O objetivo dessa investigação é avançar no desenvolvimento de métodos e algoritmos de classificação não supervisionada
de tipo nuvens dinâmicas para dados simbólicos.
Em um primeiro trabalho (De Carvalho et al (1999)), propomos um algoritmo de transferencias para o agrupamento
de dados simbólicos boleanos. Como os algoritmos de tipo nuvens dinâmicas, esse tipo de algoritmo faz parte
de uma família mais geral denominada de algoritmos aproximados de vizinhança.
Na fase de representação, o problema de definir uma maneira conveniente de representar os grupos de dados
boleanos foi resolvido considerando que a síntese mais conveniente de um conjunto de dados simbólicos
boleanos é um objeto simbólico derivado dos elementos desse conjunto e que contenha na sua descrição o
conjunto das informações presentes em todas as descrições dos objetos simbólicos boleanos que ele sintetiza.
Os grupos são então representados por protótipos descritos por objetos simbólicos modais, caraterizados
pelas distribuições empíricas das variáveis descritoras dos objetos simbólicos boleanos que eles representam.
Na fase de alocação, o aspecto principal é escolher uma função de proximidade para associar um objeto simbólico
boleano à um grupo segundo a similaridade do mesmo ao protótipo desse grupo representado por um objeto simbólico
modal. A função de proximidade escolhida esta entre as chamadas funções de proximidade dependentes do contexto
(De Carvalho et al (1998)) que permitem levar em conta as relações entre pares de objetos e os objetos restantes.
Nos algoritmos de tipo nuvens dinâmicas, escolhido o critério a otimizar, trata-se de encontrar a melhor representação
que otimiza o critério. A peculiaridade da abordagem proposta em (De Carvalho et al (1999)) é que fixamos a
representação e para aquela representação escolhida procuramos otimizar o critério (minimizar a soma das distancias
entre os elementos de cada grupo e o protótipo do mesmo), isto é, não houve uma procura previa da melhor representação
para o critério escolhido.
Durante a estadia de Francisco de A. T. de Carvalho no INRIA (julho de 99), com a participação ativa de
Yves Lechevallier (INRIA) e Rosanna Verde (Universidade de Nápoles), novos passos nessa investigação foram
realizados nas seguintes direções:
a partir de um índice de proximidade (dependente ou independente do contexto) aplicado a uma tabela de dados simbólicos de semântica qualquer, obter uma matriz de proximidades e aplicar sobre a mesma um algoritmo de tipo nuvens dinâmicas. Nessa abordagem, não ha uma representação explicita dos grupos;
a partir de uma tabela de dados simbólicos de semântica modal, para cada um dos grupos desejados encontrar a melhor representação simbólica também de semântica modal que se ajuste o melhor possível aos elementos do grupo no sentido de um índice de proximidade entre distribuições. Se a tabela de dados for de semântica boleana, transforma-la em uma de semântica modal e seguir o procedimento descrito;
a partir de uma tabela de dados de semântica boleana e de um índice de proximidade dependente do contexto, para cada um dos grupos desejados, encontrar a melhor representação simbólica de semântica modal que se ajusta o melhor possível aos elementos do grupo no sentido do índice de proximidade dependente do contexto.
Estender os resultados obtidos até então para as tabelas de dados boleanos descritas por variáveis ordenadas;
desejamos nos dois próximos anos, pretendemos estender o método de nuvens dinâmicas as tabelas complexas de dados simbólicos boleanos. As variáveis que descrevem esses dados apresentam regras de dependências lógicas entre si e nesse caso o espaço de representação não é mais o produto cartesiano do espaço de representação de cada variável.
Esse método exige à definição de um protótipo para cada grupo e critério à ser otimizado é calculado em função
dessas regras de dependências. Inicialmente, trataremos o caso das tabelas complexas de dados simbólicos boleanos
descritas por variáveis não ordenadas.
Ao integrar as dependências entre variáveis à esses algoritmos, passamos a dispor de um problema de classificação
submetido à restrições, isto é, o protótipo deve pertencer ao espaço de descrições resultante da integração das
dependências lógicas e deveremos utilizar um índice de proximidade dependente da informação local (dependente
do contexto).
A associação de um protótipo à cada uma das classes construídas permite uma interpretação dessa classificação
mas, nesse caso, esse protótipo depende da escolha do espaço de representação e da distancia utilizada.
Afim de dispor de uma representação visual dos resultados, pensamos poder introduzir a noção de carta topologica
no processo de classificação.