Frage an c++, machine-learning, decision-tree, algorithm – Auf der Suche nach einer C ++ - Implementierung des C4.5-Algorithmus

5

Ich habe nach einer C ++ - Implementierung der gesuchtC4.5-Algorithmus, aber ich konnte noch keinen finden. Ich habe Quinlan gefundenC4.5 Release 8, aber es ist in C geschrieben ... hat jemand eine Open-Source-C ++ - Implementierung des C4.5-Algorithmus gesehen?

Ich denke darüber nach, das zu portierenJ48-Quellcode (oder einfach einen Wrapper um die C-Version schreiben), wenn ich dort draußen keine Open-Source-C ++ -Implementierung finden kann, aber ich hoffe, dass ich das nicht tun muss! Bitte lassen Sie mich wissen, wenn Sie auf eine C ++ - Implementierung des Algorithmus gestoßen sind.

Aktualisieren

Ich habe überlegt, ob ich einedünner C ++ - Wrapper rund um die C-Implementierung des C5.0-Algorithmus (C5.0 ist die verbesserte Version von C4.5). Ich habe die C-Implementierung des C5.0-Algorithmus heruntergeladen und kompiliert, aber es sieht nicht so aus, als wäre sie leicht auf C ++ übertragbar. Die C-Implementierung verwendet viele globale Variablen und das einfache Schreiben eines dünnen C ++ - Wrappers um die C-Funktionen führt nicht zu einem objektorientierten Entwurf, da jede Klasseninstanz dieselben globalen Parameter ändert. Mit anderen Worten:Ich werde keine Kapselung haben und das ist eine ziemlich grundlegende Sache, die ich brauche.

Um die Kapselung zu erhalten, muss ein vollständiger Port des C-Codes in C ++ erstellt werden. Dies entspricht in etwa der Portierung der Java-Version (J48) in C ++.

Update 2.0

Hier sind einige spezifische Anforderungen:

Jede Klassifikatorinstanz muss ihre eigenen Daten einkapseln (d. H. Keine globalen Variablen außer konstanten).Unterstützen Sie das gleichzeitige Training von Klassifikatoren und die gleichzeitige Auswertung der Klassifikatoren.

Hier ist ein gutes Szenario: Angenommen, ich mache eine 10-fache Kreuzvalidierung und möchte gleichzeitig 10 Entscheidungsbäume mit ihrem jeweiligen Teil des Trainingssatzes trainieren. Wenn ich nur das C-Programm für jedes Segment ausführen würde, müsste ich 10 Prozesse ausführen, was nicht schrecklich ist. Wenn ich jedoch Tausende von Datenproben in Echtzeit klassifizieren muss, muss ich für jede Probe, die ich klassifizieren möchte, einen neuen Prozess starten, und das ist nicht sehr effizient.

@ SaeedAmiri Ich habe immer noch Probleme damit, es unter Windows zu kompilieren. Sobald ich damit fertig bin, muss ich einen C ++ - Wrapper erstellen. Es ist wahrscheinlich nicht so schwer, aber es wäre viel einfacher, wenn es bereits eine C ++ - Version gibt. Kiril
Nehmen Sie den Hafen als Übung, es wird Ihre Fähigkeiten verbessern. Gold
Sehr interessante Seite, auf der nicht einmal erwähnt wird, worum es in der Software geht lurscher
@Lirik: habs auch nicht verstanden, vielleicht war die erste version deiner frage schwer zu bekommen? es ist am 4/5 wieder geöffnet, also sollten wir hoffentlich bald dort ankommen. Matthieu M.

Deine Antwort

3   die antwort
2

Ich habe vielleicht einen gefundenmögliche C ++ "Implementierung" von C5.0 (siehe5.0), aber ich war nicht in der Lage, den Quellcode zu untersuchen, um festzustellen, ob er wirklich wie angekündigt funktioniert.

Um meine ursprünglichen Bedenken zu wiederholen, gibt der Autor des Ports Folgendes zum C5.0-Algorithmus an:

Ein weiterer Nachteil von See5Sam [C5.0] ist die Unmöglichkeit, mehr als einen Anwendungsbaum gleichzeitig zu haben. Eine Anwendung wird bei jeder Ausführung der ausführbaren Datei aus Dateien gelesen und hier und da in globalen Variablen gespeichert.

Ich werde meine Antwort aktualisieren, sobald ich etwas Zeit habe, mich mit dem Quellcode zu befassen.

Aktualisieren

Es sieht ziemlich gut aus, hier ist die C ++ Schnittstelle:

class CMee5
{
  public:

    /**
      Create a See 5 engine from tree/rules files.
      \param pcFileStem The stem of the See 5 file system. The engine
             initialisation will look for the following files:
              - pcFileStem.names Vanilla See 5 names file (mandatory)
              - pcFileStem.tree or pcFileStem.rules Vanilla See 5 tree or rules
                file (mandatory)
              - pcFileStem.costs Vanilla See 5 costs file (mandatory)
    */
    inline CMee5(const char* pcFileStem, bool bUseRules);

    /**
      Release allocated memory for this engine.
    */
    inline ~CMee5();

    /**
      General classification routine accepting a data record.
    */
    inline unsigned int classifyDataRec(DataRec Case, float* pOutConfidence);

    /**
      Show rules that were used to classify the last case.
      Classify() will have set RulesUsed[] to
      number of active rules for trial 0,
      first active rule, second active rule, ..., last active rule,
      number of active rules for trial 1,
      first active rule, second active rule, ..., last active rule,
      and so on.
    */
    inline void showRules(int Spaces);

    /**
      Open file with given extension for read/write with the actual file stem.
    */
    inline FILE* GetFile(String Extension, String RW);

    /**
      Read a raw case from file Df.

      For each attribute, read the attribute value from the file.
      If it is a discrete valued attribute, find the associated no.
      of this attribute value (if the value is unknown this is 0).

      Returns the array of attribute values.
    */
    inline DataRec GetDataRec(FILE *Df, Boolean Train);
    inline DataRec GetDataRecFromVec(float* pfVals, Boolean Train);
    inline float TranslateStringField(int Att, const char* Name);

    inline void Error(int ErrNo, String S1, String S2);

    inline int getMaxClass() const;
    inline int getClassAtt() const;
    inline int getLabelAtt() const;
    inline int getCWtAtt() const;
    inline unsigned int getMaxAtt() const;
    inline const char* getClassName(int nClassNo) const;
    inline char* getIgnoredVals();

    inline void FreeLastCase(void* DVec);
}

Ich würde sagen, dass dies die beste Alternative ist, die ich bisher gefunden habe.

2

Eine C ++ - Implementierung für C4.5 wird aufgerufenYaDT finden Sie hier im Bereich "Entscheidungsbäume":
http://www.di.unipi.it/~ruggieri/software.html

Dies ist der Quellcode für die letzte Version:
http://www.di.unipi.it/~ruggieri/YaDT/YaDT1.2.5.zip

Aus dem Papier, in dem das Werkzeug beschrieben ist:

[...] In diesem Artikel beschreiben wir eine neue C ++ - Implementierung eines Entscheidungsbauminduktionsalgorithmus, der entropiebasierte Entscheidungsbäume im Stil von C4.5 liefert. Die Implementierung heißt YaDT, eine Abkürzung fürEin weiterer Builder für Entscheidungsbaum. Der beabsichtigte Beitrag dieses Papiers besteht darin, die Entwurfsprinzipien der Implementierung vorzustellen, die es ermöglichten, ein hocheffizientes System zu erhalten. Wir diskutieren unsere Entscheidungen zur Speicherdarstellung und -modellierung von Daten und Metadaten, zu den algorithmischen Optimierungen und deren Auswirkungen auf die Speicher- und Zeitleistung sowie zum Kompromiss zwischen Effizienz und Genauigkeit der Bereinigungsheuristik. [...]

Das Papier ist verfügbarHier.

Hallo @yochannah, ich habe einen Auszug aus dem Papier des Tools hinzugefügt. Ist es jetzt gut? Leider kann ich das Papier aufgrund meines schlechten Rufs nicht direkt verlinken. gRizzlyGR
Hey @gRizzlyGR, danke für die Links. Könntest du vielleicht ein wenig herausfinden, was die Lösung ist, damit die Links nicht verrotten? Auch wenn die Links kaputt gehen, ist diese Antwort dennoch nützlich. Vielen Dank yochannah
1

Wenn ich das richtig lese ... scheint es nicht als C-API organisiert zu sein, sondern als C-Programm. Ein Datensatz wird eingespeist, dann wird ein Algorithmus ausgeführt und Sie erhalten einige Regelbeschreibungen.

Ich denke, der Weg, den Sie einschlagen sollten, hängt davon ab, ob Sie:

Sie möchten lediglich eine C ++ - Schnittstelle für die Bereitstellung von Daten und das Abrufen von Regeln von der vorhandenen Engine oder ...

Sie möchten eine C ++ - Implementierung, an der Sie basteln können, um den Algorithmus an Ihre eigenen Bedürfnisse anzupassen

Wenn Sie (1) wollen, können Sie das Programm wirklich einfach als Prozess erzeugen, die Eingabe als Zeichenfolgen einspeisen und die Ausgabe als Zeichenfolgen verwenden. Das wäre wahrscheinlich die einfachste und zukunftssicherste Methode, einen "Wrapper" zu entwickeln. Dann müssten Sie nur noch C ++ - Klassen entwickeln, um die Eingaben darzustellen und die Regelergebnisse zu modellieren (oder vorhandene Klassen mit diesen Abstraktionen abzugleichen).

Aber wenn Sie (2) wollen, dann würde ich vorschlagen, dass Sie versuchen, welche Hacks Sie auch immer im Sinn haben, zusätzlich zu dem vorhandenen Code in C oder Java - je nachdem, was Sie am bequemsten finden. Auf diese Weise lernen Sie den Code kennen, und wenn Sie Verbesserungen vorgenommen haben, können Sie diese möglicherweise dem Autor übermitteln. Wenn Sie längerfristig eine Beziehung aufbauen, können Sie möglicherweise zusammenarbeiten und die C-Codebasis langsam nach C ++ bringen, je nach Aspekt, für den die Sprache entwickelt wurde.

Ich denke mal, die "When in Rome" -Philosophie funktioniert normalerweise besser als Port-In-One-Go, besonders zu Beginn.

ANTWORT AUF AKTUALISIERUNG: Die Prozessisolierung kümmert sich um Ihr Problem mit globalen Variablen. In Bezug auf Leistung und Datensatzgröße verfügen Sie nur über so viele Kerne / CPUs und Arbeitsspeicher wie Sie haben. Ob Sie Prozesse oder Threads verwenden, ist normalerweise nicht das Problem, wenn Sie auf dieser Ebene über Skalierungsfragen sprechen. Der Aufwand, dem Sie begegnen, ist, wennRangieren ist zu teuer.

Beweisen Sie, dass das Marshalling der Engpass ist und inwieweit ... und Sie können ein Argument dafür erstellen, warum ein Prozess ein Problem in Bezug auf einen Thread darstellt. Es kann jedoch kleine Änderungen am vorhandenen Code geben, um das Marshalling billiger zu machen, für die kein Umschreiben erforderlich ist.

Ich habe das Gefühl, dass ich bei Option 2 geblieben bin, obwohl es mir nicht besonders wichtig ist, mit dem Algorithmus zu basteln oder ihn zu modifizieren. Kiril
Weißt du, viele aktuelle Browser wie Chrome erzeugen einen Prozess pro Tab. So wie das Betriebssystem die Dinge handhabt, teilt es die Codepages im Speicher für gängige Prozesse desselben ausführbaren Abbilds ... Sie könnten überrascht sein, was es bewirken kann. Tuneinfache tests und überprüfen Sie die Leistungvor der Annahme, und selbst dann ... wenn Sie den Engpass herausfinden, werden Sie vielleicht feststellen, dass die Optimierung, die Sie benötigen, viel einfacher ist als ein Umschreiben! Vielleicht kann ein einfaches und allgemein nützliches Upstream-Feature der C-Codebasis helfen, eine Lücke zu schließen, die Sie finden. HostileFork
Yah, der schwierige Teil mit mehreren Prozessen ist IPC, weil wir den Klassifikator aus der Datei laden müssen, den Prozess offen halten und ihm weiterhin Dateninstanzen aus dem Hauptprozess zuführen müssen. Darüber hinaus ist die Idee, Ihre Anwendung vor Abstürzen zu schützen, wenn einer der Klassifikatorprozesse abstürzt, auf jeden Fall gut! Ich werde ein bisschen damit herumspielen und sehen, ob ich mehrere Instanzen gleichzeitig ausführen kann. Kiril
Richtig, soweit ich das beurteilen kann, handelt es sich eher um ein C-Programm als um eine C-API. Das Problem ist, dass ich mehrere Instanzen von Daten in Echtzeit klassifizieren muss, sodass es weder sehr effizient noch schnell ist, für jede zu klassifizierende Dateninstanz einen neuen Prozess zu starten. Schließlich kann ich es kaum erwarten, die Dateninstanzen zusammen zu stapeln, oder bestenfalls kann ich ungefähr 300 Dateninstanzen pro Sekunde stapeln (wieder, wahrscheinlich immer noch nicht sehr effizient, um 10 Prozesse pro Sekunde zu starten / zu stoppen). Beachten Sie, dass ich eine 10-fache Kreuzvalidierung verwende, sodass ich 10 Klassifikatoren für die Vorhersage auswerten muss. Kiril

Verwandte Fragen