This paper proposes an integrated framework for extracting Constraint-based Multi-level Association Rules with an ontology support. The system permits the definition of a set of domain-specific constraints on a specific domain ontology, and to query the ontology for filtering the instances used in the association rule mining process. This method can improve the quality of the extracted associations rules in terms of relevance and understandability.
OWL is a family of three ontology languages: OW L − Lite, OW L − DL, and
OW L − F ull. The first two languages can be considered syntactic variants of the
SHIF (D) and SHOIN (D) description logics (DL), respectively, whereas the
third language was designed to provide full compatibility with RDF(S). We focus
mainly on the first two variants of OWL because OWL-Full has a nonstandard
semantics that makes the language undecidable and therefore difficult to
implement. OWL comes with several syntaxes, all of which are rather verbose. Hence,
in this paper we use the standard DL syntax [
The semantics for OWL DL is fairly standard. An interpretation I = (ΔI , ·I ) is a tuple where ΔI , the domain of discourse, is the union of two disjoint sets ΔIO (the object domain) and ΔID (the data domain) and I is the interpretation function that gives meaning to the entities defined in the ontology. I maps each OWL class C to a subset CI ⊆ ΔIO, each object property PObj to a binary relation POIbj ⊆ ΔIO × ΔIO, and each datatype property PData to a binary relation PDIata ⊆ ΔIO × ΔID. The whole definition is in the OWL W3C Recommendation (http://www.w3.org/TR/owl-semantics/).
Data mining is the analysis of (often large) observational data sets to find unsuspected relationships and to summarize the data in novel ways that are both understandable and useful to the data owner. The relationships and summaries derived through a data mining exercise are often referred to as models or patterns. The main tasks of Data mining are generally divided in two categories: P redictive and Descriptive. The objective of the predictive tasks is to predict the value of a particular attribute based on the values of other attributes, while for the descriptive ones, is to derive patterns (correlations, trends, clusters, ...) that summarize the relationships in the data.
The Association rule mining is one of the major techniques of data mining and it is perhaps the most common form of local-pattern discovery in unsupervised learning systems. These methodologies retrieve all possible interesting patterns in the database. Given a database D of transactions, where each transaction
T ∈ D is a set of items, an association rule is a (statistical) implication of the
form X → Y , where X, Y ∈ D and X ∩ Y = ∅. A rule X → Y is said to have a
support (or frequency) factor s if and only if, at least s% of the transations in
T satisfy X ∪ Y . A rule X → Y is satisfied in the set of transactions T with a
conf idence factor c if and only if, at least c% of the transactions in T that satisfy
X also satisfy Y . The support is a measure of statistical significance, whereas
the confidence is a measure of the strength of the rule. A rule is said to be
“interesting” if its support and confidence are greater than user-defined thresholds
supmin and conmin, respectively, and the objective of the mining process is to
find all such interesting rules [
In this section, we describe our approach for guiding the extraction process of Multi-level Constraint-based Association Rules with an ontology support. Our scenario consists of the set of components shown in figure 1. The ontology (OD) describes the domain of interest (D) and it is used as a means of meta-data representation. The interpretation module translates the requests of an user (user constraints) into a set of f ormal constrains (QD defined on OD) so that they can be supplied to the Ontology Query Engine by means of a suitable query language. The aim of these constraints is to exclude some items from the output association rules, or to characterize interesting items according to an abstraction level. The user constraints syntax is formalized in table 1. It includes both pruning constraints, used for filtering a set of non-interesting items, and abstraction constraints, which permit a generalization of an item to a concept of the ontology. By using pruning constraints, one can specify the exclusion of a set of items from the input transactions set, and, as a consequence, from the extracted rules. This kind of constraints refers either to a single item, or to an ontology concept, and they can include a condition expressed on a set of ontology properties. Abstraction constraints permit exploring different levels of the ontology concepts. The generalization to a predefined level of the hierarchy I is the set of items (i1, i2, ...in ∈ I).
C is the set of the concepts of the ontology (c1, c2, ...cn ∈ C).
Pc is the set of the properties of the concept c ∈ C (p1, p2, ...pn ∈ Pc). condc is a Description Logic expression.
ALL represents all the instances defined in the ontology.
A constraint is defined on I, C and PC in the following form: 1. Pruning Constraints. A pruning constraint is of one of the following forms: (a) prune(e), where e ∈ I ∪ C ∪ {ALL}.
(b) prunecondc (c), where c ∈ C ∪ {ALL}. 2. Abstraction Constraints. An abstraction constraint is of one of the following forms: (a) abstract(e, c), where e ∈ I ∪ C, c ∈ C and c is a super-concept of e. (b) abstractcondc1 (c1, c2) where c1 ∈ C ∪ {ALL}, c2 ∈ C and c2 is a super-concept of c1. (c) abstractlconde (e), where e ∈ I ∪ C ∪ {ALL}, and l is a non-negative integer indicating the level of the hierarchy; cond can be unspecified. improves the support of association rules, and consequently avoids the discovery of a massive quantity of useless rules, especially in case of sparse data.
The ontology query engine interacts with the ontology by performing the set QD of queries. The resulting RD instances set, is used by the DB query engine for retrieving the instances that contain the filtered/abstracted/pruned items (i.e., the items specified in RD). The data base is the repository of the data to pass in input to the data mining tools. The box “Data Mining Tools” contains the tool for analyzing and processing the data. In our context we refer to a specific algorithm for extracting association rules, but we would like to point out that the system can operate with other kinds of DM tools. The support and the confidence measures are initially provided by the user. 4
In this section we show the results of a case study by using data taken from a national supermarket, and stored in a relational database (DB). The aim of this study is to construct and test the framework described in the previous section with real data and w.r.t. specific market analysis. In this case, the data consist of a set of purchase transactions T = [transID, item], where transID is the cash voucher identification and item is the purchased item. The DB contains 775,000 transactions. According to the approach proposed in sec. 3, meta-data (description of the items) and data to analyze have been organized respectively in separate structures: The ontology - contains the description of the items and their hierarchical organization. Starting from the DB structure (tables and fields)3, we derived the OWL ontology schema mapping the fields of the DB tables in classes and properties of the ontology. Also, we automatically filled up the ontology with about 30,000 items, and their attributes (approximately 100). Let us consider the item Vodka Keglevich Melon. The correspondent hierarchical structure and the list of the item attributes are shown in the table below.
∇
Hierarchical Structure Attributes of Vodka owl:Things hasColour: transparent;
XXX Supermarket hasAlcoholicContent: high; ∇ ∇L0∇LFo1∇oLDds2rtiuLVnff3kossdSkVapanoicddykDarKinekgsleDviecphaMrtmeleonnt ihhhhsaaaaFssssiSFPBzilzrrzaayiecvn::eodN:u7:0rEoK;:UcMelR;gele7lov.5nic6;h;; The DB - contains the transactions T .
The experimentation has been conducted using SeRQL (“Sesame RDF Query
Language”) [
In the first two tests we abstract all items to two upper levels (level L2 and level L1) for verifying what categories of items are bought together. In this way we abstract all items to only 14 high level concepts in the first case and to only 4 high level concepts in the second one. These abstraction constraints can be expressed respectively as:
Query 1 ≡ abstract2(ALL)
Query 2 ≡ abstract1(ALL)
The third test concerns an investigation for organizing a future promotional campaign during the holidays (Christmas and Easter). The focus is on typical sweets and cakes (with well-known brands) of the two holidays, and the alcoholic drinks. The objective is to verify how those articles are related. All kinds of sweets/cakes are abstracted to Foodstuffs (associated with the item brand) and all kinds of alcoholic drinks to Drinks. These constraints can be expressed as: Query 3 ≡ prune(∃hasBrand.=null)(ALL)∧ abstract(∃hasBrand.<>null)(Alcoholic, Drinks) ∧ abstract(∃hasBrand.<>null)(Sweets, F oodStuffs) ∧ abstract((∃hasRecurrence.=Easter)t(∃hasRecurrence.=Christmas))(Sweets, F oodStuffs) 3 We considered the DB table named Marketing that, for each article, specifies a hierarchical structure w.r.t. the department organization in the supermarket. The part of the ontology schema (i.e. the part of the DL knowledge base) related to the Query 3 can be expressed by the following TBox fragment: T3 = EatableT hing v (∃hasBrand.string) u (= 1hasBrand) u EatableT hing v (∃hasRecurrence.string) u (≥ 0hasRecurrence) u (Drinks v EatableT hing) u (F oodStuffs v EatableT hing) u (Alcoholic v Drinks) u (Sweets v F oodStuffs) According to the interpretation function I = (ΔI , ·I ) defined in section 2, the semantic interpretation of the conditions expressed by the abstract clauses is: Alcoholic v (∃hasBrand. <>null) t Sweets v (∃hasBrand. <>null) u (∃hasRecurrence. =Easter) t (∃hasRecurrence. =Christmas) = AlcoholicI ∩ {xa | ∃ya.(xa, ya) ∈ hasBrandI ∧ ya 6= nullI} ∪ SweetsI ∩ {xs | ∃ys.(xs, ys) ∈ hasBrandI ∧ ys 6= nullI} ∩ {z | ∃w.(z, w) ∈ hasRecurrenceI ∧ w = EasterI} I ∪ {h | ∃k.(h, k) ∈ hasRecurrenceI ∧ k = ChristmasI} = {A} ∩ {xa | ∃ya.(xa, ya) ∈ {(a, ba)} ∧ ya 6= null} ∪ {S} ∩ {xs | ∃ys.(xs, ys) ∈ {(s, bs)} ∧ ys 6= null} ∩ {zs | ∃ws.(zs, ws) ∈ {(p, rp)} ∧ ws = Easter}
∪ {h | ∃ks.(hs, ks) ∈ {(q, rq)} ∧ ks = Christmas} = {A} ∩ {(a, brand)} ∪ {S} ∩ {(s, brand)} ∩ {(p, Easter)} ∪ {(q, Christmas)} = {(alcoholic, ba)} ∪ {(sweetsEaster, bs)} ∪ {(sweetsChristmas, bs)} where {A} and {S} are the instances sets of the classes Alcoholic and Sweets respectively, with a ∈ {A} and s, p, q ∈ {S}; ba, bs are any well-known brands of Alcoholic and Sweets respectively. The semantic expressed by prune clause is very similar to abstract so we omit it for lack of space.
In the last test, we consider the case in which the supermarket augments its services by introducing a new department (Assisted Service). This event introduces an innovation in the supermarket domain, so we have to modify the ontology4 i.e. we have to introduce a new data property, for some category (typeOfService (ToS) with enumerated type Assisted Service, Take Away, Free Service). We abstract to level L2 all the items with typeOfService equals to Assisted Service or Take Away, ignoring the others. This constraint can be expressed as: 4 Notice that, the introduction of a new property does not imply the re-engineering of the structure, but only the introduction of the property in the higher classes so that the property is inherited by each subclasses. For the lack of space we omit the semantic interpretation of the Query4.
For evaluating our framework we submitted to the system the queries
introduced above. Our framework automatically translates these constraints into
SeRQL language for querying the ontology. In all tests we applied the Apriori
implementation of the KDDML System [
#Trans #Items #Itemsets #Rules LI AI we report the supports graph of the queries. In the abscissa there are the top 50 frequent itemsets, while in the ordinate there is the support related to the ith frequent item. As you can notice, in the picture the result of Test 2 has not been reported because it contains only 15 frequent itemsets. The use of real data typically brings issues related to the quality of the extracted model. Items at the lower levels of the taxonomy may not have enough support to appear in any frequent itemsets. This aspect is underlined in figure 2 in which we can notice that the Query 0 retrieves only itemsets with a very low support. This is mainly due to the large number of articles. Moreover, rules extracted at the lower levels of a concept, are too much specific, and may not be interesting. Consider for example the following rule extracted at low level:
The rule is not relevant due to the low support. Consider instead the following rule, that corresponds to the previous, but at an higher level of abstraction, and
satisfying Query 4: {F oodStuffs AssistitedService} ⇒ {F oodStuffs T akeAway} [supp = 0.26, conf = 0.68].
This rule abstracts all the items to level L2 of the ontology and each of them is selected by the typeOfService property. The information extracted from this association rule can suggest that the assisted service department has to provide to the customers also (take away) cooked meals (roastedchicken, cookedlasagne). In general, items abstracted at the higher levels, tend to have higher support counts. This fact increases the quality of the extracted rules, and as consequence, helps the analyst in the decision support. Association rules related to Query 3, for example, emphasize the concept of multi-level rule correlating concepts at different abstraction level. For example the concept FoodStuffs (level L2) with BAU LI and M OT T A as brands, and Drinks (level L2) with AST I6, are related to Red M eats (level L7) slaughtered and packed by the supermarket. It can suggest to the analyst some marketing decisions on these products during Easter or Christmas period.
The study of multi-level association rules is well-known in literature, and in this context, our work may not seem innovative. The focus of our approach is the introduction of the expressive power of ontologies for constraint-based multilevel association rule mining. The main advantages can be summarized in terms of extensibility and flexibility. Our framework is extensible because data properties and concepts can be introduced in the ontology without either changing the relational database containing the transaction, or the implementation of our framework. The flexibility is guaranteed from the separation of the data to
analyze (the transactions) from the meta-data (description of the data). Furthermore it interesting to point out that our approach is general, and can be adapted to further data mining analysis. 5
Methods to define and integrate item constraints are originally introduced by
Srinkant and Agrawal in [
Our approach follows the research line proposed by the cited works, nevertheless it introduces three main differences: (i) we employ an ontology to represent an item taxonomy; (ii) constraints can be defined on the basis of specific properties of the items; (iii) by using an ontology instead of a taxonomy, a new item property or a concept can be added without re-engineering the (meta-data) representation model or the relational database.
Other studies concern the merging of the association rules mining with a
domain ontology. In [
We proposed an integrated framework for the extraction of constraint-based multi-level association rules with the aid of an ontology. Our system permits the definition of domain-specific constraints by using the ontology for filtering the instances used in the association rule mining process. The main advantages of the proposed framework can be summarized in terms of extensibility and flexibility.
In our case study, the supermarket domain is modeled only by classes and data properties and it would be very interesting to study: (i) how object properties (and more complex logical relationships) can be employed in our framework; (ii) what aspects they can improve. Other important future works are the possibility of modeling the antecedent and the consequent of an association rule as ontology concepts in order to express constraints on the association rules structure. Furthermore we could improve the system by integrating the constraints evaluation directly in the mining algorithm.
Acknowledgement. This work is supported by M U SIN G project (www.musing.eu/).