A Hybrid Algorithm for
Alignment of Concept Hierarchies
Ryutaro Ichise1,2 , Masahiro Hamasaki2 , andHideaki Takeda1,2
1National Institute of Informatics,
Tokyo 101-8430, Japan
2
The Graduate University for Advanced Studies,Tokyo 101-8430, Japan{ichise@,hamasaki@grad.,takeda@}nii.ac.jp

Abstract. Hierarchical categorization is a powerful and convenientmethod so that it is commonly used in various areas, such as ontologies. Although each hierarchy is useful, there are problems to manage
multiple hierarchies. In this paper, we propose an alignment method between concept hierarchies by using the similarity of the categorizationand the contents of the instance. By using this method, instances thatexist in one hierarchy system but does not in the other can be located ina suitable position in the other. The experimental results show improved
performance compared with the previous approaches.

Hierarchical categorization is a powerful and convenient method so that it iscommonly used in various areas. Although each hierarchy is useful, there areproblems to manage multiple hierarchies. Similarity-based integration (SBI) [2]is an eﬀective method for solving this problem. By using this method, instancesthat exist in one hierarchy system but does not in the other can be locatedin a suitable position in the other. The main idea of SBI is to utilize only thesimilarity of categorizations across concept hierarchies. Namely, SBI does notanalyze the contents of information assigned to the concept hierarchies. In thispaper, we propose an extension of SBI which uses the contents in information
instances.
In order to state our problem, we describe a model of the nature of concept
hierarchies. Many information management systems for use with conceptual information like ontologies are managed via a system of hierarchical categorization.
Such information management system is comprised of 2 elements, i.e, categories
and information instances. The problem addressed in this paper is ﬁnding an appropriate category in the target concept hierarchy for each information instancein the source concept hierarchy. The important point of this approach is that thesource concept hierarchy does not need to be adjusted to ﬁt the target concept
hierarchy. Thus, a user can apply our method while continuing to use whicheverconcept hierarchy they are accustomed to.
E. Motta et al. (Eds.): EKAW 2004, LNAI 3257, pp. 474–476, 2004.
c Springer-Verlag Berlin Heidelberg 2004
A Hybrid Algorithm for Alignment of Concept Hierarchies

475

A problem of SBI is that it is hard to learn an alignment rule when thedestination category is in a lower category in the target concept hierarchy. In
other words, the learned rules are likely to assign relatively general categories inthe target concept hierarchy. In order to avoid this type of rules, we propose tocombine a contents-based classiﬁcation method after we apply the SBI algorithm.
Since Naive Bayes (NB) [4] is very popular and easy to use, we adopt NB as
the contents-based classiﬁcation method. In order to apply the NB algorithm forhierarchical classiﬁcation, we utilize the simple method of the Pachinko Machine
NB. The Pachinko Machine classiﬁes instances at internal nodes of the tree, andgreedily selects sub-branches until it reaches a leaf [3]. This method is applied
after the rule induced by SBI decides the starting category for the Pachinko
Machine NB.
In order to evaluate this algorithm, we conducted experiments using the Yahoo! [5] and Google [1] directories as concept hierarchies, and the links (URLs) ineach directory as information instances. We conducted ten-fold cross validations
for the shared instances. The accuracy is measured for each depth of the Internet directories and is shown in Figure 1. The vertical axes show the accuracy

012

345
Depth

678

9

10

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0Yahoo!: Photography Google: Photography

SBISBI-NBNB012345 6Depth

789101
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

SBI
SBI-NBNB
Accuracy

Google: Autos

SBI
SBI-NBNB

Accuracy

10.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

Accuracy

Accuracy

Yahoo!: Automotive

012345 6Depth

789101
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0SBI
SBI-NBNB

01234

5678910Depth

Fig. 1. Experimental Results

and horizontal axes show the depth of the concept hierarchies. The experimental
domains of the graphs are integration into Yahoo!: Automotive, Google: Autos,Yahoo!: Photography, and Google: Photography, from left to right. We compared
the proposed system called SBI-NB with the SBI system and the NB system.
From the comparison of the results of both NB and SBI with SBI-NB, we can expect high accuracy when NB produces a good result. On the other hand, when
the NB method has poor accuracy, our method has at least the same performance of SBI and does not have any side eﬀect from NB. From this, we canconclude that our approach is a good method for integrating the approach ofcontents-based classiﬁcation method and the approach of the similarity-based
integration method.
In this paper, we propose a new method for aligning concept hierarchies asa new approach to utilizing information in multiple concept hierarchies. Our
experimental results show improved performance compared with the previousapproaches.

476

R. Ichise et al.

References
1. Google., http://directory.google.com/, 2003.
2. Ichise R., Takeda H. and Honiden S., Integrating Multiple Internet Directories byInstance-based Learning. In Proc. of the 18th Int. Joint Conf. on AI, 22–28, 2003.
3. McCallum A., et al., Improving text classiﬁcation by shrinkage in a hierarchy ofclasses. In Proc. of the 15th Int. Conf. on Machine Learning, 359–367, 1998.
4. Mitchell. T., Machine Learning. McGraw-Hill, 1997.
5. Yahoo!, http://www.yahoo.com/, 2003.