5

我一直在寻找C4.5 算法的 C++ 实现,但我还没有找到。我找到了 Quinlan 的C4.5 Release 8,但它是用 C 编写的……有人看过 C4.5 算法的任何开源 C++ 实现吗?

如果我找不到开源 C++ 实现,我正在考虑移植J48 源代码(或简单地为 C 版本编写一个包装器),但我希望我不必这样做!如果您遇到过该算法的 C++ 实现,请告诉我。

更新

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

为了获得封装,我需要将 C 代码完整移植到 C++,这与将 Java 版本 (J48) 移植到 C++ 大致相同。

更新 2.0

以下是一些具体要求:

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

这是一个很好的场景:假设我正在进行 10 倍交叉验证,我想同时训练 10 个决策树及其各自的训练集切片。如果我只是为每个切片运行 C 程序,我将不得不运行 10 个进程,这并不可怕。但是,如果我需要对数千个数据样本进行实时分类,那么我将不得不为每个要分类的样本启动一个新流程,这不是很有效。

4

3 回答 3

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,是Yet another Decision Tree builder的首字母缩写词。本文的预期贡献是介绍允许获得高效系统的实现的设计原则。我们讨论了我们对内存表示和数据和元数据建模的选择、算法优化及其对内存和时间性能的影响,以及剪枝启发式的效率和准确性之间的权衡。[...]

该论文可在此处获得。

于 2014-12-10T15:58:34.273 回答
2

我可能已经找到了C5.0 (See5.0) 的一个可能的 C++“实现”,但我无法深入研究源代码以确定它是否真的像宣传的那样工作。

为了重申我最初的担忧,端口的作者对 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);
}

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

于 2012-06-04T21:29:37.373 回答
1

如果我没看错……它似乎不是作为 C API 组织的,而是作为 C 程序组织的。一个数据集被输入,然后它运行一个算法并给你一些规则描述。

我认为您应该采取的路径取决于您是否:

  1. 只需要一个用于从现有引擎提供数据和检索规则的 C++ 接口,或者......

  2. 想要一个可以修改的 C++ 实现,以便根据自己的目的调整算法

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

但是,如果您想要的是(2)......那么我建议您在 C 或 Java 中的现有代码之上尝试您想到的任何技巧 - 无论您最喜欢哪种方式。您将通过这种方式了解代码,如果您有任何改进,您可以将它们上游提供给作者。如果你建立了长期的关系,那么也许你可以合作并将 C 代码库慢慢地推向 C++,一次一个方面,因为该语言的设计目的。

我想我只是认为“在罗马时”的理念通常比单程港口更有效,尤其是在一开始。


对更新的响应:进程隔离会处理您的全局变量问题。至于性能和数据集大小,您只有尽可能多的内核/CPU 和内存。当您谈论该级别的规模问题时,您使用的是进程还是线程通常不是问题。您遇到的开销是编组过于昂贵。

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

于 2012-05-29T19:10:09.220 回答