Dipartimento di Informatica, Università di Pisa, Italy

Key Words: information retrieval, Web search, text categorization, hypertext navigation

Categories: H.3.1, H.3.3, H.3.5, H.5.1, I.2.7, I.5.3

1. Introduction

Assistance in retrieving documents on the Web is provided by two kinds of tools: search engines and classified directories.

Search engines provide keyword-based search on the content of quite large collections of Web documents. The results of a query are displayed as a linear list of documents, typically ranked in order of relevance. Unfortunately the list is often quite long and users have neither the willingness nor the skills necessary to perform complex boolean queries to narrow the search: a recent survey shows that the average query contains less than 3 keywords and that boolean queries are rarely used [Jansen 98]. Since the Web contains material of quite different varieties, users cannot anticipate what is available, find difficult to express their interests and get surprising results because of word ambiguities.

Classified directories organize a usually smaller subset of Web material in catalogues, consisting in a hierarchy of thematic categories: each category lists Web pages (or sites) deemed relevant for that category. Altavista™ [Altavista], Hotbot™ [Hotbot], Infoseek™ [Infoseek] are among the foremost general search engines, while Inktomi™ [Intomi] and Excite™ [Excite] specialize in providing search technology for search services in restricted domains. Lycos™ [Lycos] and Yahoo!™ [Yahoo] are among the most well known Web directories. A recent trend is visible toward the integration of the two kinds of services: Altavista™ [Altavista] has added a catalogue-based service, Lycos plans to merge its services through its acquisition of HotBot. Northern Light [Northern Light] provides an interesting combination in their search service, which dynamically organizes the results of a keyword search into groups with similar subject, source or type.

Users have shown to appreciate the value of catalogues. By navigating in a catalogue and docking to the category c of interest, a user may either (a) directly access relevant sites pre-categorized under c, or (b) perform keyword-based searches restricted to the documents within c.

The value of a catalogue can be expressed in terms of the quality of its classification schema (how understandable, accepted, complete, ordered and synthetic it is), authoritativeness (the degree of user confidence on the catalogue), accuracy (how proper is the assignment of a document to a category), consistency (similar documents are classified in the same way), timeliness (how quickly it reflects changes in the document collection), completeness (the presence of all relevant documents in each category), selectivity (the quality of listed material). The last two aspects are conflicting, since sometimes a more selective catalogue, one which chooses to exclude some material of lower quality may be preferable to a more complete listing.

Achieving these qualities in a catalogue is a difficult task. Deciding whether a document d should be categorized under category c requires, to some extent, an understanding of the meaning of both d and c. Because of this, categorization has traditionally been accomplished manually, by trained human classifiers. This is clearly unsatisfactory since:

• the categorization of a significant portion of the Web requires too much skilled manpower (S. Srinivasan, from Yahoo, acknowledges that the Web grows faster than they can);
• manual categorization is too slow to keep a catalogue up to date with the evolution of the Web. New documents are published, old ones are either removed or updated, new categories emerge, old ones fade away or take up new meanings. Keeping abreast of this evolution by manual means only is practically impossible;
• human based categorization does not guarantee in itself the quality of the resulting catalogue, since categorization decisions are often subjective [Cleverdon 84].

Techniques for automatic classification of Web pages are starting to be exploited on large scale: beyond the already mentioned Northern Light, Lycos and Arianna [ACAB] have recently made available online automatically built portions of their catalogue; Inktomi uses automatic classification in building sites like the Disney Internet Guide.

Automatic classification is typically performed by comparing representations of documents with representations of categories and computing a measure of their similarity. In many cases category profiles are built by specialist librarians [Northern Light] combining information from several sources (general classification indexes, specialized thesauri, etc.).

Techniques for automatically deriving representation of categories ("category profile extraction") and performing classification have been developed within the area of text categorization [Ittner 95, Lewis 96, Yang 94, Yang 97], a discipline at the crossroads between information retrieval and machine learning. Text categorization uses machine learning techniques to inductively build, from a training set of documents pre-categorized according to a given classification, a representation of categories which an automatic process (classifier) can compare with the representation of a document in order to decide to which categories it belongs.

Alternatively, a document can be compared to previously classified documents and placed in the category of the closest such documents [Fuhr 91], avoiding the need for category profiles.

The representation of documents is obtained through standard indexing techniques developed within the field of information retrieval [Salton 88]. Vector space retrieval [Salton 75] and fuzzy retrieval [Bookstein 76] are measures of similarity used to perform categorization.

Approaches based on identification of concepts have also been proposed which exploit neural network techniques [Autonomy] or linguistic and semantic analysis [InQuizit].

Several new techniques are being proposed specifically for the context of Web [Kleinberg 97, Brin 98].

All the approaches to categorization mentioned so far perform categorization by content [Yang 94, Schütze 95, Ng 97], since information for categorizing a document is extracted from the document itself.

Categorization by content does not exploit an essential aspect of a hypertext environment like the Web, namely the structure of documents and the link topology.

In this paper we investigate a novel technique for automatic categorization, which we dubbed categorization by context, since it exploits the context surrounding a link in an HTML document to extract useful information for categorizing the document referred by the link. Categorization by context exploits relevance hints that are present in the structure and topology of the HTML documents published on the Web. Combining a large number of such hints, an adequate degree of accuracy of classification can be achieved.

Context-based indexing categorization has the significant advantage that it can deal also with multimedia material, including images, audio and video [Shrihari 95, Guglielmo 96, Harmandas 97], since it does not rely on the ability to analyze the content of documents to classify.

Categorization by context leverages on the categorization activity that users implicitly perform when they place or refer documents on the Web, turning categorization, form an activity delegated to a restricted number of specialists, into a collaborative effort of a community of users. By restricting the analysis to the documents used by a group of people, one can build a categorization that is tuned to the need of that group.

In this paper we report on our experience in building Theseus [Teseo], an automatic classifier of Web documents that exploits the context of links in Web documents [Attardi 98].

1. Improving Web search engines

Several approaches have been attempted for improving the services provided by Web search engines.

Altavista provides a refine capability, whereby users receive suggestions about terms to include or exclude for refining the query. The problem with this approach is that suggested terms are only statistically related to query terms and rarely represent useful semantic concepts. The refined query narrows the focus of search, but does not direct the search toward the topic of interest. Moreover the approach puts additional burden on the user while providing limited benefits.

Infoseek provides grouping of query results and also allows retrieving pages similar to a given one. Related pages take the user to a parallel, possibly overlapping set of classified documents, but not necessarily to more focused ones.

Northern Light has introduced the technique of Custom Search FoldersÔ . Results of traditional keyword searches are dynamically organized into folders containing documents with similar subjects, sources, or types. When a folder is opened, a new subset of the original result list is produced containing more focused results. To implement the service, Northern Light pre-classifies automatically its whole collection of documents according to: (a) subject, using a subject hierarchy of 20000 terms hand crafted by human specialists, (b) type, in a shallow hierarchy of 150 document types, (c) language, (c) source (collection, Home Page, educational site, etc.). By performing the classification in advance, the grouping of query results can be produced quickly and effectively.

Custom Search Folders are dynamically created, as opposed to the static structure of a manually built catalogue like Yahoo!.

As an example of the benefits of this approach, consider a query on "citation processing". A typical search engine will produce several million of results, whose topics include driving violation, information retrieval, data processing, etc. With Infoseek, one can select among the results for instance a journal on information retrieval and ask for related pages; however this produces a list of 6 times more pages, apparently drifting into documents unrelated to the original query. Northern Light produces instead a number of search folders, including: Probation, Government sites, Archive & record management, Document management, Office equipment, Information retrieval. Within the latter folder, one finds folders about: Clustering, Relevancy ranking, and bubl.ac.uk (the site of the journal Information Processing and Management), that indeed help in discriminating among documents.

Automatic categorization techniques may lead to better Web retrieval tools that provide access to large amount of up-to-date documents, like search engines, with the convenience of selecting among properly organized material, like in classified directories.

Lycos is now providing a catalogue built through automatic classification: however the new catalogue consists only of links, with no summary or other useful information regarding the contents of sites. Lycos uses relevance feedback from users and sorts each list of recommended Web sites accordingly.

ACAB [ACAB] uses automatic classification techniques based on matching hand-crafted category profiles with the contents of documents and also builds an automatic summary of page contents which is displayed in the catalogue.

2. Categorization by context

Categorization by context is a technique for automatic categorization based on the following hypotheses:

1. a Web page which refers to a document must contain enough hints about its content to induce someone to read it
1. such hints are sufficient to classify the document.

Indeed a document would never be visited, except in casual browsing or through a direct referral, unless there are perceivable clues of its possible interest to potential readers. When people browse through documents, they base their decisions to follow a link on its textual description or on its position (in case of image maps or buttons). At least for textual links, in principle a document should provide sufficient information to describe a document it refers to. HTML style guides [Tilton 95] suggest making sure that the text in a link is meaningful, avoiding common mistakes like using adverbs or pronouns: "The source code is here" or "Click this". Even if the link itself is not sufficiently descriptive, the surrounding text or other parts of the document normally supply enough descriptive information. If such information is sufficient to decide whether a document is worth reading, we can assume it is also sufficient to categorize a document.

The classification task must then be capable of identifying such hints. One obvious hint is just the anchor text for the link (the text between tags <A> and </A>). But additional hints may be present elsewhere in a page: page title, section titles, list descriptions, etc. Our idea is to exploit the structure of HTML documents to extract such hints. Moreover, a page may have been reached from some other page, whose context as well may be relevant, although to a lesser extent.

Categorization by context exploits both the structure of Web documents and Web link topology to determine the context of a link. Such context is then used to classify the document referred by the link.

One may think that instead of classifying a document, we classify a virtual document, made up of portions of other documents that refer to it. The advantage of this approach is that typically one refers to a document with a more concise description and more pregnant terms than those in the document, as in the case of third party reviews. This simplifies categorization since the presence of terms, which mislead the classifier, is less likely.

Hypertext links pointing to the document to be categorized have not been used so far for categorization, although they have been used as clues for searching documents [Chalmers 98, Li 98], and for measuring the "importance" of a Web site [Brin 98].

Contextual information is exploited in ARC [Chakrabarti 98], a system for automatically compiling a list of authoritative Web resources on a topic, further discussed in Section 10.

1. Architecture

The technique of categorization by context consists in extracting contextual information about documents by analyzing the structure of Web documents that refer to them. The overall architecture of the task of categorization by context is described in [Fig. 1], and consists in spidering Web documents, HTML structure analysis, URL categorization, weight combination and catalogue update.

1. Spidering and HTML Structure Analysis

This task starts from list of URLs, retrieves each document, analyzes the structure of the document expressed in terms of its HTML tags. For an introduction to HTML we refer to the HTML Primer [HTML].

The tags considered are currently: <TITLE>, <Hn>, <UL>, <DL>, <OL>, <A>. Whenever one of these tags is found, a context phrase is recorded, which consists of the title within a pair <Hn> </Hn>, or the first portion of text after a <UL> or <DL> tag, or the phrase within a <A> tag. When a <A> tag is found containing an URL, an URL Context Path (URL: C₁: C₂: … : C_n) is produced, which consists of the sequence of the context strings so far (C₁: C₂: … : C_n) associated to the URL. Therefore C₁ is the text in the anchor of the URL, and the other C_i are the enclosing contexts in nesting order.

In the analysis tags related to layout or emphasis (<EM>, <B>, <CENTER>, <FONT> etc.) are discarded.

Another possible element for a context is the title of a column or row in a table: tag <TH>. Such title can be effectively used as a context for the elements in the corresponding column or row.

We will use throughout the following example, consisting of a fragment of an HTML page from Yahoo™! (http://www.yahoo.com/Science/Biology):

• MIT Biology Hypertextbook - introductory resource including information on chemistry, biochemistry, genetics, cell and molecular biology, and immunology.
• Biodiversity and Biological Collections - information about specimens in biological collections, taxonomic authority files, directories of biologists, reports by various standards bodies, and more.
• Biologist’s Control Panel - many biology databases, library and literature links.
• Biologists Search Palette - a collection of useful search engines for biological databases on the Internet, accessed through either the Web or gopher.

The HTML source for this page is:

the following context paths are created:

Any URL found during the analysis is passed back to the spidering process, if it points to a document within the current site and stored for later analysis if it points to an external site. This allows us to perform a depth-first visit of a site, collecting any categorization information it contains about itself and other sites.

1. Categorization

The categorization task exploits the database of URL Context Path and the Category Tree within which the URL must be categorized. The Category Tree consists of a tree (or a DAG), where each node contains a title, i.e. a single word or phrase, which identifies the category.

The goal of the categorization is to find the most appropriate categories to which an URL should belong. The output of the categorization is a sequence of weights associated to each node in the Category Tree:

Each weight w_i represents a degree of confidence that the URL should belong to the category represented by node N_i.

The weights from the Context Path for a URL are added with all other Context Paths for the same URL and normalized. If the weight for a node is greater than a certain threshold, the URL is categorized under that node.

The mechanism should allow for categorizing an URL under more than one node, but never in two nodes which are descendant of one another.

1. Algorithm

The categorization algorithm represents each node in the Category Tree as a path. For instance, let us consider the Arianna [Arianna] search engine for the Italian Web space that we are using for our experiments, and the following part of the Arianna category tree (translated into English):

 

 

Business

Insurance

Banks

Events and Fairs

News

Companies

Publications

Schools

Computer

Distribution and Sale

Events and Fairs

Publications

Schools

Software and Hardware

Sport

Events

News

This tree corresponds to the following paths:

Business: Insurance

Business: Banks

Business: Events

Business: Fairs

Business: News

Business: Companies

Business: Publications

Business: Schools

Computer: Sale

Computer: Distribution

Computer: Events

Computer: Fairs

Computer: Schools

Computer: Software

Computer: Hardware

Sport: Events

Sport: News

Notice that some categories (e.g Events) appear in several places, therefore the title of the category is not sufficient to identify the category: the whole path is necessary to disambiguate among the categories. Categorization by context exploits this fact in a fundamental way to resolve ambiguities: the presence of terms which match a category fades to irrelevance unless there are other matches with all categories in the path which confirm the specific meaning of the term. For instance, the term "band" may refer to a musical group or to clothing. The term will not contribute to categorization unless the context contains some other word that matches with either Music or Fashion, and all other categories up to the top-level of the catalogue.

Notice also that we split into two paths any title that contains two terms joined by "and": the original category corresponds to the union of the two paths.

The categorization algorithm works as follows: for categorizing an URL it computes first a vector of matching weights for each path in the Category Tree, then it determines the paths with the best matching vectors. Once all URL have been categorized, a catalogue is built by assigning each URL to the best matching categories.

1. Computing path match vectors

Given an URL context path (URL: C₁: C₂: … : C_n), the algorithm considers in turn each C_i, starting from C₁. To each level we associate a weight d_l, decreasing from C₁ = 1, for instance with a value 1/log₂(l + 1). It may be worthwhile to adapt these weights take into account the significance of a tag, for instance a <TITLE> tag may have a slightly higher weight than its position would imply.

Then we extract from C_l the noun phrases it contains n₀, … , n_k, as described in [Section 6.2].

For each path p in the Category Tree, we create a path match vector pv with as many fields as the path length, initialized to 0.

Each phrase n_i is matched against each title in each path. If there is a match between n_i and the title of category in the k-th position in path p, with matching weight mw, then d_l ´  mw is added to pv_k. This process is repeated for each level 1 < l < n.

Notice that since there can be several matching, the value in a field of a path match vector can be greater than one; therefore these values are normalized before performing comparisons.

For example, here are the non zero vectors for the URL http://esg-www.mit.edu:8001/esgbio in our example. On the left we display the path and on the right the corresponding match weight vector, which has an entry for each element of the path representing the weight of the match for the corresponding title.

science ......................................... 1.0

science : general ............................... 1.0 0.0

science : earth ................................. 1.0 0.0

science : environment ........................... 1.0 0.0

science : psychology ............................ 1.0 0.0

science : mathematics ........................... 1.0 0.0

science : engineering ........................... 1.0 0.0

science : physics ............................... 1.0 0.0

science : chemistry ............................. 1.0 0.0

science : space ................................. 1.0 0.0

science : astronomy ............................. 1.0 0.0

science : computer .............................. 1.0 0.0

science : biology ............................... 1.0 2.13093

science : botany ................................ 1.0 0.0

technology : biology ............................ 0.0 2.13093

science : archaeology ........................... 1.0 0.0

science : agriculture ........................... 1.0 0.0

The weights are based on term frequency within the context: biology appears three times, two near the URL and one in the title, which is farther and therefore contributes less to the overall weight.

Path match vectors have a quite different meaning from the index vectors used in text based information retrieval. For instance in the knn method for information retrieval, n keywords are used to represent documents, and a vector v of n elements is associated to a document; v_i is and indication of the occurrence of the i-th keyword in the document, typically based on tf (term frequency) and idf (inverse document frequency). Index vectors are directly compared among themselves or with index vectors for categories. The path match vector for a document may be considered as consisting of elements of the form:

pv_i = c ∙ v

where c is the index vector for the i-th category (category profile) and v is the index vector for the document.

2. Selecting best matching categories

Any path match vector pv that contains non-zero fields is considered as a potential candidate. The selection among these candidates is performed as follows:

1. discard any path with 0’s in its leading fields. This means that that we found matches only in some subcategory but not in the top-level categories. For instance an URL relating to a business event will match Events, but not Sports. The URL in fact will match both categories Business and Event in the Business:Event path.
1. among candidates with similar overall score, select the one with longer path. This forces categorization under the most specific category.

The first criterion is essential since it provides categorization by context with the ability to disambiguate between senses of words: only the sense which is confirmed by the context for all the categories up to the top of the classification hierarchy is retained.

The selected estimate records are stored in the database, associated to the URL. When the same URL is reached form a different path, the new estimates are combined to the previous ones. This will either enforce the indication of the category for a URL or suggest alternative categories for the URL.

The grading of candidates for http://esg-www.mit.edu:8001/esgbio produces the following:

1. Implementation

In order to compute the match between a noun phrase in a context and a title in the catalogue, we exploit several tools and data structures.

First, since it is likely that noun phrases do not use the exact terms present in the titles, we must widen somewhat the search. In order to do this we precompute a neighborhood of words for each term in a title, exploiting information from WordNet [Miller 95], which we store in a neighborhood table. Second, matching a noun phrase with a title, which in general is also a noun phrase, requires matching multiple words.

1. Neighborhood Table

In the following we will denote with D the set of titles of categories in the Categorization Tree, and with DS the set of single words in D.

For each term t in DS we build the set I(t) of terms in the neighborhood of t (synonyms, hyponyms, etc.). Moreover, for each term s in I(t) we denote with w(s, t) the weight of s with respect to t, which expresses how closely s is related term to t. If a term belongs to several of these classes, w(s, t) takes the largest of such weights.

We implement the inverted list of I as a hash table TI whose keys are elements in DS. Since we need to know the matching weight of each pair of words, it is convenient to store in this table not just the matching word but also the matching weight. Therefore the table associates to each word s in the neighborhood of some term t, a set of pairs ‹t, w(s, t)›, where t Î DS.