¿Cuál es la mejor manera de almacenar una tabla en C ++?

Estoy programando un árbol de decisión en C ++ usando una versión ligeramente modificada del algoritmo C4.5 . Cada nodo representa un atributo o una columna de su conjunto de datos y tiene un elemento secundario por valor posible del atributo.

Mi problema es cómo almacenar el conjunto de datos de entrenamiento teniendo en cuenta que tengo que usar un subconjunto para cada nodo, por lo que necesito una forma rápida de seleccionar solo un subconjunto de filas y columnas.

El objetivo principal es hacerlo con la mayor eficiencia de memoria y tiempo posible (en ese orden de prioridad).

La mejor forma en que he pensado es tener una matriz de matrices (o std :: vector), o algo así, y para cada nodo tener una lista (matriz, vector, etc.) o algo con column,line(probablemente una tupla) pares que son válidos para ese nodo.

Ahora debería haber una mejor manera de hacer esto, ¿alguna sugerencia?

ACTUALIZACIÓN: Lo que necesito es algo como esto:

Al principio tengo estos datos:

Paris    4    5.0    True
New York 7    1.3    True
Tokio    2    9.1    False
Paris    9    6.8    True
Tokio    0    8.4    False

Pero para el segundo nodo solo necesito estos datos:

Paris    4    5.0
New York 7    1.3
Paris    9    6.8

Y para el tercer nodo:

Tokio    2    9.1
Tokio    0    8.4

Pero con una tabla de millones de registros con hasta cientos de columnas.

Lo que tengo en mente es mantener todos los datos en una matriz, y luego, para cada nodo, mantener la información de las columnas y filas actuales. Algo como esto:

Paris    4    5.0    True
New York 7    1.3    True
Tokio    2    9.1    False
Paris    9    6.8    True
Tokio    0    8.4    False

Nodo 2:

columns = [0,1,2]
rows = [0,1,3]

Nodo 3:

columns = [0,1,2]
rows = [2,4]

De esta manera, en el peor de los casos, solo tengo que desperdiciar

size_of(int) * (number_of_columns + number_of_rows) * node

Eso es mucho menos que tener una matriz de datos independiente para cada nodo.

La última vez que intenté entender C4.5, fallé, pero he implementado una variante de ID3, originalmente por curiosidad, pero finalmente se usó como parte de un generador de código de despacho múltiple excesivo. Sin embargo, esto nunca trata con grandes conjuntos de datos, y es un buen trabajo. No harías bien en imitar la mayoría de lo que hice, pero tal vez con algunas excepciones, y por supuesto aprendí un poco de los errores.

Tiendo a pensar en términos de construir un árbol de decisión para un sistema experto, así que tiendo a usar los siguientes términos, perdón si eso es confuso ...

Column = Question ..... A question the expert system might ask
Row    = Conclusion ... A possible conclusion the expert system might reach
Cell   = Answer ....... For the question and conclusion, what answer should
                        the user be expected to give

En realidad, en mi caso, hice la conclusión en otra columna, similar a una tabla de verdad para una puerta lógica. Por lo tanto, los números de fila eran solo números de fila. Esto me permitió manejar problemas de estilo XOR que ni siquiera se pueden representar si la misma conclusión no puede aparecer en varias filas. No estoy seguro de si esto es relevante para usted o no. En cualquier caso, estoy ignorando esto a continuación: en realidad no hace mucha diferencia a menos que hasta que vea los detalles de elegir qué pregunta hacer de todos modos. Para la minería de datos, probablemente no tenga una información particular para tratar como la conclusión objetivo de todos modos: la "conclusión" es lo que queda cuando decide dejar de hacer preguntas.

Entonces, para cada nodo del árbol de decisión derivado hasta el momento, tiene un conjunto de preguntas pendientes (columnas) y un conjunto de conclusiones (filas) aún no eliminadas. Eso fue lo que hice. El único punto que vale la pena agregar es que utilicé vectores de bits.

IIRC, el C ++ std::vector<bool>y std::array<bool> pueden implementarse como vectores de bits, pero aún depende de los algoritmos STL para las operaciones de conjuntos, que operan un elemento a la vez. Usé mi propia clase de vector de bits que se ha ido construyendo gradualmente durante un período de tiempo y que utiliza operadores bit a bit en el subyacente std::vector<CHUNK>(donde CHUNKhay un tipo int sin signo, generalmente de 32 bits de ancho).

Puede haber una mejor opción de vector de bits en C ++ 11 o en Boost, y debe haber algunas buenas bibliotecas en algún lugar: hay muchos tipos de programas donde terminas trabajando con conjuntos de enteros sin signo. Simplemente no sé mucho sobre ellos porque he sido demasiado vago como para dejar de usar el mío.

Sin embargo, los vectores de bits son mejores cuando los conjuntos son en su mayoría densos. En este caso, el conjunto de filas es el problema obvio. Solo el nodo raíz del árbol de decisión tendrá un conjunto de filas perfectamente denso. A medida que se aleja de la raíz, los conjuntos de filas se vuelven cada vez más dispersos, y cada pregunta respondida da como resultado que el conjunto de filas se distribuya entre dos o más conjuntos de filas disjuntos del siguiente nodo.

Por lo tanto, un simple conjunto ordenado de números de fila podría ser la mejor representación para estos conjuntos. Sin embargo, también es posible que valga la pena un "vector de bits disperso". Una posible implementación es una matriz ordenada de pares donde el primero de cada par es la primera ID de fila de un bloque y el segundo es un vector de bits de tamaño fijo para ese bloque. Por ejemplo, la fila número 35 podría almacenarse en el bloque 32 ( 35 & ~(32 - 1)) en la posición de bit 3 ( 35 & (32 - 1)). Si solo guarda los pares donde el vector de bits no es cero, esto proporciona algo entre una matriz ordenada de ID y un vector de bits simple: maneja matrices dispersas razonablemente bien, especialmente cuando las ID tienden a agruparse estrechamente en conjuntos.

Además, puede valer la pena usar una clase que pueda cambiar de un vector de bits a una representación de matriz ordenada cuando el tamaño sea lo suficientemente pequeño. Sin embargo, la complicación adicional, puramente para beneficiar a unos pocos nodos cerca de la raíz, probablemente no tenga sentido.

De todos modos, sin embargo, estos conjuntos están representados, ya que se refieren a una única "base de datos" constante, esto ahorra mucho en la copia de datos y el desperdicio de espacio a medida que se ejecuta el algoritmo. Pero todavía vale la pena mirar esa "base de datos".

Utilicé una estructura de datos asociativa, lo que me permitió buscar utilizando una tupla de ID de pregunta e ID de conclusión para obtener una ID de respuesta. Eso significa que tenía una sobrecarga por elemento para la clave (ID de pregunta e ID de conclusión) y, en este caso, también sobrecarga de árbol de estilo B +. La razón, básicamente hábito. Tengo contenedores que son muy flexibles, y tiendo a usarlos mucho porque ahorra en anticipar qué capacidades necesitaré más adelante. Hay un precio por eso, pero eso es solo la vieja cosa de optimización prematura.

En su caso, está utilizando una matriz; supongo que una matriz bidimensional indexada por ID de pregunta e ID de respuesta.

La única forma en que puedo imaginar que mi versión sea más eficiente que la suya es si no se conocen la mayoría de las respuestas. En una matriz, necesita una ID de respuesta especial no conocida para eso, ocupando el mismo espacio que una ID de respuesta conocida. En un contenedor asociativo, excluye esas filas.

Aun así, una matriz ordenada sería más eficiente que mi solución basada en el árbol B +. No necesita permitir inserciones eficientes, por lo que la única sobrecarga necesaria es para las claves.

Si usa dos campos clave (pregunta y conclusión, fila y columna) eso podría ser un problema (realmente no lo recuerdo), tal vez no pueda mantener una copia de la tabla en un orden ordenado. Pero si usa una sola tecla calculada a lo largo de las líneas de (row * num_columns) + column, básicamente está implementando una matriz dispersa bidimensional de todos modos.

Para mí, la presencia de respuestas desconocidas / indefinidas para una pregunta en particular significa que todavía no puedo hacer esa pregunta, e incluso esa fue solo la teoría que usé cuando implementé el algoritmo por primera vez. En realidad nunca lo puse en uso. Hay un uso que podría utilizar, pero nunca lo logré. Para el registro, en ese generador de código de despacho múltiple, una idea era despachar en función de los campos del tipo. Como el tipo en sí es polimórfico, es posible que esos campos ni siquiera estén allí, por lo que solo es válido mirarlos una vez que haya confirmado que deben estar presentes.

Si no tiene una aplicación para respuestas desconocidas / indefinidas, su matriz existente es probablemente la mejor solución.

Básicamente, eso es todo: realmente no puedo ofrecer opciones claramente mejores, y lo que estás haciendo probablemente ya sea mejor que lo que hice. Sin embargo, hay algunas posibilidades de compensación que puede considerar, suponiendo que no sea una optimización prematura (y posiblemente falsa), por supuesto.

El principal problema de compensación se relaciona con la eficiencia de las representaciones de conjuntos de valores escasos frente a densos, por lo que no es realmente específico para C4.5 o la construcción del árbol de decisión. Y un enfoque más "sofisticado" a menudo es menos eficiente que uno simple que se eligió con cuidado.

Creo que tu idea es buena. No estoy seguro de cuán general es su biblioteca para acceder a los datos que desea ser. Pero podría algo como almacenar todos sus datos iniciales en una std::vectorde las filas. Si las columnas son invariables para usted, para el tipo de datos elegiría boost :: tuple library.

Luego, puede pasar un identificador a toda la "base de datos" a sus tipos de Nodo. Sería muy fácil recuperar / acceder a cualquier subconjunto de columnas y filas de dicha estructura. Un tipo de nodo actuaría como un tipo de objeto proxy o contenedor para acceder a los datos, actuando de alguna manera como una vista para toda la base de datos.

Además, el costo del tiempo sería constante en el tiempo, ya que se accedería directamente a los datos. La huella de memoria sería baja como mencionó, porque el costo principal es la base de datos inicial y no hay copias de los datos en sí. Solo el costo sería índices desde los vectores filas-columnas.

Sin embargo, hay una advertencia. Si habla de millones de registros y cientos de columnas, debe recordar que hay un límite de escalabilidad para la memoria. Es posible que se vea obligado a recurrir a algún sistema de base de datos real solo por las limitaciones de cantidad de memoria. Yo recomendaría probablemente SQLite. SQLite permite crear una base de datos volátil en memoria. Por lo tanto, puede usarlo inicialmente y pasar sin problemas a la base de datos de archivos normal si sus conjuntos de datos crecen demasiado.

Una cosa que puede hacer en su modelo para ahorrar espacio es administrar índices en sus nodos como matrices de bits. Entonces de tu ejemplo:

Nodo 2:

columnas = [0,1,2] = 5 o 101

filas = [0,1,3] = 11 o 1011

Nodo 3:

columnas = [0,1,2] = 5 o 101

filas = [2,4] = 20 o 10100

Esto llevaría su requerimiento de size_of (int) * (number_of_columns + number_of_rows) * node a sizeof (int) * 2 * node

Este enfoque restringirá su dimensión de matriz a un tamaño de columnas (int) y el mismo número de filas. Para superar esta limitación (especialmente fuerte en las filas), puede almacenarlos en bloques. En ese caso, necesitará un nuevo número entero en cada nodo que especifique el bloque, haciendo que su tamaño de índice total sea sizeof (int) * 3 * nodo que aún es menor que size_of (int) * (number_of_columns + number_of_rows) * node