Formal Concept Analysis (FCA) and concept lattices have shown their e ectiveness for binary clustering and concept learning. Moreover, several links between FCA and unsupervised data mining tasks such as itemset mining and association rules extraction have been emphasized. Several works also studied FCA in a supervised framework, showing that popular machine learning tools such as decision trees can be extracted from concept lattices. In this paper, we investigate the links between FCA and decision trees with numerical data. Recent works showed the e ciency of "pattern structures" to handle numerical data in FCA, compared to traditional discretization methods such as conceptual scaling.
Decision trees (DT) are among the most popular classi cation tools, especially
for their readability [
The paper is organised as follows. Section 2 presents the basics of FCA and one of its extensions called interval pattern structureq for numerical data. Section 3 recalls basic notions of decision trees. Then, we introduce some de nitions in section 4 showing the links between interval pattern structures and decision trees, and a rst algorithm for building decision trees from minimal positive and negative hypothesis extracted from the pattern structures.
Formal contexts and concept lattices. We assume that the reader is familiar
with FCA, and recall here most important de nitions from [
A0 = fm 2 M j 8g 2 A : gImg B0 = fg 2 G j 8m 2 B : gImg f or A f or B
G; M For A G, B M , a pair (A; B), such that A0 = B and B0 = A, is called a (formal) concept. In (A; B), the set A is called the extent and the set B the intent of the concept (A; B). The set of all concepts is partially ordered by (A1; B1) (A2; B2) , A1 A2 (, B2 B1) and forms a complete lattice called the concept lattice of the formal context (G; M; I).
In many applications, data usually consist in complex data involving
numbers, intervals, graphs, etc. (e.g. Table 1) and require to be conceptually scaled
into formal contexts. Instead of transforming data, leading to representation and
computational di culties, one may directly work on the original data. Indeed,
to handle complex data in FCA, Ganter & Kuznetsov [
Patterns structures. Formally, let G be a set of objects, let (D; u) be a meet-semi-lattice of potential object descriptions and let : G ! D be a mapping. Then (G; (D; u); ) is called a pattern structure. Elements of D are called patterns and are ordered by a subsumption relation v such that given c; d 2 D one has c v d () c u d = c. A pattern structure (G; (D; u); ) gives rise to the following derivation operators ( ) , given A G and an interval pattern d 2 (D; u):
A = l (g)
g2A d
= fg 2 Gjd v (g)g These operators form a Galois connection between (2G; ) and (D; v). (Pattern) concepts of (G; (D; u); ) are pairs of the form (A; d), A G, d 2 (D; u), such that A = d and A = d . For a pattern concept (A; d), d is called a pattern intent and is the common description of all objects in A, called pattern extent. When partially ordered by (A1; d1) (A2; d2) , A1 A2 (, d2 v d1), the set of all concepts forms a complete lattice called a (pattern) concept lattice.
Interval pattern structures. Pattern structures allow us to consider
complex data in full compliance with FCA formalism. This requires to de ne a meet
operator on object descriptions, inducing their partial order. Concerning
numerical data, an interesting possibility presented in [
These de nitions of u and v can be directly applied component wise on vectors of numbers or intervals, e.g. in Table 1 where objects are described by vectors of values, each dimension corresponding to an attribute. For example, h[5; 7:2]; [1; 1:8]i v h[5; 7]; [1; 1:4]i as [5; 7:2] v [5; 7] and [1; 1:8] v [1; 1:4].
Now that vectors of interval forms a u-semi-lattice, numerical data such as Table 1 give rise to a pattern structure and a pattern concept lattice. An example of application of concept forming operators (:) is given below. The corresponding pattern structure is (G; (D; u); ) with G = fp1; :::; p4; n1; :::; n3g and d 2 D is a vector with ith component corresponding to attribute mi. fp2; p3g
= (p2) u (p3) = h[5; 5:9]; [2; 3:2]; [3:5; 4:8]; [1; 1:8]i fp2; p3g
= fp2; p3; p4g
As detailed in [
Among all machine leaning tools, decision trees [
In [
Let us consider an interval pattern structure (G; (D; u); ) with an external target property . The set of objects G (the training set) is partitioned into two disjoints sets: positive G+ and negative G . Then, we obtain two di erent pattern structures (G+; (D; u); ) and (G ; (D; u); ).
De nition 1 (Positive hypothesis). A positive hypothesis h is de ned as an interval pattern of (G+; (D; u); ) that is not subsumed by any interval pattern of (G ; (D; u); ), i.e. not subsumed by any negative example. Formally, h 2 D is a positive hypothesis i h \ G = ; and 9A
G+ De nition 2 (Negative hypothesis). A negative hypothesis h is de ned as an interval pattern of (G ; (D; u); ) that is not subsumed by any interval pattern of (G+; (D; u); ), i.e. not subsumed by any positive example. Formally, h 2 D is a negative hypothesis i h \ G+ = ; and 9A
G De nition 3 (Minimal hypothesis). A positive (resp. negative) hypothesis h is minimal i there is no positive (resp. negative) hypothesis e 6= h such that e v h.
Going back to numerical data in Table 1, we now consider the external binary target property and split accordingly the object set into G+ = fp1; p2; p3; p4g and G = fn1; n2; n3g. The pattern concept lattice of (G+; (D; u); ), where D is the semi-lattice of intervals and is a mapping associating for each object its pattern description is given in Figure 1 where positive hypothesis are marked. Note that neither the interval pattern h[5:5; 7]; [2:3; 3:2]; [4; 4:8]; [1:3; 1:8]i nor h[5; 7]; [2; 3:2]; [3:5; 4:8]; [1; 1:8]i are positive hypothesis since they are both subsumed by the interval pattern (n3) = h[6:2; 6:2]; [2:8; 2:8]; [4:8; 4:8]; [1:8; 1:8]i. Therefore, there are two minimal positive hypothesis: P1 = h[5; 7]; [2; 3:2]; [3:5; 4:7]; [1; 1:4]i and P2 = h[5; 5:9]; [2; 3:2]; [3:5; 4:8]; [1; 1:8]i. From (G ; (D; u); ) (not shown), we obtain the unique minimal negative hypothesis: N1 = h[6:2; 7:2]; [2:8; 3:3]; [4:8; 6]; [1:8; 2:1]i.
Now, we consider decision trees more formally. Let the training data be described by K+ = (G+ [ G ; (D; u); ) with the derivation operator denoted by (:) . This operator is called subposition in term of FCA.
De nition 4 (Decision path). A sequence h(m1; d1); (m2; d2); : : : ; (mk; dk)i, for di erent attributes m1; m2; ; mk chosen one after another, is a called decision path of length k if there is no mi such that (mi; di); (mi; ei) and di and ei are not comparable, and there exists g 2 G+ [ G such that hd1; d2; : : : ; dki v (g) (i.e. there is at least one example g such that di v (g) for each attribute mi). For instance, h(m3; [4:8; 6]); (m1; [6:2; 7:2])i is a decision path for Example 1. If i k (respectively i < k), the sequence h(m1; d1); (m2; d2); : : : ; (mi; di)i is called subpath (proper subpath) of a decision path h(m1; d1); (m2; d2); : : : ; (mk; dk)i. De nition 5 (Full decision path). A sequence h(m1; d1); (m2; d2); : : : ; (mk; dk)i, for di erent attributes m1; m2; : : : ; mk chosen one after another, is called full decision path of length k if all object having (m1; d1); (m2; d2); : : : ; (mk; dk) (i.e. 8g 2 G; di v (g) for the attribute mi) are either positive or negative examples (i.e. have either + or value of the target attribute).
We say that a full decision path is non-redundant if none of its subpaths is a full decision path. The set of all chosen attributes in a full decision path can be considered as a su cient condition for an object to belong to a class 2 f+; g. A decision tree is then de ned as the set of full decision paths. 4.1
A rst algorithm for building decision trees from interval pattern structures In this section, we propose a rst algorithm for extracting full decision paths from the sets of minimal positive hypothesis P and minimal negative hypothesis N . Intuitively, minimal positive (resp. negative) hypothesis describe the largest areas in the attribute space that gathers the maximum number of positive (resp. negative) examples with no negative (resp. positive) example. Positive and negative areas may intersect on some dimensions. In Example 1 (see Table 1), P = fP1; P2g and N = fN1g and we denote by Pi \ Nj the interval vector for which the k-the component is the intersection of the Pi and Nj intervals for the k-the component. Recall that P1 = h[5; 7]; [2; 3:2]; [3:5; 4:7]; [1; 1:4]i, P2 = h[5; 5:9]; [2; 3:2]; [3:5; 4:8]; [1; 1:8]i and N1 = h[6:2; 7:2]; [2:8; 3:3]; [4:8; 6]; [1:8; 2:1]i. Then we have:
P1 \ N1 = h[6:2; 7]; [2:8; 3:2]; ;; ;i
P2 \ N1 = h;; [2:8; 3:2]; [4:8]; [1:8]i
We note that P1 and N1 have no intersection for attributes m3 and m4. This means that any example that has a value for m3 (resp. m4) that is contained in P1's interval for m3 (resp. m4) can directly be classi ed as positive. Similarly, any example having a value for m3 (resp. m4) contained in N1's interval for m3 (resp. m4) can directly be classi ed as negative. The same occurs for P2 and N1 for m1.
Therefore a full decision path for a minimal positive hypothesis P is de ned as a sequence h(mi; mi(P ))ii2f1:::jN jg where mi is an attribute such that mi(P \ Ni) = ;4. A full decision path for a minimal negative hypothesis N is de ned as a sequence h(mj ; mj (N ))ij2f1:::jPjg where mj is an attribute such that mj (N \ Pi) = ;.
Here examples of such decision paths (built from P1; P2 and N1 respectively) are: h(m3; [3:5; 4:7])i(P1) h(m4; [1; 1:4])i(P1) h(m1; [5; 5:9])i(P2) h(m3; [4:8; 6]); (m1; [6:2; 7:2])i(N1) h(m4; [1:8; 2:1]); (m1; [6:2; 7:2])i(N1)
Decision paths built from P1 and P2 are sequences that contain a single element since jN j = 1. Decision paths built from N1 are sequences that contain two elements since jPj = 2. Two distinct full decision paths can be built from P1 since there are two attributes for which P1 and N1 do not intersect.
A positive (resp. negative) decision tree is therefore a set of full decision paths, one for each minimal positive (resp.negative) hypothesis. For instance: 4 For any interval pattern P , the notation mi(P ) denotes its interval value for the attribute mi. "if m3 2 [3:5; 4:7] then +, else if m1 2 [5; 5:9] then + else -" is an example of positive decision path. An example of negative decision path is "if m1 2 [6:2; 7:2] and m3 2 [4:8; 6] then -, else +".
Algorithm 1 describes the computation of full decision paths for minimal positive hypothesis. The dual algorithm for minimal negative hypothesis is obtained by interchanging P and N .
1 Res empty array of size jPj; 2 foreach P 2 P do 3 foreach N 2 N such that 9mi; mi(P \ N ) = ; do 4 if (mi; mi(P )) 62 Res[P ] then 5 Res[P ] Res[P ] [ (mi; mi(P )); Algorithm 1: Modi ed algorithm for extracting full decision paths Res (including non-redundant) for minimal positive hypothesis
The di erent steps of the algorithm are detailed below: line 1: Res will contain a full decision path for each minimal positive hypothesis. line 2: Process each minimal positive hypothesis P . line 3: For each minimal negative hypothesis N that has at least one attribute m such that m(P \ N ) = ;, choose one of these attribute, called mi below. line 4: Ensure that mi has not already been selected for another N , this enables to produce non redundant full decision paths (see Example 2). line 5: Add the interval mi(P ) in the full decision path of P . The test mi 2 mi(P ) will separate between positive examples covered by P and negative examples covered by N . line 6: For each minimal negative hypothesis N that has no attribute m such that m(P \ N ) = ;. line 7: Positive examples covered by P and negative examples covered by N can be separated by a disjunction of tests m 2 m(P ) n m(P \ N )) on each attribute m. Hence, there is at least one attribute for which a positive example from P belongs to m(P ) and not to m(N ). Otherwise, N would not be a negative hypothesis.
Note that Example 1 is a particular case where all negative examples are gathered in a unique minimal negative hypothesis.
A few values have been modi ed in Table 2 in order to produce two minimal negative hypothesis.
Minimal positive hypothesis P1 and P2 remain unchanged while there are two minimal negative hypothesis:
This leads to the following intersections:
N1 = h[5:9; 7:2]; [3:2; 3:3]; [5:7; 6]; [1:4; 1:8]i N2 = h[6:2; 7:2]; [2:8; 3:2]; [4:8; 6]; [1:8; 1:8]i
P1 \ N1 = h[5:9; 7]; [3:2]; ;; [1:4]i P1 \ N2 = h[6:2; 7]; [2:8; 3:2]; ;; ;i
P2 \ N1 = h[5:9]; [3:2]; ;; [1:4; 1:8]i
P2 \ N2 = h;; [2:8; 3:2]; [4:8; 4:8]; [1:8]i Examples of full decision path computed by Algorithm 1 from P1 are h(m3; [3:5; 4:7]); (m4; [1; 1:4])i(1) h(m3; [3:5; 4:7]); (m3; [3:5; 4:7])i(2) Note that neither N1 nor N2 intersect P1 on m3, therefore the full decision path (2) can be simpli ed as h(m3; [3:5; 4:7])i. More generally, following previous de nitions, h(m3; [3:5; 4:7])i is a non-redundant full decision path while h(m3; [3:5; 4:7]); (m4; [1; 1:4])i and h(m3; [3:5; 4:7]); (m3; [3:5; 4:7])i are not. A conditional test has been added in Algorithm 1 in order to also produce such nonredundant full decision paths.
Finally a concrete positive decision tree is built from the set of full decision paths, each node corresponds to a minimal positive hypothesis Pi and contains a test that consists in the conjunction of the elements of a full decision path. The left child contains + and the right child is a node corresponding to another minimal positive hypothesis Pj or - if all minimal positive hypothesis have been processed.
An example of decision tree for example 2 is: "if m3 2 [3:5; 4:7] and m4 2 [1; 1:4] then +, else (if m3 2 [3:5; 4:8] and m1 2 [5; 5:9] then +, else -)".
We detail below the complete process for examples 1 and 2. 4.2
Example 1
Comparison with traditional decision tree learning approaches Standard algorithms such as C4.5 produce decision trees in which nodes contain tests of the form a v, i.e. the value for attribute a is less or equal to v, while our nodes contain conjunctions of tests of the form a 2 [a1; a2] ^ b 2 [b1; b2]. A solution consists in identifying minimal and maximal values for each attribute in the training set, and by replacing them by 1 and +1 respectively in the resulting trees (see Figure 4). Moreover, common decision tree induction techniques use Information Gain maximization (or equivalently conditional entropy minization) to choose the best split at each node. The conditional entropy of a split is null when each child node is pure (contains only positive or negative examples). When this perfect split can not be expressed as an attribute-value test, it can be shown that the optimal split that minimize conditional entropy consists in maximizing the number of examples in one pure child node (proof is ommited due to space limitation). This optimal split exactly matches our notion of positive (resp. negative) minimal hypothesis, which corresponds to descriptions that gathers the maximum number of only positive (resp. negative) examples.
However we insist that our algorithm is only a rst and naive attempt to produce decision trees from multi-valued contexts using pattern structures. Its aim is only to clarify the links between decision tree learning and pattern structures. Therefore it obviously lacks of relevant data structures and optimization. However we plan to focus our e orts on algorithm optimization and then on rigorous experimentations on standard datasets. 5
In this paper, we studied the links between decision trees and FCA in the particular context of numerical data. More precisely, we focused on an extension yes + yes − yes − yes + yes − yes m4 = 1:8 ^ m1 2 [6:2; 7:2] − m3 2 [5:7; 6] yes no yes − + − full paths from N1, then from N2 full paths from N2, then from N1
Fig. 3: Decision trees built from Example 2 yes + yes +
no yes + m4 1:4 yes +
no m1 5:9 no − our approach
Weka implementation of C4.5 Fig. 4: Comparison of decisions trees produced by our approach and by C4.5 for Example 1 of FCA for numerical data called interval pattern structures, that has recently gained popularity through its ability to handle numerical data without any discretization step. We showed that interval pattern structures from positive and negative examples are able to reveal positive and negative hypothesis, from which decision paths and decision trees can be built.
In future works, we will focus on a comprehensive and rigorous comparison
of our approach with traditional decision tree learning techniques. Moreover,
we will study how to introduce in our approach pruning techniques that avoid
over tting. We will also investigate solutions in order to handle nominal class
attributes (i.e. more than two classes) and heterogeneous explanatory attributes
(binary, nominal, ordinal, numerical). Finally, notice that interval patterns are
closed since (:) is a closure operator. In a recent work [