Was ist der beste Weg, um eine Tabelle in C ++ zu speichern

Ich programmiere einen Entscheidungsbaum in C ++ mit einer leicht modifizierten Version des C4.5-Algorithmus . Jeder Knoten repräsentiert ein Attribut oder eine Spalte Ihres Datensatzes und hat untergeordnete Werte pro möglichem Wert des Attributs.

Mein Problem ist das Speichern des Trainingsdatensatzes unter Berücksichtigung der Tatsache, dass ich für jeden Knoten eine Teilmenge verwenden muss, damit ich schnell nur eine Teilmenge von Zeilen und Spalten auswählen kann.

Das Hauptziel ist es, dies so speicher- und zeiteffizient wie möglich zu machen (in dieser Prioritätsreihenfolge).

Der beste Weg, an den ich gedacht habe, ist, ein Array von Arrays (oder std :: vector) oder ähnliches zu haben und für jeden Knoten eine Liste (Array, Vektor usw.) oder etwas mit dem column,line(wahrscheinlich ein Tupel) zu haben. Paare, die für diesen Knoten gültig sind.

Ich sollte es jetzt einen besseren Weg geben, irgendwelche Vorschläge?

UPDATE: Was ich brauche ist so etwas:

Am Anfang habe ich diese Daten:

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

Aber für den zweiten Knoten brauche ich nur diese Daten:

Paris    4    5.0
New York 7    1.3
Paris    9    6.8

Und für den dritten Knoten:

Tokio    2    9.1
Tokio    0    8.4

Aber mit einer Tabelle von Millionen von Datensätzen mit bis zu Hunderten von Spalten.

Was ich vorhabe, ist, alle Daten in einer Matrix zu speichern und dann für jeden Knoten die Informationen der aktuellen Spalten und Zeilen zu speichern. Etwas wie das:

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

Knoten 2:

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

Knoten 3:

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

Auf diese Weise muss ich im schlimmsten Fall nur verschwenden

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

Das ist viel weniger als eine unabhängige Datenmatrix für jeden Knoten.

Das letzte Mal, als ich versucht habe, C4.5 zu verstehen, bin ich gescheitert, aber ich habe eine Variante von ID3 implementiert - ursprünglich aus Neugier, aber sie wurde schließlich als Teil eines Overkill-Codegenerators mit mehreren Versendungen verwendet. Dies betrifft jedoch nie große Datenmengen und ist ein guter Job. Sie würden nicht gut daran tun, das meiste von dem nachzuahmen, was ich getan habe, aber vielleicht mit ein paar Ausnahmen, und natürlich habe ich ein bisschen aus den Fehlern gelernt.

Ich neige dazu, einen Entscheidungsbaum für ein Expertensystem zu erstellen, daher verwende ich die folgenden Begriffe - sorry, wenn das verwirrend ist ...

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

In meinem Fall habe ich die Schlussfolgerung in einer anderen Spalte gezogen - ähnlich einer Wahrheitstabelle für ein Logikgatter. Zeilennummern waren daher nur Zeilennummern. Dadurch konnte ich Probleme im XOR-Stil behandeln, die nicht einmal dargestellt werden können, wenn dieselbe Schlussfolgerung nicht in mehreren Zeilen angezeigt werden kann. Ich bin mir nicht sicher, ob dies für Sie relevant ist oder nicht. Auf jeden Fall ignoriere ich dies unten - es macht keinen großen Unterschied, es sei denn, Sie sehen sich die Details der Auswahl der nächsten Frage an. Für Data Mining haben Sie wahrscheinlich ohnehin keine bestimmte Information, die Sie als Zielschlussfolgerung behandeln könnten - die "Schlussfolgerung" ist genau das, was übrig bleibt, wenn Sie sich entscheiden, keine Fragen mehr zu stellen.

Also - für jeden bisher abgeleiteten Entscheidungsbaumknoten haben Sie eine Reihe offener Fragen (Spalten) und eine Reihe noch nicht eliminierter Schlussfolgerungen (Zeilen). Das ist, was ich tat. Der einzige Punkt, der hinzugefügt werden sollte, ist, dass ich Bitvektoren verwendet habe.

IIRC, C ++ std::vector<bool>und std::array<bool> können als Bitvektoren implementiert werden, aber Sie sind immer noch auf die STL-Algorithmen für gesetzte Operationen angewiesen, die jeweils ein Element ausführen. Ich habe meine eigene Bitvektorklasse verwendet, die über einen bestimmten Zeitraum schrittweise aufgebaut wurde und bitweise Operatoren für den Basiswert verwendet std::vector<CHUNK>(wobei CHUNKes sich um einen vorzeichenlosen int-Typ handelt, der normalerweise 32 Bit breit ist).

Möglicherweise gibt es in C ++ 11 oder in Boost eine bessere Bitvektoroption, und es muss einige gute Bibliotheken geben, von denen einige - es gibt viele Arten von Programmen, bei denen Sie am Ende mit vorzeichenlosen Ganzzahlen arbeiten. Ich weiß einfach nicht viel über sie, weil ich zu faul war, von meiner eigenen zu wechseln.

Bitvektoren sind dort jedoch am besten, wenn die Mengen meist dicht sind. In diesem Fall ist der Satz von Zeilen das offensichtliche Problem. Nur der Wurzelknoten des Entscheidungsbaums hat einen perfekt dichten Zeilensatz. Wenn Sie sich weiter von der Wurzel entfernen, werden die Zeilensätze immer sparsamer, wobei jede Frage beantwortet wird, was dazu führt, dass der Satz von Zeilen auf zwei oder mehr disjunkte Zeilensätze des nächsten Knotens verteilt wird.

Ein einfaches sortiertes Array von Zeilennummern könnte daher die beste Darstellung für diese Mengen sein. Es ist jedoch auch möglich, dass sich ein "spärlicher Bitvektor" lohnt. Eine mögliche Implementierung ist ein sortiertes Array von Paaren, wobei das erste jedes Paares die erste Zeilen-ID eines Blocks und das zweite ein Bitvektor fester Größe für diesen Block ist. Beispielsweise könnte die Zeilennummer 35 in Block 32 ( 35 & ~(32 - 1)) an Bitposition 3 ( 35 & (32 - 1)) gespeichert sein . Wenn Sie nur die Paare speichern, bei denen der Bitvektor nicht Null ist, ergibt sich etwas zwischen einem sortierten Array von IDs und einem einfachen Bitvektor - spärliche Arrays werden relativ gut verarbeitet, insbesondere wenn IDs dazu neigen, sich in Sätzen eng zusammenzuschließen.

Es kann sich auch lohnen, eine Klasse zu verwenden, die von einer Bitvektor- zu einer sortierten Array-Darstellung wechseln kann, wenn die Größe klein genug wird. Die zusätzliche Komplikation, die nur einigen Knoten in der Nähe der Wurzel zugute kommt, ist jedoch wahrscheinlich sinnlos.

Wie auch immer diese Sätze dargestellt werden, da sie auf eine einzelne konstante "Datenbank" verweisen, spart dies viel Datenkopie und Platzverschwendung, wenn der Algorithmus ausgeführt wird. Aber es lohnt sich immer noch, sich diese "Datenbank" anzusehen.

Ich habe eine assoziative Datenstruktur verwendet, die es mir ermöglicht, mit einem Tupel aus Frage-ID und Abschluss-ID nachzuschlagen, um eine Antwort-ID zu erhalten. Das heißt, ich hatte einen Overhead pro Element für den Schlüssel (Frage-ID und Abschluss-ID) und in diesem Fall auch einen Overhead für den Baum im B + -Stil. Der Grund - im Grunde Gewohnheit. Ich habe Container, die sehr flexibel sind, und ich benutze sie häufig, weil ich nicht vorhersehen kann, welche Funktionen ich später tatsächlich benötige. Dafür gibt es einen Preis, aber das ist nur die alte Sache der vorzeitigen Optimierung.

In Ihrem Fall verwenden Sie eine Matrix - ich gehe von einem zweidimensionalen Array aus, das durch Frage-ID und Antwort-ID indiziert ist.

Ich kann mir nur vorstellen, dass meine Version effizienter ist als Ihre, wenn die meisten Antworten nicht bekannt sind. In einer Matrix benötigen Sie dafür eine spezielle, nicht bekannte Antwort-ID, die denselben Platz wie eine bekannte Antwort-ID einnimmt. In einem assoziativen Container schließen Sie diese Zeilen aus.

Trotzdem wäre ein sortiertes Array effizienter als meine B + -Baum-basierte Lösung. Sie müssen keine effizienten Einfügungen zulassen, daher ist der einzige notwendige Overhead für die Schlüssel.

Wenn Sie zwei Schlüsselfelder verwenden (Frage und Schlussfolgerung, Zeile und Spalte), die möglicherweise ein Problem darstellen (ich erinnere mich nicht wirklich), können Sie möglicherweise nicht einfach eine Kopie der Tabelle in einer sortierten Reihenfolge aufbewahren. Wenn Sie jedoch einen einzelnen berechneten Schlüssel nach dem Vorbild von verwenden (row * num_columns) + column, implementieren Sie im Grunde genommen ohnehin ein zweidimensionales Array mit geringer Dichte.

Für mich bedeutet das Vorhandensein unbekannter / undefinierter Antworten auf eine bestimmte Frage, dass ich diese Frage noch nicht stellen darf - und selbst das war nur die Theorie, die ich bei der ersten Implementierung des Algorithmus verwendet habe. Ich habe das nie wirklich benutzt. Es gibt eine Verwendung, für die ich es verwenden könnte, aber ich bin nie dazu gekommen. Für den Datensatz bestand in diesem Mehrfachversand-Codegenerator eine Idee darin, basierend auf Feldern im Typ zu versenden. Da der Typ selbst polymorph ist, sind diese Felder möglicherweise nicht einmal vorhanden. Sie können sie daher nur anzeigen, wenn Sie bestätigt haben, dass sie vorhanden sein müssen.

Wenn Sie keine Anwendung für unbekannte / undefinierte Antworten haben, ist Ihre vorhandene Matrix wahrscheinlich bereits die beste Lösung.

Im Grunde ist es das - ich kann keine wirklich besseren Optionen anbieten, und was Sie tun, ist wahrscheinlich schon besser als das, was ich getan habe. Es gibt jedoch einige Kompromissmöglichkeiten, die Sie in Betracht ziehen könnten - vorausgesetzt, dies ist natürlich keine vorzeitige (und möglicherweise falsche) Optimierung.

Das Hauptkompromissproblem betrifft die Effizienz der Darstellung von spärlichen und dichten Wertesätzen, sodass es nicht wirklich spezifisch für C4.5 oder die Erstellung von Entscheidungsbäumen ist. Und ein "ausgefeilterer" Ansatz ist oft weniger effizient als ein einfacher, der mit Sorgfalt gewählt wurde.

Ich finde deine Idee gut. Ich bin nicht sicher, wie allgemein Ihre Bibliothek für den Zugriff auf die Daten ist, die Sie sein möchten. Sie könnten aber so etwas wie Ihre gesamten Anfangsdaten in std::vectormehreren Zeilen speichern . Wenn die Spalten für Sie unveränderlich sind, würde ich für den Datentyp die Bibliothek boost :: tuple wählen .

Dann könnten Sie ein Handle an die gesamte "Datenbank" an Ihre Knotentypen übergeben. Es wäre sehr einfach, eine Teilmenge von Spalten und Zeilen aus einer solchen Struktur abzurufen / darauf zuzugreifen. Ein Knotentyp fungiert als eine Art Proxy-Objekt oder Wrapper für den Zugriff auf die Daten und fungiert in gewisser Weise als Ansicht für die gesamte Datenbank.

Darüber hinaus wären die Zeitkosten zeitlich konstant, da direkt auf die Daten zugegriffen würde. Der Speicherbedarf wäre, wie Sie bereits erwähnt haben, gering, da die Hauptkosten die anfängliche Datenbank sind und keine Kopien der selbst erstellten Daten vorhanden sind. Nur Kosten wären Indizes aus den Zeilen-Spalten-Vektoren.

Es gibt jedoch eine Einschränkung. Wenn Sie von Millionen von Datensätzen und Hunderten von Spalten sprechen, müssen Sie berücksichtigen, dass es eine Skalierbarkeitsbeschränkung für den Speicher gibt. Sie könnten gezwungen sein, auf ein echtes Datenbanksystem zurückzugreifen, nur weil der Speicherplatz begrenzt ist. Ich würde wahrscheinlich SQLite raten. Mit SQLite können Sie eine flüchtige In-Memory-Datenbank erstellen. Sie können also zunächst damit beginnen und nahtlos in die normale Datei-DB übergehen, wenn Ihre Datenmengen zu groß werden.

Sie können auf Ihrem Modell Platz sparen, indem Sie Indizes auf Ihren Knoten als Bit-Arrays verwalten. Also aus Ihrem Beispiel:

Knoten 2:

Spalten = [0,1,2] = 5 oder 101

Zeilen = [0,1,3] = 11 oder 1011

Knoten 3:

Spalten = [0,1,2] = 5 oder 101

Zeilen = [2,4] = 20 oder 10100

Dies würde Ihre Anforderung von size_of (int) * (number_of_columns + number_of_rows) * node zu sizeof (int) * 2 * node führen

Dieser Ansatz beschränkt Ihre Matrixdimension auf eine Größe von (int) Spalten und die gleiche Anzahl von Zeilen. Um diese Einschränkung zu überwinden (besonders stark in Zeilen), können Sie sie in Blöcken speichern. In diesem Fall benötigen Sie auf jedem Knoten eine neue Ganzzahl, die den Block angibt. Dadurch wird Ihre Gesamtindexgröße auf sizeof (int) * 3 * -Knoten festgelegt, die immer noch kleiner als size_of (int) * (number_of_columns + number_of_rows) * node ist