Pytanie w sprawie decision-tree, c++, machine-learning, algorithm – Poszukiwanie implementacji algorytmu C4.5 w C ++

5

Szukałem implementacji C ++Algorytm C4.5, ale jeszcze nie udało mi się znaleźć. Znalazłem QuinlanaC4.5 Release 8, ale jest napisane w C ... czy ktokolwiek widział jakiekolwiek implementacje C4.5 algorytmu open source C ++?

Myślę o przeniesieniuKod źródłowy J48 (lub po prostu piszę otokę wokół wersji C), jeśli nie mogę znaleźć implementacji C ++ na Open Source, ale mam nadzieję, że nie muszę tego robić! Daj mi znać, jeśli natknąłeś się na implementację algorytmu C ++.

Aktualizacja

Rozważałem możliwość napisania acienki wrapper C ++ wokół implementacji C algorytmu C5.0 (C5.0 to ulepszona wersja C4.5). Pobrałem i skompilowałem implementację algorytmu C5.0 w C, ale wygląda na to, że nie jest łatwo przenośny do C ++. Implementacja C wykorzystuje wiele zmiennych globalnych i po prostu napisanie cienkiego opakowania C ++ wokół funkcji C nie spowoduje powstania projektu zorientowanego obiektowo, ponieważ każda instancja klasy będzie modyfikować te same parametry globalne. Innymi słowy:Nie będę miał enkapsulacji i to jest dość podstawowa rzecz, której potrzebuję.

Aby uzyskać hermetyzację, będę musiał utworzyć pełny kod C w C ++, który jest mniej więcej taki sam jak przeniesienie wersji Java (J48) do C ++.

Aktualizacja 2.0

Oto kilka szczególnych wymagań:

Każda instancja klasyfikatora musi hermetyzować własne dane (tj. Brak zmiennych globalnych oprócz stałych).Obsługa jednoczesnego szkolenia klasyfikatorów i jednoczesnej oceny klasyfikatorów.

Oto dobry scenariusz: załóżmy, że wykonuję 10-krotną walidację krzyżową, chciałbym jednocześnie szkolić 10 drzew decyzyjnych z odpowiednim wycinkiem zestawu treningowego. Gdybym po prostu uruchomił program C dla każdego plasterka, musiałbym uruchomić 10 procesów, co nie jest straszne. Jeśli jednak muszę sklasyfikować tysiące próbek danych w czasie rzeczywistym, musiałbym rozpocząć nowy proces dla każdej próbki, którą chcę sklasyfikować, a to nie jest zbyt wydajne.

bardzo interesująca strona, nawet nie wspomina o czym jest oprogramowanie lurscher
Gdzie mogę znaleźć ...? pytania są zazwyczaj zamknięte. BNL
@Lirik: też tego nie otrzymałem, może pierwsza wersja twojego pytania była trudna do zdobycia? jest ponownie otwarty 4/5, więc powinniśmy się tam szybko dostać. Matthieu M.
Wolisz portować ją z Javy zamiast pisać opakowanie C ++ w wersji C? Dostępny jest również następca C4.5 o nazwie C5.0:rulequest.com/see5-info.html Eugen Constantin Dinca

Twoja odpowiedź

3   odpowiedź
2

YaDT jest dostępny tutaj, w sekcji „Drzewa decyzyjne”:
http://www.di.unipi.it/~ruggieri/software.html

To jest kod źródłowy ostatniej wersji:
http://www.di.unipi.it/~ruggieri/YaDT/YaDT1.2.5.zip

Z papieru, w którym opisano narzędzie:

[...] W tym artykule opisujemy nową implementację algorytmu indukcyjnego drzewa decyzyjnego od zera, która zapewnia oparte na entropii drzewa decyzyjne w stylu C4.5. Implementacja nazywa się YaDT, skrót odKolejny budowniczy drzewa decyzyjnego. Zamierzeniem tego artykułu jest przedstawienie zasad projektowania wdrożenia, które pozwoliły uzyskać wysoce wydajny system. Omawiamy nasze wybory dotyczące reprezentacji pamięci i modelowania danych i metadanych, optymalizacji algorytmicznej i ich wpływu na pamięć i wydajność czasu, a także kompromis między wydajnością i dokładnością heurystyk przycinania. [...]

Papier jest dostępnytutaj.

Hej @gRizzlyGR, dzięki za linki. Aby pomóc uniknąć rotacji linków, czy mógłbyś opracować nieco rozwiązanie, więc nawet jeśli linki przerywają tę odpowiedź, nadal będą przydatne? Dzięki yochannah
Cześć @ yochannah, dodałem fragment z papieru narzędzia. Czy teraz jest dobrze? Niestety nie mogę bezpośrednio powiązać papieru z powodu mojej niskiej reputacji. gRizzlyGR
2

Mogłem znaleźćmożliwa „implementacja” C ++ C5.0 (See5.0), ale nie byłem w stanie zagłębić się w kod źródłowy na tyle, by stwierdzić, czy naprawdę działa zgodnie z reklamą.

Aby powtórzyć moje pierwotne obawy, autor portu podaje następujące informacje na temat algorytmu C5.0:

Inną wadą See5Sam [C5.0] jest niemożność posiadania więcej niż jednego drzewa aplikacji w tym samym czasie. Aplikacja jest odczytywana z plików za każdym razem, gdy uruchamiany jest plik wykonywalny i jest tam i tam przechowywana w zmiennych globalnych.

Zaktualizuję moją odpowiedź, gdy tylko będę miał trochę czasu na sprawdzenie kodu źródłowego.

Aktualizacja

Wygląda całkiem nieźle, oto interfejs C ++:

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);
}

Powiedziałbym, że to najlepsza alternatywa, jaką do tej pory znalazłem.

1

Jeśli czytam to poprawnie ... wydaje się, że nie jest zorganizowany jako C-API, ale jako program w C. Zestaw danych jest podawany, następnie uruchamia algorytm i podaje z powrotem niektóre opisy reguł.

Myślę, że ścieżka, którą powinieneś wybrać, zależy od tego, czy:

po prostu chcę interfejsu C ++ do dostarczania danych i pobierania reguł z istniejącego silnika lub ...

chcesz implementacji C ++, którą możesz manipulować, aby dostosować algorytm do własnych celów

Jeśli chcesz (1), to możesz po prostu odrodzić program jako proces, podać go jako ciągi i odebrać wyjście jako łańcuchy. Prawdopodobnie byłby to najłatwiejszy i najbardziej przyszłościowy sposób tworzenia „opakowania”, a następnie musiałbyś opracować klasy C ++, aby reprezentować dane wejściowe i modelować wyniki reguł (lub dopasowywać istniejące klasy do tych abstrakcji).

Ale jeśli chcesz (2) ... to sugeruję wypróbowanie wszelkich hacków, które masz na myśli w stosunku do istniejącego kodu w C lub Java - w zależności od tego, który z nich jest najwygodniejszy. Poznasz kod w ten sposób, a jeśli masz jakieś ulepszenia, możesz je przekazać autorowi. Jeśli zbudujesz relację w dłuższej perspektywie, być może będziesz mógł współpracować i powoli wprowadzać bazę kodu C do C ++, jeden aspekt naraz, tak jak został zaprojektowany.

Domyślam się, że filozofia „Kiedy w Rzymie” zazwyczaj działa lepiej niż Port-In-One-Go, zwłaszcza na początku.

ODPOWIEDŹ NA AKTUALIZACJĘ: Izolacja procesów zajmuje się problemem globalnej zmiennej. Jeśli chodzi o wydajność i rozmiar zestawu danych, masz tylko tyle rdzeni / procesorów i pamięci, ile masz. To, czy używasz procesów czy wątków, zazwyczaj nie jest problemem, gdy mówisz o sprawach skali na tym poziomie. Napotkany koszt jest taki, jakprzetaczanie to jest za drogie.

Udowodnij, że zestawianie jest wąskim gardłem i do jakiego stopnia ... i możesz zbudować sprawę, dlaczego proces jest problemem w wątku. Jednak w istniejącym kodzie mogą pojawić się drobne poprawki, które sprawią, że zestawianie będzie tańsze, co nie wymaga przepisywania.

Tak, trudną częścią wielu procesów jest IPC, ponieważ musimy załadować klasyfikator z pliku, utrzymywać proces otwarty i podawać instancje danych z głównego procesu. Co więcej, pomysł ochrony aplikacji przed awarią, jeśli jeden z procesów klasyfikatora ulegnie awarii, jest zdecydowanie dobry! Pobawię się tym trochę i zobaczę, czy mogę uruchomić wiele instancji jednocześnie. Kiril
Mam przeczucie, że pozostało mi z opcją 2, mimo że nie dbam szczególnie o modyfikowanie algorytmu lub modyfikowanie go. Kiril
Wiesz, wiele obecnych przeglądarek, takich jak Chrome, tworzy proces na kartę. Sposób, w jaki system operacyjny obsługuje rzeczy, udostępnia strony kodowe w pamięci dla typowych procesów tego samego obrazu wykonywalnego ... możesz być zaskoczony tym, co może zrobić. Robićproste testy i sprawdź wydajnośćprzed założeniem, a nawet wtedy ... kiedy odkryjesz wąskie gardło, możesz zauważyć, że zmiany, których potrzebujesz, są o wiele łatwiejsze niż przepisanie! Być może prosta i ogólnie użyteczna funkcja upstream w kodzie C może pomóc w pokonaniu każdej znalezionej luki. HostileFork
Poprawnie, z tego, co mogę powiedzieć, jest to bardziej program C i niż API C. Problem polega na tym, że muszę sklasyfikować wiele wystąpień danych w czasie rzeczywistym, więc rozpoczęcie nowego procesu dla każdej instancji danych, którą muszę sklasyfikować, nie jest ani wydajne, ani szybkie. Na koniec, nie mogę się doczekać, aby połączyć instancje danych razem lub co najwyżej mogę wsadzić około 300 instancji danych na sekundę (ponownie, prawdopodobnie nadal niezbyt wydajne, aby uruchomić / zatrzymać 10 procesów na sekundę). Zauważ, że używam 10-krotnej walidacji krzyżowej, więc mam 10 klasyfikatorów do oceny przy dokonywaniu przewidywania. Kiril

Powiązane pytania