In this paper, we tackle the problem of clustering individual resources in the context of the Web of Data, that is characterized by a huge amount of data published in a standard data model with a well-de ned semantics based on Web ontologies. In fact, clustering methods o er an e ective solution to support a lot of complex related activities, such as ontology construction, debugging and evolution, taking into account the inherent incompleteness underlying the representation. Web ontologies already encode a hierarchical organization of the resources by means of the subsumption hierarchy of the classes, which may be expressed explicitly, with proper subsumption axioms, or it must be detected indirectly, by reasoning on the available axioms that dene the classes (classi cation). However it frequently happens that such classes are sparsely populated as the hierarchy often re ect a view of the knowledge engineer prior to the actual introduction of assertions involving the individual resources. As a result, very general classes are often loosely populated, but this may happen also to speci c subclasses, making it more di cult to check the types of a resource (instance checking ), even through reasoning services. Among the large number of algorithms proposed in the Machine Learning literature, we propose a clustering method that is able to organize groups of resources hierarchically. Specifically, in this work, we introduce a conceptual clustering approach that combines a distance measure between individuals in a knowledge base in a divide-and-conquer solution that is intended to elicit ex post the underlying hierarchy based on the actual distributions of the instances.
With the growth of the Web of Data, along with the Linked Data initiative [
Web ontologies already encode a hierarchical organization of the data by means of the subsumption hierarchy of the classes, which may be expressed explicitly, with proper subsumption axioms, or it has to be determined indirectly, by reasoning on the available axioms de ning the various classes (classi cation task). However it frequently happens that such classes are sparsely populated as the hierarchy often re ects a view of the knowledge engineer prior to the actual introduction of assertions involving the individual resources. As a result, very general classes are often loosely populated, but this may happen also to speci c subclasses, hindering or, at least, making it di cult to check the types of a resource (instance checking), even employing reasoning services. This may have a strong negative impact on services based on query answering, which often only rely on explicit assertions regarding the data.
Machine Learning methods can be employed to elicit implicit pieces of
knowledge from the datasets, also in the face of such cases of inherent incompleteness,
and provide non-standard inference services [
Clustering is an unsupervised learning task aiming at partitioning a
collection of objects into subsets or clusters, so that those within each cluster are
more closely related to one another than to the objects assigned to di erent
clusters [
An object is usually described by a xed set of feature (attribute values ) and the most common notion of similarity between the objects is expressed in terms of a distance function based on this set; for example, datasets made up of objects described by tuples of numeric features and (extensions of) the Euclidean distance are adopted to determine object and cluster similarity.
An important di erence among the various clustering techniques is related
to the type of membership that is adopted. In the simplest (crisp) case, e.g.
kMeans [
In this work, moving on to conceptual clustering, we will require that classes with an intensional de nition may account for and de ne these clusters. To this purpose the algorithms should be able to exploit a background knowledge that can be expressed using expressive representation languages1, such as Description Logics. Again, in such methods, clustering requires the de nition of (dis)similarity measure between the set of the objects to be clustered.
We propose a generalized solution based on logical trees [
The rest of the paper is organized as follows: the next section illustrates the basic notions about the underlying Description Logics foundations for the intended representation and reasoning services; Sect. 3 introduces the problem of clustering individuals of a knowledge base while Sect. 4 presents the approach required for inducing terminological cluster trees. Finally, Sect. 5 illustrates the conclusions and some possible extensions. 2
In the following, we will borrow notation and terminology from Description
Logics (DLs) [
In these languages, a domain is modeled through atomic concepts (classes) NC and roles (relations) NR, which can be used to build complex descriptions regarding individuals (instances, objects), by using speci c operators (complement, conjunction and disjunction between concepts) that depend on the adopted language. A knowledge base is a couple K = (T ; A) where the TBox T contains axioms concerning concepts and roles (typically inclusion axioms such as C v D) and the ABox A contains assertions, i.e. axioms regarding the individuals (C(a), resp. R(a; b)). The set of individuals occurring in A is denoted by Ind(A).
The semantics of individuals, concepts, and roles is de ned through interpretations. An interpretation is a couple I = ( I ; I ) where I is the domain of the interpretation and I is a mapping such that, for each individual a, aI 2 I , for each concept C, CI I and for each role R, RI I I . The semantics 1 In the past, various fragments of First-Order Logic have been adopted, such as
Clausal Logics, especially in Inductive Logic Programming. 2 Datatype properties, i.e. roles ranging on concrete domains will not be considered in this study. of complex descriptions descends from the interpretation of the primitive concepts/roles and of the operators employed, depending on the adopted language. I satis es an axiom C v D (C is subsumed by D) when CI DI and an assertion C(a) (resp. R(a; b)) when aI 2 CI (resp. (aI ; bI ) 2 RI ). I is a model for K i it satis es each axiom/assertion in K, denoted with I j= . When is satis ed w.r.t. these models, we write K j= .
We will be interested in the instance-checking inference service: given an individual a and a concept description C determine if K j= C(a). Due to the Open World Assumption (OWA), answering to a class-membership query is more di cult w.r.t. ILP settings where the closed-world reasoning is the standard form. Indeed, one may not be able to prove the truth of either K j= C(a) or K j= :C(a), as there may be possible to nd di erent interpretations that satisfy either cases. 3
As we are targeting conceptual clustering for DL Knowledge Bases, the problem, in a simple formulation, may be formalized as follows:
{ a knowledge base K = hT ; Ai { a set of training individuals TI
Ind(A) { a partition of TI in n pairwise disjoint clusters fC1; : : : ; Cng { for each i = 1; : : : ; n, a concept description Di that accounts for Ci, i.e. such that 8a 2 Ci : 1. K j= Di(a) 2. K j= :Dj (a)
8j 2 f1; : : : ; ng; j 6= i
Note that in this setting the number of clusters (n) is not required as a
parameter. Condition 2. may be relaxed (e.g. K 6j= Dj (a)) to allow some overlap
between the clusters/concepts that may be further extended towards
probabilistic clustering methods and models [
This problem can be regarded as a recursive one, as each cluster, in its turn, might yield its internal partitioning and each sibling sub-cluster would be characterized intensionally by its sub-class.
The decision on whether to partition recursively a given cluster or not generally depends on cohesion metrics, assessing a measure of intra-cluster similarity (within the cluster) and the w.r.t. the inter-cluster dissimilarity (w.r.t. the sibling partitions).
The notion of terminological cluster tree extends logical clustering trees
introduced in [
Hence, a tree-node can be represented by a quadruple hD; C; Tleft; Trighti, indicating the two subtrees connected by either edge.
Person
C4
C3 C1
C2 Example 4.1 (a TCT). Fig. 1 illustrates a simple example of a TCT for describing individuals in the academic domain. The root node of the tree contains the concept Person. Two edges depart from this node: the left branch is used to denote a positive membership of an individual w.r.t. the concept Person, while 3 By convention the left branch is for positive instances and the right one is for negative instances. the right branch denote a negative membership w.r.t. the concept. On one hand, the right child of this node is a leaf that contains a cluster C4 composed by individuals that are not instances of the concept Person. On the other hand, the left child of the root node contains a further complex concept description. Again, there are two edges departing from this node: the right edge links the node to another leaf containing the cluster C3 of individuals denoting individuals that have no publication. tu
The details of the algorithms for (a) growing a TCT and (b) deriving intensional de nitions are reported in the sequel. 4.1
A Method for Inducing Terminological Cluster Trees
A terminological cluster tree T is induced by means of a recursive strategy, which
follows the same schema proposed for terminological decision trees (TDTs) [
Algorithm 1 Routines for inducing a TCT
The main routine is to be invoked as induceTCT(TI; C), where C may be > or any other general concept the individuals in TI are known to belong to by default.
In this recursive algorithm, the base case depends on a test (via stopCondition) on a threshold over the heuristics employed for growing the tree, measuring the cohesion of the cluster of individuals routed to the node in terms of a given metric. If this value exceeds then the branch is marked as completed and the cluster is stored in a leaf node. Further details about the heuristics and the stop condition will be reported later on.
In the inductive step, the current (parent) concept description C has to be specialized by means of an re nement operator ( ) exploring the search space of specializations of C. A set S of candidate specializations (C) is obtained. For each E 2 S, the set of positive and negative individuals, denoted, resp., by P and N are retrieved.
A tricky situation may occur (line 24) when either N or P is empty for a given concept (e.g. due to a total lack of disjointness axioms). In such a case, the algorithm can re-assign individuals I to N (resp. P) based on the distance between them and the prototype of P (resp. N) when this goes beyond a given threshold .
For P and N, a representative element is determined as a prototype, i.e. their medoid, a central element in a cluster, having a minimal average distance w.r.t. the other elements. Then, function selectBestConcept evaluates the specializations of the concept according to the closeness w.r.t. the medoids, determined according to a given distance measure (discussed later). The best concept E 2 S is the one for which the distance between the medoids for positive and negative instance set is maximized. Then E is installed in the current node.
After the assessment of the best concept E , the individuals are partitioned by split to be routed along the left or right branch. Di erently from TDTs, the routine does not decide the branch where the individuals will be sorted according to a concept membership test (instance check): rather it decides to split individuals according to the distance w.r.t. the prototypes of positive and negative membership w.r.t. E , i.e. the medoids of P and N. This divide-andconquer strategy is applied recursively until the instances routed to a node satisfy the stop condition. Note that, the number of the clusters is not required as an input but it depends on the number of paths generated in the growing phase: the algorithm is able to determine it naturally following the data distribution. Re nement Operator The proposed approach relies on a downward re nement operator that can generate the concepts to be installed in child-nodes performing a specialization process on the concept, say C, installed in a parentnode: 1 by adding a concept atom (or its complement) as a conjunct: C0 = C u (:)A; 2 by adding a general existential restriction (or its complement) as a conjunct:
C0 = C u (:)(9)R:>; 3 by adding a general universal restriction (or its complement) as a conjunct:
C0 = C u (:)(8)R:>; 4 by replacing a sub-description Ci in the scope of an existential restriction in
C with one of its re nements: 9R:Ci0 2 (9R:Ci) ^ Ci0 2 (Ci); 5 by replacing a sub-description Ci in the scope of a universal restriction with one of its re nements: 8R:Ci0 2 (8R:Ci) ^ Ci0 2 (Ci).
Note that the cases of 4 and 5 are recursive.
Prototypes Despite the common schema of the algorithms employed for
growing TCTs and TDTs, the latter are obtained by selecting the best test in terms
of information gain maximization [
E = arg max d (p(P); p(N))
D2 (C)
where P and N are sub-clusters obtained from splitting I w.r.t. D, d( ; ) is a
distance measure between individuals and p( ) is a function which maps a set of
individuals to its prototype. As previously mentioned, the algorithm computes
the medoids of both the set of positive and negative instances w.r.t. the test.
Distance Measure The computation of medoids requires a (possibly)
languageindependent measure for individuals whose de nition should capture aspects of
their semantics in the context of the knowledge base. However individuals don't
have an algebraic structure that can be exploited directly. In the TCT induction
algorithm a language-independent dissimilarity measure [
Given a knowledge base K, the idea is to use the behavior of an individual w.r.t. a set of concepts C = fC1; C2; : : : ; Cmg that is dubbed context or committee of features. After C has been chosen, a projection function for each Ci 2 C can be de ned as a mapping i : Ind(A) ! f0; 12 ; 1g such that 8 a 2 Ind(A) i(a) = 8 1 if K j= Ci(a) <
0 if K j= :Ci(a)
: 12 otherwise
For the value of i associated to the uncertain membership case (owing to the
OWA) we adopted a uniform prior probability. It can be set more accurately
according to the membership to Ci, i : Ind(A) ! [0; 1], with x 2 Ind(A) 7!
i(x) = P[K j= Ci(x)], if such a value can be estimated. For example, for densely
populated ontologies this may be estimated as jrA(Ci)j=jInd(A)j, where rA()
indicates the retrieval of the argument concept w.r.t. A, i.e. the set of individuals
in that are known to belong to the concept [
Through the projection function, it is possible to de ne a family of distance
measures fdpCgp2N for individuals as follows: dpC : Ind(A) Ind(A) ! [0; 1] such
that
In previous papers, e.g. [
To speed up the algorithm, the projection functions can be pre-computed (once) before the learning phase.
Stop Condition The growth of a TCT can be stopped by resorting to a heuristic that is similar to the one employed for selecting the best concept description. This can be made by introducing a threshold 2 [0; 1], for the value of d( ; ). If the value is lower than the threshold, the branch growth is stopped. 4.2
Extracting Concepts from TCTs Alg. 2 reports the sketch of the function for deriving the concept descriptions describing the clusters obtained through a TCT. Given a TCT T , essentially Algorithm 2 Routines for deriving concept de nitions from a TCT 1 function DeriveConcepts(C; T ): set of concepts 2 input C: concept name 3 T : TCT 4 begin 5 let T = hD; I; Tleft; Trighti 6 if Tleft = Tright = null then f leaf g 7 return fCg 8 else 9 CSleft DeriveConcepts(C u D; Tleft) 10 CSright DeriveConcepts(:C u :D; Tright) 11 return (CSleft [ CSright) 12 end function deriveConcepts traverses the tree structure to collect the concept descriptions that are used as parents of the leaf-nodes. In this phase, it generates a set of concept descriptions CS.
Example 4.2. The set CS that can be obtained from the tree reported in Fig. 1 contains the following concept descriptions (corresponding to the four clusters): CS = f D1; D2; D3; D4 g = f Person u 9hasPublication:> u 9hasPublication:(SWJ); (Person u 9hasPublication:>) u :(Person u 9hasPublication:(SWJ)); Person u :(Person u 9hasPublication:>); :Person g Such concepts might be also simpli ed before being output. tu
Note that also the internal nodes contain concept descriptions that account for the individuals routed to such nodes. Hence it is straightforward to extend the extraction procedure, in order to produce a list of subsumption axioms between couples of the node concepts which might be submitted to a knowledge engineer for validation. 5
In this work, we have proposed an extension of terminological decision trees [
The algorithm essentially adopts a divide-and-conquer strategy that generates concept descriptions to be installed in the inner nodes via a re nement operator and selects the most promising ones to represent clusters of similar individuals using a suitable distance measure.
This preliminary work can be extended along various possible directions
(some extensions are already being carried out), which can be listed as follows:
{ a comparison to other clustering methods in order to understand the
feasibility of the proposed solution;
{ new distance measures between the individuals : in this work we adopted a
language-independent distance measure between the individuals of a
knowledge base. In this perspective, it may be interesting to investigate other
distance measures (e.g. less computationally expensive functions);
{ new re nement operators : we adopted a re nement operator used for solving
supervised learning problems. Further extensions of this work may consider
new re nement operators that can be borrowed from other machine learning
algorithms, e.g. DL-Learner [