ABSTRACT

There have been multiple techniques to discover action-rules, but the problem of triggering those rules was left exclusively to domain knowledge and domain experts. When meta-actions are applied on objects to trigger a specific rule, they might as well trigger transitions outside of the target action rule scope. Those additional transitions are called side effects, which could be positive or negative. Negative side effects could be devastating in some domains such as healthcare. In this paper, we strive to reduce those negative side effects by extracting personalized action rules. We proposed three object-grouping schemes with regards to same negative side effects to extract personalized action rules for each object group. We also studied the tinnitus handicap inventory data to apply and compare the three grouping schemes.

1. Introduction

Action rules observe patterns, recorded on an information system, of domain experts applying their domain knowledge and expertise in real world situations. They provide efficient solutions to help naïve system users solve real world problems. There has been an increasing interest on action rule discovery algorithms since their creation by Ras and Wieczorkowska in [1]. Action rules have been used in healthcare to understand experts’ practices and improve patients’ care [2-5]. They are also used in distribution and customer loyalty systems, and maybe used in a wide range of industries such as education, and banking.

Action rules, that were first introduced in [1] and then investigated in [6-12], represent changing some of the objects’ properties that will make the overall objects state change. They model the correlation between some specific classification features values and the decision feature values.

Meta-actions are used to provoke changes in objects’ state and trigger action rules to solve specific problem. They are mainly defined by domain knowledge and domain experts and used by system users. When used to trigger actions rule, meta-actions trigger changes in objects state within the system to execute the action rule. In other words, they provoke changes in objects’ features that will not only trigger the actions rule targeted but also side effects that could be negative. The negative side effects can damage the objects’ features outside of the executed action rule scope. Naïve system users might not know about those negative side effects; thus, they will not be taken into consideration even though they might be harmful.

In this paper, we study closely the side effects of applying meta-action. We acknowledge that those negative side effects are not avoidable in most situations; therefore, we strive to personalize the action rules and their respective meta-actions applied to objects based on their reactions to meta-actions. We strongly believe that action rules should be extracted from data sets describing objects that have the same negative side effects, and we present three objects’ grouping techniques based on negative side effects.

This paper was motivated by the tinnitus handicap dataset that was exploited in previous research [5] to extract action rules. In this dataset, patients are treated using four different treatments (in this context treatments represent meta-actions); however, some of the patient’s features were changed to negative values (worse property values). Those negative changes affect objects’ properties that are outside of the action rules scope and are therefore omitted by system users.

By analyzing the patient’s negative side effects, and grouping patients based on their reactions to treatment, we can extract personalized action rules. The main contributions of this paper are:

1) Defining side effects resulting from applying metaactions;

2) Presenting three object grouping methods for personalized action rules based on negative side effects;

3) Implementing the three grouping techniques and experimenting them on the tinnitus handicap dataset.

There are a number of software packages available for discovering action rules. For instance, Action4ft-Miner module of the Lisp-Miner project developed by Jan Rauch’s group discovers action rules under different constraints which can be placed for the antecedent part of the rule [13].

2. Problem Definition

An action rule provides a set of atomic actions on its antecedent side, which will trigger the atomic action on its right side, if executed. Meta-actions are the triggers for those atomic actions to happen. However, the current solution does not provide a personalized procedure for specific objects or group of objects to whom applying certain meta-actions may result in negative side effects. For example, given a bank customer that is 24 years old, has medium salary, medium monthly expanses, high savings, low interest rate, and average loan profitability, if we apply meta-actions to increase the interest rate that triggers an action rule increasing the loan profitability, we may as well trigger a decrease in customer’s savings, thus affecting negatively the saving account profitability. This scenario may not be suitable for the bank decision maker, and may not respect the strategy of the bank.

We strive to extract personalized action rules with regards to objects negative reactions to meta-actions. To achieve this goal, we group objects based on their negative reactions and extract personalized action rules on each object group concerned by specific negative side effects.

3. Side Effects Based Personalization

In this section we explore the different techniques of grouping objects and extracting action rules from a decision system, introduced by Z. Pawlak [14], that are personalized for each group of objects.

By a decision system we mean, where:

(1) X is a set of objects;

(2) F is a set of classification features, is a function for any, where is called the domain of f;

(3) d is a decision feature, is a function, where V_d is called the domain of d;

(4), where.

Also, for each and, we assume that value is classified either as positive (normal) or negative (abnormal). To be more precise, we assume that denotes the set, and that, where is a set of posi tive values and is a set of negative values for. If, then the value is interpreted as abnormal (for instance: high temperature, cough, headache, ^…). If, then value is interpreted as normal.

3.1. Action-Rules

Action rules are rules that provide a set of actions to follow to drive the objects population from a certain state to a more profitable state. In addition, action rules are composed of features that are divided into two sets: stable features F_st, and flexible features F_fl such that.

Stable features are object properties that we do no have control over in the context of our information system. For example, age and gender are stable features. Flexible features are object properties that can transition from an initial value to another value triggering a change in the object state. For instance, salary and benefits are flexible features since they can change values.

An atomic action term is an expression that defines a change of state for a distinct feature. For example, is an atomic action term which defines a change of value of the attribute f from v₁ to v₂, where. In the case when there is no change, we omit the right arrow sign, so for example, means that the value of attribute f remains v₁, where.

Action terms are defined as the smallest collection of expressions such that:

• If t is an atomic action term, then t is an action term;

• If are action terms and Ù is a 2-argument functor called composition, then is a candidate action term;

• If t is a candidate action term and for any two atomic action terms contained in t we have, then t is an action term.

The domain of an action term t is the set of features listed in the atomic action terms contained in t. For example, is an action term that consists of two atomic action terms, namely and. Therefore,.

Action rules are expressions that take the following form:, where are action terms. The interpretation of the action rule r is that by triggering the action term t₁, we would get, as a result, the changes of states in action term t₂. We also assume that, and

For example

means that by changing the state of feature f from v₁ to v₂, and by keeping the state of feature g as w₂, we would observe a change in attribute d from the state d₁ to d₂, where d is commonly referred to as the decision attribute.

In [9], it was observed that each action rule can be seen as a composition of two classification rules. For instancethe rule is a composition of and. This fact can be recorded by the equation. Also, the definition of support and confidence of an action rule is based on support and confidence of classification rules (see below).

Assume that action rule r is a composition of two classification rules r₁ and r₂. Then [9]:

By the support of a classification rule

in a decision system, where we mean the set.

3.2. Meta-Actions

By meta-actions associated with decision system S we mean higher concepts used to model certain generalizations of actions rules [11]. Meta-actions, when executed, trigger changes in values of some flexible features in S as described by influence matrix [11] and atomic action terms.

To give an example, let us assume that classification features in S describe teaching evaluations at some school and the decision feature represents their overall score. Explain difficult concepts effectively, Speaks English fluently, Stimulate student interest in the course, Provide sufficient feedback are examples of classification features. Then, examples of meta-actions associated with S will be: Change the content of the course, Change the textbook of the course, post all material on the Web. Clearly, any of these three meta-actions will not influence the feature Speaks English fluently and the same its values will remain unchanged [11]. Let us take Hepatitis as the application domain. Then increase blood cell plague and decrease level of alkaline phosphatase are examples of an atomic action term. Drugs like Hepatil or Hepargen are seen as meta-actions triggering changes described by these two atomic action terms [4, 15].

It should be noted that Hepatil is also used to get rid of obstruction, eructation, and bleeding. However, Hepargen is not used to get rid of obstruction but it is used to get rid of eructation and bleeding.

Also, it should be mentioned here that an expert knowledge concerning meta-actions involves only classification features. Now, if some of these features are correlated with the decision feature, then the change of their values will cascade to the decision through the correlation. The goal of action rule discovery is to identify possibly all such correlations.

Consider several meta-actions, denoted. Each one can invoke changes within values of some classification features in. The expected changes of values of classification features on objects from S triggered by these meta-actions are described by the influence matrix. Table 1 gives an example of an influence matrix associated with 6 meta-actions and three features: a, b, and c.

For instance, let us take meta-action M₂. It says that by executing M₂ on objects in S, two atomic action terms are triggered. They are: and. It means that objects in S satisfying the description are expected to change their description to.

Let us define as a set of meta-actions associated with a decision system S. Let, and, then, applying the meta-actions in the set M on an object x will result in, where object x is converted to object y by applying all meta-actions in M to x. Similarly, , where x is converted to y by applying all meta-actions in M to x for all. Also, by, where, we mean.

3.3. Side Effects

The main goal of meta-actions is to trigger action rules.

Table 1. An example of an influence matrix associated with 6 meta-actions and three features: a, b, and c.

However, it is often the case that when applying metaactions for the purpose of executing a specific action rule, a set of unrelated additional and potentially harmful atomic action terms are triggered. The additional action terms resulting from the meta-action application are called side effects.

Meta-actions might move some objects’ features values from negative to positive values and (desirable positive side effects), and some object’s features values from positive to negative values and (undesirable negative side effects).

Even though the features transitioning from positive to negative values might result in catastrophic situations, they were not fully investigated in previous work involving action rules discovery.

4. Personalized Object Grouping

Unfortunately, the negative side effects resulting from applying meta-actions are unavoidable in most situations. However, we can still lower the negative side effects resulting from executing the meta-actions by personalizing the action rules applied to objects. Action rules dictate the sets of meta-actions to apply to be triggered. There are multiple subsets of meta-actions that could be applied to different action rules and result in multiple subsets of negative side effects.

We aim to minimize the negative side effects for a large number of objects by discovering personalized action rules while keeping their utility and increasing their support and confidence.

In the following, we define three techniques to group objects based on their side effects resulting from applying meta-actions for a personalized action rules discovery system.

4.1. Side Effects Based Grouping

In this technique, as the title suggests, we group objects based on side effects. In most situations, objects have known side effects such as patients having allergies. However, more side effects can be determined based on the possible meta-actions applied.

Let us define the set of meta actions on the system, such that for.

We aim at grouping objects that have same negative side effects for any meta-action in where. This grouping will result in a partition of X defined by the equivalence relation given in the following:

where, and.

Also, we assume here that x_i is converted to y_i,k and x_j is converted to y_j,k by.

In a real setting, as explained earlier, we need to follow a set of steps in order to group objects in the most optimal way minimizing the negative side effects to extract the right action rules. In fact, meta-actions result in different negative side effects from one object to another. We defined the following steps for personalizing action rules based on common negative side effects:

• We first need to extract the negative side effects from applying the meta-actions for each object if they are not defined yet. This process is performed by analyzing our decision system S and extracting all negative side effects for all for each transaction (observation) that happens directly after applying the meta-actions.

• We then group the objects that have the same side effects using the previously defined equivalence relation that will result in a partition G. Those groups encompass the objects’ observations in our decision system for each object in the group.

• We extract the personalized action rules for each group using the objects’ observation in each group and the algorithms presented in [3,9].

• Finally, we select the personalized action rules with the best support and confidence pair to apply in each group.

The personalized action rules extracted for each group of objects will result in the same negative side effects when applying the related meta-actions to trigger the action rules. However, grouping the objects by negative side effects first will decrease the object population for discovering the action rules for each group. This might result in decreasing the support of the rules or even not discovering all possible rules. To remediate to this problem, we propose the action rule based grouping that is described in the following.

4.2. Action Rules Based Grouping

Another way of grouping objects in X is by grouping action rules with respect to their common support.

Let us assume that AR_S is a set of action rules extracted from a decision system, and The binary relation is defined as follows:

Clearly, is an equivalence relation which partitions the action rules in AR_S into classes such that any two action rules in the same class have the same set of supporting objects in X. For instance, let us assume that

and . Also, we assume here that , and. Then, and , where is the set of values of attributes listed in t₁₁. Now, if, then

displays all properties which objects in X have to satisfy in order to be affected by r₁ or r₂.

So, the relation partitions the action rules in AR_S into equivalence classes in such a way that each class, where and , has a unique set of attribute values for which is used as its identifier. In the section above, .Each identifier defines a subset of all objects in X satisfying all properties listed in it. This way, we do not only group the objects in X but also identify the largest subset of objects in X which can be affected by minimum one action rule.

We still need to partition further the obtained groups of objects by taking into consideration personalized action rules based on their negative side effects. We use grouping mechanism similar to the side effects based grouping, presented in the previous section.

We define the following steps for personalizing action rules based grouping with respect to the negative side effects:

• We first extract the set of action rules AR_S from S and next we group the objects in X based on the equivalence relation. Let’s assume that represents that grouping.

• We extract the negative side effect for all resulting from applying the meta-actions to trigger the action rules in for each object.

• Then, we split each group in such a way that objects having the same side effects with respect to action rules associated with G_k are placed in the same sub-groups. For that purpose, we use the equivalence relation defined in the previous section. It will result in new sub-groupings G_ki of X.

• We merge the sub-groups G_ki if their respective action rules trigger the same negative side effects.

• Finally, we select the personalized action rules with the best support and confidence pair to apply in each group.

This grouping will not generate smaller groups than the previous technique since the merging step insures that groups with the same negative side effects are merged together.

4.3. Meta-Actions Based Grouping

The previous grouping technique based on action rules does not take the meta-actions into consideration. This may result in groups of objects with their respective action rules having different meta-actions applied to trigger their rules.

Another grouping technique groups objects first with respect to meta-actions applied to them. Of course meta-actions are not applied randomly to objects. They are either applied based on an action rule needs, or applied by an administrator making a decision based on his/her expertise.

Let us have a decision system and a set of meta-actions associated with S which can be applied to objects in X. We first group objects by meta-actions and then we split the obtained groups further with respect to the negative side effects which are triggered by them. In order to group objects in X with respect to a meta-action, where E_pk are atomic actions triggered by M_p, we assume that and define the following relation for any:

In a similar way we can group objects in X with respect to any set of meta-actions and in particular with respect to a minimal set of meta-actions triggering a given action rule. Let us assume that

represents that grouping. Next, we split each group in such a way that objects having the same side effects with respect to meta-actions associated with G_k are placed in the same sub-groups. This strategy is similar to the one presented in Section 4.1.

5. Experiments

In this paper, we used R 2.15 to process the data and built in software to discover action rules.

5.1. Data-Set Description

The dataset used in those experiments is from the Tinnitus Handicap Inventory and represents physician’s observations on patients. The data contains three categories of observations on patient’s properties that are affected by tinnitus, which are: functioning (F), emotions (E), and how catastrophic it is (C). Each category consists of several related questions describing the patient’s state. There are 25 multiple choice questions altogether, and the answers to all of them can be mapped to numeric scores: “Yes” is 4, “Sometimes” is 2 and “No” is 0. To evaluate the overall status for each patient, physicians observed three features “Sc F”, “Sc E”, and “Sc C”, which are the total score of functioning category, the total score of emotions category and the total score of catastrophic category, respectively. Those three scores represent the sum of all the answer’s scores for each category. Then feature “Sc T” (total score) is generated by adding results of “Sc F”, “Sc E”, and “Sc C” together to measure the tinnitus severity. The Tinnitus Handicap Inventory is completed during each patient visit and stored with patients’ ID, visit date and number, and patient’s gender (g). Another aspect of the data was the treatment performed on the patients at each visit. The treatment performed on the patients at each visit were divided into four treatments that are: Hearing Aid (HA), Sound Generator (SG), (CO) Combination of HA and SG, and a regular consultation (RC).

To be able to use the data in our experiments we had to perform a cleaning step along with a discretization step. In fact, the total number of patients’ visits is of 2591 visit instances; however, there are multiple missing values and incomplete visit instances that had to be removed in order to be able to complete our experiments with the cleanest data possible. After cleaning the data, we ended up having only 517 visit instances.

We distinguished our data set classification features from the side effects. We assumed that the classification features are the functioning (F), emotions (E), and the catastrophic (C) features, and we kept their score values as they were already discretized. We further assumed that the side effects were the three scores of each category of the features Sc F, Sc E, and Sc C. We discretized the side effects based on the improvements on the category score (score = 1 positive side effects if the score decreases) and the declining of the category score (score = 0 negative side effects if the score increases). The decision feature is the total score, and the main goal of the treatments was to decrease the total score. We also discretized the decision feature, the total score, based on its improvement and its declining (score = 1 if improvement i.e. score decreases) and (score = 0 if declining i.e. score increases).

5.2. Side Effects Based Grouping

In this experiment we used the steps described in our proposed approach. However, we first cleaned the data and organized it by negative side effects.

Since we already know the three side effects in our dataset, we grouped patients that have the same negative side effects by codifying the different combinations of side effects values. Since we have three side effects and two possible values for each side effect (0 for negative and 1 for positive), we will have eight possible groups of patients in our partitioning.

Grouping patients with regards to same side effects resulted in the following number of patients in each group (see Table 2):

After grouping the patients by side effects, we extracted the action rules AR (2, 85%) using our action rules discovery software. We constrained the action rules confidence to 85% and support to a minimum of 2 in each one of the groups. However, since different groups might have different support, we increased the support sequentially to have the highest minimum support that returns actions rules. Furthermore, we fixed the decision transition from no-improvement to improvement.

The results of each group’s action rules discovery after the partitioning are presented in the following Table 3.

Note that the groups of only negative side effects g₀₀₀ and the group of only positive side effects g₁₁₁ do not have any action rule. This is due to the decision feature being the same for all the group. In addition, note that the extracted rules do not have strong support. This is due to shrinking the patients populations in the groups.

An example of an action rule extracted from group g₁₁₀ is described in the following:

Table 2. Number of patients by side effects groups.

Table 3. Action rules by side effects groups.

5.3. Action Rules Based Grouping

After the data cleaning step, we extracted all possible action rules from the entire decision system. We used our action rules extraction software setting up the minimal confidence to 85%, and the starting support at a minimum of 20. This support was then decreased sequentially until we reached a minimum support that resulted in discovering at least one action rule.

First, we extracted two action rules with minimum support 20 and minimum confidence 85%. Then, we decreased the minimum support to 19 to extract more action rules while keeping the confidence at least at 85%. This way 10 additional action rules has been found.

Next, we grouped them into sets of action rules that have the same antecedent side. Grouping the action rule with same antecedent side resulted in two groups for the first partition P1 for action rules with support 20. For the second set of action rules with support 19, we ended up having a partition P2 of 10 groups. Each one of those groups is summarized in Table 4 and contains one action rule with a specific confidence and support:

For each action rule antecedent side set, we grouped patients that have the same preconditions as the antecedent part of action rules set together in the same group. This type of partitioning is natural since each patient is associated with a set of possible action rules. This step also insures that patients that do not have possible action rules are not part of the partition grouping.

Each group of action rules led to a number of patients having the same preconditions as the antecedent side of the rules. This experiment returned the same number of patients in each group as the support of the respective rules, which are 20 patients for the two groups of P1 and 19 patients for each group of P2.

Table 4. Action rules by antecedent side grouping.

Note that we do not get the same group size as the support of the corresponding rules in all situations since we are using the minimum support method to compute the rule support.

We followed the next step in our described approach where we further partitioned each group of patients presented in the previous Table 4 to subgroups having the same negative side effects.

Each action rules based group was partitioned into a number of subgroups with regards to the same negative side effects. This partitioning is represented in Table 5, where you can note that the total number of patients for all negative side effects sub-group (row sum) is larger than the total number of patients in each corresponding parent group in the action rules grouping. This is due to an overlap between the groups for patients having different applicable action rules.

The previous table also represents the merging step, where the total number of patients in each sub-group is represented by the partition with respect to side effects. Note that this number is small due to the patients overlap described earlier in the table for the action rules groups. However there is no overlap between the different side effects groupings.

5.4. Meta-Action Based Grouping

This experiment requires grouping the objects based on meta-actions. Since the physician already applied treatments (meta-actions) to patients and those treatments are recorded in the dataset, we just need to place any two patients in the same group if the same treatments have been applied to them.

Table 5. Number of patients by side effects and action rules grouping.

After cleaning the dataset and removing the missing and incomplete values, we ended up having three possible treatments that are Hearing Aid (HA), Sound Generators (SG), and Regular Consultation (RC). Thus, we grouped the patients into those three different groups. The results of the grouping based on same meta-actions are summarized in Table 6.

We then generated action rules from each group by setting up the minimum confidence to 85% and minimum support to 3; however, the support varies from one group to another depending on the group’s action rules strength. We also fixed the decision feature transition from 0 to 1 (no improvement to improvement in the score). Table 7 summarizes the results of action rules discovery:

We can note that the minimum support strength of the discovered action rules in each group is positively correlated to the number of patients in each group.

Here is the example of an action rule discovered in the RC group:

Once we have the groups of patients based on the meta-actions, we further partition each group to subgroups with respect to the same negative side effects. The results are summarized in Table 8.

5.5. Grouping Schemes Comparison

All three grouping schemes have their advantages and disadvantages with regards to action rules personalization.

Table 6. Number of patients by meta-action.

Table 7. Action rules by meta-actions groups.

Table 8. Number of patients by meta-actions and side effects grouping.

The side effects-based grouping is a patients-centric scheme with regards to their negative side effects. It allows the extraction of more personalized action rules since each group dataset used in the action rules discovery process is exclusive to patients with exactly the same negative side effects. As we can note from Tables 2 and 3 and Figure 1, the average group size is decent and the number of action rules generated is high. In addition, Figure 2 denotes the highest confidence for this scheme. However the support of the extracted rules is rather small in comparison with the other schemes as seen in Figure 3. In fact, using the partitioned datasets to extract the rules limits the number of observations; thus, limits the strength of the action rules.

In this sense, we might argue that the second scheme, action rules based grouping, is more efficient than the previous scheme. It uses the whole dataset to generate the action rules first, and then groups patients by their side effects. It allows extracting action rules with stronger support as seen in Figure 3 and Table 4. This partitioning is the most fine-grained since it allows distinguishing the patients not only by their side effects but also by their personalized rules. This is confirmed in our experiment where the number of patients in the finegrained side effects groups is very small as seen in Figure 1 and Table 5. This is due to shrinking the datasets or groups to only the action rules domains (patients with extracted applicable action rules). The total number of patients will get bigger as we decrease the support, since we will extract more rules. However, the rules confidence is the smallest in this scheme as seen in Figure 2. In addition, in order to cover all patients in the dataset, we will eventually have to decrease the support; thus, the strength of the rules.

The third grouping scheme, meta-action based grouping, is the most efficient for our dataset. As we can note from Table 7 and Figure 3, even though we used only subsets of the overall dataset in the meta-actions based grouping, we extracted a higher number of rules with the highest support for the RC group in the later scheme. Furthermore, extracted rules have a higher average confidence as seen in Figure 2 than the second scheme. In addition, the average number of patients in each side effects based sub-groups is higher than the previous scheme and encompasses all patients for our dataset as seen in Figure 1. Grouping by meta-actions filtered all the noise, such as, patients that have the same initial state but different decision feature values then the ones applied in the extracted rules.

The reason for its efficiency is that meta-actions are the source of side effects, and are directly correlated to patients’ negative side effects when applied to them. In fact, in our dataset, expert physicians apply treatments (meta-actions) to patient, based on their pathological state, knowing their negative side effects on them.

6. Related Work

There have been several research efforts on action rules since their introduction by [1]. The first effort to mine action rules from scratch was done in [7]. However multiple action rules discovery techniques were presented in [9,10].

Actio rules can also be seen as a composition of two classification rules as described in [9], where the authors described how to compute the support and confidence of an action rule based on it’s two composing classification rules.

Meta-actions were first introduced in [11] as a higher level concepts used in modeling certain generalizations of actions rules. They were described either by an influence matrix or an antology as a set of value transitions in flexible attributes. Meta-action were formalized in [16], and used in a pruning process with tree classifiers to discover action rules. In [17], the authors show the cascadeing effect of meta-actions leading to a desired effects when generating association action rules and action paths. However, the previous work on meta-action neither studied the side effects of meta-actions nor the action rules personalization problem. In this paper we presented three grouping schemes aiming at discovering personalized action rules.

7. Conclusion

Actions rules are very important in modeling expert and domain knowledge. They were used in several domains including healthcare and music information retrieval. Action rules were augmented by the introduction of meta-actions that experts use to trigger them. In this paper, we studied the tinnitus handicap disease, and noted the importance of filtering negative side effects in applying treatments to patients. We then defined formally the negative side effects, and proposed to extract personalized action rules based on these side effects. We believe that expert physicians partition patients with the same pathological state based on their side effects response to treatments. Therefore, we proposed three grouping schemes with regards to negative side effects to extract patient’s personalized action rules. We also implemented the three grouping schemes and tested them on the Tinnitus handicap dataset. We further compared the three grouping schemes and discussed their advantages and disadvantages, and justified our choice to apply the meta-action based grouping scheme. We trust that personalization is a very important aspect in filtering noise that skilled experts face when making decisions.

REFERENCES