c++ - 使用递归的机器学习算法

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

};

这只是我类(class)的一部分。如果您想查看任何其他代码，请告诉我!

Answer 1

问候，

我将用pseudocodigo 向您解释reclusive 函数是如何工作的，我还将把您在javascript 中编写的用于实现所述算法的代码留给您。

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

• Attribute:数据集的特征，通常是数据集的列名。
• 类:决策特征，一般为二进制值，通常总是数据集的最后一列。
• Value:数据集中属性的可能值，例如(Sunny、Cloudy、Rainy)
• 树:具有许多相互关联的节点的类。

• 节点:负责存储属性(问题)的实体，也有一个包含弧的列表。

• Arc:包含一个属性的值，并且有一个属性将包含以下子节点。

• 叶子: 包含一个类。此节点是决定的结果，例如(是或否)。

• 最佳特征:具有最高信息增益的属性。

根据一组数据创建树的函数:

• 获取类的值。
• 评估数据集中是否只有一种类型的类，例如(是)。
• 如果为真，那么我们创建一个 Leaf 对象并返回这个对象
• 获取每个当前属性的信息增益。
• 选择信息增益最高的属性。
• 创建一个具有最佳特征的节点。
• 获取最佳特征的值。

• 迭代这些值的列表。

  • 过滤列表，以便只有具有我们正在迭代的值的记录(将其保存在临时变量中)

  • 用这个值创建一个 Arc。- 将以下属性分配给 Arc:(这里是递归)再次调用您发送的相同的唯一函数(过滤的记录列表，类，没有最佳特征的属性列表，没有最佳特征的一般属性列表最佳特征的属性)

  • 将弧添加到节点。
• 返回节点。

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

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

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