Julien Blanchard

Bruno Pinaud

Pascale Kuntz

Fabrice Guillet

A 2D-3D visualization support for human-centered rule-mining

Keywords: knowledge discovery in databases, association rules, interactive visualization, interactive mining, rule focusing

On account of the enormous amounts of rules that can be produced by data mining algorithms, knowledge post-processing is a difficult stage in an association rule discovery process. In order to find relevant knowledge, the user needs to rummage through the rules. To make this task easier, we propose a new interactive mining methodology based on well-adapted dynamic visual representations. It allows the user to drive the discovery process by focusing his/her attention on limited subsets of rules. We have implemented our methodology with two complementary 2D and 3D visualization supports. These implementations exploit the user's focus to guide the generation of the rules by means of a specific constraint-based rule-mining algorithm.

Introduction

Although during the first decade of Knowledge Discovery in Databases (KDD) most of the research works were concerned with the development of efficient automatic algorithms able to deal with large amount of data, today the user's role has become a major concern. This need for integration has recently lead to the design of many visualization tools [START_REF] Fayyad | Information visualization in data mining and knowledge discovery[END_REF] [START_REF] Grinstein | Harnessing the human in knowledge discovery[END_REF]. Traditional visualization techniques in KDD are used essentially in the stages which precede and follow the data mining automatic procedures. Upstream the process, they assist the selection and pre-processing tasks. Downstream, they help the users to present the results intelligibly in order to make their interpretation easier. Besides, stemming from exploratory data analysis [START_REF] Tukey | Handling very large numbers of association rules in the analysis of microarray data[END_REF]) [START_REF] Cleveland | The elements of graphing data[END_REF], the so-called "visual data mining" has been developed to highlight the intrinsic properties of data and assist hypothesis generation [START_REF] Keim | Visualization techniques for mining large databases: a comparison[END_REF]. The challenge is here the development of representations of huge data sets well-adapted to the human perception abilities [START_REF] Spence | Information Visualization[END_REF].

The current ambition of the visualization tools is to go beyond a technological assistance to the manipulation and interpretation of data by explicitly considering the user as a full component of the discovery process; "The process of knowledge discovery in databases: a human-centered approach" as [START_REF] Brachman | The process of knowledge discovery in databases: a human-centered approach[END_REF] say. Let us note that this objective was stressed from the early 90s in the seminal paper of Frawley et al (1991): in the part dedicated to the future directions in KDD, they pointed out that the user has to be integrated in the "discovery loop" in order to combine the human subjectivity and the machine processing capacities.

In this paper, we focus on one of the most popular challenges in KDD, the association rule discovery, and we propose a new interactive mining environment based on visual representations where the user acts as an exploration heuristics. Introduced in KDD in the early 90s by [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF] to simply express implicative tendencies between conjunctions of items (binary attributes) in a relational database, the association rules have rapidly known an intensive use. An association rule of the form X → Y means that most of the records which verify X in the database generally verify Y too. For instance, in market data analysis, an association rule pizza, crisps → beer means that if a customer buys a pizza and crisps then (s)he most probably buys beer too. Many automatic algorithms have been proposed in the literature to extract the potentially relevant association rules from large databases (e.g. [START_REF] Hipp | Algorithms for association rule mining -A general survey and comparison[END_REF] for a survey). However, it is now well-known that in real-life situations they produce a prohibitive number of rules for a direct analysis in extenso. This may be explained by the unsupervised nature of the task. In a rule mining process, the user can neither a priori express his/her requests explicitly in the data terminology nor specify the endogenous variables. Thus, the automatic algorithms compute all the valid associations existing in the database, and consequently generate an amount of rules exponentially growing with the number of items.

To overcome these difficulties, we propose to integrate a supervised phase by allowing the user to drive the discovery process via a well-adapted interactive interface. Previous works in knowledge discovery [START_REF] Bhandari | Attribute focusing: machine-assisted knowledge discovery applied to software production process control[END_REF] and decision aid [START_REF] Barthelemy | A model of selection by aspects[END_REF] have shown how the users focus on successive restrictive subsets of attributes to process information. From a cognitive point of view, the suggested explanation is the intensive resort to the short-term working memory. Consequently, our methodology allows the user to explore large rule sets by iteratively exploiting the information brought by limited subsets. More precisely, the architecture of our interactive process is structured around three connected components which dynamically evolve with the user's requests:

1. a database which contains the studied data and additional tables to optimize the response times; 2. a heuristics which computes in the database the rule subsets associated with the user's requests -this heuristics is a local version of the Apriori algorithm [START_REF] Agrawal | Fast algorithms for mining association rules[END_REF]; 3. an interactive visualization support which allows the user to choose a subset of rules to be explored.

In this paper we detail the interaction process and we present two complementary interfaces: a 2D interface which represents the rules by a graph and a 3D interface which represents the rules by objects in virtual worlds. Section 2 presents the cognitive constraints of the user during the rule mining process and describes the dynamic exploration methodology of the search space modeled here as a graph. Section 3 details the two interactive visualization supports. In section 4, we give an illustration of the rule mining process with the 3D visualization interface. In section 5, we present related works, and finally discuss in section 6 the complementarity between the 2D and 3D interfaces.

Dynamic exploration methodology

Cognitive hypotheses

On account of the human "bounded rationality" hypothesis [START_REF] Simon | Models of Thought[END_REF], a decision process can be seen as a search for a dominance structure. More precisely, the decision-maker faced with a set of multiattribute alternatives tries to find an alternative (s)he considers dominant over the others, i.e., an alternative (s)he thinks better than the others according to his/her current representation of the decision situation [START_REF] Montgomery | Decision rules and the search for a dominance structure: towards a process model of decision making[END_REF]. This type of models of decision process can be transferred to the post-processing of association rules by considering the rules as a particular kind of alternatives with items and interestingness measures as attributes. According to Montgomery, the decision-maker isolates a limited subset of potentially useful alternatives and makes comparisons among them. This can be done iteratively during the decision process. More precisely, he has pointed out that: "The decision process acquires a certain directionality in the sense that certain alternatives and attributes will receive more attention than others [...] The directionality of the process may be determined more or less consciously. Shifts in the directionality may occur several times in the process, particularly when the decision-maker fails to find a dominance structure". Furthermore, a KDD methodology called "attribute focusing" has been proposed in [START_REF] Bhandari | Attribute focusing: machine-assisted knowledge discovery applied to software production process control[END_REF]. It results from experimental data concerning the user's behavior in the discovery process. This methodology is based on a filter which automatically detects a small number of potentially interesting attributes. The filter guides the user's attention on a small, and therefore more intelligible, subset of the database. The importance of focusing on a small number of attributes in human information processing has also been widely confirmed with works on decision strategies (cf. for example the moving basis heuristics in [START_REF] Barthelemy | A model of selection by aspects[END_REF]). Indeed, on account of his/her limited cognitive abilities, the decision-maker examines only a small amount of information at each moment.

Taking these different works into account, the dynamic exploration methodology must enable the user to focus his/her attention on limited subsets of rules. Thanks to a visual representation which evolves interactively according to his/her requests, the user can navigate among the rules and make comparisons.

Dynamic exploration

The navigation space modeled as a graph

In our interactive exploration methodology, the search space is modeled as a graph. Among visualization techniques, graphs often have a privileged place, in particular for rule relationship representation. They can be used both as powerful theoretical models (combinatorial objects) and as efficient representation tools that allow users to access complex structures without getting lost in information [START_REF] Buntine | Graphical models for discovering knowledge[END_REF].

In the simplest graph representation of a set Ω of association rules, the nodes are the antecedents and consequents of the rules, and the edges symbolize the implications [START_REF] Klemettinen | Finding interesting rules from large sets of discovered association rules[END_REF]. Such a graph allows, without a key, to grasp the equivalence classes on Ω of the relations "having the same antecedent/consequent", and to generate a partition on Ω of the connex parts of the graph. On the other hand, except for transitivity when it exists, such a graph does not allow to deduce other relations easily. This limit has led to develop other graph-based models which in particular enable deductive inferences in the form of paths [START_REF] Horschka | A support system for interpreting statistical data[END_REF] [START_REF] Lehn | An interactive rule visualization system for knowledge discovery in databases[END_REF].

The model that we favor is similar to the one of [START_REF] Horschka | A support system for interpreting statistical data[END_REF]. Let us note A = {a 1 , a 2 , ..., a p } the set of items (binary attributes) of the database. An association rule {a i , a j } → {a k }, written a i ∧a j → a k for simplification, is modeled as an edge which begins at node a i ∧ a j (the antecedent of the rule) and finishes at node a i ∧ a j ∧ a k (all the items of the rule). The relation attached to the edges is the inclusive relation among the subsets of items. Thus, this graph is directed and acyclic (figure 1). Besides, this is a subgraph of the itemset lattice.

From a logical point of view, relying on the classic support-confidence framework for rule interestingness assessment [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF]

Exploring the graph with neighborhood relations

Given an itemset1 γ in the graph, the user can be interested in two kinds of rules:

the more specific rules with γ as antecedent, -the more general rules whose antecedent is strictly included in γ.

From one rule α → β, the user can therefore access four subsets of rules: case 1. the more specific rules for α (cf. example on figure 2.1), case 2. the more specific rules for β (figure 2.2), So the graph-based model induces four relations that allow the user to navigate among the rules (i.e. accessing a new subset of rules from one selected rule). We call them neighborhood relations, since each of them define a notion of closeness between rules which makes sense for the user: case 1. The neighbors of α → β are all the rules with α as antecedent. This relation is named same antecedent. It is an equivalence relation. case 2. The neighbors of α → β are all the rules with α∧β as antecedent. This relation is named forward chaining since it is inspired by forward chaining in inference engines for expert systems: when the rule α → β is fired, the concept β becomes active and can be used with α to fire new rules and deduce new concepts. The relation is neither reflexive, nor symmetric, nor transitive. case 3. The neighbors of α → β are all the rules that can be built with the items in α. This relation is named antecedent generalization and is complementary to forward chaining: after applying forward chaining on a rule r, one can effectively come back to r by applying antecedent generalization. The relation is neither reflexive, nor symmetric, nor transitive. case 4. The neighbors of α → β are all the rules that can be built with the items in α ∧ β. This relation is named same items since it allows to reorder the items in a rule. All the rules connected by the relation concern the same population of records in the database. This relation is an equivalence relation.

During the interactive exploration process, the user navigates among the subsets of rules by using the neighborhood relations. Each time a relation is applied, a heuristics computes the rules wanted (the neighbors) which are then displayed. Thus, the rule set is explored subset by subset so that the user does not need to appropriate it entirely.

Additional filters

To allow the user to focus on potentially interesting knowledge, the rules are filtered with interestingness measures thanks to thresholds set by the user (cf. [START_REF] Hamilton | Quality Measures for Data Mining[END_REF] for a survey on interestingness measures). Only the good rules (with measures greater than the thresholds) are accessible, the others not being displayed. In our methodology, we mainly use the following measures:

the classic support and confidence 2 [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF], -the implication intensity, an asymmetric probabilistic index which evaluates the statistical significance of the rules by quantifying the unlikelihood of the number of counter-examples [START_REF] Gras | L'implication statistique : nouvelle méthode exploratoire de données[END_REF]) (Blanchard et al, 2003).

Interactive visualization supports

In this section we present two complementary interfaces we have developed for rule exploration:

a 2D interface named Felix which represents the rules by a graph, -a 3D interface named ARVis which represents the rules by objects in virtual worlds.

As regards interaction (navigation) as well as visualization, Felix directly stems from the graph-based model described in section 2.2. On the other hand, ARVis uses the graph-based model for the interaction, while the visualization is based on a totally different paradigm.

2D visualization: Felix

With Felix (Kuntz et al, 2000), one directly visualizes the graph-based model (figure 3). After an initialization step (to choose the first subset of rules to be displayed), the user can dynamically develop the graph as (s)he wishes by applying the neighborhood relations. The graph can be reduced too, i.e. instead of displaying the neighboring rules, they can be removed.

A property always required for drawing graphs which model abstract concepts is the readability. This covers physical constraints of the drawing support (e.g. standard size of computer screens) and aesthetic criteria. Aesthetics specify graphic properties that should help the reader to understand and remember the information embodied in the graph (e.g. [START_REF] Purchase | Which aesthetic has the greatest effect on human understanding?[END_REF]). They attempt to characterize readability by means of general combinatorial optimization goals. Common adopted criteria include minimizing arc crosses and minimizing the sum of the lengths of the arcs to avoid long lines which can create confusion.

In addition to these readability requirements, a drawing convention must be specified. In Felix, we consider polyline drawings with vertices arranged in vertical layers (figure 4). Each layer is associated with a degree of precision in the knowledge state: layers on the left correspond to general characteristics described by few items whereas layers on the right are more specific.

Due to the importance of this problem for many application fields, numerous efficient heuristics have been proposed. However, few of them take the interactivity with the user into account. In most algorithms a graph is given as an input and a drawing is supplied as an output. If a modification is performed (e.g. vertex and arc insertions) the algorithm runs again and produces a new drawing which may be thoroughly different from the previous one. As important changes between consecutive layouts highly disturb the interpretation task, the drawing method should preserve the "user's mental map" as much as possible [START_REF] Eades | Preserving the mental map of a diagram[END_REF]. For this reason, we have developed a genetic algorithm which is particularly efficient for this problem. By computing at each step a set of potential solutions, genetic algorithms allow indirectly to approximately solve a multicri-A B C Fig. 5. Each subset of rules is represented by a 3D world terion problem: a set of potential solutions (i.e. the population) is computed according to aesthetics measured by the fitness, and a solution is selected in this set according to its resemblance to the previous drawing (cf. Kuntz et al (2000) and [START_REF] Pinaud | Dynamic graph drawing with a hybridized genetic algorithm[END_REF] for details).

3D visualization: ARVis

In ARVis 3 (Blanchard et al, 2003), the subsets of rules are visualized in a 3D space, which we call a world (figure 5). The representation is built in the following way: each rule is symbolized by an object composed of a sphere perched on top of a cone (figure 6). In addition to textual display, the interestingness measures of the rules are here visually represented, with the graphical characteristics of the objects (position, sphere and cone sizes, sphere and cone colors). The objects are laid out in the 3D world on an arena (a transparent half-bowl), which means that the further an object is, the higher it is placed (figure 5). This arena allows a better perception of the depth dimension and reduces occultation of objects by other objects. A similar choice is made in the document manager Data Mountain of Microsoft Research, where web pages are laid out on an inclined plane [START_REF] Robertson | Data mountain: using spatial memory for document management[END_REF]. Note that a ground and a sky are represented in order to facilitate the navigation (viewpoint control) inside the world.

As pointed out by Chen ( 2004), such visual landmarks make the navigation task easier by facilitating the acquisition of spatial knowledge, and more generally by facilitating the building of the "mental map" by the user.

After an initialization step (to choose the first subset of rules to be displayed), the user can navigate among the rules thanks to the neighborhood relations. By applying a neighborhood relation on a rule, the current subset is replaced by a new subset which contains all the neighboring rules. Visually, the current world is replaced by a new world, which gives the impression of virtually moving inside the whole set of rules. At any time during the navigation, the user can go back to the previous subsets (and worlds) with the "back" operator.

For each subset of rules, at the beginning of a visit, the user is placed in the 3D world in front of the arena so that (s)he benefits from an overall and synthetic view of the rules. Then the user can wander freely over the world to browse the rules and zoom in on them. There also exist predefined viewpoints to facilitate the exploration (cf. for instance, the viewpoint from the top in figure 5.C).

Architecture

Felix and ARVis are built on a client/server architecture with three components (figure 7):

a database to store data and discovered itemsets; -a CGI script in Perl which dynamically computes the subsets of rules with their interestingness measures, in accordance with the user's requests -this is a constraint-based rule-mining algorithm [START_REF] Ng | Exploratory mining and pruning optimizations of constrained associations rules[END_REF]) [START_REF] Jeudy | Optimization of association rule mining queries[END_REF]; a graphic user interface to visualize and explore the rules (SVG/XHTML/Javascript GUI for the 2D interface and VRML GUI for 3D).

Fig
We are currently working on the integration of both interfaces.

Illustration

This example is a case study made with the firm PerformanSe SA on human resource management data. The data are a set of workers' psychological profiles used to calibrate decision support systems. It contains around 4000 individuals described by 20 categorical attributes (table 1). Each attribute has three possible values: "+" to indicate the presence of the skill, "-" to indicate that the skill is missing, and "0" to indicate a neutral behaviour. The user begins by studying people that are extrovert and motivated by power. By means of the exploration initialization interface, he displays with the 3D interface the world that contains the rules with the itemset ext=+ ∧ pow=+ in the antecedent (figure 8.A). The user explores the world. There are three rules with high interestingness measures at the bottom of the arena, and one of them especially interests the user: (ext=+ ∧ pow=+) → rec=-. To know more characteristics about this not very receptive population, he applies the neighborhood relation forward chaining on this rule. The newly displayed world contains the rules with ext=+ ∧ pow=+ ∧ rec=-in the antecedent (figure 8.B). In the same time, the 2D interface allows to keep a trace of the user's actions on the rules database and to show all the rules discovered so far (figure 9.A). For a better redeability of the graph, the minimum support value is set to 0.02. To be easily identified, the text of the vertex used for the exploration is displayed with a different color.

Next, the user finds a rule which he thinks very pertinent: (ext=+ ∧ pow=+ ∧ rec=-) → mem=+. To know the other rules verified by these extrovert, not very receptive, and motivated by power and membership people, he applies the neighborhood relation same items on the rule. In the new world, the user sees the four rules that can be built with the four items (figure 8.C). One is the transitional rule4 , two others are bad quality rules, and the fourth is a little better than the transitional rule: this is (ext=+ ∧ mem=+ ∧ rec=-) → pow=+ (see figure 9.B for the equivalent in 2D). To know whether all the items in the antecedent are useful in this rule, he applies the relation generalization on it.

In the new world (figure 8.D), there is the rule (ext=+ ∧ mem=+) → pow=+ that is as good as the transitional rule, which means that the item rec=-was superfluous.

Related works

Interactive tools of the type "rule browser" have been developed to assist the user in the post-processing of association rules [START_REF] Klemettinen | Finding interesting rules from large sets of discovered association rules[END_REF]) [START_REF] Ma | Web for data mining: organizing and interpreting the discovered rules using the Web[END_REF] (Tuzhilin and Adomavicius, 2002) [START_REF] Fule | Experiences in building a tool for navigating association rule result sets[END_REF]. They allow to reach interesting rules by applying constraints (templates) and adjusting thresholds on interestingness measures. The main limit of these tools lies in the textual representation of the rules which does not suit the study of large amounts of rules. Within the framework of inductive databases [START_REF] Imielinski | A database perspective on knowledge discovery[END_REF], several rule query languages have also been proposed [START_REF] Han | DMQL: a data mining query language for relational databases[END_REF]) [START_REF] Meo | An extension to SQL for mining association rules[END_REF]) [START_REF] Imielinski | MSQL: A query language for database mining[END_REF]) [START_REF] Braga | Mining association rules from XML Data[END_REF]. They allow to mine and post-process rules interactively under the user's guidance. However, as regards rule post-processing, the query languages are not very user-friendly (cf. [START_REF] Botta | A comparison between query languages for the extraction of association rules[END_REF] for an experimental study).

Sets of association rules can be visualized by using a directed graph [START_REF] Klemettinen | Finding interesting rules from large sets of discovered association rules[END_REF] [START_REF] Rainsford | Visualisation of temporal interval association rules[END_REF] [START_REF] Han | DBMiner: A system for data mining in relational databases and data warehouses In[END_REF]. In this kind of representations, the nodes and edges respectively symbolize the items and the rules. In [START_REF] Hao | Visualization of directed associations in e-commerce transaction data[END_REF], the method is implemented in 3D with a self-organization algorithm which optimizes the graph layout in space. A second rule visualization method consists in using a matrix representation [START_REF] Hofmann | Visual comparison of association rules[END_REF]) [START_REF] Han | DBMiner: A system for data mining in relational databases and data warehouses In[END_REF]. In an item-to-item matrix, each line corresponds to an antecedent item and each column to a consequent item. A rule between two items is symbolized in the matching cell by a 2D or 3D object. This visualization technique has been improved into rule-to-item matrices [START_REF] Wong | Visualizing association rules for text mining[END_REF], where each line corresponds to an item and each column corresponds to a rule. Compared to the item-to-item matrices, the rule-to-item matrices are less cluttered and allow a more efficient representation of rules with more than two items.

All the visual representations described so far are based on rule syntax (i.e. the items). A different approach is proposed in [START_REF] Unwin | The TwoKey plot for multiple association rules control[END_REF], where the representation is based on interestingness measures. This representation is a scatterplot between support and confidence where each point is colored according to density estimation. The user can query any point to display the names of the rules represented by the point (rules with close supports and confidence). The main advantage of such a representation is that it can contain a great number of rules. However, several rules can be represented by one and only one point, which does not facilitate the task of the users when they search for rules using items as criteria. [START_REF] Hofmann | Visualizing association rules with interactive mosaic plots[END_REF] have proposed to visualize association rules with double decker plots, inspired from the mosaic display for contingency tables. In a double decker plot, each rule is symbolized by a rectangle whose area is support and height is confidence. This technique does not deal with the visualization of a large set of rules but with the visualization of a few rules over a few items. It allows a thorough study of a restricted number of rules, making their interpretation easier and helping to understand their occurrence context.

Discussion

The two visualization supports proposed in Felix and ARVis are really complementary. As graphs are a good means of representing large networks of rules, the graph-based interface of Felix is well-adapted for global view. To avoid the computation of huge amounts of rules with data mining algorithms, the graph-based interface can be used to visualize only the set of rules that have already been explored, which allows to interactively build an history of the user's navigation. In this way the user progressively builds the global view on the rules around his/her own interest areas, without having to extract and handle the whole set of rules in one blow (for given thresholds of support and confidence). On the other hand, the 3D interface of ARVis is more appropriate to local view, to make comparisons in a limited subsets of rules. The quality-oriented visual encoding we have chosen stresses the good rules (according to the interestingness measures) whose visualization and access are made easier compared to the less good rules. So the combination of our two visualization supports answers to the need for integration between general and specific views, a classic challenge in information visualization -cf. for example the overview+details approachs [START_REF] Shneiderman | The Eyes Have It: a task by data type taxonomy for information visualization[END_REF] and focus+context approachs [START_REF] Furnas | Generalized fisheye views[END_REF] [START_REF] Sarkar | Graphical fisheye views of graphs[END_REF] [START_REF] Lamping | A focus+context technique based on hyperbolic geometry for visualizing large hierarchies[END_REF]. To our knowledge, such a multiple viewpoint approach has never been proposed for association rule exploration.

The complementarity between Felix and ARVis is also due to the 2D-3D linking. The choice between 2D and 3D representations for information visualization is still an open problem (Card et al., 1999) [START_REF] Chen | Information Visualization: beyond the horizon[END_REF]. This is especially due to the fact that the efficiency of a visualization is highly task-dependent [START_REF] Morgan Kaufmann Carswell | Graphing in depth: perspectives on the use of three-dimensional graphs to represent lower-dimensional data[END_REF]. Besides, while 3D representations are often more attractive, 2D has the advantage of a long and fruitful experience in information visualization. In fact, few research works are dedicated to the comparison between 2D and 3D. As regards the static (non interactive) visualization of statistical graphs, the 3D representations have generally not been advisable since the influential publications of [START_REF] Addison | The Visual Display of Quantitative Information[END_REF] and [START_REF] Cleveland | Graphical perception: theory, experimentation, and application to the development of graphical methods[END_REF]. Nevertheless, the psychophysics experiments of [START_REF] Spence | Visual psychophysics of simple graphical elements[END_REF][START_REF] Morgan Kaufmann Carswell | Graphing in depth: perspectives on the use of three-dimensional graphs to represent lower-dimensional data[END_REF] show that there is no significant difference of accuracy between 2D and 3D for the comparison of numerical values. In particular, Spence points out that this is not the apparent dimensionality of visual structures which counts (2 for a surface, 3 for a volume) but the actual number of parameters that show variability [START_REF] Spence | Visual psychophysics of simple graphical elements[END_REF]. In his experiments, whatever the apparent dimensionality of visual structures, Stevens's law is almost always the same when only one parameter actually varies (Stevens's law exponents are very close to 1). Under some circumstances, information may even be processed faster when represented in 3D rather than in 2D. As regards the perception of global trends in data (increase or decrease), the experimental results of [START_REF] Morgan Kaufmann Carswell | Graphing in depth: perspectives on the use of three-dimensional graphs to represent lower-dimensional data[END_REF] also show an improvement in the answer times with 3D but to the detriment of accuracy.

Conclusion

In this article we have presented a new interactive rule-mining methodology based on two kinds of visual representations: a 2D interface which represents the rules by a graph and a 3D interface which represents the rules by objects in virtual worlds. Our methodology allows the user to drive the discovery process by focusing his/her attention on limited subsets of rules. It relies on:

1. a database which contains the studied data and additional tables to optimize the response times, 2. a heuristics which dynamically computes the rule subsets associated with the user's requests, 3. an interactive visualization support which allows the user to choose a subset of rules to be explored.

The originality of our methodology in comparison with the existing rule exploration techniques mainly lies in the concept of neighborhood relations, predefined relations which enable the user to navigate among the rules. With a query language or an interactive interface like a rule browser, the user can reach any subset of rules but (s)he must explicitly specify the constraints which delimit it. With our approach, the constraint specification is implicit since it is hidden in the neighborhood relations. Actually, the neighborhood relations can be seen as generalizations of constraints (classes of constraints). We think that the user's task is made easier with neighborhood relations than with explicit constraints.

Fig. 1 .

 1 Fig. 1. A graph showing the rules a → b, a → c, a → e, a ∧ b → c, a ∧ c → b, a ∧ c → e, and a ∧ e → c

  , this model allows to represent deductive inferences in the form of paths in the graph. Let us consider for instance the rules a → b and a ∧ b → c, respectively represented by the edges (a, a ∧ b) and (a ∧ b, a ∧ b ∧ c) (figure 1). The confidence of the rule a → b ∧ c that would be represented by the edge (a, a ∧ b ∧ c) is simply the product of the confidences of the rules of the path (a, a ∧ b, a ∧ b ∧ c).

Fig. 2 .

 2 Fig. 2. The four subsets of rules that can be accessed from a ∧ b → c

Fig. 3 .

 3 Fig. 3. A rule graph in Felix

Fig. 4 .

 4 Fig. 4. Polyline drawing of a directed graph with vertices arranged in vertical layers

Fig. 6 .

 6 Fig.6. A menu provides the neighborhood relations (eight relations are implemented in ARVis)

Fig

  Fig. 8. 3D exploration

Table 1 .

 1 . 7. Architecture of Felix and ARVis Meaning of the attributes

	sta	stability	eas	motivation for easiness
	fis	fighting spirit	pro	motivation for protection
	ext	extroversion	rea	motivation for realization
	que	questioning	mem	motivation for membership
	wil	willpower	pow	motivation for power
	rec	receptiveness	imp	improvisation
	rig	rigor	dyn	dynamism
	inc	intellectual conformism	com	communication
	anx	anxiety	aff	affirmation
	soc	spirit of conciliation	ind	independence

An itemset is a conjunction of items.

Support is the proportion of records which verify a rule in the database; it evaluates the generality of the rule. Confidence is the proportion of records which verify the consequent among those which verify the antecedent; it evaluates the validity of the rule (success rate).

The transitional rule is the last rule on which the user applied a neighborhood relation. When a new subset of rules is visualized, the transitional rule is added in the subset (in this example, it is represented in the worlds by an object with a white sphere). This allows making comparisons between a rule and its neighbors.