Using HMM to learn user browsing patterns for focused Web crawling

Hongyu Liu, Jeannette Janssen, Evangelos MiliosData 2006 · DOI

TL;DR

This paper introduces a novel approach to focused web crawling that leverages Hidden Markov Models (HMMs) to learn user browsing patterns. By analyzing how users navigate web pages, the system builds a model that predicts which links are most likely to lead to relevant content, outperforming existing methods in finding topic-specific information efficiently.

What Problem Does This Paper Address?

The World Wide Web is vast and constantly growing, making it challenging for generic search engines to keep up and for users to find highly specific information. Traditional crawlers often download too much irrelevant data, wasting resources. Focused crawlers aim to address this by prioritizing links that lead to topic-specific content. However, accurately predicting these links is difficult because relevant pages can be indirectly linked through irrelevant ones. This paper tackles the problem of effectively predicting relevant web pages by learning from human browsing behavior, which implicitly captures complex semantic relationships and link structures that traditional methods might miss.

Methods

The core of the proposed system is a Hidden Markov Model (HMM) trained on user browsing data. The process involves three main stages:

  1. User Data Collection: Users browse the web on a specific topic, marking relevant pages. This browsing activity is used to construct a Web graph, representing pages as nodes and hyperlinks as edges.
  2. User Modelling via Pattern Learning:
    • Latent Semantic Indexing (LSI): Used to identify semantic content within the browsed pages and reduce the dimensionality of the term-document space.
  3. Clustering: Pages are grouped into semantically coherent clusters using the X-means algorithm.
  4. Concept Graph: A graph is built where nodes represent clusters, capturing associative relationships between page types.
  5. HMM Training: The HMM is trained on this concept graph and the user's marked target pages. The hidden states of the HMM represent the "distance" (number of hops) from a target page, while observations are the cluster assignments of the pages. This allows the model to learn sequences of topic transitions that lead to relevant content.
  6. Focused Crawling: The trained HMM is used to assign a "visit priority" to URLs in the crawl queue. Links leading to pages predicted to be closer to target states are given higher priority.

Datasets

The paper uses data collected from user browsing sessions for various topics, including "Linux," "Call for Papers," "Biking," and "Hockey." These topics were selected from the Open Directory Project (ODP) and were neither too broad nor too narrow. Users were graduate students asked to search for web pages related to these topics. The ODP was also used to help identify effective starting points for browsing.

Key Insights and Ideas

  • Human browsing as a rich signal: User navigation patterns implicitly capture complex semantic relationships and topical hierarchies that are difficult to model with purely link-based or content-based methods.
  • HMMs for sequential topic transitions: HMMs are well-suited to model the sequential nature of web browsing, where the probability of reaching a relevant page depends on the sequence of topics encountered.
  • Bridging content and linkage: The approach effectively combines semantic content analysis (via LSI and clustering) with link structure information (from the Web graph and concept graph) to make informed crawling decisions.
  • Topic-specific hierarchies exist: The paper argues that even without explicit human-curated directories, implicit hierarchical structures exist in the web (e.g., University -> Department -> People -> Faculty), and user browsing tends to follow these.

Key Results

The proposed HMM-based focused crawler consistently outperformed other methods like Best-First Search (BFS) and Context-Graph (CGS) crawling across multiple topics.

  • Linux: The HMM crawler found significantly more relevant pages compared to CGS and BFS.
  • Call for Papers: While BFS performed well in this case, the HMM crawler still showed strong performance.
  • Biking & Hockey: The HMM crawler demonstrated robust performance, often outperforming others in the long run, especially when dealing with specific target pages.
  • LSI Impact: Experiments showed that using LSI significantly boosted performance in most cases, highlighting its importance in reducing noise and revealing semantic relationships.
  • Training Data: Using user-visited pages to build the Web graph for HMM training yielded better results than using a complete Web graph with all nodes, suggesting that user-curated data is more effective.

Limitations and Future Work

  • Training Data Dependency: The system's performance relies on the quality and quantity of user browsing data. Collecting this data can be time-consuming.
  • Threshold Sensitivity: The relevance threshold (γ) can influence performance, and finding the optimal value might require tuning.
  • Future Work:
    • Exploring more sophisticated models like Conditional Random Fields (CRFs) to integrate a richer set of features (anchor text, titles, URL tokens, user queries).
  • Improving the user modeling session by combining backlinks with user-visited pages to better present topical hierarchies without overburdening the user.
  • Extending the system to handle multiple topics simultaneously.
  • Investigating ways to automatically update target pages during crawling.

Summary updated

BibTeX
@inproceedings{liu2006using,
  author = {Hongyu Liu and Jeannette Janssen and Evangelos Milios},
  title = {{Using HMM to learn user browsing patterns for focused Web crawling}},
  booktitle = {Data},
  year = {2006},
  doi = {10.1016/j.datak.2006.01.012},
}
Figure