Pregunta sobre algorithm, c++, machine-learning, decision-tree – Buscando una implementación en C ++ del algoritmo C4.5

5

He estado buscando una implementación en C ++ de laAlgoritmo C4.5, pero no he podido encontrar uno todavía. Encontré la de quinlanC4.5 Release 8, pero está escrito en C ... ¿Alguien ha visto alguna implementación de C ++ de código abierto del algoritmo C4.5?

Estoy pensando en portar elCódigo fuente J48 (o simplemente escribiendo un envoltorio alrededor de la versión C) si no puedo encontrar una implementación de código abierto de C ++, ¡pero espero que no tenga que hacerlo! Por favor, avíseme si ha encontrado una implementación en C ++ del algoritmo.

Actualizar

He estado considerando la opción de escribir unenvoltura delgada de C ++ alrededor de la implementación C del algoritmo C5.0 (C5.0 es la versión mejorada de C4.5). Descargué y compilé la implementación en C del algoritmo C5.0, pero no parece que sea fácil de transportar a C ++. La implementación de C utiliza una gran cantidad de variables globales y simplemente escribir un contenedor C ++ delgado alrededor de las funciones C no dará como resultado un diseño orientado a objetos porque cada instancia de clase modificará los mismos parámetros globales. En otras palabras:No tendré encapsulación y eso es algo bastante básico que necesito.

Para obtener la encapsulación necesitaré hacer un puerto completo del código C en C ++, que es casi lo mismo que trasladar la versión de Java (J48) a C ++.

Actualización 2.0

Aquí hay algunos requisitos específicos:

Cada instancia de clasificador debe encapsular sus propios datos (es decir, no hay variables globales aparte de las constantes).Apoyar la capacitación concurrente de clasificadores y la evaluación concurrente de los clasificadores.

Aquí hay un buen escenario: supongamos que estoy haciendo una validación cruzada de 10 veces, me gustaría entrenar simultáneamente 10 árboles de decisión con su respectivo segmento del conjunto de entrenamiento. Si solo ejecuto el programa C para cada sector, tendría que ejecutar 10 procesos, lo cual no es horrible. Sin embargo, si necesito clasificar miles de muestras de datos en tiempo real, entonces tendría que comenzar un nuevo proceso para cada muestra que quiero clasificar y eso no es muy eficiente.

Página muy interesante, ni siquiera menciona de qué trata el software. lurscher
La mejora de mis habilidades en @Gold siempre es genial, pero siento que voy a pasar una cantidad considerable de tiempo portando el código C a C ++. Me gustaría evitarlo, porque ese es el tiempo que podría dedicar a entrenar y probar los algoritmos. Kiril
Dónde puedo encontrar ...? Las preguntas suelen estar cerradas. BNL
@EugenConstantinDinca yah, estaba buscando en el código C e inicialmente pensé que era demasiado complicado para trabajar, pero crear un contenedor en C ++ será mucho más rápido que portar Java. Parece una mejor opción si una implementación de C ++ no está disponible. Kiril

Tu respuesta

3   la respuesta
2

Puedo haber encontrado unposible "implementación" de C ++ de C5.0 (ver 5.0), pero no he podido profundizar en el código fuente lo suficiente para determinar si realmente funciona como se anuncia.

Para reiterar mis preocupaciones originales, el autor del puerto dice lo siguiente sobre el algoritmo C5.0:

Otro inconveniente de See5Sam [C5.0] es la imposibilidad de tener más de un árbol de aplicaciones al mismo tiempo. Una aplicación se lee de los archivos cada vez que se ejecuta el ejecutable y se almacena en variables globales aquí y allá.

Actualizaré mi respuesta tan pronto como tenga tiempo para ver el código fuente.

Actualizar

Se ve bastante bien, aquí está la interfaz de 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);
}

Yo diría que esta es la mejor alternativa que he encontrado hasta ahora.

2

Una implementación de C ++ para C4.5 llamadaYaDT Está disponible aquí, en la sección "Árboles de decisión":
http://www.di.unipi.it/~ruggieri/software.html

Este es el código fuente de la última versión:
http://www.di.unipi.it/~ruggieri/YaDT/YaDT1.2.5.zip

Desde el papel donde se describe la herramienta:

[...] En este documento, describimos una nueva implementación desde cero de C ++ de un algoritmo de inducción de árbol de decisión, que produce árboles de decisión basados ​​en la entropía en el estilo de C4.5. La implementación se llama YaDT, un acrónimo deOtro constructor de Árbol de Decisión. La contribución prevista de este documento es presentar los principios de diseño de la implementación que permitieron obtener un sistema altamente eficiente. Discutimos nuestras opciones sobre la representación de la memoria y el modelado de datos y metadatos, sobre las optimizaciones algorítmicas y su efecto en la memoria y el rendimiento del tiempo, y sobre el equilibrio entre la eficiencia y la precisión de las heurísticas de poda. [...]

El papel esta disponibleaquí.

Hola @gRizzlyGR, gracias por los enlaces. Para ayudar a evitar la rotura de enlaces, ¿podría elaborar un poco sobre cuál es la solución, por lo que incluso si los enlaces rompen esta respuesta todavía será útil? Gracias yochannah
Hola, @yochannah, he añadido un extracto del documento de la herramienta. ¿Está bien ahora? Desafortunadamente no puedo vincular directamente el documento debido a mi baja reputación. gRizzlyGR
1

Si estoy leyendo esto correctamente ... parece no estar organizado como una API de C, sino como un programa de C. Se alimenta un conjunto de datos, luego ejecuta un algoritmo y le devuelve algunas descripciones de las reglas.

Creo que el camino que debes seguir depende de si:

simplemente desea una interfaz C ++ para suministrar datos y recuperar reglas del motor existente, o ...

desea una implementación de C ++ con la que pueda jugar para ajustar el algoritmo a sus propios fines

Si lo que desea es (1), entonces realmente podría generar el programa como un proceso, alimentarlo como cadenas y tomar la salida como cadenas. Probablemente, esa sería la forma más fácil y más segura de desarrollar un "contenedor", y luego solo tendría que desarrollar clases de C ++ para representar las entradas y modelar los resultados de la regla (o hacer coincidir las clases existentes con estas abstracciones).

Pero si lo que quieres es (2) ... entonces te sugiero que pruebes los hacks que tengas en mente además del código existente en C o Java, cualquiera sea el que te resulte más cómodo. Llegará a conocer el código de esa manera y, si tiene alguna mejora, podrá enviarlo al autor en sentido ascendente. Si construyes una relación a largo plazo, entonces podrías colaborar y hacer que el código base de C avance lentamente hacia C ++, un aspecto a la vez, como fue diseñado para el lenguaje.

Supongo que creo que la filosofía "When in Rome" por lo general funciona mejor que Port-In-One-Go, especialmente al principio.

RESPUESTA A LA ACTUALIZACIÓN: El aislamiento del proceso se encarga de su problema de variable global. En cuanto al rendimiento y el tamaño del conjunto de datos, solo tiene tantos núcleos / CPU y memoria como tiene. Si está utilizando procesos o subprocesos, por lo general no es el problema cuando se habla de asuntos de escala en ese nivel. La sobrecarga que encuentras es si elmarshalling es demasiado caro.

Demuestre que la clasificación es el cuello de botella y hasta qué punto ... y puede construir un caso por el cual un proceso es un problema en un hilo. Pero, puede haber pequeños ajustes en el código existente para hacer que el cálculo sea más barato, lo que no requiere una reescritura.

Correcto, por lo que puedo decir, se trata más de un programa en C y de una API en C. El problema es que tengo que clasificar múltiples instancias de datos en tiempo real, por lo que no es muy eficiente ni rápido comenzar un nuevo proceso para cada instancia de datos que debo clasificar. Por último, no puedo esperar para agrupar las instancias de datos o, en el mejor de los casos, puedo agrupar alrededor de 300 instancias de datos por segundo (de nuevo, probablemente no sea muy eficiente iniciar / detener 10 procesos cada segundo). Tenga en cuenta que estoy usando una validación cruzada de 10 veces, así que tengo 10 clasificadores para evaluar al hacer una predicción. Kiril
Tengo la sensación de que me queda la opción 2, a pesar del hecho de que no me interesa especialmente modificar el algoritmo o modificarlo. Kiril
Ya sabes, muchos navegadores actuales como Chrome generan un proceso por pestaña. La forma en que el sistema operativo maneja las cosas, comparte las páginas de códigos en la memoria para los procesos comunes de la misma imagen ejecutable ... es posible que se sorprenda de lo que puede lograr. Hacerpruebas simples y comprobar el rendimientoantes de asumir, e incluso entonces ... cuando descubras el cuello de botella, puedes encontrar que la modificación que necesitas es mucho más fácil que reescribir. Tal vez una característica ascendente simple y generalmente útil de la base de código de C puede ayudar a cerrar cualquier brecha que encuentre. HostileFork
Sí, la parte difícil con múltiples procesos es IPC, porque necesitamos cargar el clasificador desde un archivo, mantener el proceso abierto y seguir alimentando las instancias de datos desde el proceso principal. Además, ¡la idea de proteger su aplicación para que no se bloquee si uno de los procesos clasificadores falla definitivamente es buena! Voy a jugar un poco con él y ver si puedo hacer que varias instancias se ejecuten simultáneamente. Kiril

Preguntas relacionadas