寻找C4.5算法的C++实现

Question

我一直在寻找C++实现的C4.5算法，但我还没有找到一个。我找到昆兰的C4.5第8版，但它是用C写的.有人见过C4.5算法的开源C++实现吗？

如果我找不到开源的J48源代码实现，我正在考虑移植C++ (或者只是编写C版本的包装器)，但我希望我不必这么做！如果您遇到了算法的C++实现，请告诉我。

更新

我一直在考虑围绕C5.0算法(c5.0)的C实现编写一个瘦C++包装器的选项。我下载并编译了C5.0算法的C实现，但它似乎很难移植到C++。C实现使用了大量的全局变量，仅仅在C函数周围编写一个瘦的C++包装器不会导致面向对象的设计，因为每个类实例都将修改相同的全局参数。换句话说:我将没有封装，这是我需要的非常基本的东西。

为了获得封装，我需要将C代码的完整端口移植到C++中，这与将Java (J48)移植到C++差不多。

更新2.0

以下是一些具体要求：

1. 每个分类器实例必须封装自己的数据(除了常量变量之外，没有全局变量)。
2. 支持分类器的并行训练和分类器的并行评估。

下面是一个很好的场景:假设我正在进行10次交叉验证，我想同时训练10个决策树和它们各自的训练集。如果我只是对每个切片运行C程序，我将不得不运行10个进程，这并不可怕。然而，如果我需要实时地对数千个数据样本进行分类，那么我将不得不为我想要分类的每个样本启动一个新的过程，这并不是非常有效。

Answer 1

我可能已经找到了一个C5.0的可能C++“实现”(见5.0)，但是我还没有能够深入到源代码中来确定它是否真的像广告中所显示的那样工作。

为了重申我最初的关切，该端口的作者声明了关于C5.0算法的以下内容：

See5Sam C5.0的另一个缺点是不可能同时拥有多个应用程序树。每次运行可执行文件时，都会从文件中读取应用程序，并将其存储在全局变量中。

一旦我有时间查看源代码，我就会更新我的答案。

更新

它看起来很不错，下面是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);
}

我想说的是，这是我迄今为止找到的最好的选择。

Answer 2

在“决策树”部分，C4.5的C++实现称为YaDT：

http://www.di.unipi.it/~ruggieri/software.html

这是最后一个版本的源代码：

http://www.di.unipi.it/~ruggieri/YaDT/YaDT1.2.5.zip

在描述该工具的文件中：

..。本文描述了一种新的基于熵的决策树归纳法的C++实现，该算法以C4.5的方式生成基于熵的决策树。该实现名为YaDT，是另一个决策树构建器的缩写。本文的主要贡献是给出了实现的设计原则，从而可以获得一个高效的系统。我们讨论了数据和元数据的内存表示和建模，算法优化及其对内存和时间性能的影响，以及剪枝启发式算法的效率和准确性之间的权衡。..。

该论文提供了这里。

Answer 3

如果我正在阅读这个correctly...it，它似乎不是作为一个C组织的，而是作为一个C程序来组织的。一个数据集被输入，然后运行一个算法并给出一些规则描述。

我认为你应该走的路取决于你是否：

1. 只需要一个C++接口来提供数据和从现有引擎中检索规则，或者.
2. 想要一个您可以修改的C++实现，以便将算法调整到自己的目的。

如果您想要的是(1)，那么您实际上可以将程序派生为一个进程，将其输入作为字符串，并将输出作为字符串。这可能是开发“包装器”的最简单和最有前途的方法，然后您只需开发C++类来表示输入并对规则结果建模(或将现有类与这些抽象匹配)。

但是，如果您想要的是(2)...then，我建议在C或Java中现有代码的基础上尝试任何您想要的黑客攻击--无论您最满意的是哪种。您将通过这种方式了解代码，如果您有任何改进，您可能可以将它们上游提供给作者。如果您建立一种长期的关系，那么您也许可以协作，并将C代码库慢慢地提交给C++，这是一次一个方面，因为它是为语言设计的。

我想我只是认为“在罗马时”的哲学通常比“一条龙港”更有效，尤其是在一开始。

响应更新：进程隔离处理全局变量问题。至于性能和数据集大小，您的核心/CPU和内存只有您拥有的那么多。在这个级别上谈论规模问题时，您使用的进程还是线程通常不是问题。您所遇到的开销是如果编组太昂贵。

证明编组是瓶颈，在多大程度上.您可以构建一个案例来解释为什么进程在线程上是一个问题。但是，可能会对现有代码进行小的调整，使编组更便宜，而不需要重写。