Qual é a melhor maneira de armazenar uma tabela em C ++

Estou programando uma árvore de decisão em C ++ usando uma versão ligeiramente modificada do algoritmo C4.5 . Cada nó representa um atributo ou uma coluna do seu conjunto de dados e possui um filho por valor possível do atributo.

Meu problema é como armazenar o conjunto de dados de treinamento, tendo em mente que tenho que usar um subconjunto para cada nó, portanto, preciso de uma maneira rápida de selecionar apenas um subconjunto de linhas e colunas.

O objetivo principal é fazê-lo com a maior economia de memória e tempo possível (nessa ordem de prioridade).

A melhor maneira que pensei é ter uma matriz de matrizes (ou std :: vector), ou algo assim, e para cada nó ter uma lista (matriz, vetor, etc) ou algo com a column,line(provavelmente uma tupla) pares que são válidos para esse nó.

Eu agora deve haver uma maneira melhor de fazer isso, alguma sugestão?

UPDATE: O que eu preciso é algo como isto:

No começo eu tenho esses dados:

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

Mas para o segundo nó, eu só preciso desses dados:

Paris    4    5.0
New York 7    1.3
Paris    9    6.8

E para o terceiro nó:

Tokio    2    9.1
Tokio    0    8.4

Mas com uma tabela de milhões de registros com até centenas de colunas.

O que tenho em mente é manter todos os dados em uma matriz e, para cada nó, manter as informações das colunas e linhas atuais. Algo assim:

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

Nó 2:

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

Nó 3:

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

Desta forma, no pior cenário, eu só tenho que desperdiçar

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

Isso é muito menos do que ter uma matriz de dados independente para cada nó.

Na última vez que tentei entender o C4.5, falhei, mas implementei uma variante do ID3 - originalmente por curiosidade, mas ele acabou sendo usado como parte de um gerador de código de despacho múltiplo por excesso de capacidade. Porém, isso nunca lida com grandes conjuntos de dados e é um bom trabalho. Você não faria bem em imitar a maior parte do que eu fiz, mas talvez com algumas exceções, e é claro que aprendi um pouco com os erros.

Costumo pensar em termos de construção de uma árvore de decisão para um sistema especialista, por isso uso os seguintes termos - desculpe se isso é 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

Na verdade, no meu caso, concluí em outra coluna - semelhante a uma tabela de verdade para um portão lógico. Os números de linha eram, portanto, apenas números de linha. Isso me permitiu lidar com problemas no estilo XOR que nem sequer podem ser representados se a mesma conclusão não puder aparecer em várias linhas. Não tenho certeza se isso é relevante para você ou não. De qualquer forma, estou ignorando isso abaixo - isso realmente não faz muita diferença, a menos que você veja os detalhes da escolha de qual pergunta fazer a seguir. Para a mineração de dados, você provavelmente não tem uma informação específica a ser tratada como a conclusão desejada - a "conclusão" é apenas o que resta quando você decide parar de fazer perguntas.

Portanto - para cada nó da árvore de decisão derivado até agora, você tem um conjunto de perguntas pendentes (colunas) e um conjunto de conclusões (linhas) ainda não eliminadas. Isso é o que eu fiz. O único ponto que vale a pena acrescentar é que eu usei vetores de bits.

O IIRC, o C ++, std::vector<bool>e std::array<bool> pode ser implementado como vetor de bits, mas você ainda depende dos algoritmos STL para operações definidas, que operam um item por vez. Eu usei minha própria classe de vetor de bits que foi gradualmente construída ao longo de um período de tempo e que usa operadores bit a bit no subjacente std::vector<CHUNK>(onde CHUNKé um tipo int sem sinal, geralmente com 32 bits de largura).

Pode haver uma opção melhor de vetor de bits no C ++ 11 ou no Boost, e deve haver algumas boas bibliotecas por aí - onde há vários tipos de programas nos quais você acaba trabalhando com conjuntos de números inteiros não assinados. Só não sei muito sobre eles porque tenho preguiça de deixar de usar os meus.

No entanto, os vetores de bits são melhores quando os conjuntos são densos. Nesse caso, o conjunto de linhas é o problema óbvio. Somente o nó raiz da árvore de decisão terá um conjunto de linhas perfeitamente denso. À medida que você se distancia da raiz, os conjuntos de linhas ficam cada vez mais escassos, com cada pergunta respondida, resultando no conjunto de linhas distribuídas entre dois ou mais conjuntos de linhas do próximo nó separados.

Portanto, uma simples matriz classificada de números de linhas pode ser a melhor representação para esses conjuntos. No entanto, também é possível que um "vetor de bits esparso" valha a pena. Uma implementação possível é uma matriz classificada de pares, em que o primeiro de cada par é o primeiro ID da linha de um bloco e o segundo é um vetor de bits de tamanho fixo para esse bloco. Por exemplo, o número da linha 35 pode ser armazenado no bloco 32 ( 35 & ~(32 - 1)) na posição de bit 3 ( 35 & (32 - 1)). Se você salvar apenas os pares em que o vetor de bits é diferente de zero, isso fornece algo entre uma matriz classificada de IDs e um vetor de bits simples - ele lida com matrizes esparsas razoavelmente bem, especialmente quando as IDs tendem a se agrupar em conjuntos.

Além disso, pode valer a pena usar uma classe que pode alternar de um vetor de bits para uma representação de matriz classificada quando o tamanho é pequeno o suficiente. A complicação extra, apenas para beneficiar alguns nós próximos à raiz, é provavelmente inútil.

De qualquer forma, porém, esses conjuntos são representados, pois se referem a um único "banco de dados" constante, economizando muito na cópia de dados e no desperdício de espaço à medida que o algoritmo é executado. Mas ainda vale a pena olhar para esse "banco de dados".

Usei uma estrutura de dados associativa, permitindo pesquisar usando uma tupla de ID de pergunta e ID de conclusão para obter um ID de resposta. Isso significa que eu tinha uma sobrecarga por item para a chave (ID da pergunta e ID da conclusão) e, neste caso, a sobrecarga da árvore no estilo B + também. A razão - basicamente hábito. Tenho contêineres muito flexíveis, e costumo usá-los muito, pois economiza em antecipar quais recursos realmente precisarei mais tarde. Há um preço por isso, mas isso é apenas a velha coisa de otimização prematura.

No seu caso, você está usando uma matriz - presumo que uma matriz bidimensional indexada por ID de pergunta e ID de resposta.

A única maneira de imaginar minha versão mais eficiente que a sua é se a maioria das respostas não for conhecida. Em uma matriz, você precisa de um ID de resposta não conhecido especial para isso, ocupando o mesmo espaço que um ID de resposta conhecido. Em um contêiner associativo, você exclui essas linhas.

Mesmo assim, uma matriz classificada seria mais eficiente do que minha solução baseada em árvore B +. Você não precisa permitir inserções eficientes; portanto, a única sobrecarga necessária é para as chaves.

Se você usar dois campos-chave (pergunta e conclusão, linha e coluna) que podem ser um problema (não me lembro) - talvez você não possa simplesmente manter uma cópia da tabela em uma ordem classificada. Mas se você usar uma única chave computada ao longo das linhas de (row * num_columns) + column, estará basicamente implementando uma matriz esparsa bidimensional.

Para mim, a presença de respostas desconhecidas / indefinidas para uma pergunta em particular significa que ainda não estou autorizado a fazer essa pergunta - e mesmo essa foi apenas a teoria que usei quando implementei o algoritmo. Eu nunca coloquei isso em prática. Há um uso que eu poderia colocar, mas nunca cheguei a isso. Para o registro, naquele gerador de código de despacho múltiplo, uma idéia era despachar com base nos campos do tipo. Como o tipo em si é polimórfico, esses campos podem nem estar lá; portanto, é válido apenas examiná-los depois de confirmar que eles devem estar presentes.

Se você não possui um aplicativo para respostas desconhecidas / indefinidas, sua matriz existente provavelmente já é a melhor solução.

Então, basicamente, é isso - eu realmente não posso oferecer opções claramente melhores, e o que você está fazendo provavelmente já é melhor do que eu fiz. No entanto, existem algumas possibilidades de troca que você pode considerar - supondo que não seja uma otimização prematura (e possivelmente falsa), é claro.

A principal questão do trade-off refere-se à eficiência das representações de conjuntos de valores esparsos vs. densos, portanto, não é realmente específico do C4.5 ou da construção da árvore de decisão. E uma abordagem mais "sofisticada" geralmente é menos eficiente do que uma abordagem simples, escolhida com cuidado.

Eu acho que sua ideia é boa. Não tenho certeza de quão geral é sua biblioteca para acessar os dados que você deseja ser. Mas você pode armazenar algo como todos os dados iniciais em std::vectorvárias linhas. Se as colunas são invariáveis ​​para você, para o tipo de dados eu escolheria a biblioteca boost :: tuple .

Em seguida, você pode passar um identificador para todo o "banco de dados" para seus tipos de Nó. Seria muito fácil recuperar / acessar qualquer subconjunto de colunas e linhas dessa estrutura. Um tipo de nó atuaria como um tipo de objeto proxy ou wrapper para acessar os dados, agindo de certa forma como uma exibição para todo o banco de dados.

Além disso, o custo do tempo seria constante no tempo, pois os dados seriam acessados ​​diretamente. O espaço ocupado na memória seria baixo, como você mencionou, porque o principal custo é o banco de dados inicial e não há cópias dos dados em si. Somente o custo seria indexado a partir dos vetores de linhas-colunas.

Há, no entanto, uma ressalva. Se você falar de milhões de registros e centenas de colunas, lembre-se de que existe um limite de escalabilidade para a memória. Você pode ser forçado a recorrer a algum sistema de banco de dados real, apenas por causa das limitações da quantidade de memória. Eu aconselharia provavelmente SQLite. SQLite permite criar banco de dados volátil na memória. Assim, você pode segui-lo inicialmente e fazer a transição perfeita para o banco de dados normal do arquivo, se seus conjuntos de dados crescerem muito.

Uma coisa que você pode fazer no seu modelo para economizar espaço é gerenciar índices em seus nós como matrizes de bits. Então, do seu exemplo:

Nó 2:

colunas = [0,1,2] = 5 ou 101

linhas = [0,1,3] = 11 ou 1011

Nó 3:

colunas = [0,1,2] = 5 ou 101

linhas = [2,4] = 20 ou 10100

Isso levaria seu requisito de size_of (int) * (number_of_columns + number_of_rows) * nó para sizeof (int) * 2 * nó

Essa abordagem restringirá sua dimensão da matriz a um tamanho de colunas (int) e ao mesmo número de linhas. Para superar essa limitação (especialmente forte em linhas), você pode armazená-las em blocos. Nesse caso, você precisará de um novo número inteiro em cada nó que especifique o bloco, transformando seu tamanho total de índice em sizeof (int) * 3 * nó ainda mais baixo que size_of (int) * (número_de_colunas + número_de_rows) * nó