Our paper shows that decision trees and random forests can be described via pattern structures. This new perspective leads to a better understanding of random forests and delivers a new way of analyzing complex data with the help of pattern structures. (1) The pair (f, g) is an adjunction w.r.t. (P, L) if f x ≤ y is equivalent to x ≤ gy for all x ∈ P and y ∈ L. In this case, we will refer to (P, L, f, g) as a poset adjunction.
Pattern structures within the framework of formal concept analysis have been
introduced in [
Definition 1 (Adjunction). Let P = (P, ≤) and L = (L, ≤) be posets; furthermore let f : P → L and g : L → P be maps. (2) g is residual from L to P if the preimage of a principal filter in P under g is always a principal filter in L, that is, for every x ∈ P there exists y ∈ L s.t.
g−1{s ∈ P | x ≤ s} = {t ∈ L | y ≤ t}.
Definition 2 (restriction). Let P := (P, ≤P) be a poset; then, for every set U the poset
P | U := (U, ≤P ∩(U × U )) is called the restriction of P onto U .
Definition 3. Let f : A → B be a surjective map, then
IPf : B → 2A, b 7→ f −1b is a partition of A. We call IPf an f induced partition of A.
If we consider a poset of patterns, it often arises as a dual of a given poset. Definition 4 (Dedekind MacNeille completion). Let D := (D, ≤) be an ordered set. For every subset A ⊆ D we call
A↑ := {d ∈ D | a ≤ d for all a ∈ A} the set of all upper bounds of A. The set of all lower bounds of A is defined dually and denoted by A↓. A cut of D is a pair (A, B) with A, B ⊆ D, A↑ = B and A = B↓. It is well known that these cuts ordered
(A1, B1) ≤ (A2, B2) :⇔ A1 ⊆ A2 (⇔ B2 ⊆ B1) form a complete lattice, the Dedekind MacNeille completion. It is the smallest complete lattice containing a subset that is order isomorphic with D and denoted by DM N (D).
Definition 5 (Interval Poset). Let P := (P, ≤P) be a poset. Then we call
IntP := {[p, q]P | p, q ∈ P } with [p, q]P := {t ∈ P | p ≤P t ≤P q} the set of all intervals of P, and we refer to IntP := (IntP, ⊇) as the interval poset of P.
Remark: (i) Let P be a poset. Then IntP is an upper bounded poset, that is, ∅ is the greatest element of IntP, provided P has at least 2 elements. Furthermore, if P is a (complete) lattice, then so is IntP. (ii) If A is a set of attributes, then (RA, ≤) := (R, ≤)A is a lattice. With (i) it follows that Int(RA, ≤) is a lower bounded lattice.
The main definitions of FCA are based on a binary relation I between a set of so called objects G and a set of so called attributes M . However, in many real-world knowledge discovery problems, researchers have to deal with data sets that are much more complex than binary data tables. In our case, there was a set of numerical attributes, such as the amount of acetic acid, density, the amount of salt, etc., describing the quality of a red wine. To deal with this kind of data, pattern structures are a useful tool.
Definition 6 (pattern setup, pattern structure). A triple P = (G, D, δ) is a pattern setup if G is a set, D = (D, v) is a poset, and δ : G → D is a map. In case every subset of δG := {δg | g ∈ G} has an infimum in D, we will refer to P as pattern structure.
In the sequel we need definition 5 and an application of Theorem 1 from [
Definition 7 (pattern morphism). If G = (G, D, δ) and H = (H, E, ε) each is a pattern setup, then a pair (f, ϕ) forms a pattern morphism from G to H if f : G → H is a map and ϕ is a residual map from D to E satisfying ϕ ◦ δ = ε ◦ f , that is, the following diagram is commutative: δ
G D f ϕ
H E ε Theorem 1. Let G be a pattern structure and H be a pattern setup. If (f, ϕ) is a pattern morphism from G to H , with f being surjective, then H is also a pattern structure.
In this paper we want to present a connection between pattern structures
and random forests. Decision trees are an important data mining tool, used to
predict classes of data sets. Many applications of decision trees build a model
on a so called training set and then try to predict classes of unseen data (test
sets). For an introduction into the subject, we recommend [
Definition 8 (decision tree). A finite tree is defined as a triple T := (T, ≤T, 0T) consisting of a finite poset (T, ≤) with least element 0T. This least element will be denoted as root node. Every principal downset is partially ordered. The maximal elements of T will be called leaves of T; let LeT denote the set of leaves of T. A triple T := (G, T, λ) will be called a finite decision tree or short decision tree if G is a finite set, T := (T, ≤T, 0T) is a finite tree and λ : G LeT is a surjective map. The map
τ : T → LeT, t 7→ {b ∈ LeT | t ≤ b} allocates the set of leaves to a node, where the node is less than or equal to the leaf (in the sense of ≤T). We call
Tc := (T c, ≤T, 0T) with T c := T ∪ {1T} the tree completion of T and Tc a complete tree. This leads to a map λ : G → T c, g 7→ λg.
In the here presented context we will refer to T s := (G, T, Tc, λ, λ, τ ) as a decision tree setup.
Remark: (i) A tree completion Tc is the smallest complete lattice which contains T. (ii) The λ induced partition of G is given by
IPλ : LeT → 2G, b 7→ λ−1b
The following example illustrates the definition of a decision tree.
G
w0
w1
w2
w3
w4
w5
In [
F := (G, Tprod, λ) with Tprod := Y Ti, Tprod := Y Ti and λ : G →
i∈I i∈I a random forest.
Y Ti, g 7→ {λig}i∈I i∈I 3
The following definition establishes the connection between pattern setups and pattern structures.
Definition 10 (embedded pattern structure). Let L be a complete lattice and P := (G, D, δ) a pattern setup with D := L|D. Then we call
Pe := (G, L, D, δ) with δ : G → L, g 7→ δg the embedded pattern structure. We say the pattern setup P is embedded in the pattern structure (G, L, δ).
The following two constructions are a demonstration of how to build an embedded pattern structure from a pattern setup.
Construction 2. Let G be a set and let D := (D, ≤) be a poset, then for every map % : G → D the elementary pattern structure is given by:
P% := (G, L, ε) with L := (2D, ⊇) and ε : G → 2D, g 7→ {%g}.
Hence, the pattern setup (G, D, %) is embedded in the pattern structure P%. Construction 3. For every pattern setup P := (G, D, δ), a pattern structure is given through the Dedekind MacNeille completion and
(G, DM N (D), δ) with δ : G → DM N (D), g 7→ δg 4
In this section we are going to present a way to construct a pattern structure from a given decision tree. Starting point is the following pattern setup: Construction 4. Let T s := (G, T, Tc, λ, λ, τ ) be a decision tree setup, then
P := (G, T, λ) is a pattern setup. We embed this pattern setup in the embedded pattern structure
P e := (G, Tc, T, λ).
This leads to the pattern structure (G, Tc, λ).
This construction provides a connection between decision trees and pattern structures. Below we show the link between pattern structures and random forests. For this purpose we have to look at the product of pattern structures. Construction 5. Let I be a finite set and Pi := (G, Di, δi) a pattern structure for every i ∈ I. Then
Our construction shows that a product of pattern structures leads to a pattern structure again. A decision tree can be described via a pattern structure and, since a random forest is a product of decision trees, a random forest is characterized by a pattern structure, too. The following theorem lays this out. Construction 6. Let I be an index set and Tis := (G, Ti, Tic, λi, λi, τi) a decision tree setup for all i ∈ I, and F := (G, Tprod, λ) the corresponding random forest. Construction 4 provides us the embedded pattern structures Pie := (G, Tic, Ti, λi) for every tree Ti. Then
P := (G, T, λ) with T :=
Y Tic, T :=
Y Tic and λ : G → i∈I i∈I
Y Tic, g 7→ {λig}i∈I i∈I is a pattern structure, too.
Construction 6 presents a way to describe a random forest through a pattern structure. Not only does this novel perspective enable a deeper understanding of random forests, but it also proves useful in real world applications, as will be pointed out in the next section. 5
In this section, we are going to first describe the public data set we used, and then apply Construction 6 to a typical data-mining related classification problem. 5.1
Red Wine Data Set
To apply our previous results on a public data set we choose the red wine data set
from [
Random forests are an useful tool like this example shows, but it is hard
to comprehend how a decision tree gives a ruling. Interval pattern structures,
introduced in [
W := Y m∈M
Wm and W :=
Wm.
Y m∈M Then, a map α : G → W, g 7→
Y m∈M {αmg} such that
αm : G → Wm, g 7→ wm
is called evaluation map. We call E := (G, M, W, α) an evaluation setup.
Example 1. In the wine data set in [
In the above example, the evaluation map α : G → W assigns to every wine a vector with values of all attributes m ∈ M .
Construction 7. Let E := (G, M, W, α) be an evaluation setup and, further, let T s := (G, T, Tc, λ, λ, τ ) be a decision tree setup. Then, ϕ : T c → IntW|ϕT c, t 7→ [inf α(λ−1τ t), sup α(λ−1τ t)]
W W maps intervals to all nodes of the decision tree. The intervals are spanned by the objects in the node.
It is possible to create a pattern structure from this map, as the following theorem shows.
Theorem 2. Let E := (G, M, W, α) be an evaluation setup and T s := (G, T, Tc, λ, λ, τ ) a decision tree setup. Then
P := (G, IntW|ϕT c, ϕ ◦ λ) with ϕ : T c → IntW|ϕT c, t 7→ [inf α(λ−1τ t), sup α(λ−1τ t)]
W W is a pattern structure.
Proof. We want to apply theorem 1. Since the identity map is clearly surjective, we have to show that (id, ϕ) is a pattern morphism, more precisely we have to prove that ϕ is a residual map. This can be achieved by applying definition 1. The preimage of a principal filter in IntW|ϕT under ϕ is always a principal filter in Tc. For every x ∈ IntW|ϕT
ϕ−1{s ∈ IntW|ϕT | x ≤ s} = {t ∈ T c | ϕ−1x ≤ t} holds.
To lift the previous theorem up to a random forest, we use construction 5. Construction 8. Let E := (G, M, W, α) be an evaluation setup, I an index set, and F := Q Ti a random forest with corresponding decision tree setups i∈I Tis := (G, Ti, Tic, λi, λi, τi). Then
Pi := (G, IntW|ϕiTic, ϕi ◦ λi) with
P := (G, D, δ) is a pattern structure and with D :=
Y IntW|ϕiTic, D := i∈I
Y IntW|ϕiTic and δ : G → i∈I
Y IntW|ϕiTic, g 7→ {ϕi◦λig}i∈I i∈I is a pattern structure, too.
This construction provides a set of intervals for every g ∈ G. The intersection of these intervals is not empty because g is at least in every interval. Every g assigned a predicted class probability from a decision tree, which is a purity measure. It is calculated as the ratio of good examples to all examples in a leaf. For a random forest, the average of this ratio for all leaves, which contains g are used to calculate a score. We took the best scored g of our training set and looked at union of the intervals constructed by the random forest. We received the following result:
The diagram show all 11 attributes (fixed acidity, volatile acidity,... ) of the wines. Displayed is the interval, which is constructed from best scored wine of the random forest. This pattern contains 330 wines of the training set, 297 of them are good and 33 are bad. As mentioned before the training set contains of 75% of the data, which are 1199 wines. 652 of them are good and 547 bad. To choose a collection of intervals for a prediction model we calculate a score on a pattern p via score(p) = good wines in p all good wines
+ ([ratiop ∗ 100] − 50)/50.
To improve interpretability, we selected only the following best scored 5 intervals
and add them to the first interval to build our model. Again we looked at the
union of the intervals and scaled the range of the features to [
Combining these 6 intervals to predict the classes of the test set leads to the following confusion matrix:
Our model lost some prediction quality, but the high interpretability makes our algorithm useful. For example fixed acidity, which is the first attribute, seems not important for the quality of a wine since all patterns have a huge range in this feature. On the other hand the range in the attribute sulphates is comparatively small. This suggests the assumption, that sulphates are an important feature to classify a wine.
We introduced a novel framework for the application of pattern structures. The paper presents a new way of building a pattern structure through a given decision tree. This link is an interesting view on things and via a visualization it leads to a better understanding of how a decision tree gives a ruling. Furthermore, our paper shows that the product of pattern structures are also pattern structures and so we extend the link between pattern structures and decision trees to random forests, since they are a product of decision trees. Also we introduced a model to predict classes of red wines. This model is an abstraction of a random forest. As here introduced the prediction of the random forest is better, but the high interpretability makes our algorithm valuable. This is just a first useful example of our method. Further investigations on other data sets have to prove the importance of our algorithm.
Besides, we made some theoretical progress in the field of pattern structures by introducing embedded pattern structures. They provide a framework where it is possible to construct a pattern structure out of a given pattern setup.