Существуют ли какие-либо библиотеки для CART-подобных методов, использующих разреженные предикторы и ответы?

11

Я работаю с некоторыми большими наборами данных, используя пакет gbm в R. И моя матрица предикторов, и мой вектор ответов довольно редки (то есть большинство записей равно нулю). Я надеялся построить деревья решений, используя алгоритм, который использует преимущества этой редкости, как это было сделано здесь ). В этой статье, как и в моей ситуации, большинство элементов имеют только несколько из множества возможных функций, поэтому они смогли избежать большого количества потраченных впустую вычислений, предполагая, что их элементам не хватает определенной функции, если в данных явно не указано иное. Я надеюсь, что смогу добиться такого же ускорения, используя этот вид алгоритма (а затем обернув его алгоритмом повышения, чтобы улучшить мою предсказательную точность).

Поскольку они, похоже, не публикуют свой код, мне было интересно, есть ли какие-либо пакеты или библиотеки с открытым исходным кодом (на любом языке), оптимизированные для этого случая. В идеале я хотел бы что-то, что могло бы взять разреженную матрицу непосредственно из Matrixпакета R , но я возьму то, что смогу получить.

Я оглянулся вокруг, и кажется, что такого рода вещи должны быть там:

  • Химики, похоже, много сталкивались с этой проблемой (статья, которую я упомянул выше, касалась обучения поиску новых лекарственных соединений), но реализации, которые я мог найти, были либо проприетарными, либо узкоспециализированными для химического анализа. Вполне возможно, что один из них может быть переопределен.

  • Классификация документов также представляется областью, в которой полезно изучение из разреженных пространств признаков (большинство документов не содержат большинство слов). Например, в этой статье есть косвенная ссылка на разреженную реализацию C4.5 (алгоритм, подобный CART) , но нет кода.

  • Согласно списку рассылки , WEKA может принимать разреженные данные, но в отличие от метода, описанного в статье, которую я упомянул выше, WEKA не оптимизирована, чтобы фактически использовать ее с точки зрения предотвращения ненужных циклов ЦП.

Заранее спасибо!

Дэвид Дж. Харрис
источник
2
Не R, но Python scikits.learn имеет растущую поддержку разреженных матриц.
Chl
@ ch1 спасибо. Похоже, они еще не добавили методы дерева. Кто-то работает над реализацией , но я не уверен, сможет ли она использовать разреженные данные. Я определенно буду помнить о редких методах SVM!
Дэвид Дж. Харрис
Когда вы говорите «CART-like», вам конкретно нужны деревья решений или какая-либо прогнозирующая модель?
Майкл МакГоуэн
@ Майкл - Я бы хотел деревья, так как я буду кормить их процедурой повышения, и они имеют высокую дисперсию.
Дэвид Дж. Харрис
2
Я не знаю моделей дерева, но glmnetи e1071::svmте, и другие поддерживают разреженные Matrixобъекты. GAMboostи GLMboost(из пакета GAMboost) может также.
Зак

Ответы:

2

Я хотел бы видеть эталон их редкой реализации по сравнению с современными реализациями CART, используемыми в RF. Эта статья довольно старая с точки зрения достижений в этой области, и я был бы удивлен, если бы она все же обеспечила значительное ускорение.

Частично причина в том, что использование умного алгоритма сортировки, такого как быстрая сортировка, при поиске с разделением может обеспечить почти 0 (n) производительность для почти постоянных объектов (включая разреженные). Быстрые реализации также отслеживают, когда объект стал постоянным в пределах ветви дерева и больше не должен проверяться. Плотные представления функций обеспечивают быстрый поиск в дружественном к кэшу процессоре, поэтому вам нужно действительно умное разреженное представление, чтобы выиграть в циклах процессора.

Это обсуждается здесь , здесь , здесь .

Я фактически реализовал разреженное представление данных в одной точке моего пакета RFF CloudForest, но обнаружил, что оно медленнее, чем плотное представление данных, и отказался от него, хотя и обеспечил некоторые преимущества памяти.

Я бы порекомендовал попробовать Scikit Learn или Cloudforest, встроенные в бустинг, и посмотреть, достаточно ли это быстро. Оба могут быть расширены с помощью пользовательских критериев повышения, если вы хотите сделать что-то нестандартное. (Я фактически написал cloudforest изначально для работы с большими, многомерными наборами генетических данных, которые очень похожи на то, что вы описываете).

Райан Бресслер
источник
1

Вероятно, у любого кода, который воспользуется этим, есть небольшой шанс - вам лучше написать что-то самостоятельно.
Однако другой вариант - преобразовать ваши данные, чтобы уменьшить размер данных, удаляя лишнюю информацию. Трудно сказать, как без информации о ваших данных, но, возможно, вы можете объединить некоторые функции, которые, как вы знаете, не пересекаются, PCA части или изменить представление некоторых дескрипторов? Кроме того, если вы говорите, что ваш ответ также невелик, возможно, имеет смысл уменьшить выборку объектов с 0 в ответе?


источник
Спасибо за ответ. Понижение частоты звучит как интересная идея. В настоящее время, я вниз взвешивая некоторые аспекты данных по другим причинам, но это может быть хорошей идеей тоже. Но почему вы говорите, что код для этого вряд ли существует? Я ссылался на статью 12 лет назад, в которой, похоже, решена та же проблема.
Дэвид Дж. Харрис
@ Дэвид Короче говоря, я чувствую, что это не имеет смысла - это проблема "неправильного вопроса". Разреженность показывает, что данные находятся в крайне неоптимальной форме, и гораздо более эффективный подход состоит в том, чтобы попытаться преобразовать их. Бумага, на которую вы ссылаетесь, является немного другой проблемой.
Боюсь, не понимаю, что ты говоришь. Преобразование формы данных - это именно то, что я хочу сделать, и, насколько я могу судить, именно это и делает эта статья. Они не хотели перечислять все функции, которые отсутствовали у каждого химического вещества, только те, которые были у него. Это имело смысл в их ситуации, потому что большинству химикатов не хватает большинства функций, как в моем случае. Таким образом, они преобразовали свои функции в разреженную матрицу, а затем напрямую применили алгоритм рекурсивного разбиения к этой разреженной матрице. Я ищу способы с открытым исходным кодом сделать то же самое с моими данными. Что мне не хватает? Спасибо
Дэвид Дж. Харрис
@ Дэвид, я думаю, что точка зрения mbq в том, что большое кодирование 1-из-n (например, веб-сайт / идентификатор клиента и т. Д.) Или список присутствующих химических веществ) часто является очень плохим представлением для обучения. Вам лучше перейти на «функции», например, для веб-сайта это может быть категоризация: магазин / новости / блог спорт / технологии и т. Д.
seanv507
1

Вы смотрели на caretпакет в R? Он предоставляет интерфейс, который облегчает использование различных моделей, в том числе для рекурсивного разделения, таких как rpart, ctreeи ctree2.

Павел
источник
Я знаком с этими пакетами / функциями, и, насколько я могу судить, ни один из них не работает с разреженными данными.
Дэвид Дж. Харрис
1
Поддержка каретки для Matrixобъектов была бы замечательной, но в настоящее время ее не существует. Все приводится к data.frame.
Зак
Вы можете попробовать написать разработчику по электронной почте и спросить его об этом. Я написал ему по электронной почте о чем-то другом, и он дал полезный ответ - max.kuhn [at] pfizer.com
Пол