O volume crescente de textos digitalmente armazenados torna necessária a construção de ferramentas computacionais que permitam a organização e o acesso eficaz e eficiente à informação e ao conhecimento nele contidos. No campo do conhecimento da biomedicina este problema se torna extremamente relevante, pois a maior parte do conhecimento gerado é formalizada através de artigos científicos e é necessário que o acesso a estes seja o mais fácil e rápido possível. A área de pesquisa conhecida como Mineração de Textos (do inglês Text Mining), se propõe a enfrentar este problema ao procurar identificar novas informações e conhecimentos até então desconhecidos, em bases de dados textuais. Uma de suas tarefas é a descoberta de grupos de textos correlatos em base de dados textuais e esse problema é conhecido como agrupamento de textos (do inglês Text Clustering). Para este fim, a representação das bases de dados textuais comumente utilizada no agrupamento de textos é o Modelo Espaço-vetorial, no qual cada texto é representado por um vetor de características, que são as freqüências das palavras ou termos que nele ocorrem. O conjunto de vetores forma uma matriz denominada de documento-termo, que é esparsa e de alta dimensionalidade. Para atenuar os problemas decorrentes dessas características, normalmente é selecionado um subconjunto de termos, construindo-se assim uma nova matriz documento-termo com um número reduzido de dimensões que é então utilizada nos algoritmos de agrupamento. Este trabalho se desdobra em: i) introdução e implementação de dois algoritmos para seleção de termos e ii) avaliação dos algoritmos k-means, espectral e de particionamento de grafos, em cinco base de dados de textos previamente classificadas. As bases de dados são pré-processadas através de métodos descritos na literatura, produzindo-se as matrizes documento-termo. Os resultados indicam que os algoritmos de seleção propostos, para a redução das matrizes documento-termo, melhoram o desempenho dos algoritmos de agrupamento avaliados. Os algoritmos k-means e espectral têm um desempenho superior ao algoritmos de particionamento de grafos no agrupamento de bases de dados textuais, com ou sem a seleção de características. / The increasing amount of digitally stored texts makes necessary the development of computational tools to allow the access of information and knowledge in an efficient and efficacious manner. This problem is extremely relevant in biomedicine research, since most of the generated knowledge is translated into scientific articles and it is necessary to have the most easy and fast access. The research field known as Text Mining deals with the problem of identifying new information and knowledge in text databases. One of its tasks is to find in databases groups of texts that are correlated, an issue known as text clustering. To allow clustering, text databases must be transformed into the commonly used Vector Space Model, in which texts are represented by vectors composed by the frequency of occurrence of words and terms present in the databases. The set of vectors composing a matrix named document-term is usually sparse with high dimension. Normally, to attenuate the problems caused by these features, a subset of terms is selected, thus giving rise a new document-term matrix with reduced dimensions, which is then used by clustering algorithms. This work presents two algorithms for terms selection and the evaluation of clustering algorithms: k-means, spectral and graph portioning, in five pre-classified databases. The databases were pre-processed by previously described methods. The results indicate that the term selection algorithms implemented increased the performance of the clustering algorithms used and that the k-means and spectral algorithms outperformed the graph portioning.

Esta Tese apresenta um conjunto de técnicas propostas com o objetivo de aprimorar processos de Agrupamento de Dados (AD). O principal objetivo é fornecer à comunidade científica um ferramental para uma análise completa de estruturas implícitas em conjuntos de dados, desde a descoberta dessas estruturas, permitindo o emprego de conhecimento prévio sobre os dados, até a análise de seu significado no contexto em que eles estão inseridos. São dois os pontos principais desse ferramental. O primeiro se trata do algoritmo para AD fuzzy semi-supervisionado SSL+P e sua evolução SSL+P*, capazes de levar em consideração o conhecimento prévio disponível sobre os dados em duas formas: rótulos e níveis de proximidade de pares de exemplos, aqui denominados Dicas de Conhecimento Prévio (DCPs). Esses algoritmos também permitem que a métrica de distância seja ajustada aos dados e às DCPs. O algoritmo SSL+P* também busca estimar o número ideal de clusters para uma determinada base de dados, levando em conta as DCPs disponíveis. Os algoritmos SSL+P e SSL+P* envolvem a minimização de uma função objetivo por meio de um algoritmo de Otimização Baseado em População (OBP). Esta Tese também fornece ferramentas que podem ser utilizadas diretamente neste ponto: as duas versões modificadas do algoritmo Particle Swarm Optimization (PSO), DPSO-1 e DPSO-2 e 4 formas de inicialização de uma população inicial de soluções. O segundo ponto principal do ferramental proposto nesta Tese diz respeito à análise de clusters resultantes de um processo de AD aplicado a uma base de dados de um domínio específico. É proposta uma abordagem baseada em Mineração de Textos (MT) para a busca em informações textuais, disponibilizadas digitalmente e relacionadas com as entidades representadas nos dados. Em seguida, é fornecido ao pesquisador um conjunto de palavras associadas a cada cluster, que podem sugerir informações que ajudem a identificar as relações compartilhadas por exemplos atribuídos ao mesmo cluster / This Thesis presents a whole set of techniques designed to improve the data clustering proccess. The main goal is to provide to the scientific community a tool set for a complete analyses of the implicit structures in datasets, from the identification of these structures, allowing the use of previous knowledge about the data, to the analysis of its meaning in their context. There are two main points involved in that tool set. The first one is the semi-supervised clustering algorithm SSL+P and its upgraded version SSL+P*, which are able of take into account the available knowlegdge about de data in two forms: class labels and pairwise proximity levels, both refered here as hints. These algorithms are also capable of adapting the distance metric to the data and the available hints. The SSL+P* algorithm searches the ideal number of clusters for a dataset, considering the available hints. Both SSL+P and SSL+P* techniques involve the minimization of an objective function by a Population-based Optimization algorithm (PBO). This Thesis also provides tools that can be directly employed in this area: the two modified versions of the Particle Swarm Optimization algorithm (PSO), DPSO-1 and DPSO-2, and 4 diferent methods for initializing a population of solutions. The second main point of the tool set proposed by this Thesis regards the analysis of clusters resulting from a clustering process applied to a domain specific dataset. A Text Mining based approach is proposed to search for textual information related to the entities represented by the data, available in digital repositories. Next, a set of words associated with each cluster is presented to the researcher, which can suggest information that can support the identification of relations shared by objects assigned to the same cluster

A extração de termos em coleções textuais, que é uma atividade da etapa de Pré-Processamento da Mineração de Textos, pode ser empregada para diversos fins nos processos de extração de conhecimento. Esses termos devem ser cuidadosamente extraídos, uma vez que os resultados de todo o processo dependerão, em grande parte, da \"qualidade\" dos termos obtidos. A \"qualidade\" dos termos, neste trabalho, abrange tanto a representatividade dos termos no domínio em questão como sua compreensibilidade. Tendo em vista sua importância, neste trabalho, avaliou-se o efeito do uso de diferentes técnicas de simplificação de termos na compreensibilidade e representatividade dos termos em coleções textuais na Língua Portuguesa. Os termos foram extraídos seguindo os passos da metodologia apresentada neste trabalho e as técnicas utilizadas durante essa atividade de extração foram a radicalização, lematização e substantivação. Para apoiar tal metodologia, foi desenvolvida uma ferramenta, a ExtraT (Ferramenta para Extração de Termos). Visando garantir a \"qualidade\" dos termos extraídos, os mesmos são avaliados objetiva e subjetivamente. As avaliações subjetivas, ou seja, com o auxílio de especialistas do domínio em questão, abrangem a representatividade dos termos em seus respectivos documentos, a compreensibilidade dos termos obtidos ao utilizar cada técnica e a preferência geral subjetiva dos especialistas em cada técnica. As avaliações objetivas, que são auxiliadas por uma ferramenta desenvolvida (a TaxEM - Taxonomia em XML da Embrapa), levam em consideração a quantidade de termos extraídos por cada técnica, além de abranger tambéem a representatividade dos termos extraídos a partir de cada técnica em relação aos seus respectivos documentos. Essa avaliação objetiva da representatividade dos termos utiliza como suporte a medida CTW (Context Term Weight). Oito coleções de textos reais do domínio de agronegócio foram utilizadas na avaliaçao experimental. Como resultado foram indicadas algumas das características positivas e negativas da utilização das técnicas de simplificação de termos, mostrando que a escolha pelo uso de alguma dessas técnicas para o domínio em questão depende do objetivo principal pré-estabelecido, que pode ser desde a necessidade de se ter termos compreensíveis para o usuário até a necessidade de se trabalhar com uma menor quantidade de termos / The task of term extraction in textual domains, which is a subtask of the text pre-processing in Text Mining, can be used for many purposes in knowledge extraction processes. These terms must be carefully extracted since their quality will have a high impact in the results. In this work, the quality of these terms involves both representativity in the specific domain and comprehensibility. Considering this high importance, in this work the effects produced in the comprehensibility and representativity of terms were evaluated when different term simplification techniques are utilized in text collections in Portuguese. The term extraction process follows the methodology presented in this work and the techniques used were radicalization, lematization and substantivation. To support this metodology, a term extraction tool was developed and is presented as ExtraT. In order to guarantee the quality of the extracted terms, they were evaluated in an objective and subjective way. The subjective evaluations, assisted by domain specialists, analyze the representativity of the terms in related documents, the comprehensibility of the terms with each technique, and the specialist\'s opinion. The objective evaluations, which are assisted by TaxEM and by Thesagro (National Agricultural Thesaurus), consider the number of extracted terms by each technique and their representativity in the related documents. This objective evaluation of the representativity uses the CTW measure (Context Term Weight) as support. Eight real collections of the agronomy domain were used in the experimental evaluation. As a result, some positive and negative characteristics of each techniques were pointed out, showing that the best technique selection for this domain depends on the main pre-established goal, which can involve obtaining better comprehensibility terms for the user or reducing the quantity of extracted terms

Selecionar atributos é, por vezes, uma atividade necessária para o correto desenvolvimento de tarefas de aprendizado de máquina. Em Mineração de Textos, reduzir o número de atributos em uma base de textos é essencial para a eficácia do processo e a compreensibilidade do conhecimento extraído, uma vez que se lida com espaços de alta dimensionalidade e esparsos. Quando se lida com contextos nos quais a coleção de textos é não-rotulada, métodos não-supervisionados de redução de atributos são utilizados. No entanto, não existe forma geral predefinida para a obtenção de medidas de utilidade de atributos em métodos não-supervisionados, demandando um esforço maior em sua realização. Assim, este trabalho aborda a seleção não-supervisionada de atributos por meio de um estudo exploratório de métodos dessa natureza, comparando a eficácia de cada um deles na redução do número de atributos em aplicações de Mineração de Textos. Dez métodos são comparados - Ranking porTerm Frequency, Ranking por Document Frequency, Term Frequency-Inverse Document Frequency, Term Contribution, Term Variance, Term Variance Quality, Método de Luhn, Método LuhnDF, Método de Salton e Zone-Scored Term Frequency - sendo dois deles aqui propostos - Método LuhnDF e Zone-Scored Term Frequency. A avaliação se dá em dois focos, supervisionado, pelo medida de acurácia de quatro classificadores (C4.5, SVM, KNN e Naïve Bayes), e não-supervisionado, por meio da medida estatística de Expected Mutual Information Measure. Aos resultados de avaliação, aplica-se o teste estatístico de Kruskal-Wallis para determinação de significância estatística na diferença de desempenho dos diferentes métodos de seleção de atributos comparados. Seis bases de textos são utilizadas nas avaliações experimentais, cada uma relativa a um grande domínio e contendo subdomínios, os quais correspondiam às classes usadas para avaliação supervisionada. Com esse estudo, este trabalho visa contribuir com uma aplicação de Mineração de Textos que visa extrair taxonomias de tópicos a partir de bases textuais não-rotuladas, selecionando os atributos mais representativos em uma coleção de textos. Os resultados das avaliações mostram que não há diferença estatística significativa entre os métodos não-supervisionados de seleção de atributos comparados. Além disso, comparações desses métodos não-supervisionados com outros supervisionados (Razão de Ganho e Ganho de Informação) apontam que é possível utilizar os métodos não-supervisionados em atividades supervisionadas de Mineração de Textos, obtendo eficiência compatível com os métodos supervisionados, dado que não detectou-se diferença estatística nessas comparações, e com um custo computacional menor / Feature selection is an activity sometimes necessary to obtain good results in machine learning tasks. In Text Mining, reducing the number of features in a text base is essential for the effectiveness of the process and the comprehensibility of the extracted knowledge, since it deals with high dimensionalities and sparse contexts. When dealing with contexts in which the text collection is not labeled, unsupervised methods for feature reduction have to be used. However, there aren\'t any general predefined feature quality measures for unsupervised methods, therefore demanding a higher effort for its execution. So, this work broaches the unsupervised feature selection through an exploratory study of methods of this kind, comparing their efficacies in the reduction of the number of features in the Text Mining process. Ten methods are compared - Ranking by Term Frequency, Ranking by Document Frequency, Term Frequency-Inverse Document Frequency, Term Contribution, Term Variance, Term Variance Quality, Luhn\'s Method, LuhnDF Method, Salton\'s Method and Zone-Scored Term Frequency - and two of them are proposed in this work - LuhnDF Method and Zone-Scored Term Frequency. The evaluation process is done in two ways, supervised, through the accuracy measure of four classifiers (C4.5, SVM, KNN and Naïve Bayes), and unsupervised, using the Expected Mutual Information Measure. The evaluation results are submitted to the statistical test of Kruskal-Wallis in order to determine the statistical significance of the performance difference of the different feature selection methods. Six text bases are used in the experimental evaluation, each one related to one domain and containing sub domains, which correspond to the classes used for supervised evaluation. Through this study, this work aims to contribute with a Text Mining application that extracts topic taxonomies from unlabeled text collections, through the selection of the most representative features in a text collection. The evaluation results show that there is no statistical difference between the unsupervised feature selection methods compared. Moreover, comparisons of these unsupervised methods with other supervised ones (Gain Ratio and Information Gain) show that it is possible to use unsupervised methods in supervised Text Mining activities, obtaining an efficiency compatible with supervised methods, since there isn\'t any statistical difference the statistical test detected in these comparisons, and with a lower computational effort

Com a grande variedade de produtos e serviços disponíveis na Web, os usuários possuem, em geral, muita liberdade de escolha, o que poderia ser considerado uma vantagem se não fosse pela dificuldade encontrada em escolher o produto ou serviço que mais atenda a suas necessidades dentro do vasto conjunto de opções disponíveis. Sistemas de recomendação são sistemas que têm como objetivo auxiliar esses usuários a identificarem itens de interesse em um conjunto de opções. A maioria das abordagens de sistemas de recomendação foca em recomendar itens mais relevantes para usuários individuais, não levando em consideração o contexto dos usuários. Porém, em muitas aplicações é importante também considerar informações contextuais para fazer as recomendações. Por exemplo, um usuário pode desejar assistir um filme com a sua namorada no sábado à noite ou com os seus amigos durante um dia de semana, e uma locadora de filmes na Web pode recomendar diferentes tipos de filmes para este usuário dependendo do contexto no qual este se encontra. Um grande desafio para o uso de sistemas de recomendação sensíveis ao contexto é a falta de métodos para aquisição automática de informação contextual para estes sistemas. Diante desse cenário, neste trabalho é proposto um método para extrair informações contextuais do conteúdo de páginas Web que consiste em construir hierarquias de tópicos do conteúdo textual das páginas considerando, além da bag-of-words tradicional (informação técnica), também informações mais valiosas dos textos como entidades nomeadas e termos do domínio (informação privilegiada). Os tópicos extraídos das hierarquias das páginas Web são utilizados como informações de contexto em sistemas de recomendação sensíveis ao contexto. Neste trabalho foram realizados experimentos para avaliação do contexto extraído pelo método proposto em que foram considerados dois baselines: um sistema de recomendação que não considera informação de contexto e um método da literatura de extração de contexto implementado e adaptado para este mestrado. Além disso, foram utilizadas duas bases de dados. Os resultados obtidos foram, de forma geral, muito bons apresentando ganhos significativos sobre o baseline sem contexto. Com relação ao baseline que extrai informação contextual, o método proposto se mostrou equivalente ou melhor que o mesmo. / With the wide variety of products and services available on the web, it is difficult for users to choose the option that most meets their needs. In order to reduce or even eliminate this difficulty, recommender systems have emerged. A recommender system is used in various fields to recommend items of interest to users. Most recommender approaches focus only on users and items to make the recommendations. However, in many applications it is also important to incorporate contextual information into the recommendation process. For example, a user may want to watch a movie with his girlfriend on Saturday night or with his friends during a weekday, and a video store on the Web can recommend different types of movies for this user depending on his context. Although the use of contextual information by recommendation systems has received great focus in recent years, there is a lack of automatic methods to obtain such information for context-aware recommender systems. For this reason, the acquisition of contextual information is a research area that needs to be better explored. In this scenario, this work proposes a method to extract contextual information of Web page content. This method builds topic hierarchies of the pages textual content considering, besides the traditional bag-of-words, valuable information of texts as named entities and domain terms (privileged information). The topics extracted from the hierarchies are used as contextual information in context-aware recommender systems. By using two databases, experiments were conducted to evaluate the contextual information extracted by the proposed method. Two baselines were considered: a recommendation system that does not use contextual information (IBCF) and a method proposed in literature to extract contextual information (\\methodological\" baseline), adapted for this research. The results are, in general, very good and show significant gains over the baseline without context. Regarding the \"methodological\" baseline, the proposed method is equivalent to or better than this baseline.

O número de documentos textuais disponíveis em formato digital tem aumentado incessantemente. Técnicas de Mineração de Textos são cada vez mais utilizadas para organizar e extrair conhecimento de grandes coleções de documentos textuais. Para o uso dessas técnicas é necessário que os documentos textuais estejam representados em um formato apropriado. A maioria das pesquisas de Mineração de Textos utiliza a abordagem bag-of-words para representar os documentos da coleção. Essa representação usa cada palavra presente na coleção de documentos como possível atributo, ignorando a ordem das palavras, informa ções de pontuação ou estruturais, e é caracterizada pela alta dimensionalidade e por dados esparsos. Por outro lado, a maioria dos conceitos são compostos por mais de uma palavra, como Inteligência Articial, Rede Neural, e Mineração de Textos. As abordagens que geram atributos compostos por mais de uma palavra apresentam outros problemas além dos apresentados pela representação bag-of-words, como a geração de atributos com pouco signicado e uma dimensionalidade muito maior. Neste projeto de mestrado foi proposta uma abordagem para representar documentos textuais nomeada bag-of-related-words. A abordagem proposta gera atributos compostos por palavras relacionadas com o uso de regras de associação. Com as regras de associação, espera-se identicar relações entre palavras de um documento, além de reduzir a dimensionalidade, pois são consideradas apenas as palavras que ocorrem ou que coocorrem acima de uma determinada frequência para gerar as regras. Diferentes maneiras de mapear o documento em transações para possibilitar a geração de regras de associação são analisadas. Diversas medidas de interesse aplicadas às regras de associação para a extração de atributos mais signicativos e a redução do número de atributos também são analisadas. Para avaliar o quanto a representação bag-of-related-words pode auxiliar na organização e extração de conhecimento de coleções de documentos textuais, e na interpretabilidade dos resultados, foram realizados três grupos de experimentos: 1) classicação de documentos textuais para avaliar o quanto os atributos da representação bag-of-related-words são bons para distinguir as categorias dos documentos; 2) agrupamento de documentos textuais para avaliar a qualidade dos grupos obtidos com a bag-of-related-words e consequentemente auxiliar na obtenção da estrutura de uma hierarquia de tópicos; e 3) construção e avaliação de hierarquias de tópicos por especialistas de domínio. Todos os resultados e dimensionalidades foram comparados com a representação bag-of-words. Pelos resultados dos experimentos realizados, pode-se vericar que os atributos da representação bag-of-related-words possuem um poder preditivo tão bom quanto os da representação bag-of-words. A qualidade dos agrupamentos de documentos textuais utilizando a representação bag-of-related-words foi tão boa quanto utilizando a representação bag-of-words. Na avaliação de hierarquias de tópicos por especialistas de domínio, a utilização da representação bag-of-related-words apresentou melhores resultados em todos os quesitos analisados / The amount of textual documents available in digital format is incredibly large. Text Mining techniques are becoming essentials to manage and extract knowledge in big textual document collections. In order to use these techniques, the textual documents need to be represented in an appropriate format to allow the construction of a model that represents the embedded knowledge in these textual documents. Most of the researches on Text Mining uses the bag-of-words approach to represent textual document collections. This representation uses each word in a collection as feature, ignoring the order of the words, structural information, and it is characterized by the high dimensionality and data sparsity. On the other hand, most of the concepts are compounded by more than one word, such as Articial Intelligence, Neural Network, and Text Mining. The approaches which generate features compounded by more than one word to solve this problem, suer from other problems, as the generation of features without meaning and a dimensionality much higher than that of the bag-of-words. An approach to represent textual documents named bag-of-related-words was proposed in this master thesis. The proposed approach generates features compounded by related words using association rules. We hope to identify relationships among words and reduce the dimensionality with the use of association rules, since only the words that occur and cooccur over a frequency threshold will be used to generate rules. Dierent ways to map the document into transactions to allow the extraction of association rules are analyzed. Dierent objective interest measures applied to the association rules to generate more meaningful features and to the reduce the feature number are also analyzed. To evaluate how much the textual document representation proposed in this master project can aid the managing and knowledge extraction from textual document collections, and the understanding of the results, three experiments were carried out: 1) textual document classication to analyze the predictive power of the bag-of-related-words features, 2) textual document clustering to analyze the quality of the cluster using the bag-of-related-words representation 3) topic hierarchies building and evaluation by domain experts. All the results and dimensionalities were compared to the bag-of-words representation. The results presented that the features of the bag-of-related-words representation have a predictive power as good as the features of the bag-of-words representation. The quality of the textual document clustering also was as good as the bag-of-words. The evaluation of the topic hierarchies by domain specialists presented better results when using the bag-of-related-words representation in all the questions analyzed

Este trabalho de mestrado insere-se no contexto do projeto de uma Ferramenta Inteligente de Apoio à Pesquisa (FIP), sendo desenvolvida no Laboratório de Inteligência Computacional do ICMC-USP. A ferramenta foi proposta para recuperar, organizar e minerar grandes conjuntos de documentos científicos (na área de computação). Nesse contexto, faz-se necessário um repositório de artigos para a FIP. Ou seja, um Data Warehouse que armazene e integre todas as informações extraídas dos documentos recuperados de diferentes páginas pessoais, institucionais e de repositórios de artigos da Web. Para suportar o processamento analítico on-line (OLAP) das informações e facilitar a ?mineração? desses dados é importante que os dados estejam armazenados apropriadamente. Dessa forma, o trabalho de mestrado teve como objetivo principal projetar um Data Warehouse (DW) para a ferramenta FIP e, adicionalmente, realizar experimentos com técnicas de mineração e Aprendizado de Máquina para automatizar o processo de indexação das informações e documentos armazenados no data warehouse (descoberta de tópicos). Para as consultas multidimensionais foram construídos data marts de forma a permitir aos pesquisadores avaliar tendências e a evolução de tópicos de pesquisa / This dissertation is related to the project of an Intelligent Tool for Research Supporting (FIP), being developed at the Laboratory of Computational Intelligence at ICMC-USP. The tool was proposed to retrieve, organize, and mining large sets of scientific documents in the field of computer science. In this context, a repository of articles becomes necessary, i.e., a Data Warehouse that integrates and stores all extracted information from retrieved documents from different personal and institutional web pages, and from article repositories. Data appropriatelly stored is decisive for supporting online analytical processing (OLAP), and ?data mining? processes. Thus, the main goal of this MSc research was design the FIP Data Warehouse (DW). Additionally, we carried out experiments with Data Mining and Machine Learning techniques in order to automatize the process of indexing of information and documents stored in the data warehouse (Topic Detection). Data marts for multidimensional queries were designed in order to facilitate researchers evaluation of research topics trend and evolution

Representações visuais têm sido adotadas na exploração de conjuntos de documentos, auxiliando a extração de conhecimento sem que seja necessária a análise individual de milhares de textos. Mapas de documentos, em particular, apresentam documentos individualmente representados espalhados em um espaço visual, refletindo suas relações de similaridade ou conexões. A construção destes mapas de documentos inclui, entre outras tarefas, o posicionamento dos textos e a identificação automática de áreas temáticas. Um desafio é a visualização de conjuntos dinâmicos de documentos. Na visualização de informação, é comum que alterações no conjunto de dados tenham um forte impacto na organização do espaço visual, dificultando a manutenção, por parte do usuário, de um mapa mental que o auxilie na interpretação dos dados apresentados e no acompanhamento das mudanças sofridas pelo conjunto de dados. Esta tese introduz um algoritmo para a construção dinâmica de mapas de documentos, capaz de manter uma disposição coerente à medida que elementos são adicionados ou removidos. O processo, inerentemente incremental e de baixa complexidade, utiliza um espaço bidimensional dividido em células, análogo a um tabuleiro de xadrez. Resultados consistentes foram alcançados em comparação com técnicas não incrementais de projeção de dados multidimensionais, tendo sido a técnica aplicada também em outros domínios, além de conjuntos de documentos. A visualização resultante não está sujeita a problemas de oclusão. A identificação de áreas temáticas é alcançada com técnicas de extração de regras de associação representativas para a identificação automática de tópicos. A combinação da extração de tópicos com a projeção incremental de dados em um processo integrado de mineração visual de textos compõe um espaço visual em que tópicos e áreas de interesse são destacados e atualizados à medida que o conjunto de dados é modificado / Visual representations are often adopted to explore document collections, assisting in knowledge extraction, and avoiding the thorough analysis of thousands of documents. Document maps present individual documents in visual spaces in such a way that their placement reflects similarity relations or connections between them. Building these maps requires, among other tasks, placing each document and identifying interesting areas or subsets. A current challenge is to visualize dynamic data sets. In Information Visualization, adding and removing data elements can strongly impact the underlying visual space. That can prevent a user from preserving a mental map that could assist her/him on understanding the content of a growing collection of documents or tracking changes on the underlying data set. This thesis presents a novel algorithm to create dynamic document maps, capable of maintaining a coherent disposition of elements, even for completely renewed sets. The process is inherently incremental, has low complexity and places elements on a 2D grid, analogous to a chess board. Consistent results were obtained as compared to (non-incremental) multidimensional scaling solutions, even when applied to visualizing domains other than document collections. Moreover, the corresponding visualization is not susceptible to occlusion. To assist users in indentifying interesting subsets, a topic extraction technique based on association rule mining was also developed. Together, they create a visual space where topics and interesting subsets are highlighted and constantly updated as the data set changes

Biagrupamento e coagrupamento são tarefas de mineração de dados que permitem a extração de informação relevante sobre dados e têm sido aplicadas com sucesso em uma ampla variedade de domínios, incluindo aqueles que envolvem dados textuais -- foco de interesse desta pesquisa. Nas tarefas de biagrupamento e coagrupamento, os critérios de similaridade são aplicados simultaneamente às linhas e às colunas das matrizes de dados, agrupando simultaneamente os objetos e os atributos e possibilitando a criação de bigrupos/cogrupos. Contudo suas definições variam segundo suas naturezas e objetivos, sendo que a tarefa de coagrupamento pode ser vista como uma generalização da tarefa de biagrupamento. Estas tarefas, quando aplicadas nos dados textuais, demandam uma representação em um modelo de espaço vetorial que, comumente, leva à geração de espaços caracterizados pela alta dimensionalidade e esparsidade, afetando o desempenho de muitos dos algoritmos. Este trabalho apresenta uma análise do comportamento do algoritmo para biagrupamento Cheng e Church e do algoritmo para coagrupamento de decomposição de valores em blocos não negativos (\\textit{Non-Negative Block Value Decomposition} - NBVD), aplicado ao contexto de dados textuais. Resultados experimentais quantitativos e qualitativos são apresentados a partir das experimentações destes algoritmos em conjuntos de dados sintéticos criados com diferentes níveis de esparsidade e em um conjunto de dados real. Os resultados são avaliados em termos de medidas próprias de biagrupamento, medidas internas de agrupamento a partir das projeções nas linhas dos bigrupos/cogrupos e em termos de geração de informação. As análises dos resultados esclarecem questões referentes às dificuldades encontradas por estes algoritmos nos ambiente de experimentação, assim como se são capazes de fornecer informações diferenciadas e úteis na área de mineração de texto. De forma geral, as análises realizadas mostraram que o algoritmo NBVD é mais adequado para trabalhar com conjuntos de dados em altas dimensões e com alta esparsidade. O algoritmo de Cheng e Church, embora tenha obtidos resultados bons de acordo com os objetivos do algoritmo, no contexto de dados textuais, propiciou resultados com baixa relevância / Biclustering e coclustering are data mining tasks that allow the extraction of relevant information about data and have been applied successfully in a wide variety of domains, including those involving textual data - the focus of interest of this research. In biclustering and coclustering tasks, similarity criteria are applied simultaneously to the rows and columns of the data matrices, simultaneously grouping the objects and attributes and enabling the discovery of biclusters/coclusters. However their definitions vary according to their natures and objectives, being that the task of coclustering can be seen as a generalization of the task of biclustering. These tasks applied in the textual data demand a representation in a model of vector space, which commonly leads to the generation of spaces characterized by high dimensionality and sparsity and influences the performance of many algorithms. This work provides an analysis of the behavior of the algorithm for biclustering Cheng and Church and the algorithm for coclustering non-negative block decomposition (NBVD) applied to the context of textual data. Quantitative and qualitative experimental results are shown, from experiments on synthetic datasets created with different sparsity levels and on a real data set. The results are evaluated in terms of their biclustering oriented measures, internal clustering measures applied to the projections in the lines of the biclusters/coclusters and in terms of generation of information. The analysis of the results clarifies questions related to the difficulties faced by these algorithms in the experimental environment, as well as if they are able to provide differentiated information useful to the field of text mining. In general, the analyses carried out showed that the NBVD algorithm is better suited to work with datasets in high dimensions and with high sparsity. The algorithm of Cheng and Church, although it obtained good results according to its own objectives, provided results with low relevance in the context of textual data

O número de documentos textuais disponíveis em formato digital tem aumentado incessantemente. Técnicas de Mineração de Textos são cada vez mais utilizadas para organizar e extrair conhecimento de grandes coleções de documentos textuais. Para o uso dessas técnicas é necessário que os documentos textuais estejam representados em um formato apropriado. A maioria das pesquisas de Mineração de Textos utiliza a abordagem bag-of-words para representar os documentos da coleção. Essa representação usa cada palavra presente na coleção de documentos como possível atributo, ignorando a ordem das palavras, informa ções de pontuação ou estruturais, e é caracterizada pela alta dimensionalidade e por dados esparsos. Por outro lado, a maioria dos conceitos são compostos por mais de uma palavra, como Inteligência Articial, Rede Neural, e Mineração de Textos. As abordagens que geram atributos compostos por mais de uma palavra apresentam outros problemas além dos apresentados pela representação bag-of-words, como a geração de atributos com pouco signicado e uma dimensionalidade muito maior. Neste projeto de mestrado foi proposta uma abordagem para representar documentos textuais nomeada bag-of-related-words. A abordagem proposta gera atributos compostos por palavras relacionadas com o uso de regras de associação. Com as regras de associação, espera-se identicar relações entre palavras de um documento, além de reduzir a dimensionalidade, pois são consideradas apenas as palavras que ocorrem ou que coocorrem acima de uma determinada frequência para gerar as regras. Diferentes maneiras de mapear o documento em transações para possibilitar a geração de regras de associação são analisadas. Diversas medidas de interesse aplicadas às regras de associação para a extração de atributos mais signicativos e a redução do número de atributos também são analisadas. Para avaliar o quanto a representação bag-of-related-words pode auxiliar na organização e extração de conhecimento de coleções de documentos textuais, e na interpretabilidade dos resultados, foram realizados três grupos de experimentos: 1) classicação de documentos textuais para avaliar o quanto os atributos da representação bag-of-related-words são bons para distinguir as categorias dos documentos; 2) agrupamento de documentos textuais para avaliar a qualidade dos grupos obtidos com a bag-of-related-words e consequentemente auxiliar na obtenção da estrutura de uma hierarquia de tópicos; e 3) construção e avaliação de hierarquias de tópicos por especialistas de domínio. Todos os resultados e dimensionalidades foram comparados com a representação bag-of-words. Pelos resultados dos experimentos realizados, pode-se vericar que os atributos da representação bag-of-related-words possuem um poder preditivo tão bom quanto os da representação bag-of-words. A qualidade dos agrupamentos de documentos textuais utilizando a representação bag-of-related-words foi tão boa quanto utilizando a representação bag-of-words. Na avaliação de hierarquias de tópicos por especialistas de domínio, a utilização da representação bag-of-related-words apresentou melhores resultados em todos os quesitos analisados / The amount of textual documents available in digital format is incredibly large. Text Mining techniques are becoming essentials to manage and extract knowledge in big textual document collections. In order to use these techniques, the textual documents need to be represented in an appropriate format to allow the construction of a model that represents the embedded knowledge in these textual documents. Most of the researches on Text Mining uses the bag-of-words approach to represent textual document collections. This representation uses each word in a collection as feature, ignoring the order of the words, structural information, and it is characterized by the high dimensionality and data sparsity. On the other hand, most of the concepts are compounded by more than one word, such as Articial Intelligence, Neural Network, and Text Mining. The approaches which generate features compounded by more than one word to solve this problem, suer from other problems, as the generation of features without meaning and a dimensionality much higher than that of the bag-of-words. An approach to represent textual documents named bag-of-related-words was proposed in this master thesis. The proposed approach generates features compounded by related words using association rules. We hope to identify relationships among words and reduce the dimensionality with the use of association rules, since only the words that occur and cooccur over a frequency threshold will be used to generate rules. Dierent ways to map the document into transactions to allow the extraction of association rules are analyzed. Dierent objective interest measures applied to the association rules to generate more meaningful features and to the reduce the feature number are also analyzed. To evaluate how much the textual document representation proposed in this master project can aid the managing and knowledge extraction from textual document collections, and the understanding of the results, three experiments were carried out: 1) textual document classication to analyze the predictive power of the bag-of-related-words features, 2) textual document clustering to analyze the quality of the cluster using the bag-of-related-words representation 3) topic hierarchies building and evaluation by domain experts. All the results and dimensionalities were compared to the bag-of-words representation. The results presented that the features of the bag-of-related-words representation have a predictive power as good as the features of the bag-of-words representation. The quality of the textual document clustering also was as good as the bag-of-words. The evaluation of the topic hierarchies by domain specialists presented better results when using the bag-of-related-words representation in all the questions analyzed