• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Thèse de Doctorat
DOI
10.11606/T.55.2016.tde-29072016-100548
Document
Auteur
Nom complet
Lilian Berton
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Carlos, 2016
Directeur
Jury
Lopes, Alneu de Andrade (Président)
Hruschka Júnior, Estevam Rafael
Jorge, Alípio Mário Guedes
Liang, Zhao
Travieso, Gonzalo
Titre en portugais
Construção de redes baseadas em vizinhança para o aprendizado semissupervisionado
Mots-clés en portugais
Aprendizado semissupervisionado
Construção de redes
Métodos baseados em redes para classificação
Redes baseadas em vizinhança
Resumé en portugais
Com o aumento da capacidade de armazenamento, as bases de dados são cada vez maiores e, em muitas situações, apenas um pequeno subconjunto de itens de dados pode ser rotulado. Isto acontece devido ao processo de rotulagem ser frequentemente caro, demorado e necessitar do envolvimento de especialistas humanos. Com isso, diversos algoritmos semissupervisionados foram propostos, mostrando que é possível obter bons resultados empregando conhecimento prévio, relativo à pequena fração de dados rotulados. Dentre esses algoritmos, os que têm ganhado bastante destaque na área têm sido aqueles baseados em redes. Tal interesse, justifica-se pelas vantagens oferecidas pela representação via redes, tais como, a possibilidade de capturar a estrutura topológica dos dados, representar estruturas hierárquicas, bem como modelar manifolds no espaço multi-dimensional. No entanto, existe uma grande quantidade de dados representados em tabelas atributo-valor, nos quais não se poderia aplicar os algoritmos baseados em redes sem antes construir uma rede a partir desses dados. Como a geração das redes, assim como sua relação com o desempenho dos algoritmos têm sido pouco estudadas, esta tese investigou esses aspectos e propôs novos métodos para construção de redes, considerando características ainda não exploradas na literatura. Foram propostos três métodos para construção de redes com diferentes topologias: 1) S-kNN (Sequential k Nearest Neighbors), que gera redes regulares; 2) GBILI (Graph Based on the Informativeness of Labeled Instances) e RGCLI (Robust Graph that Considers Labeled Instances), que exploram os rótulos disponíveis gerando redes com distribuição de grau lei de potência; 3) GBLP (Graph Based on Link Prediction), que se baseia em medidas de predição de links gerando redes com propriedades mundo-pequeno. As estratégias de construção de redes propostas foram analisadas por meio de medidas de teoria dos grafos e redes complexas e validadas por meio da classificação semissupervisionada. Os métodos foram aplicados em benchmarks da área e também na classificação de gêneros musicais e segmentação de imagens. Os resultados mostram que a topologia da rede influencia diretamente os algoritmos de classificação e as estratégias propostas alcançam boa acurácia.
Titre en anglais
Graph construction based on neighborhood for semisupervised
Mots-clés en anglais
Graph construction
Graph-based methods for classification
Neighborhood graphs
Semi-supervised learning
Resumé en anglais
With the increase capacity of storage, databases are getting larger and, in many situations, only a small subset of data items can be labeled. This happens because the labeling process is often expensive, time consuming and requires the involvement of human experts. Hence, several semi-supervised algorithms have been proposed, showing that it is possible to achieve good results by using prior knowledge. Among these algorithms, those based on graphs have gained prominence in the area. Such interest is justified by the benefits provided by the representation via graphs, such as the ability to capture the topological structure of the data, represent hierarchical structures, as well as model manifold in high dimensional spaces. Nevertheless, most of available data is represented by attribute-value tables, making necessary the study of graph construction techniques in order to convert these tabular data into graphs for applying such algorithms. As the generation of the weight matrix and the sparse graph, and their relation to the performance of the algorithms have been little studied, this thesis investigated these aspects and proposed new methods for graph construction with characteristics litle explored in the literature yet. We have proposed three methods for graph construction with different topologies: 1) S-kNN (Sequential k Nearest Neighbors) that generates regular graphs; 2) GBILI (Graph Based on the informativeness of Labeled Instances) and RGCLI (Robust Graph that Considers Labeled Instances), which exploit the labels available generating power-law graphs; 3) GBLP (Graph Based on Link Prediction), which are based on link prediction measures and generates small-world graphs. The strategies proposed were analyzed by graph theory and complex networks measures and validated in semi-supervised classification tasks. The methods were applied in benchmarks of the area and also in the music genre classification and image segmentation. The results show that the topology of the graph directly affects the classification algorithms and the proposed strategies achieve good accuracy.
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
Date de Publication
2016-09-28
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
CeTI-SC/STI
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2020. Tous droits réservés.