Detecção de réplicas de sítios web usando aprendizado semi-supervisionado baseado em maximização de expectativas

Abstract

The Web contains a vast repository of information. According to the literature about 29% of this repository contains duplicate content. Duplication of content may occur within a single web site (intra-site) or between different web sites (inter-site). This thesis addresses the problem of detecting inter-site replicas. In this work, this problem is treated as a classification task, where positive and negative replica examples are used to training a binary classifier. The proposed method uses a semi-supervised learning algorithm based on the Expectation- Maximization (EM) approach. The EM algorithm is an iterative method that allows estimation of parameters in probabilistic models with latent or not observed data. In replica detection is easy to find obvious replica and non-replica examples. The EM algorithm is used to find non-obvious examples. The complementarity from replicas and non-replicas examples is exploited through the concept of Pareto Efficiency. The algorithm used for classification of unknown examples during the EM process was the Lazy Associative Classifier (LAC). The LAC algorithm employs the concept of training projection, thus producing relevant subsets of examples for each test instance. The principle of entropy minimization is used to find the optimal parameter for label transitions considering each subset of examples. The experiments show that it is possible to achieve a reduction of 19% in the number of duplicate URLs at a false-positive rate lower than 0.005. The combination of the proposed algorithm that eliminates inter-site replicas with algorithms that eliminate intra-site replicas enables a reduction up to 21% in duplicate URLs.