O processo de avalia¸c˜ao de similaridade tende a ser bastante complexo e especializado, assim v´arias t´ecnicas e abordagens diferentes s˜ao encontradas na literatura. Neste texto, os v´arios elementos envolvidos nesse processo s˜ao organizados segundo uma abstra¸c˜ao do conceito de espa¸co de similaridade (Barioni et al., 2011). Dados complexos em geral podem ser modelados por meio de conjuntos de atributos que sumarizam o seu conte´udo. Esses conjuntos de atributos s˜ao denominados na literatura como vetores de carac- ter´ısticas, embora n˜ao necessariamente formem um espa¸co vetorial (por exemplo, dados complexos de um mesmo conjunto podem ter vetores de caracter´ısticas de tamanhos dife- rentes) (Traina et al., 2003). Os algoritmos que fazem algum tipo de processamento sobre dados complexos para produzir vetores de caracter´ısticas s˜ao conhecidos como extratores de caracter´ısticas. A similaridade entre dois vetores de caracter´ısticas ´e calculada por meio de uma fun¸c˜ao matem´atica. Em geral, a avalia¸c˜ao de similaridade utiliza fun¸c˜oes de distˆancia, que calculam a dissimilaridade entre dois vetores de caracter´ısticas. Ou seja, quanto menor a distˆancia, maior a similaridade entre os elementos. Uma das van- tagens do uso de fun¸c˜oes de distˆancia ´e que a similaridade entre dois elementos idˆenticos tem um valor definido, indicada como distˆancia zero. A combina¸c˜ao de vetores de ca- racter´ısticas e fun¸c˜oes de distˆancia constituem descritores, que determinam o valor de similaridade entre elementos (Torres et al., 2009). Interpretando cada descritor, ou seja, cada par hS, δi, onde S ´e um dom´ınio definido por um vetor de caracter´ısticas e δ ´e uma
fun¸c˜ao de distˆancia definida sobre este dom´ınio, como uma instˆancia do espa¸co de similaridade, a abstra¸c˜ao do espa¸co de similaridade humano utilizada nesta tese ´e formada pelo conjunto de todas instˆancias de espa¸co de similaridade poss´ıveis. Como citado anteriormente, ocorrem varia¸c˜oes na interpreta¸c˜ao humana a respeito de um dado complexo, influenciadas por fatores como o conhecimento pr´evio do usu´ario, sua inten¸c˜ao de uso para o dado complexo no momento da consulta e o contexto de aplica¸c˜ao. Na abs- tra¸c˜ao do espa¸co de similaridade, este processo ´e modelado pela escolha de uma instˆancia do espa¸co de similaridade que defina da maneira mais pr´oxima poss´ıvel a interpreta¸c˜ao do usu´ario.
O resultado de uma consulta por similaridade depende da instˆancia do espa¸co de similaridade utilizada. Em alguns dom´ınios, esta escolha n˜ao ´e um problema. Por exem- plo, aplica¸c˜oes de geoprocessamento geralmente tratam similaridade como a distˆancia entre objetos na superf´ıcie terrestre. Neste contexto, consultas t´ıpicas, tais como “re- torne os restaurantes que est˜ao a at´e 2 Km de onde estou” e “retorne os 2 hospitais mais pr´oximos a uma escola infantil ”, s˜ao respondidas adequadamente utilizando as co- ordenadas geogr´aficas dos elementos como o vetor de caracter´ısticas e utilizando como fun¸c˜ao a distˆancia Euclideana, ou o caminho mais curto entre v´ertices, se as rotas de acesso forem modeladas como um grafo. Entretanto, para dados multim´ıdia ´e frequente- mente necess´ario identificar qual par hS, δi define a instˆancia do espa¸co de similaridade que melhor representa a interpreta¸c˜ao do usu´ario em uma dada situa¸c˜ao. Resultados ex- perimentais mostram que encontrar a melhor combina¸c˜ao entre vetor de caracter´ısticas e fun¸c˜ao de distˆancia aprimora a precis˜ao das consultas (Bugatti et al., 2008).
Desta forma, para obter resultados relevantes em consultas por similaridade sobre da- dos complexos, o maior desafio ´e identificar a instˆancia do espa¸co de similaridade que melhor satisfaz a expectativa do usu´ario. Esta instˆancia “ideal” ´e referenciada na lite- ratura como espa¸co (de similaridade) semˆantico (He et al., 2002). H´a in´umeras ´areas de pesquisa e t´ecnicas envolvidas no processo de aproxima¸c˜ao do espa¸co de similaridade semˆantico, como mostra a Figura 2.1. Esta ilustra¸c˜ao n˜ao tem o intuito de ser exaustiva, mas de incluir os conceitos mais comuns em torno da avalia¸c˜ao de similaridade. A figura destaca que alguns conceitos afetam diretamente os componentes de uma instˆancia do espa¸co de similaridade. Por exemplo, as tarefas de extra¸c˜ao, sele¸c˜ao e transforma¸c˜ao de caracter´ısticas constroem ou modificam o vetor de caracter´ısticas, definindo o dom´ınio do conjunto de dados. De forma semelhante, a fun¸c˜ao de distˆancia pode ser modificada aplicando-se t´ecnicas de pondera¸c˜ao de caracter´ısticas espec´ıficas, bem como pondera¸c˜ao de distˆancias parciais, no caso de fun¸c˜oes que agregam resultados de outras distˆancias.
A base de uma instˆancia do espa¸co de similaridade ´e formada por um dom´ınio defi- nido por um vetor de caracter´ısticas (ap´os todos os procedimentos de pr´e-processamento, extra¸c˜ao e p´os-processamento) e uma fun¸c˜ao de distˆancia (definida pela fun¸c˜ao de c´alculo e por todos os valores para os parˆametros utilizados). Portanto, qualquer modifica¸c˜ao
realizada em um destes componentes gera uma nova instˆancia do espa¸co de similaridade. Isto significa que a partir de um mesmo extrator de caracter´ısticas e de uma mesma fun¸c˜ao de distˆancia podem ser obtidas v´arias instˆancias do espa¸co de similaridade, dependendo dos pr´e- e p´os-processamentos realizados, modificando o vetor de caracter´ısticas e/ou a fun¸c˜ao de distˆancia. A Figura 2.1 tamb´em mostra que em um n´ıvel mais alto est˜ao as in- forma¸c˜oes externas, t´ecnicas e algoritmos que s˜ao utilizados para para definir como ser˜ao implementados os conceitos que afetam diretamente os componentes de uma instˆancia do espa¸co de similaridade (extra¸c˜ao, sele¸c˜ao e transforma¸c˜ao de caracter´ısticas e pondera¸c˜ao de distˆancias). Neste n´ıvel encontram-se algoritmos de processamento de dados comple- xos, t´ecnicas de descoberta de conhecimento, realimenta¸c˜ao de relevˆancia, aprendizado de m´aquina e outros.
Vetor de
Características Função deDistância
Realimentação de Relevância Seleção de Características Entrada do Usuário Aprendizado de Máquina Extração de Características Técnicas de Descoberta de Conhecimento Metadados Instância do Espaço de Similaridade
Transformação de Características Ponderação de Características Ponderação de Distâncias Parciais Métodos Algébricos e Estatísticos Processamento de Imagens Processamento de Sinais
Figura 2.1: Espa¸co de similaridade e t´ecnicas envolvidas na defini¸c˜ao de sua semˆantica. As se¸c˜oes a seguir apresentam uma breve revis˜ao da literatura a respeito de propostas envolvendo os componentes de uma instˆancia de espa¸co de similaridade.