Several rule discovery algorithms have the disadvantage to discover too much patterns sometimes obvious, useless or not very interesting to the user. In this paper we propose a new approach for patterns ranking according to their unexpectedness using semantic distance calculated based on a prior background knowledge represented by domain ontology organized as DAG (Directed Acyclic Graph) hierarchy.
Two main categories of algorithms for computing the semantic distance between terms organized in a hierarchical structure have been proposed in the literature [9]: distance-based approaches and information content-based approaches. The general idea behind the distance-based algorithms [24, 12, 32] is to nd the shortest path between two terms in terms of number of edges. Information content-based approaches [10, 24] are inspired by the perception that pairs of words which share many common contexts are semantically related. We will be using distance-based approaches in this paper. In an IS-A semantic network, the simplest form of determining the distance between two elemental concept nodes, A and B, is the shortest path that links A and B, i.e. the minimum number of edges that separate A and B or the sum of weights of the arcs along the shortest path between A and B [24].
In the hierarchy of Figure 1, the edges distance between nodes of the graph with weight=1 is: Dist(Apple, Kiwi) = 2 Dist(Carrots, Pepper) = 2 Dist(Apple, Meat) = 4 Dist(Fruit, Red Meat) = 4 2.2
The prior knowledge of domain or a process in the eld of data mining can help to select the appropriate information (preprocessing), decrease the space of hypothesis (processing), to represent results in a more comprehensible way and to improve process (post processing)[5]. Ontology expresses the domain knowledge which includes semantic links between domain individuals described as relations of inter-concepts or roles [7]. For a given rule R :X ! Y where X = X1 ^ : : : ^ Xk , Y = Y1 ^ : : : ^ Ym and D is the maximum depth of the hierarchy, we de ne the degree of unexpectedness (DU) of a rule R as : DU(R)=Distance(X,Y)/2D. To compute the distance between groups of concepts, we choose to use Hausdor Distance Distance(X, Y)= max(h(X,Y),h(Y,X)) where
max min h(X, Y)= Xi2X Yj2Y kXi Xj k
The function h(X,Y) is called the directed Hausdor 'distance' from X to Y (this function is not symmetric and thus is not a true distance). It identi es the point Xi2X that is farthest from any point of Y, and measures the distance from Xi to its nearest neighbor in Y. the Hausdor distance, H(X,Y), measures the degree of mismatch between two sets, as it re ects the distance of the point of X that is farthest from any point of Y and vice versa [8]. This expression measures semantic distance between groups X1 ^ : : : ^ Xk and Y1 ^ : : : ^ Ym of concepts which contain k Xi and m atomic Yj concepts respectively. 2.4
In this section we introduce an algorithm to rank rules according to their degree of unexpectedness based on background knowledge. The rules we consider are on the form "body ! head" where "body" and "head" are conjunctions of concepts in vocabulary of the ontology. We assume that other techniques carry out the task of patterns discovery and eliminated the patterns that do not satisfy objective criteria. With such ranking, a user can check simply few patterns on the top of the list to con rm rule pertinence.
Input : Ontology, Set of rules Output : Ordred set of rules R: Set of rules R= fRi/ Ri=body ! headg where i 2[1,N] ND: Number of nodes N: number of rules D: Maximum depth of the hierarchy DU: Array of size N representing degree of unexpectedness Xi, Yj : Atomic Concepts; i 2[1,k] ; j 2[1,m] Body = X1 ^ : : : ^ Xk Head = Y1 ^ : : : ^ Ym For i=1 to ND begin For j=1 to ND Distance (Xi; Xj) =shortest path between Xi; Xj; End For i=1 to N begin DU [i] = (Distance(X1 ^ : : : ^ Xk; Y1 ^ : : : ^ Ym))=2D End Sort Descending degree of unexpectedness DU. 3
In this section we present results from applying our method to the hierarchy of Figure 1 with a set of association rules R = fApple ! Kiwi; Apple ! Carrots; P epper; Carrots ! T urkey; Chickeng resulting from a data mining process. 3.1
The number of graph nodes in Figure 1 is ND=16 and the depth of the graph is D=3. The semantic distance (the minimum number of edges that separate 2 nodes) computation of Figure 1 graph nodes is presented in the following table (Table 1) where every cell represents the distance between the node on the line and the corresponding one on the column.
We have presented only the leaves of the hierarchy in Table 1 due to the fact that all the rules R are expressed using leaves concepts of the hierarchy. 3.2
The maximum depth of the hierarchy in Figure 1 is D=3.
For a given rule X!Y where X=X1 ^ : : : ^ Xk and Y=Y1 ^ : : : ^ Yk Distance(X,Y)= Distance (X1 ^ : : : ^ Xk; Y1 ^ : : : ^ Ym) = max(h(X; Y ); h(Y; X)) For the set of rules R = f(a), (b), (c)g where: (a) Apple! Kiwi (b) Apple ! Carrots (c) Pepper, Carrots ! Turkey, Chicken The detail computation distance of the rules (a), (b), (c) is : (a) Dist(Apple, Kiwi)=2 (b) Dist(Apple, Carrots)=4 (c ) Dist(Pepper^Carrots, Turkey^ Chicken)= max(h(Pepper^Carrots, Turkey^ Chicken), h(Turkey^ Chicken,Pepper^Carrots)) h(Pepper^Carrots, Turkey^ Chicken)=6 h(Turkey^ Chicken,Pepper^Carrots)=6 (c)Dist(Pepper^Carrots, Turkey^ Chicken)= 6 The degree of unexpectedness for a given rule X!Y is calculated using our expression DU(X!Y)=Distance(X,Y)/2D and the resulting computation is presented in (Table 2) The order of rules would be (c), (b), (a) based on degree of unexpectedness descending order as shown in (Table 2).From decision system point of view the rule (c) belongs to a higher level (Food) than the rule (b) that belongs to level (vegetable-dishes). The rule (a) belongs to a lower level (Fruit). More we move up on in the hierarchy more the decision is important and the vision of the decision maker is broader and therefore the discovered rule is more interesting. Rule (c) is the crossing result of domains (vegetables-dishes, Meat) which are farther than domains (vegetables, Fruits) of the rule (b). The rule (a) concerns domain (Fruit) only and therefore it is the less interesting. 4
The experiments were performed using a census income database with 48.842 records [3] with an implementation of our algorithm. To generate the association rules, we used the implementation of the Apriori algorithm [2] with a minimum support value equal 0.2 and a minimum con dence value equal 0.2. The number of the generated rules set is 2225. In order to perform the experiments, we created the taxonomy of 81 weighted concepts based on the data set we are studying, as shown in (Table 3).
We conducted two tests, the rst one with a weight value equals to one for all concepts with results presented in (Figure 2). The second test was conducted with di erent weights on the atomic concepts level (see Table 3 for weights), with results presented in (Figure 3). (Figure 2) and (Figure 3) are the extracted rst two lines within each distance value for each test.
Looking to the results we notice: 1. Best results are those for highest weight (Figure 3 with Bachelors concept). 2. Best results from both tests are cross level concepts (higher subsumer like 'Personal', 'Education', 'Work' or 'census-income') and not those within the same concept level. 3. Low results from both tests (last 2 lines) are within the same concept level like 'Personal'.
Our approach is based on a hierarchy in (Table 3) which guides the resulting rules. The maximum hierarchy depth is 3 and it is the same as the minimum depth; this hierarchy is distributing the load equally between its di erent branches. The rst test was conducted with weight equals to 1, for all concepts; In this case all
Private Self-emp-not-inc
Self-emp-inc Self-emp-inc Federal-gov Local-gov
State-gov Without-pay Never-worked Tech-support Craft-repair Other-service
Sales Exec-managerial
Prof-specialty Handlers-cleaners Machine-op-inspct
Adm-clerical Farming- shing Transport-moving
Protective-serv Armed-Forces 50K 50K Tech-support
Bachelors Some-college
11th
HS-grad Prof-school Assoc-acdm .
.
Preschool
9
9 num
13 num
num
15
13
15
concepts have the same degree of interest to the user. The ranking rules algorithm picks those with higher
subsumer concept. The common subsumer for the rules ((
The second test was conducted with a weight of 'bachelors' concept equals to 7 (among other concepts
settings see Table 3).The user in this case is putting more emphasis on this concept by setting its weight
to a high value or because it is really that important in the domain of study. The ranking rules algorithm
picks those with higher weight. The common subsumer for the rules (
Unexpectedness of patterns has been studied in [29, 30, 13, 14, 19, 20] and de ned in comparison with user beliefs. A rule is considered interesting if it a ects the levels of conviction of the user. The unexpectedness is de ned in probabilistic terms in [29, 30] while in [13] it is de ned as a distance and it is based on a syntactic comparison between a rule and a conviction. Similarity and distance are de ned syntactically based on the structure of the rules and convictions. A rule and a conviction are distant if the consequence of the rule and conviction is similar but antecedents are distant or vice versa. In [21] the focus is on discovering minimal unexpected patterns rather than using any of the post processing approaches, such as ltering, to determine the minimal unexpected patterns from the set of all the discovered patterns. In [18] unexpectedness is de ned from the point of view of a logical contradiction of a rule and conviction, the pattern that contradict a prior knowledge is unexpected. It is based on the contradiction of the consequence of the rule and the consequence of belief. Given a rule A!B and a belief X!Y, if B AND Y is False with A AND X is true for broad group of data, the rule is unexpected. In [15] , the subjective interestingness (unexpectedness) of a discovered pattern is characterized by asking the user to specify a set of patterns according to his/her previous knowledge or intuitive feelings. This speci ed set of patterns is then used by a fuzzy matching algorithm to match and rank the discovered patterns. [26, 27, 28] has taken a di erent approach to the discovery of interesting patterns by eliminating noninteresting association rules. Rather than getting the users de ne their entire knowledge of a domain, they are asked to identify several non-interesting rules, generated by the Apriori algorithm. [25] use genetic algorithm to dynamically maintain and search populations of rule sets for the most interesting rules rather than act as post-processor. The rules identi ed by the genetic algorithm compared favorably with the rules selected by the domain expert [17]. Most researches on the unexpectedness makes a syntactic or semantic comparison between a rule and a belief. Our de nition of unexpectedness is based on the structure of background knowledge (hierarchy) underlying the terms (vocabulary) of the rule. We are taking a di erent approach from all the preceding work. The preceding work is a ltering process based on a belief expressed as rules that the user has to enter. We are proposing a ranking process and the knowledge are not expressed as rules, but as hierarchy of concepts ontology. Ontologies enable knowledge sharing. Sharing vastly increases the potential for knowledge reuse and therefore allows our approach to get free knowledge just from using domain ontologies already available like "ONTODerm" for dermatology, "BIO-ONT" for biomedicine, "ASFA, OneFish , FIGIS , AGROVOC" for Food,etc.
In this paper we proposed a new approach to estimate the degree of unexpectedness of a rule with respect to ontology and ranking patterns according to their unexpectedness, de ned on the base of ontological distance. The ranking algorithm proposed uses an ontology to calculate the distance between the antecedent and the consequent of rules on which is based the ranking. The more the conceptual distance is high, the more the rule represents a high degree of interest. This work constitutes a contribution to post analysis stage to help the user identify the most interesting patterns.
In the future, we plan to incorporate a semantic distance threshold in the algorithm of calculation of frequent items, to exploit others relation of ontology other than "IS-A". We are also validating our approach on fuzzy ontology to take into account vague and imprecise information. [19] Balaji Padmanabhan and Alexander Tuzhilin. A belief-driven method for discovering unexpected patterns. In
KDD, pages 94{100, 1998.
[20] Balaji Padmanabhan and Alexander Tuzhilin. Unexpectedness as a measure of interestingness in knowledge
discovery, January 09 1999.
[21] Balaji Padmanabhan and Alexander Tuzhilin. On characterization and discovery of minimal unexpected patterns
in rule discovery. IEEE Trans. Knowl. Data Eng, 18(
Databases, pages 231{233. AAAI/MIT Press, 1991. [23] Gregory Piatetsky-Shapiro and Christopher J. Matheus. The interstigness of deviations. In KDD Workshop, pages 25{36, 1994. [24] R. Rada, H. Mili, E. Bicknell, and M. Blettner. Development and application of a metric on semantic nets. IEEE
Transactions on Systems, Man, and Cybernetics, 19(
In KDD, pages 275{281, 1995. [30] Abraham Silberschatz and Alexander Tuzhilin. What makes patterns interesting in knowledge discovery systems.
IEEE Transactions on Knowledge and Data Engineering, 8(