Finding Interesting Patterns Using User Expectations.
AbstractOne of the major problems in the field of knowledge discovery (or data mining) is the interestingness problem. Past research and applications have found that, in practice, it is all too easy to discover a huge number of patterns in a database. Most of these patterns are actually useless or uninteresting to the user. But due to the huge number of patterns, it is difficult for the user to comprehend them and to identify those interesting to him/her. To prevent the user from being overwhelmed by the large number of patterns, techniques are needed to rank them according to their interestingness. In this paper, we propose such a technique, called the user-expectation method. In this technique, the user is first asked to provide his/her expected patterns according to his/her past knowledge or intuitive feelings. Given these expectations, the system uses a fuzzy matching technique to match the discovered patterns against the user's expectations, and then rank the discovered patterns according to the matching results. A variety of rankings can be performed for different purposes, such as to confirm the user's knowledge and to identify unexpected patterns, which are by definition interesting. The proposed technique is general and interactive.
Introduction
In knowledge discovery, techniques are constantly being developed and improved for
discovering various types of patterns in databases. While these techniques were shown to be
useful in numerous applications, new problems have also emerged. One of the major problems
is that, in practice, it is all too easy to discover a huge number of patterns in a database. Most
of these patterns are actually useless or uninteresting to the user. But due to the huge number
of patterns, it is difficult for the user to comprehend and to identify those patterns that are
interesting to him/her. To prevent the user from being overwhelmed by the large number of
patterns, techniques are needed to rank them according to their interestingness.
So far, a number of papers have discussed the interestingness issue [e.g., 4, 8, 11, 12, 13, 14].
The main factors that contribute to the interestingness of a discovered pattern have also been
proposed. They include: coverage, confidence, strength, statistical significance, simplicity,
unexpectedness, actionability [e.g., 4, 8, 11, 12]. The first five factors are called objective
measures [15]. They can be handled with techniques requiring no application and domain
knowledge. They have been studied extensively in the literature [e.g., 12, 8]. The last two
factors are called the subjective measures [11, 15], which measure the subjective
interestingness of a pattern to the user. They are defined as follows:
1. Unexpectedness: Patterns are interesting if they are unexpected or previously unknown to
the user [4].
2. Actionability: Patterns are interesting if the user can do something with them to his/her
advantage [4,11].
It has been noted in [13, 11] that although objective measures are useful in many respects,
they are insufficient in determining the interestingness of the discovered patterns. Subjective
measures are needed. Subjective interestingness is the focus of this paper. The proposed
technique is for ranking the discovered patterns according to their subjective interestingness. It
assumes that some other techniques have performed the pattern discovery task and have
filtered out those patterns that do not meet the objective requirements.
To design a general ranking technique(s) using subjective interestingness measures is a difficult
task. Some of the reasons are: (1) in different domains (or applications), people are interested
in different things; (2) given the same database and the patterns discovered, different users
may be interested in different subsets of the patterns; (3) even for the same user, at different
points in time, his/her interests may also vary due to the specific situation he/she is in at the
particular moment. In order to identify and/or to rank the discovered patterns, it is obvious
that the system must have a great deal of knowledge about the database, the application
domain and the user's interests at a particular time.
To date a number of studies [e.g., 4, 8, 11, 12, 156] have been conducted on the subjective
interestingness issues and some systems have also been built [8, 11] with interestingness
filtering components to help users focus on the useful patterns. However, these systems mostly
handle the subjective interestingness in application/domain-specific fashions [15].
In this paper, we propose a general approach to determine the subjective interestingness
(unexpectedness and actionability) of a discovered pattern. The technique is characterized by
asking the user to specify a set of patterns according to his/her previous knowledge or
intuitive feelings. This specified set of patterns is then used by a fuzzy matching algorithm to
match and rank the discovered patterns. The assumption of this technique is that some amount
of domain knowledge and the user's interests are implicitly embedded in his/her specified
patterns. In general, we can rank the discovered patterns according to their conformities to the
user's knowledge or their unexpectedness, or their actionabilities. With such rankings, a user
can simply check the few patterns on the top of the list to confirm his/her intuitions (or
previous knowledge), or to find those patterns that are against his/her expectation, or to
discover those patterns that are actionable.
The proposed approach is simple, effective and highly interactive. Though we do not claim
that this technique solves the interestingness problem completely, we believe this is a major
step towards the right direction.
2. Problem Definition
From a user's point of view, he/she wants to find patterns from one or more databases,
denoted by D, that are useful or interesting to him/her. From a discovery system's point of
view, a technique Q is used to discover all the patterns from D that are discoverable by Q. Let
B (Q,D) be the set of patterns discovered by Q on D. We denote I (Q,D) as the set of interesting
patterns in B (Q,D) . Thus, I (Q,D) - B (Q,D) . Three points to be noted:
. I (Q,D) may not be the complete set of interesting patterns that can be discovered from D. It
is simply the set of interesting patterns that can be discovered by technique Q on D.
. Not all patterns in I (Q,D) are equally interesting. Different patterns may have different
degrees of interestingness to the user.
. I (Q,D) may be a dynamic set in the sense that the user may be interested in different things at
different points in time. The degree of interestingness of each pattern may also vary.
In general, B (Q,D) is much larger than I (Q,D) . This implies that many patterns discovered by Q are
uninteresting or useless. It is desirable that a system only gives the user the set of interesting
patterns, I (Q,D) , and ranks the patterns in I (Q,D) according to their degrees of interestingness.
Hence, we define the interestingness problem as follows:
Given B (Q,D) , the set of patterns discovered by Q on D, determine I (Q,D) and rank
the patterns in I (Q,D) according to their degrees of interestingness to the user at the
particular point in time.
In practice, this is difficult to achieve because the definition of interestingness is domain (or
application) dependent and also user and his/her situation dependent. To simplify our task, we
only rank all the patterns discovered (i.e., B (Q,D) ). Our assumption is that I (Q,D) will be a small
subset of the top-ranked patterns. The final identification task is left to the user.
So, how can a system know what is useful in a domain and what is considered interesting at a
particular moment to a user? What are the criteria used for ranking the discovered patterns?
We believe that our proposed technique is able to provide a partial answer to these problems.
3. The Proposed Technique
This section describes the proposed method. Slightly different procedures are used for finding
unexpected patterns and for finding actionable patterns.
3.1 Finding unexpected patterns and confirming user's knowledge
Patterns are unexpected if they are previously unknown to the user [4]. Unexpected patterns
are, by definition, interesting because they provide new information to the user [4, 15]. Apart
from finding unexpected patterns, sometimes the user also wishes to know whether his/her
existing knowledge about the database is correct. For these two purposes, the proposed
method has the following two steps:
1. The user is asked to provide a set of patterns E (with the same syntax as the discovered
patterns) that he/she expects to find in the database D based on his/her previous
knowledge or intuitive feelings. These user patterns are regarded as fuzzy patterns (also
called user-expected patterns), which are described with the help of fuzzy linguistic
variables [17].
A fuzzy linguistic variable is defined as a quintuple (x, T(x), U, G, ~
M ) in which x is the
name of the variable; T(x) is the term set of x; that is, the set of names of linguistic values
of x, with each value being a fuzzy variable denoted generally by x and ranging over a
universe of discourse U; G is a syntactic rule for generating the name, X, of values of x;
and M is a semantic rule for associating with each value X its meaning, ~
(X) which is a
fuzzy subset of U. A particular X is called a term.
For example, if speed is interpreted as a linguistic variable with its term
set T(speed) could be
moderate, fast, .
~
(X) gives a meaning to each term. For example, ~
M (slow) may be defined as follows:
~
where -slow u
slow (u) denotes the degree of membership of u in term slow.
Thus, in this step, the user needs to input (1) his/her expected patterns, and (2) the fuzzy
set ~
(X) for each term X used in his/her expected patterns.
2. The system then matches (in a number of ways) each discovered pattern in B (Q,D) against
the patterns in E using a fuzzy matching technique. The discovered patterns are then
ranked according to their degrees of match with E.
Note that, though the proposed technique is application/domain independent, it is not
discovery technique independent. This is because different knowledge discovery techniques
discover different types of patterns (e.g., classification patterns, association patterns, sequence
patterns, time series patterns, etc. For different pattern types, fuzzy pattern matching
methods may not be the same. For example, the matching technique for sequence patterns and
the matching technique for classification patterns (or rules) should be different.
In short, the matching algorithm must be customized for different pattern types. Thus, each
general discovery tool can have a suitable implementation of the proposed method, which may
be used for any domain and any application. Section 4 and 5 describe such an implementation.
Now let us consider an example of how the technique works. Suppose we have the following
set of discovered (classification) patterns from an accident database ("," denotes "and").
1. If P_Age > 50,
2. If P_Age > 65, killed
3. If P_Age > 50,
The user-specified expected pattern is:
Before matching can be performed, the system must know how to interpret the semantic
meanings of "OLD", "BAD_VISIBILITY" and "BAD_ACCIDENT." This is achieved by
asking the user to provide the fuzzy sets associated with these terms. A graphical user-interface
has been built to make this process of supplying the fuzzy sets easy and simple.
Having specified the semantic meanings, a matching algorithm is then executed to determine
the degrees of match between the discovered patterns and the user-specified expected pattern.
Different ranking algorithms are used for different purposes. If our purpose is to confirm a
hypothesis, the system will rank the discovered patterns such that the pattern with the highest
degree of match is ranked first. The results of such a ranking could be as follows:
A1. If P_Age > 65, killed
A2. If P_Age > 50,
A3. If P_Age > 50,
This confirms the user's belief that an old person involved in an accident at some bad location
will result in a serious injury. On the other hand, if our purpose is to find unexpected patterns
in the sense of an unexpected consequent, then a different ranking will result as shown below:
B1. If P_Age > 50,
B2. If P_Age > 65, killed
B3. If P_Age > 50,
This shows that pattern B1 is against the user's expectation because instead of a serious injury,
the old person suffers a slight injury. It is important to note that simply reversing of the order
for conformity is in general not the right method for ranking patterns according to their
unexpectedness. In fact, the unexpectedness of a pattern could be described in a number of
ways. Details on this will be discussed in Section 4.
From the example, we can see that by determining the degrees of match between the
discovered patterns and the user-specified expected patterns in various ways, and ranking the
patterns accordingly, it is possible to help the user focus on the appropriate subsets of patterns
based on his/her purpose.
It can also be observed that the working of this method depends on the following assumption.
Assumption: The user knows the database and has some intuitive feelings or previous
knowledge about the kinds of pattern that might be found in the database.
We believe this assumption is realistic because in real life, after working on a particular domain
and its database for some time, the user generally develops good intuitive sense regarding the
kinds of patterns that can be found in the database. We have tested this on our industrial
partner. Even if the user is new to the database, database visualization tools are available to
help the user obtain a good initial feel of the kinds of patterns in the database. With this as a
starting point, the user can then incrementally add more patterns to aid in the ranking process.
It is important to note, however, that this method does not require the user to provide the
complete set of his/her expected patterns at the beginning, which is quite difficult. Due to the
interactive nature of the technique, he/she may try something simple at the beginning and
slowly build up the set of expected patterns.
3.2 Finding actionable patterns
Patterns are actionable if the user can do something with them to his/her advantage [4, 11].
The key here is the usefulness to the user. It has been recognized that many unexpected
patterns are also actionable. Hence, the method presented above, in some sense, is also able to
find some actionable patterns. However, for specific cases in which the user knows what are
the possible actions that he/she can take and in what situations to take them, a variation of the
above method is proposed to identify actionable patterns. This method consists of three steps.
1. The user specifies all the possible actions Y that he/she (or his/her organization) can take.
2. For each action Y q - Y, the user specifies the situations under which he/she is likely to take
the action. The situations are represented by a set of fuzzy patterns Act q (similar to the
expected patterns in E). The patterns in Act q are called the user-specified action patterns.
3. The system then matches each discovered pattern in B (Q,D) against the patterns in Act q using
a fuzzy matching technique. The results of this matching are used to rank the discovered
patterns in B (Q,D) . For each action Y q (or Act q ), a separate ranking will be produced.
Note that:
. In finding actionable patterns, the user does not provide what he/she expects as for finding
unexpected patterns, but rather the situations under which he/she may take some actions.
These situations may or may not be what the user expects.
. This technique associates patterns with actions to be taken in response to the patterns.
Thus, more information is given to the user, i.e., not only the actionable patterns, but also
the actions to be taken.
Let us illustrate this method with an example. Considering the following discovered patterns:
1. If P_Age > 50,
2. If killed
3. If P_Age > 50,
In this example, we consider two actions:
Action 1. Educate people to be more careful at locations with good visibility. Assume there is
only one user-specified action pattern for which action 1 is to be taken:
If
Action 2. Install speed cameras at locations with bad visibility. Again assume there is only one
user-specified action pattern for which action 2 is to be taken.
If
With these and the user specified fuzzy sets for GOOD_VISIBILITY, BAD_VISIBILITY,
FAST, SLIGHT and BAD_ACCIDENT, the ranking results are:
Action 1: Rank 1 1. If P_Age > 50,
3. If P_Age > 50, T-junct then
Rank 3 2. If killed
Action 2: Rank 1 2. If killed
3. If P_Age > 50, T-junct then
Rank 3 1. If P_Age > 50,
This ranking helps the user to identifying those patterns supporting the actions. With this, the
user may decide to educate old people to be more careful, and/or to install speed cameras at
bends. Note that the actions themselves are not ranked according to the possible benefits they
may bring to the user, which will be more helpful. This will be part of our future work.
4. An Implementation of the Proposed Technique
In this and the next section, we will describe a particular implementation of the proposed
technique. The patterns assumed in this implementation is as follows:
If
where "," means "and", and P i is a proposition of the following format:
attr OP value
where attr is the name of an attribute in the database, and value is a possible value for the
attribute attr and OP -} is the operator.
C is the consequent, which has the same format as P i . However, its attr does not have to be an
attribute name in the database. For example, in the C4.5 system [14], Class is used for the
consequent. The above representation is very common for classification patterns (rules) and
association patterns. We now present the computational formulas used in the methods
discussed in Section 3.1 and 3.2.
4.1. Confirming user knowledge and finding unexpected patterns
Before presenting the detailed computation, we first define some notations. Let E be the set of
user-expected patterns and B (previously B (Q,D) ) be the set of discovered patterns. We denote
W i as the degree of match of a discovered pattern with respect to the set of expected
patterns E. We denote w (i,j) as the degree of match between a discovered pattern and an
expected pattern Ranking of the discovered patterns is performed by sorting them in a
decreasing order according to their W i (i.e., the pattern with the highest W i will be on top). Let
us now discuss the computation of w (i,j) and W i . w (i,j) is computed in two steps:
1. Attribute name match - The attribute names of the conditions of B i and E j are compared.
The set of attribute names that are common to both the conditions of B i and E j is denoted
as A (i,j) . Then, the degree of attribute name match of the conditional parts, denoted as L (i,j) ,
is computed as follows:
| |
max(| | , | |)
where |e j | and |b i | are the numbers of attribute names in the conditional parts of E j and B i
respectively, and |A (i,j) | is the size of the set A (i,j) .
Likewise the attribute names of the consequents of B i and E j are also compared. R (i,j)
denotes the degree of match for the consequent parts. R (i,j) is either 0 or 1. This is because
we assume that there is only one consequent for each pattern. Hence, either the
consequent attributes of the two patterns are the same (R different (R
For example, we have
underweight.
fit.
The set of common attributes in the conditional parts is A {Weight}. The consequent
parts have the same attribute Health_con. Hence,
2. Attribute value match - Once an attribute of B i and E j matches, the two propositions are
compared taking into consideration both the attribute operators and attribute values. We
denote V (i,j)k the degree of value match of the kth matching attribute in A (i,j) , and Z (i,j) the
degree of value match of the consequents. The computation of the two values will be
presented in the next section.
Here, we present the computation of w (i,j) and W i . As mentioned in Section 3, the proposed
method can be used for confirming user's hypothesis and also for finding unexpected patterns.
For these two purposes, different formulas are used for computing w (i,j) and W i . Note that we
do not claim these formulas are optimal. But a large number of experiments have shown that
they produce rankings that closely model human intuition of subjective interestingness.
1. Confirming user's knowledge
A
A
A
| |
| |
| |
A
- computes the degree of match of the conditional parts of B i
- computes the degree of match of the consequent parts of B i and E j .
w (i,j) gives the degree of match of pattern B i with pattern E j .
The formula for computing W i , which is the degree of match of the discovered pattern B i
with respect to the set of expected patterns E, is defined as follows (see also Figure 1):

Figure

1. Computing W i
2. Finding unexpected patterns
For this purpose, the situation is more complex. We can have a number of ways to rank
the patterns according to the types of unexpectedness.
Unexpected consequent: The conditional parts of B i and E j are similar, but the
consequents of the two patterns are far apart. Two types of ranking are possible
depending on the user's interest.
(a) Contradictory consequent (patterns with R will be ranked higher).
A
R Z A
R Z A
| |
| |
| |
1 0Explanation: Since this ranking is to find those patterns whose conditional parts
are similar, but the consequents are contradictory, we need to give higher w (i,j)
value for B i whose consequent part has the same attribute name as
the expression R Z
.
W i is computed as follows:
(b) Unanticipated consequent (patterns with R will be ranked higher).
A
R Z A
R Z A
a
| |
| |
| |
A
R Z A
A
| |
| |
| |
Explanation: A higher value is given to w a(i,j) when the attribute names of the
consequent parts of B i and E j do not match. However, B i may match well with
another expected pattern E r . Thus, w b(i,j) is needed to take this into
consideration.
W i is computed as follows:
Unexpected reason: The consequents are similar but the conditional parts of B i and
are far apart. Again two types of ranking are possible.
(a) Contradictory conditions (patterns with |A (i,j) | > 0 will be ranked higher)
A
A
R Z A
| |
| |
| |
1 0Explanation: Since this ranking is to find those patterns whose consequents match
well, but the conditional parts are contradictory, we need to give a higher w (i,j)
value for B i whose conditional part has good attribute name match with E j .
Therefore, we have the expression L
A
|
is computed as follows:
(b) Unanticipated conditions (patterns with |A (i,j) will be ranked higher)
A
A
R Z A
a
| |
| |
| |
A
A
A
| |
| |
| |
Explanation: A higher value is given to w a(i,j) when the attribute names of the
conditional parts of B i and E j do not match well. However, B i may match well
with another expected pattern E r . Thus, w b(i,j) is needed to take this into
consideration.
W i is computed as follows:
Totally unexpected patterns: Both conditional and consequent parts of B i and E j are
very different in the sense that the attribute names in B i are unexpected.
A
R Z A
R Z A
| |
| |
Explanation: Since this ranking is to find those patterns whose attribute names (both
in the conditional parts and consequent parts) have little (or no) intersection with
the set of attribute names mentioned in E, we give higher w (i,j) value for B i whose
attribute names do not match well with those of E j .
W i is computed as follows:
4.2 Finding actionable patterns
For finding actionable patterns, the notations in Section 4.1 still apply except E, which is
replaced with Act q . The formula for matching the discovered pattern B i and the user-specified
action pattern Act q
Act q is the same as the one for confirming user's knowledge in Section
4.1. However, the computation of Z (i, are slightly different from those used in
Section 4.1, which will be discussed in the next section.
A
A
A
| |
| |
| |
Explanation: The matching formula for conformity is used because the purpose of matching
here is the same as the matching for confirming the user's knowledge.
We denote W (i,q) as the degree of match of B i with respect to the set of action patterns Act q .
W (i,q) is computed as follows:
The discovered patterns in B are ranked for each action Y q - Y according to their W (i,q) values.
5. Fuzzy Matching of Attribute Values
We now discuss how to compute V (i,j)k and Z (i,j) . For this computation, we need to consider
both the attribute values and the operators. In addition, the attribute value types (discrete or
continuous) are also important. Since the computations of V (i,j)k and Z (i,j) are the same, it
suffices to just consider the computation of V (i,j)k , the degree of match for the kth matching
attribute in A (i,j) . Two cases are considered: the matching of discrete attribute values and the
matching of continuous attribute values.
5.1. Matching of discrete attribute values
In this case, the semantic rule for each term (X) used in describing the user-specified patterns
must be properly defined over the universe (or domain) of the discrete attribute. We denote U k
as the set of possible values for the attribute. For each u - U k , the user needs to input the
membership value of u in X, denoted as -X(u). In the discrete case, the formulas for computing
V (i,j)k and Z (i,j) for finding unexpected patterns and for finding actionable patterns are the same.
Let us have a example. The user gives the following pattern:
reject
Here, poor is a fuzzy term. To describe this term, the user needs to specify the semantic rule
for poor. Assume the universe (or domain) of the discrete attribute
The user may specify that "poor" grade means:
{(F, 1), (D, 0.8), (C, 0.2)}
where the left coordinate is an element in the universe (or domain) of the "Grade"
attribute, and the right coordinate is the degree of membership of that element in the fuzzy
set poor, e.g., - poor (D) = 0.8. It is assumed that all the other attribute values not mentioned
in the set have the degree of membership of 0.
When evaluating the degree of match for V (i,j)k , two factors play an important role, namely, the
semantic rules associated with the attribute value descriptions and the operators used in the
propositions. In the discrete case, the valid operators are "=" and "-". Suppose that the two
propositions to be matched are as follows:
User-specified proposition: attr Opu X
System-discovered proposition: attr Ops S
where attr is the matching attribute, Opu and Ops belong to the set {=, -}, and X and S are
the attribute values of attr. Since the matching algorithm must take into consideration the
combination of both the operators and attribute values, four cases result:
Case 1.
Case 2.
U
| |
support
| is the size of U k . If |U k | -
"-" is not possible.
Case 3.
- .
Case 4.
U
| |
support,
possible.
5.2. Matching of continuous attribute values
When an attribute takes continuous values, the semantic rule for the term (X) takes on the
form of a continuous function. To simplify the user's task of specifying the shape of this
continuous function, we assume that the function has a curve of the form as shown in Figure
2. Thus, the user merely needs to provide the values for a, b, c, and d.
a b c d1

Figure

2. Membership function
For example, the user's pattern is:
Here, young is a term for variable Age. Suppose that in this case Age takes continuous values
from 0 to 80. The user has to provide those 4 points using the values from 0 to 80. For
example, the user may give
In the continuous case, the set of values that the operator in a proposition can take is {=, -,
-" is used to represent a range like this: . With this expansion, the
total number of possible combinations to be considered is 25. All the formulas are listed in
appendix.
In this continuous case, the formulas used for finding unexpected patterns (Section 4.1) and
for finding actionable patterns (Section 4.2) are slightly different. The difference is that for
finding unexpected patterns, it compares two propositions to see how different they are. But,
for finding actionable patterns, it checks to see whether the proposition used in the discovered
pattern is covered by the proposition used in the user-specified pattern or vice versa. For
example, we have
User-specified proposition: A - 5
System-discovered proposition:
For the fuzzy term 5 (in A - 5), assume 5. In the case of finding unexpected
patterns, V (i,j)k will be evaluated to be less than 1 because the two propositions do not cover
the same area. However, in the case of finding actionable patterns, V
6. Evaluation
The proposed technique is implemented in Visual C++ on PC. A test example is given below.
An analysis of the complexity of the algorithm is also presented.
6.1. A test example
This sub-section gives a test example. The set of patterns is generated from a real database
using C4.5. All the attribute names and also some attribute values have been encoded to
ensure confidentiality of the data. Since for pattern generation in this test we used C4.5, which
generates classification patterns and uses only one attribute as the class (or as the consequent),
we cannot test the rankings for unanticipated consequent and totally unexpected patterns. To
save space, only a small subset of the patterns generated by C4.5 is listed below for ranking.
-> Class NO
Pattern 2: A1 <= 49, A3 <= 5.49, A4 >
-> Class NO
Pattern 3: A1 > 49,
-> Class YES
Pattern 4: A1 > 49, A1 <= 50
-> Class YES
Pattern 5: A1 > 55
-> Class YES
Pattern
-> Class YES
Pattern 7: A1 > 41, A4 <=
-> Class YES
Pattern 8: A1 > 41, A1 <= 47, A3 <= 3.91, A7 > 106, A4 > 60, A10 <= 5.06
-> Class YES
Three runs of the system are conducted in this testing. In the first run, the focus is on
confirming the user's knowledge, while in the second run the focus is on finding unexpected
patterns. In the third run, the focus is on finding actionable patterns.
6.1.1 Confirming user's knowledge
The set of user expected patterns is listed below with the fuzzy set attached to each term
(attribute value used in the user's patterns).
User expected pattern set 1:
-> Class NO {(NO, 1), (YES, 0)}
Pattern 2: A1 >= Re_A1
-> Class YES {(NO, 0), (YES, 1)}
. Ranking results:
-> Class YES
confirming user specified pattern 2
-> Class NO
confirming user specified pattern 1
-> Class YES
confirming user specified pattern 2
-> Class YES
confirming user specified pattern 2
2:
-> Class NO
confirming user specified pattern 1
The rest of the patterns are cut off because of their low matching values.
6.1.2 Finding unexpected patterns
The set of user expected patterns for this test run is listed below, which is followed by three
types of ranking for finding unexpected patterns.
User expected pattern set 2:
-> Class YES {(NO, 0), (YES, 1)}
Pattern 2: A3 >= 2
-> Class YES {(NO, 0), (YES, 1)}
. Unexpected consequent:
2:
-> Class NO
contradicting user specified pattern 2
The rest of the patterns are cut off because of their low matching values.
. Contradictory conditions:
-> Class YES
contradicting user specified pattern 1
-> Class YES
contradicting user specified pattern 1
-> Class YES
contradicting user specified pattern 1
The rest of the patterns are cut off because of their low matching values.
. Unanticipated conditions:
-> Class YES
-> Class YES
-> Class YES
-> Class YES
The rest of the patterns are cut off because of their low matching values.
6.1.3 Finding actionable patterns
For simplicity, we use only two actions. One action has one user-specified action pattern,
while the other has two. Due to the confidentiality, we cannot provide the real actions, but use
First_Action, and Second_Action to represent them.
User's actions and patterns:
Action 1: First_Action
User patterns: Pattern 1: A1 >= Re_A1
-> Class YES {(NO, 0), (YES, 1)}
Action 2: Second_Action
User patterns: Pattern 1: A3 >= 2
-> Class YES {(NO, 0), (YES, 1)}
Pattern 2: A7 >= 150
-> Class YES {(NO, 0), (YES, 1)}
. Ranking results:
Action 1: First_Action
-> Class YES
actionable according to user-specified pattern 1.
-> Class YES
actionable according to user-specified pattern 1.
-> Class YES
actionable according to user-specified pattern 1.
-> Class YES
actionable according to user-specified pattern 1.
The rest of the patterns are cut off because of their low matching values.
Action 2: Second_Action
-> Class YES
actionable according to user-specified pattern 2.
-> Class YES
actionable according to user-specified pattern 2.
The rest of the patterns are cut off because of their low matching values.
6.2 Efficiency analysis
Finally, let us analyze the runtime complexity of the proposed technique. Here, we only
analyze the algorithm for finding unexpected patterns. For finding actionable patterns, the
basic algorithm is the same. Assume the maximal number of propositions in a pattern (a user-
expected pattern or a discovered pattern) is N. Assuming the attribute value matching
(computing V (i,j)k and Z (i,j) ) takes constant time. Combining the individual matching values to
calculate w (i,j) also takes constant time. The computation of W i is O(|E|). Then, without
considering the final ranking which is basically a sorting process, the worst-case time
complexity of the technique is O(|E||B|N 2 ).
7. Related Work
Although the interestingness has long been identified as an important issue in data mining [4],
most of the data mining techniques and tools do not deal with this problem. Instead, their
primary concern is to discover all the patterns in the given databases [4, 11, 15].
To date, some studies have been performed on the interestingness problem [1, 4, 8, 11, 12, 13,
15]. A number of interestingness measures have also been proposed. These measures can be
classified into two classes: objective measures and subjective measures. Objective measures
typically involve analyzing the discovered patterns' structures, their predictive performances,
and their statistical significance [4, 8, 12]. Examples of objective measures are: coverage,
certainty factor, strength, statistical significance and simplicity [3, 6, 8, 11].
It has been noted in [11], however, that objective measures are insufficient for determining the
interestingness of the discovered patterns. Subjective measures are needed. Two main
subjective measures are: unexpectedness, and actionability [4, 11].
[8] defined pattern interestingness in terms of performance, simplicity, novelty, significance,
etc. Most of the measures are objective measures with the exception of novelty. However, no
general method was proposed for handling novelty. Instead, domain-specific theories are
coded to aid in filtering out the uninteresting patterns.
[11] studied the issue of interestingness in the context of a health care application. A
knowledge discovery system, KEFIR, is built. The system analyzes health care information to
uncover "key findings". Key findings refer to the important deviations from the norms for
various indicators such as cost, usage, and quality. The degree of interestingness of a finding is
estimated by the amount of benefit that could be realized if an action can be taken in response
to the finding. Domain experts provide the recommended actions to be taken for various types
of findings. Once a finding is discovered, the system computes the estimated benefit for taking
an recommended action.
The method used in KEFIR presents a good approach for incorporating the subjective
interestingness into an application system. However, the approach is application specific. Its
domain knowledge (from domain experts) is hard-coded in the system as production rules.
The system cannot be used for any other application. In contrast, our method is general. It
does not make any domain-specific assumptions. A pattern analysis system based on our
technique can be attached to each data mining tool to help the user identify the interesting
patterns. Though domain-specific systems such as KEFIR are still the most effective method
for ranking patterns and actions, the cost of building such a system is very high.
[15] proposed to use probabilistic beliefs and belief revision as the framework for describing
subjective interestingness. Specifically, a belief system is used for defining unexpectedness. A
belief is represented as an arbitrary predicate formula. Associated with each belief is a
confidence measure. Two types of beliefs are presented, hard and soft beliefs. Basically, hard
beliefs cannot be changed even in the face of new evidences, while soft beliefs are modifiable
when a new evidence arrives. If a pattern contradicts the hard beliefs of the user, then this
pattern is unexpected and interesting. The unexpectedness of a pattern is also defined with
respect to a soft belief. However, [15] is just a proposal. No system has been implemented that
utilizes this approach. For an actual implementation, a great deal of details have to be studied.
[15] also does not handle pattern actionability. Our proposed approach has been implemented
and tested. In addition, our approach allows the user to specify his/her beliefs (expectations) in
fuzzy terms which are more natural and intuitive than complex conditional probabilities that
the user has to assign in [15].
8. Conclusion
In this paper, we study the subjective interestingness issue in data mining from a domain
independent perspective. A general method for ranking the discovered patterns according to
their interestingness is proposed. An particular implementation has also been done. This
method is characterized by asking the user to input his/her expected or action patterns and
then the system ranks the discovered patterns by matching them against the expected or the
action patterns. This method can be used to confirm user's knowledge, to find unexpected
patterns, or to discover actionable patterns. Besides these applications, the proposed technique
may also be used to discover interesting trends by periodically analyzing the deviations of the
newly discovered patterns against the old patterns. This can be done simply by using the old
patterns as the user-specified patterns.
The proposed method is simple and effective. It is also highly interactive and allows the user
to identify interesting patterns incrementally. We do not claim, however, that the issues
associated with interestingness are fully understood. Much further research is still needed, e.g.,
we still do not have a good understanding of how objective interestingness measures such as
coverage and confidence interact with subjective interestingness measures, and how actions
themselves may be ranked to give the user more information.

Acknowledgment

We would like to thank Gui-Jun Yang for implementing the user interface of
the system. We thank Hwee-Leng Ong and Angeline Pang of Information Technology Institute for
many useful discussions. The project is funded by National Science and Technology Board.



--R

Database mining: a performance perspective.
Attribute focusing: machine-assisted knowledge discovery applied to software production process control

Knowledge discovery in databases: an overview.
Data driven discovery of quantitative rules in relational database.
Incremental disocvery of rules and structure by hierachical and parallel clustering.
Problems for knowledge discovery in databases and their treatment in the statistics interpreter explora.
Selecting among rules induced from a hurricane database.
Systems for knowledge discovery in databases.
An application of KEFIR to the analysis of healthcare information.
The interestingness of deviations.



On subjective measures of interestingness in knowledge discovery
Learning useful rules from inconclusive data.
Fuzzy set theory and its applications.
--TR

--CTR
Saroj Saroj , K. K. Bharadwaj, A parallel genetic algorithm approach for automated discovery of censored production rules, Proceedings of the 25th conference on Proceedings of the 25th IASTED International Multi-Conference: artificial intelligence and applications, p.435-441, February 12-14, 2007, Innsbruck, Austria
Bing Liu , Wynne Hsu, Domain knowledge to support the discovery process: previously discovered knowledge, Handbook of data mining and knowledge discovery, Oxford University Press, Inc., New York, NY, 2002
Bing Liu , Wynne Hsu, Domain knowledge to support the discovery process: user preferences, Handbook of data mining and knowledge discovery, Oxford University Press, Inc., New York, NY, 2002
Shichao Zhang , Feng Chen , Xindong Wu , Chengqi Zhang, Identifying bridging rules between conceptual clusters, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
Kaidi Zhao , Bing Liu , Jeffrey Benkler , Weimin Xiao, Opportunity map: identifying causes of failure - a deployed data mining system, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
Sugato Basu , Raymond J. Mooney , Krupakar V. Pasupuleti , Joydeep Ghosh, Evaluating the novelty of text-mined rules using lexical knowledge, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.233-238, August 26-29, 2001, San Francisco, California
B. Shekar , Rajesh Natarajan, A Framework for Evaluating Knowledge-Based Interestingness of Association Rules, Fuzzy Optimization and Decision Making, v.3 n.2, p.157-185, June 2004
Richard J. Bolton , Niall M. Adams, An iterative hypothesis-testing strategy for pattern discovery, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
Bing Liu , Kaidi Zhao , Jeffrey Benkler , Weimin Xiao, Rule interestingness analysis using OLAP operations, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
Phan , Le-Minh Nguyen , Yasushi Inoguchi , Tu-Bao Ho , Susumu Horiguchi, Improving discriminative sequential learning by discovering important association of statistics, ACM Transactions on Asian Language Information Processing (TALIP), v.5 n.4, p.413-438, December 2006
Liqiang Geng , Howard J. Hamilton, Interestingness measures for data mining: A survey, ACM Computing Surveys (CSUR), v.38 n.3, p.9-es, 2006
Stephen D. Bay , Michael J. Pazzani, Detecting Group Differences: Mining Contrast Sets, Data Mining and Knowledge Discovery, v.5 n.3, p.213-246, July 2001
pattern ranking;interesting patterns;post-analysis of patterns;knowledge discovery;unexpectedness