Traditional framework for mining association rules has pointed out the derivation of many redundant rules. In order to be reliable in a decision making process, such discovered rules have to be both concise and easily understandable for users, and/or an input to visualization tools. In this paper, we present a 3 graphical visualization prototype for handling generic bases of association rules. We discuss also the most adequate graphical visualization technique depending on the intrinsic structure of the generic bases of association rules. An interesting feature of the prototype is that it provides a ”contextual” exploration of such rule set. Such additional displayed knowledge, based on the discovery of fuzzy metarules, enhances man-machine interaction by emulating a cooperative behavior.
Modern hardware and database technology has made it possible to store gigabytes of
information in databases. However, this rapid digitalization has pointed out an important
need for tools and/or techniques to delve and efficiently discover valuable, non-obvious
information from large databases. Data mining has been proposed and studied to help
users better understand and analyze the information. Much research in data mining from
large databases has focused on the discovery of association rules [
The problem of the relevance and usefulness of extracted association rules is of primary importance. Indeed, in most real life databases, thousands and even millions of high-confidence rules are generated, among which many are redundant.
Various techniques are used to limit the number of reported rules, starting by basic
pruning techniques based on thresholds for both the frequency of the represented pattern
and the strength of the dependency between antecedent and conclusion. This pruning
can be based on patterns defined by the user (user-defined templates), on boolean
operators [
More advanced techniques that produce only a limited number of the entire set
of rules rely on closures and Galois connections [
In this paper, we are interested in the most used kind of of visualization categories
in data mining, i.e., use visualization techniques to present the information catched out
from the mining process. Visualization tools became more appealing when handling
large data sets with complex relationships, since information presented in the form of
images is more direct and easily understood by humans. Visualization tools allow users
to work in an interactive environment with ease in understanding rules. In a
basedtabular view of association rules, all strong rules are represented as in a tabular
representation format (rule table), in which each entry corresponds to a rule. All rules can
be displayed in different order, such as order by premise, conclusion, support or
confidence. This helps users to have a clearer view of the rules and locate a particular rule
more easily. The tabular view is advocated for representing a large number of rules with
varied length. As a drawback, tabular-based technique draws heavily on ”boring”
logical inference that a user should perform, and is not suitable for visualizing rules from
different aspects. For example, if a user is interested in a comprehensive view of the
relationship between rules and items. In this case, the tabular view is not very convenient,
since an item repetitively appears in the rule table as long as it is contained by a rule.
These facts underline the importance of graphical rule visualization tools, permitting
a clearer and more user-friendly view of rules and items. Indeed, visual representation
has the capability of shifting load from the user’s cognitive system to the perceptual
system [
In this paper, we are interested in presenting a graphical-based visualization prototype for handling generic bases of association rules. We try to find an answer to the following question : ”Which is the most adequate visualisation technique depending on the intrinsic structure of generic bases of association rules, specially as their sizes is by far lower than the set of all (redundant) association rules”? As we will show later, 3D histograms-based technique is particularly advocated for visualizing generic bases extracted from sparse contexts. While, 2D matrix-based technique is indicated to visualize generic bases extracted from dense contexts.
An interesting feature of the aforementioned prototype is that it provides a
”contextual” exploration of such rule set. Indeed, additional information are provided to a user
selecting a given displayed rule :
1. All the derivable rule are displayed. To derive such rules, we use the set of inference
axioms, that we introduced in [
The remainder of this paper is organized as follows. Section 2 sketches briefly the mathematical background for the extraction of generic bases of association rules. In section 3, we present the process of the extraction of fuzzy association meta-rules. Then we discuss in depth in section 4 the opportunity of the rule set contextual exploration. Section 5 concludes this paper and points out future research directions. 2
In the following, we recall some key results from the Galois lattice-based paradigm
in FCA and its applications to association rules mining. A formal context is a triplet
K = (O, A, R), where O represents a finite set of objects (or transactions), A is a finite
set of attributes and R is a binary relation (i.e., R ⊆ D × T ). Each couple (o, a) ∈ R
expresses that the transaction o ∈ O contains the attribute a ∈ A. We define two
functions that map sets of objects to sets of attributes and vice versa. Thus, for a set
O ⊆ O, we define φ(O) = {a | ∀o, o ∈ O ⇒ (o, a) ∈ R}; and for A ⊆ A,
ψ(A) = {o | ∀a, a ∈ A ⇒ (o, a) ∈ R}. Both functions φ and ψ form a Galois
connection between the respective power sets P( ) and P(O) [
Frequent closed itemset: An itemset A ⊆ A is said to be closed if A = ω(A), and is said to be frequent with respect to minsup threshold if support(A) = |ψ(A)| ≥ |O| minsup. An itemset g ⊆ A is called minimal generator of a closed itemset A, if and only if ω(g) = A and @g0 ⊆ g such that ω(g0) = A.
Iceberg Galois lattice: When only frequent closed itemsets are considered with set inclusion, the resulting structure (Lˆ, ⊆) only preserves the joint operator. In the remaining of the paper, such structure is referred to ”Iceberg Galois Lattice”.
With respect to [
For example, let us consider the transaction database given by Table 1 (Left). The
set of extracted closed itemsets, with their associated minimal generators, is depicted
by Table 1 (Right). Therefore, Table 2 yields, respectively, the set of generic exact
association rules and the set of approximative association rules that it may be possible
to derive for minsup=1.
Fuzzy Sets : Let U be a finite classical set of objects, called universe of discourse. A
fuzzy set Fe, in a universe of discourse U , is characterized by a membership function
μFe: U → [
In the following, the notion of fuzzy extraction context, made up of objects and attributes, related under a fuzzy type-1 relation, is formalized.
Fuzzy extraction context :A fuzzy extraction context is a triple De=(O,Ie,R) dee scribing a finite set O of objects, a fuzzy finite set Ie of database items (or descriptors) α and a fuzzy binary relation Re (i.e.,Re ⊆ O × Ie). Each couple (o, i) ∈ Re, denotes that the object o ∈ O, has the item i ∈ Ie, at least with a degree α.
Fuzzy Galois connection: Let De = (O, Ie, Re) be a fuzzy extraction context. For
X ⊆ O and Ye ⊆ Ie, the functions : φe : P (O) → P(Ie) and ψe : P(Ie) → P (O) are
defined as follows [
α φe(X) = {b| α = min{μR(a, b) | a ∈ X}},
e ψe(Ye ) = {a ∈ O | ∀b, b ∈ Be ⇒ μR(a, b) ≥ μY (b)}
e e
The fuzzy operator φe is applied on a crisp set of objects and determines to which degree each property is satisfied by all objects, according to their respective degrees. Note that φe, as defined formerly, presents a desired abstraction vocation. Indeed, the retrieved fuzzy set is the least generalization, through the ”min” function, of all fuzzy sets (or descriptions) associated respectively to the input set objects.
Similarly, the fuzzy operator ψe is applied on a set of properties, represented by a
fuzzy set, and determines to which degree each object satisfies all of them. The implicit
use of the Rescher-Gaines fuzzy implication permits to obtain the desired interpretation
effect. Hence, the operator ”≥” permits to filter only objects fulfilling the constraint that
the associated descriptions are more general than the input description.
Remark 1. It is noteworthy that the proposed definition of fuzzy Galois connection
without context transformation- can not be unique. This constatation is due to the
existence of multitude of semantic/syntactic parameters to take into account in any
extension to the fuzzy context (e.g., fuzzy implication choice). For instance, we
mention based-Lukasiewicz-implication propositions of Belohlavek [
The FARD [
The algorithm traverses iteratively the search space in a level-wise manner. During each iteration corresponding to a level, a set of candidate patterns is created by joining frequent patterns discovered during the previous iteration, the supports of all candidate patterns are counted and infrequent ones are discarded. Fuzzy association rules are generated in two successive steps:
As input the FARD algorithm takes a fuzzy extraction context De, minsup and minconf. In this paper, we consider that the fuzzy extraction context D is constituted as e follows: De = (O, RS, Rb), where O represents the finite set of objects, RS is a finite set of GE R and GAR and Rb is a fuzzy binary relation, where μRb (o, R) = conf (R), ∀ o ∈ O and R ∈ {GE R ∪ GAR}.
Following the general principle of a level-wise algorithm, the FARD algorithm performs in each iteration the following two steps (assuming that items are sorted in a lexicographic order): 1. Construction step: The GEN-CLOSED function, is applied to each generator in CFuFCi, determining its support and possibly its closure (if it is frequent enough). This set is pruned with respect the anti-monotonous constraint, through the minsup threshold. 2. Pruning step : The set of generators to be utilized in the next iteration, i.e. CFuFCi+1, is computed by applying the GEN-NEXT function to the set CFuFCi.
The algorithm terminates when there are no more generators to process, i.e. CFuFCi.genlist, is empty. FARD algorithm pseud-code is given in Algorithm 1.1. Note that subroutines pseudo-code is not given due to lack of available space.
Input: De : fuzzy extraction context, Se:items user-constraints, minsup Output: FuFC= ∪i FuFCi begin
CFuFC1.gen-list={1-fuzzy itemsets}; for (i = 1;CFuFCi.gen-list6= ∅;i++) do
CFuFCi.clos= ∅; FuFCi=GEN-CLOSED(CFuFCi);
CFuFCi+1=GEN-NEXT(FuFCi); end
return FuFC=∪iFuFCi Example 1. Let us consider the fuzzy extraction context depicted by Table 3. In this α context, each (Ri, j) couple means that the object j is covered by the rule Ri with a confidence equal to α. From such context, by applying the FARD algorithm, it is possible to extract the fuzzy closed itemsets from which we derive fuzzy generic exact fuzzy association rules, which are depicted by Table 4. Let us keep in mind that given a generic association rule set, we aim to set up a graphical visualization prototype permitting to enhance the man-machine interaction by providing a contextual ”knowledge”, minimizing a boring large amount of knowledge exploration. To do so, we construct a set of fuzzy meta-rules, where both premise and conclusion rule’s are made up of classical association rules. The role of such fuzzy meta-rules is to highlight ”connections” between association rules without loosing rule’s confidence information.
Here we come to a turning point: Why is it interesting to try to understand why a
user and/or a knowledge expert may be interested in a particular rule, and to determine
what interesting information or knowledge, not explicitly requested, we could provide
him, in addition to the proper answer? Indeed, improving man-machine interaction by
emulating a cooperative behavior has been proposed by some researchers through
various techniques [
The visualization prototype takes as input an XML file complying to the DTD depicted by Figure 1. This storing format is argued by the fact that XML, the eXtensible Markup Language, has recently emerged as a new standard for data representation and exchange on the Internet. As output, the set of selected rules can be saved in a file with HTML or TXT format. <?xml version="1.0" encoding="ISO-8859-1"?> <!DOCTYPE ruleSet[ <!ELEMENT ruleSet (rule+)> <!ELEMENT rule (premise, conclusion,listObjects?)> <!ELEMENT premise (item+)> <!ELEMENT conclusion (item+)> <!ELEMENT listObjects #PCDATA> <!ATTLIST rule id ID #REQUIRED> <!ATTLIST rule conf CDATA #REQUIRED > <!ATTLIST premise id ID #REQUIRED> <!ATTLIST premise deg CDATA #REQUIRED > ] >
In the prototype interface, c.f., Figure 2(Up), the user can select items that can both appear in the premise and/or the conclusion part. Once the minsup and minconf thresholds are fixed, the user can generate the desired rules. Both textual and graphical representation are provided. The user can further filter specific rules from the generated ones.
The suitable visualization technique: In the 3D histograms based visualization technique, c.f., the screenshot depicted by Figure 2(Middle), matrix floor rows represent items and columns represent item associations. The red and blue blocks of each column (rule) represent the premise and the conclusion, respectively. Item identities are shown along the right side of the matrix. The associated confidence and support are represented by a scaled histogram. While on 2D matrix-based visualization technique, rule premise items are on one axis, and the rule conclusion items are on the other axis. We use the solution introduced by MineSet software 4 allowing multiple items in rule premise
or conclusion, by grouping each of the items combinations in rule premise or rule
conclusion as one unit. The confidence value is indicated by different colors. The higher
the confidence value is, the darker the color. Currently, the user has to indicate which
visualization technique he (she) prefers. However, we are trying to set up an automatic
indicator which can choose the most adequate visualization technique depending on
an assessment of the density of the extraction context. In fact, as indicated by
experimental experiments on real-life and synthetic extraction contexts whose parameters are
summarized by Table 5, when the extraction context is dense, generic association rules
drawn from such context tend to present large conclusions (depending on the number of
items). Indeed in Table 6, we tried to assess, for multiple minsup values, the difference
between the size of the minimal generator and the average size of its associated frequent
closed itemsets. the larger the difference is, the larger the generic conclusion’s
association rule part. From the entries dedicated to dense extraction contexts in Table 6, we
remark that this difference is important comparatively to that pointed out in by sparse
contexts. Therefore, when we consider sparse extraction contexts, the length of premise
and the length of the conclusion of generic association rule tend to be equal. Then given
that it is known, 3D histograms visualization technique is adapted to visualize rules with
a small number of items in the conclusion part, we can conclude it is better to use them
for generic rules extracted from sparse contexts.
5 The syntactic derivation is based on the Cover operator introduced in [
T10I4D100 T10I10D100
option, then the system provides only all the derivable rules that have exactly the same support and confidence values as those of the generic association rule used to derive them. As depicted in Figure 3, only one rule, k⇒a, is derivable and has exactly the same support and confidence as k⇒ae. – Displaying connected rules: This option is currently under implementation and we will illustrate it through an example. Suppose that a user may be interested in rule the R1. Then, when the user clicks on R1, the visualization interface provides all rules that are connected to R1 in a displaying area. From the meta-rule MR1 depicted in Table 4, we can check that the following rules are connected to R1: R3 : e⇒k (conf.=1), R11 : k⇒e (conf.=0.8), R12 : k⇒ae (conf.=0.4) and R14 : k⇒ceg (conf.=0.5). 5
In this paper, we presented an approach for providing a cooperative exploration of generic bases of association rules. This additional knowledge highlighting connected rules to a user-select rules allows an improvement of man-machine interaction. To do so, we constructed a set of fuzzy meta-rules extracted from the discovered fuzzy closed itemsets.
The visualization prototype is currently under implementation and in the near
future, we plan also to include recommended visualization tasks, e.g., history and
extract [
Acknowledgments The authors would like to thank Mrs LEGROY Audrey for its helpful efforts in the implementation of visualization prototype.