/*
* @fileoverview Clase para discretizar un conjunto de datos numéricos en función de las
* clases a las que pertenece usando el algoritmo CAIM (class-attribute interdependence maximization)
*
* Basado en el algoritmo publicado por:
* L. A. Kurgan and K. J. Cios, "CAIM discretization algorithm," in IEEE Transactions on Knowledge and Data Engineering, vol. 16, no. 2, pp. 145-153, Feb. 2004, doi: 10.1109/TKDE.2004.1269594.
*
* Generado como parte del proyecto CAIM+BAYES+CV K-FOLDS.
*
* @author Fernando MM
* @version 1.0
* @date 2024-04-10
*
* Historial de cambios:
* - 1.0 (2024-04-10): Creación de la librería.
*/
/* ALGORITMO DE DISCRETIZACIÓN CAIM.
FUENTE: L. A. Kurgan and K. J. Cios, "CAIM discretization algorithm," in IEEE Transactions on Knowledge and Data Engineering, vol. 16, no. 2, pp. 145-153, Feb. 2004, doi: 10.1109/TKDE.2004.1269594.
Table 1. 2-D quanta matrix for attribute F and discretization scheme D
----------------------------------------------
2.2. Discretization Criterion
CAIM(C,D|F) = (SUMA[1 a n](max_r^2/M_+r)) / n
LAtex: \text{CAIM}(C, D \mid F) = \frac{\sum_{r=1}^n \left(\max_r\right)^2 / M_{+r}}{n}
----------------------------------------------
The pseudocode of the CAIM algorithm is as follows:
Given: Data consisting of M examples, S classes, and continuous attributes Fi
For every Fi do:
Step1.
1.1 find maximum (dn) and minimum (d0) values of Fi
1.2 form a set of all distinct values of Fi in ascending order, and initialize all possible interval boundaries B with minimum, maximum and all the midpoints of all the adjacent pairs in the set
1.3 set the initial discretization scheme as D: {[d0 ,dn]} , set GlobalCAIM=0
Step2.
2.1 initialize k=1;
2.2 tentatively add an inner boundary, which is not already in D, from B, and calculate corresponding CAIM value
2.3 after all the tentative additions have been tried accept the one with the highest value of CAIM
2.4 if (CAIM > GlobalCAIM or k<S) then update D with the accepted in step 2.3 boundary and set GlobalCAIM=CAIM, else terminate
2.5 set k=k+1 and go to 2.2
Output: Discretization scheme D
*/
class CAIMDiscretizer {
/**
* @description La clase CAIMDiscretizer discretiza un conjunto de datos numéricos en función de las
* clases a las que pertenece usando el algoritmo CAIM (class-attribute interdependence maximization)
*/
constructor(data, labels) {
this.data = data;
this.labels = labels;
this.classes = [...new Set(labels)];
this.boundaries = [];
}
/**
*
* @description Realiza la discretización de los datos según los pasos planteados en el artículo de L. A. Kurgan and K. J. Cios, "CAIM discretization algorithm," in IEEE Transactions on Knowledge and Data Engineering, vol. 16, no. 2, pp. 145-153, Feb. 2004, doi: 10.1109/TKDE.2004.1269594.
* @returns {Array} El esquema de discretización D que almacena el conjunto de límites mínimos y máximos de cada intervalo
*/
discretize() {
// 1.2 form a set of all distinct values of Fi in ascending order, and initialize all possible
// interval boundaries B with minimum, maximum and all the midpoints of all the adjacent pairs in the set
const intervalsB = [...new Set(this.data)].sort((a, b) => a - b);
// 1.1 find maximum (dn) and minimum (d0) values of Fi
// Los pasos se invierten por practicidad funcional, ya que el punto 1.2 facilita conseguir min y max
const min = intervalsB[0];
const max = intervalsB[intervalsB.length - 1];
console.log(intervalsB);
console.log(`min: ${min} max: ${max}`);
console.log(this.labels);
// 1.3 set the initial discretization scheme as D: {[d0 ,dn]} , set GlobalCAIM=0
// Aquí el esquema de discretización D se implementa como this.boundaries que será una propiedad pública
this.boundaries = [min, max];
let globalCAIM = 0;
const threshold = 0.01; // Valor mínimo de mejora requerido para aceptar un nuevo límite potencial
let improvement = true; //??
// 2.1 initialize k=1;
// En la implementación se usará una bandera que repetira el proceso mientras algún nuevo valor ofrezca una mejora en los intervalos
while (improvement) {
// Se asume inicialmente que el ciclo no generará ninguna mejora.
improvement = false;
// Se inicializa bestLocalCAIM a globalCAIM para garantizar que el nuevo límite propuesto ofrezca una mejora real al conjunto.
let bestLocalCAIM = globalCAIM;
let bestBoundary = null; // Almacenará el mejor valor límite encontrado en la iteración para su potencial anexión.
for (let i = 0; i < intervalsB.length - 1; i++) {
// 2.2.a tentatively add an inner boundary, ...
// Se seleccionan valores intermedios entre intervalos porque de acuerdo a (Fayyad 1993), mejoran la probabilidad de una clasificación acertada.
// “Multi-Interval Discretization of Continuous-Valued Attributes for Classification Learning” Usama M. Fayyad, Keki B. Irani. IJCAI 1993,
// Pro. of the Thirteenth International Joint Conference on Artificial Intelligence, Vol. 2, pp. 1022-1027, Morgan Kaufmann, Chambe’ry, France, August (1993).
// https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=1dc53b91327cab503acc0ca5afb9155882b717a5
const potentialBoundary = (intervalsB[i] + intervalsB[i + 1]) / 2;
// 2.2.b ...which is not already in D, from B, ...
if (!this.boundaries.includes(potentialBoundary)) {
// 2.2.c ...and calculate corresponding CAIM value
// Se genera una copia dado que aún no es decisivo que será aceptado.
const newBoundaries = [...this.boundaries, potentialBoundary].sort((a, b) => a - b);
const localCAIM = this.calculateCAIM(newBoundaries);
console.log(`potentialBoundary: ${potentialBoundary} | bestBoundary: ${bestBoundary} | localCAIM: ${localCAIM} | bestLocalCAIM: ${bestLocalCAIM} | globalCAIM: ${globalCAIM} | `);
// 2.3 after all the tentative additions have been tried accept the one with the highest value of CAIM
// Garantiza que exista una mejora real con respecto al mejor previamente encontrado agregando un valor de threshold
if (localCAIM > (bestLocalCAIM + threshold)) {
console.log(`[SELECTED] improvement: ${localCAIM - (bestLocalCAIM + threshold)} | bestBoundary: ${bestBoundary} | bestLocalCAIM: ${bestLocalCAIM}`);
bestLocalCAIM = localCAIM;
bestBoundary = potentialBoundary;
improvement = true;
}
}
}
// 2.4 if (CAIM > GlobalCAIM or k<S) then update D with the accepted in step 2.3 boundary and set GlobalCAIM=CAIM, else terminate
// Esta verificación se hace localmente de manera continua con (localCAIM > bestLocalCAIM + threshold), pero aquí se actualiza
// D implementado como this.boundaries
if (improvement && bestBoundary !== null) {
console.log(`[ADDED] bestBoundary: ${bestBoundary} | bestLocalCAIM: ${bestLocalCAIM} | globalCAIM: ${globalCAIM}`);
this.boundaries.push(bestBoundary);
this.boundaries.sort((a, b) => a - b);
globalCAIM = bestLocalCAIM;
}
// 2.5 set k=k+1 and go to 2.2
// No hay necesidad de un contador pues el ciclo se continua mientras haya una mejora
// De acuerdo a 2.4 (CAIM > GlobalCAIM or k<S) significa que no podría haber más límites que clases?? -.^?
}
//Output: Discretization scheme D
return this.boundaries;
}
/*
// 2.2. Discretization Criterion
// CAIM(C,D|F) = (SUMA[1 a n](max_r^2/M_+r)) / n
// Evalúa la calidad de una serie de intervalos (o límites) especificados para la discretización de datos, calculando el índice CAIM
*/
/**
*
* @param {Array} boundaries Arreglo de los límites de los intervalos
* @returns {number} Valor CAIM normalizado
*/
calculateCAIM(boundaries) {
// Construye la matriz de cuantización para los límites dados
const quantaMatrix = this.buildQuantaMatrix(boundaries);
const totalValues = this.data.length; //n
let caim = 0;
// SUMA[1 a n]
for (let i = 0; i < boundaries.length - 1; i++) {
let sumq = 0;
// Máximo en el intervalo (max_r)
let maxq = 0;
for (let c = 0; c < this.classes.length; c++) {
// Obtiene el número de elementos de la clase c en el intervalo i
const q = quantaMatrix[c][i];
// Suma de elementos en el intervalo (M_r)
sumq += q;
if (q > maxq) {
maxq = q;
}
}
// Calcula el valor CAIM para el intervalo y lo suma al total
// SUMA[1 a n](max_r^2/M_+r)
caim += (maxq * maxq) / (sumq || 1);
}
// Normaliza el valor CAIM por el número de intervalos
// SUMA[1 a n](max_r^2/M_+r) / n
return caim / (boundaries.length - 1);
}
/*
// Table 1. 2-D quanta matrix for attribute F and discretization scheme D
// Construye una matriz de cuantización que representa la distribución de los valores de datos entre diferentes intervalos para cada clase
*/
/**
*
* @param {Array} boundaries Arreglo de los límites de los intervalos
* @returns {Array} Matriz Quanta
*/
buildQuantaMatrix(boundaries) {
// Crea un mapa para indexar las clases por su nombre
const classIndex = new Map(this.classes.map((c, i) => [c, i]));
const intervals = boundaries.length - 1;
// Crea una matriz inicializada en cero
const matrix = Array.from({ length: this.classes.length }, () => Array(intervals).fill(0));
this.data.forEach((value, idx) => {
const label = this.labels[idx];
// Obtiene el índice de la clase correspondiente a la etiqueta
const classIdx = classIndex.get(label);
for (let i = 0; i < intervals; i++) {
// Si el valor está dentro del intervalo actual...
if (value >= boundaries[i] && value < boundaries[i + 1]) {
// Incrementa el contador en la matriz de cuantización
matrix[classIdx][i]++;
// Sale del ciclo una vez incrementado el contador para evitar múltiples conteos
break;
}
}
});
return matrix;
}
}
/* EJEMPLO JAVASCRIPT
const X = [5.1,4.9,4.7,4.6,5,5.4,4.6,5,4.4,4.9,5.4,4.8,4.8,4.3,5.8,5.7,5.4,5.1,5.7,5.1,5.4,5.1,4.6,5.1,4.8,5,5,5.2,5.2,4.7,4.8,5.4,5.2,5.5,4.9,5,5.5,4.9,4.4,5.1,5,4.5,4.4,5,5.1,4.8,5.1,4.6,5.3,5,7,6.4,6.9,5.5,6.5,5.7,6.3,4.9,6.6,5.2,5,5.9,6,6.1,5.6,6.7,5.6,5.8,6.2,5.6,5.9,6.1,6.3,6.1,6.4,6.6,6.8,6.7,6,5.7,5.5,5.5,5.8,6,5.4,6,6.7,6.3,5.6,5.5,5.5,6.1,5.8,5,5.6,5.7,5.7,6.2,5.1,5.7,6.3,5.8,7.1,6.3,6.5,7.6,4.9,7.3,6.7,7.2,6.5,6.4,6.8,5.7,5.8,6.4,6.5,7.7,7.7,6,6.9,5.6,7.7,6.3,6.7,7.2,6.2,6.1,6.4,7.2,7.4,7.9,6.4,6.3,6.1,7.7,6.3,6.4,6,6.9,6.7,6.9,5.8,6.8,6.7,6.7,6.3,6.5,6.2,5.9];
const y = ['Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-setosa','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-versicolor','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica','Iris-virginica'];
const discretizer = new CAIMDiscretizer(X, y);
const boundaries = discretizer.discretize();
console.log('Cortes discretizados:', boundaries);
*/