In this paper we illustrate the potential of Triadic Concept Analysis (TCA) in extracting useful patterns from triadic formal contexts. To that end, we exploit our recent contributions to TCA to analyze the Groceries database and identify triadic patterns expressed by concepts and association rules, including implications.
Since datasets are frequently expressed by ternary and more generally n-ary
relations, one can observe a recent and increasing interest to propose new solutions
for the analysis and exploration of these multidimensional data, and specially
triadic contexts [
In this paper, we aim at illustrating the utilization of our software platform
using a subset of the well-known dataset named the Groceries database [
The rest of the paper is organized as follows. In Section 2 we brie y recall the main notions of Triadic Concept Analysis. Section 3 presents our platform, the original dataset and its preprocessing as well as a few examples of the generated patterns which are triadic concepts and association rules, including implications. Finally, Section 4 summarizes the paper and presents the future work in terms of the platform enrichment and validation using synthetic and real data.
Triadic concept analysis was originally introduced by Lehmann and Wille [
K 3782
Chicken Oil Pip Fruit Curd . . . . . .
J F . . . S J F . . . S J F . . . S J F . . . S J F . . . S J
1 1 1 1 1 . . . . . .
Table 1. A row of the triadic context K := (K1; K2; K3; Y ) F . . . S
A triadic concept or closed tri-set of K is a triple c = (A1; A2; A3) (also denoted by A1 A2 A3) with A1 K1, A2 K2, A3 K3 and A1 A2 A3 Y is maximal with respect to inclusion in Y . A1 is called the extent of c, A2 its intent, and A3 its modus. We name (A2; A3) the feature of c. For example, (f2512; 4320g; fcanned beerg; fJ anuary; Aprilg) is one of two triadic concepts (see the green box in Figure 2) with the same extent f2512; 4320g which indicates that the two identi ed customers have two common features. The rst feature means that both of them bought canned beer in January and April while the second one indicates that they purchased butter and canned beer in January.
Let L = (C; 1) be a poset of nodes such that each node represents the set
of triadic concepts in C with the same extent, and the relation 1 is induced
by the inclusion on extents. We de ned in [
A pair (B2; B3) is called a triadic feature-based generator [
Kk j (ai; aj ; ak) 2 Y 8ai 2 Xig (Xj ; Xk)(i) := fai 2 Ki j (ai; aj ; ak) 2 Y for all (aj ; ak) 2 Xj Xkg: (1) (2)
As an illustration, let us consider the portion of the Hasse diagram shown in Figure 2. We can see that each node represents the set of features and Fgenerators associated with one extent. For example, there are two features and two F-generators attached to the node whose extent is f2512; 4320g, The dotted red box attached to the extent f2512g contains ten F-generators. One of them is (fco ee, pastryg; fSeptemberg) which is simply denoted by (co ee, pastry September ) in Figure 2.
Biedermann [
A conditional attribute implication takes the form: A C! D, where A and D
are subsets of K2, and C is a subset of K3. It means that A implies D under all
conditions in C. In particular, the implication holds for any subset in C. This
implication is then linked to Biedermann's de nition of triadic implication as
follows [
In a dual way, an attributional condition implication is an exact association
C! D, where A and D are subsets of K3, and C is a subset rule of the form A of K2.
Let (B2; B3) be a feature-based generator associated with (A2; A3) of a triadic
concept whose extent is A1, i.e., B2 A2 and B3 A3. Then, we de ne in [
Dually, the Biedermann attributional condition implication (BACI) (B3 ! A3 n B3)B2 holds with a support equal to jA1j=jK1j if B3 A3 and B2 A2. A2 involved in a BCAI is constrained to be maximal among all the intents of the features associated with (B2; B3) and A3 inside a BACI must be maximal among all the modi of the features associated with (B2; B3).
Given a feature-based generator g = (B2; B3) and a feature (A2; A3), both associated with the node whose extent is A1 such that A2 is the maximal intent in ((B2; B3)(1))(1) that contains B2. Let the quasi-order (X1; X2; X3) .1 (A1; A2; A3) holds between the current concept c = (A1; A2; A3) and c1 = (X1; X2; X3) found in the lower cover of the node that contains c. Then, we claim the following statement:
If A2 X2 and X3 A3 and B2 X2 and B3 X3, then the following Biedermann conditional attribute association rule BCAAR holds: (B2 ! X2 n A2)B3 with a support equal to jX1j=jK1j and a con dence of jX1j=jA1j, where K1 stands for the set of objects.
In a dual way, the Biedermann attributional condition association rule BACAR can be de ned. 3 3.1
Platform
Our development platform for TCA is implemented mostly with Python and has
the following modules [
In this paper, we will mainly illustrate our work on Module 2 and parts of
Modules 3 and 4.
The Groceries database [
The reason we used such a sample is due to the fact that it allows us to illustrate the meaning of the generated patterns that are either triadic concepts, implications or association rules with a con dence lower than 1. Due to the sparsity of the initial dataset and many large subsets, the set of implications was frequently empty or small and many generated association rules were trivial with a very low support.
The sample is then converted into a triadic context where the value 1 in a cell indicates that a given customer bought an item at least once during a given month. For example, Customer 3782 purchased a pip fruit on January as shown in Table 1. In the following we show a part of the output produced for the subset of the Groceries database by rst displaying a part of the Hasse diagram and then a set of implications and association rules.
Figure 2 shows a portion of the Hasse diagram of triadic concepts where the node in the green box represents the extent of two triadic concepts as a set of two customers who share two features found inside the corresponding blue box. The rst feature tells us that Customers 2512 and 4320 bought the item canned beer on April and January while the second feature indicates that they both purchased butter and canned beer on January. Since the set of Fgenerators is equal to the set of features associated with the extent f2512; 4320g, no implication can be generated from the node labeled with this extent. If we look at the upper covers of this current node, we observe three groups of customers: those who bought canned beer in January (winter season), those who purchased canned beer in April (spring) and those who bought butter in January.
The node in the purple box concerns Customer 2512 with four features displayed in the blue box and 10 F-generators in the red box. We can then extract the following BCAI using the rst feature and the rst F-generator: (bottled water; f ruit=vegetable juice ! co ee, newspapers; pastry)September [0:1%; 100%]. It means that whenever this customer (one out of 1000 = 0:1%) buys f ruit=vegetable juice and bottled water at least once on September, then he/she purchases co ee, newspapers and pastry during this month. In a similar way, we can identify the following BACI from another node in the diagram (not shown in Figure 2): (F ebruary; April ! N ovember)root vegetables [2%; 100%]. It means that buying root vegetables on February and April implies making the same purchase on November with a support of 2%.
All the empirical tests are executed using multi-threading on a Ubuntu 19.10 based system with 32GB of RAM memory and an Intel i7-4790 3.6GHz 8-core processor.
In Table 3 we present a few statistics about the size of the output as well as the execution time of each one of the platform component.
Statistics Nb. of links Nb. of distinct extents Nb. of triadic concepts Nb.of minimal F-generators Nb. of implications (sup >0) Nb. of association rules (conf. <1) Execution time in seconds per step T-iPred F-generator computation Implication computation Association rule computation (conf. <1) Total time
In this paper we illustrated the application of algorithms for Triadic Concept Analysis to a subset of the Groceries database as a triadic context to discover concepts and association rules, including implications. The merits of TCA lie in the fact that patterns are in a compact form and under many perspectives in the sense that for a given extent (set of objects) of a triadic concept, we obtain di erent views expressed by distinct features, and for a given generator and compatible features, we may get more than one association rule or implication.
Our current work is to complete the development of our software solution to
make it an open source for everyone and continue our investigation of new kinds
of association rules [
Finally, in order to help researchers validate their present and future
contributions in TCA and more generally in Polyadic Concept Analysis [
This study was nanced in part by the NSERC (Natural Sciences and Engineering Research Council of Canada) and by the Coordenac~ao de Aperfeicoamento de Pessoal de N vel Superior - Brazil (CAPES) - Finance Code 001.