Random Forest Regression with sparse data in Python

Question

I am working on a Random Forest regression model to predict housing prices. I have about 500k rows of data with the following information:

1.House area in square meters.

2.Number of rooms.

3.City.

4.Street.

5.Floor.

6.The transaction date.

7.Type of house (single house, apartment building etc.)

8.The amount paid for the house.

I am planning on making a different model for each city, but I'm having trouble in representing the street name. I was thinking on using One Hot Encoder to represent the street name but some cities have over 1000 streets and that would give me over 1000 variables with moslty zero values.

I have read about sparse representation but I don't know how to use it in practice.

Let's say I already have a sparse representation of my data, how do I feed it to the Random Forest? Does the Random Forest Regressor from the sklearn library in Python support sparse data? If not, then is there another way to go about using Random Forest with sparse data in Python?

Answer 1

This is a variation on a FAQ (Frequently Asked Question) here similar posts, but so far no really good answers (as far as I can see, If you disagree please guide us to the good answers!) It seems that tree models like forests have problems with high-cardinality nominal variables, so this is an area where we can expect huge differences between implementations, so try/compare different implementations!

One paper/blog that seems to take this serious, in particular, they compare H2o and scikit-learn, and prefers the former. H20 do not use one-hot encoding, which they identify as a problem here. So some words about categorical encoding. Numerical encodings, like one-hot (better known as dummys), come from linear models. In linear models, a nominal (categorical) variable with $k$ levels is represented as a $k-1$-dimensional (assuming an intercept in the model) linear subspace. This linear subspace can be represented in many different ways, corresponding to a choice of basis.

For linear models and methods the choice of a basis is just a convenience, results with any of them are equivalent. But when using non-linear methods like trees, forests, this is no longer true. In particular, when using one-hot encoding, you are only searching for splits on single levels, which might be highly inefficient, especially when there is very many levels. Some kind of hierarchical encoding might be much better. There must be a huge scope for work here! You could look throug many-categories for some ideas, but most posts there is about linear models. You could try the idea in Strange encoding for categorical features. Also remember that with random forests, there is no need to use the same predictors/encodings for each tree search, you could, as an idea, use random projections, but different ones for each tree search. But if there is existing implementations with such ideas, I do not know.

Some other relevant and interesting links/papers I found is one-hot-encoding-is-making-your-tree-based-ensembles-worse-heres-why, Random Forests, Decision Trees, and Categorical Predictors: The “Absent Levels” Problem, a stored google scholar search.

Answer 2

There are 2 ways to approach this problem:

1. Convert each categorical features to several binary indicators, a process known as "one-hot encoding"
2. Apply a transformation known variously as "target encoding" or "impact coding" that replaces the categorical feature with a numerical one.

You should be able to use any of those terms to get you started in your search. The target encoding method is likely to be the most useful here; look up the library "category_encoders" for a Python implementation, and "vtreat" for R.

Answer 3

This is meant as a follow-on to the answer of kjetil b halvorsen, showing the use of random projection methods and random forests applied to housing data from here

There are several CART ensembles that use random projections for in their regressions:

• Extreme Forests (cran link)
• Uniform Random forests (cran link)

There are several that are for classification:

• Oblique random forests (cran link)
• random Ferns (cran link)

First I preprocess the data:

#read in the data
df <- fread(fname) %>% setDF()

#set columns of interest
x <- 1:ncol(df)
y <- 3
bad <- c(1,2,18,19)

x <- x[-c(y,bad)]

#split into train/test
split_idx <- sample(x = 1:nrow(df), 
                    size = floor(nrow(df)/4) )

x_train <- df[-split_idx,x]
y_train <- df[-split_idx,y]

x_test  <- df[split_idx,x]
y_test  <- df[split_idx,y]

The goal is to use a method other than the classic random forest, so we will first use a classic random forest to compare/contrast.

Here is the code for a basic random forest: require(randomForest) est_rf <- randomForest(x=x_train, y=y_train, ntree=100, nodesize = 5)

Here is the benchmark of it:

require(bench)
bnch_rf <- bench::mark(
  est_rf <- randomForest(x=x_train, 
                         y=y_train,
                         ntree=100,
                         nodesize = 5)
)

print(bnch_rf)[2:13]

Here is the result of the random random forest:

Call:
 randomForest(x = x_train, y = y_train, ntree = 100, nodesize = 5) 
               Type of random forest: regression
                     Number of trees: 100
No. of variables tried at each split: 5

          Mean of squared residuals: 28830947769
                    % Var explained: 79.01

Here is its benchmark:

# A tibble: 1 x 12
     min  median `itr/sec` mem_alloc `gc/sec` n_itr  n_gc total_time result  memory     time   gc     
  <bch:> <bch:t>     <dbl> <bch:byt>    <dbl> <int> <dbl>   <bch:tm> <list>  <list>     <list> <list> 
1  25.7s   25.7s    0.0390     344MB    0.117     1     3      25.7s <rndmF~ <Rprofmem~ <bch:~ <tibbl~

When I read this I see the 25.7s to compute and the 344MB of memory.

Here is the code for an extremely randomized trees (extraTrees)

bnch_xt <- bench::mark(
  est_xt <- extraTrees(x=x_train, 
                       y=y_train,
                       ntree=100, 
                       nodesize = 5)
)

yhat <- predict(est_xt, x_test)

err <- mse(y_test, yhat)
print(err)

print(bnch_xt)[2:13]

Here is the result for it:

> print(err)
[1] 28595478516

# A tibble: 1 x 12
     min  median `itr/sec` mem_alloc `gc/sec` n_itr  n_gc total_time result  memory     time   gc     
  <bch:> <bch:t>     <dbl> <bch:byt>    <dbl> <int> <dbl>   <bch:tm> <list>  <list>     <list> <list> 
1  1.77s   1.77s     0.564    4.03MB        0     1     0      1.77s <extra~ <Rprofmem~ <bch:~ <tibbl~

From these I infer that the errors are within 0.8% of each other, so they are compatible, and that the extraTrees execute about 14.5x faster (no shock, RF is a dinosaur) and and using about 85x less memory.

Here is the uniform random forests code:

bnch_ruf <- bench::mark(
  est_ruf <- randomUniformForest(X=x_train, 
                                 Y=y_train,
                                 ntree=100,
                                 nodesize = 5)
)

summary(est_ruf)

print(bnch_ruf)[2:13]

Here is the uniform random forests results:

> summary(est_ruf)

Global Variable importance:
       variables        score percent percent.importance
1          grade 1.543907e+14  100.00                 21
2    sqft_living 1.324927e+14   85.82                 18
3  sqft_living15 7.193851e+13   46.60                 10
4       yr_built 6.971531e+13   45.16                 10
5        zipcode 4.962832e+13   32.14                  7
6     sqft_above 4.656379e+13   30.16                  6
7           view 4.549295e+13   29.47                  6
8     waterfront 3.483347e+13   22.56                  5
9      bathrooms 3.424015e+13   22.18                  5
10 sqft_basement 2.260674e+13   14.64                  3
11     condition 1.922995e+13   12.46                  3
12    sqft_lot15 1.279410e+13    8.29                  2
13        floors 1.052994e+13    6.82                  1
14  yr_renovated 8.759744e+12    5.67                  1
15      bedrooms 8.282042e+12    5.36                  1
16      sqft_lot 8.018249e+12    5.19                  1

Average tree size (number of nodes) summary:  
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
   7947    8061    8103    8104    8143    8267 

Average Leaf nodes (number of terminal nodes) summary:  
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
   3974    4031    4052    4052    4072    4134 

Leaf nodes size (number of observations per leaf node) summary:  
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
    1.0     1.0     3.0     2.8     4.0    61.0 

Average tree depth : 13 

Theoretical (balanced) tree depth : 14 

Here is the benchmark for it:

# A tibble: 1 x 12
     min  median `itr/sec` mem_alloc `gc/sec` n_itr  n_gc total_time result  memory     time   gc     
  <bch:> <bch:t>     <dbl> <bch:byt>    <dbl> <int> <dbl>   <bch:tm> <list>  <list>     <list> <list> 
1  39.9s   39.9s    0.0251    2.07GB    0.426     1    17      39.9s <rndmU~ <Rprofmem~ <bch:~ <tibbl~

It was slower, and fatter, but the summary suggests it did more baked-in analysis on variable importance.