Paper link: http://florent.avellaneda.free.fr/dl/AAAI20.pdf

The source code is designed to be compiled and executed on GNU/Linux.

• g++
• cmake
• minisat : http://minisat.se/
• xdot : https://github.com/jrfonseca/xdot.py
• CLI11 : https://github.com/CLIUtils/CLI11

The following instructions have been tested on Ubuntu 19.04

sudo apt install g++ cmake minisat2 xdot libzip-dev libboost-dev

search yum install minisat2 https://centos.pkgs.org/7/lux/minisat2-libs-2.2.1-1.el7.lux.x86_64.rpm.html

git clone https://github.com/zhzdeng/minisat sudo cp -r minisat/minisat /usr/local/include/

yum install epel-release yum install gcc-c++ cmake xdotool libzip-devel boost-devel

sudo echo '[group_kdesig-cmake3_EPEL] name=Copr repo for cmake3_EPEL owned by @kdesig baseurl=https://copr-be.cloud.fedoraproject.org/results/@kdesig/cmake3_EPEL/epel-7-$basearch/ type=rpm-md skip_if_unavailable=True gpgcheck=1 gpgkey=https://copr-be.cloud.fedoraproject.org/results/@kdesig/cmake3_EPEL/pubkey.gpg repo_gpgcheck=0 enabled=1 enabled_metadata=1' >> /etc/yum.repos.d/cmake3.repo

yum install cmake3

sudo yum install centos-release-scl sudo yum install devtoolset-9-gcc* scl enable devtoolset-9 bash gcc -v

cmake .
make

Infer a decision tree with the algorithm DT_depth for the dataset "mouse":

./InferDT -d data/mouse.csv -v infer

Infer a decision tree with the algorithm DT_size for the dataset "car":

./InferDT data/car.csv -v infer

Run a 10-cross-validation on the dataset "mouse" with the algorithm DT_size:

./InferDT data/mouse.csv bench

Infer a decision tree with the algorithm DT_size for the training set balance-scale.csv.train1 and evaluate the model with the testing set balance-scale.csv.test1:

./InferDT data/balance-scale.csv.train1.csv infer -t data/balance-scale.csv.test1.csv

Print a help message:

./InferDT --help

We ran experiments on Ubuntu with Intel Core CPU i7-2600K @ 3.40 GHz.

The datasets we used are extracted from the paper of Verwer and Zhang and are available at (https://github.com/SiccoVerwer/binoct).

S: Number of examples in the dataset

B: Number of Boolean features in the dataset

Time DT_depth: Time used by our algorithm with parameter "-d"

Accuracy DT_depth: Accuracy of our algorithm with parameter "-d"

k: Depth of inferred decision trees

n: Number of nodes in inferred decision trees

Time DT_size: Time used by our algorithm without parameter "-d"

Accuracy DT_size: Accuracy of our algorithm without parameter "-d"

Accuracy BinOCT: Accuracy of algorithm from https://github.com/SiccoVerwer/binoct

We used dataset Mouse that the authors Bessiere, Hebrard and O'Sullivan shared with us. Each entry in rows DT_size and DT_depth corresponds to the average over 100 runs. The first columns correspond to the name of each algorithm used. The next three columns correspond to inferring a decision tree from the whole dataset. The last column corresponds the 10-fold cross-validations.

In this section we perform x 10-cross-validations made randomly and record the average.

S: Number of examples in the dataset

B: Number of Boolean features in the dataset

k: Average depth of inferred decision trees

n: Average number of nodes in inferred decision trees

x: Number of 10-cross-validation performed