Speed up computation
Bypass memory limitations
Quite easy for independent simulations
Not so simple for non-independent simulations
Using for
Data Mining Competitions
Case Studies
Why Data Mining Competitions?
Why R?
Jonathan Lee, University of Western Ontario
GTA R Users Group
November 25, 2011
Ryerson University
Additional Resources
2007
2009
2008
October 2, 2007
Ready-to-use data
Structured goal
No accountability, no stress
Recognition and prizes ($$)
Publication opportunity
Fun!
So Where Are They?
Great for You
A Bit of History
Low-cost way to get innovative solutions
Crowd sourcing
Ownership of solution
Great for Companies
Benefits
open source
cross-platform
powerful
de-facto standard
Prezi (this presentation software)
http://prezi.com
R-bloggers
http://www.r-bloggers.com
Kaggle blog: No Free Hunch
http://blog.kaggle.com/
R Package Recommendation Engine
Tourism Forecasting
HIV Viral Load Prediction
The Usual Suspects
There's a package for that
Isn't (insert language here) Faster?
Run-time? Perhaps.
Development time? Probably not!
Packages to note: compiler, Rcpp
The Prize
Not the first data mining competition, but probably the most well-known.
2006
2010
Netflix is an online movie rental service
Can we predict a Netflix user's rating for a movie given previous movie rating data?
The Problem
The Players
The Journey
The Data
The Goal
Data Mining
Competitions
Competition
Platforms
Individual
Competitions
An incomplete list...
Do better than Netflix's existing system, Cinematch, by at least 10%
Cinematch uses simple linear models with data conditioning
Grand prize: $1 million USD
Anyone could join
Computer scientists, statisticians, programmers etc.
51051 contestants on 41305 teams from 186 countries.
Training Set
(~100 million entries)
Quiz set (~1 million entries)
Test set (~1 million entries)
Model tested on quiz set to determine leaderboard ranking
Competition deadline set once 10% improvement is reached
At end of competition, models with at least 10% improvement are tested on test set.
Best performing model on test set is declared the winner.
All data including answers are provided
Models are fit onto this data
There are so many packages that exist for R
Impossible to know all of them -- so which ones should one invest time in learning?
Cinematch for R
The Problem
Any 3 books from the UseR! book list (postage included)
Winner is determined by highest AUC value on test set
The Prize
The Data
Voluntary sample of 52 R users
~100,000 rows of data for 1865 packages
Each row contains metadata of package and whether or not a user has that package installed.
PackageName The name of current R package
DependencyCount Number of other packages that have it as a dependency
SuggestionCount Number of other packages that suggest it
ViewsIncluding Number of views that include it
CorePackage Whether or not it is a core package (binary)
RecommendedPackage Whether or not it is a recommended package (binary)
Maintainer Name and e-mail of package maintainer
PackagesMaintaining How many other packages the maintainer maintains
Training set (2/3)
Test set (1/3)
Add in automatic stepwise model selection...
AUC on test set: 0.9453
A better model
Synthesize better predictor variables
Add a little bit of intuition
AUC: 0.9682
An even better model
A winning model
AUC: Area Under the (ROC) Curve
For a binary classification problem, we can get a confusion matrix.
Receiver Operator Characteristic (ROC) space is defined as the True Positive Rate vs the False Positive Rate.
Our predicted values are not binary, but rather a probability between 0 and 1.
By evaluating the ROC at every classification threshold, we get an ROC curve.
Positive
Negative
Positive
Negative
True Positive
False Positive
True Negative
False Negative
Actual
Predicted
## Fit model on training data
logit.fit <- glm(Installed ~ (LogDependencyCount +
LogSuggestionCount +
LogImportCount +
ViewsIncluding)^2 +
factor(User) -
LogSuggestionCount:ViewsIncluding -
LogImportCount:ViewsIncluding,
data = train.data,
family = binomial(link = 'logit'))
#### Predicting the test data
logit.predict <- predict.glm(logit.fit, newdata=test.data, type='response')
If a package is installed, assume all dependencies and imports are installed
Assume all core packages are installed
Logistic regression (stats package) on predictor variables with some variable transformation
AUC on test set: 0.8178
A simple model
## Fit the model to the training data
logit.fit <- glm(Installed ~ LogDependencyCount +
LogSuggestionCount +
LogImportCount +
LogViewsIncluding +
LogPackagesMaintaining +
CorePackage +
RecommendedPackage +
factor(User),
data = train.data,
family = binomial(link = 'logit'))
## Use model to predict on the test set
logit.predict <- predict.glm(logit.fit,newdata=test.data,type='response')
Jonathan Lee
E-mail: jlee253@uwo.ca
Website: http://www.stats.uwo.ca/gradwebs/jlee/
This presentation and slides will be made available on my blog: http://www.compmath.com
My Contact
from
IJCNN Social Network Challenge
Predicting edges in an online social network
If you and I are both connected to Bob, what is the probability (p) that I am connected to you?
The Problem
Free registration for two to the IJCNN 2011 Conference and chance to present your solution. ($950 value)
Winner is determined by highest AUC value on test set
The Prize
The Data
1,133,547 nodes (users)
7,246,943 edges (contacts)
No additional covariates given
What social network generates this type of graph?
Directed graph
0.1 % used as test set
A winning model
Number of mutual friends
p=1 if within two degrees of separation
p=0 otherwise
AUC on test set: 0.7529
Two Degrees of Separation
Inbound nodes
1,133,518
Inbound and Outbound nodes
37,689
Outbound nodes
29
for (i in 1:test.size) {
a <- test$V1[i]
b <- test$V2[i]
# Get all nodes that connect to a
a.list <- c(train$V1[which(train$V2==a)],train$V2[which(train$V1==a)])
# Get all nodes that connect to b
b.list <- c(train$V1[which(train$V2==b)],train$V2[which(train$V1==b)])
# Find number of mutual nodes
mutual[i] <- sum(a.list %in% b.list)
}
Can't feasibly find 3+ degrees of separation
Let's put this into a graph (igraph package) and find the degrees of separation
Inverse function of degrees of separation?
AUC on test set: 0.832
n Degrees of Separation
library(igraph)
edges <- matrix(c(train$V1,train$V2),ncol=2,byrow=FALSE)
sngraph <- graph.edgelist(edges,directed=TRUE)
get.path.lengths <- function(v1,v2,graph) length(get.shortest.paths(sngraph,v1,v2,mode="all")[[1]])-1
path.lengths <- mapply(get.path.lengths,test$V1,test$V2,MoreArgs=list(graph=sngraph))
Having a graph opens up a lot of possible covariates
After logistic regression...
AUC on test set: 0.8704
More covariates
Number of friends
Shortest path
Number of shortest paths etc.
Realized the dataset came from
De-anonymized the users (not an easy task!)
Recreated the missing edges (60%)
Used randomForests on standard social network features to fill in the rest
So why not 100% accuracy?
Social networks evolve over time.
AUC of 0.9812!
How did they do it?
Going Beyond the Data
INFORMS 2011
The Heritage Health Prize
Predict the number of days a patient will spend in the hospital in the next year given historical claims data.
$3M grand prize + $240k progress
Ends April 2013
Big Data
Netflix data - a matrix of about 480,000 members' ratings for about 18,000 movies) was about 65 GB!
Matrix package using sparseMatrix( ) function efficiently stores the data in ~800 MB
irlba package can be used to efficiently do SVD and PCA for large sparse matricies
Data Visualization
Machine Learning
ahaz
arules
BayesTree
Boruta
BPHO
caret
class
CORElearn
CoxBoost
Cubist
e1071
earth
elasticnet
Model Evaluation
Most packages have built in model evaluation tools
ROCR: powerful and easy-to-use package for visualizing classifier performance
How can we collaborate?
Code hosting (with version control)
Github http://www.github.com
SourceForge http://www.sourceforge.net
R-forge http://r-forge.r-project.org
RGoogleDocs package
Data Mining is a Team Sport
The Elements of Statistical Learning
http://www-stat.stanford.edu/~tibs/ElemStatLearn/
Stanford's Machine Learning Course
http://www.ml-class.org
Data Mining and
Machine Learning
require(tm)
require(wordcloud)
data(crude)
crude <- tm_map(crude, removePunctuation)
crude <- tm_map(crude, function(x)removeWords(x,stopwords()))
tdm <- TermDocumentMatrix(crude)
v <- sort(rowSums(as.matrix(tdm)),decreasing=TRUE)
d <- data.frame(word = names(v),freq=v)
wordcloud(d$word,d$freq)
wordcloud
Some examples from R graph gallery: http://addictedtor.free.fr/graphiques/
anaglyph
require(anaglyph)
attach(mtcars)
anaglyph.plot(x=wt,y=mpg,z=disp,
main="Weight vs Miles Per Gallon vs Displacement",
xlab="Weight (lb/1000lb)",
ylab="Miles/US Gallon")
by Ian Fellows
by Jonathan Lee
RnavGraph
by Adrian Waddell
lattice
require(lattice)
histogram( ~ height | voice.part, data = singer,
xlab = "Height (inches)", type = "density",
panel = function(x, ...) {
panel.histogram(x, ...)
panel.mathdensity(dmath = dnorm, col = "black",
args = list(mean=mean(x),sd=sd(x)))
} )
by Deepayan Sarkar
ggplot2
require(ggplot2)
ggplot(diamonds, aes(depth, fill = cut))
+ geom_density(alpha = 0.2)
+ xlim(55, 70)
by Hadley Wickham
rgl
by Daniel Adler and Duncan Murdoch
Example: Netflix
Parallel R
Rmpi
snow
multicore
parallel (default in version 2.14)
Commercial software
built on top of R
Optimized for Multi-processor
workstations
Multi-threaded Math libraries
Terabyte file structures and
optimized algorithms for "Big Data"
Free for academic users
Revolution R
More info: http://www.revolutionanalytics.com/products/enterprise-big-data.php
library(caret)
model.1 <- rfe(hiv.412[,c(5:617)], as.factor(hiv.412[,618]),
sizes = c(1:10, 15, 30, 60, 90, 120, 150, 200, 250, 300, 350),
rfeControl = rfeControl(functions = rfFuncs , method="cv"))
model.1.prediction <- predict(model.1$fit, hiv.692)
Winning Algorithm
library(RandomForest)
fin.train.1e.5050 <- randomForest(as.factor(Resp) ~ VL.t0 + rt184 + CD4.t0 + rt215 +
rt98 + rt225 + rt35 + rt151 + rt207 + rt227 + pr12 + pr70 +
rt101 + pr71 + rt69 + rt75 + rt187 + rt203 + rt41 + pr60 +
pr20 + rt43 + rt179 + pr82 + pr46 + pr90 + rt31 + pr30 +
pr10 + rt44 + pr58 + rt121 + pr73 + rt195 + pr63 + rt109 +
pr54 + rt173 + pr88 + rt205 + rt190 + rt77 + pr13 + rt115 +
rt106 + pr32 + pr14 + rt170 + rt4 + pr92 + pr35,
na.action=na.omit, data=yellow.5050, mtry=15)
The Problem
Single Hidden Layer NN
Netflix Prize contest announced.
October 8, 2007
Cinematch performance surpassed.
October 15, 2007
1% improvement reached.
November 13, 2007
BellKor awarded $50,000 progress prize 8.43% improvement
Description of algorithm published
December 10, 2008
BellKor in Big Chaos awarded $50,000 progress prize
9.44% improvement
Description of algorithm published
June 26, 2009
BellKor's Pragmatic Chaos reaches 10.05% improvement.
"Last call" for final submissions.
July 27, 2009
BellKor's Pragmatic Chaos wins grand prize
($1,000,000)
September 21, 2009
Accuracy, error rate, true positive rate, false positive rate, true negative rate, false negative rate, sensitivity, specificity, recall, positive predictive value, negative predictive value, precision, fallout, miss, phi correlation coefficient, Matthews correlation coefficient, mutual information, chi square statistic, odds ratio, lift value, precision/recall F measure, ROC convex hull, area under the ROC curve, precision/recall break-even point, calibration error, mean cross-entropy, root mean squared error, SAR measure, expected cost, explicit cost.
http://rocr.bioinf.mpi-sb.mpg.de/
ROC curves, precision/recall plots, lift charts, cost curves, custom curves by freely selecting one performance measure for the x axis and one for the y axis, handling of data from cross-validation or bootstrapping, curve averaging (vertically, horizontally, or by threshold), standard error bars, box plots, curves that are color-coded by cutoff, printing threshold values on the curve, tight integration with Rs plotting facilities (making it easy to adjust plots or to combine multiple plots), fully customizable, easy to use (only 3 commands).
Supported measures
Features
Check out the MachineLearning Task View on CRAN
ElemStatLearn
gafit
GAMBoost
gbm
glmnet
glmpath
grplasso
hda
igraph
ipred
kernlab
klaR
party
penalized
penalizedSVM
predbayescor
quantregForest
randomForest
randomSurvivalForest
rda
rdetools
REEMtree
relaxo
rgenoud
lars
lasso2
lda
LiblineaR
LogicForest
LogicReg
ltr
mboost
mvpart
ncvreg
nnet
pamr
rgp
rminer
ROCR
rpart
RSNNS
RWeka
sda
SDDA
svmpath
tgp
tree
TWIX
varSelRF
http://cran.r-project.org/web/views/MachineLearning.html
http://cran.r-project.org/web/views/HighPerformanceComputing.html
Max Lin's 2nd place solution: Ensemble Learning with 4 classifiers
Source: https://github.com/m4xl1n/r_recommendation_system
Take training data and create an out-of-sample test set
1
Training Data (80%)
Test (10%)
Test (10%)
2
Train classifiers with training data
3
Use classifiers to predict test data
4
Fit ensemble model using logistic regression on test data (ROCR)
x 10-folds
10
=0.9833
logistic regression (stats)
latent factor model (ltr)
latent Dirichlet allocation on topic (lda)
latent Dirichlet allocation on task view (lda)
logistic regression
(stats)
+ intuition
logistic regression (stats)
latent factor model (ltr)
latent Dirichlet allocation on topic (lda)
latent Dirichlet allocation on task view (lda)
AUC
Hidden Layer
Input Layer
Output Layer
The Problem
Predict stock price movements at 5-minute intervals
Useful for high-frequency traders
Performance measured by AUC
The Data
Time series with 609 blind explanatory variables for an unknown stock
stock prices
sectoral data
economic data
experts' predictions
indexes
Training set: 5922 observations taken at 5-minute intervals.
Test set: 2539 observations taken at 5-minute intervals.
V74CA0
V74HA1
V74CD12
V74LA13
V88CA1
V88H12A12
Logisitic Regression
Feature selection done to select top two significant variables at lag 12
Further significance noticed at lag 1
2 variables * 4 prices * 4 lags = 32 covariates
V74 and V88
Each variable has 4 prices: Open, High, Low, Last
Take lag 0, 1, 12, 13
Model Selection
Manual model selection results in logistic regression model of the form...
Target ~ V74LASTAdv0
+V74HIGHAdv1
+V74LASTAdv12
+V74LASTAdv13
+V88LASTAdv1
+V88HIGHAdv12
= 0.9908
Artificial Neural Network
nnet package to fit a feed-forward neural network with a single hidden layer
Using the covariates from the previous logisitic regression model, we get...
AUC
= 0.9898
AUC
Missing Data
Many features had missing data
Solutions?
Impute it
impute package (i.e. knn.impute)
Ignore it
Remove it
I liked , will I like ?
Cole Harris (Team DejaVu)'s Winning Solution
True Crowdsourcing
Predict the likelihood that an HIV patient's infection will become less severe, given a small dataset and limited clinical information.
Chris Raimondi
caret package for recursive feature elimination - rfe( )
RandomForest to fit model
by Arvind Narayanan, Elaine Shi, Ben Rubinstein, and Yong J Kil
Full description: http://blog.kaggle.com/2011/01/15/how-we-did-it-the-winners-of-the-ijcnn-social-network-challenge/
Predicting tourism related time series
Miscellaneous