• 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
 
 
Mémoire de Maîtrise
DOI
https://doi.org/10.11606/D.100.2023.tde-11052023-184459
Document
Auteur
Nom complet
Waldyr Lourenço de Freitas Junior
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2023
Directeur
Jury
Peres, Sarajane Marques (Président)
França, Fabrício Olivetti de
Vargas, Rosana Retsos Signorelli
 
Titre en portugais
Um comparativo quantitativo e qualitativo de algoritmos de coagrupamento baseados em fatoração de matrizes
Mots-clés en portugais
Coagrupamento
Fatoração de matrizes
Interpretação humana
Resumé en portugais
Agrupamento é uma estratégia para análise de dados que objetiva encontrar grupos cujos dados são mais similares entre si, enquanto dados organizados em grupos distintos são mais dissimilares entre si. Coagrupamento é uma estratégia semelhante, contudo, aplicado simultaneamente sobre os dados e atributos de um conjunto de dados. Diferentes contextos usam coagrupamento, tais como análise de imagens, bioinformática e mineração de textos. Para este último, cujos dados sob análise dizem respeito a contextos caracterizados por subjetividade, a literatura apresenta alguns poucos estudos relacionados à interação humana para interpretação dos resultados. Dentre uma série de abordagens de coagrupamento, destaca-se a fatoração tripla de matrizes não negativas (NMTF). Estudos reconhecem a utilidade dessa abordagem por seu alto desempenho e facilidade em trabalhar com dados diádicos e dados com alta dimensionalidade. Corpus textuais, cuja representação seja baseada no modelo de espaço vetorial, podem produzir matrizes de dados com alta dimensionalidade e alta esparsidade. Essas características tornam tais problemas candidatos a serem tratados por meio da abordagem NMTF. A literatura apresenta diferentes algoritmos de coagrupamento baseados em fatoração de matrizes; tais estudos concentraram-se na avaliação da capacidade de agrupamento dos algoritmos, mas não trataram o aspecto da qualidade dos resultados segundo a ótica da interpretação humana. Assim, o objetivo principal deste trabalho foi explorar sistematicamente um conjunto de algoritmos de coagrupamento baseados em fatoração de matrizes, com atenção à interpretação humana dos resultados produzidos por eles. Este trabalho também explorou esses algoritmos em diferentes circunstâncias e revelou mais claramente suas vantagens e desvantagens. Os experimentos se basearam em conjuntos de dados sintéticos e do mundo real. Os conjuntos de dados sintéticos foram rotulados e contavam com diferentes estruturas de cogrupos; o objetivo foi explorar a capacidade que os algoritmos têm em agrupar dados e atributos. Um conjunto de dados do mundo real usado como referência para tarefas de análise automática de textos foi escolhido para uso nos experimentos com dados do mundo real. O conjunto consiste de um corpus público de notícias (com e sem caráter de hiperpartidarismo), extraídas de diferentes sites entre 2016 e 2018; o objetivo foi realizar uma análise detalhada da robustez dos algoritmos sob uma análise qualitativa de resultados, realizada sob uma ótica de interpretação humana. Para essa análise qualitativa, foram realizadas uma série de tarefas baseadas em questionários estruturados aplicados a alunos de graduação da Universidade de São Paulo. Os experimentos com dados sintéticos e do mundo real demostraram que algoritmos com restrições binárias apresentam desempenho melhor que os demais. Além disso, uma análise de palavras que melhor representam grupos de notícias evidenciou dificuldades dos algoritmos em definir claramente, no sentido semântico, tais grupos. O algoritmo proposto neste trabalho (WC-FNMTF) foi submetido a diferentes tarefas e apresentou bons resultados. A tarefa com humanos revelou superioridade do algoritmo NBVD, seguido do WC-FNMTF.
 
Titre en anglais
A quantitative and qualitative comparison of co-clustering algorithms based on matrix factorization
Mots-clés en anglais
Co-clustering
Human interpretation
Matrix factorization
Resumé en anglais
Clustering is a strategy for data analysis to identify clusters whose data points are more similar to each other. Data points organized into distinct clusters are more dissimilar to each other. Co-clustering is a similar strategy, however, it is applied simultaneously to data and attributes of a data set. Different contexts use co-clustering, such as image analysis, bioinformatics, and text mining. For the latter, whose data under analysis concern contexts characterized by subjectivity, the literature presents a few studies related to human interaction for interpreting results. Among several co-clustering approaches, the Non-negative Matrix Factorization (NMTF) stands out. Studies recognize the usefulness of such an approach because of its high performance and ease of working with dyadic data and data with high dimensionality. Corpus, whose representation is based on the vector space model, can produce data matrices with high dimensionality and high sparsity. These characteristics make such problems candidates to be addressed through the NMTF approach. The literature presents different co-clustering algorithms based on matrix factorization; such studies focused on evaluating the algorithms clustering ability but did not address quality aspects from the perspective of human interpretation of the meaning of the generated clusters. Thus, the main objective of this work was systematically to explore a set of co-clustering algorithms based on matrix factorization, with attention to human interpretation of the results produced by them. This work also explored such algorithms in different circumstances to reveal their advantages and disadvantages. Experiments were based on synthetic data sets and real-world data sets. The synthetic data sets were labeled and composed of different co-cluster structures; the goal was to explore algorithms ability to cluster attributes and data. A real-world data set used as a reference for automatic text analysis tasks was chosen for experiments with real-world data. The data set comprises a public corpus of news (with and without a hyper-partisan character), drawn from different websites between the years 2016 and 2018; the aim was to carry out a detailed analysis of the robustness of the algorithms under a qualitative analysis, from the human perspective of interpretation. For this qualitative analysis, a series of tasks were carried out based on structured questionnaires applied to undergraduate students at the University of São Paulo. Experiments with both synthetic data and real-world data showed algorithms with binary restrictions performed better than the others. An analysis of words that best represent clusters of news showed algorithms' difficulties in precisely defining, in the semantic sense, such clusters. The algorithm proposed in this work (WC-FNMTF) was submitted to several tasks and presented promising results. The task with humans revealed the superiority of the NBVD algorithm, followed by the WC-FNMTF.
 
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
2023-07-10
 
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
© 2001-2024. Bibliothèque Numérique de Thèses et Mémoires de l'USP.