Adaptive Web Sites: Conceptual Cluster Mining

1 Introduction

Designing a complex web site so that it readily yields its information is tricky. First, different visitors have dis­ tinct goals. Second, the same visitor may seek different information at different times. Third, many sites out­ grow their original design, accumulating links and pages in unlikely places. Fourth, a site may be designed for a particular kind of use, but may be used in many differ­ ent ways in practice; the designer's a priori expectations may be violated. Too often web site designs are fossils cast in HTML, while web navigation is dynamic, time­ dependent , and idiosyncratic.

In [Perkowitz and Etzioni, 1997], we challenged the AI community to address this problem by creating adap­ tive web sites: sites that automatically improve their organization and presentation by learning from visitor access patterns. Many AI advances, both practical and theoretical , have come about in response to such chal­ lenges . The quest to build a chess-playing computer, for example, has led to many advances in search techniques (e.g., [Anantharaman et al., 1990]) . Similarly, the au­ tonomous land vehicle project at CMU [Thorpe, 1990] resulted not only in a highway-cruising vehicle but also in breakthroughs in vision, robotics, and neural networks. We believe that the adaptive web sites challenge will also drive AI advances.

Much of the previous work on adaptive web sites has focused on fairly simple adaptations (e.g., automatically creating shortcuts in the site) and on customization - "personalizing" a web site to suit the needs of each in­ dividual user. In contrast, our own work has been mo­ tivated by two goals: first , we seek to demonstrate that relatively sophisticated adaptations can be generated; second, we seek to aggregate information gleaned from a population of users to transform the site - altering it to make navigation easier for a large number of users. These goals have led us to investigate the problem of index page synthesis: the automatic creation of naviga­ tional pages that consist of a comprehensive set of links to pages at the site on a particular topic (e.g., an index page on "electric guitars" at a musical instruments web site).

In [Perkowitz and Etzioni , 1998], we formally defined the index page synthesis problem and presented an algo­ rithm called PageGather for discovering candidate link sets which would form the basis for new index pages, based on visitor access logs. In that paper, we compared PageGather to classical clustering alforithms [Voorhees, 1986; Rasmussen, 1992; Willet, 1988 and to Apriori, the classical data mining algorithm for the discovery of fre­ quent sets [Agrawal and Srikant, 1994] using the "co­ hesiveness" of the link sets generated as the basis for comparison (see Section 4 for a precise definition of our measure). We found that PageGather produced sub­ stantially better candidates in our domain. Surprisingly, we also found that PageGather's candidates were bet­ ter than human-authored index ·pages available at our experimental test site.

More detailed examination of the data reveals the rea­ son for PageGather's "super-human" performance: hu­ man index page authors operate under a constraint that

Given:

1. A data collection D (e.g., a set of pages at a web site).
2. A pairwise similarity measure m defined over D (e.g., page co-occurrence frequencies derived from access logs) .
3. A conceptual language L for describing elements of D (e.g., conjunctions of descriptive features) .
4. A description in L of each object in D.

Output all subsets c of D such that

1. c is highly cohesive with respect tom (e.g., the average pairwise similarity of objects inc exceeds some threshold) .
2. c corresponds to a concept describable in L.

Figure 1: The Conceptual Cluster Mining Problem. Given a data collection, a similarity measure, and conceptual descriptions of data objects, find sets of objects that are both similar and conceptually related.

PageGather ignored - for successful navigation, index pages typically correspond to a topic or concept that is intuitive to visitors; they cannot be composed of a co­ hesive, but arbitrary, set of links. For example, if the topic of the index page is "electric guitars", the page should contain no links to information about pianos or drums, and there should be no local pages about electric guitars that are not linked to from the index page.

PageGather relies on a statistical approach to discov­ ering candidate link sets; its candidates do not corre­ spond precisely to intuitive concepts, whereas human­ authored index pages do. In this paper, we present a key extension to PageGather that guarantees that Page­ Gather will generate only link sets that correspond to topics, given a language for describing topics. Our ex­ tension also constitutes a novel approach to the long­ standing problem of conceptual clustering [Michalski and Stepp, 1983].

This paper is organized as follows. We first define the conceptual cluster mining problem and discuss previous work. Next, we present the SCML algorithm schema and discuss several instantiations. We experimentally evaluate instantiations of SCML and compare them to the COBWEB conceptual clustering algorithm and to human-authored clusters. We then discuss ways to auto­ matically generate the object descriptions that concep­ tual clustering algorithms take as input. We conclude with a discussion of contributions and future work.

2 Conceptual Cluster Mining

In this section, we define the conceptual cluster mining problem, describe previous work, and present our own approach.

2.1 Problem Definition

In [Perkowitz and Etzioni, 1998], we presented a novel approach to clustering called cluster mining: instead of attempting to partition the entire data space into dis­ joint clusters, we search for a small number of cohe­ sive (and possibly overlapping) clusters. In that paper we showed that, in our domain, cluster mining outper­ formed traditional clustering algorithms.

In this paper we introduce conceptual cluster mining: given a collection of objects, a pairwise similarity mea­ sure over those objects, and a conceptual language for describing them, we search for a small set of cohesive clusters that correspond to concepts expressible in the language. We formalize this problem in Figure 1.

2.2 Previous Work

Relevant previous work is of two types: statistical ap­ proaches to clustering and data mining and conceptual clustering. Statistical clustering (see rvoorhees, 1986; Rasmussen, 1992; Willet, 1988]) is a technique for parti­ tioning a set of objects in a multidimensional data space into "clusters" of objects that are close in that space. Cluster mining is a statistical technique for finding only cohesive clusters in a data space, instead of partition­ ing the entire space. PageGather (see [Perkowitz and Etzioni, 1998]) is a cluster mining algorithm which has been applied to the problem of synthesizing web pages. Frequent set algorithms are designed to find sets of sim­ ilar items in large collections (see [Agrawal and Srikant, 1994; Savasere et al., 1995; Toivonen, 1996]). In a tra­ ditional frequent set problem, the data is a collection of market basket information. Each basket contains a set of items, and the goal is to find sets of items that appear together in many baskets. The standard frequent set al­ gorithm is Apriori [Agrawal and Srikant, 1994] . All of these statistical approaches are useful for finding cohe­ sive sets of objects in large collections of data, but make no attempt to ensure that their results correspond to a intuitive concept.

Conceptual clustering algorithms (see [Michalski and Stepp, 1983]), like their statistical counterparts, parti­ tion a data collection into clusters of similar objects. In a conceptual clustering problem, however, objects are de­ scribed in a conceptual description language, and each cluster corresponds to a concept expressible in that lan­ guage. These conceptual languages may be simple con­ junctions of attributes as in [Michalski and Stepp, 1983], probabilistic descriptions as in [Fisher, 1987], or complex and cognitively inspired as in [Hanson and Bauer, 1989]. All of these are clustering rather than cluster mining al­ gorithms; they attempt to find the best partition of the entire space rather than the best concepts. For our prob­ lem, we require an algorithm that can discover a small set of clusters that are both cohesive and "conceptual".

2.3 The SCML Algorithm Schema

The naive algorithm for the conceptual cluster mining problem might look like this:

The SCML Algorithm Schema [D, r]

1. Run statistical clustering algorithm n on the data collection D , producing a set C of clusters.
2. For each cluster c in C
3. (a) Tag the objects inc as positive examples.
4. (b) Tag remaining objects (D - c) as negative ex­ amples.
5. (c) Use these as input to concept learning algo­ rithm r.
6. (d) Find the concept v = r(c, D- c, L) .
7. (e) Find the set of objects Cv which is the extension of v.
8. Return all the sets Cv found .

Figure 2: The SCML algorithm schema, which is instanti­ ated with a statistical cluster mining algorithm and a concept learning algorithm.

1. Enumerate all concepts l expressible in L
2. For each l, compute l's cohesiveness with respect to the similarity measure m.
3. Return alll with a cohesiveness score over a certain threshold.

Of course, the number of expressions in L could be quite large. For example, when L contains conjunctions of at­ tributes, the number of expressions in Lis exponential in the number of attributes, making this algorithm imprac­ tical for real applications. How can we devise a tractable algorithm for this problem?

Our previous work has presented cluster mining, a tractable technique for finding cohesive statistical clus­ ters; if we could efficiently transform these clusters into conceptual ones, we would have a tractable algorithm. In essence, we would like to find the conceptual cluster that best approximates each statistical one. Our key in­ sight was that the members of a statistical cluster can be viewed as positive examples of the desired concept, and objects outside the cluster as negative examples, en­ abling us to apply concept learning techniques to effi­ ciently generate the desired approximations.

We therefore propose the SCML algorithm schema (Figure 2), which uses statistical cluster mining to find cohesive clusters and concept learning to find a concept that describes each statistical cluster. As the match be­ tween statistical and conceptual clusters will be imper­ fect , we will require a noise-tolerant learning algorithm. The output of this schema is a set of clusters (and their conceptual descriptions) . This approach is not guaran­ teed to find the optimal set of conceptual clusters, but it is tractable and it enables us to leverage continuing advances in concept learning research.

3 SCML and Index Page Synthesis

We have presented the general conceptual cluster min­ ing problem. In this section we frame the index page synthesis problem as conceptual cluster mining. Page synthesis is the automatic creation of web pages. An in­ dex page is a page consisting of links to a set of pages that cover a particular topic (e.g., electric guitars). Given this terminology we define the index page synthesis problem: given a web site and a visitor access log, create new index pages that contain coherent collections of links: ones that exhaustively cover specific topics at the site. We are not provided with a pre-selected set of topics. Possible top­ ics are instead described in a conceptual language, and the exponential number of expressible topics makes enu­ merating them impractical. Instead, we must search the space of possible concepts. An access log contains one entry for each page requested of the web server. Each re­ quest lists at least the origin (IP address) of the request, the URL requested, and the time of the request.

Previously, our approach to this problem has been to use statistical cluster mining, embodied in PageGather, our statistical page synthesis algorithm. Briefly, Page­ Gather creates a graph in which each node represents a page at the web site. The algorithm then processes the access logs to find pages that are often visited together by the site's users; such pages are connected by an edge in the graph. Finally, the algorithm finds maximal cliques in the graph and outputs those sets of pages.l

We instantiate the SCML schema using PageGather for D. We use three different algorithms for r . As a baseline, we wished to use a simple algorithm that would perform a greedy search from general to specific, con­ structing a conjunctive rule, as this approach seems well­ tailored to our problem. Accordingly, we based our algo­ rithm on GREEDY-3 [Pagallo and Haussler, 1990] . The algorithm iteratively builds a conjunctive rule, choosing a conjunct that maximizes the scoring function at each iteration.

We use two scoring functions, producing two instan­ tiations of SCML. As positive examples in our domain are typically outnumbered by negatives, the first scor­ ing function - called PG POS - is a simple count of positives (with negatives used to break ties); we use a maximum rule length to limit the complexity of rules. The second - PGMDL- is based on minimum descrip­ tion length (MDL) [Quinlan and Rivest, 1989] . As the MDL measure includes a tradeoff between the complex­ ity of a rule (its length in conjuncts) and its effectiveness, we do not need an explicit maximum length; the simple measure provides no such tradeoff.

The third algorithm is PG RIp, which uses RIP PERk [Cohen, 1995] for the concept learning algorithm r . RIPPERk is a rule-learning algorithm designed to work well with large, noisy datasets and is competitive with the classic concept learning systems C4.5 and C4.5rules in both speed and performance. In section 4, we present results from PGpos, PGMDL, and PGRIP·

4 Experiments

In this section, we evaluate the SCML algorithm schema, comparing it to PageGather, COBWEB (a popular con­ ceptual clustering algorithm), and clusters derived from human-authored pages at a web site. Furthermore, we compare several instances of the SCML algorithm schema.

1 The cluster size is bounded to ensure a polynomial-time algorithm.

Our experiments draw on data collected from the Mu­ sic Machines web site, 2 a site devoted to information about many kinds of electronic musical instruments . The site contains approximately 2500 distinct documents, in­ cluding HTML pages, plain text , images, and audio sam­ ples. Music Machines receives approximately 10,000 hits per day from roughly 1200 distinct visitors. In our ex­ periments, the training data is a collection of access logs for six months; the test data is a set of logs from a sub­ sequent one-month period. 3 Our conceptual language L consists of conjunctions of attributes describing pages and musical instruments (e.g., type of instrument, price, and type of file ; see Figure 5 for examples).

We compare the algorithms in terms of the quality of the candidate index pages they produce. Measuring clus­ ter quality is a notoriously difficult problem. To measure the quality of a cluster as an index page candidate, we need some measure of whether the cluster captures a set of pages that are viewed by users in the same visit. If so, then grouping them together on an index page would save the user the trouble of traversing the site to find them. As an approximate measure we ask: if a user vis­ its any one page in the cluster, what percentage of pages in the cluster is she likely to visit overall? More formally, let V be the set of user visits to the site and Vc be the set of v E V that include at least one page from cluster c. For a particular visit v E Vc, the set .of pages visited in c is v n c. The average number of hits to a cluster, over all visits, is LvEVc ~~~~~- Finally, the average percentage

'\' ]_v_r1_cJ_ · l · d' 'd d b th · f L.... vev Tv.T I 1s t us average tvt e y e stze o c: 121 . n each experiment , each algorithm outputs a ranked list of clusters. In all graphs, these clusters are sorted by average visit percentage for the sake of clarity.

First, we compare instantiations of SCML. In section 3, we described three different learning algorithms to plug into the SCML schema: (1) RIPPERk (PGRJp); (2) a greedy algorithm with a scoring function based on positive examples (PGpos); and (3) the greedy algo­ rithm with an MDL-based scoring function (PGMDL)­ Figure 3 compares these three variations. We see that PG RIp performs substantially better than either of the other algorithms. All of PG RIp's clusters are better than all but one of those found by the other algorithms.

2 http://machines.hyperreal.org

3 Data sets are available from the authors.

In Figure 3, we also compare the PageGather algo­ rithm with SCML. We see in this graph that the clusters found by PageGather are substantially more cohesive than those found by SCML. The best PageGather clus­ ters have an average visit percentage of over 70%, while SCML tops out below 40%. PageGather, in essence, finds the most cohesive clusters in the data, regardless of their conceptual coherence; SCML must respect the conceptual constraint and so cannot necessarily return the most cohesive clusters . Although PageGather pro­ duces more cohesive clusters, we feel that conceptual co­ herence is essential; coherence makes the pages easier to name automatically, easier to evaluate by the human webmaster, and easier to navigate by site visitors.

In Figure 4 we compare SCML with both COBWEB and human-authored clusters. COBWEB is a popu­ lar conceptual clustering algorithm, first presented in [Fisher, 1987]. COBWEB builds a hierarchical partition of the object space, using probabilistic representations of clusters. Typically, the top level of the hierarchy is the basic level, or most appropriate level at which to parti­ tion the space. However, since our domain dictates that the clusters be in a certain size range (it is impractical to create a web page containing hundreds of links), we choose the level of the hierarchy at which the average cluster size is in the right range - typically 20-30. The best clusters found by SCML are substantially better ­ with average visit percentages at around 35- 40% - than any of those found by COBWEB. Otherwise, both algo­ rithms find clusters with visit percentages around 10%.

It is natural to ask how good our clusters really are, and how high of an average visit percentage is high enough. To attempt to answer this question we look to the "ideal" case: index pages created by a human webmaster. Music Machines contains many index pages of different kinds. Expecting all of the site's index pages to score substantially better than PageGather's output, we chose index pages pertaining to four representative topics: (1) instruments produced by a particular man­ ufacturer (Roland); (2) documents pertaining to a par­ ticular instrument (the Roland Juno keyboard); (3) all instruments of a particular type (drum machines); and (4) all files of a particular type (audio samples). The set of outgoing links on each page (excluding standard navi­ gation links) was treated as a "cluster" and evaluated on our test data. Figure 4 shows the comparison of these clusters to the output of PGRIP· Although PGRrp's clusters show higher average visit percentages than the human-authored pages, the human-authored pages tend to be substantially larger, often leading to lower percent­ age scores. If we instead compare the average number of hits to each cluster, the human-authored pages perform at least as well as PG RIp's.

Visit percentage measures only the statistical cohe­ siveness of our clusters with respect to the data. Of course, as demanded by our problem definition, we also require that these clusters correspond to intuitive con­ cepts. Excepting the original PageGather algorithm, all the algorithms we have discussed produce conjunctive concepts in L. Keeping in mind that we wish to find concepts that we can express to users of the web site, these concepts should be fairly simple - i.e. without too many conjuncts. Figure 5 shows the top five con­ cepts found by both PGRrP and COBWEB. Although both algorithms produce clusters of a reasonable size, COBWEB's concepts tend to be more complex.

5 Automatically Derived Conceptual Descriptions

We have presented two general algorithms for finding clusters of related pages at a web site: PageGather and SCML. PageGather requires no input beyond the web site and access log, but cannot produce conceptually co­ herent clusters. SCML, on the other hand, produces conceptual clusters but carries the strong requirement that all documents at the site be fully described in a conceptual language. We now explore the question of whether it is possible to gain some of the advantages of conceptual clustering without paying the price of gener­ ating full meta-information.

Our approach is to derive meta-information from the structure of the web site or the content of the pages themselves, which may be done completely automati­ cally or with some assistance from the webmaster. We describe two such approaches and present preliminary experimental results. Both approaches are based upon defining a different conceptual language in which to de­ scribe web pages.

The first approach is based on file types. Rather than describing every document at the site with a set of at­ tributes (as was done for SCML), we tag each page with its filetype. Filetypes are derived solely from the file suffix; common suffixes include JPG, GIF, ZIP, HTML, TXT, and so on. Each statistical cluster found by Page­ Gather is partitioned by filetype; small partitions are dis­ carded. The remaining partitions are our final clusters. Note that we only guarantee that all pages in a cluster are of the same type; we do not add all other pages of that type to the cluster as SCML would. Therefore, this approach can find concepts that SCML could not. We have implemented this algorithm - PGTY p E - and tested it on our data.

The second approach is based on content-based clus­ tering. PageGather clusters pages based on visitor ac­ cess patterns; perhaps by clustering them based on their content, we will discover clusters that are more concep­ tually coherent. We apply a clustering algorithm to the pages at the site to obtain a set of content-based clusters. Next, for each cluster output by PageGather, we find the closest content-based cluster- the one with the highest overlap. These closest clusters are our final output. Note that these concepts are defined with respect to keywords rather than more intuitive concepts. Keywords may in­ dicate conceptual similarity, but are not perfect due to synonyms and homonyms. We have implemented this algorithm using suffix-tree clustering (STC) [Zamir and Etzioni, 1998] and tested PG STC on our data.

In Figure 6, we compare PGRrP with PGTYPE and PG sTc. Clusters found by PGTY p E have the high­ est average visit percentages; this is not surprising, as PGTYPE's output is closest to PageGather clusters.

6 Conclusion and Future Work

This paper has responded to the broad Adaptive Web Sites challenge task by presenting and evaluating a method for index page synthesis. More precisely, the method solves the problem of discovering coherent and cohesive link sets, which can be presented to a human webmaster as candidate index pages. While our method is based on previous work, this paper introduces and evaluates a key extension which ensures that the can­ didate index pages generated correspond to an intuitive concept, which makes the pages easier to name auto­ matically, easier to evaluate by the human webmaster, and easier to navigate by site visitors. We have also explored two ways of relaxing the requirement of full meta-information by deriving information from the site's structure and content.

The challenge has also led us to formulate the domain­ independent problem of Conceptual Cluster Mining (Fig­ ure 1) , and an algorithm schema for its solution. We have instantiated SCML with various concept learn­ ing algorithms and conceptual languages, and compared these instantiations experimentally. We have shown that PG RIP outperforms COBWEB (a leading conceptual clustering algorithm) in our domain.

In future work, we plan to investigate alternative mea­ sures of index page quality and also to carry out user studies (with both Web site visitors and webmasters) to assess the impact of the suggested adaptations on users in practice. In addition, we plan to test our approach on additional web sites, including our department's web site in the near future . Finally, index page synthesis itseif is a step towards the long-term goal of change in view: adaptive sites that automatically suggest re- orga­ nizations of their contents based on visitor access pat­ terns.