Adaptive Web Sites: Automatically Synthesizing Web Pages

AAAI 1998

TL;DR

This paper introduces PageGather, a novel algorithm for automatically synthesizing index pages for websites by analyzing user navigation patterns from web server logs. It tackles the challenge of improving website organization and usability through "optimization" (improving structure for all users) rather than "customization" (personalizing for individuals), offering a faster and more effective approach than traditional clustering methods.

What Problem Does This Paper Address?

Designing effective websites is a persistent challenge. Websites often become complex and difficult to navigate as they grow, with information scattered and links becoming outdated or illogical. Visitors have diverse goals and may seek different information at different times, making a one-size-fits-all design suboptimal. Traditional web design is static, while user navigation is dynamic and idiosyncratic. The authors propose "adaptive web sites" that automatically improve their organization and presentation by learning from visitor behavior. They distinguish between "customization" (tailoring to individual users, which can be intrusive) and "optimization" (improving the site's structure for everyone based on collective user behavior). This paper focuses on the latter, specifically addressing the problem of automatically creating new "index pages" – pages that group links to related content, thereby facilitating user navigation.

Methods

The core of the paper introduces "cluster mining," a novel approach to clustering designed for synthesizing index pages. Unlike traditional clustering that partitions data into disjoint sets, cluster mining aims to find a small number of high-quality, potentially overlapping clusters. This is particularly useful for web navigation where a page might logically belong to multiple topical groupings.

The algorithm, named PageGather, operates in four main steps:

  1. Process Access Log into Visits: The raw web server logs (containing hits, URLs, and timestamps) are processed to reconstruct individual user "visits" – ordered sequences of pages accessed by a single user in a session. This relies on the "visit-coherence assumption": pages visited within a single session are likely conceptually related.
  2. Compute Co-occurrence Frequencies and Similarity Matrix: For every pair of pages, the algorithm calculates the probability of a user visiting one page given they've visited the other. The "co-occurrence frequency" is the minimum of these two conditional probabilities. Crucially, if two pages are already linked, their similarity is set to zero to focus on finding new organizational structures. A sparse graph is then created by applying a threshold to these frequencies.
  3. Create Graph and Find Cliques/Connected Components: The similarity matrix is transformed into a graph where pages are nodes and non-zero similarity values are arcs. The algorithm then searches for clusters within this graph, either by finding cliques (subgraphs where every pair of nodes is connected) or connected components (subgraphs where a path exists between any two nodes). Cliques represent more tightly related pages, while connected components are larger and faster to find.
  4. Create Web Page for Each Cluster: For each identified cluster, a new index page is generated. The paper focuses on synthesizing the content (the set of links) for these pages, with titles and placement handled by simpler methods or left to human webmasters for future work.

Datasets

The experiments were conducted using access logs collected from the http://www.hyperreal.org/music/machines/ website. This site contains approximately 2500 distinct documents and receives about 10,000 hits per day from 1200 different visitors. The training data consisted of logs from one month, and the test data from a subsequent ten-day period. No new benchmarks were introduced; rather, existing web server logs were used to evaluate the proposed algorithm against traditional methods.

Key Insights and Ideas

  • Optimization vs. Customization: The paper clearly articulates the distinction between improving a website for all users (optimization) versus tailoring it to individuals (customization), advocating for the former as a less intrusive and more scalable approach.
  • Visit-Coherence Assumption: The idea that pages visited within a single user session are conceptually related is a powerful heuristic for inferring topical groupings from raw access logs.
  • Cluster Mining for Web Structure: Adapting clustering to find a small number of high-quality, potentially overlapping clusters is more suitable for synthesizing index pages than traditional partitioning methods. This allows for more flexible and nuanced organization.
  • Nondestructive Transformations: The principle of only adding links or pages, rather than removing or altering existing ones, is crucial for integrating adaptive features without disrupting the original site design.
  • Focus on Index Page Synthesis: By narrowing the problem to automatically generating the content of index pages, the authors make the challenge tractable while still addressing a significant aspect of website usability.

Key Results

  • Speed: PageGather was significantly faster than traditional clustering algorithms. The clustering portion of PageGather (excluding similarity matrix creation) took about 1 minute 5 seconds (using connected components) or 1 minute 12 seconds (using cliques), compared to 48 minutes for a modified K-Means and over 48 hours for Hierarchical Agglomerative Clustering (HAC).
  • Quality: PageGather variants (both clique and connected component based) outperformed K-Means in terms of "predictive performance," a metric measuring how likely a user is to visit more pages within a cluster if they visit one page from it. PageGather's clusters were found to be more coherent.
  • Overlapping Clusters: The paper suggests that allowing clusters to overlap is beneficial for this task, as removing overlap significantly degraded the performance of the clique-based PageGather.

Limitations and Future Work

  • Limited Scope of Synthesis: The current work focuses solely on synthesizing the content (links) of index pages. Future work needs to address other subproblems like determining the page title, ordering links, labeling hyperlinks, ensuring graphical consistency, and deciding where to integrate the new page into the site.
  • Handling Large Clusters: While cluster mining is designed to find small, coherent clusters, the paper acknowledges that visitors expect complete listings. Future work proposes using cluster mining to generate initial clusters and then learning a general rule to define membership for more comprehensive index pages.
  • Site Structure Awareness: The current approach doesn't explicitly leverage existing site structure or ontologies. Incorporating meta-information about page types could lead to more homogeneous and meaningful clusters.
  • User Testing: The authors acknowledge the need for user testing to qualitatively assess the coherence and usefulness of the generated index pages.
  • Scalability of Similarity Matrix: The creation of the similarity matrix is noted as the most expensive part of the algorithm, even for versions that don't use cluster mining.
  • Data Granularity: While the paper notes that coincidences in logs from shared IP addresses are unlikely to significantly affect results, it acknowledges that more accurate logs (e.g., from WebThreads) could be used if necessary.

Summary updated

BibTeX
@inproceedings{1998adaptive,
  title = {{Adaptive Web Sites: Automatically Synthesizing Web Pages}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1998},
}
Figure