I am currently working on a very beginners version of the ID3 machine learning algorithm. I am stuck on how to recursively call my build_tree function to actually make the rest of the decision tree and output it in a nice format. I have calculated gains, entropies, gain ratios, etc. but I have no clue how to integrate recursion into my function.

I am given a data set, which after doing all the calculations mentioned above, have split it into two datasets. Now I need to be able to recursively call it until both the left and right data sets become pure [which can easily be checked by a function i wrote called dataset.is_pure()], all while keeping track of the threshold at each node. I know that all my calculations and split methods are working as I have done individuual testing on them. It is just the recursive part that I am having trouble with.

Here is my build_tree function that I am having a recursion nightmare with. I am currently working in a linux environment with the g++ compiler. The code I have right now compiles, but when run gives me a segmentation error. Any and all help would be greatly appreciated!

   struct node
            vector<vector<string>> data;
            double atrb;
            node* parent;
            node* left = NULL;
            node* right = NULL;

            node(node* parent) : parent(parent) {}

    node* root = new node(NULL);

    void build_tree(node* current, dataset data_set)
            vector<vector<string>> l_d;
            vector<vector<string>> r_d;

            double global_entropy = calc_entropy(data_set.get_col(data_set.n_col()-1));

            int best_col = this->get_best_col(data_set, global_entropy);

            hash_map selected_atrb(data_set.n_row(), data_set.truncate(best_col));
            double threshold = get_threshold(selected_atrb, global_entropy);
            cout << threshold << "\n";

            split_data(threshold, best_col, data_set, l_d, r_d);

            dataset right_data(r_d);
            dataset left_data(l_d);


                    node* new_left = new node(current);
                    new_left->atrb = threshold;
                    current->left = new_left;
                    new_left->data = l_d;
                    return build_tree(new_left, left_data);

                    node* new_right = new node(current);
                    new_right->atrb = threshold;
                    current->right = new_right;
                    new_right->data = r_d;
                    return build_tree(new_right, right_data);

    id3(dataset data)
            build_tree(root, data);


This is only a part of my class. If you wish to see any other code, just let me know!

  • This doesn't look like java; it looks like c++. Are you sure you have tagged your question correctly ? – Erwin Bolwidt Dec 2 '18 at 11:38
  • @ErwinBolwidt Sorry about that. It was about 3am when i posted the question :/ I've updated the tags, thanks for pointing it out! – nitish mallavarapu Dec 2 '18 at 20:26


I will explain to you with pseudocodigo how the reclusive function works, I will also leave you the code that you make in javascript for the implementation of said algorithm.

Before going into detail, I will mention certain concepts and classes you use.

  • Attribute: Characteristic of the data set, it is usually the name of a column of the data set.
  • Class: Decision characteristic, it is generally of binary value and usually it is always the last column of the data set.
  • Value: Possible value of the attribute in the data set, for example (Sunny, Cloudy, Rainy)
  • Tree: classes that have a number of nodes associated with each other.
  • Node: Entity in charge of storing the attribute (question), also has a list with the arcs.

  • Arc: Contains the value of an attribute and has an attribute that will contain the following child node.

  • Leaf : Contains a class. This node is the result of a decision, for example (Yes or No).

  • Best feature: Attribute with the highest information gain.

Function to create the tree from a set of data:

  • Obtain the values ​​of a class.
  • Evaluate if there is only one type of class in the data set, for example (Yes).   
  • If true, then we create a Leaf object and return this object
  • Obtain the information gain of each current attribute.
  • Choose the attribute with the highest information gain.
  • Create a node with the best feature.
  • Obtain the values ​​of the best feature.
  • Iterate the list of those values.

    • Filter the list, so that there are only records with the value that we are iterating (save it in a variable temporary)

    • Create an Arc with this value.      - Assign the following attribute to the Arc: (Here comes the recursion) call again the same only function that you send (the filtered list of records, the class, the list of attributes without the best feature, the list of general attributes without the attributes of the best feature)

    • Add the arc to the node.
  • Return the node.

This would be the segment of code that is responsible for creating the tree

let crearArbol = (ejemplosLista, clase, atributos, valores) => {
        let valoresClase = obtenerValoresAtributo(ejemplosLista, clase);
        if (valoresClase.length == 1) {
            return new Hoja(valoresClase[0], autoIncremental);

        if (atributos.length == 0) {
            let claseDominante = claseMayoritaria(ejemplosLista);
            return new Atributo();

        let gananciaAtributos = obtenerGananciaAtributos(ejemplosLista, valores, atributos);
        let atributoMaximo = atributos[maximaGanancia(gananciaAtributos)];

        let nodo = new Atributo(atributoMaximo, [], autoIncremental);
        let valoresLista = obtenerValoresAtributo(ejemplosLista, atributoMaximo);

        valoresLista.forEach((valor) => {
            let ejemplosFiltrados = arrayDistincAtributos(ejemplosLista, atributoMaximo, valor);
            let arco = new Arco(valor);
            arco.sigNodo = crearArbol(ejemplosFiltrados, clase, [...eliminarAtributo(atributoMaximo, atributos)], [...eliminarValores(atributoMaximo, valores)]);

        return nodo;

Unfortunately, the code is only in Spanish. This is the repository that contains my project with this implementation Source code of id3

Your Answer

