6
$\begingroup$

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:

  1. 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.
  2. 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[1]

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.

$\endgroup$
  • 1
    $\begingroup$ It is unclear (a) what you mean by "unrolling" the data, (b) what you mean by "operating ... directly," and (c) why you are concerned about memory usage with such a small dataset. Could you please edit this question to clarify these things? $\endgroup$ – whuber May 21 '14 at 19:22
  • $\begingroup$ I edited the post, is there something else that's not clear? By "operating directly" I mean I want some algorithm which works with probabilities, i.e. 4 successes out of 1000 trials has a probability of 0.004 and a weight of 1000. Alternatively, I can fit unrolled binary data (1 for success, 0 for failure), but I do not wan to go down this path. $\endgroup$ – AOp May 21 '14 at 19:58
0
$\begingroup$

An possible algorithm would be to use a hash table with combinations of t1 and t2.

Sth i use frequently (and relatively simple) i using t1_t2 as a string key to a map of successes

Thus for your example you map would be sth like this:

Hash MAP:

Key        Value (successes)

1_4        4
1_8        8
2_4        4
2_8        8

.. etc...

Your map will only have each observed combination of t1,t2 only once and the value will be the total number of successes for this combination

All other combinations not present in the map can be assumed to have value(successes) zero.

This can be very efficient. In fact a single pass through the data can generate the map (in any language that supports hash maps)

Subsequently the map can be used to do any other computation on the data

UPDATE:

In order to compute a pdf from the data using the hashmap , one can do sth like the following (for illustration purposes only):

count = 0
for t1 in 1..4  # use the categories for t1 here
for t2 in 1..4  # use the categories for t2 here

count++

if 't1_t2' in map:
    pdf(t1_t2) += map.get(t1_t2)/count

end
end

UPDATE2:

if you want to store the number oftrials also in the map it canbe done like this (value will now be an array instead of single number):

Hash MAP:

Key        Value ([successes, ntrials])

1_4        [4, 1000]
1_8        [8, 999]
2_4        [4, 100]
2_8        [8, 1000]

.. etc...

$\endgroup$
  • 5
    $\begingroup$ Please avoid abbreviations like "sth". There's no 140 character limit and it's not like typing "something" will break your fingers ... but it will make your post understandable by a wider range of readers. $\endgroup$ – Glen_b -Reinstate Monica Aug 27 '14 at 9:04

Not the answer you're looking for? Browse other questions tagged or ask your own question.