Author(s): Santos, Carlos Alexandre Lourenço dos
Date: 2016
Persistent ID: http://hdl.handle.net/10451/25166
Origin: Repositório da Universidade de Lisboa
Subject(s): Ontologia; Semelhança semântica; Segmentação; Prospecção de dados; Teses de mestrado - 2016; Departamento de Informática
Tese de mestrado, Engenharia Informática (Sistemas de Informação) Universidade de Lisboa, Faculdade de Ciências, 2016
Muitas das técnicas de prospecção de dados actualmente utilizadas funcionam de um modo “cego”, limitando-se ao que pode ser extraído directamente a partir dos dados, sem compreender o seu significado e, de um modo geral, deixando a interpretação dos resultados para peritos humanos. É, no entanto, amplamente reconhecido que codificar um maior número de relações entre objectos melhora o desempenho de abordagens de prospecção de dados. Isto, tipicamente, envolve a feitura de regras que sejam capazes de expressar conhecimento relativamente à forma como objectos de dados se relacionam entre si, mas o surgimento de tecnologias de Semantic Web e a sua aplicação em domínios diversificados como as ciências da vida, a astronomia ou a geografia, está a disponibilizar uma grande quantidade de dados enriquecidos com conhecimento de domínio na forma de múltiplas ontologias. Este cenário apresenta oportunidades únicas para a combinação do poder de abordagens de prospecção de dados e aprendizagem máquina com o conhecimento codificado em ontologias. O presente trabalho tem por objectivo abordar o desafio apresentado por esta mudança de paradigma através do desenvolvimento de novas abordagens para a descoberta de conhecimento alavancadas em tecnologias de Semantic Web e na abundância de conhecimento tornado disponível por intermédio das mesmas. Neste contexto, a semelhança semântica surge como um possível caminho para fazer a ponte entre os dois mundos, uma vez que pode ser usada para produzir uma medida de distância entre dois conceitos de uma ontologia ou entre duas entidades anotadas com conjuntos de conceitos de uma ontologia. Tendo em consideração que a distância é uma pedra angular de um número considerável de abordagens de aprendizagem máquina, incluindo diversas abordagens de segmentação (como, por exemplo, k-Means e Farthest First), a integração de semelhança semântica em algoritmos representativos do estado da arte da aprendizagem máquina disponibiliza uma forma de explorar dados usando o conhecimento contido em ontologias. Tendo em vista atingir os objectivos descritos, foi implementada uma estrutura que utiliza duas bibliotecas de software do mais alto nível de desenvolvimento: a Biblioteca de Medidas Semânticas (SML) para o cálculo de semelhança semântica e o Ambiente Waikato para Análise de Conhecimento (WEKA) para algoritmos de aprendizagem máquina. A SML foi ainda estendida tendo em vista permitir a computação de semelhança semântica usando múltiplas ontologias. Pela disponibilização de informação acrescida relativamente a relações entre entidades, o recurso a referências semânticas provenientes de mais do que uma ontologia representa uma oportunidade para reforçar a qualidade potencial de processos de segmentação. Lidar com a integração de múltiplas ontologias numa única medida de semelhança semântica é um desafio conhecido. Neste trabalho foram usadas duas abordagens simples: Híper-grafo e Média Ponderada. Para se obter um híper-grafo na SML, é necessário levar a efeito um processo de redefinição de raízes em que uma raiz virtual é criada para ligar os grafos carregados com cada uma das ontologias envolvidas. A abordagem de média ponderada combina os valores de semelhança semântica pela ponderação dos contributos de cada ontologia. No que diz respeito ao interface com o utilizador, para além de uma opção simples baseada em texto e da possibilidade de execução com especificação de parâmetros em linha de comando foi feita a integração das novas opções no explorador gráfico do WEKA e desenvolvido um ambiente gráfico próprio. Os resultados de cada execução são disponibilizados num ficheiro cujo conteúdo visa essencialmente disponibilizar toda a informação relativa a essa execução com o máximo de clareza incluindo, nomeadamente, uma designada matriz de confusão identificando o número de instâncias de cada classe de dados afetado a cada segmento. O conjunto de dados usado na avaliação da aplicação de segmentação desenvolvida foi obtido a partir de caminhos metabólicos presentes no repositório Reactome que disponibiliza uma lista de proteínas envolvidas para cada um dos caminhos metabólicos. A avaliação foi focada em três tipos de conjuntos de caminhos metabólicos humanos com anotações na ontologia de genes (GO) e/ou na ontologia de entidades químicas de interesse biológico (ChEBI): (1) Sem Ligação, ou seja, grupos distantes de caminhos metabólicos, sem qualquer ligação entre si; (2) Com Ligação, ou seja, diferentes grupos de caminhos metabólicos com uma ligação entre si e (3) Mesmo Grupo, ou seja, caminhos metabólicos pertences a um mesmo grupo de caminhos. Para cada conjunto foram efectuados oito testes, cada um deles com dezasseis tarefas de segmentação, com tamanhos de dados e números de segmentos alvo diversificados. A aplicação inclui dois algoritmos de segmentação, SimplekMeans e Farthest First, e foi testada com duas bem conhecidas medidas de semelhança semântica, a medida semântica de comparação directa de grupos de anotações por cada duas entidades SimGIC e a medida semântica de comparação indirecta de grupos de anotações por cada duas entidades baseada na medida de comparação de pares de conceitos Lin com uma estratégia de agregação Média de Melhores Correspondências. Uma linha de base – referência para os resultados de segmentação tendo em vista capturar a influência da utilização de distâncias semânticas em contraponto às distâncias convencionalmente usadas em segmentação – foi estabelecida cujas anotações foram tratadas como palavras usando filtro disponibilizado pelo WEKA que converte um atributo de cadeia de caracteres num vector representativo das frequências de ocorrência de palavras. Tendo em conta o tipo (dos três atrás descritos) de conjunto de caminhos metabólico, o uso de semelhança semântica é claramente benéfico tanto para o tipo Sem Ligação como para o tipo Com Ligação, com aumentos de desempenho que vão desde +3% a +11%. No que diz respeito ao conjunto Mesmo Grupo, a linha de base tem um desempenho em média melhor do que as abordagens baseadas em semelhança semântica. Os resultados usando ambas as ontologias ou apenas a GO revelam desempenhos muito semelhantes para as mesmas abordagens de segmentação e semelhança semântica, o que não acontece quando é usada unicamente a ontologia ChEBI. Uma pequena parte das proteínas usadas nos conjuntos de dados são anotadas com conceitos da ontologia ChEBI (apenas cerca de 5 a 10%) e a estrutura daquela ontologia é maioritariamente plana, com uma grande proporção de nodos folhas, o que se confirmou diminuir o impacto da utilização de medidas de semelhança semântica. Foi possível confirmar a conhecida tendência em algoritmos de segmentação baseados no k-Means para uma diminuição do desempenho da segmentação associada ao aumento do número alvo de segmentos e ainda, verificar que essa tendência se agrava consideravelmente se, com um elevado número de segmentos alvo, se conjugar um muito elevado número de instâncias a segmentar. Mostrou-se também que esta conjugação se revela, como seria de esperar, causadora de piores tempos de execução com a curiosidade de tal se verificar quando é usado o SimplekMeans mas não com o Farthest First. O primeiro foi, nas mesmas condições de teste, sempre mais lento que o segundo assim como a medida SimGIC foi sempre mais rápida do que a baseada na medida Lin. Foi então possível demonstrar que a utilidade de empregar semelhança semântica depende não só da diversidade e qualidade das anotações existentes nos conjuntos de dados, mas também da estrutura das ontologia usadas e do grau em que as mesmas são capazes de acrescentar informação útil para identificar instâncias semelhantes. O presente trabalho constitui-se como um primeiro contributo que abre caminho a esforços futuros complementares em frentes diversas como, por exemplo: (1) Avaliar melhor as suas potencialidades com testes adicionais com diferentes combinações e números de ontologias usadas bem como diferentes fontes de dados; (2) Explorar algoritmos de segmentação, incluindo métodos de inicialização de centróides, alternativos; (3) Considerar medidas de semelhança semântica mais complexas e (4) Investigar aspectos relacionados com a eficiência computacional no uso de múltiplas ontologias. Em última análise, a abordagem proposta pode vir a ser usada para analisar conjuntos de dados diversos compostos tanto por anotações semânticas como por valores numéricos, através da sua combinação comas abordagens convencionais já disponíveis.
Many of the currently employed data mining techniques work in a blind mode, limiting themselves to what can be extracted directly from the data, without understanding its meaning. It is, however, widely recognized that encoding more relations between objects increases the performance of data mining approaches. This typically involves the handcrafting of rules that are able to express knowledge about how data objects relate to each other, but the emergence of semantic web technologies and their application in diverse domains is providing a wealth of data that is enriched with domain knowledge in the form of multiple ontologies. The present work aims at addressing the challenge presented by this paradigm shift by integrating semantic similarity into machine learning algorithms to explore data using the knowledge contained in ontologies. A software application was developed that utilizes two state of the art libraries: The Semantic Measures Library (SML) for semantic similarity calculations and The Waikato Environment for Knowledge Analysis (WEKA) for machine learning algorithms. SML was further extended to allow the computation of semantic similarity using multiple ontologies. The data-set used in the application’s evaluation was derived from the metabolic pathways present in Reactome, which provides a list of involved proteins for each of the pathways. The evaluation focused on three types of sets of human pathways with annotations to GO and ChEBI: (1) No Link, not linked pathways’ groups; (2) Link, pathways’ groups with one link and (3) Same Group, pathways in the same group. It was shown that the usefulness of employing semantic similarity depends not only on the diversity and quality of the data-sets annotations, but also on the structure of the ontologies employed, and the degree to which they are able to impart useful information to identify similar instances. Ultimately, the proposed approach can be used to analyze diverse data-sets composed of both semantic annotations and numerical values, by combining it with the conventional approaches already available.
