The goal of inductive learning classi cation is to form generalizations from a set of training examples such that the classi cation accuracy on previously unobserved examples is maximized. Given a speci c learning algorithm, it is obvious that its classi cation accuracy depends on the quality of training data. In learning from examples, noise is anything which obscures correlations between attributes and the class [1]. There are many possible solutions to deal with the existence of noise. Data cleaning or detection and elimination of noisy examples constitutes the rst approach. Due to the risk of data cleaning, when noisy examples are retained while good examples are removed, e orts have been taken to construct noise tolerant classi ers. Although both these approaches seem very di erent, they try to somehow 'clean' this noisy training data. In this paper, we propose an approach to 'admit and utilize' noisy data by enabling to model di erent levels of knowledge granularity both in training and testing examples. The proposed knowledge representation use hierarchies of sets of attribute values, derived from subsumption hierarchies of concepts from an ontology represented in description logic. The main contributions of the paper are: (i) we propose a novel extension of the nave Bayesian classi er by hierarchical, ontology based attributes (ontological attributes ), (ii) we propose an inference scheme that handles ontological attributes.
There are three major sources of noise: (i) insu ciency of the description for
attributes or the class (or both), (ii) corruption of attribute values in the
training examples, (iii) erroneous classi cation of training examples [
In order to model di erent levels of knowledge granularity, each testing and
training example would be described by a set of values for any attribute. These
sets of values should re ect the domain knowledge and could not be constructed
arbitrarily. Let us notice, that in some domains, hierarchical or taxonomical
relationships between sets of values, represented by so called concepts, may be
observed and this knowledge could be explored. Such knowledge is currently
often available in the form of ontologies. The most widely used language to
represent ontologies, suitable in particular to model taxonomical knowledge, is
Web Ontology Language (OWL) 1. The theoretical counterpart of OWL, from
which its semantics is drawn, is constituted by a family of languages called
description logics (DLs) [
Given is an attribute A and the set V = fV1; V2; :::; Vng, where n > 1, of nominal values of this attribute. Let us assume that given is a TBox, which speci es domain knowledge relevant to a given classi cation task. In particular, it expresses a multilevel subsumption ("is-a") hierarchy of concepts. Each concept is described by a subset of the set V for every attribute A. Then we can formulate a de nition of an ontological attribute as follows.
Ontological attribute An ontological attribute A is de ned by a tuple hH; V i, where: { by H is denoted a multilevel subsumption hierarchy of concepts, derived from a DL knowledge base. This hierarchy of concepts consists of the set of nodes N H = froot; N C ; N T g. This hierarchy de nes a root-node, denoted by root, a set N C of complex-nodes and a set N T of terminal-nodes. 1 www.w3.org/TR/owl-features/ { by V is denoted a nite set V = fV1; V2; :::; Vng, where n > 1 of nominal values of A. { each node Nk 2 N T [ N C represents a subset of the set V , denoted as val(Nk); the root-node represents the set V
To model actual training examples, an ABox would be used. 3.1
Using Ontological Attributes in the Nave Bayesian Classi er In order to apply the proposed ontological attributes in the nave Bayesian classi er, we further specify the general de nition of an ontological attribute given in the former section. Please note, that by making the assumptions presented in the following paragraphs, we will implicitly switch from the usual open world assumption used to reason with a DL knowledge base to produce a concept hierarchy, to the closed world assumption, more appropriate to the case of inference with nave Bayesian classi er. In particular we will assume that a hierarchy of concepts would represent such hierarchical partitioning of the set V of attribute values, such that each concept would correspond to a non-empty subset of V . Properties of nodes Each complex-node represents a concept from the KB, described by a proper, non-empty subset of V . Each terminal-node represents a concept from the KB, described by a unique value Vi from the set V . Relations between nodes For a given ontological attribute A, the hierarchy H is a tree, i.e. each node Nk 2 fN C [ N T g has exactly one parent, denoted as pa(Nk), such that val(Nk) val(pa(Nk)). Moreover, each node Nk 2 froot [ N C g speci es a set ch(Nk) of his children. To model di erent levels of knowledge granularity, we assume that for each Nk 2 froot [ N C g all his children are pairwise disjoint and this node Nk is a union of his children. Finally, for each node Nk 2 froot [ N C g we de ne a set de(Nk) of descendants of this node, as a set of its children or children of his descendants.
The role of complex-nodes In the setting of learning with description-noise, each training and testing example can be described in general by a set Zl of values for each attribute A, where Zl V . We can divide training examples into no-noisy examples (jZlj = 1) and noisy examples (jZlj > 1). In order to represent noisy (training and testing) examples, the ontological attribute A uses complex-nodes. We will call such a hierarchy a complex-hierarchy.
Algorithm 1 (Populating a complex-hierarchy). For each ontological attribute A we proceed as follows: We associate each training example t described by a set Zl of values of A and a class label Cj (t : A = Zl ^ C = Cj ) to a node Nk. When jZlj = 1, Zl is associated to a terminal-node Nk, such that Zl = val(Nk). Otherwise, we associate the training example to a complex-node Nk, such that Zl val(Nk), at the lowest possible level of the complex-hierarchy.
Root : V N1 : fV1g
N2 : fV2g
N6 : Z1 = fV3; V4; V5g N3 : fV3g
N7 : Z2 = fV4; V5g N4 : fV4g
N5 : fV5g Example Given is an attribute A such that V =fV1,V2,V3,V4,V5g and given is a class variable C such that it takes values from the set fC1; C2g. Let us assume, that the description-noise is modeled by sets Z1 = fV3; V4; V5g and Z2 = fV4; V5g. Let us assume a sample scenario in which the single values of the attribute A are determined by conducting three medical tests. The rst test is able to partition the set V into the following disjoint subsets: fV1g, fV2g and Z1 = fV3; V4; V5g. If the result of the rst test is Z1, then in some cases it is conducted a second test, that partitions the set Z1 into the following disjoint subsets: fV3g and Z2 = fV4; V5g. Only in critical cases it is conducted the last test, that can partition the set Z2 into disjoint subsets: fV4g and fV5g. Following this domain-knowledge, we have introduced two complex-nodes N6 and N7, such that they represent the sets Z1 and Z2 respectively. Terminal-nodes N1; N2; N3; N4; N5 represent single values from the set V . The root-node represents the set V . The resulting complex-hierarchy is presented in Figure 1. We can approximate the required probability distribution for a noisy testing example described by a set Zl = val(Nk), following principles of the probabilistic theory, by collecting frequencies of training examples T , described by sets Zm Zl, as follows:
P (ZljCj ) = PZm Zl jT : A = Zm ^ C = Cj j (1)
jT : C = Cj j
Let us remind, that a set Zl is assigned to the node Nk, such that Zl = val(Nk). The key property of an ontological attribute A, is that for the node Nk all its children are pairwise disjoint. Since then, all training examples described by sets Zm Zl, are represented by the node Nk or its descendants, and the probability distribution for a noisy testing example described by a set Zl we can de ne as follows: P (ZljCj ) = jT : A val(Nk) ^ C = Cj j + PNd2de(Nk) jT : A jT : C = Cj j val(Nd) ^ C = Cj j(2)
In this way we are able to classify a new noisy example using other less noisy and no-noisy training examples. For example, we can classify a testing example, described by the set Z1, and associated to the node N6 using all training examples described by all subsets of the set Z1. These training examples would be associated to the complex-node N6 or his descendants. 4
The topic of learning with ontologies is relatively new, and so far there are few
approaches in this line of research, for the classi cation task see for example [
In the future, we will concentrate on the problem of the optimality of the complex-hierarchy, derived from a knowledge domain of the form of subsumption hierarchies of concepts.