Taxonomies are becoming essential in several elds, playing an important role in a large number of applications, particularly for speci c domains. Taxonomies provide e cient tools to people by organizing a huge amount of information into a small hierarchical structure. Taxonomies were originally built by hand, but nowadays the technology permits to produce a vast amount of information. Consequently, recent research activities have been focused on automated taxonomy generation. In this paper, we propose a novel approach for automatically build a taxonomy, starting from a set of categories. We deem that, in a hierarchical structure, each node should intuitively be represented with proper meaningful and discriminant features, instead of considering a xed feature space. Our proposal relies on two metrics able to identify the most meaningful features. Our conjecture is that a feature could signi cantly change its discriminant power (hence, its role) along the taxonomy levels. Hence, we devise a greedy algorithm able to build a taxonomy by identifying the meaningful terms for each level. We perform preliminary experiments that give rise to the usefulness of the proposed approach.
Taxonomies play an important role in a growing number of application, particularly for speci c domains. Originally built by hand, taxonomies have been recently focused on their automatic building. In particular, a crucial issue of taxonomy building is the choice of the most suitable features (e.g., meaningful terms in textual documents). We deem that, in a hierarchical structure, a node should intuitively be identi ed by proper discriminant terms, rather than de ning a sole feature space for the entire taxonomy.
In this paper, we de ne a novel approach for automatically build a taxonomy,
starting from a set of categories. We adopt two novel metrics, i.e., the
discriminant capability and the characteristic capability [
The rest of the paper is organized as follows: Section 2 presents the background and the related work on taxonomy generation; Section 3 describes the discriminant and characteristic capabilities, whereas in Section 4 the proposed algorithm is described and detailed; experiments are reported in Section 5, while Section 6 ends the paper with the conclusions and the future work. 2
Nowadays, taxonomies are indispensable to a huge number of applications. For
example, in web search, organizing domain-speci c queries into a hierarchy can
help to better understand the queries and improve search result [
An important task for taxonomy building is to recognize the most meaningful features. Our insight is that, due to the hierarchical structure, each node intuitively should be represented with proper meaningful terms, instead of considering a xed vocabulary for the entire structure. we deem that each document collection is unique, making useful to devise methods and algorithms able to automatically build a distinct list of meaningful features for each collection. 3
In this Section we describe the adopted metrics and their properties. 3.1
The metrics have been devised for both classi ers performance assessment and
feature selection [
In the underlying scenario of text categorization, measures the ability of a
term to distinguish a given category C against others, whereas ' measures to
which extent a term is pervasive in the given set of documents. in formula:
=
' =
#(t; C)
#(C)
#(t; C)
#(C)
+
#(t; C)
#(C)
#(t; C)
#(C)
1
where a generic term t contained in a document represents the binary feature
under analysis, meaning that it can be assume two values, depending on the
presence or absence in the document. The meaning of each component in the
formulas are the following: #(t; C) is the number of documents of C containing t;
#(t; C) is the number of documents of C containing t; #(C) is the total number
of documents of C; #(C) is the total number of documents of C.
Let us recall that in [
Important terms for text classi cation appear in upper and lower corner of the rhombus in Figure 1, as they have high values of j j. In particular, a high positive value of (the region marked as + in the Figure 1) means that the term frequently occurs in C and is rare in C; ideally, is +1 when the term occurs in all documents of C and no documents of C contain it. Conversely, a high negative value of (the region) means that the term frequently occurs in C and is rare in C; ideally, = 1 means that all documents of C contain the term, and no documents of C contain it. As for the characteristic capability, terms that occur barely on the entire domain are expected to appear in the left corner of the rhombus (' ), while stopwords are expected to appear in the right handed corner ('+). Ideally, ' = +1 when the term occurs in each document of the entire domain, whereas ' = 1 when the term is completely absent in the domain. Figure 1 outlines the expected behavior for all cases.
Terms falling in '+ do not necessarily represent typical stopwords only (i.e.,
common articles, nouns, conjunctions, verbs, and adverbs). Rather, also
domaindependent stopwords are located in that area [
Moreover, theoretically, if a term has a zero value for both and ' in a given category C, it is equally distributed in the domain in this way: half of C documents contain the term, and also half of documents of the alternate category C contain the term. If a term is projected close to the origin of the space, there is uncertainty in considering the term as stopword, irrelevant, or discriminant1.
In a previous work a preliminary analysis on how each feature changes its
role along taxonomy nodes has been performed [
Furthermore, a domain-dependent stopword becomes discriminant in the upper levels, giving rise to the relevance of such terms. 4
The algorithm proposed in this work is based on a bottom-up approach for building a hierarchy tree, starting from a set of leaf categories over a corpus of documents. The information needed to initialize the algorithm is, for each category: a) the number of documents falling into the category and b) for each term t in the corpus, the number of documents containing t.
In the previous work about the term roles in a taxonomy [
4.1
As discussed in the previous section, the properties of a term depend on which region of the ' rhombus it falls. Let us de ne two regions: the characteristic (A') and the discriminant (A ) areas. In this preliminary study, we simply identify the areas by the following schema: (3) (4) (5)
These equations need to be generalized for a hierarchy. We de ne a hierarchy as a series of level represented by a layer of categories. Each layer contains the categories belonging to the respective level of the hierarchy, grouped by their parent category. For example, if a particular level contains the categories A; B; C; D; E, and A; B; C have X as parent category and D; E have Y as parent category, the layer for that level will be de ned as: fA; B; Cg; fD; Eg. We call fA; B; Cg and fD; Eg siblings groups. We can see a layer as the partition of the categories in a level, de ned by their sibling relations.
We de ne the indicator function for the characteristic terms of a sibling group Sk as follows: (t; Sk) = 8 > ><1 > >:0 jSkj X i=1 otherwise (t; Ci; Ci) jSkj 2 where Ci is the alternate category of a given class Ci, i.e., the union of the siblings of Ci.
In a similar way we can de ne the indicator function for the discriminant terms of a sibling group in a layer L: (t; Sk; L) =
(t; P (Sk); P (Sk)) where Sk is the union of the rest of siblings groups, and P (S) indicates the parent node for a siblings group S.
Using Eq. 5 and Eq. 6 we can now de ne the set of characteristic terms T' and the set of discriminant terms T for each siblings group in a layer:
T'(Sk) = ft : (t; Sk) = 1g T (Sk; L) = ft : (t; Sk; L) = 1g (6) (7) (8) 4.2
The proposed bottom-up algorithm is split into a series of optimal partition problems. For the current set of categories at hand (starting from the leaves), we strive for identifying the optimal layer, that is, the optimal set of siblings groups. Once these groups are identi ed, the categories inside them are \collapsed" together to generate the parent categories, and the algorithm goes on recursively, layer by layer, until some stop condition is met.
To identify the optimal layer we use a target function that is derived from Eq. 7 and Eq. 8. The rationale behind this function has already been discussed in Sec. 3.2: the behavior we expect in a taxonomy is that a large number of characteristic terms of a sibling group become determinant terms of the parent category. We de ne the target function, that we call layer score (G), as following: jLj G(L)B = X k=1 jT'(Sk) \ T (Sk; L)j (9)
The optimization task that identi es the optimal layer L can then be stated as follows:
L = arg max G(L) (10)
L
Solving exactly Eq. 10 is an NP-hard problem as the search space is de ned
by the Bell number [
The algorithm starts from the trivial layer, in which each siblings group contains exactly one category, and proceeds recursively. The layer under analysis is the current candidate. At each step, the algorithm looks for all the layers reachable by moving exactly one category from its current sibling group to another group. The algorithm then evaluates the layer score of each of these layers, and if the maximum score exceeds the score of the starting layer, the associated layer becomes the current candidate. If not, the current candidate is chosen as the one satisfying (approximately) Eq. 10.
Once the optimal layer has been chosen, each sibling group is collapsed to generate the parent categories (P ): (11) P (Sk) = jSkj [ Ci i=1
In the rest of the discussion, it is implicit that some sort of mechanism is in place to keep track of which categories (if any) are children of a given category. 4.3
We are now able to describe the entire algorithm succinctly. It expects the following inputs: { the set of leaf categories Cleaves; { for each leaf category Ci, all the data needed to calculate ' and , described in Sec. 3.1.
The output is the generated taxonomy T . The algorithm then proceeds iteratively, until the stop condition (Step 6) is met. There are two distinct loops: in the outer one, we build the taxonomy one level at a time; in the inner loop, we search for an approximation of the optimal layer. 1. Add the current set of categories to the taxonomy T as a taxonomy level ; 2. Put the current set of categories in a trivial layer ; 3. Mark the trivial layer as the chosen layer Lc and calculate its score Gc; 4. Mark the next layer Ln = Lc, and next layer score Gn = Gc; 5. For each (unordered) pair of sibling groups in Lc: (a) Evaluate the score Gh of the layer obtained by merging the pair of groups, Lh; (b) If Gh > Gn: set Ln = Lh and Gn = Gh; 6. If Ln is still the trivial layer: the stop condition is met: return T . 7. If Ln 6= Lc: set Lc = Ln and Gc = Gn; go back to Step 5; 8. Otherwise: consider Lc the optimal layer and collapse it to generate the set of parent categories (use Eq. 11 on each of its sibling groups); go back to Step 1. 5
Assessing an algorithm for the generation of taxonomies is an hard task. This is due to the fact that existing taxonomies are far from being considered \golden standards", that is, they are not precise enough to guarantee that they can be taken as absolute reference during the test phase. Moreover, many metrics exist to measure the agreement between two taxonomies, and none of them is universally accepted as a good one. 5.1
Let TR be the reference taxonomy and TL the learned taxonomy, that the algorithm described in Sec. 4.3 generates. We need to assess the learned taxonomy by comparing them with the reference.
To measure the agreement between TR and TL, we use the metric de ned by
Navigli [
To assess the agreement between the two taxonomies, we rst measure the agreement between two unwrapped layers: Where n11 is the number of pair of leaves included in the same group in both layers, n01 is the number of pair of leaves included in the same group in the learned layer but not in the reference layer, and viceversa for n10.
The overall metric is then de ned as:
B(TR; TL) = k 1 X i + 1 Bi
k 2 k + 1 i=0 It can easily be noticed that B takes into higher consideration the layer metric of the deeper layers in the taxonomy. This is necessary to counterbalance the fact that as less sibling groups are found in the rst layers, the probability that a pair of categories is found in the same group just by chance is increased; they thus need to be given a lower weight in the overall metric.
If the depth of the learned taxonomy is di erent from the depth of the reference one, we have to slightly adjust the previous de nition: { if kL > kR: the layers after kR are ignored: this way we give an higher score to more structured learned taxonomies; { if kL < kR: the last layer in the learned taxonomy is repeated as many times as needed to reach kR. This way less structured taxonomies get a lower score. (12) (13) Experiments are performed using a collection of webpage documents. The dataset is extracted from the DMOZ taxonomy2. Aside from the leaves, each node is built with the union of the children's documents. Textual information from each page code is extracted, and each document is converted into a bag of words representation, each word being weighted with two values: and ', computed by applying equations 1 and 2. We built 19 small sub-taxonomies of DMOZ. We grouped them in terms of \di culty". Table 1 shows the main properties of each taxonomy. \Easy" and \easy-medium" taxonomies have base categories very di erent between them, so also the leaves will clearly be very di erent or very similar between them, and the grouping task should be easier. \Medium" taxonomies stem from the same root category, so the similarity between leaves increases. Finally, \medium-hard" and \hard" taxonomies have a lot more leaves and multiple root and intermediate categories. Fig. 3 and Fig. 4 are examples of taxonomies used in the experiments. 5.3
Tab. 2 contains a summary of the experimental results, and Fig. 5 shows an example of taxonomy learned by the algorithm. Let us note that the generated
Arts Crafts 5 leaves Internet 4 leaves Computer Science
Departments People
Computers
Hardware+Internet
H+I 1 Peripherals Systems On the Web Web Design
H+I 2 E-mail RFCs taxonomy is very close to the original one even from a qualitative point of view. The obtained scores con rm the quality in most of the cases. 6
In this paper, a novel approach for automatically build a taxonomy has been proposed. The proposal adopts two novel metrics, i.e., the discriminant capability and the characteristic capability, able to measure the discriminant power of a feature. The former grows in accordance with the ability to distinguish a given category against others, the latter grows in accordance to how the feature is frequent and common over all categories. Our conjecture is that a feature could change its role, depending on its discriminant power, along the taxonomy levels. This behavior has been exploited for devising the algorithm, that is based on the identi cation of the meaningful terms for each level. In particular, we devise a greedy bottom-up algorithm that recursively identi es the optimal layer for each level.
The proposal, even if it is still in a preliminary stage, provides encouraging results, as shown by the experiments. As for future work, we are currently improving and re ning the algorithm, with di erent strategies. Furthermore, a set of comparing experiments with several state of the art approaches are planned, in order to give rise to the usefulness of the proposed approach.