Decision tree learning is one of the most popular classification techniques. However, by its nature it is a greedy approach to finding a classification hypothesis that optimizes some information-based criterion. It is very fast but may lead to finding suboptimal classification hypotheses. Moreover, in spite of decision trees being easily interpretable, ensembles of trees (random forests and gradient-boosted trees) are not, which is crucial in some domains, like medical diagnostics or bank credit scoring. In case of such “small, but important-data” problems one is not obliged to perform a greedy search for classification hypotheses, and therefore alternatives to decision tree learning techniques may be considered. In this paper, we propose an FCA-based classification technique where each test instance is classified with a set of the best (in terms of some information-based criterion) classification rules. In a set of benchmarking experiments, the proposed strategy is compared with decision tree and nearest neighbor learning.
The classification task in machine learning aims to use some historical data
(a training set) to predict unknown discrete variables in unknown data (a test
set). While there are dozens of popular methods for solving the classification
problem, usually there is an accuracy-interpretability trade-off when choosing
a method for a particular task. Neural networks, random forests and ensemble
techniques (boosting, bagging, stacking etc.) are known to outperform simple
methods in difficult tasks. Kaggle competitions also bear testimony for that –
usually, winners resort to ensemble techniques, mainly to gradient boosting [
However, in lots of applications we need a model to be interpretable as well as
accurate. Some classification rules, built from data and examined by experts, may
be justified or proved. In medical diagnostics, when making highly responsible
decisions (e.g., predicting whether a patient has cancer), experts prefer to extract
readable rules from a machine learning model in order to “understand” it and
justify the decision. In credit scoring, for instance, applying ensemble techniques
can be very effective, but the model is often obliged to have “sound business
logic”, that is, to be interpretable [
In what follows, we introduce some notions from Formal Concept Analysis
(FCA) [
Pattern structures are natural extension of Formal Concept Analysis to
objects with arbitrary partially-ordered descriptions [
Definition 1. Let G be a set (of objects), let (D; u) be a meet-semi-lattice (of
all possible object descriptions) and let : G ! D be a mapping between objects
and descriptions. Set (G) := f (g)jg 2 Gg generates a complete subsemilattice
(D ; u) of (D; u), if every subset X of (G) has infimum uX in (D; u).
Pattern structure is a triple (G; D; ), where D = (D; u), provided that the
set (G) := f (g) j g 2 Gg generates a complete subsemilattice (D ; u) [
A = l (g) g2A
for A 2 G; d = fg 2 G j d v (g)g for d 2 (D; u):
Pairs (A; d) satisfying A pattern concepts of (G; D; ).
G; d 2 D; A = d, and A = d are called
As in classical FCA, pattern concepts form a pattern concept lattice. In case it is too computationally demanding to build the whole lattice, projections are used to simplify object descriptions and boost the formation of a pattern concept lattice.
Definition 3. A projection [
The theoretical part of the proposed approach is based on Formal Concept
Analysis and pattern structures, in particular, on Interval Pattern Structures [
Definition 4. Let (G; (D; u); ) be an interval pattern structure. Let Ti = f i1; : : : ; iti g; i = 1; : : : ; m be m sets of real numbers where m is a cardinality of each d 2 D. Then, (h[ai; bi]ii2[1;m]) = h[maxf j 2 Ti [ f 1; +1g; aig; minf j 2 Ti [ f 1; +1g; big]i is called a discretizing projection of a semilattice (D; u).
The discretizing projection, as defined in Def. 4, is a projection according to the definition Def. 3.
Example 1. Consider a toy dataset with only 4 objects and 1 numeric attribute
as shown in Fig. 1 (left). In order to apply decision tree learning for some
classification task with this dataset, one would apply some discretization method to
produce binary attributes from attribute a. Consider the discretization shown in
Fig. 1 (middle). The corresponding concept lattice is shown in the same figure
on the right-hand side.
([a; b]) = [maxf j 2 T +; ag; minf j 2 T +; bg] with
T + = f 1; 1:5; 3:5; +1g is a projection of the semilattice built for a context
that arises from the interordinal scaling of the initial many-valued numerical
context. Address to [
Introducing a discretizing projection is a general way to express any discretizing procedure (essential part of decision tree learning algorithms) in terms of FCA. 4
For classification tasks with complex data we propose Algorithm 1. The main
idea is to find the classification rule for each test instance that maximizes some
information criterion (Gini index, pairwise mutual information etc.). In case
of interval pattern structures, by its design, the algorithm guarantees to classify
each test instance with at least as good rule (in terms of an information criterion)
as a decision tree. We apply a modification of the CloseByOne algorithm [
Let P Strain = (Gtrain; ((D; u); ctrain); train) and P Stest = (Gtest; (D; u); test) be two pattern structures corresponding to a train and a test set in a classification task. Let CbOP S (P S; min_supp) be the algorithm used to find all pattern concepts of a pattern structure P S with support greater or equal to min_supp. Let inf : D [ ctrain ! R be an information criterion used to rate classification rules (we use Gini impurity by default). Finally, let min_supp and n_rules be the parameters of the algorithm (the minimal support of each classification rule’s premise and the number of rules to be used for prediction of each test instance’s class attribute).
With this designations, the main steps of the proposed algorithm are the following: 1. Initialize a list of predicted labels for test instances ctest and a dictionary of classification rules rtest for each test instance. 2. Calculate the proportion of positive objects in the training set: fpos = jc0trainj jGtrainj 3. With the CbOP S algorithm, find S – a dictionary of all pattern concepts (with support greater or equal to min_supp) of a pattern structure P Strain Meanwhile, calculate the value of the criterion inf (values in the dictionary S) for each concept intent (keys in the dictionary S). 4. Sort S by its values. 5. For each test instance gt 2 Gtest: – Find first nrules concept intents from S such that
(Ai; di) 2 S; gt v di; i = 1; : : : ; nrules – For each “top-ranked” concept intent di determine ci – the proportion of positive objects among di : fi+ = jdi \ c0trainj .
jdi j – Thus, form fdi ! f +
i gi2[1;n_rules] – a set of classification rules for gt.
Set rtest[t] be equal to this set of rules. – Predict the value of the class attribute for gt as an indicator of the average antecedent of rtest[t] being greater or equal to the proportion of positive objects in the training set:
n_rules ctest[i] = [ X
fi+ i=1 fpos n_rules] Algorithm 1 Concept Lattice-Based Rule-learner (CoLiBRi) Input: P Strain = (Gtrain; ((D; u); ctrain); train) P Stest = (Gtest; (D; u); test) min_supp 2 R+; nrules 2 N; CbOP S(P S; min_supp) : P S ! S; inf : D ctrain ! R; sort(S; inf ) : S ! S Output: ctest; rtest ctest = ;; rtest = ; fpos = jc0trainj
jGtrainj S = f(A; d) : inf (d; ctrain) j A CbOP S(P Strain; min_supp) S = sort(S; inf ) for gt 2 Gtest do fdigi2[1;nrules] = fd j (A; d) 2 S; gt v dg fi+ = jdi \ c0trainj
jdi j rtest[i] = fdi ! fi+gi2[1;nrules] ctest[i] = [Pin=_1rules fi+ fpos n_rules] end for
Gtrain; d 2 D; A = d; d = A; jAj min_suppg =
In case of a classification task with numeric attributes we apply the same Algorithm 1 for interval pattern structures. To make it tractable, we apply it to projections (P Strain) and (P Stest) of a training and a test interval pattern structure. Here (P S); is a discretizing pattern structure projection as defined in Def. 4. 5
We compare the proposed classification algorithm (denoted as “CoLiBRi” for
“Concept Lattice-Based Rule-learner”) with Scikit-learn [
We used Gini impurity as a criterion for rule selection and MDL [
Parameter min_supp for “CoLiBRi” was taken equal to CART’s min_samples_leaf for each dataset. We used n = 10 classification rules to vote for a test instance label. The described algorithms were implemented in Python 2.7.3 and run on a 4-CPU machine with 4 GB RAM.
The results are presented in Table 1. Each entry stands for the average metric (accuracy or F1-score) in 5 runs of 5-fold cross-validation. In the table, the algorithm with the best performance on each metric is boldfaced. Other algorithm’s whose performance is not statistically distinguishable from the best algorithm at p = 0.05 using paired t-tests on the 5 runs are *’ed. The best parameters for each algorithm are mentioned in Table 2.
As it can be seen, the proposed approach performs better than CART and is statistically indistinguishable from RF on most of the datasets. Surprising enough, kNN seems to be the best-performer (on average over all datasets) in terms of accuracy but not F1-score.
In this paper, we have shown how searching for classification hypotheses in a formal concept lattice may yield accurate results while providing interpretable classification rules.
Further we plan to test the proposed strategy in classification tasks such as predicting biological activity (toxicology, mutagenicity, etc.) and telecom client dataset audiology balance-scale breast cancer car hayses-roth lymph mol-bio-prom nursery primary tumor solar flare soybean spect train tic-tac-toe satisfaction where objects have complex descriptions (graphs and sequences correspondingly).
We also plan to introduce some randomization in mining rules for each test instance (as it is done with random forests) in order to further improve the classification quality.