This paper presents a robust method for the construction of collection-speci c document models. These document models are variants of the well-known vector space model, which relies on a process of selecting, modifying, and weighting index terms with respect to a given document collection. We improve the step of index term selection by applying statistical methods for concept identi cation. This approach is particularly suited for post-retrieval categorization and retrieval tasks in closed collections, which is typical for intranet search.
Each text retrieval task that is automated by a computer relies on some kind of document model, which is an abstraction of the original document d. The document model must be tailored well with respect to the retrieval task in question: It determines the quality of the analysis, anddiametrically opposedits computational complexity. Though its obvious simplicity the vector space model has shown great success in many text retrieval tasks [11; 12; 16; 15], and, the analysis of this paper uses this model as its starting point.
The standard vector space model abstracts a document d toward a vector d of weighted index terms. Each term t that is included in d derives from a term 2 d by af x removal, which is necessary to map morphological variants of onto the same stem t. The respective term weights in d account for the different discriminative power of the original terms in d and are computed according to some frequency scheme. The main application of the vector space model is document similarity computation.
1.1
lies on additional domain knowledge, or if it exploits external information sources by means of some inference procedure, or both.
viewpoint of a human reader, while the related instances of the
vector space model do not re ect this fact because of the different words
used. Index term enrichment can account for this by adding
synonymous terms, hypernyms, hyponyms, or co-occurring terms [
Semantic approaches are oriented at the human understanding of language and text, and, as given in the case of ontological index term enrichment, they are computationally ef cient. However, the application of the semantic approaches is problematic, if, for instance, the document language is unknown or if a document combines passages from several languages. Moreover, there are situations where semantic approaches can even impair the retrieval quality: Consider a document collection with specialized texts, then ontological index term enrichment will move the speci c character of a text toward a more general understanding. As a consequence, the similarity of highly specialized text is diluted in favor of less specialized text which compares to the effect of adding noise. 1.2
We investigate variants of the vector space model with respect to their classi cation performance. Starting point is the standard vector space model where the step of index term selection is improved by a syntactic approach for concept identi cation; the resulting model is compared to semantically enriched vector space models. The syntactic concept identi cation approach is based on a collection-speci c suf x tree analysis. In a nutshell, the paper's underlying question may be summarized as follows:
Can syntactically determined concepts keep up with a
semantically motivated index term enrichment?
To answer this question we have set up a number of text categorization experiments with different clustering algorithms. Since these algorithms are susceptible to various side effects, we will also present results that rely on an objective similarity assessment statistic: the measure of expected density, . Perhaps the most interesting result may be anticipated: The positive effect of semantic index term enrichment, which has been reported by some authors in the past, could hardly be observed in our comprehensive analysis.
A document d can be viewed under different aspects: layout, structural or logical setup, and semantics. A computer representation d of d may capture different portions of theses aspects. Note that d is designed purposefully, with respect to the structure of a formalized query, q, and also with having a particular retrieval model in mind. A retrieval model, R, provides the linguistic rationale for the model formation process behind the mapping d 7! d. This mapping involves an inevitable simpli cation of d that should be
retically or empirically, and provides a concrete means, (q; d), for quantifying the relevance between a formalized query q and a document's computer representation d. Note that (q; d) is often specied in the form of a similarity measure '.
retrieval model R form the document model; Figure 2 illustrates the connections.
Let D be a document collection and let T be the set of all terms that occur in D. The vector space model d of a document d is a vector of jT j weights, each of which quantifying the importance of some index term in T with respect to d.3 This quanti cation must be seen against the background that one is interested in a similarity function ' that maps from the vectors d1 and d2 of two documents d1, d2 into the interval [0; 1] and that has the following property: If '(d1; d2) is close to 1 then the documents d1 and d2 are similar; likewise, a value close to zero indicates a high dissimilarity. Note that document models and similarity functions determine each other: The vector space model and its variants are amenable to the cosine similarity (= normalized dot product) in rst place, but can also be used in connection with Euclidean distance, overlap measures, or other distance concepts.
Under the vector space paradigm the document model construction process is determined in two dimensions: index construction and weight computation. In the following we will concentrate on the former dimension since this paper contributes right here. We have clas3 Note that, in effect, the vector space model is a computer representation of a the textual content of a document. However, in the literature the term vector space model is also understood as a retrieval model with a certain kind of relevance computation.
Index construction principle
Conceptual model Layout view Structural / logical view Semantic view
d ÎD Real-world document
Computer representation of document Relevance computation
Linguistic theory
Retrieval model R r(q,d)
Document model
q ÎQ Formalized query
q ÎQ Information need si ed the index construction principles for vector space models in four main classes, which are shown in Figure 1.
Index Term Selection. Selection methods further divide into inclusion and exclusion methods. An important exclusion method is stopword removal: Common words, such as prepositions or conjunctions, introduce noise and provide no discriminating similarity information; they are usually discarded from the index set. However, there are special purpose models (e. g. for text genre identi cation) that rely on stopword features [13; 9].
method but simply takes the entire set T without stopwords. More advanced vector space models use also n-grams, i. e., continuous sequences of n words, n 4, which occur in the documents of D.
all n-grams should be added but threshold-based selection methods
be applied, which rely on the information gain or a similar
statistic [
Index Term Modi cation. Most term modi cation methods aim at generalization. A common problem in this connection is the mapping of morphologically different words that embody the same concept onto the same index term. So-called stemming algorithms apply here; their goal is to nd canonical forms for in ected or derived words, e. g. for declined nouns or conjugated verbs. Since the uni cation of words with respect to gender, number, time, and case is a language-speci c issue, rule-based stemming algorithms require the development of specialized rule sets for each language. Recall that
Co-occurrence analysis
Stopword removal Stemming Addition of synonym sets Singular value decomposition the application of language-speci c rule sets requires the problem of language detection both in unilingual and multilingual documents to be solved.
Index Term Enrichment. We classify a method as term enriching, if it introduces terms not found in T . By nature, meaningful index term enrichment must be semantically motivated and exploit linguistic knowledge. A standard approach is thepossibly transitiveextension of T by synonyms, hypernyms, hyponyms, and co-occurring terms. The extension shall alleviate the problem of different writing styles, or of vocabulary variations observed in very small document snippets as they are returned from search engines.
Index Transformation. In contrast to the construction methods mentioned before, transformation methods operate on all document vectors of a collection D at the same time by analyzing the termdocument matrix, A. A popular index transformation method is latent semantic indexing (LSI), which uses a singular value decomposition of A in order to improve query rankings and similarity computations [2; 1; 8]. For this purpose, the document vectors are projected into a low-dimensional space that is spanned by the eigenvectors that belong to the largest singular values of the decomposition of A. 2.1
Index terms that consist of a single word can be found by a skillful analysis of pre x frequency and pre x length. This idea can be extended to the identi cation of compound word concepts in written text. If continuous sequences of n words occur signi cantly often, then it is likely that these words form a concept. Put another way, concept detection reduces to the identi cation of frequent n-grams.
n-grams as a replacement for index term enrichment has been
analyzed by several authors in the past, with moderate success only [
inate the positive impact of few additional concepts: Most authors apply a strategy of complete extension; i. e., they add all 2-grams and 3-grams to the index vector. However, when analyzing the frequency distribution of n-grams, it becomes clear that only a small fraction of all compound word sequences is statistically relevant.
struction can be summarized as follows:
document snippets are involved. This problem is also investigated in the next section, where the development of the index quality is compared against the underlying collection size.
word concepts are essentially the samethe level of granularity makes the difference: Stemming means frequency analysis at the level of characters; likewise, the identi cation of concepts means frequency analysis at the level of words.
enrichment are contradictory [4; 5; 7], and not all of the published
performance improvements could be reproduced [
the same cluster algorithm under different document models may tell us two things: (i) whether one document model captures more of the gist of the original document d than another model, and, (ii) whether the cluster algorithm is able to take advantage of this added value.
such as the cluster number, its randomized start con guration, or preset similarity thresholds, etc., which renders a comparison dif cult. Moreover, there is the prevalently observed effect that different cluster algorithms behave differently sensitive to document model improvements. From an analysis point of view the following questions arise:
(the best for the dataset, the most commonly used, the simplest)?
rent research: Common practice is to select the best result compared to a given reference classi cation, e. g. by maximizing the F
vised/supervised methods is far away from reality.4
An objective way to rank different document models is to compare their ability to capture the intrinsic similarity relations of a given collection D. Basic idea is the construction of a similarity graph, measuring its conformance to a reference classi cation, and analyzing the improvement or decline of this conformance under some document model. Exactly this is operationalized in form of the -measure that is introduced below; it enables one to evaluate differences in the similarity concepts of alternative document models without being dependent on a cluster algorithm.5
prise two types of analyses: (i) Experiments that, based on , quantify objective improvements or declines of a document model, (ii) experiments that, based on the F -Measure, quantify the effects of a document model onto different cluster algorithms. 3.1
As before let D = fd1; : : : ; dng be a document collection whose corresponding computer representations are denoted as d1; : : : ; dn. A similarity graph G = hV; E; 'i for D is a graph where a node in
the similarity '(di; dj ).
A graph G = hV; E; wi is called sparse if jEj = O(jV j); it
is called dense if jEj = O(jV j2). Put another way, we can
compute the density of a graph from the equation jEj = jV j . With
4 This issue is addressed in [
subgraph G0 = hV 0; E0; w0i of G to the density of G: G0 is sparse (dense) compared to G if the quotient w(G0)=(jV 0j ) is smaller (larger) than 1. This consideration provides a key to quantify a document model's ability to capture the intrinsic similarity relations of
Let C = fC1; : : : ; Ckg be an exclusive categorization of D in k distinct categories, that is to say, Ci; Cj D with Ci \ Cj = ; and [ik=1Ci = D, and let Gi = hVi; Ei; 'i be the induced subgraph of G with respect to category Ci. Then the expected density of C is de ned as follows.
k (C) = X jVij
jV j i=1 w(Gi) ; jVij where jV j = w(G)
associated with V , a higher value of indicates a better modeling of a collection's similarity relations. 3.2
Aside from the standard vector space model our analysis compares
the following three vector space model variants:
1. Syntactic Term Selection. Within this variant the index term
selection step also considers syntactically identi ed concepts, i. e.,
2grams, 3-grams, and 4-grams. To identify the signi cant n-grams
the document collection D is inserted into a suf x tree and a
statistical successor variety analysis is applied. The operationalized
principle behind this analysis is the peak-and-plateau method [
tf idf -scheme; stopwords are not indexed and unigram stemming is done according to Porter's algorithm.
Discussion. The resulting graphs in Figure 3 as well as the comparison in Table 1 show that the syntactic approach outperforms both semantic approaches. From the semantic variants only the semantic hypernym enrichment is above the baseline; note that this happens even if a large number synsets is added. We explain the results as follows: Index terms with a high term weight typically belong to a special vocabulary, and, from a semantic point of view, they are used deliberately so that adding their synsets will tend to decrease their importance. Likewise, adding the synsets of low-weighted terms has no effect other than adding noise since the importance of these terms will be increased without a true rationale.
standard vector space model synonym enrichment hypernym enrichment n-gram index term selection F -min F -max F -av. (sample size 1000, 10 categories) -8% +5% +15% baseline +4% +12% +6% -2% +3% +8%
Corporation for research purposes. It contains more than 800,000 documents each of which consisting of a few hundred up to several thousands words. The documents are tagged with meta information like category (also called topic), geographic region, or industry sector. There are 103 different categories, which are arranged within a hierarchy of the four top level categories Government, Social, Economics, Markets, and Corporate, Industrial. Each of the top level categories de nes the root of a tree of sub-categories, where each child node ne grains the information given by its parent. Note that a document d can be assigned to several categories c1; : : : ; cp, and that d does also belong to all ancestor categories of some category ci.
belong to the same category if they share the same top level category ct and the same most speci c category cs. Moreover, the test sets are constructed in such a way that there is no document di whose most speci c category cs is an ancestor of the most speci c category of some other document dj .
trinsic similarity relations based on , the sample sizes ranged from 200 to 1000 documents taken from 5 categories. For the analysis of the categorization experiments, based on cluster algorithms and evaluated with the F -Measure, the sample sizes were 1000 documents taken from 10 categories.7
RCV1
Government, Social Economics Markets Corporate, Industrial
Insolvency, Liquidity Performance ...
Account, Earnings Comment, Forecasts
Annual results
ods for the construction of vector space models; the special focus was index term selection. Interestingly, little attention has been paid to the mentioned syntactical methods in connection with text retrieval tasks. Following results of our paper shall be emphasized:
7 To make our analysis results reproducible for other researchers, meta information les that describe the compiled test collections have been recorded; they are available upon request.
benchmarks to compare research efforts related to document models or similarity measures.
Though syntactical analyses must not be seen as a cure-all for the index construction of vector space models, they provide advantages over semantic methods, such as language independence, robustness, and tailored index sets. With respect to several retrieval tasks they can keep up with semantic methodshowever, our results give no room for an over-simpli cation: Both paradigms have the potential to outperform the other.
[15] Michael Steinbach, George Karypis, and Vipin Kumar, `A comparison of document clustering techniques', Technical
ICML-97, 14th International Conference on Machine
(1997). Morgan Kaufmann Publishers, San Francisco, US.