Predicting Knowledge in an Ontology Stream

1 Introduction

The semantic web [Berners-Lee et al., 2001] is considered to be the future of the current web. The semantics of information is represented using rich description languages e.g., OWL the Web Ontology Language, which is underpinned by Description Logics (DL) [Baader et al., 2003] to define web ontologies. Their dynamic extension i.e., ontology stream [Ren and Pan, 2011], is used for representing knowledge evolution [Huang and Stuckenschmidt, 2005]. Enriched with inference models e.g., stream-based (i) querying [Calbimonte et al., 2010] for real-time filtering, (ii) reasoning [Valle et al., 2009] for interpreting evolution or (iii) diagnosing [L´ecu´e, 2012] for explaining anomalies, ontology stream is envisioned to span many real world applications. From semantics-empowered sensors [Sheth, 2010], to social semantic web [Auer et al., 2006], all are examples of applications where multiple, large and expressive ontology streams have an important role.

Predictive inference, as a reasoning technique for estimating future (or missing) observations in a stream given some historical information, has been largely studied in Statistics, Jeff Z. Pan University of Aberdeen, UK

∗The research leading to these results has received funding from the European Unions Seventh Framework Programme (FP7/20072013) under grant agreement IDs 318201 (SIMPLI-CITY) and 286348 (K-Drive).

Database and Artificial Intelligence [H¨ardle, 1992] but not in the context of semantics-enhanced data as envisioned in an ontology stream. For instance, prediction in (raw) data stream mining applications is estimated by correlating current and past data patterns using different distance metrics [Gehrke et al., 2001] between (syntactic) numeric/symbolic values. Even if [Papadimitriou et al., 2005] augmented such models with cross-correlation over streams, they all fail in using and interpreting the underlying semantics of data, making prediction not necessarily consistent and accurate, specially if streams are characterized by many major changes over time (concept drift). From a different perspective, [Bloehdorn and Sure, 2007] combine machine learning and semantic web for predicting class-membership of data by mining its instances in ontologies. This approach cannot be applied since data to be "class"-ed is not known beforehand in an ontology stream.

Facing these limitations, we address the problem of predicting knowledge in an ontology stream. Given some continuous knowledge, how do we capture time-evolving trends and patterns in the stream to make accurate predictions? Our approach determines consistent patterns by inferring and mining rules across exogenous streams, where their DL-based semantic representations are captured and interpreted through some static background knowledge. Predictive reasoning is addressed by analyzing stream evolution through correlation of its changes and their inconsistencies. Predictions, modeled as DL entailments, are derived consistent by selecting and applying relevant cross-streams association rules. The significance of rules is evaluated with respect to their (i) context of applicability, (ii) support, (iii) confidence over time, and (iv) DL consistency of their prediction. The experiments have shown accurate prediction with real, live, stream (semantics augmented) data from Dublin City in Ireland.

The remainder of this paper is as follows. Section 2 briefly reviews the logic we adopt together with ontology stream. In Section 3 we study knowledge correlation over time and rules mining in streams. Section 4 presents our consistent knowledge prediction approach. Section 5 reports experiment results on scalability and accuracy. Section 6 briefly comments on related work. Finally, Section 7 draws some conclusions.

2 Background

Both static background knowledge and semantics of stream data are represented using an ontology. Dynamic knowledge is then captured by reasoning on stream data descriptions in this ontology. We focus on DL as a formal knowledge representation language to define ontologies since this logic offers good reasoning support for most of its expressive families and compatibility to W3C standards e.g., OWL 2. We review (i) DL basics of EL++, (ii) ontology stream and its behavior.

2.1 EL++ Description Logics

We illustrate our work with DL EL++ [Baader et al., 2005] where satisfiability and subsumption are decidable. The selection of this DL fragment, which is the logic underpinning OWL 2 EL and the basis of many more expressive DL, has been guided by (i) the expressivity which was required to model semantics of data in our transportation domain (Section 5), and (ii) the scalability of the underlying basic reasoning mechanisms required in our stream context.

A signature Σ, noted (CN , RN , IN ) consists of 3 disjoint sets of (i) atomic concepts CN, (ii) atomic roles RN, and (iii) individuals IN. Given a signature, the top concept ⊤, the bottom concept ⊥, an atomic concept A, an individual a, an atomic role r, EL++ concept expressions C and D can be composed with constructs:

We slightly abuse the notion of atomic concepts to include ⊤, ⊥ and nominals [Horrocks and Sattler, 2001] i.e., individuals appearing in concept definitions of form {a}.

The DL ontology O .=< T ,A > is composed of a TBox T and ABox A. A TBox is a set of concept and role axioms.

Example 1. (TBox Fragment)

Figure 1 presents a TBox where e.g., CongestedRoad (2) denotes the concept of "road with at least a bus in a heavy traffic". The busStatus role (4) informs about the dynamics of buses e.g., stopped, or inMove.

∃from.Area ⊓ to.Area ⊓ ∃travel.Bus ⊑ Road ⊓ ∃with.Bus (1) Road ⊓ ∃with.(Bus ⊓ ∃congested.Heavy) ⊑ CongestedRoad (2) Road ⊓ ∃with.(Bus ⊓ ∃congested.Light) ⊑ FreeRoad (3) busStatus ◦ stopped ⊑ congested %Roles composition (4) Road ⊓ ∃travelTime.Normal ⊑ Road ⊓ ∃with.OnTimeBus (5) CongestedRoad ⊓ FreeRoad ⊑ ⊥ % Incompatibility (6) {r1} ⊑ Road (7) {r2} ⊑ Road (8) {r3} ⊑ Road (9)

EL++ supports General Concept Inclusion axioms (GCIs, e.g. C ⊑ D with C is subsumee and D subsumer) and role inclusion axioms (RIs, e.g., r ⊑ s, r1 ◦ · · · ◦ rn ⊑ s). An ABox is a set of concept assertion axioms e.g., a : C, role assertion axioms e.g., (a; b) : R, and individual in/equality axioms e.g., a ̸= b or a = b.

Table 1 sketches completion rules [Baader et al., 2005] that are used to classify EL++ TBox T and entail subsumption for any concept in CNT . Reasoning with such rules is PTimeComplete [Baader et al., 2008a]. We internalize ABox into TBox axioms (along ⇝) so (i) rules in Table 1 can be applied on both axioms, (ii) TBox reasoning (e.g., subsumption, satifiablility) can be performed on internalized ABox axioms.

Besides considering an internalized ABox, we assume that the EL++ TBox is normalized, and all subsumption closures are pre-computed [Baader et al., 2005]. Due to limited space, we do not formally introduce the notions of interpretation, and entailment (|=) here.

2.2 Ontology Stream and its Evolution

We represent knowledge evolution by a dynamic, evolutive versions of ontologies in Definition 1 [Ren and Pan, 2011].

Definition 1. (Ontology Stream)

An ontology stream Onm from point of time m to point of time n is a sequence of ontologies (Onm(m),Onm(m + 1), · · · , Onm(n)) where m, n ∈ N and m < n.

Onm(i) is a snapshot of an ontology stream Onm (stream for short) at point of time i, referring to a set of axioms in a DL L. A transition from Onm(i) to Onm(i + 1) is an update. We will consider streams On 0 for the sake of clarity and will assume all its snapshots to be consistent w.r.t. T . Inconsistent snapshots generate special cases during the stream auto-correlation and mining processes in Section 3, easy to be handled but not described due to space restriction.

Example 2. (Ontology Stream)

Figure 2 illustrates three partial ontology streams O9 0 , P 9 0 and Q90 through some snapshots at point of time i ∈ {6, 7, 8}.

O9 0(6) : {bus7} ⊑ Bus ⊓ ∃busStatus.(∃stopped.Light) (10) : ∃from.{RockRd} ⊓ ∃to.{Y orkRd} ⊓ ∃travel.{bus7} ⊑ {r1} ⊓ ∃with.{bus7} (11) P 9 0(6) : {r1} ⊑ ∃adj.({r2}⊓∃withWeather.HighHumidity) (12) Q90(6) : {r1} ⊑ ∃adj.({r3}) ⊓ ∃travelT ime.Normal) (13) O9 0(7) : {bus7} ⊑ Bus ⊓ ∃busStatus.(∃stopped.Heavy) (14) : ∃from.{RockRd} ⊓ ∃to.{Y orkRd} ⊓ ∃travel.{bus7} ⊑ {r1} ⊓ ∃with.{bus7} (15) P 9 0(7) : {r1} ⊑ ∃adj.({r2} ⊓ ∃withWeather.LowHumidity) (16) Q90(7) : {r1} ⊑ ∃adj.({r3} ⊓ ∃travelT ime.Long) (17) O9 0(8) : {bus7} ⊑ Bus ⊓ ∃busStatus.(∃stopped.Heavy) (18) : ∃from.{RockRd} ⊓ ∃to.{Y orkRd} ⊓ ∃travel.{bus7} ⊑ {r1} ⊓ ∃with.{bus7} (19) P 9 0(8) : {r1} ⊑ ∃adj.({r2}⊓∃withWeather.HighHumidity) (20) Q90(8) : {r1} ⊑ ∃adj.({r3} ⊓ ∃travelT ime.Long) (21)

By applying completion rules in Table 1 on both background knowledge T and some streams On 0 , we are able to infer axioms which are specific to some snapshots.

Example 3. (Subsumption Reasoning in Ontology Stream) (22), (23), as dynamic knowledge are entailed from T (Figure

1), stream O9 0 (Figure 2), and rules in Table 1. For instance {r1} is entailed to be free in O9 0 (6); and congested in O9 0 (8).

The evolution of a stream is captured along its changes i.e., new, obsolete and invariant ABox entailments from one snapshot to another one in Definition 2.

Definition 2. (ABox Entailment-based StreamChanges)

Let (i) L be a DL, (ii) On 0 (i), On 0 (j) be snapshots in On 0 , (iii) T be L-axioms, G its ABox entailments. Stream changes occurring from On 0 (i) to On 0 (j) (where i < j), denoted by On 0 (j)∇On 0 (i), are ABox entailments (entailments for short) in G being new (Gi,j new ), obsolete (G i,j obs ), invariant (G i,j inv ).

G i,j new reflects knowledge we obtain by moving from On 0 (i) to On 0 (j) while G i,j obs denotes knowledge we lose. G i,j inv captures stability of knowledge. Definition 2, extending the definition of change in [Huang and Stuckenschmidt, 2005] to support ABox entailment-based changes, provides basics for understanding how knowledge is connected among snapshots.

Example 4. (ABox Entailment-based StreamChanges)

Table 2 illustrates changes (new, inv-ariant, obs-olete) occurring from O9 0 (i)6≤i≤7 to O9 0 (8) through entailements {r1} ⊑ FreeRoad, {r1} ⊑ CongestedRoad. E.g., {r1} is a new CongestedRoad in O9 0 (8) with respect to O9 0 (6).

3 Ontology StreamAuto-Correlation&Mining

We present auto-correlation and association rules, as a basis for predicting knowledge in ontology streams.

3.1 Auto-Correlation in An Ontology Stream

Understanding correlations between a stream On 0 and its own past is important for detecting knowledge similarity, repeats, periodicity, even divergence. Definition 3 revisits the concept of auto-correlation [Bracewell, 1999] in Signal Processing for capturing knowledge similarity at various point of time in On 0 .

Definition 3. (Auto-Correlation in An Ontology Stream)

Let (i) L be a DL, (ii) T be L-axioms, (iii) On 0 be a Lontology stream. The (symmetric) auto-correlation between time i and j in [0, n] of On 0 , denoted by A(On 0 (i), On 0 (j)), is:

where the expressions in between | refer to its cardinality i.e., the number of new, obsolete and invariant ABox entailments obtained from On 0 (i) to On 0 (j) using rules in Table 1.

With values in [-1, 1], (27) captures negative and positive correlations. The snapshots On 0 (i) and On 0 (j) are negatively correlated if they are inconsistent i.e., at least one concept has an empty extension in On 0 (i) ∪ On 0 (j) with respect to T . The contradictions and their logical consequences make the correlation negative. Alternatively, they have a positive correlation i.e., On 0 (i) and On 0 (j) share some "elements" (i.e., ABox entailments) of knowledge. In both cases, the number of invariant entailments has a strong and positive influence on the auto-correlation. On contrary, the number of new and obsolete ABox entailments, capturing some differentiators in knowledge evolution, has a negative impact. When an inconsistency occurs, the value 1 is subtracted to (27) instead of considering its additive inverse. This ensures that the invariant factor has always a positive impact on autocorrelation.

Evaluating (27) is in worst case polynomial time with respect to T and On 0 in EL++. Indeed its evaluation requires (i) ABox materialisation, and (ii) basic set theory operations from Definition 2, both in polynomial time [Baader et al., 2005; 2008b].

Example 5. (Auto-Correlation in An Ontology Stream)

All entailments in O9 0 (8), O9 0 (7) and O9 0 (6), derived using Table 1, are required for evaluating (27) with i, j ∈ {6, 7, 8}. In the simple case of O9 0 (8)∇O9 0 (6), we reach the number of 28 invariants, 16 new, 13 obsolete entailments, hence an auto-correlation of -0.508. The negative correlation, due to inconsistency of T ∪O9 0 (6)∪O9 0 (8), is caused by (6), (22-23). The evaluation of A(O9 0 (7), O9 0 (8)), scoring 1, is simpler due to the similar knowledge at points of time 7 and 8 of O9 0 .

Remark 1. (Auto-Correlation Extensions)

It is straightforward to extend Definition 3 for capturing finergrained levels of auto-correlation. For instance the degree of inconsistency, among others, could have been discriminated further by reporting the proportion of concepts with an empty extension. It consists in considering and weighting (27) with the number of inconsistent axioms over two snapshots. Such a modification may fit better some applications e.g., in case our capture of inconsistency is too loose.

Given a point of time j ≤ n, its set of correlated snapshots On 0 (i),i∈[0,n]\{j} can be compared and ordered by applying ≤ on their A(On 0 (i), On 0 (j)) (Figure 3). Thus the best correlated snapshots of On 0 (j) can be retrieved with respect to (27).

Example 6. (Auto-Correlation Comparison and Ordering) Following Example 5, A(O9 0 (7), O9 0 (8)) > A(O9 0 (6), O9 0 (8)) i.e., O9 0 (8) has a stronger auto-correlation with O9 0 (7).

A similarity of auto-correlation scores does not necessarily mean similar knowledge. Indeed (27) does not reflect which invariant, new and obsolete entailments are shared.

3.2 Association Rules Mining in Ontology Streams

Discovering interesting relations and rules between elements of knowledge in multiple streams is crucial for identifying how knowledge could be associated at a given point of time. Definition 4 revisits the concept of association rules [Agrawal et al., 1993] in the context of ontology streams.

Definition 4. (Association Rules in Ontology Streams)

Let (i) L be a DL, (ii) T be L-axioms, (iii) On 0 , P n 0 be Lstreams, (iv) i ∈ [0, n] be a point of time, (v) G be axioms such that T ∪On 0 (i) |= G, (vi) h be an axiom such that T ∪P n 0 (i) |= h. G ↠ h is an association rule in On 0 ×P n 0 iff:

Definition 4 identifies an association rule (Figure 4) as an implication relation between axioms G and h. (28-29) ensure that consequent h is "associated" with antecedent G in neither On 0 nor P n 0 in at least one point of time i ∈ [0, n]. These constraints are important for scalability as they discard trivial rules i.e., associations which can be directly entailed by a snapshot of a unique stream: T ∪P n 0 (i) or T ∪On 0 (i). These rules could be useful if snapshots have missing information.

Example 7. (Association Rules in Ontology Streams)

At point of time 8 in streams of Figure 2, we obtain rules: (30) from O9 0 ∪P 9 0 to Q90 ; (31) fromO9 0 to Q90 among a large set.

For instance, (30) denotes the rule: "if {r1} is congested and humidity is high on {r2} then travel time is long on {r3}".

As the number of rules grows exponentially with the number of entailments in On 0 and P n 0 , it is neither practical nor desirable to mine all potential rules in On 0 × P n 0 . To measure their significance and select interesting rules, we adapt the well-known concepts of support (Definition 5) and confidence (Definition 6), introduced in the database community.

Definition 5. (Axioms Support in Ontology Stream)

Let (i) L be a DL, (ii) T be L-axioms, (iii) On 0 be a L-stream, (iv) G be axioms. The support supp(G) ∈ [0, 1] is the proportion of snapshots in On 0 where T ∪On 0 (i) |= G, i ∈ [0, n].

Example 8. (Axioms Support in Ontology Stream)

Let O8 5 , P 8 5 , Q85 be respectively streams O9 0 , P 9 0 , Q90 restricted to time interval [5, 8] where knowledge at point of time 5 extends [6, 8] in Figure 2. Table 3 illustrates the support of some of their axioms, grouped by syntactic similarity, streamdereferenced e.g., (17) .= (21). (23) is entailed at point of time 5, 7, and 8 of O8 5 but not at 6, thus a support of 3 4 .

Definition 6. (Confidence of an Association Rule)

Let (i) L be a DL, (ii) On 0 , P n 0 be L-streams, (iii) G be sets of axioms and h be an axiom, and (iv) G ↠ h be an association rule in On 0 ×P n 0 . The confidence c of G ↠ h in [0, 1] is:

with supp(G ∪ h), as the support of G ↠ h, is the proportion of snapshots in On 0 ∪P n 0 where both G, h are entailed.

The rule confidence is defined as the percentage of snapshots in On 0 ∪ P n 0 where both G and h are satisfiable with regard to the overall number of snapshots where G is satisfiable. That is, the rule confidence can be understood as the conditional probability p(T ∪P n 0 |= h | T ∪On 0 |= G).

Example 9. (Rule Confidence in Ontology Streams)

The confidence of (30), with G : (23), (20), h : (21) is:

i.e., a score of 1/2 in O8 5 ∪P 8 5 ∪Q85 . (30) is correct in 50%of points of time [5, 8]. A confidence of 1/4 is obtained for (31).

Remark 2. (Association Rules Restrictions)

Other measures e.g., lift, conviction [Geng et al., 2006], all as a combination of support and confidence, can be adapted for capturing other degrees of significance. Similarly, other constraints on types of axioms in G∪h could be considered for restricting rules e.g., axioms with ≡T -similar subsumees/ers.

4 Knowledge Prediction in Ontology Stream

We tackle the problem of prediction by (i) determining the most appropriate rules in evolutive knowledge (Algorithm 1), and (ii) exploiting the effects of injecting their consequents on streams (Algorithm 2).

4.1 Auto-Correlation-Driven Rules Selection

Algorithm 1 combines auto-correlation in lines (7-8) and association rules mining in lines (10-11), for deriving the most relevant rules in On 0 × P n 0 . In particular the rules are constrained to meet a minimal threshold of support and confidence (line 11). More importantly, these degrees of significance are contextualized and evaluated against only correlated snapshots (line 8). Thus, the selection is strongly driven by the factor of auto-correlation, making the rules mining knowledge evolution-aware. This constraint ensures that we learn rules that could be applied in similar context i.e., where knowledge evolution is not impacted by major changes.

Computing a solution with Algorithm 1 given a polynomial input n, the number of axioms in T , On 0 , P n 0 and the number of initial rules |R| is in worst case polynomial time, due to the auto-correlation (Definition 3). However, if |R| is not bounded, the rules selection is in worst case NP with respect to the number of entailments in On 0 ∪P n 0 .

Algorithm 1: Rules-Selection〈L, T , On 0 , P n 0 , k,ma,ms,mc〉.

1 Input: (i) DL L, (ii) Terminology T , (iii) L-streams On 0 , P n 0 defined by some axioms, (iv) k ∈ [0, n], (v) Min. threshold of auto-correlation ma,support ms,confidence mc. 2 Result: R .= {ρ ∈ ˜ On 0 ×P n 0 | (i) ˜ On 0 ⊆ On 0 , (ii) ∀i, A( ˜ On 0 (i), ˜ On 0 (k)) > ma, (iii) supp(ρ) > ms, c(ρ) > mc} 3 4 begin 5 ˜ On 0 ← ∅; R ← ∅; % Initialization of ˜ On 0 and result set R. 6 % ˜ On 0 : snapshots of On 0 which auto-correlates On 0 (k). 7 foreach i ∈ [0, n] do 8 if A(On 0 (i), On 0 (k)) > ma then ˜ On 0 (i) ← On 0 (i); 9 %Min. support, confidence-constrained rules in ˜ On 0 ×P n 0 . 10 foreach ρ ∈ ˜ On 0 ×P n 0 do 11 if supp(ρ) > ms ∧ c(ρ) > mc then R ← R ∪ {ρ}; 12 return R;

Example 10. (Auto-Correlation-Driven Rules Selection)

〈L, T , X , Y, 8, 0, 1/3, 1/2〉 are inputs of Algorithm 1 for identifying rules fromX .= O8 5 ∪P 8 5 to Y .= Q85 . Following Example 5, ˜ X (lines 8) is defined at time i ∈ {5, 7, 8}. Indeed T ∪ X (α)∪X (β) is consistent for (α, β) ∈ {(5, 8), (7, 8), (8, 8)}, not for (6, 8), hence A(X (6), X (8)) < 0. Following lines 1011, the support of rule (30) meets ms i.e., 1/3 in ˜ X × Y while it did not in X × Y with a score of 1/4 (Examples 9), hence a better consideration of rules in similar context. The constraint mc is also met in both contexts with a score of 1/2.

Theorem 1. (Consistent-based Evolution of Streams)

˜

Let R ⊆ On 0 ×P n 0 be output rules of Algorithm 1 with ma = 0 and ˜ On 0 ⊆ On 0 . ∀ρ ∈ R, supp(ρ) and c(ρ) have similar values in ˜ On 0 ×P n 0 and On 0 ×P n 0 if:

Proof. (Sketch) Algorithm 1 is applied with ma = 0, thus all snapshots in On 0 which are negatively correlated with On 0 (j) do not appear in ˜ On 0 (line 8). As (34) is valid ∀i, j ∈ [0, n], all snapshots in On 0 are pairwise consistent, hence all positively correlated. Thus, condition in line 8 is always true (Definition 3), hence ˜ On 0 .= On 0 and ˜ On 0 × P n 0 .= On 0 × P n 0 i.e., no snapshot has been removed from On 0 .

The auto-correlation does not impact the rules selection if snapshots are pairwise consistent over time and ma = 0.

Example 11. (Consistent-based Evolution of Streams)

The support and confidence of any rule in P 8 5 ×Q85 remain unchanged by applying Algorithm 1 with ma = 0 because of the consistency of P 8 5 (i) ∪ P 8 5 (j), ∀i, j ∈ [5, 8].

4.2 Rules-based Consistent Prediction

The prediction of knowledge at point of time n in stream P n-1 0 is achieved using Algorithm 2, illustrated in Figure 5.

All significant rules are identified by Algorithm 1 under constraints of support, confidence (line 6 and ρ, ρ′ in Figure 5). To enforce their applicability at time n, auto-correlation can be positively considered through ma (A(i, n), A(j, n) in Figure 5). All rules G ↠ h, are then filtered by confidence (line 8 and conditions (i) in Figure 5). Finally, the consistency of G in On 0 and h in P n 0 (line 10 and conditions (ii-iii) in Figure 5) are checked to ensure a consistent prediction P n 0 (n) (line 11 and --⇢ in Figure 5) using filtered rules (lines 8-10 and ρ in Figure 5).

Algorithm 2: P rediction〈L, T , On 0 , P n-1 0 ,ma,ms,mc〉.

1 Input: (i) DL L, (ii) Terminology T , (iii) L-streams On 0 , P n-1 0 defined by some axioms, (iv) Min. threshold of auto-correlation ma, support ms, confidence mc. 2 Result: P n 0 (n): Knowledge predicted at point of time n. 3 begin 4 P n 0 (n) ← ∅; % Initialization of prediction. 5 % Identification of significant rules in On 0 ×P n - 1 0 . 1© 6 R←Rules-Selection〈L, T ,On 0 , P n-1 0 , n,ma,ms,mc〉; 7 %All rules ρ : G ↠ h in Rwith highest confidence. 8 foreach ρ : G ↠ h | ∄ρ′ : G′ ↠ h′ , c(ρ′ ) > c(ρ) do 9 %Evaluation of rule ρ ∈ R at point of time n. 2© 10 if (T ∪On 0 (n) ∪ G ̸|= ⊥) ∧ (T ∪ P n 0 (n) ∪ h ̸|= ⊥) then % Axiom h extends knowledge of P n 0 at time n. 11 P n 0 (n) ← P n 0 (n) ∪ h;% 3© 12 return P n 0 (n);

Predicting knowledge given a polynomial number of rules R with Algorithm 2 is in worst case polynomial time, due to line 6 (Algorithm 1) and line 10 [Baader et al., 2005] in EL++. In the worst case of an exponential number of rules captured in On 0 × P n 0 by Algorithm 2 (line 6), prediction is in NP. According to Theorem 1, the set of significant rules is strongly impacted by the stream inconsistency of On 0 . Thus the more inconsistent the evolution of streamOn 0 is, the more scalable will be the prediction.

Example 12. (Rules-based Consistent Prediction)

Let O9 5 , P 9 5 be L-stream O8 5 , P 8 5 extended at time 9 (Table 4). Predicting knowledge of Q85 at time 9 consists in applying Algorithm 2 e.g., 〈L, T ,X, Y, 0, 1/3, 1/2〉 with X .= O9 5 ∪ P 9 5 , Y .= Q85 . Since ma = 0, line 6 (Algorithm 2) returns only rules with entailments in X(6) ×Y(6). Indeed, Injected in P n 0 (n), predictions can be used by DL reasoners for deriving new entailments, as a side-effect of Algorithm 2. Example 13. (Prediction Side Effects in Ontology Streams) Applying GCI (5) and prediction (13) in Example 12 using DL reasoning reaches to bus delay information on road {r3}. Although Examples 12 and 13 illustrate prediction where all entailments and rules are restricted to only {r1}, Algorithm 2 (line 8) is designed for more complex and general cases.

Table 4: Support of Entailment g ∈ G in O8 5 , P 8 5 , Q85 .

5 Experimental Results

We report (i) scalability of our approach and (ii) accuracy of its results. In particular we study the impact of axioms, their consistency together with support, confidence, and autocorrelation thresholds on Algorithms 1 (A1 for rules selection), 2 (A2 for knowledge prediction). Our implementation is based on (i) an extension of InfoSphere Streams [Biem et al., 2010] for processing ontology streams in real-time, coupled with (ii) CEL reasoner [Baader et al., 2006] for standard DL reasoning, and (iii) an adaptation of Apriori [Agrawal and Srikant, 1994] supporting subsumption for determining association rules. For scalability reasons, rules are not injected in DL reasoning but only their consequents. The experiments have been conducted on a server of 4 Intel(R) Xeon(R) X5650, 2.67GHz cores, 6GB RAM.

• Context: Reputable live stream data (Table 5) related to road [a] weather conditions, [b] travel times, [c] incidents together with [d] bus GPS location, delay and congestion status in Dublin City has been considered. Besides an ontology of 55 concepts, 19 role descriptions (17 concepts subsume the 38 remaining ones with a depth of 3), we inject 14, 316 EL++ GCIs (through 6 RDF triples) to describe 4772 roads, their interconnections. The objective is to predict which buses (among 300 buses) in [d] will be delayed in the next hour, using cross-stream rules selected from A1 and A2.
• Scalability Result: Figure 6 reports scalability of A1, A2 ((ma,ms,mc) being (0, 1/2, 1/2)) and compares its computation time with a state-of-the-art approach [Wang et al.,

2003] in stream prediction, noted [W03]. They solve a classification problem over sensor raw data using statistics-based data mining techniques. The evaluation is achieved on (i) various sizes of stream windows |w| (for learning/training) i.e., {1, 12, 48} hours, and (ii) different number of streams |s| i.e., {1, 3, 4} for respectively [d], [b,c,d], [a,b,c,d] in Table 5.

����� ���� �� � � ������ ������ �� ����� ���� ������ �� ��������

Unsurprisingly, [W03] scales much better than our approach in all contexts. Our approach requires some non-negligible computation time for the semantic enrichment of streams. In addition, as the number of potential rules is exponential with the number of entailments in streams (secondary vertical axis), the identification of significant rules is time consuming specially when the window size is growing. Once all rules are identified, the pure prediction part performs from 1.1s to 6.2s. As [W03] is mainly designed for one stream, the computation time remains unchanged if multiple streams are considered.

• Accuracy Result: Figure 7 reports the prediction accuracy of both approaches where Table 6 is used only to configure the parameters values (ma,mc,ms) of our approach A2. Prediction is computed within a window of 48 hours with all streams (Table 5). Accuracy is measured by comparing predictions (delayed buses) with real-time situations in Dublin City, where results can be easily extracted and compared from the raw and semantic data in respectively [W03] and our approach. Negative auto-correlation (c1-c4) strongly alters the accuracy while support and confidence have a positive effect. The confidence has a stronger impact on (i) the reduction of significant rules and (ii) accuracy. If positive auto-correlation, the accuracy of A2 (with a minimum confidence and support of .4) results outperforms results of [W03].
• Lessons Learnt: Although inferring cross-streams rules has a positive impact on consistent prediction and its accuracy, it alters its computation time specially if streams derived numerous entailments. It is even worst with more expressive DLs because of the auto-correlation evaluation (line 7 in Algorithm 1) and consistency check (line 10 in Algo-

rithm 2). The scalability (resp. accuracy) of prediction is negatively (resp. positively) impacted by the ordered settings: (1) stream window size, (2), expressivity of DL, (3) update frequency. The window size is probably the most critical as it drives some heterogeneity in the rules elaboration, which could improve accuracy, but not scalability. The uncertainty related to sensor data e.g., through mis-calibration, noise has also some impacts on association rules hence their accuracy. However accurate prediction can be achieved in real-time using a stream window size |w| of 12 hours in our context of EL++ DL and minimal update frequency of 40 seconds.

�� ������� � �� �������������� � �������� �� ��� �� � ����� �

Figure 7: Accuracy of Prediction.

6 RelatedWork

Prediction, or the problem of estimating future observations given some historical information, spans many research fields, from Statistics to Database and various fields of Artificial Intelligence e.g., planning, knowledge representation and reasoning. Depending on the level of data representation which is considered, a prediction problem [Han and Kamber, 2006] can be formulated as a standard machine learning classification (for symbolic values) [Wang et al., 2003] or regression (for numeric values) task [H¨ardle, 1992].

In most of data stream mining applications, prediction is estimated by correlating current and past data patterns using different distance metrics [Gehrke et al., 2001]. More sophisticated approaches e.g., [Zaki, 2001] investigated sequential pattern mining for capturing the time-based evolution of data in streams. [Papadimitriou et al., 2005] goes further by augmenting existing models with cross-correlation over streams. These approaches are designed for very fast processing and mining of (syntactic) raw data from sensor networks. However they all fail in using and interpreting underlying semantics of data, making prediction in ontology streams not as accurate and consistent as it could be, specially in a context of concept drift (i.e., streams characterized by many changes over time). [Lisi and Malerba, 2004] partially tackles this issue by mining multi-level association rules following hierarchies-based representation of data. However (i) multi-streams dimension, (ii) their inconsistent evolution and (iii) predictive inference are not addressed.

From an ontology stream perspective, (i) reasoning [Valle et al., 2009] for capturing real-time knowledge, or (ii) diagnosing [L´ecu´e, 2012] for explaining anomalies in streams have been recently addressed. Similarly to prediction, the latter requires metrics for evaluating similarities over time e.g., through the detection of changes [Noy and Musen, 2002] in ontologies. These techniques among others [Shvaiko and Euzenat, 2013] could be adapted for correlating past and current semantics-augmented observations and then deriving prediction. However the prediction would solely depends on few observations, which can be noisy, not necessarily accurate, and also ignore potential (logics-based) correlations with other streams. This may prevent the identification of relevant and accurate patterns and rules.

Alternative approaches [Bloehdorn and Sure, 2007], combining machine learning and semantic web principles, are able to predict high level classes of data by mining data instances in ontologies [Stumme et al., 2006]. While promising for learning structure and class-membership on the semantic web, such methods would require major adaptations for predicting knowledge in streams.

7 Conclusion and FutureWork

We studied ontology stream i.e., a dynamic and an evolutive versions of ontologies over time, and addressed the problem of predicting its future (or missing) knowledge. We envisioned predictive reasoning as a correlation and interpretation of past semantics-augmented data over multiple ontology streams. We inferred and mined rules across exogenous streams, where their DL-based semantic representations are captured and interpreted through some background knowledge. Based on an analysis of stream evolution, consistent predictions are constructed by selecting and applying relevant cross-streams association rules. The step of lifting raw stream data at semantic (i.e., ontology stream) level was beneficial for (i) easy integration and adaptation of heterogenous data streams with static knowledge, (ii) cross-correlating and mining knowledge as a basis of the prediction approach and (iii) bootstrapping knowledge. In particular the semantic representation of the domain was crucial for pruning the search space of association rules and identify those which are relevant (in the sense of semantic consistency) for prediction. Our experiments have shown accurate prediction with real and live stream data from Dublin City.

In future work we will improve the scalability for supporting high throughput sensors. One direction is to apply novel reasoning services, e.g. by using summarization techniques [Fokoue et al., 2006; 2012] to reduce the size of window of observations while maintaining its knowledge or by using native support for stream reasoning and parallel reasoning in TrOWL [Thomas et al., 2010]. The classification and generalization of rules using background knowledge is another direction.

Acknowledgments

The authors would like to thank Alice Marascu for helpful discussions, and the anonymous reviewers for their valuable comments and suggestions to improve the paper.