Optimized record extraction from web pages using signal processing and machine learning

Abstract

A extração de dados estruturados (i.e. registros) de páginas da web permite uma série de aplicações importantes e possui imenso valor devido à quantidade e diversidade de informações disponíveis que podem ser extraídas. Esse problema, embora amplamente estudado, permanece em aberto pois não é trivial. Devido ao volume dos dados, uma abordagem viável precisa ser automática e eficiente (e, é claro, eficaz). É apresentada aqui uma nova abordagem, automática e computacionalmente eficiente, usando técnicas de processamento de sinais para detectar regularidades e padrões na estrutura de páginas da web e também aprendizado de máquina supervisionado para classificar os dados extraídos como conteúdo ou ruído. Também é apresentado um estudo comparativo das várias técnicas de aprendizado de máquina supervisionado, incluindo ensembles homogêneos e heterogêneos, para resolver o problema de classificação de conteúdo e ruído em páginas da web. Utilizamos o aprendizado de máquina, especificamente, para resolver o problema de detectar conteúdo em dados semiestruturados (por exemplo, resultados de pesquisa de comércio eletrônico) em duas situações distintas: primeiro em um ambiente controlado contendo apenas documentos com conteúdo estruturado e depois; em um ambiente aberto em que a página da web que está sendo processada pode ou não ter conteúdo estruturado. As características usadas para classificar o conteúdo são obtidas automaticamente a partir da abordagem de extração. Além de comparar o desempenho entre diferentes modelos, também foi realizada uma ampla análise das combinações de caracteristicas para apurar sua relevância para o problema. A abordagem proposta segmenta a página da web, detecta as regiões de dados dentro do documento, identifica os limites (início e fim) dos registros, alinha os registros encontrados e os classifica como conteúdo ou ruído. Também é apresentada uma otimização da abordagem de extração ingênua. A otimização proposta melhora o limite superior de O(nlogn) para O(n), mantendo os mesmos resultados qualitativos (ou seja, sem perda de eficácia) e alcançando uma melhoria de 11,77% no tempo de execução. Os resultados demonstram que a abordagem proposta tem comportamento linear de complexidade de tempo e f-score de cerca de 93% em um ambiente controlado e 91% em um ambiente aberto. A abordagem proposta é mais eficiente e tão eficaz quanto o estado da arte além de abordar a questão da detecção de conteúdo, normalmente negligenciada na maioria dos trabalhos.

Abstract: Extracting structured data (i.e. records) from web pages enables a number of important applications and has immense value due to the amount and diversity of available information that can be extracted. This problem, although vastly studied, remains open because it is not a trivial one. Due to the scale of data, a feasible approach must be both automatic and efficient (and of course effective). We present here a novel approach, mostly automatic and computationally efficient, using signal processing techniques to detect regularities and patterns in the structure of web pages and supervised machine learning to classify extracted data as content or noise. We also present a comparative study using several supervised machine learning techniques, including homogeneous and heterogeneous ensembles, to solve the problem of classifying content and noise in web pages. We use machine learning, specifically, to tackle the problem of detecting content in semi-structured data (e.g., e-commerce search results) under two different settings: a controlled environment with only structured content documents and; an open environment where the web page being processed may or may not have structured content. The features are automatically obtained from the underlying extraction approach. Besides comparing the performance between different models we have also conducted extensive feature selection/combination experiments. Our approach segments the web page, detects the data regions within it, identifies the records boundaries, aligns the records and classifies them as content or noise. We also present an optimization over the naïve extraction approach. The proposed optimization improves the upper bound from O(nlogn) to O(n) while maintaining the same qualitative results as before (i.e., no loss in efficacy) and achieving 11.77% improvement in runtime efficiency. Results show linear time complexity behaviour and an f-score of about 93% in a controlled setting and 91% in an open setting. Our proposal is more efficient and just as effective as the state-of-the-art approaches and, in addition, we deal with content detection, which is neglect by most works.