Existem bibliotecas disponíveis para métodos do tipo CART usando preditores e respostas esparsas?

Estou trabalhando com alguns conjuntos de dados grandes usando o pacote gbm em R. Tanto minha matriz preditora quanto meu vetor de resposta são muito escassos (ou seja, a maioria das entradas é zero). Eu esperava construir árvores de decisão usando um algoritmo que aproveitasse essa escassez, como foi feito aqui ). Nesse artigo, como na minha situação, a maioria dos itens possui apenas alguns dos muitos recursos possíveis; portanto, eles foram capazes de evitar muita computação desperdiçada assumindo que seus itens não possuíam um determinado recurso, a menos que os dados dissessem explicitamente o contrário. Minha esperança é que eu possa obter uma aceleração semelhante usando esse tipo de algoritmo (e, em seguida, envolvendo um algoritmo de reforço em torno dele para melhorar minha precisão preditiva).

Como eles não pareciam publicar seu código, fiquei pensando se havia algum pacote ou biblioteca de código aberto (em qualquer idioma) otimizados para esse caso. Idealmente, eu gostaria de algo que pudesse levar uma matriz esparsa diretamente do Matrixpacote de R , mas eu pegarei o que conseguir.

Eu olhei em volta e parece que esse tipo de coisa deveria estar por aí:

• Os químicos parecem se deparar bastante com essa questão (o artigo que eu listei acima foi sobre aprender a encontrar novos compostos de drogas), mas as implementações que eu pude encontrar eram proprietárias ou altamente especializadas em análises químicas. É possível que um deles possa ser re-proposto, no entanto.

• A classificação de documentos também parece ser uma área em que é útil aprender com espaços esparsos de recursos (a maioria dos documentos não contém muitas palavras). Por exemplo, há uma referência oblíqua a uma implementação esparsa do C4.5 (um algoritmo semelhante ao CART) neste documento , mas nenhum código.

• De acordo com a lista de discussão , o WEKA pode aceitar dados esparsos, mas, diferentemente do método descrito no artigo acima, o WEKA não é otimizado para realmente tirar proveito dele em termos de evitar ciclos de CPU desperdiçados.

Desde já, obrigado!

Eu gostaria de ver uma referência de sua implementação esparsa em relação às implementações modernas do CART usadas nas RF. Esse artigo é bastante antigo em termos de avanços nessa área e eu ficaria surpreso se ele ainda fornecesse uma velocidade significativa.

Parte do motivo é que o uso de um algoritmo de classificação inteligente como o Quicksort na pesquisa dividida pode fornecer desempenho próximo de O (n) para recursos quase constantes (incluindo os esparsos). Implementações rápidas também rastreiam quando um recurso se torna constante dentro de um ramo de uma árvore e não deve mais ser examinado. Representações de recursos densos fornecem pesquisas rápidas de maneira amigável ao cache da CPU, para que você precise de uma representação esparsa realmente inteligente para vencer nos ciclos da CPU.

Isso é discutido aqui , aqui , aqui .

Na verdade, implementei uma representação de dados esparsos em um ponto do pacote CloudForest, mas achei que era mais lento que uma representação densa dos dados e o abandonei, apesar de fornecer algumas vantagens de memória.

Minha recomendação seria tentar o scikit learn ou o cloudforest construído para impulsionar coisas e ver se é rápido o suficiente. Ambos podem ser estendidos com critérios de aumento personalizados, se você quiser fazer algo fora do padrão. (Na verdade, eu escrevi a floresta na nuvem originalmente para trabalhar com conjuntos de dados genéticos grandes e altamente dimensionais, muito parecidos com o que você está descrevendo).

Provavelmente, existe uma pequena chance de qualquer código que tire proveito disso - você prefere escrever algo por conta própria.
No entanto, a outra opção é transformar seus dados para reduzir o tamanho dos dados, removendo informações redundantes. É difícil dizer como, sem as informações sobre seus dados, mas talvez você possa mesclar alguns recursos que você sabe que não se sobrepõem, partes do PCA ou alterar a representação de alguns descritores? Além disso, se você diz que sua resposta também é esparsa, talvez seja razoável reduzir a amostra de objetos com 0 em resposta?

Você já viu o caretpacote em R? Ele fornece uma interface que facilita o uso de uma variedade de modelos, incluindo alguns para particionamento recursivo, como rpart, ctreee ctree2.