Introduction

Endowing OWL ontologies with capabilities of representing and processing imprecise knowledge is a highly desirable feature since the Semantic Web is full of imprecise and uncertain information coming from perceptual data (i.e., data coming from subjective judgments), incomplete data, data with errors, etc. [16]. Moreover, even in the case that precise information is available, imprecise knowledge could be advantageous: tolerance to imprecision may lead to concrete benefits such as compact knowledge representation, and efficient and robust reasoning [20]. Additionally, humans continually acquire, manipulate and communicate imprecise knowledge: therefore any ontology capable of expressing imprecise knowledge, when a precise alternative leads to a complex representation, could be more interpretable by human users, i.e. easier to read and understand [1].

A number of mathematical tools are available to deal with imprecision and uncertainty in knowledge representation. The choice of the right tool depends on the type of imprecision. In particular, imprecision due to the lack of boundaries in concepts (such as coldness in the domain of indoor temperatures, interestingness of movies, etc.) are well modeled through fuzzy sets. In essence, fuzzy sets define collections of objects whose membership can be partial. Differently to probability measures, the degree of membership does not measure how likely an object is referred by a concept, but rather it quantifies how much the concept is applicable to the object. Fuzziness pervades human reasoning and allows it to intelligently act in complex environments: since fuzzy sets make possible a computational representation of concepts with no sharp boundaries, they enable machines to carry out human-centered information processing and reasoning [5].

The integration of fuzzy sets in ontologies for the Semantic Web can be achieved in different ways (see [19] for an updated overview). However, in most cases, fuzzy sets are defined by hand or with some heuristic procedure that does not take into account the distribution of available data. In this paper, we propose the adoption of a fuzzy clustering procedure to automatically acquire fuzzy sets from data. Also, we exploit the resulting clusters, together with fuzzy quantifiers, to develop a granular view of the individuals in an OWL ontology.

The paper is structured as follows. Section 2 presents some preliminary information on Description Logics1 (2.1), Fuzzy Set Theory (2.2), and Fuzzy DLs (2.3). Section 3 describes the proposed granulation method on OWL schemas at increasing levels of complexity. Finally, Section 4 draws some conclusive remarks along with future research directions.

Preliminaries

Description Logics

Description Logics (DLs) are a family of decidable First Order Logic (FOL) fragments that allow for the specification of structured knowledge in terms of classes (concepts), instances (individuals), and binary relations between instances (roles) [2]. Complex concepts (denoted with C) can be defined from atomic concepts (A) and roles (R) by means of the constructors available for the DL in hand. The members of the DL family differ from each other as for the set of constructors, thus for the complexity of concept expressions they can generate. For the sake of illustrative purposes, we present here a salient representative of the DL family, namely ALC [15], which is often considered to illustrate some new notions related to DLs. A DL Knowledge Base (KB) K = T , A is a pair where T is the so-called Terminological Box (TBox) and A is the so-called Assertional Box (ABox). The TBox is a finite set of General Concept Inclusion (GCI) axioms which represent is-a relations between concepts, whereas the ABox is a finite set of assertions (or facts) that represent instance-of relations between individuals (resp. couples of individuals) and concepts (resp. roles). Thus, when a DL-based ontology language is adopted, an ontology is nothing else than a TBox (i.e., the intensional level of knowledge), and a populated ontology corresponds to a whole KB (i.e., encompassing also an ABox, that is, the extensional level of knowledge).

The semantics of DLs can be defined directly with set-theoretic formalizations or through a mapping to FOL (as shown in [8]). Specifically, an interpretation I = (∆ I , • I ) for a DL KB consists of a domain ∆ I and a mapping function • I . For instance, I maps a concept C into a set of individuals C I ⊆ ∆ I , i.e. I maps C into a function C I : ∆ I → {0, 1} (either an individual belongs to the extension of C or does not belong to it). Under the Unique Names Assumption (UNA) [13], individuals are mapped to elements of ∆ I such that a I = b I if a = b. However UNA does not hold by default in DLs. An interpretation I is a model of a KB K iff it satisfies all axioms and assertions in T and A. In DLs a KB represents many different interpretations, i.e. all its models. This is coherent with the Open World Assumption (OWA) that holds in FOL semantics. A DL KB is satisfiable if it has at least one model. We also write C K D if in any

A A I ⊆ ∆ I abstract role R R I ⊆ ∆ I × ∆ I concrete role T T I ⊆ ∆ I × ∆ D individual a a I ∈ ∆ I concrete value v v I ∈ ∆ D concept intersection C D C I ∩ D I concept union C D C I ∪ D I concept negation ¬C ∆ I \ C I universal abstract role restriction ∀R.C {x ∈ ∆ I | ∀y (x, y) ∈ R I → y ∈ C I } existential abstract role restriction ∃R.C {x ∈ ∆ I | ∃y (x, y) ∈ R I ∧ y ∈ C I } universal concrete role restriction ∀T.d {x ∈ ∆ I | ∀z (x, z) ∈ T I → z ∈ d D } existential concrete role restriction ∃T.d {x ∈ ∆ I | ∃z (x, z) ∈ T I ∧ z ∈ d D } general concept inclusion C D C I ⊆ D I concept assertion a : C a I ∈ C I abstract role assertion (a, b) : R (a I , b I ) ∈ R I concrete role assertion (a, v) : T (a I , v I ) ∈ T I model I of K, C I ⊆ D I (concept C is subsumed by concept D). Moreover we write C K D if C K D and D K C.

The consistency check, which tries to prove the satisfiability of a DL KB K, is the main reasoning task in DLs. It is performed by applying decision procedures mostly based on tableau calculus. All other reasoning tasks can be reformulated as consistency checks.

In many applications, it is important to equip DLs with expressive means that allow to describe "concrete qualities" of real-world objects such as the length of a car. The standard approach is to augment DLs with a so-called concrete domain (or datatype theory) D = ∆ D , • D , which consists of a datatype domain ∆ D (e.g., the set of real numbers in double precision) and a mapping • D that assigns to each data value an element of ∆ D , and to every n-ary datatype predicate d an n-ary (typically, n = 1) relation over ∆ D [3]. In DLs extended with concrete domains, each role is therefore either abstract (denoted with R) or concrete (denoted with T ). The set of constructors for ALC(D) is reported in Table 1.

Fuzzy Set TheoryA crisp set A over a Universe of Discourse X is characterised by a function A : X → {0, 1}, that is, for any x ∈ X either x ∈ A (i.e., A(x) = 1) or x ∈ A (i.e., A(x) = 0). A fuzzy set F over X is characterised by a membership function F : X → [0, 1]. For a fuzzy set F , unlike crisp sets, x ∈ X belongs to F to a degree F (x) in [0, 1].

The trapezoidal, the triangular, the left-shoulder, and the right-shoulder functions are frequently used as membership functions of fuzzy sets (see Fig. 1 for a graphical representation). In particular, the trapezoidal function is defined as follows: let a < b ≤ c < d be rational numbers then

d c b a 0 1 x c b a 0 1 x b a 0 1 x b a 0 1 x (a) (b) (c) (d)trz(a, b, c, d)(x) =            0 if x < a (x − a)/(b − a) if x ∈ [a, b) 1 if x ∈ [b, c] (d − x)/(d − c) if x ∈ (c, d] 0 if x > d .(1)

Note that triangular, left-shoulder and right-shoulder fuzzy sets are special cases of trapezoidal fuzzy sets. 2Fuzzy sets can be used to represent information granules, i.e. collections of objects kept together due to their similarity, proximity, etc. [4]. Information granules promote abstraction as far as they can be labeled by symbolic terms. Information granules represented by fuzzy sets are good candidates to represent perceptual information, thus they could be conveniently labeled by linguistic terms coming from natural language. The granularity level (quantifiable as the area of the membership function, for fuzzy sets) assesses the specificity of an information granule: the most specific information granule is a set with a single element (precise information); on the other extreme, an information granule covering the whole universe of discourse is the least specific.

Fuzzy clustering Although fuzzy sets have a greater expressive power than crisp sets, their usefulness depends critically on the capability to construct appropriate membership functions for various given concepts in different contexts. The problem of constructing meaningful membership functions is not a trivial one (see, e.g., [10,Chapter 10]). One easy method is to define a uniform Strong Fuzzy Partition (SFP) usually with 5 ± 2 fuzzy sets. A SFP is a collection of fuzzy sets (usually with triangular or trapezoidal fuzzy sets) such that, for each element of the Universe of Discourse, the sum of memberships of all fuzzy sets is always 1. SFPs with trapezoidal fuzzy sets greatly enhance the efficiency of calculations because they guarantee that each element has non-zero membership degree for at most two fuzzy sets. A uniform SFP is based on fuzzy sets with the same granularity. It is very simple to define a uniform SFP, but this approach does not take into account the distribution of available data; in fact, coarse grained fuzzy sets are more useful to cover regions of the Universe of Discourse where data are more sparse; on the other hand, data crammed in small areas are better represented by more specific (fine grained) fuzzy sets.

The derivation of a SFP with variable granularity, adapted to available data, can be achieved through fuzzy clustering. A widespread algorithm for fuzzy clustering is Fuzzy C-Means (FCM) [6], an extension of the well-known K-Means that accommodates partial memberships of data to clusters. FCM, applied to one-dimensional, numerical data, can be used to derive a set of c clusters characterized by prototypes π 1 , π 2 , . . . , π c , with π j ∈ R and π j < π j+1 . These prototypes, along with the range of data, provide enough information to define a SFP with two trapezoidal fuzzy sets and c − 2 triangular fuzzy sets according to the following rules:

F j =    trz (m, m, π 1 , π 2 ) if j = 1 trz (π j−1 , π j , π j , π j+1 ) if 1 < j < c trz (π c−1 , π c , M, M ) if j = c. (2)

where [m, M ] is the range of data. In Fig. 2 an example of SFP, consisting of five fuzzy sets with variable granularity, is depicted. Fuzzy quantifiers Fuzzy sets, like crisp sets, can be quantified in terms of their cardinality. Several definitions of cardinality of fuzzy sets are possible [9], although in this paper we consider only relative scalar cardinalities like the relative σ-count, defined for a finite Universe of Discourse X as:

σ(F ) = x∈X F (x) |X|(3)

A relative scalar cardinality yields a value within [0, 1] (being |∅| = 0 and |X| = 1). On this interval, a number of fuzzy sets can be defined to represent granular concepts about cardinalities, such as Many (see Fig. 3 for some notable examples). These concepts are called fuzzy quantifiers. Note that the usual existential quantifier (∃) and universal quantifier (∀) can be represented as special cases of fuzzy quantifiers: Given a fuzzy quantifier Q and a fuzzy set F , the membership degree Q(σ(F )) can be intended as the degree of truth of a fuzzy proposition of the form "Qx are F " (e.g."Many x are Tall").

Q ∃ (x) = 1 iff x > 0, 0 otherwise; Q ∀ (x) = 1 iff x = 1, 0 otherwise.

Fuzzy Description Logics

In fuzzy DLs, an interpretation I = (∆ I , • I ) consists of a nonempty (crisp) set ∆ I (the domain) and of a fuzzy interpretation function • I that, e.g., maps a concept C into a function C I : ∆ I → [0, 1] and, thus, an individual belongs to the extension of C to some degree in [0, 1], i.e. C I is a fuzzy set. The definition of • I for ALC(D) with fuzzy concrete domains is reported in [18]. In particular,

•

where e.g. ≥ v corresponds to the crisp set of data values that are greater or equal than the value v.

Axioms in a fuzzy ALC(D) KB K = T , A are graded, e.g. a GCI is of the form C 1 C 2 , α (i.e. C 1 is a sub-concept of C 2 to degree at least α). We may omit the truth degree α of an axiom; in this case α = 1 is assumed. An interpretation I satisfies an axiom τ, α if (τ ) I ≥ α. I is a model of K iff I satisfies each axiom in K. We say that K entails an axiom τ, α , denoted K |= τ, α , if any model of K satisfies τ, α . Further details of the reasoning procedures for fuzzy DLs can be found in [17].

Fuzzy quantifiers have been also studied in fuzzy DLs. In particular, Sanchez and Tettamanzi [14] define an extension of fuzzy ALC(D) involving fuzzy quantifiers of the absolute and relative kind, and using qualifiers. They also provide algorithms for performing two important reasoning tasks with their DL: Reasoning about instances, and calculating the fuzzy satisfiability of a fuzzy concept.

In this Section we show our proposal of introducing a granular view within an ontology. We shall proceed incrementally starting from the simplest case. For the sake of simplicity, we shall use the OWL terminology henceforth instead of the DL terminology (We remind the reader that class stands for concept, and property stands for role).

Case 1

Let C be a class and T a functional datatype property connecting instances of C to values in a numerical range d. See Fig. 4 for a graphical representation of this costruct. This schema can be directly translated into a table (see Table 2) with two columns and as many rows as the number of individuals of C for which T holds.

Table 2. Tabular representation of the OWL schema depicted in Fig. 4.

C T a1 v1 a2 v2 • • • • • • an vn

The dataset in Table 2 can be easily granulated in a number of fuzzy sets F 1 , F 2 , . . . , F c by applying, e.g., the fuzzy clustering method mentioned in Section 2.2. In essence, the granulation process puts individuals in the same information granule if their respective values are similar. The use of fuzzy sets to define granules ensures a gradual membership degree of individuals to such granules, where the maximal membership is assigned to individuals detected as "prototypes" of each granule. Each fuzzy set represents a fuzzy concept, and can be tagged by a linguistic term, e.g. Low.

Table 3. Granulated individuals obtained from Table 2.

C F1 F2 • • • Fc a1 µ11 µ12 • • • µ1c a2 µ21 µ22 • • • µ2c • • • • • • • • • • • • • • • an µn1 µn2 • • • µnc

The result of granulation can be represented in a new table (see Table 3), where each individual a i is associated to a row of membership values µ ij , being

µ ij = F j (v i )(5)

For each granule F j , the relative cardinality σ(F j ) can be computed by means of the formula in Eq. ( 3). Given a fuzzy quantifier Q k , the membership degree

q jk = Q k (σ(F j ))(6)

identifies the degree of truth of the fuzzy proposition "Q k x are F j ". In this way, a new table can be constructed from a collection Q 1 , Q 2 , . . . , Q m of fuzzy quantifiers, as shown in Table 4. If cm n, a sensible reduction of data can be achieved to represent the original property through a granulated view. (To further reduce data, a threshold τ can be set, so that all q jk less than τ are set to zero.) Table 4. Quantified cardinalities for the granules reported in Table 3.

Q1 Q2 • • • Qm F1 q11 q12 • • • q1m F2 q21 q22 • • • q2m • • • • • • • • • • • • • • • Fc qc1 qc2 • • • qcm

The new granulated view can be integrated in the ontology as follows. The fuzzy sets F j are the starting point for the definition of new subclasses of C defined as D j ≡ C ∃T.F j . Also, a new class Granule is defined, with individuals g 1 , g 2 , . . . , g c , where each individual g j is an information granule corresponding to F j . Each individual in D j is then mapped to g j by means of an object property mapsTo. Also, the cardinality of information granules is modeled by means of a datatype property hasCardinality with domain in Granule and range in the datatype domain xsd:double. Moreover, for each fuzzy quantifier Q k , a new class is introduced, which models one of the fuzzy sets over the cardinalities of information granules. The connection between the class Granule and each class Q k is established through hasCardinality, once fuzzified, with degrees identified as in Table 4. Note that the fuzzy proposition "Q k x are F j " is then represented as the fuzzy assertion g j : ∃hasCardinality.Q k .

Example 1. In the tourism domain, we might consider an OWL ontology which encompasses the datatype property hasPrice with the class Hotel as domain and range in the datatype domain xsd:double. Let us suppose that the room price for Hotel Verdi (instance verdi of Hotel) is 105, i.e. the KB contains the assertion (verdi, 105):hasPrice. By applying fuzzy clustering to hasPrice, we might obtain three fuzzy sets (Low, Medium, High) from which the following classes are derived LowPriceHotel ≡ Hotel ∃hasPrice.Low MidPriceHotel ≡ Hotel ∃hasPrice.Medium HighPriceHotel ≡ Hotel ∃hasPrice.High.

With respect to these classes verdi shows different degrees of membership, e.g. verdi is a low-price hotel at degree 0.8 and a mid-price hotel at degree 0.2 (see Fig. 5 for a graphical representation). Subsequently, we might be interested in obtaining aggregated information about hotels. Here the class Granule comes into play. Quantified cardinalities allow us, for instance, to represent the fact that "Many hotels are low-price" as the fuzzy assertion lph : ∃hasCardinality.Many with truth degree 0.7, where lph is an instance of Granule (i.e., it is an information granule) which corresponds to LowPriceHotel, and Many is one of the fuzzy sets obtained from hasCardinality. Note that verdi, being an instance of LowPriceHotel, maps to lph, i.e. (verdi, lph) : mapsTo holds to some degree.

Case 2

A natural extension of the proposed granulation method follows when the class C is specialized in subclasses, as in Fig. 6. In this case, there are as many tables with the same structure of Table 2 as the number of subclasses.

Analogously, for each subclass SubC j a structure of fuzzy information granules F j1 , F j2 , . . . , F jc is produced and quantified according to the usual fuzzy quantifiers Q 1 , Q 2 , . . . , Q m . (The quantifiers do not depend on the subclass as their definition is fixed for all information granules.) Example 2. Following Example 1, one may think of having a subsumption hierarchy with the class Accommodation as the root and Hotel and B&B as subclasses (see Fig. 7). Hotels are granulated in three fuzzy subclasses (LowPriceHotel, MidPriceHotel and HighPriceHotel) while B&Bs are granulated in two fuzzy subclasses (CheapB&B and ExpensiveB&B). These fuzzy classes are related to the classes representing fuzzy quantifiers via Granule analogously to Example 1.

Case 3

A case of particular interest is given by OWL schemas representing ternary relations. A ternary relation is a subset of the Cartesian product involving three domains C × D × N (for our purposes, we will assume N a numerical domain). Because of DL restrictions, however, ternary relations are not directly representable in OWL, yet they can be indirectly represented through an auxiliary class E, two object properties R 1 and R 2 , and one datatype property T , as depicted in Fig. 8.

The structure in Fig. 8 corresponds to a tabular representation with three columns, and as many rows as the number of elements of the relation, as in table 5. By removing one of the two columns in Table 5, the resulting table is in accordance with Table 2, which was the starting point of the granulation process. In particular, as in the previous cases, a number of fuzzy sets F 1 , F 2 , . . . , F c can be derived starting from the dataset represented in Table 5, where one column has been dropped. (We henceforth assume to drop column C.)

In order to connect information granules with classes, we proceed as follows. Given an individual a ∈ C, a subset of Table 5 can be obtained, as in Table 6. Table 5. Tabular representation of the OWL schema depicted in Fig. 8.

C D T a1 b1 v1 • • • • • • • • • ai bj v k • • • • • • • • • an bm v l

More precisely, for each information granule F j , it is possible to compute the relative cardinality

σ ja = na i=1 F j (v ai ) n a(7)

Such cardinality can be quantified according to the fuzzy quantifiers Q 1 , . . . , Q m . The result is a table similar to Table 4, but now related to the individual a.

• • • • • • • • • a ba na va na

Information granules, connected with the individuals in C, are arranged in the ontology in a way that merges the modeling of ternary relations as in Fig. 8 with the granular model illustrated in case 1. The new classes, representing information granules, are defined as E j ≡ E ∃R 2 .D ∃T.F j . They are connected to E in order to express a granular view of the relation between C and D. Finally, a natural extension of this case allows the specialization of the class D in subclasses (as in case 2). Example 3. With reference to the touristic domain, we might also consider the distances between hotels and attractions (see Fig. 9). This is clearly a case of ternary relation which requires to be modeled through an auxiliary class Distance which is connected to the classes Hotel and Attraction by means of the object properties hasDistance and isDistanceFor, respectively, and plays the role of domain for a datatype property hasValue with range xsd:double. The knowledge that "Hotel Verdi has a distance of 100 meters from the British Museum" can be therefore modeled as follows:

(verdi, d1) : hasDistance (d1, british museum) : isDistanceFor (d1, 100) : hasValue After fuzzy granulation, the imprecise sentence "Hotel Verdi has a low distance from many attractions" can be considered as a consequence of the previous and the following axioms and assertions LowDistance ≡ Distance ∃isDistanceFor.Attraction ∃hasValue.Low d1 : LowDistance (to some degree) (d1, ld) : mapsTo (ld, 0.5) : hasCardinality ld : ∃hasCardinality.Many (to some degree) where Many is defined as mentioned in Example 1.

Conclusions

This paper presents a starting point for introducing a granular view of data within an OWL ontology. According to the ideas presented in the paper, a number of individuals belonging to the ontology can be replaced by information granules, represented as fuzzy sets. In particular, the connection between the existing individuals (not involved in granulation) and the granulated view is possible by exploiting the peculiar representation of ternary relations in OWL.

This work is in a preliminary stage. We are currently evaluating the possibility of representing the output of our fuzzy granulation method by using OWL 2, i.e. within the current Semantic Web languages as suggested by Bobillo and Straccia in their proposal of Fuzzy OWL 2 [7]. In a certain sense, we are pursuing an alternative direction in comparison with the work of Sanchez and Tettamanzi [14] which, if implemented, could lead to the extension of current Semantic Web languages. However, it should be noted that there are some non-negligible restrictions to make their approach work in current fuzzy DLs. Notably, the approach considers a finite number of individuals, which causes a mismatch with the usual semantics for DLs (i.e., OWA with infinite interpretations).

Future research is aimed at integrating our fuzzy granulation approach within inductive learning algorithms, such as Foil-DL [11], with the aim of verifying the benefits of information granulation in terms of efficiency and effectiveness of the learning process, as well as in terms of interpretability of the learning results.