I am working with the following sample dataset:
t1 t2 ntrial nsuccess 1 4 1000 4 1 8 1000 8 2 4 1000 4 2 8 1000 8
Predictors (features) t1 and t2 are categorical: t1 has categories 1 and 2, and t2 has categories 4 and 8. There is no ordering to these categories. In reality, for each combination of t1 and t2, I observe either a success, or a failure. For example, in first row (t1, t2) = (1, 4) and I recorded 4 successes from 1000 observations.
So really the dataset has 4000 rows (call this unrolled binary data), which can be compressed for the purposes of, say, Logistic Regression. Obviously unrolling this data is memory-inefficient, because unrolled data will look something like this:
t1 t2 success 1 4 1 1 4 1 1 4 1 1 4 1 1 4 0 ... 996 zeros 1 4 0 1 8 1 1 8 1 ... and so on
In this toy example, I only have 1000 observations per row, so the data can be unrolled, but in reality my dataset has 10^9 observations, and many features/predictors, so unrolling it is not really feasible.
I would like to know:
- Is there an algorithm (in say, R, or Java, etc) which can operate on this dataset directly, without me having to unroll the rows? The algorithm has to be relatively fast and simple to train and predict.
- Is there a cross-validation routine which can also work on this dataset without unrolling the rows?
Here's some starter R code which I tried so far. I fit weighted Logistic Regression (the more observations we have, the lower the variance of predicted quantity, so we have weighted regression on our hands) and Regression Tree.
library(boot) set.seed(1) input_file = 'data\\test\\test.txt' # number of cross-validation folds K = 10 input <- read.csv(input_file, header=TRUE, sep='\t', quote="", colClasses=c(rep('factor', 2), 'numeric', 'numeric')) # change the contents of the frame input$nfail = pmax(0, input$ntrial - input$nsuccess) # compute the probability of success input$prob = input$nsuccess/input$ntrial # fit the main model glm.model = glm(cbind(input$nsuccess, input$nfail) ~ input$t1 + input$t2, family = binomial, weights = input$ntrial) cost <- function(y,yhat) sum(input$ntrial*((y-yhat)^2))/sum(input$ntrial) # this produces an error, cv.glm doesn't realize rows have to be unrolled cv.glm(input, glm.model, cost = cost, K=K)$delta library(tree) control = tree.control(sum(input$ntrial)) tree.model <- tree(input$prob ~ input$t1 + input$t2, weights = input$ntrial, control = control) plot(tree.model) text(tree.model, pretty=0) # this is too big to fit in memory, R fails cv.tree(tree.model, K = K)
For example, if I want to perform 10-fold cross-validation, I have to sample each fold randomly from each of 4000 rows, either sampling a 1 or a 0 (success or failure), and then for each fold I add up the numbers of successes and failures for each particular combination of t1 and t2.