Source: id3.js

/*
 * @fileoverview Clase para realizar clasificación generando un árbol ID3.
 *
 * Generado como parte del proyecto CAIM+BAYES+ID3+CV K-FOLDS.
 * 
 * @author Fernando MM
 * @version 1.0
 * @date 2024-04-24
 * 
 * Dependencias:
 * - arffDataSet.js
 * - caimDiscretizer.js
 * 
 * Historial de cambios:
 * - 1.0 (2024-04-24): Creación de la librería.
 * 
 */
/**
 * @class La clase ID3 crea un árbol de decisión.
 */
class ID3 {
    constructor() {
        /**
        * @type {object}
        */
        this.tree = null; // Almacena árbol de decisiones.
    }
    /**
     * @description Regresa el nombre del modelo usado.
     * @returns {string}
    */
    getClassifierName(){
        return "ID3";
    }
    /**
     * @description Entrena el modelo con un conjunto de datos de características (X) y etiquetas de clase (y).
     * @param {Array} X Representa las características de las instancias.
     * @param {Array} y Representa las etiquetas de clase correspondientes.
    */
    train(X, y) {
        const data = X.map((features, index) => [...features, y[index]]);
        this.tree = this.buildTree(data, X[0].map((_, index) => index));
    }
    /**
     * @description Construye el árbol de decisión usando el algoritmo ID3.
     * @param {Array} data Representa cada una de las instancias del conjunto de datos.
     * @param {Array} features Representa los atributos de las instancias.
     * @returns {object}
    */
    buildTree(data, features) {
        if (data.length === 0) return null;

        const classes = data.map(row => row[row.length - 1]);
        if (new Set(classes).size === 1) return { label: classes[0] };

        if (features.length === 0) {
            const majorityClass = this.majorityClass(classes);
            return { label: majorityClass };
        }

        const bestFeature = this.chooseBestFeature(data, features);
        const tree = { feature: bestFeature, branches: {} };

        const featureValues = new Set(data.map(row => row[bestFeature]));
        featureValues.forEach(value => {
            const subset = data.filter(row => row[bestFeature] === value);
            const newFeatures = features.filter(f => f !== bestFeature);
            tree.branches[value] = this.buildTree(subset, newFeatures);
        });

        return tree;
    }
    /**
     * @description Calcula la clase mayoritaria.
     * @param {Array} classes Representa las clases del conjunto de datos.
     * @returns {Array}
    */
    // Calcula la clase mayoritaria.
    majorityClass(classes) {
        const classCounts = classes.reduce((count, label) => {
            count[label] = (count[label] || 0) + 1;
            return count;
        }, {});

        return Object.keys(classCounts).reduce((a, b) => classCounts[a] > classCounts[b] ? a : b);
    }
    /**
     * @description Elige la mejor característica para dividir el conjunto de datos.
     * @param {Array} data Representa cada una de las instancias del conjunto de datos.
     * @param {Array} features Representa los atributos de las instancias.
     * @returns {Array}
    */
    chooseBestFeature(data, features) {
        let bestFeature = features[0];
        let bestInformationGain = 0;
        const baseEntropy = this.calculateEntropy(data.map(row => row[row.length - 1]));

        features.forEach(feature => {
            const values = data.map(row => row[feature]);
            const entropy = this.calculateEntropyForFeature(values, data);
            const informationGain = baseEntropy - entropy;
            if (informationGain > bestInformationGain) {
                bestInformationGain = informationGain;
                bestFeature = feature;
            }
        });

        return bestFeature;
    }
    /**
     * @description Calcula la entropía de un conjunto de clases.
     * @param {Array} classes Representa las clases del conjunto de datos.
     * @returns {object}
    */
    calculateEntropy(classes) {
        const classCounts = classes.reduce((count, label) => {
            count[label] = (count[label] || 0) + 1;
            return count;
        }, {});

        return Object.values(classCounts).reduce((entropy, count) => {
            const p = count / classes.length;
            return entropy - p * Math.log2(p);
        }, 0);
    }
    /**
     * @description Calcula la entropía condicional para una característica específica.
     * @param {Array} values Representa un conjunto de atributos.
     * @param {Array} data Representa todas las instancias del conjunto de datos.
     * @returns {object}
    */
    calculateEntropyForFeature(values, data) {
        const uniqueValues = new Set(values);
        let entropySum = 0;
        uniqueValues.forEach(value => {
            const subset = data.filter((row, index) => values[index] === value);
            const weight = subset.length / data.length;
            const subsetEntropy = this.calculateEntropy(subset.map(row => row[row.length - 1]));
            entropySum += weight * subsetEntropy;
        });
        return entropySum;
    }
    /**
     * @description Predice las clases de un nuevo conjunto de datos de características (X).
     * @param {Array} X Datos para predicción.
     * @returns {Array}
    */
    predict(X) {
        return X.map(instance => this.predictInstance(instance, this.tree));
    }
    /**
     * @description Método auxiliar para predecir la clase de una única instancia usando el árbol.
     * @param {Array} instance Datos para predicción.
     * @returns {Array}
    */
    predictInstance(instance, node) {
        if (node.label !== undefined) return node.label;
        const branch = node.branches[instance[node.feature]];
        if (!branch) {
            // Si no hay una rama que corresponda al valor de la instancia, elige un nodo aleatorio.
            const randomBranch = Object.values(node.branches)[0];
            return this.predictInstance(instance, randomBranch);
        }
        return this.predictInstance(instance, branch);
    }
}
/*
// Ejemplo de uso similar al  NaiveBayes
const id3 = new ID3();
const X = [
    [1, 1],
    [1, 0],
    [0, 1],
    [0, 0]
];
const y = ['yes', 'yes', 'no', 'no'];
id3.train(X, y);
const newInstances = [
    [1, 1],
    [0, 0]
];
const predictions = id3.predict(newInstances);
console.log("Predicciones:", predictions);
*/