Вопрос по c++, algorithm – Ищите реализацию C ++ алгоритма C4.5

5

Я искал реализацию C ++Алгоритм C4.5, но я пока не смог найти. Я нашел КуинланаC4.5 Выпуск 8, но он написан на C ... Кто-нибудь видел какие-либо реализации C ++ с открытым исходным кодом алгоритма C4.5?

Я думаю о переносеJ48 исходный код (или просто написать обертку вокруг версии C), если я не могу найти реализацию C ++ с открытым исходным кодом, но я надеюсь, что мне это не нужно! Пожалуйста, дайте мне знать, если вы сталкивались с реализацией алгоритма на C ++.

Update

Я рассматривал возможность написанияthin C++ wrapper вокруг реализации C алгоритма C5.0 (C5.0 - улучшенная версия C4.5). Я скачал и скомпилировал реализацию C алгоритма C5.0, но он не выглядит так, как будто его легко переносить на C ++. Реализация C использует множество глобальных переменных, и простое написание тонкой оболочки C ++ вокруг функций C не приведет к объектно-ориентированному проектированию, поскольку каждый экземпляр класса будет модифицировать одни и те же глобальные параметры. Другими словами:I will have no encapsulation and that's a pretty basic thing that I need.

Чтобы получить инкапсуляцию, мне нужно будет сделать полноценный порт кода C на C ++, что примерно так же, как перенос версии Java (J48) на C ++.

Update 2.0

Вот некоторые конкретные требования:

Each classifier instance must encapsulate its own data (i.e. no global variables aside from constant ones). Support the concurrent training of classifiers and the concurrent evaluation of the classifiers.

Вот хороший сценарий: предположим, что я делаю 10-кратную перекрестную проверку, я хотел бы одновременно обучить 10 деревьев решений с их соответствующим срезом обучающего набора. Если бы я просто запускал C-программу для каждого среза, мне пришлось бы запустить 10 процессов, что не так уж и ужасно. Однако, если мне нужно классифицировать тысячи выборок данных в режиме реального времени, то мне придется начинать новый процесс для каждой выборки, которую я хочу классифицировать, и это не очень эффективно.

@NicolBolas Я думаю, что комментарий о том, что SO не является фермой ссылок, предназначен для решения проблемы создания ссылок на ваш собственный сайт с целью повышения рейтинга вашей страницы: в этом вопросе я не разместил ссылку на какой-либо из моих личных материалов так что я не знаю, как это применимо. Я также посмотрел на Google, но я не нашел каких-либо реализаций алгоритма на C ++. Kiril
Голосование возобновить - ИМХО это законный вопрос. Кроме того, не ответ - но может быть полезным для других -Weka имеет реализацию с открытым исходным кодом C4.5, но она написана на Java. amit
Алгоритм генерации деревьев решений.Wiki для заинтересованных G. Martinek
Вы предпочли бы перенести его из Java вместо написания оболочки C ++ поверх версии C? Также доступен преемник C4.5 под названием C5.0:rulequest.com/see5-info.html Eugen Constantin Dinca

Ваш Ответ

3   ответа
2

YaDT доступно здесь, в разделе «Деревья решений». раздел:
http://www.di.unipi.it/~ruggieri/software.html

Это исходный код для последней версии:
http://www.di.unipi.it/~ruggieri/YaDT/YaDT1.2.5.zip

Из статьи, где описан инструмент:

[...] In this paper, we describe a new from-scratch C++ implementation of a decision tree induction algorithm, which yields entropy-based decision trees in the style of C4.5. The implementation is called YaDT, an acronym for Yet another Decision Tree builder. The intended contribution of this paper is to present the design principles of the implementation that allowed for obtaining a highly efficient system. We discuss our choices on memory representation and modelling of data and metadata,on the algorithmic optimizations and their effect on memory and time performances, and on the trade-off between efficiency and accuracy of pruning heuristics. [...]

Бумага доступнаВот.

Привет @gRizzlyGR, спасибо за ссылки. Чтобы избежать гниения ссылок, не могли бы вы немного рассказать о том, каково решение, поэтому даже если ссылки не работают, этот ответ все еще будет полезен? Спасибо
Здравствуйте, @yochannah. Я добавил отрывок из статьи об инструменте. Это нормально сейчас? К сожалению, я не могу напрямую связать газету из-за моей низкой репутации.
2

возможная C ++ "реализация" из C5.0 (см. 5.0), но я не смог покопаться в исходном коде достаточно, чтобы определить, действительно ли он работает так, как рекламируется.

Чтобы повторить мои первоначальные опасения, автор порта заявляет следующее об алгоритме C5.0:

Another drawback with See5Sam [C5.0] is the impossibility to have more than one application tree at the same time. An application is read from files each time the executable is run and is stored in global variables here and there.

Я обновлю свой ответ, как только у меня будет время посмотреть исходный код.

Update

Выглядит неплохо, вот интерфейс 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);
}

Я бы сказал, что это лучшая альтернатива, которую я нашел до сих пор.

1

что он организован не как C API, а как C программа. Набор данных подается, затем он запускает алгоритм и возвращает вам некоторые описания правил.

Я думаю, что путь, который вы должны выбрать, зависит от того:

merely want a C++ interface for supplying data and retrieving rules from the existing engine, or...

want a C++ implementation that you can tinker with in order to tweak the algorithm to your own ends

Если вам нужно (1), то вы могли бы просто порождать программу как процесс, передавать ее как строки и воспринимать как строки. Это, вероятно, будет самым простым и наиболее перспективным способом разработки «оболочки», и тогда вам нужно будет только разработать классы C ++ для представления входных данных и моделирования результатов правила (или сопоставления существующих классов с этими абстракциями).

Но если вы хотите (2) ... тогда я бы предложил попробовать любые хаки, которые вы имеете в виду, поверх существующего кода на C или Java - в зависимости от того, что вам удобнее. Таким образом, вы узнаете код, и если у вас появятся какие-либо улучшения, вы сможете сообщить их автору. Если вы строите отношения на более длительный срок, то, возможно, вы могли бы сотрудничать и медленно переносить кодовую базу C на C ++, по одному аспекту за раз, для которого был разработан язык.

Думаю, я просто думаю «Когда в Риме» Философия обычно работает лучше, чем Port-In-One-Go, особенно с самого начала.

RESPONSE TO UPDATE: Изоляция процесса решает проблему глобальной переменной. Что касается производительности и размера набора данных, у вас есть столько же ядер / процессоров и памяти, сколько у вас есть. Независимо от того, используете ли вы процессы или потоки, обычно это не проблема, когда вы говорите о вопросах масштаба на этом уровне. Накладные расходы, с которыми вы сталкиваетесь,сортировочный это слишком дорого

Докажите, что сортировка является узким местом, и в какой степени ... и вы можете обосновать, почему процесс является проблемой для потока. Но могут быть небольшие изменения в существующем коде, чтобы сделать маршаллинг дешевле, который не требует переписывания.

Да, самая сложная часть с несколькими процессами - это IPC, потому что нам нужно загрузить классификатор из файла, оставить процесс открытым и передать его экземпляры данных из основного процесса. Кроме того, идея защиты вашего приложения от сбоев в случае сбоя одного из процессов классификатора, безусловно, хороша! Я немного поиграюсь с этим и посмотрю, смогу ли я запустить несколько экземпляров одновременно. Kiril
Правильно, из того, что я могу сказать, это больше о C-программе, чем о C API. Проблема заключается в том, что мне приходится классифицировать несколько экземпляров данных в режиме реального времени, поэтому не очень эффективно и не быстро запускать новый процесс для каждого экземпляра данных, который я должен классифицировать. Наконец, я не могу дождаться, чтобы собрать вместе экземпляры данных, или, в лучшем случае, я могу собрать около 300 экземпляров данных в секунду (да, возможно, все еще не очень эффективно запускать / останавливать 10 процессов каждую секунду). Обратите внимание, что я использую 10-кратную перекрестную проверку, поэтому у меня есть 10 классификаторов для оценки при прогнозировании. Kiril
Да, знаете, многие современные браузеры, такие как Chrome, создают процесс на вкладке. То, как ОС обрабатывает вещи, она разделяет кодовые страницы в памяти для общих процессов одного и того же исполняемого образа ... вы можете быть удивлены тем, что она может осуществить. Делатьsimple tests и проверить работоспособностьbefore assumingи даже тогда ... когда вы обнаружите узкое место, вы можете найти нужную настройку, намного проще, чем переписать! Возможно, простая и в целом полезная восходящая функция для базы кода C может помочь устранить любой пробел, который вы найдете.
У меня есть ощущение, что я остался с вариантом 2, несмотря на тот факт, что мне не особенно важно переделывать алгоритм или модифицировать его. Kiril

Похожие вопросы