This paper presents new inference algorithms based on rules partition. Optimisation relies on reducing the number of rules searched in each run of inference and reducing the number of unnecessary recursive calls and avoiding the extraction of too many new facts. The rst part of the paper presents the de nition of the model of knowledge base based on rules partition. The second part describes the modi cations of both forward and backward inference algorithms using knowledge base with rules assigned to the groups given by the partition strategy. At the end, the paper consists of an example of knowledge base with the description of inference processes for this particular knowledge base.
Knowledge bases are still one of the most popular method of knowledge
representation. They are constantly increasing in volume, thus the knowledge stored
as a set of rules is getting progressively more complex. The ability to obtain large
rules sets in easy and automatic way has got an enormous negative impact on the
time of decision making | inference in large rules sets is time consuming
process and the results of inference are in many cases hard to understand [
This paper presents a new idea of partitioning of rule knowledge base and
application of this idea in inference optimisation task. We introduce an approach,
which assumes that the rule knowledge base is decomposed into the groups of
rules, called rules partitions. Knowledge base in the form of rules partitions
allows to improve the e ciency of inference algorithms. The groups of rules on
which the knowledge base is partitioned let to reduce the search space for
inference algorithms and to decrease the time needed to browse rules. Thus we may
say that the knowledge base in the form of rules partition optimises inference
processes. In this work we introduce two types of strategies for partitioning of
knowledge base. First important strategy, divides the rules knowledge base into
groups of rules with similar premisses, the second divides the rules into groups of
rules with the same conclusion. The rst one is called strategy based on similar
premisses. The second one is known as decision strategy. Both of the strategies
will be used as a base for proposed modi cation of inference algorithms. The
introduced partition strategies correspond to the research carried out so far by
the authors on cluster analysis for the rules in the knowledge base [8{10] and the
application of the concept of decision unit idea [
The rst part of the work presents the rules partitioning approach. The second part consists of the description of interence algorithms modi cations. At the end, the paper contains an example of knowledge base with the description of inference processes for this particular knowledge base. 2
The proposed concept assumes division of knowledge base into coherent subgroups of rules. This section presents the basic concepts and notations of knowledge base partitioning, because this conception is a relatively new and it is not widely known. A signi cant part of this work contains detailed description of proposed approach. 2.1
The rules-based knowledge base R consists of n rules: r1; : : : ; ri; : : : ; rn and is an unordered set. Each rule ri 2 R is stored as a Horn's clause: ri : p1 ^ p2 ^ : : : ^ pm ! c, where m is the number of literals1 in conditional part of rule ri (m 0, i = 1 : : : n) and c is the literal for the conclusion part of rule ri. An attribute a 2 A may be a conclusion of rule ri as well as a premise of it. For each rule ri 2 R, the function concl(ri) returns the conclusion literal of rule ri, whereas the function cond(ri) returns the set of conditional literals of rule ri. The set of facts is denoted as F = ff1; f2; : : : fsg, the facts are also stored as literals. The knowledge base KB is de ned as a pair: KB = (R; F ). 1 literals in the form of pairs of attribute and its value (a; via) (or equally a = via). Let A be a non empty nite set of conditional and conclusion (decision) attributes. For every attribute a 2 A, the set Va is called the set of values of attribute a.
For every rules base R with n rules the number of possible subsets is 2n. Any arbitrarily created subset of rules R 2 2R is called a group of rules P R or rules partition. It is created by partition strategy, denoted by P S, which generates groups of rules P R: P S(R) g)en P R. Partition strategy P S for rules set R generates the partition of rules P R 2R:P R = fR1; R2; : : : ; Rkg where: k is the number of groups of rules formed by the partition P R, and Rj is j-th group of rules, R 2 2R and j = 1; : : : ; k. Partition strategy P S is the general concept. It is possible to show a lot of di erent approaches for creating groups of rules. Each of them can be done with a di erent partition strategy. Every simple partition strategy involves the necessity of de ning the membership criteria mc : R P R ! [0::1]. We can de ne mc in a variety of ways, also we can consider speci c form of this function (mc : R P R ! f0; 1g), for example: mc(ri; Rj ) = 1 if sim(ri; Rj ) T 0 in the opposite case (1) where sim(ri; Rj ) is de ned in eq.3.
In general, the value 1 denotes the situation when rule ri 2 R is de nitely included in the group Rj and 0 in the opposite case. The value between 0 and 1 denotes the degree of membership of rule ri to the group Rj . It is possible to achieve many di erent partitions of rules. Generally, including op, as any operator from the set [>, >, <, 6, =, 6=], we can simply de ne partition P R as follows: P R = fRj : Rj 2 2R ^ 8ri2Rj mc(ri; Rj ) op T g, where value mc(ri; Rj ) de nes the membership of rule ri to the group Rj which can be higher, higher or equal, equal, less, less or equal to the threshold value T (0 T 1).
The exceptional case of a simple strategy is the speci c partition called further the selection. The selection divides the set of rules R into two subsets R and R R in such a way, that all rules from R meet the membership criterion for some partition strategy P S, and all other rules do not meet such criterion. Partition P R = fR; R Rg, which is the result of the selection, is important in practical terms. During the inference process, we search within the knowledge base one rule by one (which is time consuming) in order to nd a set of relevant rules. Selection serves the same role, because it provides rules necessary to be activated during the inference process, but in a more e cient way.
There are two types of partition strategies: simple and complex. Simple strategy creates nal partition P R by a single search of rules set R and by assigning each rule ri to group Rj according to the value of the membership function mc(ri; Rj ). The example of simple strategy is a selection of a pair of most similar rules or selection a group of rules to which a given rule is the most similar according to the value of threshold T and membership function mc. The strategy of creating groups of similar rules is the example of complex strategy because it usually multiply runs the simple strategy of nding two most similar rules or groups of rules. Complex strategies very often do not generate the nal partition in a single step. Usually, they begin with a preliminary partition, which is modi ed further in accordance to the methods of partition. It is de ned by a combination of a few simple strategies, an iteration of one of them or the combination of both methods.
Partition strategy based on nding groups of rules with similar premisses is
the example of complex strategy which uses simple strategy known as strategy of
choosing a pair of the most similar rules many times. Finding the pair of most
similar objects is a crucial step in every clustering algorithm. Thus the
partition strategy which divides rules into the groups of rules with similar premisses
has the result similar to the Agglomerative Hierarchical Clustering (AHC)
algorithm but the hierarchy does not need to be saved [
To determine the similarity between rules here the authors use the function R R ! [0::1] de ned as: sim(ri; rj ) = jcond(ri) \ cond(rj )j : jcond(ri) [ cond(rj )j (3) The value of sim(ri; rj ) is equal to 1 if rules are formed by the same literals and 0 when they do not have any common literals. The more similar the rules are, the value of sim(ri; rj ) is closer to 1. It uses the similarity of conditional part of rules. However, we may also use the information about conclusions of rules while measuring the similarity of rules. This similarity measure works well with either rules, groups of rules, representatives of rules or set of facts. It is worth to mention that each group in created rules partition achieves its' representative called Pro le. Instead of searching within the full structure of rules, only representatives of groups are compared. They are usually given by the set of common literals among all the literals belonging to all the rules forming a group of rules, a set of the most frequent literals or the set of distinctive ones. To nd a relevant group of rules during the inference process the maximal value of similarity (see eq. 3) between the set of facts F (and/or hypothesis to be proven) and the representatives of each group of rules P rof ile(Rj ) is searched. Value of sim(F; P rof ile(Rj )) is equal to 0 if there is no such fact fi (or hypothesis to prove) which is included in the representative of any group Rj . It is equal to 1 if all facts (and/or hypothesis) are included in the P rof ile(Rj ) of group Rj . The more facts with hypotesis included in the pro le of group Rj the greater the value of similarity. Exhaustive search of rules is done only within a given group. Details of inference process are given in the section 3.
Partition strategy for rules with the same conclusions creates the groups
of rules from R by grouping rules with the same attribute in conclusions. It
also can be called decision oriented partition strategy. The membership criterion
for rule ri and group Rj is given by the function mc de ned in eq. 1. When
we will use the simple partition algorithm (described below in the next section
as Alg01:createPartitions ) with the mc function de ned in this way, we obtain
decision oriented partitions. Each group of the rules generated by this algorithm
may have the following form: R = fr 2 R : 8ri2R concl(ri) = concl(r)g. The
number of groups in the partition k : 1 k n depends on the number of
di erent decisions included in conclusions of such rules. When we distinguish
di erent decision by the di erent conclusions appearing in the rules | we get one
group for each conclusion. This partition strategy corresponds to the concept of
the decision units presented in [
The attribute in knowledge base usually represents the particular concept
or property from real word. The value of attribute expresses the determined
meaning of the concept or state of the property. If we consider the speci ed
(a; v) pair, we think about particular kind of concept or about particular property
state. Similarly, in decision tables DT = (U; A [ fdg) | considered in the Rough
Set Theory | values of decision attributes d de nes partition of objects from
U into the decision class CLASSA(d) = fXA1; XA2; : : : XAr(d)g, where r(d) is the
cardinality of value set for attribute a and XAi is the i-th decision class of A [
The input parameters for rules partition algorithm based on simple strategy are: knowledge base R, mc function and the value of the threshold T . Output data is the partition P R. Time complexity of such algorithm is O(n k), where n = jRj, k = jP Rj. For each rule r 2 R we have to check whether the goal partition P R contains the group R with rule r (the value of the mc function has to be at least equal to T : mc(r; R) > T ). If such a rule doesn't exist the given rule r becomes the seed of a new group which is added to the created partition P R. Alg01:
Ensure: P R = fR1; R2; : : : ; Rkg; procedure createPartitions ( R, var P R, mc, T ) var R, r; begin P R = fg; for all r 2 R do if 9R 2 P R : mc(r; R) > T then
R = R [ r; else
R = frg;
P R = P R [ R; end if end for end procedure
The algorithm of creating the speci c partition called selection is presented below. The input parameters are knowledge base R, the function mc which de nes the membership criterion and the threshold value T . Output data is the single group of rules R, which consists of rules from R, that ful ll the condition of mc. In fact, each selection generates the partition which has two elements, but the second group is de ned implicitly as R R. So the nal partition of P R for the selection strategy is created as: P R = fR; R Rg. Time complexity of this algorithm is O(n), where n = jRj.
Let us notice that presented algorithm does not have any knowledge about the speci cation of a given group of rules. It uses only the values of the membership function mc. If the parameter R is an empty set, the function of mc determines whether the rule r ful lls the condition given by the membership function for empty group R. Alg02: Selection strategy algorithm
Ensure: R = fr1; r2; : : : ; rlg; procedure createSelection ( R, var R, mc, T ) var r; begin for all r 2 R do if mc(r; R) > T then
R = R [ r; end if end for end procedure
An example of partition algorithm (di erent to selection strategy algorithm) is the algorithm based on clustering rules into groups of similar rules. For each rule it checks if a particular rule should be included in a given group. The result is a partition of k groups: P R = fR1; R2; : : : ; Rkg. This algorithm describes the AHC or mAHC algorithms and it is presented as follows.
Ensure: P R = fR1; R2; : : : ; Rkg; procedure clustering ( R, var R, mc, T )
repeat carry out some processing
ndTwoMostSimilarGroupsOfRules (R); createNewGroup(pOR, R ); until maxfsim(Ri; Rj )g T
where R0 denotes the created rules' partition. ndTwoMostSimilarGroupsOfRules ( R ) is the procedure that compares groups' representatives and nds the two most similar. The createNewGroup(pOR, R) function adds the new, recently created group to the structure and reduces the size of the structure by removing the elements which formed the newly created group.
Partitions generated by the algorithms Alg01, Alg02, Alg03 are unique and complete | each rule r 2 R is considered, and quali ed to one group R, that matches the criteria of mc. Presented modi cation of backward inference will utilise this features. For this reason algorithms which generates incomplete or non-unique partitions will not be presented in this work. 3
The main goal of the decision support systems (DSSs) is to infer new knowledge
from data stored in knowledge base. The inference is the process of proving (or
falsifying) the hypothesis, knowing that the facts used in the process are true
[
This type of inference is also called data or facts driven. Each rule is analysed whether all its' premisses are satis ed. If that is the case, the rule is activated and its' conclusions are added to the set of facts. The algorithm stops either where there are no more rules which can be activated or when the starting hypothesis is added to the set of facts [5{8]. Forward inference leads to a massive growth of new facts, but most of them are nonessential to prove the starting hypothesis and can slow down the inference process signi cantly. Unfortunately, when the DSS consists of more than 100 rules, the vast majority of time (over 90%) is consumed to nd the rules which can be activated [2{4]. The inference process can be divided into three stages: matching, choosing and execution. At rst, the premisses of each and every rule are analysed to match it to the current set of facts. Then the subset of the con ict set is chosen consisting of those rules, which are actually activated. At the end, previously selected rules are analysed and the set of facts is updated. The matching phase usually takes the biggest amount of processing time during the inference. To reduce the time necessary to realise the matching phase, the authors propose to partition the rules into groups that match the facts set with minimal covering threshold. It is not necessary to build a full partition and to create the selection from all the rules which are relevant to set of facts with some minimal covering factor. Having the structure with rules' partition, the forward inference works as follows: in each iteration the representatives of each group are browsed and only a group with the highest similarity to the given set of facts is chosen for further analysis. This particular group is the browsed. Each rule belonging to this group is analysed and when the rules' premisses are fully covered by the set of facts, rule is activated. The conclusion of the activated rule is added to the set of facts.
The pseudocode of such inference process is following:
Ensure: F ; procedure forwardInference ( R, F ) var R; begin createFactsMatchingSelection ( R, F , R ); while R 6= ; do applyRules ( R, F ); excludeRules ( R, R ); createFactsMatchingSelection ( R, F , R ); end while end procedure
The algorithm uses temporary variable R, which is the set of rules that is the result of the previous selection. The procedure responsible for nding the most relevant group to the given set of facts (F ) and thus - the rules to activate is createFactsMatchingSelection. It is responsible for creating the selection of rules that match the given condition de ned by mc. The membership function mc checks whether the sim(ri; Rj ) is greater or equal to T . Using the createFactsMatchingSelection procedure reduces the time necessary to nd relevant rules signi cantly. The original time complexity O(n) is reduced to the O(k) where k << n, k denotes the number of created groups. If the result of the selection is not empty (R 6= ;) the procedure applyRules is commenced. It adds the new facts which are the conclusions of all rules activated from the set R to the set of facts. The excludeRules function temporarily removes activated rules from further searching. Afterwords, the createF actsM atchingSelection procedure is called again. The whole presented process is repeated in while loop until the selection becomes empty.
It should now be clear that the most often used method of running the mc function is to calculate the similarity value between a given set of facts and a rule from the previously selected set R.
Among the advantages of the proposed modi cation of the classical forward inference process are: reducing the time necessary to search within the whole knowledge base in order to nd rules to activate and achieving additional information about fraction of rules that match the input knowledge (the set of facts). 3.2
In this section we present the backward inference algorithm, which use the conception of the decision partitions P R, created by the selection algorithm Alg01. The proposed modi cation utilises the following concepts: (i) the reduction of the search space by choosing only rules from particular rule group, according to a current structure of decision oriented rules partition and (ii) the estimation of the usefulness for each recursive call for sub-goals, only promising recursive calls of classical backward algorithm will be made.
Modi ed algorithm for backward inference will use the following input data: P R | the decision partition, F | the set of facts, g | the goal of the inference. The output data of the algorithm: F | the set of facts, including possible new facts obtained through inference, the function's result as boolean value, true if the goal g is in the set of facts: g 2 F , false otherwise.
The proposed modi cation of backward inference algorithm utilises the information from decision partitions of rules to reduce the number of unnecessary recursive calls and the number of rules searched for in each run of the inference. Only promising groups of rules are selected for further processing (select R 2 P R where g 2 Concl(R)), where Concl(R) is the set of conclusions for the group of rule R, containing literals appearing in the conclusion parts of the rules r from R. Only the selected subset of the whole rules of (R A) is processed in each iteration. Finally, only the promising recursive calls are made (w 2 InC (R)). InC (R) denotes connected inputs of the rules group, de ned in the following way: InC (R) = f(a; v) 2 Cond(R) : 9r2R (a; v) = concl(r)g, where Cond(R) is the set of conditions for the group of rule R, containing literals appearing in the conditional parts of the rules r from R. In each iteration the set R contains only proper rules matching to the currently considered goal, it completely eliminates the necessity of searching for rules with conclusion matching to the inference goal, it is not necessary to search within the whole set of rules R | this information is simply stored in the decision-units and does not have to be generated. 3.3
To illustrate the conception of partitioning and exploring the knowledge base, let us consider an example of knowledge base R which consists of following rules. r1 : (a; 1) ^ (b; 1) ! (c; 1) r2 : (a; 1) ^ (b; 2) ! (c; 2) r3 : (a; 1) ^ (b; 3) ! (c; 1) r4 : (b; 3) ^ (d; 3) ! (e; 1) r5 : (b; 3) ^ (d; 2) ! (e; 1) r6 : (b; 3) ! (e; 2) r7 : (d; 4) ! (f; 1) r8 : (d; 4) ^ (g; 1) ! (f; 1) r9 : (a; 1) ! (d; 4)
According to the knowledge base presented below and the set of facts F = f(a; 1)g, in case of goal driven inference algorithm, for con rmation of the main goal of the inference described by literal (f; 1), it is necessary to nd rules matching to the goal. Next | if such rules exist | we have to select the rule to be activated. In our simple example we select a group R1 with rules r7 and r8 from which we are choosing r7 as the rule with higher similarity value. Now we have to con rm the truth of the premise (d; 4). Because it doesn't appear in the facts set, it becomes a new sub-goal of inference and inference algorithm runs recursively. The classic version of the algorithm does not known whether the call is promising | i.e. it is unknown if there is a rule that proves the new goal of inference. For goal (d; 4) we use recursive call for (a; 1). It is a fact and when it is con rmed the other subgoal will also be con rmed (d; 4) as well as the main hypothesis (f; 1).
According to the rules' partition based on nding similar rules and the set of facts f(g; 1); (d; 4)g the process of data driven inference algorithm goes as follows. Assuming that chosen partition strategy returns the following structure of knowledge base:
R1 = fr7; r8g R2 = fr1; r3g R3 = fr4; r5g R4 = fr2g R5 = fr6g R6 = fr9g we check the similarity2 between the set of facts F and the representative of each group: sim(F; P rof ile(R1)) = 23 ; sim(F; P rof ile(R2)) = 0; sim(F; P rof ile(R3)) = 0; sim(F; P rof ile(R4)) = 0; sim(F; P rof ile(R5)) = 0; sim(F; P rof ile(R6)) = 0:
Next we choose the most similar group to the set of facts (which is R1) and we check the similarity between every rule in this particular group:
We activate rules with all known premisses (in our case it is only one rule r8).
Then we include new fact to F : F = F [ f(f; 1)g. The new fact is the conclusion
of activated rule r8. Of course we block rule r8 to make sure that it will not
be analyzed later because it would only increase the time of inference process
without gaining additional knowledge. We also block the whole group if all its'
rules are already blocked. The result of the inference process is eventually given
as a set of facts F = f(g; 1); (d; 4); (f; 1)g. If the rules partition is the result
of using the partition strategy based on clustering algorithm, it is necessary to
search the groups of rules using similarity measure based on searching using
pro les of groups. We may use any algorithms for rules clustering but the most
e cient one is, in authors' opinion, the AHC or mAHC algorithm presented
in [
We have introduced the approach, which assumes that the rule knowledge base is decomposed into the groups of rules, called rules partitions. In our opinion each knowledge base contains enough information, which allows to improve the e ciency of the classic inference algorithms. We introduce partitions of rules as the source of such information. Modi cation of the classical inference algorithms is based on information extracted from the rules of groups generated by the proposed, two partitioning strategy.
The proposed modi cation of forward algorithm consists of the reduction the time necessary to realise the matching phase of inference by choosing only the rules from particular rule group, which match the facts set with minimal covering threshold. The proposed modi cation of backward algorithm consists of the reduction of the search space by choosing only the rules from particular rule group, according to a current structure of decision oriented rules partition and the estimation of the usefulness for each recursive call for sub-goals. Therefore, 2 the value for a pair F and P rof ile(R1) is equal to 23 because there are two common literals ((g; 1); (d; 4)) both in the set of facts and the representative of a group R1 = f(g; 1); (d; 4); (f; 1)g. only necessary rules are searched and only promising recursive call of the classical backward algorithm will made.
The concept of rules partitions is the new proposition, based on the previous
research concerning on rules clusters [
This work is a part of the project ,,Exploration of rule knowledge bases" founded by the Polish National Science Centre (NCN: 2011/03/D/ST6/03027).