Com o grande crescimento dos volumes de dados que as organizações vêm registrando e a diversidade das fontes destes dados, o fato de se aproveitar informações contidas nessas massas de dados se tornou uma necessidade. Surgiu então uma área denominada Descoberta de Conhecimento em Bases de Dados (DCBD). Tal área utiliza alguns modelos, técnicas e algoritmos que realizam operações de extração de conhecimento útil de grandes volumes de dados. Entre as principais técnicas utilizadas para minerar os dados está a de Regras de Associação. A técnica de Regras de Associação se propõe a encontrar todas as associações relevantes entre um conjunto de itens aplicados a outros itens, e utiliza alguns algoritmos para realizar seu objetivo. Este estudo apresenta alguns algoritmos para a aplicação da técnica de Regras de Associação, também, busca abranger um pouco da tecnologia de Data Warehouse, muito útil para que o processo de mineração de dados possa ser realizado com maior sucesso. Neste trabalho são aplicadas técnicas de descoberta de conhecimento na área de saúde, vinculando dados referentes à situação socioeconômica do paciente com os procedimentos que foram realizados nas internações hospitalares a que foi submetido. Devido ao grande número de regras que poderiam se geradas resultantes das inúmeras possibilidades da base de dados, foi construído um protótipo de uma ferramenta para extração de regras de associação, que não só é baseado no suporte e confiança, mas também utiliza os conceitos de lift e improvement os quais ajudam na diminuição de regras triviais. Foram realizadas minerações com a base de dados de pacientes da Secretaria Municipal de Saúde de Londrina-PR, para análise da utilidade dos dados minerados. / The increasing amount of data that organization have been registering and the diversity of data sources have generate the necessity of extract knowledge from this mass of data. Based on this necessity a new area has emerged which is named Knowledge Discovery in Data Base (KDD). In this work apply the association rule mining technique in the public health area, linking social economic situation of patients which were attended in our hospitals. Because of large number of rules that can be produce we developed a prototype of a tool for extract association rules, not only based on support and confidence, but using too the measures lift and improvement in order to reduce the number of rules. Experiments were performed with the “Secretaria Municipal de Saúde de Londrina – PR” database

O casamento entre esquemas XML e esquemas relacionais é necessário em diversas aplicações, tais como integração de informação e intercâmbio de dados. Tipicamente o casamento de esquemas é um processo manual, talvez suportado por uma interface grá ca. No entanto, o casamento manual de esquemas muito grandes é um processo dispendioso e sujeito a erros. Disto surge a necessidade de técnicas (semi)-automáticas de casamento de esquemas que auxiliem o usuário fornecendo sugestões de casamento, dessa forma reduzindo o esforço manual aplicado nesta tarefa. Apesar deste tema já ter sido estudado na literatura, o casamento entre esquemas XML e esquemas relacionais é ainda um tema em aberto. Isto porque os trabalhos existentes ou se aplicam para esquemas de nidos no mesmo modelo, ou são genéricos demais para o problema em questão. O objetivo desta dissertação é o desenvolvimento de técnicas especí cas para o casamento de esquemas XML e esquemas relacionais. Tais técnicas exploram as particularidades existentes entre estes esquemas para inferir valores de similaridade entre eles. As técnicas propostas são avaliadas através de experimentos com esquemas do mundo real. / The matching between XML schemas and relational schemas has many applications, such as information integration and data exchange. Typically, schema matching is done manually by domain experts, sometimes using a graphical tool. However, the matching of large schemas is a time consuming and error-prone task. The use of (semi-)automatic schema matching techniques can help the user in nding the correct matches, thereby reducing his labor. The schema matching problem has already been addressed in the literature. Nevertheless, the matching of XML schemas and relational schemas is still an open issue. This comes from the fact that the existing work is whether speci c for schemas designed in the same model, or too generic for the problem in discussion. The mais goal of this dissertation is to develop speci c techniques for the matching of XML schemas and relational schemas. Such techniques exploit the particularities found when analyzing the two schemas together, and use these cues to leverage the matching process. The techniques are evaluated by running experiments with real-world schemas.

Este trabalho propõe a utilização de algoritmos de mineração de regras de associação para a Recuperação de Informações Multilíngues. Esses algoritmos têm sido amplamente utilizados para analisar transações de registro de vendas. A ideia é mapear o problema de encontrar associações entre itens vendidos para o problema de encontrar termos equivalentes entre idiomas diferentes em um corpus paralelo. A proposta foi validada por meio de experimentos com diferentes idiomas, conjuntos de consultas e corpora. Os resultados mostram que a eficácia da abordagem proposta é comparável ao estado da arte, ao resultado monolíngue e à tradução automática de consultas, embora este utilize técnicas mais complexas de processamento de linguagem natural. Foi criado um protótipo que faz consultas à Web utilizando o método proposto. O sistema recebe palavras-chave em português, as traduz para o inglês e submete a consulta a diversos sites de busca. / This work proposes the use of algorithms for mining association rules as an approach for Cross-Language Information Retrieval. These algorithms have been widely used to analyze market basket data. The idea is to map the problem of finding associations between sales items to the problem of finding term translations over a parallel corpus. The proposal was validated by means of experiments using different languages, queries and corpora. The results show that the performance of our proposed approach is comparable to the performance of the monolingual baseline and to query translation via machine translation, even though these systems employ more complex Natural Language Processing techniques. A prototype for cross-language web querying was implemented to test the proposed method. The system accepts keywords in Portuguese, translates them into English and submits the query to several web-sites that provide search functionalities.

Bibliotecas digitais tornaram-se uma importante fonte de informação para comunidades científicas. Entretanto, por coletar dados de diferentes fontes, surge o problema de informações ambíguas ou duplicadas de nomes de autores. Métodos tradicionais de desambiguação de nomes utilizam informação sintática de atributos. Todavia, recentemente o uso de redes de relacionamentos, que traz informação semântica, tem sido estudado em desambiguação de dados. Em desambiguação de nomes de autores, relações de co-autoria podem ser usadas para criar uma rede social, que pode ser utilizada para melhorar métodos de desambiguação de nomes de autores. Esta dissertação apresenta um estudo do impacto de adicionar análise de redes sociais a métodos de desambiguação de nomes de autores baseados em informação sintática de atributos. Nós apresentamos uma abordagem de aprendizagem de máquina baseada em Programação Genética e a utilizamos para avaliar o impacto de adicionar análise de redes sociais a desambiguação de nomes de autores. Através de experimentos usando subconjuntos de bibliotecas digitais reais, nós demonstramos que o uso de análise de redes sociais melhora de forma significativa a qualidade dos resultados. Adicionalmente, nós demonstramos que as funções de casamento criadas por nossa abordagem baseada em Programação Genética são capazes de competir com métodos do estado da arte. / Digital libraries have become an important source of information for scientific communities. However, by gathering data from different sources, the problem of duplicate and ambiguous information about author names arises. Traditional methods of name disambiguation use syntactic attribute information. However, recently the use of relationship networks, which provides semantic information, has been studied in data disambiguation. In author name disambiguation, the co-authorship relations can be used to create a social network, which can be used to improve author name disambiguation methods. This dissertation presents a study of the impact of adding social network analysis to author name disambiguation methods based on syntactic attribute information. We present a machine learning approach based on Genetic Programming and use it to evaluate the impact of social network analysis in author name disambiguation. Through experiments using subsets of real digital libraries, we show that the use of social network analysis significantly improves the quality of results. Also, we demonstrate that match functions created by our Genetic Programming approach are able to compete with state-of-the-art methods.

Plágio é um dos delitos mais graves no meio acadêmico. É definido como “o uso do trabalho de uma pessoa sem a devida referência ao trabalho original”. Em contrapartida a esse problema, existem diversos métodos que tentam detectar automaticamente plágio entre documentos. Nesse contexto, esse trabalho propõe um novo método para Análise de Plágio Multilíngue. O objetivo do método é detectar casos de plágio em documentos suspeitos baseado em uma coleção de documentos ditos originais. Para realizar essa tarefa, é proposto um método de detecção de plágio composto por cinco fases principais: normalização do idioma, recuperação dos documentos candidatos, treinamento do classificador, análise de plágio, pós-processamento. Uma vez que o método é projetado para detectar plágio entre documentos escritos em idiomas diferentes, nós usamos um language guesser para identificar o idioma de cada documento e um tradutor automático para traduzir todos os documentos para um idioma comum (para que eles possam ser analisados de uma mesma forma). Após a normalização, nós aplicamos um algoritmo de classificação com o objetivo de construir um modelo que consiga diferenciar entre um trecho plagiado e um trecho não plagiado. Após a fase de treinamento, os documentos suspeitos podem ser analisados. Um sistema de recuperação é usado para buscar, baseado em trechos extraídos de cada documento suspeito, os trechos dos documentos originais que são mais propensos de terem sido utilizados como fonte de plágio. Somente após os trechos candidatos terem sido retornados, a análise de plágio é realizada. Por fim, uma técnica de pós-processamento é aplicada nos resultados da detecção a fim de juntar os trechos plagiados que estão próximos um dos outros. Nós avaliamos o métodos utilizando três coleções de testes disponíveis. Duas delas foram criadas para as competições PAN (PAN’09 e PAN’10), que são competições internacionais de detecção de plágio. Como apenas um pequeno percentual dos casos de plágio dessas coleções era multilíngue, nós criamos uma coleção com casos de plágio multilíngue artificiais. Essa coleção foi chamada de ECLaPA (Europarl Cross-Language Plagiarism Analysis). Os resultados alcançados ao analisar as três coleções de testes mostraram que o método proposto é uma alternativa viável para a tarefa de detecção de plágio multilíngue. / Plagiarism is one of the most serious forms of academic misconduct. It is defined as “the use of another person's written work without acknowledging the source”. As a countermeasure to this problem, there are several methods that attempt to automatically detect plagiarism between documents. In this context, this work proposes a new method for Cross-Language Plagiarism Analysis. The method aims at detecting external plagiarism cases, i.e., it tries to detect the plagiarized passages in the suspicious documents (the documents to be investigated) and their corresponding text fragments in the source documents (the original documents). To accomplish this task, we propose a plagiarism detection method composed by five main phases: language normalization, retrieval of candidate documents, classifier training, plagiarism analysis, and postprocessing. Since the method is designed to detect cross-language plagiarism, we used a language guesser to identify the language of the documents and an automatic translation tool to translate all the documents in the collection into a common language (so they can be analyzed in a uniform way). After language normalization, we applied a classification algorithm in order to build a model that is able to differentiate a plagiarized text passage from a non-plagiarized one. Once the classifier is trained, the suspicious documents can be analyzed. An information retrieval system is used to retrieve, based on passages extracted from each suspicious document, the passages from the original documents that are more likely to be the source of plagiarism. Only after the candidate passages are retrieved, the plagiarism analysis is performed. Finally, a postprocessing technique is applied in the reported results in order to join the contiguous plagiarized passages. We evaluated our method using three freely available test collections. Two of them were created for the PAN competitions (PAN’09 and PAN’10), which are international competitions on plagiarism detection. Since only a small percentage of these two collections contained cross-language plagiarism cases, we also created an artificial test collection especially designed to contain this kind of offense. We named the test collection ECLaPA (Europarl Cross-Language Plagiarism Analysis). The results achieved while analyzing these collections showed that the proposed method is a viable approach to the task of cross-language plagiarism analysis.

Consultas por palavras-chave permitem o acesso fácil a dados XML, uma vez que não exigem que o usuário aprenda uma linguagem de consulta estruturada nem estude possíveis esquemas de dados complexos. Com isso, vários motores de busca XML foram propostos para permitir a extração de fragmentos XML relevantes para consultas por palavras-chave. No entanto, esses motores de busca tratam as expressões temporais da mesma forma que qualquer outra palavra-chave. Essa abordagem ocasiona inúmeros problemas, como por exemplo, considerar como casamentos para uma expressão temporal nodos do domínio preço ou código. Este trabalho descreve TPI (Two Phase Interception), uma abordagem que permite o suporte a consultas temporais por palavras-chave em documentos XML orientados a dados. O suporte a consultas temporais é realizado através de uma camada adicional de software que executa duas interceptações no processamento de consultas, realizado por um motor de busca XML. Esta camada adicional de software é responsável pelo tratamento adequado das informações temporais presentes na consulta e no conteúdo dos documentos XML. O trabalho ainda especifica TKC (Temporal Keyword Classification), uma classificação de consultas temporais que serve de guia para qualquer mecanismo de consulta por palavras-chave, inclusive TPI. São apresentados os algoritmos de mapeamento das diferentes formas de predicados temporais por palavras-chave, especificadas em TKC, para expressões relacionais a fim de orientar a implementação do processamento das consultas temporais. É proposto um índice temporal e definidas estratégias para identificação de caminhos temporais, desambiguação de formatos de valores temporais, identificação de datas representadas por vários elementos e identificação de intervalos temporais. São demonstrados experimentos que comparam a qualidade, o tempo de processamento e a escalabilidade de um motor de busca XML com e sem a utilização de TPI. A principal contribuição desse trabalho é melhorar significativamente a qualidade dos resultados de consultas temporais por palavras-chave em documentos XML. / Keyword queries enable users to easily access XML data, since the user does not need to learn a structured query language or study possibly complex data schemas. Therewith, several XML search engines have been proposed to extract relevant XML fragments in response to keyword queries. However, these search engines treat the temporal expressions as any other keyword. This approach may lead to several problems. It could, for example, consider prices and codes as matches to a temporal expression. This work describes TPI (Two Phase Interception), an approach that supports temporal keyword queries on data-centric XML documents. The temporal query support is performed by adding an additional software layer that executes two interceptions in the query processing performed by a XML search engine. This additional software layer is responsible for the adequate treatment of the temporal expressions contained in the query and in the contents of the XML documents. This work also specifies TKC (Temporal Keyword Classification), a temporal query classification to be used as guidance for any keyword query mechanism, including TPI. We present the algorithms for mapping different temporal predicates expressed by keywords to relational expressions in order to guide the implementation of the temporal query processing. We propose a temporal index together with strategies to perform temporal path identification, format disambiguation, identification of dates represented by many elements and detection of temporal intervals. This work also reports on experiments which evaluate quality, processing time and scalability of an XML search engine with TPI and without TPI. The main contribution of this work is the significant improvement in the quality of the results of temporal keyword queries on XML documents.

Over theWeb, distributed and heterogeneous sources with structured and related content form rich repositories of information commonly referred to as dataspaces. To provide access to this heterogeneous data, information integration systems have traditionally relied on the availability of a mediated schema, along with mappings between this schema and the schema of the source schemas. On dataspaces, where sources are plentiful, autonomous and extremely volatile, a system based on the existence of a pre-defined mediated schema and mapping information presents several drawbacks. Notably, the cost of keeping the mappings up to date as new sources are found or existing sources change can be prohibitively high. We propose a novel querying architecture that requires neither a mediated schema nor source mappings, which is based mainly on indexing mechanisms and on-the-fly rewriting algorithms. Our indexes are designed for data that is represented as relations, and are able to capture the structure of the sources, their instances and the connections between them. In the absence of a mediated schema, the user formulates structured queries based on what she expects to find. These queries are rewritten using a best-effort approach: the proposed rewriting algorithms compare a user query against the source schemas and produces a set of rewritings based on the matches found. Based on this architecture, two different querying approaches are tested. Experiments show that the indexing and rewriting algorithms are scalable, i.e., able to handle a very large number of structured Web sources; and that support simple, yet expressive queries that exploit the inherent structure of the data.

Este trabalho é dedicado ao estudo e à aplicação da mineração de regras de associação a fim de descobrir padrões de navegação no ambiente Web. As regras de associação são padrões descritivos que representam a probabilidade de um conjunto de itens aparecer em uma transação visto que outro conjunto está presente. Dentre as possibilidades de aplicação da mineração de dados na Web, a mineração do seu uso consiste na extração de regras e padrões que descrevam o perfil dos visitantes aos sites e o seu comportamento navegacional. Neste contexto, alguns trabalhos já foram propostos, contudo diversos pontos foram deixados em aberto por seus autores. O objetivo principal deste trabalho é a apresentação de um modelo para a extração de regras de associação aplicado ao uso da Web. Este modelo, denominado Access Miner, caracteriza-se por enfocar as etapas do processo de descoberta do conhecimento desde a obtenção dos dados até a apresentação das regras obtidas ao analista. Características específicas do domínio foram consideradas, como a estrutura do site, para o pósprocessamento das regras mineradas a fim de selecionar as potencialmente mais interessantes e reduzir a quantidade de regras a serem apreciadas. O projeto possibilitou a implementação de uma ferramenta para a automação das diversas etapas do processo, sendo consideradas, na sua construção, as características de interatividade e iteratividade, necessárias para a descoberta e consolidação do conhecimento. Finalmente, alguns resultados foram obtidos a partir da aplicação desta ferramenta em dois casos, de forma que o modelo proposto pôde ser validado.

A maioria das empresas interage com seus clientes através de computadores. Com o passar do tempo está armazenado nos computadores um histórico da atividade da empresa que pode ser explorado para a melhoria do processo de tomada de decisões. Ferramentas de descoberta de conhecimento em bancos de dados exploram este histórico a fim de extrair vários tipos de informação. Um dos tipos de informação que pode ser extraída destes tipos de bancos de dados são as regras de associação que consistem em relacionamentos ou dependências importantes entre itens tal que a presença de alguns itens em uma transação irá implicar a presença de outros itens na mesma transação. Neste trabalho são aplicadas técnicas de descoberta de conhecimento na área do comércio varejista de confecção. Foram detectadas algumas peculiaridades dos bancos de dados desta área sendo proposto um novo algoritmo para melhorar o desempenho da tarefa de extração de regras de associação. Para a validação dos resultados apresentados pelo algoritmo foi desenvolvido o protótipo de uma ferramenta para extração de regras de associação. Foram realizados experimentos com bancos de dados reais de uma empresa da área de comércio varejista de confecção para análise de desempenho do algoritmo.

Em sistemas reais, os dados armazenados tipicamente apresentam inconsistências causadas por erros de gra a, abreviações, caracteres trocados, entre outros. Isto faz com que diferentes representações do mesmo objeto do mundo real sejam registrados como elementos distintos, causando um problema no momento de consultar os dados. Portanto, o problema investigado nesta tese refere-se às consultas por abrangência, que procuram encontrar objetos que representam o mesmo objeto real consultado . Esse tipo de consulta não pode ser processado por coincidência exata, necessitando de um mecanismo de consulta com suporte à similaridade. Para cada consulta submetida a uma determinada coleção, a função de similaridade produz um ranking dos elementos dessa coleção ordenados pelo valor de similaridade entre cada elemento e o objeto consulta. Como somente os elementos que são variações do objeto consulta são relevantes e deveriam ser retornados, é necessário o uso de um limiar para delimitar o resultado. O primeiro desa o das consultas por abrangência é a de nição do limiar. Geralmente é o especialista humano que faz a estimativa manualmente através da identi - cação de elementos relevantes e irrelevantes para cada consulta e em seguida, utiliza uma medida como revocação e precisão (R&P). A alta dependência do especialista humano di culta o uso de consultas por abrangência na prática, principalmente em grandes coleções. Por esta razão, o método apresentado nesta tese tem por objetivo estimar R&P para vários limiares com baixa dependência do especialista humano. Como um sub-produto do método, também é possível selecionar o limiar mais adequado para uma função sobre uma determinada coleção. Considerando que as funções de similaridade são imperfeitas e que apresentam níveis diferentes de qualidade, é necessário avaliar a função de similaridade para cada coleção, pois o resultado é dependente dos dados. Um limiar para uma coleção pode ser totalmente inadequado para outra coleção, embora utilizando a mesma função de similaridade. Como forma de medir a qualidade de funções de similaridade no contexto de consultas por abrangência, esta tese apresenta a discernibilidade. Trata-se de uma medida que de ne a habilidade da função de similaridade de separar elementos relevantes e irrelevantes. Comparando com a precisão média, a discernibilidade captura variações que não são percebidas pela precisão média, o que mostra que a discernibilidade é mais apropriada para consultas por abrangência. Uma extensa avaliação experimental usando dados reais mostra a viabilidade tanto do método de estimativas como da medida de discernibilidade para consultas por abrangência. / In real systems, stored data typically have inconsistencies caused by typing errors, abbreviations, transposed characters, amongst others. For this reason, di erent representations of the same real world object are stored as distinct elements, causing problems during query processing. In this sense, this thesis investigates range queries which nd objects that represent the same real world object being queried . This type of query cannot be processed by exact matching, thus requiring the support for querying by similarity. For each query submitted to a given collection, the similarity function produces a ranked list of all elements in this collection. This ranked list is sorted decreasingly by the similarity score value with the query object. Only the variations of the query object should be part of the result as only those items are relevant. For this reason, it is necessary to apply a threshold value to properly split the ranking. The rst challenge of range queries is the de nition of a proper threshold. Usually, a human specialist makes the estimation manually through the identi cation of relevant and irrelevant elements for each query. Then, he/she uses measures such as recall and precision (R&P). The high dependency on the human specialist is the main di culty related to use of range queries in real situations, specially for large collections. In this sense, the method presented in this thesis has the objective of estimating R&P at several thresholds with low human intervention. As a by-product of this method, it is possible to select the optimal threshold for a similarity function in a given collection. Considering the fact that the similarity functions are imperfect and vary in quality, it is necessary to evaluate the similarity function for each collection as the result is domain dependent. A threshold value for a collection could be totally inappropriate for another, even though the same similarity function is applied. As a measure of quality of similarity functions for range queries, this thesis introduces discernability. This is a measure to quantify the ability of the similarity function in separating relevant and irrelevant elements. Comparing discernability and mean average precision, the rst one can capture variations that are not noticed by precision-based measures. This property shows that discernability presents better results for evaluating similarity functions for range queries. An extended experimental evaluation using real data shows the viability of both, the estimation method and the discernability measure, applied to range queries.