Monotonicity Check

This code is an improvement to that used in the monotonicity violations graph and monotone relabeling algorithms I’ve used before.  It uses a sort operation to begin with according to the sum of the x values.  We know we can’t have x_i ≥ x_{i+1} so only need to check if x_i ≤ x_j and y_i > y_j for monotonicity violations, the upshot of which is we just need n(n-1)/2 comparisons rather than n^2, i.e. it should be approximately half.

To give an idea of the approximate improvement, the following gives the elapsed time from <system.time> for a 7-variate data set:

#data            new         old

100         4.692         8.755

500       113.535       220.359

1000    454.449     867.285

The speed scales at about the same factor (x^2) but is consistently close to twice as fast (as you would expect).  The dataset I used was a Lipschitz monotonised version of the Abalone dataset.  This has 4177 and is a bit troublesome so such a time-saving can be the difference between having to wait the whole day or not being able to do it at all!

R-implementation

## use mon.check4(yourdata) to check for monotonicity
## output is the number of monotonicity violations
# partial order function
parto3<-function(x,y){
as.numeric(sum(as.numeric(x[1:n]<=y[1:n]))==n)
}
# monotonicity check function
mon.check4<- function(x) {
n<-ncol(x)-1
violations <- 0
# add ordering column and fill with sum of x1+x2+...+xn
x <- cbind(x,0)
for(i in 1:nrow(x)) x[i,ncol(x)]<-sum(x[i,1:n])
# reorder
x <- x[order(x[,ncol(x)]),]
# check monotonicity
for(i in 1:nrow(x))
for(j in i:nrow(x))
if(  parto3(x[i,],x[j,])&(x[i,n]>x[j,n])==1 ) {
violations <- violations+1}
# return the total number of violations
violations
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s