基于递归的机器学习算法

Question

我目前正在研究ID3机器学习算法的一个非常初级的版本。在如何递归调用我的build_tree函数以实际生成决策树的其余部分并以一种很好的格式输出它时，我陷入了困境。我计算了增益、熵、增益比等，但我不知道如何将递归集成到我的函数中。

给我一个数据集，在做完上述所有的计算之后，将它分成两个数据集。现在，我需要能够递归地调用它，直到左数据集和右数据集变得纯净为止，我编写的函数dataset.is_pure()可以很容易地检查这些数据集，同时跟踪每个节点的阈值。我知道我所有的计算和分裂方法都在起作用，就像我对它们进行了个别测试一样。这只是我遇到麻烦的递归部分。

下面是我的build_tree函数，我正在做一个递归噩梦。我目前正在g++编译器的linux环境中工作。我现在拥有的代码会编译，但运行时会出现分段错误。任何和所有的帮助都将不胜感激！

   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);

            right_data.delete_col(best_col);
            left_data.delete_col(best_col);

            if(left_data.is_pure())
                    return;
            else
            {
                    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);
            }

            if(right_data.is_pure())
                    return;
            else
            {
                    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);
    }

}；

这只是我班上的一部分。如果你想看其他代码，请告诉我！

Answer 1

致以敬意，

我将用伪代码向您解释隐秘函数是如何工作的，我还将留给您在javascript中为实现上述算法而编写的代码。

在详细介绍之前，我将提到您使用的某些概念和类。

• 属性:数据集的特征，它通常是数据集列的名称。
• 类：决策特征，通常是二进制值，通常是数据集的最后一列。
• 值:数据集中属性的可能值，例如(Sunny，Cloudy，Rainy)
• 树:具有多个节点相互关联的类。
• 节点:负责存储属性(问题)的实体，也有一个带有arcs的列表。
• 圆弧：包含属性值，并具有将包含以下子节点的属性。
• 叶子:包含一个类。此节点是决策的结果，例如(是或否)。
• 最佳特性:具有最高信息增益的属性。

函数从一组数据创建树：

• 获取类的值​​。
• 计算数据集中是否只有一种类型的类，例如(是).   
• 如果为true，则创建叶子对象并返回此对象
• 获取每个当前属性的信息增益。
• 选择信息增益最高的属性。
• 创建一个具有最佳功能的节点。
• 获得最佳特性的值​​。
• 迭代这些值的列表。

- 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.

​

• 返回节点。

这将是负责创建树的代码段。

let crearArbol = (ejemplosLista, clase, atributos, valores) => {
        let valoresClase = obtenerValoresAtributo(ejemplosLista, clase);
        if (valoresClase.length == 1) {
            autoIncremental++;
            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)];

        autoIncremental++;
        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)]);
            nodo.hijos.push(arco);
        });

        return nodo;
    };

不幸的是，代码只有西班牙语。这是包含有此实现id3源代码的项目的存储库。