Doctor of Philosophy / Department of Computing and Information Sciences / William H. Hsu / Association rule learning is a data mining technique that can capture relationships between pairs of entities in different domains. The goal of this research is to discover factors from data that can improve the precision, recall, and accuracy of association rules found using interestingness measures and frequent itemset mining. Such factors can be calibrated using validation data and applied to rank candidate rules in domain-dependent tasks such as link existence prediction. In addition, I use interestingness measures themselves as numerical features to improve link existence prediction. The focus of this dissertation is on developing and testing an analytical framework for association rule interestingness measures, to make them sensitive to the relative size of itemsets. I survey existing interestingness measures and then introduce adaptive parametric models for normalizing and optimizing these measures, based on the size of itemsets containing a candidate pair of co-occurring entities. The central thesis of this work is that in certain domains, the link strength between entities is related to the rarity of their shared memberships (i.e., the size of itemsets in which they co-occur), and that a data-driven approach can capture such properties by normalizing the quantitative measures used to rank associations. To test this hypothesis under different levels of variability in itemset size, I develop several test bed domains, each containing an association rule mining task and a link existence prediction task. The definitions of itemset membership and link existence in each domain depend on its local semantics. My primary goals are: to capture quantitative aspects of these local semantics in normalization factors for association rule interestingness measures; to represent these factors as quantitative features for link existence prediction, to apply them to significantly improve precision and recall in several real-world domains; and to build an experimental framework for measuring this improvement, using information theory and classification-based validation.

Master of Science / Department of Computing and Information Sciences / Doina Caragea / William H. Hsu / An ontology can be seen as an explicit description of the concepts and relationships that exist in a domain. In this thesis, we address the problem of building an interests' ontology and using the same to construct features for predicting both potential friendship relations between users in the social network Live Journal, and users' interests. Previous work has shown that the accuracy of predicting friendship links in this network is very low if simply interests common to two users are used as features and no network graph features are considered. Thus, our goal is to organize users' interests into an ontology (specifically, a concept hierarchy) and to use the semantics captured by this ontology to improve the performance of learning algorithms at the task of predicting if two users can be friends. To achieve this goal, we have designed and implemented a hybrid clustering algorithm, which combines hierarchical agglomerative and divisive clustering paradigms, and automatically builds the interests' ontology. We have explored the use of this ontology to construct interest-based features and shown that the resulting features improve the performance of various classifiers for predicting friendships in the Live Journal social network. We have also shown that using the interests' ontology, one can address the problem of predicting the interests of Live Journal users, a task that in absence of the ontology is not feasible otherwise as there is an overwhelming number of interests.

Context. The advances in location-acquisition and mobile computing techniques have generated massive spatial trajectory data. Such spatial trajectory data accumulated by telecommunication operators is huge, analyzing the data with a right tool or method can uncover patterns and connections which can be used for improving telecom services. Forecasting trajectory data or predicting next location of users is one of such analysis. It can be used for producing synthetic data and also to determine the network capacity needed for a cell tower in future. Objectives. The objectives of this thesis is, Firstly, to have a new application for CWT (Collapsed Weighted Tensor) method. Secondly, to modify the CWT method to predict the location of a user. Thirdly, to provide a suitable method for the given Telenor dataset to predict the user’s location over a period of time.   Methods. The thesis work has been carried out by implementing the modified CWT method. The predicted location obtained by modified CWT cannot be determined to which time stamp it belongs as the given Telenor dataset contains missing time stamps. So, the modified CWT method is implemented in two different methods. Replacing missing values with first value in dataset. Replacing missing values with second value in dataset. These two methods are implemented and determined which method can predict the location of users with minimal error.   Results. The results are carried by assuming that the given Telenor dataset for one week will be same as that for the next week. Users are selected in a random sample and above mentioned methods are performed. Furthermore, RMSD values and computational time are calculated for each method and selected users.   Conclusion. Based on the analysis of the results, Firstly, it can be concluded that CWT method have been modified and used for predicting the user’s location for next time stamp. Secondly, the method can be extended to predict over a period of time. Finally, modified CWT method predicts location of the user with minimal error when missing values are replaced by first value in the dataset.

La prédiction de connexions entre objets, basée soit sur une observation bruitée, soit sur une suite d'observations est un problème d'intérêt pour un nombre d'applications allant de la conception de système de recommandation en commerce électronique et réseaux sociaux jusqu'à l'inférence de réseaux en biologie moléculaire. Ce travail présente des formulations du problème de prédiction de lien, dans les cadres statique et temporel, comme un problème régularisé. Dans le scénario statique c'est la combinaison de deux normes bien connues, la norme L1 et la trace-norme qui permet de prédire les liens, alors que dans le cas dynamique, l'utilisation d'un modèle autoregressif sur des descripteurs linéaires permet d'améliorer la qualité de la prédiction. Nous étudierons la nature des solutions des problèmes d'optimisation à la fois en termes statistique et algorithmique. Des résultats empiriques encourageant mettent en évidence l'apport de la méthodologie adoptée. / Predicting connections among objects, based either on a noisy observation or on a sequence of observations, is a problem of interest for numerous applications such as recommender systems for e-commerce and social networks, and also in system biology, for inferring interaction patterns among proteins. This work presents formulations of the graph prediction problem, in both dynamic and static scenarios, as regularization problems. In the static scenario we encode the mixture of two different kinds of structural assumptions in a convex penalty involving the L1 and the trace norm. In the dynamic setting we assume that certain graph features, such as the node degree, follow a vector autoregressive model and we propose to use this information to improve the accuracy of prediction. The solutions of the optimization problems are studied both from an algorithmic and statistical point of view. Empirical evidences on synthetic and real data are presented showing the benefit of using the suggested methods.

Comorbidade é a coocorrência de dois ou mais distúrbios em uma pessoa. Identificar quais fatores genéticos ou quais são os mecanismos subjacentes à comorbidade é um grande desafio da ciência. Outra constatação relevante é que muitos pares de doenças que compartilham genes comuns não mostram comorbidade significativa nos registros clínicos. Vários estudos clínicos e epidemiológicos têm demonstrado que a comorbidade é uma situação médica universal porque pacientes com vários transtornos médicos são a regra e não a exceção. Neste trabalho, é proposta uma metodologia de predição de associação doença-doença por meio da integração de dados públicos sobre genes e sobre doenças e suas comorbidades. Analisando as redes formadas pelos genes e pelas doenças, a partir da utilização de cinco métodos de predição de links: Vizinhos Comuns, Adamic-Adar, Índice de Conexão Preferencial, Índice de Alocação de Recursos e Katz, a fim de encontrar novas relações de comorbidade. Como resultados foram criadas duas redes: uma rede epidemiológica chamada de rede_DATASUS com 1.941 nós e 248.508 arestas e uma rede gênica, rede_KEGG, com 288 nós e 1.983 arestas. E a predição em cima da rede_KEGG, e dentre as associações de doenças preditas e analisadas encontramos 6 associações preditas que estão presentes na rede_DATASUS e relatos na literatura. Acreditamos que as associações entre genes podem elucidar as causas de algumas comorbidades / Comorbidity is the co-occurrence of two or more heath disturbances in a person. Identify which genetic factors or what are the biological mechanisms underlying the comorbidity is a big challenge in science. Another relevant finding is that many pairs of diseases that share common genes do not show significant comorbidity clinical records. Several clinical and epidemiological studies have shown that comorbidity is a universal medical situation because patients with various medical disorders are the rule and not the exception In this work, a methodology of prediction of disease-illness is provided through the integration of data on genes and on diseases and their comorbidities. Analyzing how to redesign genes and diseases, using five link prediction methods: Common Neighbours, Adamic-Adar, Preferential Attachment Index, Resource Allocation Index and emph Katz, an end to find new relationships of comorbidity. As a redesigned network: an epidemiological network called network_DATASUS network with 1,941 nodes and 248,508 edges and a genetic network, network_KEGG, with 288 nodes and 1,983 edges. And the prediction over network_KEGG, and among the predicted and analyzed combinations are 6 predicted classes that are present in network_DATASUS and reports in the literature. We believe that the associations between genes can elucidate the causes of some comorbidities

Most of the reference information, nowadays, is found in repositories of documents semantically linked, created in a collaborative fashion and freely available in the web. Among the many problems faced by content providers in these repositories, one of the most important is Wikification, that is, the placement of links in the articles. These links have to support user navigation and should provide a deeper semantic interpretation of the content. Wikification is a hard task since the continuous growth of such repositories makes it increasingly demanding for editors. As consequence, they have their focus shifted from content creation, which should be their main objective. This has motivated the design of automatic Wikification tools which, traditionally, address two distinct problems: (a) how to identify which words (or phrases) in an article should be selected as anchors and (b) how to determine to which article the link, associated with the anchor, should point. Most of the methods in literature that address these problems are based on machine learning approaches which attempt to capture, through statistical features, characteristics of the concepts and its associations. Although these strategies handle the repository as a graph of concepts, normally they take limited advantage of the topological structure of this graph, as they describe it by means of human-engineered link statistical features. Despite the effectiveness of these machine learning methods, better models should take full advantage of the information topology if they describe it by means of data-oriented approaches such as matrix factorization. This indeed has been successfully done in other domains, such as movie recommendation. In this work, we fill this gap, proposing a wikification prediction model that combines the strengths of traditional predictors based on statistical features with a latent component which models the concept graph topology by means of matrix factorization. By comparing our model with a state-of-the-art wikification method, using a sample of Wikipedia articles, we obtained a gain up to 13% in F1 metric. We also provide a comprehensive analysis of the model performance showing the importance of the latent predictor component and the attributes derived from the associations between the concepts. The study still includes the analysis of the impact of ambiguous concepts, which allows us to conclude the model is resilient to ambiguity, even though does not include any explicitly disambiguation phase. We finally study the impact of selecting training samples from specific content quality classes, an information that is available in some respositories, such as Wikipedia. We empirically shown that the quality of the training samples impact on precision and overlinking, when comparing training performed using random quality samples versus high quality samples. / Atualmente, informações de referência são disponibilizadas através de repositórios de documentos semanticamente ligados, criados de forma colaborativa e com acesso livre na Web. Entre os muitos problemas enfrentados pelos provedores de conteúdo desses repositórios, destaca-se a Wikification, isto é, a inclusão de links nos artigos desses repositórios. Esses links possibilitam a navegação pelos artigos e permitem ao usuário um aprofundamento semântico do conteúdo. A Wikification é uma tarefa complexa, uma vez que o crescimento contínuo de tais repositórios resulta em um esforço cada vez maior dos editores. Como consequência, eles têm seu foco desviado da criação de conteúdo, que deveria ser o seu principal objetivo. Isso tem motivado o desenvolvimento de ferramentas de Wikification automática que, tradicionalmente, abordam dois problemas distintos: (a) como identificar que palavras (ou frases) em um artigo deveriam ser selecionados como texto de âncora e (b) como determinar para que artigos o link, associado ao texto de âncora, deveria apontar. A maioria dos métodos na literatura que abordam esses problemas usam aprendizado de máquina. Eles tentam capturar, através de atributos estatísticos, características dos conceitos e seus links. Embora essas estratégias tratam o repositório como um grafo de conceitos, normalmente elas pouco exploram a estrutura topológica do grafo, uma vez que se limitam a descrevê-lo por meio de atributos estatísticos dos links, projetados por especialistas humanos. Embora tais métodos sejam eficazes, novos modelos poderiam tirar mais proveito da topologia se a descrevessem por meio de abordagens orientados a dados, tais como a fatoração matricial. De fato, essa abordagem tem sido aplicada com sucesso em outros domínios como recomendação de filmes. Neste trabalho, propomos um modelo de previsão para Wikification que combina a força dos previsores tradicionais baseados em atributos estatísticos, projetados por seres humanos, com um componente de previsão latente, que modela a topologia do grafo de conceitos usando fatoração matricial. Ao comparar nosso modelo com o estado-da-arte em Wikification, usando uma amostra de artigos Wikipédia, observamos um ganho de até 13% em F1. Além disso, fornecemos uma análise detalhada do desempenho do modelo enfatizando a importância do componente de previsão latente e dos atributos derivados dos links entre os conceitos. Também analisamos o impacto de conceitos ambíguos, o que permite concluir que nosso modelo se porta bem mesmo diante de ambiguidade, apesar de não tratar explicitamente este problema. Ainda realizamos um estudo sobre o impacto da seleção das amostras de treino conforme a qualidade dos seus conteúdos, uma informação disponível em alguns repositórios, tais como a Wikipédia. Nós observamos que o treino com documentos de alta qualidade melhora a precisão do método, minimizando o uso de links desnecessários.

Diferentes sistemas do mundo real podem ser representados por redes. As redes são estruturas nas quais seus vértices (nós) representam entidades e links representam relações entre essas entidades. Além disso, as redes caracterizam-se por ser estruturas dinâmicas, o que implica na rápida aparição e desaparição de entidades e seus relacionamentos. Nesse cenário, um dos problemas importantes a serem enfrentados no contexto das redes, é da predição de links, isto é, prever a ocorrência futura de um link ainda não existente entre dois vértices com base nas informações já existentes. A importância da predição de links deve-se ao fato de ter aplicações na recuperação de informação, identificação de interações espúrias e, ainda, na avaliação de mecanismos de evolução das redes. Para enfrentar o problema da predição de links, a maioria dos métodos utiliza informações da vizinhança topológica das redes para atribuir um valor que represente a probabilidade de conexão futura entre um par de vértices analisados. No entanto, recentemente têm aparecido métodos híbridos, caracterizados por usar outras informações além da vizinhança topológica, sendo as informações das comunidades as normalmente usadas, isso, devido ao fato que, ao serem grupos de vértices densamente ligados entre si e esparsamente ligados com vértices de outros grupos, fornecem informações que podem ser úteis para determinar o comportamento futuro das redes. Assim, neste trabalho são apresentadas duas propostas na linha dos métodos baseados nas informações das comunidades para predição de links. A primeira proposta consiste em um novo índice de similaridade que usa as informações dos vértices pertencentes a mesma comunidade na vizinhança de um par de vértices analisados, bem como as informações dos vértices pertencentes a diferentes comunidades nessa mesma vizinhança. A segunda proposta consiste de um conjunto de índices obtidos a partir da reformulação de algumas propostas já existentes, porém, inserindo neles informações dos vértices pertencentes unicamente à mesma comunidade na vizinhança topológica de um par de vértices analisados. Experimentos realizados em dez redes complexas de diferentes domínios demonstraram que, em geral, os índices propostos obtiveram desempenho superior às abordagens usuais / Different real-world systems can be represented as networks. Networks are structures in which vertices (nodes) represent entities and links represent relationships between these entities. Moreover, networks are dynamic structures, which implies rapid appearance and disappearance of entities and their relationships. In this scenario, the link prediction problem attempts to predict the future existence of a link between a pair of vertices considering existing information. The link prediction importance is due to the fact of having different applications in areas such as information retrieval, identification of spurious interactions, as well as for understanding mechanisms of network evolution. To address the link prediction problem, many proposals use topological information to assign a value that represents the likelihood of a future connection between a pair of vertices. However, hybrid methods have appeared recently. These methods use additional information such as community information. Communities are groups of vertices densely connected among them and sparsely connected to vertices from other groups, providing useful information to determinate the future behavior of networks. So, this research presents two proposals for link prediction based on communities information. The first proposal consists of a new similarity index that uses information about the communities that the vertices in the neighborhood of a analyzed pair of vertices belong. The second proposal is a set of indices obtained from the reformulation of various existing proposals, however, using only the information from vertices belonging to the same community in the neighborhood of a pair of vertices analyzed. Experiments conducted in ten complex networks of different fields show the proposals outperform traditional approaches

Predição de Links é uma área de pesquisa importante no contexto de Análise de Redes Sociais tendo em vista que predizer sua evolução é um mecanismo útil para melhorar e propiciar a comunicação entre usuários. Nas redes de coautoria isso pode ser utilizado para recomendação de usuários com interesses de pesquisa comuns. Este trabalho propõe um processo sistemático baseado em métricas não-dicotômicas para avaliação de predição de links em redes de coautoria, sendo considerada a definição de métodos para as seguintes tarefas identificadas: seleção de dados, determinação de novos links e avaliação dos resultados. Para seleção de dados definiu-se um sensor fuzzy baseado em atributos dos nós. O uso de composições fuzzy foi considerado para determinação de novos links _ponderados_ entre dois autores, adotando-se não apenas atributos dos nós, mas também a combinação de atributos de outros links observados. O link ponderado é denominado _qualidade da relação_ e é obtido pelo uso de propriedades estruturais da rede. Para avaliação dos resultados foi proposta a curva ROC fuzzy, que permite explorar os pesos dos links não apenas para ordenação dos exemplos. / Link prediction is an important research line in the Social Network Analysis context, as predicting the evolution of such nets is a useful mechanism to improve and encourage communication among users. In co-authorship networks, it can be used for recommending users with common research interests. This work proposes a systematic process based on non-dichotomic metrics for evaluation of link prediction in co-authorship networks considering the definition of methods for the following tasks: data selection, new link determination and result evaluation. Fuzzy sensor based on node attributes is adopted for data selection. Fuzzy compositions are used to predict new link weights between two authors, adopting not only attributes nodes, but also the combination of attributes of other observed links. The link weight called _relation quality_ is obtained by using structural features of the social network. The fuzzy roc curve is used for results evaluation, allowing us to consider the weights of the links and not only the ordering of examples.

Most of the reference information, nowadays, is found in repositories of documents semantically linked, created in a collaborative fashion and freely available in the web. Among the many problems faced by content providers in these repositories, one of the most important is Wikification, that is, the placement of links in the articles. These links have to support user navigation and should provide a deeper semantic interpretation of the content. Wikification is a hard task since the continuous growth of such repositories makes it increasingly demanding for editors. As consequence, they have their focus shifted from content creation, which should be their main objective. This has motivated the design of automatic Wikification tools which, traditionally, address two distinct problems: (a) how to identify which words (or phrases) in an article should be selected as anchors and (b) how to determine to which article the link, associated with the anchor, should point. Most of the methods in literature that address these problems are based on machine learning approaches which attempt to capture, through statistical features, characteristics of the concepts and its associations. Although these strategies handle the repository as a graph of concepts, normally they take limited advantage of the topological structure of this graph, as they describe it by means of human-engineered link statistical features. Despite the effectiveness of these machine learning methods, better models should take full advantage of the information topology if they describe it by means of data-oriented approaches such as matrix factorization. This indeed has been successfully done in other domains, such as movie recommendation. In this work, we fill this gap, proposing a wikification prediction model that combines the strengths of traditional predictors based on statistical features with a latent component which models the concept graph topology by means of matrix factorization. By comparing our model with a state-of-the-art wikification method, using a sample of Wikipedia articles, we obtained a gain up to 13% in F1 metric. We also provide a comprehensive analysis of the model performance showing the importance of the latent predictor component and the attributes derived from the associations between the concepts. The study still includes the analysis of the impact of ambiguous concepts, which allows us to conclude the model is resilient to ambiguity, even though does not include any explicitly disambiguation phase. We finally study the impact of selecting training samples from specific content quality classes, an information that is available in some respositories, such as Wikipedia. We empirically shown that the quality of the training samples impact on precision and overlinking, when comparing training performed using random quality samples versus high quality samples. / Atualmente, informações de referência são disponibilizadas através de repositórios de documentos semanticamente ligados, criados de forma colaborativa e com acesso livre na Web. Entre os muitos problemas enfrentados pelos provedores de conteúdo desses repositórios, destaca-se a Wikification, isto é, a inclusão de links nos artigos desses repositórios. Esses links possibilitam a navegação pelos artigos e permitem ao usuário um aprofundamento semântico do conteúdo. A Wikification é uma tarefa complexa, uma vez que o crescimento contínuo de tais repositórios resulta em um esforço cada vez maior dos editores. Como consequência, eles têm seu foco desviado da criação de conteúdo, que deveria ser o seu principal objetivo. Isso tem motivado o desenvolvimento de ferramentas de Wikification automática que, tradicionalmente, abordam dois problemas distintos: (a) como identificar que palavras (ou frases) em um artigo deveriam ser selecionados como texto de âncora e (b) como determinar para que artigos o link, associado ao texto de âncora, deveria apontar. A maioria dos métodos na literatura que abordam esses problemas usam aprendizado de máquina. Eles tentam capturar, através de atributos estatísticos, características dos conceitos e seus links. Embora essas estratégias tratam o repositório como um grafo de conceitos, normalmente elas pouco exploram a estrutura topológica do grafo, uma vez que se limitam a descrevê-lo por meio de atributos estatísticos dos links, projetados por especialistas humanos. Embora tais métodos sejam eficazes, novos modelos poderiam tirar mais proveito da topologia se a descrevessem por meio de abordagens orientados a dados, tais como a fatoração matricial. De fato, essa abordagem tem sido aplicada com sucesso em outros domínios como recomendação de filmes. Neste trabalho, propomos um modelo de previsão para Wikification que combina a força dos previsores tradicionais baseados em atributos estatísticos, projetados por seres humanos, com um componente de previsão latente, que modela a topologia do grafo de conceitos usando fatoração matricial. Ao comparar nosso modelo com o estado-da-arte em Wikification, usando uma amostra de artigos Wikipédia, observamos um ganho de até 13% em F1. Além disso, fornecemos uma análise detalhada do desempenho do modelo enfatizando a importância do componente de previsão latente e dos atributos derivados dos links entre os conceitos. Também analisamos o impacto de conceitos ambíguos, o que permite concluir que nosso modelo se porta bem mesmo diante de ambiguidade, apesar de não tratar explicitamente este problema. Ainda realizamos um estudo sobre o impacto da seleção das amostras de treino conforme a qualidade dos seus conteúdos, uma informação disponível em alguns repositórios, tais como a Wikipédia. Nós observamos que o treino com documentos de alta qualidade melhora a precisão do método, minimizando o uso de links desnecessários.

Predição de Links é uma área de pesquisa importante no contexto de Análise de Redes Sociais tendo em vista que predizer sua evolução é um mecanismo útil para melhorar e propiciar a comunicação entre usuários. Nas redes de coautoria isso pode ser utilizado para recomendação de usuários com interesses de pesquisa comuns. Este trabalho propõe um processo sistemático baseado em métricas não-dicotômicas para avaliação de predição de links em redes de coautoria, sendo considerada a definição de métodos para as seguintes tarefas identificadas: seleção de dados, determinação de novos links e avaliação dos resultados. Para seleção de dados definiu-se um sensor fuzzy baseado em atributos dos nós. O uso de composições fuzzy foi considerado para determinação de novos links _ponderados_ entre dois autores, adotando-se não apenas atributos dos nós, mas também a combinação de atributos de outros links observados. O link ponderado é denominado _qualidade da relação_ e é obtido pelo uso de propriedades estruturais da rede. Para avaliação dos resultados foi proposta a curva ROC fuzzy, que permite explorar os pesos dos links não apenas para ordenação dos exemplos. / Link prediction is an important research line in the Social Network Analysis context, as predicting the evolution of such nets is a useful mechanism to improve and encourage communication among users. In co-authorship networks, it can be used for recommending users with common research interests. This work proposes a systematic process based on non-dichotomic metrics for evaluation of link prediction in co-authorship networks considering the definition of methods for the following tasks: data selection, new link determination and result evaluation. Fuzzy sensor based on node attributes is adopted for data selection. Fuzzy compositions are used to predict new link weights between two authors, adopting not only attributes nodes, but also the combination of attributes of other observed links. The link weight called _relation quality_ is obtained by using structural features of the social network. The fuzzy roc curve is used for results evaluation, allowing us to consider the weights of the links and not only the ordering of examples.