Towards Fuzzy Granulation in OWL Ontologies

Abstract

The integration of fuzzy sets in ontologies for the Semantic Web can be achieved in di erent ways. In most cases, fuzzy sets are de ned by hand or with some heuristic procedure that does not take into account the distribution of available data. In this paper, we describe a method for introducing a granular view of data within an OWL ontology.

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 benets such as compact knowledge representation, and e cient 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 de ne collections of objects whose membership can be partial. Di erently to probability measures, the degree of membership does not measure how likely an object is referred by a concept, but rather it quanti es 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 di erent ways (see [ 19 ] for an updated overview). However, in most cases, fuzzy sets are de ned 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 quanti ers, 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. 2 2.1

Preliminaries

Description Logics

Description Logics (DLs) are a family of decidable First Order Logic (FOL) fragments that allow for the speci cation of structured knowledge in terms of classes (concepts), instances (individuals ), and binary relations between instances (roles) [ 2 ]. Complex concepts (denoted with C) can be de ned from atomic concepts (A) and roles (R) by means of the constructors available for the DL in hand. The members of the DL family di er 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 = hT ; Ai 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 nite set of General Concept Inclusion (GCI) axioms which represent is-a relations between concepts, whereas the ABox is a nite 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 de ned directly with set-theoretic formalizations or through a mapping to FOL (as shown in [ 8 ]). Speci cally, 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 CI I , i.e. I maps C into a function CI : I ! f0; 1g (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 aI 6= bI if a 6= b. However UNA does not hold by default in DLs. An interpretation I is a model of a KB K i it satis es all axioms and assertions in T and A. In DLs a KB represents many di erent interpretations, i.e. all its models. This is coherent with the Open World Assumption (OWA) that holds in FOL semantics. A DL KB is satis able if it has at least one model. We also write C vK D if in any 1 We recap that DLs are the logical foundation of the standard for web ontology languages belonging to the OWL 2 family [ 12 ]. model I of K, CI DI (concept C is subsumed by concept D). Moreover we write C @K D if C vK D and D 6vK C. The consistency check, which tries to prove the satis ability 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 = h D; Di, 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. A crisp set A over a Universe of Discourse X is characterised by a function A : X ! f0; 1g, that is, for any x 2 X either x 2 A (i.e., A(x) = 1) or x 62 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 2 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 de ned Note that triangular, left-shoulder and right-shoulder fuzzy sets are special cases of trapezoidal fuzzy sets.2

Fuzzy 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 (quanti able as the area of the membership function, for fuzzy sets) assesses the speci city of an information granule: the most speci c 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 speci c.

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 di erent contexts. The problem of constructing meaningful membership functions is not a trivial one (see, e.g., [10, Chapter 10]). One easy method is to de ne 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 e ciency 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 de ne a uniform SFP, but this approach does not take into account the distribution of available data; in fact, coarse 2 By convention, whenever the denominator of one of the fractions in (1) is 0, the membership degree is 1. 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 speci c ( ne 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 2 R and j < j+1. These prototypes, along with the range of data, provide enough information to de ne a SFP with two trapezoidal fuzzy sets and c 2 triangular fuzzy sets according to the following rules:

Fj = 8 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 ve fuzzy sets with variable granularity, is depicted. Fuzzy quanti ers Fuzzy sets, like crisp sets, can be quanti ed in terms of their cardinality. Several de nitions of cardinality of fuzzy sets are possible [ 9 ], although in this paper we consider only relative scalar cardinalities like the relative -count, de ned for a nite Universe of Discourse X as: (F ) =

Px2X F (x) jXj (3) A relative scalar cardinality yields a value within [0; 1] (being j;j = 0 and jXj = 1). On this interval, a number of fuzzy sets can be de ned to represent granular concepts about cardinalities, such as Many (see Fig. 3 for some notable examples). These concepts are called fuzzy quanti ers. Note that the usual existential quanti er (9) and universal quanti er (8) can be represented as special cases of fuzzy quanti ers: Q9(x) = 1 i x > 0, 0 otherwise; Q8(x) = 1 i x = 1, 0 otherwise.

Given a fuzzy quanti er 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"). 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 CI : I ! [0; 1] and, thus, an individual belongs to the extension of C to some degree in [0; 1], i.e. CI is a fuzzy set. The de nition of I for ALC(D) with fuzzy concrete domains is reported in [ 18 ]. In particular,

D maps each concrete role into a function from D to [0; 1]. Typical examples of datatype predicates are

d := ls(a; b) j rs(a; b) j tri(a; b; c) j trz(a; b; c; d) j v j v j =v ; (4) 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 = hT ; Ai are graded, e.g. a GCI is of the form hC1 v C2; i (i.e. C1 is a sub-concept of C2 to degree at least ). We may omit the truth degree of an axiom; in this case = 1 is assumed. An interpretation I satis es an axiom h ; i if ( )I . I is a model of K i I satis es each axiom in K. We say that K entails an axiom h ; i, denoted K j= h ; i, if any model of K satis es h ; i. Further details of the reasoning procedures for fuzzy DLs can be found in [ 17 ].

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

Fuzzy Granulation of OWL Schemas

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). 3.1

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.

The dataset in Table 2 can be easily granulated in a number of fuzzy sets F1; F2; : : : ; Fc 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 de ne 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.

The result of granulation can be represented in a new table (see Table 3), where each individual ai is associated to a row of membership values ij , being For each granule Fj , the relative cardinality (Fj ) can be computed by means of the formula in Eq. (3). Given a fuzzy quanti er Qk, the membership degree identi es the degree of truth of the fuzzy proposition \Qkx are Fj ". In this way, a new table can be constructed from a collection Q1; Q2; : : : ; Qm of fuzzy quanti ers, 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 qjk less than are set to zero.)

The new granulated view can be integrated in the ontology as follows. The fuzzy sets Fj are the starting point for the de nition of new subclasses of C de ned as Dj C u9T:Fj . Also, a new class Granule is de ned, with individuals g1; g2; : : : ; gc, where each individual gj is an information granule corresponding to Fj . Each individual in Dj is then mapped to gj 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 quanti er Qk, 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 Qk is established through hasCardinality, once fuzzi ed, with degrees identi ed as in Table 4. Note that the fuzzy proposition \Qkx are Fj " is then represented as the fuzzy assertion gj : 9hasCardinality:Qk.

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 MidPriceHotel HighPriceHotel

Hotel u 9hasPrice.Low Hotel u 9hasPrice.Medium

Hotel u 9hasPrice.High.

With respect to these classes verdi shows di erent 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. Quanti ed cardinalities allow us, for instance, to represent the fact that \Many hotels are low-price" as the fuzzy assertion lph : 9hasCardinality: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. 3.2

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 SubCj a structure of fuzzy information granules Fj1; Fj2; : : : ; Fjc is produced and quanti ed according to the usual fuzzy quanti ers Q1; Q2; : : : ; Qm. (The quanti ers do not depend on the subclass as their de nition is xed 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 quanti ers via Granule analogously to Example 1. 3.3

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 R1 and R2, 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 F1; F2; : : : ; Fc 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 2 C, a subset of Table 5 can be obtained, as in Table 6. More precisely, for each information granule Fj , it is possible to compute the relative cardinality (7) Such cardinality can be quanti ed according to the fuzzy quanti ers Q1; : : : ; Qm. The result is a table similar to Table 4, but now related to the individual a.

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 de ned as Ej0 E u9R2:Du9T:Fj . 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 u 9isDistanceFor.Attraction u 9hasValue.Low d1 : LowDistance (to some degree) (d1; ld) : mapsTo (ld; 0.5) : hasCardinality ld : 9hasCardinality:Many (to some degree) where Many is de ned as mentioned in Example 1. 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 nite number of individuals, which causes a mismatch with the usual semantics for DLs (i.e., OWA with in nite 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 bene ts of information granulation in terms of e ciency and e ectiveness of the learning process, as well as in terms of interpretability of the learning results. Acknowledgements This work was partially funded by the Universita degli Studi di Bari \Aldo Moro" under the IDEA Giovani Ricercatori 2011 grant \Dealing with Vague Knowledge in Ontology Re nement".

References

1. Alonso , J.M. , Castiello , C. , Mencar , C. : Interpretability of Fuzzy Systems: Current Research Trends and Prospects . In: Kacprzyk, J. , Pedrycz , W. (eds.) Springer Handbook of Computational Intelligence. Springer Berlin / Heidelberg ( 2015 )

2. Baader , F. , Calvanese , D. , McGuinness , D. , Nardi , D. , Patel-Schneider , P . (eds.): The Description Logic Handbook: Theory, Implementation and Applications (2nd ed .). Cambridge University Press ( 2007 )

3. Baader , F. , Hanschke , P.: A scheme for integrating concrete domains into concept languages . In: Mylopoulos, J. , Reiter , R . (eds.) Proceedings of the 12th International Joint Conference on Arti cial Intelligence . Sydney, Australia, August 24-30 , 1991 . pp. 452 { 457 . Morgan Kaufmann ( 1991 )

4. Bargiela , A. , Pedrycz , W. : Granular computing: an introduction . Springer Science & Business Media ( 2003 )

5. Bargiela , A. , Pedrycz , W. : Human-centric information processing through granular modelling , vol. 182 . Springer Science & Business Media ( 2009 )

6. Bezdek , J.C. : Fuzzy clustering . In: Ruspini, E.H. , Bonissone , P.P. , Pedrycz , W. (eds.) Handbook of Fuzzy Computation, p. 2 . Institute of Physics Pub. ( 1998 )

7. Bobillo , F. , Straccia , U. : Representing fuzzy ontologies in OWL 2 . In: FUZZ-IEEE 2010 , IEEE International Conference on Fuzzy Systems, Barcelona, Spain, 18 - 23 July , 2010 , Proceedings. pp. 1 { 6 . IEEE ( 2010 )

8. Borgida , A. : On the relative expressiveness of description logics and predicate logics . Arti cial Intelligence 82 ( 1 {2), 353 { 367 ( 1996 )

9. Dubois , D. , Prade , H.: Fuzzy cardinality and the modeling of imprecise quanti - cation . Fuzzy sets and Systems 16 ( 3 ), 199 { 230 ( 1985 )

10. Klir , G.J. , Yuan , B. : Fuzzy sets and fuzzy logic: theory and applications . PrenticeHall, Inc. ( 1995 )

11. Lisi , F.A. , Straccia , U. : Dealing with incompleteness and vagueness in inductive logic programming . In: Cantone, D. , Nicolosi Asmundo , M. (eds.) Proceedings of the 28th Italian Conference on Computational Logic , Catania, Italy, September 25-27 , 2013 . CEUR Workshop Proceedings , vol. 1068 , pp. 179 { 193 . CEUR-WS.org ( 2013 ), http://ceur-ws. org/ Vol- 1068 /paper-l12.pdf

12. OWL 2 Web Ontology Language Document Overview : http://www.w3.org/TR/ 2009/REC-owl2 - overview-20091027/. W3C ( 2009 )

13. Reiter , R.: Equality and domain closure in rst order databases . Journal of ACM 27 , 235 { 249 ( 1980 )

14. Sanchez , D. , Tettamanzi , A.G. : Fuzzy quanti cation in fuzzy description logics . In: Sanchez, E. (ed.) Fuzzy Logic and the Semantic Web , Capturing Intelligence , vol. 1 , pp. 135 { 159 . Elsevier ( 2006 )

15. Schmidt-Schauss , M. , Smolka , G.: Attributive concept descriptions with complements . Arti cial Intelligence 48 ( 1 ), 1 { 26 ( 1991 )

16. Stoilos , G. , Simou , N. , Stamou , G. , Kollias , S. : Uncertainty and the Semantic Web . IEEE Intelligent Systems 21 ( 2006 )

17. Straccia , U. : Reasoning within fuzzy description logics . Journal of Arti cial Intelligence Research 14 , 137 { 166 ( 2001 )

18. Straccia , U. : Description logics with fuzzy concrete domains . In: UAI '05, Proceedings of the 21st Conference in Uncertainty in Arti cial Intelligence , Edinburgh, Scotland, July 26-29 , 2005 . pp. 559 { 567 . AUAI Press ( 2005 )

19. Straccia , U. : Foundations of Fuzzy Logic and Semantic Web Languages . CRC Studies in Informatics Series , Chapman & Hall ( 2013 )

20. Zadeh , L.A. : Is there a need for fuzzy logic? Information sciences 178(13) , 2751 { 2779 ( 2008 )