URL as starting point for WWW document categorisation 
Vojtech Svatek & Petr Berka
Department of Information & Knowledge Engineering
and
Laboratory of Intelligent Systems
Faculty of Informatics and Statistics,
 University of Economics, Prague
W.Churchill Sq.4, 13067 Praha 3
Czech Republic
{svatek, berka}@vse.cz

Abstract
Information about the category (type) of a WWW page can be helpful for the user within search, filtering, as well as navigation tasks. We propose a multidimensional categorisation scheme, with bibliographic dimension as the primary one. We examine the possibilities and limits of performing such categorisation based on information extracted from URL, which is particularly useful for certain on-line applications such as meta-search or navigation support. In addition, we describe the problem of ambiguity of URL terms, and suggest a method for its partial overcoming by means of machine learning. As a side–effect, we show that general purpose WWW search engines can be used for providing input data for both human and computational analysis of the web.
1 Introduction
The task of document categorisation is common within web applications, in particular for navigational, search and filtering systems, which give access to large amounts of documents. The aim of the categorisation may be
•	to eliminate documents which could be annoying for the user (such as pornographic documents or advertisements), or
•	to partition the whole mass into coherent subsets which can be selected and analysed by the user more conveniently.
In the latter case (multiway categorisation), the subsets correspond to predefined categories. Note that the task is similar to that of clustering, which is also quite frequent. Clustering, however, creates subsets which have no explicit semantics, and thus are less comprehensible for an end user.
A frequent criterion for document categorisation is relevance to predefined subject topics (such as „Computers“, „Finance“ or „Medicine“). The topics are typically arranged into hierarchies, such as the well-known Yahoo! or Open Directory. Subject topics are extremely useful for navigational access; their utility for search and filtering is, however, spurious, as they are strongly correlated with the actual user's query/profile. We assume that for structuring the output of search or filtering, more „query-orthogonal“ typologies are desirable. Information on bibliographic type is probably the most obvious criterion to be considered in this context.
In section 2 we describe the three dimensions of categorisation used in our experiments. In section 3 we outline the situations when the URL plays an important role in WWW categorisation, and illustrate them on real examples. In section 4, we describe our method of building a heuristic rulebase usable for category recognition (within the three–dimensional model) and present some empirical results. In section 5 we examine the problem of ambiguity of some frequent URL terms, and suggest a machine–learning approach to its partial overcoming. Finally, we discuss related work (in section 6), and present perspectives for the future (section 7).
2 Multidimensional categorisation
We have examined different models of categorisation, with the aim of providing the user with  useful information on the „nature“ of the page. In this respect, we propose three „typological dimensions“, which can be applied on most WWW documents more-or-less independent of each other as well as of the subject topic:
•	Bibliographic categorisation, operating on concepts like „article“, „bibliography“, „image“, „pricelist“ or „newsgroup message“. To avoid unlimited proliferation of classes, we try to follow the existing Dublin Core system (Weibel et al., 1998), which plays the role of standard for digital-library metadata, namely the suggested values of its descriptive element ResourceType. Conformably to Dublin Core, we also include classes such as „personal info“, „organisational info“ or „project info“; we however feel that, for the sake of cleaner conceptualisation, these should be separated in the future, thus forming a fourth dimension denotable as „categorisation according to the entity related to the document“.
•	Categorisation according to the „sphere of origin“, such as „commercial“,   „academic“, „governmental“, „non-profit“ or „private“. The number of categories is rather limited here: we mostly distinguish only the above ones. If needed, we could e.g. refine the concept of governmental page to discern between national/federal and local governments, or to refine the notion of „non–profit“ between „political“ and „non–political“.
•	Categorisation according to „technological type“, such as „plain text“,  „form“ or „index“. In addition to these more–or–less syntactical categories, we could include more semantically oriented ones, such as „entry–page“ (which syntactically corresponds to a page with almost no text but a graphical link to the main page) or „menu–page“ (page with a few internal links closely tied together). The number of categories depends on the degree of semantic complexity we allow for the categorisation to remain „technological“.
From the user interface viewpoint, we can either apply each dimension separately or combine them into more complex structures. If the number of hits is high enough, we can use the dimensions as three distinct levels of display; otherwise it seems to be more useful to apply a „waterfall“ model, as shown in (Berka et al., 1999): the first dimension (which is usually the bibliographical one) is applied, and only the undecided cases are kept to be categorised according to the second dimension, and then analogously to the third dimension.
3 Thoroughness/response trade-off in WWW analysis
The input for document categorisation may be quite heterogeneous, ranging from explicit metadata or simple data such as URLs and page titles, to abstract concepts extracted from free text or images, or to page access patterns. In our work, we have concentrated on the situation when the amount of information is rather limited. This is typically the case for
•	on-line meta-search systems, which can judge about the links they present to their users solely based on a few data items they receive from the primary search engines in response to user queries. These items always involve the URL and title of the page, usually also a „snippet“ extracted from the beginning of the page, as well as its creation date and filesize. 
•	on-line systems for support of navigation, which, again, cannot invest much time into the analysing of the full content of pages, in particular of those numerous ones with larger topological distance with the page currently viewed by the user.
Sometimes the reason for using only limited („header“) information is a „hard constraint“, such as unavailability of the full text of the page, especially due to stopped or overloaded server, or to security barriers, cf. e.g. (Spertus, 1997). Otherwise the choice between analysing full text vs. „header info“ corresponds to a thoroughness/response trade-off: for on-line applications, the user is unlikely to prefer more reliable categorisation of pages at the cost of waiting several minutes until the full texts are loaded. Compromises are of course possible, such as to apply fulltext analysis only on the items undecidable based on „header info“ (provided they are not too numerous). In the next section, we will however restrict ourselves to the analysis of URL alone, thus giving priority to response.
4 Analysing the URL
4.1 Informativity of the URL
The indispensable role of the URL in document categorisation lays in the insight it may provide to the directory structure at the host server, beside the information content of the server domain as a whole. On the other hand, the full text of a page: 
•	may be voluminous; its loading from a remote server may thus result in a significant response delay, as noted in the previous section; in the worst case, it is simply not accessible due to network traffic or security problems
•	is typically unstructured and thus hard to analyse; the application of sophisticated, noise–tolerant information extraction algorithms, are they available, still aggravates the problem of response
•	sometimes it does not even contain the same information as the URL (in particular, the „context“ of the page given by the directory structure, cf. the last example at Figure 2)
•	may be in a format other than plain text/HTML, such as  PostScript, PDF, or it may not be a text document at all, but is still worth analysing.
All this makes the URL useful for focusing further analysis, and even for („first–shot“) categorisation as such. Naturally, the information content of the URL can drop to zero if directory naming is completely opaque; we however assume that this is not very common, since cryptic names of directories would be an annoyance, above all, for their maintainer. A more common but a bit more soluble problem is that of shortcut terms, which may be often ambiguous (for discussion on ambiguity, see section 5).
Figure 1 and Figure 2 show examples of informative URLs, in the context of meta–search (processing hits returned by an external search engine, say AltaVista) and HTML analysis (with the aim of categorising the given page taking into account the tag structure and outgoing links), respectively. 
At Figure 2, the first three URLs indicate that the referenced page describes a project („proj“), a product („prod“), and lists the staff of a certain institution („people“), respectively. The last URL exhibits the above mentioned feature of delivering bibliographic information (the page corresponds to a technical report – „TechRep“) which is probably not explicitly stated in the full text.
Figure 3 displays a part of an HTML list with a link embedded in each list item. Two of the five URLs include the term „project“ while another two include the term „papers“. A system for text/HTML analysis could then conclude that, being summed up in the same list, the links should point at scientific papers describing a particular project (probably the one to which the whole page is devoted).
4.2 Building a category–recognition rulebase
To build a tool for category recognition, we have followed a step-by-step procedure. 
•	In the first step, we have settled down the categories to be taken into account, for each of the three dimensions above (see section 2).

LAMP: LAMP Ain't Mac POSIX 
LAMP is an ambitious project to provide a POSIX environment on Mac OS.... 
URL: www.metamage.com/proj/lamp/ 
Last modified on: 3-Aug-1999 - 3K bytes - in English

DV2043S8 Level 2 Smart Charger 
Product Brief DV2043S8 Level 2 Smart Charger. Level 2 Smart Charger evaluation and development board. Supports System Management Bus specifications... 
URL: www.benchmarq.com/prod/dv2043s8.html 
Last modified on: 18-Jun-1998 - 4K bytes - in English

The SPBTU People 
The. Signal Processing & Biomedical Technology Unit. People. Faculty. Associate Professor Stavros M. Panas. Associate Professor George Sergiadis.... 
URL: psyche.ee.auth.gr/people.htm 
Last modified on: 22-Nov-1998 - 2K bytes - in English

Cuomo, ``Analysis and Synthesis of Self-Synchronizing Chaotic Systems'' 
Kevin M. Cuomo. ``Analysis and Synthesis of Self-Synchronizing Chaotic Systems,'' MIT Research Laboratory of Electronics No. 582, February 1994.... 
URL: allegro.mit.edu/dspg/pubs.matt/TechRep/19942Cuomo.html 
Last modified on: 8-Sep-1997 - 3K bytes - in English

Figure 2: Search results with „informative“ URLs
<li> <a href="http://www.cs.cmu.edu/afs/cs.cmu.edu/project/theo-11/www/wwkb/overview-aaai98.ps.gz">
Learning to Extract Symbolic Knowledge from the World Wide Web</a>.<br>
M. Craven, D. DiPasquo, D. Freitag, A. McCallum, T. Mitchell, K. Nigam and S. Slattery.<br>
<em> Proceedings of the 15th National Conference on Artificial Intelligence (AAAI-98).</em>
<li> <a href="http://www.cs.cmu.edu/afs/cs.cmu.edu/project/theo-11/www/wwkb/overview-aij99.ps.gz">
Learning to Construct Knowledge Bases from the World Wide Web</a>.<br>
M. Craven, D. DiPasquo, D. Freitag, A. McCallum, T. Mitchell, K. Nigam and S. Slattery.<br>
to appear in <i> Artificial Intelligence </i>, 1999.
<li> <a href="http://www.cs.cmu.edu/~mccallum/papers/cora-aaaiss99.ps.gz">Building Domain-Specific 
Search Engines with Machine Learning Techniques</a>.<br>Andrew McCallum,
Kamal Nigam, Jason Rennie and Kristie Seymore.   <br><em>AAAI-99
Spring Symposium on Intelligent Agents in Cyberspace</em>.  A related paper will also appear in <em>IJCAI'99</em>.
<li> <a href="http://www.cs.cmu.edu/~craven/craven.ismb99.ps">
Constructing Biological Knowledge Bases by Extracting Information from Text Sources</a>.<br>
Mark Craven and Johan Kumlien.<br>
<em>Proceedings of the 7th International Conference on Intelligent Systems for Molecular Biology (ISMB-99)</em>.
<li> <a href="http://www.cs.cmu.edu/~knigam/papers/emcat-mlj99.ps">
Text Classification from Labeled and Unlabeled Documents using
EM</a>.<br> Kamal Nigam, Andrew McCallum, Sebastian Thrun and Tom
Mitchell.<br>To appear in the <em>Machine Learning Journal</em>. 1999.
<b><em> Draft</em></b>.<p>
Figure 3: Excerpt from a page with „informative“ URLs
•	Then we have collected a set of more than 100000 URLs from the domains „com“, „edu“, „gov“, „org“, „uk“ and „cz“ (Czech Republic).  We have used two methods of collection. First, we have submitted extremely general (to say, „empty“) queries to search engines – e.g. in the form „+domain:com“ in the case of AltaVista. Only the URLs of returned „hits“ have been collected. Next, to eliminate the bias incurred by the particular structure of search engines indices, we have used a completely different source – the cache of a WWW server. We have merged (syntactically correct URLs) from both sets.
•	We have parsed the URLs (using a simple definite–clause grammar) to the server part (as list of domains), owner info, list of directory names and the filename.
•	In the resulting structures (in particular in the directory and file names), we sought terms and concepts with frequency above a certain threshold (after some experimentation, we have set it to 0.05%), while discounting multiple occurrences from the same server. As a term separator we understood any sequence of non–alphabetic characters, or a switch from lowercase to uppercase – in this way we e.g. obtain the terms „mailing“ and „lists“ from both „mailing-lists“ and „MailingLists“. To extract potential concepts such as dates (e.g. as „18022000“), other calendar concepts (e.g. „Fall99“) or numerical ranges (e.g. as „10to12“), we have employed a few hand-crafted information extraction rules with specific ontologies.
•	We have, further, computed the frequencies of  adjacent pairs of terms from the list – this has yielded compound terms such as „about us“ or „yellow pages“. 
•	We have visually inspected the resulting, merged, list. It contained a large proportion of meaningful terms („articles“, „messages“, „products“, „books“, „users“, „products“...) or more–or–less decodeable abbreviations („cv“, „prj“, „toc“ ...); the majority of terms could be viewed as category–related. To have an idea of the relative frequencies of terms within the sample, see the fragment from the beginning of  the (alphabetically reordered) lists for both directory and filename, at Figure 3.

Directory	%	Filename	%	
about	0.17	about	0.33	
access	0.15	ad	0.43	
academic	0.12	all	0.32	
ad	0.11	archive	0.16	
admissions	0.05	art	0.22	
ads	0.21	arts	0.14	
all	0.11	banner	0.32	
and	0.18	bar	0.18	
archive	0.07	back	0.12	
archives	0.12	bio	0.26	
art	0.19	blank	0.20	
articles	0.08	black	0.12	

Figure 3: Fragments of lists of terms and their frequencies from directory structure and filename

•	We have posed each term as query to an external search engine. AltaVista could be satisfactorily adopted for this purpose, as it allows „targeted queries“ such as „+url:about“. We have inspected the results (usually the first 20–30 hits) and eliminated the term if the page information displayed seemed to deviate from our expected semantics too often (say, in more than approx. 20% of cases). Some of the unclear terms have been submitted to the disambiguation experiment, see section 5.
•	The final, most tedious step, consisted in manual formulation of  rules, which had goal categories in their conclusion parts and relevant URL terms, concepts, or their combinations in their condition parts. In addition, we have added a few heuristics not directly related to the previous analysis, such as „the website homepage (e.g. the one referred to by URL in the form of root directory) contains organisational information“. 
The rules have been implemented as a production rulebase of the CLIPS system. As an example, the rule
IF „~“  owner AND „intro“  file_terms THEN bib_type = PersonalInfo
can be rewritten in CLIPS as
	(defrule bibtype-personal-info 
(declare (salience 500))
   ?f <- (html (type1 "") (owner ?owner) (filewords $?wpred ?w $?wpo))
   (test (numberp (str-index "~" ?owner)))
   (test (lexemep ?w))
   (test (numberp (str-index "intro" ?w)))
   =>
    (modify ?f (type1 "Personal info"))
)

4.3 Experiments with category recognition
A straightforward way of collecting testing data for the WWW page categorisation task was, again, to pose queries to web search engines. In order to automate this task, we have used our experimental meta-search tool Vseved (Berka et al., 1999). The sets of links returned by Vseved (and, originally, by external search engines) have been processed by means of the above described recognition rulebase. We have then recorded the numbers of links categorised according to each dimension. 
In order to test the coverage of the rulebase in an unbiased way, we have borrowed two sets of topics which could serve as input queries:
•	The first, which had been assembled in the context of the CLEVER project (Chakrabarti et al., 1998) at the IBM Almaden center, contained 28 subjects of general public interest, such as „lyme disease“, „rock climbing“ or „Thailand tourism“. 
•	The second, more specific one, consisted of 22 names of papers from DATASEM98 – a medium–sized database conference. One half of the names was in English (such as „Transaction–oriented applications of the HTML and Java languages“), the other half was in Czech. We have considered each language separately, and used an appropriate search engine for each of them (AltaVista for the English names, and its largest Czech counterpart, Kompas, for the Czech names).

Dataset and way of categorisation	Bibliographic type	Sphere of origin	Technological type	Undecided	
CLEVER					
separate  (%)	51	89	5		
waterfall (%)	51	40	1	8	
DATASEM–CZ					
separate (%)	38	52	1		
waterfall (%)	38	36	0	26	
DATASEM–EN					
separate (%)	23	72	8		
waterfall (%)	23	59	2	16	

Table 2: Results of testing the production rulebase on independent datasets

Each topic was treated simply as a set of search terms. For each query, we have analysed only the first ten hits (considered as most relevant by the external search engine); there have thus been 280 cases for CLEVER data and 110 cases for each of the language pools of the DATASEM data.
In Table 2 we can see the percentage of cases (hits) categorised. For each dataset, the results are listed both for separate categorisation in each dimension and for waterfall categorisation, where cases undecided in one dimension fell down to the next dimension.
From the table follows (summing up the „waterfall rows“) that the rulebase has categorised 92% of general English links (to read, links returned for general English queries), 84% of specific English links and 74% of specific Czech links. In contrast, the „bibliographic“ part alone has categorised 51% of general English links, 23% of specific English links and 38% of specific Czech links. The high coverage for general English links was however due to many (48%) site homepages returned, which have been (rather problematically) labelled as „Organisational information“. The relatively high coverage for specific Czech links (where assignments to „Organisational information“ accounted for 9% only)  may, on the other hand, indicate higher lucidity of directory naming within the Czech subset of the web compared to the English-language one (given the fact that the rules themselves involved English and Czech terms in a comparable degree).
We would like to note that the proportion of recognised page types reflects merely the coverage of the recognition rules. Although we have included only URL terms which, as a result of previous „targeted querying“, should have limited chance to be used beyond the expected context, the proportions of  term occurrences with the „correct“ semantics may not be always the same – it would thus not be sound to claim that the precision exceeds 80%. In order to obtain a „canonical“ measure of precision for the given datasets, tests with laboriously pre–labelled examples would have to be performed, analogously to (Chakrabarti et al., 1998).
5 Problem of term ambiguity
Several interesting terms, and especially abbreviations, with high frequency in data, could not be immediately used in the rulebase due to their ambiguity. This was the case e.g. for the rather frequent abbreviations „art“, „pub“, „.bio“ or „cat“.  We have thus developed a method for automatic disambiguation of such (previously identified) terms, with the aid of machine learning. The disambiguation consists in specialising the original term into a more complex expression, which is able to distinguish among different senses and/or acronym interpretations; let us denote them as semantic indices of the term.
•	In the first phase, examples of hits with the particular term in the URL are retrieved, again via „targeted querying“ an external search engine (AltaVista), with queries of the sort „url:art“. In the difference to the original „targeted querying“ described in section 4.2, the querying is not done manually but by means of a simple program, which collects the hits (several hundreds for each term), and parses them into their descriptive elements: URL, title, extracted text, size and date. 
•	The examples are redisplayed, in a structured form, to multiple users (volunteers), who can assign to each example a semantic index from a precompiled list.
•	The examples which have obtained the same index from all (or most) users are kept; the other are discarded.
•	The valid examples of each class (i.e. semantic index) are converted into a predicate representation, which describes 
•	the inclusion of particular terms in the URL, title, and extracted text 
•	structure of the URL 
•	file size
•	proportion of specific symbols in the title and extracted text
	etc.
•	The examples in predicate representation are submitted to an ILP (Inductive Logic Programming) learner, which should generate hypothesis discriminating between the classes.
Up to know, we have collected sets of examples and labelled some of them with semantic indices. To illustrate the outlook of these intermediate results: preliminary analysis has revealed that approx. 60% of the links with „art“ in the directory structure deal with art, while the useful notion of article (as type of publication) accounts for approx. 20%; the rest pertains to other meanings (e.g. „article“ as item in a product list) or could not be easily identified even by humans. We are now experimenting with different predicate representations; as ILP tool, we are currently using one of the implementations of Progol (Muggleton, 1995).
6 Related work
Analysis of URL is frequently used ad–hoc, as a  means of distinguishing between certain types of pages. The most common uses include:
•	recognition of advertisements: at many servers, the so–called blocklists of terms/strings typical for publicity servers are maintained, which can be used e.g. to filter banner advertisements from display in browsers – for an overview see e.g. (Kushmerick, 1999).
•	recognition of children–unfriendly documents.
However, as it seems, a systematic account of URL utility for page categorisation has been missing so far. Moreover, bibliographic categorisation (irrespective the source of information) has been surprisingly omitted by of common search engines and navigation–support tools.
There are also several applications of Machine Learning which are comparable with our method of disambiguation of URL terms. Kushmerick (1999) used propositional machine learning (decision tree induction) to discover terms from URLs of images, in order to distinguish between banner ads and other types of images. Craven et al. (1998) used ILP for recognition of page type; the input for learning was, however, fulltext analysis, and the types distinguished in the experiments described was somewhat specific for an academic domain („teacher’s page“, „course page“, „department page“ etc.). 
Our method is, also, in a way, analogous to natural language disambiguation projects, which also often rely on Machine Learning  via ILP (see e.g. Popelínský & Pavelek, 1999).
7 Future work and conclusions
We have presented our idea of multidimensional categorisation of WWW documents, which should improve the insight of the user (of e.g. meta–search tool or intelligent browser) into the nature of the pages referenced, via delivering the information on bibliographic type, sphere of origin and technological type. Each dimension consists of a predefined number of categories, originated from existing metadata standards as well as from empirical analysis.
We have concentrated on the utility of URL as a potentially rich source of information available without significant time costs. Our analysis suggests that URLs, on average, contain more categorisation–relevant information than one would expect. An important problem is that of term ambiguity; it seems that machine learning techniques such as ILP could contribute to its solution.
Our study has also shown that general purpose search engines (such as AltaVista) can be used not only for end–user purposes but also as a flexible source of data usable for analysis of general features of the web, both by humans and by computer systems.
In the nearest future, we would like to complete the ILP experiments with term disambiguation, and to verify on data the accuracy of the resulting, complex, recognition rules.
We also intend to broaden the scope of application of the above describe URL analysis. So far, our application has been oriented toward post–processing of the output of meta–search. In the future, we would like to concentrate on the other task outlined in section 4.1, namely on the analysis of outgoing links for a given page. This task is particularly useful in the support of navigation, since the source of the current page viewed by the user is immediately available for the supporting tool but the number of pages connected via hypertext paths grows exponentially with topological distance, which is a significant time constraint for an on-line application.
Acknowledgements
The authors owe their thanks to M.Sochorová who has implemented parts of the meta-search system, to P.Šimek whose set of WWW ontologies was a precursor to our multidimensional page categorisation, to D.Šrámek for his assistance in acquiring the URL data, and to M.Kavalec who has contributed to the most recent experiments with term disambiguation. We are also grateful to the two anonymous reviewers for their comments.
The research on this topic has been partially supported by Grant no.VS96008 of the Czech Ministry of Education,  „Laboratory of Intelligent Systems“. 
References
Berka, P. & Sochorová, M. & Svátek V. & Šrámek, D. (1999). The VSEved System for Intelligent WWW Metasearch. In: INES'99 – IEEE International Conference on Intelligent Engineering Systems, Stará Lesná 1999.
Chakrabarti, S. & Dom, B. & Gibson, D. & Kleinberg, J. & Raghavan, P. & Rajagopalan, S. (1998). Automatic resource compilation by analyzing hyperlink structure and associated text. In: Proc. 7th Intl. WWW Conf., 1998.
Craven, M. & DiPasquo, D. & Freitag, D. & McCallum, A. & Mitchell, T. & Nigam, K. & Slattery, S. (1998). Learning to Extract Symbolic Knowledge from the World Wide Web. In: Proceedings of the 15th National Conference on Artificial Intelligence (AAAI-98).
Joachims, T. & Freitag, D. & Mitchell, T. (1997) WebWatcher: A Tour Guide for the World Wide Web. In: Proceedings of IJCAI97, August 1997.
Kushmerick N. (1999). Learning to remove Internet advertisements. In: 3rd Int. Conf. on Autonomous Agents, 1999.
Muggleton, S. H. (1995). Inverse Entailment and Progol, New Gen. Comput., 13:245-286.
Popelínský, L. & Pavelek, T. (1999). Mining Lemma Disambiguation Rules from Czech Corpora. In: PKDD'99 - Principles of Data Mining and Knowledge Discovery, Prague, 1999.
Spertus, E. (1997). ParaSite: Mining Structural Information on the Web. In: Proceedings of the 6th International World Wide Web Conference, 1997.
Šimek, P. (1999). Ontologies and WWW, Master thesis (in Czech), VŠE 1999.
Weibel, S. & Kunze, J, & Lagoze. C. & Wolf, M. (1998). Dublin Core Metadata for Resource Discovery. IETF #2413. The Internet Society, September 1998.